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