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