Problem 896
DFS with CRT merge, hash table for visited states, MRV heuristic.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n log n) | O(n log n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Chinese Remainder Theorem |
|---|
| Verdict | Optimal |
|---|
Flow source
# Project Euler 896
# DFS with CRT merge, hash table for visited states, MRV heuristic.
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>
}
import euler.nt { gcd }
const L: i64 = 36
const HT_SIZE: i64 = 262144
const HT_MASK: i64 = 262143
const ALL_MASK: i64 = 68719476735 # (1 << 36) - 1
const HASH_C: i64 = -7046029254386353131 # 0x9e3779b97f4a7c15 as signed i64
# Hash table (flat arrays)
let mut ht_r: ptr<i64> = null
let mut ht_m: ptr<i64> = null
let mut ht_unused: ptr<i64> = null
let mut ht_remaining: ptr<i64> = null
let mut ht_used: ptr<i32> = null
# DFS results
let mut g_M: i64 = 0
let mut g_residues: ptr<i64> = null
let mut g_num_residues: i64 = 0
# Temporary buffers for pick_index_mrv
let mut g_cands: ptr<i32> = null
let mut g_best_cands: ptr<i32> = null
function egcd(a: i64, b: i64) -> i64 {
# Returns x such that a*x ≡ 1 (mod b), assuming gcd(a,b)=1
let mut x0: i64 = 1
let mut x1: i64 = 0
let mut aa: i64 = a
let mut bb: i64 = b
while bb != 0 {
let q: i64 = aa / bb
let t: i64 = bb
bb = aa % bb
aa = t
let tx: i64 = x1
x1 = x0 - q * x1
x0 = tx
}
return x0
}
function crt_merge(r1: i64, m1: i64, r2: i64, m2: i64) -> i64 {
# Returns merged residue r, or -1 on failure
# Sets g_merged_m via global
let g: i64 = gcd(m1, m2)
let diff_raw: i64 = r2 - r1
if (diff_raw % g) != 0 {
return -1
}
let l: i64 = (m1 / g) * m2
let m1g: i64 = m1 / g
let m2g: i64 = m2 / g
let diff: i64 = diff_raw / g
let einv: i64 = egcd(m1g, m2g)
einv = ((einv % m2g) + m2g) % m2g
let t: i64 = ((diff * einv) % m2g + m2g) % m2g
let r: i64 = (r1 + m1 * t) % l
g_merged_m = l
return r
}
let mut g_merged_m: i64 = 0
function lcm_upto(n: i64) -> i64 {
let mut m: i64 = 1
let mut i: i64 = 1
while i <= n {
m = (m / gcd(m, i)) * i
i = i + 1
}
return m
}
function state_hash(r: i64, m: i64, unused_mask: i64, remaining_mask: i64) -> i64 {
let h: i64 = r % HT_SIZE
h = (h * 31 + m % HT_SIZE) % HT_SIZE
h = (h * 31 + unused_mask % HT_SIZE) % HT_SIZE
h = (h * 31 + remaining_mask % HT_SIZE) % HT_SIZE
return h
}
function ht_contains(r: i64, m: i64, unused_mask: i64, remaining_mask: i64) -> bool {
let mut h: i64 = state_hash(r, m, unused_mask, remaining_mask) & HT_MASK
while ht_used[h] != 0 {
if ht_r[h] == r && ht_m[h] == m && ht_unused[h] == unused_mask && ht_remaining[h] == remaining_mask {
return true
}
h = (h + 1) & HT_MASK
}
return false
}
function ht_insert(r: i64, m: i64, unused_mask: i64, remaining_mask: i64) -> void {
let mut h: i64 = state_hash(r, m, unused_mask, remaining_mask) & HT_MASK
while ht_used[h] != 0 {
if ht_r[h] == r && ht_m[h] == m && ht_unused[h] == unused_mask && ht_remaining[h] == remaining_mask {
return
}
h = (h + 1) & HT_MASK
}
ht_r[h] = r
ht_m[h] = m
ht_unused[h] = unused_mask
ht_remaining[h] = remaining_mask
ht_used[h] = 1
}
function candidates_offsets(unused_mask: i64, target: i64, step: i64) -> i32 {
# Fills g_cands with offsets j where j is in unused_mask and j ≡ target (mod step)
# Returns count
let mut n: i64 = 0
let mut j: i64 = target
while j < L {
if ((unused_mask >> j) & (1 as i64)) == 1 {
g_cands[n] = j as i32
n = n + 1
}
j = j + step
}
return n as i32
}
function pick_index_mrv(r: i64, m: i64, unused_mask: i64, remaining_mask: i64) -> i32 {
# Fills g_best_cands with best candidates, sets g_best_i and g_best_n
# Returns best_n, or 0 if any index has no candidates
let mut best_i: i64 = 0
let mut best_count: i64 = 1000000000
let mut best_n: i64 = 0
let mut i: i64 = L
while i >= 1 {
if ((remaining_mask >> (i - 1)) & (1 as i64)) == 0 {
i = i - 1
continue
}
let g: i64 = gcd(m, i)
let target: i64 = ((0 - r) % g + g) % g
let n: i32 = candidates_offsets(unused_mask, target, g)
let n64: i64 = n as i64
if n == 0 {
return 0
}
if n64 < best_count || (n64 == best_count && i > best_i) {
best_count = n64
best_i = i
best_n = n64
let mut k: i64 = 0
while k < n64 {
g_best_cands[k] = g_cands[k]
k = k + 1
}
}
i = i - 1
}
g_best_i = best_i
g_best_n = best_n
return best_n as i32
}
let mut g_best_i: i64 = 0
let mut g_best_n: i64 = 0
function dfs(r: i64, m: i64, unused_mask: i64, remaining_mask: i64) -> void {
let r_mod: i64 = r % m
if ht_contains(r_mod, m, unused_mask, remaining_mask) {
return
}
ht_insert(r_mod, m, unused_mask, remaining_mask)
if remaining_mask == 0 {
g_residues[g_num_residues] = r_mod
g_num_residues = g_num_residues + 1
return
}
let best_n: i32 = pick_index_mrv(r_mod, m, unused_mask, remaining_mask)
if best_n == 0 {
return
}
let best_i: i64 = g_best_i
let remaining2: i64 = remaining_mask & ~((1 as i64) << (best_i - 1))
# Copy candidates to local storage: g_best_cands and g_best_n are globals
# that get overwritten by recursive dfs calls.
let local_n: i64 = g_best_n
let mut local_cands: [i32; 36]
let mut ci: i64 = 0
while ci < local_n {
local_cands[ci] = g_best_cands[ci]
ci = ci + 1
}
let mut idx: i64 = 0
while idx < local_n {
let j: i64 = local_cands[idx] as i64
let r2_val: i64 = ((0 - j) % best_i + best_i) % best_i
let new_r: i64 = crt_merge(r_mod, m, r2_val, best_i)
if new_r >= 0 {
dfs(new_r, g_merged_m, unused_mask & ~((1 as i64) << j), remaining2)
}
idx = idx + 1
}
}
# Heapsort for i64 array
function heapsort_i64(arr: ptr<i64>, n: i64) -> void {
# Build max heap
let mut i: i64 = n / 2
while i > 0 {
i = i - 1
let mut p: i64 = i
while true {
let largest: i64 = p
let left: i64 = 2 * p + 1
let right: i64 = 2 * p + 2
if left < n && arr[left] > arr[largest] {
largest = left
}
if right < n && arr[right] > arr[largest] {
largest = right
}
if largest == p {
break
}
let tmp: i64 = arr[p]
arr[p] = arr[largest]
arr[largest] = tmp
p = largest
}
}
# Extract elements
let mut end: i64 = n - 1
while end > 0 {
let tmp: i64 = arr[0]
arr[0] = arr[end]
arr[end] = tmp
# Sift down from 0
let mut p: i64 = 0
while true {
let largest: i64 = p
let left: i64 = 2 * p + 1
let right: i64 = 2 * p + 2
if left < end && arr[left] > arr[largest] {
largest = left
}
if right < end && arr[right] > arr[largest] {
largest = right
}
if largest == p {
break
}
let tmp2: i64 = arr[p]
arr[p] = arr[largest]
arr[largest] = tmp2
p = largest
}
end = end - 1
}
}
function main() -> i32 {
# Allocate hash table
ht_r = calloc(HT_SIZE, 8)
ht_m = calloc(HT_SIZE, 8)
ht_unused = calloc(HT_SIZE, 8)
ht_remaining = calloc(HT_SIZE, 8)
ht_used = calloc(HT_SIZE, 4)
# Allocate buffers
g_cands = calloc(L, 4)
g_best_cands = calloc(L, 4)
g_residues = calloc(60000, 8)
g_M = lcm_upto(L)
let all_offsets: i64 = ALL_MASK
let all_indices: i64 = ALL_MASK
g_num_residues = 0
dfs(0, 1, all_offsets, all_indices)
# Sort and deduplicate
heapsort_i64(g_residues, g_num_residues)
let mut j: i64 = 0
let mut i: i64 = 0
while i < g_num_residues {
if i == 0 || g_residues[i] != g_residues[i - 1] {
g_residues[j] = g_residues[i]
j = j + 1
}
i = i + 1
}
g_num_residues = j
# Convert 0 to M
i = 0
while i < g_num_residues {
if g_residues[i] == 0 {
g_residues[i] = g_M
}
i = i + 1
}
# Sort again
heapsort_i64(g_residues, g_num_residues)
printf("%lld\n", g_residues[36 - 1])
free(ht_r)
free(ht_m)
free(ht_unused)
free(ht_remaining)
free(ht_used)
free(g_cands)
free(g_best_cands)
free(g_residues)
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 egcd_i64_i64(int64_t a, int64_t b);
int64_t crt_merge_i64_i64_i64_i64(int64_t r1, int64_t m1, int64_t r2, int64_t m2);
int64_t lcm_upto_i64(int64_t n);
int64_t state_hash_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask);
bool ht_contains_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask);
void ht_insert_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask);
int32_t candidates_offsets_i64_i64_i64(int64_t unused_mask, int64_t target, int64_t step);
int32_t pick_index_mrv_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask);
void dfs_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask);
void heapsort_i64_ptr_i64_i64(int64_t* arr, int64_t n);
int32_t main(void);
static const int64_t L = 36;
static const int64_t HT_SIZE = 262144;
static const int64_t HT_MASK = 262143;
static const int64_t ALL_MASK = 68719476735;
static const int64_t HASH_C = (-7046029254386353131);
/* Module statics */
static int64_t* ht_r = NULL;
static int64_t* ht_m = NULL;
static int64_t* ht_unused = NULL;
static int64_t* ht_remaining = NULL;
static int32_t* ht_used = NULL;
static int64_t g_M = 0;
static int64_t* g_residues = NULL;
static int64_t g_num_residues = 0;
static int32_t* g_cands = NULL;
static int32_t* g_best_cands = NULL;
static int64_t g_merged_m = 0;
static int64_t g_best_i = 0;
static int64_t g_best_n = 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 egcd_i64_i64(int64_t a, int64_t b) {
int64_t x0 = 1;
int64_t x1 = 0;
int64_t aa = a;
int64_t bb = b;
while (bb != 0) {
int64_t q = FLOW_CHECKED_DIV((aa), (bb));
int64_t t = bb;
bb = FLOW_CHECKED_MOD((aa), (bb));
aa = t;
int64_t tx = x1;
x1 = (x0 - (q * x1));
x0 = tx;
}
return x0;
}
int64_t crt_merge_i64_i64_i64_i64(int64_t r1, int64_t m1, int64_t r2, int64_t m2) {
int64_t g = gcd_i64_i64(m1, m2);
int64_t diff_raw = (r2 - r1);
if (FLOW_CHECKED_MOD((diff_raw), (g)) != 0) {
return (-1);
}
int64_t l = (FLOW_CHECKED_DIV((m1), (g)) * m2);
int64_t m1g = FLOW_CHECKED_DIV((m1), (g));
int64_t m2g = FLOW_CHECKED_DIV((m2), (g));
int64_t diff = FLOW_CHECKED_DIV((diff_raw), (g));
int64_t einv = egcd_i64_i64(m1g, m2g);
einv = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((einv), (m2g)) + m2g)), (m2g));
int64_t t = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((diff * einv)), (m2g)) + m2g)), (m2g));
int64_t r = FLOW_CHECKED_MOD(((r1 + (m1 * t))), (l));
g_merged_m = l;
return r;
}
int64_t lcm_upto_i64(int64_t n) {
int64_t m = 1;
int64_t i = 1;
while (i <= n) {
m = (FLOW_CHECKED_DIV((m), (gcd_i64_i64(m, i))) * i);
i = (i + 1);
}
return m;
}
int64_t state_hash_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask) {
int64_t h = FLOW_CHECKED_MOD((r), (HT_SIZE));
h = FLOW_CHECKED_MOD((((h * 31) + FLOW_CHECKED_MOD((m), (HT_SIZE)))), (HT_SIZE));
h = FLOW_CHECKED_MOD((((h * 31) + FLOW_CHECKED_MOD((unused_mask), (HT_SIZE)))), (HT_SIZE));
h = FLOW_CHECKED_MOD((((h * 31) + FLOW_CHECKED_MOD((remaining_mask), (HT_SIZE)))), (HT_SIZE));
return h;
}
bool ht_contains_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask) {
int64_t h = (state_hash_i64_i64_i64_i64(r, m, unused_mask, remaining_mask) & HT_MASK);
while (ht_used[h] != 0) {
if ((((ht_r[h] == r && ht_m[h] == m) && ht_unused[h] == unused_mask) && ht_remaining[h] == remaining_mask)) {
return 1;
}
h = ((h + 1) & HT_MASK);
}
return 0;
}
void ht_insert_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask) {
int64_t h = (state_hash_i64_i64_i64_i64(r, m, unused_mask, remaining_mask) & HT_MASK);
while (ht_used[h] != 0) {
if ((((ht_r[h] == r && ht_m[h] == m) && ht_unused[h] == unused_mask) && ht_remaining[h] == remaining_mask)) {
return;
}
h = ((h + 1) & HT_MASK);
}
ht_r[h] = r;
ht_m[h] = m;
ht_unused[h] = unused_mask;
ht_remaining[h] = remaining_mask;
ht_used[h] = 1;
}
int32_t candidates_offsets_i64_i64_i64(int64_t unused_mask, int64_t target, int64_t step) {
int64_t n = 0;
int64_t j = target;
while (j < L) {
if ((FLOW_CHECKED_SHR((unused_mask), (j)) & ((int64_t)(1))) == 1) {
g_cands[n] = ((int32_t)(j));
n = (n + 1);
}
j = (j + step);
}
return ((int32_t)(n));
}
int32_t pick_index_mrv_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask) {
int64_t best_i = 0;
int64_t best_count = 1000000000;
int64_t best_n = 0;
int64_t i = L;
while (i >= 1) {
if ((FLOW_CHECKED_SHR((remaining_mask), ((i - 1))) & ((int64_t)(1))) == 0) {
i = (i - 1);
continue;
}
int64_t g = gcd_i64_i64(m, i);
int64_t target = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((0 - r)), (g)) + g)), (g));
int32_t n = candidates_offsets_i64_i64_i64(unused_mask, target, g);
int64_t n64 = ((int64_t)(n));
if (n == 0) {
return 0;
}
if ((n64 < best_count || (n64 == best_count && i > best_i))) {
best_count = n64;
best_i = i;
best_n = n64;
int64_t k = 0;
while (k < n64) {
g_best_cands[k] = g_cands[k];
k = (k + 1);
}
}
i = (i - 1);
}
g_best_i = best_i;
g_best_n = best_n;
return ((int32_t)(best_n));
}
void dfs_i64_i64_i64_i64(int64_t r, int64_t m, int64_t unused_mask, int64_t remaining_mask) {
int64_t r_mod = FLOW_CHECKED_MOD((r), (m));
if (ht_contains_i64_i64_i64_i64(r_mod, m, unused_mask, remaining_mask)) {
return;
}
ht_insert_i64_i64_i64_i64(r_mod, m, unused_mask, remaining_mask);
if (remaining_mask == 0) {
g_residues[g_num_residues] = r_mod;
g_num_residues = (g_num_residues + 1);
return;
}
int32_t best_n = pick_index_mrv_i64_i64_i64_i64(r_mod, m, unused_mask, remaining_mask);
if (best_n == 0) {
return;
}
int64_t best_i = g_best_i;
int64_t remaining2 = (remaining_mask & (~FLOW_CHECKED_SHL((((int64_t)(1))), ((best_i - 1)))));
int64_t local_n = g_best_n;
int32_t local_cands[36];
int64_t ci = 0;
while (ci < local_n) {
local_cands[ci] = g_best_cands[ci];
ci = (ci + 1);
}
int64_t idx = 0;
while (idx < local_n) {
int64_t j = ((int64_t)((((unsigned)(idx) < 36) ? local_cands[idx] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(idx), 36), flow_fault_handler("array index out of bounds"), local_cands[0]))));
int64_t r2_val = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((0 - j)), (best_i)) + best_i)), (best_i));
int64_t new_r = crt_merge_i64_i64_i64_i64(r_mod, m, r2_val, best_i);
if (new_r >= 0) {
dfs_i64_i64_i64_i64(new_r, g_merged_m, (unused_mask & (~FLOW_CHECKED_SHL((((int64_t)(1))), (j)))), remaining2);
}
idx = (idx + 1);
}
}
void heapsort_i64_ptr_i64_i64(int64_t* arr, int64_t n) {
int64_t i = FLOW_CHECKED_DIV((n), (2));
while (i > 0) {
i = (i - 1);
int64_t p = i;
while (1) {
int64_t largest = p;
int64_t left = ((2 * p) + 1);
int64_t right = ((2 * p) + 2);
if ((left < n && arr[left] > arr[largest])) {
largest = left;
}
if ((right < n && arr[right] > arr[largest])) {
largest = right;
}
if (largest == p) {
break;
}
int64_t tmp = arr[p];
arr[p] = arr[largest];
arr[largest] = tmp;
p = largest;
}
}
int64_t end = (n - 1);
while (end > 0) {
int64_t tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
int64_t p = 0;
while (1) {
int64_t largest = p;
int64_t left = ((2 * p) + 1);
int64_t right = ((2 * p) + 2);
if ((left < end && arr[left] > arr[largest])) {
largest = left;
}
if ((right < end && arr[right] > arr[largest])) {
largest = right;
}
if (largest == p) {
break;
}
int64_t tmp2 = arr[p];
arr[p] = arr[largest];
arr[largest] = tmp2;
p = largest;
}
end = (end - 1);
}
}
int32_t main(void) {
ht_r = calloc(HT_SIZE, 8);
ht_m = calloc(HT_SIZE, 8);
ht_unused = calloc(HT_SIZE, 8);
ht_remaining = calloc(HT_SIZE, 8);
ht_used = calloc(HT_SIZE, 4);
g_cands = calloc(L, 4);
g_best_cands = calloc(L, 4);
g_residues = calloc(60000, 8);
g_M = lcm_upto_i64(L);
int64_t all_offsets = ALL_MASK;
int64_t all_indices = ALL_MASK;
g_num_residues = 0;
dfs_i64_i64_i64_i64(0, 1, all_offsets, all_indices);
heapsort_i64_ptr_i64_i64(g_residues, g_num_residues);
int64_t j = 0;
int64_t i = 0;
while (i < g_num_residues) {
if ((i == 0 || g_residues[i] != g_residues[(i - 1)])) {
g_residues[j] = g_residues[i];
j = (j + 1);
}
i = (i + 1);
}
g_num_residues = j;
i = 0;
while (i < g_num_residues) {
if (g_residues[i] == 0) {
g_residues[i] = g_M;
}
i = (i + 1);
}
heapsort_i64_ptr_i64_i64(g_residues, g_num_residues);
printf("%lld\n", g_residues[(36 - 1)]);
free(ht_r);
free(ht_m);
free(ht_unused);
free(ht_remaining);
free(ht_used);
free(g_cands);
free(g_best_cands);
free(g_residues);
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: L
llvm.mlir.global internal constant @L(36 : i64) : i64
// Constant: HT_SIZE
llvm.mlir.global internal constant @HT_SIZE(262144 : i64) : i64
// Constant: HT_MASK
llvm.mlir.global internal constant @HT_MASK(262143 : i64) : i64
// Constant: ALL_MASK
llvm.mlir.global internal constant @ALL_MASK(68719476735 : i64) : i64
// Constant: HASH_C
llvm.mlir.global internal constant @HASH_C(-7046029254386353131 : i64) : i64
// Module static: ht_r
llvm.mlir.global internal @ht_r() {addr_space = 0 : i32} : !llvm.ptr {
%175 = llvm.mlir.zero : !llvm.ptr
llvm.return %175 : !llvm.ptr
}
// Module static: ht_m
llvm.mlir.global internal @ht_m() {addr_space = 0 : i32} : !llvm.ptr {
%176 = llvm.mlir.zero : !llvm.ptr
llvm.return %176 : !llvm.ptr
}
// Module static: ht_unused
llvm.mlir.global internal @ht_unused() {addr_space = 0 : i32} : !llvm.ptr {
%177 = llvm.mlir.zero : !llvm.ptr
llvm.return %177 : !llvm.ptr
}
// Module static: ht_remaining
llvm.mlir.global internal @ht_remaining() {addr_space = 0 : i32} : !llvm.ptr {
%178 = llvm.mlir.zero : !llvm.ptr
llvm.return %178 : !llvm.ptr
}
// Module static: ht_used
llvm.mlir.global internal @ht_used() {addr_space = 0 : i32} : !llvm.ptr {
%179 = llvm.mlir.zero : !llvm.ptr
llvm.return %179 : !llvm.ptr
}
// Module static: g_M
llvm.mlir.global internal @g_M(0 : i64) : i64
// Module static: g_residues
llvm.mlir.global internal @g_residues() {addr_space = 0 : i32} : !llvm.ptr {
%180 = llvm.mlir.zero : !llvm.ptr
llvm.return %180 : !llvm.ptr
}
// Module static: g_num_residues
llvm.mlir.global internal @g_num_residues(0 : i64) : i64
// Module static: g_cands
llvm.mlir.global internal @g_cands() {addr_space = 0 : i32} : !llvm.ptr {
%181 = llvm.mlir.zero : !llvm.ptr
llvm.return %181 : !llvm.ptr
}
// Module static: g_best_cands
llvm.mlir.global internal @g_best_cands() {addr_space = 0 : i32} : !llvm.ptr {
%182 = llvm.mlir.zero : !llvm.ptr
llvm.return %182 : !llvm.ptr
}
func.func @egcd(%arg0: i64, %arg1: i64) -> i64 {
%183 = arith.constant 1 : i32
%184 = arith.extsi %183 : i32 to i64
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x i64 : (i64) -> !llvm.ptr
llvm.store %184, %186 : i64, !llvm.ptr
%187 = arith.constant 0 : i32
%188 = arith.extsi %187 : i32 to i64
%189 = llvm.mlir.constant(1 : i64) : i64
%190 = llvm.alloca %189 x i64 : (i64) -> !llvm.ptr
llvm.store %188, %190 : i64, !llvm.ptr
%191 = llvm.mlir.constant(1 : i64) : i64
%192 = llvm.alloca %191 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %192 : i64, !llvm.ptr
%193 = llvm.mlir.constant(1 : i64) : i64
%194 = llvm.alloca %193 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %194 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%195 = llvm.load %194 : !llvm.ptr -> i64
%196 = arith.constant 0 : i32
%198 = arith.extsi %196 : i32 to i64
%197 = arith.cmpi ne, %195, %198 : i64
cf.cond_br %197, ^bb43, ^bb44
^bb43:
%199 = llvm.load %192 : !llvm.ptr -> i64
%200 = llvm.load %194 : !llvm.ptr -> i64
%201 = arith.divsi %199, %200 : i64
%202 = llvm.load %194 : !llvm.ptr -> i64
%203 = llvm.load %192 : !llvm.ptr -> i64
%204 = llvm.load %194 : !llvm.ptr -> i64
%205 = arith.remsi %203, %204 : i64
llvm.store %205, %194 : i64, !llvm.ptr
llvm.store %202, %192 : i64, !llvm.ptr
%206 = llvm.load %190 : !llvm.ptr -> i64
%207 = llvm.load %186 : !llvm.ptr -> i64
%208 = llvm.load %190 : !llvm.ptr -> i64
%209 = arith.muli %201, %208 : i64
%210 = arith.subi %207, %209 : i64
llvm.store %210, %190 : i64, !llvm.ptr
llvm.store %206, %186 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%211 = llvm.load %186 : !llvm.ptr -> i64
func.return %211 : i64
}
func.func @crt_merge(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> i64 {
%212 = func.call @gcd(%arg1, %arg3) : (i64, i64) -> i64
%213 = arith.subi %arg2, %arg0 : i64
%214 = arith.remsi %213, %212 : i64
%215 = arith.constant 0 : i32
%217 = arith.extsi %215 : i32 to i64
%216 = arith.cmpi ne, %214, %217 : i64
cf.cond_br %216, ^bb45, ^bb46
^bb45:
%218 = arith.constant 1 : i32
%220 = arith.constant 0 : i32
%219 = arith.subi %220, %218 : i32
%221 = arith.extsi %219 : i32 to i64
func.return %221 : i64
^bb46:
cf.br ^bb47
^bb47:
%222 = arith.divsi %arg1, %212 : i64
%223 = arith.muli %222, %arg3 : i64
%224 = arith.divsi %arg1, %212 : i64
%225 = arith.divsi %arg3, %212 : i64
%226 = arith.divsi %213, %212 : i64
%227 = func.call @egcd(%224, %225) : (i64, i64) -> i64
%228 = arith.remsi %227, %225 : i64
%229 = arith.addi %228, %225 : i64
%230 = arith.remsi %229, %225 : i64
%231 = arith.muli %226, %230 : i64
%232 = arith.remsi %231, %225 : i64
%233 = arith.addi %232, %225 : i64
%234 = arith.remsi %233, %225 : i64
%235 = arith.muli %arg1, %234 : i64
%236 = arith.addi %arg0, %235 : i64
%237 = arith.remsi %236, %223 : i64
%238 = llvm.mlir.addressof @g_merged_m : !llvm.ptr
llvm.store %223, %238 : i64, !llvm.ptr
func.return %237 : i64
}
// Module static: g_merged_m
llvm.mlir.global internal @g_merged_m(0 : i64) : i64
func.func @lcm_upto(%arg0: i64) -> i64 {
%239 = arith.constant 1 : i32
%240 = arith.extsi %239 : i32 to i64
%241 = llvm.mlir.constant(1 : i64) : i64
%242 = llvm.alloca %241 x i64 : (i64) -> !llvm.ptr
llvm.store %240, %242 : i64, !llvm.ptr
%243 = arith.constant 1 : i32
%244 = arith.extsi %243 : i32 to i64
%245 = llvm.mlir.constant(1 : i64) : i64
%246 = llvm.alloca %245 x i64 : (i64) -> !llvm.ptr
llvm.store %244, %246 : i64, !llvm.ptr
cf.br ^bb48
^bb48:
%247 = llvm.load %246 : !llvm.ptr -> i64
%248 = arith.cmpi sle, %247, %arg0 : i64
cf.cond_br %248, ^bb49, ^bb50
^bb49:
%249 = llvm.load %242 : !llvm.ptr -> i64
%251 = llvm.load %242 : !llvm.ptr -> i64
%252 = llvm.load %246 : !llvm.ptr -> i64
%250 = func.call @gcd(%251, %252) : (i64, i64) -> i64
%253 = arith.divsi %249, %250 : i64
%254 = llvm.load %246 : !llvm.ptr -> i64
%255 = arith.muli %253, %254 : i64
llvm.store %255, %242 : i64, !llvm.ptr
%256 = llvm.load %246 : !llvm.ptr -> i64
%257 = arith.constant 1 : i32
%259 = arith.extsi %257 : i32 to i64
%258 = arith.addi %256, %259 : i64
llvm.store %258, %246 : i64, !llvm.ptr
cf.br ^bb48
^bb50:
%260 = llvm.load %242 : !llvm.ptr -> i64
func.return %260 : i64
}
func.func @state_hash(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> i64 {
%261 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%262 = llvm.load %261 : !llvm.ptr -> i64
%263 = arith.remsi %arg0, %262 : i64
%264 = arith.constant 31 : i32
%266 = arith.extsi %264 : i32 to i64
%265 = arith.muli %263, %266 : i64
%267 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%268 = llvm.load %267 : !llvm.ptr -> i64
%269 = arith.remsi %arg1, %268 : i64
%270 = arith.addi %265, %269 : i64
%271 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%272 = llvm.load %271 : !llvm.ptr -> i64
%273 = arith.remsi %270, %272 : i64
%274 = arith.constant 31 : i32
%276 = arith.extsi %274 : i32 to i64
%275 = arith.muli %273, %276 : i64
%277 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%278 = llvm.load %277 : !llvm.ptr -> i64
%279 = arith.remsi %arg2, %278 : i64
%280 = arith.addi %275, %279 : i64
%281 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%282 = llvm.load %281 : !llvm.ptr -> i64
%283 = arith.remsi %280, %282 : i64
%284 = arith.constant 31 : i32
%286 = arith.extsi %284 : i32 to i64
%285 = arith.muli %283, %286 : i64
%287 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%288 = llvm.load %287 : !llvm.ptr -> i64
%289 = arith.remsi %arg3, %288 : i64
%290 = arith.addi %285, %289 : i64
%291 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%292 = llvm.load %291 : !llvm.ptr -> i64
%293 = arith.remsi %290, %292 : i64
func.return %293 : i64
}
func.func @ht_contains(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> i1 {
%294 = func.call @state_hash(%arg0, %arg1, %arg2, %arg3) : (i64, i64, i64, i64) -> i64
%295 = llvm.mlir.addressof @HT_MASK : !llvm.ptr
%296 = llvm.load %295 : !llvm.ptr -> i64
%297 = arith.andi %294, %296 : i64
%298 = llvm.mlir.constant(1 : i64) : i64
%299 = llvm.alloca %298 x i64 : (i64) -> !llvm.ptr
llvm.store %297, %299 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%301 = llvm.mlir.addressof @ht_used : !llvm.ptr
%302 = llvm.load %301 : !llvm.ptr -> !llvm.ptr
%303 = llvm.load %299 : !llvm.ptr -> i64
%304 = llvm.getelementptr %302[%303] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%300 = llvm.load %304 : !llvm.ptr -> i32
%305 = arith.constant 0 : i32
%306 = arith.cmpi ne, %300, %305 : i32
cf.cond_br %306, ^bb52, ^bb53
^bb52:
%308 = llvm.mlir.addressof @ht_r : !llvm.ptr
%309 = llvm.load %308 : !llvm.ptr -> !llvm.ptr
%310 = llvm.load %299 : !llvm.ptr -> i64
%311 = llvm.getelementptr %309[%310] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%307 = llvm.load %311 : !llvm.ptr -> i64
%312 = arith.cmpi eq, %307, %arg0 : i64
%313 = scf.if %312 -> (i1) {
%315 = llvm.mlir.addressof @ht_m : !llvm.ptr
%316 = llvm.load %315 : !llvm.ptr -> !llvm.ptr
%317 = llvm.load %299 : !llvm.ptr -> i64
%318 = llvm.getelementptr %316[%317] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%314 = llvm.load %318 : !llvm.ptr -> i64
%319 = arith.cmpi eq, %314, %arg1 : i64
scf.yield %319 : i1
} else {
%320 = arith.constant false
scf.yield %320 : i1
}
%321 = scf.if %313 -> (i1) {
%323 = llvm.mlir.addressof @ht_unused : !llvm.ptr
%324 = llvm.load %323 : !llvm.ptr -> !llvm.ptr
%325 = llvm.load %299 : !llvm.ptr -> i64
%326 = llvm.getelementptr %324[%325] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%322 = llvm.load %326 : !llvm.ptr -> i64
%327 = arith.cmpi eq, %322, %arg2 : i64
scf.yield %327 : i1
} else {
%328 = arith.constant false
scf.yield %328 : i1
}
%329 = scf.if %321 -> (i1) {
%331 = llvm.mlir.addressof @ht_remaining : !llvm.ptr
%332 = llvm.load %331 : !llvm.ptr -> !llvm.ptr
%333 = llvm.load %299 : !llvm.ptr -> i64
%334 = llvm.getelementptr %332[%333] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%330 = llvm.load %334 : !llvm.ptr -> i64
%335 = arith.cmpi eq, %330, %arg3 : i64
scf.yield %335 : i1
} else {
%336 = arith.constant false
scf.yield %336 : i1
}
cf.cond_br %329, ^bb54, ^bb55
^bb54:
%337 = arith.constant 1 : i1
func.return %337 : i1
^bb55:
cf.br ^bb56
^bb56:
%338 = llvm.load %299 : !llvm.ptr -> i64
%339 = arith.constant 1 : i32
%341 = arith.extsi %339 : i32 to i64
%340 = arith.addi %338, %341 : i64
%342 = llvm.mlir.addressof @HT_MASK : !llvm.ptr
%343 = llvm.load %342 : !llvm.ptr -> i64
%344 = arith.andi %340, %343 : i64
llvm.store %344, %299 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%345 = arith.constant 0 : i1
func.return %345 : i1
}
func.func @ht_insert(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> () {
%346 = func.call @state_hash(%arg0, %arg1, %arg2, %arg3) : (i64, i64, i64, i64) -> i64
%347 = llvm.mlir.addressof @HT_MASK : !llvm.ptr
%348 = llvm.load %347 : !llvm.ptr -> i64
%349 = arith.andi %346, %348 : i64
%350 = llvm.mlir.constant(1 : i64) : i64
%351 = llvm.alloca %350 x i64 : (i64) -> !llvm.ptr
llvm.store %349, %351 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%353 = llvm.mlir.addressof @ht_used : !llvm.ptr
%354 = llvm.load %353 : !llvm.ptr -> !llvm.ptr
%355 = llvm.load %351 : !llvm.ptr -> i64
%356 = llvm.getelementptr %354[%355] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%352 = llvm.load %356 : !llvm.ptr -> i32
%357 = arith.constant 0 : i32
%358 = arith.cmpi ne, %352, %357 : i32
cf.cond_br %358, ^bb58, ^bb59
^bb58:
%360 = llvm.mlir.addressof @ht_r : !llvm.ptr
%361 = llvm.load %360 : !llvm.ptr -> !llvm.ptr
%362 = llvm.load %351 : !llvm.ptr -> i64
%363 = llvm.getelementptr %361[%362] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%359 = llvm.load %363 : !llvm.ptr -> i64
%364 = arith.cmpi eq, %359, %arg0 : i64
%365 = scf.if %364 -> (i1) {
%367 = llvm.mlir.addressof @ht_m : !llvm.ptr
%368 = llvm.load %367 : !llvm.ptr -> !llvm.ptr
%369 = llvm.load %351 : !llvm.ptr -> i64
%370 = llvm.getelementptr %368[%369] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%366 = llvm.load %370 : !llvm.ptr -> i64
%371 = arith.cmpi eq, %366, %arg1 : i64
scf.yield %371 : i1
} else {
%372 = arith.constant false
scf.yield %372 : i1
}
%373 = scf.if %365 -> (i1) {
%375 = llvm.mlir.addressof @ht_unused : !llvm.ptr
%376 = llvm.load %375 : !llvm.ptr -> !llvm.ptr
%377 = llvm.load %351 : !llvm.ptr -> i64
%378 = llvm.getelementptr %376[%377] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%374 = llvm.load %378 : !llvm.ptr -> i64
%379 = arith.cmpi eq, %374, %arg2 : i64
scf.yield %379 : i1
} else {
%380 = arith.constant false
scf.yield %380 : i1
}
%381 = scf.if %373 -> (i1) {
%383 = llvm.mlir.addressof @ht_remaining : !llvm.ptr
%384 = llvm.load %383 : !llvm.ptr -> !llvm.ptr
%385 = llvm.load %351 : !llvm.ptr -> i64
%386 = llvm.getelementptr %384[%385] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%382 = llvm.load %386 : !llvm.ptr -> i64
%387 = arith.cmpi eq, %382, %arg3 : i64
scf.yield %387 : i1
} else {
%388 = arith.constant false
scf.yield %388 : i1
}
cf.cond_br %381, ^bb60, ^bb61
^bb60:
func.return
^bb61:
cf.br ^bb62
^bb62:
%389 = llvm.load %351 : !llvm.ptr -> i64
%390 = arith.constant 1 : i32
%392 = arith.extsi %390 : i32 to i64
%391 = arith.addi %389, %392 : i64
%393 = llvm.mlir.addressof @HT_MASK : !llvm.ptr
%394 = llvm.load %393 : !llvm.ptr -> i64
%395 = arith.andi %391, %394 : i64
llvm.store %395, %351 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
%396 = llvm.mlir.addressof @ht_r : !llvm.ptr
%397 = llvm.load %396 : !llvm.ptr -> !llvm.ptr
%398 = llvm.load %351 : !llvm.ptr -> i64
%399 = llvm.getelementptr %397[%398] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %399 : i64, !llvm.ptr
%400 = llvm.mlir.addressof @ht_m : !llvm.ptr
%401 = llvm.load %400 : !llvm.ptr -> !llvm.ptr
%402 = llvm.load %351 : !llvm.ptr -> i64
%403 = llvm.getelementptr %401[%402] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %403 : i64, !llvm.ptr
%404 = llvm.mlir.addressof @ht_unused : !llvm.ptr
%405 = llvm.load %404 : !llvm.ptr -> !llvm.ptr
%406 = llvm.load %351 : !llvm.ptr -> i64
%407 = llvm.getelementptr %405[%406] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg2, %407 : i64, !llvm.ptr
%408 = llvm.mlir.addressof @ht_remaining : !llvm.ptr
%409 = llvm.load %408 : !llvm.ptr -> !llvm.ptr
%410 = llvm.load %351 : !llvm.ptr -> i64
%411 = llvm.getelementptr %409[%410] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg3, %411 : i64, !llvm.ptr
%412 = arith.constant 1 : i32
%413 = llvm.mlir.addressof @ht_used : !llvm.ptr
%414 = llvm.load %413 : !llvm.ptr -> !llvm.ptr
%415 = llvm.load %351 : !llvm.ptr -> i64
%416 = llvm.getelementptr %414[%415] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %412, %416 : i32, !llvm.ptr
func.return
}
func.func @candidates_offsets(%arg0: i64, %arg1: i64, %arg2: i64) -> i32 {
%417 = arith.constant 0 : i32
%418 = arith.extsi %417 : i32 to i64
%419 = llvm.mlir.constant(1 : i64) : i64
%420 = llvm.alloca %419 x i64 : (i64) -> !llvm.ptr
llvm.store %418, %420 : i64, !llvm.ptr
%421 = llvm.mlir.constant(1 : i64) : i64
%422 = llvm.alloca %421 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %422 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%423 = llvm.load %422 : !llvm.ptr -> i64
%424 = llvm.mlir.addressof @L : !llvm.ptr
%425 = llvm.load %424 : !llvm.ptr -> i64
%426 = arith.cmpi slt, %423, %425 : i64
cf.cond_br %426, ^bb64, ^bb65
^bb64:
%427 = llvm.load %422 : !llvm.ptr -> i64
%428 = arith.shrsi %arg0, %427 : i64
%429 = arith.constant 1 : i32
%430 = arith.extsi %429 : i32 to i64
%431 = arith.andi %428, %430 : i64
%432 = arith.constant 1 : i32
%434 = arith.extsi %432 : i32 to i64
%433 = arith.cmpi eq, %431, %434 : i64
cf.cond_br %433, ^bb66, ^bb67
^bb66:
%435 = llvm.load %422 : !llvm.ptr -> i64
%436 = arith.trunci %435 : i64 to i32
%437 = llvm.mlir.addressof @g_cands : !llvm.ptr
%438 = llvm.load %437 : !llvm.ptr -> !llvm.ptr
%439 = llvm.load %420 : !llvm.ptr -> i64
%440 = llvm.getelementptr %438[%439] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %436, %440 : i32, !llvm.ptr
%441 = llvm.load %420 : !llvm.ptr -> i64
%442 = arith.constant 1 : i32
%444 = arith.extsi %442 : i32 to i64
%443 = arith.addi %441, %444 : i64
llvm.store %443, %420 : i64, !llvm.ptr
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
%445 = llvm.load %422 : !llvm.ptr -> i64
%446 = arith.addi %445, %arg2 : i64
llvm.store %446, %422 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
%447 = llvm.load %420 : !llvm.ptr -> i64
%448 = arith.trunci %447 : i64 to i32
func.return %448 : i32
}
func.func @pick_index_mrv(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> i32 {
%449 = arith.constant 0 : i32
%450 = arith.extsi %449 : i32 to i64
%451 = llvm.mlir.constant(1 : i64) : i64
%452 = llvm.alloca %451 x i64 : (i64) -> !llvm.ptr
llvm.store %450, %452 : i64, !llvm.ptr
%453 = arith.constant 1000000000 : i32
%454 = arith.extsi %453 : i32 to i64
%455 = llvm.mlir.constant(1 : i64) : i64
%456 = llvm.alloca %455 x i64 : (i64) -> !llvm.ptr
llvm.store %454, %456 : i64, !llvm.ptr
%457 = arith.constant 0 : i32
%458 = arith.extsi %457 : i32 to i64
%459 = llvm.mlir.constant(1 : i64) : i64
%460 = llvm.alloca %459 x i64 : (i64) -> !llvm.ptr
llvm.store %458, %460 : i64, !llvm.ptr
%461 = llvm.mlir.addressof @L : !llvm.ptr
%462 = llvm.load %461 : !llvm.ptr -> i64
%463 = llvm.mlir.constant(1 : i64) : i64
%464 = llvm.alloca %463 x i64 : (i64) -> !llvm.ptr
llvm.store %462, %464 : i64, !llvm.ptr
cf.br ^bb69
^bb69:
%465 = llvm.load %464 : !llvm.ptr -> i64
%466 = arith.constant 1 : i32
%468 = arith.extsi %466 : i32 to i64
%467 = arith.cmpi sge, %465, %468 : i64
cf.cond_br %467, ^bb70, ^bb71
^bb70:
%469 = llvm.load %464 : !llvm.ptr -> i64
%470 = arith.constant 1 : i32
%472 = arith.extsi %470 : i32 to i64
%471 = arith.subi %469, %472 : i64
%473 = arith.shrsi %arg3, %471 : i64
%474 = arith.constant 1 : i32
%475 = arith.extsi %474 : i32 to i64
%476 = arith.andi %473, %475 : i64
%477 = arith.constant 0 : i32
%479 = arith.extsi %477 : i32 to i64
%478 = arith.cmpi eq, %476, %479 : i64
cf.cond_br %478, ^bb72, ^bb73
^bb72:
%480 = llvm.load %464 : !llvm.ptr -> i64
%481 = arith.constant 1 : i32
%483 = arith.extsi %481 : i32 to i64
%482 = arith.subi %480, %483 : i64
llvm.store %482, %464 : i64, !llvm.ptr
cf.br ^bb69
^bb73:
cf.br ^bb74
^bb74:
%485 = llvm.load %464 : !llvm.ptr -> i64
%484 = func.call @gcd(%arg1, %485) : (i64, i64) -> i64
%486 = arith.constant 0 : i32
%488 = arith.extsi %486 : i32 to i64
%487 = arith.subi %488, %arg0 : i64
%489 = arith.remsi %487, %484 : i64
%490 = arith.addi %489, %484 : i64
%491 = arith.remsi %490, %484 : i64
%492 = func.call @candidates_offsets(%arg2, %491, %484) : (i64, i64, i64) -> i32
%493 = arith.extsi %492 : i32 to i64
%494 = arith.constant 0 : i32
%495 = arith.cmpi eq, %492, %494 : i32
cf.cond_br %495, ^bb75, ^bb76
^bb75:
%496 = arith.constant 0 : i32
func.return %496 : i32
^bb76:
cf.br ^bb77
^bb77:
%497 = llvm.load %456 : !llvm.ptr -> i64
%498 = arith.cmpi slt, %493, %497 : i64
%499 = scf.if %498 -> (i1) {
%500 = arith.constant true
scf.yield %500 : i1
} else {
%501 = llvm.load %456 : !llvm.ptr -> i64
%502 = arith.cmpi eq, %493, %501 : i64
%503 = scf.if %502 -> (i1) {
%504 = llvm.load %464 : !llvm.ptr -> i64
%505 = llvm.load %452 : !llvm.ptr -> i64
%506 = arith.cmpi sgt, %504, %505 : i64
scf.yield %506 : i1
} else {
%507 = arith.constant false
scf.yield %507 : i1
}
scf.yield %503 : i1
}
cf.cond_br %499, ^bb78, ^bb79
^bb78:
llvm.store %493, %456 : i64, !llvm.ptr
%508 = llvm.load %464 : !llvm.ptr -> i64
llvm.store %508, %452 : i64, !llvm.ptr
llvm.store %493, %460 : i64, !llvm.ptr
%509 = arith.constant 0 : i32
%510 = arith.extsi %509 : i32 to i64
%511 = llvm.mlir.constant(1 : i64) : i64
%512 = llvm.alloca %511 x i64 : (i64) -> !llvm.ptr
llvm.store %510, %512 : i64, !llvm.ptr
cf.br ^bb81
^bb81:
%513 = llvm.load %512 : !llvm.ptr -> i64
%514 = arith.cmpi slt, %513, %493 : i64
cf.cond_br %514, ^bb82, ^bb83
^bb82:
%516 = llvm.mlir.addressof @g_cands : !llvm.ptr
%517 = llvm.load %516 : !llvm.ptr -> !llvm.ptr
%518 = llvm.load %512 : !llvm.ptr -> i64
%519 = llvm.getelementptr %517[%518] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%515 = llvm.load %519 : !llvm.ptr -> i32
%520 = llvm.mlir.addressof @g_best_cands : !llvm.ptr
%521 = llvm.load %520 : !llvm.ptr -> !llvm.ptr
%522 = llvm.load %512 : !llvm.ptr -> i64
%523 = llvm.getelementptr %521[%522] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %515, %523 : i32, !llvm.ptr
%524 = llvm.load %512 : !llvm.ptr -> i64
%525 = arith.constant 1 : i32
%527 = arith.extsi %525 : i32 to i64
%526 = arith.addi %524, %527 : i64
llvm.store %526, %512 : i64, !llvm.ptr
cf.br ^bb81
^bb83:
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%528 = llvm.load %464 : !llvm.ptr -> i64
%529 = arith.constant 1 : i32
%531 = arith.extsi %529 : i32 to i64
%530 = arith.subi %528, %531 : i64
llvm.store %530, %464 : i64, !llvm.ptr
cf.br ^bb69
^bb71:
%532 = llvm.load %452 : !llvm.ptr -> i64
%533 = llvm.mlir.addressof @g_best_i : !llvm.ptr
llvm.store %532, %533 : i64, !llvm.ptr
%534 = llvm.load %460 : !llvm.ptr -> i64
%535 = llvm.mlir.addressof @g_best_n : !llvm.ptr
llvm.store %534, %535 : i64, !llvm.ptr
%536 = llvm.load %460 : !llvm.ptr -> i64
%537 = arith.trunci %536 : i64 to i32
func.return %537 : i32
}
// Module static: g_best_i
llvm.mlir.global internal @g_best_i(0 : i64) : i64
// Module static: g_best_n
llvm.mlir.global internal @g_best_n(0 : i64) : i64
func.func @dfs(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> () {
%538 = arith.remsi %arg0, %arg1 : i64
%539 = func.call @ht_contains(%538, %arg1, %arg2, %arg3) : (i64, i64, i64, i64) -> i1
cf.cond_br %539, ^bb84, ^bb85
^bb84:
func.return
^bb85:
cf.br ^bb86
^bb86:
func.call @ht_insert(%538, %arg1, %arg2, %arg3) : (i64, i64, i64, i64) -> ()
%541 = arith.constant 0 : i32
%543 = arith.extsi %541 : i32 to i64
%542 = arith.cmpi eq, %arg3, %543 : i64
cf.cond_br %542, ^bb87, ^bb88
^bb87:
%544 = llvm.mlir.addressof @g_residues : !llvm.ptr
%545 = llvm.load %544 : !llvm.ptr -> !llvm.ptr
%546 = llvm.mlir.addressof @g_num_residues : !llvm.ptr
%547 = llvm.load %546 : !llvm.ptr -> i64
%548 = llvm.getelementptr %545[%547] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %538, %548 : i64, !llvm.ptr
%549 = llvm.mlir.addressof @g_num_residues : !llvm.ptr
%550 = llvm.load %549 : !llvm.ptr -> i64
%551 = arith.constant 1 : i32
%553 = arith.extsi %551 : i32 to i64
%552 = arith.addi %550, %553 : i64
%554 = llvm.mlir.addressof @g_num_residues : !llvm.ptr
llvm.store %552, %554 : i64, !llvm.ptr
func.return
^bb88:
cf.br ^bb89
^bb89:
%555 = func.call @pick_index_mrv(%538, %arg1, %arg2, %arg3) : (i64, i64, i64, i64) -> i32
%556 = arith.constant 0 : i32
%557 = arith.cmpi eq, %555, %556 : i32
cf.cond_br %557, ^bb90, ^bb91
^bb90:
func.return
^bb91:
cf.br ^bb92
^bb92:
%558 = llvm.mlir.addressof @g_best_i : !llvm.ptr
%559 = llvm.load %558 : !llvm.ptr -> i64
%560 = arith.constant 1 : i32
%561 = arith.extsi %560 : i32 to i64
%562 = arith.constant 1 : i32
%564 = arith.extsi %562 : i32 to i64
%563 = arith.subi %559, %564 : i64
%565 = arith.shli %561, %563 : i64
%567 = arith.constant -1 : i64
%566 = arith.xori %565, %567 : i64
%568 = arith.andi %arg3, %566 : i64
%569 = llvm.mlir.addressof @g_best_n : !llvm.ptr
%570 = llvm.load %569 : !llvm.ptr -> i64
%571 = memref.alloca() {type = memref<36xi32>} : memref<36xi32>
%572 = arith.constant 0 : i32
%573 = arith.extsi %572 : i32 to i64
%574 = llvm.mlir.constant(1 : i64) : i64
%575 = llvm.alloca %574 x i64 : (i64) -> !llvm.ptr
llvm.store %573, %575 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%576 = llvm.load %575 : !llvm.ptr -> i64
%577 = arith.cmpi slt, %576, %570 : i64
cf.cond_br %577, ^bb94, ^bb95
^bb94:
%579 = llvm.mlir.addressof @g_best_cands : !llvm.ptr
%580 = llvm.load %579 : !llvm.ptr -> !llvm.ptr
%581 = llvm.load %575 : !llvm.ptr -> i64
%582 = llvm.getelementptr %580[%581] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%578 = llvm.load %582 : !llvm.ptr -> i32
%583 = llvm.load %575 : !llvm.ptr -> i64
%584 = arith.index_cast %583 : i32 to index
memref.store %578, %571[%584] : memref<36xi32>
%585 = llvm.load %575 : !llvm.ptr -> i64
%586 = arith.constant 1 : i32
%588 = arith.extsi %586 : i32 to i64
%587 = arith.addi %585, %588 : i64
llvm.store %587, %575 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%589 = arith.constant 0 : i32
%590 = arith.extsi %589 : i32 to i64
%591 = llvm.mlir.constant(1 : i64) : i64
%592 = llvm.alloca %591 x i64 : (i64) -> !llvm.ptr
llvm.store %590, %592 : i64, !llvm.ptr
cf.br ^bb96
^bb96:
%593 = llvm.load %592 : !llvm.ptr -> i64
%594 = arith.cmpi slt, %593, %570 : i64
cf.cond_br %594, ^bb97, ^bb98
^bb97:
%596 = llvm.load %592 : !llvm.ptr -> i64
%597 = arith.index_cast %596 : i32 to index
%595 = memref.load %571[%597] : memref<36xi32>
%598 = arith.extsi %595 : i32 to i64
%599 = arith.constant 0 : i32
%601 = arith.extsi %599 : i32 to i64
%600 = arith.subi %601, %598 : i64
%602 = arith.remsi %600, %559 : i64
%603 = arith.addi %602, %559 : i64
%604 = arith.remsi %603, %559 : i64
%605 = func.call @crt_merge(%538, %arg1, %604, %559) : (i64, i64, i64, i64) -> i64
%606 = arith.constant 0 : i32
%608 = arith.extsi %606 : i32 to i64
%607 = arith.cmpi sge, %605, %608 : i64
cf.cond_br %607, ^bb99, ^bb100
^bb99:
%610 = llvm.mlir.addressof @g_merged_m : !llvm.ptr
%611 = llvm.load %610 : !llvm.ptr -> i64
%612 = arith.constant 1 : i32
%613 = arith.extsi %612 : i32 to i64
%614 = arith.shli %613, %598 : i64
%616 = arith.constant -1 : i64
%615 = arith.xori %614, %616 : i64
%617 = arith.andi %arg2, %615 : i64
func.call @dfs(%605, %611, %617, %568) : (i64, i64, i64, i64) -> ()
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
%618 = llvm.load %592 : !llvm.ptr -> i64
%619 = arith.constant 1 : i32
%621 = arith.extsi %619 : i32 to i64
%620 = arith.addi %618, %621 : i64
llvm.store %620, %592 : i64, !llvm.ptr
cf.br ^bb96
^bb98:
func.return
}
func.func @heapsort_i64(%arg0: !llvm.ptr, %arg1: i64) -> () {
%622 = arith.constant 2 : i32
%624 = arith.extsi %622 : i32 to i64
%623 = arith.divsi %arg1, %624 : i64
%625 = llvm.mlir.constant(1 : i64) : i64
%626 = llvm.alloca %625 x i64 : (i64) -> !llvm.ptr
llvm.store %623, %626 : i64, !llvm.ptr
cf.br ^bb102
^bb102:
%627 = llvm.load %626 : !llvm.ptr -> i64
%628 = arith.constant 0 : i32
%630 = arith.extsi %628 : i32 to i64
%629 = arith.cmpi sgt, %627, %630 : i64
cf.cond_br %629, ^bb103, ^bb104
^bb103:
%631 = llvm.load %626 : !llvm.ptr -> i64
%632 = arith.constant 1 : i32
%634 = arith.extsi %632 : i32 to i64
%633 = arith.subi %631, %634 : i64
llvm.store %633, %626 : i64, !llvm.ptr
%635 = llvm.load %626 : !llvm.ptr -> i64
%636 = llvm.mlir.constant(1 : i64) : i64
%637 = llvm.alloca %636 x i64 : (i64) -> !llvm.ptr
llvm.store %635, %637 : i64, !llvm.ptr
cf.br ^bb105
^bb105:
%638 = arith.constant 1 : i1
cf.cond_br %638, ^bb106, ^bb107
^bb106:
%639 = llvm.load %637 : !llvm.ptr -> i64
%640 = arith.constant 2 : i32
%641 = llvm.load %637 : !llvm.ptr -> i64
%643 = arith.extsi %640 : i32 to i64
%642 = arith.muli %643, %641 : i64
%644 = arith.constant 1 : i32
%646 = arith.extsi %644 : i32 to i64
%645 = arith.addi %642, %646 : i64
%647 = arith.constant 2 : i32
%648 = llvm.load %637 : !llvm.ptr -> i64
%650 = arith.extsi %647 : i32 to i64
%649 = arith.muli %650, %648 : i64
%651 = arith.constant 2 : i32
%653 = arith.extsi %651 : i32 to i64
%652 = arith.addi %649, %653 : i64
%654 = arith.cmpi slt, %645, %arg1 : i64
%655 = scf.if %654 -> (i1) {
%657 = llvm.getelementptr %arg0[%645] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%656 = llvm.load %657 : !llvm.ptr -> i64
%659 = llvm.getelementptr %arg0[%639] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%658 = llvm.load %659 : !llvm.ptr -> i64
%660 = arith.cmpi sgt, %656, %658 : i64
scf.yield %660 : i1
} else {
%661 = arith.constant false
scf.yield %661 : i1
}
%662 = scf.if %655 -> (i64) {
scf.yield %645 : i64
} else {
scf.yield %639 : i64
}
%663 = arith.cmpi slt, %652, %arg1 : i64
%664 = scf.if %663 -> (i1) {
%666 = llvm.getelementptr %arg0[%652] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%665 = llvm.load %666 : !llvm.ptr -> i64
%668 = llvm.getelementptr %arg0[%662] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%667 = llvm.load %668 : !llvm.ptr -> i64
%669 = arith.cmpi sgt, %665, %667 : i64
scf.yield %669 : i1
} else {
%670 = arith.constant false
scf.yield %670 : i1
}
%671 = scf.if %664 -> (i64) {
scf.yield %652 : i64
} else {
scf.yield %662 : i64
}
%672 = llvm.load %637 : !llvm.ptr -> i64
%673 = arith.cmpi eq, %671, %672 : i64
cf.cond_br %673, ^bb108, ^bb109
^bb108:
cf.br ^bb107
^bb109:
cf.br ^bb110
^bb110:
%675 = llvm.load %637 : !llvm.ptr -> i64
%676 = llvm.getelementptr %arg0[%675] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%674 = llvm.load %676 : !llvm.ptr -> i64
%678 = llvm.getelementptr %arg0[%671] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%677 = llvm.load %678 : !llvm.ptr -> i64
%679 = llvm.load %637 : !llvm.ptr -> i64
%680 = llvm.getelementptr %arg0[%679] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %677, %680 : i64, !llvm.ptr
%681 = llvm.getelementptr %arg0[%671] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %674, %681 : i64, !llvm.ptr
llvm.store %671, %637 : i64, !llvm.ptr
cf.br ^bb105
^bb107:
cf.br ^bb102
^bb104:
%682 = arith.constant 1 : i32
%684 = arith.extsi %682 : i32 to i64
%683 = arith.subi %arg1, %684 : i64
%685 = llvm.mlir.constant(1 : i64) : i64
%686 = llvm.alloca %685 x i64 : (i64) -> !llvm.ptr
llvm.store %683, %686 : i64, !llvm.ptr
cf.br ^bb111
^bb111:
%687 = llvm.load %686 : !llvm.ptr -> i64
%688 = arith.constant 0 : i32
%690 = arith.extsi %688 : i32 to i64
%689 = arith.cmpi sgt, %687, %690 : i64
cf.cond_br %689, ^bb112, ^bb113
^bb112:
%692 = arith.constant 0 : i32
%693 = arith.extsi %692 : i32 to i64
%694 = llvm.getelementptr %arg0[%693] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%691 = llvm.load %694 : !llvm.ptr -> i64
%696 = llvm.load %686 : !llvm.ptr -> i64
%697 = llvm.getelementptr %arg0[%696] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%695 = llvm.load %697 : !llvm.ptr -> i64
%698 = arith.constant 0 : i32
%699 = arith.extsi %698 : i32 to i64
%700 = llvm.getelementptr %arg0[%699] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %695, %700 : i64, !llvm.ptr
%701 = llvm.load %686 : !llvm.ptr -> i64
%702 = llvm.getelementptr %arg0[%701] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %691, %702 : i64, !llvm.ptr
%703 = arith.constant 0 : i32
%704 = arith.extsi %703 : i32 to i64
%705 = llvm.mlir.constant(1 : i64) : i64
%706 = llvm.alloca %705 x i64 : (i64) -> !llvm.ptr
llvm.store %704, %706 : i64, !llvm.ptr
cf.br ^bb114
^bb114:
%707 = arith.constant 1 : i1
cf.cond_br %707, ^bb115, ^bb116
^bb115:
%708 = llvm.load %706 : !llvm.ptr -> i64
%709 = arith.constant 2 : i32
%710 = llvm.load %706 : !llvm.ptr -> i64
%712 = arith.extsi %709 : i32 to i64
%711 = arith.muli %712, %710 : i64
%713 = arith.constant 1 : i32
%715 = arith.extsi %713 : i32 to i64
%714 = arith.addi %711, %715 : i64
%716 = arith.constant 2 : i32
%717 = llvm.load %706 : !llvm.ptr -> i64
%719 = arith.extsi %716 : i32 to i64
%718 = arith.muli %719, %717 : i64
%720 = arith.constant 2 : i32
%722 = arith.extsi %720 : i32 to i64
%721 = arith.addi %718, %722 : i64
%723 = llvm.load %686 : !llvm.ptr -> i64
%724 = arith.cmpi slt, %714, %723 : i64
%725 = scf.if %724 -> (i1) {
%727 = llvm.getelementptr %arg0[%714] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%726 = llvm.load %727 : !llvm.ptr -> i64
%729 = llvm.getelementptr %arg0[%708] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%728 = llvm.load %729 : !llvm.ptr -> i64
%730 = arith.cmpi sgt, %726, %728 : i64
scf.yield %730 : i1
} else {
%731 = arith.constant false
scf.yield %731 : i1
}
%732 = scf.if %725 -> (i64) {
scf.yield %714 : i64
} else {
scf.yield %708 : i64
}
%733 = llvm.load %686 : !llvm.ptr -> i64
%734 = arith.cmpi slt, %721, %733 : i64
%735 = scf.if %734 -> (i1) {
%737 = llvm.getelementptr %arg0[%721] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%736 = llvm.load %737 : !llvm.ptr -> i64
%739 = llvm.getelementptr %arg0[%732] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%738 = llvm.load %739 : !llvm.ptr -> i64
%740 = arith.cmpi sgt, %736, %738 : i64
scf.yield %740 : i1
} else {
%741 = arith.constant false
scf.yield %741 : i1
}
%742 = scf.if %735 -> (i64) {
scf.yield %721 : i64
} else {
scf.yield %732 : i64
}
%743 = llvm.load %706 : !llvm.ptr -> i64
%744 = arith.cmpi eq, %742, %743 : i64
cf.cond_br %744, ^bb117, ^bb118
^bb117:
cf.br ^bb116
^bb118:
cf.br ^bb119
^bb119:
%746 = llvm.load %706 : !llvm.ptr -> i64
%747 = llvm.getelementptr %arg0[%746] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%745 = llvm.load %747 : !llvm.ptr -> i64
%749 = llvm.getelementptr %arg0[%742] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%748 = llvm.load %749 : !llvm.ptr -> i64
%750 = llvm.load %706 : !llvm.ptr -> i64
%751 = llvm.getelementptr %arg0[%750] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %748, %751 : i64, !llvm.ptr
%752 = llvm.getelementptr %arg0[%742] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %745, %752 : i64, !llvm.ptr
llvm.store %742, %706 : i64, !llvm.ptr
cf.br ^bb114
^bb116:
%753 = llvm.load %686 : !llvm.ptr -> i64
%754 = arith.constant 1 : i32
%756 = arith.extsi %754 : i32 to i64
%755 = arith.subi %753, %756 : i64
llvm.store %755, %686 : i64, !llvm.ptr
cf.br ^bb111
^bb113:
func.return
}
func.func @main() -> i32 {
%758 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%759 = llvm.load %758 : !llvm.ptr -> i64
%760 = arith.constant 8 : i32
%761 = arith.extsi %760 : i32 to i64
%757 = func.call @calloc(%759, %761) : (i64, i64) -> !llvm.ptr
%762 = llvm.mlir.addressof @ht_r : !llvm.ptr
llvm.store %757, %762 : !llvm.ptr, !llvm.ptr
%764 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%765 = llvm.load %764 : !llvm.ptr -> i64
%766 = arith.constant 8 : i32
%767 = arith.extsi %766 : i32 to i64
%763 = func.call @calloc(%765, %767) : (i64, i64) -> !llvm.ptr
%768 = llvm.mlir.addressof @ht_m : !llvm.ptr
llvm.store %763, %768 : !llvm.ptr, !llvm.ptr
%770 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%771 = llvm.load %770 : !llvm.ptr -> i64
%772 = arith.constant 8 : i32
%773 = arith.extsi %772 : i32 to i64
%769 = func.call @calloc(%771, %773) : (i64, i64) -> !llvm.ptr
%774 = llvm.mlir.addressof @ht_unused : !llvm.ptr
llvm.store %769, %774 : !llvm.ptr, !llvm.ptr
%776 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%777 = llvm.load %776 : !llvm.ptr -> i64
%778 = arith.constant 8 : i32
%779 = arith.extsi %778 : i32 to i64
%775 = func.call @calloc(%777, %779) : (i64, i64) -> !llvm.ptr
%780 = llvm.mlir.addressof @ht_remaining : !llvm.ptr
llvm.store %775, %780 : !llvm.ptr, !llvm.ptr
%782 = llvm.mlir.addressof @HT_SIZE : !llvm.ptr
%783 = llvm.load %782 : !llvm.ptr -> i64
%784 = arith.constant 4 : i32
%785 = arith.extsi %784 : i32 to i64
%781 = func.call @calloc(%783, %785) : (i64, i64) -> !llvm.ptr
%786 = llvm.mlir.addressof @ht_used : !llvm.ptr
llvm.store %781, %786 : !llvm.ptr, !llvm.ptr
%788 = llvm.mlir.addressof @L : !llvm.ptr
%789 = llvm.load %788 : !llvm.ptr -> i64
%790 = arith.constant 4 : i32
%791 = arith.extsi %790 : i32 to i64
%787 = func.call @calloc(%789, %791) : (i64, i64) -> !llvm.ptr
%792 = llvm.mlir.addressof @g_cands : !llvm.ptr
llvm.store %787, %792 : !llvm.ptr, !llvm.ptr
%794 = llvm.mlir.addressof @L : !llvm.ptr
%795 = llvm.load %794 : !llvm.ptr -> i64
%796 = arith.constant 4 : i32
%797 = arith.extsi %796 : i32 to i64
%793 = func.call @calloc(%795, %797) : (i64, i64) -> !llvm.ptr
%798 = llvm.mlir.addressof @g_best_cands : !llvm.ptr
llvm.store %793, %798 : !llvm.ptr, !llvm.ptr
%800 = arith.constant 60000 : i32
%801 = arith.constant 8 : i32
%802 = arith.extsi %800 : i32 to i64
%803 = arith.extsi %801 : i32 to i64
%799 = func.call @calloc(%802, %803) : (i64, i64) -> !llvm.ptr
%804 = llvm.mlir.addressof @g_residues : !llvm.ptr
llvm.store %799, %804 : !llvm.ptr, !llvm.ptr
%806 = llvm.mlir.addressof @L : !llvm.ptr
%807 = llvm.load %806 : !llvm.ptr -> i64
%805 = func.call @lcm_upto(%807) : (i64) -> i64
%808 = llvm.mlir.addressof @g_M : !llvm.ptr
llvm.store %805, %808 : i64, !llvm.ptr
%809 = llvm.mlir.addressof @ALL_MASK : !llvm.ptr
%810 = llvm.load %809 : !llvm.ptr -> i64
%811 = llvm.mlir.addressof @ALL_MASK : !llvm.ptr
%812 = llvm.load %811 : !llvm.ptr -> i64
%813 = arith.constant 0 : i32
%814 = arith.extsi %813 : i32 to i64
%815 = llvm.mlir.addressof @g_num_residues : !llvm.ptr
llvm.store %814, %815 : i64, !llvm.ptr
%817 = arith.constant 0 : i32
%818 = arith.constant 1 : i32
%819 = arith.extsi %817 : i32 to i64
%820 = arith.extsi %818 : i32 to i64
func.call @dfs(%819, %820, %810, %812) : (i64, i64, i64, i64) -> ()
%822 = llvm.mlir.addressof @g_residues : !llvm.ptr
%823 = llvm.load %822 : !llvm.ptr -> !llvm.ptr
%824 = llvm.mlir.addressof @g_num_residues : !llvm.ptr
%825 = llvm.load %824 : !llvm.ptr -> i64
func.call @heapsort_i64(%823, %825) : (!llvm.ptr, i64) -> ()
%826 = arith.constant 0 : i32
%827 = arith.extsi %826 : i32 to i64
%828 = llvm.mlir.constant(1 : i64) : i64
%829 = llvm.alloca %828 x i64 : (i64) -> !llvm.ptr
llvm.store %827, %829 : i64, !llvm.ptr
%830 = arith.constant 0 : i32
%831 = arith.extsi %830 : i32 to i64
%832 = llvm.mlir.constant(1 : i64) : i64
%833 = llvm.alloca %832 x i64 : (i64) -> !llvm.ptr
llvm.store %831, %833 : i64, !llvm.ptr
cf.br ^bb120
^bb120:
%834 = llvm.load %833 : !llvm.ptr -> i64
%835 = llvm.mlir.addressof @g_num_residues : !llvm.ptr
%836 = llvm.load %835 : !llvm.ptr -> i64
%837 = arith.cmpi slt, %834, %836 : i64
cf.cond_br %837, ^bb121, ^bb122
^bb121:
%838 = llvm.load %833 : !llvm.ptr -> i64
%839 = arith.constant 0 : i32
%841 = arith.extsi %839 : i32 to i64
%840 = arith.cmpi eq, %838, %841 : i64
%842 = scf.if %840 -> (i1) {
%843 = arith.constant true
scf.yield %843 : i1
} else {
%845 = llvm.mlir.addressof @g_residues : !llvm.ptr
%846 = llvm.load %845 : !llvm.ptr -> !llvm.ptr
%847 = llvm.load %833 : !llvm.ptr -> i64
%848 = llvm.getelementptr %846[%847] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%844 = llvm.load %848 : !llvm.ptr -> i64
%850 = llvm.mlir.addressof @g_residues : !llvm.ptr
%851 = llvm.load %850 : !llvm.ptr -> !llvm.ptr
%852 = llvm.load %833 : !llvm.ptr -> i64
%853 = arith.constant 1 : i32
%855 = arith.extsi %853 : i32 to i64
%854 = arith.subi %852, %855 : i64
%856 = llvm.getelementptr %851[%854] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%849 = llvm.load %856 : !llvm.ptr -> i64
%857 = arith.cmpi ne, %844, %849 : i64
scf.yield %857 : i1
}
cf.cond_br %842, ^bb123, ^bb124
^bb123:
%859 = llvm.mlir.addressof @g_residues : !llvm.ptr
%860 = llvm.load %859 : !llvm.ptr -> !llvm.ptr
%861 = llvm.load %833 : !llvm.ptr -> i64
%862 = llvm.getelementptr %860[%861] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%858 = llvm.load %862 : !llvm.ptr -> i64
%863 = llvm.mlir.addressof @g_residues : !llvm.ptr
%864 = llvm.load %863 : !llvm.ptr -> !llvm.ptr
%865 = llvm.load %829 : !llvm.ptr -> i64
%866 = llvm.getelementptr %864[%865] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %858, %866 : i64, !llvm.ptr
%867 = llvm.load %829 : !llvm.ptr -> i64
%868 = arith.constant 1 : i32
%870 = arith.extsi %868 : i32 to i64
%869 = arith.addi %867, %870 : i64
llvm.store %869, %829 : i64, !llvm.ptr
cf.br ^bb125
^bb124:
cf.br ^bb125
^bb125:
%871 = llvm.load %833 : !llvm.ptr -> i64
%872 = arith.constant 1 : i32
%874 = arith.extsi %872 : i32 to i64
%873 = arith.addi %871, %874 : i64
llvm.store %873, %833 : i64, !llvm.ptr
cf.br ^bb120
^bb122:
%875 = llvm.load %829 : !llvm.ptr -> i64
%876 = llvm.mlir.addressof @g_num_residues : !llvm.ptr
llvm.store %875, %876 : i64, !llvm.ptr
%877 = arith.constant 0 : i32
%878 = arith.extsi %877 : i32 to i64
llvm.store %878, %833 : i64, !llvm.ptr
cf.br ^bb126
^bb126:
%879 = llvm.load %833 : !llvm.ptr -> i64
%880 = llvm.mlir.addressof @g_num_residues : !llvm.ptr
%881 = llvm.load %880 : !llvm.ptr -> i64
%882 = arith.cmpi slt, %879, %881 : i64
cf.cond_br %882, ^bb127, ^bb128
^bb127:
%884 = llvm.mlir.addressof @g_residues : !llvm.ptr
%885 = llvm.load %884 : !llvm.ptr -> !llvm.ptr
%886 = llvm.load %833 : !llvm.ptr -> i64
%887 = llvm.getelementptr %885[%886] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%883 = llvm.load %887 : !llvm.ptr -> i64
%888 = arith.constant 0 : i32
%890 = arith.extsi %888 : i32 to i64
%889 = arith.cmpi eq, %883, %890 : i64
cf.cond_br %889, ^bb129, ^bb130
^bb129:
%891 = llvm.mlir.addressof @g_M : !llvm.ptr
%892 = llvm.load %891 : !llvm.ptr -> i64
%893 = llvm.mlir.addressof @g_residues : !llvm.ptr
%894 = llvm.load %893 : !llvm.ptr -> !llvm.ptr
%895 = llvm.load %833 : !llvm.ptr -> i64
%896 = llvm.getelementptr %894[%895] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %892, %896 : i64, !llvm.ptr
cf.br ^bb131
^bb130:
cf.br ^bb131
^bb131:
%897 = llvm.load %833 : !llvm.ptr -> i64
%898 = arith.constant 1 : i32
%900 = arith.extsi %898 : i32 to i64
%899 = arith.addi %897, %900 : i64
llvm.store %899, %833 : i64, !llvm.ptr
cf.br ^bb126
^bb128:
%902 = llvm.mlir.addressof @g_residues : !llvm.ptr
%903 = llvm.load %902 : !llvm.ptr -> !llvm.ptr
%904 = llvm.mlir.addressof @g_num_residues : !llvm.ptr
%905 = llvm.load %904 : !llvm.ptr -> i64
func.call @heapsort_i64(%903, %905) : (!llvm.ptr, i64) -> ()
%906 = llvm.mlir.addressof @str_0 : !llvm.ptr
%908 = llvm.mlir.addressof @g_residues : !llvm.ptr
%909 = llvm.load %908 : !llvm.ptr -> !llvm.ptr
%910 = arith.constant 36 : i32
%911 = arith.constant 1 : i32
%912 = arith.subi %910, %911 : i32
%913 = arith.extsi %912 : i32 to i64
%914 = llvm.getelementptr %909[%913] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%907 = llvm.load %914 : !llvm.ptr -> i64
%915 = llvm.call @printf(%906, %907) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%917 = llvm.mlir.addressof @ht_r : !llvm.ptr
%918 = llvm.load %917 : !llvm.ptr -> !llvm.ptr
func.call @free(%918) : (!llvm.ptr) -> ()
%920 = llvm.mlir.addressof @ht_m : !llvm.ptr
%921 = llvm.load %920 : !llvm.ptr -> !llvm.ptr
func.call @free(%921) : (!llvm.ptr) -> ()
%923 = llvm.mlir.addressof @ht_unused : !llvm.ptr
%924 = llvm.load %923 : !llvm.ptr -> !llvm.ptr
func.call @free(%924) : (!llvm.ptr) -> ()
%926 = llvm.mlir.addressof @ht_remaining : !llvm.ptr
%927 = llvm.load %926 : !llvm.ptr -> !llvm.ptr
func.call @free(%927) : (!llvm.ptr) -> ()
%929 = llvm.mlir.addressof @ht_used : !llvm.ptr
%930 = llvm.load %929 : !llvm.ptr -> !llvm.ptr
func.call @free(%930) : (!llvm.ptr) -> ()
%932 = llvm.mlir.addressof @g_cands : !llvm.ptr
%933 = llvm.load %932 : !llvm.ptr -> !llvm.ptr
func.call @free(%933) : (!llvm.ptr) -> ()
%935 = llvm.mlir.addressof @g_best_cands : !llvm.ptr
%936 = llvm.load %935 : !llvm.ptr -> !llvm.ptr
func.call @free(%936) : (!llvm.ptr) -> ()
%938 = llvm.mlir.addressof @g_residues : !llvm.ptr
%939 = llvm.load %938 : !llvm.ptr -> !llvm.ptr
func.call @free(%939) : (!llvm.ptr) -> ()
%940 = arith.constant 0 : i32
func.return %940 : i32
}
}