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