← All problems Problem 812
Dynamical Polynomials: S(10000) mod 998244353 via NTT-based polynomial exp/ln. Pure Flow port of the native C solver.
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 812
# Dynamical Polynomials: S(10000) mod 998244353 via NTT-based polynomial exp/ln.
# Pure Flow port of the native C solver.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
function memset(p: ptr<void>, c: i32, n: i64) -> ptr<void>
}
const MOD: i64 = 998244353
const PRIMITIVE_ROOT: i64 = 3
let mut g_out_len: i32 = 0
let mut g_prime_count: i32 = 0
function powmod(base: i64, exp: i64, mod_val: i64) -> i64 {
let mut r: i64 = 1 % mod_val
let mut b: i64 = base % mod_val
if b < 0 { b = b + mod_val }
let mut e: i64 = exp
while e > 0 {
if e % 2 == 1 {
r = r * b % mod_val
}
b = b * b % mod_val
e = e / 2
}
return r
}
function inv_mod(a: i64) -> i64 {
return powmod(a, MOD - 2, MOD)
}
function ntt(a: ptr<i64>, n: i32, invert: i32) -> void {
let mut j: i32 = 0
let mut i: i32 = 1
while i < n {
let mut bit: i32 = n >> 1
while (j & bit) != 0 {
j = j ^ bit
bit = bit >> 1
}
j = j ^ bit
if i < j {
let tmp: i64 = a[i]
a[i] = a[j]
a[j] = tmp
}
i = i + 1
}
let mut len_val: i32 = 2
while len_val <= n {
let mut wlen: i64 = powmod(PRIMITIVE_ROOT, (MOD - 1) / (len_val as i64), MOD)
if invert != 0 {
wlen = powmod(wlen, MOD - 2, MOD)
}
let half: i32 = len_val >> 1
let mut i2: i32 = 0
while i2 < n {
let mut w: i64 = 1
let mut j2: i32 = 0
while j2 < half {
let u: i64 = a[i2 + j2]
let v: i64 = a[i2 + j2 + half] * w % MOD
a[i2 + j2] = (u + v) % MOD
let mut tmp2: i64 = (u - v) % MOD
if tmp2 < 0 { tmp2 = tmp2 + MOD }
a[i2 + j2 + half] = tmp2
w = w * wlen % MOD
j2 = j2 + 1
}
i2 = i2 + len_val
}
len_val = len_val << 1
}
if invert != 0 {
let inv_n: i64 = powmod(n as i64, MOD - 2, MOD)
let mut i3: i32 = 0
while i3 < n {
a[i3] = a[i3] * inv_n % MOD
i3 = i3 + 1
}
}
}
function polymul(a: ptr<i64>, la: i32, b: ptr<i64>, lb: i32) -> ptr<i64> {
if la == 0 || lb == 0 {
g_out_len = 0
return null
}
let n: i32 = la + lb - 1
# Small-size fallback
if la <= 32 || lb <= 32 {
let res: ptr<i64> = calloc(n as i64, 8)
let mut i: i32 = 0
while i < la {
if a[i] != 0 {
let mut j: i32 = 0
while j < lb {
res[i + j] = (res[i + j] + a[i] * b[j]) % MOD
j = j + 1
}
}
i = i + 1
}
g_out_len = n
return res
}
let mut size: i32 = 1
while size < n {
size = size << 1
}
let fa: ptr<i64> = calloc(size as i64, 8)
let fb: ptr<i64> = calloc(size as i64, 8)
memcpy(fa, a, (la as i64) * 8)
memcpy(fb, b, (lb as i64) * 8)
ntt(fa, size, 0)
ntt(fb, size, 0)
let mut i: i32 = 0
while i < size {
fa[i] = fa[i] * fb[i] % MOD
i = i + 1
}
ntt(fa, size, 1)
let res: ptr<i64> = malloc((n as i64) * 8)
memcpy(res, fa, (n as i64) * 8)
free(fa)
free(fb)
g_out_len = n
return res
}
function poly_der(a: ptr<i64>, la: i32) -> ptr<i64> {
if la <= 1 {
g_out_len = 0
return null
}
let out_len: i32 = la - 1
let res: ptr<i64> = malloc((out_len as i64) * 8)
let mut i: i32 = 1
while i < la {
res[i - 1] = (i as i64) * a[i] % MOD
i = i + 1
}
g_out_len = out_len
return res
}
function poly_int(a: ptr<i64>, la: i32, invs: ptr<i64>) -> ptr<i64> {
let out_len: i32 = la + 1
let res: ptr<i64> = calloc(out_len as i64, 8)
let mut i: i32 = 0
while i < la {
res[i + 1] = a[i] * invs[i + 1] % MOD
i = i + 1
}
g_out_len = out_len
return res
}
function poly_inv(a: ptr<i64>, la: i32, n: i32) -> ptr<i64> {
let res: ptr<i64> = calloc(n as i64, 8)
res[0] = powmod(a[0], MOD - 2, MOD)
let mut m: i32 = 1
while m < n {
let mut m2: i32 = m * 2
if m2 > n { m2 = n }
let la_used: i32 = la
let la_arg: i32 = if la_used > m2 { m2 } else { la_used }
let t: ptr<i64> = polymul(a, la_arg, res, m)
let t_len: i32 = g_out_len
let tl: i32 = if t_len > m2 { m2 } else { t_len }
let t2: ptr<i64> = calloc(m2 as i64, 8)
let mut i: i32 = 0
while i < tl {
t2[i] = t[i]
i = i + 1
}
free(t)
t2[0] = (2 - t2[0]) % MOD
if t2[0] < 0 { t2[0] = t2[0] + MOD }
let mut i2: i32 = 1
while i2 < m2 {
t2[i2] = (0 - t2[i2]) % MOD
if t2[i2] < 0 { t2[i2] = t2[i2] + MOD }
i2 = i2 + 1
}
let new_res: ptr<i64> = polymul(res, m, t2, m2)
let r_len: i32 = g_out_len
let rl: i32 = if r_len > m2 { m2 } else { r_len }
memcpy(res, new_res, (rl as i64) * 8)
free(new_res)
free(t2)
m = m2
}
g_out_len = n
return res
}
function poly_ln(a: ptr<i64>, la: i32, n: i32, invs: ptr<i64>) -> ptr<i64> {
let der: ptr<i64> = poly_der(a, la)
let der_len: i32 = g_out_len
let inv_a: ptr<i64> = poly_inv(a, la, n)
let inv_len: i32 = g_out_len
let q: ptr<i64> = polymul(der, der_len, inv_a, inv_len)
let q_len: i32 = g_out_len
let ql: i32 = if n - 1 > q_len { q_len } else { n - 1 }
if ql < 0 { ql = 0 }
let result: ptr<i64> = poly_int(q, ql, invs)
let int_len: i32 = g_out_len
let rl: i32 = if n > int_len { int_len } else { n }
free(der)
free(inv_a)
free(q)
let res: ptr<i64> = calloc(n as i64, 8)
memcpy(res, result, (rl as i64) * 8)
free(result)
g_out_len = n
return res
}
function poly_exp(f: ptr<i64>, lf: i32, n: i32, invs: ptr<i64>) -> ptr<i64> {
let g: ptr<i64> = calloc(n as i64, 8)
g[0] = 1
let mut m: i32 = 1
while m < n {
let mut m2: i32 = m * 2
if m2 > n { m2 = n }
let g_pad: ptr<i64> = calloc(m2 as i64, 8)
memcpy(g_pad, g, (m as i64) * 8)
let ln_g: ptr<i64> = poly_ln(g_pad, m2, m2, invs)
let ln_len: i32 = g_out_len
let diff: ptr<i64> = calloc(m2 as i64, 8)
let mut i: i32 = 0
while i < m2 {
let fi: i64 = if i < lf { f[i] } else { 0 }
let mut d: i64 = (fi - ln_g[i]) % MOD
if d < 0 { d = d + MOD }
diff[i] = d
i = i + 1
}
diff[0] = (diff[0] + 1) % MOD
let new_g: ptr<i64> = polymul(g, m, diff, m2)
let new_len: i32 = g_out_len
let nl: i32 = if new_len > m2 { m2 } else { new_len }
memcpy(g, new_g, (nl as i64) * 8)
free(g_pad)
free(ln_g)
free(diff)
free(new_g)
m = m2
}
g_out_len = n
return g
}
function special_component(N: i32) -> ptr<i64> {
let inv2: i64 = (MOD + 1) / 2
let v1: ptr<i64> = calloc((N + 1) as i64, 8)
v1[0] = 1
let mut p: i32 = 2
while p <= N {
let mut d: i32 = p
while d <= N {
v1[d] = (v1[d] + v1[d - p]) % MOD
d = d + 1
}
p = p << 1
}
let vminus: ptr<i64> = calloc((N + 1) as i64, 8)
vminus[0] = 1
let mut p2: i32 = 2
while p2 <= N {
let new_arr: ptr<i64> = calloc((N + 1) as i64, 8)
let mut d: i32 = 0
while d <= N {
let mut val: i64 = vminus[d]
if d >= p2 {
val = (val - new_arr[d - p2]) % MOD
if val < 0 { val = val + MOD }
}
new_arr[d] = val
d = d + 1
}
# Copy new_arr back into vminus (overwrite in place, no free/realloc)
let mut d2: i32 = 0
while d2 <= N {
vminus[d2] = new_arr[d2]
d2 = d2 + 1
}
free(new_arr)
p2 = p2 << 1
}
# P(x) = 1/2 * ((1+x)V1 + (1-x)Vminus)
let pser: ptr<i64> = calloc((N + 1) as i64, 8)
let mut d3: i32 = 0
while d3 <= N {
let mut t1: i64 = v1[d3]
if d3 > 0 { t1 = (t1 + v1[d3 - 1]) % MOD }
let mut t2: i64 = vminus[d3]
if d3 > 0 {
t2 = (t2 - vminus[d3 - 1]) % MOD
if t2 < 0 { t2 = t2 + MOD }
}
pser[d3] = (t1 + t2) % MOD * inv2 % MOD
d3 = d3 + 1
}
# Multiply by 1/(1-x): prefix sums
let a: ptr<i64> = calloc((N + 1) as i64, 8)
let mut s: i64 = 0
let mut d4: i32 = 0
while d4 <= N {
s = (s + pser[d4]) % MOD
a[d4] = s
d4 = d4 + 1
}
# Multiply by 1/(1-x^2)
let b: ptr<i64> = calloc((N + 1) as i64, 8)
let mut d5: i32 = 0
while d5 <= N {
let mut val: i64 = a[d5]
if d5 >= 2 { val = (val + b[d5 - 2]) % MOD }
b[d5] = val
d5 = d5 + 1
}
free(v1)
free(vminus)
free(pser)
free(a)
return b
}
function add_component_multiplicities(c: ptr<i64>, N: i32) -> void {
let limit_phi: i32 = 2 * N
# Sieve primes <= limit_phi + 1
let sieve_n: i32 = limit_phi + 1
let bs: ptr<i8> = malloc((sieve_n + 1) as i64)
memset(bs, 1, (sieve_n + 1) as i64)
bs[0] = 0
bs[1] = 0
let mut p: i32 = 2
while (p as i64) * (p as i64) <= sieve_n as i64 {
if bs[p] != 0 {
let mut j: i32 = p * p
while j <= sieve_n {
bs[j] = 0
j = j + p
}
}
p = p + 1
}
let mut prime_count: i32 = 0
let mut i: i32 = 2
while i <= sieve_n {
if bs[i] != 0 { prime_count = prime_count + 1 }
i = i + 1
}
let primes: ptr<i32> = malloc((prime_count as i64) * 4)
let mut idx: i32 = 0
let mut i2: i32 = 2
while i2 <= sieve_n {
if bs[i2] != 0 {
primes[idx] = i2
idx = idx + 1
}
i2 = i2 + 1
}
free(bs)
# Filter odd primes
let odd_primes: ptr<i32> = malloc((prime_count as i64) * 4)
let mut nop: i32 = 0
let mut i3: i32 = 0
while i3 < prime_count {
if (primes[i3] & 1) != 0 {
odd_primes[nop] = primes[i3]
nop = nop + 1
}
i3 = i3 + 1
}
# DFS using explicit stack
# Stack frame: (start_idx, n_val, phi_val)
let stack_cap: i32 = 200000
let stack_start: ptr<i32> = malloc((stack_cap as i64) * 4)
let stack_n: ptr<i64> = malloc((stack_cap as i64) * 8)
let stack_phi: ptr<i64> = malloc((stack_cap as i64) * 8)
let mut sp: i32 = 0
stack_start[sp] = 0
stack_n[sp] = 1
stack_phi[sp] = 1
sp = sp + 1
while sp > 0 {
sp = sp - 1
let f_start: i32 = stack_start[sp]
let f_n: i64 = stack_n[sp]
let f_phi: i64 = stack_phi[sp]
# Record this odd m0 (exclude 1)
if f_n > 1 {
let ph: i64 = f_phi
let deg0: i64 = ph / 2
let mut w: i64 = 0
let mut k: i32 = 0
while true {
let mut deg: i64 = 0
if k == 0 || k == 1 {
deg = deg0
} else {
deg = ph * ((1 as i64) << (k - 2))
}
w = w + deg
if w > (N as i64) { break }
c[w] = c[w] + 1
k = k + 1
}
}
# Extend by adding new prime powers
let mut i: i32 = f_start
while i < nop {
let p_val: i32 = odd_primes[i]
if f_phi * ((p_val - 1) as i64) > limit_phi as i64 { break }
# exponent 1
# stack_cap is 200000, large enough that sp never reaches it
stack_start[sp] = i + 1
stack_n[sp] = f_n * (p_val as i64)
stack_phi[sp] = f_phi * ((p_val - 1) as i64)
sp = sp + 1
# exponent >= 2
let mut n_e: i64 = f_n * (p_val as i64) * (p_val as i64)
let mut phi_e: i64 = f_phi * ((p_val - 1) as i64) * (p_val as i64)
while phi_e <= limit_phi as i64 {
stack_start[sp] = i + 1
stack_n[sp] = n_e
stack_phi[sp] = phi_e
sp = sp + 1
n_e = n_e * (p_val as i64)
phi_e = phi_e * (p_val as i64)
}
i = i + 1
}
}
free(stack_start)
free(stack_n)
free(stack_phi)
free(primes)
free(odd_primes)
}
function solve(N: i32) -> i64 {
let c: ptr<i64> = calloc((N + 1) as i64, 8)
add_component_multiplicities(c, N)
# Build g(x) = log(F)(x) where F(x) = Prod (1 - x^a)^(-c[a])
let g: ptr<i64> = calloc((N + 1) as i64, 8)
let mut d: i32 = 1
while d <= N {
let cd: i64 = c[d]
if cd != 0 {
let add_val: i64 = (d as i64) * (cd % MOD) % MOD
let mut k: i32 = d
while k <= N {
g[k] = (g[k] + add_val) % MOD
k = k + d
}
}
d = d + 1
}
# Inverses
let invs: ptr<i64> = calloc((N + 2) as i64, 8)
let mut i: i32 = 1
while i <= N + 1 {
invs[i] = inv_mod(i as i64)
i = i + 1
}
# h[k] = g[k] * invs[k]
let h: ptr<i64> = calloc((N + 1) as i64, 8)
let mut k: i32 = 1
while k <= N {
h[k] = g[k] * invs[k] % MOD
k = k + 1
}
let colored: ptr<i64> = poly_exp(h, N + 1, N + 1, invs)
let colored_len: i32 = g_out_len
let special: ptr<i64> = special_component(N)
# Total = convolution of colored and special
let total: ptr<i64> = polymul(colored, colored_len, special, N + 1)
let total_len: i32 = g_out_len
let result: i64 = total[N] % MOD
free(c)
free(g)
free(invs)
free(h)
free(colored)
free(special)
free(total)
return result
}
function main() -> i32 {
printf("%lld\n", solve(10000))
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 powmod_i64_i64_i64(int64_t base, int64_t exp, int64_t mod_val);
int64_t inv_mod_i64(int64_t a);
void ntt_ptr_i64_i32_i32(int64_t* a, int32_t n, int32_t invert);
int64_t* polymul_ptr_i64_i32_ptr_i64_i32(int64_t* a, int32_t la, int64_t* b, int32_t lb);
int64_t* poly_der_ptr_i64_i32(int64_t* a, int32_t la);
int64_t* poly_int_ptr_i64_i32_ptr_i64(int64_t* a, int32_t la, int64_t* invs);
int64_t* poly_inv_ptr_i64_i32_i32(int64_t* a, int32_t la, int32_t n);
int64_t* poly_ln_ptr_i64_i32_i32_ptr_i64(int64_t* a, int32_t la, int32_t n, int64_t* invs);
int64_t* poly_exp_ptr_i64_i32_i32_ptr_i64(int64_t* f, int32_t lf, int32_t n, int64_t* invs);
int64_t* special_component_i32(int32_t N);
void add_component_multiplicities_ptr_i64_i32(int64_t* c, int32_t N);
int64_t solve_i32(int32_t N);
int32_t main(void);
static const int64_t MOD = 998244353;
static const int64_t PRIMITIVE_ROOT = 3;
/* Module statics */
static int32_t g_out_len = 0;
static int32_t g_prime_count = 0;
int64_t powmod_i64_i64_i64(int64_t base, int64_t exp, int64_t mod_val) {
int64_t r = FLOW_CHECKED_MOD((1), (mod_val));
int64_t b = FLOW_CHECKED_MOD((base), (mod_val));
if (b < 0) {
b = (b + mod_val);
}
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
r = FLOW_CHECKED_MOD(((r * b)), (mod_val));
}
b = FLOW_CHECKED_MOD(((b * b)), (mod_val));
e = FLOW_CHECKED_DIV((e), (2));
}
return r;
}
int64_t inv_mod_i64(int64_t a) {
return powmod_i64_i64_i64(a, (MOD - 2), MOD);
}
void ntt_ptr_i64_i32_i32(int64_t* a, int32_t n, int32_t invert) {
int32_t j = 0;
int32_t i = 1;
while (i < n) {
int32_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 tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
i = (i + 1);
}
int32_t len_val = 2;
while (len_val <= n) {
int64_t wlen = powmod_i64_i64_i64(PRIMITIVE_ROOT, FLOW_CHECKED_DIV(((MOD - 1)), (((int64_t)(len_val)))), MOD);
if (invert != 0) {
wlen = powmod_i64_i64_i64(wlen, (MOD - 2), MOD);
}
int32_t half = FLOW_CHECKED_SHR((len_val), (1));
int32_t i2 = 0;
while (i2 < n) {
int64_t w = 1;
int32_t j2 = 0;
while (j2 < half) {
int64_t u = a[(i2 + j2)];
int64_t v = FLOW_CHECKED_MOD(((a[((i2 + j2) + half)] * w)), (MOD));
a[(i2 + j2)] = FLOW_CHECKED_MOD(((u + v)), (MOD));
int64_t tmp2 = FLOW_CHECKED_MOD(((u - v)), (MOD));
if (tmp2 < 0) {
tmp2 = (tmp2 + MOD);
}
a[((i2 + j2) + half)] = tmp2;
w = FLOW_CHECKED_MOD(((w * wlen)), (MOD));
j2 = (j2 + 1);
}
i2 = (i2 + len_val);
}
len_val = FLOW_CHECKED_SHL((len_val), (1));
}
if (invert != 0) {
int64_t inv_n = powmod_i64_i64_i64(((int64_t)(n)), (MOD - 2), MOD);
int32_t i3 = 0;
while (i3 < n) {
a[i3] = FLOW_CHECKED_MOD(((a[i3] * inv_n)), (MOD));
i3 = (i3 + 1);
}
}
}
int64_t* polymul_ptr_i64_i32_ptr_i64_i32(int64_t* a, int32_t la, int64_t* b, int32_t lb) {
if ((la == 0 || lb == 0)) {
g_out_len = 0;
return NULL;
}
int32_t n = ((la + lb) - 1);
if ((la <= 32 || lb <= 32)) {
int64_t* res = (int64_t*)(calloc(((int64_t)(n)), 8));
int32_t i = 0;
while (i < la) {
if (a[i] != 0) {
int32_t j = 0;
while (j < lb) {
res[(i + j)] = FLOW_CHECKED_MOD(((res[(i + j)] + (a[i] * b[j]))), (MOD));
j = (j + 1);
}
}
i = (i + 1);
}
g_out_len = n;
return res;
}
int32_t size = 1;
while (size < n) {
size = FLOW_CHECKED_SHL((size), (1));
}
int64_t* fa = (int64_t*)(calloc(((int64_t)(size)), 8));
int64_t* fb = (int64_t*)(calloc(((int64_t)(size)), 8));
memcpy(fa, a, (((int64_t)(la)) * 8));
memcpy(fb, b, (((int64_t)(lb)) * 8));
ntt_ptr_i64_i32_i32(fa, size, 0);
ntt_ptr_i64_i32_i32(fb, size, 0);
int32_t i = 0;
while (i < size) {
fa[i] = FLOW_CHECKED_MOD(((fa[i] * fb[i])), (MOD));
i = (i + 1);
}
ntt_ptr_i64_i32_i32(fa, size, 1);
int64_t* res = (int64_t*)(malloc((((int64_t)(n)) * 8)));
memcpy(res, fa, (((int64_t)(n)) * 8));
free(fa);
free(fb);
g_out_len = n;
return res;
}
int64_t* poly_der_ptr_i64_i32(int64_t* a, int32_t la) {
if (la <= 1) {
g_out_len = 0;
return NULL;
}
int32_t out_len = (la - 1);
int64_t* res = (int64_t*)(malloc((((int64_t)(out_len)) * 8)));
int32_t i = 1;
while (i < la) {
res[(i - 1)] = FLOW_CHECKED_MOD(((((int64_t)(i)) * a[i])), (MOD));
i = (i + 1);
}
g_out_len = out_len;
return res;
}
int64_t* poly_int_ptr_i64_i32_ptr_i64(int64_t* a, int32_t la, int64_t* invs) {
int32_t out_len = (la + 1);
int64_t* res = (int64_t*)(calloc(((int64_t)(out_len)), 8));
int32_t i = 0;
while (i < la) {
res[(i + 1)] = FLOW_CHECKED_MOD(((a[i] * invs[(i + 1)])), (MOD));
i = (i + 1);
}
g_out_len = out_len;
return res;
}
int64_t* poly_inv_ptr_i64_i32_i32(int64_t* a, int32_t la, int32_t n) {
int64_t* res = (int64_t*)(calloc(((int64_t)(n)), 8));
res[0] = powmod_i64_i64_i64(a[0], (MOD - 2), MOD);
int32_t m = 1;
while (m < n) {
int32_t m2 = (m * 2);
if (m2 > n) {
m2 = n;
}
int32_t la_used = la;
int32_t la_arg = ((la_used > m2) ? (m2) : (la_used));
int64_t* t = (int64_t*)(polymul_ptr_i64_i32_ptr_i64_i32(a, la_arg, res, m));
int32_t t_len = g_out_len;
int32_t tl = ((t_len > m2) ? (m2) : (t_len));
int64_t* t2 = (int64_t*)(calloc(((int64_t)(m2)), 8));
int32_t i = 0;
while (i < tl) {
t2[i] = t[i];
i = (i + 1);
}
free(t);
t2[0] = FLOW_CHECKED_MOD(((2 - t2[0])), (MOD));
if (t2[0] < 0) {
t2[0] = (t2[0] + MOD);
}
int32_t i2 = 1;
while (i2 < m2) {
t2[i2] = FLOW_CHECKED_MOD(((0 - t2[i2])), (MOD));
if (t2[i2] < 0) {
t2[i2] = (t2[i2] + MOD);
}
i2 = (i2 + 1);
}
int64_t* new_res = (int64_t*)(polymul_ptr_i64_i32_ptr_i64_i32(res, m, t2, m2));
int32_t r_len = g_out_len;
int32_t rl = ((r_len > m2) ? (m2) : (r_len));
memcpy(res, new_res, (((int64_t)(rl)) * 8));
free(new_res);
free(t2);
m = m2;
}
g_out_len = n;
return res;
}
int64_t* poly_ln_ptr_i64_i32_i32_ptr_i64(int64_t* a, int32_t la, int32_t n, int64_t* invs) {
int64_t* der = (int64_t*)(poly_der_ptr_i64_i32(a, la));
int32_t der_len = g_out_len;
int64_t* inv_a = (int64_t*)(poly_inv_ptr_i64_i32_i32(a, la, n));
int32_t inv_len = g_out_len;
int64_t* q = (int64_t*)(polymul_ptr_i64_i32_ptr_i64_i32(der, der_len, inv_a, inv_len));
int32_t q_len = g_out_len;
int32_t ql = (((n - 1) > q_len) ? (q_len) : ((n - 1)));
if (ql < 0) {
ql = 0;
}
int64_t* result = (int64_t*)(poly_int_ptr_i64_i32_ptr_i64(q, ql, invs));
int32_t int_len = g_out_len;
int32_t rl = ((n > int_len) ? (int_len) : (n));
free(der);
free(inv_a);
free(q);
int64_t* res = (int64_t*)(calloc(((int64_t)(n)), 8));
memcpy(res, result, (((int64_t)(rl)) * 8));
free(result);
g_out_len = n;
return res;
}
int64_t* poly_exp_ptr_i64_i32_i32_ptr_i64(int64_t* f, int32_t lf, int32_t n, int64_t* invs) {
int64_t* g = (int64_t*)(calloc(((int64_t)(n)), 8));
g[0] = 1;
int32_t m = 1;
while (m < n) {
int32_t m2 = (m * 2);
if (m2 > n) {
m2 = n;
}
int64_t* g_pad = (int64_t*)(calloc(((int64_t)(m2)), 8));
memcpy(g_pad, g, (((int64_t)(m)) * 8));
int64_t* ln_g = (int64_t*)(poly_ln_ptr_i64_i32_i32_ptr_i64(g_pad, m2, m2, invs));
int32_t ln_len = g_out_len;
int64_t* diff = (int64_t*)(calloc(((int64_t)(m2)), 8));
int32_t i = 0;
while (i < m2) {
int64_t fi = ((i < lf) ? (f[i]) : (0));
int64_t d = FLOW_CHECKED_MOD(((fi - ln_g[i])), (MOD));
if (d < 0) {
d = (d + MOD);
}
diff[i] = d;
i = (i + 1);
}
diff[0] = FLOW_CHECKED_MOD(((diff[0] + 1)), (MOD));
int64_t* new_g = (int64_t*)(polymul_ptr_i64_i32_ptr_i64_i32(g, m, diff, m2));
int32_t new_len = g_out_len;
int32_t nl = ((new_len > m2) ? (m2) : (new_len));
memcpy(g, new_g, (((int64_t)(nl)) * 8));
free(g_pad);
free(ln_g);
free(diff);
free(new_g);
m = m2;
}
g_out_len = n;
return g;
}
int64_t* special_component_i32(int32_t N) {
int64_t inv2 = FLOW_CHECKED_DIV(((MOD + 1)), (2));
int64_t* v1 = (int64_t*)(calloc(((int64_t)((N + 1))), 8));
v1[0] = 1;
int32_t p = 2;
while (p <= N) {
int32_t d = p;
while (d <= N) {
v1[d] = FLOW_CHECKED_MOD(((v1[d] + v1[(d - p)])), (MOD));
d = (d + 1);
}
p = FLOW_CHECKED_SHL((p), (1));
}
int64_t* vminus = (int64_t*)(calloc(((int64_t)((N + 1))), 8));
vminus[0] = 1;
int32_t p2 = 2;
while (p2 <= N) {
int64_t* new_arr = (int64_t*)(calloc(((int64_t)((N + 1))), 8));
int32_t d = 0;
while (d <= N) {
int64_t val = vminus[d];
if (d >= p2) {
val = FLOW_CHECKED_MOD(((val - new_arr[(d - p2)])), (MOD));
if (val < 0) {
val = (val + MOD);
}
}
new_arr[d] = val;
d = (d + 1);
}
int32_t d2 = 0;
while (d2 <= N) {
vminus[d2] = new_arr[d2];
d2 = (d2 + 1);
}
free(new_arr);
p2 = FLOW_CHECKED_SHL((p2), (1));
}
int64_t* pser = (int64_t*)(calloc(((int64_t)((N + 1))), 8));
int32_t d3 = 0;
while (d3 <= N) {
int64_t t1 = v1[d3];
if (d3 > 0) {
t1 = FLOW_CHECKED_MOD(((t1 + v1[(d3 - 1)])), (MOD));
}
int64_t t2 = vminus[d3];
if (d3 > 0) {
t2 = FLOW_CHECKED_MOD(((t2 - vminus[(d3 - 1)])), (MOD));
if (t2 < 0) {
t2 = (t2 + MOD);
}
}
pser[d3] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((t1 + t2)), (MOD)) * inv2)), (MOD));
d3 = (d3 + 1);
}
int64_t* a = (int64_t*)(calloc(((int64_t)((N + 1))), 8));
int64_t s = 0;
int32_t d4 = 0;
while (d4 <= N) {
s = FLOW_CHECKED_MOD(((s + pser[d4])), (MOD));
a[d4] = s;
d4 = (d4 + 1);
}
int64_t* b = (int64_t*)(calloc(((int64_t)((N + 1))), 8));
int32_t d5 = 0;
while (d5 <= N) {
int64_t val = a[d5];
if (d5 >= 2) {
val = FLOW_CHECKED_MOD(((val + b[(d5 - 2)])), (MOD));
}
b[d5] = val;
d5 = (d5 + 1);
}
free(v1);
free(vminus);
free(pser);
free(a);
return b;
}
void add_component_multiplicities_ptr_i64_i32(int64_t* c, int32_t N) {
int32_t limit_phi = (2 * N);
int32_t sieve_n = (limit_phi + 1);
int8_t* bs = (int8_t*)(malloc(((int64_t)((sieve_n + 1)))));
memset(bs, 1, ((int64_t)((sieve_n + 1))));
bs[0] = 0;
bs[1] = 0;
int32_t p = 2;
while ((((int64_t)(p)) * ((int64_t)(p))) <= ((int64_t)(sieve_n))) {
if (bs[p] != 0) {
int32_t j = (p * p);
while (j <= sieve_n) {
bs[j] = 0;
j = (j + p);
}
}
p = (p + 1);
}
int32_t prime_count = 0;
int32_t i = 2;
while (i <= sieve_n) {
if (bs[i] != 0) {
prime_count = (prime_count + 1);
}
i = (i + 1);
}
int32_t* primes = (int32_t*)(malloc((((int64_t)(prime_count)) * 4)));
int32_t idx = 0;
int32_t i2 = 2;
while (i2 <= sieve_n) {
if (bs[i2] != 0) {
primes[idx] = i2;
idx = (idx + 1);
}
i2 = (i2 + 1);
}
free(bs);
int32_t* odd_primes = (int32_t*)(malloc((((int64_t)(prime_count)) * 4)));
int32_t nop = 0;
int32_t i3 = 0;
while (i3 < prime_count) {
if ((primes[i3] & 1) != 0) {
odd_primes[nop] = primes[i3];
nop = (nop + 1);
}
i3 = (i3 + 1);
}
int32_t stack_cap = 200000;
int32_t* stack_start = (int32_t*)(malloc((((int64_t)(stack_cap)) * 4)));
int64_t* stack_n = (int64_t*)(malloc((((int64_t)(stack_cap)) * 8)));
int64_t* stack_phi = (int64_t*)(malloc((((int64_t)(stack_cap)) * 8)));
int32_t sp = 0;
stack_start[sp] = 0;
stack_n[sp] = 1;
stack_phi[sp] = 1;
sp = (sp + 1);
while (sp > 0) {
sp = (sp - 1);
int32_t f_start = stack_start[sp];
int64_t f_n = stack_n[sp];
int64_t f_phi = stack_phi[sp];
if (f_n > 1) {
int64_t ph = f_phi;
int64_t deg0 = FLOW_CHECKED_DIV((ph), (2));
int64_t w = 0;
int32_t k = 0;
while (1) {
int64_t deg = 0;
if ((k == 0 || k == 1)) {
deg = deg0;
} else {
deg = (ph * FLOW_CHECKED_SHL((((int64_t)(1))), ((k - 2))));
}
w = (w + deg);
if (w > ((int64_t)(N))) {
break;
}
c[w] = (c[w] + 1);
k = (k + 1);
}
}
int32_t i = f_start;
while (i < nop) {
int32_t p_val = odd_primes[i];
if ((f_phi * ((int64_t)((p_val - 1)))) > ((int64_t)(limit_phi))) {
break;
}
stack_start[sp] = (i + 1);
stack_n[sp] = (f_n * ((int64_t)(p_val)));
stack_phi[sp] = (f_phi * ((int64_t)((p_val - 1))));
sp = (sp + 1);
int64_t n_e = ((f_n * ((int64_t)(p_val))) * ((int64_t)(p_val)));
int64_t phi_e = ((f_phi * ((int64_t)((p_val - 1)))) * ((int64_t)(p_val)));
while (phi_e <= ((int64_t)(limit_phi))) {
stack_start[sp] = (i + 1);
stack_n[sp] = n_e;
stack_phi[sp] = phi_e;
sp = (sp + 1);
n_e = (n_e * ((int64_t)(p_val)));
phi_e = (phi_e * ((int64_t)(p_val)));
}
i = (i + 1);
}
}
free(stack_start);
free(stack_n);
free(stack_phi);
free(primes);
free(odd_primes);
}
int64_t solve_i32(int32_t N) {
int64_t* c = (int64_t*)(calloc(((int64_t)((N + 1))), 8));
add_component_multiplicities_ptr_i64_i32(c, N);
int64_t* g = (int64_t*)(calloc(((int64_t)((N + 1))), 8));
int32_t d = 1;
while (d <= N) {
int64_t cd = c[d];
if (cd != 0) {
int64_t add_val = FLOW_CHECKED_MOD(((((int64_t)(d)) * FLOW_CHECKED_MOD((cd), (MOD)))), (MOD));
int32_t k = d;
while (k <= N) {
g[k] = FLOW_CHECKED_MOD(((g[k] + add_val)), (MOD));
k = (k + d);
}
}
d = (d + 1);
}
int64_t* invs = (int64_t*)(calloc(((int64_t)((N + 2))), 8));
int32_t i = 1;
while (i <= (N + 1)) {
invs[i] = inv_mod_i64(((int64_t)(i)));
i = (i + 1);
}
int64_t* h = (int64_t*)(calloc(((int64_t)((N + 1))), 8));
int32_t k = 1;
while (k <= N) {
h[k] = FLOW_CHECKED_MOD(((g[k] * invs[k])), (MOD));
k = (k + 1);
}
int64_t* colored = (int64_t*)(poly_exp_ptr_i64_i32_i32_ptr_i64(h, (N + 1), (N + 1), invs));
int32_t colored_len = g_out_len;
int64_t* special = (int64_t*)(special_component_i32(N));
int64_t* total = (int64_t*)(polymul_ptr_i64_i32_ptr_i64_i32(colored, colored_len, special, (N + 1)));
int32_t total_len = g_out_len;
int64_t result = FLOW_CHECKED_MOD((total[N]), (MOD));
free(c);
free(g);
free(invs);
free(h);
free(colored);
free(special);
free(total);
return result;
}
int32_t main(void) {
printf("%lld\n", solve_i32(10000));
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 @malloc(i64) -> !llvm.ptr
func.func private @memcpy(!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
func.func private @memset(!llvm.ptr, i32, i64) -> !llvm.ptr
// Constant: MOD
llvm.mlir.global internal constant @MOD(998244353 : i64) : i64
// Constant: PRIMITIVE_ROOT
llvm.mlir.global internal constant @PRIMITIVE_ROOT(3 : i64) : i64
// Module static: g_out_len
llvm.mlir.global internal @g_out_len(0 : i32) : i32
// Module static: g_prime_count
llvm.mlir.global internal @g_prime_count(0 : i32) : i32
func.func @powmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%0 = arith.constant 1 : i32
%2 = arith.extsi %0 : i32 to i64
%1 = arith.remsi %2, %arg2 : i64
%3 = llvm.mlir.constant(1 : i64) : i64
%4 = llvm.alloca %3 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %4 : i64, !llvm.ptr
%5 = arith.remsi %arg0, %arg2 : i64
%6 = llvm.mlir.constant(1 : i64) : i64
%7 = llvm.alloca %6 x i64 : (i64) -> !llvm.ptr
llvm.store %5, %7 : i64, !llvm.ptr
%8 = llvm.load %7 : !llvm.ptr -> i64
%9 = arith.constant 0 : i32
%11 = arith.extsi %9 : i32 to i64
%10 = arith.cmpi slt, %8, %11 : i64
cf.cond_br %10, ^bb0, ^bb1
^bb0:
%12 = llvm.load %7 : !llvm.ptr -> i64
%13 = arith.addi %12, %arg2 : i64
llvm.store %13, %7 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%14 = llvm.mlir.constant(1 : i64) : i64
%15 = llvm.alloca %14 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %15 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%16 = llvm.load %15 : !llvm.ptr -> i64
%17 = arith.constant 0 : i32
%19 = arith.extsi %17 : i32 to i64
%18 = arith.cmpi sgt, %16, %19 : i64
cf.cond_br %18, ^bb4, ^bb5
^bb4:
%20 = llvm.load %15 : !llvm.ptr -> i64
%21 = arith.constant 2 : i32
%23 = arith.extsi %21 : i32 to i64
%22 = arith.remsi %20, %23 : i64
%24 = arith.constant 1 : i32
%26 = arith.extsi %24 : i32 to i64
%25 = arith.cmpi eq, %22, %26 : i64
cf.cond_br %25, ^bb6, ^bb7
^bb6:
%27 = llvm.load %4 : !llvm.ptr -> i64
%28 = llvm.load %7 : !llvm.ptr -> i64
%29 = arith.muli %27, %28 : i64
%30 = arith.remsi %29, %arg2 : i64
llvm.store %30, %4 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%31 = llvm.load %7 : !llvm.ptr -> i64
%32 = llvm.load %7 : !llvm.ptr -> i64
%33 = arith.muli %31, %32 : i64
%34 = arith.remsi %33, %arg2 : i64
llvm.store %34, %7 : i64, !llvm.ptr
%35 = llvm.load %15 : !llvm.ptr -> i64
%36 = arith.constant 2 : i32
%38 = arith.extsi %36 : i32 to i64
%37 = arith.divsi %35, %38 : i64
llvm.store %37, %15 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%39 = llvm.load %4 : !llvm.ptr -> i64
func.return %39 : i64
}
func.func @inv_mod(%arg0: i64) -> i64 {
%41 = llvm.mlir.addressof @MOD : !llvm.ptr
%42 = llvm.load %41 : !llvm.ptr -> i64
%43 = arith.constant 2 : i32
%45 = arith.extsi %43 : i32 to i64
%44 = arith.subi %42, %45 : i64
%46 = llvm.mlir.addressof @MOD : !llvm.ptr
%47 = llvm.load %46 : !llvm.ptr -> i64
%40 = func.call @powmod(%arg0, %44, %47) : (i64, i64, i64) -> i64
func.return %40 : i64
}
func.func @ntt(%arg0: !llvm.ptr, %arg1: i32, %arg2: i32) -> () {
%48 = arith.constant 0 : i32
%49 = llvm.mlir.constant(1 : i64) : i64
%50 = llvm.alloca %49 x i32 : (i64) -> !llvm.ptr
llvm.store %48, %50 : i32, !llvm.ptr
%51 = arith.constant 1 : i32
%52 = llvm.mlir.constant(1 : i64) : i64
%53 = llvm.alloca %52 x i32 : (i64) -> !llvm.ptr
llvm.store %51, %53 : i32, !llvm.ptr
cf.br ^bb9
^bb9:
%54 = llvm.load %53 : !llvm.ptr -> i32
%55 = arith.cmpi slt, %54, %arg1 : i32
cf.cond_br %55, ^bb10, ^bb11
^bb10:
%56 = arith.constant 1 : i32
%57 = arith.shrsi %arg1, %56 : i32
%58 = llvm.mlir.constant(1 : i64) : i64
%59 = llvm.alloca %58 x i32 : (i64) -> !llvm.ptr
llvm.store %57, %59 : i32, !llvm.ptr
cf.br ^bb12
^bb12:
%60 = llvm.load %50 : !llvm.ptr -> i32
%61 = llvm.load %59 : !llvm.ptr -> i32
%62 = arith.andi %60, %61 : i32
%63 = arith.constant 0 : i32
%64 = arith.cmpi ne, %62, %63 : i32
cf.cond_br %64, ^bb13, ^bb14
^bb13:
%65 = llvm.load %50 : !llvm.ptr -> i32
%66 = llvm.load %59 : !llvm.ptr -> i32
%67 = arith.xori %65, %66 : i32
llvm.store %67, %50 : i32, !llvm.ptr
%68 = llvm.load %59 : !llvm.ptr -> i32
%69 = arith.constant 1 : i32
%70 = arith.shrsi %68, %69 : i32
llvm.store %70, %59 : i32, !llvm.ptr
cf.br ^bb12
^bb14:
%71 = llvm.load %50 : !llvm.ptr -> i32
%72 = llvm.load %59 : !llvm.ptr -> i32
%73 = arith.xori %71, %72 : i32
llvm.store %73, %50 : i32, !llvm.ptr
%74 = llvm.load %53 : !llvm.ptr -> i32
%75 = llvm.load %50 : !llvm.ptr -> i32
%76 = arith.cmpi slt, %74, %75 : i32
cf.cond_br %76, ^bb15, ^bb16
^bb15:
%78 = llvm.load %53 : !llvm.ptr -> i32
%79 = arith.extsi %78 : i32 to i64
%80 = llvm.getelementptr %arg0[%79] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%77 = llvm.load %80 : !llvm.ptr -> i64
%82 = llvm.load %50 : !llvm.ptr -> i32
%83 = arith.extsi %82 : i32 to i64
%84 = llvm.getelementptr %arg0[%83] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%81 = llvm.load %84 : !llvm.ptr -> i64
%85 = llvm.load %53 : !llvm.ptr -> i32
%86 = arith.extsi %85 : i32 to i64
%87 = llvm.getelementptr %arg0[%86] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %81, %87 : i64, !llvm.ptr
%88 = llvm.load %50 : !llvm.ptr -> i32
%89 = arith.extsi %88 : i32 to i64
%90 = llvm.getelementptr %arg0[%89] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %77, %90 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%91 = llvm.load %53 : !llvm.ptr -> i32
%92 = arith.constant 1 : i32
%93 = arith.addi %91, %92 : i32
llvm.store %93, %53 : i32, !llvm.ptr
cf.br ^bb9
^bb11:
%94 = arith.constant 2 : i32
%95 = llvm.mlir.constant(1 : i64) : i64
%96 = llvm.alloca %95 x i32 : (i64) -> !llvm.ptr
llvm.store %94, %96 : i32, !llvm.ptr
cf.br ^bb18
^bb18:
%97 = llvm.load %96 : !llvm.ptr -> i32
%98 = arith.cmpi sle, %97, %arg1 : i32
cf.cond_br %98, ^bb19, ^bb20
^bb19:
%100 = llvm.mlir.addressof @PRIMITIVE_ROOT : !llvm.ptr
%101 = llvm.load %100 : !llvm.ptr -> i64
%102 = llvm.mlir.addressof @MOD : !llvm.ptr
%103 = llvm.load %102 : !llvm.ptr -> i64
%104 = arith.constant 1 : i32
%106 = arith.extsi %104 : i32 to i64
%105 = arith.subi %103, %106 : i64
%107 = llvm.load %96 : !llvm.ptr -> i32
%108 = arith.extsi %107 : i32 to i64
%109 = arith.divsi %105, %108 : i64
%110 = llvm.mlir.addressof @MOD : !llvm.ptr
%111 = llvm.load %110 : !llvm.ptr -> i64
%99 = func.call @powmod(%101, %109, %111) : (i64, i64, i64) -> i64
%112 = llvm.mlir.constant(1 : i64) : i64
%113 = llvm.alloca %112 x i64 : (i64) -> !llvm.ptr
llvm.store %99, %113 : i64, !llvm.ptr
%114 = arith.constant 0 : i32
%115 = arith.cmpi ne, %arg2, %114 : i32
cf.cond_br %115, ^bb21, ^bb22
^bb21:
%117 = llvm.load %113 : !llvm.ptr -> i64
%118 = llvm.mlir.addressof @MOD : !llvm.ptr
%119 = llvm.load %118 : !llvm.ptr -> i64
%120 = arith.constant 2 : i32
%122 = arith.extsi %120 : i32 to i64
%121 = arith.subi %119, %122 : i64
%123 = llvm.mlir.addressof @MOD : !llvm.ptr
%124 = llvm.load %123 : !llvm.ptr -> i64
%116 = func.call @powmod(%117, %121, %124) : (i64, i64, i64) -> i64
llvm.store %116, %113 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%125 = llvm.load %96 : !llvm.ptr -> i32
%126 = arith.constant 1 : i32
%127 = arith.shrsi %125, %126 : i32
%128 = arith.constant 0 : i32
%129 = llvm.mlir.constant(1 : i64) : i64
%130 = llvm.alloca %129 x i32 : (i64) -> !llvm.ptr
llvm.store %128, %130 : i32, !llvm.ptr
cf.br ^bb24
^bb24:
%131 = llvm.load %130 : !llvm.ptr -> i32
%132 = arith.cmpi slt, %131, %arg1 : i32
cf.cond_br %132, ^bb25, ^bb26
^bb25:
%133 = arith.constant 1 : i32
%134 = arith.extsi %133 : i32 to i64
%135 = llvm.mlir.constant(1 : i64) : i64
%136 = llvm.alloca %135 x i64 : (i64) -> !llvm.ptr
llvm.store %134, %136 : i64, !llvm.ptr
%137 = arith.constant 0 : i32
%138 = llvm.mlir.constant(1 : i64) : i64
%139 = llvm.alloca %138 x i32 : (i64) -> !llvm.ptr
llvm.store %137, %139 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%140 = llvm.load %139 : !llvm.ptr -> i32
%141 = arith.cmpi slt, %140, %127 : i32
cf.cond_br %141, ^bb28, ^bb29
^bb28:
%143 = llvm.load %130 : !llvm.ptr -> i32
%144 = llvm.load %139 : !llvm.ptr -> i32
%145 = arith.addi %143, %144 : i32
%146 = arith.extsi %145 : i32 to i64
%147 = llvm.getelementptr %arg0[%146] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%142 = llvm.load %147 : !llvm.ptr -> i64
%149 = llvm.load %130 : !llvm.ptr -> i32
%150 = llvm.load %139 : !llvm.ptr -> i32
%151 = arith.addi %149, %150 : i32
%152 = arith.addi %151, %127 : i32
%153 = arith.extsi %152 : i32 to i64
%154 = llvm.getelementptr %arg0[%153] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%148 = llvm.load %154 : !llvm.ptr -> i64
%155 = llvm.load %136 : !llvm.ptr -> i64
%156 = arith.muli %148, %155 : i64
%157 = llvm.mlir.addressof @MOD : !llvm.ptr
%158 = llvm.load %157 : !llvm.ptr -> i64
%159 = arith.remsi %156, %158 : i64
%160 = arith.addi %142, %159 : i64
%161 = llvm.mlir.addressof @MOD : !llvm.ptr
%162 = llvm.load %161 : !llvm.ptr -> i64
%163 = arith.remsi %160, %162 : i64
%164 = llvm.load %130 : !llvm.ptr -> i32
%165 = llvm.load %139 : !llvm.ptr -> i32
%166 = arith.addi %164, %165 : i32
%167 = arith.extsi %166 : i32 to i64
%168 = llvm.getelementptr %arg0[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %163, %168 : i64, !llvm.ptr
%169 = arith.subi %142, %159 : i64
%170 = llvm.mlir.addressof @MOD : !llvm.ptr
%171 = llvm.load %170 : !llvm.ptr -> i64
%172 = arith.remsi %169, %171 : i64
%173 = llvm.mlir.constant(1 : i64) : i64
%174 = llvm.alloca %173 x i64 : (i64) -> !llvm.ptr
llvm.store %172, %174 : i64, !llvm.ptr
%175 = llvm.load %174 : !llvm.ptr -> i64
%176 = arith.constant 0 : i32
%178 = arith.extsi %176 : i32 to i64
%177 = arith.cmpi slt, %175, %178 : i64
cf.cond_br %177, ^bb30, ^bb31
^bb30:
%179 = llvm.load %174 : !llvm.ptr -> i64
%180 = llvm.mlir.addressof @MOD : !llvm.ptr
%181 = llvm.load %180 : !llvm.ptr -> i64
%182 = arith.addi %179, %181 : i64
llvm.store %182, %174 : i64, !llvm.ptr
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%183 = llvm.load %174 : !llvm.ptr -> i64
%184 = llvm.load %130 : !llvm.ptr -> i32
%185 = llvm.load %139 : !llvm.ptr -> i32
%186 = arith.addi %184, %185 : i32
%187 = arith.addi %186, %127 : i32
%188 = arith.extsi %187 : i32 to i64
%189 = llvm.getelementptr %arg0[%188] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %183, %189 : i64, !llvm.ptr
%190 = llvm.load %136 : !llvm.ptr -> i64
%191 = llvm.load %113 : !llvm.ptr -> i64
%192 = arith.muli %190, %191 : i64
%193 = llvm.mlir.addressof @MOD : !llvm.ptr
%194 = llvm.load %193 : !llvm.ptr -> i64
%195 = arith.remsi %192, %194 : i64
llvm.store %195, %136 : i64, !llvm.ptr
%196 = llvm.load %139 : !llvm.ptr -> i32
%197 = arith.constant 1 : i32
%198 = arith.addi %196, %197 : i32
llvm.store %198, %139 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%199 = llvm.load %130 : !llvm.ptr -> i32
%200 = llvm.load %96 : !llvm.ptr -> i32
%201 = arith.addi %199, %200 : i32
llvm.store %201, %130 : i32, !llvm.ptr
cf.br ^bb24
^bb26:
%202 = llvm.load %96 : !llvm.ptr -> i32
%203 = arith.constant 1 : i32
%204 = arith.shli %202, %203 : i32
llvm.store %204, %96 : i32, !llvm.ptr
cf.br ^bb18
^bb20:
%205 = arith.constant 0 : i32
%206 = arith.cmpi ne, %arg2, %205 : i32
cf.cond_br %206, ^bb33, ^bb34
^bb33:
%208 = arith.extsi %arg1 : i32 to i64
%209 = llvm.mlir.addressof @MOD : !llvm.ptr
%210 = llvm.load %209 : !llvm.ptr -> i64
%211 = arith.constant 2 : i32
%213 = arith.extsi %211 : i32 to i64
%212 = arith.subi %210, %213 : i64
%214 = llvm.mlir.addressof @MOD : !llvm.ptr
%215 = llvm.load %214 : !llvm.ptr -> i64
%207 = func.call @powmod(%208, %212, %215) : (i64, i64, i64) -> i64
%216 = arith.constant 0 : i32
%217 = llvm.mlir.constant(1 : i64) : i64
%218 = llvm.alloca %217 x i32 : (i64) -> !llvm.ptr
llvm.store %216, %218 : i32, !llvm.ptr
cf.br ^bb36
^bb36:
%219 = llvm.load %218 : !llvm.ptr -> i32
%220 = arith.cmpi slt, %219, %arg1 : i32
cf.cond_br %220, ^bb37, ^bb38
^bb37:
%222 = llvm.load %218 : !llvm.ptr -> i32
%223 = arith.extsi %222 : i32 to i64
%224 = llvm.getelementptr %arg0[%223] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%221 = llvm.load %224 : !llvm.ptr -> i64
%225 = arith.muli %221, %207 : i64
%226 = llvm.mlir.addressof @MOD : !llvm.ptr
%227 = llvm.load %226 : !llvm.ptr -> i64
%228 = arith.remsi %225, %227 : i64
%229 = llvm.load %218 : !llvm.ptr -> i32
%230 = arith.extsi %229 : i32 to i64
%231 = llvm.getelementptr %arg0[%230] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %228, %231 : i64, !llvm.ptr
%232 = llvm.load %218 : !llvm.ptr -> i32
%233 = arith.constant 1 : i32
%234 = arith.addi %232, %233 : i32
llvm.store %234, %218 : i32, !llvm.ptr
cf.br ^bb36
^bb38:
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
func.return
}
func.func @polymul(%arg0: !llvm.ptr, %arg1: i32, %arg2: !llvm.ptr, %arg3: i32) -> !llvm.ptr {
%235 = arith.constant 0 : i32
%236 = arith.cmpi eq, %arg1, %235 : i32
%237 = scf.if %236 -> (i1) {
%238 = arith.constant true
scf.yield %238 : i1
} else {
%239 = arith.constant 0 : i32
%240 = arith.cmpi eq, %arg3, %239 : i32
scf.yield %240 : i1
}
cf.cond_br %237, ^bb39, ^bb40
^bb39:
%241 = arith.constant 0 : i32
%242 = llvm.mlir.addressof @g_out_len : !llvm.ptr
llvm.store %241, %242 : i32, !llvm.ptr
%243 = llvm.mlir.zero : !llvm.ptr
func.return %243 : !llvm.ptr
^bb40:
cf.br ^bb41
^bb41:
%244 = arith.addi %arg1, %arg3 : i32
%245 = arith.constant 1 : i32
%246 = arith.subi %244, %245 : i32
%247 = arith.constant 32 : i32
%248 = arith.cmpi sle, %arg1, %247 : i32
%249 = scf.if %248 -> (i1) {
%250 = arith.constant true
scf.yield %250 : i1
} else {
%251 = arith.constant 32 : i32
%252 = arith.cmpi sle, %arg3, %251 : i32
scf.yield %252 : i1
}
cf.cond_br %249, ^bb42, ^bb43
^bb42:
%254 = arith.extsi %246 : i32 to i64
%255 = arith.constant 8 : i32
%256 = arith.extsi %255 : i32 to i64
%253 = func.call @calloc(%254, %256) : (i64, i64) -> !llvm.ptr
%257 = arith.constant 0 : i32
%258 = llvm.mlir.constant(1 : i64) : i64
%259 = llvm.alloca %258 x i32 : (i64) -> !llvm.ptr
llvm.store %257, %259 : i32, !llvm.ptr
cf.br ^bb45
^bb45:
%260 = llvm.load %259 : !llvm.ptr -> i32
%261 = arith.cmpi slt, %260, %arg1 : i32
cf.cond_br %261, ^bb46, ^bb47
^bb46:
%263 = llvm.load %259 : !llvm.ptr -> i32
%264 = arith.extsi %263 : i32 to i64
%265 = llvm.getelementptr %arg0[%264] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%262 = llvm.load %265 : !llvm.ptr -> i64
%266 = arith.constant 0 : i32
%268 = arith.extsi %266 : i32 to i64
%267 = arith.cmpi ne, %262, %268 : i64
cf.cond_br %267, ^bb48, ^bb49
^bb48:
%269 = arith.constant 0 : i32
%270 = llvm.mlir.constant(1 : i64) : i64
%271 = llvm.alloca %270 x i32 : (i64) -> !llvm.ptr
llvm.store %269, %271 : i32, !llvm.ptr
cf.br ^bb51
^bb51:
%272 = llvm.load %271 : !llvm.ptr -> i32
%273 = arith.cmpi slt, %272, %arg3 : i32
cf.cond_br %273, ^bb52, ^bb53
^bb52:
%275 = llvm.load %259 : !llvm.ptr -> i32
%276 = llvm.load %271 : !llvm.ptr -> i32
%277 = arith.addi %275, %276 : i32
%278 = arith.extsi %277 : i32 to i64
%279 = llvm.getelementptr %253[%278] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%274 = llvm.load %279 : !llvm.ptr -> i64
%281 = llvm.load %259 : !llvm.ptr -> i32
%282 = arith.extsi %281 : i32 to i64
%283 = llvm.getelementptr %arg0[%282] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%280 = llvm.load %283 : !llvm.ptr -> i64
%285 = llvm.load %271 : !llvm.ptr -> i32
%286 = arith.extsi %285 : i32 to i64
%287 = llvm.getelementptr %arg2[%286] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%284 = llvm.load %287 : !llvm.ptr -> i64
%288 = arith.muli %280, %284 : i64
%289 = arith.addi %274, %288 : i64
%290 = llvm.mlir.addressof @MOD : !llvm.ptr
%291 = llvm.load %290 : !llvm.ptr -> i64
%292 = arith.remsi %289, %291 : i64
%293 = llvm.load %259 : !llvm.ptr -> i32
%294 = llvm.load %271 : !llvm.ptr -> i32
%295 = arith.addi %293, %294 : i32
%296 = arith.extsi %295 : i32 to i64
%297 = llvm.getelementptr %253[%296] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %292, %297 : i64, !llvm.ptr
%298 = llvm.load %271 : !llvm.ptr -> i32
%299 = arith.constant 1 : i32
%300 = arith.addi %298, %299 : i32
llvm.store %300, %271 : i32, !llvm.ptr
cf.br ^bb51
^bb53:
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%301 = llvm.load %259 : !llvm.ptr -> i32
%302 = arith.constant 1 : i32
%303 = arith.addi %301, %302 : i32
llvm.store %303, %259 : i32, !llvm.ptr
cf.br ^bb45
^bb47:
%304 = llvm.mlir.addressof @g_out_len : !llvm.ptr
llvm.store %246, %304 : i32, !llvm.ptr
func.return %253 : !llvm.ptr
^bb43:
cf.br ^bb44
^bb44:
%305 = arith.constant 1 : i32
%306 = llvm.mlir.constant(1 : i64) : i64
%307 = llvm.alloca %306 x i32 : (i64) -> !llvm.ptr
llvm.store %305, %307 : i32, !llvm.ptr
cf.br ^bb54
^bb54:
%308 = llvm.load %307 : !llvm.ptr -> i32
%309 = arith.cmpi slt, %308, %246 : i32
cf.cond_br %309, ^bb55, ^bb56
^bb55:
%310 = llvm.load %307 : !llvm.ptr -> i32
%311 = arith.constant 1 : i32
%312 = arith.shli %310, %311 : i32
llvm.store %312, %307 : i32, !llvm.ptr
cf.br ^bb54
^bb56:
%314 = llvm.load %307 : !llvm.ptr -> i32
%315 = arith.extsi %314 : i32 to i64
%316 = arith.constant 8 : i32
%317 = arith.extsi %316 : i32 to i64
%313 = func.call @calloc(%315, %317) : (i64, i64) -> !llvm.ptr
%319 = llvm.load %307 : !llvm.ptr -> i32
%320 = arith.extsi %319 : i32 to i64
%321 = arith.constant 8 : i32
%322 = arith.extsi %321 : i32 to i64
%318 = func.call @calloc(%320, %322) : (i64, i64) -> !llvm.ptr
%324 = arith.extsi %arg1 : i32 to i64
%325 = arith.constant 8 : i32
%327 = arith.extsi %325 : i32 to i64
%326 = arith.muli %324, %327 : i64
%323 = func.call @memcpy(%313, %arg0, %326) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
%329 = arith.extsi %arg3 : i32 to i64
%330 = arith.constant 8 : i32
%332 = arith.extsi %330 : i32 to i64
%331 = arith.muli %329, %332 : i64
%328 = func.call @memcpy(%318, %arg2, %331) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
%334 = llvm.load %307 : !llvm.ptr -> i32
%335 = arith.constant 0 : i32
func.call @ntt(%313, %334, %335) : (!llvm.ptr, i32, i32) -> ()
%337 = llvm.load %307 : !llvm.ptr -> i32
%338 = arith.constant 0 : i32
func.call @ntt(%318, %337, %338) : (!llvm.ptr, i32, i32) -> ()
%339 = arith.constant 0 : i32
%340 = llvm.mlir.constant(1 : i64) : i64
%341 = llvm.alloca %340 x i32 : (i64) -> !llvm.ptr
llvm.store %339, %341 : i32, !llvm.ptr
cf.br ^bb57
^bb57:
%342 = llvm.load %341 : !llvm.ptr -> i32
%343 = llvm.load %307 : !llvm.ptr -> i32
%344 = arith.cmpi slt, %342, %343 : i32
cf.cond_br %344, ^bb58, ^bb59
^bb58:
%346 = llvm.load %341 : !llvm.ptr -> i32
%347 = arith.extsi %346 : i32 to i64
%348 = llvm.getelementptr %313[%347] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%345 = llvm.load %348 : !llvm.ptr -> i64
%350 = llvm.load %341 : !llvm.ptr -> i32
%351 = arith.extsi %350 : i32 to i64
%352 = llvm.getelementptr %318[%351] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%349 = llvm.load %352 : !llvm.ptr -> i64
%353 = arith.muli %345, %349 : i64
%354 = llvm.mlir.addressof @MOD : !llvm.ptr
%355 = llvm.load %354 : !llvm.ptr -> i64
%356 = arith.remsi %353, %355 : i64
%357 = llvm.load %341 : !llvm.ptr -> i32
%358 = arith.extsi %357 : i32 to i64
%359 = llvm.getelementptr %313[%358] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %356, %359 : i64, !llvm.ptr
%360 = llvm.load %341 : !llvm.ptr -> i32
%361 = arith.constant 1 : i32
%362 = arith.addi %360, %361 : i32
llvm.store %362, %341 : i32, !llvm.ptr
cf.br ^bb57
^bb59:
%364 = llvm.load %307 : !llvm.ptr -> i32
%365 = arith.constant 1 : i32
func.call @ntt(%313, %364, %365) : (!llvm.ptr, i32, i32) -> ()
%367 = arith.extsi %246 : i32 to i64
%368 = arith.constant 8 : i32
%370 = arith.extsi %368 : i32 to i64
%369 = arith.muli %367, %370 : i64
%366 = func.call @malloc(%369) : (i64) -> !llvm.ptr
%372 = arith.extsi %246 : i32 to i64
%373 = arith.constant 8 : i32
%375 = arith.extsi %373 : i32 to i64
%374 = arith.muli %372, %375 : i64
%371 = func.call @memcpy(%366, %313, %374) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
func.call @free(%313) : (!llvm.ptr) -> ()
func.call @free(%318) : (!llvm.ptr) -> ()
%378 = llvm.mlir.addressof @g_out_len : !llvm.ptr
llvm.store %246, %378 : i32, !llvm.ptr
func.return %366 : !llvm.ptr
}
func.func @poly_der(%arg0: !llvm.ptr, %arg1: i32) -> !llvm.ptr {
%379 = arith.constant 1 : i32
%380 = arith.cmpi sle, %arg1, %379 : i32
cf.cond_br %380, ^bb60, ^bb61
^bb60:
%381 = arith.constant 0 : i32
%382 = llvm.mlir.addressof @g_out_len : !llvm.ptr
llvm.store %381, %382 : i32, !llvm.ptr
%383 = llvm.mlir.zero : !llvm.ptr
func.return %383 : !llvm.ptr
^bb61:
cf.br ^bb62
^bb62:
%384 = arith.constant 1 : i32
%385 = arith.subi %arg1, %384 : i32
%387 = arith.extsi %385 : i32 to i64
%388 = arith.constant 8 : i32
%390 = arith.extsi %388 : i32 to i64
%389 = arith.muli %387, %390 : i64
%386 = func.call @malloc(%389) : (i64) -> !llvm.ptr
%391 = arith.constant 1 : i32
%392 = llvm.mlir.constant(1 : i64) : i64
%393 = llvm.alloca %392 x i32 : (i64) -> !llvm.ptr
llvm.store %391, %393 : i32, !llvm.ptr
cf.br ^bb63
^bb63:
%394 = llvm.load %393 : !llvm.ptr -> i32
%395 = arith.cmpi slt, %394, %arg1 : i32
cf.cond_br %395, ^bb64, ^bb65
^bb64:
%396 = llvm.load %393 : !llvm.ptr -> i32
%397 = arith.extsi %396 : i32 to i64
%399 = llvm.load %393 : !llvm.ptr -> i32
%400 = arith.extsi %399 : i32 to i64
%401 = llvm.getelementptr %arg0[%400] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%398 = llvm.load %401 : !llvm.ptr -> i64
%402 = arith.muli %397, %398 : i64
%403 = llvm.mlir.addressof @MOD : !llvm.ptr
%404 = llvm.load %403 : !llvm.ptr -> i64
%405 = arith.remsi %402, %404 : i64
%406 = llvm.load %393 : !llvm.ptr -> i32
%407 = arith.constant 1 : i32
%408 = arith.subi %406, %407 : i32
%409 = arith.extsi %408 : i32 to i64
%410 = llvm.getelementptr %386[%409] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %405, %410 : i64, !llvm.ptr
%411 = llvm.load %393 : !llvm.ptr -> i32
%412 = arith.constant 1 : i32
%413 = arith.addi %411, %412 : i32
llvm.store %413, %393 : i32, !llvm.ptr
cf.br ^bb63
^bb65:
%414 = llvm.mlir.addressof @g_out_len : !llvm.ptr
llvm.store %385, %414 : i32, !llvm.ptr
func.return %386 : !llvm.ptr
}
func.func @poly_int(%arg0: !llvm.ptr, %arg1: i32, %arg2: !llvm.ptr) -> !llvm.ptr {
%415 = arith.constant 1 : i32
%416 = arith.addi %arg1, %415 : i32
%418 = arith.extsi %416 : i32 to i64
%419 = arith.constant 8 : i32
%420 = arith.extsi %419 : i32 to i64
%417 = func.call @calloc(%418, %420) : (i64, i64) -> !llvm.ptr
%421 = arith.constant 0 : i32
%422 = llvm.mlir.constant(1 : i64) : i64
%423 = llvm.alloca %422 x i32 : (i64) -> !llvm.ptr
llvm.store %421, %423 : i32, !llvm.ptr
cf.br ^bb66
^bb66:
%424 = llvm.load %423 : !llvm.ptr -> i32
%425 = arith.cmpi slt, %424, %arg1 : i32
cf.cond_br %425, ^bb67, ^bb68
^bb67:
%427 = llvm.load %423 : !llvm.ptr -> i32
%428 = arith.extsi %427 : i32 to i64
%429 = llvm.getelementptr %arg0[%428] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%426 = llvm.load %429 : !llvm.ptr -> i64
%431 = llvm.load %423 : !llvm.ptr -> i32
%432 = arith.constant 1 : i32
%433 = arith.addi %431, %432 : i32
%434 = arith.extsi %433 : i32 to i64
%435 = llvm.getelementptr %arg2[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%430 = llvm.load %435 : !llvm.ptr -> i64
%436 = arith.muli %426, %430 : i64
%437 = llvm.mlir.addressof @MOD : !llvm.ptr
%438 = llvm.load %437 : !llvm.ptr -> i64
%439 = arith.remsi %436, %438 : i64
%440 = llvm.load %423 : !llvm.ptr -> i32
%441 = arith.constant 1 : i32
%442 = arith.addi %440, %441 : i32
%443 = arith.extsi %442 : i32 to i64
%444 = llvm.getelementptr %417[%443] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %439, %444 : i64, !llvm.ptr
%445 = llvm.load %423 : !llvm.ptr -> i32
%446 = arith.constant 1 : i32
%447 = arith.addi %445, %446 : i32
llvm.store %447, %423 : i32, !llvm.ptr
cf.br ^bb66
^bb68:
%448 = llvm.mlir.addressof @g_out_len : !llvm.ptr
llvm.store %416, %448 : i32, !llvm.ptr
func.return %417 : !llvm.ptr
}
func.func @poly_inv(%arg0: !llvm.ptr, %arg1: i32, %arg2: i32) -> !llvm.ptr {
%450 = arith.extsi %arg2 : i32 to i64
%451 = arith.constant 8 : i32
%452 = arith.extsi %451 : i32 to i64
%449 = func.call @calloc(%450, %452) : (i64, i64) -> !llvm.ptr
%455 = arith.constant 0 : i32
%456 = arith.extsi %455 : i32 to i64
%457 = llvm.getelementptr %arg0[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%454 = llvm.load %457 : !llvm.ptr -> i64
%458 = llvm.mlir.addressof @MOD : !llvm.ptr
%459 = llvm.load %458 : !llvm.ptr -> i64
%460 = arith.constant 2 : i32
%462 = arith.extsi %460 : i32 to i64
%461 = arith.subi %459, %462 : i64
%463 = llvm.mlir.addressof @MOD : !llvm.ptr
%464 = llvm.load %463 : !llvm.ptr -> i64
%453 = func.call @powmod(%454, %461, %464) : (i64, i64, i64) -> i64
%465 = arith.constant 0 : i32
%466 = arith.extsi %465 : i32 to i64
%467 = llvm.getelementptr %449[%466] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %453, %467 : i64, !llvm.ptr
%468 = arith.constant 1 : i32
%469 = llvm.mlir.constant(1 : i64) : i64
%470 = llvm.alloca %469 x i32 : (i64) -> !llvm.ptr
llvm.store %468, %470 : i32, !llvm.ptr
cf.br ^bb69
^bb69:
%471 = llvm.load %470 : !llvm.ptr -> i32
%472 = arith.cmpi slt, %471, %arg2 : i32
cf.cond_br %472, ^bb70, ^bb71
^bb70:
%473 = llvm.load %470 : !llvm.ptr -> i32
%474 = arith.constant 2 : i32
%475 = arith.muli %473, %474 : i32
%476 = llvm.mlir.constant(1 : i64) : i64
%477 = llvm.alloca %476 x i32 : (i64) -> !llvm.ptr
llvm.store %475, %477 : i32, !llvm.ptr
%478 = llvm.load %477 : !llvm.ptr -> i32
%479 = arith.cmpi sgt, %478, %arg2 : i32
cf.cond_br %479, ^bb72, ^bb73
^bb72:
llvm.store %arg2, %477 : i32, !llvm.ptr
cf.br ^bb74
^bb73:
cf.br ^bb74
^bb74:
%480 = llvm.load %477 : !llvm.ptr -> i32
%481 = arith.cmpi sgt, %arg1, %480 : i32
%482 = scf.if %481 -> (i32) {
%483 = llvm.load %477 : !llvm.ptr -> i32
scf.yield %483 : i32
} else {
scf.yield %arg1 : i32
}
%485 = llvm.load %470 : !llvm.ptr -> i32
%484 = func.call @polymul(%arg0, %482, %449, %485) : (!llvm.ptr, i32, !llvm.ptr, i32) -> !llvm.ptr
%486 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%487 = llvm.load %486 : !llvm.ptr -> i32
%488 = llvm.load %477 : !llvm.ptr -> i32
%489 = arith.cmpi sgt, %487, %488 : i32
%490 = scf.if %489 -> (i32) {
%491 = llvm.load %477 : !llvm.ptr -> i32
scf.yield %491 : i32
} else {
scf.yield %487 : i32
}
%493 = llvm.load %477 : !llvm.ptr -> i32
%494 = arith.extsi %493 : i32 to i64
%495 = arith.constant 8 : i32
%496 = arith.extsi %495 : i32 to i64
%492 = func.call @calloc(%494, %496) : (i64, i64) -> !llvm.ptr
%497 = arith.constant 0 : i32
%498 = llvm.mlir.constant(1 : i64) : i64
%499 = llvm.alloca %498 x i32 : (i64) -> !llvm.ptr
llvm.store %497, %499 : i32, !llvm.ptr
cf.br ^bb75
^bb75:
%500 = llvm.load %499 : !llvm.ptr -> i32
%501 = arith.cmpi slt, %500, %490 : i32
cf.cond_br %501, ^bb76, ^bb77
^bb76:
%503 = llvm.load %499 : !llvm.ptr -> i32
%504 = arith.extsi %503 : i32 to i64
%505 = llvm.getelementptr %484[%504] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%502 = llvm.load %505 : !llvm.ptr -> i64
%506 = llvm.load %499 : !llvm.ptr -> i32
%507 = arith.extsi %506 : i32 to i64
%508 = llvm.getelementptr %492[%507] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %502, %508 : i64, !llvm.ptr
%509 = llvm.load %499 : !llvm.ptr -> i32
%510 = arith.constant 1 : i32
%511 = arith.addi %509, %510 : i32
llvm.store %511, %499 : i32, !llvm.ptr
cf.br ^bb75
^bb77:
func.call @free(%484) : (!llvm.ptr) -> ()
%513 = arith.constant 2 : i32
%515 = arith.constant 0 : i32
%516 = arith.extsi %515 : i32 to i64
%517 = llvm.getelementptr %492[%516] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%514 = llvm.load %517 : !llvm.ptr -> i64
%519 = arith.extsi %513 : i32 to i64
%518 = arith.subi %519, %514 : i64
%520 = llvm.mlir.addressof @MOD : !llvm.ptr
%521 = llvm.load %520 : !llvm.ptr -> i64
%522 = arith.remsi %518, %521 : i64
%523 = arith.constant 0 : i32
%524 = arith.extsi %523 : i32 to i64
%525 = llvm.getelementptr %492[%524] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %522, %525 : i64, !llvm.ptr
%527 = arith.constant 0 : i32
%528 = arith.extsi %527 : i32 to i64
%529 = llvm.getelementptr %492[%528] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%526 = llvm.load %529 : !llvm.ptr -> i64
%530 = arith.constant 0 : i32
%532 = arith.extsi %530 : i32 to i64
%531 = arith.cmpi slt, %526, %532 : i64
cf.cond_br %531, ^bb78, ^bb79
^bb78:
%534 = arith.constant 0 : i32
%535 = arith.extsi %534 : i32 to i64
%536 = llvm.getelementptr %492[%535] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%533 = llvm.load %536 : !llvm.ptr -> i64
%537 = llvm.mlir.addressof @MOD : !llvm.ptr
%538 = llvm.load %537 : !llvm.ptr -> i64
%539 = arith.addi %533, %538 : i64
%540 = arith.constant 0 : i32
%541 = arith.extsi %540 : i32 to i64
%542 = llvm.getelementptr %492[%541] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %539, %542 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%543 = arith.constant 1 : i32
%544 = llvm.mlir.constant(1 : i64) : i64
%545 = llvm.alloca %544 x i32 : (i64) -> !llvm.ptr
llvm.store %543, %545 : i32, !llvm.ptr
cf.br ^bb81
^bb81:
%546 = llvm.load %545 : !llvm.ptr -> i32
%547 = llvm.load %477 : !llvm.ptr -> i32
%548 = arith.cmpi slt, %546, %547 : i32
cf.cond_br %548, ^bb82, ^bb83
^bb82:
%549 = arith.constant 0 : i32
%551 = llvm.load %545 : !llvm.ptr -> i32
%552 = arith.extsi %551 : i32 to i64
%553 = llvm.getelementptr %492[%552] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%550 = llvm.load %553 : !llvm.ptr -> i64
%555 = arith.extsi %549 : i32 to i64
%554 = arith.subi %555, %550 : i64
%556 = llvm.mlir.addressof @MOD : !llvm.ptr
%557 = llvm.load %556 : !llvm.ptr -> i64
%558 = arith.remsi %554, %557 : i64
%559 = llvm.load %545 : !llvm.ptr -> i32
%560 = arith.extsi %559 : i32 to i64
%561 = llvm.getelementptr %492[%560] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %558, %561 : i64, !llvm.ptr
%563 = llvm.load %545 : !llvm.ptr -> i32
%564 = arith.extsi %563 : i32 to i64
%565 = llvm.getelementptr %492[%564] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%562 = llvm.load %565 : !llvm.ptr -> i64
%566 = arith.constant 0 : i32
%568 = arith.extsi %566 : i32 to i64
%567 = arith.cmpi slt, %562, %568 : i64
cf.cond_br %567, ^bb84, ^bb85
^bb84:
%570 = llvm.load %545 : !llvm.ptr -> i32
%571 = arith.extsi %570 : i32 to i64
%572 = llvm.getelementptr %492[%571] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%569 = llvm.load %572 : !llvm.ptr -> i64
%573 = llvm.mlir.addressof @MOD : !llvm.ptr
%574 = llvm.load %573 : !llvm.ptr -> i64
%575 = arith.addi %569, %574 : i64
%576 = llvm.load %545 : !llvm.ptr -> i32
%577 = arith.extsi %576 : i32 to i64
%578 = llvm.getelementptr %492[%577] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %575, %578 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
%579 = llvm.load %545 : !llvm.ptr -> i32
%580 = arith.constant 1 : i32
%581 = arith.addi %579, %580 : i32
llvm.store %581, %545 : i32, !llvm.ptr
cf.br ^bb81
^bb83:
%583 = llvm.load %470 : !llvm.ptr -> i32
%584 = llvm.load %477 : !llvm.ptr -> i32
%582 = func.call @polymul(%449, %583, %492, %584) : (!llvm.ptr, i32, !llvm.ptr, i32) -> !llvm.ptr
%585 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%586 = llvm.load %585 : !llvm.ptr -> i32
%587 = llvm.load %477 : !llvm.ptr -> i32
%588 = arith.cmpi sgt, %586, %587 : i32
%589 = scf.if %588 -> (i32) {
%590 = llvm.load %477 : !llvm.ptr -> i32
scf.yield %590 : i32
} else {
scf.yield %586 : i32
}
%592 = arith.extsi %589 : i32 to i64
%593 = arith.constant 8 : i32
%595 = arith.extsi %593 : i32 to i64
%594 = arith.muli %592, %595 : i64
%591 = func.call @memcpy(%449, %582, %594) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
func.call @free(%582) : (!llvm.ptr) -> ()
func.call @free(%492) : (!llvm.ptr) -> ()
%598 = llvm.load %477 : !llvm.ptr -> i32
llvm.store %598, %470 : i32, !llvm.ptr
cf.br ^bb69
^bb71:
%599 = llvm.mlir.addressof @g_out_len : !llvm.ptr
llvm.store %arg2, %599 : i32, !llvm.ptr
func.return %449 : !llvm.ptr
}
func.func @poly_ln(%arg0: !llvm.ptr, %arg1: i32, %arg2: i32, %arg3: !llvm.ptr) -> !llvm.ptr {
%600 = func.call @poly_der(%arg0, %arg1) : (!llvm.ptr, i32) -> !llvm.ptr
%601 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%602 = llvm.load %601 : !llvm.ptr -> i32
%603 = func.call @poly_inv(%arg0, %arg1, %arg2) : (!llvm.ptr, i32, i32) -> !llvm.ptr
%604 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%605 = llvm.load %604 : !llvm.ptr -> i32
%606 = func.call @polymul(%600, %602, %603, %605) : (!llvm.ptr, i32, !llvm.ptr, i32) -> !llvm.ptr
%607 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%608 = llvm.load %607 : !llvm.ptr -> i32
%609 = arith.constant 1 : i32
%610 = arith.subi %arg2, %609 : i32
%611 = arith.cmpi sgt, %610, %608 : i32
%612 = scf.if %611 -> (i32) {
scf.yield %608 : i32
} else {
%613 = arith.constant 1 : i32
%614 = arith.subi %arg2, %613 : i32
scf.yield %614 : i32
}
%615 = arith.constant 0 : i32
%616 = arith.cmpi slt, %612, %615 : i32
%617 = scf.if %616 -> (i32) {
%618 = arith.constant 0 : i32
scf.yield %618 : i32
} else {
scf.yield %612 : i32
}
%619 = func.call @poly_int(%606, %617, %arg3) : (!llvm.ptr, i32, !llvm.ptr) -> !llvm.ptr
%620 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%621 = llvm.load %620 : !llvm.ptr -> i32
%622 = arith.cmpi sgt, %arg2, %621 : i32
%623 = scf.if %622 -> (i32) {
scf.yield %621 : i32
} else {
scf.yield %arg2 : i32
}
func.call @free(%600) : (!llvm.ptr) -> ()
func.call @free(%603) : (!llvm.ptr) -> ()
func.call @free(%606) : (!llvm.ptr) -> ()
%628 = arith.extsi %arg2 : i32 to i64
%629 = arith.constant 8 : i32
%630 = arith.extsi %629 : i32 to i64
%627 = func.call @calloc(%628, %630) : (i64, i64) -> !llvm.ptr
%632 = arith.extsi %623 : i32 to i64
%633 = arith.constant 8 : i32
%635 = arith.extsi %633 : i32 to i64
%634 = arith.muli %632, %635 : i64
%631 = func.call @memcpy(%627, %619, %634) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
func.call @free(%619) : (!llvm.ptr) -> ()
%637 = llvm.mlir.addressof @g_out_len : !llvm.ptr
llvm.store %arg2, %637 : i32, !llvm.ptr
func.return %627 : !llvm.ptr
}
func.func @poly_exp(%arg0: !llvm.ptr, %arg1: i32, %arg2: i32, %arg3: !llvm.ptr) -> !llvm.ptr {
%639 = arith.extsi %arg2 : i32 to i64
%640 = arith.constant 8 : i32
%641 = arith.extsi %640 : i32 to i64
%638 = func.call @calloc(%639, %641) : (i64, i64) -> !llvm.ptr
%642 = arith.constant 1 : i32
%643 = arith.constant 0 : i32
%644 = arith.extsi %642 : i32 to i64
%645 = arith.extsi %643 : i32 to i64
%646 = llvm.getelementptr %638[%645] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %644, %646 : i64, !llvm.ptr
%647 = arith.constant 1 : i32
%648 = llvm.mlir.constant(1 : i64) : i64
%649 = llvm.alloca %648 x i32 : (i64) -> !llvm.ptr
llvm.store %647, %649 : i32, !llvm.ptr
cf.br ^bb87
^bb87:
%650 = llvm.load %649 : !llvm.ptr -> i32
%651 = arith.cmpi slt, %650, %arg2 : i32
cf.cond_br %651, ^bb88, ^bb89
^bb88:
%652 = llvm.load %649 : !llvm.ptr -> i32
%653 = arith.constant 2 : i32
%654 = arith.muli %652, %653 : i32
%655 = llvm.mlir.constant(1 : i64) : i64
%656 = llvm.alloca %655 x i32 : (i64) -> !llvm.ptr
llvm.store %654, %656 : i32, !llvm.ptr
%657 = llvm.load %656 : !llvm.ptr -> i32
%658 = arith.cmpi sgt, %657, %arg2 : i32
cf.cond_br %658, ^bb90, ^bb91
^bb90:
llvm.store %arg2, %656 : i32, !llvm.ptr
cf.br ^bb92
^bb91:
cf.br ^bb92
^bb92:
%660 = llvm.load %656 : !llvm.ptr -> i32
%661 = arith.extsi %660 : i32 to i64
%662 = arith.constant 8 : i32
%663 = arith.extsi %662 : i32 to i64
%659 = func.call @calloc(%661, %663) : (i64, i64) -> !llvm.ptr
%665 = llvm.load %649 : !llvm.ptr -> i32
%666 = arith.extsi %665 : i32 to i64
%667 = arith.constant 8 : i32
%669 = arith.extsi %667 : i32 to i64
%668 = arith.muli %666, %669 : i64
%664 = func.call @memcpy(%659, %638, %668) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
%671 = llvm.load %656 : !llvm.ptr -> i32
%672 = llvm.load %656 : !llvm.ptr -> i32
%670 = func.call @poly_ln(%659, %671, %672, %arg3) : (!llvm.ptr, i32, i32, !llvm.ptr) -> !llvm.ptr
%673 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%674 = llvm.load %673 : !llvm.ptr -> i32
%676 = llvm.load %656 : !llvm.ptr -> i32
%677 = arith.extsi %676 : i32 to i64
%678 = arith.constant 8 : i32
%679 = arith.extsi %678 : i32 to i64
%675 = func.call @calloc(%677, %679) : (i64, i64) -> !llvm.ptr
%680 = arith.constant 0 : i32
%681 = llvm.mlir.constant(1 : i64) : i64
%682 = llvm.alloca %681 x i32 : (i64) -> !llvm.ptr
llvm.store %680, %682 : i32, !llvm.ptr
cf.br ^bb93
^bb93:
%683 = llvm.load %682 : !llvm.ptr -> i32
%684 = llvm.load %656 : !llvm.ptr -> i32
%685 = arith.cmpi slt, %683, %684 : i32
cf.cond_br %685, ^bb94, ^bb95
^bb94:
%686 = llvm.load %682 : !llvm.ptr -> i32
%687 = arith.cmpi slt, %686, %arg1 : i32
%688 = scf.if %687 -> (i64) {
%690 = llvm.load %682 : !llvm.ptr -> i32
%691 = arith.extsi %690 : i32 to i64
%692 = llvm.getelementptr %arg0[%691] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%689 = llvm.load %692 : !llvm.ptr -> i64
scf.yield %689 : i64
} else {
%693 = arith.constant 0 : i32
scf.yield %693 : i32
}
%695 = llvm.load %682 : !llvm.ptr -> i32
%696 = arith.extsi %695 : i32 to i64
%697 = llvm.getelementptr %670[%696] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%694 = llvm.load %697 : !llvm.ptr -> i64
%698 = arith.subi %688, %694 : i64
%699 = llvm.mlir.addressof @MOD : !llvm.ptr
%700 = llvm.load %699 : !llvm.ptr -> i64
%701 = arith.remsi %698, %700 : i64
%702 = llvm.mlir.constant(1 : i64) : i64
%703 = llvm.alloca %702 x i64 : (i64) -> !llvm.ptr
llvm.store %701, %703 : i64, !llvm.ptr
%704 = llvm.load %703 : !llvm.ptr -> i64
%705 = arith.constant 0 : i32
%707 = arith.extsi %705 : i32 to i64
%706 = arith.cmpi slt, %704, %707 : i64
cf.cond_br %706, ^bb96, ^bb97
^bb96:
%708 = llvm.load %703 : !llvm.ptr -> i64
%709 = llvm.mlir.addressof @MOD : !llvm.ptr
%710 = llvm.load %709 : !llvm.ptr -> i64
%711 = arith.addi %708, %710 : i64
llvm.store %711, %703 : i64, !llvm.ptr
cf.br ^bb98
^bb97:
cf.br ^bb98
^bb98:
%712 = llvm.load %703 : !llvm.ptr -> i64
%713 = llvm.load %682 : !llvm.ptr -> i32
%714 = arith.extsi %713 : i32 to i64
%715 = llvm.getelementptr %675[%714] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %712, %715 : i64, !llvm.ptr
%716 = llvm.load %682 : !llvm.ptr -> i32
%717 = arith.constant 1 : i32
%718 = arith.addi %716, %717 : i32
llvm.store %718, %682 : i32, !llvm.ptr
cf.br ^bb93
^bb95:
%720 = arith.constant 0 : i32
%721 = arith.extsi %720 : i32 to i64
%722 = llvm.getelementptr %675[%721] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%719 = llvm.load %722 : !llvm.ptr -> i64
%723 = arith.constant 1 : i32
%725 = arith.extsi %723 : i32 to i64
%724 = arith.addi %719, %725 : i64
%726 = llvm.mlir.addressof @MOD : !llvm.ptr
%727 = llvm.load %726 : !llvm.ptr -> i64
%728 = arith.remsi %724, %727 : i64
%729 = arith.constant 0 : i32
%730 = arith.extsi %729 : i32 to i64
%731 = llvm.getelementptr %675[%730] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %728, %731 : i64, !llvm.ptr
%733 = llvm.load %649 : !llvm.ptr -> i32
%734 = llvm.load %656 : !llvm.ptr -> i32
%732 = func.call @polymul(%638, %733, %675, %734) : (!llvm.ptr, i32, !llvm.ptr, i32) -> !llvm.ptr
%735 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%736 = llvm.load %735 : !llvm.ptr -> i32
%737 = llvm.load %656 : !llvm.ptr -> i32
%738 = arith.cmpi sgt, %736, %737 : i32
%739 = scf.if %738 -> (i32) {
%740 = llvm.load %656 : !llvm.ptr -> i32
scf.yield %740 : i32
} else {
scf.yield %736 : i32
}
%742 = arith.extsi %739 : i32 to i64
%743 = arith.constant 8 : i32
%745 = arith.extsi %743 : i32 to i64
%744 = arith.muli %742, %745 : i64
%741 = func.call @memcpy(%638, %732, %744) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
func.call @free(%659) : (!llvm.ptr) -> ()
func.call @free(%670) : (!llvm.ptr) -> ()
func.call @free(%675) : (!llvm.ptr) -> ()
func.call @free(%732) : (!llvm.ptr) -> ()
%750 = llvm.load %656 : !llvm.ptr -> i32
llvm.store %750, %649 : i32, !llvm.ptr
cf.br ^bb87
^bb89:
%751 = llvm.mlir.addressof @g_out_len : !llvm.ptr
llvm.store %arg2, %751 : i32, !llvm.ptr
func.return %638 : !llvm.ptr
}
func.func @special_component(%arg0: i32) -> !llvm.ptr {
%752 = llvm.mlir.addressof @MOD : !llvm.ptr
%753 = llvm.load %752 : !llvm.ptr -> i64
%754 = arith.constant 1 : i32
%756 = arith.extsi %754 : i32 to i64
%755 = arith.addi %753, %756 : i64
%757 = arith.constant 2 : i32
%759 = arith.extsi %757 : i32 to i64
%758 = arith.divsi %755, %759 : i64
%761 = arith.constant 1 : i32
%762 = arith.addi %arg0, %761 : i32
%763 = arith.extsi %762 : i32 to i64
%764 = arith.constant 8 : i32
%765 = arith.extsi %764 : i32 to i64
%760 = func.call @calloc(%763, %765) : (i64, i64) -> !llvm.ptr
%766 = arith.constant 1 : i32
%767 = arith.constant 0 : i32
%768 = arith.extsi %766 : i32 to i64
%769 = arith.extsi %767 : i32 to i64
%770 = llvm.getelementptr %760[%769] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %768, %770 : i64, !llvm.ptr
%771 = arith.constant 2 : i32
%772 = llvm.mlir.constant(1 : i64) : i64
%773 = llvm.alloca %772 x i32 : (i64) -> !llvm.ptr
llvm.store %771, %773 : i32, !llvm.ptr
cf.br ^bb99
^bb99:
%774 = llvm.load %773 : !llvm.ptr -> i32
%775 = arith.cmpi sle, %774, %arg0 : i32
cf.cond_br %775, ^bb100, ^bb101
^bb100:
%776 = llvm.load %773 : !llvm.ptr -> i32
%777 = llvm.mlir.constant(1 : i64) : i64
%778 = llvm.alloca %777 x i32 : (i64) -> !llvm.ptr
llvm.store %776, %778 : i32, !llvm.ptr
cf.br ^bb102
^bb102:
%779 = llvm.load %778 : !llvm.ptr -> i32
%780 = arith.cmpi sle, %779, %arg0 : i32
cf.cond_br %780, ^bb103, ^bb104
^bb103:
%782 = llvm.load %778 : !llvm.ptr -> i32
%783 = arith.extsi %782 : i32 to i64
%784 = llvm.getelementptr %760[%783] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%781 = llvm.load %784 : !llvm.ptr -> i64
%786 = llvm.load %778 : !llvm.ptr -> i32
%787 = llvm.load %773 : !llvm.ptr -> i32
%788 = arith.subi %786, %787 : i32
%789 = arith.extsi %788 : i32 to i64
%790 = llvm.getelementptr %760[%789] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%785 = llvm.load %790 : !llvm.ptr -> i64
%791 = arith.addi %781, %785 : i64
%792 = llvm.mlir.addressof @MOD : !llvm.ptr
%793 = llvm.load %792 : !llvm.ptr -> i64
%794 = arith.remsi %791, %793 : i64
%795 = llvm.load %778 : !llvm.ptr -> i32
%796 = arith.extsi %795 : i32 to i64
%797 = llvm.getelementptr %760[%796] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %794, %797 : i64, !llvm.ptr
%798 = llvm.load %778 : !llvm.ptr -> i32
%799 = arith.constant 1 : i32
%800 = arith.addi %798, %799 : i32
llvm.store %800, %778 : i32, !llvm.ptr
cf.br ^bb102
^bb104:
%801 = llvm.load %773 : !llvm.ptr -> i32
%802 = arith.constant 1 : i32
%803 = arith.shli %801, %802 : i32
llvm.store %803, %773 : i32, !llvm.ptr
cf.br ^bb99
^bb101:
%805 = arith.constant 1 : i32
%806 = arith.addi %arg0, %805 : i32
%807 = arith.extsi %806 : i32 to i64
%808 = arith.constant 8 : i32
%809 = arith.extsi %808 : i32 to i64
%804 = func.call @calloc(%807, %809) : (i64, i64) -> !llvm.ptr
%810 = arith.constant 1 : i32
%811 = arith.constant 0 : i32
%812 = arith.extsi %810 : i32 to i64
%813 = arith.extsi %811 : i32 to i64
%814 = llvm.getelementptr %804[%813] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %812, %814 : i64, !llvm.ptr
%815 = arith.constant 2 : i32
%816 = llvm.mlir.constant(1 : i64) : i64
%817 = llvm.alloca %816 x i32 : (i64) -> !llvm.ptr
llvm.store %815, %817 : i32, !llvm.ptr
cf.br ^bb105
^bb105:
%818 = llvm.load %817 : !llvm.ptr -> i32
%819 = arith.cmpi sle, %818, %arg0 : i32
cf.cond_br %819, ^bb106, ^bb107
^bb106:
%821 = arith.constant 1 : i32
%822 = arith.addi %arg0, %821 : i32
%823 = arith.extsi %822 : i32 to i64
%824 = arith.constant 8 : i32
%825 = arith.extsi %824 : i32 to i64
%820 = func.call @calloc(%823, %825) : (i64, i64) -> !llvm.ptr
%826 = arith.constant 0 : i32
%827 = llvm.mlir.constant(1 : i64) : i64
%828 = llvm.alloca %827 x i32 : (i64) -> !llvm.ptr
llvm.store %826, %828 : i32, !llvm.ptr
cf.br ^bb108
^bb108:
%829 = llvm.load %828 : !llvm.ptr -> i32
%830 = arith.cmpi sle, %829, %arg0 : i32
cf.cond_br %830, ^bb109, ^bb110
^bb109:
%832 = llvm.load %828 : !llvm.ptr -> i32
%833 = arith.extsi %832 : i32 to i64
%834 = llvm.getelementptr %804[%833] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%831 = llvm.load %834 : !llvm.ptr -> i64
%835 = llvm.mlir.constant(1 : i64) : i64
%836 = llvm.alloca %835 x i64 : (i64) -> !llvm.ptr
llvm.store %831, %836 : i64, !llvm.ptr
%837 = llvm.load %828 : !llvm.ptr -> i32
%838 = llvm.load %817 : !llvm.ptr -> i32
%839 = arith.cmpi sge, %837, %838 : i32
cf.cond_br %839, ^bb111, ^bb112
^bb111:
%840 = llvm.load %836 : !llvm.ptr -> i64
%842 = llvm.load %828 : !llvm.ptr -> i32
%843 = llvm.load %817 : !llvm.ptr -> i32
%844 = arith.subi %842, %843 : i32
%845 = arith.extsi %844 : i32 to i64
%846 = llvm.getelementptr %820[%845] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%841 = llvm.load %846 : !llvm.ptr -> i64
%847 = arith.subi %840, %841 : i64
%848 = llvm.mlir.addressof @MOD : !llvm.ptr
%849 = llvm.load %848 : !llvm.ptr -> i64
%850 = arith.remsi %847, %849 : i64
llvm.store %850, %836 : i64, !llvm.ptr
%851 = llvm.load %836 : !llvm.ptr -> i64
%852 = arith.constant 0 : i32
%854 = arith.extsi %852 : i32 to i64
%853 = arith.cmpi slt, %851, %854 : i64
cf.cond_br %853, ^bb114, ^bb115
^bb114:
%855 = llvm.load %836 : !llvm.ptr -> i64
%856 = llvm.mlir.addressof @MOD : !llvm.ptr
%857 = llvm.load %856 : !llvm.ptr -> i64
%858 = arith.addi %855, %857 : i64
llvm.store %858, %836 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
cf.br ^bb113
^bb112:
cf.br ^bb113
^bb113:
%859 = llvm.load %836 : !llvm.ptr -> i64
%860 = llvm.load %828 : !llvm.ptr -> i32
%861 = arith.extsi %860 : i32 to i64
%862 = llvm.getelementptr %820[%861] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %859, %862 : i64, !llvm.ptr
%863 = llvm.load %828 : !llvm.ptr -> i32
%864 = arith.constant 1 : i32
%865 = arith.addi %863, %864 : i32
llvm.store %865, %828 : i32, !llvm.ptr
cf.br ^bb108
^bb110:
%866 = arith.constant 0 : i32
%867 = llvm.mlir.constant(1 : i64) : i64
%868 = llvm.alloca %867 x i32 : (i64) -> !llvm.ptr
llvm.store %866, %868 : i32, !llvm.ptr
cf.br ^bb117
^bb117:
%869 = llvm.load %868 : !llvm.ptr -> i32
%870 = arith.cmpi sle, %869, %arg0 : i32
cf.cond_br %870, ^bb118, ^bb119
^bb118:
%872 = llvm.load %868 : !llvm.ptr -> i32
%873 = arith.extsi %872 : i32 to i64
%874 = llvm.getelementptr %820[%873] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%871 = llvm.load %874 : !llvm.ptr -> i64
%875 = llvm.load %868 : !llvm.ptr -> i32
%876 = arith.extsi %875 : i32 to i64
%877 = llvm.getelementptr %804[%876] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %871, %877 : i64, !llvm.ptr
%878 = llvm.load %868 : !llvm.ptr -> i32
%879 = arith.constant 1 : i32
%880 = arith.addi %878, %879 : i32
llvm.store %880, %868 : i32, !llvm.ptr
cf.br ^bb117
^bb119:
func.call @free(%820) : (!llvm.ptr) -> ()
%882 = llvm.load %817 : !llvm.ptr -> i32
%883 = arith.constant 1 : i32
%884 = arith.shli %882, %883 : i32
llvm.store %884, %817 : i32, !llvm.ptr
cf.br ^bb105
^bb107:
%886 = arith.constant 1 : i32
%887 = arith.addi %arg0, %886 : i32
%888 = arith.extsi %887 : i32 to i64
%889 = arith.constant 8 : i32
%890 = arith.extsi %889 : i32 to i64
%885 = func.call @calloc(%888, %890) : (i64, i64) -> !llvm.ptr
%891 = arith.constant 0 : i32
%892 = llvm.mlir.constant(1 : i64) : i64
%893 = llvm.alloca %892 x i32 : (i64) -> !llvm.ptr
llvm.store %891, %893 : i32, !llvm.ptr
cf.br ^bb120
^bb120:
%894 = llvm.load %893 : !llvm.ptr -> i32
%895 = arith.cmpi sle, %894, %arg0 : i32
cf.cond_br %895, ^bb121, ^bb122
^bb121:
%897 = llvm.load %893 : !llvm.ptr -> i32
%898 = arith.extsi %897 : i32 to i64
%899 = llvm.getelementptr %760[%898] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%896 = llvm.load %899 : !llvm.ptr -> i64
%900 = llvm.mlir.constant(1 : i64) : i64
%901 = llvm.alloca %900 x i64 : (i64) -> !llvm.ptr
llvm.store %896, %901 : i64, !llvm.ptr
%902 = llvm.load %893 : !llvm.ptr -> i32
%903 = arith.constant 0 : i32
%904 = arith.cmpi sgt, %902, %903 : i32
cf.cond_br %904, ^bb123, ^bb124
^bb123:
%905 = llvm.load %901 : !llvm.ptr -> i64
%907 = llvm.load %893 : !llvm.ptr -> i32
%908 = arith.constant 1 : i32
%909 = arith.subi %907, %908 : i32
%910 = arith.extsi %909 : i32 to i64
%911 = llvm.getelementptr %760[%910] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%906 = llvm.load %911 : !llvm.ptr -> i64
%912 = arith.addi %905, %906 : i64
%913 = llvm.mlir.addressof @MOD : !llvm.ptr
%914 = llvm.load %913 : !llvm.ptr -> i64
%915 = arith.remsi %912, %914 : i64
llvm.store %915, %901 : i64, !llvm.ptr
cf.br ^bb125
^bb124:
cf.br ^bb125
^bb125:
%917 = llvm.load %893 : !llvm.ptr -> i32
%918 = arith.extsi %917 : i32 to i64
%919 = llvm.getelementptr %804[%918] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%916 = llvm.load %919 : !llvm.ptr -> i64
%920 = llvm.mlir.constant(1 : i64) : i64
%921 = llvm.alloca %920 x i64 : (i64) -> !llvm.ptr
llvm.store %916, %921 : i64, !llvm.ptr
%922 = llvm.load %893 : !llvm.ptr -> i32
%923 = arith.constant 0 : i32
%924 = arith.cmpi sgt, %922, %923 : i32
cf.cond_br %924, ^bb126, ^bb127
^bb126:
%925 = llvm.load %921 : !llvm.ptr -> i64
%927 = llvm.load %893 : !llvm.ptr -> i32
%928 = arith.constant 1 : i32
%929 = arith.subi %927, %928 : i32
%930 = arith.extsi %929 : i32 to i64
%931 = llvm.getelementptr %804[%930] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%926 = llvm.load %931 : !llvm.ptr -> i64
%932 = arith.subi %925, %926 : i64
%933 = llvm.mlir.addressof @MOD : !llvm.ptr
%934 = llvm.load %933 : !llvm.ptr -> i64
%935 = arith.remsi %932, %934 : i64
llvm.store %935, %921 : i64, !llvm.ptr
%936 = llvm.load %921 : !llvm.ptr -> i64
%937 = arith.constant 0 : i32
%939 = arith.extsi %937 : i32 to i64
%938 = arith.cmpi slt, %936, %939 : i64
cf.cond_br %938, ^bb129, ^bb130
^bb129:
%940 = llvm.load %921 : !llvm.ptr -> i64
%941 = llvm.mlir.addressof @MOD : !llvm.ptr
%942 = llvm.load %941 : !llvm.ptr -> i64
%943 = arith.addi %940, %942 : i64
llvm.store %943, %921 : i64, !llvm.ptr
cf.br ^bb131
^bb130:
cf.br ^bb131
^bb131:
cf.br ^bb128
^bb127:
cf.br ^bb128
^bb128:
%944 = llvm.load %901 : !llvm.ptr -> i64
%945 = llvm.load %921 : !llvm.ptr -> i64
%946 = arith.addi %944, %945 : i64
%947 = llvm.mlir.addressof @MOD : !llvm.ptr
%948 = llvm.load %947 : !llvm.ptr -> i64
%949 = arith.remsi %946, %948 : i64
%950 = arith.muli %949, %758 : i64
%951 = llvm.mlir.addressof @MOD : !llvm.ptr
%952 = llvm.load %951 : !llvm.ptr -> i64
%953 = arith.remsi %950, %952 : i64
%954 = llvm.load %893 : !llvm.ptr -> i32
%955 = arith.extsi %954 : i32 to i64
%956 = llvm.getelementptr %885[%955] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %953, %956 : i64, !llvm.ptr
%957 = llvm.load %893 : !llvm.ptr -> i32
%958 = arith.constant 1 : i32
%959 = arith.addi %957, %958 : i32
llvm.store %959, %893 : i32, !llvm.ptr
cf.br ^bb120
^bb122:
%961 = arith.constant 1 : i32
%962 = arith.addi %arg0, %961 : i32
%963 = arith.extsi %962 : i32 to i64
%964 = arith.constant 8 : i32
%965 = arith.extsi %964 : i32 to i64
%960 = func.call @calloc(%963, %965) : (i64, i64) -> !llvm.ptr
%966 = arith.constant 0 : i32
%967 = arith.extsi %966 : i32 to i64
%968 = llvm.mlir.constant(1 : i64) : i64
%969 = llvm.alloca %968 x i64 : (i64) -> !llvm.ptr
llvm.store %967, %969 : i64, !llvm.ptr
%970 = arith.constant 0 : i32
%971 = llvm.mlir.constant(1 : i64) : i64
%972 = llvm.alloca %971 x i32 : (i64) -> !llvm.ptr
llvm.store %970, %972 : i32, !llvm.ptr
cf.br ^bb132
^bb132:
%973 = llvm.load %972 : !llvm.ptr -> i32
%974 = arith.cmpi sle, %973, %arg0 : i32
cf.cond_br %974, ^bb133, ^bb134
^bb133:
%975 = llvm.load %969 : !llvm.ptr -> i64
%977 = llvm.load %972 : !llvm.ptr -> i32
%978 = arith.extsi %977 : i32 to i64
%979 = llvm.getelementptr %885[%978] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%976 = llvm.load %979 : !llvm.ptr -> i64
%980 = arith.addi %975, %976 : i64
%981 = llvm.mlir.addressof @MOD : !llvm.ptr
%982 = llvm.load %981 : !llvm.ptr -> i64
%983 = arith.remsi %980, %982 : i64
llvm.store %983, %969 : i64, !llvm.ptr
%984 = llvm.load %969 : !llvm.ptr -> i64
%985 = llvm.load %972 : !llvm.ptr -> i32
%986 = arith.extsi %985 : i32 to i64
%987 = llvm.getelementptr %960[%986] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %984, %987 : i64, !llvm.ptr
%988 = llvm.load %972 : !llvm.ptr -> i32
%989 = arith.constant 1 : i32
%990 = arith.addi %988, %989 : i32
llvm.store %990, %972 : i32, !llvm.ptr
cf.br ^bb132
^bb134:
%992 = arith.constant 1 : i32
%993 = arith.addi %arg0, %992 : i32
%994 = arith.extsi %993 : i32 to i64
%995 = arith.constant 8 : i32
%996 = arith.extsi %995 : i32 to i64
%991 = func.call @calloc(%994, %996) : (i64, i64) -> !llvm.ptr
%997 = arith.constant 0 : i32
%998 = llvm.mlir.constant(1 : i64) : i64
%999 = llvm.alloca %998 x i32 : (i64) -> !llvm.ptr
llvm.store %997, %999 : i32, !llvm.ptr
cf.br ^bb135
^bb135:
%1000 = llvm.load %999 : !llvm.ptr -> i32
%1001 = arith.cmpi sle, %1000, %arg0 : i32
cf.cond_br %1001, ^bb136, ^bb137
^bb136:
%1003 = llvm.load %999 : !llvm.ptr -> i32
%1004 = arith.extsi %1003 : i32 to i64
%1005 = llvm.getelementptr %960[%1004] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1002 = llvm.load %1005 : !llvm.ptr -> i64
%1006 = llvm.mlir.constant(1 : i64) : i64
%1007 = llvm.alloca %1006 x i64 : (i64) -> !llvm.ptr
llvm.store %1002, %1007 : i64, !llvm.ptr
%1008 = llvm.load %999 : !llvm.ptr -> i32
%1009 = arith.constant 2 : i32
%1010 = arith.cmpi sge, %1008, %1009 : i32
cf.cond_br %1010, ^bb138, ^bb139
^bb138:
%1011 = llvm.load %1007 : !llvm.ptr -> i64
%1013 = llvm.load %999 : !llvm.ptr -> i32
%1014 = arith.constant 2 : i32
%1015 = arith.subi %1013, %1014 : i32
%1016 = arith.extsi %1015 : i32 to i64
%1017 = llvm.getelementptr %991[%1016] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1012 = llvm.load %1017 : !llvm.ptr -> i64
%1018 = arith.addi %1011, %1012 : i64
%1019 = llvm.mlir.addressof @MOD : !llvm.ptr
%1020 = llvm.load %1019 : !llvm.ptr -> i64
%1021 = arith.remsi %1018, %1020 : i64
llvm.store %1021, %1007 : i64, !llvm.ptr
cf.br ^bb140
^bb139:
cf.br ^bb140
^bb140:
%1022 = llvm.load %1007 : !llvm.ptr -> i64
%1023 = llvm.load %999 : !llvm.ptr -> i32
%1024 = arith.extsi %1023 : i32 to i64
%1025 = llvm.getelementptr %991[%1024] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1022, %1025 : i64, !llvm.ptr
%1026 = llvm.load %999 : !llvm.ptr -> i32
%1027 = arith.constant 1 : i32
%1028 = arith.addi %1026, %1027 : i32
llvm.store %1028, %999 : i32, !llvm.ptr
cf.br ^bb135
^bb137:
func.call @free(%760) : (!llvm.ptr) -> ()
func.call @free(%804) : (!llvm.ptr) -> ()
func.call @free(%885) : (!llvm.ptr) -> ()
func.call @free(%960) : (!llvm.ptr) -> ()
func.return %991 : !llvm.ptr
}
func.func @add_component_multiplicities(%arg0: !llvm.ptr, %arg1: i32) -> () {
%1033 = arith.constant 2 : i32
%1034 = arith.muli %1033, %arg1 : i32
%1035 = arith.constant 1 : i32
%1036 = arith.addi %1034, %1035 : i32
%1038 = arith.constant 1 : i32
%1039 = arith.addi %1036, %1038 : i32
%1040 = arith.extsi %1039 : i32 to i64
%1037 = func.call @malloc(%1040) : (i64) -> !llvm.ptr
%1042 = arith.constant 1 : i32
%1043 = arith.constant 1 : i32
%1044 = arith.addi %1036, %1043 : i32
%1045 = arith.extsi %1044 : i32 to i64
%1041 = func.call @memset(%1037, %1042, %1045) : (!llvm.ptr, i32, i64) -> !llvm.ptr
%1046 = arith.constant 0 : i32
%1047 = arith.constant 0 : i32
%1048 = arith.trunci %1046 : i32 to i8
%1049 = arith.extsi %1047 : i32 to i64
%1050 = llvm.getelementptr %1037[%1049] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %1048, %1050 : i8, !llvm.ptr
%1051 = arith.constant 0 : i32
%1052 = arith.constant 1 : i32
%1053 = arith.trunci %1051 : i32 to i8
%1054 = arith.extsi %1052 : i32 to i64
%1055 = llvm.getelementptr %1037[%1054] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %1053, %1055 : i8, !llvm.ptr
%1056 = arith.constant 2 : i32
%1057 = llvm.mlir.constant(1 : i64) : i64
%1058 = llvm.alloca %1057 x i32 : (i64) -> !llvm.ptr
llvm.store %1056, %1058 : i32, !llvm.ptr
cf.br ^bb141
^bb141:
%1059 = llvm.load %1058 : !llvm.ptr -> i32
%1060 = arith.extsi %1059 : i32 to i64
%1061 = llvm.load %1058 : !llvm.ptr -> i32
%1062 = arith.extsi %1061 : i32 to i64
%1063 = arith.muli %1060, %1062 : i64
%1064 = arith.extsi %1036 : i32 to i64
%1065 = arith.cmpi sle, %1063, %1064 : i64
cf.cond_br %1065, ^bb142, ^bb143
^bb142:
%1067 = llvm.load %1058 : !llvm.ptr -> i32
%1068 = arith.extsi %1067 : i32 to i64
%1069 = llvm.getelementptr %1037[%1068] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%1066 = llvm.load %1069 : !llvm.ptr -> i8
%1070 = arith.constant 0 : i32
%1072 = arith.extsi %1066 : i8 to i32
%1071 = arith.cmpi ne, %1072, %1070 : i32
cf.cond_br %1071, ^bb144, ^bb145
^bb144:
%1073 = llvm.load %1058 : !llvm.ptr -> i32
%1074 = llvm.load %1058 : !llvm.ptr -> i32
%1075 = arith.muli %1073, %1074 : i32
%1076 = llvm.mlir.constant(1 : i64) : i64
%1077 = llvm.alloca %1076 x i32 : (i64) -> !llvm.ptr
llvm.store %1075, %1077 : i32, !llvm.ptr
cf.br ^bb147
^bb147:
%1078 = llvm.load %1077 : !llvm.ptr -> i32
%1079 = arith.cmpi sle, %1078, %1036 : i32
cf.cond_br %1079, ^bb148, ^bb149
^bb148:
%1080 = arith.constant 0 : i32
%1081 = llvm.load %1077 : !llvm.ptr -> i32
%1082 = arith.trunci %1080 : i32 to i8
%1083 = arith.extsi %1081 : i32 to i64
%1084 = llvm.getelementptr %1037[%1083] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %1082, %1084 : i8, !llvm.ptr
%1085 = llvm.load %1077 : !llvm.ptr -> i32
%1086 = llvm.load %1058 : !llvm.ptr -> i32
%1087 = arith.addi %1085, %1086 : i32
llvm.store %1087, %1077 : i32, !llvm.ptr
cf.br ^bb147
^bb149:
cf.br ^bb146
^bb145:
cf.br ^bb146
^bb146:
%1088 = llvm.load %1058 : !llvm.ptr -> i32
%1089 = arith.constant 1 : i32
%1090 = arith.addi %1088, %1089 : i32
llvm.store %1090, %1058 : i32, !llvm.ptr
cf.br ^bb141
^bb143:
%1091 = arith.constant 0 : i32
%1092 = llvm.mlir.constant(1 : i64) : i64
%1093 = llvm.alloca %1092 x i32 : (i64) -> !llvm.ptr
llvm.store %1091, %1093 : i32, !llvm.ptr
%1094 = arith.constant 2 : i32
%1095 = llvm.mlir.constant(1 : i64) : i64
%1096 = llvm.alloca %1095 x i32 : (i64) -> !llvm.ptr
llvm.store %1094, %1096 : i32, !llvm.ptr
cf.br ^bb150
^bb150:
%1097 = llvm.load %1096 : !llvm.ptr -> i32
%1098 = arith.cmpi sle, %1097, %1036 : i32
cf.cond_br %1098, ^bb151, ^bb152
^bb151:
%1100 = llvm.load %1096 : !llvm.ptr -> i32
%1101 = arith.extsi %1100 : i32 to i64
%1102 = llvm.getelementptr %1037[%1101] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%1099 = llvm.load %1102 : !llvm.ptr -> i8
%1103 = arith.constant 0 : i32
%1105 = arith.extsi %1099 : i8 to i32
%1104 = arith.cmpi ne, %1105, %1103 : i32
cf.cond_br %1104, ^bb153, ^bb154
^bb153:
%1106 = llvm.load %1093 : !llvm.ptr -> i32
%1107 = arith.constant 1 : i32
%1108 = arith.addi %1106, %1107 : i32
llvm.store %1108, %1093 : i32, !llvm.ptr
cf.br ^bb155
^bb154:
cf.br ^bb155
^bb155:
%1109 = llvm.load %1096 : !llvm.ptr -> i32
%1110 = arith.constant 1 : i32
%1111 = arith.addi %1109, %1110 : i32
llvm.store %1111, %1096 : i32, !llvm.ptr
cf.br ^bb150
^bb152:
%1113 = llvm.load %1093 : !llvm.ptr -> i32
%1114 = arith.extsi %1113 : i32 to i64
%1115 = arith.constant 4 : i32
%1117 = arith.extsi %1115 : i32 to i64
%1116 = arith.muli %1114, %1117 : i64
%1112 = func.call @malloc(%1116) : (i64) -> !llvm.ptr
%1118 = arith.constant 0 : i32
%1119 = llvm.mlir.constant(1 : i64) : i64
%1120 = llvm.alloca %1119 x i32 : (i64) -> !llvm.ptr
llvm.store %1118, %1120 : i32, !llvm.ptr
%1121 = arith.constant 2 : i32
%1122 = llvm.mlir.constant(1 : i64) : i64
%1123 = llvm.alloca %1122 x i32 : (i64) -> !llvm.ptr
llvm.store %1121, %1123 : i32, !llvm.ptr
cf.br ^bb156
^bb156:
%1124 = llvm.load %1123 : !llvm.ptr -> i32
%1125 = arith.cmpi sle, %1124, %1036 : i32
cf.cond_br %1125, ^bb157, ^bb158
^bb157:
%1127 = llvm.load %1123 : !llvm.ptr -> i32
%1128 = arith.extsi %1127 : i32 to i64
%1129 = llvm.getelementptr %1037[%1128] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%1126 = llvm.load %1129 : !llvm.ptr -> i8
%1130 = arith.constant 0 : i32
%1132 = arith.extsi %1126 : i8 to i32
%1131 = arith.cmpi ne, %1132, %1130 : i32
cf.cond_br %1131, ^bb159, ^bb160
^bb159:
%1133 = llvm.load %1123 : !llvm.ptr -> i32
%1134 = llvm.load %1120 : !llvm.ptr -> i32
%1135 = arith.extsi %1134 : i32 to i64
%1136 = llvm.getelementptr %1112[%1135] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1133, %1136 : i32, !llvm.ptr
%1137 = llvm.load %1120 : !llvm.ptr -> i32
%1138 = arith.constant 1 : i32
%1139 = arith.addi %1137, %1138 : i32
llvm.store %1139, %1120 : i32, !llvm.ptr
cf.br ^bb161
^bb160:
cf.br ^bb161
^bb161:
%1140 = llvm.load %1123 : !llvm.ptr -> i32
%1141 = arith.constant 1 : i32
%1142 = arith.addi %1140, %1141 : i32
llvm.store %1142, %1123 : i32, !llvm.ptr
cf.br ^bb156
^bb158:
func.call @free(%1037) : (!llvm.ptr) -> ()
%1145 = llvm.load %1093 : !llvm.ptr -> i32
%1146 = arith.extsi %1145 : i32 to i64
%1147 = arith.constant 4 : i32
%1149 = arith.extsi %1147 : i32 to i64
%1148 = arith.muli %1146, %1149 : i64
%1144 = func.call @malloc(%1148) : (i64) -> !llvm.ptr
%1150 = arith.constant 0 : i32
%1151 = llvm.mlir.constant(1 : i64) : i64
%1152 = llvm.alloca %1151 x i32 : (i64) -> !llvm.ptr
llvm.store %1150, %1152 : i32, !llvm.ptr
%1153 = arith.constant 0 : i32
%1154 = llvm.mlir.constant(1 : i64) : i64
%1155 = llvm.alloca %1154 x i32 : (i64) -> !llvm.ptr
llvm.store %1153, %1155 : i32, !llvm.ptr
cf.br ^bb162
^bb162:
%1156 = llvm.load %1155 : !llvm.ptr -> i32
%1157 = llvm.load %1093 : !llvm.ptr -> i32
%1158 = arith.cmpi slt, %1156, %1157 : i32
cf.cond_br %1158, ^bb163, ^bb164
^bb163:
%1160 = llvm.load %1155 : !llvm.ptr -> i32
%1161 = arith.extsi %1160 : i32 to i64
%1162 = llvm.getelementptr %1112[%1161] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1159 = llvm.load %1162 : !llvm.ptr -> i32
%1163 = arith.constant 1 : i32
%1164 = arith.andi %1159, %1163 : i32
%1165 = arith.constant 0 : i32
%1166 = arith.cmpi ne, %1164, %1165 : i32
cf.cond_br %1166, ^bb165, ^bb166
^bb165:
%1168 = llvm.load %1155 : !llvm.ptr -> i32
%1169 = arith.extsi %1168 : i32 to i64
%1170 = llvm.getelementptr %1112[%1169] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1167 = llvm.load %1170 : !llvm.ptr -> i32
%1171 = llvm.load %1152 : !llvm.ptr -> i32
%1172 = arith.extsi %1171 : i32 to i64
%1173 = llvm.getelementptr %1144[%1172] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1167, %1173 : i32, !llvm.ptr
%1174 = llvm.load %1152 : !llvm.ptr -> i32
%1175 = arith.constant 1 : i32
%1176 = arith.addi %1174, %1175 : i32
llvm.store %1176, %1152 : i32, !llvm.ptr
cf.br ^bb167
^bb166:
cf.br ^bb167
^bb167:
%1177 = llvm.load %1155 : !llvm.ptr -> i32
%1178 = arith.constant 1 : i32
%1179 = arith.addi %1177, %1178 : i32
llvm.store %1179, %1155 : i32, !llvm.ptr
cf.br ^bb162
^bb164:
%1180 = arith.constant 200000 : i32
%1182 = arith.extsi %1180 : i32 to i64
%1183 = arith.constant 4 : i32
%1185 = arith.extsi %1183 : i32 to i64
%1184 = arith.muli %1182, %1185 : i64
%1181 = func.call @malloc(%1184) : (i64) -> !llvm.ptr
%1187 = arith.extsi %1180 : i32 to i64
%1188 = arith.constant 8 : i32
%1190 = arith.extsi %1188 : i32 to i64
%1189 = arith.muli %1187, %1190 : i64
%1186 = func.call @malloc(%1189) : (i64) -> !llvm.ptr
%1192 = arith.extsi %1180 : i32 to i64
%1193 = arith.constant 8 : i32
%1195 = arith.extsi %1193 : i32 to i64
%1194 = arith.muli %1192, %1195 : i64
%1191 = func.call @malloc(%1194) : (i64) -> !llvm.ptr
%1196 = arith.constant 0 : i32
%1197 = llvm.mlir.constant(1 : i64) : i64
%1198 = llvm.alloca %1197 x i32 : (i64) -> !llvm.ptr
llvm.store %1196, %1198 : i32, !llvm.ptr
%1199 = arith.constant 0 : i32
%1200 = llvm.load %1198 : !llvm.ptr -> i32
%1201 = arith.extsi %1200 : i32 to i64
%1202 = llvm.getelementptr %1181[%1201] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1199, %1202 : i32, !llvm.ptr
%1203 = arith.constant 1 : i32
%1204 = llvm.load %1198 : !llvm.ptr -> i32
%1205 = arith.extsi %1203 : i32 to i64
%1206 = arith.extsi %1204 : i32 to i64
%1207 = llvm.getelementptr %1186[%1206] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1205, %1207 : i64, !llvm.ptr
%1208 = arith.constant 1 : i32
%1209 = llvm.load %1198 : !llvm.ptr -> i32
%1210 = arith.extsi %1208 : i32 to i64
%1211 = arith.extsi %1209 : i32 to i64
%1212 = llvm.getelementptr %1191[%1211] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1210, %1212 : i64, !llvm.ptr
%1213 = llvm.load %1198 : !llvm.ptr -> i32
%1214 = arith.constant 1 : i32
%1215 = arith.addi %1213, %1214 : i32
llvm.store %1215, %1198 : i32, !llvm.ptr
cf.br ^bb168
^bb168:
%1216 = llvm.load %1198 : !llvm.ptr -> i32
%1217 = arith.constant 0 : i32
%1218 = arith.cmpi sgt, %1216, %1217 : i32
cf.cond_br %1218, ^bb169, ^bb170
^bb169:
%1219 = llvm.load %1198 : !llvm.ptr -> i32
%1220 = arith.constant 1 : i32
%1221 = arith.subi %1219, %1220 : i32
llvm.store %1221, %1198 : i32, !llvm.ptr
%1223 = llvm.load %1198 : !llvm.ptr -> i32
%1224 = arith.extsi %1223 : i32 to i64
%1225 = llvm.getelementptr %1181[%1224] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1222 = llvm.load %1225 : !llvm.ptr -> i32
%1227 = llvm.load %1198 : !llvm.ptr -> i32
%1228 = arith.extsi %1227 : i32 to i64
%1229 = llvm.getelementptr %1186[%1228] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1226 = llvm.load %1229 : !llvm.ptr -> i64
%1231 = llvm.load %1198 : !llvm.ptr -> i32
%1232 = arith.extsi %1231 : i32 to i64
%1233 = llvm.getelementptr %1191[%1232] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1230 = llvm.load %1233 : !llvm.ptr -> i64
%1234 = arith.constant 1 : i32
%1236 = arith.extsi %1234 : i32 to i64
%1235 = arith.cmpi sgt, %1226, %1236 : i64
cf.cond_br %1235, ^bb171, ^bb172
^bb171:
%1237 = arith.constant 2 : i32
%1239 = arith.extsi %1237 : i32 to i64
%1238 = arith.divsi %1230, %1239 : i64
%1240 = arith.constant 0 : i32
%1241 = arith.extsi %1240 : i32 to i64
%1242 = llvm.mlir.constant(1 : i64) : i64
%1243 = llvm.alloca %1242 x i64 : (i64) -> !llvm.ptr
llvm.store %1241, %1243 : i64, !llvm.ptr
%1244 = arith.constant 0 : i32
%1245 = llvm.mlir.constant(1 : i64) : i64
%1246 = llvm.alloca %1245 x i32 : (i64) -> !llvm.ptr
llvm.store %1244, %1246 : i32, !llvm.ptr
cf.br ^bb174
^bb174:
%1247 = arith.constant 1 : i1
cf.cond_br %1247, ^bb175, ^bb176
^bb175:
%1248 = arith.constant 0 : i32
%1249 = arith.extsi %1248 : i32 to i64
%1250 = llvm.mlir.constant(1 : i64) : i64
%1251 = llvm.alloca %1250 x i64 : (i64) -> !llvm.ptr
llvm.store %1249, %1251 : i64, !llvm.ptr
%1252 = llvm.load %1246 : !llvm.ptr -> i32
%1253 = arith.constant 0 : i32
%1254 = arith.cmpi eq, %1252, %1253 : i32
%1255 = scf.if %1254 -> (i1) {
%1256 = arith.constant true
scf.yield %1256 : i1
} else {
%1257 = llvm.load %1246 : !llvm.ptr -> i32
%1258 = arith.constant 1 : i32
%1259 = arith.cmpi eq, %1257, %1258 : i32
scf.yield %1259 : i1
}
cf.cond_br %1255, ^bb177, ^bb178
^bb177:
llvm.store %1238, %1251 : i64, !llvm.ptr
cf.br ^bb179
^bb178:
%1260 = arith.constant 1 : i32
%1261 = arith.extsi %1260 : i32 to i64
%1262 = llvm.load %1246 : !llvm.ptr -> i32
%1263 = arith.constant 2 : i32
%1264 = arith.subi %1262, %1263 : i32
%1266 = arith.extsi %1264 : i32 to i64
%1265 = arith.shli %1261, %1266 : i64
%1267 = arith.muli %1230, %1265 : i64
llvm.store %1267, %1251 : i64, !llvm.ptr
cf.br ^bb179
^bb179:
%1268 = llvm.load %1243 : !llvm.ptr -> i64
%1269 = llvm.load %1251 : !llvm.ptr -> i64
%1270 = arith.addi %1268, %1269 : i64
llvm.store %1270, %1243 : i64, !llvm.ptr
%1271 = llvm.load %1243 : !llvm.ptr -> i64
%1272 = arith.extsi %arg1 : i32 to i64
%1273 = arith.cmpi sgt, %1271, %1272 : i64
cf.cond_br %1273, ^bb180, ^bb181
^bb180:
cf.br ^bb176
^bb181:
cf.br ^bb182
^bb182:
%1275 = llvm.load %1243 : !llvm.ptr -> i64
%1276 = llvm.getelementptr %arg0[%1275] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1274 = llvm.load %1276 : !llvm.ptr -> i64
%1277 = arith.constant 1 : i32
%1279 = arith.extsi %1277 : i32 to i64
%1278 = arith.addi %1274, %1279 : i64
%1280 = llvm.load %1243 : !llvm.ptr -> i64
%1281 = llvm.getelementptr %arg0[%1280] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1278, %1281 : i64, !llvm.ptr
%1282 = llvm.load %1246 : !llvm.ptr -> i32
%1283 = arith.constant 1 : i32
%1284 = arith.addi %1282, %1283 : i32
llvm.store %1284, %1246 : i32, !llvm.ptr
cf.br ^bb174
^bb176:
cf.br ^bb173
^bb172:
cf.br ^bb173
^bb173:
%1285 = llvm.mlir.constant(1 : i64) : i64
%1286 = llvm.alloca %1285 x i32 : (i64) -> !llvm.ptr
llvm.store %1222, %1286 : i32, !llvm.ptr
cf.br ^bb183
^bb183:
%1287 = llvm.load %1286 : !llvm.ptr -> i32
%1288 = llvm.load %1152 : !llvm.ptr -> i32
%1289 = arith.cmpi slt, %1287, %1288 : i32
cf.cond_br %1289, ^bb184, ^bb185
^bb184:
%1291 = llvm.load %1286 : !llvm.ptr -> i32
%1292 = arith.extsi %1291 : i32 to i64
%1293 = llvm.getelementptr %1144[%1292] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1290 = llvm.load %1293 : !llvm.ptr -> i32
%1294 = arith.constant 1 : i32
%1295 = arith.subi %1290, %1294 : i32
%1296 = arith.extsi %1295 : i32 to i64
%1297 = arith.muli %1230, %1296 : i64
%1298 = arith.extsi %1034 : i32 to i64
%1299 = arith.cmpi sgt, %1297, %1298 : i64
cf.cond_br %1299, ^bb186, ^bb187
^bb186:
cf.br ^bb185
^bb187:
cf.br ^bb188
^bb188:
%1300 = llvm.load %1286 : !llvm.ptr -> i32
%1301 = arith.constant 1 : i32
%1302 = arith.addi %1300, %1301 : i32
%1303 = llvm.load %1198 : !llvm.ptr -> i32
%1304 = arith.extsi %1303 : i32 to i64
%1305 = llvm.getelementptr %1181[%1304] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1302, %1305 : i32, !llvm.ptr
%1306 = arith.extsi %1290 : i32 to i64
%1307 = arith.muli %1226, %1306 : i64
%1308 = llvm.load %1198 : !llvm.ptr -> i32
%1309 = arith.extsi %1308 : i32 to i64
%1310 = llvm.getelementptr %1186[%1309] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1307, %1310 : i64, !llvm.ptr
%1311 = arith.constant 1 : i32
%1312 = arith.subi %1290, %1311 : i32
%1313 = arith.extsi %1312 : i32 to i64
%1314 = arith.muli %1230, %1313 : i64
%1315 = llvm.load %1198 : !llvm.ptr -> i32
%1316 = arith.extsi %1315 : i32 to i64
%1317 = llvm.getelementptr %1191[%1316] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1314, %1317 : i64, !llvm.ptr
%1318 = llvm.load %1198 : !llvm.ptr -> i32
%1319 = arith.constant 1 : i32
%1320 = arith.addi %1318, %1319 : i32
llvm.store %1320, %1198 : i32, !llvm.ptr
%1321 = arith.extsi %1290 : i32 to i64
%1322 = arith.muli %1226, %1321 : i64
%1323 = arith.extsi %1290 : i32 to i64
%1324 = arith.muli %1322, %1323 : i64
%1325 = llvm.mlir.constant(1 : i64) : i64
%1326 = llvm.alloca %1325 x i64 : (i64) -> !llvm.ptr
llvm.store %1324, %1326 : i64, !llvm.ptr
%1327 = arith.constant 1 : i32
%1328 = arith.subi %1290, %1327 : i32
%1329 = arith.extsi %1328 : i32 to i64
%1330 = arith.muli %1230, %1329 : i64
%1331 = arith.extsi %1290 : i32 to i64
%1332 = arith.muli %1330, %1331 : i64
%1333 = llvm.mlir.constant(1 : i64) : i64
%1334 = llvm.alloca %1333 x i64 : (i64) -> !llvm.ptr
llvm.store %1332, %1334 : i64, !llvm.ptr
cf.br ^bb189
^bb189:
%1335 = llvm.load %1334 : !llvm.ptr -> i64
%1336 = arith.extsi %1034 : i32 to i64
%1337 = arith.cmpi sle, %1335, %1336 : i64
cf.cond_br %1337, ^bb190, ^bb191
^bb190:
%1338 = llvm.load %1286 : !llvm.ptr -> i32
%1339 = arith.constant 1 : i32
%1340 = arith.addi %1338, %1339 : i32
%1341 = llvm.load %1198 : !llvm.ptr -> i32
%1342 = arith.extsi %1341 : i32 to i64
%1343 = llvm.getelementptr %1181[%1342] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1340, %1343 : i32, !llvm.ptr
%1344 = llvm.load %1326 : !llvm.ptr -> i64
%1345 = llvm.load %1198 : !llvm.ptr -> i32
%1346 = arith.extsi %1345 : i32 to i64
%1347 = llvm.getelementptr %1186[%1346] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1344, %1347 : i64, !llvm.ptr
%1348 = llvm.load %1334 : !llvm.ptr -> i64
%1349 = llvm.load %1198 : !llvm.ptr -> i32
%1350 = arith.extsi %1349 : i32 to i64
%1351 = llvm.getelementptr %1191[%1350] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1348, %1351 : i64, !llvm.ptr
%1352 = llvm.load %1198 : !llvm.ptr -> i32
%1353 = arith.constant 1 : i32
%1354 = arith.addi %1352, %1353 : i32
llvm.store %1354, %1198 : i32, !llvm.ptr
%1355 = llvm.load %1326 : !llvm.ptr -> i64
%1356 = arith.extsi %1290 : i32 to i64
%1357 = arith.muli %1355, %1356 : i64
llvm.store %1357, %1326 : i64, !llvm.ptr
%1358 = llvm.load %1334 : !llvm.ptr -> i64
%1359 = arith.extsi %1290 : i32 to i64
%1360 = arith.muli %1358, %1359 : i64
llvm.store %1360, %1334 : i64, !llvm.ptr
cf.br ^bb189
^bb191:
%1361 = llvm.load %1286 : !llvm.ptr -> i32
%1362 = arith.constant 1 : i32
%1363 = arith.addi %1361, %1362 : i32
llvm.store %1363, %1286 : i32, !llvm.ptr
cf.br ^bb183
^bb185:
cf.br ^bb168
^bb170:
func.call @free(%1181) : (!llvm.ptr) -> ()
func.call @free(%1186) : (!llvm.ptr) -> ()
func.call @free(%1191) : (!llvm.ptr) -> ()
func.call @free(%1112) : (!llvm.ptr) -> ()
func.call @free(%1144) : (!llvm.ptr) -> ()
func.return
}
func.func @solve(%arg0: i32) -> i64 {
%1370 = arith.constant 1 : i32
%1371 = arith.addi %arg0, %1370 : i32
%1372 = arith.extsi %1371 : i32 to i64
%1373 = arith.constant 8 : i32
%1374 = arith.extsi %1373 : i32 to i64
%1369 = func.call @calloc(%1372, %1374) : (i64, i64) -> !llvm.ptr
func.call @add_component_multiplicities(%1369, %arg0) : (!llvm.ptr, i32) -> ()
%1377 = arith.constant 1 : i32
%1378 = arith.addi %arg0, %1377 : i32
%1379 = arith.extsi %1378 : i32 to i64
%1380 = arith.constant 8 : i32
%1381 = arith.extsi %1380 : i32 to i64
%1376 = func.call @calloc(%1379, %1381) : (i64, i64) -> !llvm.ptr
%1382 = arith.constant 1 : i32
%1383 = llvm.mlir.constant(1 : i64) : i64
%1384 = llvm.alloca %1383 x i32 : (i64) -> !llvm.ptr
llvm.store %1382, %1384 : i32, !llvm.ptr
cf.br ^bb192
^bb192:
%1385 = llvm.load %1384 : !llvm.ptr -> i32
%1386 = arith.cmpi sle, %1385, %arg0 : i32
cf.cond_br %1386, ^bb193, ^bb194
^bb193:
%1388 = llvm.load %1384 : !llvm.ptr -> i32
%1389 = arith.extsi %1388 : i32 to i64
%1390 = llvm.getelementptr %1369[%1389] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1387 = llvm.load %1390 : !llvm.ptr -> i64
%1391 = arith.constant 0 : i32
%1393 = arith.extsi %1391 : i32 to i64
%1392 = arith.cmpi ne, %1387, %1393 : i64
cf.cond_br %1392, ^bb195, ^bb196
^bb195:
%1394 = llvm.load %1384 : !llvm.ptr -> i32
%1395 = arith.extsi %1394 : i32 to i64
%1396 = llvm.mlir.addressof @MOD : !llvm.ptr
%1397 = llvm.load %1396 : !llvm.ptr -> i64
%1398 = arith.remsi %1387, %1397 : i64
%1399 = arith.muli %1395, %1398 : i64
%1400 = llvm.mlir.addressof @MOD : !llvm.ptr
%1401 = llvm.load %1400 : !llvm.ptr -> i64
%1402 = arith.remsi %1399, %1401 : i64
%1403 = llvm.load %1384 : !llvm.ptr -> i32
%1404 = llvm.mlir.constant(1 : i64) : i64
%1405 = llvm.alloca %1404 x i32 : (i64) -> !llvm.ptr
llvm.store %1403, %1405 : i32, !llvm.ptr
cf.br ^bb198
^bb198:
%1406 = llvm.load %1405 : !llvm.ptr -> i32
%1407 = arith.cmpi sle, %1406, %arg0 : i32
cf.cond_br %1407, ^bb199, ^bb200
^bb199:
%1409 = llvm.load %1405 : !llvm.ptr -> i32
%1410 = arith.extsi %1409 : i32 to i64
%1411 = llvm.getelementptr %1376[%1410] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1408 = llvm.load %1411 : !llvm.ptr -> i64
%1412 = arith.addi %1408, %1402 : i64
%1413 = llvm.mlir.addressof @MOD : !llvm.ptr
%1414 = llvm.load %1413 : !llvm.ptr -> i64
%1415 = arith.remsi %1412, %1414 : i64
%1416 = llvm.load %1405 : !llvm.ptr -> i32
%1417 = arith.extsi %1416 : i32 to i64
%1418 = llvm.getelementptr %1376[%1417] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1415, %1418 : i64, !llvm.ptr
%1419 = llvm.load %1405 : !llvm.ptr -> i32
%1420 = llvm.load %1384 : !llvm.ptr -> i32
%1421 = arith.addi %1419, %1420 : i32
llvm.store %1421, %1405 : i32, !llvm.ptr
cf.br ^bb198
^bb200:
cf.br ^bb197
^bb196:
cf.br ^bb197
^bb197:
%1422 = llvm.load %1384 : !llvm.ptr -> i32
%1423 = arith.constant 1 : i32
%1424 = arith.addi %1422, %1423 : i32
llvm.store %1424, %1384 : i32, !llvm.ptr
cf.br ^bb192
^bb194:
%1426 = arith.constant 2 : i32
%1427 = arith.addi %arg0, %1426 : i32
%1428 = arith.extsi %1427 : i32 to i64
%1429 = arith.constant 8 : i32
%1430 = arith.extsi %1429 : i32 to i64
%1425 = func.call @calloc(%1428, %1430) : (i64, i64) -> !llvm.ptr
%1431 = arith.constant 1 : i32
%1432 = llvm.mlir.constant(1 : i64) : i64
%1433 = llvm.alloca %1432 x i32 : (i64) -> !llvm.ptr
llvm.store %1431, %1433 : i32, !llvm.ptr
cf.br ^bb201
^bb201:
%1434 = llvm.load %1433 : !llvm.ptr -> i32
%1435 = arith.constant 1 : i32
%1436 = arith.addi %arg0, %1435 : i32
%1437 = arith.cmpi sle, %1434, %1436 : i32
cf.cond_br %1437, ^bb202, ^bb203
^bb202:
%1439 = llvm.load %1433 : !llvm.ptr -> i32
%1440 = arith.extsi %1439 : i32 to i64
%1438 = func.call @inv_mod(%1440) : (i64) -> i64
%1441 = llvm.load %1433 : !llvm.ptr -> i32
%1442 = arith.extsi %1441 : i32 to i64
%1443 = llvm.getelementptr %1425[%1442] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1438, %1443 : i64, !llvm.ptr
%1444 = llvm.load %1433 : !llvm.ptr -> i32
%1445 = arith.constant 1 : i32
%1446 = arith.addi %1444, %1445 : i32
llvm.store %1446, %1433 : i32, !llvm.ptr
cf.br ^bb201
^bb203:
%1448 = arith.constant 1 : i32
%1449 = arith.addi %arg0, %1448 : i32
%1450 = arith.extsi %1449 : i32 to i64
%1451 = arith.constant 8 : i32
%1452 = arith.extsi %1451 : i32 to i64
%1447 = func.call @calloc(%1450, %1452) : (i64, i64) -> !llvm.ptr
%1453 = arith.constant 1 : i32
%1454 = llvm.mlir.constant(1 : i64) : i64
%1455 = llvm.alloca %1454 x i32 : (i64) -> !llvm.ptr
llvm.store %1453, %1455 : i32, !llvm.ptr
cf.br ^bb204
^bb204:
%1456 = llvm.load %1455 : !llvm.ptr -> i32
%1457 = arith.cmpi sle, %1456, %arg0 : i32
cf.cond_br %1457, ^bb205, ^bb206
^bb205:
%1459 = llvm.load %1455 : !llvm.ptr -> i32
%1460 = arith.extsi %1459 : i32 to i64
%1461 = llvm.getelementptr %1376[%1460] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1458 = llvm.load %1461 : !llvm.ptr -> i64
%1463 = llvm.load %1455 : !llvm.ptr -> i32
%1464 = arith.extsi %1463 : i32 to i64
%1465 = llvm.getelementptr %1425[%1464] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1462 = llvm.load %1465 : !llvm.ptr -> i64
%1466 = arith.muli %1458, %1462 : i64
%1467 = llvm.mlir.addressof @MOD : !llvm.ptr
%1468 = llvm.load %1467 : !llvm.ptr -> i64
%1469 = arith.remsi %1466, %1468 : i64
%1470 = llvm.load %1455 : !llvm.ptr -> i32
%1471 = arith.extsi %1470 : i32 to i64
%1472 = llvm.getelementptr %1447[%1471] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1469, %1472 : i64, !llvm.ptr
%1473 = llvm.load %1455 : !llvm.ptr -> i32
%1474 = arith.constant 1 : i32
%1475 = arith.addi %1473, %1474 : i32
llvm.store %1475, %1455 : i32, !llvm.ptr
cf.br ^bb204
^bb206:
%1477 = arith.constant 1 : i32
%1478 = arith.addi %arg0, %1477 : i32
%1479 = arith.constant 1 : i32
%1480 = arith.addi %arg0, %1479 : i32
%1476 = func.call @poly_exp(%1447, %1478, %1480, %1425) : (!llvm.ptr, i32, i32, !llvm.ptr) -> !llvm.ptr
%1481 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%1482 = llvm.load %1481 : !llvm.ptr -> i32
%1483 = func.call @special_component(%arg0) : (i32) -> !llvm.ptr
%1485 = arith.constant 1 : i32
%1486 = arith.addi %arg0, %1485 : i32
%1484 = func.call @polymul(%1476, %1482, %1483, %1486) : (!llvm.ptr, i32, !llvm.ptr, i32) -> !llvm.ptr
%1487 = llvm.mlir.addressof @g_out_len : !llvm.ptr
%1488 = llvm.load %1487 : !llvm.ptr -> i32
%1490 = arith.extsi %arg0 : i32 to i64
%1491 = llvm.getelementptr %1484[%1490] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1489 = llvm.load %1491 : !llvm.ptr -> i64
%1492 = llvm.mlir.addressof @MOD : !llvm.ptr
%1493 = llvm.load %1492 : !llvm.ptr -> i64
%1494 = arith.remsi %1489, %1493 : i64
func.call @free(%1369) : (!llvm.ptr) -> ()
func.call @free(%1376) : (!llvm.ptr) -> ()
func.call @free(%1425) : (!llvm.ptr) -> ()
func.call @free(%1447) : (!llvm.ptr) -> ()
func.call @free(%1476) : (!llvm.ptr) -> ()
func.call @free(%1483) : (!llvm.ptr) -> ()
func.call @free(%1484) : (!llvm.ptr) -> ()
func.return %1494 : i64
}
func.func @main() -> i32 {
%1502 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1504 = arith.constant 10000 : i32
%1503 = func.call @solve(%1504) : (i32) -> i64
%1505 = llvm.call @printf(%1502, %1503) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1506 = arith.constant 0 : i32
func.return %1506 : i32
}
}