Problem 586
Binary Quadratic Form — f(10^15, 40).
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n log n) | ? |
|---|
| Space complexity | O(n^2) | ? |
|---|
| Approach | Flow solution | Not curated |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 586
# Binary Quadratic Form — f(10^15, 40).
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function realloc(p: ptr<void>, size: i64) -> ptr<void>
}
function isqrt(n: i64) -> i64 {
if n <= 0 { return 0 }
let mut x: i64 = n
let mut y: i64 = (x + 1) / 2
while y < x { x = y; y = (x + n / x) / 2 }
return x
}
function iroot(n: i64, k: i64) -> i64 {
if k <= 1 { return n }
if k == 2 { return isqrt(n) }
if n < 1 { return 0 }
let mut lo: i64 = 1
let mut hi: i64 = n
while lo < hi {
let mid: i64 = (lo + hi + 1) / 2
let mut p: i128 = 1
let mut i: i64 = 0
let mut ov: i64 = 0
while i < k {
if p > (n as i128) / (mid as i128) { ov = 1; break }
p = p * (mid as i128)
i = i + 1
}
if ov != 0 || p > (n as i128) {
hi = mid - 1
} else {
lo = mid
}
}
return lo
}
function ipow(base: i64, e: i64) -> i64 {
let mut r: i64 = 1
let mut i: i64 = 0
while i < e { r = r * base; i = i + 1 }
return r
}
function sieve(limit: i64, primes: ptr<i64>) -> i64 {
let s: ptr<i8> = calloc(limit + 1, 1)
let mut i: i64 = 0
while i <= limit { s[i] = 1; i = i + 1 }
s[0] = 0; s[1] = 0
i = 2
while i * i <= limit {
if s[i] != 0 {
let mut j: i64 = i * i
while j <= limit { s[j] = 0; j = j + i }
}
i = i + 1
}
let mut m: i64 = 0
i = 2
while i <= limit {
if s[i] != 0 { primes[m] = i; m = m + 1 }
i = i + 1
}
free(s)
return m
}
function bisect_right(a: ptr<i64>, n: i64, x: i64) -> i64 {
let mut lo: i64 = 0
let mut hi: i64 = n
while lo < hi {
let mid: i64 = (lo + hi) / 2
if a[mid] <= x { lo = mid + 1 } else { hi = mid }
}
return lo
}
let mut SPLIT: ptr<i64> = null
let mut NSPLIT: i64 = 0
let mut Warr: ptr<i64> = null
let mut NLIMIT: i64 = 0
let mut INERT: ptr<i64> = null
let mut NINERT: i64 = 0
let mut VALS: ptr<i64> = null
let mut NVALS: i64 = 0
let mut VCAP: i64 = 0
function add_val(v: i64) -> void {
if NVALS >= VCAP {
let mut nc: i64 = 1024
if VCAP > 0 { nc = VCAP * 2 }
VALS = realloc(VALS, nc * 8)
VCAP = nc
}
VALS[NVALS] = v
NVALS = NVALS + 1
}
function mult_rec(idx: i64, cur: i64, qmax: i64) -> void {
let mut t: i64 = cur
while t <= qmax {
add_val(t)
if t > qmax / 5 { break }
t = t * 5
}
let mut j: i64 = idx
while j < NINERT {
let p: i64 = INERT[j]
let p2: i64 = p * p
if cur > qmax / p2 { break }
let mut x: i64 = cur * p2
while x <= qmax {
mult_rec(j + 1, x, qmax)
if x > qmax / p2 { break }
x = x * p2
}
j = j + 1
}
}
function build_W(qmax: i64) -> void {
let lim: i64 = isqrt(qmax) + 1
let pr: ptr<i64> = calloc(lim + 10, 8)
let np: i64 = sieve(lim, pr)
INERT = calloc(np, 8)
NINERT = 0
let mut i: i64 = 0
while i < np {
let p: i64 = pr[i]
let m: i64 = p % 5
if m == 2 || m == 3 {
INERT[NINERT] = p
NINERT = NINERT + 1
}
i = i + 1
}
NVALS = 0
VCAP = 0
VALS = null
mult_rec(0, 1, qmax)
# sort
let mut gap: i64 = NVALS / 2
while gap > 0 {
i = gap
while i < NVALS {
let key: i64 = VALS[i]
let mut j: i64 = i
while j >= gap && VALS[j - gap] > key {
VALS[j] = VALS[j - gap]
j = j - gap
}
VALS[j] = key
i = i + 1
}
gap = gap / 2
}
let mut w: i64 = 0
i = 0
while i < NVALS {
if w == 0 || VALS[i] != VALS[w - 1] {
VALS[w] = VALS[i]
w = w + 1
}
i = i + 1
}
NVALS = w
Warr = calloc(qmax + 1, 8)
let mut c: i64 = 0
let mut vi: i64 = 0
let mut x: i64 = 1
while x <= qmax {
while vi < NVALS && VALS[vi] == x {
c = c + 1
vi = vi + 1
}
Warr[x] = c
x = x + 1
}
free(pr); free(INERT); free(VALS)
}
function sum_last(A: i64, start_idx: i64, e: i64) -> i64 {
let max_p: i64 = iroot(NLIMIT / A, e)
let end_idx: i64 = bisect_right(SPLIT, NSPLIT, max_p)
if end_idx <= start_idx { return 0 }
let mut total: i64 = 0
let mut idx: i64 = start_idx
while idx < end_idx {
let p: i64 = SPLIT[idx]
let pe: i64 = ipow(p, e)
let q: i64 = NLIMIT / (A * pe)
let mut high_p: i64 = iroot(NLIMIT / (A * q), e)
if high_p > max_p { high_p = max_p }
let mut idx2: i64 = bisect_right(SPLIT, NSPLIT, high_p)
if idx2 > end_idx { idx2 = end_idx }
total = total + (idx2 - idx) * Warr[q]
idx = idx2
}
return total
}
let mut SEQ: ptr<i64> = null
let mut SEQL: i64 = 0
let mut ACC: i64 = 0
function rec(pos: i64, start_idx: i64, A: i64) -> void {
if pos == SEQL - 1 {
ACC = ACC + sum_last(A, start_idx, SEQ[pos])
return
}
let e: i64 = SEQ[pos]
let max_p_here: i64 = iroot(NLIMIT / A, e)
let mut idx: i64 = start_idx
while idx < NSPLIT {
if idx + (SEQL - 1 - pos) >= NSPLIT { break }
let p: i64 = SPLIT[idx]
if p > max_p_here { break }
let pe: i64 = ipow(p, e)
if A > NLIMIT / pe { break }
let newA: i64 = A * pe
let max_rem: i64 = NLIMIT / newA
let mut prod_min: i64 = 1
let mut ok: i64 = 1
let mut j: i64 = pos + 1
while j < SEQL {
let pj: i64 = SPLIT[idx + (j - pos)]
let ej: i64 = SEQ[j]
let pje: i64 = ipow(pj, ej)
if prod_min > max_rem / pje { ok = 0; break }
prod_min = prod_min * pje
j = j + 1
}
if ok == 0 { break }
rec(pos + 1, idx + 1, newA)
idx = idx + 1
}
}
# Sequence generation
let mut FS: ptr<i64> = null
let mut NFS: i64 = 0
let mut ALLSEQ: ptr<i64> = null
let mut ALLLEN: ptr<i64> = null
let mut NALL: i64 = 0
let mut ACAP: i64 = 0
function save_seq(cur: ptr<i64>, k: i64) -> void {
let mut prod: i64 = 1
let mut i: i64 = 0
while i < k {
let mut e: i64 = 0
while e < cur[i] {
if prod > NLIMIT / FS[i] { return }
prod = prod * FS[i]
e = e + 1
}
i = i + 1
}
if NALL >= ACAP {
let mut nc: i64 = 64
if ACAP > 0 { nc = ACAP * 2 }
ALLSEQ = realloc(ALLSEQ, nc * 16 * 8)
ALLLEN = realloc(ALLLEN, nc * 8)
ACAP = nc
}
i = 0
while i < k {
ALLSEQ[NALL * 16 + i] = cur[i]
i = i + 1
}
ALLLEN[NALL] = k
NALL = NALL + 1
}
function perm_rec(pos: i64, exps: ptr<i64>, k: i64, used: ptr<i8>, cur: ptr<i64>) -> void {
if pos == k {
save_seq(cur, k)
return
}
let mut prev: i64 = -999
let mut i: i64 = 0
while i < k {
if used[i] == 0 && exps[i] != prev {
used[i] = 1
cur[pos] = exps[i]
perm_rec(pos + 1, exps, k, used, cur)
used[i] = 0
prev = exps[i]
}
i = i + 1
}
}
function fac_rec(rem: i64, start: i64, cur: ptr<i64>, cn: i64) -> void {
if rem == 1 {
let exps: ptr<i64> = calloc(cn, 8)
let mut i: i64 = 0
while i < cn { exps[i] = cur[i] - 1; i = i + 1 }
let used: ptr<i8> = calloc(cn, 1)
let perm: ptr<i64> = calloc(cn, 8)
perm_rec(0, exps, cn, used, perm)
free(exps); free(used); free(perm)
return
}
let mut f: i64 = start
while f <= rem {
if rem % f == 0 {
cur[cn] = f
fac_rec(rem / f, f, cur, cn + 1)
}
f = f + 1
}
}
function compute_f(n: i64, r: i64) -> i64 {
NLIMIT = n
let small: ptr<i64> = calloc(4000, 8)
let ns: i64 = sieve(20000, small)
FS = calloc(ns, 8)
NFS = 0
let mut i: i64 = 0
while i < ns {
let p: i64 = small[i]
let m: i64 = p % 5
if m == 1 || m == 4 {
FS[NFS] = p
NFS = NFS + 1
}
i = i + 1
}
NALL = 0; ACAP = 0; ALLSEQ = null; ALLLEN = null
let curf: ptr<i64> = calloc(64, 8)
fac_rec(2 * r, 2, curf, 0)
fac_rec(2 * r + 1, 2, curf, 0)
free(curf)
if NALL == 0 { return 0 }
let mut min_core: i64 = 0
i = 0
while i < NALL {
let k: i64 = ALLLEN[i]
let mut prod: i64 = 1
let mut j: i64 = 0
while j < k {
prod = prod * ipow(FS[j], ALLSEQ[i * 16 + j])
j = j + 1
}
if min_core == 0 || prod < min_core { min_core = prod }
i = i + 1
}
let qmax: i64 = n / min_core
build_W(qmax)
let mut max_need: i64 = 0
i = 0
while i < NALL {
let k: i64 = ALLLEN[i]
let mut bound: i64 = 0
if k == 1 {
bound = iroot(n, ALLSEQ[i * 16])
} else {
let mut prod: i64 = 1
let mut j: i64 = 0
while j < k - 1 {
prod = prod * ipow(FS[j], ALLSEQ[i * 16 + j])
j = j + 1
}
bound = iroot(n / prod, ALLSEQ[i * 16 + k - 1])
}
if bound > max_need { max_need = bound }
i = i + 1
}
let pr: ptr<i64> = calloc(max_need / 3 + 100, 8)
let np: i64 = sieve(max_need + 10, pr)
SPLIT = calloc(np, 8)
NSPLIT = 0
i = 0
while i < np {
let p: i64 = pr[i]
let m: i64 = p % 5
if m == 1 || m == 4 {
SPLIT[NSPLIT] = p
NSPLIT = NSPLIT + 1
}
i = i + 1
}
free(pr); free(small)
let mut ans: i64 = 0
i = 0
while i < NALL {
SEQL = ALLLEN[i]
SEQ = ALLSEQ + i * 16
ACC = 0
rec(0, 0, 1)
ans = ans + ACC
i = i + 1
}
free(Warr); free(SPLIT); free(FS); free(ALLSEQ); free(ALLLEN)
return ans
}
function main() -> i32 {
printf("%lld\n", compute_f(1000000000000000, 40))
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 isqrt_i64(int64_t n);
int64_t iroot_i64_i64(int64_t n, int64_t k);
int64_t ipow_i64_i64(int64_t base, int64_t e);
int64_t sieve_i64_ptr_i64(int64_t limit, int64_t* primes);
int64_t bisect_right_ptr_i64_i64_i64(int64_t* a, int64_t n, int64_t x);
void add_val_i64(int64_t v);
void mult_rec_i64_i64_i64(int64_t idx, int64_t cur, int64_t qmax);
void build_W_i64(int64_t qmax);
int64_t sum_last_i64_i64_i64(int64_t A, int64_t start_idx, int64_t e);
void rec_i64_i64_i64(int64_t pos, int64_t start_idx, int64_t A);
void save_seq_ptr_i64_i64(int64_t* cur, int64_t k);
void perm_rec_i64_ptr_i64_i64_ptr_i8_ptr_i64(int64_t pos, int64_t* exps, int64_t k, int8_t* used, int64_t* cur);
void fac_rec_i64_i64_ptr_i64_i64(int64_t rem, int64_t start, int64_t* cur, int64_t cn);
int64_t compute_f_i64_i64(int64_t n, int64_t r);
int32_t main(void);
/* Module statics */
static int64_t* SPLIT = NULL;
static int64_t NSPLIT = 0;
static int64_t* Warr = NULL;
static int64_t NLIMIT = 0;
static int64_t* INERT = NULL;
static int64_t NINERT = 0;
static int64_t* VALS = NULL;
static int64_t NVALS = 0;
static int64_t VCAP = 0;
static int64_t* SEQ = NULL;
static int64_t SEQL = 0;
static int64_t ACC = 0;
static int64_t* FS = NULL;
static int64_t NFS = 0;
static int64_t* ALLSEQ = NULL;
static int64_t* ALLLEN = NULL;
static int64_t NALL = 0;
static int64_t ACAP = 0;
int64_t isqrt_i64(int64_t n) {
if (n <= 0) {
return 0;
}
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 iroot_i64_i64(int64_t n, int64_t k) {
if (k <= 1) {
return n;
}
if (k == 2) {
return isqrt_i64(n);
}
if (n < 1) {
return 0;
}
int64_t lo = 1;
int64_t hi = n;
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV((((lo + hi) + 1)), (2));
__int128 p = 1;
int64_t i = 0;
int64_t ov = 0;
while (i < k) {
if (p > FLOW_CHECKED_DIV((((__int128)(n))), (((__int128)(mid))))) {
ov = 1;
break;
}
p = (p * ((__int128)(mid)));
i = (i + 1);
}
if ((ov != 0 || p > ((__int128)(n)))) {
hi = (mid - 1);
} else {
lo = mid;
}
}
return lo;
}
int64_t ipow_i64_i64(int64_t base, int64_t e) {
int64_t r = 1;
int64_t i = 0;
while (i < e) {
r = (r * base);
i = (i + 1);
}
return r;
}
int64_t sieve_i64_ptr_i64(int64_t limit, int64_t* primes) {
int8_t* s = (int8_t*)(calloc((limit + 1), 1));
int64_t i = 0;
while (i <= limit) {
s[i] = 1;
i = (i + 1);
}
s[0] = 0;
s[1] = 0;
i = 2;
while ((i * i) <= limit) {
if (s[i] != 0) {
int64_t j = (i * i);
while (j <= limit) {
s[j] = 0;
j = (j + i);
}
}
i = (i + 1);
}
int64_t m = 0;
i = 2;
while (i <= limit) {
if (s[i] != 0) {
primes[m] = i;
m = (m + 1);
}
i = (i + 1);
}
free(s);
return m;
}
int64_t bisect_right_ptr_i64_i64_i64(int64_t* a, int64_t n, int64_t x) {
int64_t lo = 0;
int64_t hi = n;
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (a[mid] <= x) {
lo = (mid + 1);
} else {
hi = mid;
}
}
return lo;
}
void add_val_i64(int64_t v) {
if (NVALS >= VCAP) {
int64_t nc = 1024;
if (VCAP > 0) {
nc = (VCAP * 2);
}
VALS = realloc(VALS, (nc * 8));
VCAP = nc;
}
VALS[NVALS] = v;
NVALS = (NVALS + 1);
}
void mult_rec_i64_i64_i64(int64_t idx, int64_t cur, int64_t qmax) {
int64_t t = cur;
while (t <= qmax) {
add_val_i64(t);
if (t > FLOW_CHECKED_DIV((qmax), (5))) {
break;
}
t = (t * 5);
}
int64_t j = idx;
while (j < NINERT) {
int64_t p = INERT[j];
int64_t p2 = (p * p);
if (cur > FLOW_CHECKED_DIV((qmax), (p2))) {
break;
}
int64_t x = (cur * p2);
while (x <= qmax) {
mult_rec_i64_i64_i64((j + 1), x, qmax);
if (x > FLOW_CHECKED_DIV((qmax), (p2))) {
break;
}
x = (x * p2);
}
j = (j + 1);
}
}
void build_W_i64(int64_t qmax) {
int64_t lim = (isqrt_i64(qmax) + 1);
int64_t* pr = (int64_t*)(calloc((lim + 10), 8));
int64_t np = sieve_i64_ptr_i64(lim, pr);
INERT = calloc(np, 8);
NINERT = 0;
int64_t i = 0;
while (i < np) {
int64_t p = pr[i];
int64_t m = FLOW_CHECKED_MOD((p), (5));
if ((m == 2 || m == 3)) {
INERT[NINERT] = p;
NINERT = (NINERT + 1);
}
i = (i + 1);
}
NVALS = 0;
VCAP = 0;
VALS = NULL;
mult_rec_i64_i64_i64(0, 1, qmax);
int64_t gap = FLOW_CHECKED_DIV((NVALS), (2));
while (gap > 0) {
i = gap;
while (i < NVALS) {
int64_t key = VALS[i];
int64_t j = i;
while ((j >= gap && VALS[(j - gap)] > key)) {
VALS[j] = VALS[(j - gap)];
j = (j - gap);
}
VALS[j] = key;
i = (i + 1);
}
gap = FLOW_CHECKED_DIV((gap), (2));
}
int64_t w = 0;
i = 0;
while (i < NVALS) {
if ((w == 0 || VALS[i] != VALS[(w - 1)])) {
VALS[w] = VALS[i];
w = (w + 1);
}
i = (i + 1);
}
NVALS = w;
Warr = calloc((qmax + 1), 8);
int64_t c = 0;
int64_t vi = 0;
int64_t x = 1;
while (x <= qmax) {
while ((vi < NVALS && VALS[vi] == x)) {
c = (c + 1);
vi = (vi + 1);
}
Warr[x] = c;
x = (x + 1);
}
free(pr);
free(INERT);
free(VALS);
}
int64_t sum_last_i64_i64_i64(int64_t A, int64_t start_idx, int64_t e) {
int64_t max_p = iroot_i64_i64(FLOW_CHECKED_DIV((NLIMIT), (A)), e);
int64_t end_idx = bisect_right_ptr_i64_i64_i64(SPLIT, NSPLIT, max_p);
if (end_idx <= start_idx) {
return 0;
}
int64_t total = 0;
int64_t idx = start_idx;
while (idx < end_idx) {
int64_t p = SPLIT[idx];
int64_t pe = ipow_i64_i64(p, e);
int64_t q = FLOW_CHECKED_DIV((NLIMIT), ((A * pe)));
int64_t high_p = iroot_i64_i64(FLOW_CHECKED_DIV((NLIMIT), ((A * q))), e);
if (high_p > max_p) {
high_p = max_p;
}
int64_t idx2 = bisect_right_ptr_i64_i64_i64(SPLIT, NSPLIT, high_p);
if (idx2 > end_idx) {
idx2 = end_idx;
}
total = (total + ((idx2 - idx) * Warr[q]));
idx = idx2;
}
return total;
}
void rec_i64_i64_i64(int64_t pos, int64_t start_idx, int64_t A) {
if (pos == (SEQL - 1)) {
ACC = (ACC + sum_last_i64_i64_i64(A, start_idx, SEQ[pos]));
return;
}
int64_t e = SEQ[pos];
int64_t max_p_here = iroot_i64_i64(FLOW_CHECKED_DIV((NLIMIT), (A)), e);
int64_t idx = start_idx;
while (idx < NSPLIT) {
if ((idx + ((SEQL - 1) - pos)) >= NSPLIT) {
break;
}
int64_t p = SPLIT[idx];
if (p > max_p_here) {
break;
}
int64_t pe = ipow_i64_i64(p, e);
if (A > FLOW_CHECKED_DIV((NLIMIT), (pe))) {
break;
}
int64_t newA = (A * pe);
int64_t max_rem = FLOW_CHECKED_DIV((NLIMIT), (newA));
int64_t prod_min = 1;
int64_t ok = 1;
int64_t j = (pos + 1);
while (j < SEQL) {
int64_t pj = SPLIT[(idx + (j - pos))];
int64_t ej = SEQ[j];
int64_t pje = ipow_i64_i64(pj, ej);
if (prod_min > FLOW_CHECKED_DIV((max_rem), (pje))) {
ok = 0;
break;
}
prod_min = (prod_min * pje);
j = (j + 1);
}
if (ok == 0) {
break;
}
rec_i64_i64_i64((pos + 1), (idx + 1), newA);
idx = (idx + 1);
}
}
void save_seq_ptr_i64_i64(int64_t* cur, int64_t k) {
int64_t prod = 1;
int64_t i = 0;
while (i < k) {
int64_t e = 0;
while (e < cur[i]) {
if (prod > FLOW_CHECKED_DIV((NLIMIT), (FS[i]))) {
return;
}
prod = (prod * FS[i]);
e = (e + 1);
}
i = (i + 1);
}
if (NALL >= ACAP) {
int64_t nc = 64;
if (ACAP > 0) {
nc = (ACAP * 2);
}
ALLSEQ = realloc(ALLSEQ, ((nc * 16) * 8));
ALLLEN = realloc(ALLLEN, (nc * 8));
ACAP = nc;
}
i = 0;
while (i < k) {
ALLSEQ[((NALL * 16) + i)] = cur[i];
i = (i + 1);
}
ALLLEN[NALL] = k;
NALL = (NALL + 1);
}
void perm_rec_i64_ptr_i64_i64_ptr_i8_ptr_i64(int64_t pos, int64_t* exps, int64_t k, int8_t* used, int64_t* cur) {
if (pos == k) {
save_seq_ptr_i64_i64(cur, k);
return;
}
int64_t prev = (-999);
int64_t i = 0;
while (i < k) {
if ((used[i] == 0 && exps[i] != prev)) {
used[i] = 1;
cur[pos] = exps[i];
perm_rec_i64_ptr_i64_i64_ptr_i8_ptr_i64((pos + 1), exps, k, used, cur);
used[i] = 0;
prev = exps[i];
}
i = (i + 1);
}
}
void fac_rec_i64_i64_ptr_i64_i64(int64_t rem, int64_t start, int64_t* cur, int64_t cn) {
if (rem == 1) {
int64_t* exps = (int64_t*)(calloc(cn, 8));
int64_t i = 0;
while (i < cn) {
exps[i] = (cur[i] - 1);
i = (i + 1);
}
int8_t* used = (int8_t*)(calloc(cn, 1));
int64_t* perm = (int64_t*)(calloc(cn, 8));
perm_rec_i64_ptr_i64_i64_ptr_i8_ptr_i64(0, exps, cn, used, perm);
free(exps);
free(used);
free(perm);
return;
}
int64_t f = start;
while (f <= rem) {
if (FLOW_CHECKED_MOD((rem), (f)) == 0) {
cur[cn] = f;
fac_rec_i64_i64_ptr_i64_i64(FLOW_CHECKED_DIV((rem), (f)), f, cur, (cn + 1));
}
f = (f + 1);
}
}
int64_t compute_f_i64_i64(int64_t n, int64_t r) {
NLIMIT = n;
int64_t* small = (int64_t*)(calloc(4000, 8));
int64_t ns = sieve_i64_ptr_i64(20000, small);
FS = calloc(ns, 8);
NFS = 0;
int64_t i = 0;
while (i < ns) {
int64_t p = small[i];
int64_t m = FLOW_CHECKED_MOD((p), (5));
if ((m == 1 || m == 4)) {
FS[NFS] = p;
NFS = (NFS + 1);
}
i = (i + 1);
}
NALL = 0;
ACAP = 0;
ALLSEQ = NULL;
ALLLEN = NULL;
int64_t* curf = (int64_t*)(calloc(64, 8));
fac_rec_i64_i64_ptr_i64_i64((2 * r), 2, curf, 0);
fac_rec_i64_i64_ptr_i64_i64(((2 * r) + 1), 2, curf, 0);
free(curf);
if (NALL == 0) {
return 0;
}
int64_t min_core = 0;
i = 0;
while (i < NALL) {
int64_t k = ALLLEN[i];
int64_t prod = 1;
int64_t j = 0;
while (j < k) {
prod = (prod * ipow_i64_i64(FS[j], ALLSEQ[((i * 16) + j)]));
j = (j + 1);
}
if ((min_core == 0 || prod < min_core)) {
min_core = prod;
}
i = (i + 1);
}
int64_t qmax = FLOW_CHECKED_DIV((n), (min_core));
build_W_i64(qmax);
int64_t max_need = 0;
i = 0;
while (i < NALL) {
int64_t k = ALLLEN[i];
int64_t bound = 0;
if (k == 1) {
bound = iroot_i64_i64(n, ALLSEQ[(i * 16)]);
} else {
int64_t prod = 1;
int64_t j = 0;
while (j < (k - 1)) {
prod = (prod * ipow_i64_i64(FS[j], ALLSEQ[((i * 16) + j)]));
j = (j + 1);
}
bound = iroot_i64_i64(FLOW_CHECKED_DIV((n), (prod)), ALLSEQ[(((i * 16) + k) - 1)]);
}
if (bound > max_need) {
max_need = bound;
}
i = (i + 1);
}
int64_t* pr = (int64_t*)(calloc((FLOW_CHECKED_DIV((max_need), (3)) + 100), 8));
int64_t np = sieve_i64_ptr_i64((max_need + 10), pr);
SPLIT = calloc(np, 8);
NSPLIT = 0;
i = 0;
while (i < np) {
int64_t p = pr[i];
int64_t m = FLOW_CHECKED_MOD((p), (5));
if ((m == 1 || m == 4)) {
SPLIT[NSPLIT] = p;
NSPLIT = (NSPLIT + 1);
}
i = (i + 1);
}
free(pr);
free(small);
int64_t ans = 0;
i = 0;
while (i < NALL) {
SEQL = ALLLEN[i];
SEQ = (ALLSEQ + (i * 16));
ACC = 0;
rec_i64_i64_i64(0, 0, 1);
ans = (ans + ACC);
i = (i + 1);
}
free(Warr);
free(SPLIT);
free(FS);
free(ALLSEQ);
free(ALLLEN);
return ans;
}
int32_t main(void) {
printf("%lld\n", compute_f_i64_i64(1000000000000000, 40));
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 @realloc(!llvm.ptr, i64) -> !llvm.ptr
func.func @isqrt(%arg0: i64) -> i64 {
%0 = arith.constant 0 : i32
%2 = arith.extsi %0 : i32 to i64
%1 = arith.cmpi sle, %arg0, %2 : i64
cf.cond_br %1, ^bb0, ^bb1
^bb0:
%3 = arith.constant 0 : i32
%4 = arith.extsi %3 : i32 to i64
func.return %4 : i64
^bb1:
cf.br ^bb2
^bb2:
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %6 : i64, !llvm.ptr
%7 = llvm.load %6 : !llvm.ptr -> i64
%8 = arith.constant 1 : i32
%10 = arith.extsi %8 : i32 to i64
%9 = arith.addi %7, %10 : i64
%11 = arith.constant 2 : i32
%13 = arith.extsi %11 : i32 to i64
%12 = arith.divsi %9, %13 : i64
%14 = llvm.mlir.constant(1 : i64) : i64
%15 = llvm.alloca %14 x i64 : (i64) -> !llvm.ptr
llvm.store %12, %15 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%16 = llvm.load %15 : !llvm.ptr -> i64
%17 = llvm.load %6 : !llvm.ptr -> i64
%18 = arith.cmpi slt, %16, %17 : i64
cf.cond_br %18, ^bb4, ^bb5
^bb4:
%19 = llvm.load %15 : !llvm.ptr -> i64
llvm.store %19, %6 : i64, !llvm.ptr
%20 = llvm.load %6 : !llvm.ptr -> i64
%21 = llvm.load %6 : !llvm.ptr -> i64
%22 = arith.divsi %arg0, %21 : i64
%23 = arith.addi %20, %22 : i64
%24 = arith.constant 2 : i32
%26 = arith.extsi %24 : i32 to i64
%25 = arith.divsi %23, %26 : i64
llvm.store %25, %15 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%27 = llvm.load %6 : !llvm.ptr -> i64
func.return %27 : i64
}
func.func @iroot(%arg0: i64, %arg1: i64) -> i64 {
%28 = arith.constant 1 : i32
%30 = arith.extsi %28 : i32 to i64
%29 = arith.cmpi sle, %arg1, %30 : i64
cf.cond_br %29, ^bb6, ^bb7
^bb6:
func.return %arg0 : i64
^bb7:
cf.br ^bb8
^bb8:
%31 = arith.constant 2 : i32
%33 = arith.extsi %31 : i32 to i64
%32 = arith.cmpi eq, %arg1, %33 : i64
cf.cond_br %32, ^bb9, ^bb10
^bb9:
%34 = func.call @isqrt(%arg0) : (i64) -> i64
func.return %34 : i64
^bb10:
cf.br ^bb11
^bb11:
%35 = arith.constant 1 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.cmpi slt, %arg0, %37 : i64
cf.cond_br %36, ^bb12, ^bb13
^bb12:
%38 = arith.constant 0 : i32
%39 = arith.extsi %38 : i32 to i64
func.return %39 : i64
^bb13:
cf.br ^bb14
^bb14:
%40 = arith.constant 1 : i32
%41 = arith.extsi %40 : i32 to i64
%42 = llvm.mlir.constant(1 : i64) : i64
%43 = llvm.alloca %42 x i64 : (i64) -> !llvm.ptr
llvm.store %41, %43 : i64, !llvm.ptr
%44 = llvm.mlir.constant(1 : i64) : i64
%45 = llvm.alloca %44 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %45 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%46 = llvm.load %43 : !llvm.ptr -> i64
%47 = llvm.load %45 : !llvm.ptr -> i64
%48 = arith.cmpi slt, %46, %47 : i64
cf.cond_br %48, ^bb16, ^bb17
^bb16:
%49 = llvm.load %43 : !llvm.ptr -> i64
%50 = llvm.load %45 : !llvm.ptr -> i64
%51 = arith.addi %49, %50 : i64
%52 = arith.constant 1 : i32
%54 = arith.extsi %52 : i32 to i64
%53 = arith.addi %51, %54 : i64
%55 = arith.constant 2 : i32
%57 = arith.extsi %55 : i32 to i64
%56 = arith.divsi %53, %57 : i64
%58 = arith.constant 1 : i32
%59 = arith.extsi %58 : i32 to i128
%60 = llvm.mlir.constant(1 : i64) : i64
%61 = llvm.alloca %60 x i128 : (i64) -> !llvm.ptr
llvm.store %59, %61 : i128, !llvm.ptr
%62 = arith.constant 0 : i32
%63 = arith.extsi %62 : i32 to i64
%64 = llvm.mlir.constant(1 : i64) : i64
%65 = llvm.alloca %64 x i64 : (i64) -> !llvm.ptr
llvm.store %63, %65 : i64, !llvm.ptr
%66 = arith.constant 0 : i32
%67 = arith.extsi %66 : i32 to i64
%68 = llvm.mlir.constant(1 : i64) : i64
%69 = llvm.alloca %68 x i64 : (i64) -> !llvm.ptr
llvm.store %67, %69 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%70 = llvm.load %65 : !llvm.ptr -> i64
%71 = arith.cmpi slt, %70, %arg1 : i64
cf.cond_br %71, ^bb19, ^bb20
^bb19:
%72 = llvm.load %61 : !llvm.ptr -> i128
%73 = arith.extsi %arg0 : i64 to i128
%74 = arith.extsi %56 : i64 to i128
%76 = arith.trunci %73 : i128 to i64
%77 = arith.trunci %74 : i128 to i64
%75 = arith.divsi %76, %77 : i64
%79 = arith.trunci %72 : i128 to i64
%78 = arith.cmpi sgt, %79, %75 : i64
cf.cond_br %78, ^bb21, ^bb22
^bb21:
%80 = arith.constant 1 : i32
%81 = arith.extsi %80 : i32 to i64
llvm.store %81, %69 : i64, !llvm.ptr
cf.br ^bb20
^bb22:
cf.br ^bb23
^bb23:
%82 = llvm.load %61 : !llvm.ptr -> i128
%83 = arith.extsi %56 : i64 to i128
%85 = arith.trunci %82 : i128 to i64
%86 = arith.trunci %83 : i128 to i64
%84 = arith.muli %85, %86 : i64
%87 = arith.extsi %84 : i64 to i128
llvm.store %87, %61 : i128, !llvm.ptr
%88 = llvm.load %65 : !llvm.ptr -> i64
%89 = arith.constant 1 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.addi %88, %91 : i64
llvm.store %90, %65 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%92 = llvm.load %69 : !llvm.ptr -> i64
%93 = arith.constant 0 : i32
%95 = arith.extsi %93 : i32 to i64
%94 = arith.cmpi ne, %92, %95 : i64
%96 = scf.if %94 -> (i1) {
%97 = arith.constant true
scf.yield %97 : i1
} else {
%98 = llvm.load %61 : !llvm.ptr -> i128
%99 = arith.extsi %arg0 : i64 to i128
%101 = arith.trunci %98 : i128 to i64
%102 = arith.trunci %99 : i128 to i64
%100 = arith.cmpi sgt, %101, %102 : i64
scf.yield %100 : i1
}
cf.cond_br %96, ^bb24, ^bb25
^bb24:
%103 = arith.constant 1 : i32
%105 = arith.extsi %103 : i32 to i64
%104 = arith.subi %56, %105 : i64
llvm.store %104, %45 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
llvm.store %56, %43 : i64, !llvm.ptr
cf.br ^bb26
^bb26:
cf.br ^bb15
^bb17:
%106 = llvm.load %43 : !llvm.ptr -> i64
func.return %106 : i64
}
func.func @ipow(%arg0: i64, %arg1: i64) -> i64 {
%107 = arith.constant 1 : i32
%108 = arith.extsi %107 : i32 to i64
%109 = llvm.mlir.constant(1 : i64) : i64
%110 = llvm.alloca %109 x i64 : (i64) -> !llvm.ptr
llvm.store %108, %110 : i64, !llvm.ptr
%111 = arith.constant 0 : i32
%112 = arith.extsi %111 : i32 to i64
%113 = llvm.mlir.constant(1 : i64) : i64
%114 = llvm.alloca %113 x i64 : (i64) -> !llvm.ptr
llvm.store %112, %114 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%115 = llvm.load %114 : !llvm.ptr -> i64
%116 = arith.cmpi slt, %115, %arg1 : i64
cf.cond_br %116, ^bb28, ^bb29
^bb28:
%117 = llvm.load %110 : !llvm.ptr -> i64
%118 = arith.muli %117, %arg0 : i64
llvm.store %118, %110 : i64, !llvm.ptr
%119 = llvm.load %114 : !llvm.ptr -> i64
%120 = arith.constant 1 : i32
%122 = arith.extsi %120 : i32 to i64
%121 = arith.addi %119, %122 : i64
llvm.store %121, %114 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%123 = llvm.load %110 : !llvm.ptr -> i64
func.return %123 : i64
}
func.func @sieve(%arg0: i64, %arg1: !llvm.ptr) -> i64 {
%125 = arith.constant 1 : i32
%127 = arith.extsi %125 : i32 to i64
%126 = arith.addi %arg0, %127 : i64
%128 = arith.constant 1 : i32
%129 = arith.extsi %128 : i32 to i64
%124 = func.call @calloc(%126, %129) : (i64, i64) -> !llvm.ptr
%130 = arith.constant 0 : i32
%131 = arith.extsi %130 : i32 to i64
%132 = llvm.mlir.constant(1 : i64) : i64
%133 = llvm.alloca %132 x i64 : (i64) -> !llvm.ptr
llvm.store %131, %133 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%134 = llvm.load %133 : !llvm.ptr -> i64
%135 = arith.cmpi sle, %134, %arg0 : i64
cf.cond_br %135, ^bb31, ^bb32
^bb31:
%136 = arith.constant 1 : i32
%137 = llvm.load %133 : !llvm.ptr -> i64
%138 = arith.trunci %136 : i32 to i8
%139 = llvm.getelementptr %124[%137] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %138, %139 : i8, !llvm.ptr
%140 = llvm.load %133 : !llvm.ptr -> i64
%141 = arith.constant 1 : i32
%143 = arith.extsi %141 : i32 to i64
%142 = arith.addi %140, %143 : i64
llvm.store %142, %133 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%144 = arith.constant 0 : i32
%145 = arith.constant 0 : i32
%146 = arith.trunci %144 : i32 to i8
%147 = arith.extsi %145 : i32 to i64
%148 = llvm.getelementptr %124[%147] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %146, %148 : i8, !llvm.ptr
%149 = arith.constant 0 : i32
%150 = arith.constant 1 : i32
%151 = arith.trunci %149 : i32 to i8
%152 = arith.extsi %150 : i32 to i64
%153 = llvm.getelementptr %124[%152] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %151, %153 : i8, !llvm.ptr
%154 = arith.constant 2 : i32
%155 = arith.extsi %154 : i32 to i64
llvm.store %155, %133 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%156 = llvm.load %133 : !llvm.ptr -> i64
%157 = llvm.load %133 : !llvm.ptr -> i64
%158 = arith.muli %156, %157 : i64
%159 = arith.cmpi sle, %158, %arg0 : i64
cf.cond_br %159, ^bb34, ^bb35
^bb34:
%161 = llvm.load %133 : !llvm.ptr -> i64
%162 = llvm.getelementptr %124[%161] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%160 = llvm.load %162 : !llvm.ptr -> i8
%163 = arith.constant 0 : i32
%165 = arith.extsi %160 : i8 to i32
%164 = arith.cmpi ne, %165, %163 : i32
cf.cond_br %164, ^bb36, ^bb37
^bb36:
%166 = llvm.load %133 : !llvm.ptr -> i64
%167 = llvm.load %133 : !llvm.ptr -> i64
%168 = arith.muli %166, %167 : i64
%169 = llvm.mlir.constant(1 : i64) : i64
%170 = llvm.alloca %169 x i64 : (i64) -> !llvm.ptr
llvm.store %168, %170 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%171 = llvm.load %170 : !llvm.ptr -> i64
%172 = arith.cmpi sle, %171, %arg0 : i64
cf.cond_br %172, ^bb40, ^bb41
^bb40:
%173 = arith.constant 0 : i32
%174 = llvm.load %170 : !llvm.ptr -> i64
%175 = arith.trunci %173 : i32 to i8
%176 = llvm.getelementptr %124[%174] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %175, %176 : i8, !llvm.ptr
%177 = llvm.load %170 : !llvm.ptr -> i64
%178 = llvm.load %133 : !llvm.ptr -> i64
%179 = arith.addi %177, %178 : i64
llvm.store %179, %170 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%180 = llvm.load %133 : !llvm.ptr -> i64
%181 = arith.constant 1 : i32
%183 = arith.extsi %181 : i32 to i64
%182 = arith.addi %180, %183 : i64
llvm.store %182, %133 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
%184 = arith.constant 0 : i32
%185 = arith.extsi %184 : i32 to i64
%186 = llvm.mlir.constant(1 : i64) : i64
%187 = llvm.alloca %186 x i64 : (i64) -> !llvm.ptr
llvm.store %185, %187 : i64, !llvm.ptr
%188 = arith.constant 2 : i32
%189 = arith.extsi %188 : i32 to i64
llvm.store %189, %133 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%190 = llvm.load %133 : !llvm.ptr -> i64
%191 = arith.cmpi sle, %190, %arg0 : i64
cf.cond_br %191, ^bb43, ^bb44
^bb43:
%193 = llvm.load %133 : !llvm.ptr -> i64
%194 = llvm.getelementptr %124[%193] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%192 = llvm.load %194 : !llvm.ptr -> i8
%195 = arith.constant 0 : i32
%197 = arith.extsi %192 : i8 to i32
%196 = arith.cmpi ne, %197, %195 : i32
cf.cond_br %196, ^bb45, ^bb46
^bb45:
%198 = llvm.load %133 : !llvm.ptr -> i64
%199 = llvm.load %187 : !llvm.ptr -> i64
%200 = llvm.getelementptr %arg1[%199] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %198, %200 : i64, !llvm.ptr
%201 = llvm.load %187 : !llvm.ptr -> i64
%202 = arith.constant 1 : i32
%204 = arith.extsi %202 : i32 to i64
%203 = arith.addi %201, %204 : i64
llvm.store %203, %187 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%205 = llvm.load %133 : !llvm.ptr -> i64
%206 = arith.constant 1 : i32
%208 = arith.extsi %206 : i32 to i64
%207 = arith.addi %205, %208 : i64
llvm.store %207, %133 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
func.call @free(%124) : (!llvm.ptr) -> ()
%210 = llvm.load %187 : !llvm.ptr -> i64
func.return %210 : i64
}
func.func @bisect_right(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> i64 {
%211 = arith.constant 0 : i32
%212 = arith.extsi %211 : i32 to i64
%213 = llvm.mlir.constant(1 : i64) : i64
%214 = llvm.alloca %213 x i64 : (i64) -> !llvm.ptr
llvm.store %212, %214 : i64, !llvm.ptr
%215 = llvm.mlir.constant(1 : i64) : i64
%216 = llvm.alloca %215 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %216 : i64, !llvm.ptr
cf.br ^bb48
^bb48:
%217 = llvm.load %214 : !llvm.ptr -> i64
%218 = llvm.load %216 : !llvm.ptr -> i64
%219 = arith.cmpi slt, %217, %218 : i64
cf.cond_br %219, ^bb49, ^bb50
^bb49:
%220 = llvm.load %214 : !llvm.ptr -> i64
%221 = llvm.load %216 : !llvm.ptr -> i64
%222 = arith.addi %220, %221 : i64
%223 = arith.constant 2 : i32
%225 = arith.extsi %223 : i32 to i64
%224 = arith.divsi %222, %225 : i64
%227 = llvm.getelementptr %arg0[%224] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%226 = llvm.load %227 : !llvm.ptr -> i64
%228 = arith.cmpi sle, %226, %arg2 : i64
cf.cond_br %228, ^bb51, ^bb52
^bb51:
%229 = arith.constant 1 : i32
%231 = arith.extsi %229 : i32 to i64
%230 = arith.addi %224, %231 : i64
llvm.store %230, %214 : i64, !llvm.ptr
cf.br ^bb53
^bb52:
llvm.store %224, %216 : i64, !llvm.ptr
cf.br ^bb53
^bb53:
cf.br ^bb48
^bb50:
%232 = llvm.load %214 : !llvm.ptr -> i64
func.return %232 : i64
}
// Module static: SPLIT
llvm.mlir.global internal @SPLIT() {addr_space = 0 : i32} : !llvm.ptr {
%233 = llvm.mlir.zero : !llvm.ptr
llvm.return %233 : !llvm.ptr
}
// Module static: NSPLIT
llvm.mlir.global internal @NSPLIT(0 : i64) : i64
// Module static: Warr
llvm.mlir.global internal @Warr() {addr_space = 0 : i32} : !llvm.ptr {
%234 = llvm.mlir.zero : !llvm.ptr
llvm.return %234 : !llvm.ptr
}
// Module static: NLIMIT
llvm.mlir.global internal @NLIMIT(0 : i64) : i64
// Module static: INERT
llvm.mlir.global internal @INERT() {addr_space = 0 : i32} : !llvm.ptr {
%235 = llvm.mlir.zero : !llvm.ptr
llvm.return %235 : !llvm.ptr
}
// Module static: NINERT
llvm.mlir.global internal @NINERT(0 : i64) : i64
// Module static: VALS
llvm.mlir.global internal @VALS() {addr_space = 0 : i32} : !llvm.ptr {
%236 = llvm.mlir.zero : !llvm.ptr
llvm.return %236 : !llvm.ptr
}
// Module static: NVALS
llvm.mlir.global internal @NVALS(0 : i64) : i64
// Module static: VCAP
llvm.mlir.global internal @VCAP(0 : i64) : i64
func.func @add_val(%arg0: i64) -> () {
%237 = llvm.mlir.addressof @NVALS : !llvm.ptr
%238 = llvm.load %237 : !llvm.ptr -> i64
%239 = llvm.mlir.addressof @VCAP : !llvm.ptr
%240 = llvm.load %239 : !llvm.ptr -> i64
%241 = arith.cmpi sge, %238, %240 : i64
cf.cond_br %241, ^bb54, ^bb55
^bb54:
%242 = arith.constant 1024 : i32
%243 = arith.extsi %242 : i32 to i64
%244 = llvm.mlir.constant(1 : i64) : i64
%245 = llvm.alloca %244 x i64 : (i64) -> !llvm.ptr
llvm.store %243, %245 : i64, !llvm.ptr
%246 = llvm.mlir.addressof @VCAP : !llvm.ptr
%247 = llvm.load %246 : !llvm.ptr -> i64
%248 = arith.constant 0 : i32
%250 = arith.extsi %248 : i32 to i64
%249 = arith.cmpi sgt, %247, %250 : i64
cf.cond_br %249, ^bb57, ^bb58
^bb57:
%251 = llvm.mlir.addressof @VCAP : !llvm.ptr
%252 = llvm.load %251 : !llvm.ptr -> i64
%253 = arith.constant 2 : i32
%255 = arith.extsi %253 : i32 to i64
%254 = arith.muli %252, %255 : i64
llvm.store %254, %245 : i64, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%257 = llvm.mlir.addressof @VALS : !llvm.ptr
%258 = llvm.load %257 : !llvm.ptr -> !llvm.ptr
%259 = llvm.load %245 : !llvm.ptr -> i64
%260 = arith.constant 8 : i32
%262 = arith.extsi %260 : i32 to i64
%261 = arith.muli %259, %262 : i64
%256 = func.call @realloc(%258, %261) : (!llvm.ptr, i64) -> !llvm.ptr
%263 = llvm.mlir.addressof @VALS : !llvm.ptr
llvm.store %256, %263 : !llvm.ptr, !llvm.ptr
%264 = llvm.load %245 : !llvm.ptr -> i64
%265 = llvm.mlir.addressof @VCAP : !llvm.ptr
llvm.store %264, %265 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%266 = llvm.mlir.addressof @VALS : !llvm.ptr
%267 = llvm.load %266 : !llvm.ptr -> !llvm.ptr
%268 = llvm.mlir.addressof @NVALS : !llvm.ptr
%269 = llvm.load %268 : !llvm.ptr -> i64
%270 = llvm.getelementptr %267[%269] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %270 : i64, !llvm.ptr
%271 = llvm.mlir.addressof @NVALS : !llvm.ptr
%272 = llvm.load %271 : !llvm.ptr -> i64
%273 = arith.constant 1 : i32
%275 = arith.extsi %273 : i32 to i64
%274 = arith.addi %272, %275 : i64
%276 = llvm.mlir.addressof @NVALS : !llvm.ptr
llvm.store %274, %276 : i64, !llvm.ptr
func.return
}
func.func @mult_rec(%arg0: i64, %arg1: i64, %arg2: i64) -> () {
%277 = llvm.mlir.constant(1 : i64) : i64
%278 = llvm.alloca %277 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %278 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%279 = llvm.load %278 : !llvm.ptr -> i64
%280 = arith.cmpi sle, %279, %arg2 : i64
cf.cond_br %280, ^bb61, ^bb62
^bb61:
%282 = llvm.load %278 : !llvm.ptr -> i64
func.call @add_val(%282) : (i64) -> ()
%283 = llvm.load %278 : !llvm.ptr -> i64
%284 = arith.constant 5 : i32
%286 = arith.extsi %284 : i32 to i64
%285 = arith.divsi %arg2, %286 : i64
%287 = arith.cmpi sgt, %283, %285 : i64
cf.cond_br %287, ^bb63, ^bb64
^bb63:
cf.br ^bb62
^bb64:
cf.br ^bb65
^bb65:
%288 = llvm.load %278 : !llvm.ptr -> i64
%289 = arith.constant 5 : i32
%291 = arith.extsi %289 : i32 to i64
%290 = arith.muli %288, %291 : i64
llvm.store %290, %278 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
%292 = llvm.mlir.constant(1 : i64) : i64
%293 = llvm.alloca %292 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %293 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%294 = llvm.load %293 : !llvm.ptr -> i64
%295 = llvm.mlir.addressof @NINERT : !llvm.ptr
%296 = llvm.load %295 : !llvm.ptr -> i64
%297 = arith.cmpi slt, %294, %296 : i64
cf.cond_br %297, ^bb67, ^bb68
^bb67:
%299 = llvm.mlir.addressof @INERT : !llvm.ptr
%300 = llvm.load %299 : !llvm.ptr -> !llvm.ptr
%301 = llvm.load %293 : !llvm.ptr -> i64
%302 = llvm.getelementptr %300[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%298 = llvm.load %302 : !llvm.ptr -> i64
%303 = arith.muli %298, %298 : i64
%304 = arith.divsi %arg2, %303 : i64
%305 = arith.cmpi sgt, %arg1, %304 : i64
cf.cond_br %305, ^bb69, ^bb70
^bb69:
cf.br ^bb68
^bb70:
cf.br ^bb71
^bb71:
%306 = arith.muli %arg1, %303 : i64
%307 = llvm.mlir.constant(1 : i64) : i64
%308 = llvm.alloca %307 x i64 : (i64) -> !llvm.ptr
llvm.store %306, %308 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%309 = llvm.load %308 : !llvm.ptr -> i64
%310 = arith.cmpi sle, %309, %arg2 : i64
cf.cond_br %310, ^bb73, ^bb74
^bb73:
%312 = llvm.load %293 : !llvm.ptr -> i64
%313 = arith.constant 1 : i32
%315 = arith.extsi %313 : i32 to i64
%314 = arith.addi %312, %315 : i64
%316 = llvm.load %308 : !llvm.ptr -> i64
func.call @mult_rec(%314, %316, %arg2) : (i64, i64, i64) -> ()
%317 = llvm.load %308 : !llvm.ptr -> i64
%318 = arith.divsi %arg2, %303 : i64
%319 = arith.cmpi sgt, %317, %318 : i64
cf.cond_br %319, ^bb75, ^bb76
^bb75:
cf.br ^bb74
^bb76:
cf.br ^bb77
^bb77:
%320 = llvm.load %308 : !llvm.ptr -> i64
%321 = arith.muli %320, %303 : i64
llvm.store %321, %308 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
%322 = llvm.load %293 : !llvm.ptr -> i64
%323 = arith.constant 1 : i32
%325 = arith.extsi %323 : i32 to i64
%324 = arith.addi %322, %325 : i64
llvm.store %324, %293 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
func.return
}
func.func @build_W(%arg0: i64) -> () {
%326 = func.call @isqrt(%arg0) : (i64) -> i64
%327 = arith.constant 1 : i32
%329 = arith.extsi %327 : i32 to i64
%328 = arith.addi %326, %329 : i64
%331 = arith.constant 10 : i32
%333 = arith.extsi %331 : i32 to i64
%332 = arith.addi %328, %333 : i64
%334 = arith.constant 8 : i32
%335 = arith.extsi %334 : i32 to i64
%330 = func.call @calloc(%332, %335) : (i64, i64) -> !llvm.ptr
%336 = func.call @sieve(%328, %330) : (i64, !llvm.ptr) -> i64
%338 = arith.constant 8 : i32
%339 = arith.extsi %338 : i32 to i64
%337 = func.call @calloc(%336, %339) : (i64, i64) -> !llvm.ptr
%340 = llvm.mlir.addressof @INERT : !llvm.ptr
llvm.store %337, %340 : !llvm.ptr, !llvm.ptr
%341 = arith.constant 0 : i32
%342 = arith.extsi %341 : i32 to i64
%343 = llvm.mlir.addressof @NINERT : !llvm.ptr
llvm.store %342, %343 : i64, !llvm.ptr
%344 = arith.constant 0 : i32
%345 = arith.extsi %344 : i32 to i64
%346 = llvm.mlir.constant(1 : i64) : i64
%347 = llvm.alloca %346 x i64 : (i64) -> !llvm.ptr
llvm.store %345, %347 : i64, !llvm.ptr
cf.br ^bb78
^bb78:
%348 = llvm.load %347 : !llvm.ptr -> i64
%349 = arith.cmpi slt, %348, %336 : i64
cf.cond_br %349, ^bb79, ^bb80
^bb79:
%351 = llvm.load %347 : !llvm.ptr -> i64
%352 = llvm.getelementptr %330[%351] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%350 = llvm.load %352 : !llvm.ptr -> i64
%353 = arith.constant 5 : i32
%355 = arith.extsi %353 : i32 to i64
%354 = arith.remsi %350, %355 : i64
%356 = arith.constant 2 : i32
%358 = arith.extsi %356 : i32 to i64
%357 = arith.cmpi eq, %354, %358 : i64
%359 = scf.if %357 -> (i1) {
%360 = arith.constant true
scf.yield %360 : i1
} else {
%361 = arith.constant 3 : i32
%363 = arith.extsi %361 : i32 to i64
%362 = arith.cmpi eq, %354, %363 : i64
scf.yield %362 : i1
}
cf.cond_br %359, ^bb81, ^bb82
^bb81:
%364 = llvm.mlir.addressof @INERT : !llvm.ptr
%365 = llvm.load %364 : !llvm.ptr -> !llvm.ptr
%366 = llvm.mlir.addressof @NINERT : !llvm.ptr
%367 = llvm.load %366 : !llvm.ptr -> i64
%368 = llvm.getelementptr %365[%367] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %350, %368 : i64, !llvm.ptr
%369 = llvm.mlir.addressof @NINERT : !llvm.ptr
%370 = llvm.load %369 : !llvm.ptr -> i64
%371 = arith.constant 1 : i32
%373 = arith.extsi %371 : i32 to i64
%372 = arith.addi %370, %373 : i64
%374 = llvm.mlir.addressof @NINERT : !llvm.ptr
llvm.store %372, %374 : i64, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%375 = llvm.load %347 : !llvm.ptr -> i64
%376 = arith.constant 1 : i32
%378 = arith.extsi %376 : i32 to i64
%377 = arith.addi %375, %378 : i64
llvm.store %377, %347 : i64, !llvm.ptr
cf.br ^bb78
^bb80:
%379 = arith.constant 0 : i32
%380 = arith.extsi %379 : i32 to i64
%381 = llvm.mlir.addressof @NVALS : !llvm.ptr
llvm.store %380, %381 : i64, !llvm.ptr
%382 = arith.constant 0 : i32
%383 = arith.extsi %382 : i32 to i64
%384 = llvm.mlir.addressof @VCAP : !llvm.ptr
llvm.store %383, %384 : i64, !llvm.ptr
%385 = llvm.mlir.zero : !llvm.ptr
%386 = llvm.mlir.addressof @VALS : !llvm.ptr
llvm.store %385, %386 : !llvm.ptr, !llvm.ptr
%388 = arith.constant 0 : i32
%389 = arith.constant 1 : i32
%390 = arith.extsi %388 : i32 to i64
%391 = arith.extsi %389 : i32 to i64
func.call @mult_rec(%390, %391, %arg0) : (i64, i64, i64) -> ()
%392 = llvm.mlir.addressof @NVALS : !llvm.ptr
%393 = llvm.load %392 : !llvm.ptr -> i64
%394 = arith.constant 2 : i32
%396 = arith.extsi %394 : i32 to i64
%395 = arith.divsi %393, %396 : i64
%397 = llvm.mlir.constant(1 : i64) : i64
%398 = llvm.alloca %397 x i64 : (i64) -> !llvm.ptr
llvm.store %395, %398 : i64, !llvm.ptr
cf.br ^bb84
^bb84:
%399 = llvm.load %398 : !llvm.ptr -> i64
%400 = arith.constant 0 : i32
%402 = arith.extsi %400 : i32 to i64
%401 = arith.cmpi sgt, %399, %402 : i64
cf.cond_br %401, ^bb85, ^bb86
^bb85:
%403 = llvm.load %398 : !llvm.ptr -> i64
llvm.store %403, %347 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%404 = llvm.load %347 : !llvm.ptr -> i64
%405 = llvm.mlir.addressof @NVALS : !llvm.ptr
%406 = llvm.load %405 : !llvm.ptr -> i64
%407 = arith.cmpi slt, %404, %406 : i64
cf.cond_br %407, ^bb88, ^bb89
^bb88:
%409 = llvm.mlir.addressof @VALS : !llvm.ptr
%410 = llvm.load %409 : !llvm.ptr -> !llvm.ptr
%411 = llvm.load %347 : !llvm.ptr -> i64
%412 = llvm.getelementptr %410[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%408 = llvm.load %412 : !llvm.ptr -> i64
%413 = llvm.load %347 : !llvm.ptr -> i64
%414 = llvm.mlir.constant(1 : i64) : i64
%415 = llvm.alloca %414 x i64 : (i64) -> !llvm.ptr
llvm.store %413, %415 : i64, !llvm.ptr
cf.br ^bb90
^bb90:
%416 = llvm.load %415 : !llvm.ptr -> i64
%417 = llvm.load %398 : !llvm.ptr -> i64
%418 = arith.cmpi sge, %416, %417 : i64
%419 = scf.if %418 -> (i1) {
%421 = llvm.mlir.addressof @VALS : !llvm.ptr
%422 = llvm.load %421 : !llvm.ptr -> !llvm.ptr
%423 = llvm.load %415 : !llvm.ptr -> i64
%424 = llvm.load %398 : !llvm.ptr -> i64
%425 = arith.subi %423, %424 : i64
%426 = llvm.getelementptr %422[%425] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%420 = llvm.load %426 : !llvm.ptr -> i64
%427 = arith.cmpi sgt, %420, %408 : i64
scf.yield %427 : i1
} else {
%428 = arith.constant false
scf.yield %428 : i1
}
cf.cond_br %419, ^bb91, ^bb92
^bb91:
%430 = llvm.mlir.addressof @VALS : !llvm.ptr
%431 = llvm.load %430 : !llvm.ptr -> !llvm.ptr
%432 = llvm.load %415 : !llvm.ptr -> i64
%433 = llvm.load %398 : !llvm.ptr -> i64
%434 = arith.subi %432, %433 : i64
%435 = llvm.getelementptr %431[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%429 = llvm.load %435 : !llvm.ptr -> i64
%436 = llvm.mlir.addressof @VALS : !llvm.ptr
%437 = llvm.load %436 : !llvm.ptr -> !llvm.ptr
%438 = llvm.load %415 : !llvm.ptr -> i64
%439 = llvm.getelementptr %437[%438] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %429, %439 : i64, !llvm.ptr
%440 = llvm.load %415 : !llvm.ptr -> i64
%441 = llvm.load %398 : !llvm.ptr -> i64
%442 = arith.subi %440, %441 : i64
llvm.store %442, %415 : i64, !llvm.ptr
cf.br ^bb90
^bb92:
%443 = llvm.mlir.addressof @VALS : !llvm.ptr
%444 = llvm.load %443 : !llvm.ptr -> !llvm.ptr
%445 = llvm.load %415 : !llvm.ptr -> i64
%446 = llvm.getelementptr %444[%445] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %408, %446 : i64, !llvm.ptr
%447 = llvm.load %347 : !llvm.ptr -> i64
%448 = arith.constant 1 : i32
%450 = arith.extsi %448 : i32 to i64
%449 = arith.addi %447, %450 : i64
llvm.store %449, %347 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%451 = llvm.load %398 : !llvm.ptr -> i64
%452 = arith.constant 2 : i32
%454 = arith.extsi %452 : i32 to i64
%453 = arith.divsi %451, %454 : i64
llvm.store %453, %398 : i64, !llvm.ptr
cf.br ^bb84
^bb86:
%455 = arith.constant 0 : i32
%456 = arith.extsi %455 : i32 to i64
%457 = llvm.mlir.constant(1 : i64) : i64
%458 = llvm.alloca %457 x i64 : (i64) -> !llvm.ptr
llvm.store %456, %458 : i64, !llvm.ptr
%459 = arith.constant 0 : i32
%460 = arith.extsi %459 : i32 to i64
llvm.store %460, %347 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%461 = llvm.load %347 : !llvm.ptr -> i64
%462 = llvm.mlir.addressof @NVALS : !llvm.ptr
%463 = llvm.load %462 : !llvm.ptr -> i64
%464 = arith.cmpi slt, %461, %463 : i64
cf.cond_br %464, ^bb94, ^bb95
^bb94:
%465 = llvm.load %458 : !llvm.ptr -> i64
%466 = arith.constant 0 : i32
%468 = arith.extsi %466 : i32 to i64
%467 = arith.cmpi eq, %465, %468 : i64
%469 = scf.if %467 -> (i1) {
%470 = arith.constant true
scf.yield %470 : i1
} else {
%472 = llvm.mlir.addressof @VALS : !llvm.ptr
%473 = llvm.load %472 : !llvm.ptr -> !llvm.ptr
%474 = llvm.load %347 : !llvm.ptr -> i64
%475 = llvm.getelementptr %473[%474] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%471 = llvm.load %475 : !llvm.ptr -> i64
%477 = llvm.mlir.addressof @VALS : !llvm.ptr
%478 = llvm.load %477 : !llvm.ptr -> !llvm.ptr
%479 = llvm.load %458 : !llvm.ptr -> i64
%480 = arith.constant 1 : i32
%482 = arith.extsi %480 : i32 to i64
%481 = arith.subi %479, %482 : i64
%483 = llvm.getelementptr %478[%481] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%476 = llvm.load %483 : !llvm.ptr -> i64
%484 = arith.cmpi ne, %471, %476 : i64
scf.yield %484 : i1
}
cf.cond_br %469, ^bb96, ^bb97
^bb96:
%486 = llvm.mlir.addressof @VALS : !llvm.ptr
%487 = llvm.load %486 : !llvm.ptr -> !llvm.ptr
%488 = llvm.load %347 : !llvm.ptr -> i64
%489 = llvm.getelementptr %487[%488] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%485 = llvm.load %489 : !llvm.ptr -> i64
%490 = llvm.mlir.addressof @VALS : !llvm.ptr
%491 = llvm.load %490 : !llvm.ptr -> !llvm.ptr
%492 = llvm.load %458 : !llvm.ptr -> i64
%493 = llvm.getelementptr %491[%492] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %485, %493 : i64, !llvm.ptr
%494 = llvm.load %458 : !llvm.ptr -> i64
%495 = arith.constant 1 : i32
%497 = arith.extsi %495 : i32 to i64
%496 = arith.addi %494, %497 : i64
llvm.store %496, %458 : i64, !llvm.ptr
cf.br ^bb98
^bb97:
cf.br ^bb98
^bb98:
%498 = llvm.load %347 : !llvm.ptr -> i64
%499 = arith.constant 1 : i32
%501 = arith.extsi %499 : i32 to i64
%500 = arith.addi %498, %501 : i64
llvm.store %500, %347 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%502 = llvm.load %458 : !llvm.ptr -> i64
%503 = llvm.mlir.addressof @NVALS : !llvm.ptr
llvm.store %502, %503 : i64, !llvm.ptr
%505 = arith.constant 1 : i32
%507 = arith.extsi %505 : i32 to i64
%506 = arith.addi %arg0, %507 : i64
%508 = arith.constant 8 : i32
%509 = arith.extsi %508 : i32 to i64
%504 = func.call @calloc(%506, %509) : (i64, i64) -> !llvm.ptr
%510 = llvm.mlir.addressof @Warr : !llvm.ptr
llvm.store %504, %510 : !llvm.ptr, !llvm.ptr
%511 = arith.constant 0 : i32
%512 = arith.extsi %511 : i32 to 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 = arith.constant 0 : i32
%516 = arith.extsi %515 : i32 to i64
%517 = llvm.mlir.constant(1 : i64) : i64
%518 = llvm.alloca %517 x i64 : (i64) -> !llvm.ptr
llvm.store %516, %518 : i64, !llvm.ptr
%519 = arith.constant 1 : i32
%520 = arith.extsi %519 : i32 to i64
%521 = llvm.mlir.constant(1 : i64) : i64
%522 = llvm.alloca %521 x i64 : (i64) -> !llvm.ptr
llvm.store %520, %522 : i64, !llvm.ptr
cf.br ^bb99
^bb99:
%523 = llvm.load %522 : !llvm.ptr -> i64
%524 = arith.cmpi sle, %523, %arg0 : i64
cf.cond_br %524, ^bb100, ^bb101
^bb100:
cf.br ^bb102
^bb102:
%525 = llvm.load %518 : !llvm.ptr -> i64
%526 = llvm.mlir.addressof @NVALS : !llvm.ptr
%527 = llvm.load %526 : !llvm.ptr -> i64
%528 = arith.cmpi slt, %525, %527 : i64
%529 = scf.if %528 -> (i1) {
%531 = llvm.mlir.addressof @VALS : !llvm.ptr
%532 = llvm.load %531 : !llvm.ptr -> !llvm.ptr
%533 = llvm.load %518 : !llvm.ptr -> i64
%534 = llvm.getelementptr %532[%533] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%530 = llvm.load %534 : !llvm.ptr -> i64
%535 = llvm.load %522 : !llvm.ptr -> i64
%536 = arith.cmpi eq, %530, %535 : i64
scf.yield %536 : i1
} else {
%537 = arith.constant false
scf.yield %537 : i1
}
cf.cond_br %529, ^bb103, ^bb104
^bb103:
%538 = llvm.load %514 : !llvm.ptr -> i64
%539 = arith.constant 1 : i32
%541 = arith.extsi %539 : i32 to i64
%540 = arith.addi %538, %541 : i64
llvm.store %540, %514 : i64, !llvm.ptr
%542 = llvm.load %518 : !llvm.ptr -> i64
%543 = arith.constant 1 : i32
%545 = arith.extsi %543 : i32 to i64
%544 = arith.addi %542, %545 : i64
llvm.store %544, %518 : i64, !llvm.ptr
cf.br ^bb102
^bb104:
%546 = llvm.load %514 : !llvm.ptr -> i64
%547 = llvm.mlir.addressof @Warr : !llvm.ptr
%548 = llvm.load %547 : !llvm.ptr -> !llvm.ptr
%549 = llvm.load %522 : !llvm.ptr -> i64
%550 = llvm.getelementptr %548[%549] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %546, %550 : i64, !llvm.ptr
%551 = llvm.load %522 : !llvm.ptr -> i64
%552 = arith.constant 1 : i32
%554 = arith.extsi %552 : i32 to i64
%553 = arith.addi %551, %554 : i64
llvm.store %553, %522 : i64, !llvm.ptr
cf.br ^bb99
^bb101:
func.call @free(%330) : (!llvm.ptr) -> ()
%557 = llvm.mlir.addressof @INERT : !llvm.ptr
%558 = llvm.load %557 : !llvm.ptr -> !llvm.ptr
func.call @free(%558) : (!llvm.ptr) -> ()
%560 = llvm.mlir.addressof @VALS : !llvm.ptr
%561 = llvm.load %560 : !llvm.ptr -> !llvm.ptr
func.call @free(%561) : (!llvm.ptr) -> ()
func.return
}
func.func @sum_last(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%563 = llvm.mlir.addressof @NLIMIT : !llvm.ptr
%564 = llvm.load %563 : !llvm.ptr -> i64
%565 = arith.divsi %564, %arg0 : i64
%562 = func.call @iroot(%565, %arg2) : (i64, i64) -> i64
%567 = llvm.mlir.addressof @SPLIT : !llvm.ptr
%568 = llvm.load %567 : !llvm.ptr -> !llvm.ptr
%569 = llvm.mlir.addressof @NSPLIT : !llvm.ptr
%570 = llvm.load %569 : !llvm.ptr -> i64
%566 = func.call @bisect_right(%568, %570, %562) : (!llvm.ptr, i64, i64) -> i64
%571 = arith.cmpi sle, %566, %arg1 : i64
cf.cond_br %571, ^bb105, ^bb106
^bb105:
%572 = arith.constant 0 : i32
%573 = arith.extsi %572 : i32 to i64
func.return %573 : i64
^bb106:
cf.br ^bb107
^bb107:
%574 = arith.constant 0 : i32
%575 = arith.extsi %574 : i32 to i64
%576 = llvm.mlir.constant(1 : i64) : i64
%577 = llvm.alloca %576 x i64 : (i64) -> !llvm.ptr
llvm.store %575, %577 : i64, !llvm.ptr
%578 = llvm.mlir.constant(1 : i64) : i64
%579 = llvm.alloca %578 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %579 : i64, !llvm.ptr
cf.br ^bb108
^bb108:
%580 = llvm.load %579 : !llvm.ptr -> i64
%581 = arith.cmpi slt, %580, %566 : i64
cf.cond_br %581, ^bb109, ^bb110
^bb109:
%583 = llvm.mlir.addressof @SPLIT : !llvm.ptr
%584 = llvm.load %583 : !llvm.ptr -> !llvm.ptr
%585 = llvm.load %579 : !llvm.ptr -> i64
%586 = llvm.getelementptr %584[%585] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%582 = llvm.load %586 : !llvm.ptr -> i64
%587 = func.call @ipow(%582, %arg2) : (i64, i64) -> i64
%588 = llvm.mlir.addressof @NLIMIT : !llvm.ptr
%589 = llvm.load %588 : !llvm.ptr -> i64
%590 = arith.muli %arg0, %587 : i64
%591 = arith.divsi %589, %590 : i64
%593 = llvm.mlir.addressof @NLIMIT : !llvm.ptr
%594 = llvm.load %593 : !llvm.ptr -> i64
%595 = arith.muli %arg0, %591 : i64
%596 = arith.divsi %594, %595 : i64
%592 = func.call @iroot(%596, %arg2) : (i64, i64) -> i64
%597 = llvm.mlir.constant(1 : i64) : i64
%598 = llvm.alloca %597 x i64 : (i64) -> !llvm.ptr
llvm.store %592, %598 : i64, !llvm.ptr
%599 = llvm.load %598 : !llvm.ptr -> i64
%600 = arith.cmpi sgt, %599, %562 : i64
cf.cond_br %600, ^bb111, ^bb112
^bb111:
llvm.store %562, %598 : i64, !llvm.ptr
cf.br ^bb113
^bb112:
cf.br ^bb113
^bb113:
%602 = llvm.mlir.addressof @SPLIT : !llvm.ptr
%603 = llvm.load %602 : !llvm.ptr -> !llvm.ptr
%604 = llvm.mlir.addressof @NSPLIT : !llvm.ptr
%605 = llvm.load %604 : !llvm.ptr -> i64
%606 = llvm.load %598 : !llvm.ptr -> i64
%601 = func.call @bisect_right(%603, %605, %606) : (!llvm.ptr, i64, i64) -> i64
%607 = llvm.mlir.constant(1 : i64) : i64
%608 = llvm.alloca %607 x i64 : (i64) -> !llvm.ptr
llvm.store %601, %608 : i64, !llvm.ptr
%609 = llvm.load %608 : !llvm.ptr -> i64
%610 = arith.cmpi sgt, %609, %566 : i64
cf.cond_br %610, ^bb114, ^bb115
^bb114:
llvm.store %566, %608 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
%611 = llvm.load %577 : !llvm.ptr -> i64
%612 = llvm.load %608 : !llvm.ptr -> i64
%613 = llvm.load %579 : !llvm.ptr -> i64
%614 = arith.subi %612, %613 : i64
%616 = llvm.mlir.addressof @Warr : !llvm.ptr
%617 = llvm.load %616 : !llvm.ptr -> !llvm.ptr
%618 = llvm.getelementptr %617[%591] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%615 = llvm.load %618 : !llvm.ptr -> i64
%619 = arith.muli %614, %615 : i64
%620 = arith.addi %611, %619 : i64
llvm.store %620, %577 : i64, !llvm.ptr
%621 = llvm.load %608 : !llvm.ptr -> i64
llvm.store %621, %579 : i64, !llvm.ptr
cf.br ^bb108
^bb110:
%622 = llvm.load %577 : !llvm.ptr -> i64
func.return %622 : i64
}
// Module static: SEQ
llvm.mlir.global internal @SEQ() {addr_space = 0 : i32} : !llvm.ptr {
%623 = llvm.mlir.zero : !llvm.ptr
llvm.return %623 : !llvm.ptr
}
// Module static: SEQL
llvm.mlir.global internal @SEQL(0 : i64) : i64
// Module static: ACC
llvm.mlir.global internal @ACC(0 : i64) : i64
func.func @rec(%arg0: i64, %arg1: i64, %arg2: i64) -> () {
%624 = llvm.mlir.addressof @SEQL : !llvm.ptr
%625 = llvm.load %624 : !llvm.ptr -> i64
%626 = arith.constant 1 : i32
%628 = arith.extsi %626 : i32 to i64
%627 = arith.subi %625, %628 : i64
%629 = arith.cmpi eq, %arg0, %627 : i64
cf.cond_br %629, ^bb117, ^bb118
^bb117:
%630 = llvm.mlir.addressof @ACC : !llvm.ptr
%631 = llvm.load %630 : !llvm.ptr -> i64
%634 = llvm.mlir.addressof @SEQ : !llvm.ptr
%635 = llvm.load %634 : !llvm.ptr -> !llvm.ptr
%636 = llvm.getelementptr %635[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%633 = llvm.load %636 : !llvm.ptr -> i64
%632 = func.call @sum_last(%arg2, %arg1, %633) : (i64, i64, i64) -> i64
%637 = arith.addi %631, %632 : i64
%638 = llvm.mlir.addressof @ACC : !llvm.ptr
llvm.store %637, %638 : i64, !llvm.ptr
func.return
^bb118:
cf.br ^bb119
^bb119:
%640 = llvm.mlir.addressof @SEQ : !llvm.ptr
%641 = llvm.load %640 : !llvm.ptr -> !llvm.ptr
%642 = llvm.getelementptr %641[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%639 = llvm.load %642 : !llvm.ptr -> i64
%644 = llvm.mlir.addressof @NLIMIT : !llvm.ptr
%645 = llvm.load %644 : !llvm.ptr -> i64
%646 = arith.divsi %645, %arg2 : i64
%643 = func.call @iroot(%646, %639) : (i64, i64) -> i64
%647 = llvm.mlir.constant(1 : i64) : i64
%648 = llvm.alloca %647 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %648 : i64, !llvm.ptr
cf.br ^bb120
^bb120:
%649 = llvm.load %648 : !llvm.ptr -> i64
%650 = llvm.mlir.addressof @NSPLIT : !llvm.ptr
%651 = llvm.load %650 : !llvm.ptr -> i64
%652 = arith.cmpi slt, %649, %651 : i64
cf.cond_br %652, ^bb121, ^bb122
^bb121:
%653 = llvm.load %648 : !llvm.ptr -> i64
%654 = llvm.mlir.addressof @SEQL : !llvm.ptr
%655 = llvm.load %654 : !llvm.ptr -> i64
%656 = arith.constant 1 : i32
%658 = arith.extsi %656 : i32 to i64
%657 = arith.subi %655, %658 : i64
%659 = arith.subi %657, %arg0 : i64
%660 = arith.addi %653, %659 : i64
%661 = llvm.mlir.addressof @NSPLIT : !llvm.ptr
%662 = llvm.load %661 : !llvm.ptr -> i64
%663 = arith.cmpi sge, %660, %662 : i64
cf.cond_br %663, ^bb123, ^bb124
^bb123:
cf.br ^bb122
^bb124:
cf.br ^bb125
^bb125:
%665 = llvm.mlir.addressof @SPLIT : !llvm.ptr
%666 = llvm.load %665 : !llvm.ptr -> !llvm.ptr
%667 = llvm.load %648 : !llvm.ptr -> i64
%668 = llvm.getelementptr %666[%667] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%664 = llvm.load %668 : !llvm.ptr -> i64
%669 = arith.cmpi sgt, %664, %643 : i64
cf.cond_br %669, ^bb126, ^bb127
^bb126:
cf.br ^bb122
^bb127:
cf.br ^bb128
^bb128:
%670 = func.call @ipow(%664, %639) : (i64, i64) -> i64
%671 = llvm.mlir.addressof @NLIMIT : !llvm.ptr
%672 = llvm.load %671 : !llvm.ptr -> i64
%673 = arith.divsi %672, %670 : i64
%674 = arith.cmpi sgt, %arg2, %673 : i64
cf.cond_br %674, ^bb129, ^bb130
^bb129:
cf.br ^bb122
^bb130:
cf.br ^bb131
^bb131:
%675 = arith.muli %arg2, %670 : i64
%676 = llvm.mlir.addressof @NLIMIT : !llvm.ptr
%677 = llvm.load %676 : !llvm.ptr -> i64
%678 = arith.divsi %677, %675 : i64
%679 = arith.constant 1 : i32
%680 = arith.extsi %679 : i32 to i64
%681 = llvm.mlir.constant(1 : i64) : i64
%682 = llvm.alloca %681 x i64 : (i64) -> !llvm.ptr
llvm.store %680, %682 : i64, !llvm.ptr
%683 = arith.constant 1 : i32
%684 = arith.extsi %683 : i32 to i64
%685 = llvm.mlir.constant(1 : i64) : i64
%686 = llvm.alloca %685 x i64 : (i64) -> !llvm.ptr
llvm.store %684, %686 : i64, !llvm.ptr
%687 = arith.constant 1 : i32
%689 = arith.extsi %687 : i32 to i64
%688 = arith.addi %arg0, %689 : i64
%690 = llvm.mlir.constant(1 : i64) : i64
%691 = llvm.alloca %690 x i64 : (i64) -> !llvm.ptr
llvm.store %688, %691 : i64, !llvm.ptr
cf.br ^bb132
^bb132:
%692 = llvm.load %691 : !llvm.ptr -> i64
%693 = llvm.mlir.addressof @SEQL : !llvm.ptr
%694 = llvm.load %693 : !llvm.ptr -> i64
%695 = arith.cmpi slt, %692, %694 : i64
cf.cond_br %695, ^bb133, ^bb134
^bb133:
%697 = llvm.mlir.addressof @SPLIT : !llvm.ptr
%698 = llvm.load %697 : !llvm.ptr -> !llvm.ptr
%699 = llvm.load %648 : !llvm.ptr -> i64
%700 = llvm.load %691 : !llvm.ptr -> i64
%701 = arith.subi %700, %arg0 : i64
%702 = arith.addi %699, %701 : i64
%703 = llvm.getelementptr %698[%702] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%696 = llvm.load %703 : !llvm.ptr -> i64
%705 = llvm.mlir.addressof @SEQ : !llvm.ptr
%706 = llvm.load %705 : !llvm.ptr -> !llvm.ptr
%707 = llvm.load %691 : !llvm.ptr -> i64
%708 = llvm.getelementptr %706[%707] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%704 = llvm.load %708 : !llvm.ptr -> i64
%709 = func.call @ipow(%696, %704) : (i64, i64) -> i64
%710 = llvm.load %682 : !llvm.ptr -> i64
%711 = arith.divsi %678, %709 : i64
%712 = arith.cmpi sgt, %710, %711 : i64
cf.cond_br %712, ^bb135, ^bb136
^bb135:
%713 = arith.constant 0 : i32
%714 = arith.extsi %713 : i32 to i64
llvm.store %714, %686 : i64, !llvm.ptr
cf.br ^bb134
^bb136:
cf.br ^bb137
^bb137:
%715 = llvm.load %682 : !llvm.ptr -> i64
%716 = arith.muli %715, %709 : i64
llvm.store %716, %682 : i64, !llvm.ptr
%717 = llvm.load %691 : !llvm.ptr -> i64
%718 = arith.constant 1 : i32
%720 = arith.extsi %718 : i32 to i64
%719 = arith.addi %717, %720 : i64
llvm.store %719, %691 : i64, !llvm.ptr
cf.br ^bb132
^bb134:
%721 = llvm.load %686 : !llvm.ptr -> i64
%722 = arith.constant 0 : i32
%724 = arith.extsi %722 : i32 to i64
%723 = arith.cmpi eq, %721, %724 : i64
cf.cond_br %723, ^bb138, ^bb139
^bb138:
cf.br ^bb122
^bb139:
cf.br ^bb140
^bb140:
%726 = arith.constant 1 : i32
%728 = arith.extsi %726 : i32 to i64
%727 = arith.addi %arg0, %728 : i64
%729 = llvm.load %648 : !llvm.ptr -> i64
%730 = arith.constant 1 : i32
%732 = arith.extsi %730 : i32 to i64
%731 = arith.addi %729, %732 : i64
func.call @rec(%727, %731, %675) : (i64, i64, i64) -> ()
%733 = llvm.load %648 : !llvm.ptr -> i64
%734 = arith.constant 1 : i32
%736 = arith.extsi %734 : i32 to i64
%735 = arith.addi %733, %736 : i64
llvm.store %735, %648 : i64, !llvm.ptr
cf.br ^bb120
^bb122:
func.return
}
// Module static: FS
llvm.mlir.global internal @FS() {addr_space = 0 : i32} : !llvm.ptr {
%737 = llvm.mlir.zero : !llvm.ptr
llvm.return %737 : !llvm.ptr
}
// Module static: NFS
llvm.mlir.global internal @NFS(0 : i64) : i64
// Module static: ALLSEQ
llvm.mlir.global internal @ALLSEQ() {addr_space = 0 : i32} : !llvm.ptr {
%738 = llvm.mlir.zero : !llvm.ptr
llvm.return %738 : !llvm.ptr
}
// Module static: ALLLEN
llvm.mlir.global internal @ALLLEN() {addr_space = 0 : i32} : !llvm.ptr {
%739 = llvm.mlir.zero : !llvm.ptr
llvm.return %739 : !llvm.ptr
}
// Module static: NALL
llvm.mlir.global internal @NALL(0 : i64) : i64
// Module static: ACAP
llvm.mlir.global internal @ACAP(0 : i64) : i64
func.func @save_seq(%arg0: !llvm.ptr, %arg1: i64) -> () {
%740 = arith.constant 1 : i32
%741 = arith.extsi %740 : i32 to i64
%742 = llvm.mlir.constant(1 : i64) : i64
%743 = llvm.alloca %742 x i64 : (i64) -> !llvm.ptr
llvm.store %741, %743 : i64, !llvm.ptr
%744 = arith.constant 0 : i32
%745 = arith.extsi %744 : i32 to i64
%746 = llvm.mlir.constant(1 : i64) : i64
%747 = llvm.alloca %746 x i64 : (i64) -> !llvm.ptr
llvm.store %745, %747 : i64, !llvm.ptr
cf.br ^bb141
^bb141:
%748 = llvm.load %747 : !llvm.ptr -> i64
%749 = arith.cmpi slt, %748, %arg1 : i64
cf.cond_br %749, ^bb142, ^bb143
^bb142:
%750 = arith.constant 0 : i32
%751 = arith.extsi %750 : i32 to i64
%752 = llvm.mlir.constant(1 : i64) : i64
%753 = llvm.alloca %752 x i64 : (i64) -> !llvm.ptr
llvm.store %751, %753 : i64, !llvm.ptr
cf.br ^bb144
^bb144:
%754 = llvm.load %753 : !llvm.ptr -> i64
%756 = llvm.load %747 : !llvm.ptr -> i64
%757 = llvm.getelementptr %arg0[%756] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%755 = llvm.load %757 : !llvm.ptr -> i64
%758 = arith.cmpi slt, %754, %755 : i64
cf.cond_br %758, ^bb145, ^bb146
^bb145:
%759 = llvm.load %743 : !llvm.ptr -> i64
%760 = llvm.mlir.addressof @NLIMIT : !llvm.ptr
%761 = llvm.load %760 : !llvm.ptr -> i64
%763 = llvm.mlir.addressof @FS : !llvm.ptr
%764 = llvm.load %763 : !llvm.ptr -> !llvm.ptr
%765 = llvm.load %747 : !llvm.ptr -> i64
%766 = llvm.getelementptr %764[%765] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%762 = llvm.load %766 : !llvm.ptr -> i64
%767 = arith.divsi %761, %762 : i64
%768 = arith.cmpi sgt, %759, %767 : i64
cf.cond_br %768, ^bb147, ^bb148
^bb147:
func.return
^bb148:
cf.br ^bb149
^bb149:
%769 = llvm.load %743 : !llvm.ptr -> i64
%771 = llvm.mlir.addressof @FS : !llvm.ptr
%772 = llvm.load %771 : !llvm.ptr -> !llvm.ptr
%773 = llvm.load %747 : !llvm.ptr -> i64
%774 = llvm.getelementptr %772[%773] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%770 = llvm.load %774 : !llvm.ptr -> i64
%775 = arith.muli %769, %770 : i64
llvm.store %775, %743 : i64, !llvm.ptr
%776 = llvm.load %753 : !llvm.ptr -> i64
%777 = arith.constant 1 : i32
%779 = arith.extsi %777 : i32 to i64
%778 = arith.addi %776, %779 : i64
llvm.store %778, %753 : i64, !llvm.ptr
cf.br ^bb144
^bb146:
%780 = llvm.load %747 : !llvm.ptr -> i64
%781 = arith.constant 1 : i32
%783 = arith.extsi %781 : i32 to i64
%782 = arith.addi %780, %783 : i64
llvm.store %782, %747 : i64, !llvm.ptr
cf.br ^bb141
^bb143:
%784 = llvm.mlir.addressof @NALL : !llvm.ptr
%785 = llvm.load %784 : !llvm.ptr -> i64
%786 = llvm.mlir.addressof @ACAP : !llvm.ptr
%787 = llvm.load %786 : !llvm.ptr -> i64
%788 = arith.cmpi sge, %785, %787 : i64
cf.cond_br %788, ^bb150, ^bb151
^bb150:
%789 = arith.constant 64 : i32
%790 = arith.extsi %789 : i32 to i64
%791 = llvm.mlir.constant(1 : i64) : i64
%792 = llvm.alloca %791 x i64 : (i64) -> !llvm.ptr
llvm.store %790, %792 : i64, !llvm.ptr
%793 = llvm.mlir.addressof @ACAP : !llvm.ptr
%794 = llvm.load %793 : !llvm.ptr -> i64
%795 = arith.constant 0 : i32
%797 = arith.extsi %795 : i32 to i64
%796 = arith.cmpi sgt, %794, %797 : i64
cf.cond_br %796, ^bb153, ^bb154
^bb153:
%798 = llvm.mlir.addressof @ACAP : !llvm.ptr
%799 = llvm.load %798 : !llvm.ptr -> i64
%800 = arith.constant 2 : i32
%802 = arith.extsi %800 : i32 to i64
%801 = arith.muli %799, %802 : i64
llvm.store %801, %792 : i64, !llvm.ptr
cf.br ^bb155
^bb154:
cf.br ^bb155
^bb155:
%804 = llvm.mlir.addressof @ALLSEQ : !llvm.ptr
%805 = llvm.load %804 : !llvm.ptr -> !llvm.ptr
%806 = llvm.load %792 : !llvm.ptr -> i64
%807 = arith.constant 16 : i32
%809 = arith.extsi %807 : i32 to i64
%808 = arith.muli %806, %809 : i64
%810 = arith.constant 8 : i32
%812 = arith.extsi %810 : i32 to i64
%811 = arith.muli %808, %812 : i64
%803 = func.call @realloc(%805, %811) : (!llvm.ptr, i64) -> !llvm.ptr
%813 = llvm.mlir.addressof @ALLSEQ : !llvm.ptr
llvm.store %803, %813 : !llvm.ptr, !llvm.ptr
%815 = llvm.mlir.addressof @ALLLEN : !llvm.ptr
%816 = llvm.load %815 : !llvm.ptr -> !llvm.ptr
%817 = llvm.load %792 : !llvm.ptr -> i64
%818 = arith.constant 8 : i32
%820 = arith.extsi %818 : i32 to i64
%819 = arith.muli %817, %820 : i64
%814 = func.call @realloc(%816, %819) : (!llvm.ptr, i64) -> !llvm.ptr
%821 = llvm.mlir.addressof @ALLLEN : !llvm.ptr
llvm.store %814, %821 : !llvm.ptr, !llvm.ptr
%822 = llvm.load %792 : !llvm.ptr -> i64
%823 = llvm.mlir.addressof @ACAP : !llvm.ptr
llvm.store %822, %823 : i64, !llvm.ptr
cf.br ^bb152
^bb151:
cf.br ^bb152
^bb152:
%824 = arith.constant 0 : i32
%825 = arith.extsi %824 : i32 to i64
llvm.store %825, %747 : i64, !llvm.ptr
cf.br ^bb156
^bb156:
%826 = llvm.load %747 : !llvm.ptr -> i64
%827 = arith.cmpi slt, %826, %arg1 : i64
cf.cond_br %827, ^bb157, ^bb158
^bb157:
%829 = llvm.load %747 : !llvm.ptr -> i64
%830 = llvm.getelementptr %arg0[%829] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%828 = llvm.load %830 : !llvm.ptr -> i64
%831 = llvm.mlir.addressof @ALLSEQ : !llvm.ptr
%832 = llvm.load %831 : !llvm.ptr -> !llvm.ptr
%833 = llvm.mlir.addressof @NALL : !llvm.ptr
%834 = llvm.load %833 : !llvm.ptr -> i64
%835 = arith.constant 16 : i32
%837 = arith.extsi %835 : i32 to i64
%836 = arith.muli %834, %837 : i64
%838 = llvm.load %747 : !llvm.ptr -> i64
%839 = arith.addi %836, %838 : i64
%840 = llvm.getelementptr %832[%839] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %828, %840 : i64, !llvm.ptr
%841 = llvm.load %747 : !llvm.ptr -> i64
%842 = arith.constant 1 : i32
%844 = arith.extsi %842 : i32 to i64
%843 = arith.addi %841, %844 : i64
llvm.store %843, %747 : i64, !llvm.ptr
cf.br ^bb156
^bb158:
%845 = llvm.mlir.addressof @ALLLEN : !llvm.ptr
%846 = llvm.load %845 : !llvm.ptr -> !llvm.ptr
%847 = llvm.mlir.addressof @NALL : !llvm.ptr
%848 = llvm.load %847 : !llvm.ptr -> i64
%849 = llvm.getelementptr %846[%848] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %849 : i64, !llvm.ptr
%850 = llvm.mlir.addressof @NALL : !llvm.ptr
%851 = llvm.load %850 : !llvm.ptr -> i64
%852 = arith.constant 1 : i32
%854 = arith.extsi %852 : i32 to i64
%853 = arith.addi %851, %854 : i64
%855 = llvm.mlir.addressof @NALL : !llvm.ptr
llvm.store %853, %855 : i64, !llvm.ptr
func.return
}
func.func @perm_rec(%arg0: i64, %arg1: !llvm.ptr, %arg2: i64, %arg3: !llvm.ptr, %arg4: !llvm.ptr) -> () {
%856 = arith.cmpi eq, %arg0, %arg2 : i64
cf.cond_br %856, ^bb159, ^bb160
^bb159:
func.call @save_seq(%arg4, %arg2) : (!llvm.ptr, i64) -> ()
func.return
^bb160:
cf.br ^bb161
^bb161:
%858 = arith.constant 999 : i32
%860 = arith.constant 0 : i32
%859 = arith.subi %860, %858 : i32
%861 = arith.extsi %859 : i32 to i64
%862 = llvm.mlir.constant(1 : i64) : i64
%863 = llvm.alloca %862 x i64 : (i64) -> !llvm.ptr
llvm.store %861, %863 : i64, !llvm.ptr
%864 = arith.constant 0 : i32
%865 = arith.extsi %864 : i32 to i64
%866 = llvm.mlir.constant(1 : i64) : i64
%867 = llvm.alloca %866 x i64 : (i64) -> !llvm.ptr
llvm.store %865, %867 : i64, !llvm.ptr
cf.br ^bb162
^bb162:
%868 = llvm.load %867 : !llvm.ptr -> i64
%869 = arith.cmpi slt, %868, %arg2 : i64
cf.cond_br %869, ^bb163, ^bb164
^bb163:
%871 = llvm.load %867 : !llvm.ptr -> i64
%872 = llvm.getelementptr %arg3[%871] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%870 = llvm.load %872 : !llvm.ptr -> i8
%873 = arith.constant 0 : i32
%875 = arith.extsi %870 : i8 to i32
%874 = arith.cmpi eq, %875, %873 : i32
%876 = scf.if %874 -> (i1) {
%878 = llvm.load %867 : !llvm.ptr -> i64
%879 = llvm.getelementptr %arg1[%878] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%877 = llvm.load %879 : !llvm.ptr -> i64
%880 = llvm.load %863 : !llvm.ptr -> i64
%881 = arith.cmpi ne, %877, %880 : i64
scf.yield %881 : i1
} else {
%882 = arith.constant false
scf.yield %882 : i1
}
cf.cond_br %876, ^bb165, ^bb166
^bb165:
%883 = arith.constant 1 : i32
%884 = llvm.load %867 : !llvm.ptr -> i64
%885 = arith.trunci %883 : i32 to i8
%886 = llvm.getelementptr %arg3[%884] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %885, %886 : i8, !llvm.ptr
%888 = llvm.load %867 : !llvm.ptr -> i64
%889 = llvm.getelementptr %arg1[%888] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%887 = llvm.load %889 : !llvm.ptr -> i64
%890 = llvm.getelementptr %arg4[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %887, %890 : i64, !llvm.ptr
%892 = arith.constant 1 : i32
%894 = arith.extsi %892 : i32 to i64
%893 = arith.addi %arg0, %894 : i64
func.call @perm_rec(%893, %arg1, %arg2, %arg3, %arg4) : (i64, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr) -> ()
%895 = arith.constant 0 : i32
%896 = llvm.load %867 : !llvm.ptr -> i64
%897 = arith.trunci %895 : i32 to i8
%898 = llvm.getelementptr %arg3[%896] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %897, %898 : i8, !llvm.ptr
%900 = llvm.load %867 : !llvm.ptr -> i64
%901 = llvm.getelementptr %arg1[%900] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%899 = llvm.load %901 : !llvm.ptr -> i64
llvm.store %899, %863 : i64, !llvm.ptr
cf.br ^bb167
^bb166:
cf.br ^bb167
^bb167:
%902 = llvm.load %867 : !llvm.ptr -> i64
%903 = arith.constant 1 : i32
%905 = arith.extsi %903 : i32 to i64
%904 = arith.addi %902, %905 : i64
llvm.store %904, %867 : i64, !llvm.ptr
cf.br ^bb162
^bb164:
func.return
}
func.func @fac_rec(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: i64) -> () {
%906 = arith.constant 1 : i32
%908 = arith.extsi %906 : i32 to i64
%907 = arith.cmpi eq, %arg0, %908 : i64
cf.cond_br %907, ^bb168, ^bb169
^bb168:
%910 = arith.constant 8 : i32
%911 = arith.extsi %910 : i32 to i64
%909 = func.call @calloc(%arg3, %911) : (i64, i64) -> !llvm.ptr
%912 = arith.constant 0 : i32
%913 = arith.extsi %912 : i32 to i64
%914 = llvm.mlir.constant(1 : i64) : i64
%915 = llvm.alloca %914 x i64 : (i64) -> !llvm.ptr
llvm.store %913, %915 : i64, !llvm.ptr
cf.br ^bb171
^bb171:
%916 = llvm.load %915 : !llvm.ptr -> i64
%917 = arith.cmpi slt, %916, %arg3 : i64
cf.cond_br %917, ^bb172, ^bb173
^bb172:
%919 = llvm.load %915 : !llvm.ptr -> i64
%920 = llvm.getelementptr %arg2[%919] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%918 = llvm.load %920 : !llvm.ptr -> i64
%921 = arith.constant 1 : i32
%923 = arith.extsi %921 : i32 to i64
%922 = arith.subi %918, %923 : i64
%924 = llvm.load %915 : !llvm.ptr -> i64
%925 = llvm.getelementptr %909[%924] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %922, %925 : i64, !llvm.ptr
%926 = llvm.load %915 : !llvm.ptr -> i64
%927 = arith.constant 1 : i32
%929 = arith.extsi %927 : i32 to i64
%928 = arith.addi %926, %929 : i64
llvm.store %928, %915 : i64, !llvm.ptr
cf.br ^bb171
^bb173:
%931 = arith.constant 1 : i32
%932 = arith.extsi %931 : i32 to i64
%930 = func.call @calloc(%arg3, %932) : (i64, i64) -> !llvm.ptr
%934 = arith.constant 8 : i32
%935 = arith.extsi %934 : i32 to i64
%933 = func.call @calloc(%arg3, %935) : (i64, i64) -> !llvm.ptr
%937 = arith.constant 0 : i32
%938 = arith.extsi %937 : i32 to i64
func.call @perm_rec(%938, %909, %arg3, %930, %933) : (i64, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr) -> ()
func.call @free(%909) : (!llvm.ptr) -> ()
func.call @free(%930) : (!llvm.ptr) -> ()
func.call @free(%933) : (!llvm.ptr) -> ()
func.return
^bb169:
cf.br ^bb170
^bb170:
%942 = llvm.mlir.constant(1 : i64) : i64
%943 = llvm.alloca %942 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %943 : i64, !llvm.ptr
cf.br ^bb174
^bb174:
%944 = llvm.load %943 : !llvm.ptr -> i64
%945 = arith.cmpi sle, %944, %arg0 : i64
cf.cond_br %945, ^bb175, ^bb176
^bb175:
%946 = llvm.load %943 : !llvm.ptr -> i64
%947 = arith.remsi %arg0, %946 : i64
%948 = arith.constant 0 : i32
%950 = arith.extsi %948 : i32 to i64
%949 = arith.cmpi eq, %947, %950 : i64
cf.cond_br %949, ^bb177, ^bb178
^bb177:
%951 = llvm.load %943 : !llvm.ptr -> i64
%952 = llvm.getelementptr %arg2[%arg3] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %951, %952 : i64, !llvm.ptr
%954 = llvm.load %943 : !llvm.ptr -> i64
%955 = arith.divsi %arg0, %954 : i64
%956 = llvm.load %943 : !llvm.ptr -> i64
%957 = arith.constant 1 : i32
%959 = arith.extsi %957 : i32 to i64
%958 = arith.addi %arg3, %959 : i64
func.call @fac_rec(%955, %956, %arg2, %958) : (i64, i64, !llvm.ptr, i64) -> ()
cf.br ^bb179
^bb178:
cf.br ^bb179
^bb179:
%960 = llvm.load %943 : !llvm.ptr -> i64
%961 = arith.constant 1 : i32
%963 = arith.extsi %961 : i32 to i64
%962 = arith.addi %960, %963 : i64
llvm.store %962, %943 : i64, !llvm.ptr
cf.br ^bb174
^bb176:
func.return
}
func.func @compute_f(%arg0: i64, %arg1: i64) -> i64 {
%964 = llvm.mlir.addressof @NLIMIT : !llvm.ptr
llvm.store %arg0, %964 : i64, !llvm.ptr
%966 = arith.constant 4000 : i32
%967 = arith.constant 8 : i32
%968 = arith.extsi %966 : i32 to i64
%969 = arith.extsi %967 : i32 to i64
%965 = func.call @calloc(%968, %969) : (i64, i64) -> !llvm.ptr
%971 = arith.constant 20000 : i32
%972 = arith.extsi %971 : i32 to i64
%970 = func.call @sieve(%972, %965) : (i64, !llvm.ptr) -> i64
%974 = arith.constant 8 : i32
%975 = arith.extsi %974 : i32 to i64
%973 = func.call @calloc(%970, %975) : (i64, i64) -> !llvm.ptr
%976 = llvm.mlir.addressof @FS : !llvm.ptr
llvm.store %973, %976 : !llvm.ptr, !llvm.ptr
%977 = arith.constant 0 : i32
%978 = arith.extsi %977 : i32 to i64
%979 = llvm.mlir.addressof @NFS : !llvm.ptr
llvm.store %978, %979 : i64, !llvm.ptr
%980 = arith.constant 0 : i32
%981 = arith.extsi %980 : i32 to i64
%982 = llvm.mlir.constant(1 : i64) : i64
%983 = llvm.alloca %982 x i64 : (i64) -> !llvm.ptr
llvm.store %981, %983 : i64, !llvm.ptr
cf.br ^bb180
^bb180:
%984 = llvm.load %983 : !llvm.ptr -> i64
%985 = arith.cmpi slt, %984, %970 : i64
cf.cond_br %985, ^bb181, ^bb182
^bb181:
%987 = llvm.load %983 : !llvm.ptr -> i64
%988 = llvm.getelementptr %965[%987] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%986 = llvm.load %988 : !llvm.ptr -> i64
%989 = arith.constant 5 : i32
%991 = arith.extsi %989 : i32 to i64
%990 = arith.remsi %986, %991 : i64
%992 = arith.constant 1 : i32
%994 = arith.extsi %992 : i32 to i64
%993 = arith.cmpi eq, %990, %994 : i64
%995 = scf.if %993 -> (i1) {
%996 = arith.constant true
scf.yield %996 : i1
} else {
%997 = arith.constant 4 : i32
%999 = arith.extsi %997 : i32 to i64
%998 = arith.cmpi eq, %990, %999 : i64
scf.yield %998 : i1
}
cf.cond_br %995, ^bb183, ^bb184
^bb183:
%1000 = llvm.mlir.addressof @FS : !llvm.ptr
%1001 = llvm.load %1000 : !llvm.ptr -> !llvm.ptr
%1002 = llvm.mlir.addressof @NFS : !llvm.ptr
%1003 = llvm.load %1002 : !llvm.ptr -> i64
%1004 = llvm.getelementptr %1001[%1003] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %986, %1004 : i64, !llvm.ptr
%1005 = llvm.mlir.addressof @NFS : !llvm.ptr
%1006 = llvm.load %1005 : !llvm.ptr -> i64
%1007 = arith.constant 1 : i32
%1009 = arith.extsi %1007 : i32 to i64
%1008 = arith.addi %1006, %1009 : i64
%1010 = llvm.mlir.addressof @NFS : !llvm.ptr
llvm.store %1008, %1010 : i64, !llvm.ptr
cf.br ^bb185
^bb184:
cf.br ^bb185
^bb185:
%1011 = llvm.load %983 : !llvm.ptr -> i64
%1012 = arith.constant 1 : i32
%1014 = arith.extsi %1012 : i32 to i64
%1013 = arith.addi %1011, %1014 : i64
llvm.store %1013, %983 : i64, !llvm.ptr
cf.br ^bb180
^bb182:
%1015 = arith.constant 0 : i32
%1016 = arith.extsi %1015 : i32 to i64
%1017 = llvm.mlir.addressof @NALL : !llvm.ptr
llvm.store %1016, %1017 : i64, !llvm.ptr
%1018 = arith.constant 0 : i32
%1019 = arith.extsi %1018 : i32 to i64
%1020 = llvm.mlir.addressof @ACAP : !llvm.ptr
llvm.store %1019, %1020 : i64, !llvm.ptr
%1021 = llvm.mlir.zero : !llvm.ptr
%1022 = llvm.mlir.addressof @ALLSEQ : !llvm.ptr
llvm.store %1021, %1022 : !llvm.ptr, !llvm.ptr
%1023 = llvm.mlir.zero : !llvm.ptr
%1024 = llvm.mlir.addressof @ALLLEN : !llvm.ptr
llvm.store %1023, %1024 : !llvm.ptr, !llvm.ptr
%1026 = arith.constant 64 : i32
%1027 = arith.constant 8 : i32
%1028 = arith.extsi %1026 : i32 to i64
%1029 = arith.extsi %1027 : i32 to i64
%1025 = func.call @calloc(%1028, %1029) : (i64, i64) -> !llvm.ptr
%1031 = arith.constant 2 : i32
%1033 = arith.extsi %1031 : i32 to i64
%1032 = arith.muli %1033, %arg1 : i64
%1034 = arith.constant 2 : i32
%1035 = arith.constant 0 : i32
%1036 = arith.extsi %1034 : i32 to i64
%1037 = arith.extsi %1035 : i32 to i64
func.call @fac_rec(%1032, %1036, %1025, %1037) : (i64, i64, !llvm.ptr, i64) -> ()
%1039 = arith.constant 2 : i32
%1041 = arith.extsi %1039 : i32 to i64
%1040 = arith.muli %1041, %arg1 : i64
%1042 = arith.constant 1 : i32
%1044 = arith.extsi %1042 : i32 to i64
%1043 = arith.addi %1040, %1044 : i64
%1045 = arith.constant 2 : i32
%1046 = arith.constant 0 : i32
%1047 = arith.extsi %1045 : i32 to i64
%1048 = arith.extsi %1046 : i32 to i64
func.call @fac_rec(%1043, %1047, %1025, %1048) : (i64, i64, !llvm.ptr, i64) -> ()
func.call @free(%1025) : (!llvm.ptr) -> ()
%1050 = llvm.mlir.addressof @NALL : !llvm.ptr
%1051 = llvm.load %1050 : !llvm.ptr -> i64
%1052 = arith.constant 0 : i32
%1054 = arith.extsi %1052 : i32 to i64
%1053 = arith.cmpi eq, %1051, %1054 : i64
cf.cond_br %1053, ^bb186, ^bb187
^bb186:
%1055 = arith.constant 0 : i32
%1056 = arith.extsi %1055 : i32 to i64
func.return %1056 : i64
^bb187:
cf.br ^bb188
^bb188:
%1057 = arith.constant 0 : i32
%1058 = arith.extsi %1057 : i32 to i64
%1059 = llvm.mlir.constant(1 : i64) : i64
%1060 = llvm.alloca %1059 x i64 : (i64) -> !llvm.ptr
llvm.store %1058, %1060 : i64, !llvm.ptr
%1061 = arith.constant 0 : i32
%1062 = arith.extsi %1061 : i32 to i64
llvm.store %1062, %983 : i64, !llvm.ptr
cf.br ^bb189
^bb189:
%1063 = llvm.load %983 : !llvm.ptr -> i64
%1064 = llvm.mlir.addressof @NALL : !llvm.ptr
%1065 = llvm.load %1064 : !llvm.ptr -> i64
%1066 = arith.cmpi slt, %1063, %1065 : i64
cf.cond_br %1066, ^bb190, ^bb191
^bb190:
%1068 = llvm.mlir.addressof @ALLLEN : !llvm.ptr
%1069 = llvm.load %1068 : !llvm.ptr -> !llvm.ptr
%1070 = llvm.load %983 : !llvm.ptr -> i64
%1071 = llvm.getelementptr %1069[%1070] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1067 = llvm.load %1071 : !llvm.ptr -> i64
%1072 = arith.constant 1 : i32
%1073 = arith.extsi %1072 : i32 to i64
%1074 = llvm.mlir.constant(1 : i64) : i64
%1075 = llvm.alloca %1074 x i64 : (i64) -> !llvm.ptr
llvm.store %1073, %1075 : i64, !llvm.ptr
%1076 = arith.constant 0 : i32
%1077 = arith.extsi %1076 : i32 to i64
%1078 = llvm.mlir.constant(1 : i64) : i64
%1079 = llvm.alloca %1078 x i64 : (i64) -> !llvm.ptr
llvm.store %1077, %1079 : i64, !llvm.ptr
cf.br ^bb192
^bb192:
%1080 = llvm.load %1079 : !llvm.ptr -> i64
%1081 = arith.cmpi slt, %1080, %1067 : i64
cf.cond_br %1081, ^bb193, ^bb194
^bb193:
%1082 = llvm.load %1075 : !llvm.ptr -> i64
%1085 = llvm.mlir.addressof @FS : !llvm.ptr
%1086 = llvm.load %1085 : !llvm.ptr -> !llvm.ptr
%1087 = llvm.load %1079 : !llvm.ptr -> i64
%1088 = llvm.getelementptr %1086[%1087] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1084 = llvm.load %1088 : !llvm.ptr -> i64
%1090 = llvm.mlir.addressof @ALLSEQ : !llvm.ptr
%1091 = llvm.load %1090 : !llvm.ptr -> !llvm.ptr
%1092 = llvm.load %983 : !llvm.ptr -> i64
%1093 = arith.constant 16 : i32
%1095 = arith.extsi %1093 : i32 to i64
%1094 = arith.muli %1092, %1095 : i64
%1096 = llvm.load %1079 : !llvm.ptr -> i64
%1097 = arith.addi %1094, %1096 : i64
%1098 = llvm.getelementptr %1091[%1097] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1089 = llvm.load %1098 : !llvm.ptr -> i64
%1083 = func.call @ipow(%1084, %1089) : (i64, i64) -> i64
%1099 = arith.muli %1082, %1083 : i64
llvm.store %1099, %1075 : i64, !llvm.ptr
%1100 = llvm.load %1079 : !llvm.ptr -> i64
%1101 = arith.constant 1 : i32
%1103 = arith.extsi %1101 : i32 to i64
%1102 = arith.addi %1100, %1103 : i64
llvm.store %1102, %1079 : i64, !llvm.ptr
cf.br ^bb192
^bb194:
%1104 = llvm.load %1060 : !llvm.ptr -> i64
%1105 = arith.constant 0 : i32
%1107 = arith.extsi %1105 : i32 to i64
%1106 = arith.cmpi eq, %1104, %1107 : i64
%1108 = scf.if %1106 -> (i1) {
%1109 = arith.constant true
scf.yield %1109 : i1
} else {
%1110 = llvm.load %1075 : !llvm.ptr -> i64
%1111 = llvm.load %1060 : !llvm.ptr -> i64
%1112 = arith.cmpi slt, %1110, %1111 : i64
scf.yield %1112 : i1
}
cf.cond_br %1108, ^bb195, ^bb196
^bb195:
%1113 = llvm.load %1075 : !llvm.ptr -> i64
llvm.store %1113, %1060 : i64, !llvm.ptr
cf.br ^bb197
^bb196:
cf.br ^bb197
^bb197:
%1114 = llvm.load %983 : !llvm.ptr -> i64
%1115 = arith.constant 1 : i32
%1117 = arith.extsi %1115 : i32 to i64
%1116 = arith.addi %1114, %1117 : i64
llvm.store %1116, %983 : i64, !llvm.ptr
cf.br ^bb189
^bb191:
%1118 = llvm.load %1060 : !llvm.ptr -> i64
%1119 = arith.divsi %arg0, %1118 : i64
func.call @build_W(%1119) : (i64) -> ()
%1121 = arith.constant 0 : i32
%1122 = arith.extsi %1121 : i32 to i64
%1123 = llvm.mlir.constant(1 : i64) : i64
%1124 = llvm.alloca %1123 x i64 : (i64) -> !llvm.ptr
llvm.store %1122, %1124 : i64, !llvm.ptr
%1125 = arith.constant 0 : i32
%1126 = arith.extsi %1125 : i32 to i64
llvm.store %1126, %983 : i64, !llvm.ptr
cf.br ^bb198
^bb198:
%1127 = llvm.load %983 : !llvm.ptr -> i64
%1128 = llvm.mlir.addressof @NALL : !llvm.ptr
%1129 = llvm.load %1128 : !llvm.ptr -> i64
%1130 = arith.cmpi slt, %1127, %1129 : i64
cf.cond_br %1130, ^bb199, ^bb200
^bb199:
%1132 = llvm.mlir.addressof @ALLLEN : !llvm.ptr
%1133 = llvm.load %1132 : !llvm.ptr -> !llvm.ptr
%1134 = llvm.load %983 : !llvm.ptr -> i64
%1135 = llvm.getelementptr %1133[%1134] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1131 = llvm.load %1135 : !llvm.ptr -> i64
%1136 = arith.constant 0 : i32
%1137 = arith.extsi %1136 : i32 to i64
%1138 = llvm.mlir.constant(1 : i64) : i64
%1139 = llvm.alloca %1138 x i64 : (i64) -> !llvm.ptr
llvm.store %1137, %1139 : i64, !llvm.ptr
%1140 = arith.constant 1 : i32
%1142 = arith.extsi %1140 : i32 to i64
%1141 = arith.cmpi eq, %1131, %1142 : i64
cf.cond_br %1141, ^bb201, ^bb202
^bb201:
%1145 = llvm.mlir.addressof @ALLSEQ : !llvm.ptr
%1146 = llvm.load %1145 : !llvm.ptr -> !llvm.ptr
%1147 = llvm.load %983 : !llvm.ptr -> i64
%1148 = arith.constant 16 : i32
%1150 = arith.extsi %1148 : i32 to i64
%1149 = arith.muli %1147, %1150 : i64
%1151 = llvm.getelementptr %1146[%1149] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1144 = llvm.load %1151 : !llvm.ptr -> i64
%1143 = func.call @iroot(%arg0, %1144) : (i64, i64) -> i64
llvm.store %1143, %1139 : i64, !llvm.ptr
cf.br ^bb203
^bb202:
%1152 = arith.constant 1 : i32
%1153 = arith.extsi %1152 : i32 to i64
%1154 = llvm.mlir.constant(1 : i64) : i64
%1155 = llvm.alloca %1154 x i64 : (i64) -> !llvm.ptr
llvm.store %1153, %1155 : i64, !llvm.ptr
%1156 = arith.constant 0 : i32
%1157 = arith.extsi %1156 : i32 to i64
%1158 = llvm.mlir.constant(1 : i64) : i64
%1159 = llvm.alloca %1158 x i64 : (i64) -> !llvm.ptr
llvm.store %1157, %1159 : i64, !llvm.ptr
cf.br ^bb204
^bb204:
%1160 = llvm.load %1159 : !llvm.ptr -> i64
%1161 = arith.constant 1 : i32
%1163 = arith.extsi %1161 : i32 to i64
%1162 = arith.subi %1131, %1163 : i64
%1164 = arith.cmpi slt, %1160, %1162 : i64
cf.cond_br %1164, ^bb205, ^bb206
^bb205:
%1165 = llvm.load %1155 : !llvm.ptr -> i64
%1168 = llvm.mlir.addressof @FS : !llvm.ptr
%1169 = llvm.load %1168 : !llvm.ptr -> !llvm.ptr
%1170 = llvm.load %1159 : !llvm.ptr -> i64
%1171 = llvm.getelementptr %1169[%1170] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1167 = llvm.load %1171 : !llvm.ptr -> i64
%1173 = llvm.mlir.addressof @ALLSEQ : !llvm.ptr
%1174 = llvm.load %1173 : !llvm.ptr -> !llvm.ptr
%1175 = llvm.load %983 : !llvm.ptr -> i64
%1176 = arith.constant 16 : i32
%1178 = arith.extsi %1176 : i32 to i64
%1177 = arith.muli %1175, %1178 : i64
%1179 = llvm.load %1159 : !llvm.ptr -> i64
%1180 = arith.addi %1177, %1179 : i64
%1181 = llvm.getelementptr %1174[%1180] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1172 = llvm.load %1181 : !llvm.ptr -> i64
%1166 = func.call @ipow(%1167, %1172) : (i64, i64) -> i64
%1182 = arith.muli %1165, %1166 : i64
llvm.store %1182, %1155 : i64, !llvm.ptr
%1183 = llvm.load %1159 : !llvm.ptr -> i64
%1184 = arith.constant 1 : i32
%1186 = arith.extsi %1184 : i32 to i64
%1185 = arith.addi %1183, %1186 : i64
llvm.store %1185, %1159 : i64, !llvm.ptr
cf.br ^bb204
^bb206:
%1188 = llvm.load %1155 : !llvm.ptr -> i64
%1189 = arith.divsi %arg0, %1188 : i64
%1191 = llvm.mlir.addressof @ALLSEQ : !llvm.ptr
%1192 = llvm.load %1191 : !llvm.ptr -> !llvm.ptr
%1193 = llvm.load %983 : !llvm.ptr -> i64
%1194 = arith.constant 16 : i32
%1196 = arith.extsi %1194 : i32 to i64
%1195 = arith.muli %1193, %1196 : i64
%1197 = arith.addi %1195, %1131 : i64
%1198 = arith.constant 1 : i32
%1200 = arith.extsi %1198 : i32 to i64
%1199 = arith.subi %1197, %1200 : i64
%1201 = llvm.getelementptr %1192[%1199] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1190 = llvm.load %1201 : !llvm.ptr -> i64
%1187 = func.call @iroot(%1189, %1190) : (i64, i64) -> i64
llvm.store %1187, %1139 : i64, !llvm.ptr
cf.br ^bb203
^bb203:
%1202 = llvm.load %1139 : !llvm.ptr -> i64
%1203 = llvm.load %1124 : !llvm.ptr -> i64
%1204 = arith.cmpi sgt, %1202, %1203 : i64
cf.cond_br %1204, ^bb207, ^bb208
^bb207:
%1205 = llvm.load %1139 : !llvm.ptr -> i64
llvm.store %1205, %1124 : i64, !llvm.ptr
cf.br ^bb209
^bb208:
cf.br ^bb209
^bb209:
%1206 = llvm.load %983 : !llvm.ptr -> i64
%1207 = arith.constant 1 : i32
%1209 = arith.extsi %1207 : i32 to i64
%1208 = arith.addi %1206, %1209 : i64
llvm.store %1208, %983 : i64, !llvm.ptr
cf.br ^bb198
^bb200:
%1211 = llvm.load %1124 : !llvm.ptr -> i64
%1212 = arith.constant 3 : i32
%1214 = arith.extsi %1212 : i32 to i64
%1213 = arith.divsi %1211, %1214 : i64
%1215 = arith.constant 100 : i32
%1217 = arith.extsi %1215 : i32 to i64
%1216 = arith.addi %1213, %1217 : i64
%1218 = arith.constant 8 : i32
%1219 = arith.extsi %1218 : i32 to i64
%1210 = func.call @calloc(%1216, %1219) : (i64, i64) -> !llvm.ptr
%1221 = llvm.load %1124 : !llvm.ptr -> i64
%1222 = arith.constant 10 : i32
%1224 = arith.extsi %1222 : i32 to i64
%1223 = arith.addi %1221, %1224 : i64
%1220 = func.call @sieve(%1223, %1210) : (i64, !llvm.ptr) -> i64
%1226 = arith.constant 8 : i32
%1227 = arith.extsi %1226 : i32 to i64
%1225 = func.call @calloc(%1220, %1227) : (i64, i64) -> !llvm.ptr
%1228 = llvm.mlir.addressof @SPLIT : !llvm.ptr
llvm.store %1225, %1228 : !llvm.ptr, !llvm.ptr
%1229 = arith.constant 0 : i32
%1230 = arith.extsi %1229 : i32 to i64
%1231 = llvm.mlir.addressof @NSPLIT : !llvm.ptr
llvm.store %1230, %1231 : i64, !llvm.ptr
%1232 = arith.constant 0 : i32
%1233 = arith.extsi %1232 : i32 to i64
llvm.store %1233, %983 : i64, !llvm.ptr
cf.br ^bb210
^bb210:
%1234 = llvm.load %983 : !llvm.ptr -> i64
%1235 = arith.cmpi slt, %1234, %1220 : i64
cf.cond_br %1235, ^bb211, ^bb212
^bb211:
%1237 = llvm.load %983 : !llvm.ptr -> i64
%1238 = llvm.getelementptr %1210[%1237] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1236 = llvm.load %1238 : !llvm.ptr -> i64
%1239 = arith.constant 5 : i32
%1241 = arith.extsi %1239 : i32 to i64
%1240 = arith.remsi %1236, %1241 : i64
%1242 = arith.constant 1 : i32
%1244 = arith.extsi %1242 : i32 to i64
%1243 = arith.cmpi eq, %1240, %1244 : i64
%1245 = scf.if %1243 -> (i1) {
%1246 = arith.constant true
scf.yield %1246 : i1
} else {
%1247 = arith.constant 4 : i32
%1249 = arith.extsi %1247 : i32 to i64
%1248 = arith.cmpi eq, %1240, %1249 : i64
scf.yield %1248 : i1
}
cf.cond_br %1245, ^bb213, ^bb214
^bb213:
%1250 = llvm.mlir.addressof @SPLIT : !llvm.ptr
%1251 = llvm.load %1250 : !llvm.ptr -> !llvm.ptr
%1252 = llvm.mlir.addressof @NSPLIT : !llvm.ptr
%1253 = llvm.load %1252 : !llvm.ptr -> i64
%1254 = llvm.getelementptr %1251[%1253] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1236, %1254 : i64, !llvm.ptr
%1255 = llvm.mlir.addressof @NSPLIT : !llvm.ptr
%1256 = llvm.load %1255 : !llvm.ptr -> i64
%1257 = arith.constant 1 : i32
%1259 = arith.extsi %1257 : i32 to i64
%1258 = arith.addi %1256, %1259 : i64
%1260 = llvm.mlir.addressof @NSPLIT : !llvm.ptr
llvm.store %1258, %1260 : i64, !llvm.ptr
cf.br ^bb215
^bb214:
cf.br ^bb215
^bb215:
%1261 = llvm.load %983 : !llvm.ptr -> i64
%1262 = arith.constant 1 : i32
%1264 = arith.extsi %1262 : i32 to i64
%1263 = arith.addi %1261, %1264 : i64
llvm.store %1263, %983 : i64, !llvm.ptr
cf.br ^bb210
^bb212:
func.call @free(%1210) : (!llvm.ptr) -> ()
func.call @free(%965) : (!llvm.ptr) -> ()
%1267 = arith.constant 0 : i32
%1268 = arith.extsi %1267 : i32 to i64
%1269 = llvm.mlir.constant(1 : i64) : i64
%1270 = llvm.alloca %1269 x i64 : (i64) -> !llvm.ptr
llvm.store %1268, %1270 : i64, !llvm.ptr
%1271 = arith.constant 0 : i32
%1272 = arith.extsi %1271 : i32 to i64
llvm.store %1272, %983 : i64, !llvm.ptr
cf.br ^bb216
^bb216:
%1273 = llvm.load %983 : !llvm.ptr -> i64
%1274 = llvm.mlir.addressof @NALL : !llvm.ptr
%1275 = llvm.load %1274 : !llvm.ptr -> i64
%1276 = arith.cmpi slt, %1273, %1275 : i64
cf.cond_br %1276, ^bb217, ^bb218
^bb217:
%1278 = llvm.mlir.addressof @ALLLEN : !llvm.ptr
%1279 = llvm.load %1278 : !llvm.ptr -> !llvm.ptr
%1280 = llvm.load %983 : !llvm.ptr -> i64
%1281 = llvm.getelementptr %1279[%1280] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1277 = llvm.load %1281 : !llvm.ptr -> i64
%1282 = llvm.mlir.addressof @SEQL : !llvm.ptr
llvm.store %1277, %1282 : i64, !llvm.ptr
# String concatenation: !llvm.ptr + i64
%1284 = llvm.mlir.addressof @SEQ : !llvm.ptr
llvm.store %1283, %1284 : !llvm.ptr, !llvm.ptr
%1285 = arith.constant 0 : i32
%1286 = arith.extsi %1285 : i32 to i64
%1287 = llvm.mlir.addressof @ACC : !llvm.ptr
llvm.store %1286, %1287 : i64, !llvm.ptr
%1289 = arith.constant 0 : i32
%1290 = arith.constant 0 : i32
%1291 = arith.constant 1 : i32
%1292 = arith.extsi %1289 : i32 to i64
%1293 = arith.extsi %1290 : i32 to i64
%1294 = arith.extsi %1291 : i32 to i64
func.call @rec(%1292, %1293, %1294) : (i64, i64, i64) -> ()
%1295 = llvm.load %1270 : !llvm.ptr -> i64
%1296 = llvm.mlir.addressof @ACC : !llvm.ptr
%1297 = llvm.load %1296 : !llvm.ptr -> i64
%1298 = arith.addi %1295, %1297 : i64
llvm.store %1298, %1270 : i64, !llvm.ptr
%1299 = llvm.load %983 : !llvm.ptr -> i64
%1300 = arith.constant 1 : i32
%1302 = arith.extsi %1300 : i32 to i64
%1301 = arith.addi %1299, %1302 : i64
llvm.store %1301, %983 : i64, !llvm.ptr
cf.br ^bb216
^bb218:
%1304 = llvm.mlir.addressof @Warr : !llvm.ptr
%1305 = llvm.load %1304 : !llvm.ptr -> !llvm.ptr
func.call @free(%1305) : (!llvm.ptr) -> ()
%1307 = llvm.mlir.addressof @SPLIT : !llvm.ptr
%1308 = llvm.load %1307 : !llvm.ptr -> !llvm.ptr
func.call @free(%1308) : (!llvm.ptr) -> ()
%1310 = llvm.mlir.addressof @FS : !llvm.ptr
%1311 = llvm.load %1310 : !llvm.ptr -> !llvm.ptr
func.call @free(%1311) : (!llvm.ptr) -> ()
%1313 = llvm.mlir.addressof @ALLSEQ : !llvm.ptr
%1314 = llvm.load %1313 : !llvm.ptr -> !llvm.ptr
func.call @free(%1314) : (!llvm.ptr) -> ()
%1316 = llvm.mlir.addressof @ALLLEN : !llvm.ptr
%1317 = llvm.load %1316 : !llvm.ptr -> !llvm.ptr
func.call @free(%1317) : (!llvm.ptr) -> ()
%1318 = llvm.load %1270 : !llvm.ptr -> i64
func.return %1318 : i64
}
func.func @main() -> i32 {
%1319 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1321 = arith.constant 999995705032704 : i32
%1322 = arith.constant 40 : i32
%1323 = arith.extsi %1321 : i32 to i64
%1324 = arith.extsi %1322 : i32 to i64
%1320 = func.call @compute_f(%1323, %1324) : (i64, i64) -> i64
%1325 = llvm.call @printf(%1319, %1320) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1326 = arith.constant 0 : i32
func.return %1326 : i32
}
}