Problem 488
Unbalanced Nim — F(10^18) last 9 digits via XOR digit-DP.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n) | O(n) |
|---|
| Space complexity | O(1) | O(n) |
|---|
| Approach | Flow solution | Big-integer arithmetic |
|---|
| Verdict | Optimal |
|---|
Flow source
# Project Euler 488
# Unbalanced Nim — F(10^18) last 9 digits via XOR digit-DP.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function bit_length(n0: i64) -> i32 {
let mut n: i64 = n0
let mut b: i32 = 0
while n > 0 {
b = b + 1
n = n / 2
}
if b == 0 { return 1 }
return b
}
function dp_count_sum(A: i64, B: i64, C: i64, out: ptr<i64>, MOD6: i64) -> void {
if A < 0 || B < 0 || C < 0 {
out[0] = 0
out[1] = 0
return
}
let mut maxbits: i32 = bit_length(A)
let bb: i32 = bit_length(B)
let bc: i32 = bit_length(C)
if bb > maxbits { maxbits = bb }
if bc > maxbits { maxbits = bc }
let counts: ptr<i64> = calloc(8, 8)
let sumA: ptr<i64> = calloc(8, 8)
let sumB: ptr<i64> = calloc(8, 8)
let sumC: ptr<i64> = calloc(8, 8)
let ncounts: ptr<i64> = calloc(8, 8)
let nsumA: ptr<i64> = calloc(8, 8)
let nsumB: ptr<i64> = calloc(8, 8)
let nsumC: ptr<i64> = calloc(8, 8)
if counts == null { return }
counts[7] = 1
let mut p: i32 = maxbits - 1
while p >= 0 {
let bitA: i64 = (A >> p) & 1
let bitB: i64 = (B >> p) & 1
let bitC: i64 = (C >> p) & 1
let val: i64 = (1 as i64) << p
let mut s: i32 = 0
while s < 8 {
ncounts[s] = 0
nsumA[s] = 0
nsumB[s] = 0
nsumC[s] = 0
s = s + 1
}
s = 0
while s < 8 {
let cnt: i64 = counts[s]
if cnt != 0 {
let ta: i32 = (s >> 2) & 1
let tb: i32 = (s >> 1) & 1
let tc: i32 = s & 1
let mut abit: i64 = 0
while abit <= 1 {
let mut ok_a: bool = true
if ta == 1 && abit > bitA { ok_a = false }
if ok_a {
let mut nta: i32 = 0
if ta == 1 && abit == bitA { nta = 1 }
let mut bbit: i64 = 0
while bbit <= 1 {
let mut ok_b: bool = true
if tb == 1 && bbit > bitB { ok_b = false }
if ok_b {
let mut ntb: i32 = 0
if tb == 1 && bbit == bitB { ntb = 1 }
let cbit: i64 = abit ^ bbit
let mut ok_c: bool = true
if tc == 1 && cbit > bitC { ok_c = false }
if ok_c {
let mut ntc: i32 = 0
if tc == 1 && cbit == bitC { ntc = 1 }
let nstate: i32 = (nta << 2) | (ntb << 1) | ntc
ncounts[nstate] = (ncounts[nstate] + cnt) % MOD6
let addA: i64 = (((cnt as i128) * (abit as i128) * (val as i128)) % (MOD6 as i128)) as i64
let addB: i64 = (((cnt as i128) * (bbit as i128) * (val as i128)) % (MOD6 as i128)) as i64
let addC: i64 = (((cnt as i128) * (cbit as i128) * (val as i128)) % (MOD6 as i128)) as i64
nsumA[nstate] = (nsumA[nstate] + sumA[s] + addA) % MOD6
nsumB[nstate] = (nsumB[nstate] + sumB[s] + addB) % MOD6
nsumC[nstate] = (nsumC[nstate] + sumC[s] + addC) % MOD6
}
}
bbit = bbit + 1
}
}
abit = abit + 1
}
}
s = s + 1
}
s = 0
while s < 8 {
counts[s] = ncounts[s]
sumA[s] = nsumA[s]
sumB[s] = nsumB[s]
sumC[s] = nsumC[s]
s = s + 1
}
p = p - 1
}
let mut total_count: i64 = 0
let mut total_sum: i64 = 0
let mut s2: i32 = 0
while s2 < 8 {
total_count = (total_count + counts[s2]) % MOD6
total_sum = (total_sum + sumA[s2] + sumB[s2] + sumC[s2]) % MOD6
s2 = s2 + 1
}
out[0] = total_count
out[1] = total_sum
free(nsumC); free(nsumB); free(nsumA); free(ncounts)
free(sumC); free(sumB); free(sumA); free(counts)
}
function popcount8(m: i32) -> i32 {
let mut x: i32 = m
let mut c: i32 = 0
while x > 0 {
c = c + (x & 1)
x = x >> 1
}
return c
}
function main() -> i32 {
let L: i64 = 1000000000000000000
let MOD: i64 = 1000000000
let MOD6: i64 = 6000000000
let out: ptr<i64> = calloc(2, 8)
if out == null { return 1 }
let mut ordered_count: i64 = 0
let mut ordered_sum: i64 = 0
let mut mask: i32 = 0
while mask < 8 {
let mut A: i64 = L
let mut B: i64 = L
let mut C: i64 = L
if (mask & 1) != 0 { A = 1 }
if (mask & 2) != 0 { B = 1 }
if (mask & 4) != 0 { C = 1 }
dp_count_sum(A, B, C, out, MOD6)
if (popcount8(mask) & 1) == 0 {
ordered_count = (ordered_count + out[0]) % MOD6
ordered_sum = (ordered_sum + out[1]) % MOD6
} else {
ordered_count = (ordered_count - out[0] % MOD6 + MOD6) % MOD6
ordered_sum = (ordered_sum - out[1] % MOD6 + MOD6) % MOD6
}
mask = mask + 1
}
let mut diff: i64 = (ordered_sum - (3 * ordered_count) % MOD6 + MOD6) % MOD6
# divide by 6 exactly in Z/(6*10^9), result mod 10^9
let ans: i64 = (diff / 6) % MOD
printf("%lld\n", ans)
free(out)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int32_t bit_length_i64(int64_t n0);
void dp_count_sum_i64_i64_i64_ptr_i64_i64(int64_t A, int64_t B, int64_t C, int64_t* out, int64_t MOD6);
int32_t popcount8_i32(int32_t m);
int32_t main(void);
int32_t bit_length_i64(int64_t n0) {
int64_t n = n0;
int32_t b = 0;
while (n > 0) {
b = (b + 1);
n = FLOW_CHECKED_DIV((n), (2));
}
if (b == 0) {
return 1;
}
return b;
}
void dp_count_sum_i64_i64_i64_ptr_i64_i64(int64_t A, int64_t B, int64_t C, int64_t* out, int64_t MOD6) {
if (((A < 0 || B < 0) || C < 0)) {
out[0] = 0;
out[1] = 0;
return;
}
int32_t maxbits = bit_length_i64(A);
int32_t bb = bit_length_i64(B);
int32_t bc = bit_length_i64(C);
if (bb > maxbits) {
maxbits = bb;
}
if (bc > maxbits) {
maxbits = bc;
}
int64_t* counts = (int64_t*)(calloc(8, 8));
int64_t* sumA = (int64_t*)(calloc(8, 8));
int64_t* sumB = (int64_t*)(calloc(8, 8));
int64_t* sumC = (int64_t*)(calloc(8, 8));
int64_t* ncounts = (int64_t*)(calloc(8, 8));
int64_t* nsumA = (int64_t*)(calloc(8, 8));
int64_t* nsumB = (int64_t*)(calloc(8, 8));
int64_t* nsumC = (int64_t*)(calloc(8, 8));
if (counts == NULL) {
return;
}
counts[7] = 1;
int32_t p = (maxbits - 1);
while (p >= 0) {
int64_t bitA = (FLOW_CHECKED_SHR((A), (p)) & 1);
int64_t bitB = (FLOW_CHECKED_SHR((B), (p)) & 1);
int64_t bitC = (FLOW_CHECKED_SHR((C), (p)) & 1);
int64_t val = FLOW_CHECKED_SHL((((int64_t)(1))), (p));
int32_t s = 0;
while (s < 8) {
ncounts[s] = 0;
nsumA[s] = 0;
nsumB[s] = 0;
nsumC[s] = 0;
s = (s + 1);
}
s = 0;
while (s < 8) {
int64_t cnt = counts[s];
if (cnt != 0) {
int32_t ta = (FLOW_CHECKED_SHR((s), (2)) & 1);
int32_t tb = (FLOW_CHECKED_SHR((s), (1)) & 1);
int32_t tc = (s & 1);
int64_t abit = 0;
while (abit <= 1) {
bool ok_a = 1;
if ((ta == 1 && abit > bitA)) {
ok_a = 0;
}
if (ok_a) {
int32_t nta = 0;
if ((ta == 1 && abit == bitA)) {
nta = 1;
}
int64_t bbit = 0;
while (bbit <= 1) {
bool ok_b = 1;
if ((tb == 1 && bbit > bitB)) {
ok_b = 0;
}
if (ok_b) {
int32_t ntb = 0;
if ((tb == 1 && bbit == bitB)) {
ntb = 1;
}
int64_t cbit = (abit ^ bbit);
bool ok_c = 1;
if ((tc == 1 && cbit > bitC)) {
ok_c = 0;
}
if (ok_c) {
int32_t ntc = 0;
if ((tc == 1 && cbit == bitC)) {
ntc = 1;
}
int32_t nstate = ((FLOW_CHECKED_SHL((nta), (2)) | FLOW_CHECKED_SHL((ntb), (1))) | ntc);
ncounts[nstate] = FLOW_CHECKED_MOD(((ncounts[nstate] + cnt)), (MOD6));
int64_t addA = ((int64_t)(FLOW_CHECKED_MOD((((((__int128)(cnt)) * ((__int128)(abit))) * ((__int128)(val)))), (((__int128)(MOD6))))));
int64_t addB = ((int64_t)(FLOW_CHECKED_MOD((((((__int128)(cnt)) * ((__int128)(bbit))) * ((__int128)(val)))), (((__int128)(MOD6))))));
int64_t addC = ((int64_t)(FLOW_CHECKED_MOD((((((__int128)(cnt)) * ((__int128)(cbit))) * ((__int128)(val)))), (((__int128)(MOD6))))));
nsumA[nstate] = FLOW_CHECKED_MOD((((nsumA[nstate] + sumA[s]) + addA)), (MOD6));
nsumB[nstate] = FLOW_CHECKED_MOD((((nsumB[nstate] + sumB[s]) + addB)), (MOD6));
nsumC[nstate] = FLOW_CHECKED_MOD((((nsumC[nstate] + sumC[s]) + addC)), (MOD6));
}
}
bbit = (bbit + 1);
}
}
abit = (abit + 1);
}
}
s = (s + 1);
}
s = 0;
while (s < 8) {
counts[s] = ncounts[s];
sumA[s] = nsumA[s];
sumB[s] = nsumB[s];
sumC[s] = nsumC[s];
s = (s + 1);
}
p = (p - 1);
}
int64_t total_count = 0;
int64_t total_sum = 0;
int32_t s2 = 0;
while (s2 < 8) {
total_count = FLOW_CHECKED_MOD(((total_count + counts[s2])), (MOD6));
total_sum = FLOW_CHECKED_MOD(((((total_sum + sumA[s2]) + sumB[s2]) + sumC[s2])), (MOD6));
s2 = (s2 + 1);
}
out[0] = total_count;
out[1] = total_sum;
free(nsumC);
free(nsumB);
free(nsumA);
free(ncounts);
free(sumC);
free(sumB);
free(sumA);
free(counts);
}
int32_t popcount8_i32(int32_t m) {
int32_t x = m;
int32_t c = 0;
while (x > 0) {
c = (c + (x & 1));
x = FLOW_CHECKED_SHR((x), (1));
}
return c;
}
int32_t main(void) {
int64_t L = 1000000000000000000;
int64_t MOD = 1000000000;
int64_t MOD6 = 6000000000;
int64_t* out = (int64_t*)(calloc(2, 8));
if (out == NULL) {
return 1;
}
int64_t ordered_count = 0;
int64_t ordered_sum = 0;
int32_t mask = 0;
while (mask < 8) {
int64_t A = L;
int64_t B = L;
int64_t C = L;
if ((mask & 1) != 0) {
A = 1;
}
if ((mask & 2) != 0) {
B = 1;
}
if ((mask & 4) != 0) {
C = 1;
}
dp_count_sum_i64_i64_i64_ptr_i64_i64(A, B, C, out, MOD6);
if ((popcount8_i32(mask) & 1) == 0) {
ordered_count = FLOW_CHECKED_MOD(((ordered_count + out[0])), (MOD6));
ordered_sum = FLOW_CHECKED_MOD(((ordered_sum + out[1])), (MOD6));
} else {
ordered_count = FLOW_CHECKED_MOD((((ordered_count - FLOW_CHECKED_MOD((out[0]), (MOD6))) + MOD6)), (MOD6));
ordered_sum = FLOW_CHECKED_MOD((((ordered_sum - FLOW_CHECKED_MOD((out[1]), (MOD6))) + MOD6)), (MOD6));
}
mask = (mask + 1);
}
int64_t diff = FLOW_CHECKED_MOD((((ordered_sum - FLOW_CHECKED_MOD(((3 * ordered_count)), (MOD6))) + MOD6)), (MOD6));
int64_t ans = FLOW_CHECKED_MOD((FLOW_CHECKED_DIV((diff), (6))), (MOD));
printf("%lld\n", ans);
free(out);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func @bit_length(%arg0: i64) -> i32 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = arith.constant 0 : i32
%3 = llvm.mlir.constant(1 : i64) : i64
%4 = llvm.alloca %3 x i32 : (i64) -> !llvm.ptr
llvm.store %2, %4 : i32, !llvm.ptr
cf.br ^bb0
^bb0:
%5 = llvm.load %1 : !llvm.ptr -> i64
%6 = arith.constant 0 : i32
%8 = arith.extsi %6 : i32 to i64
%7 = arith.cmpi sgt, %5, %8 : i64
cf.cond_br %7, ^bb1, ^bb2
^bb1:
%9 = llvm.load %4 : !llvm.ptr -> i32
%10 = arith.constant 1 : i32
%11 = arith.addi %9, %10 : i32
llvm.store %11, %4 : i32, !llvm.ptr
%12 = llvm.load %1 : !llvm.ptr -> i64
%13 = arith.constant 2 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.divsi %12, %15 : i64
llvm.store %14, %1 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%16 = llvm.load %4 : !llvm.ptr -> i32
%17 = arith.constant 0 : i32
%18 = arith.cmpi eq, %16, %17 : i32
cf.cond_br %18, ^bb3, ^bb4
^bb3:
%19 = arith.constant 1 : i32
func.return %19 : i32
^bb4:
cf.br ^bb5
^bb5:
%20 = llvm.load %4 : !llvm.ptr -> i32
func.return %20 : i32
}
func.func @dp_count_sum(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: !llvm.ptr, %arg4: i64) -> () {
%21 = arith.constant 0 : i32
%23 = arith.extsi %21 : i32 to i64
%22 = arith.cmpi slt, %arg0, %23 : i64
%24 = scf.if %22 -> (i1) {
%25 = arith.constant true
scf.yield %25 : i1
} else {
%26 = arith.constant 0 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.cmpi slt, %arg1, %28 : i64
scf.yield %27 : i1
}
%29 = scf.if %24 -> (i1) {
%30 = arith.constant true
scf.yield %30 : i1
} else {
%31 = arith.constant 0 : i32
%33 = arith.extsi %31 : i32 to i64
%32 = arith.cmpi slt, %arg2, %33 : i64
scf.yield %32 : i1
}
cf.cond_br %29, ^bb6, ^bb7
^bb6:
%34 = arith.constant 0 : i32
%35 = arith.constant 0 : i32
%36 = arith.extsi %34 : i32 to i64
%37 = arith.extsi %35 : i32 to i64
%38 = llvm.getelementptr %arg3[%37] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %36, %38 : i64, !llvm.ptr
%39 = arith.constant 0 : i32
%40 = arith.constant 1 : i32
%41 = arith.extsi %39 : i32 to i64
%42 = arith.extsi %40 : i32 to i64
%43 = llvm.getelementptr %arg3[%42] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %41, %43 : i64, !llvm.ptr
func.return
^bb7:
cf.br ^bb8
^bb8:
%44 = func.call @bit_length(%arg0) : (i64) -> i32
%45 = llvm.mlir.constant(1 : i64) : i64
%46 = llvm.alloca %45 x i32 : (i64) -> !llvm.ptr
llvm.store %44, %46 : i32, !llvm.ptr
%47 = func.call @bit_length(%arg1) : (i64) -> i32
%48 = func.call @bit_length(%arg2) : (i64) -> i32
%49 = llvm.load %46 : !llvm.ptr -> i32
%50 = arith.cmpi sgt, %47, %49 : i32
cf.cond_br %50, ^bb9, ^bb10
^bb9:
llvm.store %47, %46 : i32, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%51 = llvm.load %46 : !llvm.ptr -> i32
%52 = arith.cmpi sgt, %48, %51 : i32
cf.cond_br %52, ^bb12, ^bb13
^bb12:
llvm.store %48, %46 : i32, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%54 = arith.constant 8 : i32
%55 = arith.constant 8 : i32
%56 = arith.extsi %54 : i32 to i64
%57 = arith.extsi %55 : i32 to i64
%53 = func.call @calloc(%56, %57) : (i64, i64) -> !llvm.ptr
%59 = arith.constant 8 : i32
%60 = arith.constant 8 : i32
%61 = arith.extsi %59 : i32 to i64
%62 = arith.extsi %60 : i32 to i64
%58 = func.call @calloc(%61, %62) : (i64, i64) -> !llvm.ptr
%64 = arith.constant 8 : i32
%65 = arith.constant 8 : i32
%66 = arith.extsi %64 : i32 to i64
%67 = arith.extsi %65 : i32 to i64
%63 = func.call @calloc(%66, %67) : (i64, i64) -> !llvm.ptr
%69 = arith.constant 8 : i32
%70 = arith.constant 8 : i32
%71 = arith.extsi %69 : i32 to i64
%72 = arith.extsi %70 : i32 to i64
%68 = func.call @calloc(%71, %72) : (i64, i64) -> !llvm.ptr
%74 = arith.constant 8 : i32
%75 = arith.constant 8 : i32
%76 = arith.extsi %74 : i32 to i64
%77 = arith.extsi %75 : i32 to i64
%73 = func.call @calloc(%76, %77) : (i64, i64) -> !llvm.ptr
%79 = arith.constant 8 : i32
%80 = arith.constant 8 : i32
%81 = arith.extsi %79 : i32 to i64
%82 = arith.extsi %80 : i32 to i64
%78 = func.call @calloc(%81, %82) : (i64, i64) -> !llvm.ptr
%84 = arith.constant 8 : i32
%85 = arith.constant 8 : i32
%86 = arith.extsi %84 : i32 to i64
%87 = arith.extsi %85 : i32 to i64
%83 = func.call @calloc(%86, %87) : (i64, i64) -> !llvm.ptr
%89 = arith.constant 8 : i32
%90 = arith.constant 8 : i32
%91 = arith.extsi %89 : i32 to i64
%92 = arith.extsi %90 : i32 to i64
%88 = func.call @calloc(%91, %92) : (i64, i64) -> !llvm.ptr
%93 = llvm.mlir.zero : !llvm.ptr
%94 = llvm.icmp "eq" %53, %93 : !llvm.ptr
cf.cond_br %94, ^bb15, ^bb16
^bb15:
func.return
^bb16:
cf.br ^bb17
^bb17:
%95 = arith.constant 1 : i32
%96 = arith.constant 7 : i32
%97 = arith.extsi %95 : i32 to i64
%98 = arith.extsi %96 : i32 to i64
%99 = llvm.getelementptr %53[%98] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %97, %99 : i64, !llvm.ptr
%100 = llvm.load %46 : !llvm.ptr -> i32
%101 = arith.constant 1 : i32
%102 = arith.subi %100, %101 : i32
%103 = llvm.mlir.constant(1 : i64) : i64
%104 = llvm.alloca %103 x i32 : (i64) -> !llvm.ptr
llvm.store %102, %104 : i32, !llvm.ptr
cf.br ^bb18
^bb18:
%105 = llvm.load %104 : !llvm.ptr -> i32
%106 = arith.constant 0 : i32
%107 = arith.cmpi sge, %105, %106 : i32
cf.cond_br %107, ^bb19, ^bb20
^bb19:
%108 = llvm.load %104 : !llvm.ptr -> i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.shrsi %arg0, %110 : i64
%111 = arith.constant 1 : i32
%113 = arith.extsi %111 : i32 to i64
%112 = arith.andi %109, %113 : i64
%114 = llvm.load %104 : !llvm.ptr -> i32
%116 = arith.extsi %114 : i32 to i64
%115 = arith.shrsi %arg1, %116 : i64
%117 = arith.constant 1 : i32
%119 = arith.extsi %117 : i32 to i64
%118 = arith.andi %115, %119 : i64
%120 = llvm.load %104 : !llvm.ptr -> i32
%122 = arith.extsi %120 : i32 to i64
%121 = arith.shrsi %arg2, %122 : i64
%123 = arith.constant 1 : i32
%125 = arith.extsi %123 : i32 to i64
%124 = arith.andi %121, %125 : i64
%126 = arith.constant 1 : i32
%127 = arith.extsi %126 : i32 to i64
%128 = llvm.load %104 : !llvm.ptr -> i32
%130 = arith.extsi %128 : i32 to i64
%129 = arith.shli %127, %130 : i64
%131 = arith.constant 0 : i32
%132 = llvm.mlir.constant(1 : i64) : i64
%133 = llvm.alloca %132 x i32 : (i64) -> !llvm.ptr
llvm.store %131, %133 : i32, !llvm.ptr
cf.br ^bb21
^bb21:
%134 = llvm.load %133 : !llvm.ptr -> i32
%135 = arith.constant 8 : i32
%136 = arith.cmpi slt, %134, %135 : i32
cf.cond_br %136, ^bb22, ^bb23
^bb22:
%137 = arith.constant 0 : i32
%138 = llvm.load %133 : !llvm.ptr -> i32
%139 = arith.extsi %137 : i32 to i64
%140 = arith.extsi %138 : i32 to i64
%141 = llvm.getelementptr %73[%140] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %139, %141 : i64, !llvm.ptr
%142 = arith.constant 0 : i32
%143 = llvm.load %133 : !llvm.ptr -> i32
%144 = arith.extsi %142 : i32 to i64
%145 = arith.extsi %143 : i32 to i64
%146 = llvm.getelementptr %78[%145] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %144, %146 : i64, !llvm.ptr
%147 = arith.constant 0 : i32
%148 = llvm.load %133 : !llvm.ptr -> i32
%149 = arith.extsi %147 : i32 to i64
%150 = arith.extsi %148 : i32 to i64
%151 = llvm.getelementptr %83[%150] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %149, %151 : i64, !llvm.ptr
%152 = arith.constant 0 : i32
%153 = llvm.load %133 : !llvm.ptr -> i32
%154 = arith.extsi %152 : i32 to i64
%155 = arith.extsi %153 : i32 to i64
%156 = llvm.getelementptr %88[%155] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %154, %156 : i64, !llvm.ptr
%157 = llvm.load %133 : !llvm.ptr -> i32
%158 = arith.constant 1 : i32
%159 = arith.addi %157, %158 : i32
llvm.store %159, %133 : i32, !llvm.ptr
cf.br ^bb21
^bb23:
%160 = arith.constant 0 : i32
llvm.store %160, %133 : i32, !llvm.ptr
cf.br ^bb24
^bb24:
%161 = llvm.load %133 : !llvm.ptr -> i32
%162 = arith.constant 8 : i32
%163 = arith.cmpi slt, %161, %162 : i32
cf.cond_br %163, ^bb25, ^bb26
^bb25:
%165 = llvm.load %133 : !llvm.ptr -> i32
%166 = arith.extsi %165 : i32 to i64
%167 = llvm.getelementptr %53[%166] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%164 = llvm.load %167 : !llvm.ptr -> i64
%168 = arith.constant 0 : i32
%170 = arith.extsi %168 : i32 to i64
%169 = arith.cmpi ne, %164, %170 : i64
cf.cond_br %169, ^bb27, ^bb28
^bb27:
%171 = llvm.load %133 : !llvm.ptr -> i32
%172 = arith.constant 2 : i32
%173 = arith.shrsi %171, %172 : i32
%174 = arith.constant 1 : i32
%175 = arith.andi %173, %174 : i32
%176 = llvm.load %133 : !llvm.ptr -> i32
%177 = arith.constant 1 : i32
%178 = arith.shrsi %176, %177 : i32
%179 = arith.constant 1 : i32
%180 = arith.andi %178, %179 : i32
%181 = llvm.load %133 : !llvm.ptr -> i32
%182 = arith.constant 1 : i32
%183 = arith.andi %181, %182 : i32
%184 = arith.constant 0 : i32
%185 = arith.extsi %184 : i32 to i64
%186 = llvm.mlir.constant(1 : i64) : i64
%187 = llvm.alloca %186 x i64 : (i64) -> !llvm.ptr
llvm.store %185, %187 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%188 = llvm.load %187 : !llvm.ptr -> i64
%189 = arith.constant 1 : i32
%191 = arith.extsi %189 : i32 to i64
%190 = arith.cmpi sle, %188, %191 : i64
cf.cond_br %190, ^bb31, ^bb32
^bb31:
%192 = arith.constant 1 : i1
%193 = llvm.mlir.constant(1 : i64) : i64
%194 = llvm.alloca %193 x i1 : (i64) -> !llvm.ptr
llvm.store %192, %194 : i1, !llvm.ptr
%195 = arith.constant 1 : i32
%196 = arith.cmpi eq, %175, %195 : i32
%197 = scf.if %196 -> (i1) {
%198 = llvm.load %187 : !llvm.ptr -> i64
%199 = arith.cmpi sgt, %198, %112 : i64
scf.yield %199 : i1
} else {
%200 = arith.constant false
scf.yield %200 : i1
}
cf.cond_br %197, ^bb33, ^bb34
^bb33:
%201 = arith.constant 0 : i1
llvm.store %201, %194 : i1, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%202 = llvm.load %194 : !llvm.ptr -> i1
cf.cond_br %202, ^bb36, ^bb37
^bb36:
%203 = arith.constant 0 : i32
%204 = llvm.mlir.constant(1 : i64) : i64
%205 = llvm.alloca %204 x i32 : (i64) -> !llvm.ptr
llvm.store %203, %205 : i32, !llvm.ptr
%206 = arith.constant 1 : i32
%207 = arith.cmpi eq, %175, %206 : i32
%208 = scf.if %207 -> (i1) {
%209 = llvm.load %187 : !llvm.ptr -> i64
%210 = arith.cmpi eq, %209, %112 : i64
scf.yield %210 : i1
} else {
%211 = arith.constant false
scf.yield %211 : i1
}
cf.cond_br %208, ^bb39, ^bb40
^bb39:
%212 = arith.constant 1 : i32
llvm.store %212, %205 : i32, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%213 = arith.constant 0 : i32
%214 = arith.extsi %213 : i32 to i64
%215 = llvm.mlir.constant(1 : i64) : i64
%216 = llvm.alloca %215 x i64 : (i64) -> !llvm.ptr
llvm.store %214, %216 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%217 = llvm.load %216 : !llvm.ptr -> i64
%218 = arith.constant 1 : i32
%220 = arith.extsi %218 : i32 to i64
%219 = arith.cmpi sle, %217, %220 : i64
cf.cond_br %219, ^bb43, ^bb44
^bb43:
%221 = arith.constant 1 : i1
%222 = llvm.mlir.constant(1 : i64) : i64
%223 = llvm.alloca %222 x i1 : (i64) -> !llvm.ptr
llvm.store %221, %223 : i1, !llvm.ptr
%224 = arith.constant 1 : i32
%225 = arith.cmpi eq, %180, %224 : i32
%226 = scf.if %225 -> (i1) {
%227 = llvm.load %216 : !llvm.ptr -> i64
%228 = arith.cmpi sgt, %227, %118 : i64
scf.yield %228 : i1
} else {
%229 = arith.constant false
scf.yield %229 : i1
}
cf.cond_br %226, ^bb45, ^bb46
^bb45:
%230 = arith.constant 0 : i1
llvm.store %230, %223 : i1, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%231 = llvm.load %223 : !llvm.ptr -> i1
cf.cond_br %231, ^bb48, ^bb49
^bb48:
%232 = arith.constant 0 : i32
%233 = llvm.mlir.constant(1 : i64) : i64
%234 = llvm.alloca %233 x i32 : (i64) -> !llvm.ptr
llvm.store %232, %234 : i32, !llvm.ptr
%235 = arith.constant 1 : i32
%236 = arith.cmpi eq, %180, %235 : i32
%237 = scf.if %236 -> (i1) {
%238 = llvm.load %216 : !llvm.ptr -> i64
%239 = arith.cmpi eq, %238, %118 : i64
scf.yield %239 : i1
} else {
%240 = arith.constant false
scf.yield %240 : i1
}
cf.cond_br %237, ^bb51, ^bb52
^bb51:
%241 = arith.constant 1 : i32
llvm.store %241, %234 : i32, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
%242 = llvm.load %187 : !llvm.ptr -> i64
%243 = llvm.load %216 : !llvm.ptr -> i64
%244 = arith.xori %242, %243 : i64
%245 = arith.constant 1 : i1
%246 = llvm.mlir.constant(1 : i64) : i64
%247 = llvm.alloca %246 x i1 : (i64) -> !llvm.ptr
llvm.store %245, %247 : i1, !llvm.ptr
%248 = arith.constant 1 : i32
%249 = arith.cmpi eq, %183, %248 : i32
%250 = scf.if %249 -> (i1) {
%251 = arith.cmpi sgt, %244, %124 : i64
scf.yield %251 : i1
} else {
%252 = arith.constant false
scf.yield %252 : i1
}
cf.cond_br %250, ^bb54, ^bb55
^bb54:
%253 = arith.constant 0 : i1
llvm.store %253, %247 : i1, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%254 = llvm.load %247 : !llvm.ptr -> i1
cf.cond_br %254, ^bb57, ^bb58
^bb57:
%255 = arith.constant 0 : i32
%256 = llvm.mlir.constant(1 : i64) : i64
%257 = llvm.alloca %256 x i32 : (i64) -> !llvm.ptr
llvm.store %255, %257 : i32, !llvm.ptr
%258 = arith.constant 1 : i32
%259 = arith.cmpi eq, %183, %258 : i32
%260 = scf.if %259 -> (i1) {
%261 = arith.cmpi eq, %244, %124 : i64
scf.yield %261 : i1
} else {
%262 = arith.constant false
scf.yield %262 : i1
}
cf.cond_br %260, ^bb60, ^bb61
^bb60:
%263 = arith.constant 1 : i32
llvm.store %263, %257 : i32, !llvm.ptr
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
%264 = llvm.load %205 : !llvm.ptr -> i32
%265 = arith.constant 2 : i32
%266 = arith.shli %264, %265 : i32
%267 = llvm.load %234 : !llvm.ptr -> i32
%268 = arith.constant 1 : i32
%269 = arith.shli %267, %268 : i32
%270 = arith.ori %266, %269 : i32
%271 = llvm.load %257 : !llvm.ptr -> i32
%272 = arith.ori %270, %271 : i32
%274 = arith.extsi %272 : i32 to i64
%275 = llvm.getelementptr %73[%274] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%273 = llvm.load %275 : !llvm.ptr -> i64
%276 = arith.addi %273, %164 : i64
%277 = arith.remsi %276, %arg4 : i64
%278 = arith.extsi %272 : i32 to i64
%279 = llvm.getelementptr %73[%278] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %277, %279 : i64, !llvm.ptr
%280 = arith.extsi %164 : i64 to i128
%281 = llvm.load %187 : !llvm.ptr -> i64
%282 = arith.extsi %281 : i64 to i128
%284 = arith.trunci %280 : i128 to i64
%285 = arith.trunci %282 : i128 to i64
%283 = arith.muli %284, %285 : i64
%286 = arith.extsi %129 : i64 to i128
%288 = arith.trunci %286 : i128 to i64
%287 = arith.muli %283, %288 : i64
%289 = arith.extsi %arg4 : i64 to i128
%291 = arith.trunci %289 : i128 to i64
%290 = arith.remsi %287, %291 : i64
%292 = arith.extsi %164 : i64 to i128
%293 = llvm.load %216 : !llvm.ptr -> i64
%294 = arith.extsi %293 : i64 to i128
%296 = arith.trunci %292 : i128 to i64
%297 = arith.trunci %294 : i128 to i64
%295 = arith.muli %296, %297 : i64
%298 = arith.extsi %129 : i64 to i128
%300 = arith.trunci %298 : i128 to i64
%299 = arith.muli %295, %300 : i64
%301 = arith.extsi %arg4 : i64 to i128
%303 = arith.trunci %301 : i128 to i64
%302 = arith.remsi %299, %303 : i64
%304 = arith.extsi %164 : i64 to i128
%305 = arith.extsi %244 : i64 to i128
%307 = arith.trunci %304 : i128 to i64
%308 = arith.trunci %305 : i128 to i64
%306 = arith.muli %307, %308 : i64
%309 = arith.extsi %129 : i64 to i128
%311 = arith.trunci %309 : i128 to i64
%310 = arith.muli %306, %311 : i64
%312 = arith.extsi %arg4 : i64 to i128
%314 = arith.trunci %312 : i128 to i64
%313 = arith.remsi %310, %314 : i64
%316 = arith.extsi %272 : i32 to i64
%317 = llvm.getelementptr %78[%316] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%315 = llvm.load %317 : !llvm.ptr -> i64
%319 = llvm.load %133 : !llvm.ptr -> i32
%320 = arith.extsi %319 : i32 to i64
%321 = llvm.getelementptr %58[%320] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%318 = llvm.load %321 : !llvm.ptr -> i64
%322 = arith.addi %315, %318 : i64
%323 = arith.addi %322, %290 : i64
%324 = arith.remsi %323, %arg4 : i64
%325 = arith.extsi %272 : i32 to i64
%326 = llvm.getelementptr %78[%325] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %324, %326 : i64, !llvm.ptr
%328 = arith.extsi %272 : i32 to i64
%329 = llvm.getelementptr %83[%328] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%327 = llvm.load %329 : !llvm.ptr -> i64
%331 = llvm.load %133 : !llvm.ptr -> i32
%332 = arith.extsi %331 : i32 to i64
%333 = llvm.getelementptr %63[%332] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%330 = llvm.load %333 : !llvm.ptr -> i64
%334 = arith.addi %327, %330 : i64
%335 = arith.addi %334, %302 : i64
%336 = arith.remsi %335, %arg4 : i64
%337 = arith.extsi %272 : i32 to i64
%338 = llvm.getelementptr %83[%337] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %336, %338 : i64, !llvm.ptr
%340 = arith.extsi %272 : i32 to i64
%341 = llvm.getelementptr %88[%340] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%339 = llvm.load %341 : !llvm.ptr -> i64
%343 = llvm.load %133 : !llvm.ptr -> i32
%344 = arith.extsi %343 : i32 to i64
%345 = llvm.getelementptr %68[%344] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%342 = llvm.load %345 : !llvm.ptr -> i64
%346 = arith.addi %339, %342 : i64
%347 = arith.addi %346, %313 : i64
%348 = arith.remsi %347, %arg4 : i64
%349 = arith.extsi %272 : i32 to i64
%350 = llvm.getelementptr %88[%349] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %348, %350 : i64, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%351 = llvm.load %216 : !llvm.ptr -> i64
%352 = arith.constant 1 : i32
%354 = arith.extsi %352 : i32 to i64
%353 = arith.addi %351, %354 : i64
llvm.store %353, %216 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%355 = llvm.load %187 : !llvm.ptr -> i64
%356 = arith.constant 1 : i32
%358 = arith.extsi %356 : i32 to i64
%357 = arith.addi %355, %358 : i64
llvm.store %357, %187 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%359 = llvm.load %133 : !llvm.ptr -> i32
%360 = arith.constant 1 : i32
%361 = arith.addi %359, %360 : i32
llvm.store %361, %133 : i32, !llvm.ptr
cf.br ^bb24
^bb26:
%362 = arith.constant 0 : i32
llvm.store %362, %133 : i32, !llvm.ptr
cf.br ^bb63
^bb63:
%363 = llvm.load %133 : !llvm.ptr -> i32
%364 = arith.constant 8 : i32
%365 = arith.cmpi slt, %363, %364 : i32
cf.cond_br %365, ^bb64, ^bb65
^bb64:
%367 = llvm.load %133 : !llvm.ptr -> i32
%368 = arith.extsi %367 : i32 to i64
%369 = llvm.getelementptr %73[%368] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%366 = llvm.load %369 : !llvm.ptr -> i64
%370 = llvm.load %133 : !llvm.ptr -> i32
%371 = arith.extsi %370 : i32 to i64
%372 = llvm.getelementptr %53[%371] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %366, %372 : i64, !llvm.ptr
%374 = llvm.load %133 : !llvm.ptr -> i32
%375 = arith.extsi %374 : i32 to i64
%376 = llvm.getelementptr %78[%375] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%373 = llvm.load %376 : !llvm.ptr -> i64
%377 = llvm.load %133 : !llvm.ptr -> i32
%378 = arith.extsi %377 : i32 to i64
%379 = llvm.getelementptr %58[%378] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %373, %379 : i64, !llvm.ptr
%381 = llvm.load %133 : !llvm.ptr -> i32
%382 = arith.extsi %381 : i32 to i64
%383 = llvm.getelementptr %83[%382] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%380 = llvm.load %383 : !llvm.ptr -> i64
%384 = llvm.load %133 : !llvm.ptr -> i32
%385 = arith.extsi %384 : i32 to i64
%386 = llvm.getelementptr %63[%385] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %380, %386 : i64, !llvm.ptr
%388 = llvm.load %133 : !llvm.ptr -> i32
%389 = arith.extsi %388 : i32 to i64
%390 = llvm.getelementptr %88[%389] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%387 = llvm.load %390 : !llvm.ptr -> i64
%391 = llvm.load %133 : !llvm.ptr -> i32
%392 = arith.extsi %391 : i32 to i64
%393 = llvm.getelementptr %68[%392] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %387, %393 : i64, !llvm.ptr
%394 = llvm.load %133 : !llvm.ptr -> i32
%395 = arith.constant 1 : i32
%396 = arith.addi %394, %395 : i32
llvm.store %396, %133 : i32, !llvm.ptr
cf.br ^bb63
^bb65:
%397 = llvm.load %104 : !llvm.ptr -> i32
%398 = arith.constant 1 : i32
%399 = arith.subi %397, %398 : i32
llvm.store %399, %104 : i32, !llvm.ptr
cf.br ^bb18
^bb20:
%400 = arith.constant 0 : i32
%401 = arith.extsi %400 : i32 to i64
%402 = llvm.mlir.constant(1 : i64) : i64
%403 = llvm.alloca %402 x i64 : (i64) -> !llvm.ptr
llvm.store %401, %403 : i64, !llvm.ptr
%404 = arith.constant 0 : i32
%405 = arith.extsi %404 : i32 to i64
%406 = llvm.mlir.constant(1 : i64) : i64
%407 = llvm.alloca %406 x i64 : (i64) -> !llvm.ptr
llvm.store %405, %407 : i64, !llvm.ptr
%408 = arith.constant 0 : i32
%409 = llvm.mlir.constant(1 : i64) : i64
%410 = llvm.alloca %409 x i32 : (i64) -> !llvm.ptr
llvm.store %408, %410 : i32, !llvm.ptr
cf.br ^bb66
^bb66:
%411 = llvm.load %410 : !llvm.ptr -> i32
%412 = arith.constant 8 : i32
%413 = arith.cmpi slt, %411, %412 : i32
cf.cond_br %413, ^bb67, ^bb68
^bb67:
%414 = llvm.load %403 : !llvm.ptr -> i64
%416 = llvm.load %410 : !llvm.ptr -> i32
%417 = arith.extsi %416 : i32 to i64
%418 = llvm.getelementptr %53[%417] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%415 = llvm.load %418 : !llvm.ptr -> i64
%419 = arith.addi %414, %415 : i64
%420 = arith.remsi %419, %arg4 : i64
llvm.store %420, %403 : i64, !llvm.ptr
%421 = llvm.load %407 : !llvm.ptr -> i64
%423 = llvm.load %410 : !llvm.ptr -> i32
%424 = arith.extsi %423 : i32 to i64
%425 = llvm.getelementptr %58[%424] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%422 = llvm.load %425 : !llvm.ptr -> i64
%426 = arith.addi %421, %422 : i64
%428 = llvm.load %410 : !llvm.ptr -> i32
%429 = arith.extsi %428 : i32 to i64
%430 = llvm.getelementptr %63[%429] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%427 = llvm.load %430 : !llvm.ptr -> i64
%431 = arith.addi %426, %427 : i64
%433 = llvm.load %410 : !llvm.ptr -> i32
%434 = arith.extsi %433 : i32 to i64
%435 = llvm.getelementptr %68[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%432 = llvm.load %435 : !llvm.ptr -> i64
%436 = arith.addi %431, %432 : i64
%437 = arith.remsi %436, %arg4 : i64
llvm.store %437, %407 : i64, !llvm.ptr
%438 = llvm.load %410 : !llvm.ptr -> i32
%439 = arith.constant 1 : i32
%440 = arith.addi %438, %439 : i32
llvm.store %440, %410 : i32, !llvm.ptr
cf.br ^bb66
^bb68:
%441 = llvm.load %403 : !llvm.ptr -> i64
%442 = arith.constant 0 : i32
%443 = arith.extsi %442 : i32 to i64
%444 = llvm.getelementptr %arg3[%443] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %441, %444 : i64, !llvm.ptr
%445 = llvm.load %407 : !llvm.ptr -> i64
%446 = arith.constant 1 : i32
%447 = arith.extsi %446 : i32 to i64
%448 = llvm.getelementptr %arg3[%447] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %445, %448 : i64, !llvm.ptr
func.call @free(%88) : (!llvm.ptr) -> ()
func.call @free(%83) : (!llvm.ptr) -> ()
func.call @free(%78) : (!llvm.ptr) -> ()
func.call @free(%73) : (!llvm.ptr) -> ()
func.call @free(%68) : (!llvm.ptr) -> ()
func.call @free(%63) : (!llvm.ptr) -> ()
func.call @free(%58) : (!llvm.ptr) -> ()
func.call @free(%53) : (!llvm.ptr) -> ()
func.return
}
func.func @popcount8(%arg0: i32) -> i32 {
%457 = llvm.mlir.constant(1 : i64) : i64
%458 = llvm.alloca %457 x i32 : (i64) -> !llvm.ptr
llvm.store %arg0, %458 : i32, !llvm.ptr
%459 = arith.constant 0 : i32
%460 = llvm.mlir.constant(1 : i64) : i64
%461 = llvm.alloca %460 x i32 : (i64) -> !llvm.ptr
llvm.store %459, %461 : i32, !llvm.ptr
cf.br ^bb69
^bb69:
%462 = llvm.load %458 : !llvm.ptr -> i32
%463 = arith.constant 0 : i32
%464 = arith.cmpi sgt, %462, %463 : i32
cf.cond_br %464, ^bb70, ^bb71
^bb70:
%465 = llvm.load %461 : !llvm.ptr -> i32
%466 = llvm.load %458 : !llvm.ptr -> i32
%467 = arith.constant 1 : i32
%468 = arith.andi %466, %467 : i32
%469 = arith.addi %465, %468 : i32
llvm.store %469, %461 : i32, !llvm.ptr
%470 = llvm.load %458 : !llvm.ptr -> i32
%471 = arith.constant 1 : i32
%472 = arith.shrsi %470, %471 : i32
llvm.store %472, %458 : i32, !llvm.ptr
cf.br ^bb69
^bb71:
%473 = llvm.load %461 : !llvm.ptr -> i32
func.return %473 : i32
}
func.func @main() -> i32 {
%474 = arith.constant 999999995705032704 : i32
%475 = arith.extsi %474 : i32 to i64
%476 = arith.constant 1000000000 : i32
%477 = arith.extsi %476 : i32 to i64
%478 = arith.constant 1705032704 : i32
%479 = arith.extsi %478 : i32 to i64
%481 = arith.constant 2 : i32
%482 = arith.constant 8 : i32
%483 = arith.extsi %481 : i32 to i64
%484 = arith.extsi %482 : i32 to i64
%480 = func.call @calloc(%483, %484) : (i64, i64) -> !llvm.ptr
%485 = llvm.mlir.zero : !llvm.ptr
%486 = llvm.icmp "eq" %480, %485 : !llvm.ptr
cf.cond_br %486, ^bb72, ^bb73
^bb72:
%487 = arith.constant 1 : i32
func.return %487 : i32
^bb73:
cf.br ^bb74
^bb74:
%488 = arith.constant 0 : i32
%489 = arith.extsi %488 : i32 to i64
%490 = llvm.mlir.constant(1 : i64) : i64
%491 = llvm.alloca %490 x i64 : (i64) -> !llvm.ptr
llvm.store %489, %491 : i64, !llvm.ptr
%492 = arith.constant 0 : i32
%493 = arith.extsi %492 : i32 to i64
%494 = llvm.mlir.constant(1 : i64) : i64
%495 = llvm.alloca %494 x i64 : (i64) -> !llvm.ptr
llvm.store %493, %495 : i64, !llvm.ptr
%496 = arith.constant 0 : i32
%497 = llvm.mlir.constant(1 : i64) : i64
%498 = llvm.alloca %497 x i32 : (i64) -> !llvm.ptr
llvm.store %496, %498 : i32, !llvm.ptr
cf.br ^bb75
^bb75:
%499 = llvm.load %498 : !llvm.ptr -> i32
%500 = arith.constant 8 : i32
%501 = arith.cmpi slt, %499, %500 : i32
cf.cond_br %501, ^bb76, ^bb77
^bb76:
%502 = llvm.mlir.constant(1 : i64) : i64
%503 = llvm.alloca %502 x i64 : (i64) -> !llvm.ptr
llvm.store %475, %503 : i64, !llvm.ptr
%504 = llvm.mlir.constant(1 : i64) : i64
%505 = llvm.alloca %504 x i64 : (i64) -> !llvm.ptr
llvm.store %475, %505 : i64, !llvm.ptr
%506 = llvm.mlir.constant(1 : i64) : i64
%507 = llvm.alloca %506 x i64 : (i64) -> !llvm.ptr
llvm.store %475, %507 : i64, !llvm.ptr
%508 = llvm.load %498 : !llvm.ptr -> i32
%509 = arith.constant 1 : i32
%510 = arith.andi %508, %509 : i32
%511 = arith.constant 0 : i32
%512 = arith.cmpi ne, %510, %511 : i32
cf.cond_br %512, ^bb78, ^bb79
^bb78:
%513 = arith.constant 1 : i32
%514 = arith.extsi %513 : i32 to i64
llvm.store %514, %503 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%515 = llvm.load %498 : !llvm.ptr -> i32
%516 = arith.constant 2 : i32
%517 = arith.andi %515, %516 : i32
%518 = arith.constant 0 : i32
%519 = arith.cmpi ne, %517, %518 : i32
cf.cond_br %519, ^bb81, ^bb82
^bb81:
%520 = arith.constant 1 : i32
%521 = arith.extsi %520 : i32 to i64
llvm.store %521, %505 : i64, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%522 = llvm.load %498 : !llvm.ptr -> i32
%523 = arith.constant 4 : i32
%524 = arith.andi %522, %523 : i32
%525 = arith.constant 0 : i32
%526 = arith.cmpi ne, %524, %525 : i32
cf.cond_br %526, ^bb84, ^bb85
^bb84:
%527 = arith.constant 1 : i32
%528 = arith.extsi %527 : i32 to i64
llvm.store %528, %507 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
%530 = llvm.load %503 : !llvm.ptr -> i64
%531 = llvm.load %505 : !llvm.ptr -> i64
%532 = llvm.load %507 : !llvm.ptr -> i64
func.call @dp_count_sum(%530, %531, %532, %480, %479) : (i64, i64, i64, !llvm.ptr, i64) -> ()
%534 = llvm.load %498 : !llvm.ptr -> i32
%533 = func.call @popcount8(%534) : (i32) -> i32
%535 = arith.constant 1 : i32
%536 = arith.andi %533, %535 : i32
%537 = arith.constant 0 : i32
%538 = arith.cmpi eq, %536, %537 : i32
cf.cond_br %538, ^bb87, ^bb88
^bb87:
%539 = llvm.load %491 : !llvm.ptr -> i64
%541 = arith.constant 0 : i32
%542 = arith.extsi %541 : i32 to i64
%543 = llvm.getelementptr %480[%542] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%540 = llvm.load %543 : !llvm.ptr -> i64
%544 = arith.addi %539, %540 : i64
%545 = arith.remsi %544, %479 : i64
llvm.store %545, %491 : i64, !llvm.ptr
%546 = llvm.load %495 : !llvm.ptr -> i64
%548 = arith.constant 1 : i32
%549 = arith.extsi %548 : i32 to i64
%550 = llvm.getelementptr %480[%549] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%547 = llvm.load %550 : !llvm.ptr -> i64
%551 = arith.addi %546, %547 : i64
%552 = arith.remsi %551, %479 : i64
llvm.store %552, %495 : i64, !llvm.ptr
cf.br ^bb89
^bb88:
%553 = llvm.load %491 : !llvm.ptr -> i64
%555 = arith.constant 0 : i32
%556 = arith.extsi %555 : i32 to i64
%557 = llvm.getelementptr %480[%556] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%554 = llvm.load %557 : !llvm.ptr -> i64
%558 = arith.remsi %554, %479 : i64
%559 = arith.subi %553, %558 : i64
%560 = arith.addi %559, %479 : i64
%561 = arith.remsi %560, %479 : i64
llvm.store %561, %491 : i64, !llvm.ptr
%562 = llvm.load %495 : !llvm.ptr -> i64
%564 = arith.constant 1 : i32
%565 = arith.extsi %564 : i32 to i64
%566 = llvm.getelementptr %480[%565] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%563 = llvm.load %566 : !llvm.ptr -> i64
%567 = arith.remsi %563, %479 : i64
%568 = arith.subi %562, %567 : i64
%569 = arith.addi %568, %479 : i64
%570 = arith.remsi %569, %479 : i64
llvm.store %570, %495 : i64, !llvm.ptr
cf.br ^bb89
^bb89:
%571 = llvm.load %498 : !llvm.ptr -> i32
%572 = arith.constant 1 : i32
%573 = arith.addi %571, %572 : i32
llvm.store %573, %498 : i32, !llvm.ptr
cf.br ^bb75
^bb77:
%574 = llvm.load %495 : !llvm.ptr -> i64
%575 = arith.constant 3 : i32
%576 = llvm.load %491 : !llvm.ptr -> i64
%578 = arith.extsi %575 : i32 to i64
%577 = arith.muli %578, %576 : i64
%579 = arith.remsi %577, %479 : i64
%580 = arith.subi %574, %579 : i64
%581 = arith.addi %580, %479 : i64
%582 = arith.remsi %581, %479 : i64
%583 = llvm.mlir.constant(1 : i64) : i64
%584 = llvm.alloca %583 x i64 : (i64) -> !llvm.ptr
llvm.store %582, %584 : i64, !llvm.ptr
%585 = llvm.load %584 : !llvm.ptr -> i64
%586 = arith.constant 6 : i32
%588 = arith.extsi %586 : i32 to i64
%587 = arith.divsi %585, %588 : i64
%589 = arith.remsi %587, %477 : i64
%590 = llvm.mlir.addressof @str_0 : !llvm.ptr
%591 = llvm.call @printf(%590, %589) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%480) : (!llvm.ptr) -> ()
%593 = arith.constant 0 : i32
func.return %593 : i32
}
}