← All problems Problem 693
f(3,000,000): max g(x) for x <= 3*10^6. g(x) = max chain length over y < x of sequence a_{z+1} = a_z^2 mod z. Track active set A_z = {a^2 mod z : a in A_{z-1}} \ {0,1} until empty. f(n) via best-first branch-and-bound. Valid upper bound: for r >= x, dropping the first (r-x) terms of any chain starting at x yields a valid chain starting at r, so g(x) <= g(r) + (r - x). Hence for an interval [l, r] whose right endpoint r has known g(r): max_{l<=x<=r} g(x) <= g(r) + (r - l). Splitting at m keeps g(r) for the right child [m, r] and uses g(m) for the left child [l, m], so every bound stays valid.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)?Space complexity O(n^2)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 693
# f(3,000,000): max g(x) for x <= 3*10^6.
# g(x) = max chain length over y < x of sequence a_{z+1} = a_z^2 mod z.
# Track active set A_z = {a^2 mod z : a in A_{z-1}} \ {0,1} until empty.
#
# f(n) via best-first branch-and-bound. Valid upper bound: for r >= x,
# dropping the first (r-x) terms of any chain starting at x yields a valid
# chain starting at r, so g(x) <= g(r) + (r - x). Hence for an interval
# [l, r] whose right endpoint r has known g(r): max_{l<=x<=r} g(x) <=
# g(r) + (r - l). Splitting at m keeps g(r) for the right child [m, r]
# and uses g(m) for the left child [l, m], so every bound stays valid.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
# Compute g(x) using active set approach
function g_x(x: i64, mark_buf: ptr<i8>, active_buf: ptr<i64>) -> i64 {
if x < 2 { return 0 }
if x == 2 { return 1 }
# Initial active set: union of y^2 mod x for y=2..x/2, excluding 0 and 1
let mut n_active: i64 = 0
let mut y: i64 = 2
while y <= x / 2 {
let sq: i64 = (y * y) % x
if sq > 1 && mark_buf[sq] == 0 {
mark_buf[sq] = 1
active_buf[n_active] = sq
n_active = n_active + 1
}
y = y + 1
}
# Clear marks
for k in 0..n_active { mark_buf[active_buf[k]] = 0 }
let mut length: i64 = 2
let mut mod_val: i64 = x + 1
# Reduce active set until empty or singleton
while n_active > 1 {
let mut next_n: i64 = 0
for k in 0..n_active {
let v: i64 = (active_buf[k] * active_buf[k]) % mod_val
if v > 1 && mark_buf[v] == 0 {
mark_buf[v] = 1
active_buf[next_n] = v
next_n = next_n + 1
}
}
# Clear marks
for k in 0..next_n { mark_buf[active_buf[k]] = 0 }
n_active = next_n
length = length + 1
mod_val = mod_val + 1
}
if n_active == 0 { return length }
# Singleton fast path
let mut v: i64 = active_buf[0]
while v > 1 {
v = (v * v) % mod_val
length = length + 1
mod_val = mod_val + 1
}
return length
}
# Cached g(x)
function G(x: i64, gcache: ptr<i32>, gdone: ptr<i8>,
mark_buf: ptr<i8>, active_buf: ptr<i64>) -> i64 {
if gdone[x] == 1 { return gcache[x] as i64 }
let v: i64 = g_x(x, mark_buf, active_buf)
gcache[x] = v as i32
gdone[x] = 1
return v
}
function main() -> i32 {
let N: i64 = 3000000
let BUFSZ: i64 = N * 2
let mark_buf: ptr<i8> = calloc(BUFSZ, 1)
let active_buf: ptr<i64> = calloc(BUFSZ, 8)
if mark_buf == null || active_buf == null { return 1 }
let gcache: ptr<i32> = calloc(N + 2, 4)
let gdone: ptr<i8> = calloc(N + 2, 1)
if gcache == null || gdone == null { return 1 }
let MAX_INTERVALS: i64 = 400000
let il: ptr<i64> = calloc(MAX_INTERVALS, 8)
let ir: ptr<i64> = calloc(MAX_INTERVALS, 8)
let iub: ptr<i64> = calloc(MAX_INTERVALS, 8)
let igr: ptr<i64> = calloc(MAX_INTERVALS, 8)
if il == null || ir == null || iub == null || igr == null { return 1 }
let grid: i64 = 200000
let mut best: i64 = 0
let mut n_intervals: i64 = 0
# Coarse grid: evaluate g at 2, 2+grid, ...; intervals between consecutive
# grid points use the right endpoint's g for the upper bound.
let mut prev_pt: i64 = 2
let mut gprev: i64 = G(2, gcache, gdone, mark_buf, active_buf)
if gprev > best { best = gprev }
let mut x: i64 = 2 + grid
while x <= N {
let gx: i64 = G(x, gcache, gdone, mark_buf, active_buf)
if gx > best { best = gx }
il[n_intervals] = prev_pt
ir[n_intervals] = x
iub[n_intervals] = gx + (x - prev_pt)
igr[n_intervals] = gx
n_intervals = n_intervals + 1
prev_pt = x
x = x + grid
}
if prev_pt < N {
let gN: i64 = G(N, gcache, gdone, mark_buf, active_buf)
if gN > best { best = gN }
il[n_intervals] = prev_pt
ir[n_intervals] = N
iub[n_intervals] = gN + (N - prev_pt)
igr[n_intervals] = gN
n_intervals = n_intervals + 1
}
# Branch-and-bound: always pop the interval with the highest upper bound.
while n_intervals > 0 {
let mut max_idx: i64 = 0
let mut max_ub: i64 = iub[0]
for mi in 1..n_intervals {
if iub[mi] > max_ub { max_ub = iub[mi]; max_idx = mi }
}
if best >= max_ub { break }
let lo: i64 = il[max_idx]
let hi: i64 = ir[max_idx]
let gr: i64 = igr[max_idx]
n_intervals = n_intervals - 1
if max_idx < n_intervals {
il[max_idx] = il[n_intervals]
ir[max_idx] = ir[n_intervals]
iub[max_idx] = iub[n_intervals]
igr[max_idx] = igr[n_intervals]
}
if hi - lo > 1 {
let mid: i64 = (lo + hi) / 2
let gmid: i64 = G(mid, gcache, gdone, mark_buf, active_buf)
if gmid > best { best = gmid }
# Left child [lo, mid]: right endpoint is mid.
if mid - lo > 1 {
let ub_left: i64 = gmid + (mid - lo)
if ub_left > best {
il[n_intervals] = lo
ir[n_intervals] = mid
iub[n_intervals] = ub_left
igr[n_intervals] = gmid
n_intervals = n_intervals + 1
}
}
# Right child [mid, hi]: right endpoint stays hi, keep g(hi).
if hi - mid > 1 {
let ub_right: i64 = gr + (hi - mid)
if ub_right > best {
il[n_intervals] = mid
ir[n_intervals] = hi
iub[n_intervals] = ub_right
igr[n_intervals] = gr
n_intervals = n_intervals + 1
}
}
}
}
printf("%lld\n", best)
free(igr)
free(iub)
free(ir)
free(il)
free(gdone)
free(gcache)
free(active_buf)
free(mark_buf)
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 g_x_i64_ptr_i8_ptr_i64(int64_t x, int8_t* mark_buf, int64_t* active_buf);
int64_t G_i64_ptr_i32_ptr_i8_ptr_i8_ptr_i64(int64_t x, int32_t* gcache, int8_t* gdone, int8_t* mark_buf, int64_t* active_buf);
int32_t main(void);
int64_t g_x_i64_ptr_i8_ptr_i64(int64_t x, int8_t* mark_buf, int64_t* active_buf) {
if (x < 2) {
return 0;
}
if (x == 2) {
return 1;
}
int64_t n_active = 0;
int64_t y = 2;
while (y <= FLOW_CHECKED_DIV((x), (2))) {
int64_t sq = FLOW_CHECKED_MOD(((y * y)), (x));
if ((sq > 1 && mark_buf[sq] == 0)) {
mark_buf[sq] = 1;
active_buf[n_active] = sq;
n_active = (n_active + 1);
}
y = (y + 1);
}
int32_t __flow_step_1 = 1;
for (int32_t k = 0; (0 <= n_active) ? k < n_active : k > n_active; k += (0 <= n_active) ? 1 : -1) {
mark_buf[active_buf[k]] = 0;
}
int64_t length = 2;
int64_t mod_val = (x + 1);
while (n_active > 1) {
int64_t next_n = 0;
int32_t __flow_step_2 = 1;
for (int32_t k = 0; (0 <= n_active) ? k < n_active : k > n_active; k += (0 <= n_active) ? 1 : -1) {
int64_t v = FLOW_CHECKED_MOD(((active_buf[k] * active_buf[k])), (mod_val));
if ((v > 1 && mark_buf[v] == 0)) {
mark_buf[v] = 1;
active_buf[next_n] = v;
next_n = (next_n + 1);
}
}
int32_t __flow_step_3 = 1;
for (int32_t k = 0; (0 <= next_n) ? k < next_n : k > next_n; k += (0 <= next_n) ? 1 : -1) {
mark_buf[active_buf[k]] = 0;
}
n_active = next_n;
length = (length + 1);
mod_val = (mod_val + 1);
}
if (n_active == 0) {
return length;
}
int64_t v = active_buf[0];
while (v > 1) {
v = FLOW_CHECKED_MOD(((v * v)), (mod_val));
length = (length + 1);
mod_val = (mod_val + 1);
}
return length;
}
int64_t G_i64_ptr_i32_ptr_i8_ptr_i8_ptr_i64(int64_t x, int32_t* gcache, int8_t* gdone, int8_t* mark_buf, int64_t* active_buf) {
if (gdone[x] == 1) {
return ((int64_t)(gcache[x]));
}
int64_t v = g_x_i64_ptr_i8_ptr_i64(x, mark_buf, active_buf);
gcache[x] = ((int32_t)(v));
gdone[x] = 1;
return v;
}
int32_t main(void) {
int64_t N = 3000000;
int64_t BUFSZ = (N * 2);
int8_t* mark_buf = (int8_t*)(calloc(BUFSZ, 1));
int64_t* active_buf = (int64_t*)(calloc(BUFSZ, 8));
if ((mark_buf == NULL || active_buf == NULL)) {
return 1;
}
int32_t* gcache = (int32_t*)(calloc((N + 2), 4));
int8_t* gdone = (int8_t*)(calloc((N + 2), 1));
if ((gcache == NULL || gdone == NULL)) {
return 1;
}
int64_t MAX_INTERVALS = 400000;
int64_t* il = (int64_t*)(calloc(MAX_INTERVALS, 8));
int64_t* ir = (int64_t*)(calloc(MAX_INTERVALS, 8));
int64_t* iub = (int64_t*)(calloc(MAX_INTERVALS, 8));
int64_t* igr = (int64_t*)(calloc(MAX_INTERVALS, 8));
if ((((il == NULL || ir == NULL) || iub == NULL) || igr == NULL)) {
return 1;
}
int64_t grid = 200000;
int64_t best = 0;
int64_t n_intervals = 0;
int64_t prev_pt = 2;
int64_t gprev = G_i64_ptr_i32_ptr_i8_ptr_i8_ptr_i64(2, gcache, gdone, mark_buf, active_buf);
if (gprev > best) {
best = gprev;
}
int64_t x = (2 + grid);
while (x <= N) {
int64_t gx = G_i64_ptr_i32_ptr_i8_ptr_i8_ptr_i64(x, gcache, gdone, mark_buf, active_buf);
if (gx > best) {
best = gx;
}
il[n_intervals] = prev_pt;
ir[n_intervals] = x;
iub[n_intervals] = (gx + (x - prev_pt));
igr[n_intervals] = gx;
n_intervals = (n_intervals + 1);
prev_pt = x;
x = (x + grid);
}
if (prev_pt < N) {
int64_t gN = G_i64_ptr_i32_ptr_i8_ptr_i8_ptr_i64(N, gcache, gdone, mark_buf, active_buf);
if (gN > best) {
best = gN;
}
il[n_intervals] = prev_pt;
ir[n_intervals] = N;
iub[n_intervals] = (gN + (N - prev_pt));
igr[n_intervals] = gN;
n_intervals = (n_intervals + 1);
}
while (n_intervals > 0) {
int64_t max_idx = 0;
int64_t max_ub = iub[0];
int32_t __flow_step_4 = 1;
for (int32_t mi = 1; (1 <= n_intervals) ? mi < n_intervals : mi > n_intervals; mi += (1 <= n_intervals) ? 1 : -1) {
if (iub[mi] > max_ub) {
max_ub = iub[mi];
max_idx = mi;
}
}
if (best >= max_ub) {
break;
}
int64_t lo = il[max_idx];
int64_t hi = ir[max_idx];
int64_t gr = igr[max_idx];
n_intervals = (n_intervals - 1);
if (max_idx < n_intervals) {
il[max_idx] = il[n_intervals];
ir[max_idx] = ir[n_intervals];
iub[max_idx] = iub[n_intervals];
igr[max_idx] = igr[n_intervals];
}
if ((hi - lo) > 1) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
int64_t gmid = G_i64_ptr_i32_ptr_i8_ptr_i8_ptr_i64(mid, gcache, gdone, mark_buf, active_buf);
if (gmid > best) {
best = gmid;
}
if ((mid - lo) > 1) {
int64_t ub_left = (gmid + (mid - lo));
if (ub_left > best) {
il[n_intervals] = lo;
ir[n_intervals] = mid;
iub[n_intervals] = ub_left;
igr[n_intervals] = gmid;
n_intervals = (n_intervals + 1);
}
}
if ((hi - mid) > 1) {
int64_t ub_right = (gr + (hi - mid));
if (ub_right > best) {
il[n_intervals] = mid;
ir[n_intervals] = hi;
iub[n_intervals] = ub_right;
igr[n_intervals] = gr;
n_intervals = (n_intervals + 1);
}
}
}
}
printf("%lld\n", best);
free(igr);
free(iub);
free(ir);
free(il);
free(gdone);
free(gcache);
free(active_buf);
free(mark_buf);
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 @g_x(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> i64 {
%0 = arith.constant 2 : i32
%2 = arith.extsi %0 : i32 to i64
%1 = arith.cmpi slt, %arg0, %2 : i64
cf.cond_br %1, ^bb0, ^bb1
^bb0:
%3 = arith.constant 0 : i32
%4 = arith.extsi %3 : i32 to i64
func.return %4 : i64
^bb1:
cf.br ^bb2
^bb2:
%5 = arith.constant 2 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi eq, %arg0, %7 : i64
cf.cond_br %6, ^bb3, ^bb4
^bb3:
%8 = arith.constant 1 : i32
%9 = arith.extsi %8 : i32 to i64
func.return %9 : i64
^bb4:
cf.br ^bb5
^bb5:
%10 = arith.constant 0 : i32
%11 = arith.extsi %10 : i32 to i64
%12 = llvm.mlir.constant(1 : i64) : i64
%13 = llvm.alloca %12 x i64 : (i64) -> !llvm.ptr
llvm.store %11, %13 : i64, !llvm.ptr
%14 = arith.constant 2 : i32
%15 = arith.extsi %14 : i32 to i64
%16 = llvm.mlir.constant(1 : i64) : i64
%17 = llvm.alloca %16 x i64 : (i64) -> !llvm.ptr
llvm.store %15, %17 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%18 = llvm.load %17 : !llvm.ptr -> i64
%19 = arith.constant 2 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.divsi %arg0, %21 : i64
%22 = arith.cmpi sle, %18, %20 : i64
cf.cond_br %22, ^bb7, ^bb8
^bb7:
%23 = llvm.load %17 : !llvm.ptr -> i64
%24 = llvm.load %17 : !llvm.ptr -> i64
%25 = arith.muli %23, %24 : i64
%26 = arith.remsi %25, %arg0 : i64
%27 = arith.constant 1 : i32
%29 = arith.extsi %27 : i32 to i64
%28 = arith.cmpi sgt, %26, %29 : i64
%30 = scf.if %28 -> (i1) {
%32 = llvm.getelementptr %arg1[%26] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%31 = llvm.load %32 : !llvm.ptr -> i8
%33 = arith.constant 0 : i32
%35 = arith.extsi %31 : i8 to i32
%34 = arith.cmpi eq, %35, %33 : i32
scf.yield %34 : i1
} else {
%36 = arith.constant false
scf.yield %36 : i1
}
cf.cond_br %30, ^bb9, ^bb10
^bb9:
%37 = arith.constant 1 : i32
%38 = arith.trunci %37 : i32 to i8
%39 = llvm.getelementptr %arg1[%26] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %38, %39 : i8, !llvm.ptr
%40 = llvm.load %13 : !llvm.ptr -> i64
%41 = llvm.getelementptr %arg2[%40] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %26, %41 : i64, !llvm.ptr
%42 = llvm.load %13 : !llvm.ptr -> i64
%43 = arith.constant 1 : i32
%45 = arith.extsi %43 : i32 to i64
%44 = arith.addi %42, %45 : i64
llvm.store %44, %13 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%46 = llvm.load %17 : !llvm.ptr -> i64
%47 = arith.constant 1 : i32
%49 = arith.extsi %47 : i32 to i64
%48 = arith.addi %46, %49 : i64
llvm.store %48, %17 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%50 = arith.constant 0 : i32
%51 = llvm.load %13 : !llvm.ptr -> i64
%52 = arith.index_cast %50 : i32 to index
%53 = arith.index_cast %51 : i32 to index
%55 = arith.constant 1 : index
%56 = arith.constant -1 : index
%57 = arith.cmpi sle, %52, %53 : index
%54 = arith.select %57, %55, %56 : index
cf.br ^bb12(%52 : index)
^bb12(%58: index):
%59 = arith.cmpi slt, %58, %53 : index
%60 = arith.cmpi sgt, %58, %53 : index
%61 = arith.select %57, %59, %60 : i1
cf.cond_br %61, ^bb13(%58 : index), ^bb14(%58 : index)
^bb13(%62: index):
%63 = arith.constant 0 : i32
%65 = arith.index_cast %62 : index to i64
%66 = llvm.getelementptr %arg2[%65] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%64 = llvm.load %66 : !llvm.ptr -> i64
%67 = arith.trunci %63 : i32 to i8
%68 = llvm.getelementptr %arg1[%64] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %67, %68 : i8, !llvm.ptr
%69 = arith.addi %62, %54 : index
cf.br ^bb12(%69 : index)
^bb14(%70: index):
%71 = arith.constant 2 : i32
%72 = arith.extsi %71 : i32 to i64
%73 = llvm.mlir.constant(1 : i64) : i64
%74 = llvm.alloca %73 x i64 : (i64) -> !llvm.ptr
llvm.store %72, %74 : i64, !llvm.ptr
%75 = arith.constant 1 : i32
%77 = arith.extsi %75 : i32 to i64
%76 = arith.addi %arg0, %77 : i64
%78 = llvm.mlir.constant(1 : i64) : i64
%79 = llvm.alloca %78 x i64 : (i64) -> !llvm.ptr
llvm.store %76, %79 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%80 = llvm.load %13 : !llvm.ptr -> i64
%81 = arith.constant 1 : i32
%83 = arith.extsi %81 : i32 to i64
%82 = arith.cmpi sgt, %80, %83 : i64
cf.cond_br %82, ^bb16, ^bb17
^bb16:
%84 = arith.constant 0 : i32
%85 = arith.extsi %84 : i32 to i64
%86 = llvm.mlir.constant(1 : i64) : i64
%87 = llvm.alloca %86 x i64 : (i64) -> !llvm.ptr
llvm.store %85, %87 : i64, !llvm.ptr
%88 = arith.constant 0 : i32
%89 = llvm.load %13 : !llvm.ptr -> i64
%90 = arith.index_cast %88 : i32 to index
%91 = arith.index_cast %89 : i32 to index
%93 = arith.constant 1 : index
%94 = arith.constant -1 : index
%95 = arith.cmpi sle, %90, %91 : index
%92 = arith.select %95, %93, %94 : index
cf.br ^bb18(%90 : index)
^bb18(%96: index):
%97 = arith.cmpi slt, %96, %91 : index
%98 = arith.cmpi sgt, %96, %91 : index
%99 = arith.select %95, %97, %98 : i1
cf.cond_br %99, ^bb19(%96 : index), ^bb20(%96 : index)
^bb19(%100: index):
%102 = arith.index_cast %100 : index to i64
%103 = llvm.getelementptr %arg2[%102] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%101 = llvm.load %103 : !llvm.ptr -> i64
%105 = arith.index_cast %100 : index to i64
%106 = llvm.getelementptr %arg2[%105] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%104 = llvm.load %106 : !llvm.ptr -> i64
%107 = arith.muli %101, %104 : i64
%108 = llvm.load %79 : !llvm.ptr -> i64
%109 = arith.remsi %107, %108 : i64
%110 = arith.constant 1 : i32
%112 = arith.extsi %110 : i32 to i64
%111 = arith.cmpi sgt, %109, %112 : i64
%113 = scf.if %111 -> (i1) {
%115 = llvm.getelementptr %arg1[%109] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%114 = llvm.load %115 : !llvm.ptr -> i8
%116 = arith.constant 0 : i32
%118 = arith.extsi %114 : i8 to i32
%117 = arith.cmpi eq, %118, %116 : i32
scf.yield %117 : i1
} else {
%119 = arith.constant false
scf.yield %119 : i1
}
cf.cond_br %113, ^bb21, ^bb22
^bb21:
%120 = arith.constant 1 : i32
%121 = arith.trunci %120 : i32 to i8
%122 = llvm.getelementptr %arg1[%109] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %121, %122 : i8, !llvm.ptr
%123 = llvm.load %87 : !llvm.ptr -> i64
%124 = llvm.getelementptr %arg2[%123] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %109, %124 : i64, !llvm.ptr
%125 = llvm.load %87 : !llvm.ptr -> i64
%126 = arith.constant 1 : i32
%128 = arith.extsi %126 : i32 to i64
%127 = arith.addi %125, %128 : i64
llvm.store %127, %87 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%129 = arith.addi %100, %92 : index
cf.br ^bb18(%129 : index)
^bb20(%130: index):
%131 = arith.constant 0 : i32
%132 = llvm.load %87 : !llvm.ptr -> i64
%133 = arith.index_cast %131 : i32 to index
%134 = arith.index_cast %132 : i32 to index
%136 = arith.constant 1 : index
%137 = arith.constant -1 : index
%138 = arith.cmpi sle, %133, %134 : index
%135 = arith.select %138, %136, %137 : index
cf.br ^bb24(%133 : index)
^bb24(%139: index):
%140 = arith.cmpi slt, %139, %134 : index
%141 = arith.cmpi sgt, %139, %134 : index
%142 = arith.select %138, %140, %141 : i1
cf.cond_br %142, ^bb25(%139 : index), ^bb26(%139 : index)
^bb25(%143: index):
%144 = arith.constant 0 : i32
%146 = arith.index_cast %143 : index to i64
%147 = llvm.getelementptr %arg2[%146] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%145 = llvm.load %147 : !llvm.ptr -> i64
%148 = arith.trunci %144 : i32 to i8
%149 = llvm.getelementptr %arg1[%145] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %148, %149 : i8, !llvm.ptr
%150 = arith.addi %143, %135 : index
cf.br ^bb24(%150 : index)
^bb26(%151: index):
%152 = llvm.load %87 : !llvm.ptr -> i64
llvm.store %152, %13 : i64, !llvm.ptr
%153 = llvm.load %74 : !llvm.ptr -> i64
%154 = arith.constant 1 : i32
%156 = arith.extsi %154 : i32 to i64
%155 = arith.addi %153, %156 : i64
llvm.store %155, %74 : i64, !llvm.ptr
%157 = llvm.load %79 : !llvm.ptr -> i64
%158 = arith.constant 1 : i32
%160 = arith.extsi %158 : i32 to i64
%159 = arith.addi %157, %160 : i64
llvm.store %159, %79 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%161 = llvm.load %13 : !llvm.ptr -> i64
%162 = arith.constant 0 : i32
%164 = arith.extsi %162 : i32 to i64
%163 = arith.cmpi eq, %161, %164 : i64
cf.cond_br %163, ^bb27, ^bb28
^bb27:
%165 = llvm.load %74 : !llvm.ptr -> i64
func.return %165 : i64
^bb28:
cf.br ^bb29
^bb29:
%167 = arith.constant 0 : i32
%168 = arith.extsi %167 : i32 to i64
%169 = llvm.getelementptr %arg2[%168] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%166 = llvm.load %169 : !llvm.ptr -> i64
%170 = llvm.mlir.constant(1 : i64) : i64
%171 = llvm.alloca %170 x i64 : (i64) -> !llvm.ptr
llvm.store %166, %171 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%172 = llvm.load %171 : !llvm.ptr -> i64
%173 = arith.constant 1 : i32
%175 = arith.extsi %173 : i32 to i64
%174 = arith.cmpi sgt, %172, %175 : i64
cf.cond_br %174, ^bb31, ^bb32
^bb31:
%176 = llvm.load %171 : !llvm.ptr -> i64
%177 = llvm.load %171 : !llvm.ptr -> i64
%178 = arith.muli %176, %177 : i64
%179 = llvm.load %79 : !llvm.ptr -> i64
%180 = arith.remsi %178, %179 : i64
llvm.store %180, %171 : i64, !llvm.ptr
%181 = llvm.load %74 : !llvm.ptr -> i64
%182 = arith.constant 1 : i32
%184 = arith.extsi %182 : i32 to i64
%183 = arith.addi %181, %184 : i64
llvm.store %183, %74 : i64, !llvm.ptr
%185 = llvm.load %79 : !llvm.ptr -> i64
%186 = arith.constant 1 : i32
%188 = arith.extsi %186 : i32 to i64
%187 = arith.addi %185, %188 : i64
llvm.store %187, %79 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%189 = llvm.load %74 : !llvm.ptr -> i64
func.return %189 : i64
}
func.func @G(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: !llvm.ptr) -> i64 {
%191 = llvm.getelementptr %arg2[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%190 = llvm.load %191 : !llvm.ptr -> i8
%192 = arith.constant 1 : i32
%194 = arith.extsi %190 : i8 to i32
%193 = arith.cmpi eq, %194, %192 : i32
cf.cond_br %193, ^bb33, ^bb34
^bb33:
%196 = llvm.getelementptr %arg1[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%195 = llvm.load %196 : !llvm.ptr -> i32
%197 = arith.extsi %195 : i32 to i64
func.return %197 : i64
^bb34:
cf.br ^bb35
^bb35:
%198 = func.call @g_x(%arg0, %arg3, %arg4) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%199 = arith.trunci %198 : i64 to i32
%200 = llvm.getelementptr %arg1[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %199, %200 : i32, !llvm.ptr
%201 = arith.constant 1 : i32
%202 = arith.trunci %201 : i32 to i8
%203 = llvm.getelementptr %arg2[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %202, %203 : i8, !llvm.ptr
func.return %198 : i64
}
func.func @main() -> i32 {
%204 = arith.constant 3000000 : i32
%205 = arith.extsi %204 : i32 to i64
%206 = arith.constant 2 : i32
%208 = arith.extsi %206 : i32 to i64
%207 = arith.muli %205, %208 : i64
%210 = arith.constant 1 : i32
%211 = arith.extsi %210 : i32 to i64
%209 = func.call @calloc(%207, %211) : (i64, i64) -> !llvm.ptr
%213 = arith.constant 8 : i32
%214 = arith.extsi %213 : i32 to i64
%212 = func.call @calloc(%207, %214) : (i64, i64) -> !llvm.ptr
%215 = llvm.mlir.zero : !llvm.ptr
%216 = llvm.icmp "eq" %209, %215 : !llvm.ptr
%217 = scf.if %216 -> (i1) {
%218 = arith.constant true
scf.yield %218 : i1
} else {
%219 = llvm.mlir.zero : !llvm.ptr
%220 = llvm.icmp "eq" %212, %219 : !llvm.ptr
scf.yield %220 : i1
}
cf.cond_br %217, ^bb36, ^bb37
^bb36:
%221 = arith.constant 1 : i32
func.return %221 : i32
^bb37:
cf.br ^bb38
^bb38:
%223 = arith.constant 2 : i32
%225 = arith.extsi %223 : i32 to i64
%224 = arith.addi %205, %225 : i64
%226 = arith.constant 4 : i32
%227 = arith.extsi %226 : i32 to i64
%222 = func.call @calloc(%224, %227) : (i64, i64) -> !llvm.ptr
%229 = arith.constant 2 : i32
%231 = arith.extsi %229 : i32 to i64
%230 = arith.addi %205, %231 : i64
%232 = arith.constant 1 : i32
%233 = arith.extsi %232 : i32 to i64
%228 = func.call @calloc(%230, %233) : (i64, i64) -> !llvm.ptr
%234 = llvm.mlir.zero : !llvm.ptr
%235 = llvm.icmp "eq" %222, %234 : !llvm.ptr
%236 = scf.if %235 -> (i1) {
%237 = arith.constant true
scf.yield %237 : i1
} else {
%238 = llvm.mlir.zero : !llvm.ptr
%239 = llvm.icmp "eq" %228, %238 : !llvm.ptr
scf.yield %239 : i1
}
cf.cond_br %236, ^bb39, ^bb40
^bb39:
%240 = arith.constant 1 : i32
func.return %240 : i32
^bb40:
cf.br ^bb41
^bb41:
%241 = arith.constant 400000 : i32
%242 = arith.extsi %241 : i32 to i64
%244 = arith.constant 8 : i32
%245 = arith.extsi %244 : i32 to i64
%243 = func.call @calloc(%242, %245) : (i64, i64) -> !llvm.ptr
%247 = arith.constant 8 : i32
%248 = arith.extsi %247 : i32 to i64
%246 = func.call @calloc(%242, %248) : (i64, i64) -> !llvm.ptr
%250 = arith.constant 8 : i32
%251 = arith.extsi %250 : i32 to i64
%249 = func.call @calloc(%242, %251) : (i64, i64) -> !llvm.ptr
%253 = arith.constant 8 : i32
%254 = arith.extsi %253 : i32 to i64
%252 = func.call @calloc(%242, %254) : (i64, i64) -> !llvm.ptr
%255 = llvm.mlir.zero : !llvm.ptr
%256 = llvm.icmp "eq" %243, %255 : !llvm.ptr
%257 = scf.if %256 -> (i1) {
%258 = arith.constant true
scf.yield %258 : i1
} else {
%259 = llvm.mlir.zero : !llvm.ptr
%260 = llvm.icmp "eq" %246, %259 : !llvm.ptr
scf.yield %260 : i1
}
%261 = scf.if %257 -> (i1) {
%262 = arith.constant true
scf.yield %262 : i1
} else {
%263 = llvm.mlir.zero : !llvm.ptr
%264 = llvm.icmp "eq" %249, %263 : !llvm.ptr
scf.yield %264 : i1
}
%265 = scf.if %261 -> (i1) {
%266 = arith.constant true
scf.yield %266 : i1
} else {
%267 = llvm.mlir.zero : !llvm.ptr
%268 = llvm.icmp "eq" %252, %267 : !llvm.ptr
scf.yield %268 : i1
}
cf.cond_br %265, ^bb42, ^bb43
^bb42:
%269 = arith.constant 1 : i32
func.return %269 : i32
^bb43:
cf.br ^bb44
^bb44:
%270 = arith.constant 200000 : i32
%271 = arith.extsi %270 : i32 to i64
%272 = arith.constant 0 : i32
%273 = arith.extsi %272 : i32 to i64
%274 = llvm.mlir.constant(1 : i64) : i64
%275 = llvm.alloca %274 x i64 : (i64) -> !llvm.ptr
llvm.store %273, %275 : i64, !llvm.ptr
%276 = arith.constant 0 : i32
%277 = arith.extsi %276 : i32 to i64
%278 = llvm.mlir.constant(1 : i64) : i64
%279 = llvm.alloca %278 x i64 : (i64) -> !llvm.ptr
llvm.store %277, %279 : i64, !llvm.ptr
%280 = arith.constant 2 : i32
%281 = arith.extsi %280 : i32 to i64
%282 = llvm.mlir.constant(1 : i64) : i64
%283 = llvm.alloca %282 x i64 : (i64) -> !llvm.ptr
llvm.store %281, %283 : i64, !llvm.ptr
%285 = arith.constant 2 : i32
%286 = arith.extsi %285 : i32 to i64
%284 = func.call @G(%286, %222, %228, %209, %212) : (i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i64
%287 = llvm.mlir.constant(1 : i64) : i64
%288 = llvm.alloca %287 x i64 : (i64) -> !llvm.ptr
llvm.store %284, %288 : i64, !llvm.ptr
%289 = llvm.load %288 : !llvm.ptr -> i64
%290 = llvm.load %275 : !llvm.ptr -> i64
%291 = arith.cmpi sgt, %289, %290 : i64
cf.cond_br %291, ^bb45, ^bb46
^bb45:
%292 = llvm.load %288 : !llvm.ptr -> i64
llvm.store %292, %275 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%293 = arith.constant 2 : i32
%295 = arith.extsi %293 : i32 to i64
%294 = arith.addi %295, %271 : i64
%296 = llvm.mlir.constant(1 : i64) : i64
%297 = llvm.alloca %296 x i64 : (i64) -> !llvm.ptr
llvm.store %294, %297 : i64, !llvm.ptr
cf.br ^bb48
^bb48:
%298 = llvm.load %297 : !llvm.ptr -> i64
%299 = arith.cmpi sle, %298, %205 : i64
cf.cond_br %299, ^bb49, ^bb50
^bb49:
%301 = llvm.load %297 : !llvm.ptr -> i64
%300 = func.call @G(%301, %222, %228, %209, %212) : (i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i64
%302 = llvm.load %275 : !llvm.ptr -> i64
%303 = arith.cmpi sgt, %300, %302 : i64
cf.cond_br %303, ^bb51, ^bb52
^bb51:
llvm.store %300, %275 : i64, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
%304 = llvm.load %283 : !llvm.ptr -> i64
%305 = llvm.load %279 : !llvm.ptr -> i64
%306 = llvm.getelementptr %243[%305] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %304, %306 : i64, !llvm.ptr
%307 = llvm.load %297 : !llvm.ptr -> i64
%308 = llvm.load %279 : !llvm.ptr -> i64
%309 = llvm.getelementptr %246[%308] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %307, %309 : i64, !llvm.ptr
%310 = llvm.load %297 : !llvm.ptr -> i64
%311 = llvm.load %283 : !llvm.ptr -> i64
%312 = arith.subi %310, %311 : i64
%313 = arith.addi %300, %312 : i64
%314 = llvm.load %279 : !llvm.ptr -> i64
%315 = llvm.getelementptr %249[%314] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %313, %315 : i64, !llvm.ptr
%316 = llvm.load %279 : !llvm.ptr -> i64
%317 = llvm.getelementptr %252[%316] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %300, %317 : i64, !llvm.ptr
%318 = llvm.load %279 : !llvm.ptr -> i64
%319 = arith.constant 1 : i32
%321 = arith.extsi %319 : i32 to i64
%320 = arith.addi %318, %321 : i64
llvm.store %320, %279 : i64, !llvm.ptr
%322 = llvm.load %297 : !llvm.ptr -> i64
llvm.store %322, %283 : i64, !llvm.ptr
%323 = llvm.load %297 : !llvm.ptr -> i64
%324 = arith.addi %323, %271 : i64
llvm.store %324, %297 : i64, !llvm.ptr
cf.br ^bb48
^bb50:
%325 = llvm.load %283 : !llvm.ptr -> i64
%326 = arith.cmpi slt, %325, %205 : i64
cf.cond_br %326, ^bb54, ^bb55
^bb54:
%327 = func.call @G(%205, %222, %228, %209, %212) : (i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i64
%328 = llvm.load %275 : !llvm.ptr -> i64
%329 = arith.cmpi sgt, %327, %328 : i64
cf.cond_br %329, ^bb57, ^bb58
^bb57:
llvm.store %327, %275 : i64, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%330 = llvm.load %283 : !llvm.ptr -> i64
%331 = llvm.load %279 : !llvm.ptr -> i64
%332 = llvm.getelementptr %243[%331] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %330, %332 : i64, !llvm.ptr
%333 = llvm.load %279 : !llvm.ptr -> i64
%334 = llvm.getelementptr %246[%333] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %205, %334 : i64, !llvm.ptr
%335 = llvm.load %283 : !llvm.ptr -> i64
%336 = arith.subi %205, %335 : i64
%337 = arith.addi %327, %336 : i64
%338 = llvm.load %279 : !llvm.ptr -> i64
%339 = llvm.getelementptr %249[%338] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %337, %339 : i64, !llvm.ptr
%340 = llvm.load %279 : !llvm.ptr -> i64
%341 = llvm.getelementptr %252[%340] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %327, %341 : i64, !llvm.ptr
%342 = llvm.load %279 : !llvm.ptr -> i64
%343 = arith.constant 1 : i32
%345 = arith.extsi %343 : i32 to i64
%344 = arith.addi %342, %345 : i64
llvm.store %344, %279 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
cf.br ^bb60
^bb60:
%346 = llvm.load %279 : !llvm.ptr -> i64
%347 = arith.constant 0 : i32
%349 = arith.extsi %347 : i32 to i64
%348 = arith.cmpi sgt, %346, %349 : i64
cf.cond_br %348, ^bb61, ^bb62
^bb61:
%350 = arith.constant 0 : i32
%351 = arith.extsi %350 : i32 to i64
%352 = llvm.mlir.constant(1 : i64) : i64
%353 = llvm.alloca %352 x i64 : (i64) -> !llvm.ptr
llvm.store %351, %353 : i64, !llvm.ptr
%355 = arith.constant 0 : i32
%356 = arith.extsi %355 : i32 to i64
%357 = llvm.getelementptr %249[%356] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%354 = llvm.load %357 : !llvm.ptr -> i64
%358 = llvm.mlir.constant(1 : i64) : i64
%359 = llvm.alloca %358 x i64 : (i64) -> !llvm.ptr
llvm.store %354, %359 : i64, !llvm.ptr
%360 = arith.constant 1 : i32
%361 = llvm.load %279 : !llvm.ptr -> i64
%362 = arith.index_cast %360 : i32 to index
%363 = arith.index_cast %361 : i32 to index
%365 = arith.constant 1 : index
%366 = arith.constant -1 : index
%367 = arith.cmpi sle, %362, %363 : index
%364 = arith.select %367, %365, %366 : index
cf.br ^bb63(%362 : index)
^bb63(%368: index):
%369 = arith.cmpi slt, %368, %363 : index
%370 = arith.cmpi sgt, %368, %363 : index
%371 = arith.select %367, %369, %370 : i1
cf.cond_br %371, ^bb64(%368 : index), ^bb65(%368 : index)
^bb64(%372: index):
%374 = arith.index_cast %372 : index to i64
%375 = llvm.getelementptr %249[%374] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%373 = llvm.load %375 : !llvm.ptr -> i64
%376 = llvm.load %359 : !llvm.ptr -> i64
%377 = arith.cmpi sgt, %373, %376 : i64
cf.cond_br %377, ^bb66, ^bb67
^bb66:
%379 = arith.index_cast %372 : index to i64
%380 = llvm.getelementptr %249[%379] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%378 = llvm.load %380 : !llvm.ptr -> i64
llvm.store %378, %359 : i64, !llvm.ptr
%381 = arith.index_cast %372 : index to i64
llvm.store %381, %353 : i64, !llvm.ptr
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
%382 = arith.addi %372, %364 : index
cf.br ^bb63(%382 : index)
^bb65(%383: index):
%384 = llvm.load %275 : !llvm.ptr -> i64
%385 = llvm.load %359 : !llvm.ptr -> i64
%386 = arith.cmpi sge, %384, %385 : i64
cf.cond_br %386, ^bb69, ^bb70
^bb69:
cf.br ^bb62
^bb70:
cf.br ^bb71
^bb71:
%388 = llvm.load %353 : !llvm.ptr -> i64
%389 = llvm.getelementptr %243[%388] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%387 = llvm.load %389 : !llvm.ptr -> i64
%391 = llvm.load %353 : !llvm.ptr -> i64
%392 = llvm.getelementptr %246[%391] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%390 = llvm.load %392 : !llvm.ptr -> i64
%394 = llvm.load %353 : !llvm.ptr -> i64
%395 = llvm.getelementptr %252[%394] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%393 = llvm.load %395 : !llvm.ptr -> i64
%396 = llvm.load %279 : !llvm.ptr -> i64
%397 = arith.constant 1 : i32
%399 = arith.extsi %397 : i32 to i64
%398 = arith.subi %396, %399 : i64
llvm.store %398, %279 : i64, !llvm.ptr
%400 = llvm.load %353 : !llvm.ptr -> i64
%401 = llvm.load %279 : !llvm.ptr -> i64
%402 = arith.cmpi slt, %400, %401 : i64
cf.cond_br %402, ^bb72, ^bb73
^bb72:
%404 = llvm.load %279 : !llvm.ptr -> i64
%405 = llvm.getelementptr %243[%404] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%403 = llvm.load %405 : !llvm.ptr -> i64
%406 = llvm.load %353 : !llvm.ptr -> i64
%407 = llvm.getelementptr %243[%406] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %403, %407 : i64, !llvm.ptr
%409 = llvm.load %279 : !llvm.ptr -> i64
%410 = llvm.getelementptr %246[%409] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%408 = llvm.load %410 : !llvm.ptr -> i64
%411 = llvm.load %353 : !llvm.ptr -> i64
%412 = llvm.getelementptr %246[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %408, %412 : i64, !llvm.ptr
%414 = llvm.load %279 : !llvm.ptr -> i64
%415 = llvm.getelementptr %249[%414] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%413 = llvm.load %415 : !llvm.ptr -> i64
%416 = llvm.load %353 : !llvm.ptr -> i64
%417 = llvm.getelementptr %249[%416] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %413, %417 : i64, !llvm.ptr
%419 = llvm.load %279 : !llvm.ptr -> i64
%420 = llvm.getelementptr %252[%419] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%418 = llvm.load %420 : !llvm.ptr -> i64
%421 = llvm.load %353 : !llvm.ptr -> i64
%422 = llvm.getelementptr %252[%421] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %418, %422 : i64, !llvm.ptr
cf.br ^bb74
^bb73:
cf.br ^bb74
^bb74:
%423 = arith.subi %390, %387 : i64
%424 = arith.constant 1 : i32
%426 = arith.extsi %424 : i32 to i64
%425 = arith.cmpi sgt, %423, %426 : i64
cf.cond_br %425, ^bb75, ^bb76
^bb75:
%427 = arith.addi %387, %390 : i64
%428 = arith.constant 2 : i32
%430 = arith.extsi %428 : i32 to i64
%429 = arith.divsi %427, %430 : i64
%431 = func.call @G(%429, %222, %228, %209, %212) : (i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i64
%432 = llvm.load %275 : !llvm.ptr -> i64
%433 = arith.cmpi sgt, %431, %432 : i64
cf.cond_br %433, ^bb78, ^bb79
^bb78:
llvm.store %431, %275 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%434 = arith.subi %429, %387 : i64
%435 = arith.constant 1 : i32
%437 = arith.extsi %435 : i32 to i64
%436 = arith.cmpi sgt, %434, %437 : i64
cf.cond_br %436, ^bb81, ^bb82
^bb81:
%438 = arith.subi %429, %387 : i64
%439 = arith.addi %431, %438 : i64
%440 = llvm.load %275 : !llvm.ptr -> i64
%441 = arith.cmpi sgt, %439, %440 : i64
cf.cond_br %441, ^bb84, ^bb85
^bb84:
%442 = llvm.load %279 : !llvm.ptr -> i64
%443 = llvm.getelementptr %243[%442] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %387, %443 : i64, !llvm.ptr
%444 = llvm.load %279 : !llvm.ptr -> i64
%445 = llvm.getelementptr %246[%444] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %429, %445 : i64, !llvm.ptr
%446 = llvm.load %279 : !llvm.ptr -> i64
%447 = llvm.getelementptr %249[%446] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %439, %447 : i64, !llvm.ptr
%448 = llvm.load %279 : !llvm.ptr -> i64
%449 = llvm.getelementptr %252[%448] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %431, %449 : i64, !llvm.ptr
%450 = llvm.load %279 : !llvm.ptr -> i64
%451 = arith.constant 1 : i32
%453 = arith.extsi %451 : i32 to i64
%452 = arith.addi %450, %453 : i64
llvm.store %452, %279 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%454 = arith.subi %390, %429 : i64
%455 = arith.constant 1 : i32
%457 = arith.extsi %455 : i32 to i64
%456 = arith.cmpi sgt, %454, %457 : i64
cf.cond_br %456, ^bb87, ^bb88
^bb87:
%458 = arith.subi %390, %429 : i64
%459 = arith.addi %393, %458 : i64
%460 = llvm.load %275 : !llvm.ptr -> i64
%461 = arith.cmpi sgt, %459, %460 : i64
cf.cond_br %461, ^bb90, ^bb91
^bb90:
%462 = llvm.load %279 : !llvm.ptr -> i64
%463 = llvm.getelementptr %243[%462] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %429, %463 : i64, !llvm.ptr
%464 = llvm.load %279 : !llvm.ptr -> i64
%465 = llvm.getelementptr %246[%464] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %390, %465 : i64, !llvm.ptr
%466 = llvm.load %279 : !llvm.ptr -> i64
%467 = llvm.getelementptr %249[%466] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %459, %467 : i64, !llvm.ptr
%468 = llvm.load %279 : !llvm.ptr -> i64
%469 = llvm.getelementptr %252[%468] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %393, %469 : i64, !llvm.ptr
%470 = llvm.load %279 : !llvm.ptr -> i64
%471 = arith.constant 1 : i32
%473 = arith.extsi %471 : i32 to i64
%472 = arith.addi %470, %473 : i64
llvm.store %472, %279 : i64, !llvm.ptr
cf.br ^bb92
^bb91:
cf.br ^bb92
^bb92:
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
cf.br ^bb77
^bb76:
cf.br ^bb77
^bb77:
cf.br ^bb60
^bb62:
%474 = llvm.mlir.addressof @str_0 : !llvm.ptr
%475 = llvm.load %275 : !llvm.ptr -> i64
%476 = llvm.call @printf(%474, %475) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%252) : (!llvm.ptr) -> ()
func.call @free(%249) : (!llvm.ptr) -> ()
func.call @free(%246) : (!llvm.ptr) -> ()
func.call @free(%243) : (!llvm.ptr) -> ()
func.call @free(%228) : (!llvm.ptr) -> ()
func.call @free(%222) : (!llvm.ptr) -> ()
func.call @free(%212) : (!llvm.ptr) -> ()
func.call @free(%209) : (!llvm.ptr) -> ()
%485 = arith.constant 0 : i32
func.return %485 : i32
}
}