← All problems Problem 585
Nested Square Roots F(n)=A(n)+(C1(n)-C3(n))/2 with primitive-pair phi via totient.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^4)O(n log log n)Space complexity O(n^2)O(n)Approach Flow solution Sieve-based totient computation Verdict Suboptimal
Flow source
# Project Euler 585
# Nested Square Roots
# F(n)=A(n)+(C1(n)-C3(n))/2 with primitive-pair phi via totient.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function sqrt(x: f64) -> f64
}
function gcd(a0: i64, b0: i64) -> i64 {
let mut a: i64 = a0
let mut b: i64 = b0
while b != 0 {
let t: i64 = a % b
a = b
b = t
}
return a
}
function isqrt(n: i64) -> i64 {
if n <= 0 { return 0 }
let r: i64 = sqrt(n as f64) as i64
while r > 0 && r * r > n { r = r - 1 }
while (r + 1) * (r + 1) <= n { r = r + 1 }
return r
}
function grouped_sum_floor(n: i64, Sphi: ptr<i64>) -> i64 {
let mut res: i64 = 0
let mut i: i64 = 1
while i <= n {
let q: i64 = n / i
let j: i64 = n / q
res = res + q * (Sphi[j] - Sphi[i - 1])
i = j + 1
}
return res
}
function compute_C3(n: i64) -> i64 {
let lim: i64 = isqrt(n)
let is_sf: ptr<i8> = calloc(lim + 1, 1)
if is_sf == null { return -1 }
let mut i: i64 = 0
while i <= lim {
is_sf[i] = 1
i = i + 1
}
is_sf[0] = 0
let r: i64 = isqrt(lim)
let mut p: i64 = 2
while p <= r {
let sq: i64 = p * p
let mut k: i64 = sq
while k <= lim {
is_sf[k] = 0
k = k + sq
}
p = p + 1
}
let mut cnt3: i64 = 0
let mut pp: i64 = 1
while pp < lim {
if (pp + 1) * (pp + 1) > n { break }
if is_sf[pp] != 0 {
let mut q: i64 = 1
while q <= lim {
if is_sf[q] != 0 && gcd(pp, q) == 1 {
if (pp * q + 1) * (pp + q) > n { break }
let pq: i64 = pp * q
let mut rr: i64 = 1
while rr <= lim {
if is_sf[rr] != 0 && gcd(pq, rr) == 1 {
if (pq + rr) * (pp * rr + q) > n { break }
let pr: i64 = pp * rr
let pqr: i64 = pq * rr
let mut s: i64 = 1
while s <= lim {
if is_sf[s] != 0 && gcd(pqr, s) == 1 {
if (pq + rr * s) * (pr + q * s) > n { break }
let u: i64 = pq
let v: i64 = rr * s
let aa: i64 = pr
let bb: i64 = q * s
if u != v && aa != bb {
let ab_sum: i64 = aa + bb
let mut w1: i64 = 1
while (u * w1 * w1 + v) * ab_sum <= n {
let u_w1: i64 = u * w1
let u_w1_sq: i64 = u_w1 * w1
let mut w2: i64 = 1
while (u_w1_sq + v * w2 * w2) * ab_sum <= n {
let v_w2: i64 = v * w2
let s1: i64 = u_w1_sq + v_w2 * w2
let mut w3: i64 = 1
while s1 * (aa * w3 * w3 + bb) <= n {
let a_w3: i64 = aa * w3
let a_w3_sq: i64 = a_w3 * w3
let mut w4: i64 = 1
while s1 * (a_w3_sq + bb * w4 * w4) <= n {
let b_w4: i64 = bb * w4
let s2: i64 = a_w3_sq + b_w4 * w4
if u_w1_sq > v_w2 * w2 && a_w3_sq > b_w4 * w4 {
if gcd(u_w1, v_w2) == 1 && gcd(a_w3, b_w4) == 1 {
cnt3 = cnt3 + (n / s1) / s2
}
}
w4 = w4 + 1
}
w3 = w3 + 1
}
w2 = w2 + 1
}
w1 = w1 + 1
}
}
}
s = s + 1
}
}
rr = rr + 1
}
}
q = q + 1
}
}
pp = pp + 1
}
free(is_sf)
return cnt3
}
function F(n: i64) -> i64 {
let tot: ptr<i32> = calloc(n + 1, 4)
let is_comp: ptr<i8> = calloc(n + 1, 1)
let primes: ptr<i32> = calloc(n / 5 + 10, 4)
if tot == null || is_comp == null || primes == null { return -1 }
let mut np: i64 = 0
tot[1] = 1
let mut i: i64 = 2
while i <= n {
if is_comp[i] == 0 {
primes[np] = i as i32
np = np + 1
tot[i] = (i - 1) as i32
}
let mut j: i64 = 0
while j < np {
let p: i64 = primes[j] as i64
let ip: i64 = i * p
if ip > n { break }
is_comp[ip] = 1
if i % p == 0 {
tot[ip] = (tot[i] as i64 * p) as i32
break
} else {
tot[ip] = (tot[i] as i64 * (p - 1)) as i32
}
j = j + 1
}
i = i + 1
}
let phi: ptr<i32> = calloc(n + 1, 4)
if phi == null { return -1 }
i = 3
while i <= n {
phi[i] = (tot[i] as i64 / 2) as i32
i = i + 1
}
let lim: i64 = isqrt(n)
let mut a: i64 = 2
while a <= lim {
let a2: i64 = a * a
let maxb: i64 = isqrt(n - a2)
let mut b: i64 = 1
let bmax: i64 = a
if maxb + 1 < bmax { bmax = maxb + 1 }
while b < bmax {
if gcd(a, b) == 1 {
phi[a2 + b * b] = phi[a2 + b * b] - 1
}
b = b + 1
}
a = a + 1
}
let Sphi: ptr<i64> = calloc(n + 1, 8)
if Sphi == null { return -1 }
let mut acc: i64 = 0
i = 0
while i <= n {
acc = acc + (phi[i] as i64)
Sphi[i] = acc
i = i + 1
}
let A: i64 = grouped_sum_floor(n, Sphi)
# C1 with memo on floor values via open addressing
let CAP: i64 = 200003
let ckey: ptr<i64> = calloc(CAP, 8)
let cval: ptr<i64> = calloc(CAP, 8)
let cused: ptr<i8> = calloc(CAP, 1)
if ckey == null || cval == null || cused == null { return -1 }
let mut C1: i64 = 0
i = 1
while i <= n {
let q: i64 = n / i
let j: i64 = n / q
let sum_phi: i64 = Sphi[j] - Sphi[i - 1]
# P(q)
let mut h: i64 = q % CAP
if h < 0 { h = -h }
let mut Pq: i64 = 0
let mut found: i32 = 0
let mut probes: i64 = 0
while probes < 10000 {
if cused[h] == 0 {
Pq = grouped_sum_floor(q, Sphi)
cused[h] = 1
ckey[h] = q
cval[h] = Pq
found = 1
break
}
if ckey[h] == q {
Pq = cval[h]
found = 1
break
}
h = h + 1
if h >= CAP { h = 0 }
probes = probes + 1
}
if found == 0 { Pq = grouped_sum_floor(q, Sphi) }
C1 = C1 + sum_phi * Pq
i = j + 1
}
let C3: i64 = compute_C3(n)
free(tot)
free(is_comp)
free(primes)
free(phi)
free(Sphi)
free(ckey)
free(cval)
free(cused)
return A + (C1 - C3) / 2
}
function main() -> i32 {
printf("%lld\n", F(5000000))
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 isqrt_i64(int64_t n);
int64_t grouped_sum_floor_i64_ptr_i64(int64_t n, int64_t* Sphi);
int64_t compute_C3_i64(int64_t n);
int64_t F_i64(int64_t n);
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 isqrt_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t r = ((int64_t)(sqrt(((double)(n)))));
while ((r > 0 && (r * r) > n)) {
r = (r - 1);
}
while (((r + 1) * (r + 1)) <= n) {
r = (r + 1);
}
return r;
}
int64_t grouped_sum_floor_i64_ptr_i64(int64_t n, int64_t* Sphi) {
int64_t res = 0;
int64_t i = 1;
while (i <= n) {
int64_t q = FLOW_CHECKED_DIV((n), (i));
int64_t j = FLOW_CHECKED_DIV((n), (q));
res = (res + (q * (Sphi[j] - Sphi[(i - 1)])));
i = (j + 1);
}
return res;
}
int64_t compute_C3_i64(int64_t n) {
int64_t lim = isqrt_i64(n);
int8_t* is_sf = (int8_t*)(calloc((lim + 1), 1));
if (is_sf == NULL) {
return (-1);
}
int64_t i = 0;
while (i <= lim) {
is_sf[i] = 1;
i = (i + 1);
}
is_sf[0] = 0;
int64_t r = isqrt_i64(lim);
int64_t p = 2;
while (p <= r) {
int64_t sq = (p * p);
int64_t k = sq;
while (k <= lim) {
is_sf[k] = 0;
k = (k + sq);
}
p = (p + 1);
}
int64_t cnt3 = 0;
int64_t pp = 1;
while (pp < lim) {
if (((pp + 1) * (pp + 1)) > n) {
break;
}
if (is_sf[pp] != 0) {
int64_t q = 1;
while (q <= lim) {
if ((is_sf[q] != 0 && gcd_i64_i64(pp, q) == 1)) {
if ((((pp * q) + 1) * (pp + q)) > n) {
break;
}
int64_t pq = (pp * q);
int64_t rr = 1;
while (rr <= lim) {
if ((is_sf[rr] != 0 && gcd_i64_i64(pq, rr) == 1)) {
if (((pq + rr) * ((pp * rr) + q)) > n) {
break;
}
int64_t pr = (pp * rr);
int64_t pqr = (pq * rr);
int64_t s = 1;
while (s <= lim) {
if ((is_sf[s] != 0 && gcd_i64_i64(pqr, s) == 1)) {
if (((pq + (rr * s)) * (pr + (q * s))) > n) {
break;
}
int64_t u = pq;
int64_t v = (rr * s);
int64_t aa = pr;
int64_t bb = (q * s);
if ((u != v && aa != bb)) {
int64_t ab_sum = (aa + bb);
int64_t w1 = 1;
while (((((u * w1) * w1) + v) * ab_sum) <= n) {
int64_t u_w1 = (u * w1);
int64_t u_w1_sq = (u_w1 * w1);
int64_t w2 = 1;
while (((u_w1_sq + ((v * w2) * w2)) * ab_sum) <= n) {
int64_t v_w2 = (v * w2);
int64_t s1 = (u_w1_sq + (v_w2 * w2));
int64_t w3 = 1;
while ((s1 * (((aa * w3) * w3) + bb)) <= n) {
int64_t a_w3 = (aa * w3);
int64_t a_w3_sq = (a_w3 * w3);
int64_t w4 = 1;
while ((s1 * (a_w3_sq + ((bb * w4) * w4))) <= n) {
int64_t b_w4 = (bb * w4);
int64_t s2 = (a_w3_sq + (b_w4 * w4));
if ((u_w1_sq > (v_w2 * w2) && a_w3_sq > (b_w4 * w4))) {
if ((gcd_i64_i64(u_w1, v_w2) == 1 && gcd_i64_i64(a_w3, b_w4) == 1)) {
cnt3 = (cnt3 + FLOW_CHECKED_DIV((FLOW_CHECKED_DIV((n), (s1))), (s2)));
}
}
w4 = (w4 + 1);
}
w3 = (w3 + 1);
}
w2 = (w2 + 1);
}
w1 = (w1 + 1);
}
}
}
s = (s + 1);
}
}
rr = (rr + 1);
}
}
q = (q + 1);
}
}
pp = (pp + 1);
}
free(is_sf);
return cnt3;
}
int64_t F_i64(int64_t n) {
int32_t* tot = (int32_t*)(calloc((n + 1), 4));
int8_t* is_comp = (int8_t*)(calloc((n + 1), 1));
int32_t* primes = (int32_t*)(calloc((FLOW_CHECKED_DIV((n), (5)) + 10), 4));
if (((tot == NULL || is_comp == NULL) || primes == NULL)) {
return (-1);
}
int64_t np = 0;
tot[1] = 1;
int64_t i = 2;
while (i <= n) {
if (is_comp[i] == 0) {
primes[np] = ((int32_t)(i));
np = (np + 1);
tot[i] = ((int32_t)((i - 1)));
}
int64_t j = 0;
while (j < np) {
int64_t p = ((int64_t)(primes[j]));
int64_t ip = (i * p);
if (ip > n) {
break;
}
is_comp[ip] = 1;
if (FLOW_CHECKED_MOD((i), (p)) == 0) {
tot[ip] = ((int32_t)((((int64_t)(tot[i])) * p)));
break;
} else {
tot[ip] = ((int32_t)((((int64_t)(tot[i])) * (p - 1))));
}
j = (j + 1);
}
i = (i + 1);
}
int32_t* phi = (int32_t*)(calloc((n + 1), 4));
if (phi == NULL) {
return (-1);
}
i = 3;
while (i <= n) {
phi[i] = ((int32_t)(FLOW_CHECKED_DIV((((int64_t)(tot[i]))), (2))));
i = (i + 1);
}
int64_t lim = isqrt_i64(n);
int64_t a = 2;
while (a <= lim) {
int64_t a2 = (a * a);
int64_t maxb = isqrt_i64((n - a2));
int64_t b = 1;
int64_t bmax = a;
if ((maxb + 1) < bmax) {
bmax = (maxb + 1);
}
while (b < bmax) {
if (gcd_i64_i64(a, b) == 1) {
phi[(a2 + (b * b))] = (phi[(a2 + (b * b))] - 1);
}
b = (b + 1);
}
a = (a + 1);
}
int64_t* Sphi = (int64_t*)(calloc((n + 1), 8));
if (Sphi == NULL) {
return (-1);
}
int64_t acc = 0;
i = 0;
while (i <= n) {
acc = (acc + ((int64_t)(phi[i])));
Sphi[i] = acc;
i = (i + 1);
}
int64_t A = grouped_sum_floor_i64_ptr_i64(n, Sphi);
int64_t CAP = 200003;
int64_t* ckey = (int64_t*)(calloc(CAP, 8));
int64_t* cval = (int64_t*)(calloc(CAP, 8));
int8_t* cused = (int8_t*)(calloc(CAP, 1));
if (((ckey == NULL || cval == NULL) || cused == NULL)) {
return (-1);
}
int64_t C1 = 0;
i = 1;
while (i <= n) {
int64_t q = FLOW_CHECKED_DIV((n), (i));
int64_t j = FLOW_CHECKED_DIV((n), (q));
int64_t sum_phi = (Sphi[j] - Sphi[(i - 1)]);
int64_t h = FLOW_CHECKED_MOD((q), (CAP));
if (h < 0) {
h = (-h);
}
int64_t Pq = 0;
int32_t found = 0;
int64_t probes = 0;
while (probes < 10000) {
if (cused[h] == 0) {
Pq = grouped_sum_floor_i64_ptr_i64(q, Sphi);
cused[h] = 1;
ckey[h] = q;
cval[h] = Pq;
found = 1;
break;
}
if (ckey[h] == q) {
Pq = cval[h];
found = 1;
break;
}
h = (h + 1);
if (h >= CAP) {
h = 0;
}
probes = (probes + 1);
}
if (found == 0) {
Pq = grouped_sum_floor_i64_ptr_i64(q, Sphi);
}
C1 = (C1 + (sum_phi * Pq));
i = (j + 1);
}
int64_t C3 = compute_C3_i64(n);
free(tot);
free(is_comp);
free(primes);
free(phi);
free(Sphi);
free(ckey);
free(cval);
free(cused);
return (A + FLOW_CHECKED_DIV(((C1 - C3)), (2)));
}
int32_t main(void) {
printf("%lld\n", F_i64(5000000));
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @sqrt(f64) -> f64
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 @isqrt(%arg0: i64) -> i64 {
%13 = arith.constant 0 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.cmpi sle, %arg0, %15 : i64
cf.cond_br %14, ^bb3, ^bb4
^bb3:
%16 = arith.constant 0 : i32
%17 = arith.extsi %16 : i32 to i64
func.return %17 : i64
^bb4:
cf.br ^bb5
^bb5:
%18 = arith.sitofp %arg0 : i64 to f64
%19 = math.sqrt %18 : f64
%20 = arith.fptosi %19 : f64 to i64
cf.br ^bb6(%20 : i64)
^bb6(%21: i64):
%22 = arith.constant 0 : i32
%24 = arith.extsi %22 : i32 to i64
%23 = arith.cmpi sgt, %21, %24 : i64
%25 = scf.if %23 -> (i1) {
%26 = arith.muli %21, %21 : i64
%27 = arith.cmpi sgt, %26, %arg0 : i64
scf.yield %27 : i1
} else {
%28 = arith.constant false
scf.yield %28 : i1
}
cf.cond_br %25, ^bb7(%21 : i64), ^bb8(%21 : i64)
^bb7(%29: i64):
%30 = arith.constant 1 : i32
%32 = arith.extsi %30 : i32 to i64
%31 = arith.subi %29, %32 : i64
cf.br ^bb6(%31 : i64)
^bb8(%33: i64):
cf.br ^bb9(%33 : i64)
^bb9(%34: i64):
%35 = arith.constant 1 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.addi %34, %37 : i64
%38 = arith.constant 1 : i32
%40 = arith.extsi %38 : i32 to i64
%39 = arith.addi %34, %40 : i64
%41 = arith.muli %36, %39 : i64
%42 = arith.cmpi sle, %41, %arg0 : i64
cf.cond_br %42, ^bb10(%34 : i64), ^bb11(%34 : i64)
^bb10(%43: i64):
%44 = arith.constant 1 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.addi %43, %46 : i64
cf.br ^bb9(%45 : i64)
^bb11(%47: i64):
func.return %47 : i64
}
func.func @grouped_sum_floor(%arg0: i64, %arg1: !llvm.ptr) -> i64 {
%48 = arith.constant 0 : i32
%49 = arith.extsi %48 : i32 to i64
%50 = llvm.mlir.constant(1 : i64) : i64
%51 = llvm.alloca %50 x i64 : (i64) -> !llvm.ptr
llvm.store %49, %51 : i64, !llvm.ptr
%52 = arith.constant 1 : i32
%53 = arith.extsi %52 : i32 to i64
%54 = llvm.mlir.constant(1 : i64) : i64
%55 = llvm.alloca %54 x i64 : (i64) -> !llvm.ptr
llvm.store %53, %55 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%56 = llvm.load %55 : !llvm.ptr -> i64
%57 = arith.cmpi sle, %56, %arg0 : i64
cf.cond_br %57, ^bb13, ^bb14
^bb13:
%58 = llvm.load %55 : !llvm.ptr -> i64
%59 = arith.divsi %arg0, %58 : i64
%60 = arith.divsi %arg0, %59 : i64
%61 = llvm.load %51 : !llvm.ptr -> i64
%63 = llvm.getelementptr %arg1[%60] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%62 = llvm.load %63 : !llvm.ptr -> i64
%65 = llvm.load %55 : !llvm.ptr -> i64
%66 = arith.constant 1 : i32
%68 = arith.extsi %66 : i32 to i64
%67 = arith.subi %65, %68 : i64
%69 = llvm.getelementptr %arg1[%67] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%64 = llvm.load %69 : !llvm.ptr -> i64
%70 = arith.subi %62, %64 : i64
%71 = arith.muli %59, %70 : i64
%72 = arith.addi %61, %71 : i64
llvm.store %72, %51 : i64, !llvm.ptr
%73 = arith.constant 1 : i32
%75 = arith.extsi %73 : i32 to i64
%74 = arith.addi %60, %75 : i64
llvm.store %74, %55 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%76 = llvm.load %51 : !llvm.ptr -> i64
func.return %76 : i64
}
func.func @compute_C3(%arg0: i64) -> i64 {
%77 = func.call @isqrt(%arg0) : (i64) -> i64
%79 = arith.constant 1 : i32
%81 = arith.extsi %79 : i32 to i64
%80 = arith.addi %77, %81 : i64
%82 = arith.constant 1 : i32
%83 = arith.extsi %82 : i32 to i64
%78 = func.call @calloc(%80, %83) : (i64, i64) -> !llvm.ptr
%84 = llvm.mlir.zero : !llvm.ptr
%85 = llvm.icmp "eq" %78, %84 : !llvm.ptr
cf.cond_br %85, ^bb15, ^bb16
^bb15:
%86 = arith.constant 1 : i32
%88 = arith.constant 0 : i32
%87 = arith.subi %88, %86 : i32
%89 = arith.extsi %87 : i32 to i64
func.return %89 : i64
^bb16:
cf.br ^bb17
^bb17:
%90 = arith.constant 0 : i32
%91 = arith.extsi %90 : i32 to i64
%92 = llvm.mlir.constant(1 : i64) : i64
%93 = llvm.alloca %92 x i64 : (i64) -> !llvm.ptr
llvm.store %91, %93 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%94 = llvm.load %93 : !llvm.ptr -> i64
%95 = arith.cmpi sle, %94, %77 : i64
cf.cond_br %95, ^bb19, ^bb20
^bb19:
%96 = arith.constant 1 : i32
%97 = llvm.load %93 : !llvm.ptr -> i64
%98 = arith.trunci %96 : i32 to i8
%99 = llvm.getelementptr %78[%97] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %98, %99 : i8, !llvm.ptr
%100 = llvm.load %93 : !llvm.ptr -> i64
%101 = arith.constant 1 : i32
%103 = arith.extsi %101 : i32 to i64
%102 = arith.addi %100, %103 : i64
llvm.store %102, %93 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%104 = arith.constant 0 : i32
%105 = arith.constant 0 : i32
%106 = arith.trunci %104 : i32 to i8
%107 = arith.extsi %105 : i32 to i64
%108 = llvm.getelementptr %78[%107] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %106, %108 : i8, !llvm.ptr
%109 = func.call @isqrt(%77) : (i64) -> i64
%110 = arith.constant 2 : i32
%111 = arith.extsi %110 : i32 to i64
%112 = llvm.mlir.constant(1 : i64) : i64
%113 = llvm.alloca %112 x i64 : (i64) -> !llvm.ptr
llvm.store %111, %113 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%114 = llvm.load %113 : !llvm.ptr -> i64
%115 = arith.cmpi sle, %114, %109 : i64
cf.cond_br %115, ^bb22, ^bb23
^bb22:
%116 = llvm.load %113 : !llvm.ptr -> i64
%117 = llvm.load %113 : !llvm.ptr -> i64
%118 = arith.muli %116, %117 : i64
%119 = llvm.mlir.constant(1 : i64) : i64
%120 = llvm.alloca %119 x i64 : (i64) -> !llvm.ptr
llvm.store %118, %120 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%121 = llvm.load %120 : !llvm.ptr -> i64
%122 = arith.cmpi sle, %121, %77 : i64
cf.cond_br %122, ^bb25, ^bb26
^bb25:
%123 = arith.constant 0 : i32
%124 = llvm.load %120 : !llvm.ptr -> i64
%125 = arith.trunci %123 : i32 to i8
%126 = llvm.getelementptr %78[%124] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %125, %126 : i8, !llvm.ptr
%127 = llvm.load %120 : !llvm.ptr -> i64
%128 = arith.addi %127, %118 : i64
llvm.store %128, %120 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%129 = llvm.load %113 : !llvm.ptr -> i64
%130 = arith.constant 1 : i32
%132 = arith.extsi %130 : i32 to i64
%131 = arith.addi %129, %132 : i64
llvm.store %131, %113 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%133 = arith.constant 0 : i32
%134 = arith.extsi %133 : i32 to i64
%135 = llvm.mlir.constant(1 : i64) : i64
%136 = llvm.alloca %135 x i64 : (i64) -> !llvm.ptr
llvm.store %134, %136 : i64, !llvm.ptr
%137 = arith.constant 1 : i32
%138 = arith.extsi %137 : i32 to i64
%139 = llvm.mlir.constant(1 : i64) : i64
%140 = llvm.alloca %139 x i64 : (i64) -> !llvm.ptr
llvm.store %138, %140 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%141 = llvm.load %140 : !llvm.ptr -> i64
%142 = arith.cmpi slt, %141, %77 : i64
cf.cond_br %142, ^bb28, ^bb29
^bb28:
%143 = llvm.load %140 : !llvm.ptr -> i64
%144 = arith.constant 1 : i32
%146 = arith.extsi %144 : i32 to i64
%145 = arith.addi %143, %146 : i64
%147 = llvm.load %140 : !llvm.ptr -> i64
%148 = arith.constant 1 : i32
%150 = arith.extsi %148 : i32 to i64
%149 = arith.addi %147, %150 : i64
%151 = arith.muli %145, %149 : i64
%152 = arith.cmpi sgt, %151, %arg0 : i64
cf.cond_br %152, ^bb30, ^bb31
^bb30:
cf.br ^bb29
^bb31:
cf.br ^bb32
^bb32:
%154 = llvm.load %140 : !llvm.ptr -> i64
%155 = llvm.getelementptr %78[%154] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%153 = llvm.load %155 : !llvm.ptr -> i8
%156 = arith.constant 0 : i32
%158 = arith.extsi %153 : i8 to i32
%157 = arith.cmpi ne, %158, %156 : i32
cf.cond_br %157, ^bb33, ^bb34
^bb33:
%159 = arith.constant 1 : i32
%160 = arith.extsi %159 : i32 to i64
%161 = llvm.mlir.constant(1 : i64) : i64
%162 = llvm.alloca %161 x i64 : (i64) -> !llvm.ptr
llvm.store %160, %162 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%163 = llvm.load %162 : !llvm.ptr -> i64
%164 = arith.cmpi sle, %163, %77 : i64
cf.cond_br %164, ^bb37, ^bb38
^bb37:
%166 = llvm.load %162 : !llvm.ptr -> i64
%167 = llvm.getelementptr %78[%166] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%165 = llvm.load %167 : !llvm.ptr -> i8
%168 = arith.constant 0 : i32
%170 = arith.extsi %165 : i8 to i32
%169 = arith.cmpi ne, %170, %168 : i32
%171 = scf.if %169 -> (i1) {
%173 = llvm.load %140 : !llvm.ptr -> i64
%174 = llvm.load %162 : !llvm.ptr -> i64
%172 = func.call @gcd(%173, %174) : (i64, i64) -> i64
%175 = arith.constant 1 : i32
%177 = arith.extsi %175 : i32 to i64
%176 = arith.cmpi eq, %172, %177 : i64
scf.yield %176 : i1
} else {
%178 = arith.constant false
scf.yield %178 : i1
}
cf.cond_br %171, ^bb39, ^bb40
^bb39:
%179 = llvm.load %140 : !llvm.ptr -> i64
%180 = llvm.load %162 : !llvm.ptr -> i64
%181 = arith.muli %179, %180 : i64
%182 = arith.constant 1 : i32
%184 = arith.extsi %182 : i32 to i64
%183 = arith.addi %181, %184 : i64
%185 = llvm.load %140 : !llvm.ptr -> i64
%186 = llvm.load %162 : !llvm.ptr -> i64
%187 = arith.addi %185, %186 : i64
%188 = arith.muli %183, %187 : i64
%189 = arith.cmpi sgt, %188, %arg0 : i64
cf.cond_br %189, ^bb42, ^bb43
^bb42:
cf.br ^bb38
^bb43:
cf.br ^bb44
^bb44:
%190 = llvm.load %140 : !llvm.ptr -> i64
%191 = llvm.load %162 : !llvm.ptr -> i64
%192 = arith.muli %190, %191 : i64
%193 = arith.constant 1 : i32
%194 = arith.extsi %193 : i32 to i64
%195 = llvm.mlir.constant(1 : i64) : i64
%196 = llvm.alloca %195 x i64 : (i64) -> !llvm.ptr
llvm.store %194, %196 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%197 = llvm.load %196 : !llvm.ptr -> i64
%198 = arith.cmpi sle, %197, %77 : i64
cf.cond_br %198, ^bb46, ^bb47
^bb46:
%200 = llvm.load %196 : !llvm.ptr -> i64
%201 = llvm.getelementptr %78[%200] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%199 = llvm.load %201 : !llvm.ptr -> i8
%202 = arith.constant 0 : i32
%204 = arith.extsi %199 : i8 to i32
%203 = arith.cmpi ne, %204, %202 : i32
%205 = scf.if %203 -> (i1) {
%207 = llvm.load %196 : !llvm.ptr -> i64
%206 = func.call @gcd(%192, %207) : (i64, i64) -> i64
%208 = arith.constant 1 : i32
%210 = arith.extsi %208 : i32 to i64
%209 = arith.cmpi eq, %206, %210 : i64
scf.yield %209 : i1
} else {
%211 = arith.constant false
scf.yield %211 : i1
}
cf.cond_br %205, ^bb48, ^bb49
^bb48:
%212 = llvm.load %196 : !llvm.ptr -> i64
%213 = arith.addi %192, %212 : i64
%214 = llvm.load %140 : !llvm.ptr -> i64
%215 = llvm.load %196 : !llvm.ptr -> i64
%216 = arith.muli %214, %215 : i64
%217 = llvm.load %162 : !llvm.ptr -> i64
%218 = arith.addi %216, %217 : i64
%219 = arith.muli %213, %218 : i64
%220 = arith.cmpi sgt, %219, %arg0 : i64
cf.cond_br %220, ^bb51, ^bb52
^bb51:
cf.br ^bb47
^bb52:
cf.br ^bb53
^bb53:
%221 = llvm.load %140 : !llvm.ptr -> i64
%222 = llvm.load %196 : !llvm.ptr -> i64
%223 = arith.muli %221, %222 : i64
%224 = llvm.load %196 : !llvm.ptr -> i64
%225 = arith.muli %192, %224 : i64
%226 = arith.constant 1 : i32
%227 = arith.extsi %226 : i32 to i64
%228 = llvm.mlir.constant(1 : i64) : i64
%229 = llvm.alloca %228 x i64 : (i64) -> !llvm.ptr
llvm.store %227, %229 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%230 = llvm.load %229 : !llvm.ptr -> i64
%231 = arith.cmpi sle, %230, %77 : i64
cf.cond_br %231, ^bb55, ^bb56
^bb55:
%233 = llvm.load %229 : !llvm.ptr -> i64
%234 = llvm.getelementptr %78[%233] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%232 = llvm.load %234 : !llvm.ptr -> i8
%235 = arith.constant 0 : i32
%237 = arith.extsi %232 : i8 to i32
%236 = arith.cmpi ne, %237, %235 : i32
%238 = scf.if %236 -> (i1) {
%240 = llvm.load %229 : !llvm.ptr -> i64
%239 = func.call @gcd(%225, %240) : (i64, i64) -> i64
%241 = arith.constant 1 : i32
%243 = arith.extsi %241 : i32 to i64
%242 = arith.cmpi eq, %239, %243 : i64
scf.yield %242 : i1
} else {
%244 = arith.constant false
scf.yield %244 : i1
}
cf.cond_br %238, ^bb57, ^bb58
^bb57:
%245 = llvm.load %196 : !llvm.ptr -> i64
%246 = llvm.load %229 : !llvm.ptr -> i64
%247 = arith.muli %245, %246 : i64
%248 = arith.addi %192, %247 : i64
%249 = llvm.load %162 : !llvm.ptr -> i64
%250 = llvm.load %229 : !llvm.ptr -> i64
%251 = arith.muli %249, %250 : i64
%252 = arith.addi %223, %251 : i64
%253 = arith.muli %248, %252 : i64
%254 = arith.cmpi sgt, %253, %arg0 : i64
cf.cond_br %254, ^bb60, ^bb61
^bb60:
cf.br ^bb56
^bb61:
cf.br ^bb62
^bb62:
%255 = llvm.load %196 : !llvm.ptr -> i64
%256 = llvm.load %229 : !llvm.ptr -> i64
%257 = arith.muli %255, %256 : i64
%258 = llvm.load %162 : !llvm.ptr -> i64
%259 = llvm.load %229 : !llvm.ptr -> i64
%260 = arith.muli %258, %259 : i64
%261 = arith.cmpi ne, %192, %257 : i64
%262 = scf.if %261 -> (i1) {
%263 = arith.cmpi ne, %223, %260 : i64
scf.yield %263 : i1
} else {
%264 = arith.constant false
scf.yield %264 : i1
}
cf.cond_br %262, ^bb63, ^bb64
^bb63:
%265 = arith.addi %223, %260 : i64
%266 = arith.constant 1 : i32
%267 = arith.extsi %266 : i32 to i64
%268 = llvm.mlir.constant(1 : i64) : i64
%269 = llvm.alloca %268 x i64 : (i64) -> !llvm.ptr
llvm.store %267, %269 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%270 = llvm.load %269 : !llvm.ptr -> i64
%271 = arith.muli %192, %270 : i64
%272 = llvm.load %269 : !llvm.ptr -> i64
%273 = arith.muli %271, %272 : i64
%274 = arith.addi %273, %257 : i64
%275 = arith.muli %274, %265 : i64
%276 = arith.cmpi sle, %275, %arg0 : i64
cf.cond_br %276, ^bb67, ^bb68
^bb67:
%277 = llvm.load %269 : !llvm.ptr -> i64
%278 = arith.muli %192, %277 : i64
%279 = llvm.load %269 : !llvm.ptr -> i64
%280 = arith.muli %278, %279 : i64
%281 = arith.constant 1 : i32
%282 = arith.extsi %281 : i32 to i64
%283 = llvm.mlir.constant(1 : i64) : i64
%284 = llvm.alloca %283 x i64 : (i64) -> !llvm.ptr
llvm.store %282, %284 : i64, !llvm.ptr
cf.br ^bb69
^bb69:
%285 = llvm.load %284 : !llvm.ptr -> i64
%286 = arith.muli %257, %285 : i64
%287 = llvm.load %284 : !llvm.ptr -> i64
%288 = arith.muli %286, %287 : i64
%289 = arith.addi %280, %288 : i64
%290 = arith.muli %289, %265 : i64
%291 = arith.cmpi sle, %290, %arg0 : i64
cf.cond_br %291, ^bb70, ^bb71
^bb70:
%292 = llvm.load %284 : !llvm.ptr -> i64
%293 = arith.muli %257, %292 : i64
%294 = llvm.load %284 : !llvm.ptr -> i64
%295 = arith.muli %293, %294 : i64
%296 = arith.addi %280, %295 : i64
%297 = arith.constant 1 : i32
%298 = arith.extsi %297 : i32 to i64
%299 = llvm.mlir.constant(1 : i64) : i64
%300 = llvm.alloca %299 x i64 : (i64) -> !llvm.ptr
llvm.store %298, %300 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%301 = llvm.load %300 : !llvm.ptr -> i64
%302 = arith.muli %223, %301 : i64
%303 = llvm.load %300 : !llvm.ptr -> i64
%304 = arith.muli %302, %303 : i64
%305 = arith.addi %304, %260 : i64
%306 = arith.muli %296, %305 : i64
%307 = arith.cmpi sle, %306, %arg0 : i64
cf.cond_br %307, ^bb73, ^bb74
^bb73:
%308 = llvm.load %300 : !llvm.ptr -> i64
%309 = arith.muli %223, %308 : i64
%310 = llvm.load %300 : !llvm.ptr -> i64
%311 = arith.muli %309, %310 : i64
%312 = arith.constant 1 : i32
%313 = arith.extsi %312 : i32 to i64
%314 = llvm.mlir.constant(1 : i64) : i64
%315 = llvm.alloca %314 x i64 : (i64) -> !llvm.ptr
llvm.store %313, %315 : i64, !llvm.ptr
cf.br ^bb75
^bb75:
%316 = llvm.load %315 : !llvm.ptr -> i64
%317 = arith.muli %260, %316 : i64
%318 = llvm.load %315 : !llvm.ptr -> i64
%319 = arith.muli %317, %318 : i64
%320 = arith.addi %311, %319 : i64
%321 = arith.muli %296, %320 : i64
%322 = arith.cmpi sle, %321, %arg0 : i64
cf.cond_br %322, ^bb76, ^bb77
^bb76:
%323 = llvm.load %315 : !llvm.ptr -> i64
%324 = arith.muli %260, %323 : i64
%325 = llvm.load %315 : !llvm.ptr -> i64
%326 = arith.muli %324, %325 : i64
%327 = arith.addi %311, %326 : i64
%328 = llvm.load %284 : !llvm.ptr -> i64
%329 = arith.muli %293, %328 : i64
%330 = arith.cmpi sgt, %280, %329 : i64
%331 = scf.if %330 -> (i1) {
%332 = llvm.load %315 : !llvm.ptr -> i64
%333 = arith.muli %324, %332 : i64
%334 = arith.cmpi sgt, %311, %333 : i64
scf.yield %334 : i1
} else {
%335 = arith.constant false
scf.yield %335 : i1
}
cf.cond_br %331, ^bb78, ^bb79
^bb78:
%336 = func.call @gcd(%278, %293) : (i64, i64) -> i64
%337 = arith.constant 1 : i32
%339 = arith.extsi %337 : i32 to i64
%338 = arith.cmpi eq, %336, %339 : i64
%340 = scf.if %338 -> (i1) {
%341 = func.call @gcd(%309, %324) : (i64, i64) -> i64
%342 = arith.constant 1 : i32
%344 = arith.extsi %342 : i32 to i64
%343 = arith.cmpi eq, %341, %344 : i64
scf.yield %343 : i1
} else {
%345 = arith.constant false
scf.yield %345 : i1
}
cf.cond_br %340, ^bb81, ^bb82
^bb81:
%346 = llvm.load %136 : !llvm.ptr -> i64
%347 = arith.divsi %arg0, %296 : i64
%348 = arith.divsi %347, %327 : i64
%349 = arith.addi %346, %348 : i64
llvm.store %349, %136 : i64, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%350 = llvm.load %315 : !llvm.ptr -> i64
%351 = arith.constant 1 : i32
%353 = arith.extsi %351 : i32 to i64
%352 = arith.addi %350, %353 : i64
llvm.store %352, %315 : i64, !llvm.ptr
cf.br ^bb75
^bb77:
%354 = llvm.load %300 : !llvm.ptr -> i64
%355 = arith.constant 1 : i32
%357 = arith.extsi %355 : i32 to i64
%356 = arith.addi %354, %357 : i64
llvm.store %356, %300 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
%358 = llvm.load %284 : !llvm.ptr -> i64
%359 = arith.constant 1 : i32
%361 = arith.extsi %359 : i32 to i64
%360 = arith.addi %358, %361 : i64
llvm.store %360, %284 : i64, !llvm.ptr
cf.br ^bb69
^bb71:
%362 = llvm.load %269 : !llvm.ptr -> i64
%363 = arith.constant 1 : i32
%365 = arith.extsi %363 : i32 to i64
%364 = arith.addi %362, %365 : i64
llvm.store %364, %269 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
cf.br ^bb65
^bb64:
cf.br ^bb65
^bb65:
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%366 = llvm.load %229 : !llvm.ptr -> i64
%367 = arith.constant 1 : i32
%369 = arith.extsi %367 : i32 to i64
%368 = arith.addi %366, %369 : i64
llvm.store %368, %229 : i64, !llvm.ptr
cf.br ^bb54
^bb56:
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%370 = llvm.load %196 : !llvm.ptr -> i64
%371 = arith.constant 1 : i32
%373 = arith.extsi %371 : i32 to i64
%372 = arith.addi %370, %373 : i64
llvm.store %372, %196 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%374 = llvm.load %162 : !llvm.ptr -> i64
%375 = arith.constant 1 : i32
%377 = arith.extsi %375 : i32 to i64
%376 = arith.addi %374, %377 : i64
llvm.store %376, %162 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%378 = llvm.load %140 : !llvm.ptr -> i64
%379 = arith.constant 1 : i32
%381 = arith.extsi %379 : i32 to i64
%380 = arith.addi %378, %381 : i64
llvm.store %380, %140 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
func.call @free(%78) : (!llvm.ptr) -> ()
%383 = llvm.load %136 : !llvm.ptr -> i64
func.return %383 : i64
}
func.func @F(%arg0: i64) -> i64 {
%385 = arith.constant 1 : i32
%387 = arith.extsi %385 : i32 to i64
%386 = arith.addi %arg0, %387 : i64
%388 = arith.constant 4 : i32
%389 = arith.extsi %388 : i32 to i64
%384 = func.call @calloc(%386, %389) : (i64, i64) -> !llvm.ptr
%391 = arith.constant 1 : i32
%393 = arith.extsi %391 : i32 to i64
%392 = arith.addi %arg0, %393 : i64
%394 = arith.constant 1 : i32
%395 = arith.extsi %394 : i32 to i64
%390 = func.call @calloc(%392, %395) : (i64, i64) -> !llvm.ptr
%397 = arith.constant 5 : i32
%399 = arith.extsi %397 : i32 to i64
%398 = arith.divsi %arg0, %399 : i64
%400 = arith.constant 10 : i32
%402 = arith.extsi %400 : i32 to i64
%401 = arith.addi %398, %402 : i64
%403 = arith.constant 4 : i32
%404 = arith.extsi %403 : i32 to i64
%396 = func.call @calloc(%401, %404) : (i64, i64) -> !llvm.ptr
%405 = llvm.mlir.zero : !llvm.ptr
%406 = llvm.icmp "eq" %384, %405 : !llvm.ptr
%407 = scf.if %406 -> (i1) {
%408 = arith.constant true
scf.yield %408 : i1
} else {
%409 = llvm.mlir.zero : !llvm.ptr
%410 = llvm.icmp "eq" %390, %409 : !llvm.ptr
scf.yield %410 : i1
}
%411 = scf.if %407 -> (i1) {
%412 = arith.constant true
scf.yield %412 : i1
} else {
%413 = llvm.mlir.zero : !llvm.ptr
%414 = llvm.icmp "eq" %396, %413 : !llvm.ptr
scf.yield %414 : i1
}
cf.cond_br %411, ^bb84, ^bb85
^bb84:
%415 = arith.constant 1 : i32
%417 = arith.constant 0 : i32
%416 = arith.subi %417, %415 : i32
%418 = arith.extsi %416 : i32 to i64
func.return %418 : i64
^bb85:
cf.br ^bb86
^bb86:
%419 = arith.constant 0 : i32
%420 = arith.extsi %419 : i32 to i64
%421 = llvm.mlir.constant(1 : i64) : i64
%422 = llvm.alloca %421 x i64 : (i64) -> !llvm.ptr
llvm.store %420, %422 : i64, !llvm.ptr
%423 = arith.constant 1 : i32
%424 = arith.constant 1 : i32
%425 = arith.extsi %424 : i32 to i64
%426 = llvm.getelementptr %384[%425] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %423, %426 : i32, !llvm.ptr
%427 = arith.constant 2 : i32
%428 = arith.extsi %427 : i32 to i64
%429 = llvm.mlir.constant(1 : i64) : i64
%430 = llvm.alloca %429 x i64 : (i64) -> !llvm.ptr
llvm.store %428, %430 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%431 = llvm.load %430 : !llvm.ptr -> i64
%432 = arith.cmpi sle, %431, %arg0 : i64
cf.cond_br %432, ^bb88, ^bb89
^bb88:
%434 = llvm.load %430 : !llvm.ptr -> i64
%435 = llvm.getelementptr %390[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%433 = llvm.load %435 : !llvm.ptr -> i8
%436 = arith.constant 0 : i32
%438 = arith.extsi %433 : i8 to i32
%437 = arith.cmpi eq, %438, %436 : i32
cf.cond_br %437, ^bb90, ^bb91
^bb90:
%439 = llvm.load %430 : !llvm.ptr -> i64
%440 = arith.trunci %439 : i64 to i32
%441 = llvm.load %422 : !llvm.ptr -> i64
%442 = llvm.getelementptr %396[%441] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %440, %442 : i32, !llvm.ptr
%443 = llvm.load %422 : !llvm.ptr -> i64
%444 = arith.constant 1 : i32
%446 = arith.extsi %444 : i32 to i64
%445 = arith.addi %443, %446 : i64
llvm.store %445, %422 : i64, !llvm.ptr
%447 = llvm.load %430 : !llvm.ptr -> i64
%448 = arith.constant 1 : i32
%450 = arith.extsi %448 : i32 to i64
%449 = arith.subi %447, %450 : i64
%451 = arith.trunci %449 : i64 to i32
%452 = llvm.load %430 : !llvm.ptr -> i64
%453 = llvm.getelementptr %384[%452] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %451, %453 : i32, !llvm.ptr
cf.br ^bb92
^bb91:
cf.br ^bb92
^bb92:
%454 = arith.constant 0 : i32
%455 = arith.extsi %454 : i32 to i64
%456 = llvm.mlir.constant(1 : i64) : i64
%457 = llvm.alloca %456 x i64 : (i64) -> !llvm.ptr
llvm.store %455, %457 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%458 = llvm.load %457 : !llvm.ptr -> i64
%459 = llvm.load %422 : !llvm.ptr -> i64
%460 = arith.cmpi slt, %458, %459 : i64
cf.cond_br %460, ^bb94, ^bb95
^bb94:
%462 = llvm.load %457 : !llvm.ptr -> i64
%463 = llvm.getelementptr %396[%462] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%461 = llvm.load %463 : !llvm.ptr -> i32
%464 = arith.extsi %461 : i32 to i64
%465 = llvm.load %430 : !llvm.ptr -> i64
%466 = arith.muli %465, %464 : i64
%467 = arith.cmpi sgt, %466, %arg0 : i64
cf.cond_br %467, ^bb96, ^bb97
^bb96:
cf.br ^bb95
^bb97:
cf.br ^bb98
^bb98:
%468 = arith.constant 1 : i32
%469 = arith.trunci %468 : i32 to i8
%470 = llvm.getelementptr %390[%466] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %469, %470 : i8, !llvm.ptr
%471 = llvm.load %430 : !llvm.ptr -> i64
%472 = arith.remsi %471, %464 : i64
%473 = arith.constant 0 : i32
%475 = arith.extsi %473 : i32 to i64
%474 = arith.cmpi eq, %472, %475 : i64
cf.cond_br %474, ^bb99, ^bb100
^bb99:
%477 = llvm.load %430 : !llvm.ptr -> i64
%478 = llvm.getelementptr %384[%477] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%476 = llvm.load %478 : !llvm.ptr -> i32
%479 = arith.extsi %476 : i32 to i64
%480 = arith.muli %479, %464 : i64
%481 = arith.trunci %480 : i64 to i32
%482 = llvm.getelementptr %384[%466] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %481, %482 : i32, !llvm.ptr
cf.br ^bb95
^bb100:
%484 = llvm.load %430 : !llvm.ptr -> i64
%485 = llvm.getelementptr %384[%484] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%483 = llvm.load %485 : !llvm.ptr -> i32
%486 = arith.extsi %483 : i32 to i64
%487 = arith.constant 1 : i32
%489 = arith.extsi %487 : i32 to i64
%488 = arith.subi %464, %489 : i64
%490 = arith.muli %486, %488 : i64
%491 = arith.trunci %490 : i64 to i32
%492 = llvm.getelementptr %384[%466] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %491, %492 : i32, !llvm.ptr
cf.br ^bb101
^bb101:
%493 = llvm.load %457 : !llvm.ptr -> i64
%494 = arith.constant 1 : i32
%496 = arith.extsi %494 : i32 to i64
%495 = arith.addi %493, %496 : i64
llvm.store %495, %457 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%497 = llvm.load %430 : !llvm.ptr -> i64
%498 = arith.constant 1 : i32
%500 = arith.extsi %498 : i32 to i64
%499 = arith.addi %497, %500 : i64
llvm.store %499, %430 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%502 = arith.constant 1 : i32
%504 = arith.extsi %502 : i32 to i64
%503 = arith.addi %arg0, %504 : i64
%505 = arith.constant 4 : i32
%506 = arith.extsi %505 : i32 to i64
%501 = func.call @calloc(%503, %506) : (i64, i64) -> !llvm.ptr
%507 = llvm.mlir.zero : !llvm.ptr
%508 = llvm.icmp "eq" %501, %507 : !llvm.ptr
cf.cond_br %508, ^bb102, ^bb103
^bb102:
%509 = arith.constant 1 : i32
%511 = arith.constant 0 : i32
%510 = arith.subi %511, %509 : i32
%512 = arith.extsi %510 : i32 to i64
func.return %512 : i64
^bb103:
cf.br ^bb104
^bb104:
%513 = arith.constant 3 : i32
%514 = arith.extsi %513 : i32 to i64
llvm.store %514, %430 : i64, !llvm.ptr
cf.br ^bb105
^bb105:
%515 = llvm.load %430 : !llvm.ptr -> i64
%516 = arith.cmpi sle, %515, %arg0 : i64
cf.cond_br %516, ^bb106, ^bb107
^bb106:
%518 = llvm.load %430 : !llvm.ptr -> i64
%519 = llvm.getelementptr %384[%518] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%517 = llvm.load %519 : !llvm.ptr -> i32
%520 = arith.extsi %517 : i32 to i64
%521 = arith.constant 2 : i32
%523 = arith.extsi %521 : i32 to i64
%522 = arith.divsi %520, %523 : i64
%524 = arith.trunci %522 : i64 to i32
%525 = llvm.load %430 : !llvm.ptr -> i64
%526 = llvm.getelementptr %501[%525] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %524, %526 : i32, !llvm.ptr
%527 = llvm.load %430 : !llvm.ptr -> i64
%528 = arith.constant 1 : i32
%530 = arith.extsi %528 : i32 to i64
%529 = arith.addi %527, %530 : i64
llvm.store %529, %430 : i64, !llvm.ptr
cf.br ^bb105
^bb107:
%531 = func.call @isqrt(%arg0) : (i64) -> i64
%532 = arith.constant 2 : i32
%533 = arith.extsi %532 : i32 to i64
%534 = llvm.mlir.constant(1 : i64) : i64
%535 = llvm.alloca %534 x i64 : (i64) -> !llvm.ptr
llvm.store %533, %535 : i64, !llvm.ptr
cf.br ^bb108
^bb108:
%536 = llvm.load %535 : !llvm.ptr -> i64
%537 = arith.cmpi sle, %536, %531 : i64
cf.cond_br %537, ^bb109, ^bb110
^bb109:
%538 = llvm.load %535 : !llvm.ptr -> i64
%539 = llvm.load %535 : !llvm.ptr -> i64
%540 = arith.muli %538, %539 : i64
%542 = arith.subi %arg0, %540 : i64
%541 = func.call @isqrt(%542) : (i64) -> i64
%543 = arith.constant 1 : i32
%544 = arith.extsi %543 : i32 to i64
%545 = llvm.mlir.constant(1 : i64) : i64
%546 = llvm.alloca %545 x i64 : (i64) -> !llvm.ptr
llvm.store %544, %546 : i64, !llvm.ptr
%547 = llvm.load %535 : !llvm.ptr -> i64
%548 = arith.constant 1 : i32
%550 = arith.extsi %548 : i32 to i64
%549 = arith.addi %541, %550 : i64
%551 = arith.cmpi slt, %549, %547 : i64
%552 = scf.if %551 -> (i64) {
%553 = arith.constant 1 : i32
%555 = arith.extsi %553 : i32 to i64
%554 = arith.addi %541, %555 : i64
scf.yield %554 : i64
} else {
scf.yield %547 : i64
}
cf.br ^bb111
^bb111:
%556 = llvm.load %546 : !llvm.ptr -> i64
%557 = arith.cmpi slt, %556, %552 : i64
cf.cond_br %557, ^bb112, ^bb113
^bb112:
%559 = llvm.load %535 : !llvm.ptr -> i64
%560 = llvm.load %546 : !llvm.ptr -> i64
%558 = func.call @gcd(%559, %560) : (i64, i64) -> i64
%561 = arith.constant 1 : i32
%563 = arith.extsi %561 : i32 to i64
%562 = arith.cmpi eq, %558, %563 : i64
cf.cond_br %562, ^bb114, ^bb115
^bb114:
%565 = llvm.load %546 : !llvm.ptr -> i64
%566 = llvm.load %546 : !llvm.ptr -> i64
%567 = arith.muli %565, %566 : i64
%568 = arith.addi %540, %567 : i64
%569 = llvm.getelementptr %501[%568] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%564 = llvm.load %569 : !llvm.ptr -> i32
%570 = arith.constant 1 : i32
%571 = arith.subi %564, %570 : i32
%572 = llvm.load %546 : !llvm.ptr -> i64
%573 = llvm.load %546 : !llvm.ptr -> i64
%574 = arith.muli %572, %573 : i64
%575 = arith.addi %540, %574 : i64
%576 = llvm.getelementptr %501[%575] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %571, %576 : i32, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
%577 = llvm.load %546 : !llvm.ptr -> i64
%578 = arith.constant 1 : i32
%580 = arith.extsi %578 : i32 to i64
%579 = arith.addi %577, %580 : i64
llvm.store %579, %546 : i64, !llvm.ptr
cf.br ^bb111
^bb113:
%581 = llvm.load %535 : !llvm.ptr -> i64
%582 = arith.constant 1 : i32
%584 = arith.extsi %582 : i32 to i64
%583 = arith.addi %581, %584 : i64
llvm.store %583, %535 : i64, !llvm.ptr
cf.br ^bb108
^bb110:
%586 = arith.constant 1 : i32
%588 = arith.extsi %586 : i32 to i64
%587 = arith.addi %arg0, %588 : i64
%589 = arith.constant 8 : i32
%590 = arith.extsi %589 : i32 to i64
%585 = func.call @calloc(%587, %590) : (i64, i64) -> !llvm.ptr
%591 = llvm.mlir.zero : !llvm.ptr
%592 = llvm.icmp "eq" %585, %591 : !llvm.ptr
cf.cond_br %592, ^bb117, ^bb118
^bb117:
%593 = arith.constant 1 : i32
%595 = arith.constant 0 : i32
%594 = arith.subi %595, %593 : i32
%596 = arith.extsi %594 : i32 to i64
func.return %596 : i64
^bb118:
cf.br ^bb119
^bb119:
%597 = arith.constant 0 : i32
%598 = arith.extsi %597 : i32 to i64
%599 = llvm.mlir.constant(1 : i64) : i64
%600 = llvm.alloca %599 x i64 : (i64) -> !llvm.ptr
llvm.store %598, %600 : i64, !llvm.ptr
%601 = arith.constant 0 : i32
%602 = arith.extsi %601 : i32 to i64
llvm.store %602, %430 : i64, !llvm.ptr
cf.br ^bb120
^bb120:
%603 = llvm.load %430 : !llvm.ptr -> i64
%604 = arith.cmpi sle, %603, %arg0 : i64
cf.cond_br %604, ^bb121, ^bb122
^bb121:
%605 = llvm.load %600 : !llvm.ptr -> i64
%607 = llvm.load %430 : !llvm.ptr -> i64
%608 = llvm.getelementptr %501[%607] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%606 = llvm.load %608 : !llvm.ptr -> i32
%609 = arith.extsi %606 : i32 to i64
%610 = arith.addi %605, %609 : i64
llvm.store %610, %600 : i64, !llvm.ptr
%611 = llvm.load %600 : !llvm.ptr -> i64
%612 = llvm.load %430 : !llvm.ptr -> i64
%613 = llvm.getelementptr %585[%612] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %611, %613 : i64, !llvm.ptr
%614 = llvm.load %430 : !llvm.ptr -> i64
%615 = arith.constant 1 : i32
%617 = arith.extsi %615 : i32 to i64
%616 = arith.addi %614, %617 : i64
llvm.store %616, %430 : i64, !llvm.ptr
cf.br ^bb120
^bb122:
%618 = func.call @grouped_sum_floor(%arg0, %585) : (i64, !llvm.ptr) -> i64
%619 = arith.constant 200003 : i32
%620 = arith.extsi %619 : i32 to i64
%622 = arith.constant 8 : i32
%623 = arith.extsi %622 : i32 to i64
%621 = func.call @calloc(%620, %623) : (i64, i64) -> !llvm.ptr
%625 = arith.constant 8 : i32
%626 = arith.extsi %625 : i32 to i64
%624 = func.call @calloc(%620, %626) : (i64, i64) -> !llvm.ptr
%628 = arith.constant 1 : i32
%629 = arith.extsi %628 : i32 to i64
%627 = func.call @calloc(%620, %629) : (i64, i64) -> !llvm.ptr
%630 = llvm.mlir.zero : !llvm.ptr
%631 = llvm.icmp "eq" %621, %630 : !llvm.ptr
%632 = scf.if %631 -> (i1) {
%633 = arith.constant true
scf.yield %633 : i1
} else {
%634 = llvm.mlir.zero : !llvm.ptr
%635 = llvm.icmp "eq" %624, %634 : !llvm.ptr
scf.yield %635 : i1
}
%636 = scf.if %632 -> (i1) {
%637 = arith.constant true
scf.yield %637 : i1
} else {
%638 = llvm.mlir.zero : !llvm.ptr
%639 = llvm.icmp "eq" %627, %638 : !llvm.ptr
scf.yield %639 : i1
}
cf.cond_br %636, ^bb123, ^bb124
^bb123:
%640 = arith.constant 1 : i32
%642 = arith.constant 0 : i32
%641 = arith.subi %642, %640 : i32
%643 = arith.extsi %641 : i32 to i64
func.return %643 : i64
^bb124:
cf.br ^bb125
^bb125:
%644 = arith.constant 0 : i32
%645 = arith.extsi %644 : i32 to i64
%646 = llvm.mlir.constant(1 : i64) : i64
%647 = llvm.alloca %646 x i64 : (i64) -> !llvm.ptr
llvm.store %645, %647 : i64, !llvm.ptr
%648 = arith.constant 1 : i32
%649 = arith.extsi %648 : i32 to i64
llvm.store %649, %430 : i64, !llvm.ptr
cf.br ^bb126
^bb126:
%650 = llvm.load %430 : !llvm.ptr -> i64
%651 = arith.cmpi sle, %650, %arg0 : i64
cf.cond_br %651, ^bb127, ^bb128
^bb127:
%652 = llvm.load %430 : !llvm.ptr -> i64
%653 = arith.divsi %arg0, %652 : i64
%654 = arith.divsi %arg0, %653 : i64
%656 = llvm.getelementptr %585[%654] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%655 = llvm.load %656 : !llvm.ptr -> i64
%658 = llvm.load %430 : !llvm.ptr -> i64
%659 = arith.constant 1 : i32
%661 = arith.extsi %659 : i32 to i64
%660 = arith.subi %658, %661 : i64
%662 = llvm.getelementptr %585[%660] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%657 = llvm.load %662 : !llvm.ptr -> i64
%663 = arith.subi %655, %657 : i64
%664 = arith.remsi %653, %620 : i64
%665 = llvm.mlir.constant(1 : i64) : i64
%666 = llvm.alloca %665 x i64 : (i64) -> !llvm.ptr
llvm.store %664, %666 : i64, !llvm.ptr
%667 = llvm.load %666 : !llvm.ptr -> i64
%668 = arith.constant 0 : i32
%670 = arith.extsi %668 : i32 to i64
%669 = arith.cmpi slt, %667, %670 : i64
cf.cond_br %669, ^bb129, ^bb130
^bb129:
%671 = llvm.load %666 : !llvm.ptr -> i64
%673 = arith.constant 0 : i64
%672 = arith.subi %673, %671 : i64
llvm.store %672, %666 : i64, !llvm.ptr
cf.br ^bb131
^bb130:
cf.br ^bb131
^bb131:
%674 = arith.constant 0 : i32
%675 = arith.extsi %674 : i32 to i64
%676 = llvm.mlir.constant(1 : i64) : i64
%677 = llvm.alloca %676 x i64 : (i64) -> !llvm.ptr
llvm.store %675, %677 : i64, !llvm.ptr
%678 = arith.constant 0 : i32
%679 = llvm.mlir.constant(1 : i64) : i64
%680 = llvm.alloca %679 x i32 : (i64) -> !llvm.ptr
llvm.store %678, %680 : i32, !llvm.ptr
%681 = arith.constant 0 : i32
%682 = arith.extsi %681 : i32 to i64
%683 = llvm.mlir.constant(1 : i64) : i64
%684 = llvm.alloca %683 x i64 : (i64) -> !llvm.ptr
llvm.store %682, %684 : i64, !llvm.ptr
cf.br ^bb132
^bb132:
%685 = llvm.load %684 : !llvm.ptr -> i64
%686 = arith.constant 10000 : i32
%688 = arith.extsi %686 : i32 to i64
%687 = arith.cmpi slt, %685, %688 : i64
cf.cond_br %687, ^bb133, ^bb134
^bb133:
%690 = llvm.load %666 : !llvm.ptr -> i64
%691 = llvm.getelementptr %627[%690] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%689 = llvm.load %691 : !llvm.ptr -> i8
%692 = arith.constant 0 : i32
%694 = arith.extsi %689 : i8 to i32
%693 = arith.cmpi eq, %694, %692 : i32
cf.cond_br %693, ^bb135, ^bb136
^bb135:
%695 = func.call @grouped_sum_floor(%653, %585) : (i64, !llvm.ptr) -> i64
llvm.store %695, %677 : i64, !llvm.ptr
%696 = arith.constant 1 : i32
%697 = llvm.load %666 : !llvm.ptr -> i64
%698 = arith.trunci %696 : i32 to i8
%699 = llvm.getelementptr %627[%697] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %698, %699 : i8, !llvm.ptr
%700 = llvm.load %666 : !llvm.ptr -> i64
%701 = llvm.getelementptr %621[%700] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %653, %701 : i64, !llvm.ptr
%702 = llvm.load %677 : !llvm.ptr -> i64
%703 = llvm.load %666 : !llvm.ptr -> i64
%704 = llvm.getelementptr %624[%703] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %702, %704 : i64, !llvm.ptr
%705 = arith.constant 1 : i32
llvm.store %705, %680 : i32, !llvm.ptr
cf.br ^bb134
^bb136:
cf.br ^bb137
^bb137:
%707 = llvm.load %666 : !llvm.ptr -> i64
%708 = llvm.getelementptr %621[%707] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%706 = llvm.load %708 : !llvm.ptr -> i64
%709 = arith.cmpi eq, %706, %653 : i64
cf.cond_br %709, ^bb138, ^bb139
^bb138:
%711 = llvm.load %666 : !llvm.ptr -> i64
%712 = llvm.getelementptr %624[%711] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%710 = llvm.load %712 : !llvm.ptr -> i64
llvm.store %710, %677 : i64, !llvm.ptr
%713 = arith.constant 1 : i32
llvm.store %713, %680 : i32, !llvm.ptr
cf.br ^bb134
^bb139:
cf.br ^bb140
^bb140:
%714 = llvm.load %666 : !llvm.ptr -> i64
%715 = arith.constant 1 : i32
%717 = arith.extsi %715 : i32 to i64
%716 = arith.addi %714, %717 : i64
llvm.store %716, %666 : i64, !llvm.ptr
%718 = llvm.load %666 : !llvm.ptr -> i64
%719 = arith.cmpi sge, %718, %620 : i64
cf.cond_br %719, ^bb141, ^bb142
^bb141:
%720 = arith.constant 0 : i32
%721 = arith.extsi %720 : i32 to i64
llvm.store %721, %666 : i64, !llvm.ptr
cf.br ^bb143
^bb142:
cf.br ^bb143
^bb143:
%722 = llvm.load %684 : !llvm.ptr -> i64
%723 = arith.constant 1 : i32
%725 = arith.extsi %723 : i32 to i64
%724 = arith.addi %722, %725 : i64
llvm.store %724, %684 : i64, !llvm.ptr
cf.br ^bb132
^bb134:
%726 = llvm.load %680 : !llvm.ptr -> i32
%727 = arith.constant 0 : i32
%728 = arith.cmpi eq, %726, %727 : i32
cf.cond_br %728, ^bb144, ^bb145
^bb144:
%729 = func.call @grouped_sum_floor(%653, %585) : (i64, !llvm.ptr) -> i64
llvm.store %729, %677 : i64, !llvm.ptr
cf.br ^bb146
^bb145:
cf.br ^bb146
^bb146:
%730 = llvm.load %647 : !llvm.ptr -> i64
%731 = llvm.load %677 : !llvm.ptr -> i64
%732 = arith.muli %663, %731 : i64
%733 = arith.addi %730, %732 : i64
llvm.store %733, %647 : i64, !llvm.ptr
%734 = arith.constant 1 : i32
%736 = arith.extsi %734 : i32 to i64
%735 = arith.addi %654, %736 : i64
llvm.store %735, %430 : i64, !llvm.ptr
cf.br ^bb126
^bb128:
%737 = func.call @compute_C3(%arg0) : (i64) -> i64
func.call @free(%384) : (!llvm.ptr) -> ()
func.call @free(%390) : (!llvm.ptr) -> ()
func.call @free(%396) : (!llvm.ptr) -> ()
func.call @free(%501) : (!llvm.ptr) -> ()
func.call @free(%585) : (!llvm.ptr) -> ()
func.call @free(%621) : (!llvm.ptr) -> ()
func.call @free(%624) : (!llvm.ptr) -> ()
func.call @free(%627) : (!llvm.ptr) -> ()
%746 = llvm.load %647 : !llvm.ptr -> i64
%747 = arith.subi %746, %737 : i64
%748 = arith.constant 2 : i32
%750 = arith.extsi %748 : i32 to i64
%749 = arith.divsi %747, %750 : i64
%751 = arith.addi %618, %749 : i64
func.return %751 : i64
}
func.func @main() -> i32 {
%752 = llvm.mlir.addressof @str_0 : !llvm.ptr
%754 = arith.constant 5000000 : i32
%755 = arith.extsi %754 : i32 to i64
%753 = func.call @F(%755) : (i64) -> i64
%756 = llvm.call @printf(%752, %753) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%757 = arith.constant 0 : i32
func.return %757 : i32
}
}