Problem 280
Expected steps for ant moving 5 seeds on 5x5 grid.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^5) | O(n * s^2) |
|---|
| Space complexity | O(n^2) | O(s^2) |
|---|
| Approach | Flow solution | Markov chain or DP over states |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 280
# Expected steps for ant moving 5 seeds on 5x5 grid.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function popcount(x0: i64) -> i64 {
let mut x: i64 = x0
let mut c: i64 = 0
while x != 0 {
c = c + 1
x = x & (x - 1)
}
return c
}
function make_hash(x: i64, y: i64, carries: i64, top: i64, bot: i64) -> i64 {
let mut h: i64 = carries
h = (h << 5) + top
h = (h << 5) + bot
h = h * 5 + x
h = h * 5 + y
return h
}
function is_final(top: i64, carries: i64) -> bool {
return popcount(top) == 5 && carries == 0
}
function is_valid(x: i64, y: i64, carries: i64, top: i64, bot: i64) -> bool {
let one: i64 = 1
if y == 0 && carries == 1 && (top & (one << x)) == 0 {
return false
}
if y == 4 && carries == 0 && (bot & (one << x)) != 0 {
return false
}
if is_final(top, carries) && y != 0 {
return false
}
let mut seeds: i64 = popcount(top) + popcount(bot)
if carries == 1 { seeds = seeds + 1 }
return seeds == 5
}
function main() -> i32 {
let GRID: i64 = 5
let all_bits: i64 = 31
let one: i64 = 1
let max_hash: i64 = 50000
let is_state: ptr<i8> = calloc(max_hash + 1, 1)
let is_fin: ptr<i8> = calloc(max_hash + 1, 1)
let ntrans: ptr<i32> = calloc(max_hash + 1, 4)
let trans: ptr<i32> = calloc((max_hash + 1) * 4, 4)
let last: ptr<f64> = calloc(max_hash + 1, 8)
let nxt: ptr<f64> = calloc(max_hash + 1, 8)
let state_list: ptr<i32> = calloc(12000, 4)
let mut nstates: i64 = 0
let mut x: i64 = 0
while x < GRID {
let mut y: i64 = 0
while y < GRID {
let mut carries: i64 = 0
while carries <= 1 {
let mut top: i64 = 0
while top <= all_bits {
let mut bot: i64 = 0
while bot <= all_bits {
if is_valid(x, y, carries, top, bot) {
let h: i64 = make_hash(x, y, carries, top, bot)
is_state[h] = 1
state_list[nstates] = h as i32
nstates = nstates + 1
if is_final(top, carries) {
is_fin[h] = 1
}
}
bot = bot + 1
}
top = top + 1
}
carries = carries + 1
}
y = y + 1
}
x = x + 1
}
let mut si: i64 = 0
while si < nstates {
let h: i64 = state_list[si] as i64
if is_fin[h] == 1 {
si = si + 1
continue
}
# decode hash: ... reverse make_hash
let mut hh: i64 = h
let y0: i64 = hh % 5
hh = hh / 5
let x0: i64 = hh % 5
hh = hh / 5
let bot0: i64 = hh & 31
hh = hh >> 5
let top0: i64 = hh & 31
hh = hh >> 5
let car0: i64 = hh & 1
let mut nt: i64 = 0
let mut dir: i64 = 0
while dir < 4 {
let mut cx: i64 = x0
let mut cy: i64 = y0
let mut ok: bool = false
if dir == 0 && y0 > 0 { cy = y0 - 1; ok = true }
elif dir == 1 && y0 < 4 { cy = y0 + 1; ok = true }
elif dir == 2 && x0 > 0 { cx = x0 - 1; ok = true }
elif dir == 3 && x0 < 4 { cx = x0 + 1; ok = true }
if ok {
let mut ccar: i64 = car0
let mut ctop: i64 = top0
let mut cbot: i64 = bot0
if ccar == 1 && cy == 0 && (ctop & (one << cx)) == 0 {
ccar = 0
ctop = ctop | (one << cx)
}
if ccar == 0 && cy == 4 && (cbot & (one << cx)) != 0 {
ccar = 1
cbot = cbot & (all_bits ^ (one << cx))
}
let nh: i64 = make_hash(cx, cy, ccar, ctop, cbot)
trans[h * 4 + nt] = nh as i32
nt = nt + 1
}
dir = dir + 1
}
ntrans[h] = nt as i32
si = si + 1
}
let init: i64 = make_hash(2, 2, 0, 0, all_bits)
last[init] = 1.0
let mut expected: f64 = 0.0
let mut iteration: i64 = 1
let eps: f64 = 0.0000000001
while true {
let mut i: i64 = 0
while i <= max_hash {
nxt[i] = 0.0
i = i + 1
}
si = 0
while si < nstates {
let h: i64 = state_list[si] as i64
let nt: i64 = ntrans[h] as i64
if nt > 0 {
let p: f64 = last[h] / (nt as f64)
let mut t: i64 = 0
while t < nt {
let nh: i64 = trans[h * 4 + t] as i64
nxt[nh] = nxt[nh] + p
t = t + 1
}
}
si = si + 1
}
i = 0
while i <= max_hash {
last[i] = nxt[i]
i = i + 1
}
let mut add: f64 = 0.0
si = 0
while si < nstates {
let h: i64 = state_list[si] as i64
if is_fin[h] == 1 {
add = add + last[h]
}
si = si + 1
}
add = add * (iteration as f64)
expected = expected + add
if add < eps && expected > 1.0 {
break
}
iteration = iteration + 1
}
printf("%.6f\n", expected)
free(is_state); free(is_fin); free(ntrans); free(trans); free(last); free(nxt); free(state_list)
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 popcount_i64(int64_t x0);
int64_t make_hash_i64_i64_i64_i64_i64(int64_t x, int64_t y, int64_t carries, int64_t top, int64_t bot);
bool is_final_i64_i64(int64_t top, int64_t carries);
bool is_valid_i64_i64_i64_i64_i64(int64_t x, int64_t y, int64_t carries, int64_t top, int64_t bot);
int32_t main(void);
int64_t popcount_i64(int64_t x0) {
int64_t x = x0;
int64_t c = 0;
while (x != 0) {
c = (c + 1);
x = (x & (x - 1));
}
return c;
}
int64_t make_hash_i64_i64_i64_i64_i64(int64_t x, int64_t y, int64_t carries, int64_t top, int64_t bot) {
int64_t h = carries;
h = (FLOW_CHECKED_SHL((h), (5)) + top);
h = (FLOW_CHECKED_SHL((h), (5)) + bot);
h = ((h * 5) + x);
h = ((h * 5) + y);
return h;
}
bool is_final_i64_i64(int64_t top, int64_t carries) {
return (popcount_i64(top) == 5 && carries == 0);
}
bool is_valid_i64_i64_i64_i64_i64(int64_t x, int64_t y, int64_t carries, int64_t top, int64_t bot) {
int64_t one = 1;
if (((y == 0 && carries == 1) && (top & FLOW_CHECKED_SHL((one), (x))) == 0)) {
return 0;
}
if (((y == 4 && carries == 0) && (bot & FLOW_CHECKED_SHL((one), (x))) != 0)) {
return 0;
}
if ((is_final_i64_i64(top, carries) && y != 0)) {
return 0;
}
int64_t seeds = (popcount_i64(top) + popcount_i64(bot));
if (carries == 1) {
seeds = (seeds + 1);
}
return seeds == 5;
}
int32_t main(void) {
int64_t GRID = 5;
int64_t all_bits = 31;
int64_t one = 1;
int64_t max_hash = 50000;
int8_t* is_state = (int8_t*)(calloc((max_hash + 1), 1));
int8_t* is_fin = (int8_t*)(calloc((max_hash + 1), 1));
int32_t* ntrans = (int32_t*)(calloc((max_hash + 1), 4));
int32_t* trans = (int32_t*)(calloc(((max_hash + 1) * 4), 4));
double* last = (double*)(calloc((max_hash + 1), 8));
double* nxt = (double*)(calloc((max_hash + 1), 8));
int32_t* state_list = (int32_t*)(calloc(12000, 4));
int64_t nstates = 0;
int64_t x = 0;
while (x < GRID) {
int64_t y = 0;
while (y < GRID) {
int64_t carries = 0;
while (carries <= 1) {
int64_t top = 0;
while (top <= all_bits) {
int64_t bot = 0;
while (bot <= all_bits) {
if (is_valid_i64_i64_i64_i64_i64(x, y, carries, top, bot)) {
int64_t h = make_hash_i64_i64_i64_i64_i64(x, y, carries, top, bot);
is_state[h] = 1;
state_list[nstates] = ((int32_t)(h));
nstates = (nstates + 1);
if (is_final_i64_i64(top, carries)) {
is_fin[h] = 1;
}
}
bot = (bot + 1);
}
top = (top + 1);
}
carries = (carries + 1);
}
y = (y + 1);
}
x = (x + 1);
}
int64_t si = 0;
while (si < nstates) {
int64_t h = ((int64_t)(state_list[si]));
if (is_fin[h] == 1) {
si = (si + 1);
continue;
}
int64_t hh = h;
int64_t y0 = FLOW_CHECKED_MOD((hh), (5));
hh = FLOW_CHECKED_DIV((hh), (5));
int64_t x0 = FLOW_CHECKED_MOD((hh), (5));
hh = FLOW_CHECKED_DIV((hh), (5));
int64_t bot0 = (hh & 31);
hh = FLOW_CHECKED_SHR((hh), (5));
int64_t top0 = (hh & 31);
hh = FLOW_CHECKED_SHR((hh), (5));
int64_t car0 = (hh & 1);
int64_t nt = 0;
int64_t dir = 0;
while (dir < 4) {
int64_t cx = x0;
int64_t cy = y0;
bool ok = 0;
if ((dir == 0 && y0 > 0)) {
cy = (y0 - 1);
ok = 1;
} else if ((dir == 1 && y0 < 4)) {
cy = (y0 + 1);
ok = 1;
} else if ((dir == 2 && x0 > 0)) {
cx = (x0 - 1);
ok = 1;
} else if ((dir == 3 && x0 < 4)) {
cx = (x0 + 1);
ok = 1;
}
if (ok) {
int64_t ccar = car0;
int64_t ctop = top0;
int64_t cbot = bot0;
if (((ccar == 1 && cy == 0) && (ctop & FLOW_CHECKED_SHL((one), (cx))) == 0)) {
ccar = 0;
ctop = (ctop | FLOW_CHECKED_SHL((one), (cx)));
}
if (((ccar == 0 && cy == 4) && (cbot & FLOW_CHECKED_SHL((one), (cx))) != 0)) {
ccar = 1;
cbot = (cbot & (all_bits ^ FLOW_CHECKED_SHL((one), (cx))));
}
int64_t nh = make_hash_i64_i64_i64_i64_i64(cx, cy, ccar, ctop, cbot);
trans[((h * 4) + nt)] = ((int32_t)(nh));
nt = (nt + 1);
}
dir = (dir + 1);
}
ntrans[h] = ((int32_t)(nt));
si = (si + 1);
}
int64_t init = make_hash_i64_i64_i64_i64_i64(2, 2, 0, 0, all_bits);
last[init] = 1.0;
double expected = 0.0;
int64_t iteration = 1;
double eps = 0.0000000001;
while (1) {
int64_t i = 0;
while (i <= max_hash) {
nxt[i] = 0.0;
i = (i + 1);
}
si = 0;
while (si < nstates) {
int64_t h = ((int64_t)(state_list[si]));
int64_t nt = ((int64_t)(ntrans[h]));
if (nt > 0) {
double p = (last[h] / ((double)(nt)));
int64_t t = 0;
while (t < nt) {
int64_t nh = ((int64_t)(trans[((h * 4) + t)]));
nxt[nh] = (nxt[nh] + p);
t = (t + 1);
}
}
si = (si + 1);
}
i = 0;
while (i <= max_hash) {
last[i] = nxt[i];
i = (i + 1);
}
double add = 0.0;
si = 0;
while (si < nstates) {
int64_t h = ((int64_t)(state_list[si]));
if (is_fin[h] == 1) {
add = (add + last[h]);
}
si = (si + 1);
}
add = (add * ((double)(iteration)));
expected = (expected + add);
if ((add < eps && expected > 1.0)) {
break;
}
iteration = (iteration + 1);
}
printf("%.6f\n", expected);
free(is_state);
free(is_fin);
free(ntrans);
free(trans);
free(last);
free(nxt);
free(state_list);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%.6f\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 @popcount(%arg0: 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 = arith.constant 0 : i32
%3 = arith.extsi %2 : i32 to i64
%4 = llvm.mlir.constant(1 : i64) : i64
%5 = llvm.alloca %4 x i64 : (i64) -> !llvm.ptr
llvm.store %3, %5 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%6 = llvm.load %1 : !llvm.ptr -> i64
%7 = arith.constant 0 : i32
%9 = arith.extsi %7 : i32 to i64
%8 = arith.cmpi ne, %6, %9 : i64
cf.cond_br %8, ^bb1, ^bb2
^bb1:
%10 = llvm.load %5 : !llvm.ptr -> i64
%11 = arith.constant 1 : i32
%13 = arith.extsi %11 : i32 to i64
%12 = arith.addi %10, %13 : i64
llvm.store %12, %5 : i64, !llvm.ptr
%14 = llvm.load %1 : !llvm.ptr -> i64
%15 = llvm.load %1 : !llvm.ptr -> i64
%16 = arith.constant 1 : i32
%18 = arith.extsi %16 : i32 to i64
%17 = arith.subi %15, %18 : i64
%19 = arith.andi %14, %17 : i64
llvm.store %19, %1 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%20 = llvm.load %5 : !llvm.ptr -> i64
func.return %20 : i64
}
func.func @make_hash(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64, %arg4: i64) -> i64 {
%21 = llvm.mlir.constant(1 : i64) : i64
%22 = llvm.alloca %21 x i64 : (i64) -> !llvm.ptr
llvm.store %arg2, %22 : i64, !llvm.ptr
%23 = llvm.load %22 : !llvm.ptr -> i64
%24 = arith.constant 5 : i32
%26 = arith.extsi %24 : i32 to i64
%25 = arith.shli %23, %26 : i64
%27 = arith.addi %25, %arg3 : i64
llvm.store %27, %22 : i64, !llvm.ptr
%28 = llvm.load %22 : !llvm.ptr -> i64
%29 = arith.constant 5 : i32
%31 = arith.extsi %29 : i32 to i64
%30 = arith.shli %28, %31 : i64
%32 = arith.addi %30, %arg4 : i64
llvm.store %32, %22 : i64, !llvm.ptr
%33 = llvm.load %22 : !llvm.ptr -> i64
%34 = arith.constant 5 : i32
%36 = arith.extsi %34 : i32 to i64
%35 = arith.muli %33, %36 : i64
%37 = arith.addi %35, %arg0 : i64
llvm.store %37, %22 : i64, !llvm.ptr
%38 = llvm.load %22 : !llvm.ptr -> i64
%39 = arith.constant 5 : i32
%41 = arith.extsi %39 : i32 to i64
%40 = arith.muli %38, %41 : i64
%42 = arith.addi %40, %arg1 : i64
llvm.store %42, %22 : i64, !llvm.ptr
%43 = llvm.load %22 : !llvm.ptr -> i64
func.return %43 : i64
}
func.func @is_final(%arg0: i64, %arg1: i64) -> i1 {
%44 = func.call @popcount(%arg0) : (i64) -> i64
%45 = arith.constant 5 : i32
%47 = arith.extsi %45 : i32 to i64
%46 = arith.cmpi eq, %44, %47 : i64
%48 = scf.if %46 -> (i1) {
%49 = arith.constant 0 : i32
%51 = arith.extsi %49 : i32 to i64
%50 = arith.cmpi eq, %arg1, %51 : i64
scf.yield %50 : i1
} else {
%52 = arith.constant false
scf.yield %52 : i1
}
func.return %48 : i1
}
func.func @is_valid(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64, %arg4: i64) -> i1 {
%53 = arith.constant 1 : i32
%54 = arith.extsi %53 : i32 to i64
%55 = arith.constant 0 : i32
%57 = arith.extsi %55 : i32 to i64
%56 = arith.cmpi eq, %arg1, %57 : i64
%58 = scf.if %56 -> (i1) {
%59 = arith.constant 1 : i32
%61 = arith.extsi %59 : i32 to i64
%60 = arith.cmpi eq, %arg2, %61 : i64
scf.yield %60 : i1
} else {
%62 = arith.constant false
scf.yield %62 : i1
}
%63 = scf.if %58 -> (i1) {
%64 = arith.shli %54, %arg0 : i64
%65 = arith.andi %arg3, %64 : i64
%66 = arith.constant 0 : i32
%68 = arith.extsi %66 : i32 to i64
%67 = arith.cmpi eq, %65, %68 : i64
scf.yield %67 : i1
} else {
%69 = arith.constant false
scf.yield %69 : i1
}
cf.cond_br %63, ^bb3, ^bb4
^bb3:
%70 = arith.constant 0 : i1
func.return %70 : i1
^bb4:
cf.br ^bb5
^bb5:
%71 = arith.constant 4 : i32
%73 = arith.extsi %71 : i32 to i64
%72 = arith.cmpi eq, %arg1, %73 : i64
%74 = scf.if %72 -> (i1) {
%75 = arith.constant 0 : i32
%77 = arith.extsi %75 : i32 to i64
%76 = arith.cmpi eq, %arg2, %77 : i64
scf.yield %76 : i1
} else {
%78 = arith.constant false
scf.yield %78 : i1
}
%79 = scf.if %74 -> (i1) {
%80 = arith.shli %54, %arg0 : i64
%81 = arith.andi %arg4, %80 : i64
%82 = arith.constant 0 : i32
%84 = arith.extsi %82 : i32 to i64
%83 = arith.cmpi ne, %81, %84 : i64
scf.yield %83 : i1
} else {
%85 = arith.constant false
scf.yield %85 : i1
}
cf.cond_br %79, ^bb6, ^bb7
^bb6:
%86 = arith.constant 0 : i1
func.return %86 : i1
^bb7:
cf.br ^bb8
^bb8:
%87 = func.call @is_final(%arg3, %arg2) : (i64, i64) -> i1
%88 = scf.if %87 -> (i1) {
%89 = arith.constant 0 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.cmpi ne, %arg1, %91 : i64
scf.yield %90 : i1
} else {
%92 = arith.constant false
scf.yield %92 : i1
}
cf.cond_br %88, ^bb9, ^bb10
^bb9:
%93 = arith.constant 0 : i1
func.return %93 : i1
^bb10:
cf.br ^bb11
^bb11:
%94 = func.call @popcount(%arg3) : (i64) -> i64
%95 = func.call @popcount(%arg4) : (i64) -> i64
%96 = arith.addi %94, %95 : 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 = arith.constant 1 : i32
%101 = arith.extsi %99 : i32 to i64
%100 = arith.cmpi eq, %arg2, %101 : i64
cf.cond_br %100, ^bb12, ^bb13
^bb12:
%102 = llvm.load %98 : !llvm.ptr -> i64
%103 = arith.constant 1 : i32
%105 = arith.extsi %103 : i32 to i64
%104 = arith.addi %102, %105 : i64
llvm.store %104, %98 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%106 = llvm.load %98 : !llvm.ptr -> i64
%107 = arith.constant 5 : i32
%109 = arith.extsi %107 : i32 to i64
%108 = arith.cmpi eq, %106, %109 : i64
func.return %108 : i1
}
func.func @main() -> i32 {
%110 = arith.constant 5 : i32
%111 = arith.extsi %110 : i32 to i64
%112 = arith.constant 31 : i32
%113 = arith.extsi %112 : i32 to i64
%114 = arith.constant 1 : i32
%115 = arith.extsi %114 : i32 to i64
%116 = arith.constant 50000 : i32
%117 = arith.extsi %116 : i32 to i64
%119 = arith.constant 1 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.addi %117, %121 : i64
%122 = arith.constant 1 : i32
%123 = arith.extsi %122 : i32 to i64
%118 = func.call @calloc(%120, %123) : (i64, i64) -> !llvm.ptr
%125 = arith.constant 1 : i32
%127 = arith.extsi %125 : i32 to i64
%126 = arith.addi %117, %127 : i64
%128 = arith.constant 1 : i32
%129 = arith.extsi %128 : i32 to i64
%124 = func.call @calloc(%126, %129) : (i64, i64) -> !llvm.ptr
%131 = arith.constant 1 : i32
%133 = arith.extsi %131 : i32 to i64
%132 = arith.addi %117, %133 : i64
%134 = arith.constant 4 : i32
%135 = arith.extsi %134 : i32 to i64
%130 = func.call @calloc(%132, %135) : (i64, i64) -> !llvm.ptr
%137 = arith.constant 1 : i32
%139 = arith.extsi %137 : i32 to i64
%138 = arith.addi %117, %139 : i64
%140 = arith.constant 4 : i32
%142 = arith.extsi %140 : i32 to i64
%141 = arith.muli %138, %142 : i64
%143 = arith.constant 4 : i32
%144 = arith.extsi %143 : i32 to i64
%136 = func.call @calloc(%141, %144) : (i64, i64) -> !llvm.ptr
%146 = arith.constant 1 : i32
%148 = arith.extsi %146 : i32 to i64
%147 = arith.addi %117, %148 : i64
%149 = arith.constant 8 : i32
%150 = arith.extsi %149 : i32 to i64
%145 = func.call @calloc(%147, %150) : (i64, i64) -> !llvm.ptr
%152 = arith.constant 1 : i32
%154 = arith.extsi %152 : i32 to i64
%153 = arith.addi %117, %154 : i64
%155 = arith.constant 8 : i32
%156 = arith.extsi %155 : i32 to i64
%151 = func.call @calloc(%153, %156) : (i64, i64) -> !llvm.ptr
%158 = arith.constant 12000 : i32
%159 = arith.constant 4 : i32
%160 = arith.extsi %158 : i32 to i64
%161 = arith.extsi %159 : i32 to i64
%157 = func.call @calloc(%160, %161) : (i64, i64) -> !llvm.ptr
%162 = arith.constant 0 : i32
%163 = arith.extsi %162 : i32 to i64
%164 = llvm.mlir.constant(1 : i64) : i64
%165 = llvm.alloca %164 x i64 : (i64) -> !llvm.ptr
llvm.store %163, %165 : i64, !llvm.ptr
%166 = arith.constant 0 : i32
%167 = arith.extsi %166 : i32 to i64
%168 = llvm.mlir.constant(1 : i64) : i64
%169 = llvm.alloca %168 x i64 : (i64) -> !llvm.ptr
llvm.store %167, %169 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%170 = llvm.load %169 : !llvm.ptr -> i64
%171 = arith.cmpi slt, %170, %111 : i64
cf.cond_br %171, ^bb16, ^bb17
^bb16:
%172 = arith.constant 0 : i32
%173 = arith.extsi %172 : i32 to i64
%174 = llvm.mlir.constant(1 : i64) : i64
%175 = llvm.alloca %174 x i64 : (i64) -> !llvm.ptr
llvm.store %173, %175 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%176 = llvm.load %175 : !llvm.ptr -> i64
%177 = arith.cmpi slt, %176, %111 : i64
cf.cond_br %177, ^bb19, ^bb20
^bb19:
%178 = arith.constant 0 : i32
%179 = arith.extsi %178 : i32 to i64
%180 = llvm.mlir.constant(1 : i64) : i64
%181 = llvm.alloca %180 x i64 : (i64) -> !llvm.ptr
llvm.store %179, %181 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%182 = llvm.load %181 : !llvm.ptr -> i64
%183 = arith.constant 1 : i32
%185 = arith.extsi %183 : i32 to i64
%184 = arith.cmpi sle, %182, %185 : i64
cf.cond_br %184, ^bb22, ^bb23
^bb22:
%186 = arith.constant 0 : i32
%187 = arith.extsi %186 : i32 to i64
%188 = llvm.mlir.constant(1 : i64) : i64
%189 = llvm.alloca %188 x i64 : (i64) -> !llvm.ptr
llvm.store %187, %189 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%190 = llvm.load %189 : !llvm.ptr -> i64
%191 = arith.cmpi sle, %190, %113 : i64
cf.cond_br %191, ^bb25, ^bb26
^bb25:
%192 = arith.constant 0 : i32
%193 = arith.extsi %192 : i32 to i64
%194 = llvm.mlir.constant(1 : i64) : i64
%195 = llvm.alloca %194 x i64 : (i64) -> !llvm.ptr
llvm.store %193, %195 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%196 = llvm.load %195 : !llvm.ptr -> i64
%197 = arith.cmpi sle, %196, %113 : i64
cf.cond_br %197, ^bb28, ^bb29
^bb28:
%199 = llvm.load %169 : !llvm.ptr -> i64
%200 = llvm.load %175 : !llvm.ptr -> i64
%201 = llvm.load %181 : !llvm.ptr -> i64
%202 = llvm.load %189 : !llvm.ptr -> i64
%203 = llvm.load %195 : !llvm.ptr -> i64
%198 = func.call @is_valid(%199, %200, %201, %202, %203) : (i64, i64, i64, i64, i64) -> i1
cf.cond_br %198, ^bb30, ^bb31
^bb30:
%205 = llvm.load %169 : !llvm.ptr -> i64
%206 = llvm.load %175 : !llvm.ptr -> i64
%207 = llvm.load %181 : !llvm.ptr -> i64
%208 = llvm.load %189 : !llvm.ptr -> i64
%209 = llvm.load %195 : !llvm.ptr -> i64
%204 = func.call @make_hash(%205, %206, %207, %208, %209) : (i64, i64, i64, i64, i64) -> i64
%210 = arith.constant 1 : i32
%211 = arith.trunci %210 : i32 to i8
%212 = llvm.getelementptr %118[%204] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %211, %212 : i8, !llvm.ptr
%213 = arith.trunci %204 : i64 to i32
%214 = llvm.load %165 : !llvm.ptr -> i64
%215 = llvm.getelementptr %157[%214] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %213, %215 : i32, !llvm.ptr
%216 = llvm.load %165 : !llvm.ptr -> i64
%217 = arith.constant 1 : i32
%219 = arith.extsi %217 : i32 to i64
%218 = arith.addi %216, %219 : i64
llvm.store %218, %165 : i64, !llvm.ptr
%221 = llvm.load %189 : !llvm.ptr -> i64
%222 = llvm.load %181 : !llvm.ptr -> i64
%220 = func.call @is_final(%221, %222) : (i64, i64) -> i1
cf.cond_br %220, ^bb33, ^bb34
^bb33:
%223 = arith.constant 1 : i32
%224 = arith.trunci %223 : i32 to i8
%225 = llvm.getelementptr %124[%204] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %224, %225 : i8, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%226 = llvm.load %195 : !llvm.ptr -> i64
%227 = arith.constant 1 : i32
%229 = arith.extsi %227 : i32 to i64
%228 = arith.addi %226, %229 : i64
llvm.store %228, %195 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%230 = llvm.load %189 : !llvm.ptr -> i64
%231 = arith.constant 1 : i32
%233 = arith.extsi %231 : i32 to i64
%232 = arith.addi %230, %233 : i64
llvm.store %232, %189 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%234 = llvm.load %181 : !llvm.ptr -> i64
%235 = arith.constant 1 : i32
%237 = arith.extsi %235 : i32 to i64
%236 = arith.addi %234, %237 : i64
llvm.store %236, %181 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%238 = llvm.load %175 : !llvm.ptr -> i64
%239 = arith.constant 1 : i32
%241 = arith.extsi %239 : i32 to i64
%240 = arith.addi %238, %241 : i64
llvm.store %240, %175 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%242 = llvm.load %169 : !llvm.ptr -> i64
%243 = arith.constant 1 : i32
%245 = arith.extsi %243 : i32 to i64
%244 = arith.addi %242, %245 : i64
llvm.store %244, %169 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%246 = arith.constant 0 : i32
%247 = arith.extsi %246 : i32 to i64
%248 = llvm.mlir.constant(1 : i64) : i64
%249 = llvm.alloca %248 x i64 : (i64) -> !llvm.ptr
llvm.store %247, %249 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%250 = llvm.load %249 : !llvm.ptr -> i64
%251 = llvm.load %165 : !llvm.ptr -> i64
%252 = arith.cmpi slt, %250, %251 : i64
cf.cond_br %252, ^bb37, ^bb38
^bb37:
%254 = llvm.load %249 : !llvm.ptr -> i64
%255 = llvm.getelementptr %157[%254] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%253 = llvm.load %255 : !llvm.ptr -> i32
%256 = arith.extsi %253 : i32 to i64
%258 = llvm.getelementptr %124[%256] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%257 = llvm.load %258 : !llvm.ptr -> i8
%259 = arith.constant 1 : i32
%261 = arith.extsi %257 : i8 to i32
%260 = arith.cmpi eq, %261, %259 : i32
cf.cond_br %260, ^bb39, ^bb40
^bb39:
%262 = llvm.load %249 : !llvm.ptr -> i64
%263 = arith.constant 1 : i32
%265 = arith.extsi %263 : i32 to i64
%264 = arith.addi %262, %265 : i64
llvm.store %264, %249 : i64, !llvm.ptr
cf.br ^bb36
^bb40:
cf.br ^bb41
^bb41:
%266 = llvm.mlir.constant(1 : i64) : i64
%267 = llvm.alloca %266 x i64 : (i64) -> !llvm.ptr
llvm.store %256, %267 : i64, !llvm.ptr
%268 = llvm.load %267 : !llvm.ptr -> i64
%269 = arith.constant 5 : i32
%271 = arith.extsi %269 : i32 to i64
%270 = arith.remsi %268, %271 : i64
%272 = llvm.load %267 : !llvm.ptr -> i64
%273 = arith.constant 5 : i32
%275 = arith.extsi %273 : i32 to i64
%274 = arith.divsi %272, %275 : i64
llvm.store %274, %267 : i64, !llvm.ptr
%276 = llvm.load %267 : !llvm.ptr -> i64
%277 = arith.constant 5 : i32
%279 = arith.extsi %277 : i32 to i64
%278 = arith.remsi %276, %279 : i64
%280 = llvm.load %267 : !llvm.ptr -> i64
%281 = arith.constant 5 : i32
%283 = arith.extsi %281 : i32 to i64
%282 = arith.divsi %280, %283 : i64
llvm.store %282, %267 : i64, !llvm.ptr
%284 = llvm.load %267 : !llvm.ptr -> i64
%285 = arith.constant 31 : i32
%287 = arith.extsi %285 : i32 to i64
%286 = arith.andi %284, %287 : i64
%288 = llvm.load %267 : !llvm.ptr -> i64
%289 = arith.constant 5 : i32
%291 = arith.extsi %289 : i32 to i64
%290 = arith.shrsi %288, %291 : i64
llvm.store %290, %267 : i64, !llvm.ptr
%292 = llvm.load %267 : !llvm.ptr -> i64
%293 = arith.constant 31 : i32
%295 = arith.extsi %293 : i32 to i64
%294 = arith.andi %292, %295 : i64
%296 = llvm.load %267 : !llvm.ptr -> i64
%297 = arith.constant 5 : i32
%299 = arith.extsi %297 : i32 to i64
%298 = arith.shrsi %296, %299 : i64
llvm.store %298, %267 : i64, !llvm.ptr
%300 = llvm.load %267 : !llvm.ptr -> i64
%301 = arith.constant 1 : i32
%303 = arith.extsi %301 : i32 to i64
%302 = arith.andi %300, %303 : i64
%304 = arith.constant 0 : i32
%305 = arith.extsi %304 : i32 to i64
%306 = llvm.mlir.constant(1 : i64) : i64
%307 = llvm.alloca %306 x i64 : (i64) -> !llvm.ptr
llvm.store %305, %307 : i64, !llvm.ptr
%308 = arith.constant 0 : i32
%309 = arith.extsi %308 : i32 to i64
%310 = llvm.mlir.constant(1 : i64) : i64
%311 = llvm.alloca %310 x i64 : (i64) -> !llvm.ptr
llvm.store %309, %311 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%312 = llvm.load %311 : !llvm.ptr -> i64
%313 = arith.constant 4 : i32
%315 = arith.extsi %313 : i32 to i64
%314 = arith.cmpi slt, %312, %315 : i64
cf.cond_br %314, ^bb43, ^bb44
^bb43:
%316 = llvm.mlir.constant(1 : i64) : i64
%317 = llvm.alloca %316 x i64 : (i64) -> !llvm.ptr
llvm.store %278, %317 : i64, !llvm.ptr
%318 = llvm.mlir.constant(1 : i64) : i64
%319 = llvm.alloca %318 x i64 : (i64) -> !llvm.ptr
llvm.store %270, %319 : i64, !llvm.ptr
%320 = arith.constant 0 : i1
%321 = llvm.mlir.constant(1 : i64) : i64
%322 = llvm.alloca %321 x i1 : (i64) -> !llvm.ptr
llvm.store %320, %322 : i1, !llvm.ptr
%323 = llvm.load %311 : !llvm.ptr -> i64
%324 = arith.constant 0 : i32
%326 = arith.extsi %324 : i32 to i64
%325 = arith.cmpi eq, %323, %326 : i64
%327 = scf.if %325 -> (i1) {
%328 = arith.constant 0 : i32
%330 = arith.extsi %328 : i32 to i64
%329 = arith.cmpi sgt, %270, %330 : i64
scf.yield %329 : i1
} else {
%331 = arith.constant false
scf.yield %331 : i1
}
cf.cond_br %327, ^bb45, ^bb46
^bb45:
%332 = arith.constant 1 : i32
%334 = arith.extsi %332 : i32 to i64
%333 = arith.subi %270, %334 : i64
llvm.store %333, %319 : i64, !llvm.ptr
%335 = arith.constant 1 : i1
llvm.store %335, %322 : i1, !llvm.ptr
cf.br ^bb47
^bb46:
%336 = llvm.load %311 : !llvm.ptr -> 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 = arith.constant 4 : i32
%343 = arith.extsi %341 : i32 to i64
%342 = arith.cmpi slt, %270, %343 : i64
scf.yield %342 : i1
} else {
%344 = arith.constant false
scf.yield %344 : i1
}
cf.cond_br %340, ^bb49, ^bb48
^bb49:
%345 = arith.constant 1 : i32
%347 = arith.extsi %345 : i32 to i64
%346 = arith.addi %270, %347 : i64
llvm.store %346, %319 : i64, !llvm.ptr
%348 = arith.constant 1 : i1
llvm.store %348, %322 : i1, !llvm.ptr
cf.br ^bb47
^bb48:
%349 = llvm.load %311 : !llvm.ptr -> i64
%350 = arith.constant 2 : i32
%352 = arith.extsi %350 : i32 to i64
%351 = arith.cmpi eq, %349, %352 : i64
%353 = scf.if %351 -> (i1) {
%354 = arith.constant 0 : i32
%356 = arith.extsi %354 : i32 to i64
%355 = arith.cmpi sgt, %278, %356 : i64
scf.yield %355 : i1
} else {
%357 = arith.constant false
scf.yield %357 : i1
}
cf.cond_br %353, ^bb51, ^bb50
^bb51:
%358 = arith.constant 1 : i32
%360 = arith.extsi %358 : i32 to i64
%359 = arith.subi %278, %360 : i64
llvm.store %359, %317 : i64, !llvm.ptr
%361 = arith.constant 1 : i1
llvm.store %361, %322 : i1, !llvm.ptr
cf.br ^bb47
^bb50:
%362 = llvm.load %311 : !llvm.ptr -> i64
%363 = arith.constant 3 : i32
%365 = arith.extsi %363 : i32 to i64
%364 = arith.cmpi eq, %362, %365 : i64
%366 = scf.if %364 -> (i1) {
%367 = arith.constant 4 : i32
%369 = arith.extsi %367 : i32 to i64
%368 = arith.cmpi slt, %278, %369 : i64
scf.yield %368 : i1
} else {
%370 = arith.constant false
scf.yield %370 : i1
}
cf.cond_br %366, ^bb52, ^bb47
^bb52:
%371 = arith.constant 1 : i32
%373 = arith.extsi %371 : i32 to i64
%372 = arith.addi %278, %373 : i64
llvm.store %372, %317 : i64, !llvm.ptr
%374 = arith.constant 1 : i1
llvm.store %374, %322 : i1, !llvm.ptr
cf.br ^bb47
^bb47:
%375 = llvm.load %322 : !llvm.ptr -> i1
cf.cond_br %375, ^bb53, ^bb54
^bb53:
%376 = llvm.mlir.constant(1 : i64) : i64
%377 = llvm.alloca %376 x i64 : (i64) -> !llvm.ptr
llvm.store %302, %377 : i64, !llvm.ptr
%378 = llvm.mlir.constant(1 : i64) : i64
%379 = llvm.alloca %378 x i64 : (i64) -> !llvm.ptr
llvm.store %294, %379 : i64, !llvm.ptr
%380 = llvm.mlir.constant(1 : i64) : i64
%381 = llvm.alloca %380 x i64 : (i64) -> !llvm.ptr
llvm.store %286, %381 : i64, !llvm.ptr
%382 = llvm.load %377 : !llvm.ptr -> i64
%383 = arith.constant 1 : i32
%385 = arith.extsi %383 : i32 to i64
%384 = arith.cmpi eq, %382, %385 : i64
%386 = scf.if %384 -> (i1) {
%387 = llvm.load %319 : !llvm.ptr -> i64
%388 = arith.constant 0 : i32
%390 = arith.extsi %388 : i32 to i64
%389 = arith.cmpi eq, %387, %390 : i64
scf.yield %389 : i1
} else {
%391 = arith.constant false
scf.yield %391 : i1
}
%392 = scf.if %386 -> (i1) {
%393 = llvm.load %379 : !llvm.ptr -> i64
%394 = llvm.load %317 : !llvm.ptr -> i64
%395 = arith.shli %115, %394 : i64
%396 = arith.andi %393, %395 : i64
%397 = arith.constant 0 : i32
%399 = arith.extsi %397 : i32 to i64
%398 = arith.cmpi eq, %396, %399 : i64
scf.yield %398 : i1
} else {
%400 = arith.constant false
scf.yield %400 : i1
}
cf.cond_br %392, ^bb56, ^bb57
^bb56:
%401 = arith.constant 0 : i32
%402 = arith.extsi %401 : i32 to i64
llvm.store %402, %377 : i64, !llvm.ptr
%403 = llvm.load %379 : !llvm.ptr -> i64
%404 = llvm.load %317 : !llvm.ptr -> i64
%405 = arith.shli %115, %404 : i64
%406 = arith.ori %403, %405 : i64
llvm.store %406, %379 : i64, !llvm.ptr
cf.br ^bb58
^bb57:
cf.br ^bb58
^bb58:
%407 = llvm.load %377 : !llvm.ptr -> i64
%408 = arith.constant 0 : i32
%410 = arith.extsi %408 : i32 to i64
%409 = arith.cmpi eq, %407, %410 : i64
%411 = scf.if %409 -> (i1) {
%412 = llvm.load %319 : !llvm.ptr -> i64
%413 = arith.constant 4 : i32
%415 = arith.extsi %413 : i32 to i64
%414 = arith.cmpi eq, %412, %415 : i64
scf.yield %414 : i1
} else {
%416 = arith.constant false
scf.yield %416 : i1
}
%417 = scf.if %411 -> (i1) {
%418 = llvm.load %381 : !llvm.ptr -> i64
%419 = llvm.load %317 : !llvm.ptr -> i64
%420 = arith.shli %115, %419 : i64
%421 = arith.andi %418, %420 : i64
%422 = arith.constant 0 : i32
%424 = arith.extsi %422 : i32 to i64
%423 = arith.cmpi ne, %421, %424 : i64
scf.yield %423 : i1
} else {
%425 = arith.constant false
scf.yield %425 : i1
}
cf.cond_br %417, ^bb59, ^bb60
^bb59:
%426 = arith.constant 1 : i32
%427 = arith.extsi %426 : i32 to i64
llvm.store %427, %377 : i64, !llvm.ptr
%428 = llvm.load %381 : !llvm.ptr -> i64
%429 = llvm.load %317 : !llvm.ptr -> i64
%430 = arith.shli %115, %429 : i64
%431 = arith.xori %113, %430 : i64
%432 = arith.andi %428, %431 : i64
llvm.store %432, %381 : i64, !llvm.ptr
cf.br ^bb61
^bb60:
cf.br ^bb61
^bb61:
%434 = llvm.load %317 : !llvm.ptr -> i64
%435 = llvm.load %319 : !llvm.ptr -> i64
%436 = llvm.load %377 : !llvm.ptr -> i64
%437 = llvm.load %379 : !llvm.ptr -> i64
%438 = llvm.load %381 : !llvm.ptr -> i64
%433 = func.call @make_hash(%434, %435, %436, %437, %438) : (i64, i64, i64, i64, i64) -> i64
%439 = arith.trunci %433 : i64 to i32
%440 = arith.constant 4 : i32
%442 = arith.extsi %440 : i32 to i64
%441 = arith.muli %256, %442 : i64
%443 = llvm.load %307 : !llvm.ptr -> i64
%444 = arith.addi %441, %443 : i64
%445 = llvm.getelementptr %136[%444] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %439, %445 : i32, !llvm.ptr
%446 = llvm.load %307 : !llvm.ptr -> i64
%447 = arith.constant 1 : i32
%449 = arith.extsi %447 : i32 to i64
%448 = arith.addi %446, %449 : i64
llvm.store %448, %307 : i64, !llvm.ptr
cf.br ^bb55
^bb54:
cf.br ^bb55
^bb55:
%450 = llvm.load %311 : !llvm.ptr -> i64
%451 = arith.constant 1 : i32
%453 = arith.extsi %451 : i32 to i64
%452 = arith.addi %450, %453 : i64
llvm.store %452, %311 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%454 = llvm.load %307 : !llvm.ptr -> i64
%455 = arith.trunci %454 : i64 to i32
%456 = llvm.getelementptr %130[%256] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %455, %456 : i32, !llvm.ptr
%457 = llvm.load %249 : !llvm.ptr -> i64
%458 = arith.constant 1 : i32
%460 = arith.extsi %458 : i32 to i64
%459 = arith.addi %457, %460 : i64
llvm.store %459, %249 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%462 = arith.constant 2 : i32
%463 = arith.constant 2 : i32
%464 = arith.constant 0 : i32
%465 = arith.constant 0 : i32
%466 = arith.extsi %462 : i32 to i64
%467 = arith.extsi %463 : i32 to i64
%468 = arith.extsi %464 : i32 to i64
%469 = arith.extsi %465 : i32 to i64
%461 = func.call @make_hash(%466, %467, %468, %469, %113) : (i64, i64, i64, i64, i64) -> i64
%470 = arith.constant 1.0 : f32
%471 = arith.extf %470 : f32 to f64
%472 = llvm.getelementptr %145[%461] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %471, %472 : f64, !llvm.ptr
%473 = arith.constant 0.0 : f32
%474 = arith.extf %473 : f32 to f64
%475 = llvm.mlir.constant(1 : i64) : i64
%476 = llvm.alloca %475 x f64 : (i64) -> !llvm.ptr
llvm.store %474, %476 : f64, !llvm.ptr
%477 = arith.constant 1 : i32
%478 = arith.extsi %477 : i32 to i64
%479 = llvm.mlir.constant(1 : i64) : i64
%480 = llvm.alloca %479 x i64 : (i64) -> !llvm.ptr
llvm.store %478, %480 : i64, !llvm.ptr
%481 = arith.constant 0.0000000001 : f32
%482 = arith.extf %481 : f32 to f64
cf.br ^bb62
^bb62:
%483 = arith.constant 1 : i1
cf.cond_br %483, ^bb63, ^bb64
^bb63:
%484 = arith.constant 0 : i32
%485 = arith.extsi %484 : i32 to i64
%486 = llvm.mlir.constant(1 : i64) : i64
%487 = llvm.alloca %486 x i64 : (i64) -> !llvm.ptr
llvm.store %485, %487 : i64, !llvm.ptr
cf.br ^bb65
^bb65:
%488 = llvm.load %487 : !llvm.ptr -> i64
%489 = arith.cmpi sle, %488, %117 : i64
cf.cond_br %489, ^bb66, ^bb67
^bb66:
%490 = arith.constant 0.0 : f32
%491 = llvm.load %487 : !llvm.ptr -> i64
%492 = arith.extf %490 : f32 to f64
%493 = llvm.getelementptr %151[%491] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %492, %493 : f64, !llvm.ptr
%494 = llvm.load %487 : !llvm.ptr -> i64
%495 = arith.constant 1 : i32
%497 = arith.extsi %495 : i32 to i64
%496 = arith.addi %494, %497 : i64
llvm.store %496, %487 : i64, !llvm.ptr
cf.br ^bb65
^bb67:
%498 = arith.constant 0 : i32
%499 = arith.extsi %498 : i32 to i64
llvm.store %499, %249 : i64, !llvm.ptr
cf.br ^bb68
^bb68:
%500 = llvm.load %249 : !llvm.ptr -> i64
%501 = llvm.load %165 : !llvm.ptr -> i64
%502 = arith.cmpi slt, %500, %501 : i64
cf.cond_br %502, ^bb69, ^bb70
^bb69:
%504 = llvm.load %249 : !llvm.ptr -> i64
%505 = llvm.getelementptr %157[%504] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%503 = llvm.load %505 : !llvm.ptr -> i32
%506 = arith.extsi %503 : i32 to i64
%508 = llvm.getelementptr %130[%506] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%507 = llvm.load %508 : !llvm.ptr -> i32
%509 = arith.extsi %507 : i32 to i64
%510 = arith.constant 0 : i32
%512 = arith.extsi %510 : i32 to i64
%511 = arith.cmpi sgt, %509, %512 : i64
cf.cond_br %511, ^bb71, ^bb72
^bb71:
%514 = llvm.getelementptr %145[%506] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%513 = llvm.load %514 : !llvm.ptr -> f64
%515 = arith.sitofp %509 : i64 to f64
%516 = arith.divf %513, %515 : f64
%517 = arith.constant 0 : i32
%518 = arith.extsi %517 : i32 to i64
%519 = llvm.mlir.constant(1 : i64) : i64
%520 = llvm.alloca %519 x i64 : (i64) -> !llvm.ptr
llvm.store %518, %520 : i64, !llvm.ptr
cf.br ^bb74
^bb74:
%521 = llvm.load %520 : !llvm.ptr -> i64
%522 = arith.cmpi slt, %521, %509 : i64
cf.cond_br %522, ^bb75, ^bb76
^bb75:
%524 = arith.constant 4 : i32
%526 = arith.extsi %524 : i32 to i64
%525 = arith.muli %506, %526 : i64
%527 = llvm.load %520 : !llvm.ptr -> i64
%528 = arith.addi %525, %527 : i64
%529 = llvm.getelementptr %136[%528] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%523 = llvm.load %529 : !llvm.ptr -> i32
%530 = arith.extsi %523 : i32 to i64
%532 = llvm.getelementptr %151[%530] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%531 = llvm.load %532 : !llvm.ptr -> f64
%533 = arith.addf %531, %516 : f64
%534 = llvm.getelementptr %151[%530] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %533, %534 : f64, !llvm.ptr
%535 = llvm.load %520 : !llvm.ptr -> i64
%536 = arith.constant 1 : i32
%538 = arith.extsi %536 : i32 to i64
%537 = arith.addi %535, %538 : i64
llvm.store %537, %520 : i64, !llvm.ptr
cf.br ^bb74
^bb76:
cf.br ^bb73
^bb72:
cf.br ^bb73
^bb73:
%539 = llvm.load %249 : !llvm.ptr -> i64
%540 = arith.constant 1 : i32
%542 = arith.extsi %540 : i32 to i64
%541 = arith.addi %539, %542 : i64
llvm.store %541, %249 : i64, !llvm.ptr
cf.br ^bb68
^bb70:
%543 = arith.constant 0 : i32
%544 = arith.extsi %543 : i32 to i64
llvm.store %544, %487 : i64, !llvm.ptr
cf.br ^bb77
^bb77:
%545 = llvm.load %487 : !llvm.ptr -> i64
%546 = arith.cmpi sle, %545, %117 : i64
cf.cond_br %546, ^bb78, ^bb79
^bb78:
%548 = llvm.load %487 : !llvm.ptr -> i64
%549 = llvm.getelementptr %151[%548] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%547 = llvm.load %549 : !llvm.ptr -> f64
%550 = llvm.load %487 : !llvm.ptr -> i64
%551 = llvm.getelementptr %145[%550] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %547, %551 : f64, !llvm.ptr
%552 = llvm.load %487 : !llvm.ptr -> i64
%553 = arith.constant 1 : i32
%555 = arith.extsi %553 : i32 to i64
%554 = arith.addi %552, %555 : i64
llvm.store %554, %487 : i64, !llvm.ptr
cf.br ^bb77
^bb79:
%556 = arith.constant 0.0 : f32
%557 = arith.extf %556 : f32 to f64
%558 = llvm.mlir.constant(1 : i64) : i64
%559 = llvm.alloca %558 x f64 : (i64) -> !llvm.ptr
llvm.store %557, %559 : f64, !llvm.ptr
%560 = arith.constant 0 : i32
%561 = arith.extsi %560 : i32 to i64
llvm.store %561, %249 : i64, !llvm.ptr
cf.br ^bb80
^bb80:
%562 = llvm.load %249 : !llvm.ptr -> i64
%563 = llvm.load %165 : !llvm.ptr -> i64
%564 = arith.cmpi slt, %562, %563 : i64
cf.cond_br %564, ^bb81, ^bb82
^bb81:
%566 = llvm.load %249 : !llvm.ptr -> i64
%567 = llvm.getelementptr %157[%566] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%565 = llvm.load %567 : !llvm.ptr -> i32
%568 = arith.extsi %565 : i32 to i64
%570 = llvm.getelementptr %124[%568] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%569 = llvm.load %570 : !llvm.ptr -> i8
%571 = arith.constant 1 : i32
%573 = arith.extsi %569 : i8 to i32
%572 = arith.cmpi eq, %573, %571 : i32
cf.cond_br %572, ^bb83, ^bb84
^bb83:
%574 = llvm.load %559 : !llvm.ptr -> f64
%576 = llvm.getelementptr %145[%568] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%575 = llvm.load %576 : !llvm.ptr -> f64
%577 = arith.addf %574, %575 : f64
llvm.store %577, %559 : f64, !llvm.ptr
cf.br ^bb85
^bb84:
cf.br ^bb85
^bb85:
%578 = llvm.load %249 : !llvm.ptr -> i64
%579 = arith.constant 1 : i32
%581 = arith.extsi %579 : i32 to i64
%580 = arith.addi %578, %581 : i64
llvm.store %580, %249 : i64, !llvm.ptr
cf.br ^bb80
^bb82:
%582 = llvm.load %559 : !llvm.ptr -> f64
%583 = llvm.load %480 : !llvm.ptr -> i64
%584 = arith.sitofp %583 : i64 to f64
%585 = arith.mulf %582, %584 : f64
llvm.store %585, %559 : f64, !llvm.ptr
%586 = llvm.load %476 : !llvm.ptr -> f64
%587 = llvm.load %559 : !llvm.ptr -> f64
%588 = arith.addf %586, %587 : f64
llvm.store %588, %476 : f64, !llvm.ptr
%589 = llvm.load %559 : !llvm.ptr -> f64
%590 = arith.cmpf olt, %589, %482 : f64
%591 = scf.if %590 -> (i1) {
%592 = llvm.load %476 : !llvm.ptr -> f64
%593 = arith.constant 1.0 : f32
%595 = arith.extf %593 : f32 to f64
%594 = arith.cmpf ogt, %592, %595 : f64
scf.yield %594 : i1
} else {
%596 = arith.constant false
scf.yield %596 : i1
}
cf.cond_br %591, ^bb86, ^bb87
^bb86:
cf.br ^bb64
^bb87:
cf.br ^bb88
^bb88:
%597 = llvm.load %480 : !llvm.ptr -> i64
%598 = arith.constant 1 : i32
%600 = arith.extsi %598 : i32 to i64
%599 = arith.addi %597, %600 : i64
llvm.store %599, %480 : i64, !llvm.ptr
cf.br ^bb62
^bb64:
%601 = llvm.mlir.addressof @str_0 : !llvm.ptr
%602 = llvm.load %476 : !llvm.ptr -> f64
%603 = llvm.call @printf(%601, %602) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, f64) -> i32
func.call @free(%118) : (!llvm.ptr) -> ()
func.call @free(%124) : (!llvm.ptr) -> ()
func.call @free(%130) : (!llvm.ptr) -> ()
func.call @free(%136) : (!llvm.ptr) -> ()
func.call @free(%145) : (!llvm.ptr) -> ()
func.call @free(%151) : (!llvm.ptr) -> ()
func.call @free(%157) : (!llvm.ptr) -> ()
%611 = arith.constant 0 : i32
func.return %611 : i32
}
}