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