Problem 844
k-Markov Numbers - S(10^18, 10^18) mod 1405695061.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n) | O(n * s^2) |
|---|
| Space complexity | O(n^2) | O(s^2) |
|---|
| Approach | Flow solution | Markov chain or DP over states |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 844
# k-Markov Numbers - S(10^18, 10^18) mod 1405695061.
import euler.nt { isqrt }
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memset(p: ptr<void>, c: i32, n: i64) -> ptr<void>
}
const MOD: i64 = 1405695061
const MAX_NONONES: i64 = 8
const HT_CAP: i64 = 2048
const SN_CAP: i64 = 4096
const STK_CAP: i64 = 4096
let mut N_val: i64 = 0
function mmul(a: i64, b: i64) -> i64 {
return ((a as i128) * (b as i128) % (MOD as i128)) as i64
}
function madd(a: i64, b: i64) -> i64 {
return (a + b) % MOD
}
function msub(a: i64, b: i64) -> i64 {
return (a - b % MOD + MOD) % MOD
}
function modpow(base0: i64, exp0: i64, mod0: i64) -> i64 {
let mut r: i64 = 1
let mut base: i64 = base0 % mod0
let mut exp: i64 = exp0
while exp > 0 {
if (exp & 1) != 0 {
r = ((r as i128) * (base as i128) % (mod0 as i128)) as i64
}
base = ((base as i128) * (base as i128) % (mod0 as i128)) as i64
exp = exp >> 1
}
return r
}
function msum1(n: i64) -> i64 {
if n <= 0 {
return 0
}
let a: i64 = n % MOD
let b: i64 = (n + 1) % MOD
return mmul(mmul(a, b), modpow(2, MOD - 2, MOD))
}
function msum2(n: i64) -> i64 {
if n <= 0 {
return 0
}
let a: i64 = n % MOD
let b: i64 = (n + 1) % MOD
let c: i64 = (2 * n + 1) % MOD
return mmul(mmul(mmul(a, b), c), modpow(6, MOD - 2, MOD))
}
function msum3(n: i64) -> i64 {
if n <= 0 {
return 0
}
let s: i64 = msum1(n)
return mmul(s, s)
}
function rsum1(l: i64, r: i64) -> i64 {
if l > r {
return 0
}
return msub(msum1(r), msum1(l - 1))
}
function rsum2(l: i64, r: i64) -> i64 {
if l > r {
return 0
}
return msub(msum2(r), msum2(l - 1))
}
function rsum3(l: i64, r: i64) -> i64 {
if l > r {
return 0
}
return msub(msum3(r), msum3(l - 1))
}
function poly_m3(k: i64) -> i128 {
let kk: i128 = k as i128
return kk * kk * kk * kk - 2 * kk * kk * kk + kk - 1
}
function poly_a2(k: i64) -> i128 {
let kk: i128 = k as i128
return kk * kk - kk - 1
}
function poly_a3(k: i64) -> i128 {
let kk: i128 = k as i128
return kk * kk * kk - kk * kk - 2 * kk + 1
}
function pred_m3(k: i64) -> bool {
return poly_m3(k) <= (N_val as i128)
}
function pred_a3(k: i64) -> bool {
return poly_a3(k) <= (N_val as i128)
}
function max_k_m3(limit: i64, start: i64) -> i64 {
if limit < start {
return limit
}
if !pred_m3(start) {
return start - 1
}
let mut lo: i64 = start
let mut hi: i64 = start
while hi < limit && pred_m3(hi) {
lo = hi
if hi * 2 > limit {
hi = limit
} else {
hi = hi * 2
}
}
if pred_m3(hi) {
return hi
}
while lo + 1 < hi {
let mid: i64 = (lo + hi) / 2
if pred_m3(mid) {
lo = mid
} else {
hi = mid
}
}
return lo
}
function max_k_a3_inner(limit: i64, start: i64) -> i64 {
if limit < start {
return limit
}
if !pred_a3(start) {
return start - 1
}
let mut lo: i64 = start
let mut hi: i64 = start
while hi < limit && pred_a3(hi) {
lo = hi
if hi * 2 > limit {
hi = limit
} else {
hi = hi * 2
}
}
if pred_a3(hi) {
return hi
}
while lo + 1 < hi {
let mid: i64 = (lo + hi) / 2
if pred_a3(mid) {
lo = mid
} else {
hi = mid
}
}
return lo
}
function max_k_three_nonones(N: i64, K: i64) -> i64 {
if K < 3 {
return K
}
N_val = N
return max_k_m3(K, 3)
}
function max_k_a2(N: i64, K: i64) -> i64 {
if K < 1 {
return 0
}
let disc: i64 = 1 + 4 * (N + 1)
let r0: i64 = (1 + isqrt(disc)) / 2
let mut r: i64 = r0
if r > K {
r = K
}
while r > 0 && poly_a2(r) > (N as i128) {
r = r - 1
}
return r
}
function max_k_a3(N: i64, K: i64) -> i64 {
if K < 3 {
return K
}
if poly_a3(3) > (N as i128) {
return 2
}
N_val = N
let r: i64 = max_k_a3_inner(K, 3)
return r
}
# ---- mk_sum via DFS ----
# State: sorted non-one values (up to 8). Hash table stores vals[0..8] + n.
# Stack stores state vals, n, and prod (i128).
let mut ht_keys: ptr<i64> = null
let mut ht_used: ptr<i8> = null
let mut sn_keys: ptr<i64> = null
let mut sn_used: ptr<i8> = null
let mut stk_state: ptr<i64> = null
let mut stk_n: ptr<i64> = null
let mut stk_prod: ptr<i128> = null
let mut stk_sp: i64 = 0
function hash_state(vals: ptr<i64>, n: i64) -> i64 {
let mut h: i64 = -7046029254386353131
let mut i: i64 = 0
while i < n {
h = h ^ vals[i]
h = h * 1099511628211
i = i + 1
}
if h < 0 {
h = -h
}
return h % HT_CAP
}
function state_eq(a: ptr<i64>, an: i64, b: ptr<i64>, bn: i64) -> bool {
if an != bn {
return false
}
let mut i: i64 = 0
while i < an {
if a[i] != b[i] {
return false
}
i = i + 1
}
return true
}
function state_clear() -> void {
memset(ht_used, 0, HT_CAP)
}
function state_contains(vals: ptr<i64>, n: i64) -> bool {
let h0: i64 = hash_state(vals, n)
let mut h: i64 = h0
while ht_used[h] != 0 {
if state_eq(vals, n, ht_keys + h * 9, ht_keys[h * 9 + 8]) {
return true
}
h = h + 1
if h == HT_CAP {
h = 0
}
}
return false
}
function state_insert(vals: ptr<i64>, n: i64) -> void {
let h0: i64 = hash_state(vals, n)
let mut h: i64 = h0
while ht_used[h] != 0 {
if state_eq(vals, n, ht_keys + h * 9, ht_keys[h * 9 + 8]) {
return
}
h = h + 1
if h == HT_CAP {
h = 0
}
}
ht_used[h] = 1
let mut i: i64 = 0
while i < n {
ht_keys[h * 9 + i] = vals[i]
i = i + 1
}
ht_keys[h * 9 + 8] = n
}
function num_clear() -> void {
memset(sn_used, 0, SN_CAP)
}
function num_contains(v: i64) -> bool {
let mut h: i64 = v % SN_CAP
if h < 0 {
h = -h
}
while sn_used[h] != 0 {
if sn_keys[h] == v {
return true
}
h = h + 1
if h == SN_CAP {
h = 0
}
}
return false
}
function num_insert(v: i64) -> void {
let mut h: i64 = v % SN_CAP
if h < 0 {
h = -h
}
while sn_used[h] != 0 {
if sn_keys[h] == v {
return
}
h = h + 1
if h == SN_CAP {
h = 0
}
}
sn_used[h] = 1
sn_keys[h] = v
}
function mk_sum(k: i64, N: i64, mod0: i64) -> i64 {
if N < 1 {
return 0
}
let mut s: i64 = 1 % mod0
if k - 1 > N {
return s
}
state_clear()
num_clear()
num_insert(1)
stk_sp = 0
# start state: n=0, prod=1
let mut i: i64 = 0
while i < MAX_NONONES {
stk_state[0 * MAX_NONONES + i] = 0
i = i + 1
}
stk_n[0] = 0
stk_prod[0] = 1
stk_sp = 1
state_insert(stk_state + 0 * MAX_NONONES, 0)
let new_vals: ptr<i64> = calloc(MAX_NONONES, 8)
let jump_vals: ptr<i64> = calloc(MAX_NONONES + 1, 8)
while stk_sp > 0 {
stk_sp = stk_sp - 1
let non_ones_n: i64 = stk_n[stk_sp]
let prod_non_ones: i128 = stk_prod[stk_sp]
let ones: i64 = k - non_ones_n
# Save current state to local buffer: pushing new states reuses the
# popped slot, which would overwrite stk_state[base] and corrupt
# subsequent jump-value processing.
let mut cur_state: [i64; 8]
let mut si: i64 = 0
let cur_base: i64 = stk_sp * MAX_NONONES
while si < MAX_NONONES {
cur_state[si] = stk_state[cur_base + si]
si = si + 1
}
# Record coordinates
let mut i2: i64 = 0
while i2 < non_ones_n {
let v: i64 = cur_state[i2]
if v <= N && !num_contains(v) {
num_insert(v)
s = madd(s, v % mod0)
}
i2 = i2 + 1
}
# Collect unique jump values
let mut n_jump: i64 = 0
let mut i3: i64 = 0
while i3 < non_ones_n {
if i3 == 0 || cur_state[i3] != cur_state[i3 - 1] {
jump_vals[n_jump] = cur_state[i3]
n_jump = n_jump + 1
}
i3 = i3 + 1
}
if ones > 0 {
jump_vals[n_jump] = 1
n_jump = n_jump + 1
}
let mut vi: i64 = 0
while vi < n_jump {
let v: i64 = jump_vals[vi]
let new_val: i128 = 0
let new_prod: i128 = 0
let do_insert: bool = false
if v == 1 {
if ones == 0 {
vi = vi + 1
continue
}
if prod_non_ones > ((N + 1) as i128) / (k as i128) {
vi = vi + 1
continue
}
let nv: i128 = (k as i128) * prod_non_ones - 1
if nv <= 1 || nv > (N as i128) {
vi = vi + 1
continue
}
new_val = nv
new_prod = prod_non_ones * nv
} else {
let prod_div_v: i128 = prod_non_ones / (v as i128)
if prod_div_v > ((N + v) as i128) / (k as i128) {
vi = vi + 1
continue
}
let nv: i128 = (k as i128) * prod_div_v - (v as i128)
if nv <= (v as i128) || nv > (N as i128) {
vi = vi + 1
continue
}
new_val = nv
new_prod = prod_div_v * nv
}
# Build new state into new_vals
if v == 1 {
# insert new_val into sorted non_ones
let mut j: i64 = 0
while j < MAX_NONONES {
new_vals[j] = 0
j = j + 1
}
# copy existing state values first
let mut j0: i64 = 0
while j0 < non_ones_n {
new_vals[j0] = cur_state[j0]
j0 = j0 + 1
}
let mut pos: i64 = non_ones_n
let mut j2: i64 = 0
while j2 < non_ones_n {
if new_val < (cur_state[j2] as i128) {
pos = j2
break
}
j2 = j2 + 1
}
let mut j3: i64 = non_ones_n
while j3 > pos {
new_vals[j3] = new_vals[j3 - 1]
j3 = j3 - 1
}
new_vals[pos] = new_val as i64
let new_n: i64 = non_ones_n + 1
if !state_contains(new_vals, new_n) {
state_insert(new_vals, new_n)
let nb: i64 = stk_sp * MAX_NONONES
let mut j4: i64 = 0
while j4 < MAX_NONONES {
stk_state[nb + j4] = new_vals[j4]
j4 = j4 + 1
}
stk_n[stk_sp] = new_n
stk_prod[stk_sp] = new_prod
stk_sp = stk_sp + 1
}
} else {
# replace v with new_val in sorted order
let mut j: i64 = 0
while j < MAX_NONONES {
new_vals[j] = 0
j = j + 1
}
# find and remove v
let mut found: i64 = -1
let mut j2: i64 = 0
while j2 < non_ones_n {
if cur_state[j2] == v {
found = j2
break
}
j2 = j2 + 1
}
if found < 0 {
vi = vi + 1
continue
}
# copy without v
let mut idx: i64 = 0
let mut j3: i64 = 0
while j3 < non_ones_n {
if j3 != found {
new_vals[idx] = cur_state[j3]
idx = idx + 1
}
j3 = j3 + 1
}
let tmp_n: i64 = non_ones_n - 1
# insert new_val into sorted new_vals[0..tmp_n]
let mut pos: i64 = tmp_n
let mut j4: i64 = 0
while j4 < tmp_n {
if new_val < (new_vals[j4] as i128) {
pos = j4
break
}
j4 = j4 + 1
}
let mut j5: i64 = tmp_n
while j5 > pos {
new_vals[j5] = new_vals[j5 - 1]
j5 = j5 - 1
}
new_vals[pos] = new_val as i64
let new_n: i64 = tmp_n + 1
if !state_contains(new_vals, new_n) {
state_insert(new_vals, new_n)
let nb: i64 = stk_sp * MAX_NONONES
let mut j6: i64 = 0
while j6 < MAX_NONONES {
stk_state[nb + j6] = new_vals[j6]
j6 = j6 + 1
}
stk_n[stk_sp] = new_n
stk_prod[stk_sp] = new_prod
stk_sp = stk_sp + 1
}
}
vi = vi + 1
}
}
free(new_vals)
free(jump_vals)
return s % mod0
}
function main() -> i32 {
ht_keys = calloc(HT_CAP * 9, 8)
ht_used = calloc(HT_CAP, 1)
sn_keys = calloc(SN_CAP, 8)
sn_used = calloc(SN_CAP, 1)
stk_state = calloc(STK_CAP * MAX_NONONES, 8)
stk_n = calloc(STK_CAP, 8)
stk_prod = calloc(STK_CAP, 16)
let K: i64 = 1000000000000000000
let N: i64 = 1000000000000000000
let mod0: i64 = MOD
if K < 3 || N < 1 {
printf("%lld\n", 0 as i64)
return 0
}
let K_eff: i64 = if K < N + 1 { K } else { N + 1 }
let mut total: i64 = 0
let m3: i64 = max_k_three_nonones(N, K_eff)
let cutoff: i64 = if K_eff < m3 { K_eff } else { m3 }
# Enumerate exactly for k <= cutoff
let mut k: i64 = 3
while k <= cutoff {
total = madd(total, mk_sum(k, N, mod0))
k = k + 1
}
let start: i64 = cutoff + 1
if start > K_eff {
if K > K_eff {
total = madd(total, (K - K_eff) % mod0)
}
printf("%lld\n", total % mod0)
return 0
}
let k3v: i64 = max_k_a3(N, K_eff)
let k3: i64 = if K_eff < k3v { K_eff } else { k3v }
let k2v: i64 = max_k_a2(N, K_eff)
let k2: i64 = if K_eff < k2v { K_eff } else { k2v }
# Region 1: a3 <= N => M_k = k^3 - 2k
let l1: i64 = start
let r1: i64 = k3
if l1 <= r1 {
let part: i64 = msub(rsum3(l1, r1), mmul(2, rsum1(l1, r1)))
total = madd(total, part)
}
# Region 2: a2 <= N < a3 => M_k = k^2 - 1
let l2: i64 = if start > k3 + 1 { start } else { k3 + 1 }
let r2: i64 = k2
if l2 <= r2 {
let cnt: i64 = (r2 - l2 + 1) % mod0
let part: i64 = msub(rsum2(l2, r2), cnt)
total = madd(total, part)
}
# Region 3: a2 > N => M_k = k
let l3: i64 = if start > k2 + 1 { start } else { k2 + 1 }
let r3: i64 = K_eff
if l3 <= r3 {
let part: i64 = rsum1(l3, r3)
total = madd(total, part)
}
# k > N+1 contributes 1 each
if K > K_eff {
total = madd(total, (K - K_eff) % mod0)
}
printf("%lld\n", total % mod0)
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 gcd_i64_i64(int64_t a0, int64_t b0);
int64_t lcm_i64_i64(int64_t a, int64_t b);
int64_t isqrt_i64(int64_t n);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
bool is_prime_i64(int64_t n);
int64_t mmul_i64_i64(int64_t a, int64_t b);
int64_t madd_i64_i64(int64_t a, int64_t b);
int64_t msub_i64_i64(int64_t a, int64_t b);
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod0);
int64_t msum1_i64(int64_t n);
int64_t msum2_i64(int64_t n);
int64_t msum3_i64(int64_t n);
int64_t rsum1_i64_i64(int64_t l, int64_t r);
int64_t rsum2_i64_i64(int64_t l, int64_t r);
int64_t rsum3_i64_i64(int64_t l, int64_t r);
__int128 poly_m3_i64(int64_t k);
__int128 poly_a2_i64(int64_t k);
__int128 poly_a3_i64(int64_t k);
bool pred_m3_i64(int64_t k);
bool pred_a3_i64(int64_t k);
int64_t max_k_m3_i64_i64(int64_t limit, int64_t start);
int64_t max_k_a3_inner_i64_i64(int64_t limit, int64_t start);
int64_t max_k_three_nonones_i64_i64(int64_t N, int64_t K);
int64_t max_k_a2_i64_i64(int64_t N, int64_t K);
int64_t max_k_a3_i64_i64(int64_t N, int64_t K);
int64_t hash_state_ptr_i64_i64(int64_t* vals, int64_t n);
bool state_eq_ptr_i64_i64_ptr_i64_i64(int64_t* a, int64_t an, int64_t* b, int64_t bn);
void state_clear(void);
bool state_contains_ptr_i64_i64(int64_t* vals, int64_t n);
void state_insert_ptr_i64_i64(int64_t* vals, int64_t n);
void num_clear(void);
bool num_contains_i64(int64_t v);
void num_insert_i64(int64_t v);
int64_t mk_sum_i64_i64_i64(int64_t k, int64_t N, int64_t mod0);
int32_t main(void);
static const int64_t MOD = 1405695061;
static const int64_t MAX_NONONES = 8;
static const int64_t HT_CAP = 2048;
static const int64_t SN_CAP = 4096;
static const int64_t STK_CAP = 4096;
/* Module statics */
static int64_t N_val = 0;
static int64_t* ht_keys = NULL;
static int8_t* ht_used = NULL;
static int64_t* sn_keys = NULL;
static int8_t* sn_used = NULL;
static int64_t* stk_state = NULL;
static int64_t* stk_n = NULL;
static __int128* stk_prod = NULL;
static int64_t stk_sp = 0;
int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t lcm_i64_i64(int64_t a, int64_t b) {
if ((a == 0 || b == 0)) {
return 0;
}
return (FLOW_CHECKED_DIV((a), (gcd_i64_i64(a, b))) * b);
}
int64_t isqrt_i64(int64_t n) {
if (n < 2) {
return n;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod) {
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
int64_t b = FLOW_CHECKED_MOD((b0), (mod));
int64_t result = 0;
while (b > 0) {
if (FLOW_CHECKED_MOD((b), (2)) == 1) {
result = FLOW_CHECKED_MOD(((result + a)), (mod));
}
a = FLOW_CHECKED_MOD(((a * 2)), (mod));
b = FLOW_CHECKED_DIV((b), (2));
}
return result;
}
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
if (mod == 1) {
return 0;
}
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (mod));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mulmod_i64_i64_i64(result, b, mod);
}
b = mulmod_i64_i64_i64(b, b, mod);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
bool is_prime_i64(int64_t n) {
if (n < 2) {
return 0;
}
if (n < 4) {
return 1;
}
if ((FLOW_CHECKED_MOD((n), (2)) == 0 || FLOW_CHECKED_MOD((n), (3)) == 0)) {
return 0;
}
int64_t i = 5;
while ((i * i) <= n) {
if ((FLOW_CHECKED_MOD((n), (i)) == 0 || FLOW_CHECKED_MOD((n), ((i + 2))) == 0)) {
return 0;
}
i = (i + 6);
}
return 1;
}
int64_t mmul_i64_i64(int64_t a, int64_t b) {
return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(b)))), (((__int128)(MOD))))));
}
int64_t madd_i64_i64(int64_t a, int64_t b) {
return FLOW_CHECKED_MOD(((a + b)), (MOD));
}
int64_t msub_i64_i64(int64_t a, int64_t b) {
return FLOW_CHECKED_MOD((((a - FLOW_CHECKED_MOD((b), (MOD))) + MOD)), (MOD));
}
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod0) {
int64_t r = 1;
int64_t base = FLOW_CHECKED_MOD((base0), (mod0));
int64_t exp = exp0;
while (exp > 0) {
if ((exp & 1) != 0) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(base)))), (((__int128)(mod0))))));
}
base = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(base)) * ((__int128)(base)))), (((__int128)(mod0))))));
exp = FLOW_CHECKED_SHR((exp), (1));
}
return r;
}
int64_t msum1_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t a = FLOW_CHECKED_MOD((n), (MOD));
int64_t b = FLOW_CHECKED_MOD(((n + 1)), (MOD));
return mmul_i64_i64(mmul_i64_i64(a, b), modpow_i64_i64_i64(2, (MOD - 2), MOD));
}
int64_t msum2_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t a = FLOW_CHECKED_MOD((n), (MOD));
int64_t b = FLOW_CHECKED_MOD(((n + 1)), (MOD));
int64_t c = FLOW_CHECKED_MOD((((2 * n) + 1)), (MOD));
return mmul_i64_i64(mmul_i64_i64(mmul_i64_i64(a, b), c), modpow_i64_i64_i64(6, (MOD - 2), MOD));
}
int64_t msum3_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t s = msum1_i64(n);
return mmul_i64_i64(s, s);
}
int64_t rsum1_i64_i64(int64_t l, int64_t r) {
if (l > r) {
return 0;
}
return msub_i64_i64(msum1_i64(r), msum1_i64((l - 1)));
}
int64_t rsum2_i64_i64(int64_t l, int64_t r) {
if (l > r) {
return 0;
}
return msub_i64_i64(msum2_i64(r), msum2_i64((l - 1)));
}
int64_t rsum3_i64_i64(int64_t l, int64_t r) {
if (l > r) {
return 0;
}
return msub_i64_i64(msum3_i64(r), msum3_i64((l - 1)));
}
__int128 poly_m3_i64(int64_t k) {
__int128 kk = ((__int128)(k));
return ((((((kk * kk) * kk) * kk) - (((2 * kk) * kk) * kk)) + kk) - 1);
}
__int128 poly_a2_i64(int64_t k) {
__int128 kk = ((__int128)(k));
return (((kk * kk) - kk) - 1);
}
__int128 poly_a3_i64(int64_t k) {
__int128 kk = ((__int128)(k));
return (((((kk * kk) * kk) - (kk * kk)) - (2 * kk)) + 1);
}
bool pred_m3_i64(int64_t k) {
return poly_m3_i64(k) <= ((__int128)(N_val));
}
bool pred_a3_i64(int64_t k) {
return poly_a3_i64(k) <= ((__int128)(N_val));
}
int64_t max_k_m3_i64_i64(int64_t limit, int64_t start) {
if (limit < start) {
return limit;
}
if ((!(pred_m3_i64(start)))) {
return (start - 1);
}
int64_t lo = start;
int64_t hi = start;
while ((hi < limit && pred_m3_i64(hi))) {
lo = hi;
if ((hi * 2) > limit) {
hi = limit;
} else {
hi = (hi * 2);
}
}
if (pred_m3_i64(hi)) {
return hi;
}
while ((lo + 1) < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (pred_m3_i64(mid)) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
int64_t max_k_a3_inner_i64_i64(int64_t limit, int64_t start) {
if (limit < start) {
return limit;
}
if ((!(pred_a3_i64(start)))) {
return (start - 1);
}
int64_t lo = start;
int64_t hi = start;
while ((hi < limit && pred_a3_i64(hi))) {
lo = hi;
if ((hi * 2) > limit) {
hi = limit;
} else {
hi = (hi * 2);
}
}
if (pred_a3_i64(hi)) {
return hi;
}
while ((lo + 1) < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (pred_a3_i64(mid)) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
int64_t max_k_three_nonones_i64_i64(int64_t N, int64_t K) {
if (K < 3) {
return K;
}
N_val = N;
return max_k_m3_i64_i64(K, 3);
}
int64_t max_k_a2_i64_i64(int64_t N, int64_t K) {
if (K < 1) {
return 0;
}
int64_t disc = (1 + (4 * (N + 1)));
int64_t r0 = FLOW_CHECKED_DIV(((1 + isqrt_i64(disc))), (2));
int64_t r = r0;
if (r > K) {
r = K;
}
while ((r > 0 && poly_a2_i64(r) > ((__int128)(N)))) {
r = (r - 1);
}
return r;
}
int64_t max_k_a3_i64_i64(int64_t N, int64_t K) {
if (K < 3) {
return K;
}
if (poly_a3_i64(3) > ((__int128)(N))) {
return 2;
}
N_val = N;
int64_t r = max_k_a3_inner_i64_i64(K, 3);
return r;
}
int64_t hash_state_ptr_i64_i64(int64_t* vals, int64_t n) {
int64_t h = (-7046029254386353131);
int64_t i = 0;
while (i < n) {
h = (h ^ vals[i]);
h = (h * 1099511628211);
i = (i + 1);
}
if (h < 0) {
h = (-h);
}
return FLOW_CHECKED_MOD((h), (HT_CAP));
}
bool state_eq_ptr_i64_i64_ptr_i64_i64(int64_t* a, int64_t an, int64_t* b, int64_t bn) {
if (an != bn) {
return 0;
}
int64_t i = 0;
while (i < an) {
if (a[i] != b[i]) {
return 0;
}
i = (i + 1);
}
return 1;
}
void state_clear(void) {
memset(ht_used, 0, HT_CAP);
}
bool state_contains_ptr_i64_i64(int64_t* vals, int64_t n) {
int64_t h0 = hash_state_ptr_i64_i64(vals, n);
int64_t h = h0;
while (ht_used[h] != 0) {
if (state_eq_ptr_i64_i64_ptr_i64_i64(vals, n, (ht_keys + (h * 9)), ht_keys[((h * 9) + 8)])) {
return 1;
}
h = (h + 1);
if (h == HT_CAP) {
h = 0;
}
}
return 0;
}
void state_insert_ptr_i64_i64(int64_t* vals, int64_t n) {
int64_t h0 = hash_state_ptr_i64_i64(vals, n);
int64_t h = h0;
while (ht_used[h] != 0) {
if (state_eq_ptr_i64_i64_ptr_i64_i64(vals, n, (ht_keys + (h * 9)), ht_keys[((h * 9) + 8)])) {
return;
}
h = (h + 1);
if (h == HT_CAP) {
h = 0;
}
}
ht_used[h] = 1;
int64_t i = 0;
while (i < n) {
ht_keys[((h * 9) + i)] = vals[i];
i = (i + 1);
}
ht_keys[((h * 9) + 8)] = n;
}
void num_clear(void) {
memset(sn_used, 0, SN_CAP);
}
bool num_contains_i64(int64_t v) {
int64_t h = FLOW_CHECKED_MOD((v), (SN_CAP));
if (h < 0) {
h = (-h);
}
while (sn_used[h] != 0) {
if (sn_keys[h] == v) {
return 1;
}
h = (h + 1);
if (h == SN_CAP) {
h = 0;
}
}
return 0;
}
void num_insert_i64(int64_t v) {
int64_t h = FLOW_CHECKED_MOD((v), (SN_CAP));
if (h < 0) {
h = (-h);
}
while (sn_used[h] != 0) {
if (sn_keys[h] == v) {
return;
}
h = (h + 1);
if (h == SN_CAP) {
h = 0;
}
}
sn_used[h] = 1;
sn_keys[h] = v;
}
int64_t mk_sum_i64_i64_i64(int64_t k, int64_t N, int64_t mod0) {
if (N < 1) {
return 0;
}
int64_t s = FLOW_CHECKED_MOD((1), (mod0));
if ((k - 1) > N) {
return s;
}
state_clear();
num_clear();
num_insert_i64(1);
stk_sp = 0;
int64_t i = 0;
while (i < MAX_NONONES) {
stk_state[((0 * MAX_NONONES) + i)] = 0;
i = (i + 1);
}
stk_n[0] = 0;
stk_prod[0] = 1;
stk_sp = 1;
state_insert_ptr_i64_i64((stk_state + (0 * MAX_NONONES)), 0);
int64_t* new_vals = (int64_t*)(calloc(MAX_NONONES, 8));
int64_t* jump_vals = (int64_t*)(calloc((MAX_NONONES + 1), 8));
while (stk_sp > 0) {
stk_sp = (stk_sp - 1);
int64_t non_ones_n = stk_n[stk_sp];
__int128 prod_non_ones = stk_prod[stk_sp];
int64_t ones = (k - non_ones_n);
int64_t cur_state[8];
int64_t si = 0;
int64_t cur_base = (stk_sp * MAX_NONONES);
while (si < MAX_NONONES) {
cur_state[si] = stk_state[(cur_base + si)];
si = (si + 1);
}
int64_t i2 = 0;
while (i2 < non_ones_n) {
int64_t v = (((unsigned)(i2) < 8) ? cur_state[i2] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(i2), 8), flow_fault_handler("array index out of bounds"), cur_state[0]));
if ((v <= N && (!(num_contains_i64(v))))) {
num_insert_i64(v);
s = madd_i64_i64(s, FLOW_CHECKED_MOD((v), (mod0)));
}
i2 = (i2 + 1);
}
int64_t n_jump = 0;
int64_t i3 = 0;
while (i3 < non_ones_n) {
if ((i3 == 0 || (((unsigned)(i3) < 8) ? cur_state[i3] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(i3), 8), flow_fault_handler("array index out of bounds"), cur_state[0])) != (((unsigned)((i3 - 1)) < 8) ? cur_state[(i3 - 1)] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)((i3 - 1)), 8), flow_fault_handler("array index out of bounds"), cur_state[0])))) {
jump_vals[n_jump] = (((unsigned)(i3) < 8) ? cur_state[i3] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(i3), 8), flow_fault_handler("array index out of bounds"), cur_state[0]));
n_jump = (n_jump + 1);
}
i3 = (i3 + 1);
}
if (ones > 0) {
jump_vals[n_jump] = 1;
n_jump = (n_jump + 1);
}
int64_t vi = 0;
while (vi < n_jump) {
int64_t v = jump_vals[vi];
__int128 new_val = 0;
__int128 new_prod = 0;
bool do_insert = 0;
if (v == 1) {
if (ones == 0) {
vi = (vi + 1);
continue;
}
if (prod_non_ones > FLOW_CHECKED_DIV((((__int128)((N + 1)))), (((__int128)(k))))) {
vi = (vi + 1);
continue;
}
__int128 nv = ((((__int128)(k)) * prod_non_ones) - 1);
if ((nv <= 1 || nv > ((__int128)(N)))) {
vi = (vi + 1);
continue;
}
new_val = nv;
new_prod = (prod_non_ones * nv);
} else {
__int128 prod_div_v = FLOW_CHECKED_DIV((prod_non_ones), (((__int128)(v))));
if (prod_div_v > FLOW_CHECKED_DIV((((__int128)((N + v)))), (((__int128)(k))))) {
vi = (vi + 1);
continue;
}
__int128 nv = ((((__int128)(k)) * prod_div_v) - ((__int128)(v)));
if ((nv <= ((__int128)(v)) || nv > ((__int128)(N)))) {
vi = (vi + 1);
continue;
}
new_val = nv;
new_prod = (prod_div_v * nv);
}
if (v == 1) {
int64_t j = 0;
while (j < MAX_NONONES) {
new_vals[j] = 0;
j = (j + 1);
}
int64_t j0 = 0;
while (j0 < non_ones_n) {
new_vals[j0] = (((unsigned)(j0) < 8) ? cur_state[j0] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(j0), 8), flow_fault_handler("array index out of bounds"), cur_state[0]));
j0 = (j0 + 1);
}
int64_t pos = non_ones_n;
int64_t j2 = 0;
while (j2 < non_ones_n) {
if (new_val < ((__int128)((((unsigned)(j2) < 8) ? cur_state[j2] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(j2), 8), flow_fault_handler("array index out of bounds"), cur_state[0]))))) {
pos = j2;
break;
}
j2 = (j2 + 1);
}
int64_t j3 = non_ones_n;
while (j3 > pos) {
new_vals[j3] = new_vals[(j3 - 1)];
j3 = (j3 - 1);
}
new_vals[pos] = ((int64_t)(new_val));
int64_t new_n = (non_ones_n + 1);
if ((!(state_contains_ptr_i64_i64(new_vals, new_n)))) {
state_insert_ptr_i64_i64(new_vals, new_n);
int64_t nb = (stk_sp * MAX_NONONES);
int64_t j4 = 0;
while (j4 < MAX_NONONES) {
stk_state[(nb + j4)] = new_vals[j4];
j4 = (j4 + 1);
}
stk_n[stk_sp] = new_n;
stk_prod[stk_sp] = new_prod;
stk_sp = (stk_sp + 1);
}
} else {
int64_t j = 0;
while (j < MAX_NONONES) {
new_vals[j] = 0;
j = (j + 1);
}
int64_t found = (-1);
int64_t j2 = 0;
while (j2 < non_ones_n) {
if ((((unsigned)(j2) < 8) ? cur_state[j2] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(j2), 8), flow_fault_handler("array index out of bounds"), cur_state[0])) == v) {
found = j2;
break;
}
j2 = (j2 + 1);
}
if (found < 0) {
vi = (vi + 1);
continue;
}
int64_t idx = 0;
int64_t j3 = 0;
while (j3 < non_ones_n) {
if (j3 != found) {
new_vals[idx] = (((unsigned)(j3) < 8) ? cur_state[j3] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(j3), 8), flow_fault_handler("array index out of bounds"), cur_state[0]));
idx = (idx + 1);
}
j3 = (j3 + 1);
}
int64_t tmp_n = (non_ones_n - 1);
int64_t pos = tmp_n;
int64_t j4 = 0;
while (j4 < tmp_n) {
if (new_val < ((__int128)(new_vals[j4]))) {
pos = j4;
break;
}
j4 = (j4 + 1);
}
int64_t j5 = tmp_n;
while (j5 > pos) {
new_vals[j5] = new_vals[(j5 - 1)];
j5 = (j5 - 1);
}
new_vals[pos] = ((int64_t)(new_val));
int64_t new_n = (tmp_n + 1);
if ((!(state_contains_ptr_i64_i64(new_vals, new_n)))) {
state_insert_ptr_i64_i64(new_vals, new_n);
int64_t nb = (stk_sp * MAX_NONONES);
int64_t j6 = 0;
while (j6 < MAX_NONONES) {
stk_state[(nb + j6)] = new_vals[j6];
j6 = (j6 + 1);
}
stk_n[stk_sp] = new_n;
stk_prod[stk_sp] = new_prod;
stk_sp = (stk_sp + 1);
}
}
vi = (vi + 1);
}
}
free(new_vals);
free(jump_vals);
return FLOW_CHECKED_MOD((s), (mod0));
}
int32_t main(void) {
ht_keys = calloc((HT_CAP * 9), 8);
ht_used = calloc(HT_CAP, 1);
sn_keys = calloc(SN_CAP, 8);
sn_used = calloc(SN_CAP, 1);
stk_state = calloc((STK_CAP * MAX_NONONES), 8);
stk_n = calloc(STK_CAP, 8);
stk_prod = calloc(STK_CAP, 16);
int64_t K = 1000000000000000000;
int64_t N = 1000000000000000000;
int64_t mod0 = MOD;
if ((K < 3 || N < 1)) {
printf("%lld\n", ((int64_t)(0)));
return 0;
}
int64_t K_eff = ((K < (N + 1)) ? (K) : ((N + 1)));
int64_t total = 0;
int64_t m3 = max_k_three_nonones_i64_i64(N, K_eff);
int64_t cutoff = ((K_eff < m3) ? (K_eff) : (m3));
int64_t k = 3;
while (k <= cutoff) {
total = madd_i64_i64(total, mk_sum_i64_i64_i64(k, N, mod0));
k = (k + 1);
}
int64_t start = (cutoff + 1);
if (start > K_eff) {
if (K > K_eff) {
total = madd_i64_i64(total, FLOW_CHECKED_MOD(((K - K_eff)), (mod0)));
}
printf("%lld\n", FLOW_CHECKED_MOD((total), (mod0)));
return 0;
}
int64_t k3v = max_k_a3_i64_i64(N, K_eff);
int64_t k3 = ((K_eff < k3v) ? (K_eff) : (k3v));
int64_t k2v = max_k_a2_i64_i64(N, K_eff);
int64_t k2 = ((K_eff < k2v) ? (K_eff) : (k2v));
int64_t l1 = start;
int64_t r1 = k3;
if (l1 <= r1) {
int64_t part = msub_i64_i64(rsum3_i64_i64(l1, r1), mmul_i64_i64(2, rsum1_i64_i64(l1, r1)));
total = madd_i64_i64(total, part);
}
int64_t l2 = ((start > (k3 + 1)) ? (start) : ((k3 + 1)));
int64_t r2 = k2;
if (l2 <= r2) {
int64_t cnt = FLOW_CHECKED_MOD((((r2 - l2) + 1)), (mod0));
int64_t part = msub_i64_i64(rsum2_i64_i64(l2, r2), cnt);
total = madd_i64_i64(total, part);
}
int64_t l3 = ((start > (k2 + 1)) ? (start) : ((k2 + 1)));
int64_t r3 = K_eff;
if (l3 <= r3) {
int64_t part = rsum1_i64_i64(l3, r3);
total = madd_i64_i64(total, part);
}
if (K > K_eff) {
total = madd_i64_i64(total, FLOW_CHECKED_MOD(((K - K_eff)), (mod0)));
}
printf("%lld\n", FLOW_CHECKED_MOD((total), (mod0)));
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 @gcd(%arg0: i64, %arg1: i64) -> i64 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%4 = llvm.load %3 : !llvm.ptr -> i64
%5 = arith.constant 0 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi ne, %4, %7 : i64
cf.cond_br %6, ^bb1, ^bb2
^bb1:
%8 = llvm.load %1 : !llvm.ptr -> i64
%9 = llvm.load %3 : !llvm.ptr -> i64
%10 = arith.remsi %8, %9 : i64
%11 = llvm.load %3 : !llvm.ptr -> i64
llvm.store %11, %1 : i64, !llvm.ptr
llvm.store %10, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%12 = llvm.load %1 : !llvm.ptr -> i64
func.return %12 : i64
}
func.func @lcm(%arg0: i64, %arg1: i64) -> i64 {
%13 = arith.constant 0 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.cmpi eq, %arg0, %15 : i64
%16 = scf.if %14 -> (i1) {
%17 = arith.constant true
scf.yield %17 : i1
} else {
%18 = arith.constant 0 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.cmpi eq, %arg1, %20 : i64
scf.yield %19 : i1
}
cf.cond_br %16, ^bb3, ^bb4
^bb3:
%21 = arith.constant 0 : i32
%22 = arith.extsi %21 : i32 to i64
func.return %22 : i64
^bb4:
cf.br ^bb5
^bb5:
%23 = func.call @gcd(%arg0, %arg1) : (i64, i64) -> i64
%24 = arith.divsi %arg0, %23 : i64
%25 = arith.muli %24, %arg1 : i64
func.return %25 : i64
}
func.func @isqrt(%arg0: i64) -> i64 {
%26 = arith.constant 2 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.cmpi slt, %arg0, %28 : i64
cf.cond_br %27, ^bb6, ^bb7
^bb6:
func.return %arg0 : i64
^bb7:
cf.br ^bb8
^bb8:
%29 = llvm.mlir.constant(1 : i64) : i64
%30 = llvm.alloca %29 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %30 : i64, !llvm.ptr
%31 = llvm.load %30 : !llvm.ptr -> i64
%32 = arith.constant 1 : i32
%34 = arith.extsi %32 : i32 to i64
%33 = arith.addi %31, %34 : i64
%35 = arith.constant 2 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.divsi %33, %37 : i64
%38 = llvm.mlir.constant(1 : i64) : i64
%39 = llvm.alloca %38 x i64 : (i64) -> !llvm.ptr
llvm.store %36, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%40 = llvm.load %39 : !llvm.ptr -> i64
%41 = llvm.load %30 : !llvm.ptr -> i64
%42 = arith.cmpi slt, %40, %41 : i64
cf.cond_br %42, ^bb10, ^bb11
^bb10:
%43 = llvm.load %39 : !llvm.ptr -> i64
llvm.store %43, %30 : i64, !llvm.ptr
%44 = llvm.load %30 : !llvm.ptr -> i64
%45 = llvm.load %30 : !llvm.ptr -> i64
%46 = arith.divsi %arg0, %45 : i64
%47 = arith.addi %44, %46 : i64
%48 = arith.constant 2 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.divsi %47, %50 : i64
llvm.store %49, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%51 = llvm.load %30 : !llvm.ptr -> i64
func.return %51 : i64
}
func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%52 = arith.remsi %arg0, %arg2 : i64
%53 = llvm.mlir.constant(1 : i64) : i64
%54 = llvm.alloca %53 x i64 : (i64) -> !llvm.ptr
llvm.store %52, %54 : i64, !llvm.ptr
%55 = arith.remsi %arg1, %arg2 : i64
%56 = llvm.mlir.constant(1 : i64) : i64
%57 = llvm.alloca %56 x i64 : (i64) -> !llvm.ptr
llvm.store %55, %57 : i64, !llvm.ptr
%58 = arith.constant 0 : i32
%59 = arith.extsi %58 : i32 to i64
%60 = llvm.mlir.constant(1 : i64) : i64
%61 = llvm.alloca %60 x i64 : (i64) -> !llvm.ptr
llvm.store %59, %61 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%62 = llvm.load %57 : !llvm.ptr -> i64
%63 = arith.constant 0 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.cmpi sgt, %62, %65 : i64
cf.cond_br %64, ^bb13, ^bb14
^bb13:
%66 = llvm.load %57 : !llvm.ptr -> i64
%67 = arith.constant 2 : i32
%69 = arith.extsi %67 : i32 to i64
%68 = arith.remsi %66, %69 : i64
%70 = arith.constant 1 : i32
%72 = arith.extsi %70 : i32 to i64
%71 = arith.cmpi eq, %68, %72 : i64
cf.cond_br %71, ^bb15, ^bb16
^bb15:
%73 = llvm.load %61 : !llvm.ptr -> i64
%74 = llvm.load %54 : !llvm.ptr -> i64
%75 = arith.addi %73, %74 : i64
%76 = arith.remsi %75, %arg2 : i64
llvm.store %76, %61 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%77 = llvm.load %54 : !llvm.ptr -> i64
%78 = arith.constant 2 : i32
%80 = arith.extsi %78 : i32 to i64
%79 = arith.muli %77, %80 : i64
%81 = arith.remsi %79, %arg2 : i64
llvm.store %81, %54 : i64, !llvm.ptr
%82 = llvm.load %57 : !llvm.ptr -> i64
%83 = arith.constant 2 : i32
%85 = arith.extsi %83 : i32 to i64
%84 = arith.divsi %82, %85 : i64
llvm.store %84, %57 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%86 = llvm.load %61 : !llvm.ptr -> i64
func.return %86 : i64
}
func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%87 = arith.constant 1 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.cmpi eq, %arg2, %89 : i64
cf.cond_br %88, ^bb18, ^bb19
^bb18:
%90 = arith.constant 0 : i32
%91 = arith.extsi %90 : i32 to i64
func.return %91 : i64
^bb19:
cf.br ^bb20
^bb20:
%92 = arith.constant 1 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i64, !llvm.ptr
%96 = arith.remsi %arg0, %arg2 : i64
%97 = llvm.mlir.constant(1 : i64) : i64
%98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
llvm.store %96, %98 : i64, !llvm.ptr
%99 = llvm.mlir.constant(1 : i64) : i64
%100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%101 = llvm.load %100 : !llvm.ptr -> i64
%102 = arith.constant 0 : i32
%104 = arith.extsi %102 : i32 to i64
%103 = arith.cmpi sgt, %101, %104 : i64
cf.cond_br %103, ^bb22, ^bb23
^bb22:
%105 = llvm.load %100 : !llvm.ptr -> i64
%106 = arith.constant 2 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.remsi %105, %108 : i64
%109 = arith.constant 1 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.cmpi eq, %107, %111 : i64
cf.cond_br %110, ^bb24, ^bb25
^bb24:
%113 = llvm.load %95 : !llvm.ptr -> i64
%114 = llvm.load %98 : !llvm.ptr -> i64
%112 = func.call @mulmod(%113, %114, %arg2) : (i64, i64, i64) -> i64
llvm.store %112, %95 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%116 = llvm.load %98 : !llvm.ptr -> i64
%117 = llvm.load %98 : !llvm.ptr -> i64
%115 = func.call @mulmod(%116, %117, %arg2) : (i64, i64, i64) -> i64
llvm.store %115, %98 : i64, !llvm.ptr
%118 = llvm.load %100 : !llvm.ptr -> i64
%119 = arith.constant 2 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.divsi %118, %121 : i64
llvm.store %120, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%122 = llvm.load %95 : !llvm.ptr -> i64
func.return %122 : i64
}
func.func @is_prime(%arg0: i64) -> i1 {
%123 = arith.constant 2 : i32
%125 = arith.extsi %123 : i32 to i64
%124 = arith.cmpi slt, %arg0, %125 : i64
cf.cond_br %124, ^bb27, ^bb28
^bb27:
%126 = arith.constant 0 : i1
func.return %126 : i1
^bb28:
cf.br ^bb29
^bb29:
%127 = arith.constant 4 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.cmpi slt, %arg0, %129 : i64
cf.cond_br %128, ^bb30, ^bb31
^bb30:
%130 = arith.constant 1 : i1
func.return %130 : i1
^bb31:
cf.br ^bb32
^bb32:
%131 = arith.constant 2 : i32
%133 = arith.extsi %131 : i32 to i64
%132 = arith.remsi %arg0, %133 : i64
%134 = arith.constant 0 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.cmpi eq, %132, %136 : i64
%137 = scf.if %135 -> (i1) {
%138 = arith.constant true
scf.yield %138 : i1
} else {
%139 = arith.constant 3 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.remsi %arg0, %141 : i64
%142 = arith.constant 0 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.cmpi eq, %140, %144 : i64
scf.yield %143 : i1
}
cf.cond_br %137, ^bb33, ^bb34
^bb33:
%145 = arith.constant 0 : i1
func.return %145 : i1
^bb34:
cf.br ^bb35
^bb35:
%146 = arith.constant 5 : i32
%147 = arith.extsi %146 : i32 to i64
%148 = llvm.mlir.constant(1 : i64) : i64
%149 = llvm.alloca %148 x i64 : (i64) -> !llvm.ptr
llvm.store %147, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.load %149 : !llvm.ptr -> i64
%152 = arith.muli %150, %151 : i64
%153 = arith.cmpi sle, %152, %arg0 : i64
cf.cond_br %153, ^bb37, ^bb38
^bb37:
%154 = llvm.load %149 : !llvm.ptr -> i64
%155 = arith.remsi %arg0, %154 : i64
%156 = arith.constant 0 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.cmpi eq, %155, %158 : i64
%159 = scf.if %157 -> (i1) {
%160 = arith.constant true
scf.yield %160 : i1
} else {
%161 = llvm.load %149 : !llvm.ptr -> i64
%162 = arith.constant 2 : i32
%164 = arith.extsi %162 : i32 to i64
%163 = arith.addi %161, %164 : i64
%165 = arith.remsi %arg0, %163 : i64
%166 = arith.constant 0 : i32
%168 = arith.extsi %166 : i32 to i64
%167 = arith.cmpi eq, %165, %168 : i64
scf.yield %167 : i1
}
cf.cond_br %159, ^bb39, ^bb40
^bb39:
%169 = arith.constant 0 : i1
func.return %169 : i1
^bb40:
cf.br ^bb41
^bb41:
%170 = llvm.load %149 : !llvm.ptr -> i64
%171 = arith.constant 6 : i32
%173 = arith.extsi %171 : i32 to i64
%172 = arith.addi %170, %173 : i64
llvm.store %172, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%174 = arith.constant 1 : i1
func.return %174 : i1
}
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @memset(!llvm.ptr, i32, i64) -> !llvm.ptr
// Constant: MOD
llvm.mlir.global internal constant @MOD(1405695061 : i64) : i64
// Constant: MAX_NONONES
llvm.mlir.global internal constant @MAX_NONONES(8 : i64) : i64
// Constant: HT_CAP
llvm.mlir.global internal constant @HT_CAP(2048 : i64) : i64
// Constant: SN_CAP
llvm.mlir.global internal constant @SN_CAP(4096 : i64) : i64
// Constant: STK_CAP
llvm.mlir.global internal constant @STK_CAP(4096 : i64) : i64
// Module static: N_val
llvm.mlir.global internal @N_val(0 : i64) : i64
func.func @mmul(%arg0: i64, %arg1: i64) -> i64 {
%175 = arith.extsi %arg0 : i64 to i128
%176 = arith.extsi %arg1 : i64 to i128
%178 = arith.trunci %175 : i128 to i64
%179 = arith.trunci %176 : i128 to i64
%177 = arith.muli %178, %179 : i64
%180 = llvm.mlir.addressof @MOD : !llvm.ptr
%181 = llvm.load %180 : !llvm.ptr -> i64
%182 = arith.extsi %181 : i64 to i128
%184 = arith.trunci %182 : i128 to i64
%183 = arith.remsi %177, %184 : i64
func.return %183 : i64
}
func.func @madd(%arg0: i64, %arg1: i64) -> i64 {
%185 = arith.addi %arg0, %arg1 : i64
%186 = llvm.mlir.addressof @MOD : !llvm.ptr
%187 = llvm.load %186 : !llvm.ptr -> i64
%188 = arith.remsi %185, %187 : i64
func.return %188 : i64
}
func.func @msub(%arg0: i64, %arg1: i64) -> i64 {
%189 = llvm.mlir.addressof @MOD : !llvm.ptr
%190 = llvm.load %189 : !llvm.ptr -> i64
%191 = arith.remsi %arg1, %190 : i64
%192 = arith.subi %arg0, %191 : i64
%193 = llvm.mlir.addressof @MOD : !llvm.ptr
%194 = llvm.load %193 : !llvm.ptr -> i64
%195 = arith.addi %192, %194 : i64
%196 = llvm.mlir.addressof @MOD : !llvm.ptr
%197 = llvm.load %196 : !llvm.ptr -> i64
%198 = arith.remsi %195, %197 : i64
func.return %198 : i64
}
func.func @modpow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%199 = arith.constant 1 : i32
%200 = arith.extsi %199 : i32 to i64
%201 = llvm.mlir.constant(1 : i64) : i64
%202 = llvm.alloca %201 x i64 : (i64) -> !llvm.ptr
llvm.store %200, %202 : i64, !llvm.ptr
%203 = arith.remsi %arg0, %arg2 : i64
%204 = llvm.mlir.constant(1 : i64) : i64
%205 = llvm.alloca %204 x i64 : (i64) -> !llvm.ptr
llvm.store %203, %205 : i64, !llvm.ptr
%206 = llvm.mlir.constant(1 : i64) : i64
%207 = llvm.alloca %206 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %207 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%208 = llvm.load %207 : !llvm.ptr -> i64
%209 = arith.constant 0 : i32
%211 = arith.extsi %209 : i32 to i64
%210 = arith.cmpi sgt, %208, %211 : i64
cf.cond_br %210, ^bb43, ^bb44
^bb43:
%212 = llvm.load %207 : !llvm.ptr -> i64
%213 = arith.constant 1 : i32
%215 = arith.extsi %213 : i32 to i64
%214 = arith.andi %212, %215 : i64
%216 = arith.constant 0 : i32
%218 = arith.extsi %216 : i32 to i64
%217 = arith.cmpi ne, %214, %218 : i64
cf.cond_br %217, ^bb45, ^bb46
^bb45:
%219 = llvm.load %202 : !llvm.ptr -> i64
%220 = arith.extsi %219 : i64 to i128
%221 = llvm.load %205 : !llvm.ptr -> i64
%222 = arith.extsi %221 : i64 to i128
%224 = arith.trunci %220 : i128 to i64
%225 = arith.trunci %222 : i128 to i64
%223 = arith.muli %224, %225 : i64
%226 = arith.extsi %arg2 : i64 to i128
%228 = arith.trunci %226 : i128 to i64
%227 = arith.remsi %223, %228 : i64
llvm.store %227, %202 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%229 = llvm.load %205 : !llvm.ptr -> i64
%230 = arith.extsi %229 : i64 to i128
%231 = llvm.load %205 : !llvm.ptr -> i64
%232 = arith.extsi %231 : i64 to i128
%234 = arith.trunci %230 : i128 to i64
%235 = arith.trunci %232 : i128 to i64
%233 = arith.muli %234, %235 : i64
%236 = arith.extsi %arg2 : i64 to i128
%238 = arith.trunci %236 : i128 to i64
%237 = arith.remsi %233, %238 : i64
llvm.store %237, %205 : i64, !llvm.ptr
%239 = llvm.load %207 : !llvm.ptr -> i64
%240 = arith.constant 1 : i32
%242 = arith.extsi %240 : i32 to i64
%241 = arith.shrsi %239, %242 : i64
llvm.store %241, %207 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%243 = llvm.load %202 : !llvm.ptr -> i64
func.return %243 : i64
}
func.func @msum1(%arg0: i64) -> i64 {
%244 = arith.constant 0 : i32
%246 = arith.extsi %244 : i32 to i64
%245 = arith.cmpi sle, %arg0, %246 : i64
cf.cond_br %245, ^bb48, ^bb49
^bb48:
%247 = arith.constant 0 : i32
%248 = arith.extsi %247 : i32 to i64
func.return %248 : i64
^bb49:
cf.br ^bb50
^bb50:
%249 = llvm.mlir.addressof @MOD : !llvm.ptr
%250 = llvm.load %249 : !llvm.ptr -> i64
%251 = arith.remsi %arg0, %250 : i64
%252 = arith.constant 1 : i32
%254 = arith.extsi %252 : i32 to i64
%253 = arith.addi %arg0, %254 : i64
%255 = llvm.mlir.addressof @MOD : !llvm.ptr
%256 = llvm.load %255 : !llvm.ptr -> i64
%257 = arith.remsi %253, %256 : i64
%259 = func.call @mmul(%251, %257) : (i64, i64) -> i64
%261 = arith.constant 2 : i32
%262 = llvm.mlir.addressof @MOD : !llvm.ptr
%263 = llvm.load %262 : !llvm.ptr -> i64
%264 = arith.constant 2 : i32
%266 = arith.extsi %264 : i32 to i64
%265 = arith.subi %263, %266 : i64
%267 = llvm.mlir.addressof @MOD : !llvm.ptr
%268 = llvm.load %267 : !llvm.ptr -> i64
%269 = arith.extsi %261 : i32 to i64
%260 = func.call @modpow(%269, %265, %268) : (i64, i64, i64) -> i64
%258 = func.call @mmul(%259, %260) : (i64, i64) -> i64
func.return %258 : i64
}
func.func @msum2(%arg0: i64) -> i64 {
%270 = arith.constant 0 : i32
%272 = arith.extsi %270 : i32 to i64
%271 = arith.cmpi sle, %arg0, %272 : i64
cf.cond_br %271, ^bb51, ^bb52
^bb51:
%273 = arith.constant 0 : i32
%274 = arith.extsi %273 : i32 to i64
func.return %274 : i64
^bb52:
cf.br ^bb53
^bb53:
%275 = llvm.mlir.addressof @MOD : !llvm.ptr
%276 = llvm.load %275 : !llvm.ptr -> i64
%277 = arith.remsi %arg0, %276 : i64
%278 = arith.constant 1 : i32
%280 = arith.extsi %278 : i32 to i64
%279 = arith.addi %arg0, %280 : i64
%281 = llvm.mlir.addressof @MOD : !llvm.ptr
%282 = llvm.load %281 : !llvm.ptr -> i64
%283 = arith.remsi %279, %282 : i64
%284 = arith.constant 2 : i32
%286 = arith.extsi %284 : i32 to i64
%285 = arith.muli %286, %arg0 : i64
%287 = arith.constant 1 : i32
%289 = arith.extsi %287 : i32 to i64
%288 = arith.addi %285, %289 : i64
%290 = llvm.mlir.addressof @MOD : !llvm.ptr
%291 = llvm.load %290 : !llvm.ptr -> i64
%292 = arith.remsi %288, %291 : i64
%295 = func.call @mmul(%277, %283) : (i64, i64) -> i64
%294 = func.call @mmul(%295, %292) : (i64, i64) -> i64
%297 = arith.constant 6 : i32
%298 = llvm.mlir.addressof @MOD : !llvm.ptr
%299 = llvm.load %298 : !llvm.ptr -> i64
%300 = arith.constant 2 : i32
%302 = arith.extsi %300 : i32 to i64
%301 = arith.subi %299, %302 : i64
%303 = llvm.mlir.addressof @MOD : !llvm.ptr
%304 = llvm.load %303 : !llvm.ptr -> i64
%305 = arith.extsi %297 : i32 to i64
%296 = func.call @modpow(%305, %301, %304) : (i64, i64, i64) -> i64
%293 = func.call @mmul(%294, %296) : (i64, i64) -> i64
func.return %293 : i64
}
func.func @msum3(%arg0: i64) -> i64 {
%306 = arith.constant 0 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.cmpi sle, %arg0, %308 : i64
cf.cond_br %307, ^bb54, ^bb55
^bb54:
%309 = arith.constant 0 : i32
%310 = arith.extsi %309 : i32 to i64
func.return %310 : i64
^bb55:
cf.br ^bb56
^bb56:
%311 = func.call @msum1(%arg0) : (i64) -> i64
%312 = func.call @mmul(%311, %311) : (i64, i64) -> i64
func.return %312 : i64
}
func.func @rsum1(%arg0: i64, %arg1: i64) -> i64 {
%313 = arith.cmpi sgt, %arg0, %arg1 : i64
cf.cond_br %313, ^bb57, ^bb58
^bb57:
%314 = arith.constant 0 : i32
%315 = arith.extsi %314 : i32 to i64
func.return %315 : i64
^bb58:
cf.br ^bb59
^bb59:
%317 = func.call @msum1(%arg1) : (i64) -> i64
%319 = arith.constant 1 : i32
%321 = arith.extsi %319 : i32 to i64
%320 = arith.subi %arg0, %321 : i64
%318 = func.call @msum1(%320) : (i64) -> i64
%316 = func.call @msub(%317, %318) : (i64, i64) -> i64
func.return %316 : i64
}
func.func @rsum2(%arg0: i64, %arg1: i64) -> i64 {
%322 = arith.cmpi sgt, %arg0, %arg1 : i64
cf.cond_br %322, ^bb60, ^bb61
^bb60:
%323 = arith.constant 0 : i32
%324 = arith.extsi %323 : i32 to i64
func.return %324 : i64
^bb61:
cf.br ^bb62
^bb62:
%326 = func.call @msum2(%arg1) : (i64) -> i64
%328 = arith.constant 1 : i32
%330 = arith.extsi %328 : i32 to i64
%329 = arith.subi %arg0, %330 : i64
%327 = func.call @msum2(%329) : (i64) -> i64
%325 = func.call @msub(%326, %327) : (i64, i64) -> i64
func.return %325 : i64
}
func.func @rsum3(%arg0: i64, %arg1: i64) -> i64 {
%331 = arith.cmpi sgt, %arg0, %arg1 : i64
cf.cond_br %331, ^bb63, ^bb64
^bb63:
%332 = arith.constant 0 : i32
%333 = arith.extsi %332 : i32 to i64
func.return %333 : i64
^bb64:
cf.br ^bb65
^bb65:
%335 = func.call @msum3(%arg1) : (i64) -> i64
%337 = arith.constant 1 : i32
%339 = arith.extsi %337 : i32 to i64
%338 = arith.subi %arg0, %339 : i64
%336 = func.call @msum3(%338) : (i64) -> i64
%334 = func.call @msub(%335, %336) : (i64, i64) -> i64
func.return %334 : i64
}
func.func @poly_m3(%arg0: i64) -> i128 {
%340 = arith.extsi %arg0 : i64 to i128
%342 = arith.trunci %340 : i128 to i64
%343 = arith.trunci %340 : i128 to i64
%341 = arith.muli %342, %343 : i64
%345 = arith.trunci %340 : i128 to i64
%344 = arith.muli %341, %345 : i64
%347 = arith.trunci %340 : i128 to i64
%346 = arith.muli %344, %347 : i64
%348 = arith.constant 2 : i32
%350 = arith.extsi %348 : i32 to i64
%351 = arith.trunci %340 : i128 to i64
%349 = arith.muli %350, %351 : i64
%353 = arith.trunci %340 : i128 to i64
%352 = arith.muli %349, %353 : i64
%355 = arith.trunci %340 : i128 to i64
%354 = arith.muli %352, %355 : i64
%356 = arith.subi %346, %354 : i64
%358 = arith.trunci %340 : i128 to i64
%357 = arith.addi %356, %358 : i64
%359 = arith.constant 1 : i32
%361 = arith.extsi %359 : i32 to i64
%360 = arith.subi %357, %361 : i64
%362 = arith.extsi %360 : i64 to i128
func.return %362 : i128
}
func.func @poly_a2(%arg0: i64) -> i128 {
%363 = arith.extsi %arg0 : i64 to i128
%365 = arith.trunci %363 : i128 to i64
%366 = arith.trunci %363 : i128 to i64
%364 = arith.muli %365, %366 : i64
%368 = arith.trunci %363 : i128 to i64
%367 = arith.subi %364, %368 : i64
%369 = arith.constant 1 : i32
%371 = arith.extsi %369 : i32 to i64
%370 = arith.subi %367, %371 : i64
%372 = arith.extsi %370 : i64 to i128
func.return %372 : i128
}
func.func @poly_a3(%arg0: i64) -> i128 {
%373 = arith.extsi %arg0 : i64 to i128
%375 = arith.trunci %373 : i128 to i64
%376 = arith.trunci %373 : i128 to i64
%374 = arith.muli %375, %376 : i64
%378 = arith.trunci %373 : i128 to i64
%377 = arith.muli %374, %378 : i64
%380 = arith.trunci %373 : i128 to i64
%381 = arith.trunci %373 : i128 to i64
%379 = arith.muli %380, %381 : i64
%382 = arith.subi %377, %379 : i64
%383 = arith.constant 2 : i32
%385 = arith.extsi %383 : i32 to i64
%386 = arith.trunci %373 : i128 to i64
%384 = arith.muli %385, %386 : i64
%387 = arith.subi %382, %384 : i64
%388 = arith.constant 1 : i32
%390 = arith.extsi %388 : i32 to i64
%389 = arith.addi %387, %390 : i64
%391 = arith.extsi %389 : i64 to i128
func.return %391 : i128
}
func.func @pred_m3(%arg0: i64) -> i1 {
%392 = func.call @poly_m3(%arg0) : (i64) -> i128
%393 = llvm.mlir.addressof @N_val : !llvm.ptr
%394 = llvm.load %393 : !llvm.ptr -> i64
%395 = arith.extsi %394 : i64 to i128
%397 = arith.trunci %392 : i128 to i64
%398 = arith.trunci %395 : i128 to i64
%396 = arith.cmpi sle, %397, %398 : i64
func.return %396 : i1
}
func.func @pred_a3(%arg0: i64) -> i1 {
%399 = func.call @poly_a3(%arg0) : (i64) -> i128
%400 = llvm.mlir.addressof @N_val : !llvm.ptr
%401 = llvm.load %400 : !llvm.ptr -> i64
%402 = arith.extsi %401 : i64 to i128
%404 = arith.trunci %399 : i128 to i64
%405 = arith.trunci %402 : i128 to i64
%403 = arith.cmpi sle, %404, %405 : i64
func.return %403 : i1
}
func.func @max_k_m3(%arg0: i64, %arg1: i64) -> i64 {
%406 = arith.cmpi slt, %arg0, %arg1 : i64
cf.cond_br %406, ^bb66, ^bb67
^bb66:
func.return %arg0 : i64
^bb67:
cf.br ^bb68
^bb68:
%407 = func.call @pred_m3(%arg1) : (i64) -> i1
%409 = arith.constant 1 : i1
%408 = arith.xori %407, %409 : i1
cf.cond_br %408, ^bb69, ^bb70
^bb69:
%411 = arith.constant 1 : i32
%413 = arith.extsi %411 : i32 to i64
%412 = arith.subi %arg1, %413 : i64
func.return %412 : i64
^bb70:
cf.br ^bb71
^bb71:
%414 = llvm.mlir.constant(1 : i64) : i64
%415 = llvm.alloca %414 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %415 : i64, !llvm.ptr
%416 = llvm.mlir.constant(1 : i64) : i64
%417 = llvm.alloca %416 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %417 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%418 = llvm.load %417 : !llvm.ptr -> i64
%419 = arith.cmpi slt, %418, %arg0 : i64
%420 = scf.if %419 -> (i1) {
%422 = llvm.load %417 : !llvm.ptr -> i64
%421 = func.call @pred_m3(%422) : (i64) -> i1
scf.yield %421 : i1
} else {
%423 = arith.constant false
scf.yield %423 : i1
}
cf.cond_br %420, ^bb73, ^bb74
^bb73:
%424 = llvm.load %417 : !llvm.ptr -> i64
llvm.store %424, %415 : i64, !llvm.ptr
%425 = llvm.load %417 : !llvm.ptr -> i64
%426 = arith.constant 2 : i32
%428 = arith.extsi %426 : i32 to i64
%427 = arith.muli %425, %428 : i64
%429 = arith.cmpi sgt, %427, %arg0 : i64
cf.cond_br %429, ^bb75, ^bb76
^bb75:
llvm.store %arg0, %417 : i64, !llvm.ptr
cf.br ^bb77
^bb76:
%430 = llvm.load %417 : !llvm.ptr -> i64
%431 = arith.constant 2 : i32
%433 = arith.extsi %431 : i32 to i64
%432 = arith.muli %430, %433 : i64
llvm.store %432, %417 : i64, !llvm.ptr
cf.br ^bb77
^bb77:
cf.br ^bb72
^bb74:
%435 = llvm.load %417 : !llvm.ptr -> i64
%434 = func.call @pred_m3(%435) : (i64) -> i1
cf.cond_br %434, ^bb78, ^bb79
^bb78:
%436 = llvm.load %417 : !llvm.ptr -> i64
func.return %436 : i64
^bb79:
cf.br ^bb80
^bb80:
cf.br ^bb81
^bb81:
%437 = llvm.load %415 : !llvm.ptr -> i64
%438 = arith.constant 1 : i32
%440 = arith.extsi %438 : i32 to i64
%439 = arith.addi %437, %440 : i64
%441 = llvm.load %417 : !llvm.ptr -> i64
%442 = arith.cmpi slt, %439, %441 : i64
cf.cond_br %442, ^bb82, ^bb83
^bb82:
%443 = llvm.load %415 : !llvm.ptr -> i64
%444 = llvm.load %417 : !llvm.ptr -> i64
%445 = arith.addi %443, %444 : i64
%446 = arith.constant 2 : i32
%448 = arith.extsi %446 : i32 to i64
%447 = arith.divsi %445, %448 : i64
%449 = func.call @pred_m3(%447) : (i64) -> i1
cf.cond_br %449, ^bb84, ^bb85
^bb84:
llvm.store %447, %415 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
llvm.store %447, %417 : i64, !llvm.ptr
cf.br ^bb86
^bb86:
cf.br ^bb81
^bb83:
%450 = llvm.load %415 : !llvm.ptr -> i64
func.return %450 : i64
}
func.func @max_k_a3_inner(%arg0: i64, %arg1: i64) -> i64 {
%451 = arith.cmpi slt, %arg0, %arg1 : i64
cf.cond_br %451, ^bb87, ^bb88
^bb87:
func.return %arg0 : i64
^bb88:
cf.br ^bb89
^bb89:
%452 = func.call @pred_a3(%arg1) : (i64) -> i1
%454 = arith.constant 1 : i1
%453 = arith.xori %452, %454 : i1
cf.cond_br %453, ^bb90, ^bb91
^bb90:
%456 = arith.constant 1 : i32
%458 = arith.extsi %456 : i32 to i64
%457 = arith.subi %arg1, %458 : i64
func.return %457 : i64
^bb91:
cf.br ^bb92
^bb92:
%459 = llvm.mlir.constant(1 : i64) : i64
%460 = llvm.alloca %459 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %460 : i64, !llvm.ptr
%461 = llvm.mlir.constant(1 : i64) : i64
%462 = llvm.alloca %461 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %462 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%463 = llvm.load %462 : !llvm.ptr -> i64
%464 = arith.cmpi slt, %463, %arg0 : i64
%465 = scf.if %464 -> (i1) {
%467 = llvm.load %462 : !llvm.ptr -> i64
%466 = func.call @pred_a3(%467) : (i64) -> i1
scf.yield %466 : i1
} else {
%468 = arith.constant false
scf.yield %468 : i1
}
cf.cond_br %465, ^bb94, ^bb95
^bb94:
%469 = llvm.load %462 : !llvm.ptr -> i64
llvm.store %469, %460 : i64, !llvm.ptr
%470 = llvm.load %462 : !llvm.ptr -> i64
%471 = arith.constant 2 : i32
%473 = arith.extsi %471 : i32 to i64
%472 = arith.muli %470, %473 : i64
%474 = arith.cmpi sgt, %472, %arg0 : i64
cf.cond_br %474, ^bb96, ^bb97
^bb96:
llvm.store %arg0, %462 : i64, !llvm.ptr
cf.br ^bb98
^bb97:
%475 = llvm.load %462 : !llvm.ptr -> i64
%476 = arith.constant 2 : i32
%478 = arith.extsi %476 : i32 to i64
%477 = arith.muli %475, %478 : i64
llvm.store %477, %462 : i64, !llvm.ptr
cf.br ^bb98
^bb98:
cf.br ^bb93
^bb95:
%480 = llvm.load %462 : !llvm.ptr -> i64
%479 = func.call @pred_a3(%480) : (i64) -> i1
cf.cond_br %479, ^bb99, ^bb100
^bb99:
%481 = llvm.load %462 : !llvm.ptr -> i64
func.return %481 : i64
^bb100:
cf.br ^bb101
^bb101:
cf.br ^bb102
^bb102:
%482 = llvm.load %460 : !llvm.ptr -> i64
%483 = arith.constant 1 : i32
%485 = arith.extsi %483 : i32 to i64
%484 = arith.addi %482, %485 : i64
%486 = llvm.load %462 : !llvm.ptr -> i64
%487 = arith.cmpi slt, %484, %486 : i64
cf.cond_br %487, ^bb103, ^bb104
^bb103:
%488 = llvm.load %460 : !llvm.ptr -> i64
%489 = llvm.load %462 : !llvm.ptr -> i64
%490 = arith.addi %488, %489 : i64
%491 = arith.constant 2 : i32
%493 = arith.extsi %491 : i32 to i64
%492 = arith.divsi %490, %493 : i64
%494 = func.call @pred_a3(%492) : (i64) -> i1
cf.cond_br %494, ^bb105, ^bb106
^bb105:
llvm.store %492, %460 : i64, !llvm.ptr
cf.br ^bb107
^bb106:
llvm.store %492, %462 : i64, !llvm.ptr
cf.br ^bb107
^bb107:
cf.br ^bb102
^bb104:
%495 = llvm.load %460 : !llvm.ptr -> i64
func.return %495 : i64
}
func.func @max_k_three_nonones(%arg0: i64, %arg1: i64) -> i64 {
%496 = arith.constant 3 : i32
%498 = arith.extsi %496 : i32 to i64
%497 = arith.cmpi slt, %arg1, %498 : i64
cf.cond_br %497, ^bb108, ^bb109
^bb108:
func.return %arg1 : i64
^bb109:
cf.br ^bb110
^bb110:
%499 = llvm.mlir.addressof @N_val : !llvm.ptr
llvm.store %arg0, %499 : i64, !llvm.ptr
%501 = arith.constant 3 : i32
%502 = arith.extsi %501 : i32 to i64
%500 = func.call @max_k_m3(%arg1, %502) : (i64, i64) -> i64
func.return %500 : i64
}
func.func @max_k_a2(%arg0: i64, %arg1: i64) -> i64 {
%503 = arith.constant 1 : i32
%505 = arith.extsi %503 : i32 to i64
%504 = arith.cmpi slt, %arg1, %505 : i64
cf.cond_br %504, ^bb111, ^bb112
^bb111:
%506 = arith.constant 0 : i32
%507 = arith.extsi %506 : i32 to i64
func.return %507 : i64
^bb112:
cf.br ^bb113
^bb113:
%508 = arith.constant 1 : i32
%509 = arith.constant 4 : i32
%510 = arith.constant 1 : i32
%512 = arith.extsi %510 : i32 to i64
%511 = arith.addi %arg0, %512 : i64
%514 = arith.extsi %509 : i32 to i64
%513 = arith.muli %514, %511 : i64
%516 = arith.extsi %508 : i32 to i64
%515 = arith.addi %516, %513 : i64
%517 = arith.constant 1 : i32
%518 = func.call @isqrt(%515) : (i64) -> i64
%520 = arith.extsi %517 : i32 to i64
%519 = arith.addi %520, %518 : i64
%521 = arith.constant 2 : i32
%523 = arith.extsi %521 : i32 to i64
%522 = arith.divsi %519, %523 : i64
%524 = llvm.mlir.constant(1 : i64) : i64
%525 = llvm.alloca %524 x i64 : (i64) -> !llvm.ptr
llvm.store %522, %525 : i64, !llvm.ptr
%526 = llvm.load %525 : !llvm.ptr -> i64
%527 = arith.cmpi sgt, %526, %arg1 : i64
cf.cond_br %527, ^bb114, ^bb115
^bb114:
llvm.store %arg1, %525 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
cf.br ^bb117
^bb117:
%528 = llvm.load %525 : !llvm.ptr -> i64
%529 = arith.constant 0 : i32
%531 = arith.extsi %529 : i32 to i64
%530 = arith.cmpi sgt, %528, %531 : i64
%532 = scf.if %530 -> (i1) {
%534 = llvm.load %525 : !llvm.ptr -> i64
%533 = func.call @poly_a2(%534) : (i64) -> i128
%535 = arith.extsi %arg0 : i64 to i128
%537 = arith.trunci %533 : i128 to i64
%538 = arith.trunci %535 : i128 to i64
%536 = arith.cmpi sgt, %537, %538 : i64
scf.yield %536 : i1
} else {
%539 = arith.constant false
scf.yield %539 : i1
}
cf.cond_br %532, ^bb118, ^bb119
^bb118:
%540 = llvm.load %525 : !llvm.ptr -> i64
%541 = arith.constant 1 : i32
%543 = arith.extsi %541 : i32 to i64
%542 = arith.subi %540, %543 : i64
llvm.store %542, %525 : i64, !llvm.ptr
cf.br ^bb117
^bb119:
%544 = llvm.load %525 : !llvm.ptr -> i64
func.return %544 : i64
}
func.func @max_k_a3(%arg0: i64, %arg1: i64) -> i64 {
%545 = arith.constant 3 : i32
%547 = arith.extsi %545 : i32 to i64
%546 = arith.cmpi slt, %arg1, %547 : i64
cf.cond_br %546, ^bb120, ^bb121
^bb120:
func.return %arg1 : i64
^bb121:
cf.br ^bb122
^bb122:
%549 = arith.constant 3 : i32
%550 = arith.extsi %549 : i32 to i64
%548 = func.call @poly_a3(%550) : (i64) -> i128
%551 = arith.extsi %arg0 : i64 to i128
%553 = arith.trunci %548 : i128 to i64
%554 = arith.trunci %551 : i128 to i64
%552 = arith.cmpi sgt, %553, %554 : i64
cf.cond_br %552, ^bb123, ^bb124
^bb123:
%555 = arith.constant 2 : i32
%556 = arith.extsi %555 : i32 to i64
func.return %556 : i64
^bb124:
cf.br ^bb125
^bb125:
%557 = llvm.mlir.addressof @N_val : !llvm.ptr
llvm.store %arg0, %557 : i64, !llvm.ptr
%559 = arith.constant 3 : i32
%560 = arith.extsi %559 : i32 to i64
%558 = func.call @max_k_a3_inner(%arg1, %560) : (i64, i64) -> i64
func.return %558 : i64
}
// Module static: ht_keys
llvm.mlir.global internal @ht_keys() {addr_space = 0 : i32} : !llvm.ptr {
%561 = llvm.mlir.zero : !llvm.ptr
llvm.return %561 : !llvm.ptr
}
// Module static: ht_used
llvm.mlir.global internal @ht_used() {addr_space = 0 : i32} : !llvm.ptr {
%562 = llvm.mlir.zero : !llvm.ptr
llvm.return %562 : !llvm.ptr
}
// Module static: sn_keys
llvm.mlir.global internal @sn_keys() {addr_space = 0 : i32} : !llvm.ptr {
%563 = llvm.mlir.zero : !llvm.ptr
llvm.return %563 : !llvm.ptr
}
// Module static: sn_used
llvm.mlir.global internal @sn_used() {addr_space = 0 : i32} : !llvm.ptr {
%564 = llvm.mlir.zero : !llvm.ptr
llvm.return %564 : !llvm.ptr
}
// Module static: stk_state
llvm.mlir.global internal @stk_state() {addr_space = 0 : i32} : !llvm.ptr {
%565 = llvm.mlir.zero : !llvm.ptr
llvm.return %565 : !llvm.ptr
}
// Module static: stk_n
llvm.mlir.global internal @stk_n() {addr_space = 0 : i32} : !llvm.ptr {
%566 = llvm.mlir.zero : !llvm.ptr
llvm.return %566 : !llvm.ptr
}
// Module static: stk_prod
llvm.mlir.global internal @stk_prod() {addr_space = 0 : i32} : !llvm.ptr {
%567 = llvm.mlir.zero : !llvm.ptr
llvm.return %567 : !llvm.ptr
}
// Module static: stk_sp
llvm.mlir.global internal @stk_sp(0 : i64) : i64
func.func @hash_state(%arg0: !llvm.ptr, %arg1: i64) -> i64 {
%568 = arith.constant 7046029250091385835 : i32
%570 = arith.constant 0 : i32
%569 = arith.subi %570, %568 : i32
%571 = arith.extsi %569 : i32 to i64
%572 = llvm.mlir.constant(1 : i64) : i64
%573 = llvm.alloca %572 x i64 : (i64) -> !llvm.ptr
llvm.store %571, %573 : i64, !llvm.ptr
%574 = arith.constant 0 : i32
%575 = arith.extsi %574 : i32 to i64
%576 = llvm.mlir.constant(1 : i64) : i64
%577 = llvm.alloca %576 x i64 : (i64) -> !llvm.ptr
llvm.store %575, %577 : i64, !llvm.ptr
cf.br ^bb126
^bb126:
%578 = llvm.load %577 : !llvm.ptr -> i64
%579 = arith.cmpi slt, %578, %arg1 : i64
cf.cond_br %579, ^bb127, ^bb128
^bb127:
%580 = llvm.load %573 : !llvm.ptr -> i64
%582 = llvm.load %577 : !llvm.ptr -> i64
%583 = llvm.getelementptr %arg0[%582] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%581 = llvm.load %583 : !llvm.ptr -> i64
%584 = arith.xori %580, %581 : i64
llvm.store %584, %573 : i64, !llvm.ptr
%585 = llvm.load %573 : !llvm.ptr -> i64
%586 = arith.constant 1095216660915 : i32
%588 = arith.extsi %586 : i32 to i64
%587 = arith.muli %585, %588 : i64
llvm.store %587, %573 : i64, !llvm.ptr
%589 = llvm.load %577 : !llvm.ptr -> i64
%590 = arith.constant 1 : i32
%592 = arith.extsi %590 : i32 to i64
%591 = arith.addi %589, %592 : i64
llvm.store %591, %577 : i64, !llvm.ptr
cf.br ^bb126
^bb128:
%593 = llvm.load %573 : !llvm.ptr -> i64
%594 = arith.constant 0 : i32
%596 = arith.extsi %594 : i32 to i64
%595 = arith.cmpi slt, %593, %596 : i64
cf.cond_br %595, ^bb129, ^bb130
^bb129:
%597 = llvm.load %573 : !llvm.ptr -> i64
%599 = arith.constant 0 : i64
%598 = arith.subi %599, %597 : i64
llvm.store %598, %573 : i64, !llvm.ptr
cf.br ^bb131
^bb130:
cf.br ^bb131
^bb131:
%600 = llvm.load %573 : !llvm.ptr -> i64
%601 = llvm.mlir.addressof @HT_CAP : !llvm.ptr
%602 = llvm.load %601 : !llvm.ptr -> i64
%603 = arith.remsi %600, %602 : i64
func.return %603 : i64
}
func.func @state_eq(%arg0: !llvm.ptr, %arg1: i64, %arg2: !llvm.ptr, %arg3: i64) -> i1 {
%604 = arith.cmpi ne, %arg1, %arg3 : i64
cf.cond_br %604, ^bb132, ^bb133
^bb132:
%605 = arith.constant 0 : i1
func.return %605 : i1
^bb133:
cf.br ^bb134
^bb134:
%606 = arith.constant 0 : i32
%607 = arith.extsi %606 : i32 to i64
%608 = llvm.mlir.constant(1 : i64) : i64
%609 = llvm.alloca %608 x i64 : (i64) -> !llvm.ptr
llvm.store %607, %609 : i64, !llvm.ptr
cf.br ^bb135
^bb135:
%610 = llvm.load %609 : !llvm.ptr -> i64
%611 = arith.cmpi slt, %610, %arg1 : i64
cf.cond_br %611, ^bb136, ^bb137
^bb136:
%613 = llvm.load %609 : !llvm.ptr -> i64
%614 = llvm.getelementptr %arg0[%613] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%612 = llvm.load %614 : !llvm.ptr -> i64
%616 = llvm.load %609 : !llvm.ptr -> i64
%617 = llvm.getelementptr %arg2[%616] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%615 = llvm.load %617 : !llvm.ptr -> i64
%618 = arith.cmpi ne, %612, %615 : i64
cf.cond_br %618, ^bb138, ^bb139
^bb138:
%619 = arith.constant 0 : i1
func.return %619 : i1
^bb139:
cf.br ^bb140
^bb140:
%620 = llvm.load %609 : !llvm.ptr -> i64
%621 = arith.constant 1 : i32
%623 = arith.extsi %621 : i32 to i64
%622 = arith.addi %620, %623 : i64
llvm.store %622, %609 : i64, !llvm.ptr
cf.br ^bb135
^bb137:
%624 = arith.constant 1 : i1
func.return %624 : i1
}
func.func @state_clear() -> () {
%626 = llvm.mlir.addressof @ht_used : !llvm.ptr
%627 = llvm.load %626 : !llvm.ptr -> !llvm.ptr
%628 = arith.constant 0 : i32
%629 = llvm.mlir.addressof @HT_CAP : !llvm.ptr
%630 = llvm.load %629 : !llvm.ptr -> i64
%625 = func.call @memset(%627, %628, %630) : (!llvm.ptr, i32, i64) -> !llvm.ptr
func.return
}
func.func @state_contains(%arg0: !llvm.ptr, %arg1: i64) -> i1 {
%631 = func.call @hash_state(%arg0, %arg1) : (!llvm.ptr, i64) -> i64
%632 = llvm.mlir.constant(1 : i64) : i64
%633 = llvm.alloca %632 x i64 : (i64) -> !llvm.ptr
llvm.store %631, %633 : i64, !llvm.ptr
cf.br ^bb141
^bb141:
%635 = llvm.mlir.addressof @ht_used : !llvm.ptr
%636 = llvm.load %635 : !llvm.ptr -> !llvm.ptr
%637 = llvm.load %633 : !llvm.ptr -> i64
%638 = llvm.getelementptr %636[%637] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%634 = llvm.load %638 : !llvm.ptr -> i8
%639 = arith.constant 0 : i32
%641 = arith.extsi %634 : i8 to i32
%640 = arith.cmpi ne, %641, %639 : i32
cf.cond_br %640, ^bb142, ^bb143
^bb142:
# String concatenation: !llvm.ptr + i64
%645 = llvm.mlir.addressof @ht_keys : !llvm.ptr
%646 = llvm.load %645 : !llvm.ptr -> !llvm.ptr
%647 = llvm.load %633 : !llvm.ptr -> i64
%648 = arith.constant 9 : i32
%650 = arith.extsi %648 : i32 to i64
%649 = arith.muli %647, %650 : i64
%651 = arith.constant 8 : i32
%653 = arith.extsi %651 : i32 to i64
%652 = arith.addi %649, %653 : i64
%654 = llvm.getelementptr %646[%652] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%644 = llvm.load %654 : !llvm.ptr -> i64
%642 = func.call @state_eq(%arg0, %arg1, %643, %644) : (!llvm.ptr, i64, !llvm.ptr, i64) -> i1
cf.cond_br %642, ^bb144, ^bb145
^bb144:
%655 = arith.constant 1 : i1
func.return %655 : i1
^bb145:
cf.br ^bb146
^bb146:
%656 = llvm.load %633 : !llvm.ptr -> i64
%657 = arith.constant 1 : i32
%659 = arith.extsi %657 : i32 to i64
%658 = arith.addi %656, %659 : i64
llvm.store %658, %633 : i64, !llvm.ptr
%660 = llvm.load %633 : !llvm.ptr -> i64
%661 = llvm.mlir.addressof @HT_CAP : !llvm.ptr
%662 = llvm.load %661 : !llvm.ptr -> i64
%663 = arith.cmpi eq, %660, %662 : i64
cf.cond_br %663, ^bb147, ^bb148
^bb147:
%664 = arith.constant 0 : i32
%665 = arith.extsi %664 : i32 to i64
llvm.store %665, %633 : i64, !llvm.ptr
cf.br ^bb149
^bb148:
cf.br ^bb149
^bb149:
cf.br ^bb141
^bb143:
%666 = arith.constant 0 : i1
func.return %666 : i1
}
func.func @state_insert(%arg0: !llvm.ptr, %arg1: i64) -> () {
%667 = func.call @hash_state(%arg0, %arg1) : (!llvm.ptr, i64) -> i64
%668 = llvm.mlir.constant(1 : i64) : i64
%669 = llvm.alloca %668 x i64 : (i64) -> !llvm.ptr
llvm.store %667, %669 : i64, !llvm.ptr
cf.br ^bb150
^bb150:
%671 = llvm.mlir.addressof @ht_used : !llvm.ptr
%672 = llvm.load %671 : !llvm.ptr -> !llvm.ptr
%673 = llvm.load %669 : !llvm.ptr -> i64
%674 = llvm.getelementptr %672[%673] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%670 = llvm.load %674 : !llvm.ptr -> i8
%675 = arith.constant 0 : i32
%677 = arith.extsi %670 : i8 to i32
%676 = arith.cmpi ne, %677, %675 : i32
cf.cond_br %676, ^bb151, ^bb152
^bb151:
# String concatenation: !llvm.ptr + i64
%681 = llvm.mlir.addressof @ht_keys : !llvm.ptr
%682 = llvm.load %681 : !llvm.ptr -> !llvm.ptr
%683 = llvm.load %669 : !llvm.ptr -> i64
%684 = arith.constant 9 : i32
%686 = arith.extsi %684 : i32 to i64
%685 = arith.muli %683, %686 : i64
%687 = arith.constant 8 : i32
%689 = arith.extsi %687 : i32 to i64
%688 = arith.addi %685, %689 : i64
%690 = llvm.getelementptr %682[%688] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%680 = llvm.load %690 : !llvm.ptr -> i64
%678 = func.call @state_eq(%arg0, %arg1, %679, %680) : (!llvm.ptr, i64, !llvm.ptr, i64) -> i1
cf.cond_br %678, ^bb153, ^bb154
^bb153:
func.return
^bb154:
cf.br ^bb155
^bb155:
%691 = llvm.load %669 : !llvm.ptr -> i64
%692 = arith.constant 1 : i32
%694 = arith.extsi %692 : i32 to i64
%693 = arith.addi %691, %694 : i64
llvm.store %693, %669 : i64, !llvm.ptr
%695 = llvm.load %669 : !llvm.ptr -> i64
%696 = llvm.mlir.addressof @HT_CAP : !llvm.ptr
%697 = llvm.load %696 : !llvm.ptr -> i64
%698 = arith.cmpi eq, %695, %697 : i64
cf.cond_br %698, ^bb156, ^bb157
^bb156:
%699 = arith.constant 0 : i32
%700 = arith.extsi %699 : i32 to i64
llvm.store %700, %669 : i64, !llvm.ptr
cf.br ^bb158
^bb157:
cf.br ^bb158
^bb158:
cf.br ^bb150
^bb152:
%701 = arith.constant 1 : i32
%702 = llvm.mlir.addressof @ht_used : !llvm.ptr
%703 = llvm.load %702 : !llvm.ptr -> !llvm.ptr
%704 = llvm.load %669 : !llvm.ptr -> i64
%705 = arith.trunci %701 : i32 to i8
%706 = llvm.getelementptr %703[%704] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %705, %706 : i8, !llvm.ptr
%707 = arith.constant 0 : i32
%708 = arith.extsi %707 : i32 to i64
%709 = llvm.mlir.constant(1 : i64) : i64
%710 = llvm.alloca %709 x i64 : (i64) -> !llvm.ptr
llvm.store %708, %710 : i64, !llvm.ptr
cf.br ^bb159
^bb159:
%711 = llvm.load %710 : !llvm.ptr -> i64
%712 = arith.cmpi slt, %711, %arg1 : i64
cf.cond_br %712, ^bb160, ^bb161
^bb160:
%714 = llvm.load %710 : !llvm.ptr -> i64
%715 = llvm.getelementptr %arg0[%714] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%713 = llvm.load %715 : !llvm.ptr -> i64
%716 = llvm.mlir.addressof @ht_keys : !llvm.ptr
%717 = llvm.load %716 : !llvm.ptr -> !llvm.ptr
%718 = llvm.load %669 : !llvm.ptr -> i64
%719 = arith.constant 9 : i32
%721 = arith.extsi %719 : i32 to i64
%720 = arith.muli %718, %721 : i64
%722 = llvm.load %710 : !llvm.ptr -> i64
%723 = arith.addi %720, %722 : i64
%724 = llvm.getelementptr %717[%723] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %713, %724 : i64, !llvm.ptr
%725 = llvm.load %710 : !llvm.ptr -> i64
%726 = arith.constant 1 : i32
%728 = arith.extsi %726 : i32 to i64
%727 = arith.addi %725, %728 : i64
llvm.store %727, %710 : i64, !llvm.ptr
cf.br ^bb159
^bb161:
%729 = llvm.mlir.addressof @ht_keys : !llvm.ptr
%730 = llvm.load %729 : !llvm.ptr -> !llvm.ptr
%731 = llvm.load %669 : !llvm.ptr -> i64
%732 = arith.constant 9 : i32
%734 = arith.extsi %732 : i32 to i64
%733 = arith.muli %731, %734 : i64
%735 = arith.constant 8 : i32
%737 = arith.extsi %735 : i32 to i64
%736 = arith.addi %733, %737 : i64
%738 = llvm.getelementptr %730[%736] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %738 : i64, !llvm.ptr
func.return
}
func.func @num_clear() -> () {
%740 = llvm.mlir.addressof @sn_used : !llvm.ptr
%741 = llvm.load %740 : !llvm.ptr -> !llvm.ptr
%742 = arith.constant 0 : i32
%743 = llvm.mlir.addressof @SN_CAP : !llvm.ptr
%744 = llvm.load %743 : !llvm.ptr -> i64
%739 = func.call @memset(%741, %742, %744) : (!llvm.ptr, i32, i64) -> !llvm.ptr
func.return
}
func.func @num_contains(%arg0: i64) -> i1 {
%745 = llvm.mlir.addressof @SN_CAP : !llvm.ptr
%746 = llvm.load %745 : !llvm.ptr -> i64
%747 = arith.remsi %arg0, %746 : i64
%748 = llvm.mlir.constant(1 : i64) : i64
%749 = llvm.alloca %748 x i64 : (i64) -> !llvm.ptr
llvm.store %747, %749 : i64, !llvm.ptr
%750 = llvm.load %749 : !llvm.ptr -> i64
%751 = arith.constant 0 : i32
%753 = arith.extsi %751 : i32 to i64
%752 = arith.cmpi slt, %750, %753 : i64
cf.cond_br %752, ^bb162, ^bb163
^bb162:
%754 = llvm.load %749 : !llvm.ptr -> i64
%756 = arith.constant 0 : i64
%755 = arith.subi %756, %754 : i64
llvm.store %755, %749 : i64, !llvm.ptr
cf.br ^bb164
^bb163:
cf.br ^bb164
^bb164:
cf.br ^bb165
^bb165:
%758 = llvm.mlir.addressof @sn_used : !llvm.ptr
%759 = llvm.load %758 : !llvm.ptr -> !llvm.ptr
%760 = llvm.load %749 : !llvm.ptr -> i64
%761 = llvm.getelementptr %759[%760] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%757 = llvm.load %761 : !llvm.ptr -> i8
%762 = arith.constant 0 : i32
%764 = arith.extsi %757 : i8 to i32
%763 = arith.cmpi ne, %764, %762 : i32
cf.cond_br %763, ^bb166, ^bb167
^bb166:
%766 = llvm.mlir.addressof @sn_keys : !llvm.ptr
%767 = llvm.load %766 : !llvm.ptr -> !llvm.ptr
%768 = llvm.load %749 : !llvm.ptr -> i64
%769 = llvm.getelementptr %767[%768] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%765 = llvm.load %769 : !llvm.ptr -> i64
%770 = arith.cmpi eq, %765, %arg0 : i64
cf.cond_br %770, ^bb168, ^bb169
^bb168:
%771 = arith.constant 1 : i1
func.return %771 : i1
^bb169:
cf.br ^bb170
^bb170:
%772 = llvm.load %749 : !llvm.ptr -> i64
%773 = arith.constant 1 : i32
%775 = arith.extsi %773 : i32 to i64
%774 = arith.addi %772, %775 : i64
llvm.store %774, %749 : i64, !llvm.ptr
%776 = llvm.load %749 : !llvm.ptr -> i64
%777 = llvm.mlir.addressof @SN_CAP : !llvm.ptr
%778 = llvm.load %777 : !llvm.ptr -> i64
%779 = arith.cmpi eq, %776, %778 : i64
cf.cond_br %779, ^bb171, ^bb172
^bb171:
%780 = arith.constant 0 : i32
%781 = arith.extsi %780 : i32 to i64
llvm.store %781, %749 : i64, !llvm.ptr
cf.br ^bb173
^bb172:
cf.br ^bb173
^bb173:
cf.br ^bb165
^bb167:
%782 = arith.constant 0 : i1
func.return %782 : i1
}
func.func @num_insert(%arg0: i64) -> () {
%783 = llvm.mlir.addressof @SN_CAP : !llvm.ptr
%784 = llvm.load %783 : !llvm.ptr -> i64
%785 = arith.remsi %arg0, %784 : i64
%786 = llvm.mlir.constant(1 : i64) : i64
%787 = llvm.alloca %786 x i64 : (i64) -> !llvm.ptr
llvm.store %785, %787 : i64, !llvm.ptr
%788 = llvm.load %787 : !llvm.ptr -> i64
%789 = arith.constant 0 : i32
%791 = arith.extsi %789 : i32 to i64
%790 = arith.cmpi slt, %788, %791 : i64
cf.cond_br %790, ^bb174, ^bb175
^bb174:
%792 = llvm.load %787 : !llvm.ptr -> i64
%794 = arith.constant 0 : i64
%793 = arith.subi %794, %792 : i64
llvm.store %793, %787 : i64, !llvm.ptr
cf.br ^bb176
^bb175:
cf.br ^bb176
^bb176:
cf.br ^bb177
^bb177:
%796 = llvm.mlir.addressof @sn_used : !llvm.ptr
%797 = llvm.load %796 : !llvm.ptr -> !llvm.ptr
%798 = llvm.load %787 : !llvm.ptr -> i64
%799 = llvm.getelementptr %797[%798] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%795 = llvm.load %799 : !llvm.ptr -> i8
%800 = arith.constant 0 : i32
%802 = arith.extsi %795 : i8 to i32
%801 = arith.cmpi ne, %802, %800 : i32
cf.cond_br %801, ^bb178, ^bb179
^bb178:
%804 = llvm.mlir.addressof @sn_keys : !llvm.ptr
%805 = llvm.load %804 : !llvm.ptr -> !llvm.ptr
%806 = llvm.load %787 : !llvm.ptr -> i64
%807 = llvm.getelementptr %805[%806] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%803 = llvm.load %807 : !llvm.ptr -> i64
%808 = arith.cmpi eq, %803, %arg0 : i64
cf.cond_br %808, ^bb180, ^bb181
^bb180:
func.return
^bb181:
cf.br ^bb182
^bb182:
%809 = llvm.load %787 : !llvm.ptr -> i64
%810 = arith.constant 1 : i32
%812 = arith.extsi %810 : i32 to i64
%811 = arith.addi %809, %812 : i64
llvm.store %811, %787 : i64, !llvm.ptr
%813 = llvm.load %787 : !llvm.ptr -> i64
%814 = llvm.mlir.addressof @SN_CAP : !llvm.ptr
%815 = llvm.load %814 : !llvm.ptr -> i64
%816 = arith.cmpi eq, %813, %815 : i64
cf.cond_br %816, ^bb183, ^bb184
^bb183:
%817 = arith.constant 0 : i32
%818 = arith.extsi %817 : i32 to i64
llvm.store %818, %787 : i64, !llvm.ptr
cf.br ^bb185
^bb184:
cf.br ^bb185
^bb185:
cf.br ^bb177
^bb179:
%819 = arith.constant 1 : i32
%820 = llvm.mlir.addressof @sn_used : !llvm.ptr
%821 = llvm.load %820 : !llvm.ptr -> !llvm.ptr
%822 = llvm.load %787 : !llvm.ptr -> i64
%823 = arith.trunci %819 : i32 to i8
%824 = llvm.getelementptr %821[%822] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %823, %824 : i8, !llvm.ptr
%825 = llvm.mlir.addressof @sn_keys : !llvm.ptr
%826 = llvm.load %825 : !llvm.ptr -> !llvm.ptr
%827 = llvm.load %787 : !llvm.ptr -> i64
%828 = llvm.getelementptr %826[%827] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %828 : i64, !llvm.ptr
func.return
}
func.func @mk_sum(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%829 = arith.constant 1 : i32
%831 = arith.extsi %829 : i32 to i64
%830 = arith.cmpi slt, %arg1, %831 : i64
cf.cond_br %830, ^bb186, ^bb187
^bb186:
%832 = arith.constant 0 : i32
%833 = arith.extsi %832 : i32 to i64
func.return %833 : i64
^bb187:
cf.br ^bb188
^bb188:
%834 = arith.constant 1 : i32
%836 = arith.extsi %834 : i32 to i64
%835 = arith.remsi %836, %arg2 : i64
%837 = llvm.mlir.constant(1 : i64) : i64
%838 = llvm.alloca %837 x i64 : (i64) -> !llvm.ptr
llvm.store %835, %838 : i64, !llvm.ptr
%839 = arith.constant 1 : i32
%841 = arith.extsi %839 : i32 to i64
%840 = arith.subi %arg0, %841 : i64
%842 = arith.cmpi sgt, %840, %arg1 : i64
cf.cond_br %842, ^bb189, ^bb190
^bb189:
%843 = llvm.load %838 : !llvm.ptr -> i64
func.return %843 : i64
^bb190:
cf.br ^bb191
^bb191:
func.call @state_clear() : () -> ()
func.call @num_clear() : () -> ()
%847 = arith.constant 1 : i32
%848 = arith.extsi %847 : i32 to i64
func.call @num_insert(%848) : (i64) -> ()
%849 = arith.constant 0 : i32
%850 = arith.extsi %849 : i32 to i64
%851 = llvm.mlir.addressof @stk_sp : !llvm.ptr
llvm.store %850, %851 : i64, !llvm.ptr
%852 = arith.constant 0 : i32
%853 = arith.extsi %852 : i32 to i64
%854 = llvm.mlir.constant(1 : i64) : i64
%855 = llvm.alloca %854 x i64 : (i64) -> !llvm.ptr
llvm.store %853, %855 : i64, !llvm.ptr
cf.br ^bb192
^bb192:
%856 = llvm.load %855 : !llvm.ptr -> i64
%857 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%858 = llvm.load %857 : !llvm.ptr -> i64
%859 = arith.cmpi slt, %856, %858 : i64
cf.cond_br %859, ^bb193, ^bb194
^bb193:
%860 = arith.constant 0 : i32
%861 = llvm.mlir.addressof @stk_state : !llvm.ptr
%862 = llvm.load %861 : !llvm.ptr -> !llvm.ptr
%863 = arith.constant 0 : i32
%864 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%865 = llvm.load %864 : !llvm.ptr -> i64
%867 = arith.extsi %863 : i32 to i64
%866 = arith.muli %867, %865 : i64
%868 = llvm.load %855 : !llvm.ptr -> i64
%869 = arith.addi %866, %868 : i64
%870 = arith.extsi %860 : i32 to i64
%871 = llvm.getelementptr %862[%869] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %870, %871 : i64, !llvm.ptr
%872 = llvm.load %855 : !llvm.ptr -> i64
%873 = arith.constant 1 : i32
%875 = arith.extsi %873 : i32 to i64
%874 = arith.addi %872, %875 : i64
llvm.store %874, %855 : i64, !llvm.ptr
cf.br ^bb192
^bb194:
%876 = arith.constant 0 : i32
%877 = llvm.mlir.addressof @stk_n : !llvm.ptr
%878 = llvm.load %877 : !llvm.ptr -> !llvm.ptr
%879 = arith.constant 0 : i32
%880 = arith.extsi %876 : i32 to i64
%881 = arith.extsi %879 : i32 to i64
%882 = llvm.getelementptr %878[%881] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %880, %882 : i64, !llvm.ptr
%883 = arith.constant 1 : i32
%884 = llvm.mlir.addressof @stk_prod : !llvm.ptr
%885 = llvm.load %884 : !llvm.ptr -> !llvm.ptr
%886 = arith.constant 0 : i32
%887 = arith.extsi %883 : i32 to i128
%888 = arith.extsi %886 : i32 to i64
%889 = llvm.getelementptr %885[%888] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %887, %889 : i128, !llvm.ptr
%890 = arith.constant 1 : i32
%891 = arith.extsi %890 : i32 to i64
%892 = llvm.mlir.addressof @stk_sp : !llvm.ptr
llvm.store %891, %892 : i64, !llvm.ptr
# String concatenation: !llvm.ptr + i64
%895 = arith.constant 0 : i32
%896 = arith.extsi %895 : i32 to i64
func.call @state_insert(%894, %896) : (!llvm.ptr, i64) -> ()
%898 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%899 = llvm.load %898 : !llvm.ptr -> i64
%900 = arith.constant 8 : i32
%901 = arith.extsi %900 : i32 to i64
%897 = func.call @calloc(%899, %901) : (i64, i64) -> !llvm.ptr
%903 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%904 = llvm.load %903 : !llvm.ptr -> i64
%905 = arith.constant 1 : i32
%907 = arith.extsi %905 : i32 to i64
%906 = arith.addi %904, %907 : i64
%908 = arith.constant 8 : i32
%909 = arith.extsi %908 : i32 to i64
%902 = func.call @calloc(%906, %909) : (i64, i64) -> !llvm.ptr
cf.br ^bb195
^bb195:
%910 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%911 = llvm.load %910 : !llvm.ptr -> i64
%912 = arith.constant 0 : i32
%914 = arith.extsi %912 : i32 to i64
%913 = arith.cmpi sgt, %911, %914 : i64
cf.cond_br %913, ^bb196, ^bb197
^bb196:
%915 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%916 = llvm.load %915 : !llvm.ptr -> i64
%917 = arith.constant 1 : i32
%919 = arith.extsi %917 : i32 to i64
%918 = arith.subi %916, %919 : i64
%920 = llvm.mlir.addressof @stk_sp : !llvm.ptr
llvm.store %918, %920 : i64, !llvm.ptr
%922 = llvm.mlir.addressof @stk_n : !llvm.ptr
%923 = llvm.load %922 : !llvm.ptr -> !llvm.ptr
%924 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%925 = llvm.load %924 : !llvm.ptr -> i64
%926 = llvm.getelementptr %923[%925] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%921 = llvm.load %926 : !llvm.ptr -> i64
%928 = llvm.mlir.addressof @stk_prod : !llvm.ptr
%929 = llvm.load %928 : !llvm.ptr -> !llvm.ptr
%930 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%931 = llvm.load %930 : !llvm.ptr -> i64
%932 = llvm.getelementptr %929[%931] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%927 = llvm.load %932 : !llvm.ptr -> i128
%933 = arith.subi %arg0, %921 : i64
%934 = memref.alloca() {type = memref<8xi64>} : memref<8xi64>
%935 = arith.constant 0 : i32
%936 = arith.extsi %935 : i32 to i64
%937 = llvm.mlir.constant(1 : i64) : i64
%938 = llvm.alloca %937 x i64 : (i64) -> !llvm.ptr
llvm.store %936, %938 : i64, !llvm.ptr
%939 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%940 = llvm.load %939 : !llvm.ptr -> i64
%941 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%942 = llvm.load %941 : !llvm.ptr -> i64
%943 = arith.muli %940, %942 : i64
cf.br ^bb198
^bb198:
%944 = llvm.load %938 : !llvm.ptr -> i64
%945 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%946 = llvm.load %945 : !llvm.ptr -> i64
%947 = arith.cmpi slt, %944, %946 : i64
cf.cond_br %947, ^bb199, ^bb200
^bb199:
%949 = llvm.mlir.addressof @stk_state : !llvm.ptr
%950 = llvm.load %949 : !llvm.ptr -> !llvm.ptr
%951 = llvm.load %938 : !llvm.ptr -> i64
%952 = arith.addi %943, %951 : i64
%953 = llvm.getelementptr %950[%952] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%948 = llvm.load %953 : !llvm.ptr -> i64
%954 = llvm.load %938 : !llvm.ptr -> i64
%955 = arith.index_cast %954 : i32 to index
memref.store %948, %934[%955] : memref<8xi64>
%956 = llvm.load %938 : !llvm.ptr -> i64
%957 = arith.constant 1 : i32
%959 = arith.extsi %957 : i32 to i64
%958 = arith.addi %956, %959 : i64
llvm.store %958, %938 : i64, !llvm.ptr
cf.br ^bb198
^bb200:
%960 = arith.constant 0 : i32
%961 = arith.extsi %960 : i32 to i64
%962 = llvm.mlir.constant(1 : i64) : i64
%963 = llvm.alloca %962 x i64 : (i64) -> !llvm.ptr
llvm.store %961, %963 : i64, !llvm.ptr
cf.br ^bb201
^bb201:
%964 = llvm.load %963 : !llvm.ptr -> i64
%965 = arith.cmpi slt, %964, %921 : i64
cf.cond_br %965, ^bb202, ^bb203
^bb202:
%967 = llvm.load %963 : !llvm.ptr -> i64
%968 = arith.index_cast %967 : i32 to index
%966 = memref.load %934[%968] : memref<8xi64>
%969 = arith.cmpi sle, %966, %arg1 : i64
%970 = scf.if %969 -> (i1) {
%971 = func.call @num_contains(%966) : (i64) -> i1
%973 = arith.constant 1 : i1
%972 = arith.xori %971, %973 : i1
scf.yield %972 : i1
} else {
%975 = arith.constant false
scf.yield %975 : i1
}
cf.cond_br %970, ^bb204, ^bb205
^bb204:
func.call @num_insert(%966) : (i64) -> ()
%978 = llvm.load %838 : !llvm.ptr -> i64
%979 = arith.remsi %966, %arg2 : i64
%977 = func.call @madd(%978, %979) : (i64, i64) -> i64
llvm.store %977, %838 : i64, !llvm.ptr
cf.br ^bb206
^bb205:
cf.br ^bb206
^bb206:
%980 = llvm.load %963 : !llvm.ptr -> i64
%981 = arith.constant 1 : i32
%983 = arith.extsi %981 : i32 to i64
%982 = arith.addi %980, %983 : i64
llvm.store %982, %963 : i64, !llvm.ptr
cf.br ^bb201
^bb203:
%984 = arith.constant 0 : i32
%985 = arith.extsi %984 : i32 to i64
%986 = llvm.mlir.constant(1 : i64) : i64
%987 = llvm.alloca %986 x i64 : (i64) -> !llvm.ptr
llvm.store %985, %987 : i64, !llvm.ptr
%988 = arith.constant 0 : i32
%989 = arith.extsi %988 : i32 to i64
%990 = llvm.mlir.constant(1 : i64) : i64
%991 = llvm.alloca %990 x i64 : (i64) -> !llvm.ptr
llvm.store %989, %991 : i64, !llvm.ptr
cf.br ^bb207
^bb207:
%992 = llvm.load %991 : !llvm.ptr -> i64
%993 = arith.cmpi slt, %992, %921 : i64
cf.cond_br %993, ^bb208, ^bb209
^bb208:
%994 = llvm.load %991 : !llvm.ptr -> i64
%995 = arith.constant 0 : i32
%997 = arith.extsi %995 : i32 to i64
%996 = arith.cmpi eq, %994, %997 : i64
%998 = scf.if %996 -> (i1) {
%999 = arith.constant true
scf.yield %999 : i1
} else {
%1001 = llvm.load %991 : !llvm.ptr -> i64
%1002 = arith.index_cast %1001 : i32 to index
%1000 = memref.load %934[%1002] : memref<8xi64>
%1004 = llvm.load %991 : !llvm.ptr -> i64
%1005 = arith.constant 1 : i32
%1007 = arith.extsi %1005 : i32 to i64
%1006 = arith.subi %1004, %1007 : i64
%1008 = arith.index_cast %1006 : i32 to index
%1003 = memref.load %934[%1008] : memref<8xi64>
%1009 = arith.cmpi ne, %1000, %1003 : i64
scf.yield %1009 : i1
}
cf.cond_br %998, ^bb210, ^bb211
^bb210:
%1011 = llvm.load %991 : !llvm.ptr -> i64
%1012 = arith.index_cast %1011 : i32 to index
%1010 = memref.load %934[%1012] : memref<8xi64>
%1013 = llvm.load %987 : !llvm.ptr -> i64
%1014 = llvm.getelementptr %902[%1013] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1010, %1014 : i64, !llvm.ptr
%1015 = llvm.load %987 : !llvm.ptr -> i64
%1016 = arith.constant 1 : i32
%1018 = arith.extsi %1016 : i32 to i64
%1017 = arith.addi %1015, %1018 : i64
llvm.store %1017, %987 : i64, !llvm.ptr
cf.br ^bb212
^bb211:
cf.br ^bb212
^bb212:
%1019 = llvm.load %991 : !llvm.ptr -> i64
%1020 = arith.constant 1 : i32
%1022 = arith.extsi %1020 : i32 to i64
%1021 = arith.addi %1019, %1022 : i64
llvm.store %1021, %991 : i64, !llvm.ptr
cf.br ^bb207
^bb209:
%1023 = arith.constant 0 : i32
%1025 = arith.extsi %1023 : i32 to i64
%1024 = arith.cmpi sgt, %933, %1025 : i64
cf.cond_br %1024, ^bb213, ^bb214
^bb213:
%1026 = arith.constant 1 : i32
%1027 = llvm.load %987 : !llvm.ptr -> i64
%1028 = arith.extsi %1026 : i32 to i64
%1029 = llvm.getelementptr %902[%1027] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1028, %1029 : i64, !llvm.ptr
%1030 = llvm.load %987 : !llvm.ptr -> i64
%1031 = arith.constant 1 : i32
%1033 = arith.extsi %1031 : i32 to i64
%1032 = arith.addi %1030, %1033 : i64
llvm.store %1032, %987 : i64, !llvm.ptr
cf.br ^bb215
^bb214:
cf.br ^bb215
^bb215:
%1034 = arith.constant 0 : i32
%1035 = arith.extsi %1034 : i32 to i64
%1036 = llvm.mlir.constant(1 : i64) : i64
%1037 = llvm.alloca %1036 x i64 : (i64) -> !llvm.ptr
llvm.store %1035, %1037 : i64, !llvm.ptr
cf.br ^bb216
^bb216:
%1038 = llvm.load %1037 : !llvm.ptr -> i64
%1039 = llvm.load %987 : !llvm.ptr -> i64
%1040 = arith.cmpi slt, %1038, %1039 : i64
cf.cond_br %1040, ^bb217, ^bb218
^bb217:
%1042 = llvm.load %1037 : !llvm.ptr -> i64
%1043 = llvm.getelementptr %902[%1042] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1041 = llvm.load %1043 : !llvm.ptr -> i64
%1044 = arith.constant 0 : i32
%1045 = arith.extsi %1044 : i32 to i128
%1046 = arith.constant 0 : i32
%1047 = arith.extsi %1046 : i32 to i128
%1048 = arith.constant 0 : i1
%1049 = arith.constant 1 : i32
%1051 = arith.extsi %1049 : i32 to i64
%1050 = arith.cmpi eq, %1041, %1051 : i64
cf.cond_br %1050, ^bb219, ^bb220
^bb219:
%1052 = arith.constant 0 : i32
%1054 = arith.extsi %1052 : i32 to i64
%1053 = arith.cmpi eq, %933, %1054 : i64
cf.cond_br %1053, ^bb222, ^bb223
^bb222:
%1055 = llvm.load %1037 : !llvm.ptr -> i64
%1056 = arith.constant 1 : i32
%1058 = arith.extsi %1056 : i32 to i64
%1057 = arith.addi %1055, %1058 : i64
llvm.store %1057, %1037 : i64, !llvm.ptr
cf.br ^bb216
^bb223:
cf.br ^bb224
^bb224:
%1059 = arith.constant 1 : i32
%1061 = arith.extsi %1059 : i32 to i64
%1060 = arith.addi %arg1, %1061 : i64
%1062 = arith.extsi %1060 : i64 to i128
%1063 = arith.extsi %arg0 : i64 to i128
%1065 = arith.trunci %1062 : i128 to i64
%1066 = arith.trunci %1063 : i128 to i64
%1064 = arith.divsi %1065, %1066 : i64
%1068 = arith.trunci %927 : i128 to i64
%1067 = arith.cmpi sgt, %1068, %1064 : i64
cf.cond_br %1067, ^bb225, ^bb226
^bb225:
%1069 = llvm.load %1037 : !llvm.ptr -> i64
%1070 = arith.constant 1 : i32
%1072 = arith.extsi %1070 : i32 to i64
%1071 = arith.addi %1069, %1072 : i64
llvm.store %1071, %1037 : i64, !llvm.ptr
cf.br ^bb216
^bb226:
cf.br ^bb227
^bb227:
%1073 = arith.extsi %arg0 : i64 to i128
%1075 = arith.trunci %1073 : i128 to i64
%1076 = arith.trunci %927 : i128 to i64
%1074 = arith.muli %1075, %1076 : i64
%1077 = arith.constant 1 : i32
%1079 = arith.extsi %1077 : i32 to i64
%1078 = arith.subi %1074, %1079 : i64
%1080 = arith.extsi %1078 : i64 to i128
%1081 = arith.constant 1 : i32
%1083 = arith.trunci %1080 : i128 to i64
%1084 = arith.extsi %1081 : i32 to i64
%1082 = arith.cmpi sle, %1083, %1084 : i64
%1085 = scf.if %1082 -> (i1) {
%1086 = arith.constant true
scf.yield %1086 : i1
} else {
%1087 = arith.extsi %arg1 : i64 to i128
%1089 = arith.trunci %1080 : i128 to i64
%1090 = arith.trunci %1087 : i128 to i64
%1088 = arith.cmpi sgt, %1089, %1090 : i64
scf.yield %1088 : i1
}
cf.cond_br %1085, ^bb228, ^bb229
^bb228:
%1091 = llvm.load %1037 : !llvm.ptr -> i64
%1092 = arith.constant 1 : i32
%1094 = arith.extsi %1092 : i32 to i64
%1093 = arith.addi %1091, %1094 : i64
llvm.store %1093, %1037 : i64, !llvm.ptr
cf.br ^bb216
^bb229:
cf.br ^bb230
^bb230:
%1096 = arith.trunci %927 : i128 to i64
%1097 = arith.trunci %1080 : i128 to i64
%1095 = arith.muli %1096, %1097 : i64
%1098 = arith.extsi %1095 : i64 to i128
cf.br ^bb221(%1080, %1098 : i128, i128)
^bb220:
%1099 = arith.extsi %1041 : i64 to i128
%1101 = arith.trunci %927 : i128 to i64
%1102 = arith.trunci %1099 : i128 to i64
%1100 = arith.divsi %1101, %1102 : i64
%1103 = arith.extsi %1100 : i64 to i128
%1104 = arith.addi %arg1, %1041 : i64
%1105 = arith.extsi %1104 : i64 to i128
%1106 = arith.extsi %arg0 : i64 to i128
%1108 = arith.trunci %1105 : i128 to i64
%1109 = arith.trunci %1106 : i128 to i64
%1107 = arith.divsi %1108, %1109 : i64
%1111 = arith.trunci %1103 : i128 to i64
%1110 = arith.cmpi sgt, %1111, %1107 : i64
cf.cond_br %1110, ^bb231, ^bb232
^bb231:
%1112 = llvm.load %1037 : !llvm.ptr -> i64
%1113 = arith.constant 1 : i32
%1115 = arith.extsi %1113 : i32 to i64
%1114 = arith.addi %1112, %1115 : i64
llvm.store %1114, %1037 : i64, !llvm.ptr
cf.br ^bb216
^bb232:
cf.br ^bb233
^bb233:
%1116 = arith.extsi %arg0 : i64 to i128
%1118 = arith.trunci %1116 : i128 to i64
%1119 = arith.trunci %1103 : i128 to i64
%1117 = arith.muli %1118, %1119 : i64
%1120 = arith.extsi %1041 : i64 to i128
%1122 = arith.trunci %1120 : i128 to i64
%1121 = arith.subi %1117, %1122 : i64
%1123 = arith.extsi %1121 : i64 to i128
%1124 = arith.extsi %1041 : i64 to i128
%1126 = arith.trunci %1123 : i128 to i64
%1127 = arith.trunci %1124 : i128 to i64
%1125 = arith.cmpi sle, %1126, %1127 : i64
%1128 = scf.if %1125 -> (i1) {
%1129 = arith.constant true
scf.yield %1129 : i1
} else {
%1130 = arith.extsi %arg1 : i64 to i128
%1132 = arith.trunci %1123 : i128 to i64
%1133 = arith.trunci %1130 : i128 to i64
%1131 = arith.cmpi sgt, %1132, %1133 : i64
scf.yield %1131 : i1
}
cf.cond_br %1128, ^bb234, ^bb235
^bb234:
%1134 = llvm.load %1037 : !llvm.ptr -> i64
%1135 = arith.constant 1 : i32
%1137 = arith.extsi %1135 : i32 to i64
%1136 = arith.addi %1134, %1137 : i64
llvm.store %1136, %1037 : i64, !llvm.ptr
cf.br ^bb216
^bb235:
cf.br ^bb236
^bb236:
%1139 = arith.trunci %1103 : i128 to i64
%1140 = arith.trunci %1123 : i128 to i64
%1138 = arith.muli %1139, %1140 : i64
%1141 = arith.extsi %1138 : i64 to i128
cf.br ^bb221(%1123, %1141 : i128, i128)
^bb221(%1142: i128, %1143: i128):
%1144 = arith.constant 1 : i32
%1146 = arith.extsi %1144 : i32 to i64
%1145 = arith.cmpi eq, %1041, %1146 : i64
cf.cond_br %1145, ^bb237, ^bb238
^bb237:
%1147 = arith.constant 0 : i32
%1148 = arith.extsi %1147 : i32 to i64
%1149 = llvm.mlir.constant(1 : i64) : i64
%1150 = llvm.alloca %1149 x i64 : (i64) -> !llvm.ptr
llvm.store %1148, %1150 : i64, !llvm.ptr
cf.br ^bb240
^bb240:
%1151 = llvm.load %1150 : !llvm.ptr -> i64
%1152 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%1153 = llvm.load %1152 : !llvm.ptr -> i64
%1154 = arith.cmpi slt, %1151, %1153 : i64
cf.cond_br %1154, ^bb241, ^bb242
^bb241:
%1155 = arith.constant 0 : i32
%1156 = llvm.load %1150 : !llvm.ptr -> i64
%1157 = arith.extsi %1155 : i32 to i64
%1158 = llvm.getelementptr %897[%1156] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1157, %1158 : i64, !llvm.ptr
%1159 = llvm.load %1150 : !llvm.ptr -> i64
%1160 = arith.constant 1 : i32
%1162 = arith.extsi %1160 : i32 to i64
%1161 = arith.addi %1159, %1162 : i64
llvm.store %1161, %1150 : i64, !llvm.ptr
cf.br ^bb240
^bb242:
%1163 = arith.constant 0 : i32
%1164 = arith.extsi %1163 : i32 to i64
%1165 = llvm.mlir.constant(1 : i64) : i64
%1166 = llvm.alloca %1165 x i64 : (i64) -> !llvm.ptr
llvm.store %1164, %1166 : i64, !llvm.ptr
cf.br ^bb243
^bb243:
%1167 = llvm.load %1166 : !llvm.ptr -> i64
%1168 = arith.cmpi slt, %1167, %921 : i64
cf.cond_br %1168, ^bb244, ^bb245
^bb244:
%1170 = llvm.load %1166 : !llvm.ptr -> i64
%1171 = arith.index_cast %1170 : i32 to index
%1169 = memref.load %934[%1171] : memref<8xi64>
%1172 = llvm.load %1166 : !llvm.ptr -> i64
%1173 = llvm.getelementptr %897[%1172] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1169, %1173 : i64, !llvm.ptr
%1174 = llvm.load %1166 : !llvm.ptr -> i64
%1175 = arith.constant 1 : i32
%1177 = arith.extsi %1175 : i32 to i64
%1176 = arith.addi %1174, %1177 : i64
llvm.store %1176, %1166 : i64, !llvm.ptr
cf.br ^bb243
^bb245:
%1178 = llvm.mlir.constant(1 : i64) : i64
%1179 = llvm.alloca %1178 x i64 : (i64) -> !llvm.ptr
llvm.store %921, %1179 : i64, !llvm.ptr
%1180 = arith.constant 0 : i32
%1181 = arith.extsi %1180 : i32 to i64
%1182 = llvm.mlir.constant(1 : i64) : i64
%1183 = llvm.alloca %1182 x i64 : (i64) -> !llvm.ptr
llvm.store %1181, %1183 : i64, !llvm.ptr
cf.br ^bb246
^bb246:
%1184 = llvm.load %1183 : !llvm.ptr -> i64
%1185 = arith.cmpi slt, %1184, %921 : i64
cf.cond_br %1185, ^bb247, ^bb248
^bb247:
%1187 = llvm.load %1183 : !llvm.ptr -> i64
%1188 = arith.index_cast %1187 : i32 to index
%1186 = memref.load %934[%1188] : memref<8xi64>
%1189 = arith.extsi %1186 : i64 to i128
%1191 = arith.trunci %1142 : i128 to i64
%1192 = arith.trunci %1189 : i128 to i64
%1190 = arith.cmpi slt, %1191, %1192 : i64
cf.cond_br %1190, ^bb249, ^bb250
^bb249:
%1193 = llvm.load %1183 : !llvm.ptr -> i64
llvm.store %1193, %1179 : i64, !llvm.ptr
cf.br ^bb248
^bb250:
cf.br ^bb251
^bb251:
%1194 = llvm.load %1183 : !llvm.ptr -> i64
%1195 = arith.constant 1 : i32
%1197 = arith.extsi %1195 : i32 to i64
%1196 = arith.addi %1194, %1197 : i64
llvm.store %1196, %1183 : i64, !llvm.ptr
cf.br ^bb246
^bb248:
%1198 = llvm.mlir.constant(1 : i64) : i64
%1199 = llvm.alloca %1198 x i64 : (i64) -> !llvm.ptr
llvm.store %921, %1199 : i64, !llvm.ptr
cf.br ^bb252
^bb252:
%1200 = llvm.load %1199 : !llvm.ptr -> i64
%1201 = llvm.load %1179 : !llvm.ptr -> i64
%1202 = arith.cmpi sgt, %1200, %1201 : i64
cf.cond_br %1202, ^bb253, ^bb254
^bb253:
%1204 = llvm.load %1199 : !llvm.ptr -> i64
%1205 = arith.constant 1 : i32
%1207 = arith.extsi %1205 : i32 to i64
%1206 = arith.subi %1204, %1207 : i64
%1208 = llvm.getelementptr %897[%1206] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1203 = llvm.load %1208 : !llvm.ptr -> i64
%1209 = llvm.load %1199 : !llvm.ptr -> i64
%1210 = llvm.getelementptr %897[%1209] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1203, %1210 : i64, !llvm.ptr
%1211 = llvm.load %1199 : !llvm.ptr -> i64
%1212 = arith.constant 1 : i32
%1214 = arith.extsi %1212 : i32 to i64
%1213 = arith.subi %1211, %1214 : i64
llvm.store %1213, %1199 : i64, !llvm.ptr
cf.br ^bb252
^bb254:
%1215 = arith.trunci %1142 : i128 to i64
%1216 = llvm.load %1179 : !llvm.ptr -> i64
%1217 = llvm.getelementptr %897[%1216] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1215, %1217 : i64, !llvm.ptr
%1218 = arith.constant 1 : i32
%1220 = arith.extsi %1218 : i32 to i64
%1219 = arith.addi %921, %1220 : i64
%1221 = func.call @state_contains(%897, %1219) : (!llvm.ptr, i64) -> i1
%1223 = arith.constant 1 : i1
%1222 = arith.xori %1221, %1223 : i1
cf.cond_br %1222, ^bb255, ^bb256
^bb255:
func.call @state_insert(%897, %1219) : (!llvm.ptr, i64) -> ()
%1226 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%1227 = llvm.load %1226 : !llvm.ptr -> i64
%1228 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%1229 = llvm.load %1228 : !llvm.ptr -> i64
%1230 = arith.muli %1227, %1229 : i64
%1231 = arith.constant 0 : i32
%1232 = arith.extsi %1231 : i32 to i64
%1233 = llvm.mlir.constant(1 : i64) : i64
%1234 = llvm.alloca %1233 x i64 : (i64) -> !llvm.ptr
llvm.store %1232, %1234 : i64, !llvm.ptr
cf.br ^bb258
^bb258:
%1235 = llvm.load %1234 : !llvm.ptr -> i64
%1236 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%1237 = llvm.load %1236 : !llvm.ptr -> i64
%1238 = arith.cmpi slt, %1235, %1237 : i64
cf.cond_br %1238, ^bb259, ^bb260
^bb259:
%1240 = llvm.load %1234 : !llvm.ptr -> i64
%1241 = llvm.getelementptr %897[%1240] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1239 = llvm.load %1241 : !llvm.ptr -> i64
%1242 = llvm.mlir.addressof @stk_state : !llvm.ptr
%1243 = llvm.load %1242 : !llvm.ptr -> !llvm.ptr
%1244 = llvm.load %1234 : !llvm.ptr -> i64
%1245 = arith.addi %1230, %1244 : i64
%1246 = llvm.getelementptr %1243[%1245] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1239, %1246 : i64, !llvm.ptr
%1247 = llvm.load %1234 : !llvm.ptr -> i64
%1248 = arith.constant 1 : i32
%1250 = arith.extsi %1248 : i32 to i64
%1249 = arith.addi %1247, %1250 : i64
llvm.store %1249, %1234 : i64, !llvm.ptr
cf.br ^bb258
^bb260:
%1251 = llvm.mlir.addressof @stk_n : !llvm.ptr
%1252 = llvm.load %1251 : !llvm.ptr -> !llvm.ptr
%1253 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%1254 = llvm.load %1253 : !llvm.ptr -> i64
%1255 = llvm.getelementptr %1252[%1254] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1219, %1255 : i64, !llvm.ptr
%1256 = llvm.mlir.addressof @stk_prod : !llvm.ptr
%1257 = llvm.load %1256 : !llvm.ptr -> !llvm.ptr
%1258 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%1259 = llvm.load %1258 : !llvm.ptr -> i64
%1260 = llvm.getelementptr %1257[%1259] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %1143, %1260 : i128, !llvm.ptr
%1261 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%1262 = llvm.load %1261 : !llvm.ptr -> i64
%1263 = arith.constant 1 : i32
%1265 = arith.extsi %1263 : i32 to i64
%1264 = arith.addi %1262, %1265 : i64
%1266 = llvm.mlir.addressof @stk_sp : !llvm.ptr
llvm.store %1264, %1266 : i64, !llvm.ptr
cf.br ^bb257
^bb256:
cf.br ^bb257
^bb257:
cf.br ^bb239
^bb238:
%1267 = arith.constant 0 : i32
%1268 = arith.extsi %1267 : i32 to i64
%1269 = llvm.mlir.constant(1 : i64) : i64
%1270 = llvm.alloca %1269 x i64 : (i64) -> !llvm.ptr
llvm.store %1268, %1270 : i64, !llvm.ptr
cf.br ^bb261
^bb261:
%1271 = llvm.load %1270 : !llvm.ptr -> i64
%1272 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%1273 = llvm.load %1272 : !llvm.ptr -> i64
%1274 = arith.cmpi slt, %1271, %1273 : i64
cf.cond_br %1274, ^bb262, ^bb263
^bb262:
%1275 = arith.constant 0 : i32
%1276 = llvm.load %1270 : !llvm.ptr -> i64
%1277 = arith.extsi %1275 : i32 to i64
%1278 = llvm.getelementptr %897[%1276] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1277, %1278 : i64, !llvm.ptr
%1279 = llvm.load %1270 : !llvm.ptr -> i64
%1280 = arith.constant 1 : i32
%1282 = arith.extsi %1280 : i32 to i64
%1281 = arith.addi %1279, %1282 : i64
llvm.store %1281, %1270 : i64, !llvm.ptr
cf.br ^bb261
^bb263:
%1283 = arith.constant 1 : i32
%1285 = arith.constant 0 : i32
%1284 = arith.subi %1285, %1283 : i32
%1286 = arith.extsi %1284 : i32 to i64
%1287 = llvm.mlir.constant(1 : i64) : i64
%1288 = llvm.alloca %1287 x i64 : (i64) -> !llvm.ptr
llvm.store %1286, %1288 : i64, !llvm.ptr
%1289 = arith.constant 0 : i32
%1290 = arith.extsi %1289 : i32 to i64
%1291 = llvm.mlir.constant(1 : i64) : i64
%1292 = llvm.alloca %1291 x i64 : (i64) -> !llvm.ptr
llvm.store %1290, %1292 : i64, !llvm.ptr
cf.br ^bb264
^bb264:
%1293 = llvm.load %1292 : !llvm.ptr -> i64
%1294 = arith.cmpi slt, %1293, %921 : i64
cf.cond_br %1294, ^bb265, ^bb266
^bb265:
%1296 = llvm.load %1292 : !llvm.ptr -> i64
%1297 = arith.index_cast %1296 : i32 to index
%1295 = memref.load %934[%1297] : memref<8xi64>
%1298 = arith.cmpi eq, %1295, %1041 : i64
cf.cond_br %1298, ^bb267, ^bb268
^bb267:
%1299 = llvm.load %1292 : !llvm.ptr -> i64
llvm.store %1299, %1288 : i64, !llvm.ptr
cf.br ^bb266
^bb268:
cf.br ^bb269
^bb269:
%1300 = llvm.load %1292 : !llvm.ptr -> i64
%1301 = arith.constant 1 : i32
%1303 = arith.extsi %1301 : i32 to i64
%1302 = arith.addi %1300, %1303 : i64
llvm.store %1302, %1292 : i64, !llvm.ptr
cf.br ^bb264
^bb266:
%1304 = llvm.load %1288 : !llvm.ptr -> i64
%1305 = arith.constant 0 : i32
%1307 = arith.extsi %1305 : i32 to i64
%1306 = arith.cmpi slt, %1304, %1307 : i64
cf.cond_br %1306, ^bb270, ^bb271
^bb270:
%1308 = llvm.load %1037 : !llvm.ptr -> i64
%1309 = arith.constant 1 : i32
%1311 = arith.extsi %1309 : i32 to i64
%1310 = arith.addi %1308, %1311 : i64
llvm.store %1310, %1037 : i64, !llvm.ptr
cf.br ^bb216
^bb271:
cf.br ^bb272
^bb272:
%1312 = arith.constant 0 : i32
%1313 = arith.extsi %1312 : i32 to i64
%1314 = llvm.mlir.constant(1 : i64) : i64
%1315 = llvm.alloca %1314 x i64 : (i64) -> !llvm.ptr
llvm.store %1313, %1315 : i64, !llvm.ptr
%1316 = arith.constant 0 : i32
%1317 = arith.extsi %1316 : i32 to i64
%1318 = llvm.mlir.constant(1 : i64) : i64
%1319 = llvm.alloca %1318 x i64 : (i64) -> !llvm.ptr
llvm.store %1317, %1319 : i64, !llvm.ptr
cf.br ^bb273
^bb273:
%1320 = llvm.load %1319 : !llvm.ptr -> i64
%1321 = arith.cmpi slt, %1320, %921 : i64
cf.cond_br %1321, ^bb274, ^bb275
^bb274:
%1322 = llvm.load %1319 : !llvm.ptr -> i64
%1323 = llvm.load %1288 : !llvm.ptr -> i64
%1324 = arith.cmpi ne, %1322, %1323 : i64
cf.cond_br %1324, ^bb276, ^bb277
^bb276:
%1326 = llvm.load %1319 : !llvm.ptr -> i64
%1327 = arith.index_cast %1326 : i32 to index
%1325 = memref.load %934[%1327] : memref<8xi64>
%1328 = llvm.load %1315 : !llvm.ptr -> i64
%1329 = llvm.getelementptr %897[%1328] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1325, %1329 : i64, !llvm.ptr
%1330 = llvm.load %1315 : !llvm.ptr -> i64
%1331 = arith.constant 1 : i32
%1333 = arith.extsi %1331 : i32 to i64
%1332 = arith.addi %1330, %1333 : i64
llvm.store %1332, %1315 : i64, !llvm.ptr
cf.br ^bb278
^bb277:
cf.br ^bb278
^bb278:
%1334 = llvm.load %1319 : !llvm.ptr -> i64
%1335 = arith.constant 1 : i32
%1337 = arith.extsi %1335 : i32 to i64
%1336 = arith.addi %1334, %1337 : i64
llvm.store %1336, %1319 : i64, !llvm.ptr
cf.br ^bb273
^bb275:
%1338 = arith.constant 1 : i32
%1340 = arith.extsi %1338 : i32 to i64
%1339 = arith.subi %921, %1340 : i64
%1341 = llvm.mlir.constant(1 : i64) : i64
%1342 = llvm.alloca %1341 x i64 : (i64) -> !llvm.ptr
llvm.store %1339, %1342 : i64, !llvm.ptr
%1343 = arith.constant 0 : i32
%1344 = arith.extsi %1343 : i32 to i64
%1345 = llvm.mlir.constant(1 : i64) : i64
%1346 = llvm.alloca %1345 x i64 : (i64) -> !llvm.ptr
llvm.store %1344, %1346 : i64, !llvm.ptr
cf.br ^bb279
^bb279:
%1347 = llvm.load %1346 : !llvm.ptr -> i64
%1348 = arith.cmpi slt, %1347, %1339 : i64
cf.cond_br %1348, ^bb280, ^bb281
^bb280:
%1350 = llvm.load %1346 : !llvm.ptr -> i64
%1351 = llvm.getelementptr %897[%1350] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1349 = llvm.load %1351 : !llvm.ptr -> i64
%1352 = arith.extsi %1349 : i64 to i128
%1354 = arith.trunci %1142 : i128 to i64
%1355 = arith.trunci %1352 : i128 to i64
%1353 = arith.cmpi slt, %1354, %1355 : i64
cf.cond_br %1353, ^bb282, ^bb283
^bb282:
%1356 = llvm.load %1346 : !llvm.ptr -> i64
llvm.store %1356, %1342 : i64, !llvm.ptr
cf.br ^bb281
^bb283:
cf.br ^bb284
^bb284:
%1357 = llvm.load %1346 : !llvm.ptr -> i64
%1358 = arith.constant 1 : i32
%1360 = arith.extsi %1358 : i32 to i64
%1359 = arith.addi %1357, %1360 : i64
llvm.store %1359, %1346 : i64, !llvm.ptr
cf.br ^bb279
^bb281:
%1361 = llvm.mlir.constant(1 : i64) : i64
%1362 = llvm.alloca %1361 x i64 : (i64) -> !llvm.ptr
llvm.store %1339, %1362 : i64, !llvm.ptr
cf.br ^bb285
^bb285:
%1363 = llvm.load %1362 : !llvm.ptr -> i64
%1364 = llvm.load %1342 : !llvm.ptr -> i64
%1365 = arith.cmpi sgt, %1363, %1364 : i64
cf.cond_br %1365, ^bb286, ^bb287
^bb286:
%1367 = llvm.load %1362 : !llvm.ptr -> i64
%1368 = arith.constant 1 : i32
%1370 = arith.extsi %1368 : i32 to i64
%1369 = arith.subi %1367, %1370 : i64
%1371 = llvm.getelementptr %897[%1369] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1366 = llvm.load %1371 : !llvm.ptr -> i64
%1372 = llvm.load %1362 : !llvm.ptr -> i64
%1373 = llvm.getelementptr %897[%1372] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1366, %1373 : i64, !llvm.ptr
%1374 = llvm.load %1362 : !llvm.ptr -> i64
%1375 = arith.constant 1 : i32
%1377 = arith.extsi %1375 : i32 to i64
%1376 = arith.subi %1374, %1377 : i64
llvm.store %1376, %1362 : i64, !llvm.ptr
cf.br ^bb285
^bb287:
%1378 = arith.trunci %1142 : i128 to i64
%1379 = llvm.load %1342 : !llvm.ptr -> i64
%1380 = llvm.getelementptr %897[%1379] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1378, %1380 : i64, !llvm.ptr
%1381 = arith.constant 1 : i32
%1383 = arith.extsi %1381 : i32 to i64
%1382 = arith.addi %1339, %1383 : i64
%1384 = func.call @state_contains(%897, %1382) : (!llvm.ptr, i64) -> i1
%1386 = arith.constant 1 : i1
%1385 = arith.xori %1384, %1386 : i1
cf.cond_br %1385, ^bb288, ^bb289
^bb288:
func.call @state_insert(%897, %1382) : (!llvm.ptr, i64) -> ()
%1389 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%1390 = llvm.load %1389 : !llvm.ptr -> i64
%1391 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%1392 = llvm.load %1391 : !llvm.ptr -> i64
%1393 = arith.muli %1390, %1392 : i64
%1394 = arith.constant 0 : i32
%1395 = arith.extsi %1394 : i32 to i64
%1396 = llvm.mlir.constant(1 : i64) : i64
%1397 = llvm.alloca %1396 x i64 : (i64) -> !llvm.ptr
llvm.store %1395, %1397 : i64, !llvm.ptr
cf.br ^bb291
^bb291:
%1398 = llvm.load %1397 : !llvm.ptr -> i64
%1399 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%1400 = llvm.load %1399 : !llvm.ptr -> i64
%1401 = arith.cmpi slt, %1398, %1400 : i64
cf.cond_br %1401, ^bb292, ^bb293
^bb292:
%1403 = llvm.load %1397 : !llvm.ptr -> i64
%1404 = llvm.getelementptr %897[%1403] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1402 = llvm.load %1404 : !llvm.ptr -> i64
%1405 = llvm.mlir.addressof @stk_state : !llvm.ptr
%1406 = llvm.load %1405 : !llvm.ptr -> !llvm.ptr
%1407 = llvm.load %1397 : !llvm.ptr -> i64
%1408 = arith.addi %1393, %1407 : i64
%1409 = llvm.getelementptr %1406[%1408] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1402, %1409 : i64, !llvm.ptr
%1410 = llvm.load %1397 : !llvm.ptr -> i64
%1411 = arith.constant 1 : i32
%1413 = arith.extsi %1411 : i32 to i64
%1412 = arith.addi %1410, %1413 : i64
llvm.store %1412, %1397 : i64, !llvm.ptr
cf.br ^bb291
^bb293:
%1414 = llvm.mlir.addressof @stk_n : !llvm.ptr
%1415 = llvm.load %1414 : !llvm.ptr -> !llvm.ptr
%1416 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%1417 = llvm.load %1416 : !llvm.ptr -> i64
%1418 = llvm.getelementptr %1415[%1417] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1382, %1418 : i64, !llvm.ptr
%1419 = llvm.mlir.addressof @stk_prod : !llvm.ptr
%1420 = llvm.load %1419 : !llvm.ptr -> !llvm.ptr
%1421 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%1422 = llvm.load %1421 : !llvm.ptr -> i64
%1423 = llvm.getelementptr %1420[%1422] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %1143, %1423 : i128, !llvm.ptr
%1424 = llvm.mlir.addressof @stk_sp : !llvm.ptr
%1425 = llvm.load %1424 : !llvm.ptr -> i64
%1426 = arith.constant 1 : i32
%1428 = arith.extsi %1426 : i32 to i64
%1427 = arith.addi %1425, %1428 : i64
%1429 = llvm.mlir.addressof @stk_sp : !llvm.ptr
llvm.store %1427, %1429 : i64, !llvm.ptr
cf.br ^bb290
^bb289:
cf.br ^bb290
^bb290:
cf.br ^bb239
^bb239:
%1430 = llvm.load %1037 : !llvm.ptr -> i64
%1431 = arith.constant 1 : i32
%1433 = arith.extsi %1431 : i32 to i64
%1432 = arith.addi %1430, %1433 : i64
llvm.store %1432, %1037 : i64, !llvm.ptr
cf.br ^bb216
^bb218:
cf.br ^bb195
^bb197:
func.call @free(%897) : (!llvm.ptr) -> ()
func.call @free(%902) : (!llvm.ptr) -> ()
%1436 = llvm.load %838 : !llvm.ptr -> i64
%1437 = arith.remsi %1436, %arg2 : i64
func.return %1437 : i64
}
func.func @main() -> i32 {
%1439 = llvm.mlir.addressof @HT_CAP : !llvm.ptr
%1440 = llvm.load %1439 : !llvm.ptr -> i64
%1441 = arith.constant 9 : i32
%1443 = arith.extsi %1441 : i32 to i64
%1442 = arith.muli %1440, %1443 : i64
%1444 = arith.constant 8 : i32
%1445 = arith.extsi %1444 : i32 to i64
%1438 = func.call @calloc(%1442, %1445) : (i64, i64) -> !llvm.ptr
%1446 = llvm.mlir.addressof @ht_keys : !llvm.ptr
llvm.store %1438, %1446 : !llvm.ptr, !llvm.ptr
%1448 = llvm.mlir.addressof @HT_CAP : !llvm.ptr
%1449 = llvm.load %1448 : !llvm.ptr -> i64
%1450 = arith.constant 1 : i32
%1451 = arith.extsi %1450 : i32 to i64
%1447 = func.call @calloc(%1449, %1451) : (i64, i64) -> !llvm.ptr
%1452 = llvm.mlir.addressof @ht_used : !llvm.ptr
llvm.store %1447, %1452 : !llvm.ptr, !llvm.ptr
%1454 = llvm.mlir.addressof @SN_CAP : !llvm.ptr
%1455 = llvm.load %1454 : !llvm.ptr -> i64
%1456 = arith.constant 8 : i32
%1457 = arith.extsi %1456 : i32 to i64
%1453 = func.call @calloc(%1455, %1457) : (i64, i64) -> !llvm.ptr
%1458 = llvm.mlir.addressof @sn_keys : !llvm.ptr
llvm.store %1453, %1458 : !llvm.ptr, !llvm.ptr
%1460 = llvm.mlir.addressof @SN_CAP : !llvm.ptr
%1461 = llvm.load %1460 : !llvm.ptr -> i64
%1462 = arith.constant 1 : i32
%1463 = arith.extsi %1462 : i32 to i64
%1459 = func.call @calloc(%1461, %1463) : (i64, i64) -> !llvm.ptr
%1464 = llvm.mlir.addressof @sn_used : !llvm.ptr
llvm.store %1459, %1464 : !llvm.ptr, !llvm.ptr
%1466 = llvm.mlir.addressof @STK_CAP : !llvm.ptr
%1467 = llvm.load %1466 : !llvm.ptr -> i64
%1468 = llvm.mlir.addressof @MAX_NONONES : !llvm.ptr
%1469 = llvm.load %1468 : !llvm.ptr -> i64
%1470 = arith.muli %1467, %1469 : i64
%1471 = arith.constant 8 : i32
%1472 = arith.extsi %1471 : i32 to i64
%1465 = func.call @calloc(%1470, %1472) : (i64, i64) -> !llvm.ptr
%1473 = llvm.mlir.addressof @stk_state : !llvm.ptr
llvm.store %1465, %1473 : !llvm.ptr, !llvm.ptr
%1475 = llvm.mlir.addressof @STK_CAP : !llvm.ptr
%1476 = llvm.load %1475 : !llvm.ptr -> i64
%1477 = arith.constant 8 : i32
%1478 = arith.extsi %1477 : i32 to i64
%1474 = func.call @calloc(%1476, %1478) : (i64, i64) -> !llvm.ptr
%1479 = llvm.mlir.addressof @stk_n : !llvm.ptr
llvm.store %1474, %1479 : !llvm.ptr, !llvm.ptr
%1481 = llvm.mlir.addressof @STK_CAP : !llvm.ptr
%1482 = llvm.load %1481 : !llvm.ptr -> i64
%1483 = arith.constant 16 : i32
%1484 = arith.extsi %1483 : i32 to i64
%1480 = func.call @calloc(%1482, %1484) : (i64, i64) -> !llvm.ptr
%1485 = llvm.mlir.addressof @stk_prod : !llvm.ptr
llvm.store %1480, %1485 : !llvm.ptr, !llvm.ptr
%1486 = arith.constant 999999995705032704 : i32
%1487 = arith.extsi %1486 : i32 to i64
%1488 = arith.constant 999999995705032704 : i32
%1489 = arith.extsi %1488 : i32 to i64
%1490 = llvm.mlir.addressof @MOD : !llvm.ptr
%1491 = llvm.load %1490 : !llvm.ptr -> i64
%1492 = arith.constant 3 : i32
%1494 = arith.extsi %1492 : i32 to i64
%1493 = arith.cmpi slt, %1487, %1494 : i64
%1495 = scf.if %1493 -> (i1) {
%1496 = arith.constant true
scf.yield %1496 : i1
} else {
%1497 = arith.constant 1 : i32
%1499 = arith.extsi %1497 : i32 to i64
%1498 = arith.cmpi slt, %1489, %1499 : i64
scf.yield %1498 : i1
}
cf.cond_br %1495, ^bb294, ^bb295
^bb294:
%1500 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1501 = arith.constant 0 : i32
%1502 = arith.extsi %1501 : i32 to i64
%1503 = llvm.call @printf(%1500, %1502) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1504 = arith.constant 0 : i32
func.return %1504 : i32
^bb295:
cf.br ^bb296
^bb296:
%1505 = arith.constant 1 : i32
%1507 = arith.extsi %1505 : i32 to i64
%1506 = arith.addi %1489, %1507 : i64
%1508 = arith.cmpi slt, %1487, %1506 : i64
%1509 = scf.if %1508 -> (i64) {
scf.yield %1487 : i64
} else {
%1510 = arith.constant 1 : i32
%1512 = arith.extsi %1510 : i32 to i64
%1511 = arith.addi %1489, %1512 : i64
scf.yield %1511 : i64
}
%1513 = arith.constant 0 : i32
%1514 = arith.extsi %1513 : i32 to i64
%1515 = llvm.mlir.constant(1 : i64) : i64
%1516 = llvm.alloca %1515 x i64 : (i64) -> !llvm.ptr
llvm.store %1514, %1516 : i64, !llvm.ptr
%1517 = func.call @max_k_three_nonones(%1489, %1509) : (i64, i64) -> i64
%1518 = arith.cmpi slt, %1509, %1517 : i64
%1519 = scf.if %1518 -> (i64) {
scf.yield %1509 : i64
} else {
scf.yield %1517 : i64
}
%1520 = arith.constant 3 : i32
%1521 = arith.extsi %1520 : i32 to i64
%1522 = llvm.mlir.constant(1 : i64) : i64
%1523 = llvm.alloca %1522 x i64 : (i64) -> !llvm.ptr
llvm.store %1521, %1523 : i64, !llvm.ptr
cf.br ^bb297
^bb297:
%1524 = llvm.load %1523 : !llvm.ptr -> i64
%1525 = arith.cmpi sle, %1524, %1519 : i64
cf.cond_br %1525, ^bb298, ^bb299
^bb298:
%1527 = llvm.load %1516 : !llvm.ptr -> i64
%1529 = llvm.load %1523 : !llvm.ptr -> i64
%1528 = func.call @mk_sum(%1529, %1489, %1491) : (i64, i64, i64) -> i64
%1526 = func.call @madd(%1527, %1528) : (i64, i64) -> i64
llvm.store %1526, %1516 : i64, !llvm.ptr
%1530 = llvm.load %1523 : !llvm.ptr -> i64
%1531 = arith.constant 1 : i32
%1533 = arith.extsi %1531 : i32 to i64
%1532 = arith.addi %1530, %1533 : i64
llvm.store %1532, %1523 : i64, !llvm.ptr
cf.br ^bb297
^bb299:
%1534 = arith.constant 1 : i32
%1536 = arith.extsi %1534 : i32 to i64
%1535 = arith.addi %1519, %1536 : i64
%1537 = arith.cmpi sgt, %1535, %1509 : i64
cf.cond_br %1537, ^bb300, ^bb301
^bb300:
%1538 = arith.cmpi sgt, %1487, %1509 : i64
cf.cond_br %1538, ^bb303, ^bb304
^bb303:
%1540 = llvm.load %1516 : !llvm.ptr -> i64
%1541 = arith.subi %1487, %1509 : i64
%1542 = arith.remsi %1541, %1491 : i64
%1539 = func.call @madd(%1540, %1542) : (i64, i64) -> i64
llvm.store %1539, %1516 : i64, !llvm.ptr
cf.br ^bb305
^bb304:
cf.br ^bb305
^bb305:
%1543 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1544 = llvm.load %1516 : !llvm.ptr -> i64
%1545 = arith.remsi %1544, %1491 : i64
%1546 = llvm.call @printf(%1543, %1545) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1547 = arith.constant 0 : i32
func.return %1547 : i32
^bb301:
cf.br ^bb302
^bb302:
%1548 = func.call @max_k_a3(%1489, %1509) : (i64, i64) -> i64
%1549 = arith.cmpi slt, %1509, %1548 : i64
%1550 = scf.if %1549 -> (i64) {
scf.yield %1509 : i64
} else {
scf.yield %1548 : i64
}
%1551 = func.call @max_k_a2(%1489, %1509) : (i64, i64) -> i64
%1552 = arith.cmpi slt, %1509, %1551 : i64
%1553 = scf.if %1552 -> (i64) {
scf.yield %1509 : i64
} else {
scf.yield %1551 : i64
}
%1554 = arith.cmpi sle, %1535, %1550 : i64
cf.cond_br %1554, ^bb306, ^bb307
^bb306:
%1556 = func.call @rsum3(%1535, %1550) : (i64, i64) -> i64
%1558 = arith.constant 2 : i32
%1559 = func.call @rsum1(%1535, %1550) : (i64, i64) -> i64
%1560 = arith.extsi %1558 : i32 to i64
%1557 = func.call @mmul(%1560, %1559) : (i64, i64) -> i64
%1555 = func.call @msub(%1556, %1557) : (i64, i64) -> i64
%1562 = llvm.load %1516 : !llvm.ptr -> i64
%1561 = func.call @madd(%1562, %1555) : (i64, i64) -> i64
llvm.store %1561, %1516 : i64, !llvm.ptr
cf.br ^bb308
^bb307:
cf.br ^bb308
^bb308:
%1563 = arith.constant 1 : i32
%1565 = arith.extsi %1563 : i32 to i64
%1564 = arith.addi %1550, %1565 : i64
%1566 = arith.cmpi sgt, %1535, %1564 : i64
%1567 = scf.if %1566 -> (i64) {
scf.yield %1535 : i64
} else {
%1568 = arith.constant 1 : i32
%1570 = arith.extsi %1568 : i32 to i64
%1569 = arith.addi %1550, %1570 : i64
scf.yield %1569 : i64
}
%1571 = arith.cmpi sle, %1567, %1553 : i64
cf.cond_br %1571, ^bb309, ^bb310
^bb309:
%1572 = arith.subi %1553, %1567 : i64
%1573 = arith.constant 1 : i32
%1575 = arith.extsi %1573 : i32 to i64
%1574 = arith.addi %1572, %1575 : i64
%1576 = arith.remsi %1574, %1491 : i64
%1578 = func.call @rsum2(%1567, %1553) : (i64, i64) -> i64
%1577 = func.call @msub(%1578, %1576) : (i64, i64) -> i64
%1580 = llvm.load %1516 : !llvm.ptr -> i64
%1579 = func.call @madd(%1580, %1577) : (i64, i64) -> i64
llvm.store %1579, %1516 : i64, !llvm.ptr
cf.br ^bb311
^bb310:
cf.br ^bb311
^bb311:
%1581 = arith.constant 1 : i32
%1583 = arith.extsi %1581 : i32 to i64
%1582 = arith.addi %1553, %1583 : i64
%1584 = arith.cmpi sgt, %1535, %1582 : i64
%1585 = scf.if %1584 -> (i64) {
scf.yield %1535 : i64
} else {
%1586 = arith.constant 1 : i32
%1588 = arith.extsi %1586 : i32 to i64
%1587 = arith.addi %1553, %1588 : i64
scf.yield %1587 : i64
}
%1589 = arith.cmpi sle, %1585, %1509 : i64
cf.cond_br %1589, ^bb312, ^bb313
^bb312:
%1590 = func.call @rsum1(%1585, %1509) : (i64, i64) -> i64
%1592 = llvm.load %1516 : !llvm.ptr -> i64
%1591 = func.call @madd(%1592, %1590) : (i64, i64) -> i64
llvm.store %1591, %1516 : i64, !llvm.ptr
cf.br ^bb314
^bb313:
cf.br ^bb314
^bb314:
%1593 = arith.cmpi sgt, %1487, %1509 : i64
cf.cond_br %1593, ^bb315, ^bb316
^bb315:
%1595 = llvm.load %1516 : !llvm.ptr -> i64
%1596 = arith.subi %1487, %1509 : i64
%1597 = arith.remsi %1596, %1491 : i64
%1594 = func.call @madd(%1595, %1597) : (i64, i64) -> i64
llvm.store %1594, %1516 : i64, !llvm.ptr
cf.br ^bb317
^bb316:
cf.br ^bb317
^bb317:
%1598 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1599 = llvm.load %1516 : !llvm.ptr -> i64
%1600 = arith.remsi %1599, %1491 : i64
%1601 = llvm.call @printf(%1598, %1600) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1602 = arith.constant 0 : i32
func.return %1602 : i32
}
}