Problem 754
Product of Gauss Factorials: product of GF(n) for 1<=n<=10^8, mod 1e9+7.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Big-integer factorial |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 754
# Product of Gauss Factorials: product of GF(n) for 1<=n<=10^8, mod 1e9+7.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
const MOD: i64 = 1000000007
const EXP_MOD: i64 = 1000000006
const LIMIT: i64 = 100000000
function mm(a: i64, b: i64) -> i64 {
return ((a as i128) * (b as i128) % (MOD as i128)) as i64
}
function mpow(base0: i64, exp0: i64) -> i64 {
let mut r: i64 = 1
let mut base: i64 = base0 % MOD
if base < 0 { base = base + MOD }
let mut exp: i64 = exp0
while exp > 0 {
if (exp & 1) != 0 { r = mm(r, base) }
base = mm(base, base)
exp = exp >> 1
}
return r
}
# Heapsort for i64 arrays
function heapsort_i64(arr: ptr<i64>, n: i64) -> void {
let mut start: i64 = n / 2
while start > 0 {
start = start - 1
let mut root: i64 = start
while 2 * root + 1 < n {
let child: i64 = 2 * root + 1
let mut swap_idx: i64 = root
if arr[swap_idx] < arr[child] { swap_idx = child }
if child + 1 < n {
if arr[swap_idx] < arr[child + 1] { swap_idx = child + 1 }
}
if swap_idx == root { break }
let tmp: i64 = arr[root]
arr[root] = arr[swap_idx]
arr[swap_idx] = tmp
root = swap_idx
}
}
let mut end: i64 = n - 1
while end > 0 {
let tmp: i64 = arr[0]
arr[0] = arr[end]
arr[end] = tmp
let mut root: i64 = 0
while 2 * root + 1 < end {
let child: i64 = 2 * root + 1
let mut swap_idx: i64 = root
if arr[swap_idx] < arr[child] { swap_idx = child }
if child + 1 < end {
if arr[swap_idx] < arr[child + 1] { swap_idx = child + 1 }
}
if swap_idx == root { break }
let tmp2: i64 = arr[root]
arr[root] = arr[swap_idx]
arr[swap_idx] = tmp2
root = swap_idx
}
end = end - 1
}
}
# Global superfactorial table
let mut sf_keys: ptr<i64> = null
let mut sf_vals: ptr<i64> = null
let mut sf_count: i64 = 0
function sf_lookup(key: i64) -> i64 {
let mut lo: i64 = 0
let hi: i64 = sf_count
while lo < hi {
let mid: i64 = (lo + hi) / 2
if sf_keys[mid] < key { lo = mid + 1 }
else { hi = mid }
}
if lo < sf_count && sf_keys[lo] == key { return sf_vals[lo] }
return 1
}
function compute_superfactorials(keys: ptr<i64>, nkeys0: i64) -> void {
heapsort_i64(keys, nkeys0)
let mut unique: i64 = 0
let mut i: i64 = 0
while i < nkeys0 {
if i == 0 || keys[i] != keys[i - 1] {
keys[unique] = keys[i]
unique = unique + 1
}
i = i + 1
}
let nkeys: i64 = unique
sf_keys = malloc(nkeys * 8) as ptr<i64>
sf_vals = malloc(nkeys * 8) as ptr<i64>
sf_count = 0
let mut pos: i64 = 0
if nkeys > 0 && keys[0] == 0 {
sf_keys[0] = 0
sf_vals[0] = 1
sf_count = 1
pos = 1
}
let stop: i64 = if nkeys > 0 { keys[nkeys - 1] } else { 0 }
let mut factorial: i64 = 1
let mut superfactorial: i64 = 1
let mut x: i64 = 1
while x <= stop {
factorial = mm(factorial, x % MOD)
superfactorial = mm(superfactorial, factorial)
while pos < nkeys && keys[pos] == x {
sf_keys[sf_count] = x
sf_vals[sf_count] = superfactorial
sf_count = sf_count + 1
pos = pos + 1
}
x = x + 1
}
}
function main() -> i32 {
let mu: ptr<i8> = calloc(LIMIT + 1, 1) as ptr<i8>
let comp: ptr<i8> = calloc(LIMIT + 1, 1) as ptr<i8>
let primes: ptr<i32> = malloc(6000000 * 4) as ptr<i32>
let mut pc: i64 = 0
let mut agg_cap: i64 = 65536
let mut agg_q: ptr<i64> = malloc(agg_cap * 8) as ptr<i64>
let mut agg_pos_prod: ptr<i64> = malloc(agg_cap * 8) as ptr<i64>
let mut agg_neg_prod: ptr<i64> = malloc(agg_cap * 8) as ptr<i64>
let mut agg_mu_sum: ptr<i64> = malloc(agg_cap * 8) as ptr<i64>
let mut agg_n: i64 = 0
agg_q[0] = LIMIT
agg_pos_prod[0] = 1
agg_neg_prod[0] = 1
agg_mu_sum[0] = 1
agg_n = 1
mu[1] = 1
let mut lo: i64 = 2
if lo <= LIMIT {
let mut q: i64 = LIMIT / lo
let mut hi: i64 = LIMIT / q
let mut pos_prod: i64 = 1
let mut neg_prod: i64 = 1
let mut mu_sum: i64 = 0
let mut x: i64 = 2
let mut done: bool = false
while x <= LIMIT && !done {
let mux: i8 = if comp[x] == 0 { 2 } else { mu[x] }
if comp[x] == 0 {
primes[pc] = x as i32
pc = pc + 1
mu[x] = 2
}
if mux == 1 {
pos_prod = mm(pos_prod, x % MOD)
mu_sum = mu_sum + 1
} else {
if mux == 2 {
neg_prod = mm(neg_prod, x % MOD)
mu_sum = mu_sum - 1
}
}
let mut i: i64 = 0
while i < pc {
let p: i32 = primes[i]
let y: i64 = x * (p as i64)
if y > LIMIT { break }
comp[y] = 1
if x % (p as i64) == 0 { break }
if mux == 1 { mu[y] = 2 }
else { if mux == 2 { mu[y] = 1 } }
i = i + 1
}
if x == hi {
if agg_n >= agg_cap {
let new_cap: i64 = agg_cap * 2
let nq: ptr<i64> = malloc(new_cap * 8) as ptr<i64>
let npp: ptr<i64> = malloc(new_cap * 8) as ptr<i64>
let nnp: ptr<i64> = malloc(new_cap * 8) as ptr<i64>
let nms: ptr<i64> = malloc(new_cap * 8) as ptr<i64>
let mut ci: i64 = 0
while ci < agg_n {
nq[ci] = agg_q[ci]
npp[ci] = agg_pos_prod[ci]
nnp[ci] = agg_neg_prod[ci]
nms[ci] = agg_mu_sum[ci]
ci = ci + 1
}
free(agg_q)
free(agg_pos_prod)
free(agg_neg_prod)
free(agg_mu_sum)
agg_q = nq
agg_pos_prod = npp
agg_neg_prod = nnp
agg_mu_sum = nms
agg_cap = new_cap
}
agg_q[agg_n] = q
agg_pos_prod[agg_n] = pos_prod
agg_neg_prod[agg_n] = neg_prod
agg_mu_sum[agg_n] = mu_sum
agg_n = agg_n + 1
lo = hi + 1
if lo > LIMIT { done = true }
else {
q = LIMIT / lo
hi = LIMIT / q
pos_prod = 1
neg_prod = 1
mu_sum = 0
}
}
x = x + 1
}
}
free(mu)
free(comp)
free(primes)
let keys: ptr<i64> = malloc(agg_n * 8) as ptr<i64>
let mut i: i64 = 0
while i < agg_n {
keys[i] = agg_q[i] - 1
i = i + 1
}
compute_superfactorials(keys, agg_n)
free(keys)
let mut result: i64 = 1
i = 0
while i < agg_n {
let aq: i64 = agg_q[i]
let exponent: i64 = (aq * (aq - 1) / 2) % EXP_MOD
if exponent != 0 {
result = mm(result, mpow(agg_pos_prod[i], exponent))
let neg_exp: i64 = (EXP_MOD - exponent) % EXP_MOD
if neg_exp != 0 {
result = mm(result, mpow(agg_neg_prod[i], neg_exp))
}
}
let sf_power: i64 = ((agg_mu_sum[i] % EXP_MOD) + EXP_MOD) % EXP_MOD
if sf_power != 0 {
let sf: i64 = sf_lookup(agg_q[i] - 1)
result = mm(result, mpow(sf, sf_power))
}
i = i + 1
}
free(agg_q)
free(agg_pos_prod)
free(agg_neg_prod)
free(agg_mu_sum)
free(sf_keys)
free(sf_vals)
printf("%lld\n", result)
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 mm_i64_i64(int64_t a, int64_t b);
int64_t mpow_i64_i64(int64_t base0, int64_t exp0);
void heapsort_i64_ptr_i64_i64(int64_t* arr, int64_t n);
int64_t sf_lookup_i64(int64_t key);
void compute_superfactorials_ptr_i64_i64(int64_t* keys, int64_t nkeys0);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int64_t EXP_MOD = 1000000006;
static const int64_t LIMIT = 100000000;
/* Module statics */
static int64_t* sf_keys = NULL;
static int64_t* sf_vals = NULL;
static int64_t sf_count = 0;
int64_t mm_i64_i64(int64_t a, int64_t b) {
return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(b)))), (((__int128)(MOD))))));
}
int64_t mpow_i64_i64(int64_t base0, int64_t exp0) {
int64_t r = 1;
int64_t base = FLOW_CHECKED_MOD((base0), (MOD));
if (base < 0) {
base = (base + MOD);
}
int64_t exp = exp0;
while (exp > 0) {
if ((exp & 1) != 0) {
r = mm_i64_i64(r, base);
}
base = mm_i64_i64(base, base);
exp = FLOW_CHECKED_SHR((exp), (1));
}
return r;
}
void heapsort_i64_ptr_i64_i64(int64_t* arr, int64_t n) {
int64_t start = FLOW_CHECKED_DIV((n), (2));
while (start > 0) {
start = (start - 1);
int64_t root = start;
while (((2 * root) + 1) < n) {
int64_t child = ((2 * root) + 1);
int64_t swap_idx = root;
if (arr[swap_idx] < arr[child]) {
swap_idx = child;
}
if ((child + 1) < n) {
if (arr[swap_idx] < arr[(child + 1)]) {
swap_idx = (child + 1);
}
}
if (swap_idx == root) {
break;
}
int64_t tmp = arr[root];
arr[root] = arr[swap_idx];
arr[swap_idx] = tmp;
root = swap_idx;
}
}
int64_t end = (n - 1);
while (end > 0) {
int64_t tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
int64_t root = 0;
while (((2 * root) + 1) < end) {
int64_t child = ((2 * root) + 1);
int64_t swap_idx = root;
if (arr[swap_idx] < arr[child]) {
swap_idx = child;
}
if ((child + 1) < end) {
if (arr[swap_idx] < arr[(child + 1)]) {
swap_idx = (child + 1);
}
}
if (swap_idx == root) {
break;
}
int64_t tmp2 = arr[root];
arr[root] = arr[swap_idx];
arr[swap_idx] = tmp2;
root = swap_idx;
}
end = (end - 1);
}
}
int64_t sf_lookup_i64(int64_t key) {
int64_t lo = 0;
int64_t hi = sf_count;
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (sf_keys[mid] < key) {
lo = (mid + 1);
} else {
hi = mid;
}
}
if ((lo < sf_count && sf_keys[lo] == key)) {
return sf_vals[lo];
}
return 1;
}
void compute_superfactorials_ptr_i64_i64(int64_t* keys, int64_t nkeys0) {
heapsort_i64_ptr_i64_i64(keys, nkeys0);
int64_t unique = 0;
int64_t i = 0;
while (i < nkeys0) {
if ((i == 0 || keys[i] != keys[(i - 1)])) {
keys[unique] = keys[i];
unique = (unique + 1);
}
i = (i + 1);
}
int64_t nkeys = unique;
sf_keys = ((int64_t*)(malloc((nkeys * 8))));
sf_vals = ((int64_t*)(malloc((nkeys * 8))));
sf_count = 0;
int64_t pos = 0;
if ((nkeys > 0 && keys[0] == 0)) {
sf_keys[0] = 0;
sf_vals[0] = 1;
sf_count = 1;
pos = 1;
}
int64_t stop = ((nkeys > 0) ? (keys[(nkeys - 1)]) : (0));
int64_t factorial = 1;
int64_t superfactorial = 1;
int64_t x = 1;
while (x <= stop) {
factorial = mm_i64_i64(factorial, FLOW_CHECKED_MOD((x), (MOD)));
superfactorial = mm_i64_i64(superfactorial, factorial);
while ((pos < nkeys && keys[pos] == x)) {
sf_keys[sf_count] = x;
sf_vals[sf_count] = superfactorial;
sf_count = (sf_count + 1);
pos = (pos + 1);
}
x = (x + 1);
}
}
int32_t main(void) {
int8_t* mu = (int8_t*)(((int8_t*)(calloc((LIMIT + 1), 1))));
int8_t* comp = (int8_t*)(((int8_t*)(calloc((LIMIT + 1), 1))));
int32_t* primes = (int32_t*)(((int32_t*)(malloc((6000000 * 4)))));
int64_t pc = 0;
int64_t agg_cap = 65536;
int64_t* agg_q = (int64_t*)(((int64_t*)(malloc((agg_cap * 8)))));
int64_t* agg_pos_prod = (int64_t*)(((int64_t*)(malloc((agg_cap * 8)))));
int64_t* agg_neg_prod = (int64_t*)(((int64_t*)(malloc((agg_cap * 8)))));
int64_t* agg_mu_sum = (int64_t*)(((int64_t*)(malloc((agg_cap * 8)))));
int64_t agg_n = 0;
agg_q[0] = LIMIT;
agg_pos_prod[0] = 1;
agg_neg_prod[0] = 1;
agg_mu_sum[0] = 1;
agg_n = 1;
mu[1] = 1;
int64_t lo = 2;
if (lo <= LIMIT) {
int64_t q = FLOW_CHECKED_DIV((LIMIT), (lo));
int64_t hi = FLOW_CHECKED_DIV((LIMIT), (q));
int64_t pos_prod = 1;
int64_t neg_prod = 1;
int64_t mu_sum = 0;
int64_t x = 2;
bool done = 0;
while ((x <= LIMIT && (!(done)))) {
int8_t mux = ((comp[x] == 0) ? (2) : (mu[x]));
if (comp[x] == 0) {
primes[pc] = ((int32_t)(x));
pc = (pc + 1);
mu[x] = 2;
}
if (mux == 1) {
pos_prod = mm_i64_i64(pos_prod, FLOW_CHECKED_MOD((x), (MOD)));
mu_sum = (mu_sum + 1);
} else {
if (mux == 2) {
neg_prod = mm_i64_i64(neg_prod, FLOW_CHECKED_MOD((x), (MOD)));
mu_sum = (mu_sum - 1);
}
}
int64_t i = 0;
while (i < pc) {
int32_t p = primes[i];
int64_t y = (x * ((int64_t)(p)));
if (y > LIMIT) {
break;
}
comp[y] = 1;
if (FLOW_CHECKED_MOD((x), (((int64_t)(p)))) == 0) {
break;
}
if (mux == 1) {
mu[y] = 2;
} else {
if (mux == 2) {
mu[y] = 1;
}
}
i = (i + 1);
}
if (x == hi) {
if (agg_n >= agg_cap) {
int64_t new_cap = (agg_cap * 2);
int64_t* nq = (int64_t*)(((int64_t*)(malloc((new_cap * 8)))));
int64_t* npp = (int64_t*)(((int64_t*)(malloc((new_cap * 8)))));
int64_t* nnp = (int64_t*)(((int64_t*)(malloc((new_cap * 8)))));
int64_t* nms = (int64_t*)(((int64_t*)(malloc((new_cap * 8)))));
int64_t ci = 0;
while (ci < agg_n) {
nq[ci] = agg_q[ci];
npp[ci] = agg_pos_prod[ci];
nnp[ci] = agg_neg_prod[ci];
nms[ci] = agg_mu_sum[ci];
ci = (ci + 1);
}
free(agg_q);
free(agg_pos_prod);
free(agg_neg_prod);
free(agg_mu_sum);
agg_q = nq;
agg_pos_prod = npp;
agg_neg_prod = nnp;
agg_mu_sum = nms;
agg_cap = new_cap;
}
agg_q[agg_n] = q;
agg_pos_prod[agg_n] = pos_prod;
agg_neg_prod[agg_n] = neg_prod;
agg_mu_sum[agg_n] = mu_sum;
agg_n = (agg_n + 1);
lo = (hi + 1);
if (lo > LIMIT) {
done = 1;
} else {
q = FLOW_CHECKED_DIV((LIMIT), (lo));
hi = FLOW_CHECKED_DIV((LIMIT), (q));
pos_prod = 1;
neg_prod = 1;
mu_sum = 0;
}
}
x = (x + 1);
}
}
free(mu);
free(comp);
free(primes);
int64_t* keys = (int64_t*)(((int64_t*)(malloc((agg_n * 8)))));
int64_t i = 0;
while (i < agg_n) {
keys[i] = (agg_q[i] - 1);
i = (i + 1);
}
compute_superfactorials_ptr_i64_i64(keys, agg_n);
free(keys);
int64_t result = 1;
i = 0;
while (i < agg_n) {
int64_t aq = agg_q[i];
int64_t exponent = FLOW_CHECKED_MOD((FLOW_CHECKED_DIV(((aq * (aq - 1))), (2))), (EXP_MOD));
if (exponent != 0) {
result = mm_i64_i64(result, mpow_i64_i64(agg_pos_prod[i], exponent));
int64_t neg_exp = FLOW_CHECKED_MOD(((EXP_MOD - exponent)), (EXP_MOD));
if (neg_exp != 0) {
result = mm_i64_i64(result, mpow_i64_i64(agg_neg_prod[i], neg_exp));
}
}
int64_t sf_power = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((agg_mu_sum[i]), (EXP_MOD)) + EXP_MOD)), (EXP_MOD));
if (sf_power != 0) {
int64_t sf = sf_lookup_i64((agg_q[i] - 1));
result = mm_i64_i64(result, mpow_i64_i64(sf, sf_power));
}
i = (i + 1);
}
free(agg_q);
free(agg_pos_prod);
free(agg_neg_prod);
free(agg_mu_sum);
free(sf_keys);
free(sf_vals);
printf("%lld\n", result);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @malloc(i64) -> !llvm.ptr
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
// Constant: EXP_MOD
llvm.mlir.global internal constant @EXP_MOD(1000000006 : i64) : i64
// Constant: LIMIT
llvm.mlir.global internal constant @LIMIT(100000000 : i64) : i64
func.func @mm(%arg0: i64, %arg1: i64) -> i64 {
%0 = arith.extsi %arg0 : i64 to i128
%1 = arith.extsi %arg1 : i64 to i128
%3 = arith.trunci %0 : i128 to i64
%4 = arith.trunci %1 : i128 to i64
%2 = arith.muli %3, %4 : i64
%5 = llvm.mlir.addressof @MOD : !llvm.ptr
%6 = llvm.load %5 : !llvm.ptr -> i64
%7 = arith.extsi %6 : i64 to i128
%9 = arith.trunci %7 : i128 to i64
%8 = arith.remsi %2, %9 : i64
func.return %8 : i64
}
func.func @mpow(%arg0: i64, %arg1: i64) -> i64 {
%10 = arith.constant 1 : i32
%11 = arith.extsi %10 : i32 to i64
%12 = llvm.mlir.constant(1 : i64) : i64
%13 = llvm.alloca %12 x i64 : (i64) -> !llvm.ptr
llvm.store %11, %13 : i64, !llvm.ptr
%14 = llvm.mlir.addressof @MOD : !llvm.ptr
%15 = llvm.load %14 : !llvm.ptr -> i64
%16 = arith.remsi %arg0, %15 : i64
%17 = llvm.mlir.constant(1 : i64) : i64
%18 = llvm.alloca %17 x i64 : (i64) -> !llvm.ptr
llvm.store %16, %18 : i64, !llvm.ptr
%19 = llvm.load %18 : !llvm.ptr -> i64
%20 = arith.constant 0 : i32
%22 = arith.extsi %20 : i32 to i64
%21 = arith.cmpi slt, %19, %22 : i64
cf.cond_br %21, ^bb0, ^bb1
^bb0:
%23 = llvm.load %18 : !llvm.ptr -> i64
%24 = llvm.mlir.addressof @MOD : !llvm.ptr
%25 = llvm.load %24 : !llvm.ptr -> i64
%26 = arith.addi %23, %25 : i64
llvm.store %26, %18 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%27 = llvm.mlir.constant(1 : i64) : i64
%28 = llvm.alloca %27 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %28 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%29 = llvm.load %28 : !llvm.ptr -> i64
%30 = arith.constant 0 : i32
%32 = arith.extsi %30 : i32 to i64
%31 = arith.cmpi sgt, %29, %32 : i64
cf.cond_br %31, ^bb4, ^bb5
^bb4:
%33 = llvm.load %28 : !llvm.ptr -> i64
%34 = arith.constant 1 : i32
%36 = arith.extsi %34 : i32 to i64
%35 = arith.andi %33, %36 : i64
%37 = arith.constant 0 : i32
%39 = arith.extsi %37 : i32 to i64
%38 = arith.cmpi ne, %35, %39 : i64
cf.cond_br %38, ^bb6, ^bb7
^bb6:
%41 = llvm.load %13 : !llvm.ptr -> i64
%42 = llvm.load %18 : !llvm.ptr -> i64
%40 = func.call @mm(%41, %42) : (i64, i64) -> i64
llvm.store %40, %13 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%44 = llvm.load %18 : !llvm.ptr -> i64
%45 = llvm.load %18 : !llvm.ptr -> i64
%43 = func.call @mm(%44, %45) : (i64, i64) -> i64
llvm.store %43, %18 : i64, !llvm.ptr
%46 = llvm.load %28 : !llvm.ptr -> i64
%47 = arith.constant 1 : i32
%49 = arith.extsi %47 : i32 to i64
%48 = arith.shrsi %46, %49 : i64
llvm.store %48, %28 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%50 = llvm.load %13 : !llvm.ptr -> i64
func.return %50 : i64
}
func.func @heapsort_i64(%arg0: !llvm.ptr, %arg1: i64) -> () {
%51 = arith.constant 2 : i32
%53 = arith.extsi %51 : i32 to i64
%52 = arith.divsi %arg1, %53 : i64
%54 = llvm.mlir.constant(1 : i64) : i64
%55 = llvm.alloca %54 x i64 : (i64) -> !llvm.ptr
llvm.store %52, %55 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%56 = llvm.load %55 : !llvm.ptr -> i64
%57 = arith.constant 0 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.cmpi sgt, %56, %59 : i64
cf.cond_br %58, ^bb10, ^bb11
^bb10:
%60 = llvm.load %55 : !llvm.ptr -> i64
%61 = arith.constant 1 : i32
%63 = arith.extsi %61 : i32 to i64
%62 = arith.subi %60, %63 : i64
llvm.store %62, %55 : i64, !llvm.ptr
%64 = llvm.load %55 : !llvm.ptr -> i64
%65 = llvm.mlir.constant(1 : i64) : i64
%66 = llvm.alloca %65 x i64 : (i64) -> !llvm.ptr
llvm.store %64, %66 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%67 = arith.constant 2 : i32
%68 = llvm.load %66 : !llvm.ptr -> i64
%70 = arith.extsi %67 : i32 to i64
%69 = arith.muli %70, %68 : i64
%71 = arith.constant 1 : i32
%73 = arith.extsi %71 : i32 to i64
%72 = arith.addi %69, %73 : i64
%74 = arith.cmpi slt, %72, %arg1 : i64
cf.cond_br %74, ^bb13, ^bb14
^bb13:
%75 = arith.constant 2 : i32
%76 = llvm.load %66 : !llvm.ptr -> i64
%78 = arith.extsi %75 : i32 to i64
%77 = arith.muli %78, %76 : i64
%79 = arith.constant 1 : i32
%81 = arith.extsi %79 : i32 to i64
%80 = arith.addi %77, %81 : i64
%82 = llvm.load %66 : !llvm.ptr -> i64
%83 = llvm.mlir.constant(1 : i64) : i64
%84 = llvm.alloca %83 x i64 : (i64) -> !llvm.ptr
llvm.store %82, %84 : i64, !llvm.ptr
%86 = llvm.load %84 : !llvm.ptr -> i64
%87 = llvm.getelementptr %arg0[%86] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%85 = llvm.load %87 : !llvm.ptr -> i64
%89 = llvm.getelementptr %arg0[%80] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%88 = llvm.load %89 : !llvm.ptr -> i64
%90 = arith.cmpi slt, %85, %88 : i64
cf.cond_br %90, ^bb15, ^bb16
^bb15:
llvm.store %80, %84 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%91 = arith.constant 1 : i32
%93 = arith.extsi %91 : i32 to i64
%92 = arith.addi %80, %93 : i64
%94 = arith.cmpi slt, %92, %arg1 : i64
cf.cond_br %94, ^bb18, ^bb19
^bb18:
%96 = llvm.load %84 : !llvm.ptr -> i64
%97 = llvm.getelementptr %arg0[%96] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%95 = llvm.load %97 : !llvm.ptr -> i64
%99 = arith.constant 1 : i32
%101 = arith.extsi %99 : i32 to i64
%100 = arith.addi %80, %101 : i64
%102 = llvm.getelementptr %arg0[%100] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%98 = llvm.load %102 : !llvm.ptr -> i64
%103 = arith.cmpi slt, %95, %98 : i64
cf.cond_br %103, ^bb21, ^bb22
^bb21:
%104 = arith.constant 1 : i32
%106 = arith.extsi %104 : i32 to i64
%105 = arith.addi %80, %106 : i64
llvm.store %105, %84 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%107 = llvm.load %84 : !llvm.ptr -> i64
%108 = llvm.load %66 : !llvm.ptr -> i64
%109 = arith.cmpi eq, %107, %108 : i64
cf.cond_br %109, ^bb24, ^bb25
^bb24:
cf.br ^bb14
^bb25:
cf.br ^bb26
^bb26:
%111 = llvm.load %66 : !llvm.ptr -> i64
%112 = llvm.getelementptr %arg0[%111] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%110 = llvm.load %112 : !llvm.ptr -> i64
%114 = llvm.load %84 : !llvm.ptr -> i64
%115 = llvm.getelementptr %arg0[%114] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%113 = llvm.load %115 : !llvm.ptr -> i64
%116 = llvm.load %66 : !llvm.ptr -> i64
%117 = llvm.getelementptr %arg0[%116] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %113, %117 : i64, !llvm.ptr
%118 = llvm.load %84 : !llvm.ptr -> i64
%119 = llvm.getelementptr %arg0[%118] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %110, %119 : i64, !llvm.ptr
%120 = llvm.load %84 : !llvm.ptr -> i64
llvm.store %120, %66 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
cf.br ^bb9
^bb11:
%121 = arith.constant 1 : i32
%123 = arith.extsi %121 : i32 to i64
%122 = arith.subi %arg1, %123 : i64
%124 = llvm.mlir.constant(1 : i64) : i64
%125 = llvm.alloca %124 x i64 : (i64) -> !llvm.ptr
llvm.store %122, %125 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%126 = llvm.load %125 : !llvm.ptr -> i64
%127 = arith.constant 0 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.cmpi sgt, %126, %129 : i64
cf.cond_br %128, ^bb28, ^bb29
^bb28:
%131 = arith.constant 0 : i32
%132 = arith.extsi %131 : i32 to i64
%133 = llvm.getelementptr %arg0[%132] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%130 = llvm.load %133 : !llvm.ptr -> i64
%135 = llvm.load %125 : !llvm.ptr -> i64
%136 = llvm.getelementptr %arg0[%135] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%134 = llvm.load %136 : !llvm.ptr -> i64
%137 = arith.constant 0 : i32
%138 = arith.extsi %137 : i32 to i64
%139 = llvm.getelementptr %arg0[%138] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %134, %139 : i64, !llvm.ptr
%140 = llvm.load %125 : !llvm.ptr -> i64
%141 = llvm.getelementptr %arg0[%140] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %130, %141 : i64, !llvm.ptr
%142 = arith.constant 0 : i32
%143 = arith.extsi %142 : i32 to i64
%144 = llvm.mlir.constant(1 : i64) : i64
%145 = llvm.alloca %144 x i64 : (i64) -> !llvm.ptr
llvm.store %143, %145 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%146 = arith.constant 2 : i32
%147 = llvm.load %145 : !llvm.ptr -> i64
%149 = arith.extsi %146 : i32 to i64
%148 = arith.muli %149, %147 : i64
%150 = arith.constant 1 : i32
%152 = arith.extsi %150 : i32 to i64
%151 = arith.addi %148, %152 : i64
%153 = llvm.load %125 : !llvm.ptr -> i64
%154 = arith.cmpi slt, %151, %153 : i64
cf.cond_br %154, ^bb31, ^bb32
^bb31:
%155 = arith.constant 2 : i32
%156 = llvm.load %145 : !llvm.ptr -> i64
%158 = arith.extsi %155 : i32 to i64
%157 = arith.muli %158, %156 : i64
%159 = arith.constant 1 : i32
%161 = arith.extsi %159 : i32 to i64
%160 = arith.addi %157, %161 : i64
%162 = llvm.load %145 : !llvm.ptr -> i64
%163 = llvm.mlir.constant(1 : i64) : i64
%164 = llvm.alloca %163 x i64 : (i64) -> !llvm.ptr
llvm.store %162, %164 : i64, !llvm.ptr
%166 = llvm.load %164 : !llvm.ptr -> i64
%167 = llvm.getelementptr %arg0[%166] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%165 = llvm.load %167 : !llvm.ptr -> i64
%169 = llvm.getelementptr %arg0[%160] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%168 = llvm.load %169 : !llvm.ptr -> i64
%170 = arith.cmpi slt, %165, %168 : i64
cf.cond_br %170, ^bb33, ^bb34
^bb33:
llvm.store %160, %164 : i64, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%171 = arith.constant 1 : i32
%173 = arith.extsi %171 : i32 to i64
%172 = arith.addi %160, %173 : i64
%174 = llvm.load %125 : !llvm.ptr -> i64
%175 = arith.cmpi slt, %172, %174 : i64
cf.cond_br %175, ^bb36, ^bb37
^bb36:
%177 = llvm.load %164 : !llvm.ptr -> i64
%178 = llvm.getelementptr %arg0[%177] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%176 = llvm.load %178 : !llvm.ptr -> i64
%180 = arith.constant 1 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.addi %160, %182 : i64
%183 = llvm.getelementptr %arg0[%181] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%179 = llvm.load %183 : !llvm.ptr -> i64
%184 = arith.cmpi slt, %176, %179 : i64
cf.cond_br %184, ^bb39, ^bb40
^bb39:
%185 = arith.constant 1 : i32
%187 = arith.extsi %185 : i32 to i64
%186 = arith.addi %160, %187 : i64
llvm.store %186, %164 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%188 = llvm.load %164 : !llvm.ptr -> i64
%189 = llvm.load %145 : !llvm.ptr -> i64
%190 = arith.cmpi eq, %188, %189 : i64
cf.cond_br %190, ^bb42, ^bb43
^bb42:
cf.br ^bb32
^bb43:
cf.br ^bb44
^bb44:
%192 = llvm.load %145 : !llvm.ptr -> i64
%193 = llvm.getelementptr %arg0[%192] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%191 = llvm.load %193 : !llvm.ptr -> i64
%195 = llvm.load %164 : !llvm.ptr -> i64
%196 = llvm.getelementptr %arg0[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%194 = llvm.load %196 : !llvm.ptr -> i64
%197 = llvm.load %145 : !llvm.ptr -> i64
%198 = llvm.getelementptr %arg0[%197] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %194, %198 : i64, !llvm.ptr
%199 = llvm.load %164 : !llvm.ptr -> i64
%200 = llvm.getelementptr %arg0[%199] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %191, %200 : i64, !llvm.ptr
%201 = llvm.load %164 : !llvm.ptr -> i64
llvm.store %201, %145 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%202 = llvm.load %125 : !llvm.ptr -> i64
%203 = arith.constant 1 : i32
%205 = arith.extsi %203 : i32 to i64
%204 = arith.subi %202, %205 : i64
llvm.store %204, %125 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
func.return
}
// Module static: sf_keys
llvm.mlir.global internal @sf_keys() {addr_space = 0 : i32} : !llvm.ptr {
%206 = llvm.mlir.zero : !llvm.ptr
llvm.return %206 : !llvm.ptr
}
// Module static: sf_vals
llvm.mlir.global internal @sf_vals() {addr_space = 0 : i32} : !llvm.ptr {
%207 = llvm.mlir.zero : !llvm.ptr
llvm.return %207 : !llvm.ptr
}
// Module static: sf_count
llvm.mlir.global internal @sf_count(0 : i64) : i64
func.func @sf_lookup(%arg0: i64) -> i64 {
%208 = arith.constant 0 : i32
%209 = arith.extsi %208 : i32 to i64
%210 = llvm.mlir.constant(1 : i64) : i64
%211 = llvm.alloca %210 x i64 : (i64) -> !llvm.ptr
llvm.store %209, %211 : i64, !llvm.ptr
%212 = llvm.mlir.addressof @sf_count : !llvm.ptr
%213 = llvm.load %212 : !llvm.ptr -> i64
cf.br ^bb45(%213 : i64)
^bb45(%214: i64):
%215 = llvm.load %211 : !llvm.ptr -> i64
%216 = arith.cmpi slt, %215, %214 : i64
cf.cond_br %216, ^bb46(%214 : i64), ^bb47(%214 : i64)
^bb46(%217: i64):
%218 = llvm.load %211 : !llvm.ptr -> i64
%219 = arith.addi %218, %217 : i64
%220 = arith.constant 2 : i32
%222 = arith.extsi %220 : i32 to i64
%221 = arith.divsi %219, %222 : i64
%224 = llvm.mlir.addressof @sf_keys : !llvm.ptr
%225 = llvm.load %224 : !llvm.ptr -> !llvm.ptr
%226 = llvm.getelementptr %225[%221] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%223 = llvm.load %226 : !llvm.ptr -> i64
%227 = arith.cmpi slt, %223, %arg0 : i64
%228 = scf.if %227 -> (i64) {
%229 = arith.constant 1 : i32
%231 = arith.extsi %229 : i32 to i64
%230 = arith.addi %221, %231 : i64
llvm.store %230, %211 : i64, !llvm.ptr
scf.yield %217 : i64
} else {
scf.yield %221 : i64
}
cf.br ^bb45(%228 : i64)
^bb47(%232: i64):
%233 = llvm.load %211 : !llvm.ptr -> i64
%234 = llvm.mlir.addressof @sf_count : !llvm.ptr
%235 = llvm.load %234 : !llvm.ptr -> i64
%236 = arith.cmpi slt, %233, %235 : i64
%237 = scf.if %236 -> (i1) {
%239 = llvm.mlir.addressof @sf_keys : !llvm.ptr
%240 = llvm.load %239 : !llvm.ptr -> !llvm.ptr
%241 = llvm.load %211 : !llvm.ptr -> i64
%242 = llvm.getelementptr %240[%241] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%238 = llvm.load %242 : !llvm.ptr -> i64
%243 = arith.cmpi eq, %238, %arg0 : i64
scf.yield %243 : i1
} else {
%244 = arith.constant false
scf.yield %244 : i1
}
cf.cond_br %237, ^bb48, ^bb49
^bb48:
%246 = llvm.mlir.addressof @sf_vals : !llvm.ptr
%247 = llvm.load %246 : !llvm.ptr -> !llvm.ptr
%248 = llvm.load %211 : !llvm.ptr -> i64
%249 = llvm.getelementptr %247[%248] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%245 = llvm.load %249 : !llvm.ptr -> i64
func.return %245 : i64
^bb49:
cf.br ^bb50
^bb50:
%250 = arith.constant 1 : i32
%251 = arith.extsi %250 : i32 to i64
func.return %251 : i64
}
func.func @compute_superfactorials(%arg0: !llvm.ptr, %arg1: i64) -> () {
func.call @heapsort_i64(%arg0, %arg1) : (!llvm.ptr, i64) -> ()
%253 = arith.constant 0 : i32
%254 = arith.extsi %253 : i32 to i64
%255 = llvm.mlir.constant(1 : i64) : i64
%256 = llvm.alloca %255 x i64 : (i64) -> !llvm.ptr
llvm.store %254, %256 : i64, !llvm.ptr
%257 = arith.constant 0 : i32
%258 = arith.extsi %257 : i32 to i64
%259 = llvm.mlir.constant(1 : i64) : i64
%260 = llvm.alloca %259 x i64 : (i64) -> !llvm.ptr
llvm.store %258, %260 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%261 = llvm.load %260 : !llvm.ptr -> i64
%262 = arith.cmpi slt, %261, %arg1 : i64
cf.cond_br %262, ^bb52, ^bb53
^bb52:
%263 = llvm.load %260 : !llvm.ptr -> i64
%264 = arith.constant 0 : i32
%266 = arith.extsi %264 : i32 to i64
%265 = arith.cmpi eq, %263, %266 : i64
%267 = scf.if %265 -> (i1) {
%268 = arith.constant true
scf.yield %268 : i1
} else {
%270 = llvm.load %260 : !llvm.ptr -> i64
%271 = llvm.getelementptr %arg0[%270] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%269 = llvm.load %271 : !llvm.ptr -> i64
%273 = llvm.load %260 : !llvm.ptr -> i64
%274 = arith.constant 1 : i32
%276 = arith.extsi %274 : i32 to i64
%275 = arith.subi %273, %276 : i64
%277 = llvm.getelementptr %arg0[%275] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%272 = llvm.load %277 : !llvm.ptr -> i64
%278 = arith.cmpi ne, %269, %272 : i64
scf.yield %278 : i1
}
cf.cond_br %267, ^bb54, ^bb55
^bb54:
%280 = llvm.load %260 : !llvm.ptr -> i64
%281 = llvm.getelementptr %arg0[%280] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%279 = llvm.load %281 : !llvm.ptr -> i64
%282 = llvm.load %256 : !llvm.ptr -> i64
%283 = llvm.getelementptr %arg0[%282] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %279, %283 : i64, !llvm.ptr
%284 = llvm.load %256 : !llvm.ptr -> i64
%285 = arith.constant 1 : i32
%287 = arith.extsi %285 : i32 to i64
%286 = arith.addi %284, %287 : i64
llvm.store %286, %256 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%288 = llvm.load %260 : !llvm.ptr -> i64
%289 = arith.constant 1 : i32
%291 = arith.extsi %289 : i32 to i64
%290 = arith.addi %288, %291 : i64
llvm.store %290, %260 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%292 = llvm.load %256 : !llvm.ptr -> i64
%294 = arith.constant 8 : i32
%296 = arith.extsi %294 : i32 to i64
%295 = arith.muli %292, %296 : i64
%293 = func.call @malloc(%295) : (i64) -> !llvm.ptr
%297 = llvm.mlir.addressof @sf_keys : !llvm.ptr
llvm.store %293, %297 : !llvm.ptr, !llvm.ptr
%299 = arith.constant 8 : i32
%301 = arith.extsi %299 : i32 to i64
%300 = arith.muli %292, %301 : i64
%298 = func.call @malloc(%300) : (i64) -> !llvm.ptr
%302 = llvm.mlir.addressof @sf_vals : !llvm.ptr
llvm.store %298, %302 : !llvm.ptr, !llvm.ptr
%303 = arith.constant 0 : i32
%304 = arith.extsi %303 : i32 to i64
%305 = llvm.mlir.addressof @sf_count : !llvm.ptr
llvm.store %304, %305 : i64, !llvm.ptr
%306 = arith.constant 0 : i32
%307 = arith.extsi %306 : i32 to i64
%308 = llvm.mlir.constant(1 : i64) : i64
%309 = llvm.alloca %308 x i64 : (i64) -> !llvm.ptr
llvm.store %307, %309 : i64, !llvm.ptr
%310 = arith.constant 0 : i32
%312 = arith.extsi %310 : i32 to i64
%311 = arith.cmpi sgt, %292, %312 : i64
%313 = scf.if %311 -> (i1) {
%315 = arith.constant 0 : i32
%316 = arith.extsi %315 : i32 to i64
%317 = llvm.getelementptr %arg0[%316] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%314 = llvm.load %317 : !llvm.ptr -> i64
%318 = arith.constant 0 : i32
%320 = arith.extsi %318 : i32 to i64
%319 = arith.cmpi eq, %314, %320 : i64
scf.yield %319 : i1
} else {
%321 = arith.constant false
scf.yield %321 : i1
}
cf.cond_br %313, ^bb57, ^bb58
^bb57:
%322 = arith.constant 0 : i32
%323 = llvm.mlir.addressof @sf_keys : !llvm.ptr
%324 = llvm.load %323 : !llvm.ptr -> !llvm.ptr
%325 = arith.constant 0 : i32
%326 = arith.extsi %322 : i32 to i64
%327 = arith.extsi %325 : i32 to i64
%328 = llvm.getelementptr %324[%327] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %326, %328 : i64, !llvm.ptr
%329 = arith.constant 1 : i32
%330 = llvm.mlir.addressof @sf_vals : !llvm.ptr
%331 = llvm.load %330 : !llvm.ptr -> !llvm.ptr
%332 = arith.constant 0 : i32
%333 = arith.extsi %329 : i32 to i64
%334 = arith.extsi %332 : i32 to i64
%335 = llvm.getelementptr %331[%334] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %333, %335 : i64, !llvm.ptr
%336 = arith.constant 1 : i32
%337 = arith.extsi %336 : i32 to i64
%338 = llvm.mlir.addressof @sf_count : !llvm.ptr
llvm.store %337, %338 : i64, !llvm.ptr
%339 = arith.constant 1 : i32
%340 = arith.extsi %339 : i32 to i64
llvm.store %340, %309 : i64, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%341 = arith.constant 0 : i32
%343 = arith.extsi %341 : i32 to i64
%342 = arith.cmpi sgt, %292, %343 : i64
%344 = scf.if %342 -> (i64) {
%346 = arith.constant 1 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.subi %292, %348 : i64
%349 = llvm.getelementptr %arg0[%347] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%345 = llvm.load %349 : !llvm.ptr -> i64
scf.yield %345 : i64
} else {
%350 = arith.constant 0 : i32
scf.yield %350 : i32
}
%351 = arith.constant 1 : i32
%352 = arith.extsi %351 : i32 to i64
%353 = llvm.mlir.constant(1 : i64) : i64
%354 = llvm.alloca %353 x i64 : (i64) -> !llvm.ptr
llvm.store %352, %354 : i64, !llvm.ptr
%355 = arith.constant 1 : i32
%356 = arith.extsi %355 : i32 to i64
%357 = llvm.mlir.constant(1 : i64) : i64
%358 = llvm.alloca %357 x i64 : (i64) -> !llvm.ptr
llvm.store %356, %358 : i64, !llvm.ptr
%359 = arith.constant 1 : i32
%360 = arith.extsi %359 : i32 to i64
%361 = llvm.mlir.constant(1 : i64) : i64
%362 = llvm.alloca %361 x i64 : (i64) -> !llvm.ptr
llvm.store %360, %362 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%363 = llvm.load %362 : !llvm.ptr -> i64
%364 = arith.cmpi sle, %363, %344 : i64
cf.cond_br %364, ^bb61, ^bb62
^bb61:
%366 = llvm.load %354 : !llvm.ptr -> i64
%367 = llvm.load %362 : !llvm.ptr -> i64
%368 = llvm.mlir.addressof @MOD : !llvm.ptr
%369 = llvm.load %368 : !llvm.ptr -> i64
%370 = arith.remsi %367, %369 : i64
%365 = func.call @mm(%366, %370) : (i64, i64) -> i64
llvm.store %365, %354 : i64, !llvm.ptr
%372 = llvm.load %358 : !llvm.ptr -> i64
%373 = llvm.load %354 : !llvm.ptr -> i64
%371 = func.call @mm(%372, %373) : (i64, i64) -> i64
llvm.store %371, %358 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%374 = llvm.load %309 : !llvm.ptr -> i64
%375 = arith.cmpi slt, %374, %292 : i64
%376 = scf.if %375 -> (i1) {
%378 = llvm.load %309 : !llvm.ptr -> i64
%379 = llvm.getelementptr %arg0[%378] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%377 = llvm.load %379 : !llvm.ptr -> i64
%380 = llvm.load %362 : !llvm.ptr -> i64
%381 = arith.cmpi eq, %377, %380 : i64
scf.yield %381 : i1
} else {
%382 = arith.constant false
scf.yield %382 : i1
}
cf.cond_br %376, ^bb64, ^bb65
^bb64:
%383 = llvm.load %362 : !llvm.ptr -> i64
%384 = llvm.mlir.addressof @sf_keys : !llvm.ptr
%385 = llvm.load %384 : !llvm.ptr -> !llvm.ptr
%386 = llvm.mlir.addressof @sf_count : !llvm.ptr
%387 = llvm.load %386 : !llvm.ptr -> i64
%388 = llvm.getelementptr %385[%387] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %383, %388 : i64, !llvm.ptr
%389 = llvm.load %358 : !llvm.ptr -> i64
%390 = llvm.mlir.addressof @sf_vals : !llvm.ptr
%391 = llvm.load %390 : !llvm.ptr -> !llvm.ptr
%392 = llvm.mlir.addressof @sf_count : !llvm.ptr
%393 = llvm.load %392 : !llvm.ptr -> i64
%394 = llvm.getelementptr %391[%393] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %389, %394 : i64, !llvm.ptr
%395 = llvm.mlir.addressof @sf_count : !llvm.ptr
%396 = llvm.load %395 : !llvm.ptr -> i64
%397 = arith.constant 1 : i32
%399 = arith.extsi %397 : i32 to i64
%398 = arith.addi %396, %399 : i64
%400 = llvm.mlir.addressof @sf_count : !llvm.ptr
llvm.store %398, %400 : i64, !llvm.ptr
%401 = llvm.load %309 : !llvm.ptr -> i64
%402 = arith.constant 1 : i32
%404 = arith.extsi %402 : i32 to i64
%403 = arith.addi %401, %404 : i64
llvm.store %403, %309 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
%405 = llvm.load %362 : !llvm.ptr -> i64
%406 = arith.constant 1 : i32
%408 = arith.extsi %406 : i32 to i64
%407 = arith.addi %405, %408 : i64
llvm.store %407, %362 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
func.return
}
func.func @main() -> i32 {
%410 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%411 = llvm.load %410 : !llvm.ptr -> i64
%412 = arith.constant 1 : i32
%414 = arith.extsi %412 : i32 to i64
%413 = arith.addi %411, %414 : i64
%415 = arith.constant 1 : i32
%416 = arith.extsi %415 : i32 to i64
%409 = func.call @calloc(%413, %416) : (i64, i64) -> !llvm.ptr
%418 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%419 = llvm.load %418 : !llvm.ptr -> i64
%420 = arith.constant 1 : i32
%422 = arith.extsi %420 : i32 to i64
%421 = arith.addi %419, %422 : i64
%423 = arith.constant 1 : i32
%424 = arith.extsi %423 : i32 to i64
%417 = func.call @calloc(%421, %424) : (i64, i64) -> !llvm.ptr
%426 = arith.constant 6000000 : i32
%427 = arith.constant 4 : i32
%428 = arith.muli %426, %427 : i32
%429 = arith.extsi %428 : i32 to i64
%425 = func.call @malloc(%429) : (i64) -> !llvm.ptr
%430 = arith.constant 0 : i32
%431 = arith.extsi %430 : i32 to i64
%432 = llvm.mlir.constant(1 : i64) : i64
%433 = llvm.alloca %432 x i64 : (i64) -> !llvm.ptr
llvm.store %431, %433 : i64, !llvm.ptr
%434 = arith.constant 65536 : i32
%435 = arith.extsi %434 : i32 to i64
%436 = llvm.mlir.constant(1 : i64) : i64
%437 = llvm.alloca %436 x i64 : (i64) -> !llvm.ptr
llvm.store %435, %437 : i64, !llvm.ptr
%439 = llvm.load %437 : !llvm.ptr -> i64
%440 = arith.constant 8 : i32
%442 = arith.extsi %440 : i32 to i64
%441 = arith.muli %439, %442 : i64
%438 = func.call @malloc(%441) : (i64) -> !llvm.ptr
%443 = llvm.mlir.constant(1 : i64) : i64
%444 = llvm.alloca %443 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %438, %444 : !llvm.ptr, !llvm.ptr
%446 = llvm.load %437 : !llvm.ptr -> i64
%447 = arith.constant 8 : i32
%449 = arith.extsi %447 : i32 to i64
%448 = arith.muli %446, %449 : i64
%445 = func.call @malloc(%448) : (i64) -> !llvm.ptr
%450 = llvm.mlir.constant(1 : i64) : i64
%451 = llvm.alloca %450 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %445, %451 : !llvm.ptr, !llvm.ptr
%453 = llvm.load %437 : !llvm.ptr -> i64
%454 = arith.constant 8 : i32
%456 = arith.extsi %454 : i32 to i64
%455 = arith.muli %453, %456 : i64
%452 = func.call @malloc(%455) : (i64) -> !llvm.ptr
%457 = llvm.mlir.constant(1 : i64) : i64
%458 = llvm.alloca %457 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %452, %458 : !llvm.ptr, !llvm.ptr
%460 = llvm.load %437 : !llvm.ptr -> i64
%461 = arith.constant 8 : i32
%463 = arith.extsi %461 : i32 to i64
%462 = arith.muli %460, %463 : i64
%459 = func.call @malloc(%462) : (i64) -> !llvm.ptr
%464 = llvm.mlir.constant(1 : i64) : i64
%465 = llvm.alloca %464 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %459, %465 : !llvm.ptr, !llvm.ptr
%466 = arith.constant 0 : i32
%467 = arith.extsi %466 : i32 to i64
%468 = llvm.mlir.constant(1 : i64) : i64
%469 = llvm.alloca %468 x i64 : (i64) -> !llvm.ptr
llvm.store %467, %469 : i64, !llvm.ptr
%470 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%471 = llvm.load %470 : !llvm.ptr -> i64
%472 = llvm.load %444 : !llvm.ptr -> !llvm.ptr
%473 = arith.constant 0 : i32
%474 = arith.extsi %473 : i32 to i64
%475 = llvm.getelementptr %472[%474] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %471, %475 : i64, !llvm.ptr
%476 = arith.constant 1 : i32
%477 = llvm.load %451 : !llvm.ptr -> !llvm.ptr
%478 = arith.constant 0 : i32
%479 = arith.extsi %476 : i32 to i64
%480 = arith.extsi %478 : i32 to i64
%481 = llvm.getelementptr %477[%480] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %479, %481 : i64, !llvm.ptr
%482 = arith.constant 1 : i32
%483 = llvm.load %458 : !llvm.ptr -> !llvm.ptr
%484 = arith.constant 0 : i32
%485 = arith.extsi %482 : i32 to i64
%486 = arith.extsi %484 : i32 to i64
%487 = llvm.getelementptr %483[%486] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %485, %487 : i64, !llvm.ptr
%488 = arith.constant 1 : i32
%489 = llvm.load %465 : !llvm.ptr -> !llvm.ptr
%490 = arith.constant 0 : i32
%491 = arith.extsi %488 : i32 to i64
%492 = arith.extsi %490 : i32 to i64
%493 = llvm.getelementptr %489[%492] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %491, %493 : i64, !llvm.ptr
%494 = arith.constant 1 : i32
%495 = arith.extsi %494 : i32 to i64
llvm.store %495, %469 : i64, !llvm.ptr
%496 = arith.constant 1 : i32
%497 = arith.constant 1 : i32
%498 = arith.trunci %496 : i32 to i8
%499 = arith.extsi %497 : i32 to i64
%500 = llvm.getelementptr %409[%499] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %498, %500 : i8, !llvm.ptr
%501 = arith.constant 2 : i32
%502 = arith.extsi %501 : i32 to i64
%503 = llvm.mlir.constant(1 : i64) : i64
%504 = llvm.alloca %503 x i64 : (i64) -> !llvm.ptr
llvm.store %502, %504 : i64, !llvm.ptr
%505 = llvm.load %504 : !llvm.ptr -> i64
%506 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%507 = llvm.load %506 : !llvm.ptr -> i64
%508 = arith.cmpi sle, %505, %507 : i64
cf.cond_br %508, ^bb66, ^bb67
^bb66:
%509 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%510 = llvm.load %509 : !llvm.ptr -> i64
%511 = llvm.load %504 : !llvm.ptr -> i64
%512 = arith.divsi %510, %511 : i64
%513 = llvm.mlir.constant(1 : i64) : i64
%514 = llvm.alloca %513 x i64 : (i64) -> !llvm.ptr
llvm.store %512, %514 : i64, !llvm.ptr
%515 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%516 = llvm.load %515 : !llvm.ptr -> i64
%517 = llvm.load %514 : !llvm.ptr -> i64
%518 = arith.divsi %516, %517 : i64
%519 = llvm.mlir.constant(1 : i64) : i64
%520 = llvm.alloca %519 x i64 : (i64) -> !llvm.ptr
llvm.store %518, %520 : i64, !llvm.ptr
%521 = arith.constant 1 : i32
%522 = arith.extsi %521 : i32 to i64
%523 = llvm.mlir.constant(1 : i64) : i64
%524 = llvm.alloca %523 x i64 : (i64) -> !llvm.ptr
llvm.store %522, %524 : i64, !llvm.ptr
%525 = arith.constant 1 : i32
%526 = arith.extsi %525 : i32 to i64
%527 = llvm.mlir.constant(1 : i64) : i64
%528 = llvm.alloca %527 x i64 : (i64) -> !llvm.ptr
llvm.store %526, %528 : i64, !llvm.ptr
%529 = arith.constant 0 : i32
%530 = arith.extsi %529 : i32 to i64
%531 = llvm.mlir.constant(1 : i64) : i64
%532 = llvm.alloca %531 x i64 : (i64) -> !llvm.ptr
llvm.store %530, %532 : i64, !llvm.ptr
%533 = arith.constant 2 : i32
%534 = arith.extsi %533 : i32 to i64
%535 = llvm.mlir.constant(1 : i64) : i64
%536 = llvm.alloca %535 x i64 : (i64) -> !llvm.ptr
llvm.store %534, %536 : i64, !llvm.ptr
%537 = arith.constant 0 : i1
%538 = llvm.mlir.constant(1 : i64) : i64
%539 = llvm.alloca %538 x i1 : (i64) -> !llvm.ptr
llvm.store %537, %539 : i1, !llvm.ptr
cf.br ^bb69
^bb69:
%540 = llvm.load %536 : !llvm.ptr -> i64
%541 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%542 = llvm.load %541 : !llvm.ptr -> i64
%543 = arith.cmpi sle, %540, %542 : i64
%544 = scf.if %543 -> (i1) {
%545 = llvm.load %539 : !llvm.ptr -> i1
%547 = arith.constant 1 : i1
%546 = arith.xori %545, %547 : i1
scf.yield %546 : i1
} else {
%549 = arith.constant false
scf.yield %549 : i1
}
cf.cond_br %544, ^bb70, ^bb71
^bb70:
%551 = llvm.load %536 : !llvm.ptr -> i64
%552 = llvm.getelementptr %417[%551] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%550 = llvm.load %552 : !llvm.ptr -> i8
%553 = arith.constant 0 : i32
%555 = arith.extsi %550 : i8 to i32
%554 = arith.cmpi eq, %555, %553 : i32
%556 = scf.if %554 -> (i32) {
%557 = arith.constant 2 : i32
scf.yield %557 : i32
} else {
%559 = llvm.load %536 : !llvm.ptr -> i64
%560 = llvm.getelementptr %409[%559] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%558 = llvm.load %560 : !llvm.ptr -> i8
scf.yield %558 : i8
}
%561 = arith.trunci %556 : i32 to i8
%563 = llvm.load %536 : !llvm.ptr -> i64
%564 = llvm.getelementptr %417[%563] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%562 = llvm.load %564 : !llvm.ptr -> i8
%565 = arith.constant 0 : i32
%567 = arith.extsi %562 : i8 to i32
%566 = arith.cmpi eq, %567, %565 : i32
cf.cond_br %566, ^bb72, ^bb73
^bb72:
%568 = llvm.load %536 : !llvm.ptr -> i64
%569 = arith.trunci %568 : i64 to i32
%570 = llvm.load %433 : !llvm.ptr -> i64
%571 = llvm.getelementptr %425[%570] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %569, %571 : i32, !llvm.ptr
%572 = llvm.load %433 : !llvm.ptr -> i64
%573 = arith.constant 1 : i32
%575 = arith.extsi %573 : i32 to i64
%574 = arith.addi %572, %575 : i64
llvm.store %574, %433 : i64, !llvm.ptr
%576 = arith.constant 2 : i32
%577 = llvm.load %536 : !llvm.ptr -> i64
%578 = arith.trunci %576 : i32 to i8
%579 = llvm.getelementptr %409[%577] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %578, %579 : i8, !llvm.ptr
cf.br ^bb74
^bb73:
cf.br ^bb74
^bb74:
%580 = arith.constant 1 : i32
%582 = arith.extsi %561 : i8 to i32
%581 = arith.cmpi eq, %582, %580 : i32
cf.cond_br %581, ^bb75, ^bb76
^bb75:
%584 = llvm.load %524 : !llvm.ptr -> i64
%585 = llvm.load %536 : !llvm.ptr -> i64
%586 = llvm.mlir.addressof @MOD : !llvm.ptr
%587 = llvm.load %586 : !llvm.ptr -> i64
%588 = arith.remsi %585, %587 : i64
%583 = func.call @mm(%584, %588) : (i64, i64) -> i64
llvm.store %583, %524 : i64, !llvm.ptr
%589 = llvm.load %532 : !llvm.ptr -> i64
%590 = arith.constant 1 : i32
%592 = arith.extsi %590 : i32 to i64
%591 = arith.addi %589, %592 : i64
llvm.store %591, %532 : i64, !llvm.ptr
cf.br ^bb77
^bb76:
%593 = arith.constant 2 : i32
%595 = arith.extsi %561 : i8 to i32
%594 = arith.cmpi eq, %595, %593 : i32
cf.cond_br %594, ^bb78, ^bb79
^bb78:
%597 = llvm.load %528 : !llvm.ptr -> i64
%598 = llvm.load %536 : !llvm.ptr -> i64
%599 = llvm.mlir.addressof @MOD : !llvm.ptr
%600 = llvm.load %599 : !llvm.ptr -> i64
%601 = arith.remsi %598, %600 : i64
%596 = func.call @mm(%597, %601) : (i64, i64) -> i64
llvm.store %596, %528 : i64, !llvm.ptr
%602 = llvm.load %532 : !llvm.ptr -> i64
%603 = arith.constant 1 : i32
%605 = arith.extsi %603 : i32 to i64
%604 = arith.subi %602, %605 : i64
llvm.store %604, %532 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
cf.br ^bb77
^bb77:
%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 ^bb81
^bb81:
%610 = llvm.load %609 : !llvm.ptr -> i64
%611 = llvm.load %433 : !llvm.ptr -> i64
%612 = arith.cmpi slt, %610, %611 : i64
cf.cond_br %612, ^bb82, ^bb83
^bb82:
%614 = llvm.load %609 : !llvm.ptr -> i64
%615 = llvm.getelementptr %425[%614] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%613 = llvm.load %615 : !llvm.ptr -> i32
%616 = llvm.load %536 : !llvm.ptr -> i64
%617 = arith.extsi %613 : i32 to i64
%618 = arith.muli %616, %617 : i64
%619 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%620 = llvm.load %619 : !llvm.ptr -> i64
%621 = arith.cmpi sgt, %618, %620 : i64
cf.cond_br %621, ^bb84, ^bb85
^bb84:
cf.br ^bb83
^bb85:
cf.br ^bb86
^bb86:
%622 = arith.constant 1 : i32
%623 = arith.trunci %622 : i32 to i8
%624 = llvm.getelementptr %417[%618] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %623, %624 : i8, !llvm.ptr
%625 = llvm.load %536 : !llvm.ptr -> i64
%626 = arith.extsi %613 : i32 to i64
%627 = arith.remsi %625, %626 : i64
%628 = arith.constant 0 : i32
%630 = arith.extsi %628 : i32 to i64
%629 = arith.cmpi eq, %627, %630 : i64
cf.cond_br %629, ^bb87, ^bb88
^bb87:
cf.br ^bb83
^bb88:
cf.br ^bb89
^bb89:
%631 = arith.constant 1 : i32
%633 = arith.extsi %561 : i8 to i32
%632 = arith.cmpi eq, %633, %631 : i32
cf.cond_br %632, ^bb90, ^bb91
^bb90:
%634 = arith.constant 2 : i32
%635 = arith.trunci %634 : i32 to i8
%636 = llvm.getelementptr %409[%618] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %635, %636 : i8, !llvm.ptr
cf.br ^bb92
^bb91:
%637 = arith.constant 2 : i32
%639 = arith.extsi %561 : i8 to i32
%638 = arith.cmpi eq, %639, %637 : i32
cf.cond_br %638, ^bb93, ^bb94
^bb93:
%640 = arith.constant 1 : i32
%641 = arith.trunci %640 : i32 to i8
%642 = llvm.getelementptr %409[%618] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %641, %642 : i8, !llvm.ptr
cf.br ^bb95
^bb94:
cf.br ^bb95
^bb95:
cf.br ^bb92
^bb92:
%643 = llvm.load %609 : !llvm.ptr -> i64
%644 = arith.constant 1 : i32
%646 = arith.extsi %644 : i32 to i64
%645 = arith.addi %643, %646 : i64
llvm.store %645, %609 : i64, !llvm.ptr
cf.br ^bb81
^bb83:
%647 = llvm.load %536 : !llvm.ptr -> i64
%648 = llvm.load %520 : !llvm.ptr -> i64
%649 = arith.cmpi eq, %647, %648 : i64
cf.cond_br %649, ^bb96, ^bb97
^bb96:
%650 = llvm.load %469 : !llvm.ptr -> i64
%651 = llvm.load %437 : !llvm.ptr -> i64
%652 = arith.cmpi sge, %650, %651 : i64
cf.cond_br %652, ^bb99, ^bb100
^bb99:
%653 = llvm.load %437 : !llvm.ptr -> i64
%654 = arith.constant 2 : i32
%656 = arith.extsi %654 : i32 to i64
%655 = arith.muli %653, %656 : i64
%658 = arith.constant 8 : i32
%660 = arith.extsi %658 : i32 to i64
%659 = arith.muli %655, %660 : i64
%657 = func.call @malloc(%659) : (i64) -> !llvm.ptr
%662 = arith.constant 8 : i32
%664 = arith.extsi %662 : i32 to i64
%663 = arith.muli %655, %664 : i64
%661 = func.call @malloc(%663) : (i64) -> !llvm.ptr
%666 = arith.constant 8 : i32
%668 = arith.extsi %666 : i32 to i64
%667 = arith.muli %655, %668 : i64
%665 = func.call @malloc(%667) : (i64) -> !llvm.ptr
%670 = arith.constant 8 : i32
%672 = arith.extsi %670 : i32 to i64
%671 = arith.muli %655, %672 : i64
%669 = func.call @malloc(%671) : (i64) -> !llvm.ptr
%673 = arith.constant 0 : i32
%674 = arith.extsi %673 : i32 to i64
%675 = llvm.mlir.constant(1 : i64) : i64
%676 = llvm.alloca %675 x i64 : (i64) -> !llvm.ptr
llvm.store %674, %676 : i64, !llvm.ptr
cf.br ^bb102
^bb102:
%677 = llvm.load %676 : !llvm.ptr -> i64
%678 = llvm.load %469 : !llvm.ptr -> i64
%679 = arith.cmpi slt, %677, %678 : i64
cf.cond_br %679, ^bb103, ^bb104
^bb103:
%681 = llvm.load %444 : !llvm.ptr -> !llvm.ptr
%682 = llvm.load %676 : !llvm.ptr -> i64
%683 = llvm.getelementptr %681[%682] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%680 = llvm.load %683 : !llvm.ptr -> i64
%684 = llvm.load %676 : !llvm.ptr -> i64
%685 = llvm.getelementptr %657[%684] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %680, %685 : i64, !llvm.ptr
%687 = llvm.load %451 : !llvm.ptr -> !llvm.ptr
%688 = llvm.load %676 : !llvm.ptr -> i64
%689 = llvm.getelementptr %687[%688] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%686 = llvm.load %689 : !llvm.ptr -> i64
%690 = llvm.load %676 : !llvm.ptr -> i64
%691 = llvm.getelementptr %661[%690] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %686, %691 : i64, !llvm.ptr
%693 = llvm.load %458 : !llvm.ptr -> !llvm.ptr
%694 = llvm.load %676 : !llvm.ptr -> i64
%695 = llvm.getelementptr %693[%694] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%692 = llvm.load %695 : !llvm.ptr -> i64
%696 = llvm.load %676 : !llvm.ptr -> i64
%697 = llvm.getelementptr %665[%696] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %692, %697 : i64, !llvm.ptr
%699 = llvm.load %465 : !llvm.ptr -> !llvm.ptr
%700 = llvm.load %676 : !llvm.ptr -> i64
%701 = llvm.getelementptr %699[%700] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%698 = llvm.load %701 : !llvm.ptr -> i64
%702 = llvm.load %676 : !llvm.ptr -> i64
%703 = llvm.getelementptr %669[%702] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %698, %703 : i64, !llvm.ptr
%704 = llvm.load %676 : !llvm.ptr -> i64
%705 = arith.constant 1 : i32
%707 = arith.extsi %705 : i32 to i64
%706 = arith.addi %704, %707 : i64
llvm.store %706, %676 : i64, !llvm.ptr
cf.br ^bb102
^bb104:
%709 = llvm.load %444 : !llvm.ptr -> !llvm.ptr
func.call @free(%709) : (!llvm.ptr) -> ()
%711 = llvm.load %451 : !llvm.ptr -> !llvm.ptr
func.call @free(%711) : (!llvm.ptr) -> ()
%713 = llvm.load %458 : !llvm.ptr -> !llvm.ptr
func.call @free(%713) : (!llvm.ptr) -> ()
%715 = llvm.load %465 : !llvm.ptr -> !llvm.ptr
func.call @free(%715) : (!llvm.ptr) -> ()
llvm.store %657, %444 : !llvm.ptr, !llvm.ptr
llvm.store %661, %451 : !llvm.ptr, !llvm.ptr
llvm.store %665, %458 : !llvm.ptr, !llvm.ptr
llvm.store %669, %465 : !llvm.ptr, !llvm.ptr
llvm.store %655, %437 : i64, !llvm.ptr
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
%716 = llvm.load %514 : !llvm.ptr -> i64
%717 = llvm.load %444 : !llvm.ptr -> !llvm.ptr
%718 = llvm.load %469 : !llvm.ptr -> i64
%719 = llvm.getelementptr %717[%718] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %716, %719 : i64, !llvm.ptr
%720 = llvm.load %524 : !llvm.ptr -> i64
%721 = llvm.load %451 : !llvm.ptr -> !llvm.ptr
%722 = llvm.load %469 : !llvm.ptr -> i64
%723 = llvm.getelementptr %721[%722] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %720, %723 : i64, !llvm.ptr
%724 = llvm.load %528 : !llvm.ptr -> i64
%725 = llvm.load %458 : !llvm.ptr -> !llvm.ptr
%726 = llvm.load %469 : !llvm.ptr -> i64
%727 = llvm.getelementptr %725[%726] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %724, %727 : i64, !llvm.ptr
%728 = llvm.load %532 : !llvm.ptr -> i64
%729 = llvm.load %465 : !llvm.ptr -> !llvm.ptr
%730 = llvm.load %469 : !llvm.ptr -> i64
%731 = llvm.getelementptr %729[%730] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %728, %731 : i64, !llvm.ptr
%732 = llvm.load %469 : !llvm.ptr -> i64
%733 = arith.constant 1 : i32
%735 = arith.extsi %733 : i32 to i64
%734 = arith.addi %732, %735 : i64
llvm.store %734, %469 : i64, !llvm.ptr
%736 = llvm.load %520 : !llvm.ptr -> i64
%737 = arith.constant 1 : i32
%739 = arith.extsi %737 : i32 to i64
%738 = arith.addi %736, %739 : i64
llvm.store %738, %504 : i64, !llvm.ptr
%740 = llvm.load %504 : !llvm.ptr -> i64
%741 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%742 = llvm.load %741 : !llvm.ptr -> i64
%743 = arith.cmpi sgt, %740, %742 : i64
cf.cond_br %743, ^bb105, ^bb106
^bb105:
%744 = arith.constant 1 : i1
llvm.store %744, %539 : i1, !llvm.ptr
cf.br ^bb107
^bb106:
%745 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%746 = llvm.load %745 : !llvm.ptr -> i64
%747 = llvm.load %504 : !llvm.ptr -> i64
%748 = arith.divsi %746, %747 : i64
llvm.store %748, %514 : i64, !llvm.ptr
%749 = llvm.mlir.addressof @LIMIT : !llvm.ptr
%750 = llvm.load %749 : !llvm.ptr -> i64
%751 = llvm.load %514 : !llvm.ptr -> i64
%752 = arith.divsi %750, %751 : i64
llvm.store %752, %520 : i64, !llvm.ptr
%753 = arith.constant 1 : i32
%754 = arith.extsi %753 : i32 to i64
llvm.store %754, %524 : i64, !llvm.ptr
%755 = arith.constant 1 : i32
%756 = arith.extsi %755 : i32 to i64
llvm.store %756, %528 : i64, !llvm.ptr
%757 = arith.constant 0 : i32
%758 = arith.extsi %757 : i32 to i64
llvm.store %758, %532 : i64, !llvm.ptr
cf.br ^bb107
^bb107:
cf.br ^bb98
^bb97:
cf.br ^bb98
^bb98:
%759 = llvm.load %536 : !llvm.ptr -> i64
%760 = arith.constant 1 : i32
%762 = arith.extsi %760 : i32 to i64
%761 = arith.addi %759, %762 : i64
llvm.store %761, %536 : i64, !llvm.ptr
cf.br ^bb69
^bb71:
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
func.call @free(%409) : (!llvm.ptr) -> ()
func.call @free(%417) : (!llvm.ptr) -> ()
func.call @free(%425) : (!llvm.ptr) -> ()
%767 = llvm.load %469 : !llvm.ptr -> i64
%768 = arith.constant 8 : i32
%770 = arith.extsi %768 : i32 to i64
%769 = arith.muli %767, %770 : i64
%766 = func.call @malloc(%769) : (i64) -> !llvm.ptr
%771 = arith.constant 0 : i32
%772 = arith.extsi %771 : i32 to i64
%773 = llvm.mlir.constant(1 : i64) : i64
%774 = llvm.alloca %773 x i64 : (i64) -> !llvm.ptr
llvm.store %772, %774 : i64, !llvm.ptr
cf.br ^bb108
^bb108:
%775 = llvm.load %774 : !llvm.ptr -> i64
%776 = llvm.load %469 : !llvm.ptr -> i64
%777 = arith.cmpi slt, %775, %776 : i64
cf.cond_br %777, ^bb109, ^bb110
^bb109:
%779 = llvm.load %444 : !llvm.ptr -> !llvm.ptr
%780 = llvm.load %774 : !llvm.ptr -> i64
%781 = llvm.getelementptr %779[%780] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%778 = llvm.load %781 : !llvm.ptr -> i64
%782 = arith.constant 1 : i32
%784 = arith.extsi %782 : i32 to i64
%783 = arith.subi %778, %784 : i64
%785 = llvm.load %774 : !llvm.ptr -> i64
%786 = llvm.getelementptr %766[%785] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %783, %786 : i64, !llvm.ptr
%787 = llvm.load %774 : !llvm.ptr -> i64
%788 = arith.constant 1 : i32
%790 = arith.extsi %788 : i32 to i64
%789 = arith.addi %787, %790 : i64
llvm.store %789, %774 : i64, !llvm.ptr
cf.br ^bb108
^bb110:
%792 = llvm.load %469 : !llvm.ptr -> i64
func.call @compute_superfactorials(%766, %792) : (!llvm.ptr, i64) -> ()
func.call @free(%766) : (!llvm.ptr) -> ()
%794 = arith.constant 1 : i32
%795 = arith.extsi %794 : i32 to i64
%796 = llvm.mlir.constant(1 : i64) : i64
%797 = llvm.alloca %796 x i64 : (i64) -> !llvm.ptr
llvm.store %795, %797 : i64, !llvm.ptr
%798 = arith.constant 0 : i32
%799 = arith.extsi %798 : i32 to i64
llvm.store %799, %774 : i64, !llvm.ptr
cf.br ^bb111
^bb111:
%800 = llvm.load %774 : !llvm.ptr -> i64
%801 = llvm.load %469 : !llvm.ptr -> i64
%802 = arith.cmpi slt, %800, %801 : i64
cf.cond_br %802, ^bb112, ^bb113
^bb112:
%804 = llvm.load %444 : !llvm.ptr -> !llvm.ptr
%805 = llvm.load %774 : !llvm.ptr -> i64
%806 = llvm.getelementptr %804[%805] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%803 = llvm.load %806 : !llvm.ptr -> i64
%807 = arith.constant 1 : i32
%809 = arith.extsi %807 : i32 to i64
%808 = arith.subi %803, %809 : i64
%810 = arith.muli %803, %808 : i64
%811 = arith.constant 2 : i32
%813 = arith.extsi %811 : i32 to i64
%812 = arith.divsi %810, %813 : i64
%814 = llvm.mlir.addressof @EXP_MOD : !llvm.ptr
%815 = llvm.load %814 : !llvm.ptr -> i64
%816 = arith.remsi %812, %815 : i64
%817 = arith.constant 0 : i32
%819 = arith.extsi %817 : i32 to i64
%818 = arith.cmpi ne, %816, %819 : i64
cf.cond_br %818, ^bb114, ^bb115
^bb114:
%821 = llvm.load %797 : !llvm.ptr -> i64
%824 = llvm.load %451 : !llvm.ptr -> !llvm.ptr
%825 = llvm.load %774 : !llvm.ptr -> i64
%826 = llvm.getelementptr %824[%825] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%823 = llvm.load %826 : !llvm.ptr -> i64
%822 = func.call @mpow(%823, %816) : (i64, i64) -> i64
%820 = func.call @mm(%821, %822) : (i64, i64) -> i64
llvm.store %820, %797 : i64, !llvm.ptr
%827 = llvm.mlir.addressof @EXP_MOD : !llvm.ptr
%828 = llvm.load %827 : !llvm.ptr -> i64
%829 = arith.subi %828, %816 : i64
%830 = llvm.mlir.addressof @EXP_MOD : !llvm.ptr
%831 = llvm.load %830 : !llvm.ptr -> i64
%832 = arith.remsi %829, %831 : i64
%833 = arith.constant 0 : i32
%835 = arith.extsi %833 : i32 to i64
%834 = arith.cmpi ne, %832, %835 : i64
cf.cond_br %834, ^bb117, ^bb118
^bb117:
%837 = llvm.load %797 : !llvm.ptr -> i64
%840 = llvm.load %458 : !llvm.ptr -> !llvm.ptr
%841 = llvm.load %774 : !llvm.ptr -> i64
%842 = llvm.getelementptr %840[%841] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%839 = llvm.load %842 : !llvm.ptr -> i64
%838 = func.call @mpow(%839, %832) : (i64, i64) -> i64
%836 = func.call @mm(%837, %838) : (i64, i64) -> i64
llvm.store %836, %797 : i64, !llvm.ptr
cf.br ^bb119
^bb118:
cf.br ^bb119
^bb119:
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
%844 = llvm.load %465 : !llvm.ptr -> !llvm.ptr
%845 = llvm.load %774 : !llvm.ptr -> i64
%846 = llvm.getelementptr %844[%845] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%843 = llvm.load %846 : !llvm.ptr -> i64
%847 = llvm.mlir.addressof @EXP_MOD : !llvm.ptr
%848 = llvm.load %847 : !llvm.ptr -> i64
%849 = arith.remsi %843, %848 : i64
%850 = llvm.mlir.addressof @EXP_MOD : !llvm.ptr
%851 = llvm.load %850 : !llvm.ptr -> i64
%852 = arith.addi %849, %851 : i64
%853 = llvm.mlir.addressof @EXP_MOD : !llvm.ptr
%854 = llvm.load %853 : !llvm.ptr -> i64
%855 = arith.remsi %852, %854 : i64
%856 = arith.constant 0 : i32
%858 = arith.extsi %856 : i32 to i64
%857 = arith.cmpi ne, %855, %858 : i64
cf.cond_br %857, ^bb120, ^bb121
^bb120:
%861 = llvm.load %444 : !llvm.ptr -> !llvm.ptr
%862 = llvm.load %774 : !llvm.ptr -> i64
%863 = llvm.getelementptr %861[%862] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%860 = llvm.load %863 : !llvm.ptr -> i64
%864 = arith.constant 1 : i32
%866 = arith.extsi %864 : i32 to i64
%865 = arith.subi %860, %866 : i64
%859 = func.call @sf_lookup(%865) : (i64) -> i64
%868 = llvm.load %797 : !llvm.ptr -> i64
%869 = func.call @mpow(%859, %855) : (i64, i64) -> i64
%867 = func.call @mm(%868, %869) : (i64, i64) -> i64
llvm.store %867, %797 : i64, !llvm.ptr
cf.br ^bb122
^bb121:
cf.br ^bb122
^bb122:
%870 = llvm.load %774 : !llvm.ptr -> i64
%871 = arith.constant 1 : i32
%873 = arith.extsi %871 : i32 to i64
%872 = arith.addi %870, %873 : i64
llvm.store %872, %774 : i64, !llvm.ptr
cf.br ^bb111
^bb113:
%875 = llvm.load %444 : !llvm.ptr -> !llvm.ptr
func.call @free(%875) : (!llvm.ptr) -> ()
%877 = llvm.load %451 : !llvm.ptr -> !llvm.ptr
func.call @free(%877) : (!llvm.ptr) -> ()
%879 = llvm.load %458 : !llvm.ptr -> !llvm.ptr
func.call @free(%879) : (!llvm.ptr) -> ()
%881 = llvm.load %465 : !llvm.ptr -> !llvm.ptr
func.call @free(%881) : (!llvm.ptr) -> ()
%883 = llvm.mlir.addressof @sf_keys : !llvm.ptr
%884 = llvm.load %883 : !llvm.ptr -> !llvm.ptr
func.call @free(%884) : (!llvm.ptr) -> ()
%886 = llvm.mlir.addressof @sf_vals : !llvm.ptr
%887 = llvm.load %886 : !llvm.ptr -> !llvm.ptr
func.call @free(%887) : (!llvm.ptr) -> ()
%888 = llvm.mlir.addressof @str_0 : !llvm.ptr
%889 = llvm.load %797 : !llvm.ptr -> i64
%890 = llvm.call @printf(%888, %889) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%891 = arith.constant 0 : i32
func.return %891 : i32
}
}