← All problems Problem 774
Counts sequences a_1..a_l with 0 <= a_i <= m such that every pair of equal values a_i = a_j (i < j) has gcd(a_i, ..., a_j) > 1. D(length, bound, left, right) is memoised with open-addressing hash table. Pure Flow port of the native C solver.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n)?Space complexity O(n^2)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 774: Divide and Rule.
# Counts sequences a_1..a_l with 0 <= a_i <= m such that every pair of
# equal values a_i = a_j (i < j) has gcd(a_i, ..., a_j) > 1.
# D(length, bound, left, right) is memoised with open-addressing hash table.
# Pure Flow port of the native C solver.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 998244353
const TOP: i32 = -1
const ODD: i32 = -2
const MAX_N: i64 = 123
# Fibonacci table mod MOD.
let mut FIB: ptr<i64> = null
function init_fib() -> void {
FIB = calloc(MAX_N + 2, 8) as ptr<i64>
FIB[0] = 0
FIB[1] = 1 % MOD
let mut i: i64 = 2
while i < MAX_N + 2 {
FIB[i] = (FIB[i - 1] + FIB[i - 2]) % MOD
i = i + 1
}
}
function fib(index: i32) -> i64 {
if index >= 0 {
return FIB[index]
}
let k: i64 = -(index as i64)
if k % 2 == 1 {
return FIB[k]
}
let mut v: i64 = -(FIB[k]) % MOD
if v < 0 {
v = v + MOD
}
return v
}
function boundary_is_impossible(state: i32) -> i32 {
if state == 0 {
return 1
}
return 0
}
function satisfies(state: i32, value: i64) -> i32 {
if state == TOP {
return 1
}
if state == ODD {
if value % 2 == 1 {
return 1
}
return 0
}
if (value & (state as i64)) != 0 {
return 1
}
return 0
}
function phi_even(state: i32) -> i32 {
if state == TOP {
return TOP
}
if state == ODD {
return 0
}
return state / 2
}
function phi_odd(state: i32) -> i32 {
if state == TOP || state == ODD {
return TOP
}
if state % 2 == 1 {
return TOP
}
return state / 2
}
# Memoisation hash table. Key: (length, bound, left, right). Value: result mod MOD.
# Store keys as parallel arrays of 4 i32 fields.
let mut memo_len: ptr<i32> = null
let mut memo_bnd: ptr<i32> = null
let mut memo_lft: ptr<i32> = null
let mut memo_rgt: ptr<i32> = null
let mut memo_val: ptr<i64> = null
let mut memo_used: ptr<i8> = null
let mut memo_cap: i64 = 0
let mut memo_count: i64 = 0
function hash_key(length: i32, bound: i32, left: i32, right: i32) -> i64 {
let mut h: i64 = 1469598103934665603
h = h ^ (length as i64)
h = h * 1099511628211
h = h ^ (bound as i64)
h = h * 1099511628211
h = h ^ (left as i64)
h = h * 1099511628211
h = h ^ (right as i64)
h = h * 1099511628211
return h
}
function memo_init(cap: i64) -> void {
memo_cap = cap
memo_count = 0
memo_len = calloc(cap, 4) as ptr<i32>
memo_bnd = calloc(cap, 4) as ptr<i32>
memo_lft = calloc(cap, 4) as ptr<i32>
memo_rgt = calloc(cap, 4) as ptr<i32>
memo_val = calloc(cap, 8) as ptr<i64>
memo_used = calloc(cap, 1) as ptr<i8>
}
function memo_lookup(length: i32, bound: i32, left: i32, right: i32, out: ptr<i64>) -> i32 {
if memo_cap == 0 {
return 0
}
let mask: i64 = memo_cap - 1
let mut h: i64 = hash_key(length, bound, left, right) & mask
while memo_used[h] != 0 {
if memo_len[h] == length && memo_bnd[h] == bound && memo_lft[h] == left && memo_rgt[h] == right {
out[0] = memo_val[h]
return 1
}
h = (h + 1) & mask
}
return 0
}
function memo_insert_raw(length: i32, bound: i32, left: i32, right: i32, v: i64) -> void {
let mask: i64 = memo_cap - 1
let mut h: i64 = hash_key(length, bound, left, right) & mask
while memo_used[h] != 0 {
h = (h + 1) & mask
}
memo_used[h] = 1
memo_len[h] = length
memo_bnd[h] = bound
memo_lft[h] = left
memo_rgt[h] = right
memo_val[h] = v
memo_count = memo_count + 1
}
function memo_grow() -> void {
let old_len: ptr<i32> = memo_len
let old_bnd: ptr<i32> = memo_bnd
let old_lft: ptr<i32> = memo_lft
let old_rgt: ptr<i32> = memo_rgt
let old_val: ptr<i64> = memo_val
let old_used: ptr<i8> = memo_used
let old_cap: i64 = memo_cap
memo_cap = memo_cap * 2
memo_len = calloc(memo_cap, 4) as ptr<i32>
memo_bnd = calloc(memo_cap, 4) as ptr<i32>
memo_lft = calloc(memo_cap, 4) as ptr<i32>
memo_rgt = calloc(memo_cap, 4) as ptr<i32>
memo_val = calloc(memo_cap, 8) as ptr<i64>
memo_used = calloc(memo_cap, 1) as ptr<i8>
memo_count = 0
let mut i: i64 = 0
while i < old_cap {
if old_used[i] != 0 {
memo_insert_raw(old_len[i], old_bnd[i], old_lft[i], old_rgt[i], old_val[i])
}
i = i + 1
}
free(old_len)
free(old_bnd)
free(old_lft)
free(old_rgt)
free(old_val)
free(old_used)
}
function memo_put(length: i32, bound: i32, left: i32, right: i32, v: i64) -> void {
if memo_count * 10 >= memo_cap * 7 {
memo_grow()
}
memo_insert_raw(length, bound, left, right, v)
}
# Core recursion D(length, bound, left, right).
function D(length: i32, bound: i32, left: i32, right: i32) -> i64 {
if boundary_is_impossible(left) != 0 || boundary_is_impossible(right) != 0 {
return 0
}
if length == 0 {
if left == TOP && right == TOP {
return 1
}
return 0
}
if bound <= 1 {
if length == 1 {
let mut s: i64 = 0
let mut value: i64 = 0
while value <= (bound as i64) {
if satisfies(left, value) != 0 && satisfies(right, value) != 0 {
s = s + 1
}
value = value + 1
}
return s
}
if bound == 0 {
return 0
}
if satisfies(left, 1) != 0 && satisfies(right, 1) != 0 {
return 1
}
return 0
}
let outp: ptr<i64> = calloc(1, 8) as ptr<i64>
if memo_lookup(length, bound, left, right, outp) != 0 {
let rv: i64 = outp[0]
free(outp)
return rv
}
free(outp)
let mut total: i64 = 0
if bound % 2 == 0 {
let marked_bound: i32 = bound
total = D(length, bound - 1, left, right)
let mut split: i32 = 1
while split <= length {
let prefix_len: i32 = split - 1
let suffix_len: i32 = length - split
let mut prefix_count: i64 = 0
if prefix_len == 0 {
if satisfies(left, bound as i64) != 0 {
prefix_count = 1
}
} else {
prefix_count = D(prefix_len, bound - 1, left, marked_bound)
}
if prefix_count != 0 {
let mut suffix_count: i64 = 0
if suffix_len == 0 {
if satisfies(right, bound as i64) != 0 {
suffix_count = 1
}
} else {
suffix_count = D(suffix_len, bound, marked_bound, right)
}
total = (total + prefix_count * suffix_count) % MOD
}
split = split + 1
}
memo_put(length, bound, left, right, total)
return total
}
# bound is odd
let reduced_bound: i32 = (bound - 1) / 2
let left_even: i32 = phi_even(left)
let left_odd: i32 = phi_odd(left)
let right_even: i32 = phi_even(right)
let right_odd: i32 = phi_odd(right)
total = D(length, reduced_bound, left_even, right_even) * fib(length) % MOD
total = (total + D(length, reduced_bound, left_even, right_odd) * fib(length - 1)) % MOD
total = (total + D(length, reduced_bound, left_odd, right_even) * fib(length - 1)) % MOD
total = (total + D(length, reduced_bound, left_odd, right_odd) * fib(length - 2)) % MOD
total = total % MOD
let mut cut: i32 = 1
while cut < length {
let mut prefix: i64 = D(cut, reduced_bound, left_odd, TOP) * fib(cut - 2) % MOD
if cut > 1 {
prefix = (prefix + D(cut, reduced_bound, left_even, TOP) * fib(cut - 1)) % MOD
}
if prefix != 0 {
total = (total + D(length - cut, bound, ODD, right) * prefix) % MOD
}
cut = cut + 1
}
memo_put(length, bound, left, right, total)
return total
}
function c_func(length: i32, bound: i32) -> i64 {
return D(length, bound, TOP, TOP)
}
function main() -> i32 {
init_fib()
memo_init(1 << 16)
printf("%lld\n", c_func(123, 123456789))
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; }
void init_fib(void);
int64_t fib_i32(int32_t index);
int32_t boundary_is_impossible_i32(int32_t state);
int32_t satisfies_i32_i64(int32_t state, int64_t value);
int32_t phi_even_i32(int32_t state);
int32_t phi_odd_i32(int32_t state);
int64_t hash_key_i32_i32_i32_i32(int32_t length, int32_t bound, int32_t left, int32_t right);
void memo_init_i64(int64_t cap);
int32_t memo_lookup_i32_i32_i32_i32_ptr_i64(int32_t length, int32_t bound, int32_t left, int32_t right, int64_t* out);
void memo_insert_raw_i32_i32_i32_i32_i64(int32_t length, int32_t bound, int32_t left, int32_t right, int64_t v);
void memo_grow(void);
void memo_put_i32_i32_i32_i32_i64(int32_t length, int32_t bound, int32_t left, int32_t right, int64_t v);
int64_t D_i32_i32_i32_i32(int32_t length, int32_t bound, int32_t left, int32_t right);
int64_t c_func_i32_i32(int32_t length, int32_t bound);
int32_t main(void);
static const int64_t MOD = 998244353;
static const int32_t TOP = (-1);
static const int32_t ODD = (-2);
static const int64_t MAX_N = 123;
/* Module statics */
static int64_t* FIB = NULL;
static int32_t* memo_len = NULL;
static int32_t* memo_bnd = NULL;
static int32_t* memo_lft = NULL;
static int32_t* memo_rgt = NULL;
static int64_t* memo_val = NULL;
static int8_t* memo_used = NULL;
static int64_t memo_cap = 0;
static int64_t memo_count = 0;
void init_fib(void) {
FIB = ((int64_t*)(calloc((MAX_N + 2), 8)));
FIB[0] = 0;
FIB[1] = FLOW_CHECKED_MOD((1), (MOD));
int64_t i = 2;
while (i < (MAX_N + 2)) {
FIB[i] = FLOW_CHECKED_MOD(((FIB[(i - 1)] + FIB[(i - 2)])), (MOD));
i = (i + 1);
}
}
int64_t fib_i32(int32_t index) {
if (index >= 0) {
return FIB[index];
}
int64_t k = (-((int64_t)(index)));
if (FLOW_CHECKED_MOD((k), (2)) == 1) {
return FIB[k];
}
int64_t v = FLOW_CHECKED_MOD(((-FIB[k])), (MOD));
if (v < 0) {
v = (v + MOD);
}
return v;
}
int32_t boundary_is_impossible_i32(int32_t state) {
if (state == 0) {
return 1;
}
return 0;
}
int32_t satisfies_i32_i64(int32_t state, int64_t value) {
if (state == TOP) {
return 1;
}
if (state == ODD) {
if (FLOW_CHECKED_MOD((value), (2)) == 1) {
return 1;
}
return 0;
}
if ((value & ((int64_t)(state))) != 0) {
return 1;
}
return 0;
}
int32_t phi_even_i32(int32_t state) {
if (state == TOP) {
return TOP;
}
if (state == ODD) {
return 0;
}
return FLOW_CHECKED_DIV((state), (2));
}
int32_t phi_odd_i32(int32_t state) {
if ((state == TOP || state == ODD)) {
return TOP;
}
if (FLOW_CHECKED_MOD((state), (2)) == 1) {
return TOP;
}
return FLOW_CHECKED_DIV((state), (2));
}
int64_t hash_key_i32_i32_i32_i32(int32_t length, int32_t bound, int32_t left, int32_t right) {
int64_t h = 1469598103934665603;
h = (h ^ ((int64_t)(length)));
h = (h * 1099511628211);
h = (h ^ ((int64_t)(bound)));
h = (h * 1099511628211);
h = (h ^ ((int64_t)(left)));
h = (h * 1099511628211);
h = (h ^ ((int64_t)(right)));
h = (h * 1099511628211);
return h;
}
void memo_init_i64(int64_t cap) {
memo_cap = cap;
memo_count = 0;
memo_len = ((int32_t*)(calloc(cap, 4)));
memo_bnd = ((int32_t*)(calloc(cap, 4)));
memo_lft = ((int32_t*)(calloc(cap, 4)));
memo_rgt = ((int32_t*)(calloc(cap, 4)));
memo_val = ((int64_t*)(calloc(cap, 8)));
memo_used = ((int8_t*)(calloc(cap, 1)));
}
int32_t memo_lookup_i32_i32_i32_i32_ptr_i64(int32_t length, int32_t bound, int32_t left, int32_t right, int64_t* out) {
if (memo_cap == 0) {
return 0;
}
int64_t mask = (memo_cap - 1);
int64_t h = (hash_key_i32_i32_i32_i32(length, bound, left, right) & mask);
while (memo_used[h] != 0) {
if ((((memo_len[h] == length && memo_bnd[h] == bound) && memo_lft[h] == left) && memo_rgt[h] == right)) {
out[0] = memo_val[h];
return 1;
}
h = ((h + 1) & mask);
}
return 0;
}
void memo_insert_raw_i32_i32_i32_i32_i64(int32_t length, int32_t bound, int32_t left, int32_t right, int64_t v) {
int64_t mask = (memo_cap - 1);
int64_t h = (hash_key_i32_i32_i32_i32(length, bound, left, right) & mask);
while (memo_used[h] != 0) {
h = ((h + 1) & mask);
}
memo_used[h] = 1;
memo_len[h] = length;
memo_bnd[h] = bound;
memo_lft[h] = left;
memo_rgt[h] = right;
memo_val[h] = v;
memo_count = (memo_count + 1);
}
void memo_grow(void) {
int32_t* old_len = (int32_t*)(memo_len);
int32_t* old_bnd = (int32_t*)(memo_bnd);
int32_t* old_lft = (int32_t*)(memo_lft);
int32_t* old_rgt = (int32_t*)(memo_rgt);
int64_t* old_val = (int64_t*)(memo_val);
int8_t* old_used = (int8_t*)(memo_used);
int64_t old_cap = memo_cap;
memo_cap = (memo_cap * 2);
memo_len = ((int32_t*)(calloc(memo_cap, 4)));
memo_bnd = ((int32_t*)(calloc(memo_cap, 4)));
memo_lft = ((int32_t*)(calloc(memo_cap, 4)));
memo_rgt = ((int32_t*)(calloc(memo_cap, 4)));
memo_val = ((int64_t*)(calloc(memo_cap, 8)));
memo_used = ((int8_t*)(calloc(memo_cap, 1)));
memo_count = 0;
int64_t i = 0;
while (i < old_cap) {
if (old_used[i] != 0) {
memo_insert_raw_i32_i32_i32_i32_i64(old_len[i], old_bnd[i], old_lft[i], old_rgt[i], old_val[i]);
}
i = (i + 1);
}
free(old_len);
free(old_bnd);
free(old_lft);
free(old_rgt);
free(old_val);
free(old_used);
}
void memo_put_i32_i32_i32_i32_i64(int32_t length, int32_t bound, int32_t left, int32_t right, int64_t v) {
if ((memo_count * 10) >= (memo_cap * 7)) {
memo_grow();
}
memo_insert_raw_i32_i32_i32_i32_i64(length, bound, left, right, v);
}
int64_t D_i32_i32_i32_i32(int32_t length, int32_t bound, int32_t left, int32_t right) {
if ((boundary_is_impossible_i32(left) != 0 || boundary_is_impossible_i32(right) != 0)) {
return 0;
}
if (length == 0) {
if ((left == TOP && right == TOP)) {
return 1;
}
return 0;
}
if (bound <= 1) {
if (length == 1) {
int64_t s = 0;
int64_t value = 0;
while (value <= ((int64_t)(bound))) {
if ((satisfies_i32_i64(left, value) != 0 && satisfies_i32_i64(right, value) != 0)) {
s = (s + 1);
}
value = (value + 1);
}
return s;
}
if (bound == 0) {
return 0;
}
if ((satisfies_i32_i64(left, 1) != 0 && satisfies_i32_i64(right, 1) != 0)) {
return 1;
}
return 0;
}
int64_t* outp = (int64_t*)(((int64_t*)(calloc(1, 8))));
if (memo_lookup_i32_i32_i32_i32_ptr_i64(length, bound, left, right, outp) != 0) {
int64_t rv = outp[0];
free(outp);
return rv;
}
free(outp);
int64_t total = 0;
if (FLOW_CHECKED_MOD((bound), (2)) == 0) {
int32_t marked_bound = bound;
total = D_i32_i32_i32_i32(length, (bound - 1), left, right);
int32_t split = 1;
while (split <= length) {
int32_t prefix_len = (split - 1);
int32_t suffix_len = (length - split);
int64_t prefix_count = 0;
if (prefix_len == 0) {
if (satisfies_i32_i64(left, ((int64_t)(bound))) != 0) {
prefix_count = 1;
}
} else {
prefix_count = D_i32_i32_i32_i32(prefix_len, (bound - 1), left, marked_bound);
}
if (prefix_count != 0) {
int64_t suffix_count = 0;
if (suffix_len == 0) {
if (satisfies_i32_i64(right, ((int64_t)(bound))) != 0) {
suffix_count = 1;
}
} else {
suffix_count = D_i32_i32_i32_i32(suffix_len, bound, marked_bound, right);
}
total = FLOW_CHECKED_MOD(((total + (prefix_count * suffix_count))), (MOD));
}
split = (split + 1);
}
memo_put_i32_i32_i32_i32_i64(length, bound, left, right, total);
return total;
}
int32_t reduced_bound = FLOW_CHECKED_DIV(((bound - 1)), (2));
int32_t left_even = phi_even_i32(left);
int32_t left_odd = phi_odd_i32(left);
int32_t right_even = phi_even_i32(right);
int32_t right_odd = phi_odd_i32(right);
total = FLOW_CHECKED_MOD(((D_i32_i32_i32_i32(length, reduced_bound, left_even, right_even) * fib_i32(length))), (MOD));
total = FLOW_CHECKED_MOD(((total + (D_i32_i32_i32_i32(length, reduced_bound, left_even, right_odd) * fib_i32((length - 1))))), (MOD));
total = FLOW_CHECKED_MOD(((total + (D_i32_i32_i32_i32(length, reduced_bound, left_odd, right_even) * fib_i32((length - 1))))), (MOD));
total = FLOW_CHECKED_MOD(((total + (D_i32_i32_i32_i32(length, reduced_bound, left_odd, right_odd) * fib_i32((length - 2))))), (MOD));
total = FLOW_CHECKED_MOD((total), (MOD));
int32_t cut = 1;
while (cut < length) {
int64_t prefix = FLOW_CHECKED_MOD(((D_i32_i32_i32_i32(cut, reduced_bound, left_odd, TOP) * fib_i32((cut - 2)))), (MOD));
if (cut > 1) {
prefix = FLOW_CHECKED_MOD(((prefix + (D_i32_i32_i32_i32(cut, reduced_bound, left_even, TOP) * fib_i32((cut - 1))))), (MOD));
}
if (prefix != 0) {
total = FLOW_CHECKED_MOD(((total + (D_i32_i32_i32_i32((length - cut), bound, ODD, right) * prefix))), (MOD));
}
cut = (cut + 1);
}
memo_put_i32_i32_i32_i32_i64(length, bound, left, right, total);
return total;
}
int64_t c_func_i32_i32(int32_t length, int32_t bound) {
return D_i32_i32_i32_i32(length, bound, TOP, TOP);
}
int32_t main(void) {
init_fib();
memo_init_i64(FLOW_CHECKED_SHL((1), (16)));
printf("%lld\n", c_func_i32_i32(123, 123456789));
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: MOD
llvm.mlir.global internal constant @MOD(998244353 : i64) : i64
// Constant: TOP
llvm.mlir.global internal constant @TOP(-1 : i32) : i32
// Constant: ODD
llvm.mlir.global internal constant @ODD(-2 : i32) : i32
// Constant: MAX_N
llvm.mlir.global internal constant @MAX_N(123 : i64) : i64
// Module static: FIB
llvm.mlir.global internal @FIB() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
func.func @init_fib() -> () {
%2 = llvm.mlir.addressof @MAX_N : !llvm.ptr
%3 = llvm.load %2 : !llvm.ptr -> i64
%4 = arith.constant 2 : i32
%6 = arith.extsi %4 : i32 to i64
%5 = arith.addi %3, %6 : i64
%7 = arith.constant 8 : i32
%8 = arith.extsi %7 : i32 to i64
%1 = func.call @calloc(%5, %8) : (i64, i64) -> !llvm.ptr
%9 = llvm.mlir.addressof @FIB : !llvm.ptr
llvm.store %1, %9 : !llvm.ptr, !llvm.ptr
%10 = arith.constant 0 : i32
%11 = llvm.mlir.addressof @FIB : !llvm.ptr
%12 = llvm.load %11 : !llvm.ptr -> !llvm.ptr
%13 = arith.constant 0 : i32
%14 = arith.extsi %10 : i32 to i64
%15 = arith.extsi %13 : i32 to i64
%16 = llvm.getelementptr %12[%15] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %14, %16 : i64, !llvm.ptr
%17 = arith.constant 1 : i32
%18 = llvm.mlir.addressof @MOD : !llvm.ptr
%19 = llvm.load %18 : !llvm.ptr -> i64
%21 = arith.extsi %17 : i32 to i64
%20 = arith.remsi %21, %19 : i64
%22 = llvm.mlir.addressof @FIB : !llvm.ptr
%23 = llvm.load %22 : !llvm.ptr -> !llvm.ptr
%24 = arith.constant 1 : i32
%25 = arith.extsi %24 : i32 to i64
%26 = llvm.getelementptr %23[%25] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %20, %26 : i64, !llvm.ptr
%27 = arith.constant 2 : i32
%28 = arith.extsi %27 : i32 to i64
%29 = llvm.mlir.constant(1 : i64) : i64
%30 = llvm.alloca %29 x i64 : (i64) -> !llvm.ptr
llvm.store %28, %30 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%31 = llvm.load %30 : !llvm.ptr -> i64
%32 = llvm.mlir.addressof @MAX_N : !llvm.ptr
%33 = llvm.load %32 : !llvm.ptr -> i64
%34 = arith.constant 2 : i32
%36 = arith.extsi %34 : i32 to i64
%35 = arith.addi %33, %36 : i64
%37 = arith.cmpi slt, %31, %35 : i64
cf.cond_br %37, ^bb1, ^bb2
^bb1:
%39 = llvm.mlir.addressof @FIB : !llvm.ptr
%40 = llvm.load %39 : !llvm.ptr -> !llvm.ptr
%41 = llvm.load %30 : !llvm.ptr -> i64
%42 = arith.constant 1 : i32
%44 = arith.extsi %42 : i32 to i64
%43 = arith.subi %41, %44 : i64
%45 = llvm.getelementptr %40[%43] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%38 = llvm.load %45 : !llvm.ptr -> i64
%47 = llvm.mlir.addressof @FIB : !llvm.ptr
%48 = llvm.load %47 : !llvm.ptr -> !llvm.ptr
%49 = llvm.load %30 : !llvm.ptr -> i64
%50 = arith.constant 2 : i32
%52 = arith.extsi %50 : i32 to i64
%51 = arith.subi %49, %52 : i64
%53 = llvm.getelementptr %48[%51] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%46 = llvm.load %53 : !llvm.ptr -> i64
%54 = arith.addi %38, %46 : i64
%55 = llvm.mlir.addressof @MOD : !llvm.ptr
%56 = llvm.load %55 : !llvm.ptr -> i64
%57 = arith.remsi %54, %56 : i64
%58 = llvm.mlir.addressof @FIB : !llvm.ptr
%59 = llvm.load %58 : !llvm.ptr -> !llvm.ptr
%60 = llvm.load %30 : !llvm.ptr -> i64
%61 = llvm.getelementptr %59[%60] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %57, %61 : i64, !llvm.ptr
%62 = llvm.load %30 : !llvm.ptr -> i64
%63 = arith.constant 1 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.addi %62, %65 : i64
llvm.store %64, %30 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
func.return
}
func.func @fib(%arg0: i32) -> i64 {
%66 = arith.constant 0 : i32
%67 = arith.cmpi sge, %arg0, %66 : i32
cf.cond_br %67, ^bb3, ^bb4
^bb3:
%69 = llvm.mlir.addressof @FIB : !llvm.ptr
%70 = llvm.load %69 : !llvm.ptr -> !llvm.ptr
%71 = arith.extsi %arg0 : i32 to i64
%72 = llvm.getelementptr %70[%71] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%68 = llvm.load %72 : !llvm.ptr -> i64
func.return %68 : i64
^bb4:
cf.br ^bb5
^bb5:
%73 = arith.extsi %arg0 : i32 to i64
%75 = arith.constant 0 : i64
%74 = arith.subi %75, %73 : i64
%76 = arith.constant 2 : i32
%78 = arith.extsi %76 : i32 to i64
%77 = arith.remsi %74, %78 : i64
%79 = arith.constant 1 : i32
%81 = arith.extsi %79 : i32 to i64
%80 = arith.cmpi eq, %77, %81 : i64
cf.cond_br %80, ^bb6, ^bb7
^bb6:
%83 = llvm.mlir.addressof @FIB : !llvm.ptr
%84 = llvm.load %83 : !llvm.ptr -> !llvm.ptr
%85 = llvm.getelementptr %84[%74] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%82 = llvm.load %85 : !llvm.ptr -> i64
func.return %82 : i64
^bb7:
cf.br ^bb8
^bb8:
%87 = llvm.mlir.addressof @FIB : !llvm.ptr
%88 = llvm.load %87 : !llvm.ptr -> !llvm.ptr
%89 = llvm.getelementptr %88[%74] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%86 = llvm.load %89 : !llvm.ptr -> i64
%91 = arith.constant 0 : i64
%90 = arith.subi %91, %86 : i64
%92 = llvm.mlir.addressof @MOD : !llvm.ptr
%93 = llvm.load %92 : !llvm.ptr -> i64
%94 = arith.remsi %90, %93 : i64
%95 = llvm.mlir.constant(1 : i64) : i64
%96 = llvm.alloca %95 x i64 : (i64) -> !llvm.ptr
llvm.store %94, %96 : i64, !llvm.ptr
%97 = llvm.load %96 : !llvm.ptr -> i64
%98 = arith.constant 0 : i32
%100 = arith.extsi %98 : i32 to i64
%99 = arith.cmpi slt, %97, %100 : i64
cf.cond_br %99, ^bb9, ^bb10
^bb9:
%101 = llvm.load %96 : !llvm.ptr -> i64
%102 = llvm.mlir.addressof @MOD : !llvm.ptr
%103 = llvm.load %102 : !llvm.ptr -> i64
%104 = arith.addi %101, %103 : i64
llvm.store %104, %96 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%105 = llvm.load %96 : !llvm.ptr -> i64
func.return %105 : i64
}
func.func @boundary_is_impossible(%arg0: i32) -> i32 {
%106 = arith.constant 0 : i32
%107 = arith.cmpi eq, %arg0, %106 : i32
cf.cond_br %107, ^bb12, ^bb13
^bb12:
%108 = arith.constant 1 : i32
func.return %108 : i32
^bb13:
cf.br ^bb14
^bb14:
%109 = arith.constant 0 : i32
func.return %109 : i32
}
func.func @satisfies(%arg0: i32, %arg1: i64) -> i32 {
%110 = llvm.mlir.addressof @TOP : !llvm.ptr
%111 = llvm.load %110 : !llvm.ptr -> i32
%112 = arith.cmpi eq, %arg0, %111 : i32
cf.cond_br %112, ^bb15, ^bb16
^bb15:
%113 = arith.constant 1 : i32
func.return %113 : i32
^bb16:
cf.br ^bb17
^bb17:
%114 = llvm.mlir.addressof @ODD : !llvm.ptr
%115 = llvm.load %114 : !llvm.ptr -> i32
%116 = arith.cmpi eq, %arg0, %115 : i32
cf.cond_br %116, ^bb18, ^bb19
^bb18:
%117 = arith.constant 2 : i32
%119 = arith.extsi %117 : i32 to i64
%118 = arith.remsi %arg1, %119 : i64
%120 = arith.constant 1 : i32
%122 = arith.extsi %120 : i32 to i64
%121 = arith.cmpi eq, %118, %122 : i64
cf.cond_br %121, ^bb21, ^bb22
^bb21:
%123 = arith.constant 1 : i32
func.return %123 : i32
^bb22:
cf.br ^bb23
^bb23:
%124 = arith.constant 0 : i32
func.return %124 : i32
^bb19:
cf.br ^bb20
^bb20:
%125 = arith.extsi %arg0 : i32 to i64
%126 = arith.andi %arg1, %125 : i64
%127 = arith.constant 0 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.cmpi ne, %126, %129 : i64
cf.cond_br %128, ^bb24, ^bb25
^bb24:
%130 = arith.constant 1 : i32
func.return %130 : i32
^bb25:
cf.br ^bb26
^bb26:
%131 = arith.constant 0 : i32
func.return %131 : i32
}
func.func @phi_even(%arg0: i32) -> i32 {
%132 = llvm.mlir.addressof @TOP : !llvm.ptr
%133 = llvm.load %132 : !llvm.ptr -> i32
%134 = arith.cmpi eq, %arg0, %133 : i32
cf.cond_br %134, ^bb27, ^bb28
^bb27:
%135 = llvm.mlir.addressof @TOP : !llvm.ptr
%136 = llvm.load %135 : !llvm.ptr -> i32
func.return %136 : i32
^bb28:
cf.br ^bb29
^bb29:
%137 = llvm.mlir.addressof @ODD : !llvm.ptr
%138 = llvm.load %137 : !llvm.ptr -> i32
%139 = arith.cmpi eq, %arg0, %138 : i32
cf.cond_br %139, ^bb30, ^bb31
^bb30:
%140 = arith.constant 0 : i32
func.return %140 : i32
^bb31:
cf.br ^bb32
^bb32:
%141 = arith.constant 2 : i32
%142 = arith.divsi %arg0, %141 : i32
func.return %142 : i32
}
func.func @phi_odd(%arg0: i32) -> i32 {
%143 = llvm.mlir.addressof @TOP : !llvm.ptr
%144 = llvm.load %143 : !llvm.ptr -> i32
%145 = arith.cmpi eq, %arg0, %144 : i32
%146 = scf.if %145 -> (i1) {
%147 = arith.constant true
scf.yield %147 : i1
} else {
%148 = llvm.mlir.addressof @ODD : !llvm.ptr
%149 = llvm.load %148 : !llvm.ptr -> i32
%150 = arith.cmpi eq, %arg0, %149 : i32
scf.yield %150 : i1
}
cf.cond_br %146, ^bb33, ^bb34
^bb33:
%151 = llvm.mlir.addressof @TOP : !llvm.ptr
%152 = llvm.load %151 : !llvm.ptr -> i32
func.return %152 : i32
^bb34:
cf.br ^bb35
^bb35:
%153 = arith.constant 2 : i32
%154 = arith.remsi %arg0, %153 : i32
%155 = arith.constant 1 : i32
%156 = arith.cmpi eq, %154, %155 : i32
cf.cond_br %156, ^bb36, ^bb37
^bb36:
%157 = llvm.mlir.addressof @TOP : !llvm.ptr
%158 = llvm.load %157 : !llvm.ptr -> i32
func.return %158 : i32
^bb37:
cf.br ^bb38
^bb38:
%159 = arith.constant 2 : i32
%160 = arith.divsi %arg0, %159 : i32
func.return %160 : i32
}
// Module static: memo_len
llvm.mlir.global internal @memo_len() {addr_space = 0 : i32} : !llvm.ptr {
%161 = llvm.mlir.zero : !llvm.ptr
llvm.return %161 : !llvm.ptr
}
// Module static: memo_bnd
llvm.mlir.global internal @memo_bnd() {addr_space = 0 : i32} : !llvm.ptr {
%162 = llvm.mlir.zero : !llvm.ptr
llvm.return %162 : !llvm.ptr
}
// Module static: memo_lft
llvm.mlir.global internal @memo_lft() {addr_space = 0 : i32} : !llvm.ptr {
%163 = llvm.mlir.zero : !llvm.ptr
llvm.return %163 : !llvm.ptr
}
// Module static: memo_rgt
llvm.mlir.global internal @memo_rgt() {addr_space = 0 : i32} : !llvm.ptr {
%164 = llvm.mlir.zero : !llvm.ptr
llvm.return %164 : !llvm.ptr
}
// Module static: memo_val
llvm.mlir.global internal @memo_val() {addr_space = 0 : i32} : !llvm.ptr {
%165 = llvm.mlir.zero : !llvm.ptr
llvm.return %165 : !llvm.ptr
}
// Module static: memo_used
llvm.mlir.global internal @memo_used() {addr_space = 0 : i32} : !llvm.ptr {
%166 = llvm.mlir.zero : !llvm.ptr
llvm.return %166 : !llvm.ptr
}
// Module static: memo_cap
llvm.mlir.global internal @memo_cap(0 : i64) : i64
// Module static: memo_count
llvm.mlir.global internal @memo_count(0 : i64) : i64
func.func @hash_key(%arg0: i32, %arg1: i32, %arg2: i32, %arg3: i32) -> i64 {
%167 = arith.constant 1469598099639698307 : i32
%168 = arith.extsi %167 : i32 to i64
%169 = llvm.mlir.constant(1 : i64) : i64
%170 = llvm.alloca %169 x i64 : (i64) -> !llvm.ptr
llvm.store %168, %170 : i64, !llvm.ptr
%171 = llvm.load %170 : !llvm.ptr -> i64
%172 = arith.extsi %arg0 : i32 to i64
%173 = arith.xori %171, %172 : i64
llvm.store %173, %170 : i64, !llvm.ptr
%174 = llvm.load %170 : !llvm.ptr -> i64
%175 = arith.constant 1095216660915 : i32
%177 = arith.extsi %175 : i32 to i64
%176 = arith.muli %174, %177 : i64
llvm.store %176, %170 : i64, !llvm.ptr
%178 = llvm.load %170 : !llvm.ptr -> i64
%179 = arith.extsi %arg1 : i32 to i64
%180 = arith.xori %178, %179 : i64
llvm.store %180, %170 : i64, !llvm.ptr
%181 = llvm.load %170 : !llvm.ptr -> i64
%182 = arith.constant 1095216660915 : i32
%184 = arith.extsi %182 : i32 to i64
%183 = arith.muli %181, %184 : i64
llvm.store %183, %170 : i64, !llvm.ptr
%185 = llvm.load %170 : !llvm.ptr -> i64
%186 = arith.extsi %arg2 : i32 to i64
%187 = arith.xori %185, %186 : i64
llvm.store %187, %170 : i64, !llvm.ptr
%188 = llvm.load %170 : !llvm.ptr -> i64
%189 = arith.constant 1095216660915 : i32
%191 = arith.extsi %189 : i32 to i64
%190 = arith.muli %188, %191 : i64
llvm.store %190, %170 : i64, !llvm.ptr
%192 = llvm.load %170 : !llvm.ptr -> i64
%193 = arith.extsi %arg3 : i32 to i64
%194 = arith.xori %192, %193 : i64
llvm.store %194, %170 : i64, !llvm.ptr
%195 = llvm.load %170 : !llvm.ptr -> i64
%196 = arith.constant 1095216660915 : i32
%198 = arith.extsi %196 : i32 to i64
%197 = arith.muli %195, %198 : i64
llvm.store %197, %170 : i64, !llvm.ptr
%199 = llvm.load %170 : !llvm.ptr -> i64
func.return %199 : i64
}
func.func @memo_init(%arg0: i64) -> () {
%200 = llvm.mlir.addressof @memo_cap : !llvm.ptr
llvm.store %arg0, %200 : i64, !llvm.ptr
%201 = arith.constant 0 : i32
%202 = arith.extsi %201 : i32 to i64
%203 = llvm.mlir.addressof @memo_count : !llvm.ptr
llvm.store %202, %203 : i64, !llvm.ptr
%205 = arith.constant 4 : i32
%206 = arith.extsi %205 : i32 to i64
%204 = func.call @calloc(%arg0, %206) : (i64, i64) -> !llvm.ptr
%207 = llvm.mlir.addressof @memo_len : !llvm.ptr
llvm.store %204, %207 : !llvm.ptr, !llvm.ptr
%209 = arith.constant 4 : i32
%210 = arith.extsi %209 : i32 to i64
%208 = func.call @calloc(%arg0, %210) : (i64, i64) -> !llvm.ptr
%211 = llvm.mlir.addressof @memo_bnd : !llvm.ptr
llvm.store %208, %211 : !llvm.ptr, !llvm.ptr
%213 = arith.constant 4 : i32
%214 = arith.extsi %213 : i32 to i64
%212 = func.call @calloc(%arg0, %214) : (i64, i64) -> !llvm.ptr
%215 = llvm.mlir.addressof @memo_lft : !llvm.ptr
llvm.store %212, %215 : !llvm.ptr, !llvm.ptr
%217 = arith.constant 4 : i32
%218 = arith.extsi %217 : i32 to i64
%216 = func.call @calloc(%arg0, %218) : (i64, i64) -> !llvm.ptr
%219 = llvm.mlir.addressof @memo_rgt : !llvm.ptr
llvm.store %216, %219 : !llvm.ptr, !llvm.ptr
%221 = arith.constant 8 : i32
%222 = arith.extsi %221 : i32 to i64
%220 = func.call @calloc(%arg0, %222) : (i64, i64) -> !llvm.ptr
%223 = llvm.mlir.addressof @memo_val : !llvm.ptr
llvm.store %220, %223 : !llvm.ptr, !llvm.ptr
%225 = arith.constant 1 : i32
%226 = arith.extsi %225 : i32 to i64
%224 = func.call @calloc(%arg0, %226) : (i64, i64) -> !llvm.ptr
%227 = llvm.mlir.addressof @memo_used : !llvm.ptr
llvm.store %224, %227 : !llvm.ptr, !llvm.ptr
func.return
}
func.func @memo_lookup(%arg0: i32, %arg1: i32, %arg2: i32, %arg3: i32, %arg4: !llvm.ptr) -> i32 {
%228 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%229 = llvm.load %228 : !llvm.ptr -> i64
%230 = arith.constant 0 : i32
%232 = arith.extsi %230 : i32 to i64
%231 = arith.cmpi eq, %229, %232 : i64
cf.cond_br %231, ^bb39, ^bb40
^bb39:
%233 = arith.constant 0 : i32
func.return %233 : i32
^bb40:
cf.br ^bb41
^bb41:
%234 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%235 = llvm.load %234 : !llvm.ptr -> i64
%236 = arith.constant 1 : i32
%238 = arith.extsi %236 : i32 to i64
%237 = arith.subi %235, %238 : i64
%239 = func.call @hash_key(%arg0, %arg1, %arg2, %arg3) : (i32, i32, i32, i32) -> i64
%240 = arith.andi %239, %237 : i64
%241 = llvm.mlir.constant(1 : i64) : i64
%242 = llvm.alloca %241 x i64 : (i64) -> !llvm.ptr
llvm.store %240, %242 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%244 = llvm.mlir.addressof @memo_used : !llvm.ptr
%245 = llvm.load %244 : !llvm.ptr -> !llvm.ptr
%246 = llvm.load %242 : !llvm.ptr -> i64
%247 = llvm.getelementptr %245[%246] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%243 = llvm.load %247 : !llvm.ptr -> i8
%248 = arith.constant 0 : i32
%250 = arith.extsi %243 : i8 to i32
%249 = arith.cmpi ne, %250, %248 : i32
cf.cond_br %249, ^bb43, ^bb44
^bb43:
%252 = llvm.mlir.addressof @memo_len : !llvm.ptr
%253 = llvm.load %252 : !llvm.ptr -> !llvm.ptr
%254 = llvm.load %242 : !llvm.ptr -> i64
%255 = llvm.getelementptr %253[%254] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%251 = llvm.load %255 : !llvm.ptr -> i32
%256 = arith.cmpi eq, %251, %arg0 : i32
%257 = scf.if %256 -> (i1) {
%259 = llvm.mlir.addressof @memo_bnd : !llvm.ptr
%260 = llvm.load %259 : !llvm.ptr -> !llvm.ptr
%261 = llvm.load %242 : !llvm.ptr -> i64
%262 = llvm.getelementptr %260[%261] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%258 = llvm.load %262 : !llvm.ptr -> i32
%263 = arith.cmpi eq, %258, %arg1 : i32
scf.yield %263 : i1
} else {
%264 = arith.constant false
scf.yield %264 : i1
}
%265 = scf.if %257 -> (i1) {
%267 = llvm.mlir.addressof @memo_lft : !llvm.ptr
%268 = llvm.load %267 : !llvm.ptr -> !llvm.ptr
%269 = llvm.load %242 : !llvm.ptr -> i64
%270 = llvm.getelementptr %268[%269] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%266 = llvm.load %270 : !llvm.ptr -> i32
%271 = arith.cmpi eq, %266, %arg2 : i32
scf.yield %271 : i1
} else {
%272 = arith.constant false
scf.yield %272 : i1
}
%273 = scf.if %265 -> (i1) {
%275 = llvm.mlir.addressof @memo_rgt : !llvm.ptr
%276 = llvm.load %275 : !llvm.ptr -> !llvm.ptr
%277 = llvm.load %242 : !llvm.ptr -> i64
%278 = llvm.getelementptr %276[%277] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%274 = llvm.load %278 : !llvm.ptr -> i32
%279 = arith.cmpi eq, %274, %arg3 : i32
scf.yield %279 : i1
} else {
%280 = arith.constant false
scf.yield %280 : i1
}
cf.cond_br %273, ^bb45, ^bb46
^bb45:
%282 = llvm.mlir.addressof @memo_val : !llvm.ptr
%283 = llvm.load %282 : !llvm.ptr -> !llvm.ptr
%284 = llvm.load %242 : !llvm.ptr -> i64
%285 = llvm.getelementptr %283[%284] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%281 = llvm.load %285 : !llvm.ptr -> i64
%286 = arith.constant 0 : i32
%287 = arith.extsi %286 : i32 to i64
%288 = llvm.getelementptr %arg4[%287] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %281, %288 : i64, !llvm.ptr
%289 = arith.constant 1 : i32
func.return %289 : i32
^bb46:
cf.br ^bb47
^bb47:
%290 = llvm.load %242 : !llvm.ptr -> i64
%291 = arith.constant 1 : i32
%293 = arith.extsi %291 : i32 to i64
%292 = arith.addi %290, %293 : i64
%294 = arith.andi %292, %237 : i64
llvm.store %294, %242 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%295 = arith.constant 0 : i32
func.return %295 : i32
}
func.func @memo_insert_raw(%arg0: i32, %arg1: i32, %arg2: i32, %arg3: i32, %arg4: i64) -> () {
%296 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%297 = llvm.load %296 : !llvm.ptr -> i64
%298 = arith.constant 1 : i32
%300 = arith.extsi %298 : i32 to i64
%299 = arith.subi %297, %300 : i64
%301 = func.call @hash_key(%arg0, %arg1, %arg2, %arg3) : (i32, i32, i32, i32) -> i64
%302 = arith.andi %301, %299 : i64
%303 = llvm.mlir.constant(1 : i64) : i64
%304 = llvm.alloca %303 x i64 : (i64) -> !llvm.ptr
llvm.store %302, %304 : i64, !llvm.ptr
cf.br ^bb48
^bb48:
%306 = llvm.mlir.addressof @memo_used : !llvm.ptr
%307 = llvm.load %306 : !llvm.ptr -> !llvm.ptr
%308 = llvm.load %304 : !llvm.ptr -> i64
%309 = llvm.getelementptr %307[%308] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%305 = llvm.load %309 : !llvm.ptr -> i8
%310 = arith.constant 0 : i32
%312 = arith.extsi %305 : i8 to i32
%311 = arith.cmpi ne, %312, %310 : i32
cf.cond_br %311, ^bb49, ^bb50
^bb49:
%313 = llvm.load %304 : !llvm.ptr -> i64
%314 = arith.constant 1 : i32
%316 = arith.extsi %314 : i32 to i64
%315 = arith.addi %313, %316 : i64
%317 = arith.andi %315, %299 : i64
llvm.store %317, %304 : i64, !llvm.ptr
cf.br ^bb48
^bb50:
%318 = arith.constant 1 : i32
%319 = llvm.mlir.addressof @memo_used : !llvm.ptr
%320 = llvm.load %319 : !llvm.ptr -> !llvm.ptr
%321 = llvm.load %304 : !llvm.ptr -> i64
%322 = arith.trunci %318 : i32 to i8
%323 = llvm.getelementptr %320[%321] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %322, %323 : i8, !llvm.ptr
%324 = llvm.mlir.addressof @memo_len : !llvm.ptr
%325 = llvm.load %324 : !llvm.ptr -> !llvm.ptr
%326 = llvm.load %304 : !llvm.ptr -> i64
%327 = llvm.getelementptr %325[%326] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %arg0, %327 : i32, !llvm.ptr
%328 = llvm.mlir.addressof @memo_bnd : !llvm.ptr
%329 = llvm.load %328 : !llvm.ptr -> !llvm.ptr
%330 = llvm.load %304 : !llvm.ptr -> i64
%331 = llvm.getelementptr %329[%330] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %arg1, %331 : i32, !llvm.ptr
%332 = llvm.mlir.addressof @memo_lft : !llvm.ptr
%333 = llvm.load %332 : !llvm.ptr -> !llvm.ptr
%334 = llvm.load %304 : !llvm.ptr -> i64
%335 = llvm.getelementptr %333[%334] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %arg2, %335 : i32, !llvm.ptr
%336 = llvm.mlir.addressof @memo_rgt : !llvm.ptr
%337 = llvm.load %336 : !llvm.ptr -> !llvm.ptr
%338 = llvm.load %304 : !llvm.ptr -> i64
%339 = llvm.getelementptr %337[%338] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %arg3, %339 : i32, !llvm.ptr
%340 = llvm.mlir.addressof @memo_val : !llvm.ptr
%341 = llvm.load %340 : !llvm.ptr -> !llvm.ptr
%342 = llvm.load %304 : !llvm.ptr -> i64
%343 = llvm.getelementptr %341[%342] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg4, %343 : i64, !llvm.ptr
%344 = llvm.mlir.addressof @memo_count : !llvm.ptr
%345 = llvm.load %344 : !llvm.ptr -> i64
%346 = arith.constant 1 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.addi %345, %348 : i64
%349 = llvm.mlir.addressof @memo_count : !llvm.ptr
llvm.store %347, %349 : i64, !llvm.ptr
func.return
}
func.func @memo_grow() -> () {
%350 = llvm.mlir.addressof @memo_len : !llvm.ptr
%351 = llvm.load %350 : !llvm.ptr -> !llvm.ptr
%352 = llvm.mlir.addressof @memo_bnd : !llvm.ptr
%353 = llvm.load %352 : !llvm.ptr -> !llvm.ptr
%354 = llvm.mlir.addressof @memo_lft : !llvm.ptr
%355 = llvm.load %354 : !llvm.ptr -> !llvm.ptr
%356 = llvm.mlir.addressof @memo_rgt : !llvm.ptr
%357 = llvm.load %356 : !llvm.ptr -> !llvm.ptr
%358 = llvm.mlir.addressof @memo_val : !llvm.ptr
%359 = llvm.load %358 : !llvm.ptr -> !llvm.ptr
%360 = llvm.mlir.addressof @memo_used : !llvm.ptr
%361 = llvm.load %360 : !llvm.ptr -> !llvm.ptr
%362 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%363 = llvm.load %362 : !llvm.ptr -> i64
%364 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%365 = llvm.load %364 : !llvm.ptr -> i64
%366 = arith.constant 2 : i32
%368 = arith.extsi %366 : i32 to i64
%367 = arith.muli %365, %368 : i64
%369 = llvm.mlir.addressof @memo_cap : !llvm.ptr
llvm.store %367, %369 : i64, !llvm.ptr
%371 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%372 = llvm.load %371 : !llvm.ptr -> i64
%373 = arith.constant 4 : i32
%374 = arith.extsi %373 : i32 to i64
%370 = func.call @calloc(%372, %374) : (i64, i64) -> !llvm.ptr
%375 = llvm.mlir.addressof @memo_len : !llvm.ptr
llvm.store %370, %375 : !llvm.ptr, !llvm.ptr
%377 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%378 = llvm.load %377 : !llvm.ptr -> i64
%379 = arith.constant 4 : i32
%380 = arith.extsi %379 : i32 to i64
%376 = func.call @calloc(%378, %380) : (i64, i64) -> !llvm.ptr
%381 = llvm.mlir.addressof @memo_bnd : !llvm.ptr
llvm.store %376, %381 : !llvm.ptr, !llvm.ptr
%383 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%384 = llvm.load %383 : !llvm.ptr -> i64
%385 = arith.constant 4 : i32
%386 = arith.extsi %385 : i32 to i64
%382 = func.call @calloc(%384, %386) : (i64, i64) -> !llvm.ptr
%387 = llvm.mlir.addressof @memo_lft : !llvm.ptr
llvm.store %382, %387 : !llvm.ptr, !llvm.ptr
%389 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%390 = llvm.load %389 : !llvm.ptr -> i64
%391 = arith.constant 4 : i32
%392 = arith.extsi %391 : i32 to i64
%388 = func.call @calloc(%390, %392) : (i64, i64) -> !llvm.ptr
%393 = llvm.mlir.addressof @memo_rgt : !llvm.ptr
llvm.store %388, %393 : !llvm.ptr, !llvm.ptr
%395 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%396 = llvm.load %395 : !llvm.ptr -> i64
%397 = arith.constant 8 : i32
%398 = arith.extsi %397 : i32 to i64
%394 = func.call @calloc(%396, %398) : (i64, i64) -> !llvm.ptr
%399 = llvm.mlir.addressof @memo_val : !llvm.ptr
llvm.store %394, %399 : !llvm.ptr, !llvm.ptr
%401 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%402 = llvm.load %401 : !llvm.ptr -> i64
%403 = arith.constant 1 : i32
%404 = arith.extsi %403 : i32 to i64
%400 = func.call @calloc(%402, %404) : (i64, i64) -> !llvm.ptr
%405 = llvm.mlir.addressof @memo_used : !llvm.ptr
llvm.store %400, %405 : !llvm.ptr, !llvm.ptr
%406 = arith.constant 0 : i32
%407 = arith.extsi %406 : i32 to i64
%408 = llvm.mlir.addressof @memo_count : !llvm.ptr
llvm.store %407, %408 : i64, !llvm.ptr
%409 = arith.constant 0 : i32
%410 = arith.extsi %409 : i32 to i64
%411 = llvm.mlir.constant(1 : i64) : i64
%412 = llvm.alloca %411 x i64 : (i64) -> !llvm.ptr
llvm.store %410, %412 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%413 = llvm.load %412 : !llvm.ptr -> i64
%414 = arith.cmpi slt, %413, %363 : i64
cf.cond_br %414, ^bb52, ^bb53
^bb52:
%416 = llvm.load %412 : !llvm.ptr -> i64
%417 = llvm.getelementptr %361[%416] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%415 = llvm.load %417 : !llvm.ptr -> i8
%418 = arith.constant 0 : i32
%420 = arith.extsi %415 : i8 to i32
%419 = arith.cmpi ne, %420, %418 : i32
cf.cond_br %419, ^bb54, ^bb55
^bb54:
%423 = llvm.load %412 : !llvm.ptr -> i64
%424 = llvm.getelementptr %351[%423] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%422 = llvm.load %424 : !llvm.ptr -> i32
%426 = llvm.load %412 : !llvm.ptr -> i64
%427 = llvm.getelementptr %353[%426] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%425 = llvm.load %427 : !llvm.ptr -> i32
%429 = llvm.load %412 : !llvm.ptr -> i64
%430 = llvm.getelementptr %355[%429] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%428 = llvm.load %430 : !llvm.ptr -> i32
%432 = llvm.load %412 : !llvm.ptr -> i64
%433 = llvm.getelementptr %357[%432] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%431 = llvm.load %433 : !llvm.ptr -> i32
%435 = llvm.load %412 : !llvm.ptr -> i64
%436 = llvm.getelementptr %359[%435] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%434 = llvm.load %436 : !llvm.ptr -> i64
func.call @memo_insert_raw(%422, %425, %428, %431, %434) : (i32, i32, i32, i32, i64) -> ()
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%437 = llvm.load %412 : !llvm.ptr -> i64
%438 = arith.constant 1 : i32
%440 = arith.extsi %438 : i32 to i64
%439 = arith.addi %437, %440 : i64
llvm.store %439, %412 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
func.call @free(%351) : (!llvm.ptr) -> ()
func.call @free(%353) : (!llvm.ptr) -> ()
func.call @free(%355) : (!llvm.ptr) -> ()
func.call @free(%357) : (!llvm.ptr) -> ()
func.call @free(%359) : (!llvm.ptr) -> ()
func.call @free(%361) : (!llvm.ptr) -> ()
func.return
}
func.func @memo_put(%arg0: i32, %arg1: i32, %arg2: i32, %arg3: i32, %arg4: i64) -> () {
%447 = llvm.mlir.addressof @memo_count : !llvm.ptr
%448 = llvm.load %447 : !llvm.ptr -> i64
%449 = arith.constant 10 : i32
%451 = arith.extsi %449 : i32 to i64
%450 = arith.muli %448, %451 : i64
%452 = llvm.mlir.addressof @memo_cap : !llvm.ptr
%453 = llvm.load %452 : !llvm.ptr -> i64
%454 = arith.constant 7 : i32
%456 = arith.extsi %454 : i32 to i64
%455 = arith.muli %453, %456 : i64
%457 = arith.cmpi sge, %450, %455 : i64
cf.cond_br %457, ^bb57, ^bb58
^bb57:
func.call @memo_grow() : () -> ()
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
func.call @memo_insert_raw(%arg0, %arg1, %arg2, %arg3, %arg4) : (i32, i32, i32, i32, i64) -> ()
func.return
}
func.func @D(%arg0: i32, %arg1: i32, %arg2: i32, %arg3: i32) -> i64 {
%460 = func.call @boundary_is_impossible(%arg2) : (i32) -> i32
%461 = arith.constant 0 : i32
%462 = arith.cmpi ne, %460, %461 : i32
%463 = scf.if %462 -> (i1) {
%464 = arith.constant true
scf.yield %464 : i1
} else {
%465 = func.call @boundary_is_impossible(%arg3) : (i32) -> i32
%466 = arith.constant 0 : i32
%467 = arith.cmpi ne, %465, %466 : i32
scf.yield %467 : i1
}
cf.cond_br %463, ^bb60, ^bb61
^bb60:
%468 = arith.constant 0 : i32
%469 = arith.extsi %468 : i32 to i64
func.return %469 : i64
^bb61:
cf.br ^bb62
^bb62:
%470 = arith.constant 0 : i32
%471 = arith.cmpi eq, %arg0, %470 : i32
cf.cond_br %471, ^bb63, ^bb64
^bb63:
%472 = llvm.mlir.addressof @TOP : !llvm.ptr
%473 = llvm.load %472 : !llvm.ptr -> i32
%474 = arith.cmpi eq, %arg2, %473 : i32
%475 = scf.if %474 -> (i1) {
%476 = llvm.mlir.addressof @TOP : !llvm.ptr
%477 = llvm.load %476 : !llvm.ptr -> i32
%478 = arith.cmpi eq, %arg3, %477 : i32
scf.yield %478 : i1
} else {
%479 = arith.constant false
scf.yield %479 : i1
}
cf.cond_br %475, ^bb66, ^bb67
^bb66:
%480 = arith.constant 1 : i32
%481 = arith.extsi %480 : i32 to i64
func.return %481 : i64
^bb67:
cf.br ^bb68
^bb68:
%482 = arith.constant 0 : i32
%483 = arith.extsi %482 : i32 to i64
func.return %483 : i64
^bb64:
cf.br ^bb65
^bb65:
%484 = arith.constant 1 : i32
%485 = arith.cmpi sle, %arg1, %484 : i32
cf.cond_br %485, ^bb69, ^bb70
^bb69:
%486 = arith.constant 1 : i32
%487 = arith.cmpi eq, %arg0, %486 : i32
cf.cond_br %487, ^bb72, ^bb73
^bb72:
%488 = arith.constant 0 : i32
%489 = arith.extsi %488 : i32 to i64
%490 = llvm.mlir.constant(1 : i64) : i64
%491 = llvm.alloca %490 x i64 : (i64) -> !llvm.ptr
llvm.store %489, %491 : i64, !llvm.ptr
%492 = arith.constant 0 : i32
%493 = arith.extsi %492 : i32 to i64
%494 = llvm.mlir.constant(1 : i64) : i64
%495 = llvm.alloca %494 x i64 : (i64) -> !llvm.ptr
llvm.store %493, %495 : i64, !llvm.ptr
cf.br ^bb75
^bb75:
%496 = llvm.load %495 : !llvm.ptr -> i64
%497 = arith.extsi %arg1 : i32 to i64
%498 = arith.cmpi sle, %496, %497 : i64
cf.cond_br %498, ^bb76, ^bb77
^bb76:
%500 = llvm.load %495 : !llvm.ptr -> i64
%499 = func.call @satisfies(%arg2, %500) : (i32, i64) -> i32
%501 = arith.constant 0 : i32
%502 = arith.cmpi ne, %499, %501 : i32
%503 = scf.if %502 -> (i1) {
%505 = llvm.load %495 : !llvm.ptr -> i64
%504 = func.call @satisfies(%arg3, %505) : (i32, i64) -> i32
%506 = arith.constant 0 : i32
%507 = arith.cmpi ne, %504, %506 : i32
scf.yield %507 : i1
} else {
%508 = arith.constant false
scf.yield %508 : i1
}
cf.cond_br %503, ^bb78, ^bb79
^bb78:
%509 = llvm.load %491 : !llvm.ptr -> i64
%510 = arith.constant 1 : i32
%512 = arith.extsi %510 : i32 to i64
%511 = arith.addi %509, %512 : i64
llvm.store %511, %491 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%513 = llvm.load %495 : !llvm.ptr -> i64
%514 = arith.constant 1 : i32
%516 = arith.extsi %514 : i32 to i64
%515 = arith.addi %513, %516 : i64
llvm.store %515, %495 : i64, !llvm.ptr
cf.br ^bb75
^bb77:
%517 = llvm.load %491 : !llvm.ptr -> i64
func.return %517 : i64
^bb73:
cf.br ^bb74
^bb74:
%518 = arith.constant 0 : i32
%519 = arith.cmpi eq, %arg1, %518 : i32
cf.cond_br %519, ^bb81, ^bb82
^bb81:
%520 = arith.constant 0 : i32
%521 = arith.extsi %520 : i32 to i64
func.return %521 : i64
^bb82:
cf.br ^bb83
^bb83:
%523 = arith.constant 1 : i32
%524 = arith.extsi %523 : i32 to i64
%522 = func.call @satisfies(%arg2, %524) : (i32, i64) -> i32
%525 = arith.constant 0 : i32
%526 = arith.cmpi ne, %522, %525 : i32
%527 = scf.if %526 -> (i1) {
%529 = arith.constant 1 : i32
%530 = arith.extsi %529 : i32 to i64
%528 = func.call @satisfies(%arg3, %530) : (i32, i64) -> i32
%531 = arith.constant 0 : i32
%532 = arith.cmpi ne, %528, %531 : i32
scf.yield %532 : i1
} else {
%533 = arith.constant false
scf.yield %533 : i1
}
cf.cond_br %527, ^bb84, ^bb85
^bb84:
%534 = arith.constant 1 : i32
%535 = arith.extsi %534 : i32 to i64
func.return %535 : i64
^bb85:
cf.br ^bb86
^bb86:
%536 = arith.constant 0 : i32
%537 = arith.extsi %536 : i32 to i64
func.return %537 : i64
^bb70:
cf.br ^bb71
^bb71:
%539 = arith.constant 1 : i32
%540 = arith.constant 8 : i32
%541 = arith.extsi %539 : i32 to i64
%542 = arith.extsi %540 : i32 to i64
%538 = func.call @calloc(%541, %542) : (i64, i64) -> !llvm.ptr
%543 = func.call @memo_lookup(%arg0, %arg1, %arg2, %arg3, %538) : (i32, i32, i32, i32, !llvm.ptr) -> i32
%544 = arith.constant 0 : i32
%545 = arith.cmpi ne, %543, %544 : i32
cf.cond_br %545, ^bb87, ^bb88
^bb87:
%547 = arith.constant 0 : i32
%548 = arith.extsi %547 : i32 to i64
%549 = llvm.getelementptr %538[%548] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%546 = llvm.load %549 : !llvm.ptr -> i64
func.call @free(%538) : (!llvm.ptr) -> ()
func.return %546 : i64
^bb88:
cf.br ^bb89
^bb89:
func.call @free(%538) : (!llvm.ptr) -> ()
%552 = arith.constant 0 : i32
%553 = arith.extsi %552 : i32 to i64
%554 = llvm.mlir.constant(1 : i64) : i64
%555 = llvm.alloca %554 x i64 : (i64) -> !llvm.ptr
llvm.store %553, %555 : i64, !llvm.ptr
%556 = arith.constant 2 : i32
%557 = arith.remsi %arg1, %556 : i32
%558 = arith.constant 0 : i32
%559 = arith.cmpi eq, %557, %558 : i32
cf.cond_br %559, ^bb90, ^bb91
^bb90:
%561 = arith.constant 1 : i32
%562 = arith.subi %arg1, %561 : i32
%560 = func.call @D(%arg0, %562, %arg2, %arg3) : (i32, i32, i32, i32) -> i64
llvm.store %560, %555 : i64, !llvm.ptr
%563 = arith.constant 1 : i32
%564 = llvm.mlir.constant(1 : i64) : i64
%565 = llvm.alloca %564 x i32 : (i64) -> !llvm.ptr
llvm.store %563, %565 : i32, !llvm.ptr
cf.br ^bb93
^bb93:
%566 = llvm.load %565 : !llvm.ptr -> i32
%567 = arith.cmpi sle, %566, %arg0 : i32
cf.cond_br %567, ^bb94, ^bb95
^bb94:
%568 = llvm.load %565 : !llvm.ptr -> i32
%569 = arith.constant 1 : i32
%570 = arith.subi %568, %569 : i32
%571 = llvm.load %565 : !llvm.ptr -> i32
%572 = arith.subi %arg0, %571 : i32
%573 = arith.constant 0 : i32
%574 = arith.extsi %573 : i32 to i64
%575 = llvm.mlir.constant(1 : i64) : i64
%576 = llvm.alloca %575 x i64 : (i64) -> !llvm.ptr
llvm.store %574, %576 : i64, !llvm.ptr
%577 = arith.constant 0 : i32
%578 = arith.cmpi eq, %570, %577 : i32
cf.cond_br %578, ^bb96, ^bb97
^bb96:
%580 = arith.extsi %arg1 : i32 to i64
%579 = func.call @satisfies(%arg2, %580) : (i32, i64) -> i32
%581 = arith.constant 0 : i32
%582 = arith.cmpi ne, %579, %581 : i32
cf.cond_br %582, ^bb99, ^bb100
^bb99:
%583 = arith.constant 1 : i32
%584 = arith.extsi %583 : i32 to i64
llvm.store %584, %576 : i64, !llvm.ptr
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
cf.br ^bb98
^bb97:
%586 = arith.constant 1 : i32
%587 = arith.subi %arg1, %586 : i32
%585 = func.call @D(%570, %587, %arg2, %arg1) : (i32, i32, i32, i32) -> i64
llvm.store %585, %576 : i64, !llvm.ptr
cf.br ^bb98
^bb98:
%588 = llvm.load %576 : !llvm.ptr -> i64
%589 = arith.constant 0 : i32
%591 = arith.extsi %589 : i32 to i64
%590 = arith.cmpi ne, %588, %591 : i64
cf.cond_br %590, ^bb102, ^bb103
^bb102:
%592 = arith.constant 0 : i32
%593 = arith.extsi %592 : i32 to i64
%594 = llvm.mlir.constant(1 : i64) : i64
%595 = llvm.alloca %594 x i64 : (i64) -> !llvm.ptr
llvm.store %593, %595 : i64, !llvm.ptr
%596 = arith.constant 0 : i32
%597 = arith.cmpi eq, %572, %596 : i32
cf.cond_br %597, ^bb105, ^bb106
^bb105:
%599 = arith.extsi %arg1 : i32 to i64
%598 = func.call @satisfies(%arg3, %599) : (i32, i64) -> i32
%600 = arith.constant 0 : i32
%601 = arith.cmpi ne, %598, %600 : i32
cf.cond_br %601, ^bb108, ^bb109
^bb108:
%602 = arith.constant 1 : i32
%603 = arith.extsi %602 : i32 to i64
llvm.store %603, %595 : i64, !llvm.ptr
cf.br ^bb110
^bb109:
cf.br ^bb110
^bb110:
cf.br ^bb107
^bb106:
%604 = func.call @D(%572, %arg1, %arg1, %arg3) : (i32, i32, i32, i32) -> i64
llvm.store %604, %595 : i64, !llvm.ptr
cf.br ^bb107
^bb107:
%605 = llvm.load %555 : !llvm.ptr -> i64
%606 = llvm.load %576 : !llvm.ptr -> i64
%607 = llvm.load %595 : !llvm.ptr -> i64
%608 = arith.muli %606, %607 : i64
%609 = arith.addi %605, %608 : i64
%610 = llvm.mlir.addressof @MOD : !llvm.ptr
%611 = llvm.load %610 : !llvm.ptr -> i64
%612 = arith.remsi %609, %611 : i64
llvm.store %612, %555 : i64, !llvm.ptr
cf.br ^bb104
^bb103:
cf.br ^bb104
^bb104:
%613 = llvm.load %565 : !llvm.ptr -> i32
%614 = arith.constant 1 : i32
%615 = arith.addi %613, %614 : i32
llvm.store %615, %565 : i32, !llvm.ptr
cf.br ^bb93
^bb95:
%617 = llvm.load %555 : !llvm.ptr -> i64
func.call @memo_put(%arg0, %arg1, %arg2, %arg3, %617) : (i32, i32, i32, i32, i64) -> ()
%618 = llvm.load %555 : !llvm.ptr -> i64
func.return %618 : i64
^bb91:
cf.br ^bb92
^bb92:
%619 = arith.constant 1 : i32
%620 = arith.subi %arg1, %619 : i32
%621 = arith.constant 2 : i32
%622 = arith.divsi %620, %621 : i32
%623 = func.call @phi_even(%arg2) : (i32) -> i32
%624 = func.call @phi_odd(%arg2) : (i32) -> i32
%625 = func.call @phi_even(%arg3) : (i32) -> i32
%626 = func.call @phi_odd(%arg3) : (i32) -> i32
%627 = func.call @D(%arg0, %622, %623, %625) : (i32, i32, i32, i32) -> i64
%628 = func.call @fib(%arg0) : (i32) -> i64
%629 = arith.muli %627, %628 : i64
%630 = llvm.mlir.addressof @MOD : !llvm.ptr
%631 = llvm.load %630 : !llvm.ptr -> i64
%632 = arith.remsi %629, %631 : i64
llvm.store %632, %555 : i64, !llvm.ptr
%633 = llvm.load %555 : !llvm.ptr -> i64
%634 = func.call @D(%arg0, %622, %623, %626) : (i32, i32, i32, i32) -> i64
%636 = arith.constant 1 : i32
%637 = arith.subi %arg0, %636 : i32
%635 = func.call @fib(%637) : (i32) -> i64
%638 = arith.muli %634, %635 : i64
%639 = arith.addi %633, %638 : i64
%640 = llvm.mlir.addressof @MOD : !llvm.ptr
%641 = llvm.load %640 : !llvm.ptr -> i64
%642 = arith.remsi %639, %641 : i64
llvm.store %642, %555 : i64, !llvm.ptr
%643 = llvm.load %555 : !llvm.ptr -> i64
%644 = func.call @D(%arg0, %622, %624, %625) : (i32, i32, i32, i32) -> i64
%646 = arith.constant 1 : i32
%647 = arith.subi %arg0, %646 : i32
%645 = func.call @fib(%647) : (i32) -> i64
%648 = arith.muli %644, %645 : i64
%649 = arith.addi %643, %648 : i64
%650 = llvm.mlir.addressof @MOD : !llvm.ptr
%651 = llvm.load %650 : !llvm.ptr -> i64
%652 = arith.remsi %649, %651 : i64
llvm.store %652, %555 : i64, !llvm.ptr
%653 = llvm.load %555 : !llvm.ptr -> i64
%654 = func.call @D(%arg0, %622, %624, %626) : (i32, i32, i32, i32) -> i64
%656 = arith.constant 2 : i32
%657 = arith.subi %arg0, %656 : i32
%655 = func.call @fib(%657) : (i32) -> i64
%658 = arith.muli %654, %655 : i64
%659 = arith.addi %653, %658 : i64
%660 = llvm.mlir.addressof @MOD : !llvm.ptr
%661 = llvm.load %660 : !llvm.ptr -> i64
%662 = arith.remsi %659, %661 : i64
llvm.store %662, %555 : i64, !llvm.ptr
%663 = llvm.load %555 : !llvm.ptr -> i64
%664 = llvm.mlir.addressof @MOD : !llvm.ptr
%665 = llvm.load %664 : !llvm.ptr -> i64
%666 = arith.remsi %663, %665 : i64
llvm.store %666, %555 : i64, !llvm.ptr
%667 = arith.constant 1 : i32
%668 = llvm.mlir.constant(1 : i64) : i64
%669 = llvm.alloca %668 x i32 : (i64) -> !llvm.ptr
llvm.store %667, %669 : i32, !llvm.ptr
cf.br ^bb111
^bb111:
%670 = llvm.load %669 : !llvm.ptr -> i32
%671 = arith.cmpi slt, %670, %arg0 : i32
cf.cond_br %671, ^bb112, ^bb113
^bb112:
%673 = llvm.load %669 : !llvm.ptr -> i32
%674 = llvm.mlir.addressof @TOP : !llvm.ptr
%675 = llvm.load %674 : !llvm.ptr -> i32
%672 = func.call @D(%673, %622, %624, %675) : (i32, i32, i32, i32) -> i64
%677 = llvm.load %669 : !llvm.ptr -> i32
%678 = arith.constant 2 : i32
%679 = arith.subi %677, %678 : i32
%676 = func.call @fib(%679) : (i32) -> i64
%680 = arith.muli %672, %676 : i64
%681 = llvm.mlir.addressof @MOD : !llvm.ptr
%682 = llvm.load %681 : !llvm.ptr -> i64
%683 = arith.remsi %680, %682 : i64
%684 = llvm.mlir.constant(1 : i64) : i64
%685 = llvm.alloca %684 x i64 : (i64) -> !llvm.ptr
llvm.store %683, %685 : i64, !llvm.ptr
%686 = llvm.load %669 : !llvm.ptr -> i32
%687 = arith.constant 1 : i32
%688 = arith.cmpi sgt, %686, %687 : i32
cf.cond_br %688, ^bb114, ^bb115
^bb114:
%689 = llvm.load %685 : !llvm.ptr -> i64
%691 = llvm.load %669 : !llvm.ptr -> i32
%692 = llvm.mlir.addressof @TOP : !llvm.ptr
%693 = llvm.load %692 : !llvm.ptr -> i32
%690 = func.call @D(%691, %622, %623, %693) : (i32, i32, i32, i32) -> i64
%695 = llvm.load %669 : !llvm.ptr -> i32
%696 = arith.constant 1 : i32
%697 = arith.subi %695, %696 : i32
%694 = func.call @fib(%697) : (i32) -> i64
%698 = arith.muli %690, %694 : i64
%699 = arith.addi %689, %698 : i64
%700 = llvm.mlir.addressof @MOD : !llvm.ptr
%701 = llvm.load %700 : !llvm.ptr -> i64
%702 = arith.remsi %699, %701 : i64
llvm.store %702, %685 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
%703 = llvm.load %685 : !llvm.ptr -> i64
%704 = arith.constant 0 : i32
%706 = arith.extsi %704 : i32 to i64
%705 = arith.cmpi ne, %703, %706 : i64
cf.cond_br %705, ^bb117, ^bb118
^bb117:
%707 = llvm.load %555 : !llvm.ptr -> i64
%709 = llvm.load %669 : !llvm.ptr -> i32
%710 = arith.subi %arg0, %709 : i32
%711 = llvm.mlir.addressof @ODD : !llvm.ptr
%712 = llvm.load %711 : !llvm.ptr -> i32
%708 = func.call @D(%710, %arg1, %712, %arg3) : (i32, i32, i32, i32) -> i64
%713 = llvm.load %685 : !llvm.ptr -> i64
%714 = arith.muli %708, %713 : i64
%715 = arith.addi %707, %714 : i64
%716 = llvm.mlir.addressof @MOD : !llvm.ptr
%717 = llvm.load %716 : !llvm.ptr -> i64
%718 = arith.remsi %715, %717 : i64
llvm.store %718, %555 : i64, !llvm.ptr
cf.br ^bb119
^bb118:
cf.br ^bb119
^bb119:
%719 = llvm.load %669 : !llvm.ptr -> i32
%720 = arith.constant 1 : i32
%721 = arith.addi %719, %720 : i32
llvm.store %721, %669 : i32, !llvm.ptr
cf.br ^bb111
^bb113:
%723 = llvm.load %555 : !llvm.ptr -> i64
func.call @memo_put(%arg0, %arg1, %arg2, %arg3, %723) : (i32, i32, i32, i32, i64) -> ()
%724 = llvm.load %555 : !llvm.ptr -> i64
func.return %724 : i64
}
func.func @c_func(%arg0: i32, %arg1: i32) -> i64 {
%726 = llvm.mlir.addressof @TOP : !llvm.ptr
%727 = llvm.load %726 : !llvm.ptr -> i32
%728 = llvm.mlir.addressof @TOP : !llvm.ptr
%729 = llvm.load %728 : !llvm.ptr -> i32
%725 = func.call @D(%arg0, %arg1, %727, %729) : (i32, i32, i32, i32) -> i64
func.return %725 : i64
}
func.func @main() -> i32 {
func.call @init_fib() : () -> ()
%732 = arith.constant 1 : i32
%733 = arith.constant 16 : i32
%734 = arith.shli %732, %733 : i32
%735 = arith.extsi %734 : i32 to i64
func.call @memo_init(%735) : (i64) -> ()
%736 = llvm.mlir.addressof @str_0 : !llvm.ptr
%738 = arith.constant 123 : i32
%739 = arith.constant 123456789 : i32
%737 = func.call @c_func(%738, %739) : (i32, i32) -> i64
%740 = llvm.call @printf(%736, %737) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%741 = arith.constant 0 : i32
func.return %741 : i32
}
}