Problem 958
Euclid's Labour: meet-in-the-middle search on the Stern-Brocot tree.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(2^n) | O(log n) |
|---|
| Space complexity | O(1) | O(log n) |
|---|
| Approach | Flow solution | Stern-Brocot or binary representation |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 958
# Euclid's Labour: meet-in-the-middle search on the Stern-Brocot tree.
let mut g_n: i64 = 0
let mut g_steps: i64 = 0
let mut g_split_depth: i64 = 0
let mut g_best_steps: i64 = 0
let mut g_best_value: i64 = 0
let mut g_local_a: i64 = 0
let mut g_local_b: i64 = 0
let mut g_norm: i64 = 0
let mut g_inv_result: i64 = 0
function mod_inverse(value0: i64, modulus: i64) -> i32 {
let mut value: i64 = ((value0 % modulus) + modulus) % modulus
let mut old_r: i128 = modulus as i128
let mut r: i128 = value as i128
let mut old_s: i128 = 0 as i128
let mut s: i128 = 1 as i128
while r != 0 as i128 {
let q: i128 = old_r / r
let tmp: i128 = old_r - q * r
old_r = r
r = tmp
let tmp2: i128 = old_s - q * s
old_s = s
s = tmp2
}
if old_r != 1 as i128 {
return 0
}
let mm: i128 = modulus as i128
g_inv_result = (((old_s % mm) + mm) % mm) as i64
return 1
}
function check(candidate_a: i64, candidate_b: i64, current_depth: i64) -> void {
if candidate_a < 0 || candidate_b < 0 {
return
}
if candidate_a * candidate_a + candidate_b * candidate_b > g_norm {
return
}
let mut x: i64 = candidate_a
let mut y: i64 = candidate_b
let mut vx: i64 = g_local_a
let mut vy: i64 = g_local_b
if (g_steps & 1) != 0 {
if (vx & 1) != 0 || (y & 1) != 0 {
return
}
x = x - y / 2
vy = vy + vx / 2
if (vy & 1) != 0 || (x & 1) != 0 {
return
}
x = x / 2
y = y / 2
vx = vx / 2
vy = vy / 2
}
if x * vx + y * vy != g_n {
return
}
let remaining_steps: i64 = g_steps - g_split_depth
let mut used_steps: i64 = 0
while used_steps <= remaining_steps && x != 0 && y != 0 {
if x > y {
let t: i64 = x
x = y
y = t
let t2: i64 = vx
vx = vy
vy = t2
}
y = y - x
vx = vx + vy
used_steps = used_steps + 1
}
if used_steps > remaining_steps {
return
}
let residue: i64 = (((vx + vy - g_n) % g_n + g_n) % g_n)
if mod_inverse(residue, g_n) == 0 {
return
}
let inv_residue: i64 = g_inv_result
let total_steps: i64 = current_depth + used_steps
let nn: i64 = g_n
let mut value: i64 = residue
if nn - residue < value {
value = nn - residue
}
if inv_residue < value {
value = inv_residue
}
if nn - inv_residue < value {
value = nn - inv_residue
}
if total_steps < g_best_steps {
g_best_steps = total_steps
g_best_value = value
} else {
if total_steps == g_best_steps && value < g_best_value {
g_best_steps = total_steps
g_best_value = value
}
}
}
function consider(basis_a0: i64, basis_b0: i64, coeff_a0: i64, coeff_b0: i64, current_depth: i64) -> void {
let mut basis_a: i64 = basis_a0
let mut basis_b: i64 = basis_b0
let mut coeff_a: i64 = coeff_a0
let mut coeff_b: i64 = coeff_b0
if basis_a > basis_b {
let t: i64 = basis_a
basis_a = basis_b
basis_b = t
let t2: i64 = coeff_a
coeff_a = coeff_b
coeff_b = t2
}
if coeff_b < 0 {
return
}
if coeff_a < 0 {
let shift: i64 = (0 - coeff_a + basis_b - 1) / basis_b
coeff_a = coeff_a + shift * basis_b
coeff_b = coeff_b - shift * basis_a
if coeff_b < 0 {
return
}
}
if basis_a * coeff_a + basis_b * coeff_b != g_n {
return
}
if current_depth == g_split_depth {
let mut local_a: i64 = basis_a
let mut local_b: i64 = basis_b
let mut local_ca: i64 = coeff_a
let mut local_cb: i64 = coeff_b
if (g_steps & 1) != 0 {
local_a = local_a * 2
local_b = local_b * 2
local_ca = local_ca * 2
local_cb = local_cb * 2
local_b = local_b - local_a / 2
local_ca = local_ca + local_cb / 2
if local_a * local_ca + local_b * local_cb != 4 * g_n {
return
}
}
let norm: i64 = local_a * local_a + local_b * local_b
if norm < g_n {
return
}
let cross: i64 = local_ca * local_b - local_cb * local_a
let shift: i64 = cross / norm
local_ca = local_ca - shift * local_b
local_cb = local_cb + shift * local_a
let cross2: i64 = cross - shift * norm
if cross2 < 0 {
local_ca = local_ca + local_b
local_cb = local_cb - local_a
}
g_local_a = local_a
g_local_b = local_b
g_norm = norm
check(local_ca, local_cb, current_depth)
check(local_ca - local_b, local_cb + local_a, current_depth)
return
}
let mut x: i64 = basis_a
let mut y: i64 = basis_b
let mut i: i64 = current_depth
while i < g_steps / 2 {
if x > y {
let t: i64 = x
x = y
y = t
}
x = x + y
let t: i64 = x
x = y
y = t
i = i + 1
}
if x > y {
let t: i64 = x
x = y
y = t
}
if (g_steps & 1) != 0 {
if 5 * y * y / 4 + x * y + x * x < g_n {
return
}
} else {
if x * x + y * y < g_n {
return
}
}
consider(basis_b, basis_a + basis_b, coeff_b - coeff_a, coeff_a, current_depth + 1)
if basis_a > 0 && basis_a < basis_b {
consider(basis_a, basis_a + basis_b, coeff_a - coeff_b, coeff_b, current_depth + 1)
}
}
function f(n: i64) -> i64 {
g_n = n
let mut steps: i64 = 0
while true {
g_steps = steps
g_split_depth = (steps + 1) / 2
g_best_steps = steps
g_best_value = n + 1
consider(0, 1, 0, n, 0)
if g_best_value <= n {
return g_best_value
}
steps = steps + 1
}
return 0
}
function main() -> i32 {
printf("%lld\n", f(1000000000000 + 39))
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; }
int32_t mod_inverse_i64_i64(int64_t value0, int64_t modulus);
void check_i64_i64_i64(int64_t candidate_a, int64_t candidate_b, int64_t current_depth);
void consider_i64_i64_i64_i64_i64(int64_t basis_a0, int64_t basis_b0, int64_t coeff_a0, int64_t coeff_b0, int64_t current_depth);
int64_t f_i64(int64_t n);
int32_t main(void);
/* Module statics */
static int64_t g_n = 0;
static int64_t g_steps = 0;
static int64_t g_split_depth = 0;
static int64_t g_best_steps = 0;
static int64_t g_best_value = 0;
static int64_t g_local_a = 0;
static int64_t g_local_b = 0;
static int64_t g_norm = 0;
static int64_t g_inv_result = 0;
int32_t mod_inverse_i64_i64(int64_t value0, int64_t modulus) {
int64_t value = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((value0), (modulus)) + modulus)), (modulus));
__int128 old_r = ((__int128)(modulus));
__int128 r = ((__int128)(value));
__int128 old_s = ((__int128)(0));
__int128 s = ((__int128)(1));
while (r != ((__int128)(0))) {
__int128 q = FLOW_CHECKED_DIV((old_r), (r));
__int128 tmp = (old_r - (q * r));
old_r = r;
r = tmp;
__int128 tmp2 = (old_s - (q * s));
old_s = s;
s = tmp2;
}
if (old_r != ((__int128)(1))) {
return 0;
}
__int128 mm = ((__int128)(modulus));
g_inv_result = ((int64_t)(FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((old_s), (mm)) + mm)), (mm))));
return 1;
}
void check_i64_i64_i64(int64_t candidate_a, int64_t candidate_b, int64_t current_depth) {
if ((candidate_a < 0 || candidate_b < 0)) {
return;
}
if (((candidate_a * candidate_a) + (candidate_b * candidate_b)) > g_norm) {
return;
}
int64_t x = candidate_a;
int64_t y = candidate_b;
int64_t vx = g_local_a;
int64_t vy = g_local_b;
if ((g_steps & 1) != 0) {
if (((vx & 1) != 0 || (y & 1) != 0)) {
return;
}
x = (x - FLOW_CHECKED_DIV((y), (2)));
vy = (vy + FLOW_CHECKED_DIV((vx), (2)));
if (((vy & 1) != 0 || (x & 1) != 0)) {
return;
}
x = FLOW_CHECKED_DIV((x), (2));
y = FLOW_CHECKED_DIV((y), (2));
vx = FLOW_CHECKED_DIV((vx), (2));
vy = FLOW_CHECKED_DIV((vy), (2));
}
if (((x * vx) + (y * vy)) != g_n) {
return;
}
int64_t remaining_steps = (g_steps - g_split_depth);
int64_t used_steps = 0;
while (((used_steps <= remaining_steps && x != 0) && y != 0)) {
if (x > y) {
int64_t t = x;
x = y;
y = t;
int64_t t2 = vx;
vx = vy;
vy = t2;
}
y = (y - x);
vx = (vx + vy);
used_steps = (used_steps + 1);
}
if (used_steps > remaining_steps) {
return;
}
int64_t residue = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((vx + vy) - g_n)), (g_n)) + g_n)), (g_n));
if (mod_inverse_i64_i64(residue, g_n) == 0) {
return;
}
int64_t inv_residue = g_inv_result;
int64_t total_steps = (current_depth + used_steps);
int64_t nn = g_n;
int64_t value = residue;
if ((nn - residue) < value) {
value = (nn - residue);
}
if (inv_residue < value) {
value = inv_residue;
}
if ((nn - inv_residue) < value) {
value = (nn - inv_residue);
}
if (total_steps < g_best_steps) {
g_best_steps = total_steps;
g_best_value = value;
} else {
if ((total_steps == g_best_steps && value < g_best_value)) {
g_best_steps = total_steps;
g_best_value = value;
}
}
}
void consider_i64_i64_i64_i64_i64(int64_t basis_a0, int64_t basis_b0, int64_t coeff_a0, int64_t coeff_b0, int64_t current_depth) {
int64_t basis_a = basis_a0;
int64_t basis_b = basis_b0;
int64_t coeff_a = coeff_a0;
int64_t coeff_b = coeff_b0;
if (basis_a > basis_b) {
int64_t t = basis_a;
basis_a = basis_b;
basis_b = t;
int64_t t2 = coeff_a;
coeff_a = coeff_b;
coeff_b = t2;
}
if (coeff_b < 0) {
return;
}
if (coeff_a < 0) {
int64_t shift = FLOW_CHECKED_DIV(((((0 - coeff_a) + basis_b) - 1)), (basis_b));
coeff_a = (coeff_a + (shift * basis_b));
coeff_b = (coeff_b - (shift * basis_a));
if (coeff_b < 0) {
return;
}
}
if (((basis_a * coeff_a) + (basis_b * coeff_b)) != g_n) {
return;
}
if (current_depth == g_split_depth) {
int64_t local_a = basis_a;
int64_t local_b = basis_b;
int64_t local_ca = coeff_a;
int64_t local_cb = coeff_b;
if ((g_steps & 1) != 0) {
local_a = (local_a * 2);
local_b = (local_b * 2);
local_ca = (local_ca * 2);
local_cb = (local_cb * 2);
local_b = (local_b - FLOW_CHECKED_DIV((local_a), (2)));
local_ca = (local_ca + FLOW_CHECKED_DIV((local_cb), (2)));
if (((local_a * local_ca) + (local_b * local_cb)) != (4 * g_n)) {
return;
}
}
int64_t norm = ((local_a * local_a) + (local_b * local_b));
if (norm < g_n) {
return;
}
int64_t cross = ((local_ca * local_b) - (local_cb * local_a));
int64_t shift = FLOW_CHECKED_DIV((cross), (norm));
local_ca = (local_ca - (shift * local_b));
local_cb = (local_cb + (shift * local_a));
int64_t cross2 = (cross - (shift * norm));
if (cross2 < 0) {
local_ca = (local_ca + local_b);
local_cb = (local_cb - local_a);
}
g_local_a = local_a;
g_local_b = local_b;
g_norm = norm;
check_i64_i64_i64(local_ca, local_cb, current_depth);
check_i64_i64_i64((local_ca - local_b), (local_cb + local_a), current_depth);
return;
}
int64_t x = basis_a;
int64_t y = basis_b;
int64_t i = current_depth;
while (i < FLOW_CHECKED_DIV((g_steps), (2))) {
if (x > y) {
int64_t t = x;
x = y;
y = t;
}
x = (x + y);
int64_t t = x;
x = y;
y = t;
i = (i + 1);
}
if (x > y) {
int64_t t = x;
x = y;
y = t;
}
if ((g_steps & 1) != 0) {
if (((FLOW_CHECKED_DIV((((5 * y) * y)), (4)) + (x * y)) + (x * x)) < g_n) {
return;
}
} else {
if (((x * x) + (y * y)) < g_n) {
return;
}
}
consider_i64_i64_i64_i64_i64(basis_b, (basis_a + basis_b), (coeff_b - coeff_a), coeff_a, (current_depth + 1));
if ((basis_a > 0 && basis_a < basis_b)) {
consider_i64_i64_i64_i64_i64(basis_a, (basis_a + basis_b), (coeff_a - coeff_b), coeff_b, (current_depth + 1));
}
}
int64_t f_i64(int64_t n) {
g_n = n;
int64_t steps = 0;
while (1) {
g_steps = steps;
g_split_depth = FLOW_CHECKED_DIV(((steps + 1)), (2));
g_best_steps = steps;
g_best_value = (n + 1);
consider_i64_i64_i64_i64_i64(0, 1, 0, n, 0);
if (g_best_value <= n) {
return g_best_value;
}
steps = (steps + 1);
}
return 0;
}
int32_t main(void) {
printf("%lld\n", f_i64((1000000000000 + 39)));
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>
// Module static: g_n
llvm.mlir.global internal @g_n(0 : i64) : i64
// Module static: g_steps
llvm.mlir.global internal @g_steps(0 : i64) : i64
// Module static: g_split_depth
llvm.mlir.global internal @g_split_depth(0 : i64) : i64
// Module static: g_best_steps
llvm.mlir.global internal @g_best_steps(0 : i64) : i64
// Module static: g_best_value
llvm.mlir.global internal @g_best_value(0 : i64) : i64
// Module static: g_local_a
llvm.mlir.global internal @g_local_a(0 : i64) : i64
// Module static: g_local_b
llvm.mlir.global internal @g_local_b(0 : i64) : i64
// Module static: g_norm
llvm.mlir.global internal @g_norm(0 : i64) : i64
// Module static: g_inv_result
llvm.mlir.global internal @g_inv_result(0 : i64) : i64
func.func @mod_inverse(%arg0: i64, %arg1: i64) -> i32 {
%0 = arith.remsi %arg0, %arg1 : i64
%1 = arith.addi %0, %arg1 : i64
%2 = arith.remsi %1, %arg1 : i64
%3 = llvm.mlir.constant(1 : i64) : i64
%4 = llvm.alloca %3 x i64 : (i64) -> !llvm.ptr
llvm.store %2, %4 : i64, !llvm.ptr
%5 = arith.extsi %arg1 : i64 to i128
%6 = llvm.mlir.constant(1 : i64) : i64
%7 = llvm.alloca %6 x i128 : (i64) -> !llvm.ptr
llvm.store %5, %7 : i128, !llvm.ptr
%8 = llvm.load %4 : !llvm.ptr -> i64
%9 = arith.extsi %8 : i64 to i128
%10 = llvm.mlir.constant(1 : i64) : i64
%11 = llvm.alloca %10 x i128 : (i64) -> !llvm.ptr
llvm.store %9, %11 : i128, !llvm.ptr
%12 = arith.constant 0 : i32
%13 = arith.extsi %12 : i32 to i128
%14 = llvm.mlir.constant(1 : i64) : i64
%15 = llvm.alloca %14 x i128 : (i64) -> !llvm.ptr
llvm.store %13, %15 : i128, !llvm.ptr
%16 = arith.constant 1 : i32
%17 = arith.extsi %16 : i32 to i128
%18 = llvm.mlir.constant(1 : i64) : i64
%19 = llvm.alloca %18 x i128 : (i64) -> !llvm.ptr
llvm.store %17, %19 : i128, !llvm.ptr
cf.br ^bb0
^bb0:
%20 = llvm.load %11 : !llvm.ptr -> i128
%21 = arith.constant 0 : i32
%22 = arith.extsi %21 : i32 to i128
%24 = arith.trunci %20 : i128 to i64
%25 = arith.trunci %22 : i128 to i64
%23 = arith.cmpi ne, %24, %25 : i64
cf.cond_br %23, ^bb1, ^bb2
^bb1:
%26 = llvm.load %7 : !llvm.ptr -> i128
%27 = llvm.load %11 : !llvm.ptr -> i128
%29 = arith.trunci %26 : i128 to i64
%30 = arith.trunci %27 : i128 to i64
%28 = arith.divsi %29, %30 : i64
%31 = arith.extsi %28 : i64 to i128
%32 = llvm.load %7 : !llvm.ptr -> i128
%33 = llvm.load %11 : !llvm.ptr -> i128
%35 = arith.trunci %31 : i128 to i64
%36 = arith.trunci %33 : i128 to i64
%34 = arith.muli %35, %36 : i64
%38 = arith.trunci %32 : i128 to i64
%37 = arith.subi %38, %34 : i64
%39 = arith.extsi %37 : i64 to i128
%40 = llvm.load %11 : !llvm.ptr -> i128
llvm.store %40, %7 : i128, !llvm.ptr
llvm.store %39, %11 : i128, !llvm.ptr
%41 = llvm.load %15 : !llvm.ptr -> i128
%42 = llvm.load %19 : !llvm.ptr -> i128
%44 = arith.trunci %31 : i128 to i64
%45 = arith.trunci %42 : i128 to i64
%43 = arith.muli %44, %45 : i64
%47 = arith.trunci %41 : i128 to i64
%46 = arith.subi %47, %43 : i64
%48 = arith.extsi %46 : i64 to i128
%49 = llvm.load %19 : !llvm.ptr -> i128
llvm.store %49, %15 : i128, !llvm.ptr
llvm.store %48, %19 : i128, !llvm.ptr
cf.br ^bb0
^bb2:
%50 = llvm.load %7 : !llvm.ptr -> i128
%51 = arith.constant 1 : i32
%52 = arith.extsi %51 : i32 to i128
%54 = arith.trunci %50 : i128 to i64
%55 = arith.trunci %52 : i128 to i64
%53 = arith.cmpi ne, %54, %55 : i64
cf.cond_br %53, ^bb3, ^bb4
^bb3:
%56 = arith.constant 0 : i32
func.return %56 : i32
^bb4:
cf.br ^bb5
^bb5:
%57 = arith.extsi %arg1 : i64 to i128
%58 = llvm.load %15 : !llvm.ptr -> i128
%60 = arith.trunci %58 : i128 to i64
%61 = arith.trunci %57 : i128 to i64
%59 = arith.remsi %60, %61 : i64
%63 = arith.trunci %57 : i128 to i64
%62 = arith.addi %59, %63 : i64
%65 = arith.trunci %57 : i128 to i64
%64 = arith.remsi %62, %65 : i64
%66 = llvm.mlir.addressof @g_inv_result : !llvm.ptr
llvm.store %64, %66 : i64, !llvm.ptr
%67 = arith.constant 1 : i32
func.return %67 : i32
}
func.func @check(%arg0: i64, %arg1: i64, %arg2: i64) -> () {
%68 = arith.constant 0 : i32
%70 = arith.extsi %68 : i32 to i64
%69 = arith.cmpi slt, %arg0, %70 : i64
%71 = scf.if %69 -> (i1) {
%72 = arith.constant true
scf.yield %72 : i1
} else {
%73 = arith.constant 0 : i32
%75 = arith.extsi %73 : i32 to i64
%74 = arith.cmpi slt, %arg1, %75 : i64
scf.yield %74 : i1
}
cf.cond_br %71, ^bb6, ^bb7
^bb6:
func.return
^bb7:
cf.br ^bb8
^bb8:
%76 = arith.muli %arg0, %arg0 : i64
%77 = arith.muli %arg1, %arg1 : i64
%78 = arith.addi %76, %77 : i64
%79 = llvm.mlir.addressof @g_norm : !llvm.ptr
%80 = llvm.load %79 : !llvm.ptr -> i64
%81 = arith.cmpi sgt, %78, %80 : i64
cf.cond_br %81, ^bb9, ^bb10
^bb9:
func.return
^bb10:
cf.br ^bb11
^bb11:
%82 = llvm.mlir.constant(1 : i64) : i64
%83 = llvm.alloca %82 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %83 : i64, !llvm.ptr
%84 = llvm.mlir.constant(1 : i64) : i64
%85 = llvm.alloca %84 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %85 : i64, !llvm.ptr
%86 = llvm.mlir.addressof @g_local_a : !llvm.ptr
%87 = llvm.load %86 : !llvm.ptr -> i64
%88 = llvm.mlir.constant(1 : i64) : i64
%89 = llvm.alloca %88 x i64 : (i64) -> !llvm.ptr
llvm.store %87, %89 : i64, !llvm.ptr
%90 = llvm.mlir.addressof @g_local_b : !llvm.ptr
%91 = llvm.load %90 : !llvm.ptr -> i64
%92 = llvm.mlir.constant(1 : i64) : i64
%93 = llvm.alloca %92 x i64 : (i64) -> !llvm.ptr
llvm.store %91, %93 : i64, !llvm.ptr
%94 = llvm.mlir.addressof @g_steps : !llvm.ptr
%95 = llvm.load %94 : !llvm.ptr -> i64
%96 = arith.constant 1 : i32
%98 = arith.extsi %96 : i32 to i64
%97 = arith.andi %95, %98 : i64
%99 = arith.constant 0 : i32
%101 = arith.extsi %99 : i32 to i64
%100 = arith.cmpi ne, %97, %101 : i64
cf.cond_br %100, ^bb12, ^bb13
^bb12:
%102 = llvm.load %89 : !llvm.ptr -> i64
%103 = arith.constant 1 : i32
%105 = arith.extsi %103 : i32 to i64
%104 = arith.andi %102, %105 : i64
%106 = arith.constant 0 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.cmpi ne, %104, %108 : i64
%109 = scf.if %107 -> (i1) {
%110 = arith.constant true
scf.yield %110 : i1
} else {
%111 = llvm.load %85 : !llvm.ptr -> i64
%112 = arith.constant 1 : i32
%114 = arith.extsi %112 : i32 to i64
%113 = arith.andi %111, %114 : i64
%115 = arith.constant 0 : i32
%117 = arith.extsi %115 : i32 to i64
%116 = arith.cmpi ne, %113, %117 : i64
scf.yield %116 : i1
}
cf.cond_br %109, ^bb15, ^bb16
^bb15:
func.return
^bb16:
cf.br ^bb17
^bb17:
%118 = llvm.load %83 : !llvm.ptr -> i64
%119 = llvm.load %85 : !llvm.ptr -> i64
%120 = arith.constant 2 : i32
%122 = arith.extsi %120 : i32 to i64
%121 = arith.divsi %119, %122 : i64
%123 = arith.subi %118, %121 : i64
llvm.store %123, %83 : i64, !llvm.ptr
%124 = llvm.load %93 : !llvm.ptr -> i64
%125 = llvm.load %89 : !llvm.ptr -> i64
%126 = arith.constant 2 : i32
%128 = arith.extsi %126 : i32 to i64
%127 = arith.divsi %125, %128 : i64
%129 = arith.addi %124, %127 : i64
llvm.store %129, %93 : i64, !llvm.ptr
%130 = llvm.load %93 : !llvm.ptr -> i64
%131 = arith.constant 1 : i32
%133 = arith.extsi %131 : i32 to i64
%132 = arith.andi %130, %133 : i64
%134 = arith.constant 0 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.cmpi ne, %132, %136 : i64
%137 = scf.if %135 -> (i1) {
%138 = arith.constant true
scf.yield %138 : i1
} else {
%139 = llvm.load %83 : !llvm.ptr -> i64
%140 = arith.constant 1 : i32
%142 = arith.extsi %140 : i32 to i64
%141 = arith.andi %139, %142 : i64
%143 = arith.constant 0 : i32
%145 = arith.extsi %143 : i32 to i64
%144 = arith.cmpi ne, %141, %145 : i64
scf.yield %144 : i1
}
cf.cond_br %137, ^bb18, ^bb19
^bb18:
func.return
^bb19:
cf.br ^bb20
^bb20:
%146 = llvm.load %83 : !llvm.ptr -> i64
%147 = arith.constant 2 : i32
%149 = arith.extsi %147 : i32 to i64
%148 = arith.divsi %146, %149 : i64
llvm.store %148, %83 : i64, !llvm.ptr
%150 = llvm.load %85 : !llvm.ptr -> i64
%151 = arith.constant 2 : i32
%153 = arith.extsi %151 : i32 to i64
%152 = arith.divsi %150, %153 : i64
llvm.store %152, %85 : i64, !llvm.ptr
%154 = llvm.load %89 : !llvm.ptr -> i64
%155 = arith.constant 2 : i32
%157 = arith.extsi %155 : i32 to i64
%156 = arith.divsi %154, %157 : i64
llvm.store %156, %89 : i64, !llvm.ptr
%158 = llvm.load %93 : !llvm.ptr -> i64
%159 = arith.constant 2 : i32
%161 = arith.extsi %159 : i32 to i64
%160 = arith.divsi %158, %161 : i64
llvm.store %160, %93 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%162 = llvm.load %83 : !llvm.ptr -> i64
%163 = llvm.load %89 : !llvm.ptr -> i64
%164 = arith.muli %162, %163 : i64
%165 = llvm.load %85 : !llvm.ptr -> i64
%166 = llvm.load %93 : !llvm.ptr -> i64
%167 = arith.muli %165, %166 : i64
%168 = arith.addi %164, %167 : i64
%169 = llvm.mlir.addressof @g_n : !llvm.ptr
%170 = llvm.load %169 : !llvm.ptr -> i64
%171 = arith.cmpi ne, %168, %170 : i64
cf.cond_br %171, ^bb21, ^bb22
^bb21:
func.return
^bb22:
cf.br ^bb23
^bb23:
%172 = llvm.mlir.addressof @g_steps : !llvm.ptr
%173 = llvm.load %172 : !llvm.ptr -> i64
%174 = llvm.mlir.addressof @g_split_depth : !llvm.ptr
%175 = llvm.load %174 : !llvm.ptr -> i64
%176 = arith.subi %173, %175 : i64
%177 = arith.constant 0 : i32
%178 = arith.extsi %177 : i32 to i64
%179 = llvm.mlir.constant(1 : i64) : i64
%180 = llvm.alloca %179 x i64 : (i64) -> !llvm.ptr
llvm.store %178, %180 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%181 = llvm.load %180 : !llvm.ptr -> i64
%182 = arith.cmpi sle, %181, %176 : i64
%183 = scf.if %182 -> (i1) {
%184 = llvm.load %83 : !llvm.ptr -> i64
%185 = arith.constant 0 : i32
%187 = arith.extsi %185 : i32 to i64
%186 = arith.cmpi ne, %184, %187 : i64
scf.yield %186 : i1
} else {
%188 = arith.constant false
scf.yield %188 : i1
}
%189 = scf.if %183 -> (i1) {
%190 = llvm.load %85 : !llvm.ptr -> i64
%191 = arith.constant 0 : i32
%193 = arith.extsi %191 : i32 to i64
%192 = arith.cmpi ne, %190, %193 : i64
scf.yield %192 : i1
} else {
%194 = arith.constant false
scf.yield %194 : i1
}
cf.cond_br %189, ^bb25, ^bb26
^bb25:
%195 = llvm.load %83 : !llvm.ptr -> i64
%196 = llvm.load %85 : !llvm.ptr -> i64
%197 = arith.cmpi sgt, %195, %196 : i64
cf.cond_br %197, ^bb27, ^bb28
^bb27:
%198 = llvm.load %83 : !llvm.ptr -> i64
%199 = llvm.load %85 : !llvm.ptr -> i64
llvm.store %199, %83 : i64, !llvm.ptr
llvm.store %198, %85 : i64, !llvm.ptr
%200 = llvm.load %89 : !llvm.ptr -> i64
%201 = llvm.load %93 : !llvm.ptr -> i64
llvm.store %201, %89 : i64, !llvm.ptr
llvm.store %200, %93 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%202 = llvm.load %85 : !llvm.ptr -> i64
%203 = llvm.load %83 : !llvm.ptr -> i64
%204 = arith.subi %202, %203 : i64
llvm.store %204, %85 : i64, !llvm.ptr
%205 = llvm.load %89 : !llvm.ptr -> i64
%206 = llvm.load %93 : !llvm.ptr -> i64
%207 = arith.addi %205, %206 : i64
llvm.store %207, %89 : i64, !llvm.ptr
%208 = llvm.load %180 : !llvm.ptr -> i64
%209 = arith.constant 1 : i32
%211 = arith.extsi %209 : i32 to i64
%210 = arith.addi %208, %211 : i64
llvm.store %210, %180 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%212 = llvm.load %180 : !llvm.ptr -> i64
%213 = arith.cmpi sgt, %212, %176 : i64
cf.cond_br %213, ^bb30, ^bb31
^bb30:
func.return
^bb31:
cf.br ^bb32
^bb32:
%214 = llvm.load %89 : !llvm.ptr -> i64
%215 = llvm.load %93 : !llvm.ptr -> i64
%216 = arith.addi %214, %215 : i64
%217 = llvm.mlir.addressof @g_n : !llvm.ptr
%218 = llvm.load %217 : !llvm.ptr -> i64
%219 = arith.subi %216, %218 : i64
%220 = llvm.mlir.addressof @g_n : !llvm.ptr
%221 = llvm.load %220 : !llvm.ptr -> i64
%222 = arith.remsi %219, %221 : i64
%223 = llvm.mlir.addressof @g_n : !llvm.ptr
%224 = llvm.load %223 : !llvm.ptr -> i64
%225 = arith.addi %222, %224 : i64
%226 = llvm.mlir.addressof @g_n : !llvm.ptr
%227 = llvm.load %226 : !llvm.ptr -> i64
%228 = arith.remsi %225, %227 : i64
%230 = llvm.mlir.addressof @g_n : !llvm.ptr
%231 = llvm.load %230 : !llvm.ptr -> i64
%229 = func.call @mod_inverse(%228, %231) : (i64, i64) -> i32
%232 = arith.constant 0 : i32
%233 = arith.cmpi eq, %229, %232 : i32
cf.cond_br %233, ^bb33, ^bb34
^bb33:
func.return
^bb34:
cf.br ^bb35
^bb35:
%234 = llvm.mlir.addressof @g_inv_result : !llvm.ptr
%235 = llvm.load %234 : !llvm.ptr -> i64
%236 = llvm.load %180 : !llvm.ptr -> i64
%237 = arith.addi %arg2, %236 : i64
%238 = llvm.mlir.addressof @g_n : !llvm.ptr
%239 = llvm.load %238 : !llvm.ptr -> i64
%240 = llvm.mlir.constant(1 : i64) : i64
%241 = llvm.alloca %240 x i64 : (i64) -> !llvm.ptr
llvm.store %228, %241 : i64, !llvm.ptr
%242 = arith.subi %239, %228 : i64
%243 = llvm.load %241 : !llvm.ptr -> i64
%244 = arith.cmpi slt, %242, %243 : i64
cf.cond_br %244, ^bb36, ^bb37
^bb36:
%245 = arith.subi %239, %228 : i64
llvm.store %245, %241 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%246 = llvm.load %241 : !llvm.ptr -> i64
%247 = arith.cmpi slt, %235, %246 : i64
cf.cond_br %247, ^bb39, ^bb40
^bb39:
llvm.store %235, %241 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%248 = arith.subi %239, %235 : i64
%249 = llvm.load %241 : !llvm.ptr -> i64
%250 = arith.cmpi slt, %248, %249 : i64
cf.cond_br %250, ^bb42, ^bb43
^bb42:
%251 = arith.subi %239, %235 : i64
llvm.store %251, %241 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%252 = llvm.mlir.addressof @g_best_steps : !llvm.ptr
%253 = llvm.load %252 : !llvm.ptr -> i64
%254 = arith.cmpi slt, %237, %253 : i64
cf.cond_br %254, ^bb45, ^bb46
^bb45:
%255 = llvm.mlir.addressof @g_best_steps : !llvm.ptr
llvm.store %237, %255 : i64, !llvm.ptr
%256 = llvm.load %241 : !llvm.ptr -> i64
%257 = llvm.mlir.addressof @g_best_value : !llvm.ptr
llvm.store %256, %257 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
%258 = llvm.mlir.addressof @g_best_steps : !llvm.ptr
%259 = llvm.load %258 : !llvm.ptr -> i64
%260 = arith.cmpi eq, %237, %259 : i64
%261 = scf.if %260 -> (i1) {
%262 = llvm.load %241 : !llvm.ptr -> i64
%263 = llvm.mlir.addressof @g_best_value : !llvm.ptr
%264 = llvm.load %263 : !llvm.ptr -> i64
%265 = arith.cmpi slt, %262, %264 : i64
scf.yield %265 : i1
} else {
%266 = arith.constant false
scf.yield %266 : i1
}
cf.cond_br %261, ^bb48, ^bb49
^bb48:
%267 = llvm.mlir.addressof @g_best_steps : !llvm.ptr
llvm.store %237, %267 : i64, !llvm.ptr
%268 = llvm.load %241 : !llvm.ptr -> i64
%269 = llvm.mlir.addressof @g_best_value : !llvm.ptr
llvm.store %268, %269 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
cf.br ^bb47
^bb47:
func.return
}
func.func @consider(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64, %arg4: i64) -> () {
%270 = llvm.mlir.constant(1 : i64) : i64
%271 = llvm.alloca %270 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %271 : i64, !llvm.ptr
%272 = llvm.mlir.constant(1 : i64) : i64
%273 = llvm.alloca %272 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %273 : i64, !llvm.ptr
%274 = llvm.mlir.constant(1 : i64) : i64
%275 = llvm.alloca %274 x i64 : (i64) -> !llvm.ptr
llvm.store %arg2, %275 : i64, !llvm.ptr
%276 = llvm.mlir.constant(1 : i64) : i64
%277 = llvm.alloca %276 x i64 : (i64) -> !llvm.ptr
llvm.store %arg3, %277 : i64, !llvm.ptr
%278 = llvm.load %271 : !llvm.ptr -> i64
%279 = llvm.load %273 : !llvm.ptr -> i64
%280 = arith.cmpi sgt, %278, %279 : i64
cf.cond_br %280, ^bb51, ^bb52
^bb51:
%281 = llvm.load %271 : !llvm.ptr -> i64
%282 = llvm.load %273 : !llvm.ptr -> i64
llvm.store %282, %271 : i64, !llvm.ptr
llvm.store %281, %273 : i64, !llvm.ptr
%283 = llvm.load %275 : !llvm.ptr -> i64
%284 = llvm.load %277 : !llvm.ptr -> i64
llvm.store %284, %275 : i64, !llvm.ptr
llvm.store %283, %277 : i64, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
%285 = llvm.load %277 : !llvm.ptr -> i64
%286 = arith.constant 0 : i32
%288 = arith.extsi %286 : i32 to i64
%287 = arith.cmpi slt, %285, %288 : i64
cf.cond_br %287, ^bb54, ^bb55
^bb54:
func.return
^bb55:
cf.br ^bb56
^bb56:
%289 = llvm.load %275 : !llvm.ptr -> i64
%290 = arith.constant 0 : i32
%292 = arith.extsi %290 : i32 to i64
%291 = arith.cmpi slt, %289, %292 : i64
cf.cond_br %291, ^bb57, ^bb58
^bb57:
%293 = arith.constant 0 : i32
%294 = llvm.load %275 : !llvm.ptr -> i64
%296 = arith.extsi %293 : i32 to i64
%295 = arith.subi %296, %294 : i64
%297 = llvm.load %273 : !llvm.ptr -> i64
%298 = arith.addi %295, %297 : i64
%299 = arith.constant 1 : i32
%301 = arith.extsi %299 : i32 to i64
%300 = arith.subi %298, %301 : i64
%302 = llvm.load %273 : !llvm.ptr -> i64
%303 = arith.divsi %300, %302 : i64
%304 = llvm.load %275 : !llvm.ptr -> i64
%305 = llvm.load %273 : !llvm.ptr -> i64
%306 = arith.muli %303, %305 : i64
%307 = arith.addi %304, %306 : i64
llvm.store %307, %275 : i64, !llvm.ptr
%308 = llvm.load %277 : !llvm.ptr -> i64
%309 = llvm.load %271 : !llvm.ptr -> i64
%310 = arith.muli %303, %309 : i64
%311 = arith.subi %308, %310 : i64
llvm.store %311, %277 : i64, !llvm.ptr
%312 = llvm.load %277 : !llvm.ptr -> i64
%313 = arith.constant 0 : i32
%315 = arith.extsi %313 : i32 to i64
%314 = arith.cmpi slt, %312, %315 : i64
cf.cond_br %314, ^bb60, ^bb61
^bb60:
func.return
^bb61:
cf.br ^bb62
^bb62:
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%316 = llvm.load %271 : !llvm.ptr -> i64
%317 = llvm.load %275 : !llvm.ptr -> i64
%318 = arith.muli %316, %317 : i64
%319 = llvm.load %273 : !llvm.ptr -> i64
%320 = llvm.load %277 : !llvm.ptr -> i64
%321 = arith.muli %319, %320 : i64
%322 = arith.addi %318, %321 : i64
%323 = llvm.mlir.addressof @g_n : !llvm.ptr
%324 = llvm.load %323 : !llvm.ptr -> i64
%325 = arith.cmpi ne, %322, %324 : i64
cf.cond_br %325, ^bb63, ^bb64
^bb63:
func.return
^bb64:
cf.br ^bb65
^bb65:
%326 = llvm.mlir.addressof @g_split_depth : !llvm.ptr
%327 = llvm.load %326 : !llvm.ptr -> i64
%328 = arith.cmpi eq, %arg4, %327 : i64
cf.cond_br %328, ^bb66, ^bb67
^bb66:
%329 = llvm.load %271 : !llvm.ptr -> i64
%330 = llvm.mlir.constant(1 : i64) : i64
%331 = llvm.alloca %330 x i64 : (i64) -> !llvm.ptr
llvm.store %329, %331 : i64, !llvm.ptr
%332 = llvm.load %273 : !llvm.ptr -> i64
%333 = llvm.mlir.constant(1 : i64) : i64
%334 = llvm.alloca %333 x i64 : (i64) -> !llvm.ptr
llvm.store %332, %334 : i64, !llvm.ptr
%335 = llvm.load %275 : !llvm.ptr -> i64
%336 = llvm.mlir.constant(1 : i64) : i64
%337 = llvm.alloca %336 x i64 : (i64) -> !llvm.ptr
llvm.store %335, %337 : i64, !llvm.ptr
%338 = llvm.load %277 : !llvm.ptr -> i64
%339 = llvm.mlir.constant(1 : i64) : i64
%340 = llvm.alloca %339 x i64 : (i64) -> !llvm.ptr
llvm.store %338, %340 : i64, !llvm.ptr
%341 = llvm.mlir.addressof @g_steps : !llvm.ptr
%342 = llvm.load %341 : !llvm.ptr -> i64
%343 = arith.constant 1 : i32
%345 = arith.extsi %343 : i32 to i64
%344 = arith.andi %342, %345 : i64
%346 = arith.constant 0 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.cmpi ne, %344, %348 : i64
cf.cond_br %347, ^bb69, ^bb70
^bb69:
%349 = llvm.load %331 : !llvm.ptr -> i64
%350 = arith.constant 2 : i32
%352 = arith.extsi %350 : i32 to i64
%351 = arith.muli %349, %352 : i64
llvm.store %351, %331 : i64, !llvm.ptr
%353 = llvm.load %334 : !llvm.ptr -> i64
%354 = arith.constant 2 : i32
%356 = arith.extsi %354 : i32 to i64
%355 = arith.muli %353, %356 : i64
llvm.store %355, %334 : i64, !llvm.ptr
%357 = llvm.load %337 : !llvm.ptr -> i64
%358 = arith.constant 2 : i32
%360 = arith.extsi %358 : i32 to i64
%359 = arith.muli %357, %360 : i64
llvm.store %359, %337 : i64, !llvm.ptr
%361 = llvm.load %340 : !llvm.ptr -> i64
%362 = arith.constant 2 : i32
%364 = arith.extsi %362 : i32 to i64
%363 = arith.muli %361, %364 : i64
llvm.store %363, %340 : i64, !llvm.ptr
%365 = llvm.load %334 : !llvm.ptr -> i64
%366 = llvm.load %331 : !llvm.ptr -> i64
%367 = arith.constant 2 : i32
%369 = arith.extsi %367 : i32 to i64
%368 = arith.divsi %366, %369 : i64
%370 = arith.subi %365, %368 : i64
llvm.store %370, %334 : i64, !llvm.ptr
%371 = llvm.load %337 : !llvm.ptr -> i64
%372 = llvm.load %340 : !llvm.ptr -> i64
%373 = arith.constant 2 : i32
%375 = arith.extsi %373 : i32 to i64
%374 = arith.divsi %372, %375 : i64
%376 = arith.addi %371, %374 : i64
llvm.store %376, %337 : i64, !llvm.ptr
%377 = llvm.load %331 : !llvm.ptr -> i64
%378 = llvm.load %337 : !llvm.ptr -> i64
%379 = arith.muli %377, %378 : i64
%380 = llvm.load %334 : !llvm.ptr -> i64
%381 = llvm.load %340 : !llvm.ptr -> i64
%382 = arith.muli %380, %381 : i64
%383 = arith.addi %379, %382 : i64
%384 = arith.constant 4 : i32
%385 = llvm.mlir.addressof @g_n : !llvm.ptr
%386 = llvm.load %385 : !llvm.ptr -> i64
%388 = arith.extsi %384 : i32 to i64
%387 = arith.muli %388, %386 : i64
%389 = arith.cmpi ne, %383, %387 : i64
cf.cond_br %389, ^bb72, ^bb73
^bb72:
func.return
^bb73:
cf.br ^bb74
^bb74:
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
%390 = llvm.load %331 : !llvm.ptr -> i64
%391 = llvm.load %331 : !llvm.ptr -> i64
%392 = arith.muli %390, %391 : i64
%393 = llvm.load %334 : !llvm.ptr -> i64
%394 = llvm.load %334 : !llvm.ptr -> i64
%395 = arith.muli %393, %394 : i64
%396 = arith.addi %392, %395 : i64
%397 = llvm.mlir.addressof @g_n : !llvm.ptr
%398 = llvm.load %397 : !llvm.ptr -> i64
%399 = arith.cmpi slt, %396, %398 : i64
cf.cond_br %399, ^bb75, ^bb76
^bb75:
func.return
^bb76:
cf.br ^bb77
^bb77:
%400 = llvm.load %337 : !llvm.ptr -> i64
%401 = llvm.load %334 : !llvm.ptr -> i64
%402 = arith.muli %400, %401 : i64
%403 = llvm.load %340 : !llvm.ptr -> i64
%404 = llvm.load %331 : !llvm.ptr -> i64
%405 = arith.muli %403, %404 : i64
%406 = arith.subi %402, %405 : i64
%407 = arith.divsi %406, %396 : i64
%408 = llvm.load %337 : !llvm.ptr -> i64
%409 = llvm.load %334 : !llvm.ptr -> i64
%410 = arith.muli %407, %409 : i64
%411 = arith.subi %408, %410 : i64
llvm.store %411, %337 : i64, !llvm.ptr
%412 = llvm.load %340 : !llvm.ptr -> i64
%413 = llvm.load %331 : !llvm.ptr -> i64
%414 = arith.muli %407, %413 : i64
%415 = arith.addi %412, %414 : i64
llvm.store %415, %340 : i64, !llvm.ptr
%416 = arith.muli %407, %396 : i64
%417 = arith.subi %406, %416 : i64
%418 = arith.constant 0 : i32
%420 = arith.extsi %418 : i32 to i64
%419 = arith.cmpi slt, %417, %420 : i64
cf.cond_br %419, ^bb78, ^bb79
^bb78:
%421 = llvm.load %337 : !llvm.ptr -> i64
%422 = llvm.load %334 : !llvm.ptr -> i64
%423 = arith.addi %421, %422 : i64
llvm.store %423, %337 : i64, !llvm.ptr
%424 = llvm.load %340 : !llvm.ptr -> i64
%425 = llvm.load %331 : !llvm.ptr -> i64
%426 = arith.subi %424, %425 : i64
llvm.store %426, %340 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%427 = llvm.load %331 : !llvm.ptr -> i64
%428 = llvm.mlir.addressof @g_local_a : !llvm.ptr
llvm.store %427, %428 : i64, !llvm.ptr
%429 = llvm.load %334 : !llvm.ptr -> i64
%430 = llvm.mlir.addressof @g_local_b : !llvm.ptr
llvm.store %429, %430 : i64, !llvm.ptr
%431 = llvm.mlir.addressof @g_norm : !llvm.ptr
llvm.store %396, %431 : i64, !llvm.ptr
%433 = llvm.load %337 : !llvm.ptr -> i64
%434 = llvm.load %340 : !llvm.ptr -> i64
func.call @check(%433, %434, %arg4) : (i64, i64, i64) -> ()
%436 = llvm.load %337 : !llvm.ptr -> i64
%437 = llvm.load %334 : !llvm.ptr -> i64
%438 = arith.subi %436, %437 : i64
%439 = llvm.load %340 : !llvm.ptr -> i64
%440 = llvm.load %331 : !llvm.ptr -> i64
%441 = arith.addi %439, %440 : i64
func.call @check(%438, %441, %arg4) : (i64, i64, i64) -> ()
func.return
^bb67:
cf.br ^bb68
^bb68:
%442 = llvm.load %271 : !llvm.ptr -> i64
%443 = llvm.mlir.constant(1 : i64) : i64
%444 = llvm.alloca %443 x i64 : (i64) -> !llvm.ptr
llvm.store %442, %444 : i64, !llvm.ptr
%445 = llvm.load %273 : !llvm.ptr -> i64
%446 = llvm.mlir.constant(1 : i64) : i64
%447 = llvm.alloca %446 x i64 : (i64) -> !llvm.ptr
llvm.store %445, %447 : i64, !llvm.ptr
%448 = llvm.mlir.constant(1 : i64) : i64
%449 = llvm.alloca %448 x i64 : (i64) -> !llvm.ptr
llvm.store %arg4, %449 : i64, !llvm.ptr
cf.br ^bb81
^bb81:
%450 = llvm.load %449 : !llvm.ptr -> i64
%451 = llvm.mlir.addressof @g_steps : !llvm.ptr
%452 = llvm.load %451 : !llvm.ptr -> i64
%453 = arith.constant 2 : i32
%455 = arith.extsi %453 : i32 to i64
%454 = arith.divsi %452, %455 : i64
%456 = arith.cmpi slt, %450, %454 : i64
cf.cond_br %456, ^bb82, ^bb83
^bb82:
%457 = llvm.load %444 : !llvm.ptr -> i64
%458 = llvm.load %447 : !llvm.ptr -> i64
%459 = arith.cmpi sgt, %457, %458 : i64
cf.cond_br %459, ^bb84, ^bb85
^bb84:
%460 = llvm.load %444 : !llvm.ptr -> i64
%461 = llvm.load %447 : !llvm.ptr -> i64
llvm.store %461, %444 : i64, !llvm.ptr
llvm.store %460, %447 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
%462 = llvm.load %444 : !llvm.ptr -> i64
%463 = llvm.load %447 : !llvm.ptr -> i64
%464 = arith.addi %462, %463 : i64
llvm.store %464, %444 : i64, !llvm.ptr
%465 = llvm.load %444 : !llvm.ptr -> i64
%466 = llvm.load %447 : !llvm.ptr -> i64
llvm.store %466, %444 : i64, !llvm.ptr
llvm.store %465, %447 : i64, !llvm.ptr
%467 = llvm.load %449 : !llvm.ptr -> i64
%468 = arith.constant 1 : i32
%470 = arith.extsi %468 : i32 to i64
%469 = arith.addi %467, %470 : i64
llvm.store %469, %449 : i64, !llvm.ptr
cf.br ^bb81
^bb83:
%471 = llvm.load %444 : !llvm.ptr -> i64
%472 = llvm.load %447 : !llvm.ptr -> i64
%473 = arith.cmpi sgt, %471, %472 : i64
cf.cond_br %473, ^bb87, ^bb88
^bb87:
%474 = llvm.load %444 : !llvm.ptr -> i64
%475 = llvm.load %447 : !llvm.ptr -> i64
llvm.store %475, %444 : i64, !llvm.ptr
llvm.store %474, %447 : i64, !llvm.ptr
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
%476 = llvm.mlir.addressof @g_steps : !llvm.ptr
%477 = llvm.load %476 : !llvm.ptr -> i64
%478 = arith.constant 1 : i32
%480 = arith.extsi %478 : i32 to i64
%479 = arith.andi %477, %480 : i64
%481 = arith.constant 0 : i32
%483 = arith.extsi %481 : i32 to i64
%482 = arith.cmpi ne, %479, %483 : i64
cf.cond_br %482, ^bb90, ^bb91
^bb90:
%484 = arith.constant 5 : i32
%485 = llvm.load %447 : !llvm.ptr -> i64
%487 = arith.extsi %484 : i32 to i64
%486 = arith.muli %487, %485 : i64
%488 = llvm.load %447 : !llvm.ptr -> i64
%489 = arith.muli %486, %488 : i64
%490 = arith.constant 4 : i32
%492 = arith.extsi %490 : i32 to i64
%491 = arith.divsi %489, %492 : i64
%493 = llvm.load %444 : !llvm.ptr -> i64
%494 = llvm.load %447 : !llvm.ptr -> i64
%495 = arith.muli %493, %494 : i64
%496 = arith.addi %491, %495 : i64
%497 = llvm.load %444 : !llvm.ptr -> i64
%498 = llvm.load %444 : !llvm.ptr -> i64
%499 = arith.muli %497, %498 : i64
%500 = arith.addi %496, %499 : i64
%501 = llvm.mlir.addressof @g_n : !llvm.ptr
%502 = llvm.load %501 : !llvm.ptr -> i64
%503 = arith.cmpi slt, %500, %502 : i64
cf.cond_br %503, ^bb93, ^bb94
^bb93:
func.return
^bb94:
cf.br ^bb95
^bb95:
cf.br ^bb92
^bb91:
%504 = llvm.load %444 : !llvm.ptr -> i64
%505 = llvm.load %444 : !llvm.ptr -> i64
%506 = arith.muli %504, %505 : i64
%507 = llvm.load %447 : !llvm.ptr -> i64
%508 = llvm.load %447 : !llvm.ptr -> i64
%509 = arith.muli %507, %508 : i64
%510 = arith.addi %506, %509 : i64
%511 = llvm.mlir.addressof @g_n : !llvm.ptr
%512 = llvm.load %511 : !llvm.ptr -> i64
%513 = arith.cmpi slt, %510, %512 : i64
cf.cond_br %513, ^bb96, ^bb97
^bb96:
func.return
^bb97:
cf.br ^bb98
^bb98:
cf.br ^bb92
^bb92:
%515 = llvm.load %273 : !llvm.ptr -> i64
%516 = llvm.load %271 : !llvm.ptr -> i64
%517 = llvm.load %273 : !llvm.ptr -> i64
%518 = arith.addi %516, %517 : i64
%519 = llvm.load %277 : !llvm.ptr -> i64
%520 = llvm.load %275 : !llvm.ptr -> i64
%521 = arith.subi %519, %520 : i64
%522 = llvm.load %275 : !llvm.ptr -> i64
%523 = arith.constant 1 : i32
%525 = arith.extsi %523 : i32 to i64
%524 = arith.addi %arg4, %525 : i64
func.call @consider(%515, %518, %521, %522, %524) : (i64, i64, i64, i64, i64) -> ()
%526 = llvm.load %271 : !llvm.ptr -> i64
%527 = arith.constant 0 : i32
%529 = arith.extsi %527 : i32 to i64
%528 = arith.cmpi sgt, %526, %529 : i64
%530 = scf.if %528 -> (i1) {
%531 = llvm.load %271 : !llvm.ptr -> i64
%532 = llvm.load %273 : !llvm.ptr -> i64
%533 = arith.cmpi slt, %531, %532 : i64
scf.yield %533 : i1
} else {
%534 = arith.constant false
scf.yield %534 : i1
}
cf.cond_br %530, ^bb99, ^bb100
^bb99:
%536 = llvm.load %271 : !llvm.ptr -> i64
%537 = llvm.load %271 : !llvm.ptr -> i64
%538 = llvm.load %273 : !llvm.ptr -> i64
%539 = arith.addi %537, %538 : i64
%540 = llvm.load %275 : !llvm.ptr -> i64
%541 = llvm.load %277 : !llvm.ptr -> i64
%542 = arith.subi %540, %541 : i64
%543 = llvm.load %277 : !llvm.ptr -> i64
%544 = arith.constant 1 : i32
%546 = arith.extsi %544 : i32 to i64
%545 = arith.addi %arg4, %546 : i64
func.call @consider(%536, %539, %542, %543, %545) : (i64, i64, i64, i64, i64) -> ()
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
func.return
}
func.func @f(%arg0: i64) -> i64 {
%547 = llvm.mlir.addressof @g_n : !llvm.ptr
llvm.store %arg0, %547 : i64, !llvm.ptr
%548 = arith.constant 0 : i32
%549 = arith.extsi %548 : i32 to i64
%550 = llvm.mlir.constant(1 : i64) : i64
%551 = llvm.alloca %550 x i64 : (i64) -> !llvm.ptr
llvm.store %549, %551 : i64, !llvm.ptr
cf.br ^bb102
^bb102:
%552 = arith.constant 1 : i1
cf.cond_br %552, ^bb103, ^bb104
^bb103:
%553 = llvm.load %551 : !llvm.ptr -> i64
%554 = llvm.mlir.addressof @g_steps : !llvm.ptr
llvm.store %553, %554 : i64, !llvm.ptr
%555 = llvm.load %551 : !llvm.ptr -> i64
%556 = arith.constant 1 : i32
%558 = arith.extsi %556 : i32 to i64
%557 = arith.addi %555, %558 : i64
%559 = arith.constant 2 : i32
%561 = arith.extsi %559 : i32 to i64
%560 = arith.divsi %557, %561 : i64
%562 = llvm.mlir.addressof @g_split_depth : !llvm.ptr
llvm.store %560, %562 : i64, !llvm.ptr
%563 = llvm.load %551 : !llvm.ptr -> i64
%564 = llvm.mlir.addressof @g_best_steps : !llvm.ptr
llvm.store %563, %564 : i64, !llvm.ptr
%565 = arith.constant 1 : i32
%567 = arith.extsi %565 : i32 to i64
%566 = arith.addi %arg0, %567 : i64
%568 = llvm.mlir.addressof @g_best_value : !llvm.ptr
llvm.store %566, %568 : i64, !llvm.ptr
%570 = arith.constant 0 : i32
%571 = arith.constant 1 : i32
%572 = arith.constant 0 : i32
%573 = arith.constant 0 : i32
%574 = arith.extsi %570 : i32 to i64
%575 = arith.extsi %571 : i32 to i64
%576 = arith.extsi %572 : i32 to i64
%577 = arith.extsi %573 : i32 to i64
func.call @consider(%574, %575, %576, %arg0, %577) : (i64, i64, i64, i64, i64) -> ()
%578 = llvm.mlir.addressof @g_best_value : !llvm.ptr
%579 = llvm.load %578 : !llvm.ptr -> i64
%580 = arith.cmpi sle, %579, %arg0 : i64
cf.cond_br %580, ^bb105, ^bb106
^bb105:
%581 = llvm.mlir.addressof @g_best_value : !llvm.ptr
%582 = llvm.load %581 : !llvm.ptr -> i64
func.return %582 : i64
^bb106:
cf.br ^bb107
^bb107:
%583 = llvm.load %551 : !llvm.ptr -> i64
%584 = arith.constant 1 : i32
%586 = arith.extsi %584 : i32 to i64
%585 = arith.addi %583, %586 : i64
llvm.store %585, %551 : i64, !llvm.ptr
cf.br ^bb102
^bb104:
%587 = arith.constant 0 : i32
%588 = arith.extsi %587 : i32 to i64
func.return %588 : i64
}
func.func @main() -> i32 {
%589 = llvm.mlir.addressof @str_0 : !llvm.ptr
%591 = arith.constant 995705032704 : i32
%592 = arith.constant 39 : i32
%593 = arith.addi %591, %592 : i32
%594 = arith.extsi %593 : i32 to i64
%590 = func.call @f(%594) : (i64) -> i64
%595 = llvm.call @printf(%589, %590) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%596 = arith.constant 0 : i32
func.return %596 : i32
}
}