← All problems Problem 621
Sum of three triangular numbers: G(17526 * 10^9). G(n) = r_3(8n+3) / 8 Uses class number formula: G(n) = 3 * h(D) * S / w_div2 where D = -n0, N = n0 * f^2, S = sum_{d|f} mu(d)*(D/d)*sigma(f/d)
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 Sieve-based divisor sums Verdict Suboptimal
Flow source
# Project Euler 621
# Sum of three triangular numbers: G(17526 * 10^9).
# G(n) = r_3(8n+3) / 8
# Uses class number formula: G(n) = 3 * h(D) * S / w_div2
# where D = -n0, N = n0 * f^2, S = sum_{d|f} mu(d)*(D/d)*sigma(f/d)
import euler.nt { gcd, isqrt, mod_pow, is_prime }
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
}
function mul_mod_ll(a: i64, b: i64, m: i64) -> i64 {
return ((a as i128) * (b as i128) % (m as i128)) as i64
}
function pow_mod_ll(a0: i64, e0: i64, m: i64) -> i64 {
let mut r: i64 = 1
let mut b: i64 = a0 % m
let mut e: i64 = e0
while e > 0 {
if e % 2 == 1 { r = mul_mod_ll(r, b, m) }
b = mul_mod_ll(b, b, m)
e = e / 2
}
return r
}
# Miller-Rabin (deterministic for 64-bit)
function is_prime_ll(n: i64) -> bool {
if n < 2 { return false }
let small: array<i64, 11> = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 37]
for i in 0..11 {
if n == small[i] { return true }
if n % small[i] == 0 { return false }
}
let mut d: i64 = n - 1
let mut s: i32 = 0
while d % 2 == 0 { d = d / 2; s = s + 1 }
let bases: array<i64, 7> = [2, 3, 5, 7, 11, 13, 17]
for i in 0..7 {
let a: i64 = bases[i]
if a % n == 0 { continue }
let mut x: i64 = pow_mod_ll(a, d, n)
if x == 1 || x == n - 1 { continue }
let mut found: bool = false
for j in 0..(s - 1) {
x = mul_mod_ll(x, x, n)
if x == n - 1 { found = true; break }
}
if !found { return false }
}
return true
}
# Pollard's rho
function pollard_rho(n: i64) -> i64 {
if n % 2 == 0 { return 2 }
if n % 3 == 0 { return 3 }
if is_prime_ll(n) { return n }
let mut c: i64 = 1
let mut x: i64 = 2
let mut y: i64 = 2
let mut d: i64 = 1
while d == 1 {
x = (mul_mod_ll(x, x, n) + c) % n
y = (mul_mod_ll(y, y, n) + c) % n
y = (mul_mod_ll(y, y, n) + c) % n
let diff: i64 = if x > y { x - y } else { y - x }
d = gcd(diff, n)
}
if d == n {
c = 2
while c < 100 {
x = 2; y = 2; d = 1
while d == 1 {
x = (mul_mod_ll(x, x, n) + c) % n
y = (mul_mod_ll(y, y, n) + c) % n
y = (mul_mod_ll(y, y, n) + c) % n
let diff: i64 = if x > y { x - y } else { y - x }
d = gcd(diff, n)
}
if d != n { return d }
c = c + 1
}
}
return d
}
# Factorize n into primes[] and exps[]
function factorize_ll(n0: i64, primes: ptr<i64>, exps: ptr<i32>) -> i32 {
let mut n: i64 = n0
let mut cnt: i32 = 0
while n > 1 {
if is_prime_ll(n) {
let mut found: bool = false
for i in 0..cnt {
if primes[i] == n { exps[i] = exps[i] + 1; found = true; break }
}
if !found {
primes[cnt] = n
exps[cnt] = 1
cnt = cnt + 1
}
break
}
let mut d: i64 = pollard_rho(n)
while !is_prime_ll(d) { d = pollard_rho(d) }
let mut found: bool = false
for i in 0..cnt {
if primes[i] == d { exps[i] = exps[i] + 1; found = true; break }
}
if !found {
primes[cnt] = d
exps[cnt] = 1
cnt = cnt + 1
}
n = n / d
}
return cnt
}
# Legendre symbol (a/p) for odd prime p
function legendre(a0: i64, p: i64) -> i32 {
let a: i64 = a0 % p
let a2: i64 = if a < 0 { a + p } else { a }
if a2 == 0 { return 0 }
let t: i64 = pow_mod_ll(a2, (p - 1) / 2, p)
if t == p - 1 { return -1 }
return 1
}
# Tonelli-Shanks: sqrt of n mod p (odd prime)
function tonelli_shanks2(n0: i64, p: i64) -> i64 {
let n: i64 = n0 % p
let n2: i64 = if n < 0 { n + p } else { n }
if n2 == 0 { return 0 }
if legendre(n2, p) != 1 { return -1 }
if p % 4 == 3 { return pow_mod_ll(n2, (p + 1) / 4, p) }
let mut q: i64 = p - 1
let mut s: i32 = 0
while q % 2 == 0 { q = q / 2; s = s + 1 }
let mut z: i64 = 2
while legendre(z, p) != -1 { z = z + 1 }
let mut c: i64 = pow_mod_ll(z, q, p)
let mut r: i64 = pow_mod_ll(n2, (q + 1) / 2, p)
let mut t: i64 = pow_mod_ll(n2, q, p)
let mut m: i32 = s
while t != 1 {
let mut i: i32 = 1
let mut t2: i64 = mul_mod_ll(t, t, p)
while i < m && t2 != 1 {
t2 = mul_mod_ll(t2, t2, p)
i = i + 1
}
let b: i64 = pow_mod_ll(c, (1 as i64) << (m - i - 1), p)
r = mul_mod_ll(r, b, p)
t = mul_mod_ll(mul_mod_ll(t, b, p), b, p)
c = mul_mod_ll(b, b, p)
m = i
}
return r
}
# Hensel lift: lift root r mod p to root mod p^e
function hensel_lift(n0: i64, p: i64, e: i32, r0: i64) -> i64 {
let mut pe: i64 = p
let mut r_mod: i64 = r0 % p
let mut pe_final: i64 = 1
for i in 0..e { pe_final = pe_final * p }
let mut n: i64 = n0 % pe_final
if n < 0 { n = n + pe_final }
let mut k: i32 = 1
while k < e {
let diff: i64 = r_mod * r_mod - n
let mut q: i64 = diff / pe
if diff % pe != 0 && ((diff < 0) != (pe < 0)) { q = q - 1 }
let mut rhs: i64 = q % p
if rhs < 0 { rhs = rhs + p }
let inv: i64 = pow_mod_ll((2 * r_mod) % p, p - 2, p)
let t: i64 = (p - rhs) * inv % p
r_mod = r_mod + t * pe
pe = pe * p
r_mod = r_mod % pe
k = k + 1
}
return r_mod
}
# Roots of x^2 = n (mod p^e) for odd prime p
# Returns number of roots, fills roots[]
function roots_mod_pe(n0: i64, p: i64, e: i32, roots: ptr<i64>) -> i32 {
let mut pe: i64 = 1
for i in 0..e { pe = pe * p }
let mut n: i64 = n0 % pe
if n < 0 { n = n + pe }
if n % p == 0 {
if n == 0 {
let mut step: i64 = 1
for i in 0..((e + 1) / 2) { step = step * p }
let mut cnt: i32 = 0
let mut x: i64 = 0
while x < pe {
roots[cnt] = x
cnt = cnt + 1
x = x + step
}
return cnt
}
if e == 1 { roots[0] = 0; return 1 }
return 0
}
let r: i64 = tonelli_shanks2(n, p)
if r == -1 { return 0 }
let mut r2: i64 = r
if e > 1 {
r2 = hensel_lift(n, p, e, r)
}
let r2b: i64 = pe - r2
if r2b == r2 { roots[0] = r2; return 1 }
roots[0] = r2
roots[1] = r2b
return 2
}
# Extended Euclidean algorithm
function ext_gcd(a0: i64, b0: i64, x: ptr<i64>, y: ptr<i64>) -> i64 {
if b0 == 0 { x[0] = 1; y[0] = 0; return a0 }
let x1: ptr<i64> = calloc(1, 8) as ptr<i64>
let y1: ptr<i64> = calloc(1, 8) as ptr<i64>
let g: i64 = ext_gcd(b0, a0 % b0, x1, y1)
x[0] = y1[0]
y[0] = x1[0] - (a0 / b0) * y1[0]
free(x1 as ptr<void>)
free(y1 as ptr<void>)
return g
}
# Modular inverse of a mod m
function mod_inv_general(a0: i64, m: i64) -> i64 {
let x: ptr<i64> = calloc(1, 8) as ptr<i64>
let y: ptr<i64> = calloc(1, 8) as ptr<i64>
let mut a: i64 = a0 % m
if a < 0 { a = a + m }
ext_gcd(a, m, x, y)
let mut r: i64 = x[0] % m
if r < 0 { r = r + m }
free(x as ptr<void>)
free(y as ptr<void>)
return r
}
# CRT: combine x=a1 (mod m1), x=a2 (mod m2)
function crt(a1: i64, m1: i64, a2: i64, m2: i64, out_x: ptr<i64>, out_m: ptr<i64>) -> void {
if m1 == 1 { out_x[0] = a2; out_m[0] = m2; return }
if m2 == 1 { out_x[0] = a1; out_m[0] = m1; return }
let inv: i64 = mod_inv_general(m1 % m2, m2)
let t: i64 = (((a2 - a1) % m2 + m2) % m2) * inv % m2
out_x[0] = a1 + m1 * t
out_m[0] = m1 * m2
}
# Sieve smallest prime factor
function sieve_spf(n: i32, spf: ptr<i32>) -> void {
for i in 0..(n + 1) { spf[i] = i }
let mut i: i32 = 2
while i * i <= n {
if spf[i] == i {
let mut j: i32 = i * i
while j <= n {
if spf[j] == j { spf[j] = i }
j = j + i
}
}
i = i + 1
}
}
# Factorize small number using spf
function factorize_small(x0: i32, spf: ptr<i32>, primes: ptr<i32>, exps: ptr<i32>) -> i32 {
let mut x: i32 = x0
let mut cnt: i32 = 0
while x > 1 {
let p: i32 = spf[x]
let mut e: i32 = 0
while x % p == 0 { x = x / p; e = e + 1 }
primes[cnt] = p
exps[cnt] = e
cnt = cnt + 1
}
return cnt
}
# Class number h(D) for D < 0, D = 5 mod 8
function class_number(D: i64) -> i64 {
let absD: i64 = -D
let amax: i64 = isqrt(absD / 3)
let spf: ptr<i32> = calloc((amax + 1) as i64, 4) as ptr<i32>
sieve_spf(amax as i32, spf)
let mut h: i64 = 0
# For D = 5 mod 8, only odd a values
let mut a: i64 = 1
while a <= amax {
let fac_p: ptr<i32> = calloc(20, 4) as ptr<i32>
let fac_e: ptr<i32> = calloc(20, 4) as ptr<i32>
let nfac: i32 = factorize_small(a as i32, spf, fac_p, fac_e)
# Check: if p|D and p^2|a, skip
let mut bad: bool = false
for i in 0..nfac {
if fac_e[i] >= 2 && D % (fac_p[i] as i64) == 0 { bad = true; break }
}
if !bad {
# Build roots mod a via CRT
let roots: ptr<i64> = calloc(1024, 8) as ptr<i64>
let mut n_roots: i32 = 1
roots[0] = 0
let mut mod: i64 = 1
let mut ok: bool = true
for i in 0..nfac {
let p: i64 = fac_p[i] as i64
let e: i32 = fac_e[i]
let mut pe: i64 = 1
for j in 0..e { pe = pe * p }
let rset: ptr<i64> = calloc(8, 8) as ptr<i64>
let nr: i32 = roots_mod_pe(D, p, e, rset)
if nr == 0 { ok = false; free(rset as ptr<void>); break }
let new_roots: ptr<i64> = calloc(1024, 8) as ptr<i64>
let mut new_nr: i32 = 0
for j in 0..n_roots {
for k in 0..nr {
let x: ptr<i64> = calloc(1, 8) as ptr<i64>
let m: ptr<i64> = calloc(1, 8) as ptr<i64>
crt(roots[j], mod, rset[k], pe, x, m)
new_roots[new_nr] = x[0]
new_nr = new_nr + 1
free(x as ptr<void>)
free(m as ptr<void>)
}
}
memcpy(roots as ptr<void>, new_roots as ptr<void>, (new_nr as i64) * 8)
n_roots = new_nr
mod = mod * pe
free(new_roots as ptr<void>)
free(rset as ptr<void>)
}
if ok {
for ri in 0..n_roots {
let r: i64 = roots[ri]
let b_signed: i64
if r == 0 {
b_signed = a
} else {
if r % 2 == 1 {
b_signed = r
} else {
b_signed = r - a
}
}
let b: i64 = if b_signed < 0 { -b_signed } else { b_signed }
if b > a { continue }
let num: i64 = b * b - D
let den: i64 = 4 * a
if num % den != 0 { continue }
let c: i64 = num / den
if a > c { continue }
let abs_b: i64 = if b_signed < 0 { -b_signed } else { b_signed }
if (abs_b == a || a == c) && b_signed < 0 { continue }
h = h + 1
}
}
free(roots as ptr<void>)
}
free(fac_p as ptr<void>)
free(fac_e as ptr<void>)
a = a + 2
}
free(spf as ptr<void>)
return h
}
function main() -> i32 {
let n: i64 = (17526 as i64) * 1000000000
let N: i64 = 8 * n + 3
# Factor N
let primes: ptr<i64> = calloc(20, 8) as ptr<i64>
let exps: ptr<i32> = calloc(20, 4) as ptr<i32>
let nfac: i32 = factorize_ll(N, primes, exps)
# N = n0 * f^2, n0 squarefree
let mut n0: i64 = 1
let mut f: i64 = 1
for i in 0..nfac {
if exps[i] % 2 == 1 { n0 = n0 * primes[i] }
for j in 0..(exps[i] / 2) { f = f * primes[i] }
}
let D: i64 = -n0
let h: i64 = class_number(D)
# w_div2
let mut w_div2: i64 = 1
if D == -3 { w_div2 = 3 }
else {
if D == -4 { w_div2 = 2 }
}
# S = sum_{d|f} mu(d) * (D/d) * sigma(f/d)
let f_primes: ptr<i64> = calloc(20, 8) as ptr<i64>
let f_exps: ptr<i32> = calloc(20, 4) as ptr<i32>
let nffac: i32 = factorize_ll(f, f_primes, f_exps)
let mut S: i64 = 0
let nprimes: i32 = nffac
for mask in 0..(1 << nprimes) {
let mut bits: i32 = 0
let mut jac: i64 = 1
let mut sig: i64 = 1
let mut valid: bool = true
for i in 0..nprimes {
let p: i64 = f_primes[i]
let mut e: i32 = f_exps[i]
if ((mask >> i) & 1) == 1 {
bits = bits + 1
jac = jac * (legendre(D, p) as i64)
e = e - 1
}
if e < 0 { sig = 0; valid = false; break }
# sigma(p^e) = (p^(e+1)-1)/(p-1)
let mut pe: i64 = 1
for j in 0..(e + 1) { pe = pe * p }
sig = sig * (pe - 1) / (p - 1)
}
if !valid || sig == 0 { continue }
let sign: i64 = if bits % 2 == 1 { -1 } else { 1 }
S = S + sign * jac * sig
}
# G(n) = 3 * h * S / w_div2
let result: i64 = 3 * h * S / w_div2
printf("%lld\n", result)
free(primes as ptr<void>)
free(exps as ptr<void>)
free(f_primes as ptr<void>)
free(f_exps as ptr<void>)
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 gcd_i64_i64(int64_t a0, int64_t b0);
int64_t lcm_i64_i64(int64_t a, int64_t b);
int64_t isqrt_i64(int64_t n);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
bool is_prime_i64(int64_t n);
int64_t mul_mod_ll_i64_i64_i64(int64_t a, int64_t b, int64_t m);
int64_t pow_mod_ll_i64_i64_i64(int64_t a0, int64_t e0, int64_t m);
bool is_prime_ll_i64(int64_t n);
int64_t pollard_rho_i64(int64_t n);
int32_t factorize_ll_i64_ptr_i64_ptr_i32(int64_t n0, int64_t* primes, int32_t* exps);
int32_t legendre_i64_i64(int64_t a0, int64_t p);
int64_t tonelli_shanks2_i64_i64(int64_t n0, int64_t p);
int64_t hensel_lift_i64_i64_i32_i64(int64_t n0, int64_t p, int32_t e, int64_t r0);
int32_t roots_mod_pe_i64_i64_i32_ptr_i64(int64_t n0, int64_t p, int32_t e, int64_t* roots);
int64_t ext_gcd_i64_i64_ptr_i64_ptr_i64(int64_t a0, int64_t b0, int64_t* x, int64_t* y);
int64_t mod_inv_general_i64_i64(int64_t a0, int64_t m);
void crt_i64_i64_i64_i64_ptr_i64_ptr_i64(int64_t a1, int64_t m1, int64_t a2, int64_t m2, int64_t* out_x, int64_t* out_m);
void sieve_spf_i32_ptr_i32(int32_t n, int32_t* spf);
int32_t factorize_small_i32_ptr_i32_ptr_i32_ptr_i32(int32_t x0, int32_t* spf, int32_t* primes, int32_t* exps);
int64_t class_number_i64(int64_t D);
int32_t main(void);
int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t lcm_i64_i64(int64_t a, int64_t b) {
if ((a == 0 || b == 0)) {
return 0;
}
return (FLOW_CHECKED_DIV((a), (gcd_i64_i64(a, b))) * b);
}
int64_t isqrt_i64(int64_t n) {
if (n < 2) {
return n;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod) {
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
int64_t b = FLOW_CHECKED_MOD((b0), (mod));
int64_t result = 0;
while (b > 0) {
if (FLOW_CHECKED_MOD((b), (2)) == 1) {
result = FLOW_CHECKED_MOD(((result + a)), (mod));
}
a = FLOW_CHECKED_MOD(((a * 2)), (mod));
b = FLOW_CHECKED_DIV((b), (2));
}
return result;
}
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
if (mod == 1) {
return 0;
}
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (mod));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mulmod_i64_i64_i64(result, b, mod);
}
b = mulmod_i64_i64_i64(b, b, mod);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
bool is_prime_i64(int64_t n) {
if (n < 2) {
return 0;
}
if (n < 4) {
return 1;
}
if ((FLOW_CHECKED_MOD((n), (2)) == 0 || FLOW_CHECKED_MOD((n), (3)) == 0)) {
return 0;
}
int64_t i = 5;
while ((i * i) <= n) {
if ((FLOW_CHECKED_MOD((n), (i)) == 0 || FLOW_CHECKED_MOD((n), ((i + 2))) == 0)) {
return 0;
}
i = (i + 6);
}
return 1;
}
int64_t mul_mod_ll_i64_i64_i64(int64_t a, int64_t b, int64_t m) {
return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(b)))), (((__int128)(m))))));
}
int64_t pow_mod_ll_i64_i64_i64(int64_t a0, int64_t e0, int64_t m) {
int64_t r = 1;
int64_t b = FLOW_CHECKED_MOD((a0), (m));
int64_t e = e0;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
r = mul_mod_ll_i64_i64_i64(r, b, m);
}
b = mul_mod_ll_i64_i64_i64(b, b, m);
e = FLOW_CHECKED_DIV((e), (2));
}
return r;
}
bool is_prime_ll_i64(int64_t n) {
if (n < 2) {
return 0;
}
int64_t small[11] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 37 };
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= 11) ? i < 11 : i > 11; i += (0 <= 11) ? 1 : -1) {
if (n == (((unsigned)(i) < 11) ? small[i] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(i), 11), flow_fault_handler("array index out of bounds"), small[0]))) {
return 1;
}
if (FLOW_CHECKED_MOD((n), ((((unsigned)(i) < 11) ? small[i] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(i), 11), flow_fault_handler("array index out of bounds"), small[0])))) == 0) {
return 0;
}
}
int64_t d = (n - 1);
int32_t s = 0;
while (FLOW_CHECKED_MOD((d), (2)) == 0) {
d = FLOW_CHECKED_DIV((d), (2));
s = (s + 1);
}
int64_t bases[7] = { 2, 3, 5, 7, 11, 13, 17 };
int32_t __flow_step_2 = 1;
for (int32_t i = 0; (0 <= 7) ? i < 7 : i > 7; i += (0 <= 7) ? 1 : -1) {
int64_t a = (((unsigned)(i) < 7) ? bases[i] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(i), 7), flow_fault_handler("array index out of bounds"), bases[0]));
if (FLOW_CHECKED_MOD((a), (n)) == 0) {
continue;
}
int64_t x = pow_mod_ll_i64_i64_i64(a, d, n);
if ((x == 1 || x == (n - 1))) {
continue;
}
bool found = 0;
int32_t __flow_step_3 = 1;
for (int32_t j = 0; (0 <= (s - 1)) ? j < (s - 1) : j > (s - 1); j += (0 <= (s - 1)) ? 1 : -1) {
x = mul_mod_ll_i64_i64_i64(x, x, n);
if (x == (n - 1)) {
found = 1;
break;
}
}
if ((!(found))) {
return 0;
}
}
return 1;
}
int64_t pollard_rho_i64(int64_t n) {
if (FLOW_CHECKED_MOD((n), (2)) == 0) {
return 2;
}
if (FLOW_CHECKED_MOD((n), (3)) == 0) {
return 3;
}
if (is_prime_ll_i64(n)) {
return n;
}
int64_t c = 1;
int64_t x = 2;
int64_t y = 2;
int64_t d = 1;
while (d == 1) {
x = FLOW_CHECKED_MOD(((mul_mod_ll_i64_i64_i64(x, x, n) + c)), (n));
y = FLOW_CHECKED_MOD(((mul_mod_ll_i64_i64_i64(y, y, n) + c)), (n));
y = FLOW_CHECKED_MOD(((mul_mod_ll_i64_i64_i64(y, y, n) + c)), (n));
int64_t diff = ((x > y) ? ((x - y)) : ((y - x)));
d = gcd_i64_i64(diff, n);
}
if (d == n) {
c = 2;
while (c < 100) {
x = 2;
y = 2;
d = 1;
while (d == 1) {
x = FLOW_CHECKED_MOD(((mul_mod_ll_i64_i64_i64(x, x, n) + c)), (n));
y = FLOW_CHECKED_MOD(((mul_mod_ll_i64_i64_i64(y, y, n) + c)), (n));
y = FLOW_CHECKED_MOD(((mul_mod_ll_i64_i64_i64(y, y, n) + c)), (n));
int64_t diff = ((x > y) ? ((x - y)) : ((y - x)));
d = gcd_i64_i64(diff, n);
}
if (d != n) {
return d;
}
c = (c + 1);
}
}
return d;
}
int32_t factorize_ll_i64_ptr_i64_ptr_i32(int64_t n0, int64_t* primes, int32_t* exps) {
int64_t n = n0;
int32_t cnt = 0;
while (n > 1) {
if (is_prime_ll_i64(n)) {
bool found = 0;
int32_t __flow_step_4 = 1;
for (int32_t i = 0; (0 <= cnt) ? i < cnt : i > cnt; i += (0 <= cnt) ? 1 : -1) {
if (primes[i] == n) {
exps[i] = (exps[i] + 1);
found = 1;
break;
}
}
if ((!(found))) {
primes[cnt] = n;
exps[cnt] = 1;
cnt = (cnt + 1);
}
break;
}
int64_t d = pollard_rho_i64(n);
while ((!(is_prime_ll_i64(d)))) {
d = pollard_rho_i64(d);
}
bool found = 0;
int32_t __flow_step_5 = 1;
for (int32_t i = 0; (0 <= cnt) ? i < cnt : i > cnt; i += (0 <= cnt) ? 1 : -1) {
if (primes[i] == d) {
exps[i] = (exps[i] + 1);
found = 1;
break;
}
}
if ((!(found))) {
primes[cnt] = d;
exps[cnt] = 1;
cnt = (cnt + 1);
}
n = FLOW_CHECKED_DIV((n), (d));
}
return cnt;
}
int32_t legendre_i64_i64(int64_t a0, int64_t p) {
int64_t a = FLOW_CHECKED_MOD((a0), (p));
int64_t a2 = ((a < 0) ? ((a + p)) : (a));
if (a2 == 0) {
return 0;
}
int64_t t = pow_mod_ll_i64_i64_i64(a2, FLOW_CHECKED_DIV(((p - 1)), (2)), p);
if (t == (p - 1)) {
return (-1);
}
return 1;
}
int64_t tonelli_shanks2_i64_i64(int64_t n0, int64_t p) {
int64_t n = FLOW_CHECKED_MOD((n0), (p));
int64_t n2 = ((n < 0) ? ((n + p)) : (n));
if (n2 == 0) {
return 0;
}
if (legendre_i64_i64(n2, p) != 1) {
return (-1);
}
if (FLOW_CHECKED_MOD((p), (4)) == 3) {
return pow_mod_ll_i64_i64_i64(n2, FLOW_CHECKED_DIV(((p + 1)), (4)), p);
}
int64_t q = (p - 1);
int32_t s = 0;
while (FLOW_CHECKED_MOD((q), (2)) == 0) {
q = FLOW_CHECKED_DIV((q), (2));
s = (s + 1);
}
int64_t z = 2;
while (legendre_i64_i64(z, p) != (-1)) {
z = (z + 1);
}
int64_t c = pow_mod_ll_i64_i64_i64(z, q, p);
int64_t r = pow_mod_ll_i64_i64_i64(n2, FLOW_CHECKED_DIV(((q + 1)), (2)), p);
int64_t t = pow_mod_ll_i64_i64_i64(n2, q, p);
int32_t m = s;
while (t != 1) {
int32_t i = 1;
int64_t t2 = mul_mod_ll_i64_i64_i64(t, t, p);
while ((i < m && t2 != 1)) {
t2 = mul_mod_ll_i64_i64_i64(t2, t2, p);
i = (i + 1);
}
int64_t b = pow_mod_ll_i64_i64_i64(c, FLOW_CHECKED_SHL((((int64_t)(1))), (((m - i) - 1))), p);
r = mul_mod_ll_i64_i64_i64(r, b, p);
t = mul_mod_ll_i64_i64_i64(mul_mod_ll_i64_i64_i64(t, b, p), b, p);
c = mul_mod_ll_i64_i64_i64(b, b, p);
m = i;
}
return r;
}
int64_t hensel_lift_i64_i64_i32_i64(int64_t n0, int64_t p, int32_t e, int64_t r0) {
int64_t pe = p;
int64_t r_mod = FLOW_CHECKED_MOD((r0), (p));
int64_t pe_final = 1;
int32_t __flow_step_6 = 1;
for (int32_t i = 0; (0 <= e) ? i < e : i > e; i += (0 <= e) ? 1 : -1) {
pe_final = (pe_final * p);
}
int64_t n = FLOW_CHECKED_MOD((n0), (pe_final));
if (n < 0) {
n = (n + pe_final);
}
int32_t k = 1;
while (k < e) {
int64_t diff = ((r_mod * r_mod) - n);
int64_t q = FLOW_CHECKED_DIV((diff), (pe));
if ((FLOW_CHECKED_MOD((diff), (pe)) != 0 && diff < 0 != pe < 0)) {
q = (q - 1);
}
int64_t rhs = FLOW_CHECKED_MOD((q), (p));
if (rhs < 0) {
rhs = (rhs + p);
}
int64_t inv = pow_mod_ll_i64_i64_i64(FLOW_CHECKED_MOD(((2 * r_mod)), (p)), (p - 2), p);
int64_t t = FLOW_CHECKED_MOD((((p - rhs) * inv)), (p));
r_mod = (r_mod + (t * pe));
pe = (pe * p);
r_mod = FLOW_CHECKED_MOD((r_mod), (pe));
k = (k + 1);
}
return r_mod;
}
int32_t roots_mod_pe_i64_i64_i32_ptr_i64(int64_t n0, int64_t p, int32_t e, int64_t* roots) {
int64_t pe = 1;
int32_t __flow_step_7 = 1;
for (int32_t i = 0; (0 <= e) ? i < e : i > e; i += (0 <= e) ? 1 : -1) {
pe = (pe * p);
}
int64_t n = FLOW_CHECKED_MOD((n0), (pe));
if (n < 0) {
n = (n + pe);
}
if (FLOW_CHECKED_MOD((n), (p)) == 0) {
if (n == 0) {
int64_t step = 1;
int32_t __flow_step_8 = 1;
for (int32_t i = 0; (0 <= FLOW_CHECKED_DIV(((e + 1)), (2))) ? i < FLOW_CHECKED_DIV(((e + 1)), (2)) : i > FLOW_CHECKED_DIV(((e + 1)), (2)); i += (0 <= FLOW_CHECKED_DIV(((e + 1)), (2))) ? 1 : -1) {
step = (step * p);
}
int32_t cnt = 0;
int64_t x = 0;
while (x < pe) {
roots[cnt] = x;
cnt = (cnt + 1);
x = (x + step);
}
return cnt;
}
if (e == 1) {
roots[0] = 0;
return 1;
}
return 0;
}
int64_t r = tonelli_shanks2_i64_i64(n, p);
if (r == (-1)) {
return 0;
}
int64_t r2 = r;
if (e > 1) {
r2 = hensel_lift_i64_i64_i32_i64(n, p, e, r);
}
int64_t r2b = (pe - r2);
if (r2b == r2) {
roots[0] = r2;
return 1;
}
roots[0] = r2;
roots[1] = r2b;
return 2;
}
int64_t ext_gcd_i64_i64_ptr_i64_ptr_i64(int64_t a0, int64_t b0, int64_t* x, int64_t* y) {
if (b0 == 0) {
x[0] = 1;
y[0] = 0;
return a0;
}
int64_t* x1 = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* y1 = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t g = ext_gcd_i64_i64_ptr_i64_ptr_i64(b0, FLOW_CHECKED_MOD((a0), (b0)), x1, y1);
x[0] = y1[0];
y[0] = (x1[0] - (FLOW_CHECKED_DIV((a0), (b0)) * y1[0]));
free(((void*)(x1)));
free(((void*)(y1)));
return g;
}
int64_t mod_inv_general_i64_i64(int64_t a0, int64_t m) {
int64_t* x = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* y = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t a = FLOW_CHECKED_MOD((a0), (m));
if (a < 0) {
a = (a + m);
}
ext_gcd_i64_i64_ptr_i64_ptr_i64(a, m, x, y);
int64_t r = FLOW_CHECKED_MOD((x[0]), (m));
if (r < 0) {
r = (r + m);
}
free(((void*)(x)));
free(((void*)(y)));
return r;
}
void crt_i64_i64_i64_i64_ptr_i64_ptr_i64(int64_t a1, int64_t m1, int64_t a2, int64_t m2, int64_t* out_x, int64_t* out_m) {
if (m1 == 1) {
out_x[0] = a2;
out_m[0] = m2;
return;
}
if (m2 == 1) {
out_x[0] = a1;
out_m[0] = m1;
return;
}
int64_t inv = mod_inv_general_i64_i64(FLOW_CHECKED_MOD((m1), (m2)), m2);
int64_t t = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((a2 - a1)), (m2)) + m2)), (m2)) * inv)), (m2));
out_x[0] = (a1 + (m1 * t));
out_m[0] = (m1 * m2);
}
void sieve_spf_i32_ptr_i32(int32_t n, int32_t* spf) {
int32_t __flow_step_9 = 1;
for (int32_t i = 0; (0 <= (n + 1)) ? i < (n + 1) : i > (n + 1); i += (0 <= (n + 1)) ? 1 : -1) {
spf[i] = i;
}
int32_t i = 2;
while ((i * i) <= n) {
if (spf[i] == i) {
int32_t j = (i * i);
while (j <= n) {
if (spf[j] == j) {
spf[j] = i;
}
j = (j + i);
}
}
i = (i + 1);
}
}
int32_t factorize_small_i32_ptr_i32_ptr_i32_ptr_i32(int32_t x0, int32_t* spf, int32_t* primes, int32_t* exps) {
int32_t x = x0;
int32_t cnt = 0;
while (x > 1) {
int32_t p = spf[x];
int32_t e = 0;
while (FLOW_CHECKED_MOD((x), (p)) == 0) {
x = FLOW_CHECKED_DIV((x), (p));
e = (e + 1);
}
primes[cnt] = p;
exps[cnt] = e;
cnt = (cnt + 1);
}
return cnt;
}
int64_t class_number_i64(int64_t D) {
int64_t absD = (-D);
int64_t amax = isqrt_i64(FLOW_CHECKED_DIV((absD), (3)));
int32_t* spf = (int32_t*)(((int32_t*)(calloc(((int64_t)((amax + 1))), 4))));
sieve_spf_i32_ptr_i32(((int32_t)(amax)), spf);
int64_t h = 0;
int64_t a = 1;
while (a <= amax) {
int32_t* fac_p = (int32_t*)(((int32_t*)(calloc(20, 4))));
int32_t* fac_e = (int32_t*)(((int32_t*)(calloc(20, 4))));
int32_t nfac = factorize_small_i32_ptr_i32_ptr_i32_ptr_i32(((int32_t)(a)), spf, fac_p, fac_e);
bool bad = 0;
int32_t __flow_step_10 = 1;
for (int32_t i = 0; (0 <= nfac) ? i < nfac : i > nfac; i += (0 <= nfac) ? 1 : -1) {
if ((fac_e[i] >= 2 && FLOW_CHECKED_MOD((D), (((int64_t)(fac_p[i])))) == 0)) {
bad = 1;
break;
}
}
if ((!(bad))) {
int64_t* roots = (int64_t*)(((int64_t*)(calloc(1024, 8))));
int32_t n_roots = 1;
roots[0] = 0;
int64_t mod = 1;
bool ok = 1;
int32_t __flow_step_11 = 1;
for (int32_t i = 0; (0 <= nfac) ? i < nfac : i > nfac; i += (0 <= nfac) ? 1 : -1) {
int64_t p = ((int64_t)(fac_p[i]));
int32_t e = fac_e[i];
int64_t pe = 1;
int32_t __flow_step_12 = 1;
for (int32_t j = 0; (0 <= e) ? j < e : j > e; j += (0 <= e) ? 1 : -1) {
pe = (pe * p);
}
int64_t* rset = (int64_t*)(((int64_t*)(calloc(8, 8))));
int32_t nr = roots_mod_pe_i64_i64_i32_ptr_i64(D, p, e, rset);
if (nr == 0) {
ok = 0;
free(((void*)(rset)));
break;
}
int64_t* new_roots = (int64_t*)(((int64_t*)(calloc(1024, 8))));
int32_t new_nr = 0;
int32_t __flow_step_13 = 1;
for (int32_t j = 0; (0 <= n_roots) ? j < n_roots : j > n_roots; j += (0 <= n_roots) ? 1 : -1) {
int32_t __flow_step_14 = 1;
for (int32_t k = 0; (0 <= nr) ? k < nr : k > nr; k += (0 <= nr) ? 1 : -1) {
int64_t* x = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* m = (int64_t*)(((int64_t*)(calloc(1, 8))));
crt_i64_i64_i64_i64_ptr_i64_ptr_i64(roots[j], mod, rset[k], pe, x, m);
new_roots[new_nr] = x[0];
new_nr = (new_nr + 1);
free(((void*)(x)));
free(((void*)(m)));
}
}
memcpy(((void*)(roots)), ((void*)(new_roots)), (((int64_t)(new_nr)) * 8));
n_roots = new_nr;
mod = (mod * pe);
free(((void*)(new_roots)));
free(((void*)(rset)));
}
if (ok) {
int32_t __flow_step_15 = 1;
for (int32_t ri = 0; (0 <= n_roots) ? ri < n_roots : ri > n_roots; ri += (0 <= n_roots) ? 1 : -1) {
int64_t r = roots[ri];
int64_t b_signed;
if (r == 0) {
b_signed = a;
} else {
if (FLOW_CHECKED_MOD((r), (2)) == 1) {
b_signed = r;
} else {
b_signed = (r - a);
}
}
int64_t b = ((b_signed < 0) ? ((-b_signed)) : (b_signed));
if (b > a) {
continue;
}
int64_t num = ((b * b) - D);
int64_t den = (4 * a);
if (FLOW_CHECKED_MOD((num), (den)) != 0) {
continue;
}
int64_t c = FLOW_CHECKED_DIV((num), (den));
if (a > c) {
continue;
}
int64_t abs_b = ((b_signed < 0) ? ((-b_signed)) : (b_signed));
if (((abs_b == a || a == c) && b_signed < 0)) {
continue;
}
h = (h + 1);
}
}
free(((void*)(roots)));
}
free(((void*)(fac_p)));
free(((void*)(fac_e)));
a = (a + 2);
}
free(((void*)(spf)));
return h;
}
int32_t main(void) {
int64_t n = (((int64_t)(17526)) * 1000000000);
int64_t N = ((8 * n) + 3);
int64_t* primes = (int64_t*)(((int64_t*)(calloc(20, 8))));
int32_t* exps = (int32_t*)(((int32_t*)(calloc(20, 4))));
int32_t nfac = factorize_ll_i64_ptr_i64_ptr_i32(N, primes, exps);
int64_t n0 = 1;
int64_t f = 1;
int32_t __flow_step_16 = 1;
for (int32_t i = 0; (0 <= nfac) ? i < nfac : i > nfac; i += (0 <= nfac) ? 1 : -1) {
if (FLOW_CHECKED_MOD((exps[i]), (2)) == 1) {
n0 = (n0 * primes[i]);
}
int32_t __flow_step_17 = 1;
for (int32_t j = 0; (0 <= FLOW_CHECKED_DIV((exps[i]), (2))) ? j < FLOW_CHECKED_DIV((exps[i]), (2)) : j > FLOW_CHECKED_DIV((exps[i]), (2)); j += (0 <= FLOW_CHECKED_DIV((exps[i]), (2))) ? 1 : -1) {
f = (f * primes[i]);
}
}
int64_t D = (-n0);
int64_t h = class_number_i64(D);
int64_t w_div2 = 1;
if (D == (-3)) {
w_div2 = 3;
} else {
if (D == (-4)) {
w_div2 = 2;
}
}
int64_t* f_primes = (int64_t*)(((int64_t*)(calloc(20, 8))));
int32_t* f_exps = (int32_t*)(((int32_t*)(calloc(20, 4))));
int32_t nffac = factorize_ll_i64_ptr_i64_ptr_i32(f, f_primes, f_exps);
int64_t S = 0;
int32_t nprimes = nffac;
int32_t __flow_step_18 = 1;
for (int32_t mask = 0; (0 <= FLOW_CHECKED_SHL((1), (nprimes))) ? mask < FLOW_CHECKED_SHL((1), (nprimes)) : mask > FLOW_CHECKED_SHL((1), (nprimes)); mask += (0 <= FLOW_CHECKED_SHL((1), (nprimes))) ? 1 : -1) {
int32_t bits = 0;
int64_t jac = 1;
int64_t sig = 1;
bool valid = 1;
int32_t __flow_step_19 = 1;
for (int32_t i = 0; (0 <= nprimes) ? i < nprimes : i > nprimes; i += (0 <= nprimes) ? 1 : -1) {
int64_t p = f_primes[i];
int32_t e = f_exps[i];
if ((FLOW_CHECKED_SHR((mask), (i)) & 1) == 1) {
bits = (bits + 1);
jac = (jac * ((int64_t)(legendre_i64_i64(D, p))));
e = (e - 1);
}
if (e < 0) {
sig = 0;
valid = 0;
break;
}
int64_t pe = 1;
int32_t __flow_step_20 = 1;
for (int32_t j = 0; (0 <= (e + 1)) ? j < (e + 1) : j > (e + 1); j += (0 <= (e + 1)) ? 1 : -1) {
pe = (pe * p);
}
sig = FLOW_CHECKED_DIV(((sig * (pe - 1))), ((p - 1)));
}
if (((!(valid)) || sig == 0)) {
continue;
}
int64_t sign = ((FLOW_CHECKED_MOD((bits), (2)) == 1) ? ((-1)) : (1));
S = (S + ((sign * jac) * sig));
}
int64_t result = FLOW_CHECKED_DIV((((3 * h) * S)), (w_div2));
printf("%lld\n", result);
free(((void*)(primes)));
free(((void*)(exps)));
free(((void*)(f_primes)));
free(((void*)(f_exps)));
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 @gcd(%arg0: i64, %arg1: i64) -> i64 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%4 = llvm.load %3 : !llvm.ptr -> i64
%5 = arith.constant 0 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi ne, %4, %7 : i64
cf.cond_br %6, ^bb1, ^bb2
^bb1:
%8 = llvm.load %1 : !llvm.ptr -> i64
%9 = llvm.load %3 : !llvm.ptr -> i64
%10 = arith.remsi %8, %9 : i64
%11 = llvm.load %3 : !llvm.ptr -> i64
llvm.store %11, %1 : i64, !llvm.ptr
llvm.store %10, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%12 = llvm.load %1 : !llvm.ptr -> i64
func.return %12 : i64
}
func.func @lcm(%arg0: i64, %arg1: i64) -> i64 {
%13 = arith.constant 0 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.cmpi eq, %arg0, %15 : i64
%16 = scf.if %14 -> (i1) {
%17 = arith.constant true
scf.yield %17 : i1
} else {
%18 = arith.constant 0 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.cmpi eq, %arg1, %20 : i64
scf.yield %19 : i1
}
cf.cond_br %16, ^bb3, ^bb4
^bb3:
%21 = arith.constant 0 : i32
%22 = arith.extsi %21 : i32 to i64
func.return %22 : i64
^bb4:
cf.br ^bb5
^bb5:
%23 = func.call @gcd(%arg0, %arg1) : (i64, i64) -> i64
%24 = arith.divsi %arg0, %23 : i64
%25 = arith.muli %24, %arg1 : i64
func.return %25 : i64
}
func.func @isqrt(%arg0: i64) -> i64 {
%26 = arith.constant 2 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.cmpi slt, %arg0, %28 : i64
cf.cond_br %27, ^bb6, ^bb7
^bb6:
func.return %arg0 : i64
^bb7:
cf.br ^bb8
^bb8:
%29 = llvm.mlir.constant(1 : i64) : i64
%30 = llvm.alloca %29 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %30 : i64, !llvm.ptr
%31 = llvm.load %30 : !llvm.ptr -> i64
%32 = arith.constant 1 : i32
%34 = arith.extsi %32 : i32 to i64
%33 = arith.addi %31, %34 : i64
%35 = arith.constant 2 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.divsi %33, %37 : i64
%38 = llvm.mlir.constant(1 : i64) : i64
%39 = llvm.alloca %38 x i64 : (i64) -> !llvm.ptr
llvm.store %36, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%40 = llvm.load %39 : !llvm.ptr -> i64
%41 = llvm.load %30 : !llvm.ptr -> i64
%42 = arith.cmpi slt, %40, %41 : i64
cf.cond_br %42, ^bb10, ^bb11
^bb10:
%43 = llvm.load %39 : !llvm.ptr -> i64
llvm.store %43, %30 : i64, !llvm.ptr
%44 = llvm.load %30 : !llvm.ptr -> i64
%45 = llvm.load %30 : !llvm.ptr -> i64
%46 = arith.divsi %arg0, %45 : i64
%47 = arith.addi %44, %46 : i64
%48 = arith.constant 2 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.divsi %47, %50 : i64
llvm.store %49, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%51 = llvm.load %30 : !llvm.ptr -> i64
func.return %51 : i64
}
func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%52 = arith.remsi %arg0, %arg2 : i64
%53 = llvm.mlir.constant(1 : i64) : i64
%54 = llvm.alloca %53 x i64 : (i64) -> !llvm.ptr
llvm.store %52, %54 : i64, !llvm.ptr
%55 = arith.remsi %arg1, %arg2 : i64
%56 = llvm.mlir.constant(1 : i64) : i64
%57 = llvm.alloca %56 x i64 : (i64) -> !llvm.ptr
llvm.store %55, %57 : i64, !llvm.ptr
%58 = arith.constant 0 : i32
%59 = arith.extsi %58 : i32 to i64
%60 = llvm.mlir.constant(1 : i64) : i64
%61 = llvm.alloca %60 x i64 : (i64) -> !llvm.ptr
llvm.store %59, %61 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%62 = llvm.load %57 : !llvm.ptr -> i64
%63 = arith.constant 0 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.cmpi sgt, %62, %65 : i64
cf.cond_br %64, ^bb13, ^bb14
^bb13:
%66 = llvm.load %57 : !llvm.ptr -> i64
%67 = arith.constant 2 : i32
%69 = arith.extsi %67 : i32 to i64
%68 = arith.remsi %66, %69 : i64
%70 = arith.constant 1 : i32
%72 = arith.extsi %70 : i32 to i64
%71 = arith.cmpi eq, %68, %72 : i64
cf.cond_br %71, ^bb15, ^bb16
^bb15:
%73 = llvm.load %61 : !llvm.ptr -> i64
%74 = llvm.load %54 : !llvm.ptr -> i64
%75 = arith.addi %73, %74 : i64
%76 = arith.remsi %75, %arg2 : i64
llvm.store %76, %61 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%77 = llvm.load %54 : !llvm.ptr -> i64
%78 = arith.constant 2 : i32
%80 = arith.extsi %78 : i32 to i64
%79 = arith.muli %77, %80 : i64
%81 = arith.remsi %79, %arg2 : i64
llvm.store %81, %54 : i64, !llvm.ptr
%82 = llvm.load %57 : !llvm.ptr -> i64
%83 = arith.constant 2 : i32
%85 = arith.extsi %83 : i32 to i64
%84 = arith.divsi %82, %85 : i64
llvm.store %84, %57 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%86 = llvm.load %61 : !llvm.ptr -> i64
func.return %86 : i64
}
func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%87 = arith.constant 1 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.cmpi eq, %arg2, %89 : i64
cf.cond_br %88, ^bb18, ^bb19
^bb18:
%90 = arith.constant 0 : i32
%91 = arith.extsi %90 : i32 to i64
func.return %91 : i64
^bb19:
cf.br ^bb20
^bb20:
%92 = arith.constant 1 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i64, !llvm.ptr
%96 = arith.remsi %arg0, %arg2 : i64
%97 = llvm.mlir.constant(1 : i64) : i64
%98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
llvm.store %96, %98 : i64, !llvm.ptr
%99 = llvm.mlir.constant(1 : i64) : i64
%100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%101 = llvm.load %100 : !llvm.ptr -> i64
%102 = arith.constant 0 : i32
%104 = arith.extsi %102 : i32 to i64
%103 = arith.cmpi sgt, %101, %104 : i64
cf.cond_br %103, ^bb22, ^bb23
^bb22:
%105 = llvm.load %100 : !llvm.ptr -> i64
%106 = arith.constant 2 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.remsi %105, %108 : i64
%109 = arith.constant 1 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.cmpi eq, %107, %111 : i64
cf.cond_br %110, ^bb24, ^bb25
^bb24:
%113 = llvm.load %95 : !llvm.ptr -> i64
%114 = llvm.load %98 : !llvm.ptr -> i64
%112 = func.call @mulmod(%113, %114, %arg2) : (i64, i64, i64) -> i64
llvm.store %112, %95 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%116 = llvm.load %98 : !llvm.ptr -> i64
%117 = llvm.load %98 : !llvm.ptr -> i64
%115 = func.call @mulmod(%116, %117, %arg2) : (i64, i64, i64) -> i64
llvm.store %115, %98 : i64, !llvm.ptr
%118 = llvm.load %100 : !llvm.ptr -> i64
%119 = arith.constant 2 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.divsi %118, %121 : i64
llvm.store %120, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%122 = llvm.load %95 : !llvm.ptr -> i64
func.return %122 : i64
}
func.func @is_prime(%arg0: i64) -> i1 {
%123 = arith.constant 2 : i32
%125 = arith.extsi %123 : i32 to i64
%124 = arith.cmpi slt, %arg0, %125 : i64
cf.cond_br %124, ^bb27, ^bb28
^bb27:
%126 = arith.constant 0 : i1
func.return %126 : i1
^bb28:
cf.br ^bb29
^bb29:
%127 = arith.constant 4 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.cmpi slt, %arg0, %129 : i64
cf.cond_br %128, ^bb30, ^bb31
^bb30:
%130 = arith.constant 1 : i1
func.return %130 : i1
^bb31:
cf.br ^bb32
^bb32:
%131 = arith.constant 2 : i32
%133 = arith.extsi %131 : i32 to i64
%132 = arith.remsi %arg0, %133 : i64
%134 = arith.constant 0 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.cmpi eq, %132, %136 : i64
%137 = scf.if %135 -> (i1) {
%138 = arith.constant true
scf.yield %138 : i1
} else {
%139 = arith.constant 3 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.remsi %arg0, %141 : i64
%142 = arith.constant 0 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.cmpi eq, %140, %144 : i64
scf.yield %143 : i1
}
cf.cond_br %137, ^bb33, ^bb34
^bb33:
%145 = arith.constant 0 : i1
func.return %145 : i1
^bb34:
cf.br ^bb35
^bb35:
%146 = arith.constant 5 : i32
%147 = arith.extsi %146 : i32 to i64
%148 = llvm.mlir.constant(1 : i64) : i64
%149 = llvm.alloca %148 x i64 : (i64) -> !llvm.ptr
llvm.store %147, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.load %149 : !llvm.ptr -> i64
%152 = arith.muli %150, %151 : i64
%153 = arith.cmpi sle, %152, %arg0 : i64
cf.cond_br %153, ^bb37, ^bb38
^bb37:
%154 = llvm.load %149 : !llvm.ptr -> i64
%155 = arith.remsi %arg0, %154 : i64
%156 = arith.constant 0 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.cmpi eq, %155, %158 : i64
%159 = scf.if %157 -> (i1) {
%160 = arith.constant true
scf.yield %160 : i1
} else {
%161 = llvm.load %149 : !llvm.ptr -> i64
%162 = arith.constant 2 : i32
%164 = arith.extsi %162 : i32 to i64
%163 = arith.addi %161, %164 : i64
%165 = arith.remsi %arg0, %163 : i64
%166 = arith.constant 0 : i32
%168 = arith.extsi %166 : i32 to i64
%167 = arith.cmpi eq, %165, %168 : i64
scf.yield %167 : i1
}
cf.cond_br %159, ^bb39, ^bb40
^bb39:
%169 = arith.constant 0 : i1
func.return %169 : i1
^bb40:
cf.br ^bb41
^bb41:
%170 = llvm.load %149 : !llvm.ptr -> i64
%171 = arith.constant 6 : i32
%173 = arith.extsi %171 : i32 to i64
%172 = arith.addi %170, %173 : i64
llvm.store %172, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%174 = arith.constant 1 : i1
func.return %174 : i1
}
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @memcpy(!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
func.func @mul_mod_ll(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%175 = arith.extsi %arg0 : i64 to i128
%176 = arith.extsi %arg1 : i64 to i128
%178 = arith.trunci %175 : i128 to i64
%179 = arith.trunci %176 : i128 to i64
%177 = arith.muli %178, %179 : i64
%180 = arith.extsi %arg2 : i64 to i128
%182 = arith.trunci %180 : i128 to i64
%181 = arith.remsi %177, %182 : i64
func.return %181 : i64
}
func.func @pow_mod_ll(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%183 = arith.constant 1 : i32
%184 = arith.extsi %183 : i32 to i64
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x i64 : (i64) -> !llvm.ptr
llvm.store %184, %186 : i64, !llvm.ptr
%187 = arith.remsi %arg0, %arg2 : i64
%188 = llvm.mlir.constant(1 : i64) : i64
%189 = llvm.alloca %188 x i64 : (i64) -> !llvm.ptr
llvm.store %187, %189 : i64, !llvm.ptr
%190 = llvm.mlir.constant(1 : i64) : i64
%191 = llvm.alloca %190 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %191 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%192 = llvm.load %191 : !llvm.ptr -> i64
%193 = arith.constant 0 : i32
%195 = arith.extsi %193 : i32 to i64
%194 = arith.cmpi sgt, %192, %195 : i64
cf.cond_br %194, ^bb43, ^bb44
^bb43:
%196 = llvm.load %191 : !llvm.ptr -> i64
%197 = arith.constant 2 : i32
%199 = arith.extsi %197 : i32 to i64
%198 = arith.remsi %196, %199 : i64
%200 = arith.constant 1 : i32
%202 = arith.extsi %200 : i32 to i64
%201 = arith.cmpi eq, %198, %202 : i64
cf.cond_br %201, ^bb45, ^bb46
^bb45:
%204 = llvm.load %186 : !llvm.ptr -> i64
%205 = llvm.load %189 : !llvm.ptr -> i64
%203 = func.call @mul_mod_ll(%204, %205, %arg2) : (i64, i64, i64) -> i64
llvm.store %203, %186 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%207 = llvm.load %189 : !llvm.ptr -> i64
%208 = llvm.load %189 : !llvm.ptr -> i64
%206 = func.call @mul_mod_ll(%207, %208, %arg2) : (i64, i64, i64) -> i64
llvm.store %206, %189 : i64, !llvm.ptr
%209 = llvm.load %191 : !llvm.ptr -> i64
%210 = arith.constant 2 : i32
%212 = arith.extsi %210 : i32 to i64
%211 = arith.divsi %209, %212 : i64
llvm.store %211, %191 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%213 = llvm.load %186 : !llvm.ptr -> i64
func.return %213 : i64
}
func.func @is_prime_ll(%arg0: i64) -> i1 {
%214 = arith.constant 2 : i32
%216 = arith.extsi %214 : i32 to i64
%215 = arith.cmpi slt, %arg0, %216 : i64
cf.cond_br %215, ^bb48, ^bb49
^bb48:
%217 = arith.constant 0 : i1
func.return %217 : i1
^bb49:
cf.br ^bb50
^bb50:
%219 = arith.constant 2 : i32
%220 = arith.constant 3 : i32
%221 = arith.constant 5 : i32
%222 = arith.constant 7 : i32
%223 = arith.constant 11 : i32
%224 = arith.constant 13 : i32
%225 = arith.constant 17 : i32
%226 = arith.constant 19 : i32
%227 = arith.constant 23 : i32
%228 = arith.constant 29 : i32
%229 = arith.constant 37 : i32
%230 = llvm.mlir.constant(1 : i64) : i64
%231 = llvm.alloca %230 x !llvm.array<11 x i64> : (i64) -> !llvm.ptr
%232 = llvm.mlir.zero : !llvm.array<11 x i64>
llvm.store %232, %231 : !llvm.array<11 x i64>, !llvm.ptr
%233 = arith.extsi %219 : i32 to i64
%234 = arith.extsi %220 : i32 to i64
%235 = arith.extsi %221 : i32 to i64
%236 = arith.extsi %222 : i32 to i64
%237 = arith.extsi %223 : i32 to i64
%238 = arith.extsi %224 : i32 to i64
%239 = arith.extsi %225 : i32 to i64
%240 = arith.extsi %226 : i32 to i64
%241 = arith.extsi %227 : i32 to i64
%242 = arith.extsi %228 : i32 to i64
%243 = arith.extsi %229 : i32 to i64
%244 = llvm.mlir.constant(0 : i64) : i64
%245 = llvm.getelementptr %231[0, %244] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %233, %245 : i64, !llvm.ptr
%246 = llvm.mlir.constant(1 : i64) : i64
%247 = llvm.getelementptr %231[0, %246] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %234, %247 : i64, !llvm.ptr
%248 = llvm.mlir.constant(2 : i64) : i64
%249 = llvm.getelementptr %231[0, %248] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %235, %249 : i64, !llvm.ptr
%250 = llvm.mlir.constant(3 : i64) : i64
%251 = llvm.getelementptr %231[0, %250] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %236, %251 : i64, !llvm.ptr
%252 = llvm.mlir.constant(4 : i64) : i64
%253 = llvm.getelementptr %231[0, %252] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %237, %253 : i64, !llvm.ptr
%254 = llvm.mlir.constant(5 : i64) : i64
%255 = llvm.getelementptr %231[0, %254] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %238, %255 : i64, !llvm.ptr
%256 = llvm.mlir.constant(6 : i64) : i64
%257 = llvm.getelementptr %231[0, %256] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %239, %257 : i64, !llvm.ptr
%258 = llvm.mlir.constant(7 : i64) : i64
%259 = llvm.getelementptr %231[0, %258] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %240, %259 : i64, !llvm.ptr
%260 = llvm.mlir.constant(8 : i64) : i64
%261 = llvm.getelementptr %231[0, %260] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %241, %261 : i64, !llvm.ptr
%262 = llvm.mlir.constant(9 : i64) : i64
%263 = llvm.getelementptr %231[0, %262] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %242, %263 : i64, !llvm.ptr
%264 = llvm.mlir.constant(10 : i64) : i64
%265 = llvm.getelementptr %231[0, %264] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
llvm.store %243, %265 : i64, !llvm.ptr
%266 = arith.constant 0 : i32
%267 = arith.constant 11 : i32
%268 = arith.index_cast %266 : i32 to index
%269 = arith.index_cast %267 : i32 to index
%271 = arith.constant 1 : index
%272 = arith.constant -1 : index
%273 = arith.cmpi sle, %268, %269 : index
%270 = arith.select %273, %271, %272 : index
cf.br ^bb51(%268 : index)
^bb51(%274: index):
%275 = arith.cmpi slt, %274, %269 : index
%276 = arith.cmpi sgt, %274, %269 : index
%277 = arith.select %273, %275, %276 : i1
cf.cond_br %277, ^bb52(%274 : index), ^bb53(%274 : index)
^bb52(%278: index):
%280 = arith.index_cast %278 : index to i64
%281 = llvm.getelementptr %231[0, %280] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
%279 = llvm.load %281 : !llvm.ptr -> i64
%282 = arith.cmpi eq, %arg0, %279 : i64
cf.cond_br %282, ^bb54, ^bb55
^bb54:
%283 = arith.constant 1 : i1
func.return %283 : i1
^bb55:
cf.br ^bb56
^bb56:
%285 = arith.index_cast %278 : index to i64
%286 = llvm.getelementptr %231[0, %285] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<11 x i64>
%284 = llvm.load %286 : !llvm.ptr -> i64
%287 = arith.remsi %arg0, %284 : i64
%288 = arith.constant 0 : i32
%290 = arith.extsi %288 : i32 to i64
%289 = arith.cmpi eq, %287, %290 : i64
cf.cond_br %289, ^bb57, ^bb58
^bb57:
%291 = arith.constant 0 : i1
func.return %291 : i1
^bb58:
cf.br ^bb59
^bb59:
%292 = arith.addi %278, %270 : index
cf.br ^bb51(%292 : index)
^bb53(%293: index):
%294 = arith.constant 1 : i32
%296 = arith.extsi %294 : i32 to i64
%295 = arith.subi %arg0, %296 : i64
%297 = llvm.mlir.constant(1 : i64) : i64
%298 = llvm.alloca %297 x i64 : (i64) -> !llvm.ptr
llvm.store %295, %298 : i64, !llvm.ptr
%299 = arith.constant 0 : i32
%300 = llvm.mlir.constant(1 : i64) : i64
%301 = llvm.alloca %300 x i32 : (i64) -> !llvm.ptr
llvm.store %299, %301 : i32, !llvm.ptr
cf.br ^bb60
^bb60:
%302 = llvm.load %298 : !llvm.ptr -> i64
%303 = arith.constant 2 : i32
%305 = arith.extsi %303 : i32 to i64
%304 = arith.remsi %302, %305 : i64
%306 = arith.constant 0 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.cmpi eq, %304, %308 : i64
cf.cond_br %307, ^bb61, ^bb62
^bb61:
%309 = llvm.load %298 : !llvm.ptr -> i64
%310 = arith.constant 2 : i32
%312 = arith.extsi %310 : i32 to i64
%311 = arith.divsi %309, %312 : i64
llvm.store %311, %298 : i64, !llvm.ptr
%313 = llvm.load %301 : !llvm.ptr -> i32
%314 = arith.constant 1 : i32
%315 = arith.addi %313, %314 : i32
llvm.store %315, %301 : i32, !llvm.ptr
cf.br ^bb60
^bb62:
%317 = arith.constant 2 : i32
%318 = arith.constant 3 : i32
%319 = arith.constant 5 : i32
%320 = arith.constant 7 : i32
%321 = arith.constant 11 : i32
%322 = arith.constant 13 : i32
%323 = arith.constant 17 : i32
%324 = llvm.mlir.constant(1 : i64) : i64
%325 = llvm.alloca %324 x !llvm.array<7 x i64> : (i64) -> !llvm.ptr
%326 = llvm.mlir.zero : !llvm.array<7 x i64>
llvm.store %326, %325 : !llvm.array<7 x i64>, !llvm.ptr
%327 = arith.extsi %317 : i32 to i64
%328 = arith.extsi %318 : i32 to i64
%329 = arith.extsi %319 : i32 to i64
%330 = arith.extsi %320 : i32 to i64
%331 = arith.extsi %321 : i32 to i64
%332 = arith.extsi %322 : i32 to i64
%333 = arith.extsi %323 : i32 to i64
%334 = llvm.mlir.constant(0 : i64) : i64
%335 = llvm.getelementptr %325[0, %334] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %327, %335 : i64, !llvm.ptr
%336 = llvm.mlir.constant(1 : i64) : i64
%337 = llvm.getelementptr %325[0, %336] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %328, %337 : i64, !llvm.ptr
%338 = llvm.mlir.constant(2 : i64) : i64
%339 = llvm.getelementptr %325[0, %338] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %329, %339 : i64, !llvm.ptr
%340 = llvm.mlir.constant(3 : i64) : i64
%341 = llvm.getelementptr %325[0, %340] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %330, %341 : i64, !llvm.ptr
%342 = llvm.mlir.constant(4 : i64) : i64
%343 = llvm.getelementptr %325[0, %342] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %331, %343 : i64, !llvm.ptr
%344 = llvm.mlir.constant(5 : i64) : i64
%345 = llvm.getelementptr %325[0, %344] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %332, %345 : i64, !llvm.ptr
%346 = llvm.mlir.constant(6 : i64) : i64
%347 = llvm.getelementptr %325[0, %346] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %333, %347 : i64, !llvm.ptr
%348 = arith.constant 0 : i32
%349 = arith.constant 7 : i32
%350 = arith.index_cast %348 : i32 to index
%351 = arith.index_cast %349 : i32 to index
%353 = arith.constant 1 : index
%354 = arith.constant -1 : index
%355 = arith.cmpi sle, %350, %351 : index
%352 = arith.select %355, %353, %354 : index
cf.br ^bb63(%350 : index)
^bb63(%356: index):
%357 = arith.cmpi slt, %356, %351 : index
%358 = arith.cmpi sgt, %356, %351 : index
%359 = arith.select %355, %357, %358 : i1
cf.cond_br %359, ^bb64(%356 : index), ^bb65(%356 : index)
^bb64(%360: index):
%362 = arith.index_cast %360 : index to i64
%363 = llvm.getelementptr %325[0, %362] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
%361 = llvm.load %363 : !llvm.ptr -> i64
%364 = arith.remsi %361, %arg0 : i64
%365 = arith.constant 0 : i32
%367 = arith.extsi %365 : i32 to i64
%366 = arith.cmpi eq, %364, %367 : i64
cf.cond_br %366, ^bb66, ^bb67
^bb66:
%368 = arith.addi %360, %352 : index
cf.br ^bb63(%368 : index)
^bb67:
cf.br ^bb68
^bb68:
%370 = llvm.load %298 : !llvm.ptr -> i64
%369 = func.call @pow_mod_ll(%361, %370, %arg0) : (i64, i64, i64) -> i64
%371 = llvm.mlir.constant(1 : i64) : i64
%372 = llvm.alloca %371 x i64 : (i64) -> !llvm.ptr
llvm.store %369, %372 : i64, !llvm.ptr
%373 = llvm.load %372 : !llvm.ptr -> i64
%374 = arith.constant 1 : i32
%376 = arith.extsi %374 : i32 to i64
%375 = arith.cmpi eq, %373, %376 : i64
%377 = scf.if %375 -> (i1) {
%378 = arith.constant true
scf.yield %378 : i1
} else {
%379 = llvm.load %372 : !llvm.ptr -> i64
%380 = arith.constant 1 : i32
%382 = arith.extsi %380 : i32 to i64
%381 = arith.subi %arg0, %382 : i64
%383 = arith.cmpi eq, %379, %381 : i64
scf.yield %383 : i1
}
cf.cond_br %377, ^bb69, ^bb70
^bb69:
%384 = arith.addi %360, %352 : index
cf.br ^bb63(%384 : index)
^bb70:
cf.br ^bb71
^bb71:
%385 = arith.constant 0 : i1
%386 = llvm.mlir.constant(1 : i64) : i64
%387 = llvm.alloca %386 x i1 : (i64) -> !llvm.ptr
llvm.store %385, %387 : i1, !llvm.ptr
%388 = arith.constant 0 : i32
%389 = llvm.load %301 : !llvm.ptr -> i32
%390 = arith.constant 1 : i32
%391 = arith.subi %389, %390 : i32
%392 = arith.index_cast %388 : i32 to index
%393 = arith.index_cast %391 : i32 to index
%395 = arith.constant 1 : index
%396 = arith.constant -1 : index
%397 = arith.cmpi sle, %392, %393 : index
%394 = arith.select %397, %395, %396 : index
cf.br ^bb72(%392 : index)
^bb72(%398: index):
%399 = arith.cmpi slt, %398, %393 : index
%400 = arith.cmpi sgt, %398, %393 : index
%401 = arith.select %397, %399, %400 : i1
cf.cond_br %401, ^bb73(%398 : index), ^bb74(%398 : index)
^bb73(%402: index):
%404 = llvm.load %372 : !llvm.ptr -> i64
%405 = llvm.load %372 : !llvm.ptr -> i64
%403 = func.call @mul_mod_ll(%404, %405, %arg0) : (i64, i64, i64) -> i64
llvm.store %403, %372 : i64, !llvm.ptr
%406 = llvm.load %372 : !llvm.ptr -> i64
%407 = arith.constant 1 : i32
%409 = arith.extsi %407 : i32 to i64
%408 = arith.subi %arg0, %409 : i64
%410 = arith.cmpi eq, %406, %408 : i64
cf.cond_br %410, ^bb75, ^bb76
^bb75:
%411 = arith.constant 1 : i1
llvm.store %411, %387 : i1, !llvm.ptr
cf.br ^bb74(%402 : index)
^bb76:
cf.br ^bb77
^bb77:
%412 = arith.addi %402, %394 : index
cf.br ^bb72(%412 : index)
^bb74(%413: index):
%414 = llvm.load %387 : !llvm.ptr -> i1
%416 = arith.constant 1 : i1
%415 = arith.xori %414, %416 : i1
cf.cond_br %415, ^bb78, ^bb79
^bb78:
%418 = arith.constant 0 : i1
func.return %418 : i1
^bb79:
cf.br ^bb80
^bb80:
%419 = arith.addi %360, %352 : index
cf.br ^bb63(%419 : index)
^bb65(%420: index):
%421 = arith.constant 1 : i1
func.return %421 : i1
}
func.func @pollard_rho(%arg0: i64) -> i64 {
%422 = arith.constant 2 : i32
%424 = arith.extsi %422 : i32 to i64
%423 = arith.remsi %arg0, %424 : i64
%425 = arith.constant 0 : i32
%427 = arith.extsi %425 : i32 to i64
%426 = arith.cmpi eq, %423, %427 : i64
cf.cond_br %426, ^bb81, ^bb82
^bb81:
%428 = arith.constant 2 : i32
%429 = arith.extsi %428 : i32 to i64
func.return %429 : i64
^bb82:
cf.br ^bb83
^bb83:
%430 = arith.constant 3 : i32
%432 = arith.extsi %430 : i32 to i64
%431 = arith.remsi %arg0, %432 : i64
%433 = arith.constant 0 : i32
%435 = arith.extsi %433 : i32 to i64
%434 = arith.cmpi eq, %431, %435 : i64
cf.cond_br %434, ^bb84, ^bb85
^bb84:
%436 = arith.constant 3 : i32
%437 = arith.extsi %436 : i32 to i64
func.return %437 : i64
^bb85:
cf.br ^bb86
^bb86:
%438 = func.call @is_prime_ll(%arg0) : (i64) -> i1
cf.cond_br %438, ^bb87, ^bb88
^bb87:
func.return %arg0 : i64
^bb88:
cf.br ^bb89
^bb89:
%439 = arith.constant 1 : i32
%440 = arith.extsi %439 : i32 to i64
%441 = llvm.mlir.constant(1 : i64) : i64
%442 = llvm.alloca %441 x i64 : (i64) -> !llvm.ptr
llvm.store %440, %442 : i64, !llvm.ptr
%443 = arith.constant 2 : i32
%444 = arith.extsi %443 : i32 to i64
%445 = llvm.mlir.constant(1 : i64) : i64
%446 = llvm.alloca %445 x i64 : (i64) -> !llvm.ptr
llvm.store %444, %446 : i64, !llvm.ptr
%447 = arith.constant 2 : i32
%448 = arith.extsi %447 : i32 to i64
%449 = llvm.mlir.constant(1 : i64) : i64
%450 = llvm.alloca %449 x i64 : (i64) -> !llvm.ptr
llvm.store %448, %450 : i64, !llvm.ptr
%451 = arith.constant 1 : i32
%452 = arith.extsi %451 : i32 to i64
%453 = llvm.mlir.constant(1 : i64) : i64
%454 = llvm.alloca %453 x i64 : (i64) -> !llvm.ptr
llvm.store %452, %454 : i64, !llvm.ptr
cf.br ^bb90
^bb90:
%455 = llvm.load %454 : !llvm.ptr -> i64
%456 = arith.constant 1 : i32
%458 = arith.extsi %456 : i32 to i64
%457 = arith.cmpi eq, %455, %458 : i64
cf.cond_br %457, ^bb91, ^bb92
^bb91:
%460 = llvm.load %446 : !llvm.ptr -> i64
%461 = llvm.load %446 : !llvm.ptr -> i64
%459 = func.call @mul_mod_ll(%460, %461, %arg0) : (i64, i64, i64) -> i64
%462 = llvm.load %442 : !llvm.ptr -> i64
%463 = arith.addi %459, %462 : i64
%464 = arith.remsi %463, %arg0 : i64
llvm.store %464, %446 : i64, !llvm.ptr
%466 = llvm.load %450 : !llvm.ptr -> i64
%467 = llvm.load %450 : !llvm.ptr -> i64
%465 = func.call @mul_mod_ll(%466, %467, %arg0) : (i64, i64, i64) -> i64
%468 = llvm.load %442 : !llvm.ptr -> i64
%469 = arith.addi %465, %468 : i64
%470 = arith.remsi %469, %arg0 : i64
llvm.store %470, %450 : i64, !llvm.ptr
%472 = llvm.load %450 : !llvm.ptr -> i64
%473 = llvm.load %450 : !llvm.ptr -> i64
%471 = func.call @mul_mod_ll(%472, %473, %arg0) : (i64, i64, i64) -> i64
%474 = llvm.load %442 : !llvm.ptr -> i64
%475 = arith.addi %471, %474 : i64
%476 = arith.remsi %475, %arg0 : i64
llvm.store %476, %450 : i64, !llvm.ptr
%477 = llvm.load %446 : !llvm.ptr -> i64
%478 = llvm.load %450 : !llvm.ptr -> i64
%479 = arith.cmpi sgt, %477, %478 : i64
%480 = scf.if %479 -> (i64) {
%481 = llvm.load %446 : !llvm.ptr -> i64
%482 = llvm.load %450 : !llvm.ptr -> i64
%483 = arith.subi %481, %482 : i64
scf.yield %483 : i64
} else {
%484 = llvm.load %450 : !llvm.ptr -> i64
%485 = llvm.load %446 : !llvm.ptr -> i64
%486 = arith.subi %484, %485 : i64
scf.yield %486 : i64
}
%487 = func.call @gcd(%480, %arg0) : (i64, i64) -> i64
llvm.store %487, %454 : i64, !llvm.ptr
cf.br ^bb90
^bb92:
%488 = llvm.load %454 : !llvm.ptr -> i64
%489 = arith.cmpi eq, %488, %arg0 : i64
cf.cond_br %489, ^bb93, ^bb94
^bb93:
%490 = arith.constant 2 : i32
%491 = arith.extsi %490 : i32 to i64
llvm.store %491, %442 : i64, !llvm.ptr
cf.br ^bb96
^bb96:
%492 = llvm.load %442 : !llvm.ptr -> i64
%493 = arith.constant 100 : i32
%495 = arith.extsi %493 : i32 to i64
%494 = arith.cmpi slt, %492, %495 : i64
cf.cond_br %494, ^bb97, ^bb98
^bb97:
%496 = arith.constant 2 : i32
%497 = arith.extsi %496 : i32 to i64
llvm.store %497, %446 : i64, !llvm.ptr
%498 = arith.constant 2 : i32
%499 = arith.extsi %498 : i32 to i64
llvm.store %499, %450 : i64, !llvm.ptr
%500 = arith.constant 1 : i32
%501 = arith.extsi %500 : i32 to i64
llvm.store %501, %454 : i64, !llvm.ptr
cf.br ^bb99
^bb99:
%502 = llvm.load %454 : !llvm.ptr -> i64
%503 = arith.constant 1 : i32
%505 = arith.extsi %503 : i32 to i64
%504 = arith.cmpi eq, %502, %505 : i64
cf.cond_br %504, ^bb100, ^bb101
^bb100:
%507 = llvm.load %446 : !llvm.ptr -> i64
%508 = llvm.load %446 : !llvm.ptr -> i64
%506 = func.call @mul_mod_ll(%507, %508, %arg0) : (i64, i64, i64) -> i64
%509 = llvm.load %442 : !llvm.ptr -> i64
%510 = arith.addi %506, %509 : i64
%511 = arith.remsi %510, %arg0 : i64
llvm.store %511, %446 : i64, !llvm.ptr
%513 = llvm.load %450 : !llvm.ptr -> i64
%514 = llvm.load %450 : !llvm.ptr -> i64
%512 = func.call @mul_mod_ll(%513, %514, %arg0) : (i64, i64, i64) -> i64
%515 = llvm.load %442 : !llvm.ptr -> i64
%516 = arith.addi %512, %515 : i64
%517 = arith.remsi %516, %arg0 : i64
llvm.store %517, %450 : i64, !llvm.ptr
%519 = llvm.load %450 : !llvm.ptr -> i64
%520 = llvm.load %450 : !llvm.ptr -> i64
%518 = func.call @mul_mod_ll(%519, %520, %arg0) : (i64, i64, i64) -> i64
%521 = llvm.load %442 : !llvm.ptr -> i64
%522 = arith.addi %518, %521 : i64
%523 = arith.remsi %522, %arg0 : i64
llvm.store %523, %450 : i64, !llvm.ptr
%524 = llvm.load %446 : !llvm.ptr -> i64
%525 = llvm.load %450 : !llvm.ptr -> i64
%526 = arith.cmpi sgt, %524, %525 : i64
%527 = scf.if %526 -> (i64) {
%528 = llvm.load %446 : !llvm.ptr -> i64
%529 = llvm.load %450 : !llvm.ptr -> i64
%530 = arith.subi %528, %529 : i64
scf.yield %530 : i64
} else {
%531 = llvm.load %450 : !llvm.ptr -> i64
%532 = llvm.load %446 : !llvm.ptr -> i64
%533 = arith.subi %531, %532 : i64
scf.yield %533 : i64
}
%534 = func.call @gcd(%527, %arg0) : (i64, i64) -> i64
llvm.store %534, %454 : i64, !llvm.ptr
cf.br ^bb99
^bb101:
%535 = llvm.load %454 : !llvm.ptr -> i64
%536 = arith.cmpi ne, %535, %arg0 : i64
cf.cond_br %536, ^bb102, ^bb103
^bb102:
%537 = llvm.load %454 : !llvm.ptr -> i64
func.return %537 : i64
^bb103:
cf.br ^bb104
^bb104:
%538 = llvm.load %442 : !llvm.ptr -> i64
%539 = arith.constant 1 : i32
%541 = arith.extsi %539 : i32 to i64
%540 = arith.addi %538, %541 : i64
llvm.store %540, %442 : i64, !llvm.ptr
cf.br ^bb96
^bb98:
cf.br ^bb95
^bb94:
cf.br ^bb95
^bb95:
%542 = llvm.load %454 : !llvm.ptr -> i64
func.return %542 : i64
}
func.func @factorize_ll(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> i32 {
%543 = llvm.mlir.constant(1 : i64) : i64
%544 = llvm.alloca %543 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %544 : i64, !llvm.ptr
%545 = arith.constant 0 : i32
%546 = llvm.mlir.constant(1 : i64) : i64
%547 = llvm.alloca %546 x i32 : (i64) -> !llvm.ptr
llvm.store %545, %547 : i32, !llvm.ptr
cf.br ^bb105
^bb105:
%548 = llvm.load %544 : !llvm.ptr -> i64
%549 = arith.constant 1 : i32
%551 = arith.extsi %549 : i32 to i64
%550 = arith.cmpi sgt, %548, %551 : i64
cf.cond_br %550, ^bb106, ^bb107
^bb106:
%553 = llvm.load %544 : !llvm.ptr -> i64
%552 = func.call @is_prime_ll(%553) : (i64) -> i1
cf.cond_br %552, ^bb108, ^bb109
^bb108:
%554 = arith.constant 0 : i1
%555 = llvm.mlir.constant(1 : i64) : i64
%556 = llvm.alloca %555 x i1 : (i64) -> !llvm.ptr
llvm.store %554, %556 : i1, !llvm.ptr
%557 = arith.constant 0 : i32
%558 = llvm.load %547 : !llvm.ptr -> i32
%559 = arith.index_cast %557 : i32 to index
%560 = arith.index_cast %558 : i32 to index
%562 = arith.constant 1 : index
%563 = arith.constant -1 : index
%564 = arith.cmpi sle, %559, %560 : index
%561 = arith.select %564, %562, %563 : index
cf.br ^bb111(%559 : index)
^bb111(%565: index):
%566 = arith.cmpi slt, %565, %560 : index
%567 = arith.cmpi sgt, %565, %560 : index
%568 = arith.select %564, %566, %567 : i1
cf.cond_br %568, ^bb112(%565 : index), ^bb113(%565 : index)
^bb112(%569: index):
%571 = arith.index_cast %569 : index to i64
%572 = llvm.getelementptr %arg1[%571] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%570 = llvm.load %572 : !llvm.ptr -> i64
%573 = llvm.load %544 : !llvm.ptr -> i64
%574 = arith.cmpi eq, %570, %573 : i64
cf.cond_br %574, ^bb114, ^bb115
^bb114:
%576 = arith.index_cast %569 : index to i64
%577 = llvm.getelementptr %arg2[%576] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%575 = llvm.load %577 : !llvm.ptr -> i32
%578 = arith.constant 1 : i32
%579 = arith.addi %575, %578 : i32
%580 = arith.index_cast %569 : index to i64
%581 = llvm.getelementptr %arg2[%580] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %579, %581 : i32, !llvm.ptr
%582 = arith.constant 1 : i1
llvm.store %582, %556 : i1, !llvm.ptr
cf.br ^bb113(%569 : index)
^bb115:
cf.br ^bb116
^bb116:
%583 = arith.addi %569, %561 : index
cf.br ^bb111(%583 : index)
^bb113(%584: index):
%585 = llvm.load %556 : !llvm.ptr -> i1
%587 = arith.constant 1 : i1
%586 = arith.xori %585, %587 : i1
cf.cond_br %586, ^bb117, ^bb118
^bb117:
%589 = llvm.load %544 : !llvm.ptr -> i64
%590 = llvm.load %547 : !llvm.ptr -> i32
%591 = arith.extsi %590 : i32 to i64
%592 = llvm.getelementptr %arg1[%591] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %589, %592 : i64, !llvm.ptr
%593 = arith.constant 1 : i32
%594 = llvm.load %547 : !llvm.ptr -> i32
%595 = arith.extsi %594 : i32 to i64
%596 = llvm.getelementptr %arg2[%595] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %593, %596 : i32, !llvm.ptr
%597 = llvm.load %547 : !llvm.ptr -> i32
%598 = arith.constant 1 : i32
%599 = arith.addi %597, %598 : i32
llvm.store %599, %547 : i32, !llvm.ptr
cf.br ^bb119
^bb118:
cf.br ^bb119
^bb119:
cf.br ^bb107
^bb109:
cf.br ^bb110
^bb110:
%601 = llvm.load %544 : !llvm.ptr -> i64
%600 = func.call @pollard_rho(%601) : (i64) -> i64
%602 = llvm.mlir.constant(1 : i64) : i64
%603 = llvm.alloca %602 x i64 : (i64) -> !llvm.ptr
llvm.store %600, %603 : i64, !llvm.ptr
cf.br ^bb120
^bb120:
%605 = llvm.load %603 : !llvm.ptr -> i64
%604 = func.call @is_prime_ll(%605) : (i64) -> i1
%607 = arith.constant 1 : i1
%606 = arith.xori %604, %607 : i1
cf.cond_br %606, ^bb121, ^bb122
^bb121:
%610 = llvm.load %603 : !llvm.ptr -> i64
%609 = func.call @pollard_rho(%610) : (i64) -> i64
llvm.store %609, %603 : i64, !llvm.ptr
cf.br ^bb120
^bb122:
%611 = arith.constant 0 : i1
%612 = llvm.mlir.constant(1 : i64) : i64
%613 = llvm.alloca %612 x i1 : (i64) -> !llvm.ptr
llvm.store %611, %613 : i1, !llvm.ptr
%614 = arith.constant 0 : i32
%615 = llvm.load %547 : !llvm.ptr -> i32
%616 = arith.index_cast %614 : i32 to index
%617 = arith.index_cast %615 : i32 to index
%619 = arith.constant 1 : index
%620 = arith.constant -1 : index
%621 = arith.cmpi sle, %616, %617 : index
%618 = arith.select %621, %619, %620 : index
cf.br ^bb123(%616 : index)
^bb123(%622: index):
%623 = arith.cmpi slt, %622, %617 : index
%624 = arith.cmpi sgt, %622, %617 : index
%625 = arith.select %621, %623, %624 : i1
cf.cond_br %625, ^bb124(%622 : index), ^bb125(%622 : index)
^bb124(%626: index):
%628 = arith.index_cast %626 : index to i64
%629 = llvm.getelementptr %arg1[%628] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%627 = llvm.load %629 : !llvm.ptr -> i64
%630 = llvm.load %603 : !llvm.ptr -> i64
%631 = arith.cmpi eq, %627, %630 : i64
cf.cond_br %631, ^bb126, ^bb127
^bb126:
%633 = arith.index_cast %626 : index to i64
%634 = llvm.getelementptr %arg2[%633] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%632 = llvm.load %634 : !llvm.ptr -> i32
%635 = arith.constant 1 : i32
%636 = arith.addi %632, %635 : i32
%637 = arith.index_cast %626 : index to i64
%638 = llvm.getelementptr %arg2[%637] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %636, %638 : i32, !llvm.ptr
%639 = arith.constant 1 : i1
llvm.store %639, %613 : i1, !llvm.ptr
cf.br ^bb125(%626 : index)
^bb127:
cf.br ^bb128
^bb128:
%640 = arith.addi %626, %618 : index
cf.br ^bb123(%640 : index)
^bb125(%641: index):
%642 = llvm.load %613 : !llvm.ptr -> i1
%644 = arith.constant 1 : i1
%643 = arith.xori %642, %644 : i1
cf.cond_br %643, ^bb129, ^bb130
^bb129:
%646 = llvm.load %603 : !llvm.ptr -> i64
%647 = llvm.load %547 : !llvm.ptr -> i32
%648 = arith.extsi %647 : i32 to i64
%649 = llvm.getelementptr %arg1[%648] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %646, %649 : i64, !llvm.ptr
%650 = arith.constant 1 : i32
%651 = llvm.load %547 : !llvm.ptr -> i32
%652 = arith.extsi %651 : i32 to i64
%653 = llvm.getelementptr %arg2[%652] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %650, %653 : i32, !llvm.ptr
%654 = llvm.load %547 : !llvm.ptr -> i32
%655 = arith.constant 1 : i32
%656 = arith.addi %654, %655 : i32
llvm.store %656, %547 : i32, !llvm.ptr
cf.br ^bb131
^bb130:
cf.br ^bb131
^bb131:
%657 = llvm.load %544 : !llvm.ptr -> i64
%658 = llvm.load %603 : !llvm.ptr -> i64
%659 = arith.divsi %657, %658 : i64
llvm.store %659, %544 : i64, !llvm.ptr
cf.br ^bb105
^bb107:
%660 = llvm.load %547 : !llvm.ptr -> i32
func.return %660 : i32
}
func.func @legendre(%arg0: i64, %arg1: i64) -> i32 {
%661 = arith.remsi %arg0, %arg1 : i64
%662 = arith.constant 0 : i32
%664 = arith.extsi %662 : i32 to i64
%663 = arith.cmpi slt, %661, %664 : i64
%665 = scf.if %663 -> (i64) {
%666 = arith.addi %661, %arg1 : i64
scf.yield %666 : i64
} else {
scf.yield %661 : i64
}
%667 = arith.constant 0 : i32
%669 = arith.extsi %667 : i32 to i64
%668 = arith.cmpi eq, %665, %669 : i64
cf.cond_br %668, ^bb132, ^bb133
^bb132:
%670 = arith.constant 0 : i32
func.return %670 : i32
^bb133:
cf.br ^bb134
^bb134:
%672 = arith.constant 1 : i32
%674 = arith.extsi %672 : i32 to i64
%673 = arith.subi %arg1, %674 : i64
%675 = arith.constant 2 : i32
%677 = arith.extsi %675 : i32 to i64
%676 = arith.divsi %673, %677 : i64
%671 = func.call @pow_mod_ll(%665, %676, %arg1) : (i64, i64, i64) -> i64
%678 = arith.constant 1 : i32
%680 = arith.extsi %678 : i32 to i64
%679 = arith.subi %arg1, %680 : i64
%681 = arith.cmpi eq, %671, %679 : i64
cf.cond_br %681, ^bb135, ^bb136
^bb135:
%682 = arith.constant 1 : i32
%684 = arith.constant 0 : i32
%683 = arith.subi %684, %682 : i32
func.return %683 : i32
^bb136:
cf.br ^bb137
^bb137:
%685 = arith.constant 1 : i32
func.return %685 : i32
}
func.func @tonelli_shanks2(%arg0: i64, %arg1: i64) -> i64 {
%686 = arith.remsi %arg0, %arg1 : i64
%687 = arith.constant 0 : i32
%689 = arith.extsi %687 : i32 to i64
%688 = arith.cmpi slt, %686, %689 : i64
%690 = scf.if %688 -> (i64) {
%691 = arith.addi %686, %arg1 : i64
scf.yield %691 : i64
} else {
scf.yield %686 : i64
}
%692 = arith.constant 0 : i32
%694 = arith.extsi %692 : i32 to i64
%693 = arith.cmpi eq, %690, %694 : i64
cf.cond_br %693, ^bb138, ^bb139
^bb138:
%695 = arith.constant 0 : i32
%696 = arith.extsi %695 : i32 to i64
func.return %696 : i64
^bb139:
cf.br ^bb140
^bb140:
%697 = func.call @legendre(%690, %arg1) : (i64, i64) -> i32
%698 = arith.constant 1 : i32
%699 = arith.cmpi ne, %697, %698 : i32
cf.cond_br %699, ^bb141, ^bb142
^bb141:
%700 = arith.constant 1 : i32
%702 = arith.constant 0 : i32
%701 = arith.subi %702, %700 : i32
%703 = arith.extsi %701 : i32 to i64
func.return %703 : i64
^bb142:
cf.br ^bb143
^bb143:
%704 = arith.constant 4 : i32
%706 = arith.extsi %704 : i32 to i64
%705 = arith.remsi %arg1, %706 : i64
%707 = arith.constant 3 : i32
%709 = arith.extsi %707 : i32 to i64
%708 = arith.cmpi eq, %705, %709 : i64
cf.cond_br %708, ^bb144, ^bb145
^bb144:
%711 = arith.constant 1 : i32
%713 = arith.extsi %711 : i32 to i64
%712 = arith.addi %arg1, %713 : i64
%714 = arith.constant 4 : i32
%716 = arith.extsi %714 : i32 to i64
%715 = arith.divsi %712, %716 : i64
%710 = func.call @pow_mod_ll(%690, %715, %arg1) : (i64, i64, i64) -> i64
func.return %710 : i64
^bb145:
cf.br ^bb146
^bb146:
%717 = arith.constant 1 : i32
%719 = arith.extsi %717 : i32 to i64
%718 = arith.subi %arg1, %719 : i64
%720 = llvm.mlir.constant(1 : i64) : i64
%721 = llvm.alloca %720 x i64 : (i64) -> !llvm.ptr
llvm.store %718, %721 : i64, !llvm.ptr
%722 = arith.constant 0 : i32
%723 = llvm.mlir.constant(1 : i64) : i64
%724 = llvm.alloca %723 x i32 : (i64) -> !llvm.ptr
llvm.store %722, %724 : i32, !llvm.ptr
cf.br ^bb147
^bb147:
%725 = llvm.load %721 : !llvm.ptr -> i64
%726 = arith.constant 2 : i32
%728 = arith.extsi %726 : i32 to i64
%727 = arith.remsi %725, %728 : i64
%729 = arith.constant 0 : i32
%731 = arith.extsi %729 : i32 to i64
%730 = arith.cmpi eq, %727, %731 : i64
cf.cond_br %730, ^bb148, ^bb149
^bb148:
%732 = llvm.load %721 : !llvm.ptr -> i64
%733 = arith.constant 2 : i32
%735 = arith.extsi %733 : i32 to i64
%734 = arith.divsi %732, %735 : i64
llvm.store %734, %721 : i64, !llvm.ptr
%736 = llvm.load %724 : !llvm.ptr -> i32
%737 = arith.constant 1 : i32
%738 = arith.addi %736, %737 : i32
llvm.store %738, %724 : i32, !llvm.ptr
cf.br ^bb147
^bb149:
%739 = arith.constant 2 : i32
%740 = arith.extsi %739 : i32 to i64
%741 = llvm.mlir.constant(1 : i64) : i64
%742 = llvm.alloca %741 x i64 : (i64) -> !llvm.ptr
llvm.store %740, %742 : i64, !llvm.ptr
cf.br ^bb150
^bb150:
%744 = llvm.load %742 : !llvm.ptr -> i64
%743 = func.call @legendre(%744, %arg1) : (i64, i64) -> i32
%745 = arith.constant 1 : i32
%747 = arith.constant 0 : i32
%746 = arith.subi %747, %745 : i32
%748 = arith.cmpi ne, %743, %746 : i32
cf.cond_br %748, ^bb151, ^bb152
^bb151:
%749 = llvm.load %742 : !llvm.ptr -> i64
%750 = arith.constant 1 : i32
%752 = arith.extsi %750 : i32 to i64
%751 = arith.addi %749, %752 : i64
llvm.store %751, %742 : i64, !llvm.ptr
cf.br ^bb150
^bb152:
%754 = llvm.load %742 : !llvm.ptr -> i64
%755 = llvm.load %721 : !llvm.ptr -> i64
%753 = func.call @pow_mod_ll(%754, %755, %arg1) : (i64, i64, i64) -> i64
%756 = llvm.mlir.constant(1 : i64) : i64
%757 = llvm.alloca %756 x i64 : (i64) -> !llvm.ptr
llvm.store %753, %757 : i64, !llvm.ptr
%759 = llvm.load %721 : !llvm.ptr -> i64
%760 = arith.constant 1 : i32
%762 = arith.extsi %760 : i32 to i64
%761 = arith.addi %759, %762 : i64
%763 = arith.constant 2 : i32
%765 = arith.extsi %763 : i32 to i64
%764 = arith.divsi %761, %765 : i64
%758 = func.call @pow_mod_ll(%690, %764, %arg1) : (i64, i64, i64) -> i64
%766 = llvm.mlir.constant(1 : i64) : i64
%767 = llvm.alloca %766 x i64 : (i64) -> !llvm.ptr
llvm.store %758, %767 : i64, !llvm.ptr
%769 = llvm.load %721 : !llvm.ptr -> i64
%768 = func.call @pow_mod_ll(%690, %769, %arg1) : (i64, i64, i64) -> i64
%770 = llvm.mlir.constant(1 : i64) : i64
%771 = llvm.alloca %770 x i64 : (i64) -> !llvm.ptr
llvm.store %768, %771 : i64, !llvm.ptr
%772 = llvm.load %724 : !llvm.ptr -> i32
%773 = llvm.mlir.constant(1 : i64) : i64
%774 = llvm.alloca %773 x i32 : (i64) -> !llvm.ptr
llvm.store %772, %774 : i32, !llvm.ptr
cf.br ^bb153
^bb153:
%775 = llvm.load %771 : !llvm.ptr -> i64
%776 = arith.constant 1 : i32
%778 = arith.extsi %776 : i32 to i64
%777 = arith.cmpi ne, %775, %778 : i64
cf.cond_br %777, ^bb154, ^bb155
^bb154:
%779 = arith.constant 1 : i32
%780 = llvm.mlir.constant(1 : i64) : i64
%781 = llvm.alloca %780 x i32 : (i64) -> !llvm.ptr
llvm.store %779, %781 : i32, !llvm.ptr
%783 = llvm.load %771 : !llvm.ptr -> i64
%784 = llvm.load %771 : !llvm.ptr -> i64
%782 = func.call @mul_mod_ll(%783, %784, %arg1) : (i64, i64, i64) -> i64
%785 = llvm.mlir.constant(1 : i64) : i64
%786 = llvm.alloca %785 x i64 : (i64) -> !llvm.ptr
llvm.store %782, %786 : i64, !llvm.ptr
cf.br ^bb156
^bb156:
%787 = llvm.load %781 : !llvm.ptr -> i32
%788 = llvm.load %774 : !llvm.ptr -> i32
%789 = arith.cmpi slt, %787, %788 : i32
%790 = scf.if %789 -> (i1) {
%791 = llvm.load %786 : !llvm.ptr -> i64
%792 = arith.constant 1 : i32
%794 = arith.extsi %792 : i32 to i64
%793 = arith.cmpi ne, %791, %794 : i64
scf.yield %793 : i1
} else {
%795 = arith.constant false
scf.yield %795 : i1
}
cf.cond_br %790, ^bb157, ^bb158
^bb157:
%797 = llvm.load %786 : !llvm.ptr -> i64
%798 = llvm.load %786 : !llvm.ptr -> i64
%796 = func.call @mul_mod_ll(%797, %798, %arg1) : (i64, i64, i64) -> i64
llvm.store %796, %786 : i64, !llvm.ptr
%799 = llvm.load %781 : !llvm.ptr -> i32
%800 = arith.constant 1 : i32
%801 = arith.addi %799, %800 : i32
llvm.store %801, %781 : i32, !llvm.ptr
cf.br ^bb156
^bb158:
%803 = llvm.load %757 : !llvm.ptr -> i64
%804 = arith.constant 1 : i32
%805 = arith.extsi %804 : i32 to i64
%806 = llvm.load %774 : !llvm.ptr -> i32
%807 = llvm.load %781 : !llvm.ptr -> i32
%808 = arith.subi %806, %807 : i32
%809 = arith.constant 1 : i32
%810 = arith.subi %808, %809 : i32
%812 = arith.extsi %810 : i32 to i64
%811 = arith.shli %805, %812 : i64
%802 = func.call @pow_mod_ll(%803, %811, %arg1) : (i64, i64, i64) -> i64
%814 = llvm.load %767 : !llvm.ptr -> i64
%813 = func.call @mul_mod_ll(%814, %802, %arg1) : (i64, i64, i64) -> i64
llvm.store %813, %767 : i64, !llvm.ptr
%817 = llvm.load %771 : !llvm.ptr -> i64
%816 = func.call @mul_mod_ll(%817, %802, %arg1) : (i64, i64, i64) -> i64
%815 = func.call @mul_mod_ll(%816, %802, %arg1) : (i64, i64, i64) -> i64
llvm.store %815, %771 : i64, !llvm.ptr
%818 = func.call @mul_mod_ll(%802, %802, %arg1) : (i64, i64, i64) -> i64
llvm.store %818, %757 : i64, !llvm.ptr
%819 = llvm.load %781 : !llvm.ptr -> i32
llvm.store %819, %774 : i32, !llvm.ptr
cf.br ^bb153
^bb155:
%820 = llvm.load %767 : !llvm.ptr -> i64
func.return %820 : i64
}
func.func @hensel_lift(%arg0: i64, %arg1: i64, %arg2: i32, %arg3: i64) -> i64 {
%821 = llvm.mlir.constant(1 : i64) : i64
%822 = llvm.alloca %821 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %822 : i64, !llvm.ptr
%823 = arith.remsi %arg3, %arg1 : i64
%824 = llvm.mlir.constant(1 : i64) : i64
%825 = llvm.alloca %824 x i64 : (i64) -> !llvm.ptr
llvm.store %823, %825 : i64, !llvm.ptr
%826 = arith.constant 1 : i32
%827 = arith.extsi %826 : i32 to i64
%828 = llvm.mlir.constant(1 : i64) : i64
%829 = llvm.alloca %828 x i64 : (i64) -> !llvm.ptr
llvm.store %827, %829 : i64, !llvm.ptr
%830 = arith.constant 0 : i32
%831 = arith.index_cast %830 : i32 to index
%832 = arith.index_cast %arg2 : i32 to index
%834 = arith.constant 1 : index
%835 = arith.constant -1 : index
%836 = arith.cmpi sle, %831, %832 : index
%833 = arith.select %836, %834, %835 : index
cf.br ^bb159(%831 : index)
^bb159(%837: index):
%838 = arith.cmpi slt, %837, %832 : index
%839 = arith.cmpi sgt, %837, %832 : index
%840 = arith.select %836, %838, %839 : i1
cf.cond_br %840, ^bb160(%837 : index), ^bb161(%837 : index)
^bb160(%841: index):
%842 = llvm.load %829 : !llvm.ptr -> i64
%843 = arith.muli %842, %arg1 : i64
llvm.store %843, %829 : i64, !llvm.ptr
%844 = arith.addi %841, %833 : index
cf.br ^bb159(%844 : index)
^bb161(%845: index):
%846 = llvm.load %829 : !llvm.ptr -> i64
%847 = arith.remsi %arg0, %846 : 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 = llvm.load %849 : !llvm.ptr -> i64
%851 = arith.constant 0 : i32
%853 = arith.extsi %851 : i32 to i64
%852 = arith.cmpi slt, %850, %853 : i64
cf.cond_br %852, ^bb162, ^bb163
^bb162:
%854 = llvm.load %849 : !llvm.ptr -> i64
%855 = llvm.load %829 : !llvm.ptr -> i64
%856 = arith.addi %854, %855 : i64
llvm.store %856, %849 : i64, !llvm.ptr
cf.br ^bb164
^bb163:
cf.br ^bb164
^bb164:
%857 = arith.constant 1 : i32
%858 = llvm.mlir.constant(1 : i64) : i64
%859 = llvm.alloca %858 x i32 : (i64) -> !llvm.ptr
llvm.store %857, %859 : i32, !llvm.ptr
cf.br ^bb165
^bb165:
%860 = llvm.load %859 : !llvm.ptr -> i32
%861 = arith.cmpi slt, %860, %arg2 : i32
cf.cond_br %861, ^bb166, ^bb167
^bb166:
%862 = llvm.load %825 : !llvm.ptr -> i64
%863 = llvm.load %825 : !llvm.ptr -> i64
%864 = arith.muli %862, %863 : i64
%865 = llvm.load %849 : !llvm.ptr -> i64
%866 = arith.subi %864, %865 : i64
%867 = llvm.load %822 : !llvm.ptr -> i64
%868 = arith.divsi %866, %867 : i64
%869 = llvm.mlir.constant(1 : i64) : i64
%870 = llvm.alloca %869 x i64 : (i64) -> !llvm.ptr
llvm.store %868, %870 : i64, !llvm.ptr
%871 = llvm.load %822 : !llvm.ptr -> i64
%872 = arith.remsi %866, %871 : i64
%873 = arith.constant 0 : i32
%875 = arith.extsi %873 : i32 to i64
%874 = arith.cmpi ne, %872, %875 : i64
%876 = scf.if %874 -> (i1) {
%877 = arith.constant 0 : i32
%879 = arith.extsi %877 : i32 to i64
%878 = arith.cmpi slt, %866, %879 : i64
%880 = llvm.load %822 : !llvm.ptr -> i64
%881 = arith.constant 0 : i32
%883 = arith.extsi %881 : i32 to i64
%882 = arith.cmpi slt, %880, %883 : i64
%884 = arith.cmpi ne, %878, %882 : i1
scf.yield %884 : i1
} else {
%885 = arith.constant false
scf.yield %885 : i1
}
cf.cond_br %876, ^bb168, ^bb169
^bb168:
%886 = llvm.load %870 : !llvm.ptr -> i64
%887 = arith.constant 1 : i32
%889 = arith.extsi %887 : i32 to i64
%888 = arith.subi %886, %889 : i64
llvm.store %888, %870 : i64, !llvm.ptr
cf.br ^bb170
^bb169:
cf.br ^bb170
^bb170:
%890 = llvm.load %870 : !llvm.ptr -> i64
%891 = arith.remsi %890, %arg1 : i64
%892 = llvm.mlir.constant(1 : i64) : i64
%893 = llvm.alloca %892 x i64 : (i64) -> !llvm.ptr
llvm.store %891, %893 : i64, !llvm.ptr
%894 = llvm.load %893 : !llvm.ptr -> i64
%895 = arith.constant 0 : i32
%897 = arith.extsi %895 : i32 to i64
%896 = arith.cmpi slt, %894, %897 : i64
cf.cond_br %896, ^bb171, ^bb172
^bb171:
%898 = llvm.load %893 : !llvm.ptr -> i64
%899 = arith.addi %898, %arg1 : i64
llvm.store %899, %893 : i64, !llvm.ptr
cf.br ^bb173
^bb172:
cf.br ^bb173
^bb173:
%901 = arith.constant 2 : i32
%902 = llvm.load %825 : !llvm.ptr -> i64
%904 = arith.extsi %901 : i32 to i64
%903 = arith.muli %904, %902 : i64
%905 = arith.remsi %903, %arg1 : i64
%906 = arith.constant 2 : i32
%908 = arith.extsi %906 : i32 to i64
%907 = arith.subi %arg1, %908 : i64
%900 = func.call @pow_mod_ll(%905, %907, %arg1) : (i64, i64, i64) -> i64
%909 = llvm.load %893 : !llvm.ptr -> i64
%910 = arith.subi %arg1, %909 : i64
%911 = arith.muli %910, %900 : i64
%912 = arith.remsi %911, %arg1 : i64
%913 = llvm.load %825 : !llvm.ptr -> i64
%914 = llvm.load %822 : !llvm.ptr -> i64
%915 = arith.muli %912, %914 : i64
%916 = arith.addi %913, %915 : i64
llvm.store %916, %825 : i64, !llvm.ptr
%917 = llvm.load %822 : !llvm.ptr -> i64
%918 = arith.muli %917, %arg1 : i64
llvm.store %918, %822 : i64, !llvm.ptr
%919 = llvm.load %825 : !llvm.ptr -> i64
%920 = llvm.load %822 : !llvm.ptr -> i64
%921 = arith.remsi %919, %920 : i64
llvm.store %921, %825 : i64, !llvm.ptr
%922 = llvm.load %859 : !llvm.ptr -> i32
%923 = arith.constant 1 : i32
%924 = arith.addi %922, %923 : i32
llvm.store %924, %859 : i32, !llvm.ptr
cf.br ^bb165
^bb167:
%925 = llvm.load %825 : !llvm.ptr -> i64
func.return %925 : i64
}
func.func @roots_mod_pe(%arg0: i64, %arg1: i64, %arg2: i32, %arg3: !llvm.ptr) -> i32 {
%926 = arith.constant 1 : i32
%927 = arith.extsi %926 : i32 to i64
%928 = llvm.mlir.constant(1 : i64) : i64
%929 = llvm.alloca %928 x i64 : (i64) -> !llvm.ptr
llvm.store %927, %929 : i64, !llvm.ptr
%930 = arith.constant 0 : i32
%931 = arith.index_cast %930 : i32 to index
%932 = arith.index_cast %arg2 : i32 to index
%934 = arith.constant 1 : index
%935 = arith.constant -1 : index
%936 = arith.cmpi sle, %931, %932 : index
%933 = arith.select %936, %934, %935 : index
cf.br ^bb174(%931 : index)
^bb174(%937: index):
%938 = arith.cmpi slt, %937, %932 : index
%939 = arith.cmpi sgt, %937, %932 : index
%940 = arith.select %936, %938, %939 : i1
cf.cond_br %940, ^bb175(%937 : index), ^bb176(%937 : index)
^bb175(%941: index):
%942 = llvm.load %929 : !llvm.ptr -> i64
%943 = arith.muli %942, %arg1 : i64
llvm.store %943, %929 : i64, !llvm.ptr
%944 = arith.addi %941, %933 : index
cf.br ^bb174(%944 : index)
^bb176(%945: index):
%946 = llvm.load %929 : !llvm.ptr -> i64
%947 = arith.remsi %arg0, %946 : i64
%948 = llvm.mlir.constant(1 : i64) : i64
%949 = llvm.alloca %948 x i64 : (i64) -> !llvm.ptr
llvm.store %947, %949 : i64, !llvm.ptr
%950 = llvm.load %949 : !llvm.ptr -> i64
%951 = arith.constant 0 : i32
%953 = arith.extsi %951 : i32 to i64
%952 = arith.cmpi slt, %950, %953 : i64
cf.cond_br %952, ^bb177, ^bb178
^bb177:
%954 = llvm.load %949 : !llvm.ptr -> i64
%955 = llvm.load %929 : !llvm.ptr -> i64
%956 = arith.addi %954, %955 : i64
llvm.store %956, %949 : i64, !llvm.ptr
cf.br ^bb179
^bb178:
cf.br ^bb179
^bb179:
%957 = llvm.load %949 : !llvm.ptr -> i64
%958 = arith.remsi %957, %arg1 : i64
%959 = arith.constant 0 : i32
%961 = arith.extsi %959 : i32 to i64
%960 = arith.cmpi eq, %958, %961 : i64
cf.cond_br %960, ^bb180, ^bb181
^bb180:
%962 = llvm.load %949 : !llvm.ptr -> i64
%963 = arith.constant 0 : i32
%965 = arith.extsi %963 : i32 to i64
%964 = arith.cmpi eq, %962, %965 : i64
cf.cond_br %964, ^bb183, ^bb184
^bb183:
%966 = arith.constant 1 : i32
%967 = arith.extsi %966 : i32 to i64
%968 = llvm.mlir.constant(1 : i64) : i64
%969 = llvm.alloca %968 x i64 : (i64) -> !llvm.ptr
llvm.store %967, %969 : i64, !llvm.ptr
%970 = arith.constant 0 : i32
%971 = arith.constant 1 : i32
%972 = arith.addi %arg2, %971 : i32
%973 = arith.constant 2 : i32
%974 = arith.divsi %972, %973 : i32
%975 = arith.index_cast %970 : i32 to index
%976 = arith.index_cast %974 : i32 to index
%978 = arith.constant 1 : index
%979 = arith.constant -1 : index
%980 = arith.cmpi sle, %975, %976 : index
%977 = arith.select %980, %978, %979 : index
cf.br ^bb186(%975 : index)
^bb186(%981: index):
%982 = arith.cmpi slt, %981, %976 : index
%983 = arith.cmpi sgt, %981, %976 : index
%984 = arith.select %980, %982, %983 : i1
cf.cond_br %984, ^bb187(%981 : index), ^bb188(%981 : index)
^bb187(%985: index):
%986 = llvm.load %969 : !llvm.ptr -> i64
%987 = arith.muli %986, %arg1 : i64
llvm.store %987, %969 : i64, !llvm.ptr
%988 = arith.addi %985, %977 : index
cf.br ^bb186(%988 : index)
^bb188(%989: index):
%990 = arith.constant 0 : i32
%991 = llvm.mlir.constant(1 : i64) : i64
%992 = llvm.alloca %991 x i32 : (i64) -> !llvm.ptr
llvm.store %990, %992 : i32, !llvm.ptr
%993 = arith.constant 0 : i32
%994 = arith.extsi %993 : i32 to i64
%995 = llvm.mlir.constant(1 : i64) : i64
%996 = llvm.alloca %995 x i64 : (i64) -> !llvm.ptr
llvm.store %994, %996 : i64, !llvm.ptr
cf.br ^bb189
^bb189:
%997 = llvm.load %996 : !llvm.ptr -> i64
%998 = llvm.load %929 : !llvm.ptr -> i64
%999 = arith.cmpi slt, %997, %998 : i64
cf.cond_br %999, ^bb190, ^bb191
^bb190:
%1000 = llvm.load %996 : !llvm.ptr -> i64
%1001 = llvm.load %992 : !llvm.ptr -> i32
%1002 = arith.extsi %1001 : i32 to i64
%1003 = llvm.getelementptr %arg3[%1002] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1000, %1003 : i64, !llvm.ptr
%1004 = llvm.load %992 : !llvm.ptr -> i32
%1005 = arith.constant 1 : i32
%1006 = arith.addi %1004, %1005 : i32
llvm.store %1006, %992 : i32, !llvm.ptr
%1007 = llvm.load %996 : !llvm.ptr -> i64
%1008 = llvm.load %969 : !llvm.ptr -> i64
%1009 = arith.addi %1007, %1008 : i64
llvm.store %1009, %996 : i64, !llvm.ptr
cf.br ^bb189
^bb191:
%1010 = llvm.load %992 : !llvm.ptr -> i32
func.return %1010 : i32
^bb184:
cf.br ^bb185
^bb185:
%1011 = arith.constant 1 : i32
%1012 = arith.cmpi eq, %arg2, %1011 : i32
cf.cond_br %1012, ^bb192, ^bb193
^bb192:
%1013 = arith.constant 0 : i32
%1014 = arith.constant 0 : i32
%1015 = arith.extsi %1013 : i32 to i64
%1016 = arith.extsi %1014 : i32 to i64
%1017 = llvm.getelementptr %arg3[%1016] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1015, %1017 : i64, !llvm.ptr
%1018 = arith.constant 1 : i32
func.return %1018 : i32
^bb193:
cf.br ^bb194
^bb194:
%1019 = arith.constant 0 : i32
func.return %1019 : i32
^bb181:
cf.br ^bb182
^bb182:
%1021 = llvm.load %949 : !llvm.ptr -> i64
%1020 = func.call @tonelli_shanks2(%1021, %arg1) : (i64, i64) -> i64
%1022 = arith.constant 1 : i32
%1024 = arith.constant 0 : i32
%1023 = arith.subi %1024, %1022 : i32
%1026 = arith.extsi %1023 : i32 to i64
%1025 = arith.cmpi eq, %1020, %1026 : i64
cf.cond_br %1025, ^bb195, ^bb196
^bb195:
%1027 = arith.constant 0 : i32
func.return %1027 : i32
^bb196:
cf.br ^bb197
^bb197:
%1028 = llvm.mlir.constant(1 : i64) : i64
%1029 = llvm.alloca %1028 x i64 : (i64) -> !llvm.ptr
llvm.store %1020, %1029 : i64, !llvm.ptr
%1030 = arith.constant 1 : i32
%1031 = arith.cmpi sgt, %arg2, %1030 : i32
cf.cond_br %1031, ^bb198, ^bb199
^bb198:
%1033 = llvm.load %949 : !llvm.ptr -> i64
%1032 = func.call @hensel_lift(%1033, %arg1, %arg2, %1020) : (i64, i64, i32, i64) -> i64
llvm.store %1032, %1029 : i64, !llvm.ptr
cf.br ^bb200
^bb199:
cf.br ^bb200
^bb200:
%1034 = llvm.load %929 : !llvm.ptr -> i64
%1035 = llvm.load %1029 : !llvm.ptr -> i64
%1036 = arith.subi %1034, %1035 : i64
%1037 = llvm.load %1029 : !llvm.ptr -> i64
%1038 = arith.cmpi eq, %1036, %1037 : i64
cf.cond_br %1038, ^bb201, ^bb202
^bb201:
%1039 = llvm.load %1029 : !llvm.ptr -> i64
%1040 = arith.constant 0 : i32
%1041 = arith.extsi %1040 : i32 to i64
%1042 = llvm.getelementptr %arg3[%1041] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1039, %1042 : i64, !llvm.ptr
%1043 = arith.constant 1 : i32
func.return %1043 : i32
^bb202:
cf.br ^bb203
^bb203:
%1044 = llvm.load %1029 : !llvm.ptr -> i64
%1045 = arith.constant 0 : i32
%1046 = arith.extsi %1045 : i32 to i64
%1047 = llvm.getelementptr %arg3[%1046] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1044, %1047 : i64, !llvm.ptr
%1048 = arith.constant 1 : i32
%1049 = arith.extsi %1048 : i32 to i64
%1050 = llvm.getelementptr %arg3[%1049] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1036, %1050 : i64, !llvm.ptr
%1051 = arith.constant 2 : i32
func.return %1051 : i32
}
func.func @ext_gcd(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: !llvm.ptr) -> i64 {
%1052 = arith.constant 0 : i32
%1054 = arith.extsi %1052 : i32 to i64
%1053 = arith.cmpi eq, %arg1, %1054 : i64
cf.cond_br %1053, ^bb204, ^bb205
^bb204:
%1055 = arith.constant 1 : i32
%1056 = arith.constant 0 : i32
%1057 = arith.extsi %1055 : i32 to i64
%1058 = arith.extsi %1056 : i32 to i64
%1059 = llvm.getelementptr %arg2[%1058] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1057, %1059 : i64, !llvm.ptr
%1060 = arith.constant 0 : i32
%1061 = arith.constant 0 : i32
%1062 = arith.extsi %1060 : i32 to i64
%1063 = arith.extsi %1061 : i32 to i64
%1064 = llvm.getelementptr %arg3[%1063] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1062, %1064 : i64, !llvm.ptr
func.return %arg0 : i64
^bb205:
cf.br ^bb206
^bb206:
%1066 = arith.constant 1 : i32
%1067 = arith.constant 8 : i32
%1068 = arith.extsi %1066 : i32 to i64
%1069 = arith.extsi %1067 : i32 to i64
%1065 = func.call @calloc(%1068, %1069) : (i64, i64) -> !llvm.ptr
%1071 = arith.constant 1 : i32
%1072 = arith.constant 8 : i32
%1073 = arith.extsi %1071 : i32 to i64
%1074 = arith.extsi %1072 : i32 to i64
%1070 = func.call @calloc(%1073, %1074) : (i64, i64) -> !llvm.ptr
%1076 = arith.remsi %arg0, %arg1 : i64
%1075 = func.call @ext_gcd(%arg1, %1076, %1065, %1070) : (i64, i64, !llvm.ptr, !llvm.ptr) -> i64
%1078 = arith.constant 0 : i32
%1079 = arith.extsi %1078 : i32 to i64
%1080 = llvm.getelementptr %1070[%1079] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1077 = llvm.load %1080 : !llvm.ptr -> i64
%1081 = arith.constant 0 : i32
%1082 = arith.extsi %1081 : i32 to i64
%1083 = llvm.getelementptr %arg2[%1082] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1077, %1083 : i64, !llvm.ptr
%1085 = arith.constant 0 : i32
%1086 = arith.extsi %1085 : i32 to i64
%1087 = llvm.getelementptr %1065[%1086] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1084 = llvm.load %1087 : !llvm.ptr -> i64
%1088 = arith.divsi %arg0, %arg1 : i64
%1090 = arith.constant 0 : i32
%1091 = arith.extsi %1090 : i32 to i64
%1092 = llvm.getelementptr %1070[%1091] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1089 = llvm.load %1092 : !llvm.ptr -> i64
%1093 = arith.muli %1088, %1089 : i64
%1094 = arith.subi %1084, %1093 : i64
%1095 = arith.constant 0 : i32
%1096 = arith.extsi %1095 : i32 to i64
%1097 = llvm.getelementptr %arg3[%1096] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1094, %1097 : i64, !llvm.ptr
func.call @free(%1065) : (!llvm.ptr) -> ()
func.call @free(%1070) : (!llvm.ptr) -> ()
func.return %1075 : i64
}
func.func @mod_inv_general(%arg0: i64, %arg1: i64) -> i64 {
%1101 = arith.constant 1 : i32
%1102 = arith.constant 8 : i32
%1103 = arith.extsi %1101 : i32 to i64
%1104 = arith.extsi %1102 : i32 to i64
%1100 = func.call @calloc(%1103, %1104) : (i64, i64) -> !llvm.ptr
%1106 = arith.constant 1 : i32
%1107 = arith.constant 8 : i32
%1108 = arith.extsi %1106 : i32 to i64
%1109 = arith.extsi %1107 : i32 to i64
%1105 = func.call @calloc(%1108, %1109) : (i64, i64) -> !llvm.ptr
%1110 = arith.remsi %arg0, %arg1 : i64
%1111 = llvm.mlir.constant(1 : i64) : i64
%1112 = llvm.alloca %1111 x i64 : (i64) -> !llvm.ptr
llvm.store %1110, %1112 : i64, !llvm.ptr
%1113 = llvm.load %1112 : !llvm.ptr -> i64
%1114 = arith.constant 0 : i32
%1116 = arith.extsi %1114 : i32 to i64
%1115 = arith.cmpi slt, %1113, %1116 : i64
cf.cond_br %1115, ^bb207, ^bb208
^bb207:
%1117 = llvm.load %1112 : !llvm.ptr -> i64
%1118 = arith.addi %1117, %arg1 : i64
llvm.store %1118, %1112 : i64, !llvm.ptr
cf.br ^bb209
^bb208:
cf.br ^bb209
^bb209:
%1120 = llvm.load %1112 : !llvm.ptr -> i64
%1119 = func.call @ext_gcd(%1120, %arg1, %1100, %1105) : (i64, i64, !llvm.ptr, !llvm.ptr) -> i64
%1122 = arith.constant 0 : i32
%1123 = arith.extsi %1122 : i32 to i64
%1124 = llvm.getelementptr %1100[%1123] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1121 = llvm.load %1124 : !llvm.ptr -> i64
%1125 = arith.remsi %1121, %arg1 : i64
%1126 = llvm.mlir.constant(1 : i64) : i64
%1127 = llvm.alloca %1126 x i64 : (i64) -> !llvm.ptr
llvm.store %1125, %1127 : i64, !llvm.ptr
%1128 = llvm.load %1127 : !llvm.ptr -> i64
%1129 = arith.constant 0 : i32
%1131 = arith.extsi %1129 : i32 to i64
%1130 = arith.cmpi slt, %1128, %1131 : i64
cf.cond_br %1130, ^bb210, ^bb211
^bb210:
%1132 = llvm.load %1127 : !llvm.ptr -> i64
%1133 = arith.addi %1132, %arg1 : i64
llvm.store %1133, %1127 : i64, !llvm.ptr
cf.br ^bb212
^bb211:
cf.br ^bb212
^bb212:
func.call @free(%1100) : (!llvm.ptr) -> ()
func.call @free(%1105) : (!llvm.ptr) -> ()
%1136 = llvm.load %1127 : !llvm.ptr -> i64
func.return %1136 : i64
}
func.func @crt(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64, %arg4: !llvm.ptr, %arg5: !llvm.ptr) -> () {
%1137 = arith.constant 1 : i32
%1139 = arith.extsi %1137 : i32 to i64
%1138 = arith.cmpi eq, %arg1, %1139 : i64
cf.cond_br %1138, ^bb213, ^bb214
^bb213:
%1140 = arith.constant 0 : i32
%1141 = arith.extsi %1140 : i32 to i64
%1142 = llvm.getelementptr %arg4[%1141] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg2, %1142 : i64, !llvm.ptr
%1143 = arith.constant 0 : i32
%1144 = arith.extsi %1143 : i32 to i64
%1145 = llvm.getelementptr %arg5[%1144] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg3, %1145 : i64, !llvm.ptr
func.return
^bb214:
cf.br ^bb215
^bb215:
%1146 = arith.constant 1 : i32
%1148 = arith.extsi %1146 : i32 to i64
%1147 = arith.cmpi eq, %arg3, %1148 : i64
cf.cond_br %1147, ^bb216, ^bb217
^bb216:
%1149 = arith.constant 0 : i32
%1150 = arith.extsi %1149 : i32 to i64
%1151 = llvm.getelementptr %arg4[%1150] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %1151 : i64, !llvm.ptr
%1152 = arith.constant 0 : i32
%1153 = arith.extsi %1152 : i32 to i64
%1154 = llvm.getelementptr %arg5[%1153] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %1154 : i64, !llvm.ptr
func.return
^bb217:
cf.br ^bb218
^bb218:
%1156 = arith.remsi %arg1, %arg3 : i64
%1155 = func.call @mod_inv_general(%1156, %arg3) : (i64, i64) -> i64
%1157 = arith.subi %arg2, %arg0 : i64
%1158 = arith.remsi %1157, %arg3 : i64
%1159 = arith.addi %1158, %arg3 : i64
%1160 = arith.remsi %1159, %arg3 : i64
%1161 = arith.muli %1160, %1155 : i64
%1162 = arith.remsi %1161, %arg3 : i64
%1163 = arith.muli %arg1, %1162 : i64
%1164 = arith.addi %arg0, %1163 : i64
%1165 = arith.constant 0 : i32
%1166 = arith.extsi %1165 : i32 to i64
%1167 = llvm.getelementptr %arg4[%1166] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1164, %1167 : i64, !llvm.ptr
%1168 = arith.muli %arg1, %arg3 : i64
%1169 = arith.constant 0 : i32
%1170 = arith.extsi %1169 : i32 to i64
%1171 = llvm.getelementptr %arg5[%1170] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1168, %1171 : i64, !llvm.ptr
func.return
}
func.func @sieve_spf(%arg0: i32, %arg1: !llvm.ptr) -> () {
%1172 = arith.constant 0 : i32
%1173 = arith.constant 1 : i32
%1174 = arith.addi %arg0, %1173 : i32
%1175 = arith.index_cast %1172 : i32 to index
%1176 = arith.index_cast %1174 : i32 to index
%1178 = arith.constant 1 : index
%1179 = arith.constant -1 : index
%1180 = arith.cmpi sle, %1175, %1176 : index
%1177 = arith.select %1180, %1178, %1179 : index
cf.br ^bb219(%1175 : index)
^bb219(%1181: index):
%1182 = arith.cmpi slt, %1181, %1176 : index
%1183 = arith.cmpi sgt, %1181, %1176 : index
%1184 = arith.select %1180, %1182, %1183 : i1
cf.cond_br %1184, ^bb220(%1181 : index), ^bb221(%1181 : index)
^bb220(%1185: index):
%1186 = arith.index_cast %1185 : index to i32
%1187 = arith.index_cast %1185 : index to i64
%1188 = llvm.getelementptr %arg1[%1187] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1186, %1188 : i32, !llvm.ptr
%1189 = arith.addi %1185, %1177 : index
cf.br ^bb219(%1189 : index)
^bb221(%1190: index):
%1191 = arith.constant 2 : i32
%1192 = llvm.mlir.constant(1 : i64) : i64
%1193 = llvm.alloca %1192 x i32 : (i64) -> !llvm.ptr
llvm.store %1191, %1193 : i32, !llvm.ptr
cf.br ^bb222
^bb222:
%1194 = llvm.load %1193 : !llvm.ptr -> i32
%1195 = llvm.load %1193 : !llvm.ptr -> i32
%1196 = arith.muli %1194, %1195 : i32
%1197 = arith.cmpi sle, %1196, %arg0 : i32
cf.cond_br %1197, ^bb223, ^bb224
^bb223:
%1199 = llvm.load %1193 : !llvm.ptr -> i32
%1200 = arith.extsi %1199 : i32 to i64
%1201 = llvm.getelementptr %arg1[%1200] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1198 = llvm.load %1201 : !llvm.ptr -> i32
%1202 = llvm.load %1193 : !llvm.ptr -> i32
%1203 = arith.cmpi eq, %1198, %1202 : i32
cf.cond_br %1203, ^bb225, ^bb226
^bb225:
%1204 = llvm.load %1193 : !llvm.ptr -> i32
%1205 = llvm.load %1193 : !llvm.ptr -> i32
%1206 = arith.muli %1204, %1205 : i32
%1207 = llvm.mlir.constant(1 : i64) : i64
%1208 = llvm.alloca %1207 x i32 : (i64) -> !llvm.ptr
llvm.store %1206, %1208 : i32, !llvm.ptr
cf.br ^bb228
^bb228:
%1209 = llvm.load %1208 : !llvm.ptr -> i32
%1210 = arith.cmpi sle, %1209, %arg0 : i32
cf.cond_br %1210, ^bb229, ^bb230
^bb229:
%1212 = llvm.load %1208 : !llvm.ptr -> i32
%1213 = arith.extsi %1212 : i32 to i64
%1214 = llvm.getelementptr %arg1[%1213] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1211 = llvm.load %1214 : !llvm.ptr -> i32
%1215 = llvm.load %1208 : !llvm.ptr -> i32
%1216 = arith.cmpi eq, %1211, %1215 : i32
cf.cond_br %1216, ^bb231, ^bb232
^bb231:
%1217 = llvm.load %1193 : !llvm.ptr -> i32
%1218 = llvm.load %1208 : !llvm.ptr -> i32
%1219 = arith.extsi %1218 : i32 to i64
%1220 = llvm.getelementptr %arg1[%1219] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1217, %1220 : i32, !llvm.ptr
cf.br ^bb233
^bb232:
cf.br ^bb233
^bb233:
%1221 = llvm.load %1208 : !llvm.ptr -> i32
%1222 = llvm.load %1193 : !llvm.ptr -> i32
%1223 = arith.addi %1221, %1222 : i32
llvm.store %1223, %1208 : i32, !llvm.ptr
cf.br ^bb228
^bb230:
cf.br ^bb227
^bb226:
cf.br ^bb227
^bb227:
%1224 = llvm.load %1193 : !llvm.ptr -> i32
%1225 = arith.constant 1 : i32
%1226 = arith.addi %1224, %1225 : i32
llvm.store %1226, %1193 : i32, !llvm.ptr
cf.br ^bb222
^bb224:
func.return
}
func.func @factorize_small(%arg0: i32, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr) -> i32 {
%1227 = llvm.mlir.constant(1 : i64) : i64
%1228 = llvm.alloca %1227 x i32 : (i64) -> !llvm.ptr
llvm.store %arg0, %1228 : i32, !llvm.ptr
%1229 = arith.constant 0 : i32
%1230 = llvm.mlir.constant(1 : i64) : i64
%1231 = llvm.alloca %1230 x i32 : (i64) -> !llvm.ptr
llvm.store %1229, %1231 : i32, !llvm.ptr
cf.br ^bb234
^bb234:
%1232 = llvm.load %1228 : !llvm.ptr -> i32
%1233 = arith.constant 1 : i32
%1234 = arith.cmpi sgt, %1232, %1233 : i32
cf.cond_br %1234, ^bb235, ^bb236
^bb235:
%1236 = llvm.load %1228 : !llvm.ptr -> i32
%1237 = arith.extsi %1236 : i32 to i64
%1238 = llvm.getelementptr %arg1[%1237] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1235 = llvm.load %1238 : !llvm.ptr -> i32
%1239 = arith.constant 0 : i32
%1240 = llvm.mlir.constant(1 : i64) : i64
%1241 = llvm.alloca %1240 x i32 : (i64) -> !llvm.ptr
llvm.store %1239, %1241 : i32, !llvm.ptr
cf.br ^bb237
^bb237:
%1242 = llvm.load %1228 : !llvm.ptr -> i32
%1243 = arith.remsi %1242, %1235 : i32
%1244 = arith.constant 0 : i32
%1245 = arith.cmpi eq, %1243, %1244 : i32
cf.cond_br %1245, ^bb238, ^bb239
^bb238:
%1246 = llvm.load %1228 : !llvm.ptr -> i32
%1247 = arith.divsi %1246, %1235 : i32
llvm.store %1247, %1228 : i32, !llvm.ptr
%1248 = llvm.load %1241 : !llvm.ptr -> i32
%1249 = arith.constant 1 : i32
%1250 = arith.addi %1248, %1249 : i32
llvm.store %1250, %1241 : i32, !llvm.ptr
cf.br ^bb237
^bb239:
%1251 = llvm.load %1231 : !llvm.ptr -> i32
%1252 = arith.extsi %1251 : i32 to i64
%1253 = llvm.getelementptr %arg2[%1252] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1235, %1253 : i32, !llvm.ptr
%1254 = llvm.load %1241 : !llvm.ptr -> i32
%1255 = llvm.load %1231 : !llvm.ptr -> i32
%1256 = arith.extsi %1255 : i32 to i64
%1257 = llvm.getelementptr %arg3[%1256] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1254, %1257 : i32, !llvm.ptr
%1258 = llvm.load %1231 : !llvm.ptr -> i32
%1259 = arith.constant 1 : i32
%1260 = arith.addi %1258, %1259 : i32
llvm.store %1260, %1231 : i32, !llvm.ptr
cf.br ^bb234
^bb236:
%1261 = llvm.load %1231 : !llvm.ptr -> i32
func.return %1261 : i32
}
func.func @class_number(%arg0: i64) -> i64 {
%1263 = arith.constant 0 : i64
%1262 = arith.subi %1263, %arg0 : i64
%1265 = arith.constant 3 : i32
%1267 = arith.extsi %1265 : i32 to i64
%1266 = arith.divsi %1262, %1267 : i64
%1264 = func.call @isqrt(%1266) : (i64) -> i64
%1269 = arith.constant 1 : i32
%1271 = arith.extsi %1269 : i32 to i64
%1270 = arith.addi %1264, %1271 : i64
%1272 = arith.constant 4 : i32
%1273 = arith.extsi %1272 : i32 to i64
%1268 = func.call @calloc(%1270, %1273) : (i64, i64) -> !llvm.ptr
%1275 = arith.trunci %1264 : i64 to i32
func.call @sieve_spf(%1275, %1268) : (i32, !llvm.ptr) -> ()
%1276 = arith.constant 0 : i32
%1277 = arith.extsi %1276 : i32 to i64
%1278 = llvm.mlir.constant(1 : i64) : i64
%1279 = llvm.alloca %1278 x i64 : (i64) -> !llvm.ptr
llvm.store %1277, %1279 : i64, !llvm.ptr
%1280 = arith.constant 1 : i32
%1281 = arith.extsi %1280 : i32 to i64
%1282 = llvm.mlir.constant(1 : i64) : i64
%1283 = llvm.alloca %1282 x i64 : (i64) -> !llvm.ptr
llvm.store %1281, %1283 : i64, !llvm.ptr
cf.br ^bb240
^bb240:
%1284 = llvm.load %1283 : !llvm.ptr -> i64
%1285 = arith.cmpi sle, %1284, %1264 : i64
cf.cond_br %1285, ^bb241, ^bb242
^bb241:
%1287 = arith.constant 20 : i32
%1288 = arith.constant 4 : i32
%1289 = arith.extsi %1287 : i32 to i64
%1290 = arith.extsi %1288 : i32 to i64
%1286 = func.call @calloc(%1289, %1290) : (i64, i64) -> !llvm.ptr
%1292 = arith.constant 20 : i32
%1293 = arith.constant 4 : i32
%1294 = arith.extsi %1292 : i32 to i64
%1295 = arith.extsi %1293 : i32 to i64
%1291 = func.call @calloc(%1294, %1295) : (i64, i64) -> !llvm.ptr
%1297 = llvm.load %1283 : !llvm.ptr -> i64
%1298 = arith.trunci %1297 : i64 to i32
%1296 = func.call @factorize_small(%1298, %1268, %1286, %1291) : (i32, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i32
%1299 = arith.constant 0 : i1
%1300 = llvm.mlir.constant(1 : i64) : i64
%1301 = llvm.alloca %1300 x i1 : (i64) -> !llvm.ptr
llvm.store %1299, %1301 : i1, !llvm.ptr
%1302 = arith.constant 0 : i32
%1303 = arith.index_cast %1302 : i32 to index
%1304 = arith.index_cast %1296 : i32 to index
%1306 = arith.constant 1 : index
%1307 = arith.constant -1 : index
%1308 = arith.cmpi sle, %1303, %1304 : index
%1305 = arith.select %1308, %1306, %1307 : index
cf.br ^bb243(%1303 : index)
^bb243(%1309: index):
%1310 = arith.cmpi slt, %1309, %1304 : index
%1311 = arith.cmpi sgt, %1309, %1304 : index
%1312 = arith.select %1308, %1310, %1311 : i1
cf.cond_br %1312, ^bb244(%1309 : index), ^bb245(%1309 : index)
^bb244(%1313: index):
%1315 = arith.index_cast %1313 : index to i64
%1316 = llvm.getelementptr %1291[%1315] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1314 = llvm.load %1316 : !llvm.ptr -> i32
%1317 = arith.constant 2 : i32
%1318 = arith.cmpi sge, %1314, %1317 : i32
%1319 = scf.if %1318 -> (i1) {
%1321 = arith.index_cast %1313 : index to i64
%1322 = llvm.getelementptr %1286[%1321] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1320 = llvm.load %1322 : !llvm.ptr -> i32
%1323 = arith.extsi %1320 : i32 to i64
%1324 = arith.remsi %arg0, %1323 : i64
%1325 = arith.constant 0 : i32
%1327 = arith.extsi %1325 : i32 to i64
%1326 = arith.cmpi eq, %1324, %1327 : i64
scf.yield %1326 : i1
} else {
%1328 = arith.constant false
scf.yield %1328 : i1
}
cf.cond_br %1319, ^bb246, ^bb247
^bb246:
%1329 = arith.constant 1 : i1
llvm.store %1329, %1301 : i1, !llvm.ptr
cf.br ^bb245(%1313 : index)
^bb247:
cf.br ^bb248
^bb248:
%1330 = arith.addi %1313, %1305 : index
cf.br ^bb243(%1330 : index)
^bb245(%1331: index):
%1332 = llvm.load %1301 : !llvm.ptr -> i1
%1334 = arith.constant 1 : i1
%1333 = arith.xori %1332, %1334 : i1
cf.cond_br %1333, ^bb249, ^bb250
^bb249:
%1337 = arith.constant 1024 : i32
%1338 = arith.constant 8 : i32
%1339 = arith.extsi %1337 : i32 to i64
%1340 = arith.extsi %1338 : i32 to i64
%1336 = func.call @calloc(%1339, %1340) : (i64, i64) -> !llvm.ptr
%1341 = arith.constant 1 : i32
%1342 = llvm.mlir.constant(1 : i64) : i64
%1343 = llvm.alloca %1342 x i32 : (i64) -> !llvm.ptr
llvm.store %1341, %1343 : i32, !llvm.ptr
%1344 = arith.constant 0 : i32
%1345 = arith.constant 0 : i32
%1346 = arith.extsi %1344 : i32 to i64
%1347 = arith.extsi %1345 : i32 to i64
%1348 = llvm.getelementptr %1336[%1347] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1346, %1348 : i64, !llvm.ptr
%1349 = arith.constant 1 : i32
%1350 = arith.extsi %1349 : i32 to i64
%1351 = llvm.mlir.constant(1 : i64) : i64
%1352 = llvm.alloca %1351 x i64 : (i64) -> !llvm.ptr
llvm.store %1350, %1352 : i64, !llvm.ptr
%1353 = arith.constant 1 : i1
%1354 = llvm.mlir.constant(1 : i64) : i64
%1355 = llvm.alloca %1354 x i1 : (i64) -> !llvm.ptr
llvm.store %1353, %1355 : i1, !llvm.ptr
%1356 = arith.constant 0 : i32
%1357 = arith.index_cast %1356 : i32 to index
%1358 = arith.index_cast %1296 : i32 to index
%1360 = arith.constant 1 : index
%1361 = arith.constant -1 : index
%1362 = arith.cmpi sle, %1357, %1358 : index
%1359 = arith.select %1362, %1360, %1361 : index
cf.br ^bb252(%1357 : index)
^bb252(%1363: index):
%1364 = arith.cmpi slt, %1363, %1358 : index
%1365 = arith.cmpi sgt, %1363, %1358 : index
%1366 = arith.select %1362, %1364, %1365 : i1
cf.cond_br %1366, ^bb253(%1363 : index), ^bb254(%1363 : index)
^bb253(%1367: index):
%1369 = arith.index_cast %1367 : index to i64
%1370 = llvm.getelementptr %1286[%1369] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1368 = llvm.load %1370 : !llvm.ptr -> i32
%1371 = arith.extsi %1368 : i32 to i64
%1373 = arith.index_cast %1367 : index to i64
%1374 = llvm.getelementptr %1291[%1373] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1372 = llvm.load %1374 : !llvm.ptr -> i32
%1375 = arith.constant 1 : i32
%1376 = arith.extsi %1375 : i32 to i64
%1377 = llvm.mlir.constant(1 : i64) : i64
%1378 = llvm.alloca %1377 x i64 : (i64) -> !llvm.ptr
llvm.store %1376, %1378 : i64, !llvm.ptr
%1379 = arith.constant 0 : i32
%1380 = arith.index_cast %1379 : i32 to index
%1381 = arith.index_cast %1372 : i32 to index
%1383 = arith.constant 1 : index
%1384 = arith.constant -1 : index
%1385 = arith.cmpi sle, %1380, %1381 : index
%1382 = arith.select %1385, %1383, %1384 : index
cf.br ^bb255(%1380 : index)
^bb255(%1386: index):
%1387 = arith.cmpi slt, %1386, %1381 : index
%1388 = arith.cmpi sgt, %1386, %1381 : index
%1389 = arith.select %1385, %1387, %1388 : i1
cf.cond_br %1389, ^bb256(%1386 : index), ^bb257(%1386 : index)
^bb256(%1390: index):
%1391 = llvm.load %1378 : !llvm.ptr -> i64
%1392 = arith.muli %1391, %1371 : i64
llvm.store %1392, %1378 : i64, !llvm.ptr
%1393 = arith.addi %1390, %1382 : index
cf.br ^bb255(%1393 : index)
^bb257(%1394: index):
%1396 = arith.constant 8 : i32
%1397 = arith.constant 8 : i32
%1398 = arith.extsi %1396 : i32 to i64
%1399 = arith.extsi %1397 : i32 to i64
%1395 = func.call @calloc(%1398, %1399) : (i64, i64) -> !llvm.ptr
%1400 = func.call @roots_mod_pe(%arg0, %1371, %1372, %1395) : (i64, i64, i32, !llvm.ptr) -> i32
%1401 = arith.constant 0 : i32
%1402 = arith.cmpi eq, %1400, %1401 : i32
cf.cond_br %1402, ^bb258, ^bb259
^bb258:
%1403 = arith.constant 0 : i1
llvm.store %1403, %1355 : i1, !llvm.ptr
func.call @free(%1395) : (!llvm.ptr) -> ()
cf.br ^bb254(%1367 : index)
^bb259:
cf.br ^bb260
^bb260:
%1406 = arith.constant 1024 : i32
%1407 = arith.constant 8 : i32
%1408 = arith.extsi %1406 : i32 to i64
%1409 = arith.extsi %1407 : i32 to i64
%1405 = func.call @calloc(%1408, %1409) : (i64, i64) -> !llvm.ptr
%1410 = arith.constant 0 : i32
%1411 = llvm.mlir.constant(1 : i64) : i64
%1412 = llvm.alloca %1411 x i32 : (i64) -> !llvm.ptr
llvm.store %1410, %1412 : i32, !llvm.ptr
%1413 = arith.constant 0 : i32
%1414 = llvm.load %1343 : !llvm.ptr -> i32
%1415 = arith.index_cast %1413 : i32 to index
%1416 = arith.index_cast %1414 : i32 to index
%1418 = arith.constant 1 : index
%1419 = arith.constant -1 : index
%1420 = arith.cmpi sle, %1415, %1416 : index
%1417 = arith.select %1420, %1418, %1419 : index
cf.br ^bb261(%1415 : index)
^bb261(%1421: index):
%1422 = arith.cmpi slt, %1421, %1416 : index
%1423 = arith.cmpi sgt, %1421, %1416 : index
%1424 = arith.select %1420, %1422, %1423 : i1
cf.cond_br %1424, ^bb262(%1421 : index), ^bb263(%1421 : index)
^bb262(%1425: index):
%1426 = arith.constant 0 : i32
%1427 = arith.index_cast %1426 : i32 to index
%1428 = arith.index_cast %1400 : i32 to index
%1430 = arith.constant 1 : index
%1431 = arith.constant -1 : index
%1432 = arith.cmpi sle, %1427, %1428 : index
%1429 = arith.select %1432, %1430, %1431 : index
cf.br ^bb264(%1427 : index)
^bb264(%1433: index):
%1434 = arith.cmpi slt, %1433, %1428 : index
%1435 = arith.cmpi sgt, %1433, %1428 : index
%1436 = arith.select %1432, %1434, %1435 : i1
cf.cond_br %1436, ^bb265(%1433 : index), ^bb266(%1433 : index)
^bb265(%1437: index):
%1439 = arith.constant 1 : i32
%1440 = arith.constant 8 : i32
%1441 = arith.extsi %1439 : i32 to i64
%1442 = arith.extsi %1440 : i32 to i64
%1438 = func.call @calloc(%1441, %1442) : (i64, i64) -> !llvm.ptr
%1444 = arith.constant 1 : i32
%1445 = arith.constant 8 : i32
%1446 = arith.extsi %1444 : i32 to i64
%1447 = arith.extsi %1445 : i32 to i64
%1443 = func.call @calloc(%1446, %1447) : (i64, i64) -> !llvm.ptr
%1450 = arith.index_cast %1425 : index to i64
%1451 = llvm.getelementptr %1336[%1450] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1449 = llvm.load %1451 : !llvm.ptr -> i64
%1452 = llvm.load %1352 : !llvm.ptr -> i64
%1454 = arith.index_cast %1437 : index to i64
%1455 = llvm.getelementptr %1395[%1454] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1453 = llvm.load %1455 : !llvm.ptr -> i64
%1456 = llvm.load %1378 : !llvm.ptr -> i64
func.call @crt(%1449, %1452, %1453, %1456, %1438, %1443) : (i64, i64, i64, i64, !llvm.ptr, !llvm.ptr) -> ()
%1458 = arith.constant 0 : i32
%1459 = arith.extsi %1458 : i32 to i64
%1460 = llvm.getelementptr %1438[%1459] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1457 = llvm.load %1460 : !llvm.ptr -> i64
%1461 = llvm.load %1412 : !llvm.ptr -> i32
%1462 = arith.extsi %1461 : i32 to i64
%1463 = llvm.getelementptr %1405[%1462] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1457, %1463 : i64, !llvm.ptr
%1464 = llvm.load %1412 : !llvm.ptr -> i32
%1465 = arith.constant 1 : i32
%1466 = arith.addi %1464, %1465 : i32
llvm.store %1466, %1412 : i32, !llvm.ptr
func.call @free(%1438) : (!llvm.ptr) -> ()
func.call @free(%1443) : (!llvm.ptr) -> ()
%1469 = arith.addi %1437, %1429 : index
cf.br ^bb264(%1469 : index)
^bb266(%1470: index):
%1471 = arith.addi %1425, %1417 : index
cf.br ^bb261(%1471 : index)
^bb263(%1472: index):
%1474 = llvm.load %1412 : !llvm.ptr -> i32
%1475 = arith.extsi %1474 : i32 to i64
%1476 = arith.constant 8 : i32
%1478 = arith.extsi %1476 : i32 to i64
%1477 = arith.muli %1475, %1478 : i64
%1473 = func.call @memcpy(%1336, %1405, %1477) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
%1479 = llvm.load %1412 : !llvm.ptr -> i32
llvm.store %1479, %1343 : i32, !llvm.ptr
%1480 = llvm.load %1352 : !llvm.ptr -> i64
%1481 = llvm.load %1378 : !llvm.ptr -> i64
%1482 = arith.muli %1480, %1481 : i64
llvm.store %1482, %1352 : i64, !llvm.ptr
func.call @free(%1405) : (!llvm.ptr) -> ()
func.call @free(%1395) : (!llvm.ptr) -> ()
%1485 = arith.addi %1367, %1359 : index
cf.br ^bb252(%1485 : index)
^bb254(%1486: index):
%1487 = llvm.load %1355 : !llvm.ptr -> i1
cf.cond_br %1487, ^bb267, ^bb268
^bb267:
%1488 = arith.constant 0 : i32
%1489 = llvm.load %1343 : !llvm.ptr -> i32
%1490 = arith.index_cast %1488 : i32 to index
%1491 = arith.index_cast %1489 : i32 to index
%1493 = arith.constant 1 : index
%1494 = arith.constant -1 : index
%1495 = arith.cmpi sle, %1490, %1491 : index
%1492 = arith.select %1495, %1493, %1494 : index
cf.br ^bb270(%1490 : index)
^bb270(%1496: index):
%1497 = arith.cmpi slt, %1496, %1491 : index
%1498 = arith.cmpi sgt, %1496, %1491 : index
%1499 = arith.select %1495, %1497, %1498 : i1
cf.cond_br %1499, ^bb271(%1496 : index), ^bb272(%1496 : index)
^bb271(%1500: index):
%1502 = arith.index_cast %1500 : index to i64
%1503 = llvm.getelementptr %1336[%1502] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1501 = llvm.load %1503 : !llvm.ptr -> i64
%1504 = llvm.mlir.undef : i64
%1505 = arith.constant 0 : i32
%1507 = arith.extsi %1505 : i32 to i64
%1506 = arith.cmpi eq, %1501, %1507 : i64
cf.cond_br %1506, ^bb273, ^bb274
^bb273:
%1508 = llvm.load %1283 : !llvm.ptr -> i64
cf.br ^bb275(%1508 : i64)
^bb274:
%1509 = arith.constant 2 : i32
%1511 = arith.extsi %1509 : i32 to i64
%1510 = arith.remsi %1501, %1511 : i64
%1512 = arith.constant 1 : i32
%1514 = arith.extsi %1512 : i32 to i64
%1513 = arith.cmpi eq, %1510, %1514 : i64
%1515 = scf.if %1513 -> (i64) {
scf.yield %1501 : i64
} else {
%1516 = llvm.load %1283 : !llvm.ptr -> i64
%1517 = arith.subi %1501, %1516 : i64
scf.yield %1517 : i64
}
cf.br ^bb275(%1515 : i64)
^bb275(%1518: i64):
%1519 = arith.constant 0 : i32
%1521 = arith.extsi %1519 : i32 to i64
%1520 = arith.cmpi slt, %1518, %1521 : i64
%1522 = scf.if %1520 -> (i64) {
%1524 = arith.constant 0 : i64
%1523 = arith.subi %1524, %1518 : i64
scf.yield %1523 : i64
} else {
scf.yield %1518 : i64
}
%1525 = llvm.load %1283 : !llvm.ptr -> i64
%1526 = arith.cmpi sgt, %1522, %1525 : i64
cf.cond_br %1526, ^bb276, ^bb277
^bb276:
%1527 = arith.addi %1500, %1492 : index
cf.br ^bb270(%1527 : index)
^bb277:
cf.br ^bb278
^bb278:
%1528 = arith.muli %1522, %1522 : i64
%1529 = arith.subi %1528, %arg0 : i64
%1530 = arith.constant 4 : i32
%1531 = llvm.load %1283 : !llvm.ptr -> i64
%1533 = arith.extsi %1530 : i32 to i64
%1532 = arith.muli %1533, %1531 : i64
%1534 = arith.remsi %1529, %1532 : i64
%1535 = arith.constant 0 : i32
%1537 = arith.extsi %1535 : i32 to i64
%1536 = arith.cmpi ne, %1534, %1537 : i64
cf.cond_br %1536, ^bb279, ^bb280
^bb279:
%1538 = arith.addi %1500, %1492 : index
cf.br ^bb270(%1538 : index)
^bb280:
cf.br ^bb281
^bb281:
%1539 = arith.divsi %1529, %1532 : i64
%1540 = llvm.load %1283 : !llvm.ptr -> i64
%1541 = arith.cmpi sgt, %1540, %1539 : i64
cf.cond_br %1541, ^bb282, ^bb283
^bb282:
%1542 = arith.addi %1500, %1492 : index
cf.br ^bb270(%1542 : index)
^bb283:
cf.br ^bb284
^bb284:
%1543 = arith.constant 0 : i32
%1545 = arith.extsi %1543 : i32 to i64
%1544 = arith.cmpi slt, %1518, %1545 : i64
%1546 = scf.if %1544 -> (i64) {
%1548 = arith.constant 0 : i64
%1547 = arith.subi %1548, %1518 : i64
scf.yield %1547 : i64
} else {
scf.yield %1518 : i64
}
%1549 = llvm.load %1283 : !llvm.ptr -> i64
%1550 = arith.cmpi eq, %1546, %1549 : i64
%1551 = scf.if %1550 -> (i1) {
%1552 = arith.constant true
scf.yield %1552 : i1
} else {
%1553 = llvm.load %1283 : !llvm.ptr -> i64
%1554 = arith.cmpi eq, %1553, %1539 : i64
scf.yield %1554 : i1
}
%1555 = scf.if %1551 -> (i1) {
%1556 = arith.constant 0 : i32
%1558 = arith.extsi %1556 : i32 to i64
%1557 = arith.cmpi slt, %1518, %1558 : i64
scf.yield %1557 : i1
} else {
%1559 = arith.constant false
scf.yield %1559 : i1
}
cf.cond_br %1555, ^bb285, ^bb286
^bb285:
%1560 = arith.addi %1500, %1492 : index
cf.br ^bb270(%1560 : index)
^bb286:
cf.br ^bb287
^bb287:
%1561 = llvm.load %1279 : !llvm.ptr -> i64
%1562 = arith.constant 1 : i32
%1564 = arith.extsi %1562 : i32 to i64
%1563 = arith.addi %1561, %1564 : i64
llvm.store %1563, %1279 : i64, !llvm.ptr
%1565 = arith.addi %1500, %1492 : index
cf.br ^bb270(%1565 : index)
^bb272(%1566: index):
cf.br ^bb269
^bb268:
cf.br ^bb269
^bb269:
func.call @free(%1336) : (!llvm.ptr) -> ()
cf.br ^bb251
^bb250:
cf.br ^bb251
^bb251:
func.call @free(%1286) : (!llvm.ptr) -> ()
func.call @free(%1291) : (!llvm.ptr) -> ()
%1570 = llvm.load %1283 : !llvm.ptr -> i64
%1571 = arith.constant 2 : i32
%1573 = arith.extsi %1571 : i32 to i64
%1572 = arith.addi %1570, %1573 : i64
llvm.store %1572, %1283 : i64, !llvm.ptr
cf.br ^bb240
^bb242:
func.call @free(%1268) : (!llvm.ptr) -> ()
%1575 = llvm.load %1279 : !llvm.ptr -> i64
func.return %1575 : i64
}
func.func @main() -> i32 {
%1576 = arith.constant 17526 : i32
%1577 = arith.extsi %1576 : i32 to i64
%1578 = arith.constant 1000000000 : i32
%1580 = arith.extsi %1578 : i32 to i64
%1579 = arith.muli %1577, %1580 : i64
%1581 = arith.constant 8 : i32
%1583 = arith.extsi %1581 : i32 to i64
%1582 = arith.muli %1583, %1579 : i64
%1584 = arith.constant 3 : i32
%1586 = arith.extsi %1584 : i32 to i64
%1585 = arith.addi %1582, %1586 : i64
%1588 = arith.constant 20 : i32
%1589 = arith.constant 8 : i32
%1590 = arith.extsi %1588 : i32 to i64
%1591 = arith.extsi %1589 : i32 to i64
%1587 = func.call @calloc(%1590, %1591) : (i64, i64) -> !llvm.ptr
%1593 = arith.constant 20 : i32
%1594 = arith.constant 4 : i32
%1595 = arith.extsi %1593 : i32 to i64
%1596 = arith.extsi %1594 : i32 to i64
%1592 = func.call @calloc(%1595, %1596) : (i64, i64) -> !llvm.ptr
%1597 = func.call @factorize_ll(%1585, %1587, %1592) : (i64, !llvm.ptr, !llvm.ptr) -> i32
%1598 = arith.constant 1 : i32
%1599 = arith.extsi %1598 : i32 to i64
%1600 = llvm.mlir.constant(1 : i64) : i64
%1601 = llvm.alloca %1600 x i64 : (i64) -> !llvm.ptr
llvm.store %1599, %1601 : i64, !llvm.ptr
%1602 = arith.constant 1 : i32
%1603 = arith.extsi %1602 : i32 to i64
%1604 = llvm.mlir.constant(1 : i64) : i64
%1605 = llvm.alloca %1604 x i64 : (i64) -> !llvm.ptr
llvm.store %1603, %1605 : i64, !llvm.ptr
%1606 = arith.constant 0 : i32
%1607 = arith.index_cast %1606 : i32 to index
%1608 = arith.index_cast %1597 : i32 to index
%1610 = arith.constant 1 : index
%1611 = arith.constant -1 : index
%1612 = arith.cmpi sle, %1607, %1608 : index
%1609 = arith.select %1612, %1610, %1611 : index
cf.br ^bb288(%1607 : index)
^bb288(%1613: index):
%1614 = arith.cmpi slt, %1613, %1608 : index
%1615 = arith.cmpi sgt, %1613, %1608 : index
%1616 = arith.select %1612, %1614, %1615 : i1
cf.cond_br %1616, ^bb289(%1613 : index), ^bb290(%1613 : index)
^bb289(%1617: index):
%1619 = arith.index_cast %1617 : index to i64
%1620 = llvm.getelementptr %1592[%1619] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1618 = llvm.load %1620 : !llvm.ptr -> i32
%1621 = arith.constant 2 : i32
%1622 = arith.remsi %1618, %1621 : i32
%1623 = arith.constant 1 : i32
%1624 = arith.cmpi eq, %1622, %1623 : i32
cf.cond_br %1624, ^bb291, ^bb292
^bb291:
%1625 = llvm.load %1601 : !llvm.ptr -> i64
%1627 = arith.index_cast %1617 : index to i64
%1628 = llvm.getelementptr %1587[%1627] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1626 = llvm.load %1628 : !llvm.ptr -> i64
%1629 = arith.muli %1625, %1626 : i64
llvm.store %1629, %1601 : i64, !llvm.ptr
cf.br ^bb293
^bb292:
cf.br ^bb293
^bb293:
%1630 = arith.constant 0 : i32
%1632 = arith.index_cast %1617 : index to i64
%1633 = llvm.getelementptr %1592[%1632] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1631 = llvm.load %1633 : !llvm.ptr -> i32
%1634 = arith.constant 2 : i32
%1635 = arith.divsi %1631, %1634 : i32
%1636 = arith.index_cast %1630 : i32 to index
%1637 = arith.index_cast %1635 : i32 to index
%1639 = arith.constant 1 : index
%1640 = arith.constant -1 : index
%1641 = arith.cmpi sle, %1636, %1637 : index
%1638 = arith.select %1641, %1639, %1640 : index
cf.br ^bb294(%1636 : index)
^bb294(%1642: index):
%1643 = arith.cmpi slt, %1642, %1637 : index
%1644 = arith.cmpi sgt, %1642, %1637 : index
%1645 = arith.select %1641, %1643, %1644 : i1
cf.cond_br %1645, ^bb295(%1642 : index), ^bb296(%1642 : index)
^bb295(%1646: index):
%1647 = llvm.load %1605 : !llvm.ptr -> i64
%1649 = arith.index_cast %1617 : index to i64
%1650 = llvm.getelementptr %1587[%1649] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1648 = llvm.load %1650 : !llvm.ptr -> i64
%1651 = arith.muli %1647, %1648 : i64
llvm.store %1651, %1605 : i64, !llvm.ptr
%1652 = arith.addi %1646, %1638 : index
cf.br ^bb294(%1652 : index)
^bb296(%1653: index):
%1654 = arith.addi %1617, %1609 : index
cf.br ^bb288(%1654 : index)
^bb290(%1655: index):
%1656 = llvm.load %1601 : !llvm.ptr -> i64
%1658 = arith.constant 0 : i64
%1657 = arith.subi %1658, %1656 : i64
%1659 = func.call @class_number(%1657) : (i64) -> i64
%1660 = arith.constant 1 : i32
%1661 = arith.extsi %1660 : i32 to i64
%1662 = llvm.mlir.constant(1 : i64) : i64
%1663 = llvm.alloca %1662 x i64 : (i64) -> !llvm.ptr
llvm.store %1661, %1663 : i64, !llvm.ptr
%1664 = arith.constant 3 : i32
%1666 = arith.constant 0 : i32
%1665 = arith.subi %1666, %1664 : i32
%1668 = arith.extsi %1665 : i32 to i64
%1667 = arith.cmpi eq, %1657, %1668 : i64
cf.cond_br %1667, ^bb297, ^bb298
^bb297:
%1669 = arith.constant 3 : i32
%1670 = arith.extsi %1669 : i32 to i64
llvm.store %1670, %1663 : i64, !llvm.ptr
cf.br ^bb299
^bb298:
%1671 = arith.constant 4 : i32
%1673 = arith.constant 0 : i32
%1672 = arith.subi %1673, %1671 : i32
%1675 = arith.extsi %1672 : i32 to i64
%1674 = arith.cmpi eq, %1657, %1675 : i64
cf.cond_br %1674, ^bb300, ^bb301
^bb300:
%1676 = arith.constant 2 : i32
%1677 = arith.extsi %1676 : i32 to i64
llvm.store %1677, %1663 : i64, !llvm.ptr
cf.br ^bb302
^bb301:
cf.br ^bb302
^bb302:
cf.br ^bb299
^bb299:
%1679 = arith.constant 20 : i32
%1680 = arith.constant 8 : i32
%1681 = arith.extsi %1679 : i32 to i64
%1682 = arith.extsi %1680 : i32 to i64
%1678 = func.call @calloc(%1681, %1682) : (i64, i64) -> !llvm.ptr
%1684 = arith.constant 20 : i32
%1685 = arith.constant 4 : i32
%1686 = arith.extsi %1684 : i32 to i64
%1687 = arith.extsi %1685 : i32 to i64
%1683 = func.call @calloc(%1686, %1687) : (i64, i64) -> !llvm.ptr
%1689 = llvm.load %1605 : !llvm.ptr -> i64
%1688 = func.call @factorize_ll(%1689, %1678, %1683) : (i64, !llvm.ptr, !llvm.ptr) -> i32
%1690 = arith.constant 0 : i32
%1691 = arith.extsi %1690 : i32 to i64
%1692 = llvm.mlir.constant(1 : i64) : i64
%1693 = llvm.alloca %1692 x i64 : (i64) -> !llvm.ptr
llvm.store %1691, %1693 : i64, !llvm.ptr
%1694 = arith.constant 0 : i32
%1695 = arith.constant 1 : i32
%1696 = arith.shli %1695, %1688 : i32
%1697 = arith.index_cast %1694 : i32 to index
%1698 = arith.index_cast %1696 : i32 to index
%1700 = arith.constant 1 : index
%1701 = arith.constant -1 : index
%1702 = arith.cmpi sle, %1697, %1698 : index
%1699 = arith.select %1702, %1700, %1701 : index
cf.br ^bb303(%1697 : index)
^bb303(%1703: index):
%1704 = arith.cmpi slt, %1703, %1698 : index
%1705 = arith.cmpi sgt, %1703, %1698 : index
%1706 = arith.select %1702, %1704, %1705 : i1
cf.cond_br %1706, ^bb304(%1703 : index), ^bb305(%1703 : index)
^bb304(%1707: index):
%1708 = arith.constant 0 : i32
%1709 = llvm.mlir.constant(1 : i64) : i64
%1710 = llvm.alloca %1709 x i32 : (i64) -> !llvm.ptr
llvm.store %1708, %1710 : i32, !llvm.ptr
%1711 = arith.constant 1 : i32
%1712 = arith.extsi %1711 : i32 to i64
%1713 = llvm.mlir.constant(1 : i64) : i64
%1714 = llvm.alloca %1713 x i64 : (i64) -> !llvm.ptr
llvm.store %1712, %1714 : i64, !llvm.ptr
%1715 = arith.constant 1 : i32
%1716 = arith.extsi %1715 : i32 to i64
%1717 = llvm.mlir.constant(1 : i64) : i64
%1718 = llvm.alloca %1717 x i64 : (i64) -> !llvm.ptr
llvm.store %1716, %1718 : i64, !llvm.ptr
%1719 = arith.constant 1 : i1
%1720 = llvm.mlir.constant(1 : i64) : i64
%1721 = llvm.alloca %1720 x i1 : (i64) -> !llvm.ptr
llvm.store %1719, %1721 : i1, !llvm.ptr
%1722 = arith.constant 0 : i32
%1723 = arith.index_cast %1722 : i32 to index
%1724 = arith.index_cast %1688 : i32 to index
%1726 = arith.constant 1 : index
%1727 = arith.constant -1 : index
%1728 = arith.cmpi sle, %1723, %1724 : index
%1725 = arith.select %1728, %1726, %1727 : index
cf.br ^bb306(%1723 : index)
^bb306(%1729: index):
%1730 = arith.cmpi slt, %1729, %1724 : index
%1731 = arith.cmpi sgt, %1729, %1724 : index
%1732 = arith.select %1728, %1730, %1731 : i1
cf.cond_br %1732, ^bb307(%1729 : index), ^bb308(%1729 : index)
^bb307(%1733: index):
%1735 = arith.index_cast %1733 : index to i64
%1736 = llvm.getelementptr %1678[%1735] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1734 = llvm.load %1736 : !llvm.ptr -> i64
%1738 = arith.index_cast %1733 : index to i64
%1739 = llvm.getelementptr %1683[%1738] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1737 = llvm.load %1739 : !llvm.ptr -> i32
%1740 = llvm.mlir.constant(1 : i64) : i64
%1741 = llvm.alloca %1740 x i32 : (i64) -> !llvm.ptr
llvm.store %1737, %1741 : i32, !llvm.ptr
%1742 = arith.shrsi %1707, %1733 : index
%1743 = arith.constant 1 : i32
%1745 = arith.index_cast %1742 : index to i32
%1744 = arith.andi %1745, %1743 : i32
%1746 = arith.constant 1 : i32
%1747 = arith.cmpi eq, %1744, %1746 : i32
cf.cond_br %1747, ^bb309, ^bb310
^bb309:
%1748 = llvm.load %1710 : !llvm.ptr -> i32
%1749 = arith.constant 1 : i32
%1750 = arith.addi %1748, %1749 : i32
llvm.store %1750, %1710 : i32, !llvm.ptr
%1751 = llvm.load %1714 : !llvm.ptr -> i64
%1752 = func.call @legendre(%1657, %1734) : (i64, i64) -> i32
%1753 = arith.extsi %1752 : i32 to i64
%1754 = arith.muli %1751, %1753 : i64
llvm.store %1754, %1714 : i64, !llvm.ptr
%1755 = llvm.load %1741 : !llvm.ptr -> i32
%1756 = arith.constant 1 : i32
%1757 = arith.subi %1755, %1756 : i32
llvm.store %1757, %1741 : i32, !llvm.ptr
cf.br ^bb311
^bb310:
cf.br ^bb311
^bb311:
%1758 = llvm.load %1741 : !llvm.ptr -> i32
%1759 = arith.constant 0 : i32
%1760 = arith.cmpi slt, %1758, %1759 : i32
cf.cond_br %1760, ^bb312, ^bb313
^bb312:
%1761 = arith.constant 0 : i32
%1762 = arith.extsi %1761 : i32 to i64
llvm.store %1762, %1718 : i64, !llvm.ptr
%1763 = arith.constant 0 : i1
llvm.store %1763, %1721 : i1, !llvm.ptr
cf.br ^bb308(%1733 : index)
^bb313:
cf.br ^bb314
^bb314:
%1764 = arith.constant 1 : i32
%1765 = arith.extsi %1764 : i32 to i64
%1766 = llvm.mlir.constant(1 : i64) : i64
%1767 = llvm.alloca %1766 x i64 : (i64) -> !llvm.ptr
llvm.store %1765, %1767 : i64, !llvm.ptr
%1768 = arith.constant 0 : i32
%1769 = llvm.load %1741 : !llvm.ptr -> i32
%1770 = arith.constant 1 : i32
%1771 = arith.addi %1769, %1770 : i32
%1772 = arith.index_cast %1768 : i32 to index
%1773 = arith.index_cast %1771 : i32 to index
%1775 = arith.constant 1 : index
%1776 = arith.constant -1 : index
%1777 = arith.cmpi sle, %1772, %1773 : index
%1774 = arith.select %1777, %1775, %1776 : index
cf.br ^bb315(%1772 : index)
^bb315(%1778: index):
%1779 = arith.cmpi slt, %1778, %1773 : index
%1780 = arith.cmpi sgt, %1778, %1773 : index
%1781 = arith.select %1777, %1779, %1780 : i1
cf.cond_br %1781, ^bb316(%1778 : index), ^bb317(%1778 : index)
^bb316(%1782: index):
%1783 = llvm.load %1767 : !llvm.ptr -> i64
%1784 = arith.muli %1783, %1734 : i64
llvm.store %1784, %1767 : i64, !llvm.ptr
%1785 = arith.addi %1782, %1774 : index
cf.br ^bb315(%1785 : index)
^bb317(%1786: index):
%1787 = llvm.load %1718 : !llvm.ptr -> i64
%1788 = llvm.load %1767 : !llvm.ptr -> i64
%1789 = arith.constant 1 : i32
%1791 = arith.extsi %1789 : i32 to i64
%1790 = arith.subi %1788, %1791 : i64
%1792 = arith.muli %1787, %1790 : i64
%1793 = arith.constant 1 : i32
%1795 = arith.extsi %1793 : i32 to i64
%1794 = arith.subi %1734, %1795 : i64
%1796 = arith.divsi %1792, %1794 : i64
llvm.store %1796, %1718 : i64, !llvm.ptr
%1797 = arith.addi %1733, %1725 : index
cf.br ^bb306(%1797 : index)
^bb308(%1798: index):
%1799 = llvm.load %1721 : !llvm.ptr -> i1
%1801 = arith.constant 1 : i1
%1800 = arith.xori %1799, %1801 : i1
%1803 = scf.if %1800 -> (i1) {
%1804 = arith.constant true
scf.yield %1804 : i1
} else {
%1805 = llvm.load %1718 : !llvm.ptr -> i64
%1806 = arith.constant 0 : i32
%1808 = arith.extsi %1806 : i32 to i64
%1807 = arith.cmpi eq, %1805, %1808 : i64
scf.yield %1807 : i1
}
cf.cond_br %1803, ^bb318, ^bb319
^bb318:
%1809 = arith.addi %1707, %1699 : index
cf.br ^bb303(%1809 : index)
^bb319:
cf.br ^bb320
^bb320:
%1810 = llvm.load %1710 : !llvm.ptr -> i32
%1811 = arith.constant 2 : i32
%1812 = arith.remsi %1810, %1811 : i32
%1813 = arith.constant 1 : i32
%1814 = arith.cmpi eq, %1812, %1813 : i32
%1815 = scf.if %1814 -> (i32) {
%1816 = arith.constant 1 : i32
%1818 = arith.constant 0 : i32
%1817 = arith.subi %1818, %1816 : i32
scf.yield %1817 : i32
} else {
%1819 = arith.constant 1 : i32
scf.yield %1819 : i32
}
%1820 = arith.extsi %1815 : i32 to i64
%1821 = llvm.load %1693 : !llvm.ptr -> i64
%1822 = llvm.load %1714 : !llvm.ptr -> i64
%1823 = arith.muli %1820, %1822 : i64
%1824 = llvm.load %1718 : !llvm.ptr -> i64
%1825 = arith.muli %1823, %1824 : i64
%1826 = arith.addi %1821, %1825 : i64
llvm.store %1826, %1693 : i64, !llvm.ptr
%1827 = arith.addi %1707, %1699 : index
cf.br ^bb303(%1827 : index)
^bb305(%1828: index):
%1829 = arith.constant 3 : i32
%1831 = arith.extsi %1829 : i32 to i64
%1830 = arith.muli %1831, %1659 : i64
%1832 = llvm.load %1693 : !llvm.ptr -> i64
%1833 = arith.muli %1830, %1832 : i64
%1834 = llvm.load %1663 : !llvm.ptr -> i64
%1835 = arith.divsi %1833, %1834 : i64
%1836 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1837 = llvm.call @printf(%1836, %1835) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%1587) : (!llvm.ptr) -> ()
func.call @free(%1592) : (!llvm.ptr) -> ()
func.call @free(%1678) : (!llvm.ptr) -> ()
func.call @free(%1683) : (!llvm.ptr) -> ()
%1842 = arith.constant 0 : i32
func.return %1842 : i32
}
}