Problem 505
Bidirectional Recurrence — A(10^12) via frontier block minimax.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(2^n) | ? |
|---|
| Space complexity | O(n^2) | ? |
|---|
| Approach | Flow solution | Not curated |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 505
# Bidirectional Recurrence — A(10^12) via frontier block minimax.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MASK: i64 = 1152921504606846975 # 2^60 - 1
const CAP: i64 = 1048576
function combine(a: i64, b: i64, c: i64, d: i64) -> i64 {
return ((a * b) + (c * d)) & MASK
}
function state_at(k: i64, out_x: ptr<i64>, out_p: ptr<i64>) -> void {
if k == 0 {
out_x[0] = 0
out_p[0] = 0
return
}
let mut x: i64 = 1
let mut parent: i64 = 0
let mut bits: i32 = 0
let mut t: i64 = k
while t > 0 {
bits = bits + 1
t = t / 2
}
let mut bit: i32 = bits - 2
while bit >= 0 {
if ((k >> bit) & 1) == 1 {
let next_x: i64 = combine(2, x, 3, parent)
parent = x
x = next_x
} else {
let next_x2: i64 = combine(3, x, 2, parent)
parent = x
x = next_x2
}
bit = bit - 1
}
out_x[0] = x
out_p[0] = parent
}
function minimax(x0: i64, parent0: i64, depth: i32, alpha0: i64, beta0: i64) -> i64 {
if depth == 0 { return x0 }
let left0: i64 = combine(3, x0, 2, parent0)
let right0: i64 = combine(2, x0, 3, parent0)
let mut left: i64 = left0
let mut right: i64 = right0
let mut alpha: i64 = alpha0
let mut beta: i64 = beta0
if (depth & 1) == 1 {
if left < right {
let tmp: i64 = left
left = right
right = tmp
}
if depth == 1 { return left }
let mut value: i64 = minimax(left, x0, depth - 1, alpha, beta)
if value > alpha { alpha = value }
if alpha >= beta { return alpha }
value = minimax(right, x0, depth - 1, alpha, beta)
if value > alpha { return value }
return alpha
}
if left > right {
let tmp2: i64 = left
left = right
right = tmp2
}
if depth == 1 { return left }
let mut value2: i64 = minimax(left, x0, depth - 1, alpha, beta)
if value2 < beta { beta = value2 }
if alpha >= beta { return beta }
value2 = minimax(right, x0, depth - 1, alpha, beta)
if value2 < beta { return value2 }
return beta
}
function evaluate_subtree(k: i64, depth: i32, buf: ptr<i64>) -> i64 {
state_at(k, buf, buf + 1)
return minimax(buf[0], buf[1], depth, 0, MASK)
}
function block_value(start: i64, depth: i32, right_side: i32, base: i64, buf: ptr<i64>) -> i64 {
let leaf_start: i64 = base + start
if right_side == 0 {
return evaluate_subtree(leaf_start >> depth, depth, buf)
}
if depth == 0 {
state_at(leaf_start >> 1, buf, buf + 1)
return MASK - buf[0]
}
return MASK - evaluate_subtree(leaf_start >> depth, depth - 1, buf)
}
function hslot(key: i64, keys: ptr<i64>, used: ptr<i8>) -> i64 {
let mut h: i64 = key % CAP
if h < 0 { h = h + CAP }
while used[h] == 1 && keys[h] != key {
h = h + 1
if h == CAP { h = 0 }
}
return h
}
function collect_blocks(start: i64, depth: i32, left_length: i64,
bs: ptr<i64>, bd: ptr<i32>, br: ptr<i8>, bn: ptr<i64>) -> void {
let size: i64 = (1 as i64) << depth
if start + size <= left_length {
let i: i64 = bn[0]
bs[i] = start
bd[i] = depth
br[i] = 0
bn[0] = i + 1
return
}
if start >= left_length {
let i2: i64 = bn[0]
bs[i2] = start
bd[i2] = depth
br[i2] = 1
bn[0] = i2 + 1
return
}
let half: i64 = size >> 1
collect_blocks(start, depth - 1, left_length, bs, bd, br, bn)
collect_blocks(start + half, depth - 1, left_length, bs, bd, br, bn)
}
function fold(start: i64, depth: i32, keys: ptr<i64>, vals: ptr<i64>, used: ptr<i8>,
buf: ptr<i64>, base: i64) -> i64 {
let key: i64 = (start << 6) | (depth as i64)
let s: i64 = hslot(key, keys, used)
if used[s] == 1 { return vals[s] }
# If this is a leaf block we should have prefilled; otherwise recurse.
let half: i64 = (1 as i64) << (depth - 1)
let left: i64 = fold(start, depth - 1, keys, vals, used, buf, base)
let right: i64 = fold(start + half, depth - 1, keys, vals, used, buf, base)
let mut val: i64 = 0
if (depth & 1) == 1 {
if left > right { val = left } else { val = right }
} else {
if left < right { val = left } else { val = right }
}
used[s] = 1
keys[s] = key
vals[s] = val
return val
}
function A(n: i64, buf: ptr<i64>, keys: ptr<i64>, vals: ptr<i64>, used: ptr<i8>,
bs: ptr<i64>, bd: ptr<i32>, br: ptr<i8>, bn: ptr<i64>) -> i64 {
if n == 1 { return 1 }
let total_nodes: i64 = 2 * n - 1
let mut height: i32 = 0
let mut t: i64 = total_nodes
while t > 1 {
height = height + 1
t = t / 2
}
let base: i64 = (1 as i64) << height
let boundary: i64 = 2 * n
let left_length: i64 = boundary - base
bn[0] = 0
collect_blocks(0, height, left_length, bs, bd, br, bn)
# clear memo
let mut i: i64 = 0
while i < CAP {
used[i] = 0
i = i + 1
}
i = 0
while i < bn[0] {
let start: i64 = bs[i]
let depth: i32 = bd[i]
let right_side: i32 = br[i] as i32
let key: i64 = (start << 6) | (depth as i64)
let s: i64 = hslot(key, keys, used)
used[s] = 1
keys[s] = key
vals[s] = block_value(start, depth, right_side, base, buf)
i = i + 1
}
let value: i64 = fold(0, height, keys, vals, used, buf, base)
if (height & 1) == 1 {
return MASK - value
}
return value
}
function main() -> i32 {
let buf: ptr<i64> = calloc(4, 8)
let keys: ptr<i64> = calloc(CAP, 8)
let vals: ptr<i64> = calloc(CAP, 8)
let used: ptr<i8> = calloc(CAP, 1)
let bs: ptr<i64> = calloc(4096, 8)
let bd: ptr<i32> = calloc(4096, 4)
let br: ptr<i8> = calloc(4096, 1)
let bn: ptr<i64> = calloc(1, 8)
if buf == null || keys == null || vals == null || used == null
|| bs == null || bd == null || br == null || bn == null {
return 1
}
let ans: i64 = A(1000000000000, buf, keys, vals, used, bs, bd, br, bn)
printf("%lld\n", ans)
free(buf); free(keys); free(vals); free(used); free(bs); free(bd); free(br); free(bn)
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 combine_i64_i64_i64_i64(int64_t a, int64_t b, int64_t c, int64_t d);
void state_at_i64_ptr_i64_ptr_i64(int64_t k, int64_t* out_x, int64_t* out_p);
int64_t minimax_i64_i64_i32_i64_i64(int64_t x0, int64_t parent0, int32_t depth, int64_t alpha0, int64_t beta0);
int64_t evaluate_subtree_i64_i32_ptr_i64(int64_t k, int32_t depth, int64_t* buf);
int64_t block_value_i64_i32_i32_i64_ptr_i64(int64_t start, int32_t depth, int32_t right_side, int64_t base, int64_t* buf);
int64_t hslot_i64_ptr_i64_ptr_i8(int64_t key, int64_t* keys, int8_t* used);
void collect_blocks_i64_i32_i64_ptr_i64_ptr_i32_ptr_i8_ptr_i64(int64_t start, int32_t depth, int64_t left_length, int64_t* bs, int32_t* bd, int8_t* br, int64_t* bn);
int64_t fold_i64_i32_ptr_i64_ptr_i64_ptr_i8_ptr_i64_i64(int64_t start, int32_t depth, int64_t* keys, int64_t* vals, int8_t* used, int64_t* buf, int64_t base);
int64_t A_i64_ptr_i64_ptr_i64_ptr_i64_ptr_i8_ptr_i64_ptr_i32_ptr_i8_ptr_i64(int64_t n, int64_t* buf, int64_t* keys, int64_t* vals, int8_t* used, int64_t* bs, int32_t* bd, int8_t* br, int64_t* bn);
int32_t main(void);
static const int64_t MASK = 1152921504606846975;
static const int64_t CAP = 1048576;
int64_t combine_i64_i64_i64_i64(int64_t a, int64_t b, int64_t c, int64_t d) {
return (((a * b) + (c * d)) & MASK);
}
void state_at_i64_ptr_i64_ptr_i64(int64_t k, int64_t* out_x, int64_t* out_p) {
if (k == 0) {
out_x[0] = 0;
out_p[0] = 0;
return;
}
int64_t x = 1;
int64_t parent = 0;
int32_t bits = 0;
int64_t t = k;
while (t > 0) {
bits = (bits + 1);
t = FLOW_CHECKED_DIV((t), (2));
}
int32_t bit = (bits - 2);
while (bit >= 0) {
if ((FLOW_CHECKED_SHR((k), (bit)) & 1) == 1) {
int64_t next_x = combine_i64_i64_i64_i64(2, x, 3, parent);
parent = x;
x = next_x;
} else {
int64_t next_x2 = combine_i64_i64_i64_i64(3, x, 2, parent);
parent = x;
x = next_x2;
}
bit = (bit - 1);
}
out_x[0] = x;
out_p[0] = parent;
}
int64_t minimax_i64_i64_i32_i64_i64(int64_t x0, int64_t parent0, int32_t depth, int64_t alpha0, int64_t beta0) {
if (depth == 0) {
return x0;
}
int64_t left0 = combine_i64_i64_i64_i64(3, x0, 2, parent0);
int64_t right0 = combine_i64_i64_i64_i64(2, x0, 3, parent0);
int64_t left = left0;
int64_t right = right0;
int64_t alpha = alpha0;
int64_t beta = beta0;
if ((depth & 1) == 1) {
if (left < right) {
int64_t tmp = left;
left = right;
right = tmp;
}
if (depth == 1) {
return left;
}
int64_t value = minimax_i64_i64_i32_i64_i64(left, x0, (depth - 1), alpha, beta);
if (value > alpha) {
alpha = value;
}
if (alpha >= beta) {
return alpha;
}
value = minimax_i64_i64_i32_i64_i64(right, x0, (depth - 1), alpha, beta);
if (value > alpha) {
return value;
}
return alpha;
}
if (left > right) {
int64_t tmp2 = left;
left = right;
right = tmp2;
}
if (depth == 1) {
return left;
}
int64_t value2 = minimax_i64_i64_i32_i64_i64(left, x0, (depth - 1), alpha, beta);
if (value2 < beta) {
beta = value2;
}
if (alpha >= beta) {
return beta;
}
value2 = minimax_i64_i64_i32_i64_i64(right, x0, (depth - 1), alpha, beta);
if (value2 < beta) {
return value2;
}
return beta;
}
int64_t evaluate_subtree_i64_i32_ptr_i64(int64_t k, int32_t depth, int64_t* buf) {
state_at_i64_ptr_i64_ptr_i64(k, buf, (buf + 1));
return minimax_i64_i64_i32_i64_i64(buf[0], buf[1], depth, 0, MASK);
}
int64_t block_value_i64_i32_i32_i64_ptr_i64(int64_t start, int32_t depth, int32_t right_side, int64_t base, int64_t* buf) {
int64_t leaf_start = (base + start);
if (right_side == 0) {
return evaluate_subtree_i64_i32_ptr_i64(FLOW_CHECKED_SHR((leaf_start), (depth)), depth, buf);
}
if (depth == 0) {
state_at_i64_ptr_i64_ptr_i64(FLOW_CHECKED_SHR((leaf_start), (1)), buf, (buf + 1));
return (MASK - buf[0]);
}
return (MASK - evaluate_subtree_i64_i32_ptr_i64(FLOW_CHECKED_SHR((leaf_start), (depth)), (depth - 1), buf));
}
int64_t hslot_i64_ptr_i64_ptr_i8(int64_t key, int64_t* keys, int8_t* used) {
int64_t h = FLOW_CHECKED_MOD((key), (CAP));
if (h < 0) {
h = (h + CAP);
}
while ((used[h] == 1 && keys[h] != key)) {
h = (h + 1);
if (h == CAP) {
h = 0;
}
}
return h;
}
void collect_blocks_i64_i32_i64_ptr_i64_ptr_i32_ptr_i8_ptr_i64(int64_t start, int32_t depth, int64_t left_length, int64_t* bs, int32_t* bd, int8_t* br, int64_t* bn) {
int64_t size = FLOW_CHECKED_SHL((((int64_t)(1))), (depth));
if ((start + size) <= left_length) {
int64_t i = bn[0];
bs[i] = start;
bd[i] = depth;
br[i] = 0;
bn[0] = (i + 1);
return;
}
if (start >= left_length) {
int64_t i2 = bn[0];
bs[i2] = start;
bd[i2] = depth;
br[i2] = 1;
bn[0] = (i2 + 1);
return;
}
int64_t half = FLOW_CHECKED_SHR((size), (1));
collect_blocks_i64_i32_i64_ptr_i64_ptr_i32_ptr_i8_ptr_i64(start, (depth - 1), left_length, bs, bd, br, bn);
collect_blocks_i64_i32_i64_ptr_i64_ptr_i32_ptr_i8_ptr_i64((start + half), (depth - 1), left_length, bs, bd, br, bn);
}
int64_t fold_i64_i32_ptr_i64_ptr_i64_ptr_i8_ptr_i64_i64(int64_t start, int32_t depth, int64_t* keys, int64_t* vals, int8_t* used, int64_t* buf, int64_t base) {
int64_t key = (FLOW_CHECKED_SHL((start), (6)) | ((int64_t)(depth)));
int64_t s = hslot_i64_ptr_i64_ptr_i8(key, keys, used);
if (used[s] == 1) {
return vals[s];
}
int64_t half = FLOW_CHECKED_SHL((((int64_t)(1))), ((depth - 1)));
int64_t left = fold_i64_i32_ptr_i64_ptr_i64_ptr_i8_ptr_i64_i64(start, (depth - 1), keys, vals, used, buf, base);
int64_t right = fold_i64_i32_ptr_i64_ptr_i64_ptr_i8_ptr_i64_i64((start + half), (depth - 1), keys, vals, used, buf, base);
int64_t val = 0;
if ((depth & 1) == 1) {
if (left > right) {
val = left;
} else {
val = right;
}
} else {
if (left < right) {
val = left;
} else {
val = right;
}
}
used[s] = 1;
keys[s] = key;
vals[s] = val;
return val;
}
int64_t A_i64_ptr_i64_ptr_i64_ptr_i64_ptr_i8_ptr_i64_ptr_i32_ptr_i8_ptr_i64(int64_t n, int64_t* buf, int64_t* keys, int64_t* vals, int8_t* used, int64_t* bs, int32_t* bd, int8_t* br, int64_t* bn) {
if (n == 1) {
return 1;
}
int64_t total_nodes = ((2 * n) - 1);
int32_t height = 0;
int64_t t = total_nodes;
while (t > 1) {
height = (height + 1);
t = FLOW_CHECKED_DIV((t), (2));
}
int64_t base = FLOW_CHECKED_SHL((((int64_t)(1))), (height));
int64_t boundary = (2 * n);
int64_t left_length = (boundary - base);
bn[0] = 0;
collect_blocks_i64_i32_i64_ptr_i64_ptr_i32_ptr_i8_ptr_i64(0, height, left_length, bs, bd, br, bn);
int64_t i = 0;
while (i < CAP) {
used[i] = 0;
i = (i + 1);
}
i = 0;
while (i < bn[0]) {
int64_t start = bs[i];
int32_t depth = bd[i];
int32_t right_side = ((int32_t)(br[i]));
int64_t key = (FLOW_CHECKED_SHL((start), (6)) | ((int64_t)(depth)));
int64_t s = hslot_i64_ptr_i64_ptr_i8(key, keys, used);
used[s] = 1;
keys[s] = key;
vals[s] = block_value_i64_i32_i32_i64_ptr_i64(start, depth, right_side, base, buf);
i = (i + 1);
}
int64_t value = fold_i64_i32_ptr_i64_ptr_i64_ptr_i8_ptr_i64_i64(0, height, keys, vals, used, buf, base);
if ((height & 1) == 1) {
return (MASK - value);
}
return value;
}
int32_t main(void) {
int64_t* buf = (int64_t*)(calloc(4, 8));
int64_t* keys = (int64_t*)(calloc(CAP, 8));
int64_t* vals = (int64_t*)(calloc(CAP, 8));
int8_t* used = (int8_t*)(calloc(CAP, 1));
int64_t* bs = (int64_t*)(calloc(4096, 8));
int32_t* bd = (int32_t*)(calloc(4096, 4));
int8_t* br = (int8_t*)(calloc(4096, 1));
int64_t* bn = (int64_t*)(calloc(1, 8));
if ((((((((buf == NULL || keys == NULL) || vals == NULL) || used == NULL) || bs == NULL) || bd == NULL) || br == NULL) || bn == NULL)) {
return 1;
}
int64_t ans = A_i64_ptr_i64_ptr_i64_ptr_i64_ptr_i8_ptr_i64_ptr_i32_ptr_i8_ptr_i64(1000000000000, buf, keys, vals, used, bs, bd, br, bn);
printf("%lld\n", ans);
free(buf);
free(keys);
free(vals);
free(used);
free(bs);
free(bd);
free(br);
free(bn);
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) -> ()
// Constant: MASK
llvm.mlir.global internal constant @MASK(1152921504606846975 : i64) : i64
// Constant: CAP
llvm.mlir.global internal constant @CAP(1048576 : i64) : i64
func.func @combine(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> i64 {
%0 = arith.muli %arg0, %arg1 : i64
%1 = arith.muli %arg2, %arg3 : i64
%2 = arith.addi %0, %1 : i64
%3 = llvm.mlir.addressof @MASK : !llvm.ptr
%4 = llvm.load %3 : !llvm.ptr -> i64
%5 = arith.andi %2, %4 : i64
func.return %5 : i64
}
func.func @state_at(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%6 = arith.constant 0 : i32
%8 = arith.extsi %6 : i32 to i64
%7 = arith.cmpi eq, %arg0, %8 : i64
cf.cond_br %7, ^bb0, ^bb1
^bb0:
%9 = arith.constant 0 : i32
%10 = arith.constant 0 : i32
%11 = arith.extsi %9 : i32 to i64
%12 = arith.extsi %10 : i32 to i64
%13 = llvm.getelementptr %arg1[%12] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %11, %13 : i64, !llvm.ptr
%14 = arith.constant 0 : i32
%15 = arith.constant 0 : i32
%16 = arith.extsi %14 : i32 to i64
%17 = arith.extsi %15 : i32 to i64
%18 = llvm.getelementptr %arg2[%17] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %16, %18 : i64, !llvm.ptr
func.return
^bb1:
cf.br ^bb2
^bb2:
%19 = arith.constant 1 : i32
%20 = arith.extsi %19 : i32 to i64
%21 = llvm.mlir.constant(1 : i64) : i64
%22 = llvm.alloca %21 x i64 : (i64) -> !llvm.ptr
llvm.store %20, %22 : i64, !llvm.ptr
%23 = arith.constant 0 : i32
%24 = arith.extsi %23 : i32 to i64
%25 = llvm.mlir.constant(1 : i64) : i64
%26 = llvm.alloca %25 x i64 : (i64) -> !llvm.ptr
llvm.store %24, %26 : i64, !llvm.ptr
%27 = arith.constant 0 : i32
%28 = llvm.mlir.constant(1 : i64) : i64
%29 = llvm.alloca %28 x i32 : (i64) -> !llvm.ptr
llvm.store %27, %29 : i32, !llvm.ptr
%30 = llvm.mlir.constant(1 : i64) : i64
%31 = llvm.alloca %30 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %31 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%32 = llvm.load %31 : !llvm.ptr -> i64
%33 = arith.constant 0 : i32
%35 = arith.extsi %33 : i32 to i64
%34 = arith.cmpi sgt, %32, %35 : i64
cf.cond_br %34, ^bb4, ^bb5
^bb4:
%36 = llvm.load %29 : !llvm.ptr -> i32
%37 = arith.constant 1 : i32
%38 = arith.addi %36, %37 : i32
llvm.store %38, %29 : i32, !llvm.ptr
%39 = llvm.load %31 : !llvm.ptr -> i64
%40 = arith.constant 2 : i32
%42 = arith.extsi %40 : i32 to i64
%41 = arith.divsi %39, %42 : i64
llvm.store %41, %31 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%43 = llvm.load %29 : !llvm.ptr -> i32
%44 = arith.constant 2 : i32
%45 = arith.subi %43, %44 : i32
%46 = llvm.mlir.constant(1 : i64) : i64
%47 = llvm.alloca %46 x i32 : (i64) -> !llvm.ptr
llvm.store %45, %47 : i32, !llvm.ptr
cf.br ^bb6
^bb6:
%48 = llvm.load %47 : !llvm.ptr -> i32
%49 = arith.constant 0 : i32
%50 = arith.cmpi sge, %48, %49 : i32
cf.cond_br %50, ^bb7, ^bb8
^bb7:
%51 = llvm.load %47 : !llvm.ptr -> i32
%53 = arith.extsi %51 : i32 to i64
%52 = arith.shrsi %arg0, %53 : i64
%54 = arith.constant 1 : i32
%56 = arith.extsi %54 : i32 to i64
%55 = arith.andi %52, %56 : i64
%57 = arith.constant 1 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.cmpi eq, %55, %59 : i64
cf.cond_br %58, ^bb9, ^bb10
^bb9:
%61 = arith.constant 2 : i32
%62 = llvm.load %22 : !llvm.ptr -> i64
%63 = arith.constant 3 : i32
%64 = llvm.load %26 : !llvm.ptr -> i64
%65 = arith.extsi %61 : i32 to i64
%66 = arith.extsi %63 : i32 to i64
%60 = func.call @combine(%65, %62, %66, %64) : (i64, i64, i64, i64) -> i64
%67 = llvm.load %22 : !llvm.ptr -> i64
llvm.store %67, %26 : i64, !llvm.ptr
llvm.store %60, %22 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
%69 = arith.constant 3 : i32
%70 = llvm.load %22 : !llvm.ptr -> i64
%71 = arith.constant 2 : i32
%72 = llvm.load %26 : !llvm.ptr -> i64
%73 = arith.extsi %69 : i32 to i64
%74 = arith.extsi %71 : i32 to i64
%68 = func.call @combine(%73, %70, %74, %72) : (i64, i64, i64, i64) -> i64
%75 = llvm.load %22 : !llvm.ptr -> i64
llvm.store %75, %26 : i64, !llvm.ptr
llvm.store %68, %22 : i64, !llvm.ptr
cf.br ^bb11
^bb11:
%76 = llvm.load %47 : !llvm.ptr -> i32
%77 = arith.constant 1 : i32
%78 = arith.subi %76, %77 : i32
llvm.store %78, %47 : i32, !llvm.ptr
cf.br ^bb6
^bb8:
%79 = llvm.load %22 : !llvm.ptr -> i64
%80 = arith.constant 0 : i32
%81 = arith.extsi %80 : i32 to i64
%82 = llvm.getelementptr %arg1[%81] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %79, %82 : i64, !llvm.ptr
%83 = llvm.load %26 : !llvm.ptr -> i64
%84 = arith.constant 0 : i32
%85 = arith.extsi %84 : i32 to i64
%86 = llvm.getelementptr %arg2[%85] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %83, %86 : i64, !llvm.ptr
func.return
}
func.func @minimax(%arg0: i64, %arg1: i64, %arg2: i32, %arg3: i64, %arg4: i64) -> i64 {
%87 = arith.constant 0 : i32
%88 = arith.cmpi eq, %arg2, %87 : i32
cf.cond_br %88, ^bb12, ^bb13
^bb12:
func.return %arg0 : i64
^bb13:
cf.br ^bb14
^bb14:
%90 = arith.constant 3 : i32
%91 = arith.constant 2 : i32
%92 = arith.extsi %90 : i32 to i64
%93 = arith.extsi %91 : i32 to i64
%89 = func.call @combine(%92, %arg0, %93, %arg1) : (i64, i64, i64, i64) -> i64
%95 = arith.constant 2 : i32
%96 = arith.constant 3 : i32
%97 = arith.extsi %95 : i32 to i64
%98 = arith.extsi %96 : i32 to i64
%94 = func.call @combine(%97, %arg0, %98, %arg1) : (i64, i64, i64, i64) -> i64
%99 = llvm.mlir.constant(1 : i64) : i64
%100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
llvm.store %89, %100 : i64, !llvm.ptr
%101 = llvm.mlir.constant(1 : i64) : i64
%102 = llvm.alloca %101 x i64 : (i64) -> !llvm.ptr
llvm.store %94, %102 : i64, !llvm.ptr
%103 = llvm.mlir.constant(1 : i64) : i64
%104 = llvm.alloca %103 x i64 : (i64) -> !llvm.ptr
llvm.store %arg3, %104 : i64, !llvm.ptr
%105 = llvm.mlir.constant(1 : i64) : i64
%106 = llvm.alloca %105 x i64 : (i64) -> !llvm.ptr
llvm.store %arg4, %106 : i64, !llvm.ptr
%107 = arith.constant 1 : i32
%108 = arith.andi %arg2, %107 : i32
%109 = arith.constant 1 : i32
%110 = arith.cmpi eq, %108, %109 : i32
cf.cond_br %110, ^bb15, ^bb16
^bb15:
%111 = llvm.load %100 : !llvm.ptr -> i64
%112 = llvm.load %102 : !llvm.ptr -> i64
%113 = arith.cmpi slt, %111, %112 : i64
cf.cond_br %113, ^bb18, ^bb19
^bb18:
%114 = llvm.load %100 : !llvm.ptr -> i64
%115 = llvm.load %102 : !llvm.ptr -> i64
llvm.store %115, %100 : i64, !llvm.ptr
llvm.store %114, %102 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%116 = arith.constant 1 : i32
%117 = arith.cmpi eq, %arg2, %116 : i32
cf.cond_br %117, ^bb21, ^bb22
^bb21:
%118 = llvm.load %100 : !llvm.ptr -> i64
func.return %118 : i64
^bb22:
cf.br ^bb23
^bb23:
%120 = llvm.load %100 : !llvm.ptr -> i64
%121 = arith.constant 1 : i32
%122 = arith.subi %arg2, %121 : i32
%123 = llvm.load %104 : !llvm.ptr -> i64
%124 = llvm.load %106 : !llvm.ptr -> i64
%119 = func.call @minimax(%120, %arg0, %122, %123, %124) : (i64, i64, i32, i64, i64) -> i64
%125 = llvm.mlir.constant(1 : i64) : i64
%126 = llvm.alloca %125 x i64 : (i64) -> !llvm.ptr
llvm.store %119, %126 : i64, !llvm.ptr
%127 = llvm.load %126 : !llvm.ptr -> i64
%128 = llvm.load %104 : !llvm.ptr -> i64
%129 = arith.cmpi sgt, %127, %128 : i64
cf.cond_br %129, ^bb24, ^bb25
^bb24:
%130 = llvm.load %126 : !llvm.ptr -> i64
llvm.store %130, %104 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%131 = llvm.load %104 : !llvm.ptr -> i64
%132 = llvm.load %106 : !llvm.ptr -> i64
%133 = arith.cmpi sge, %131, %132 : i64
cf.cond_br %133, ^bb27, ^bb28
^bb27:
%134 = llvm.load %104 : !llvm.ptr -> i64
func.return %134 : i64
^bb28:
cf.br ^bb29
^bb29:
%136 = llvm.load %102 : !llvm.ptr -> i64
%137 = arith.constant 1 : i32
%138 = arith.subi %arg2, %137 : i32
%139 = llvm.load %104 : !llvm.ptr -> i64
%140 = llvm.load %106 : !llvm.ptr -> i64
%135 = func.call @minimax(%136, %arg0, %138, %139, %140) : (i64, i64, i32, i64, i64) -> i64
llvm.store %135, %126 : i64, !llvm.ptr
%141 = llvm.load %126 : !llvm.ptr -> i64
%142 = llvm.load %104 : !llvm.ptr -> i64
%143 = arith.cmpi sgt, %141, %142 : i64
cf.cond_br %143, ^bb30, ^bb31
^bb30:
%144 = llvm.load %126 : !llvm.ptr -> i64
func.return %144 : i64
^bb31:
cf.br ^bb32
^bb32:
%145 = llvm.load %104 : !llvm.ptr -> i64
func.return %145 : i64
^bb16:
cf.br ^bb17
^bb17:
%146 = llvm.load %100 : !llvm.ptr -> i64
%147 = llvm.load %102 : !llvm.ptr -> i64
%148 = arith.cmpi sgt, %146, %147 : i64
cf.cond_br %148, ^bb33, ^bb34
^bb33:
%149 = llvm.load %100 : !llvm.ptr -> i64
%150 = llvm.load %102 : !llvm.ptr -> i64
llvm.store %150, %100 : i64, !llvm.ptr
llvm.store %149, %102 : i64, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%151 = arith.constant 1 : i32
%152 = arith.cmpi eq, %arg2, %151 : i32
cf.cond_br %152, ^bb36, ^bb37
^bb36:
%153 = llvm.load %100 : !llvm.ptr -> i64
func.return %153 : i64
^bb37:
cf.br ^bb38
^bb38:
%155 = llvm.load %100 : !llvm.ptr -> i64
%156 = arith.constant 1 : i32
%157 = arith.subi %arg2, %156 : i32
%158 = llvm.load %104 : !llvm.ptr -> i64
%159 = llvm.load %106 : !llvm.ptr -> i64
%154 = func.call @minimax(%155, %arg0, %157, %158, %159) : (i64, i64, i32, i64, i64) -> i64
%160 = llvm.mlir.constant(1 : i64) : i64
%161 = llvm.alloca %160 x i64 : (i64) -> !llvm.ptr
llvm.store %154, %161 : i64, !llvm.ptr
%162 = llvm.load %161 : !llvm.ptr -> i64
%163 = llvm.load %106 : !llvm.ptr -> i64
%164 = arith.cmpi slt, %162, %163 : i64
cf.cond_br %164, ^bb39, ^bb40
^bb39:
%165 = llvm.load %161 : !llvm.ptr -> i64
llvm.store %165, %106 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%166 = llvm.load %104 : !llvm.ptr -> i64
%167 = llvm.load %106 : !llvm.ptr -> i64
%168 = arith.cmpi sge, %166, %167 : i64
cf.cond_br %168, ^bb42, ^bb43
^bb42:
%169 = llvm.load %106 : !llvm.ptr -> i64
func.return %169 : i64
^bb43:
cf.br ^bb44
^bb44:
%171 = llvm.load %102 : !llvm.ptr -> i64
%172 = arith.constant 1 : i32
%173 = arith.subi %arg2, %172 : i32
%174 = llvm.load %104 : !llvm.ptr -> i64
%175 = llvm.load %106 : !llvm.ptr -> i64
%170 = func.call @minimax(%171, %arg0, %173, %174, %175) : (i64, i64, i32, i64, i64) -> i64
llvm.store %170, %161 : i64, !llvm.ptr
%176 = llvm.load %161 : !llvm.ptr -> i64
%177 = llvm.load %106 : !llvm.ptr -> i64
%178 = arith.cmpi slt, %176, %177 : i64
cf.cond_br %178, ^bb45, ^bb46
^bb45:
%179 = llvm.load %161 : !llvm.ptr -> i64
func.return %179 : i64
^bb46:
cf.br ^bb47
^bb47:
%180 = llvm.load %106 : !llvm.ptr -> i64
func.return %180 : i64
}
func.func @evaluate_subtree(%arg0: i64, %arg1: i32, %arg2: !llvm.ptr) -> i64 {
# String concatenation: !llvm.ptr + i32
func.call @state_at(%arg0, %arg2, %182) : (i64, !llvm.ptr, !llvm.ptr) -> ()
%185 = arith.constant 0 : i32
%186 = arith.extsi %185 : i32 to i64
%187 = llvm.getelementptr %arg2[%186] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%184 = llvm.load %187 : !llvm.ptr -> i64
%189 = arith.constant 1 : i32
%190 = arith.extsi %189 : i32 to i64
%191 = llvm.getelementptr %arg2[%190] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%188 = llvm.load %191 : !llvm.ptr -> i64
%192 = arith.constant 0 : i32
%193 = llvm.mlir.addressof @MASK : !llvm.ptr
%194 = llvm.load %193 : !llvm.ptr -> i64
%195 = arith.extsi %192 : i32 to i64
%183 = func.call @minimax(%184, %188, %arg1, %195, %194) : (i64, i64, i32, i64, i64) -> i64
func.return %183 : i64
}
func.func @block_value(%arg0: i64, %arg1: i32, %arg2: i32, %arg3: i64, %arg4: !llvm.ptr) -> i64 {
%196 = arith.addi %arg3, %arg0 : i64
%197 = arith.constant 0 : i32
%198 = arith.cmpi eq, %arg2, %197 : i32
cf.cond_br %198, ^bb48, ^bb49
^bb48:
%201 = arith.extsi %arg1 : i32 to i64
%200 = arith.shrsi %196, %201 : i64
%199 = func.call @evaluate_subtree(%200, %arg1, %arg4) : (i64, i32, !llvm.ptr) -> i64
func.return %199 : i64
^bb49:
cf.br ^bb50
^bb50:
%202 = arith.constant 0 : i32
%203 = arith.cmpi eq, %arg1, %202 : i32
cf.cond_br %203, ^bb51, ^bb52
^bb51:
%205 = arith.constant 1 : i32
%207 = arith.extsi %205 : i32 to i64
%206 = arith.shrsi %196, %207 : i64
# String concatenation: !llvm.ptr + i32
func.call @state_at(%206, %arg4, %208) : (i64, !llvm.ptr, !llvm.ptr) -> ()
%209 = llvm.mlir.addressof @MASK : !llvm.ptr
%210 = llvm.load %209 : !llvm.ptr -> i64
%212 = arith.constant 0 : i32
%213 = arith.extsi %212 : i32 to i64
%214 = llvm.getelementptr %arg4[%213] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%211 = llvm.load %214 : !llvm.ptr -> i64
%215 = arith.subi %210, %211 : i64
func.return %215 : i64
^bb52:
cf.br ^bb53
^bb53:
%216 = llvm.mlir.addressof @MASK : !llvm.ptr
%217 = llvm.load %216 : !llvm.ptr -> i64
%220 = arith.extsi %arg1 : i32 to i64
%219 = arith.shrsi %196, %220 : i64
%221 = arith.constant 1 : i32
%222 = arith.subi %arg1, %221 : i32
%218 = func.call @evaluate_subtree(%219, %222, %arg4) : (i64, i32, !llvm.ptr) -> i64
%223 = arith.subi %217, %218 : i64
func.return %223 : i64
}
func.func @hslot(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> i64 {
%224 = llvm.mlir.addressof @CAP : !llvm.ptr
%225 = llvm.load %224 : !llvm.ptr -> i64
%226 = arith.remsi %arg0, %225 : i64
%227 = llvm.mlir.constant(1 : i64) : i64
%228 = llvm.alloca %227 x i64 : (i64) -> !llvm.ptr
llvm.store %226, %228 : i64, !llvm.ptr
%229 = llvm.load %228 : !llvm.ptr -> i64
%230 = arith.constant 0 : i32
%232 = arith.extsi %230 : i32 to i64
%231 = arith.cmpi slt, %229, %232 : i64
cf.cond_br %231, ^bb54, ^bb55
^bb54:
%233 = llvm.load %228 : !llvm.ptr -> i64
%234 = llvm.mlir.addressof @CAP : !llvm.ptr
%235 = llvm.load %234 : !llvm.ptr -> i64
%236 = arith.addi %233, %235 : i64
llvm.store %236, %228 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
cf.br ^bb57
^bb57:
%238 = llvm.load %228 : !llvm.ptr -> i64
%239 = llvm.getelementptr %arg2[%238] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%237 = llvm.load %239 : !llvm.ptr -> i8
%240 = arith.constant 1 : i32
%242 = arith.extsi %237 : i8 to i32
%241 = arith.cmpi eq, %242, %240 : i32
%243 = scf.if %241 -> (i1) {
%245 = llvm.load %228 : !llvm.ptr -> i64
%246 = llvm.getelementptr %arg1[%245] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%244 = llvm.load %246 : !llvm.ptr -> i64
%247 = arith.cmpi ne, %244, %arg0 : i64
scf.yield %247 : i1
} else {
%248 = arith.constant false
scf.yield %248 : i1
}
cf.cond_br %243, ^bb58, ^bb59
^bb58:
%249 = llvm.load %228 : !llvm.ptr -> i64
%250 = arith.constant 1 : i32
%252 = arith.extsi %250 : i32 to i64
%251 = arith.addi %249, %252 : i64
llvm.store %251, %228 : i64, !llvm.ptr
%253 = llvm.load %228 : !llvm.ptr -> i64
%254 = llvm.mlir.addressof @CAP : !llvm.ptr
%255 = llvm.load %254 : !llvm.ptr -> i64
%256 = arith.cmpi eq, %253, %255 : i64
cf.cond_br %256, ^bb60, ^bb61
^bb60:
%257 = arith.constant 0 : i32
%258 = arith.extsi %257 : i32 to i64
llvm.store %258, %228 : i64, !llvm.ptr
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
cf.br ^bb57
^bb59:
%259 = llvm.load %228 : !llvm.ptr -> i64
func.return %259 : i64
}
func.func @collect_blocks(%arg0: i64, %arg1: i32, %arg2: i64, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: !llvm.ptr) -> () {
%260 = arith.constant 1 : i32
%261 = arith.extsi %260 : i32 to i64
%263 = arith.extsi %arg1 : i32 to i64
%262 = arith.shli %261, %263 : i64
%264 = arith.addi %arg0, %262 : i64
%265 = arith.cmpi sle, %264, %arg2 : i64
cf.cond_br %265, ^bb63, ^bb64
^bb63:
%267 = arith.constant 0 : i32
%268 = arith.extsi %267 : i32 to i64
%269 = llvm.getelementptr %arg6[%268] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%266 = llvm.load %269 : !llvm.ptr -> i64
%270 = llvm.getelementptr %arg3[%266] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %270 : i64, !llvm.ptr
%271 = llvm.getelementptr %arg4[%266] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %arg1, %271 : i32, !llvm.ptr
%272 = arith.constant 0 : i32
%273 = arith.trunci %272 : i32 to i8
%274 = llvm.getelementptr %arg5[%266] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %273, %274 : i8, !llvm.ptr
%275 = arith.constant 1 : i32
%277 = arith.extsi %275 : i32 to i64
%276 = arith.addi %266, %277 : i64
%278 = arith.constant 0 : i32
%279 = arith.extsi %278 : i32 to i64
%280 = llvm.getelementptr %arg6[%279] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %276, %280 : i64, !llvm.ptr
func.return
^bb64:
cf.br ^bb65
^bb65:
%281 = arith.cmpi sge, %arg0, %arg2 : i64
cf.cond_br %281, ^bb66, ^bb67
^bb66:
%283 = arith.constant 0 : i32
%284 = arith.extsi %283 : i32 to i64
%285 = llvm.getelementptr %arg6[%284] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%282 = llvm.load %285 : !llvm.ptr -> i64
%286 = llvm.getelementptr %arg3[%282] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %286 : i64, !llvm.ptr
%287 = llvm.getelementptr %arg4[%282] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %arg1, %287 : i32, !llvm.ptr
%288 = arith.constant 1 : i32
%289 = arith.trunci %288 : i32 to i8
%290 = llvm.getelementptr %arg5[%282] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %289, %290 : i8, !llvm.ptr
%291 = arith.constant 1 : i32
%293 = arith.extsi %291 : i32 to i64
%292 = arith.addi %282, %293 : i64
%294 = arith.constant 0 : i32
%295 = arith.extsi %294 : i32 to i64
%296 = llvm.getelementptr %arg6[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %292, %296 : i64, !llvm.ptr
func.return
^bb67:
cf.br ^bb68
^bb68:
%297 = arith.constant 1 : i32
%299 = arith.extsi %297 : i32 to i64
%298 = arith.shrsi %262, %299 : i64
%301 = arith.constant 1 : i32
%302 = arith.subi %arg1, %301 : i32
func.call @collect_blocks(%arg0, %302, %arg2, %arg3, %arg4, %arg5, %arg6) : (i64, i32, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%304 = arith.addi %arg0, %298 : i64
%305 = arith.constant 1 : i32
%306 = arith.subi %arg1, %305 : i32
func.call @collect_blocks(%304, %306, %arg2, %arg3, %arg4, %arg5, %arg6) : (i64, i32, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.return
}
func.func @fold(%arg0: i64, %arg1: i32, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: i64) -> i64 {
%307 = arith.constant 6 : i32
%309 = arith.extsi %307 : i32 to i64
%308 = arith.shli %arg0, %309 : i64
%310 = arith.extsi %arg1 : i32 to i64
%311 = arith.ori %308, %310 : i64
%312 = func.call @hslot(%311, %arg2, %arg4) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%314 = llvm.getelementptr %arg4[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%313 = llvm.load %314 : !llvm.ptr -> i8
%315 = arith.constant 1 : i32
%317 = arith.extsi %313 : i8 to i32
%316 = arith.cmpi eq, %317, %315 : i32
cf.cond_br %316, ^bb69, ^bb70
^bb69:
%319 = llvm.getelementptr %arg3[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%318 = llvm.load %319 : !llvm.ptr -> i64
func.return %318 : i64
^bb70:
cf.br ^bb71
^bb71:
%320 = arith.constant 1 : i32
%321 = arith.extsi %320 : i32 to i64
%322 = arith.constant 1 : i32
%323 = arith.subi %arg1, %322 : i32
%325 = arith.extsi %323 : i32 to i64
%324 = arith.shli %321, %325 : i64
%327 = arith.constant 1 : i32
%328 = arith.subi %arg1, %327 : i32
%326 = func.call @fold(%arg0, %328, %arg2, %arg3, %arg4, %arg5, %arg6) : (i64, i32, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> i64
%330 = arith.addi %arg0, %324 : i64
%331 = arith.constant 1 : i32
%332 = arith.subi %arg1, %331 : i32
%329 = func.call @fold(%330, %332, %arg2, %arg3, %arg4, %arg5, %arg6) : (i64, i32, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> i64
%333 = arith.constant 0 : i32
%334 = arith.extsi %333 : i32 to i64
%335 = llvm.mlir.constant(1 : i64) : i64
%336 = llvm.alloca %335 x i64 : (i64) -> !llvm.ptr
llvm.store %334, %336 : i64, !llvm.ptr
%337 = arith.constant 1 : i32
%338 = arith.andi %arg1, %337 : i32
%339 = arith.constant 1 : i32
%340 = arith.cmpi eq, %338, %339 : i32
cf.cond_br %340, ^bb72, ^bb73
^bb72:
%341 = arith.cmpi sgt, %326, %329 : i64
cf.cond_br %341, ^bb75, ^bb76
^bb75:
llvm.store %326, %336 : i64, !llvm.ptr
cf.br ^bb77
^bb76:
llvm.store %329, %336 : i64, !llvm.ptr
cf.br ^bb77
^bb77:
cf.br ^bb74
^bb73:
%342 = arith.cmpi slt, %326, %329 : i64
cf.cond_br %342, ^bb78, ^bb79
^bb78:
llvm.store %326, %336 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
llvm.store %329, %336 : i64, !llvm.ptr
cf.br ^bb80
^bb80:
cf.br ^bb74
^bb74:
%343 = arith.constant 1 : i32
%344 = arith.trunci %343 : i32 to i8
%345 = llvm.getelementptr %arg4[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %344, %345 : i8, !llvm.ptr
%346 = llvm.getelementptr %arg2[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %311, %346 : i64, !llvm.ptr
%347 = llvm.load %336 : !llvm.ptr -> i64
%348 = llvm.getelementptr %arg3[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %347, %348 : i64, !llvm.ptr
%349 = llvm.load %336 : !llvm.ptr -> i64
func.return %349 : i64
}
func.func @A(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: !llvm.ptr) -> i64 {
%350 = arith.constant 1 : i32
%352 = arith.extsi %350 : i32 to i64
%351 = arith.cmpi eq, %arg0, %352 : i64
cf.cond_br %351, ^bb81, ^bb82
^bb81:
%353 = arith.constant 1 : i32
%354 = arith.extsi %353 : i32 to i64
func.return %354 : i64
^bb82:
cf.br ^bb83
^bb83:
%355 = arith.constant 2 : i32
%357 = arith.extsi %355 : i32 to i64
%356 = arith.muli %357, %arg0 : i64
%358 = arith.constant 1 : i32
%360 = arith.extsi %358 : i32 to i64
%359 = arith.subi %356, %360 : i64
%361 = arith.constant 0 : i32
%362 = llvm.mlir.constant(1 : i64) : i64
%363 = llvm.alloca %362 x i32 : (i64) -> !llvm.ptr
llvm.store %361, %363 : i32, !llvm.ptr
%364 = llvm.mlir.constant(1 : i64) : i64
%365 = llvm.alloca %364 x i64 : (i64) -> !llvm.ptr
llvm.store %359, %365 : i64, !llvm.ptr
cf.br ^bb84
^bb84:
%366 = llvm.load %365 : !llvm.ptr -> i64
%367 = arith.constant 1 : i32
%369 = arith.extsi %367 : i32 to i64
%368 = arith.cmpi sgt, %366, %369 : i64
cf.cond_br %368, ^bb85, ^bb86
^bb85:
%370 = llvm.load %363 : !llvm.ptr -> i32
%371 = arith.constant 1 : i32
%372 = arith.addi %370, %371 : i32
llvm.store %372, %363 : i32, !llvm.ptr
%373 = llvm.load %365 : !llvm.ptr -> i64
%374 = arith.constant 2 : i32
%376 = arith.extsi %374 : i32 to i64
%375 = arith.divsi %373, %376 : i64
llvm.store %375, %365 : i64, !llvm.ptr
cf.br ^bb84
^bb86:
%377 = arith.constant 1 : i32
%378 = arith.extsi %377 : i32 to i64
%379 = llvm.load %363 : !llvm.ptr -> i32
%381 = arith.extsi %379 : i32 to i64
%380 = arith.shli %378, %381 : i64
%382 = arith.constant 2 : i32
%384 = arith.extsi %382 : i32 to i64
%383 = arith.muli %384, %arg0 : i64
%385 = arith.subi %383, %380 : i64
%386 = arith.constant 0 : i32
%387 = arith.constant 0 : i32
%388 = arith.extsi %386 : i32 to i64
%389 = arith.extsi %387 : i32 to i64
%390 = llvm.getelementptr %arg8[%389] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %388, %390 : i64, !llvm.ptr
%392 = arith.constant 0 : i32
%393 = llvm.load %363 : !llvm.ptr -> i32
%394 = arith.extsi %392 : i32 to i64
func.call @collect_blocks(%394, %393, %385, %arg5, %arg6, %arg7, %arg8) : (i64, i32, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%395 = arith.constant 0 : i32
%396 = arith.extsi %395 : i32 to i64
%397 = llvm.mlir.constant(1 : i64) : i64
%398 = llvm.alloca %397 x i64 : (i64) -> !llvm.ptr
llvm.store %396, %398 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%399 = llvm.load %398 : !llvm.ptr -> i64
%400 = llvm.mlir.addressof @CAP : !llvm.ptr
%401 = llvm.load %400 : !llvm.ptr -> i64
%402 = arith.cmpi slt, %399, %401 : i64
cf.cond_br %402, ^bb88, ^bb89
^bb88:
%403 = arith.constant 0 : i32
%404 = llvm.load %398 : !llvm.ptr -> i64
%405 = arith.trunci %403 : i32 to i8
%406 = llvm.getelementptr %arg4[%404] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %405, %406 : i8, !llvm.ptr
%407 = llvm.load %398 : !llvm.ptr -> i64
%408 = arith.constant 1 : i32
%410 = arith.extsi %408 : i32 to i64
%409 = arith.addi %407, %410 : i64
llvm.store %409, %398 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%411 = arith.constant 0 : i32
%412 = arith.extsi %411 : i32 to i64
llvm.store %412, %398 : i64, !llvm.ptr
cf.br ^bb90
^bb90:
%413 = llvm.load %398 : !llvm.ptr -> i64
%415 = arith.constant 0 : i32
%416 = arith.extsi %415 : i32 to i64
%417 = llvm.getelementptr %arg8[%416] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%414 = llvm.load %417 : !llvm.ptr -> i64
%418 = arith.cmpi slt, %413, %414 : i64
cf.cond_br %418, ^bb91, ^bb92
^bb91:
%420 = llvm.load %398 : !llvm.ptr -> i64
%421 = llvm.getelementptr %arg5[%420] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%419 = llvm.load %421 : !llvm.ptr -> i64
%423 = llvm.load %398 : !llvm.ptr -> i64
%424 = llvm.getelementptr %arg6[%423] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%422 = llvm.load %424 : !llvm.ptr -> i32
%426 = llvm.load %398 : !llvm.ptr -> i64
%427 = llvm.getelementptr %arg7[%426] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%425 = llvm.load %427 : !llvm.ptr -> i8
%428 = arith.extsi %425 : i8 to i32
%429 = arith.constant 6 : i32
%431 = arith.extsi %429 : i32 to i64
%430 = arith.shli %419, %431 : i64
%432 = arith.extsi %422 : i32 to i64
%433 = arith.ori %430, %432 : i64
%434 = func.call @hslot(%433, %arg2, %arg4) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%435 = arith.constant 1 : i32
%436 = arith.trunci %435 : i32 to i8
%437 = llvm.getelementptr %arg4[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %436, %437 : i8, !llvm.ptr
%438 = llvm.getelementptr %arg2[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %433, %438 : i64, !llvm.ptr
%439 = func.call @block_value(%419, %422, %428, %380, %arg1) : (i64, i32, i32, i64, !llvm.ptr) -> i64
%440 = llvm.getelementptr %arg3[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %439, %440 : i64, !llvm.ptr
%441 = llvm.load %398 : !llvm.ptr -> i64
%442 = arith.constant 1 : i32
%444 = arith.extsi %442 : i32 to i64
%443 = arith.addi %441, %444 : i64
llvm.store %443, %398 : i64, !llvm.ptr
cf.br ^bb90
^bb92:
%446 = arith.constant 0 : i32
%447 = llvm.load %363 : !llvm.ptr -> i32
%448 = arith.extsi %446 : i32 to i64
%445 = func.call @fold(%448, %447, %arg2, %arg3, %arg4, %arg1, %380) : (i64, i32, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> i64
%449 = llvm.load %363 : !llvm.ptr -> i32
%450 = arith.constant 1 : i32
%451 = arith.andi %449, %450 : i32
%452 = arith.constant 1 : i32
%453 = arith.cmpi eq, %451, %452 : i32
cf.cond_br %453, ^bb93, ^bb94
^bb93:
%454 = llvm.mlir.addressof @MASK : !llvm.ptr
%455 = llvm.load %454 : !llvm.ptr -> i64
%456 = arith.subi %455, %445 : i64
func.return %456 : i64
^bb94:
cf.br ^bb95
^bb95:
func.return %445 : i64
}
func.func @main() -> i32 {
%458 = arith.constant 4 : i32
%459 = arith.constant 8 : i32
%460 = arith.extsi %458 : i32 to i64
%461 = arith.extsi %459 : i32 to i64
%457 = func.call @calloc(%460, %461) : (i64, i64) -> !llvm.ptr
%463 = llvm.mlir.addressof @CAP : !llvm.ptr
%464 = llvm.load %463 : !llvm.ptr -> i64
%465 = arith.constant 8 : i32
%466 = arith.extsi %465 : i32 to i64
%462 = func.call @calloc(%464, %466) : (i64, i64) -> !llvm.ptr
%468 = llvm.mlir.addressof @CAP : !llvm.ptr
%469 = llvm.load %468 : !llvm.ptr -> i64
%470 = arith.constant 8 : i32
%471 = arith.extsi %470 : i32 to i64
%467 = func.call @calloc(%469, %471) : (i64, i64) -> !llvm.ptr
%473 = llvm.mlir.addressof @CAP : !llvm.ptr
%474 = llvm.load %473 : !llvm.ptr -> i64
%475 = arith.constant 1 : i32
%476 = arith.extsi %475 : i32 to i64
%472 = func.call @calloc(%474, %476) : (i64, i64) -> !llvm.ptr
%478 = arith.constant 4096 : i32
%479 = arith.constant 8 : i32
%480 = arith.extsi %478 : i32 to i64
%481 = arith.extsi %479 : i32 to i64
%477 = func.call @calloc(%480, %481) : (i64, i64) -> !llvm.ptr
%483 = arith.constant 4096 : i32
%484 = arith.constant 4 : i32
%485 = arith.extsi %483 : i32 to i64
%486 = arith.extsi %484 : i32 to i64
%482 = func.call @calloc(%485, %486) : (i64, i64) -> !llvm.ptr
%488 = arith.constant 4096 : i32
%489 = arith.constant 1 : i32
%490 = arith.extsi %488 : i32 to i64
%491 = arith.extsi %489 : i32 to i64
%487 = func.call @calloc(%490, %491) : (i64, i64) -> !llvm.ptr
%493 = arith.constant 1 : i32
%494 = arith.constant 8 : i32
%495 = arith.extsi %493 : i32 to i64
%496 = arith.extsi %494 : i32 to i64
%492 = func.call @calloc(%495, %496) : (i64, i64) -> !llvm.ptr
%497 = llvm.mlir.zero : !llvm.ptr
%498 = llvm.icmp "eq" %457, %497 : !llvm.ptr
%499 = scf.if %498 -> (i1) {
%500 = arith.constant true
scf.yield %500 : i1
} else {
%501 = llvm.mlir.zero : !llvm.ptr
%502 = llvm.icmp "eq" %462, %501 : !llvm.ptr
scf.yield %502 : i1
}
%503 = scf.if %499 -> (i1) {
%504 = arith.constant true
scf.yield %504 : i1
} else {
%505 = llvm.mlir.zero : !llvm.ptr
%506 = llvm.icmp "eq" %467, %505 : !llvm.ptr
scf.yield %506 : i1
}
%507 = scf.if %503 -> (i1) {
%508 = arith.constant true
scf.yield %508 : i1
} else {
%509 = llvm.mlir.zero : !llvm.ptr
%510 = llvm.icmp "eq" %472, %509 : !llvm.ptr
scf.yield %510 : i1
}
%511 = scf.if %507 -> (i1) {
%512 = arith.constant true
scf.yield %512 : i1
} else {
%513 = llvm.mlir.zero : !llvm.ptr
%514 = llvm.icmp "eq" %477, %513 : !llvm.ptr
scf.yield %514 : i1
}
%515 = scf.if %511 -> (i1) {
%516 = arith.constant true
scf.yield %516 : i1
} else {
%517 = llvm.mlir.zero : !llvm.ptr
%518 = llvm.icmp "eq" %482, %517 : !llvm.ptr
scf.yield %518 : i1
}
%519 = scf.if %515 -> (i1) {
%520 = arith.constant true
scf.yield %520 : i1
} else {
%521 = llvm.mlir.zero : !llvm.ptr
%522 = llvm.icmp "eq" %487, %521 : !llvm.ptr
scf.yield %522 : i1
}
%523 = scf.if %519 -> (i1) {
%524 = arith.constant true
scf.yield %524 : i1
} else {
%525 = llvm.mlir.zero : !llvm.ptr
%526 = llvm.icmp "eq" %492, %525 : !llvm.ptr
scf.yield %526 : i1
}
cf.cond_br %523, ^bb96, ^bb97
^bb96:
%527 = arith.constant 1 : i32
func.return %527 : i32
^bb97:
cf.br ^bb98
^bb98:
%529 = arith.constant 995705032704 : i32
%530 = arith.extsi %529 : i32 to i64
%528 = func.call @A(%530, %457, %462, %467, %472, %477, %482, %487, %492) : (i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i64
%531 = llvm.mlir.addressof @str_0 : !llvm.ptr
%532 = llvm.call @printf(%531, %528) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%457) : (!llvm.ptr) -> ()
func.call @free(%462) : (!llvm.ptr) -> ()
func.call @free(%467) : (!llvm.ptr) -> ()
func.call @free(%472) : (!llvm.ptr) -> ()
func.call @free(%477) : (!llvm.ptr) -> ()
func.call @free(%482) : (!llvm.ptr) -> ()
func.call @free(%487) : (!llvm.ptr) -> ()
func.call @free(%492) : (!llvm.ptr) -> ()
%541 = arith.constant 0 : i32
func.return %541 : i32
}
}