Problem 529
10-substrings — DFA + Berlekamp-Massey + poly exponentiation at n=10^18.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^3) | ? |
|---|
| Space complexity | O(n^2) | ? |
|---|
| Approach | Flow solution | Not curated |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 529
# 10-substrings — DFA + Berlekamp-Massey + poly exponentiation at n=10^18.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000000007
const CAP: i64 = 8192
const MAXS: i64 = 4096
const N_EXP: i64 = 1000000000000000000
function modpow(base0: i64, exp0: i64, mod: i64) -> i64 {
let mut r: i64 = 1
let mut b: i64 = base0 % mod
let mut e: i64 = exp0
while e > 0 {
if (e & 1) == 1 { r = ((r as i128) * (b as i128) % (mod as i128)) as i64 }
b = ((b as i128) * (b as i128) % (mod as i128)) as i64
e = e / 2
}
return r
}
function hslot(key: i64, keys: ptr<i64>, used: ptr<i8>) -> i64 {
let mut h: i64 = key % CAP
if h < 0 { h = h + CAP }
while used[h] == 1 && keys[h] != key {
h = h + 1
if h == CAP { h = 0 }
}
return h
}
function pack_key(dlen: i32, digs: ptr<i8>, uncovered: i32) -> i64 {
let mut p: i64 = 0
let mut i: i32 = 0
while i < dlen {
p = p * 10 + (digs[i] as i64)
i = i + 1
}
return (uncovered as i64) * 10000000000 + p
}
function decode_digs(key: i64, dlen: ptr<i32>, digs: ptr<i8>, uncovered: ptr<i32>) -> void {
uncovered[0] = (key / 10000000000) as i32
let mut p: i64 = key % 10000000000
if p == 0 {
dlen[0] = 0
return
}
let tmp: ptr<i8> = calloc(16, 1)
let mut n: i32 = 0
while p > 0 {
tmp[n] = (p % 10) as i8
p = p / 10
n = n + 1
}
dlen[0] = n
let mut i: i32 = 0
while i < n {
digs[i] = tmp[n - 1 - i]
i = i + 1
}
free(tmp)
}
function dig_sum(st: i64, dlen: i32, digs_arr: ptr<i8>) -> i32 {
let mut s: i32 = 0
let mut i: i32 = 0
while i < dlen {
s = s + (digs_arr[st * 12 + (i as i64)] as i32)
i = i + 1
}
return s
}
function try_transition(
st: i64, dlen: i32, sum_d: i32, uncovered: i32, digit: i32,
digs_arr: ptr<i8>, odlen: ptr<i32>, odigs: ptr<i8>, ou: ptr<i32>
) -> i32 {
let nd: ptr<i8> = calloc(16, 1)
if nd == null { return 0 }
let mut i: i32 = 0
while i < dlen {
nd[i] = digs_arr[st * 12 + (i as i64)]
i = i + 1
}
nd[dlen] = digit as i8
let mut nlen: i32 = dlen + 1
let mut nu: i32 = uncovered + 1
let mut nsum: i32 = sum_d + digit
while nsum > 10 {
if nlen == nu { free(nd); return 0 }
nsum = nsum - (nd[0] as i32)
let mut j: i32 = 0
while j + 1 < nlen {
nd[j] = nd[j + 1]
j = j + 1
}
nlen = nlen - 1
}
if nsum == 10 { nu = 0 }
odlen[0] = nlen
i = 0
while i < nlen {
odigs[i] = nd[i]
i = i + 1
}
ou[0] = nu
free(nd)
return 1
}
function poly_mul_mod(a: ptr<i64>, b: ptr<i64>, out: ptr<i64>, L: i64, REC: ptr<i64>) -> void {
let tmp: ptr<i64> = calloc(2 * L, 8)
if tmp == null { return }
let mut i: i64 = 0
while i < 2 * L { tmp[i] = 0; i = i + 1 }
i = 0
while i < L {
let mut j: i64 = 0
while j < L {
tmp[i + j] = (tmp[i + j] + ((a[i] as i128) * (b[j] as i128) % (MOD as i128)) as i64) % MOD
j = j + 1
}
i = i + 1
}
i = 2 * L - 2
while i >= L {
let c: i64 = tmp[i]
if c != 0 {
let mut k: i64 = 0
while k < L {
tmp[i - 1 - k] = (tmp[i - 1 - k] + ((c as i128) * (REC[k] as i128) % (MOD as i128)) as i64) % MOD
k = k + 1
}
}
i = i - 1
}
i = 0
while i < L {
out[i] = tmp[i] % MOD
i = i + 1
}
free(tmp)
}
function main() -> i32 {
let sk: ptr<i64> = calloc(CAP, 8)
let su: ptr<i8> = calloc(CAP, 1)
let sid: ptr<i32> = calloc(CAP, 4)
let trans: ptr<i32> = calloc(MAXS * 9, 4)
let accept: ptr<i8> = calloc(MAXS, 1)
let uncovered_arr: ptr<i32> = calloc(MAXS, 4)
let dlen_arr: ptr<i32> = calloc(MAXS, 4)
let digs_arr: ptr<i8> = calloc(MAXS * 12, 1)
if sk == null || trans == null { return 1 }
let start_key: i64 = 0
let s0: i64 = hslot(start_key, sk, su)
su[s0] = 1
sk[s0] = start_key
sid[s0] = 0
uncovered_arr[0] = 0
dlen_arr[0] = 0
let mut ns: i32 = 1
let mut q: ptr<i64> = calloc(MAXS, 8)
q[0] = 0
let mut qh: i64 = 0
let mut qt: i64 = 1
while qh < qt {
let cur: i64 = q[qh]
qh = qh + 1
let sum_d: i32 = dig_sum(cur, dlen_arr[cur as i32], digs_arr)
let dlen: i32 = dlen_arr[cur as i32]
let uncovered: i32 = uncovered_arr[cur as i32]
if dlen > 0 && uncovered == 0 { accept[cur] = 1 }
let mut digit: i32 = 1
while digit <= 9 {
let odlen: ptr<i32> = calloc(1, 4)
let odigs: ptr<i8> = calloc(12, 1)
let ou: ptr<i32> = calloc(1, 4)
if try_transition(cur, dlen, sum_d, uncovered, digit, digs_arr, odlen, odigs, ou) == 1 {
let nkey: i64 = pack_key(odlen[0], odigs, ou[0])
let sl: i64 = hslot(nkey, sk, su)
let mut nid: i32 = 0
if su[sl] == 0 {
su[sl] = 1
sk[sl] = nkey
sid[sl] = ns
uncovered_arr[ns] = ou[0]
dlen_arr[ns] = odlen[0]
let mut di: i32 = 0
while di < odlen[0] {
digs_arr[ns * 12 + di] = odigs[di]
di = di + 1
}
q[qt] = ns as i64
qt = qt + 1
nid = ns
ns = ns + 1
} else {
nid = sid[sl]
}
trans[cur * 9 + (digit - 1)] = nid
} else {
trans[cur * 9 + (digit - 1)] = -1
}
free(odlen); free(odigs); free(ou)
digit = digit + 1
}
}
let S: i32 = ns
let nterms: i32 = 2 * S + 5
let E: ptr<i64> = calloc(nterms as i64, 8)
let dp: ptr<i64> = calloc(S as i64, 8)
let ndp: ptr<i64> = calloc(S as i64, 8)
if E == null || dp == null { return 1 }
dp[0] = 1
let mut t: i32 = 1
while t < nterms {
let mut i: i32 = 0
while i < S {
ndp[i] = 0
i = i + 1
}
i = 0
while i < S {
let v: i64 = dp[i]
if v != 0 {
let mut d: i32 = 1
while d <= 9 {
let j: i32 = trans[i * 9 + (d - 1)]
if j >= 0 {
ndp[j] = (ndp[j] + v) % MOD
}
d = d + 1
}
}
i = i + 1
}
let mut tot: i64 = 0
i = 0
while i < S {
if accept[i] == 1 { tot = (tot + ndp[i]) % MOD }
dp[i] = ndp[i]
i = i + 1
}
E[t] = tot
t = t + 1
}
# Berlekamp-Massey
let bm_cap: i64 = nterms as i64 + 10
let C: ptr<i64> = calloc(bm_cap, 8)
let B: ptr<i64> = calloc(bm_cap, 8)
C[0] = 1
B[0] = 1
let mut clen: i64 = 1
let mut blen: i64 = 1
let mut Lbm: i64 = 0
let mut m: i64 = 1
let mut bval: i64 = 1
let mut nn: i64 = 0
let mut jj: i64 = 0
while nn < (nterms as i64) {
let mut d: i64 = E[nn]
jj = 1
while jj <= Lbm {
d = (d + ((C[jj] as i128) * (E[nn - jj] as i128) % (MOD as i128)) as i64) % MOD
jj = jj + 1
}
if d == 0 {
m = m + 1
} else {
let coef: i64 = ((d as i128) * (modpow(bval, MOD - 2, MOD) as i128) % (MOD as i128)) as i64
let T: ptr<i64> = calloc(bm_cap, 8)
let tlen: i64 = clen
jj = 0
while jj < tlen { T[jj] = C[jj]; jj = jj + 1 }
jj = 0
while jj < blen {
let idx: i64 = jj + m
while clen <= idx { C[clen] = 0; clen = clen + 1 }
C[idx] = (C[idx] - ((coef as i128) * (B[jj] as i128) % (MOD as i128)) as i64) % MOD
if C[idx] < 0 { C[idx] = C[idx] + MOD }
jj = jj + 1
}
if 2 * Lbm <= nn {
jj = 0
while jj < tlen { B[jj] = T[jj]; jj = jj + 1 }
blen = tlen
Lbm = nn + 1 - Lbm
bval = d
m = 1
} else {
m = m + 1
}
free(T)
}
nn = nn + 1
}
let L: i64 = Lbm
let REC: ptr<i64> = calloc(L, 8)
jj = 1
while jj <= L {
REC[jj - 1] = (-C[jj]) % MOD
if REC[jj - 1] < 0 { REC[jj - 1] = REC[jj - 1] + MOD }
jj = jj + 1
}
free(C); free(B)
let base: ptr<i64> = calloc(L, 8)
let res: ptr<i64> = calloc(L, 8)
let tmp: ptr<i64> = calloc(L, 8)
let tmp2: ptr<i64> = calloc(L, 8)
base[0] = 1
if L > 1 { base[1] = 1 }
res[0] = 1
let mut e: i64 = N_EXP
let mut i2: i64 = 0
while e > 0 {
if (e & 1) == 1 {
poly_mul_mod(res, base, tmp, L, REC)
i2 = 0
while i2 < L { res[i2] = tmp[i2]; i2 = i2 + 1 }
}
poly_mul_mod(base, base, tmp2, L, REC)
i2 = 0
while i2 < L { base[i2] = tmp2[i2]; i2 = i2 + 1 }
e = e / 2
}
let mut ans: i64 = 0
i2 = 0
while i2 < L {
ans = (ans + ((res[i2] as i128) * (E[i2] as i128) % (MOD as i128)) as i64) % MOD
i2 = i2 + 1
}
printf("%lld\n", ans)
free(sk); free(su); free(sid); free(trans); free(accept)
free(uncovered_arr); free(dlen_arr); free(digs_arr); free(q)
free(E); free(dp); free(ndp); free(REC)
free(base); free(res); free(tmp); free(tmp2)
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 modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod);
int64_t hslot_i64_ptr_i64_ptr_i8(int64_t key, int64_t* keys, int8_t* used);
int64_t pack_key_i32_ptr_i8_i32(int32_t dlen, int8_t* digs, int32_t uncovered);
void decode_digs_i64_ptr_i32_ptr_i8_ptr_i32(int64_t key, int32_t* dlen, int8_t* digs, int32_t* uncovered);
int32_t dig_sum_i64_i32_ptr_i8(int64_t st, int32_t dlen, int8_t* digs_arr);
int32_t try_transition_i64_i32_i32_i32_i32_ptr_i8_ptr_i32_ptr_i8_ptr_i32(int64_t st, int32_t dlen, int32_t sum_d, int32_t uncovered, int32_t digit, int8_t* digs_arr, int32_t* odlen, int8_t* odigs, int32_t* ou);
void poly_mul_mod_ptr_i64_ptr_i64_ptr_i64_i64_ptr_i64(int64_t* a, int64_t* b, int64_t* out, int64_t L, int64_t* REC);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int64_t CAP = 8192;
static const int64_t MAXS = 4096;
static const int64_t N_EXP = 1000000000000000000;
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod) {
int64_t r = 1;
int64_t b = FLOW_CHECKED_MOD((base0), (mod));
int64_t e = exp0;
while (e > 0) {
if ((e & 1) == 1) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(b)))), (((__int128)(mod))))));
}
b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(b)) * ((__int128)(b)))), (((__int128)(mod))))));
e = FLOW_CHECKED_DIV((e), (2));
}
return r;
}
int64_t hslot_i64_ptr_i64_ptr_i8(int64_t key, int64_t* keys, int8_t* used) {
int64_t h = FLOW_CHECKED_MOD((key), (CAP));
if (h < 0) {
h = (h + CAP);
}
while ((used[h] == 1 && keys[h] != key)) {
h = (h + 1);
if (h == CAP) {
h = 0;
}
}
return h;
}
int64_t pack_key_i32_ptr_i8_i32(int32_t dlen, int8_t* digs, int32_t uncovered) {
int64_t p = 0;
int32_t i = 0;
while (i < dlen) {
p = ((p * 10) + ((int64_t)(digs[i])));
i = (i + 1);
}
return ((((int64_t)(uncovered)) * 10000000000) + p);
}
void decode_digs_i64_ptr_i32_ptr_i8_ptr_i32(int64_t key, int32_t* dlen, int8_t* digs, int32_t* uncovered) {
uncovered[0] = ((int32_t)(FLOW_CHECKED_DIV((key), (10000000000))));
int64_t p = FLOW_CHECKED_MOD((key), (10000000000));
if (p == 0) {
dlen[0] = 0;
return;
}
int8_t* tmp = (int8_t*)(calloc(16, 1));
int32_t n = 0;
while (p > 0) {
tmp[n] = ((int8_t)(FLOW_CHECKED_MOD((p), (10))));
p = FLOW_CHECKED_DIV((p), (10));
n = (n + 1);
}
dlen[0] = n;
int32_t i = 0;
while (i < n) {
digs[i] = tmp[((n - 1) - i)];
i = (i + 1);
}
free(tmp);
}
int32_t dig_sum_i64_i32_ptr_i8(int64_t st, int32_t dlen, int8_t* digs_arr) {
int32_t s = 0;
int32_t i = 0;
while (i < dlen) {
s = (s + ((int32_t)(digs_arr[((st * 12) + ((int64_t)(i)))])));
i = (i + 1);
}
return s;
}
int32_t try_transition_i64_i32_i32_i32_i32_ptr_i8_ptr_i32_ptr_i8_ptr_i32(int64_t st, int32_t dlen, int32_t sum_d, int32_t uncovered, int32_t digit, int8_t* digs_arr, int32_t* odlen, int8_t* odigs, int32_t* ou) {
int8_t* nd = (int8_t*)(calloc(16, 1));
if (nd == NULL) {
return 0;
}
int32_t i = 0;
while (i < dlen) {
nd[i] = digs_arr[((st * 12) + ((int64_t)(i)))];
i = (i + 1);
}
nd[dlen] = ((int8_t)(digit));
int32_t nlen = (dlen + 1);
int32_t nu = (uncovered + 1);
int32_t nsum = (sum_d + digit);
while (nsum > 10) {
if (nlen == nu) {
free(nd);
return 0;
}
nsum = (nsum - ((int32_t)(nd[0])));
int32_t j = 0;
while ((j + 1) < nlen) {
nd[j] = nd[(j + 1)];
j = (j + 1);
}
nlen = (nlen - 1);
}
if (nsum == 10) {
nu = 0;
}
odlen[0] = nlen;
i = 0;
while (i < nlen) {
odigs[i] = nd[i];
i = (i + 1);
}
ou[0] = nu;
free(nd);
return 1;
}
void poly_mul_mod_ptr_i64_ptr_i64_ptr_i64_i64_ptr_i64(int64_t* a, int64_t* b, int64_t* out, int64_t L, int64_t* REC) {
int64_t* tmp = (int64_t*)(calloc((2 * L), 8));
if (tmp == NULL) {
return;
}
int64_t i = 0;
while (i < (2 * L)) {
tmp[i] = 0;
i = (i + 1);
}
i = 0;
while (i < L) {
int64_t j = 0;
while (j < L) {
tmp[(i + j)] = FLOW_CHECKED_MOD(((tmp[(i + j)] + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a[i])) * ((__int128)(b[j])))), (((__int128)(MOD)))))))), (MOD));
j = (j + 1);
}
i = (i + 1);
}
i = ((2 * L) - 2);
while (i >= L) {
int64_t c = tmp[i];
if (c != 0) {
int64_t k = 0;
while (k < L) {
tmp[((i - 1) - k)] = FLOW_CHECKED_MOD(((tmp[((i - 1) - k)] + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(c)) * ((__int128)(REC[k])))), (((__int128)(MOD)))))))), (MOD));
k = (k + 1);
}
}
i = (i - 1);
}
i = 0;
while (i < L) {
out[i] = FLOW_CHECKED_MOD((tmp[i]), (MOD));
i = (i + 1);
}
free(tmp);
}
int32_t main(void) {
int64_t* sk = (int64_t*)(calloc(CAP, 8));
int8_t* su = (int8_t*)(calloc(CAP, 1));
int32_t* sid = (int32_t*)(calloc(CAP, 4));
int32_t* trans = (int32_t*)(calloc((MAXS * 9), 4));
int8_t* accept = (int8_t*)(calloc(MAXS, 1));
int32_t* uncovered_arr = (int32_t*)(calloc(MAXS, 4));
int32_t* dlen_arr = (int32_t*)(calloc(MAXS, 4));
int8_t* digs_arr = (int8_t*)(calloc((MAXS * 12), 1));
if ((sk == NULL || trans == NULL)) {
return 1;
}
int64_t start_key = 0;
int64_t s0 = hslot_i64_ptr_i64_ptr_i8(start_key, sk, su);
su[s0] = 1;
sk[s0] = start_key;
sid[s0] = 0;
uncovered_arr[0] = 0;
dlen_arr[0] = 0;
int32_t ns = 1;
int64_t* q = (int64_t*)(calloc(MAXS, 8));
q[0] = 0;
int64_t qh = 0;
int64_t qt = 1;
while (qh < qt) {
int64_t cur = q[qh];
qh = (qh + 1);
int32_t sum_d = dig_sum_i64_i32_ptr_i8(cur, dlen_arr[((int32_t)(cur))], digs_arr);
int32_t dlen = dlen_arr[((int32_t)(cur))];
int32_t uncovered = uncovered_arr[((int32_t)(cur))];
if ((dlen > 0 && uncovered == 0)) {
accept[cur] = 1;
}
int32_t digit = 1;
while (digit <= 9) {
int32_t* odlen = (int32_t*)(calloc(1, 4));
int8_t* odigs = (int8_t*)(calloc(12, 1));
int32_t* ou = (int32_t*)(calloc(1, 4));
if (try_transition_i64_i32_i32_i32_i32_ptr_i8_ptr_i32_ptr_i8_ptr_i32(cur, dlen, sum_d, uncovered, digit, digs_arr, odlen, odigs, ou) == 1) {
int64_t nkey = pack_key_i32_ptr_i8_i32(odlen[0], odigs, ou[0]);
int64_t sl = hslot_i64_ptr_i64_ptr_i8(nkey, sk, su);
int32_t nid = 0;
if (su[sl] == 0) {
su[sl] = 1;
sk[sl] = nkey;
sid[sl] = ns;
uncovered_arr[ns] = ou[0];
dlen_arr[ns] = odlen[0];
int32_t di = 0;
while (di < odlen[0]) {
digs_arr[((ns * 12) + di)] = odigs[di];
di = (di + 1);
}
q[qt] = ((int64_t)(ns));
qt = (qt + 1);
nid = ns;
ns = (ns + 1);
} else {
nid = sid[sl];
}
trans[((cur * 9) + (digit - 1))] = nid;
} else {
trans[((cur * 9) + (digit - 1))] = (-1);
}
free(odlen);
free(odigs);
free(ou);
digit = (digit + 1);
}
}
int32_t S = ns;
int32_t nterms = ((2 * S) + 5);
int64_t* E = (int64_t*)(calloc(((int64_t)(nterms)), 8));
int64_t* dp = (int64_t*)(calloc(((int64_t)(S)), 8));
int64_t* ndp = (int64_t*)(calloc(((int64_t)(S)), 8));
if ((E == NULL || dp == NULL)) {
return 1;
}
dp[0] = 1;
int32_t t = 1;
while (t < nterms) {
int32_t i = 0;
while (i < S) {
ndp[i] = 0;
i = (i + 1);
}
i = 0;
while (i < S) {
int64_t v = dp[i];
if (v != 0) {
int32_t d = 1;
while (d <= 9) {
int32_t j = trans[((i * 9) + (d - 1))];
if (j >= 0) {
ndp[j] = FLOW_CHECKED_MOD(((ndp[j] + v)), (MOD));
}
d = (d + 1);
}
}
i = (i + 1);
}
int64_t tot = 0;
i = 0;
while (i < S) {
if (accept[i] == 1) {
tot = FLOW_CHECKED_MOD(((tot + ndp[i])), (MOD));
}
dp[i] = ndp[i];
i = (i + 1);
}
E[t] = tot;
t = (t + 1);
}
int64_t bm_cap = (((int64_t)(nterms)) + 10);
int64_t* C = (int64_t*)(calloc(bm_cap, 8));
int64_t* B = (int64_t*)(calloc(bm_cap, 8));
C[0] = 1;
B[0] = 1;
int64_t clen = 1;
int64_t blen = 1;
int64_t Lbm = 0;
int64_t m = 1;
int64_t bval = 1;
int64_t nn = 0;
int64_t jj = 0;
while (nn < ((int64_t)(nterms))) {
int64_t d = E[nn];
jj = 1;
while (jj <= Lbm) {
d = FLOW_CHECKED_MOD(((d + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(C[jj])) * ((__int128)(E[(nn - jj)])))), (((__int128)(MOD)))))))), (MOD));
jj = (jj + 1);
}
if (d == 0) {
m = (m + 1);
} else {
int64_t coef = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(d)) * ((__int128)(modpow_i64_i64_i64(bval, (MOD - 2), MOD))))), (((__int128)(MOD))))));
int64_t* T = (int64_t*)(calloc(bm_cap, 8));
int64_t tlen = clen;
jj = 0;
while (jj < tlen) {
T[jj] = C[jj];
jj = (jj + 1);
}
jj = 0;
while (jj < blen) {
int64_t idx = (jj + m);
while (clen <= idx) {
C[clen] = 0;
clen = (clen + 1);
}
C[idx] = FLOW_CHECKED_MOD(((C[idx] - ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(coef)) * ((__int128)(B[jj])))), (((__int128)(MOD)))))))), (MOD));
if (C[idx] < 0) {
C[idx] = (C[idx] + MOD);
}
jj = (jj + 1);
}
if ((2 * Lbm) <= nn) {
jj = 0;
while (jj < tlen) {
B[jj] = T[jj];
jj = (jj + 1);
}
blen = tlen;
Lbm = ((nn + 1) - Lbm);
bval = d;
m = 1;
} else {
m = (m + 1);
}
free(T);
}
nn = (nn + 1);
}
int64_t L = Lbm;
int64_t* REC = (int64_t*)(calloc(L, 8));
jj = 1;
while (jj <= L) {
REC[(jj - 1)] = FLOW_CHECKED_MOD(((-C[jj])), (MOD));
if (REC[(jj - 1)] < 0) {
REC[(jj - 1)] = (REC[(jj - 1)] + MOD);
}
jj = (jj + 1);
}
free(C);
free(B);
int64_t* base = (int64_t*)(calloc(L, 8));
int64_t* res = (int64_t*)(calloc(L, 8));
int64_t* tmp = (int64_t*)(calloc(L, 8));
int64_t* tmp2 = (int64_t*)(calloc(L, 8));
base[0] = 1;
if (L > 1) {
base[1] = 1;
}
res[0] = 1;
int64_t e = N_EXP;
int64_t i2 = 0;
while (e > 0) {
if ((e & 1) == 1) {
poly_mul_mod_ptr_i64_ptr_i64_ptr_i64_i64_ptr_i64(res, base, tmp, L, REC);
i2 = 0;
while (i2 < L) {
res[i2] = tmp[i2];
i2 = (i2 + 1);
}
}
poly_mul_mod_ptr_i64_ptr_i64_ptr_i64_i64_ptr_i64(base, base, tmp2, L, REC);
i2 = 0;
while (i2 < L) {
base[i2] = tmp2[i2];
i2 = (i2 + 1);
}
e = FLOW_CHECKED_DIV((e), (2));
}
int64_t ans = 0;
i2 = 0;
while (i2 < L) {
ans = FLOW_CHECKED_MOD(((ans + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(res[i2])) * ((__int128)(E[i2])))), (((__int128)(MOD)))))))), (MOD));
i2 = (i2 + 1);
}
printf("%lld\n", ans);
free(sk);
free(su);
free(sid);
free(trans);
free(accept);
free(uncovered_arr);
free(dlen_arr);
free(digs_arr);
free(q);
free(E);
free(dp);
free(ndp);
free(REC);
free(base);
free(res);
free(tmp);
free(tmp2);
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) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
// Constant: CAP
llvm.mlir.global internal constant @CAP(8192 : i64) : i64
// Constant: MAXS
llvm.mlir.global internal constant @MAXS(4096 : i64) : i64
// Constant: N_EXP
llvm.mlir.global internal constant @N_EXP(1000000000000000000 : i64) : i64
func.func @modpow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%0 = arith.constant 1 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i64, !llvm.ptr
%4 = arith.remsi %arg0, %arg2 : i64
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i64 : (i64) -> !llvm.ptr
llvm.store %4, %6 : i64, !llvm.ptr
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %8 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%9 = llvm.load %8 : !llvm.ptr -> i64
%10 = arith.constant 0 : i32
%12 = arith.extsi %10 : i32 to i64
%11 = arith.cmpi sgt, %9, %12 : i64
cf.cond_br %11, ^bb1, ^bb2
^bb1:
%13 = llvm.load %8 : !llvm.ptr -> i64
%14 = arith.constant 1 : i32
%16 = arith.extsi %14 : i32 to i64
%15 = arith.andi %13, %16 : i64
%17 = arith.constant 1 : i32
%19 = arith.extsi %17 : i32 to i64
%18 = arith.cmpi eq, %15, %19 : i64
cf.cond_br %18, ^bb3, ^bb4
^bb3:
%20 = llvm.load %3 : !llvm.ptr -> i64
%21 = arith.extsi %20 : i64 to i128
%22 = llvm.load %6 : !llvm.ptr -> i64
%23 = arith.extsi %22 : i64 to i128
%25 = arith.trunci %21 : i128 to i64
%26 = arith.trunci %23 : i128 to i64
%24 = arith.muli %25, %26 : i64
%27 = arith.extsi %arg2 : i64 to i128
%29 = arith.trunci %27 : i128 to i64
%28 = arith.remsi %24, %29 : i64
llvm.store %28, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%30 = llvm.load %6 : !llvm.ptr -> i64
%31 = arith.extsi %30 : i64 to i128
%32 = llvm.load %6 : !llvm.ptr -> i64
%33 = arith.extsi %32 : i64 to i128
%35 = arith.trunci %31 : i128 to i64
%36 = arith.trunci %33 : i128 to i64
%34 = arith.muli %35, %36 : i64
%37 = arith.extsi %arg2 : i64 to i128
%39 = arith.trunci %37 : i128 to i64
%38 = arith.remsi %34, %39 : i64
llvm.store %38, %6 : i64, !llvm.ptr
%40 = llvm.load %8 : !llvm.ptr -> i64
%41 = arith.constant 2 : i32
%43 = arith.extsi %41 : i32 to i64
%42 = arith.divsi %40, %43 : i64
llvm.store %42, %8 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%44 = llvm.load %3 : !llvm.ptr -> i64
func.return %44 : i64
}
func.func @hslot(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> i64 {
%45 = llvm.mlir.addressof @CAP : !llvm.ptr
%46 = llvm.load %45 : !llvm.ptr -> i64
%47 = arith.remsi %arg0, %46 : i64
%48 = llvm.mlir.constant(1 : i64) : i64
%49 = llvm.alloca %48 x i64 : (i64) -> !llvm.ptr
llvm.store %47, %49 : i64, !llvm.ptr
%50 = llvm.load %49 : !llvm.ptr -> i64
%51 = arith.constant 0 : i32
%53 = arith.extsi %51 : i32 to i64
%52 = arith.cmpi slt, %50, %53 : i64
cf.cond_br %52, ^bb6, ^bb7
^bb6:
%54 = llvm.load %49 : !llvm.ptr -> i64
%55 = llvm.mlir.addressof @CAP : !llvm.ptr
%56 = llvm.load %55 : !llvm.ptr -> i64
%57 = arith.addi %54, %56 : i64
llvm.store %57, %49 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
cf.br ^bb9
^bb9:
%59 = llvm.load %49 : !llvm.ptr -> i64
%60 = llvm.getelementptr %arg2[%59] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%58 = llvm.load %60 : !llvm.ptr -> i8
%61 = arith.constant 1 : i32
%63 = arith.extsi %58 : i8 to i32
%62 = arith.cmpi eq, %63, %61 : i32
%64 = scf.if %62 -> (i1) {
%66 = llvm.load %49 : !llvm.ptr -> i64
%67 = llvm.getelementptr %arg1[%66] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%65 = llvm.load %67 : !llvm.ptr -> i64
%68 = arith.cmpi ne, %65, %arg0 : i64
scf.yield %68 : i1
} else {
%69 = arith.constant false
scf.yield %69 : i1
}
cf.cond_br %64, ^bb10, ^bb11
^bb10:
%70 = llvm.load %49 : !llvm.ptr -> i64
%71 = arith.constant 1 : i32
%73 = arith.extsi %71 : i32 to i64
%72 = arith.addi %70, %73 : i64
llvm.store %72, %49 : i64, !llvm.ptr
%74 = llvm.load %49 : !llvm.ptr -> i64
%75 = llvm.mlir.addressof @CAP : !llvm.ptr
%76 = llvm.load %75 : !llvm.ptr -> i64
%77 = arith.cmpi eq, %74, %76 : i64
cf.cond_br %77, ^bb12, ^bb13
^bb12:
%78 = arith.constant 0 : i32
%79 = arith.extsi %78 : i32 to i64
llvm.store %79, %49 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
cf.br ^bb9
^bb11:
%80 = llvm.load %49 : !llvm.ptr -> i64
func.return %80 : i64
}
func.func @pack_key(%arg0: i32, %arg1: !llvm.ptr, %arg2: i32) -> i64 {
%81 = arith.constant 0 : i32
%82 = arith.extsi %81 : i32 to i64
%83 = llvm.mlir.constant(1 : i64) : i64
%84 = llvm.alloca %83 x i64 : (i64) -> !llvm.ptr
llvm.store %82, %84 : i64, !llvm.ptr
%85 = arith.constant 0 : i32
%86 = llvm.mlir.constant(1 : i64) : i64
%87 = llvm.alloca %86 x i32 : (i64) -> !llvm.ptr
llvm.store %85, %87 : i32, !llvm.ptr
cf.br ^bb15
^bb15:
%88 = llvm.load %87 : !llvm.ptr -> i32
%89 = arith.cmpi slt, %88, %arg0 : i32
cf.cond_br %89, ^bb16, ^bb17
^bb16:
%90 = llvm.load %84 : !llvm.ptr -> i64
%91 = arith.constant 10 : i32
%93 = arith.extsi %91 : i32 to i64
%92 = arith.muli %90, %93 : i64
%95 = llvm.load %87 : !llvm.ptr -> i32
%96 = arith.extsi %95 : i32 to i64
%97 = llvm.getelementptr %arg1[%96] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%94 = llvm.load %97 : !llvm.ptr -> i8
%98 = arith.extsi %94 : i8 to i64
%99 = arith.addi %92, %98 : i64
llvm.store %99, %84 : i64, !llvm.ptr
%100 = llvm.load %87 : !llvm.ptr -> i32
%101 = arith.constant 1 : i32
%102 = arith.addi %100, %101 : i32
llvm.store %102, %87 : i32, !llvm.ptr
cf.br ^bb15
^bb17:
%103 = arith.extsi %arg2 : i32 to i64
%104 = arith.constant 5705032704 : i32
%106 = arith.extsi %104 : i32 to i64
%105 = arith.muli %103, %106 : i64
%107 = llvm.load %84 : !llvm.ptr -> i64
%108 = arith.addi %105, %107 : i64
func.return %108 : i64
}
func.func @decode_digs(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr) -> () {
%109 = arith.constant 5705032704 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.divsi %arg0, %111 : i64
%112 = arith.trunci %110 : i64 to i32
%113 = arith.constant 0 : i32
%114 = arith.extsi %113 : i32 to i64
%115 = llvm.getelementptr %arg3[%114] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %112, %115 : i32, !llvm.ptr
%116 = arith.constant 5705032704 : i32
%118 = arith.extsi %116 : i32 to i64
%117 = arith.remsi %arg0, %118 : i64
%119 = llvm.mlir.constant(1 : i64) : i64
%120 = llvm.alloca %119 x i64 : (i64) -> !llvm.ptr
llvm.store %117, %120 : i64, !llvm.ptr
%121 = llvm.load %120 : !llvm.ptr -> i64
%122 = arith.constant 0 : i32
%124 = arith.extsi %122 : i32 to i64
%123 = arith.cmpi eq, %121, %124 : i64
cf.cond_br %123, ^bb18, ^bb19
^bb18:
%125 = arith.constant 0 : i32
%126 = arith.constant 0 : i32
%127 = arith.extsi %126 : i32 to i64
%128 = llvm.getelementptr %arg1[%127] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %125, %128 : i32, !llvm.ptr
func.return
^bb19:
cf.br ^bb20
^bb20:
%130 = arith.constant 16 : i32
%131 = arith.constant 1 : i32
%132 = arith.extsi %130 : i32 to i64
%133 = arith.extsi %131 : i32 to i64
%129 = func.call @calloc(%132, %133) : (i64, i64) -> !llvm.ptr
%134 = arith.constant 0 : i32
%135 = llvm.mlir.constant(1 : i64) : i64
%136 = llvm.alloca %135 x i32 : (i64) -> !llvm.ptr
llvm.store %134, %136 : i32, !llvm.ptr
cf.br ^bb21
^bb21:
%137 = llvm.load %120 : !llvm.ptr -> i64
%138 = arith.constant 0 : i32
%140 = arith.extsi %138 : i32 to i64
%139 = arith.cmpi sgt, %137, %140 : i64
cf.cond_br %139, ^bb22, ^bb23
^bb22:
%141 = llvm.load %120 : !llvm.ptr -> i64
%142 = arith.constant 10 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.remsi %141, %144 : i64
%145 = arith.trunci %143 : i64 to i8
%146 = llvm.load %136 : !llvm.ptr -> i32
%147 = arith.extsi %146 : i32 to i64
%148 = llvm.getelementptr %129[%147] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %145, %148 : i8, !llvm.ptr
%149 = llvm.load %120 : !llvm.ptr -> i64
%150 = arith.constant 10 : i32
%152 = arith.extsi %150 : i32 to i64
%151 = arith.divsi %149, %152 : i64
llvm.store %151, %120 : i64, !llvm.ptr
%153 = llvm.load %136 : !llvm.ptr -> i32
%154 = arith.constant 1 : i32
%155 = arith.addi %153, %154 : i32
llvm.store %155, %136 : i32, !llvm.ptr
cf.br ^bb21
^bb23:
%156 = llvm.load %136 : !llvm.ptr -> i32
%157 = arith.constant 0 : i32
%158 = arith.extsi %157 : i32 to i64
%159 = llvm.getelementptr %arg1[%158] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %156, %159 : i32, !llvm.ptr
%160 = arith.constant 0 : i32
%161 = llvm.mlir.constant(1 : i64) : i64
%162 = llvm.alloca %161 x i32 : (i64) -> !llvm.ptr
llvm.store %160, %162 : i32, !llvm.ptr
cf.br ^bb24
^bb24:
%163 = llvm.load %162 : !llvm.ptr -> i32
%164 = llvm.load %136 : !llvm.ptr -> i32
%165 = arith.cmpi slt, %163, %164 : i32
cf.cond_br %165, ^bb25, ^bb26
^bb25:
%167 = llvm.load %136 : !llvm.ptr -> i32
%168 = arith.constant 1 : i32
%169 = arith.subi %167, %168 : i32
%170 = llvm.load %162 : !llvm.ptr -> i32
%171 = arith.subi %169, %170 : i32
%172 = arith.extsi %171 : i32 to i64
%173 = llvm.getelementptr %129[%172] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%166 = llvm.load %173 : !llvm.ptr -> i8
%174 = llvm.load %162 : !llvm.ptr -> i32
%175 = arith.extsi %174 : i32 to i64
%176 = llvm.getelementptr %arg2[%175] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %166, %176 : i8, !llvm.ptr
%177 = llvm.load %162 : !llvm.ptr -> i32
%178 = arith.constant 1 : i32
%179 = arith.addi %177, %178 : i32
llvm.store %179, %162 : i32, !llvm.ptr
cf.br ^bb24
^bb26:
func.call @free(%129) : (!llvm.ptr) -> ()
func.return
}
func.func @dig_sum(%arg0: i64, %arg1: i32, %arg2: !llvm.ptr) -> i32 {
%181 = arith.constant 0 : i32
%182 = llvm.mlir.constant(1 : i64) : i64
%183 = llvm.alloca %182 x i32 : (i64) -> !llvm.ptr
llvm.store %181, %183 : i32, !llvm.ptr
%184 = arith.constant 0 : i32
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x i32 : (i64) -> !llvm.ptr
llvm.store %184, %186 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%187 = llvm.load %186 : !llvm.ptr -> i32
%188 = arith.cmpi slt, %187, %arg1 : i32
cf.cond_br %188, ^bb28, ^bb29
^bb28:
%189 = llvm.load %183 : !llvm.ptr -> i32
%191 = arith.constant 12 : i32
%193 = arith.extsi %191 : i32 to i64
%192 = arith.muli %arg0, %193 : i64
%194 = llvm.load %186 : !llvm.ptr -> i32
%195 = arith.extsi %194 : i32 to i64
%196 = arith.addi %192, %195 : i64
%197 = llvm.getelementptr %arg2[%196] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%190 = llvm.load %197 : !llvm.ptr -> i8
%198 = arith.extsi %190 : i8 to i32
%199 = arith.addi %189, %198 : i32
llvm.store %199, %183 : i32, !llvm.ptr
%200 = llvm.load %186 : !llvm.ptr -> i32
%201 = arith.constant 1 : i32
%202 = arith.addi %200, %201 : i32
llvm.store %202, %186 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%203 = llvm.load %183 : !llvm.ptr -> i32
func.return %203 : i32
}
func.func @try_transition(%arg0: i64, %arg1: i32, %arg2: i32, %arg3: i32, %arg4: i32, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: !llvm.ptr) -> i32 {
%205 = arith.constant 16 : i32
%206 = arith.constant 1 : i32
%207 = arith.extsi %205 : i32 to i64
%208 = arith.extsi %206 : i32 to i64
%204 = func.call @calloc(%207, %208) : (i64, i64) -> !llvm.ptr
%209 = llvm.mlir.zero : !llvm.ptr
%210 = llvm.icmp "eq" %204, %209 : !llvm.ptr
cf.cond_br %210, ^bb30, ^bb31
^bb30:
%211 = arith.constant 0 : i32
func.return %211 : i32
^bb31:
cf.br ^bb32
^bb32:
%212 = arith.constant 0 : i32
%213 = llvm.mlir.constant(1 : i64) : i64
%214 = llvm.alloca %213 x i32 : (i64) -> !llvm.ptr
llvm.store %212, %214 : i32, !llvm.ptr
cf.br ^bb33
^bb33:
%215 = llvm.load %214 : !llvm.ptr -> i32
%216 = arith.cmpi slt, %215, %arg1 : i32
cf.cond_br %216, ^bb34, ^bb35
^bb34:
%218 = arith.constant 12 : i32
%220 = arith.extsi %218 : i32 to i64
%219 = arith.muli %arg0, %220 : i64
%221 = llvm.load %214 : !llvm.ptr -> i32
%222 = arith.extsi %221 : i32 to i64
%223 = arith.addi %219, %222 : i64
%224 = llvm.getelementptr %arg5[%223] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%217 = llvm.load %224 : !llvm.ptr -> i8
%225 = llvm.load %214 : !llvm.ptr -> i32
%226 = arith.extsi %225 : i32 to i64
%227 = llvm.getelementptr %204[%226] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %217, %227 : i8, !llvm.ptr
%228 = llvm.load %214 : !llvm.ptr -> i32
%229 = arith.constant 1 : i32
%230 = arith.addi %228, %229 : i32
llvm.store %230, %214 : i32, !llvm.ptr
cf.br ^bb33
^bb35:
%231 = arith.trunci %arg4 : i32 to i8
%232 = arith.extsi %arg1 : i32 to i64
%233 = llvm.getelementptr %204[%232] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %231, %233 : i8, !llvm.ptr
%234 = arith.constant 1 : i32
%235 = arith.addi %arg1, %234 : i32
%236 = llvm.mlir.constant(1 : i64) : i64
%237 = llvm.alloca %236 x i32 : (i64) -> !llvm.ptr
llvm.store %235, %237 : i32, !llvm.ptr
%238 = arith.constant 1 : i32
%239 = arith.addi %arg3, %238 : i32
%240 = llvm.mlir.constant(1 : i64) : i64
%241 = llvm.alloca %240 x i32 : (i64) -> !llvm.ptr
llvm.store %239, %241 : i32, !llvm.ptr
%242 = arith.addi %arg2, %arg4 : i32
%243 = llvm.mlir.constant(1 : i64) : i64
%244 = llvm.alloca %243 x i32 : (i64) -> !llvm.ptr
llvm.store %242, %244 : i32, !llvm.ptr
cf.br ^bb36
^bb36:
%245 = llvm.load %244 : !llvm.ptr -> i32
%246 = arith.constant 10 : i32
%247 = arith.cmpi sgt, %245, %246 : i32
cf.cond_br %247, ^bb37, ^bb38
^bb37:
%248 = llvm.load %237 : !llvm.ptr -> i32
%249 = llvm.load %241 : !llvm.ptr -> i32
%250 = arith.cmpi eq, %248, %249 : i32
cf.cond_br %250, ^bb39, ^bb40
^bb39:
func.call @free(%204) : (!llvm.ptr) -> ()
%252 = arith.constant 0 : i32
func.return %252 : i32
^bb40:
cf.br ^bb41
^bb41:
%253 = llvm.load %244 : !llvm.ptr -> i32
%255 = arith.constant 0 : i32
%256 = arith.extsi %255 : i32 to i64
%257 = llvm.getelementptr %204[%256] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%254 = llvm.load %257 : !llvm.ptr -> i8
%258 = arith.extsi %254 : i8 to i32
%259 = arith.subi %253, %258 : i32
llvm.store %259, %244 : i32, !llvm.ptr
%260 = arith.constant 0 : i32
%261 = llvm.mlir.constant(1 : i64) : i64
%262 = llvm.alloca %261 x i32 : (i64) -> !llvm.ptr
llvm.store %260, %262 : i32, !llvm.ptr
cf.br ^bb42
^bb42:
%263 = llvm.load %262 : !llvm.ptr -> i32
%264 = arith.constant 1 : i32
%265 = arith.addi %263, %264 : i32
%266 = llvm.load %237 : !llvm.ptr -> i32
%267 = arith.cmpi slt, %265, %266 : i32
cf.cond_br %267, ^bb43, ^bb44
^bb43:
%269 = llvm.load %262 : !llvm.ptr -> i32
%270 = arith.constant 1 : i32
%271 = arith.addi %269, %270 : i32
%272 = arith.extsi %271 : i32 to i64
%273 = llvm.getelementptr %204[%272] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%268 = llvm.load %273 : !llvm.ptr -> i8
%274 = llvm.load %262 : !llvm.ptr -> i32
%275 = arith.extsi %274 : i32 to i64
%276 = llvm.getelementptr %204[%275] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %268, %276 : i8, !llvm.ptr
%277 = llvm.load %262 : !llvm.ptr -> i32
%278 = arith.constant 1 : i32
%279 = arith.addi %277, %278 : i32
llvm.store %279, %262 : i32, !llvm.ptr
cf.br ^bb42
^bb44:
%280 = llvm.load %237 : !llvm.ptr -> i32
%281 = arith.constant 1 : i32
%282 = arith.subi %280, %281 : i32
llvm.store %282, %237 : i32, !llvm.ptr
cf.br ^bb36
^bb38:
%283 = llvm.load %244 : !llvm.ptr -> i32
%284 = arith.constant 10 : i32
%285 = arith.cmpi eq, %283, %284 : i32
cf.cond_br %285, ^bb45, ^bb46
^bb45:
%286 = arith.constant 0 : i32
llvm.store %286, %241 : i32, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%287 = llvm.load %237 : !llvm.ptr -> i32
%288 = arith.constant 0 : i32
%289 = arith.extsi %288 : i32 to i64
%290 = llvm.getelementptr %arg6[%289] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %287, %290 : i32, !llvm.ptr
%291 = arith.constant 0 : i32
llvm.store %291, %214 : i32, !llvm.ptr
cf.br ^bb48
^bb48:
%292 = llvm.load %214 : !llvm.ptr -> i32
%293 = llvm.load %237 : !llvm.ptr -> i32
%294 = arith.cmpi slt, %292, %293 : i32
cf.cond_br %294, ^bb49, ^bb50
^bb49:
%296 = llvm.load %214 : !llvm.ptr -> i32
%297 = arith.extsi %296 : i32 to i64
%298 = llvm.getelementptr %204[%297] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%295 = llvm.load %298 : !llvm.ptr -> i8
%299 = llvm.load %214 : !llvm.ptr -> i32
%300 = arith.extsi %299 : i32 to i64
%301 = llvm.getelementptr %arg7[%300] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %295, %301 : i8, !llvm.ptr
%302 = llvm.load %214 : !llvm.ptr -> i32
%303 = arith.constant 1 : i32
%304 = arith.addi %302, %303 : i32
llvm.store %304, %214 : i32, !llvm.ptr
cf.br ^bb48
^bb50:
%305 = llvm.load %241 : !llvm.ptr -> i32
%306 = arith.constant 0 : i32
%307 = arith.extsi %306 : i32 to i64
%308 = llvm.getelementptr %arg8[%307] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %305, %308 : i32, !llvm.ptr
func.call @free(%204) : (!llvm.ptr) -> ()
%310 = arith.constant 1 : i32
func.return %310 : i32
}
func.func @poly_mul_mod(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: i64, %arg4: !llvm.ptr) -> () {
%312 = arith.constant 2 : i32
%314 = arith.extsi %312 : i32 to i64
%313 = arith.muli %314, %arg3 : i64
%315 = arith.constant 8 : i32
%316 = arith.extsi %315 : i32 to i64
%311 = func.call @calloc(%313, %316) : (i64, i64) -> !llvm.ptr
%317 = llvm.mlir.zero : !llvm.ptr
%318 = llvm.icmp "eq" %311, %317 : !llvm.ptr
cf.cond_br %318, ^bb51, ^bb52
^bb51:
func.return
^bb52:
cf.br ^bb53
^bb53:
%319 = arith.constant 0 : i32
%320 = arith.extsi %319 : i32 to i64
%321 = llvm.mlir.constant(1 : i64) : i64
%322 = llvm.alloca %321 x i64 : (i64) -> !llvm.ptr
llvm.store %320, %322 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%323 = llvm.load %322 : !llvm.ptr -> i64
%324 = arith.constant 2 : i32
%326 = arith.extsi %324 : i32 to i64
%325 = arith.muli %326, %arg3 : i64
%327 = arith.cmpi slt, %323, %325 : i64
cf.cond_br %327, ^bb55, ^bb56
^bb55:
%328 = arith.constant 0 : i32
%329 = llvm.load %322 : !llvm.ptr -> i64
%330 = arith.extsi %328 : i32 to i64
%331 = llvm.getelementptr %311[%329] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %330, %331 : i64, !llvm.ptr
%332 = llvm.load %322 : !llvm.ptr -> i64
%333 = arith.constant 1 : i32
%335 = arith.extsi %333 : i32 to i64
%334 = arith.addi %332, %335 : i64
llvm.store %334, %322 : i64, !llvm.ptr
cf.br ^bb54
^bb56:
%336 = arith.constant 0 : i32
%337 = arith.extsi %336 : i32 to i64
llvm.store %337, %322 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%338 = llvm.load %322 : !llvm.ptr -> i64
%339 = arith.cmpi slt, %338, %arg3 : i64
cf.cond_br %339, ^bb58, ^bb59
^bb58:
%340 = arith.constant 0 : i32
%341 = arith.extsi %340 : i32 to i64
%342 = llvm.mlir.constant(1 : i64) : i64
%343 = llvm.alloca %342 x i64 : (i64) -> !llvm.ptr
llvm.store %341, %343 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%344 = llvm.load %343 : !llvm.ptr -> i64
%345 = arith.cmpi slt, %344, %arg3 : i64
cf.cond_br %345, ^bb61, ^bb62
^bb61:
%347 = llvm.load %322 : !llvm.ptr -> i64
%348 = llvm.load %343 : !llvm.ptr -> i64
%349 = arith.addi %347, %348 : i64
%350 = llvm.getelementptr %311[%349] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%346 = llvm.load %350 : !llvm.ptr -> i64
%352 = llvm.load %322 : !llvm.ptr -> i64
%353 = llvm.getelementptr %arg0[%352] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%351 = llvm.load %353 : !llvm.ptr -> i64
%354 = arith.extsi %351 : i64 to i128
%356 = llvm.load %343 : !llvm.ptr -> i64
%357 = llvm.getelementptr %arg1[%356] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%355 = llvm.load %357 : !llvm.ptr -> i64
%358 = arith.extsi %355 : i64 to i128
%360 = arith.trunci %354 : i128 to i64
%361 = arith.trunci %358 : i128 to i64
%359 = arith.muli %360, %361 : i64
%362 = llvm.mlir.addressof @MOD : !llvm.ptr
%363 = llvm.load %362 : !llvm.ptr -> i64
%364 = arith.extsi %363 : i64 to i128
%366 = arith.trunci %364 : i128 to i64
%365 = arith.remsi %359, %366 : i64
%367 = arith.addi %346, %365 : i64
%368 = llvm.mlir.addressof @MOD : !llvm.ptr
%369 = llvm.load %368 : !llvm.ptr -> i64
%370 = arith.remsi %367, %369 : i64
%371 = llvm.load %322 : !llvm.ptr -> i64
%372 = llvm.load %343 : !llvm.ptr -> i64
%373 = arith.addi %371, %372 : i64
%374 = llvm.getelementptr %311[%373] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %370, %374 : i64, !llvm.ptr
%375 = llvm.load %343 : !llvm.ptr -> i64
%376 = arith.constant 1 : i32
%378 = arith.extsi %376 : i32 to i64
%377 = arith.addi %375, %378 : i64
llvm.store %377, %343 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
%379 = llvm.load %322 : !llvm.ptr -> i64
%380 = arith.constant 1 : i32
%382 = arith.extsi %380 : i32 to i64
%381 = arith.addi %379, %382 : i64
llvm.store %381, %322 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
%383 = arith.constant 2 : i32
%385 = arith.extsi %383 : i32 to i64
%384 = arith.muli %385, %arg3 : i64
%386 = arith.constant 2 : i32
%388 = arith.extsi %386 : i32 to i64
%387 = arith.subi %384, %388 : i64
llvm.store %387, %322 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%389 = llvm.load %322 : !llvm.ptr -> i64
%390 = arith.cmpi sge, %389, %arg3 : i64
cf.cond_br %390, ^bb64, ^bb65
^bb64:
%392 = llvm.load %322 : !llvm.ptr -> i64
%393 = llvm.getelementptr %311[%392] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%391 = llvm.load %393 : !llvm.ptr -> i64
%394 = arith.constant 0 : i32
%396 = arith.extsi %394 : i32 to i64
%395 = arith.cmpi ne, %391, %396 : i64
cf.cond_br %395, ^bb66, ^bb67
^bb66:
%397 = arith.constant 0 : i32
%398 = arith.extsi %397 : i32 to i64
%399 = llvm.mlir.constant(1 : i64) : i64
%400 = llvm.alloca %399 x i64 : (i64) -> !llvm.ptr
llvm.store %398, %400 : i64, !llvm.ptr
cf.br ^bb69
^bb69:
%401 = llvm.load %400 : !llvm.ptr -> i64
%402 = arith.cmpi slt, %401, %arg3 : i64
cf.cond_br %402, ^bb70, ^bb71
^bb70:
%404 = llvm.load %322 : !llvm.ptr -> i64
%405 = arith.constant 1 : i32
%407 = arith.extsi %405 : i32 to i64
%406 = arith.subi %404, %407 : i64
%408 = llvm.load %400 : !llvm.ptr -> i64
%409 = arith.subi %406, %408 : i64
%410 = llvm.getelementptr %311[%409] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%403 = llvm.load %410 : !llvm.ptr -> i64
%411 = arith.extsi %391 : i64 to i128
%413 = llvm.load %400 : !llvm.ptr -> i64
%414 = llvm.getelementptr %arg4[%413] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%412 = llvm.load %414 : !llvm.ptr -> i64
%415 = arith.extsi %412 : i64 to i128
%417 = arith.trunci %411 : i128 to i64
%418 = arith.trunci %415 : i128 to i64
%416 = arith.muli %417, %418 : i64
%419 = llvm.mlir.addressof @MOD : !llvm.ptr
%420 = llvm.load %419 : !llvm.ptr -> i64
%421 = arith.extsi %420 : i64 to i128
%423 = arith.trunci %421 : i128 to i64
%422 = arith.remsi %416, %423 : i64
%424 = arith.addi %403, %422 : i64
%425 = llvm.mlir.addressof @MOD : !llvm.ptr
%426 = llvm.load %425 : !llvm.ptr -> i64
%427 = arith.remsi %424, %426 : i64
%428 = llvm.load %322 : !llvm.ptr -> i64
%429 = arith.constant 1 : i32
%431 = arith.extsi %429 : i32 to i64
%430 = arith.subi %428, %431 : i64
%432 = llvm.load %400 : !llvm.ptr -> i64
%433 = arith.subi %430, %432 : i64
%434 = llvm.getelementptr %311[%433] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %427, %434 : i64, !llvm.ptr
%435 = llvm.load %400 : !llvm.ptr -> i64
%436 = arith.constant 1 : i32
%438 = arith.extsi %436 : i32 to i64
%437 = arith.addi %435, %438 : i64
llvm.store %437, %400 : i64, !llvm.ptr
cf.br ^bb69
^bb71:
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
%439 = llvm.load %322 : !llvm.ptr -> i64
%440 = arith.constant 1 : i32
%442 = arith.extsi %440 : i32 to i64
%441 = arith.subi %439, %442 : i64
llvm.store %441, %322 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
%443 = arith.constant 0 : i32
%444 = arith.extsi %443 : i32 to i64
llvm.store %444, %322 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%445 = llvm.load %322 : !llvm.ptr -> i64
%446 = arith.cmpi slt, %445, %arg3 : i64
cf.cond_br %446, ^bb73, ^bb74
^bb73:
%448 = llvm.load %322 : !llvm.ptr -> i64
%449 = llvm.getelementptr %311[%448] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%447 = llvm.load %449 : !llvm.ptr -> i64
%450 = llvm.mlir.addressof @MOD : !llvm.ptr
%451 = llvm.load %450 : !llvm.ptr -> i64
%452 = arith.remsi %447, %451 : i64
%453 = llvm.load %322 : !llvm.ptr -> i64
%454 = llvm.getelementptr %arg2[%453] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %452, %454 : i64, !llvm.ptr
%455 = llvm.load %322 : !llvm.ptr -> i64
%456 = arith.constant 1 : i32
%458 = arith.extsi %456 : i32 to i64
%457 = arith.addi %455, %458 : i64
llvm.store %457, %322 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
func.call @free(%311) : (!llvm.ptr) -> ()
func.return
}
func.func @main() -> i32 {
%461 = llvm.mlir.addressof @CAP : !llvm.ptr
%462 = llvm.load %461 : !llvm.ptr -> i64
%463 = arith.constant 8 : i32
%464 = arith.extsi %463 : i32 to i64
%460 = func.call @calloc(%462, %464) : (i64, i64) -> !llvm.ptr
%466 = llvm.mlir.addressof @CAP : !llvm.ptr
%467 = llvm.load %466 : !llvm.ptr -> i64
%468 = arith.constant 1 : i32
%469 = arith.extsi %468 : i32 to i64
%465 = func.call @calloc(%467, %469) : (i64, i64) -> !llvm.ptr
%471 = llvm.mlir.addressof @CAP : !llvm.ptr
%472 = llvm.load %471 : !llvm.ptr -> i64
%473 = arith.constant 4 : i32
%474 = arith.extsi %473 : i32 to i64
%470 = func.call @calloc(%472, %474) : (i64, i64) -> !llvm.ptr
%476 = llvm.mlir.addressof @MAXS : !llvm.ptr
%477 = llvm.load %476 : !llvm.ptr -> i64
%478 = arith.constant 9 : i32
%480 = arith.extsi %478 : i32 to i64
%479 = arith.muli %477, %480 : i64
%481 = arith.constant 4 : i32
%482 = arith.extsi %481 : i32 to i64
%475 = func.call @calloc(%479, %482) : (i64, i64) -> !llvm.ptr
%484 = llvm.mlir.addressof @MAXS : !llvm.ptr
%485 = llvm.load %484 : !llvm.ptr -> i64
%486 = arith.constant 1 : i32
%487 = arith.extsi %486 : i32 to i64
%483 = func.call @calloc(%485, %487) : (i64, i64) -> !llvm.ptr
%489 = llvm.mlir.addressof @MAXS : !llvm.ptr
%490 = llvm.load %489 : !llvm.ptr -> i64
%491 = arith.constant 4 : i32
%492 = arith.extsi %491 : i32 to i64
%488 = func.call @calloc(%490, %492) : (i64, i64) -> !llvm.ptr
%494 = llvm.mlir.addressof @MAXS : !llvm.ptr
%495 = llvm.load %494 : !llvm.ptr -> i64
%496 = arith.constant 4 : i32
%497 = arith.extsi %496 : i32 to i64
%493 = func.call @calloc(%495, %497) : (i64, i64) -> !llvm.ptr
%499 = llvm.mlir.addressof @MAXS : !llvm.ptr
%500 = llvm.load %499 : !llvm.ptr -> i64
%501 = arith.constant 12 : i32
%503 = arith.extsi %501 : i32 to i64
%502 = arith.muli %500, %503 : i64
%504 = arith.constant 1 : i32
%505 = arith.extsi %504 : i32 to i64
%498 = func.call @calloc(%502, %505) : (i64, i64) -> !llvm.ptr
%506 = llvm.mlir.zero : !llvm.ptr
%507 = llvm.icmp "eq" %460, %506 : !llvm.ptr
%508 = scf.if %507 -> (i1) {
%509 = arith.constant true
scf.yield %509 : i1
} else {
%510 = llvm.mlir.zero : !llvm.ptr
%511 = llvm.icmp "eq" %475, %510 : !llvm.ptr
scf.yield %511 : i1
}
cf.cond_br %508, ^bb75, ^bb76
^bb75:
%512 = arith.constant 1 : i32
func.return %512 : i32
^bb76:
cf.br ^bb77
^bb77:
%513 = arith.constant 0 : i32
%514 = arith.extsi %513 : i32 to i64
%515 = func.call @hslot(%514, %460, %465) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%516 = arith.constant 1 : i32
%517 = arith.trunci %516 : i32 to i8
%518 = llvm.getelementptr %465[%515] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %517, %518 : i8, !llvm.ptr
%519 = llvm.getelementptr %460[%515] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %514, %519 : i64, !llvm.ptr
%520 = arith.constant 0 : i32
%521 = llvm.getelementptr %470[%515] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %520, %521 : i32, !llvm.ptr
%522 = arith.constant 0 : i32
%523 = arith.constant 0 : i32
%524 = arith.extsi %523 : i32 to i64
%525 = llvm.getelementptr %488[%524] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %522, %525 : i32, !llvm.ptr
%526 = arith.constant 0 : i32
%527 = arith.constant 0 : i32
%528 = arith.extsi %527 : i32 to i64
%529 = llvm.getelementptr %493[%528] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %526, %529 : i32, !llvm.ptr
%530 = arith.constant 1 : i32
%531 = llvm.mlir.constant(1 : i64) : i64
%532 = llvm.alloca %531 x i32 : (i64) -> !llvm.ptr
llvm.store %530, %532 : i32, !llvm.ptr
%534 = llvm.mlir.addressof @MAXS : !llvm.ptr
%535 = llvm.load %534 : !llvm.ptr -> i64
%536 = arith.constant 8 : i32
%537 = arith.extsi %536 : i32 to i64
%533 = func.call @calloc(%535, %537) : (i64, i64) -> !llvm.ptr
%538 = llvm.mlir.constant(1 : i64) : i64
%539 = llvm.alloca %538 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %533, %539 : !llvm.ptr, !llvm.ptr
%540 = arith.constant 0 : i32
%541 = llvm.load %539 : !llvm.ptr -> !llvm.ptr
%542 = arith.constant 0 : i32
%543 = arith.extsi %540 : i32 to i64
%544 = arith.extsi %542 : i32 to i64
%545 = llvm.getelementptr %541[%544] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %543, %545 : i64, !llvm.ptr
%546 = arith.constant 0 : i32
%547 = arith.extsi %546 : i32 to i64
%548 = llvm.mlir.constant(1 : i64) : i64
%549 = llvm.alloca %548 x i64 : (i64) -> !llvm.ptr
llvm.store %547, %549 : i64, !llvm.ptr
%550 = arith.constant 1 : i32
%551 = arith.extsi %550 : i32 to i64
%552 = llvm.mlir.constant(1 : i64) : i64
%553 = llvm.alloca %552 x i64 : (i64) -> !llvm.ptr
llvm.store %551, %553 : i64, !llvm.ptr
cf.br ^bb78
^bb78:
%554 = llvm.load %549 : !llvm.ptr -> i64
%555 = llvm.load %553 : !llvm.ptr -> i64
%556 = arith.cmpi slt, %554, %555 : i64
cf.cond_br %556, ^bb79, ^bb80
^bb79:
%558 = llvm.load %539 : !llvm.ptr -> !llvm.ptr
%559 = llvm.load %549 : !llvm.ptr -> i64
%560 = llvm.getelementptr %558[%559] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%557 = llvm.load %560 : !llvm.ptr -> i64
%561 = llvm.load %549 : !llvm.ptr -> i64
%562 = arith.constant 1 : i32
%564 = arith.extsi %562 : i32 to i64
%563 = arith.addi %561, %564 : i64
llvm.store %563, %549 : i64, !llvm.ptr
%567 = arith.trunci %557 : i64 to i32
%568 = arith.extsi %567 : i32 to i64
%569 = llvm.getelementptr %493[%568] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%566 = llvm.load %569 : !llvm.ptr -> i32
%565 = func.call @dig_sum(%557, %566, %498) : (i64, i32, !llvm.ptr) -> i32
%571 = arith.trunci %557 : i64 to i32
%572 = arith.extsi %571 : i32 to i64
%573 = llvm.getelementptr %493[%572] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%570 = llvm.load %573 : !llvm.ptr -> i32
%575 = arith.trunci %557 : i64 to i32
%576 = arith.extsi %575 : i32 to i64
%577 = llvm.getelementptr %488[%576] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%574 = llvm.load %577 : !llvm.ptr -> i32
%578 = arith.constant 0 : i32
%579 = arith.cmpi sgt, %570, %578 : i32
%580 = scf.if %579 -> (i1) {
%581 = arith.constant 0 : i32
%582 = arith.cmpi eq, %574, %581 : i32
scf.yield %582 : i1
} else {
%583 = arith.constant false
scf.yield %583 : i1
}
cf.cond_br %580, ^bb81, ^bb82
^bb81:
%584 = arith.constant 1 : i32
%585 = arith.trunci %584 : i32 to i8
%586 = llvm.getelementptr %483[%557] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %585, %586 : i8, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%587 = arith.constant 1 : i32
%588 = llvm.mlir.constant(1 : i64) : i64
%589 = llvm.alloca %588 x i32 : (i64) -> !llvm.ptr
llvm.store %587, %589 : i32, !llvm.ptr
cf.br ^bb84
^bb84:
%590 = llvm.load %589 : !llvm.ptr -> i32
%591 = arith.constant 9 : i32
%592 = arith.cmpi sle, %590, %591 : i32
cf.cond_br %592, ^bb85, ^bb86
^bb85:
%594 = arith.constant 1 : i32
%595 = arith.constant 4 : i32
%596 = arith.extsi %594 : i32 to i64
%597 = arith.extsi %595 : i32 to i64
%593 = func.call @calloc(%596, %597) : (i64, i64) -> !llvm.ptr
%599 = arith.constant 12 : i32
%600 = arith.constant 1 : i32
%601 = arith.extsi %599 : i32 to i64
%602 = arith.extsi %600 : i32 to i64
%598 = func.call @calloc(%601, %602) : (i64, i64) -> !llvm.ptr
%604 = arith.constant 1 : i32
%605 = arith.constant 4 : i32
%606 = arith.extsi %604 : i32 to i64
%607 = arith.extsi %605 : i32 to i64
%603 = func.call @calloc(%606, %607) : (i64, i64) -> !llvm.ptr
%609 = llvm.load %589 : !llvm.ptr -> i32
%608 = func.call @try_transition(%557, %570, %565, %574, %609, %498, %593, %598, %603) : (i64, i32, i32, i32, i32, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i32
%610 = arith.constant 1 : i32
%611 = arith.cmpi eq, %608, %610 : i32
cf.cond_br %611, ^bb87, ^bb88
^bb87:
%614 = arith.constant 0 : i32
%615 = arith.extsi %614 : i32 to i64
%616 = llvm.getelementptr %593[%615] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%613 = llvm.load %616 : !llvm.ptr -> i32
%618 = arith.constant 0 : i32
%619 = arith.extsi %618 : i32 to i64
%620 = llvm.getelementptr %603[%619] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%617 = llvm.load %620 : !llvm.ptr -> i32
%612 = func.call @pack_key(%613, %598, %617) : (i32, !llvm.ptr, i32) -> i64
%621 = func.call @hslot(%612, %460, %465) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%622 = arith.constant 0 : i32
%623 = llvm.mlir.constant(1 : i64) : i64
%624 = llvm.alloca %623 x i32 : (i64) -> !llvm.ptr
llvm.store %622, %624 : i32, !llvm.ptr
%626 = llvm.getelementptr %465[%621] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%625 = llvm.load %626 : !llvm.ptr -> i8
%627 = arith.constant 0 : i32
%629 = arith.extsi %625 : i8 to i32
%628 = arith.cmpi eq, %629, %627 : i32
cf.cond_br %628, ^bb90, ^bb91
^bb90:
%630 = arith.constant 1 : i32
%631 = arith.trunci %630 : i32 to i8
%632 = llvm.getelementptr %465[%621] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %631, %632 : i8, !llvm.ptr
%633 = llvm.getelementptr %460[%621] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %612, %633 : i64, !llvm.ptr
%634 = llvm.load %532 : !llvm.ptr -> i32
%635 = llvm.getelementptr %470[%621] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %634, %635 : i32, !llvm.ptr
%637 = arith.constant 0 : i32
%638 = arith.extsi %637 : i32 to i64
%639 = llvm.getelementptr %603[%638] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%636 = llvm.load %639 : !llvm.ptr -> i32
%640 = llvm.load %532 : !llvm.ptr -> i32
%641 = arith.extsi %640 : i32 to i64
%642 = llvm.getelementptr %488[%641] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %636, %642 : i32, !llvm.ptr
%644 = arith.constant 0 : i32
%645 = arith.extsi %644 : i32 to i64
%646 = llvm.getelementptr %593[%645] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%643 = llvm.load %646 : !llvm.ptr -> i32
%647 = llvm.load %532 : !llvm.ptr -> i32
%648 = arith.extsi %647 : i32 to i64
%649 = llvm.getelementptr %493[%648] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %643, %649 : i32, !llvm.ptr
%650 = arith.constant 0 : i32
%651 = llvm.mlir.constant(1 : i64) : i64
%652 = llvm.alloca %651 x i32 : (i64) -> !llvm.ptr
llvm.store %650, %652 : i32, !llvm.ptr
cf.br ^bb93
^bb93:
%653 = llvm.load %652 : !llvm.ptr -> i32
%655 = arith.constant 0 : i32
%656 = arith.extsi %655 : i32 to i64
%657 = llvm.getelementptr %593[%656] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%654 = llvm.load %657 : !llvm.ptr -> i32
%658 = arith.cmpi slt, %653, %654 : i32
cf.cond_br %658, ^bb94, ^bb95
^bb94:
%660 = llvm.load %652 : !llvm.ptr -> i32
%661 = arith.extsi %660 : i32 to i64
%662 = llvm.getelementptr %598[%661] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%659 = llvm.load %662 : !llvm.ptr -> i8
%663 = llvm.load %532 : !llvm.ptr -> i32
%664 = arith.constant 12 : i32
%665 = arith.muli %663, %664 : i32
%666 = llvm.load %652 : !llvm.ptr -> i32
%667 = arith.addi %665, %666 : i32
%668 = arith.extsi %667 : i32 to i64
%669 = llvm.getelementptr %498[%668] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %659, %669 : i8, !llvm.ptr
%670 = llvm.load %652 : !llvm.ptr -> i32
%671 = arith.constant 1 : i32
%672 = arith.addi %670, %671 : i32
llvm.store %672, %652 : i32, !llvm.ptr
cf.br ^bb93
^bb95:
%673 = llvm.load %532 : !llvm.ptr -> i32
%674 = arith.extsi %673 : i32 to i64
%675 = llvm.load %539 : !llvm.ptr -> !llvm.ptr
%676 = llvm.load %553 : !llvm.ptr -> i64
%677 = llvm.getelementptr %675[%676] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %674, %677 : i64, !llvm.ptr
%678 = llvm.load %553 : !llvm.ptr -> i64
%679 = arith.constant 1 : i32
%681 = arith.extsi %679 : i32 to i64
%680 = arith.addi %678, %681 : i64
llvm.store %680, %553 : i64, !llvm.ptr
%682 = llvm.load %532 : !llvm.ptr -> i32
llvm.store %682, %624 : i32, !llvm.ptr
%683 = llvm.load %532 : !llvm.ptr -> i32
%684 = arith.constant 1 : i32
%685 = arith.addi %683, %684 : i32
llvm.store %685, %532 : i32, !llvm.ptr
cf.br ^bb92
^bb91:
%687 = llvm.getelementptr %470[%621] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%686 = llvm.load %687 : !llvm.ptr -> i32
llvm.store %686, %624 : i32, !llvm.ptr
cf.br ^bb92
^bb92:
%688 = llvm.load %624 : !llvm.ptr -> i32
%689 = arith.constant 9 : i32
%691 = arith.extsi %689 : i32 to i64
%690 = arith.muli %557, %691 : i64
%692 = llvm.load %589 : !llvm.ptr -> i32
%693 = arith.constant 1 : i32
%694 = arith.subi %692, %693 : i32
%696 = arith.extsi %694 : i32 to i64
%695 = arith.addi %690, %696 : i64
%697 = llvm.getelementptr %475[%695] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %688, %697 : i32, !llvm.ptr
cf.br ^bb89
^bb88:
%698 = arith.constant 1 : i32
%700 = arith.constant 0 : i32
%699 = arith.subi %700, %698 : i32
%701 = arith.constant 9 : i32
%703 = arith.extsi %701 : i32 to i64
%702 = arith.muli %557, %703 : i64
%704 = llvm.load %589 : !llvm.ptr -> i32
%705 = arith.constant 1 : i32
%706 = arith.subi %704, %705 : i32
%708 = arith.extsi %706 : i32 to i64
%707 = arith.addi %702, %708 : i64
%709 = llvm.getelementptr %475[%707] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %699, %709 : i32, !llvm.ptr
cf.br ^bb89
^bb89:
func.call @free(%593) : (!llvm.ptr) -> ()
func.call @free(%598) : (!llvm.ptr) -> ()
func.call @free(%603) : (!llvm.ptr) -> ()
%713 = llvm.load %589 : !llvm.ptr -> i32
%714 = arith.constant 1 : i32
%715 = arith.addi %713, %714 : i32
llvm.store %715, %589 : i32, !llvm.ptr
cf.br ^bb84
^bb86:
cf.br ^bb78
^bb80:
%716 = llvm.load %532 : !llvm.ptr -> i32
%717 = arith.constant 2 : i32
%718 = arith.muli %717, %716 : i32
%719 = arith.constant 5 : i32
%720 = arith.addi %718, %719 : i32
%722 = arith.extsi %720 : i32 to i64
%723 = arith.constant 8 : i32
%724 = arith.extsi %723 : i32 to i64
%721 = func.call @calloc(%722, %724) : (i64, i64) -> !llvm.ptr
%726 = arith.extsi %716 : i32 to i64
%727 = arith.constant 8 : i32
%728 = arith.extsi %727 : i32 to i64
%725 = func.call @calloc(%726, %728) : (i64, i64) -> !llvm.ptr
%730 = arith.extsi %716 : i32 to i64
%731 = arith.constant 8 : i32
%732 = arith.extsi %731 : i32 to i64
%729 = func.call @calloc(%730, %732) : (i64, i64) -> !llvm.ptr
%733 = llvm.mlir.zero : !llvm.ptr
%734 = llvm.icmp "eq" %721, %733 : !llvm.ptr
%735 = scf.if %734 -> (i1) {
%736 = arith.constant true
scf.yield %736 : i1
} else {
%737 = llvm.mlir.zero : !llvm.ptr
%738 = llvm.icmp "eq" %725, %737 : !llvm.ptr
scf.yield %738 : i1
}
cf.cond_br %735, ^bb96, ^bb97
^bb96:
%739 = arith.constant 1 : i32
func.return %739 : i32
^bb97:
cf.br ^bb98
^bb98:
%740 = arith.constant 1 : i32
%741 = arith.constant 0 : i32
%742 = arith.extsi %740 : i32 to i64
%743 = arith.extsi %741 : i32 to i64
%744 = llvm.getelementptr %725[%743] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %742, %744 : i64, !llvm.ptr
%745 = arith.constant 1 : i32
%746 = llvm.mlir.constant(1 : i64) : i64
%747 = llvm.alloca %746 x i32 : (i64) -> !llvm.ptr
llvm.store %745, %747 : i32, !llvm.ptr
cf.br ^bb99
^bb99:
%748 = llvm.load %747 : !llvm.ptr -> i32
%749 = arith.cmpi slt, %748, %720 : i32
cf.cond_br %749, ^bb100, ^bb101
^bb100:
%750 = arith.constant 0 : i32
%751 = llvm.mlir.constant(1 : i64) : i64
%752 = llvm.alloca %751 x i32 : (i64) -> !llvm.ptr
llvm.store %750, %752 : i32, !llvm.ptr
cf.br ^bb102
^bb102:
%753 = llvm.load %752 : !llvm.ptr -> i32
%754 = arith.cmpi slt, %753, %716 : i32
cf.cond_br %754, ^bb103, ^bb104
^bb103:
%755 = arith.constant 0 : i32
%756 = llvm.load %752 : !llvm.ptr -> i32
%757 = arith.extsi %755 : i32 to i64
%758 = arith.extsi %756 : i32 to i64
%759 = llvm.getelementptr %729[%758] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %757, %759 : i64, !llvm.ptr
%760 = llvm.load %752 : !llvm.ptr -> i32
%761 = arith.constant 1 : i32
%762 = arith.addi %760, %761 : i32
llvm.store %762, %752 : i32, !llvm.ptr
cf.br ^bb102
^bb104:
%763 = arith.constant 0 : i32
llvm.store %763, %752 : i32, !llvm.ptr
cf.br ^bb105
^bb105:
%764 = llvm.load %752 : !llvm.ptr -> i32
%765 = arith.cmpi slt, %764, %716 : i32
cf.cond_br %765, ^bb106, ^bb107
^bb106:
%767 = llvm.load %752 : !llvm.ptr -> i32
%768 = arith.extsi %767 : i32 to i64
%769 = llvm.getelementptr %725[%768] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%766 = llvm.load %769 : !llvm.ptr -> i64
%770 = arith.constant 0 : i32
%772 = arith.extsi %770 : i32 to i64
%771 = arith.cmpi ne, %766, %772 : i64
cf.cond_br %771, ^bb108, ^bb109
^bb108:
%773 = arith.constant 1 : i32
%774 = llvm.mlir.constant(1 : i64) : i64
%775 = llvm.alloca %774 x i32 : (i64) -> !llvm.ptr
llvm.store %773, %775 : i32, !llvm.ptr
cf.br ^bb111
^bb111:
%776 = llvm.load %775 : !llvm.ptr -> i32
%777 = arith.constant 9 : i32
%778 = arith.cmpi sle, %776, %777 : i32
cf.cond_br %778, ^bb112, ^bb113
^bb112:
%780 = llvm.load %752 : !llvm.ptr -> i32
%781 = arith.constant 9 : i32
%782 = arith.muli %780, %781 : i32
%783 = llvm.load %775 : !llvm.ptr -> i32
%784 = arith.constant 1 : i32
%785 = arith.subi %783, %784 : i32
%786 = arith.addi %782, %785 : i32
%787 = arith.extsi %786 : i32 to i64
%788 = llvm.getelementptr %475[%787] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%779 = llvm.load %788 : !llvm.ptr -> i32
%789 = arith.constant 0 : i32
%790 = arith.cmpi sge, %779, %789 : i32
cf.cond_br %790, ^bb114, ^bb115
^bb114:
%792 = arith.extsi %779 : i32 to i64
%793 = llvm.getelementptr %729[%792] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%791 = llvm.load %793 : !llvm.ptr -> i64
%794 = arith.addi %791, %766 : i64
%795 = llvm.mlir.addressof @MOD : !llvm.ptr
%796 = llvm.load %795 : !llvm.ptr -> i64
%797 = arith.remsi %794, %796 : i64
%798 = arith.extsi %779 : i32 to i64
%799 = llvm.getelementptr %729[%798] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %797, %799 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
%800 = llvm.load %775 : !llvm.ptr -> i32
%801 = arith.constant 1 : i32
%802 = arith.addi %800, %801 : i32
llvm.store %802, %775 : i32, !llvm.ptr
cf.br ^bb111
^bb113:
cf.br ^bb110
^bb109:
cf.br ^bb110
^bb110:
%803 = llvm.load %752 : !llvm.ptr -> i32
%804 = arith.constant 1 : i32
%805 = arith.addi %803, %804 : i32
llvm.store %805, %752 : i32, !llvm.ptr
cf.br ^bb105
^bb107:
%806 = arith.constant 0 : i32
%807 = arith.extsi %806 : i32 to i64
%808 = llvm.mlir.constant(1 : i64) : i64
%809 = llvm.alloca %808 x i64 : (i64) -> !llvm.ptr
llvm.store %807, %809 : i64, !llvm.ptr
%810 = arith.constant 0 : i32
llvm.store %810, %752 : i32, !llvm.ptr
cf.br ^bb117
^bb117:
%811 = llvm.load %752 : !llvm.ptr -> i32
%812 = arith.cmpi slt, %811, %716 : i32
cf.cond_br %812, ^bb118, ^bb119
^bb118:
%814 = llvm.load %752 : !llvm.ptr -> i32
%815 = arith.extsi %814 : i32 to i64
%816 = llvm.getelementptr %483[%815] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%813 = llvm.load %816 : !llvm.ptr -> i8
%817 = arith.constant 1 : i32
%819 = arith.extsi %813 : i8 to i32
%818 = arith.cmpi eq, %819, %817 : i32
cf.cond_br %818, ^bb120, ^bb121
^bb120:
%820 = llvm.load %809 : !llvm.ptr -> i64
%822 = llvm.load %752 : !llvm.ptr -> i32
%823 = arith.extsi %822 : i32 to i64
%824 = llvm.getelementptr %729[%823] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%821 = llvm.load %824 : !llvm.ptr -> i64
%825 = arith.addi %820, %821 : i64
%826 = llvm.mlir.addressof @MOD : !llvm.ptr
%827 = llvm.load %826 : !llvm.ptr -> i64
%828 = arith.remsi %825, %827 : i64
llvm.store %828, %809 : i64, !llvm.ptr
cf.br ^bb122
^bb121:
cf.br ^bb122
^bb122:
%830 = llvm.load %752 : !llvm.ptr -> i32
%831 = arith.extsi %830 : i32 to i64
%832 = llvm.getelementptr %729[%831] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%829 = llvm.load %832 : !llvm.ptr -> i64
%833 = llvm.load %752 : !llvm.ptr -> i32
%834 = arith.extsi %833 : i32 to i64
%835 = llvm.getelementptr %725[%834] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %829, %835 : i64, !llvm.ptr
%836 = llvm.load %752 : !llvm.ptr -> i32
%837 = arith.constant 1 : i32
%838 = arith.addi %836, %837 : i32
llvm.store %838, %752 : i32, !llvm.ptr
cf.br ^bb117
^bb119:
%839 = llvm.load %809 : !llvm.ptr -> i64
%840 = llvm.load %747 : !llvm.ptr -> i32
%841 = arith.extsi %840 : i32 to i64
%842 = llvm.getelementptr %721[%841] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %839, %842 : i64, !llvm.ptr
%843 = llvm.load %747 : !llvm.ptr -> i32
%844 = arith.constant 1 : i32
%845 = arith.addi %843, %844 : i32
llvm.store %845, %747 : i32, !llvm.ptr
cf.br ^bb99
^bb101:
%846 = arith.extsi %720 : i32 to i64
%847 = arith.constant 10 : i32
%849 = arith.extsi %847 : i32 to i64
%848 = arith.addi %846, %849 : i64
%851 = arith.constant 8 : i32
%852 = arith.extsi %851 : i32 to i64
%850 = func.call @calloc(%848, %852) : (i64, i64) -> !llvm.ptr
%854 = arith.constant 8 : i32
%855 = arith.extsi %854 : i32 to i64
%853 = func.call @calloc(%848, %855) : (i64, i64) -> !llvm.ptr
%856 = arith.constant 1 : i32
%857 = arith.constant 0 : i32
%858 = arith.extsi %856 : i32 to i64
%859 = arith.extsi %857 : i32 to i64
%860 = llvm.getelementptr %850[%859] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %858, %860 : i64, !llvm.ptr
%861 = arith.constant 1 : i32
%862 = arith.constant 0 : i32
%863 = arith.extsi %861 : i32 to i64
%864 = arith.extsi %862 : i32 to i64
%865 = llvm.getelementptr %853[%864] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %863, %865 : i64, !llvm.ptr
%866 = arith.constant 1 : i32
%867 = arith.extsi %866 : i32 to i64
%868 = llvm.mlir.constant(1 : i64) : i64
%869 = llvm.alloca %868 x i64 : (i64) -> !llvm.ptr
llvm.store %867, %869 : i64, !llvm.ptr
%870 = arith.constant 1 : i32
%871 = arith.extsi %870 : i32 to i64
%872 = llvm.mlir.constant(1 : i64) : i64
%873 = llvm.alloca %872 x i64 : (i64) -> !llvm.ptr
llvm.store %871, %873 : i64, !llvm.ptr
%874 = arith.constant 0 : i32
%875 = arith.extsi %874 : i32 to i64
%876 = llvm.mlir.constant(1 : i64) : i64
%877 = llvm.alloca %876 x i64 : (i64) -> !llvm.ptr
llvm.store %875, %877 : i64, !llvm.ptr
%878 = arith.constant 1 : i32
%879 = arith.extsi %878 : i32 to i64
%880 = llvm.mlir.constant(1 : i64) : i64
%881 = llvm.alloca %880 x i64 : (i64) -> !llvm.ptr
llvm.store %879, %881 : i64, !llvm.ptr
%882 = arith.constant 1 : i32
%883 = arith.extsi %882 : i32 to i64
%884 = llvm.mlir.constant(1 : i64) : i64
%885 = llvm.alloca %884 x i64 : (i64) -> !llvm.ptr
llvm.store %883, %885 : i64, !llvm.ptr
%886 = arith.constant 0 : i32
%887 = arith.extsi %886 : i32 to i64
%888 = llvm.mlir.constant(1 : i64) : i64
%889 = llvm.alloca %888 x i64 : (i64) -> !llvm.ptr
llvm.store %887, %889 : i64, !llvm.ptr
%890 = arith.constant 0 : i32
%891 = arith.extsi %890 : i32 to i64
%892 = llvm.mlir.constant(1 : i64) : i64
%893 = llvm.alloca %892 x i64 : (i64) -> !llvm.ptr
llvm.store %891, %893 : i64, !llvm.ptr
cf.br ^bb123
^bb123:
%894 = llvm.load %889 : !llvm.ptr -> i64
%895 = arith.extsi %720 : i32 to i64
%896 = arith.cmpi slt, %894, %895 : i64
cf.cond_br %896, ^bb124, ^bb125
^bb124:
%898 = llvm.load %889 : !llvm.ptr -> i64
%899 = llvm.getelementptr %721[%898] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%897 = llvm.load %899 : !llvm.ptr -> i64
%900 = llvm.mlir.constant(1 : i64) : i64
%901 = llvm.alloca %900 x i64 : (i64) -> !llvm.ptr
llvm.store %897, %901 : i64, !llvm.ptr
%902 = arith.constant 1 : i32
%903 = arith.extsi %902 : i32 to i64
llvm.store %903, %893 : i64, !llvm.ptr
cf.br ^bb126
^bb126:
%904 = llvm.load %893 : !llvm.ptr -> i64
%905 = llvm.load %877 : !llvm.ptr -> i64
%906 = arith.cmpi sle, %904, %905 : i64
cf.cond_br %906, ^bb127, ^bb128
^bb127:
%907 = llvm.load %901 : !llvm.ptr -> i64
%909 = llvm.load %893 : !llvm.ptr -> i64
%910 = llvm.getelementptr %850[%909] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%908 = llvm.load %910 : !llvm.ptr -> i64
%911 = arith.extsi %908 : i64 to i128
%913 = llvm.load %889 : !llvm.ptr -> i64
%914 = llvm.load %893 : !llvm.ptr -> i64
%915 = arith.subi %913, %914 : i64
%916 = llvm.getelementptr %721[%915] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%912 = llvm.load %916 : !llvm.ptr -> i64
%917 = arith.extsi %912 : i64 to i128
%919 = arith.trunci %911 : i128 to i64
%920 = arith.trunci %917 : i128 to i64
%918 = arith.muli %919, %920 : i64
%921 = llvm.mlir.addressof @MOD : !llvm.ptr
%922 = llvm.load %921 : !llvm.ptr -> i64
%923 = arith.extsi %922 : i64 to i128
%925 = arith.trunci %923 : i128 to i64
%924 = arith.remsi %918, %925 : i64
%926 = arith.addi %907, %924 : i64
%927 = llvm.mlir.addressof @MOD : !llvm.ptr
%928 = llvm.load %927 : !llvm.ptr -> i64
%929 = arith.remsi %926, %928 : i64
llvm.store %929, %901 : i64, !llvm.ptr
%930 = llvm.load %893 : !llvm.ptr -> i64
%931 = arith.constant 1 : i32
%933 = arith.extsi %931 : i32 to i64
%932 = arith.addi %930, %933 : i64
llvm.store %932, %893 : i64, !llvm.ptr
cf.br ^bb126
^bb128:
%934 = llvm.load %901 : !llvm.ptr -> i64
%935 = arith.constant 0 : i32
%937 = arith.extsi %935 : i32 to i64
%936 = arith.cmpi eq, %934, %937 : i64
cf.cond_br %936, ^bb129, ^bb130
^bb129:
%938 = llvm.load %881 : !llvm.ptr -> i64
%939 = arith.constant 1 : i32
%941 = arith.extsi %939 : i32 to i64
%940 = arith.addi %938, %941 : i64
llvm.store %940, %881 : i64, !llvm.ptr
cf.br ^bb131
^bb130:
%942 = llvm.load %901 : !llvm.ptr -> i64
%943 = arith.extsi %942 : i64 to i128
%945 = llvm.load %885 : !llvm.ptr -> i64
%946 = llvm.mlir.addressof @MOD : !llvm.ptr
%947 = llvm.load %946 : !llvm.ptr -> i64
%948 = arith.constant 2 : i32
%950 = arith.extsi %948 : i32 to i64
%949 = arith.subi %947, %950 : i64
%951 = llvm.mlir.addressof @MOD : !llvm.ptr
%952 = llvm.load %951 : !llvm.ptr -> i64
%944 = func.call @modpow(%945, %949, %952) : (i64, i64, i64) -> i64
%953 = arith.extsi %944 : i64 to i128
%955 = arith.trunci %943 : i128 to i64
%956 = arith.trunci %953 : i128 to i64
%954 = arith.muli %955, %956 : i64
%957 = llvm.mlir.addressof @MOD : !llvm.ptr
%958 = llvm.load %957 : !llvm.ptr -> i64
%959 = arith.extsi %958 : i64 to i128
%961 = arith.trunci %959 : i128 to i64
%960 = arith.remsi %954, %961 : i64
%963 = arith.constant 8 : i32
%964 = arith.extsi %963 : i32 to i64
%962 = func.call @calloc(%848, %964) : (i64, i64) -> !llvm.ptr
%965 = llvm.load %869 : !llvm.ptr -> i64
%966 = arith.constant 0 : i32
%967 = arith.extsi %966 : i32 to i64
llvm.store %967, %893 : i64, !llvm.ptr
cf.br ^bb132
^bb132:
%968 = llvm.load %893 : !llvm.ptr -> i64
%969 = arith.cmpi slt, %968, %965 : i64
cf.cond_br %969, ^bb133, ^bb134
^bb133:
%971 = llvm.load %893 : !llvm.ptr -> i64
%972 = llvm.getelementptr %850[%971] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%970 = llvm.load %972 : !llvm.ptr -> i64
%973 = llvm.load %893 : !llvm.ptr -> i64
%974 = llvm.getelementptr %962[%973] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %970, %974 : i64, !llvm.ptr
%975 = llvm.load %893 : !llvm.ptr -> i64
%976 = arith.constant 1 : i32
%978 = arith.extsi %976 : i32 to i64
%977 = arith.addi %975, %978 : i64
llvm.store %977, %893 : i64, !llvm.ptr
cf.br ^bb132
^bb134:
%979 = arith.constant 0 : i32
%980 = arith.extsi %979 : i32 to i64
llvm.store %980, %893 : i64, !llvm.ptr
cf.br ^bb135
^bb135:
%981 = llvm.load %893 : !llvm.ptr -> i64
%982 = llvm.load %873 : !llvm.ptr -> i64
%983 = arith.cmpi slt, %981, %982 : i64
cf.cond_br %983, ^bb136, ^bb137
^bb136:
%984 = llvm.load %893 : !llvm.ptr -> i64
%985 = llvm.load %881 : !llvm.ptr -> i64
%986 = arith.addi %984, %985 : i64
cf.br ^bb138
^bb138:
%987 = llvm.load %869 : !llvm.ptr -> i64
%988 = arith.cmpi sle, %987, %986 : i64
cf.cond_br %988, ^bb139, ^bb140
^bb139:
%989 = arith.constant 0 : i32
%990 = llvm.load %869 : !llvm.ptr -> i64
%991 = arith.extsi %989 : i32 to i64
%992 = llvm.getelementptr %850[%990] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %991, %992 : i64, !llvm.ptr
%993 = llvm.load %869 : !llvm.ptr -> i64
%994 = arith.constant 1 : i32
%996 = arith.extsi %994 : i32 to i64
%995 = arith.addi %993, %996 : i64
llvm.store %995, %869 : i64, !llvm.ptr
cf.br ^bb138
^bb140:
%998 = llvm.getelementptr %850[%986] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%997 = llvm.load %998 : !llvm.ptr -> i64
%999 = arith.extsi %960 : i64 to i128
%1001 = llvm.load %893 : !llvm.ptr -> i64
%1002 = llvm.getelementptr %853[%1001] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1000 = llvm.load %1002 : !llvm.ptr -> i64
%1003 = arith.extsi %1000 : i64 to i128
%1005 = arith.trunci %999 : i128 to i64
%1006 = arith.trunci %1003 : i128 to i64
%1004 = arith.muli %1005, %1006 : i64
%1007 = llvm.mlir.addressof @MOD : !llvm.ptr
%1008 = llvm.load %1007 : !llvm.ptr -> i64
%1009 = arith.extsi %1008 : i64 to i128
%1011 = arith.trunci %1009 : i128 to i64
%1010 = arith.remsi %1004, %1011 : i64
%1012 = arith.subi %997, %1010 : i64
%1013 = llvm.mlir.addressof @MOD : !llvm.ptr
%1014 = llvm.load %1013 : !llvm.ptr -> i64
%1015 = arith.remsi %1012, %1014 : i64
%1016 = llvm.getelementptr %850[%986] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1015, %1016 : i64, !llvm.ptr
%1018 = llvm.getelementptr %850[%986] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1017 = llvm.load %1018 : !llvm.ptr -> i64
%1019 = arith.constant 0 : i32
%1021 = arith.extsi %1019 : i32 to i64
%1020 = arith.cmpi slt, %1017, %1021 : i64
cf.cond_br %1020, ^bb141, ^bb142
^bb141:
%1023 = llvm.getelementptr %850[%986] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1022 = llvm.load %1023 : !llvm.ptr -> i64
%1024 = llvm.mlir.addressof @MOD : !llvm.ptr
%1025 = llvm.load %1024 : !llvm.ptr -> i64
%1026 = arith.addi %1022, %1025 : i64
%1027 = llvm.getelementptr %850[%986] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1026, %1027 : i64, !llvm.ptr
cf.br ^bb143
^bb142:
cf.br ^bb143
^bb143:
%1028 = llvm.load %893 : !llvm.ptr -> i64
%1029 = arith.constant 1 : i32
%1031 = arith.extsi %1029 : i32 to i64
%1030 = arith.addi %1028, %1031 : i64
llvm.store %1030, %893 : i64, !llvm.ptr
cf.br ^bb135
^bb137:
%1032 = arith.constant 2 : i32
%1033 = llvm.load %877 : !llvm.ptr -> i64
%1035 = arith.extsi %1032 : i32 to i64
%1034 = arith.muli %1035, %1033 : i64
%1036 = llvm.load %889 : !llvm.ptr -> i64
%1037 = arith.cmpi sle, %1034, %1036 : i64
cf.cond_br %1037, ^bb144, ^bb145
^bb144:
%1038 = arith.constant 0 : i32
%1039 = arith.extsi %1038 : i32 to i64
llvm.store %1039, %893 : i64, !llvm.ptr
cf.br ^bb147
^bb147:
%1040 = llvm.load %893 : !llvm.ptr -> i64
%1041 = arith.cmpi slt, %1040, %965 : i64
cf.cond_br %1041, ^bb148, ^bb149
^bb148:
%1043 = llvm.load %893 : !llvm.ptr -> i64
%1044 = llvm.getelementptr %962[%1043] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1042 = llvm.load %1044 : !llvm.ptr -> i64
%1045 = llvm.load %893 : !llvm.ptr -> i64
%1046 = llvm.getelementptr %853[%1045] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1042, %1046 : i64, !llvm.ptr
%1047 = llvm.load %893 : !llvm.ptr -> i64
%1048 = arith.constant 1 : i32
%1050 = arith.extsi %1048 : i32 to i64
%1049 = arith.addi %1047, %1050 : i64
llvm.store %1049, %893 : i64, !llvm.ptr
cf.br ^bb147
^bb149:
llvm.store %965, %873 : i64, !llvm.ptr
%1051 = llvm.load %889 : !llvm.ptr -> i64
%1052 = arith.constant 1 : i32
%1054 = arith.extsi %1052 : i32 to i64
%1053 = arith.addi %1051, %1054 : i64
%1055 = llvm.load %877 : !llvm.ptr -> i64
%1056 = arith.subi %1053, %1055 : i64
llvm.store %1056, %877 : i64, !llvm.ptr
%1057 = llvm.load %901 : !llvm.ptr -> i64
llvm.store %1057, %885 : i64, !llvm.ptr
%1058 = arith.constant 1 : i32
%1059 = arith.extsi %1058 : i32 to i64
llvm.store %1059, %881 : i64, !llvm.ptr
cf.br ^bb146
^bb145:
%1060 = llvm.load %881 : !llvm.ptr -> i64
%1061 = arith.constant 1 : i32
%1063 = arith.extsi %1061 : i32 to i64
%1062 = arith.addi %1060, %1063 : i64
llvm.store %1062, %881 : i64, !llvm.ptr
cf.br ^bb146
^bb146:
func.call @free(%962) : (!llvm.ptr) -> ()
cf.br ^bb131
^bb131:
%1065 = llvm.load %889 : !llvm.ptr -> i64
%1066 = arith.constant 1 : i32
%1068 = arith.extsi %1066 : i32 to i64
%1067 = arith.addi %1065, %1068 : i64
llvm.store %1067, %889 : i64, !llvm.ptr
cf.br ^bb123
^bb125:
%1069 = llvm.load %877 : !llvm.ptr -> i64
%1071 = arith.constant 8 : i32
%1072 = arith.extsi %1071 : i32 to i64
%1070 = func.call @calloc(%1069, %1072) : (i64, i64) -> !llvm.ptr
%1073 = arith.constant 1 : i32
%1074 = arith.extsi %1073 : i32 to i64
llvm.store %1074, %893 : i64, !llvm.ptr
cf.br ^bb150
^bb150:
%1075 = llvm.load %893 : !llvm.ptr -> i64
%1076 = arith.cmpi sle, %1075, %1069 : i64
cf.cond_br %1076, ^bb151, ^bb152
^bb151:
%1078 = llvm.load %893 : !llvm.ptr -> i64
%1079 = llvm.getelementptr %850[%1078] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1077 = llvm.load %1079 : !llvm.ptr -> i64
%1081 = arith.constant 0 : i64
%1080 = arith.subi %1081, %1077 : i64
%1082 = llvm.mlir.addressof @MOD : !llvm.ptr
%1083 = llvm.load %1082 : !llvm.ptr -> i64
%1084 = arith.remsi %1080, %1083 : i64
%1085 = llvm.load %893 : !llvm.ptr -> i64
%1086 = arith.constant 1 : i32
%1088 = arith.extsi %1086 : i32 to i64
%1087 = arith.subi %1085, %1088 : i64
%1089 = llvm.getelementptr %1070[%1087] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1084, %1089 : i64, !llvm.ptr
%1091 = llvm.load %893 : !llvm.ptr -> i64
%1092 = arith.constant 1 : i32
%1094 = arith.extsi %1092 : i32 to i64
%1093 = arith.subi %1091, %1094 : i64
%1095 = llvm.getelementptr %1070[%1093] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1090 = llvm.load %1095 : !llvm.ptr -> i64
%1096 = arith.constant 0 : i32
%1098 = arith.extsi %1096 : i32 to i64
%1097 = arith.cmpi slt, %1090, %1098 : i64
cf.cond_br %1097, ^bb153, ^bb154
^bb153:
%1100 = llvm.load %893 : !llvm.ptr -> i64
%1101 = arith.constant 1 : i32
%1103 = arith.extsi %1101 : i32 to i64
%1102 = arith.subi %1100, %1103 : i64
%1104 = llvm.getelementptr %1070[%1102] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1099 = llvm.load %1104 : !llvm.ptr -> i64
%1105 = llvm.mlir.addressof @MOD : !llvm.ptr
%1106 = llvm.load %1105 : !llvm.ptr -> i64
%1107 = arith.addi %1099, %1106 : i64
%1108 = llvm.load %893 : !llvm.ptr -> i64
%1109 = arith.constant 1 : i32
%1111 = arith.extsi %1109 : i32 to i64
%1110 = arith.subi %1108, %1111 : i64
%1112 = llvm.getelementptr %1070[%1110] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1107, %1112 : i64, !llvm.ptr
cf.br ^bb155
^bb154:
cf.br ^bb155
^bb155:
%1113 = llvm.load %893 : !llvm.ptr -> i64
%1114 = arith.constant 1 : i32
%1116 = arith.extsi %1114 : i32 to i64
%1115 = arith.addi %1113, %1116 : i64
llvm.store %1115, %893 : i64, !llvm.ptr
cf.br ^bb150
^bb152:
func.call @free(%850) : (!llvm.ptr) -> ()
func.call @free(%853) : (!llvm.ptr) -> ()
%1120 = arith.constant 8 : i32
%1121 = arith.extsi %1120 : i32 to i64
%1119 = func.call @calloc(%1069, %1121) : (i64, i64) -> !llvm.ptr
%1123 = arith.constant 8 : i32
%1124 = arith.extsi %1123 : i32 to i64
%1122 = func.call @calloc(%1069, %1124) : (i64, i64) -> !llvm.ptr
%1126 = arith.constant 8 : i32
%1127 = arith.extsi %1126 : i32 to i64
%1125 = func.call @calloc(%1069, %1127) : (i64, i64) -> !llvm.ptr
%1129 = arith.constant 8 : i32
%1130 = arith.extsi %1129 : i32 to i64
%1128 = func.call @calloc(%1069, %1130) : (i64, i64) -> !llvm.ptr
%1131 = arith.constant 1 : i32
%1132 = arith.constant 0 : i32
%1133 = arith.extsi %1131 : i32 to i64
%1134 = arith.extsi %1132 : i32 to i64
%1135 = llvm.getelementptr %1119[%1134] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1133, %1135 : i64, !llvm.ptr
%1136 = arith.constant 1 : i32
%1138 = arith.extsi %1136 : i32 to i64
%1137 = arith.cmpi sgt, %1069, %1138 : i64
cf.cond_br %1137, ^bb156, ^bb157
^bb156:
%1139 = arith.constant 1 : i32
%1140 = arith.constant 1 : i32
%1141 = arith.extsi %1139 : i32 to i64
%1142 = arith.extsi %1140 : i32 to i64
%1143 = llvm.getelementptr %1119[%1142] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1141, %1143 : i64, !llvm.ptr
cf.br ^bb158
^bb157:
cf.br ^bb158
^bb158:
%1144 = arith.constant 1 : i32
%1145 = arith.constant 0 : i32
%1146 = arith.extsi %1144 : i32 to i64
%1147 = arith.extsi %1145 : i32 to i64
%1148 = llvm.getelementptr %1122[%1147] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1146, %1148 : i64, !llvm.ptr
%1149 = llvm.mlir.addressof @N_EXP : !llvm.ptr
%1150 = llvm.load %1149 : !llvm.ptr -> i64
%1151 = llvm.mlir.constant(1 : i64) : i64
%1152 = llvm.alloca %1151 x i64 : (i64) -> !llvm.ptr
llvm.store %1150, %1152 : i64, !llvm.ptr
%1153 = arith.constant 0 : i32
%1154 = arith.extsi %1153 : i32 to i64
%1155 = llvm.mlir.constant(1 : i64) : i64
%1156 = llvm.alloca %1155 x i64 : (i64) -> !llvm.ptr
llvm.store %1154, %1156 : i64, !llvm.ptr
cf.br ^bb159
^bb159:
%1157 = llvm.load %1152 : !llvm.ptr -> i64
%1158 = arith.constant 0 : i32
%1160 = arith.extsi %1158 : i32 to i64
%1159 = arith.cmpi sgt, %1157, %1160 : i64
cf.cond_br %1159, ^bb160, ^bb161
^bb160:
%1161 = llvm.load %1152 : !llvm.ptr -> i64
%1162 = arith.constant 1 : i32
%1164 = arith.extsi %1162 : i32 to i64
%1163 = arith.andi %1161, %1164 : i64
%1165 = arith.constant 1 : i32
%1167 = arith.extsi %1165 : i32 to i64
%1166 = arith.cmpi eq, %1163, %1167 : i64
cf.cond_br %1166, ^bb162, ^bb163
^bb162:
func.call @poly_mul_mod(%1122, %1119, %1125, %1069, %1070) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, !llvm.ptr) -> ()
%1169 = arith.constant 0 : i32
%1170 = arith.extsi %1169 : i32 to i64
llvm.store %1170, %1156 : i64, !llvm.ptr
cf.br ^bb165
^bb165:
%1171 = llvm.load %1156 : !llvm.ptr -> i64
%1172 = arith.cmpi slt, %1171, %1069 : i64
cf.cond_br %1172, ^bb166, ^bb167
^bb166:
%1174 = llvm.load %1156 : !llvm.ptr -> i64
%1175 = llvm.getelementptr %1125[%1174] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1173 = llvm.load %1175 : !llvm.ptr -> i64
%1176 = llvm.load %1156 : !llvm.ptr -> i64
%1177 = llvm.getelementptr %1122[%1176] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1173, %1177 : i64, !llvm.ptr
%1178 = llvm.load %1156 : !llvm.ptr -> i64
%1179 = arith.constant 1 : i32
%1181 = arith.extsi %1179 : i32 to i64
%1180 = arith.addi %1178, %1181 : i64
llvm.store %1180, %1156 : i64, !llvm.ptr
cf.br ^bb165
^bb167:
cf.br ^bb164
^bb163:
cf.br ^bb164
^bb164:
func.call @poly_mul_mod(%1119, %1119, %1128, %1069, %1070) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, !llvm.ptr) -> ()
%1183 = arith.constant 0 : i32
%1184 = arith.extsi %1183 : i32 to i64
llvm.store %1184, %1156 : i64, !llvm.ptr
cf.br ^bb168
^bb168:
%1185 = llvm.load %1156 : !llvm.ptr -> i64
%1186 = arith.cmpi slt, %1185, %1069 : i64
cf.cond_br %1186, ^bb169, ^bb170
^bb169:
%1188 = llvm.load %1156 : !llvm.ptr -> i64
%1189 = llvm.getelementptr %1128[%1188] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1187 = llvm.load %1189 : !llvm.ptr -> i64
%1190 = llvm.load %1156 : !llvm.ptr -> i64
%1191 = llvm.getelementptr %1119[%1190] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1187, %1191 : i64, !llvm.ptr
%1192 = llvm.load %1156 : !llvm.ptr -> i64
%1193 = arith.constant 1 : i32
%1195 = arith.extsi %1193 : i32 to i64
%1194 = arith.addi %1192, %1195 : i64
llvm.store %1194, %1156 : i64, !llvm.ptr
cf.br ^bb168
^bb170:
%1196 = llvm.load %1152 : !llvm.ptr -> i64
%1197 = arith.constant 2 : i32
%1199 = arith.extsi %1197 : i32 to i64
%1198 = arith.divsi %1196, %1199 : i64
llvm.store %1198, %1152 : i64, !llvm.ptr
cf.br ^bb159
^bb161:
%1200 = arith.constant 0 : i32
%1201 = arith.extsi %1200 : i32 to i64
%1202 = llvm.mlir.constant(1 : i64) : i64
%1203 = llvm.alloca %1202 x i64 : (i64) -> !llvm.ptr
llvm.store %1201, %1203 : i64, !llvm.ptr
%1204 = arith.constant 0 : i32
%1205 = arith.extsi %1204 : i32 to i64
llvm.store %1205, %1156 : i64, !llvm.ptr
cf.br ^bb171
^bb171:
%1206 = llvm.load %1156 : !llvm.ptr -> i64
%1207 = arith.cmpi slt, %1206, %1069 : i64
cf.cond_br %1207, ^bb172, ^bb173
^bb172:
%1208 = llvm.load %1203 : !llvm.ptr -> i64
%1210 = llvm.load %1156 : !llvm.ptr -> i64
%1211 = llvm.getelementptr %1122[%1210] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1209 = llvm.load %1211 : !llvm.ptr -> i64
%1212 = arith.extsi %1209 : i64 to i128
%1214 = llvm.load %1156 : !llvm.ptr -> i64
%1215 = llvm.getelementptr %721[%1214] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1213 = llvm.load %1215 : !llvm.ptr -> i64
%1216 = arith.extsi %1213 : i64 to i128
%1218 = arith.trunci %1212 : i128 to i64
%1219 = arith.trunci %1216 : i128 to i64
%1217 = arith.muli %1218, %1219 : i64
%1220 = llvm.mlir.addressof @MOD : !llvm.ptr
%1221 = llvm.load %1220 : !llvm.ptr -> i64
%1222 = arith.extsi %1221 : i64 to i128
%1224 = arith.trunci %1222 : i128 to i64
%1223 = arith.remsi %1217, %1224 : i64
%1225 = arith.addi %1208, %1223 : i64
%1226 = llvm.mlir.addressof @MOD : !llvm.ptr
%1227 = llvm.load %1226 : !llvm.ptr -> i64
%1228 = arith.remsi %1225, %1227 : i64
llvm.store %1228, %1203 : i64, !llvm.ptr
%1229 = llvm.load %1156 : !llvm.ptr -> i64
%1230 = arith.constant 1 : i32
%1232 = arith.extsi %1230 : i32 to i64
%1231 = arith.addi %1229, %1232 : i64
llvm.store %1231, %1156 : i64, !llvm.ptr
cf.br ^bb171
^bb173:
%1233 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1234 = llvm.load %1203 : !llvm.ptr -> i64
%1235 = llvm.call @printf(%1233, %1234) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%460) : (!llvm.ptr) -> ()
func.call @free(%465) : (!llvm.ptr) -> ()
func.call @free(%470) : (!llvm.ptr) -> ()
func.call @free(%475) : (!llvm.ptr) -> ()
func.call @free(%483) : (!llvm.ptr) -> ()
func.call @free(%488) : (!llvm.ptr) -> ()
func.call @free(%493) : (!llvm.ptr) -> ()
func.call @free(%498) : (!llvm.ptr) -> ()
%1245 = llvm.load %539 : !llvm.ptr -> !llvm.ptr
func.call @free(%1245) : (!llvm.ptr) -> ()
func.call @free(%721) : (!llvm.ptr) -> ()
func.call @free(%725) : (!llvm.ptr) -> ()
func.call @free(%729) : (!llvm.ptr) -> ()
func.call @free(%1070) : (!llvm.ptr) -> ()
func.call @free(%1119) : (!llvm.ptr) -> ()
func.call @free(%1122) : (!llvm.ptr) -> ()
func.call @free(%1125) : (!llvm.ptr) -> ()
func.call @free(%1128) : (!llvm.ptr) -> ()
%1254 = arith.constant 0 : i32
func.return %1254 : i32
}
}