← All problems Problem 676
Digit DP over binary representation, tracking diff of digit sums in two bases. Sum over (k,l) pairs of M(10^16, 2^k, 2^l), last 16 digits.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(1)O(n)Space complexity O(n^2)O(n)Approach Flow solution Big-integer arithmetic Verdict Optimal
Flow source
# Project Euler 676: Matching Digit Sums
# Digit DP over binary representation, tracking diff of digit sums in two bases.
# Sum over (k,l) pairs of M(10^16, 2^k, 2^l), last 16 digits.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 10000000000000000 # 10^16
const MAX_DIFF: i64 = 2000
const ARR_SIZE: i64 = 4001
const OFFSET: i64 = 2000
function M_power2_bases(n: i64, k: i64, l: i64) -> i64 {
if n <= 0 { return 0 }
# Extract bits of n (MSB first)
let mut B: i64 = 0
let mut tmp: i64 = n
while tmp > 0 { B = B + 1; tmp = tmp >> 1 }
# bits[p] = bit at position p (0=LSB, B-1=MSB)
# We process from MSB to LSB
# tight_count[diff+offset], tight_sum[diff+offset]
let tight_cnt: ptr<i64> = calloc(ARR_SIZE, 8)
let tight_sum: ptr<i64> = calloc(ARR_SIZE, 8)
let loose_cnt: ptr<i64> = calloc(ARR_SIZE, 8)
let loose_sum: ptr<i64> = calloc(ARR_SIZE, 8)
let new_tight_cnt: ptr<i64> = calloc(ARR_SIZE, 8)
let new_tight_sum: ptr<i64> = calloc(ARR_SIZE, 8)
let new_loose_cnt: ptr<i64> = calloc(ARR_SIZE, 8)
let new_loose_sum: ptr<i64> = calloc(ARR_SIZE, 8)
# Initialize: tight state with diff=0, count=1, sum=0
tight_cnt[OFFSET] = 1
for idx in 0..B {
# Bit position from MSB: p = B-1-idx
let p: i64 = B - 1 - idx
# Bit value at this position in n
let lim: i64 = (n >> p) & 1
# Contribution to diff if this bit is 1
let pk: i64 = p % k
let pl: i64 = p % l
let mut ck: i64 = 1
for _ in 0..pk { ck = ck * 2 }
let mut cl: i64 = 1
for _ in 0..pl { cl = cl * 2 }
let c: i64 = ck - cl
# Weight (value contribution if bit is 1)
let mut w: i64 = 1
for _ in 0..p { w = w * 2 }
# Clear new arrays
for i in 0..ARR_SIZE {
new_tight_cnt[i] = 0
new_tight_sum[i] = 0
new_loose_cnt[i] = 0
new_loose_sum[i] = 0
}
# Extend loose states: next bit can be 0 or 1
for d in 0..ARR_SIZE {
if loose_cnt[d] == 0 { continue }
let cnt: i64 = loose_cnt[d]
let sm: i64 = loose_sum[d]
# bit 0: diff unchanged
new_loose_cnt[d] = (new_loose_cnt[d] + cnt) % MOD
new_loose_sum[d] = (new_loose_sum[d] + sm) % MOD
# bit 1: diff += c
let d1: i64 = d + c
if d1 >= 0 && d1 < ARR_SIZE {
new_loose_cnt[d1] = (new_loose_cnt[d1] + cnt) % MOD
let wcnt: i128 = (w as i128) * (cnt as i128)
new_loose_sum[d1] = ((new_loose_sum[d1] as i128 + sm as i128 + wcnt % (MOD as i128)) % (MOD as i128)) as i64
}
}
# Extend tight states
for d in 0..ARR_SIZE {
if tight_cnt[d] == 0 { continue }
let cnt: i64 = tight_cnt[d]
let sm: i64 = tight_sum[d]
if lim == 0 {
# only bit 0 keeps tight
new_tight_cnt[d] = (new_tight_cnt[d] + cnt) % MOD
new_tight_sum[d] = (new_tight_sum[d] + sm) % MOD
} else {
# choose 0 -> becomes loose
new_loose_cnt[d] = (new_loose_cnt[d] + cnt) % MOD
new_loose_sum[d] = (new_loose_sum[d] + sm) % MOD
# choose 1 -> stays tight
let d1: i64 = d + c
if d1 >= 0 && d1 < ARR_SIZE {
new_tight_cnt[d1] = (new_tight_cnt[d1] + cnt) % MOD
let wcnt2: i128 = (w as i128) * (cnt as i128)
new_tight_sum[d1] = ((new_tight_sum[d1] as i128 + sm as i128 + wcnt2 % (MOD as i128)) % (MOD as i128)) as i64
}
}
}
# Swap: copy new to current
for i in 0..ARR_SIZE {
tight_cnt[i] = new_tight_cnt[i]
tight_sum[i] = new_tight_sum[i]
loose_cnt[i] = new_loose_cnt[i]
loose_sum[i] = new_loose_sum[i]
}
}
# Answer: sum of values where diff = 0
let mut result: i64 = 0
result = (result + tight_sum[OFFSET]) % MOD
result = (result + loose_sum[OFFSET]) % MOD
free(new_loose_sum)
free(new_loose_cnt)
free(new_tight_sum)
free(new_tight_cnt)
free(loose_sum)
free(loose_cnt)
free(tight_sum)
free(tight_cnt)
return result
}
function main() -> i32 {
let N: i64 = 10000000000000000 # 10^16
let mut total: i64 = 0
# k=3, l=1
total = (total + M_power2_bases(N, 3, 1)) % MOD
# k=4, l=1,2
total = (total + M_power2_bases(N, 4, 1)) % MOD
total = (total + M_power2_bases(N, 4, 2)) % MOD
# k=5, l=1,2,3
total = (total + M_power2_bases(N, 5, 1)) % MOD
total = (total + M_power2_bases(N, 5, 2)) % MOD
total = (total + M_power2_bases(N, 5, 3)) % MOD
# k=6, l=1,2,3,4
total = (total + M_power2_bases(N, 6, 1)) % MOD
total = (total + M_power2_bases(N, 6, 2)) % MOD
total = (total + M_power2_bases(N, 6, 3)) % MOD
total = (total + M_power2_bases(N, 6, 4)) % MOD
printf("%016lld\n", total)
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; }
int64_t M_power2_bases_i64_i64_i64(int64_t n, int64_t k, int64_t l);
int32_t main(void);
static const int64_t MOD = 10000000000000000;
static const int64_t MAX_DIFF = 2000;
static const int64_t ARR_SIZE = 4001;
static const int64_t OFFSET = 2000;
int64_t M_power2_bases_i64_i64_i64(int64_t n, int64_t k, int64_t l) {
if (n <= 0) {
return 0;
}
int64_t B = 0;
int64_t tmp = n;
while (tmp > 0) {
B = (B + 1);
tmp = FLOW_CHECKED_SHR((tmp), (1));
}
int64_t* tight_cnt = (int64_t*)(calloc(ARR_SIZE, 8));
int64_t* tight_sum = (int64_t*)(calloc(ARR_SIZE, 8));
int64_t* loose_cnt = (int64_t*)(calloc(ARR_SIZE, 8));
int64_t* loose_sum = (int64_t*)(calloc(ARR_SIZE, 8));
int64_t* new_tight_cnt = (int64_t*)(calloc(ARR_SIZE, 8));
int64_t* new_tight_sum = (int64_t*)(calloc(ARR_SIZE, 8));
int64_t* new_loose_cnt = (int64_t*)(calloc(ARR_SIZE, 8));
int64_t* new_loose_sum = (int64_t*)(calloc(ARR_SIZE, 8));
tight_cnt[OFFSET] = 1;
int32_t __flow_step_1 = 1;
for (int32_t idx = 0; (0 <= B) ? idx < B : idx > B; idx += (0 <= B) ? 1 : -1) {
int64_t p = ((B - 1) - idx);
int64_t lim = (FLOW_CHECKED_SHR((n), (p)) & 1);
int64_t pk = FLOW_CHECKED_MOD((p), (k));
int64_t pl = FLOW_CHECKED_MOD((p), (l));
int64_t ck = 1;
int32_t __flow_step_2 = 1;
for (int32_t _ = 0; (0 <= pk) ? _ < pk : _ > pk; _ += (0 <= pk) ? 1 : -1) {
ck = (ck * 2);
}
int64_t cl = 1;
int32_t __flow_step_3 = 1;
for (int32_t _ = 0; (0 <= pl) ? _ < pl : _ > pl; _ += (0 <= pl) ? 1 : -1) {
cl = (cl * 2);
}
int64_t c = (ck - cl);
int64_t w = 1;
int32_t __flow_step_4 = 1;
for (int32_t _ = 0; (0 <= p) ? _ < p : _ > p; _ += (0 <= p) ? 1 : -1) {
w = (w * 2);
}
int32_t __flow_step_5 = 1;
for (int32_t i = 0; (0 <= ARR_SIZE) ? i < ARR_SIZE : i > ARR_SIZE; i += (0 <= ARR_SIZE) ? 1 : -1) {
new_tight_cnt[i] = 0;
new_tight_sum[i] = 0;
new_loose_cnt[i] = 0;
new_loose_sum[i] = 0;
}
int32_t __flow_step_6 = 1;
for (int32_t d = 0; (0 <= ARR_SIZE) ? d < ARR_SIZE : d > ARR_SIZE; d += (0 <= ARR_SIZE) ? 1 : -1) {
if (loose_cnt[d] == 0) {
continue;
}
int64_t cnt = loose_cnt[d];
int64_t sm = loose_sum[d];
new_loose_cnt[d] = FLOW_CHECKED_MOD(((new_loose_cnt[d] + cnt)), (MOD));
new_loose_sum[d] = FLOW_CHECKED_MOD(((new_loose_sum[d] + sm)), (MOD));
int64_t d1 = (d + c);
if ((d1 >= 0 && d1 < ARR_SIZE)) {
new_loose_cnt[d1] = FLOW_CHECKED_MOD(((new_loose_cnt[d1] + cnt)), (MOD));
__int128 wcnt = (((__int128)(w)) * ((__int128)(cnt)));
new_loose_sum[d1] = ((int64_t)(FLOW_CHECKED_MOD((((((__int128)(new_loose_sum[d1])) + ((__int128)(sm))) + FLOW_CHECKED_MOD((wcnt), (((__int128)(MOD)))))), (((__int128)(MOD))))));
}
}
int32_t __flow_step_7 = 1;
for (int32_t d = 0; (0 <= ARR_SIZE) ? d < ARR_SIZE : d > ARR_SIZE; d += (0 <= ARR_SIZE) ? 1 : -1) {
if (tight_cnt[d] == 0) {
continue;
}
int64_t cnt = tight_cnt[d];
int64_t sm = tight_sum[d];
if (lim == 0) {
new_tight_cnt[d] = FLOW_CHECKED_MOD(((new_tight_cnt[d] + cnt)), (MOD));
new_tight_sum[d] = FLOW_CHECKED_MOD(((new_tight_sum[d] + sm)), (MOD));
} else {
new_loose_cnt[d] = FLOW_CHECKED_MOD(((new_loose_cnt[d] + cnt)), (MOD));
new_loose_sum[d] = FLOW_CHECKED_MOD(((new_loose_sum[d] + sm)), (MOD));
int64_t d1 = (d + c);
if ((d1 >= 0 && d1 < ARR_SIZE)) {
new_tight_cnt[d1] = FLOW_CHECKED_MOD(((new_tight_cnt[d1] + cnt)), (MOD));
__int128 wcnt2 = (((__int128)(w)) * ((__int128)(cnt)));
new_tight_sum[d1] = ((int64_t)(FLOW_CHECKED_MOD((((((__int128)(new_tight_sum[d1])) + ((__int128)(sm))) + FLOW_CHECKED_MOD((wcnt2), (((__int128)(MOD)))))), (((__int128)(MOD))))));
}
}
}
int32_t __flow_step_8 = 1;
for (int32_t i = 0; (0 <= ARR_SIZE) ? i < ARR_SIZE : i > ARR_SIZE; i += (0 <= ARR_SIZE) ? 1 : -1) {
tight_cnt[i] = new_tight_cnt[i];
tight_sum[i] = new_tight_sum[i];
loose_cnt[i] = new_loose_cnt[i];
loose_sum[i] = new_loose_sum[i];
}
}
int64_t result = 0;
result = FLOW_CHECKED_MOD(((result + tight_sum[OFFSET])), (MOD));
result = FLOW_CHECKED_MOD(((result + loose_sum[OFFSET])), (MOD));
free(new_loose_sum);
free(new_loose_cnt);
free(new_tight_sum);
free(new_tight_cnt);
free(loose_sum);
free(loose_cnt);
free(tight_sum);
free(tight_cnt);
return result;
}
int32_t main(void) {
int64_t N = 10000000000000000;
int64_t total = 0;
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 3, 1))), (MOD));
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 4, 1))), (MOD));
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 4, 2))), (MOD));
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 5, 1))), (MOD));
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 5, 2))), (MOD));
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 5, 3))), (MOD));
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 6, 1))), (MOD));
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 6, 2))), (MOD));
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 6, 3))), (MOD));
total = FLOW_CHECKED_MOD(((total + M_power2_bases_i64_i64_i64(N, 6, 4))), (MOD));
printf("%016lld\n", total);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%016lld\n\00") {addr_space = 0 : i32} : !llvm.array<9 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(10000000000000000 : i64) : i64
// Constant: MAX_DIFF
llvm.mlir.global internal constant @MAX_DIFF(2000 : i64) : i64
// Constant: ARR_SIZE
llvm.mlir.global internal constant @ARR_SIZE(4001 : i64) : i64
// Constant: OFFSET
llvm.mlir.global internal constant @OFFSET(2000 : i64) : i64
func.func @M_power2_bases(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%0 = arith.constant 0 : i32
%2 = arith.extsi %0 : i32 to i64
%1 = arith.cmpi sle, %arg0, %2 : i64
cf.cond_br %1, ^bb0, ^bb1
^bb0:
%3 = arith.constant 0 : i32
%4 = arith.extsi %3 : i32 to i64
func.return %4 : i64
^bb1:
cf.br ^bb2
^bb2:
%5 = arith.constant 0 : i32
%6 = arith.extsi %5 : i32 to i64
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %6, %8 : i64, !llvm.ptr
%9 = llvm.mlir.constant(1 : i64) : i64
%10 = llvm.alloca %9 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %10 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%11 = llvm.load %10 : !llvm.ptr -> i64
%12 = arith.constant 0 : i32
%14 = arith.extsi %12 : i32 to i64
%13 = arith.cmpi sgt, %11, %14 : i64
cf.cond_br %13, ^bb4, ^bb5
^bb4:
%15 = llvm.load %8 : !llvm.ptr -> i64
%16 = arith.constant 1 : i32
%18 = arith.extsi %16 : i32 to i64
%17 = arith.addi %15, %18 : i64
llvm.store %17, %8 : i64, !llvm.ptr
%19 = llvm.load %10 : !llvm.ptr -> i64
%20 = arith.constant 1 : i32
%22 = arith.extsi %20 : i32 to i64
%21 = arith.shrsi %19, %22 : i64
llvm.store %21, %10 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%24 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%25 = llvm.load %24 : !llvm.ptr -> i64
%26 = arith.constant 8 : i32
%27 = arith.extsi %26 : i32 to i64
%23 = func.call @calloc(%25, %27) : (i64, i64) -> !llvm.ptr
%29 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%30 = llvm.load %29 : !llvm.ptr -> i64
%31 = arith.constant 8 : i32
%32 = arith.extsi %31 : i32 to i64
%28 = func.call @calloc(%30, %32) : (i64, i64) -> !llvm.ptr
%34 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%35 = llvm.load %34 : !llvm.ptr -> i64
%36 = arith.constant 8 : i32
%37 = arith.extsi %36 : i32 to i64
%33 = func.call @calloc(%35, %37) : (i64, i64) -> !llvm.ptr
%39 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%40 = llvm.load %39 : !llvm.ptr -> i64
%41 = arith.constant 8 : i32
%42 = arith.extsi %41 : i32 to i64
%38 = func.call @calloc(%40, %42) : (i64, i64) -> !llvm.ptr
%44 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%45 = llvm.load %44 : !llvm.ptr -> i64
%46 = arith.constant 8 : i32
%47 = arith.extsi %46 : i32 to i64
%43 = func.call @calloc(%45, %47) : (i64, i64) -> !llvm.ptr
%49 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%50 = llvm.load %49 : !llvm.ptr -> i64
%51 = arith.constant 8 : i32
%52 = arith.extsi %51 : i32 to i64
%48 = func.call @calloc(%50, %52) : (i64, i64) -> !llvm.ptr
%54 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%55 = llvm.load %54 : !llvm.ptr -> i64
%56 = arith.constant 8 : i32
%57 = arith.extsi %56 : i32 to i64
%53 = func.call @calloc(%55, %57) : (i64, i64) -> !llvm.ptr
%59 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%60 = llvm.load %59 : !llvm.ptr -> i64
%61 = arith.constant 8 : i32
%62 = arith.extsi %61 : i32 to i64
%58 = func.call @calloc(%60, %62) : (i64, i64) -> !llvm.ptr
%63 = arith.constant 1 : i32
%64 = llvm.mlir.addressof @OFFSET : !llvm.ptr
%65 = llvm.load %64 : !llvm.ptr -> i64
%66 = arith.extsi %63 : i32 to i64
%67 = llvm.getelementptr %23[%65] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %66, %67 : i64, !llvm.ptr
%68 = arith.constant 0 : i32
%69 = llvm.load %8 : !llvm.ptr -> i64
%70 = arith.index_cast %68 : i32 to index
%71 = arith.index_cast %69 : i32 to index
%73 = arith.constant 1 : index
%74 = arith.constant -1 : index
%75 = arith.cmpi sle, %70, %71 : index
%72 = arith.select %75, %73, %74 : index
cf.br ^bb6(%70 : index)
^bb6(%76: index):
%77 = arith.cmpi slt, %76, %71 : index
%78 = arith.cmpi sgt, %76, %71 : index
%79 = arith.select %75, %77, %78 : i1
cf.cond_br %79, ^bb7(%76 : index), ^bb8(%76 : index)
^bb7(%80: index):
%81 = llvm.load %8 : !llvm.ptr -> i64
%82 = arith.constant 1 : i32
%84 = arith.extsi %82 : i32 to i64
%83 = arith.subi %81, %84 : i64
%86 = arith.trunci %83 : i64 to i32
%87 = arith.index_cast %80 : index to i32
%85 = arith.subi %86, %87 : i32
%88 = arith.extsi %85 : i32 to i64
%89 = arith.shrsi %arg0, %88 : i64
%90 = arith.constant 1 : i32
%92 = arith.extsi %90 : i32 to i64
%91 = arith.andi %89, %92 : i64
%93 = arith.remsi %88, %arg1 : i64
%94 = arith.remsi %88, %arg2 : i64
%95 = arith.constant 1 : i32
%96 = arith.extsi %95 : i32 to i64
%97 = llvm.mlir.constant(1 : i64) : i64
%98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
llvm.store %96, %98 : i64, !llvm.ptr
%99 = arith.constant 0 : i32
%100 = arith.index_cast %99 : i32 to index
%101 = arith.index_cast %93 : i32 to index
%103 = arith.constant 1 : index
%104 = arith.constant -1 : index
%105 = arith.cmpi sle, %100, %101 : index
%102 = arith.select %105, %103, %104 : index
cf.br ^bb9(%100 : index)
^bb9(%106: index):
%107 = arith.cmpi slt, %106, %101 : index
%108 = arith.cmpi sgt, %106, %101 : index
%109 = arith.select %105, %107, %108 : i1
cf.cond_br %109, ^bb10(%106 : index), ^bb11(%106 : index)
^bb10(%110: index):
%111 = llvm.load %98 : !llvm.ptr -> i64
%112 = arith.constant 2 : i32
%114 = arith.extsi %112 : i32 to i64
%113 = arith.muli %111, %114 : i64
llvm.store %113, %98 : i64, !llvm.ptr
%115 = arith.addi %110, %102 : index
cf.br ^bb9(%115 : index)
^bb11(%116: index):
%117 = arith.constant 1 : i32
%118 = arith.extsi %117 : i32 to i64
%119 = llvm.mlir.constant(1 : i64) : i64
%120 = llvm.alloca %119 x i64 : (i64) -> !llvm.ptr
llvm.store %118, %120 : i64, !llvm.ptr
%121 = arith.constant 0 : i32
%122 = arith.index_cast %121 : i32 to index
%123 = arith.index_cast %94 : i32 to index
%125 = arith.constant 1 : index
%126 = arith.constant -1 : index
%127 = arith.cmpi sle, %122, %123 : index
%124 = arith.select %127, %125, %126 : index
cf.br ^bb12(%122 : index)
^bb12(%128: index):
%129 = arith.cmpi slt, %128, %123 : index
%130 = arith.cmpi sgt, %128, %123 : index
%131 = arith.select %127, %129, %130 : i1
cf.cond_br %131, ^bb13(%128 : index), ^bb14(%128 : index)
^bb13(%132: index):
%133 = llvm.load %120 : !llvm.ptr -> i64
%134 = arith.constant 2 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.muli %133, %136 : i64
llvm.store %135, %120 : i64, !llvm.ptr
%137 = arith.addi %132, %124 : index
cf.br ^bb12(%137 : index)
^bb14(%138: index):
%139 = llvm.load %98 : !llvm.ptr -> i64
%140 = llvm.load %120 : !llvm.ptr -> i64
%141 = arith.subi %139, %140 : i64
%142 = arith.constant 1 : i32
%143 = arith.extsi %142 : i32 to i64
%144 = llvm.mlir.constant(1 : i64) : i64
%145 = llvm.alloca %144 x i64 : (i64) -> !llvm.ptr
llvm.store %143, %145 : i64, !llvm.ptr
%146 = arith.constant 0 : i32
%147 = arith.index_cast %146 : i32 to index
%148 = arith.index_cast %88 : i32 to index
%150 = arith.constant 1 : index
%151 = arith.constant -1 : index
%152 = arith.cmpi sle, %147, %148 : index
%149 = arith.select %152, %150, %151 : index
cf.br ^bb15(%147 : index)
^bb15(%153: index):
%154 = arith.cmpi slt, %153, %148 : index
%155 = arith.cmpi sgt, %153, %148 : index
%156 = arith.select %152, %154, %155 : i1
cf.cond_br %156, ^bb16(%153 : index), ^bb17(%153 : index)
^bb16(%157: index):
%158 = llvm.load %145 : !llvm.ptr -> i64
%159 = arith.constant 2 : i32
%161 = arith.extsi %159 : i32 to i64
%160 = arith.muli %158, %161 : i64
llvm.store %160, %145 : i64, !llvm.ptr
%162 = arith.addi %157, %149 : index
cf.br ^bb15(%162 : index)
^bb17(%163: index):
%164 = arith.constant 0 : i32
%165 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%166 = llvm.load %165 : !llvm.ptr -> i64
%167 = arith.index_cast %164 : i32 to index
%168 = arith.index_cast %166 : i32 to index
%170 = arith.constant 1 : index
%171 = arith.constant -1 : index
%172 = arith.cmpi sle, %167, %168 : index
%169 = arith.select %172, %170, %171 : index
cf.br ^bb18(%167 : index)
^bb18(%173: index):
%174 = arith.cmpi slt, %173, %168 : index
%175 = arith.cmpi sgt, %173, %168 : index
%176 = arith.select %172, %174, %175 : i1
cf.cond_br %176, ^bb19(%173 : index), ^bb20(%173 : index)
^bb19(%177: index):
%178 = arith.constant 0 : i32
%179 = arith.extsi %178 : i32 to i64
%180 = arith.index_cast %177 : index to i64
%181 = llvm.getelementptr %43[%180] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %179, %181 : i64, !llvm.ptr
%182 = arith.constant 0 : i32
%183 = arith.extsi %182 : i32 to i64
%184 = arith.index_cast %177 : index to i64
%185 = llvm.getelementptr %48[%184] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %183, %185 : i64, !llvm.ptr
%186 = arith.constant 0 : i32
%187 = arith.extsi %186 : i32 to i64
%188 = arith.index_cast %177 : index to i64
%189 = llvm.getelementptr %53[%188] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %187, %189 : i64, !llvm.ptr
%190 = arith.constant 0 : i32
%191 = arith.extsi %190 : i32 to i64
%192 = arith.index_cast %177 : index to i64
%193 = llvm.getelementptr %58[%192] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %191, %193 : i64, !llvm.ptr
%194 = arith.addi %177, %169 : index
cf.br ^bb18(%194 : index)
^bb20(%195: index):
%196 = arith.constant 0 : i32
%197 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%198 = llvm.load %197 : !llvm.ptr -> i64
%199 = arith.index_cast %196 : i32 to index
%200 = arith.index_cast %198 : i32 to index
%202 = arith.constant 1 : index
%203 = arith.constant -1 : index
%204 = arith.cmpi sle, %199, %200 : index
%201 = arith.select %204, %202, %203 : index
cf.br ^bb21(%199 : index)
^bb21(%205: index):
%206 = arith.cmpi slt, %205, %200 : index
%207 = arith.cmpi sgt, %205, %200 : index
%208 = arith.select %204, %206, %207 : i1
cf.cond_br %208, ^bb22(%205 : index), ^bb23(%205 : index)
^bb22(%209: index):
%211 = arith.index_cast %209 : index to i64
%212 = llvm.getelementptr %33[%211] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%210 = llvm.load %212 : !llvm.ptr -> i64
%213 = arith.constant 0 : i32
%215 = arith.extsi %213 : i32 to i64
%214 = arith.cmpi eq, %210, %215 : i64
cf.cond_br %214, ^bb24, ^bb25
^bb24:
%216 = arith.addi %209, %201 : index
cf.br ^bb21(%216 : index)
^bb25:
cf.br ^bb26
^bb26:
%218 = arith.index_cast %209 : index to i64
%219 = llvm.getelementptr %33[%218] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%217 = llvm.load %219 : !llvm.ptr -> i64
%221 = arith.index_cast %209 : index to i64
%222 = llvm.getelementptr %38[%221] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%220 = llvm.load %222 : !llvm.ptr -> i64
%224 = arith.index_cast %209 : index to i64
%225 = llvm.getelementptr %53[%224] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%223 = llvm.load %225 : !llvm.ptr -> i64
%226 = arith.addi %223, %217 : i64
%227 = llvm.mlir.addressof @MOD : !llvm.ptr
%228 = llvm.load %227 : !llvm.ptr -> i64
%229 = arith.remsi %226, %228 : i64
%230 = arith.index_cast %209 : index to i64
%231 = llvm.getelementptr %53[%230] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %229, %231 : i64, !llvm.ptr
%233 = arith.index_cast %209 : index to i64
%234 = llvm.getelementptr %58[%233] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%232 = llvm.load %234 : !llvm.ptr -> i64
%235 = arith.addi %232, %220 : i64
%236 = llvm.mlir.addressof @MOD : !llvm.ptr
%237 = llvm.load %236 : !llvm.ptr -> i64
%238 = arith.remsi %235, %237 : i64
%239 = arith.index_cast %209 : index to i64
%240 = llvm.getelementptr %58[%239] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %238, %240 : i64, !llvm.ptr
%242 = arith.index_cast %209 : index to i32
%243 = arith.trunci %141 : i64 to i32
%241 = arith.addi %242, %243 : i32
%244 = arith.extsi %241 : i32 to i64
%245 = arith.constant 0 : i32
%247 = arith.extsi %245 : i32 to i64
%246 = arith.cmpi sge, %244, %247 : i64
%248 = scf.if %246 -> (i1) {
%249 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%250 = llvm.load %249 : !llvm.ptr -> i64
%251 = arith.cmpi slt, %244, %250 : i64
scf.yield %251 : i1
} else {
%252 = arith.constant false
scf.yield %252 : i1
}
cf.cond_br %248, ^bb27, ^bb28
^bb27:
%254 = llvm.getelementptr %53[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%253 = llvm.load %254 : !llvm.ptr -> i64
%255 = arith.addi %253, %217 : i64
%256 = llvm.mlir.addressof @MOD : !llvm.ptr
%257 = llvm.load %256 : !llvm.ptr -> i64
%258 = arith.remsi %255, %257 : i64
%259 = llvm.getelementptr %53[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %258, %259 : i64, !llvm.ptr
%260 = llvm.load %145 : !llvm.ptr -> i64
%261 = arith.extsi %260 : i64 to i128
%262 = arith.extsi %217 : i64 to i128
%264 = arith.trunci %261 : i128 to i64
%265 = arith.trunci %262 : i128 to i64
%263 = arith.muli %264, %265 : i64
%266 = arith.extsi %263 : i64 to i128
%268 = llvm.getelementptr %58[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%267 = llvm.load %268 : !llvm.ptr -> i64
%269 = arith.extsi %267 : i64 to i128
%270 = arith.extsi %220 : i64 to i128
%272 = arith.trunci %269 : i128 to i64
%273 = arith.trunci %270 : i128 to i64
%271 = arith.addi %272, %273 : i64
%274 = llvm.mlir.addressof @MOD : !llvm.ptr
%275 = llvm.load %274 : !llvm.ptr -> i64
%276 = arith.extsi %275 : i64 to i128
%278 = arith.trunci %266 : i128 to i64
%279 = arith.trunci %276 : i128 to i64
%277 = arith.remsi %278, %279 : i64
%280 = arith.addi %271, %277 : i64
%281 = llvm.mlir.addressof @MOD : !llvm.ptr
%282 = llvm.load %281 : !llvm.ptr -> i64
%283 = arith.extsi %282 : i64 to i128
%285 = arith.trunci %283 : i128 to i64
%284 = arith.remsi %280, %285 : i64
%286 = llvm.getelementptr %58[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %284, %286 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%287 = arith.addi %209, %201 : index
cf.br ^bb21(%287 : index)
^bb23(%288: index):
%289 = arith.constant 0 : i32
%290 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%291 = llvm.load %290 : !llvm.ptr -> i64
%292 = arith.index_cast %289 : i32 to index
%293 = arith.index_cast %291 : i32 to index
%295 = arith.constant 1 : index
%296 = arith.constant -1 : index
%297 = arith.cmpi sle, %292, %293 : index
%294 = arith.select %297, %295, %296 : index
cf.br ^bb30(%292 : index)
^bb30(%298: index):
%299 = arith.cmpi slt, %298, %293 : index
%300 = arith.cmpi sgt, %298, %293 : index
%301 = arith.select %297, %299, %300 : i1
cf.cond_br %301, ^bb31(%298 : index), ^bb32(%298 : index)
^bb31(%302: index):
%304 = arith.index_cast %302 : index to i64
%305 = llvm.getelementptr %23[%304] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%303 = llvm.load %305 : !llvm.ptr -> i64
%306 = arith.constant 0 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.cmpi eq, %303, %308 : i64
cf.cond_br %307, ^bb33, ^bb34
^bb33:
%309 = arith.addi %302, %294 : index
cf.br ^bb30(%309 : index)
^bb34:
cf.br ^bb35
^bb35:
%311 = arith.index_cast %302 : index to i64
%312 = llvm.getelementptr %23[%311] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%310 = llvm.load %312 : !llvm.ptr -> i64
%314 = arith.index_cast %302 : index to i64
%315 = llvm.getelementptr %28[%314] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%313 = llvm.load %315 : !llvm.ptr -> i64
%316 = arith.constant 0 : i32
%318 = arith.extsi %316 : i32 to i64
%317 = arith.cmpi eq, %91, %318 : i64
cf.cond_br %317, ^bb36, ^bb37
^bb36:
%320 = arith.index_cast %302 : index to i64
%321 = llvm.getelementptr %43[%320] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%319 = llvm.load %321 : !llvm.ptr -> i64
%322 = arith.addi %319, %310 : i64
%323 = llvm.mlir.addressof @MOD : !llvm.ptr
%324 = llvm.load %323 : !llvm.ptr -> i64
%325 = arith.remsi %322, %324 : i64
%326 = arith.index_cast %302 : index to i64
%327 = llvm.getelementptr %43[%326] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %325, %327 : i64, !llvm.ptr
%329 = arith.index_cast %302 : index to i64
%330 = llvm.getelementptr %48[%329] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%328 = llvm.load %330 : !llvm.ptr -> i64
%331 = arith.addi %328, %313 : i64
%332 = llvm.mlir.addressof @MOD : !llvm.ptr
%333 = llvm.load %332 : !llvm.ptr -> i64
%334 = arith.remsi %331, %333 : i64
%335 = arith.index_cast %302 : index to i64
%336 = llvm.getelementptr %48[%335] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %334, %336 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
%338 = arith.index_cast %302 : index to i64
%339 = llvm.getelementptr %53[%338] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%337 = llvm.load %339 : !llvm.ptr -> i64
%340 = arith.addi %337, %310 : i64
%341 = llvm.mlir.addressof @MOD : !llvm.ptr
%342 = llvm.load %341 : !llvm.ptr -> i64
%343 = arith.remsi %340, %342 : i64
%344 = arith.index_cast %302 : index to i64
%345 = llvm.getelementptr %53[%344] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %343, %345 : i64, !llvm.ptr
%347 = arith.index_cast %302 : index to i64
%348 = llvm.getelementptr %58[%347] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%346 = llvm.load %348 : !llvm.ptr -> i64
%349 = arith.addi %346, %313 : i64
%350 = llvm.mlir.addressof @MOD : !llvm.ptr
%351 = llvm.load %350 : !llvm.ptr -> i64
%352 = arith.remsi %349, %351 : i64
%353 = arith.index_cast %302 : index to i64
%354 = llvm.getelementptr %58[%353] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %352, %354 : i64, !llvm.ptr
%356 = arith.index_cast %302 : index to i32
%357 = arith.trunci %141 : i64 to i32
%355 = arith.addi %356, %357 : i32
%358 = arith.extsi %355 : i32 to i64
%359 = arith.constant 0 : i32
%361 = arith.extsi %359 : i32 to i64
%360 = arith.cmpi sge, %358, %361 : i64
%362 = scf.if %360 -> (i1) {
%363 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%364 = llvm.load %363 : !llvm.ptr -> i64
%365 = arith.cmpi slt, %358, %364 : i64
scf.yield %365 : i1
} else {
%366 = arith.constant false
scf.yield %366 : i1
}
cf.cond_br %362, ^bb39, ^bb40
^bb39:
%368 = llvm.getelementptr %43[%358] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%367 = llvm.load %368 : !llvm.ptr -> i64
%369 = arith.addi %367, %310 : i64
%370 = llvm.mlir.addressof @MOD : !llvm.ptr
%371 = llvm.load %370 : !llvm.ptr -> i64
%372 = arith.remsi %369, %371 : i64
%373 = llvm.getelementptr %43[%358] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %372, %373 : i64, !llvm.ptr
%374 = llvm.load %145 : !llvm.ptr -> i64
%375 = arith.extsi %374 : i64 to i128
%376 = arith.extsi %310 : i64 to i128
%378 = arith.trunci %375 : i128 to i64
%379 = arith.trunci %376 : i128 to i64
%377 = arith.muli %378, %379 : i64
%380 = arith.extsi %377 : i64 to i128
%382 = llvm.getelementptr %48[%358] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%381 = llvm.load %382 : !llvm.ptr -> i64
%383 = arith.extsi %381 : i64 to i128
%384 = arith.extsi %313 : i64 to i128
%386 = arith.trunci %383 : i128 to i64
%387 = arith.trunci %384 : i128 to i64
%385 = arith.addi %386, %387 : i64
%388 = llvm.mlir.addressof @MOD : !llvm.ptr
%389 = llvm.load %388 : !llvm.ptr -> i64
%390 = arith.extsi %389 : i64 to i128
%392 = arith.trunci %380 : i128 to i64
%393 = arith.trunci %390 : i128 to i64
%391 = arith.remsi %392, %393 : i64
%394 = arith.addi %385, %391 : i64
%395 = llvm.mlir.addressof @MOD : !llvm.ptr
%396 = llvm.load %395 : !llvm.ptr -> i64
%397 = arith.extsi %396 : i64 to i128
%399 = arith.trunci %397 : i128 to i64
%398 = arith.remsi %394, %399 : i64
%400 = llvm.getelementptr %48[%358] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %398, %400 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
cf.br ^bb38
^bb38:
%401 = arith.addi %302, %294 : index
cf.br ^bb30(%401 : index)
^bb32(%402: index):
%403 = arith.constant 0 : i32
%404 = llvm.mlir.addressof @ARR_SIZE : !llvm.ptr
%405 = llvm.load %404 : !llvm.ptr -> i64
%406 = arith.index_cast %403 : i32 to index
%407 = arith.index_cast %405 : i32 to index
%409 = arith.constant 1 : index
%410 = arith.constant -1 : index
%411 = arith.cmpi sle, %406, %407 : index
%408 = arith.select %411, %409, %410 : index
cf.br ^bb42(%406 : index)
^bb42(%412: index):
%413 = arith.cmpi slt, %412, %407 : index
%414 = arith.cmpi sgt, %412, %407 : index
%415 = arith.select %411, %413, %414 : i1
cf.cond_br %415, ^bb43(%412 : index), ^bb44(%412 : index)
^bb43(%416: index):
%418 = arith.index_cast %416 : index to i64
%419 = llvm.getelementptr %43[%418] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%417 = llvm.load %419 : !llvm.ptr -> i64
%420 = arith.index_cast %416 : index to i64
%421 = llvm.getelementptr %23[%420] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %417, %421 : i64, !llvm.ptr
%423 = arith.index_cast %416 : index to i64
%424 = llvm.getelementptr %48[%423] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%422 = llvm.load %424 : !llvm.ptr -> i64
%425 = arith.index_cast %416 : index to i64
%426 = llvm.getelementptr %28[%425] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %422, %426 : i64, !llvm.ptr
%428 = arith.index_cast %416 : index to i64
%429 = llvm.getelementptr %53[%428] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%427 = llvm.load %429 : !llvm.ptr -> i64
%430 = arith.index_cast %416 : index to i64
%431 = llvm.getelementptr %33[%430] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %427, %431 : i64, !llvm.ptr
%433 = arith.index_cast %416 : index to i64
%434 = llvm.getelementptr %58[%433] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%432 = llvm.load %434 : !llvm.ptr -> i64
%435 = arith.index_cast %416 : index to i64
%436 = llvm.getelementptr %38[%435] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %432, %436 : i64, !llvm.ptr
%437 = arith.addi %416, %408 : index
cf.br ^bb42(%437 : index)
^bb44(%438: index):
%439 = arith.addi %80, %72 : index
cf.br ^bb6(%439 : index)
^bb8(%440: index):
%441 = arith.constant 0 : i32
%442 = arith.extsi %441 : i32 to i64
%443 = llvm.mlir.constant(1 : i64) : i64
%444 = llvm.alloca %443 x i64 : (i64) -> !llvm.ptr
llvm.store %442, %444 : i64, !llvm.ptr
%445 = llvm.load %444 : !llvm.ptr -> i64
%447 = llvm.mlir.addressof @OFFSET : !llvm.ptr
%448 = llvm.load %447 : !llvm.ptr -> i64
%449 = llvm.getelementptr %28[%448] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%446 = llvm.load %449 : !llvm.ptr -> i64
%450 = arith.addi %445, %446 : i64
%451 = llvm.mlir.addressof @MOD : !llvm.ptr
%452 = llvm.load %451 : !llvm.ptr -> i64
%453 = arith.remsi %450, %452 : i64
llvm.store %453, %444 : i64, !llvm.ptr
%454 = llvm.load %444 : !llvm.ptr -> i64
%456 = llvm.mlir.addressof @OFFSET : !llvm.ptr
%457 = llvm.load %456 : !llvm.ptr -> i64
%458 = llvm.getelementptr %38[%457] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%455 = llvm.load %458 : !llvm.ptr -> i64
%459 = arith.addi %454, %455 : i64
%460 = llvm.mlir.addressof @MOD : !llvm.ptr
%461 = llvm.load %460 : !llvm.ptr -> i64
%462 = arith.remsi %459, %461 : i64
llvm.store %462, %444 : i64, !llvm.ptr
func.call @free(%58) : (!llvm.ptr) -> ()
func.call @free(%53) : (!llvm.ptr) -> ()
func.call @free(%48) : (!llvm.ptr) -> ()
func.call @free(%43) : (!llvm.ptr) -> ()
func.call @free(%38) : (!llvm.ptr) -> ()
func.call @free(%33) : (!llvm.ptr) -> ()
func.call @free(%28) : (!llvm.ptr) -> ()
func.call @free(%23) : (!llvm.ptr) -> ()
%471 = llvm.load %444 : !llvm.ptr -> i64
func.return %471 : i64
}
func.func @main() -> i32 {
%472 = arith.constant 9999995705032704 : i32
%473 = arith.extsi %472 : i32 to i64
%474 = arith.constant 0 : i32
%475 = arith.extsi %474 : i32 to i64
%476 = llvm.mlir.constant(1 : i64) : i64
%477 = llvm.alloca %476 x i64 : (i64) -> !llvm.ptr
llvm.store %475, %477 : i64, !llvm.ptr
%478 = llvm.load %477 : !llvm.ptr -> i64
%480 = arith.constant 3 : i32
%481 = arith.constant 1 : i32
%482 = arith.extsi %480 : i32 to i64
%483 = arith.extsi %481 : i32 to i64
%479 = func.call @M_power2_bases(%473, %482, %483) : (i64, i64, i64) -> i64
%484 = arith.addi %478, %479 : i64
%485 = llvm.mlir.addressof @MOD : !llvm.ptr
%486 = llvm.load %485 : !llvm.ptr -> i64
%487 = arith.remsi %484, %486 : i64
llvm.store %487, %477 : i64, !llvm.ptr
%488 = llvm.load %477 : !llvm.ptr -> i64
%490 = arith.constant 4 : i32
%491 = arith.constant 1 : i32
%492 = arith.extsi %490 : i32 to i64
%493 = arith.extsi %491 : i32 to i64
%489 = func.call @M_power2_bases(%473, %492, %493) : (i64, i64, i64) -> i64
%494 = arith.addi %488, %489 : i64
%495 = llvm.mlir.addressof @MOD : !llvm.ptr
%496 = llvm.load %495 : !llvm.ptr -> i64
%497 = arith.remsi %494, %496 : i64
llvm.store %497, %477 : i64, !llvm.ptr
%498 = llvm.load %477 : !llvm.ptr -> i64
%500 = arith.constant 4 : i32
%501 = arith.constant 2 : i32
%502 = arith.extsi %500 : i32 to i64
%503 = arith.extsi %501 : i32 to i64
%499 = func.call @M_power2_bases(%473, %502, %503) : (i64, i64, i64) -> i64
%504 = arith.addi %498, %499 : i64
%505 = llvm.mlir.addressof @MOD : !llvm.ptr
%506 = llvm.load %505 : !llvm.ptr -> i64
%507 = arith.remsi %504, %506 : i64
llvm.store %507, %477 : i64, !llvm.ptr
%508 = llvm.load %477 : !llvm.ptr -> i64
%510 = arith.constant 5 : i32
%511 = arith.constant 1 : i32
%512 = arith.extsi %510 : i32 to i64
%513 = arith.extsi %511 : i32 to i64
%509 = func.call @M_power2_bases(%473, %512, %513) : (i64, i64, i64) -> i64
%514 = arith.addi %508, %509 : i64
%515 = llvm.mlir.addressof @MOD : !llvm.ptr
%516 = llvm.load %515 : !llvm.ptr -> i64
%517 = arith.remsi %514, %516 : i64
llvm.store %517, %477 : i64, !llvm.ptr
%518 = llvm.load %477 : !llvm.ptr -> i64
%520 = arith.constant 5 : i32
%521 = arith.constant 2 : i32
%522 = arith.extsi %520 : i32 to i64
%523 = arith.extsi %521 : i32 to i64
%519 = func.call @M_power2_bases(%473, %522, %523) : (i64, i64, i64) -> i64
%524 = arith.addi %518, %519 : i64
%525 = llvm.mlir.addressof @MOD : !llvm.ptr
%526 = llvm.load %525 : !llvm.ptr -> i64
%527 = arith.remsi %524, %526 : i64
llvm.store %527, %477 : i64, !llvm.ptr
%528 = llvm.load %477 : !llvm.ptr -> i64
%530 = arith.constant 5 : i32
%531 = arith.constant 3 : i32
%532 = arith.extsi %530 : i32 to i64
%533 = arith.extsi %531 : i32 to i64
%529 = func.call @M_power2_bases(%473, %532, %533) : (i64, i64, i64) -> i64
%534 = arith.addi %528, %529 : i64
%535 = llvm.mlir.addressof @MOD : !llvm.ptr
%536 = llvm.load %535 : !llvm.ptr -> i64
%537 = arith.remsi %534, %536 : i64
llvm.store %537, %477 : i64, !llvm.ptr
%538 = llvm.load %477 : !llvm.ptr -> i64
%540 = arith.constant 6 : i32
%541 = arith.constant 1 : i32
%542 = arith.extsi %540 : i32 to i64
%543 = arith.extsi %541 : i32 to i64
%539 = func.call @M_power2_bases(%473, %542, %543) : (i64, i64, i64) -> i64
%544 = arith.addi %538, %539 : i64
%545 = llvm.mlir.addressof @MOD : !llvm.ptr
%546 = llvm.load %545 : !llvm.ptr -> i64
%547 = arith.remsi %544, %546 : i64
llvm.store %547, %477 : i64, !llvm.ptr
%548 = llvm.load %477 : !llvm.ptr -> i64
%550 = arith.constant 6 : i32
%551 = arith.constant 2 : i32
%552 = arith.extsi %550 : i32 to i64
%553 = arith.extsi %551 : i32 to i64
%549 = func.call @M_power2_bases(%473, %552, %553) : (i64, i64, i64) -> i64
%554 = arith.addi %548, %549 : i64
%555 = llvm.mlir.addressof @MOD : !llvm.ptr
%556 = llvm.load %555 : !llvm.ptr -> i64
%557 = arith.remsi %554, %556 : i64
llvm.store %557, %477 : i64, !llvm.ptr
%558 = llvm.load %477 : !llvm.ptr -> i64
%560 = arith.constant 6 : i32
%561 = arith.constant 3 : i32
%562 = arith.extsi %560 : i32 to i64
%563 = arith.extsi %561 : i32 to i64
%559 = func.call @M_power2_bases(%473, %562, %563) : (i64, i64, i64) -> i64
%564 = arith.addi %558, %559 : i64
%565 = llvm.mlir.addressof @MOD : !llvm.ptr
%566 = llvm.load %565 : !llvm.ptr -> i64
%567 = arith.remsi %564, %566 : i64
llvm.store %567, %477 : i64, !llvm.ptr
%568 = llvm.load %477 : !llvm.ptr -> i64
%570 = arith.constant 6 : i32
%571 = arith.constant 4 : i32
%572 = arith.extsi %570 : i32 to i64
%573 = arith.extsi %571 : i32 to i64
%569 = func.call @M_power2_bases(%473, %572, %573) : (i64, i64, i64) -> i64
%574 = arith.addi %568, %569 : i64
%575 = llvm.mlir.addressof @MOD : !llvm.ptr
%576 = llvm.load %575 : !llvm.ptr -> i64
%577 = arith.remsi %574, %576 : i64
llvm.store %577, %477 : i64, !llvm.ptr
%578 = llvm.mlir.addressof @str_0 : !llvm.ptr
%579 = llvm.load %477 : !llvm.ptr -> i64
%580 = llvm.call @printf(%578, %579) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%581 = arith.constant 0 : i32
func.return %581 : i32
}
}