← All problems Problem 415
Titanic sets on (N+1)^2 lattice, N=10^11, mod 10^8 via totient sums.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n)O(n log log n)Space complexity O(n^2)O(n)Approach Flow solution Sieve-based totient computation Verdict Optimal
Flow source
# Project Euler 415
# Titanic sets on (N+1)^2 lattice, N=10^11, mod 10^8 via totient sums.
import euler.nt { isqrt }
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 100000000
const DEFAULT_N: i64 = 100000000000
const PRECOMPUTE: i64 = 5000000
# ---- TotientSums state ----
let mut TS_limit: i64 = 0
let mut TS_pref0: ptr<i64> = null
let mut TS_pref1: ptr<i64> = null
let mut TS_pref2: ptr<i64> = null
# cache0 (phi_sum), cache1 (i_phi), cache2 (i2_phi)
let mut c0k: ptr<i64> = null
let mut c0v: ptr<i64> = null
let mut c0u: ptr<i8> = null
let mut c0cap: i64 = 0
let mut c1k: ptr<i64> = null
let mut c1v: ptr<i64> = null
let mut c1u: ptr<i8> = null
let mut c1cap: i64 = 0
let mut c2k: ptr<i64> = null
let mut c2v: ptr<i64> = null
let mut c2u: ptr<i8> = null
let mut c2cap: i64 = 0
# stats hash tables (keyed by m)
let mut sk: ptr<i64> = null
let mut s_count: ptr<i64> = null
let mut s_xy: ptr<i64> = null
let mut s_pr: ptr<i64> = null
let mut su: ptr<i8> = null
let mut scap: i64 = 0
function norm(x: i64) -> i64 {
let mut v: i64 = x % MOD
if v < 0 { v = v + MOD }
return v
}
function mod_pow_128(a0: i64, e0: i128) -> i64 {
let mut r: i64 = 1 % MOD
let mut a: i64 = a0 % MOD
let mut e: i128 = e0
while e > 0 {
let eb: i128 = e & (1 as i128)
if eb != (0 as i128) {
r = ((r as i128) * (a as i128) % (MOD as i128)) as i64
}
a = ((a as i128) * (a as i128) % (MOD as i128)) as i64
e = e >> 1
}
return r
}
function mod_pow_64(a0: i64, e0: i64) -> i64 {
let mut r: i64 = 1 % MOD
let mut a: i64 = a0 % MOD
let mut e: i64 = e0
while e > 0 {
if (e & 1) == 1 {
r = ((r as i128) * (a as i128) % (MOD as i128)) as i64
}
a = ((a as i128) * (a as i128) % (MOD as i128)) as i64
e = e / 2
}
return r
}
function s1(n: i64) -> i64 {
if n <= 0 { return 0 }
let mut a: i64 = n
let mut b: i64 = n + 1
if a % 2 == 0 { a = a / 2 } else { b = b / 2 }
return (a % MOD) * (b % MOD) % MOD
}
function s2(n: i64) -> i64 {
if n <= 0 { return 0 }
let mut a: i64 = n
let mut b: i64 = n + 1
let mut c: i64 = 2 * n + 1
if a % 2 == 0 { a = a / 2 } else { b = b / 2 }
if a % 3 == 0 { a = a / 3 }
else {
if b % 3 == 0 { b = b / 3 }
else { c = c / 3 }
}
return (a % MOD) * (b % MOD) % MOD * (c % MOD) % MOD
}
function s3(n: i64) -> i64 {
if n <= 0 { return 0 }
let t: i64 = s1(n)
return t * t % MOD
}
function range_s1(lo: i64, hi: i64) -> i64 {
return norm(s1(hi) - s1(lo - 1))
}
function range_s2(lo: i64, hi: i64) -> i64 {
return norm(s2(hi) - s2(lo - 1))
}
function range_s3(lo: i64, hi: i64) -> i64 {
return norm(s3(hi) - s3(lo - 1))
}
function pref_k_pow2(n: i64, pow2_next: i64) -> i64 {
if n < 0 { return 0 }
return norm(((n - 1) % MOD) * pow2_next + 2)
}
function pref_k2_pow2(n: i64, pow2_next: i64) -> i64 {
if n < 0 { return 0 }
let k: i64 = n % MOD
let inner: i64 = (k * k % MOD - 2 * k % MOD + 3) % MOD
return norm(inner * pow2_next - 6)
}
# ---- hash table helpers ----
function ht_get(keys: ptr<i64>, vals: ptr<i64>, used: ptr<i8>, cap: i64, key: i64) -> i64 {
let mut slot: i64 = key
if slot < 0 { slot = 0 - slot }
slot = slot & (cap - 1)
while used[slot] != 0 {
if keys[slot] == key { return vals[slot] }
slot = (slot + 1) & (cap - 1)
}
return 0 - 1
}
function ht_put(keys: ptr<i64>, vals: ptr<i64>, used: ptr<i8>, cap: i64, key: i64, val: i64) -> void {
let mut slot: i64 = key
if slot < 0 { slot = 0 - slot }
slot = slot & (cap - 1)
while used[slot] != 0 && keys[slot] != key {
slot = (slot + 1) & (cap - 1)
}
used[slot] = 1
keys[slot] = key
vals[slot] = val
}
# ---- TotientSums ----
function build_totient_sums(max_n: i64) -> void {
let mut limit: i64 = max_n
if limit > PRECOMPUTE { limit = PRECOMPUTE }
if limit < 1 { limit = 1 }
TS_limit = limit
let phi: ptr<i64> = calloc(limit + 1, 8)
let composite: ptr<i8> = calloc(limit + 1, 1)
let primes: ptr<i32> = calloc(limit + 1, 4)
let mut pcount: i64 = 0
phi[1] = 1
let mut x: i64 = 2
while x <= limit {
if composite[x] == 0 {
primes[pcount] = x as i32
pcount = pcount + 1
phi[x] = x - 1
}
let phix: i64 = phi[x]
let mut pi: i64 = 0
while pi < pcount {
let p: i64 = primes[pi] as i64
let y: i64 = x * p
if y > limit { break }
composite[y] = 1
if x % p == 0 {
phi[y] = phix * p
break
}
phi[y] = phix * (p - 1)
pi = pi + 1
}
x = x + 1
}
TS_pref0 = calloc(limit + 1, 8)
TS_pref1 = calloc(limit + 1, 8)
TS_pref2 = calloc(limit + 1, 8)
let mut i: i64 = 1
while i <= limit {
let ph: i64 = phi[i] % MOD
let xm: i64 = i % MOD
TS_pref0[i] = (TS_pref0[i - 1] + ph) % MOD
TS_pref1[i] = (TS_pref1[i - 1] + xm * ph) % MOD
TS_pref2[i] = (TS_pref2[i - 1] + xm * xm % MOD * ph) % MOD
i = i + 1
}
# init caches
c0cap = 1 << 21
c0k = calloc(c0cap, 8)
c0v = calloc(c0cap, 8)
c0u = calloc(c0cap, 1)
c1cap = 1 << 21
c1k = calloc(c1cap, 8)
c1v = calloc(c1cap, 8)
c1u = calloc(c1cap, 1)
c2cap = 1 << 21
c2k = calloc(c2cap, 8)
c2v = calloc(c2cap, 8)
c2u = calloc(c2cap, 1)
# init stats hash table
scap = 1 << 21
sk = calloc(scap, 8)
s_count = calloc(scap, 8)
s_xy = calloc(scap, 8)
s_pr = calloc(scap, 8)
su = calloc(scap, 1)
free(phi as ptr<void>)
free(composite as ptr<void>)
free(primes as ptr<void>)
}
function ts_phi_sum(n: i64) -> i64 {
if n <= TS_limit { return TS_pref0[n] }
let hit: i64 = ht_get(c0k, c0v, c0u, c0cap, n)
if hit >= 0 { return hit }
let mut total: i64 = s1(n)
let mut lo: i64 = 2
while lo <= n {
let q: i64 = n / lo
let hi: i64 = n / q
total = norm(total - ((hi - lo + 1) % MOD) * ts_phi_sum(q) % MOD)
lo = hi + 1
}
ht_put(c0k, c0v, c0u, c0cap, n, total)
return total
}
function ts_i_phi(n: i64) -> i64 {
if n <= TS_limit { return TS_pref1[n] }
let hit: i64 = ht_get(c1k, c1v, c1u, c1cap, n)
if hit >= 0 { return hit }
let mut total: i64 = s2(n)
let mut lo: i64 = 2
while lo <= n {
let q: i64 = n / lo
let hi: i64 = n / q
total = norm(total - range_s1(lo, hi) * ts_i_phi(q) % MOD)
lo = hi + 1
}
ht_put(c1k, c1v, c1u, c1cap, n, total)
return total
}
function ts_i2_phi(n: i64) -> i64 {
if n <= TS_limit { return TS_pref2[n] }
let hit: i64 = ht_get(c2k, c2v, c2u, c2cap, n)
if hit >= 0 { return hit }
let mut total: i64 = s3(n)
let mut lo: i64 = 2
while lo <= n {
let q: i64 = n / lo
let hi: i64 = n / q
total = norm(total - range_s2(lo, hi) * ts_i2_phi(q) % MOD)
lo = hi + 1
}
ht_put(c2k, c2v, c2u, c2cap, n, total)
return total
}
function ensure_stats(m: i64) -> void {
let hit: i64 = ht_get(sk, s_count, su, scap, m)
if hit >= 0 { return }
let count: i64 = 0
let coord_sum: i64 = 0
let product_sum: i64 = 0
if m > 0 {
let c: i64 = norm(2 * ts_phi_sum(m) - 1)
let xy: i64 = norm(3 * ts_i_phi(m) - 1)
let pr: i64 = ts_i2_phi(m)
ht_put(sk, s_count, su, scap, m, c)
ht_put(sk, s_xy, su, scap, m, xy)
ht_put(sk, s_pr, su, scap, m, pr)
} else {
ht_put(sk, s_count, su, scap, m, 0)
ht_put(sk, s_xy, su, scap, m, 0)
ht_put(sk, s_pr, su, scap, m, 0)
}
}
function get_stat_count(m: i64) -> i64 {
return ht_get(sk, s_count, su, scap, m)
}
function get_stat_xy(m: i64) -> i64 {
return ht_get(sk, s_xy, su, scap, m)
}
function get_stat_pr(m: i64) -> i64 {
return ht_get(sk, s_pr, su, scap, m)
}
function min64(a: i64, b: i64) -> i64 {
if a < b { return a }
return b
}
function titanic_sets(n: i64) -> i64 {
let side: i64 = n + 1
let point_count: i128 = (side as i128) * (side as i128)
let all_subsets: i64 = mod_pow_128(2, point_count)
let singleton_part: i64 = norm(1 + ((point_count % (MOD as i128)) as i64))
if n < 2 { return norm(all_subsets - singleton_part) }
# Block decomposition
let max_blocks: i64 = 2000000
let bl_lo: ptr<i64> = calloc(max_blocks, 8)
let bl_hi: ptr<i64> = calloc(max_blocks, 8)
let bl_a: ptr<i64> = calloc(max_blocks, 8)
let bl_b: ptr<i64> = calloc(max_blocks, 8)
let mut nblocks: i64 = 0
let mut lo: i64 = 2
while lo <= n {
let a: i64 = n / lo
let b: i64 = 0
if lo < n { b = n / (lo + 1) }
let hi_a: i64 = n / a
let hi_b: i64 = 0
if b != 0 { hi_b = n / b - 1 } else { hi_b = n }
let hi: i64 = min64(hi_a, hi_b)
bl_lo[nblocks] = lo
bl_hi[nblocks] = hi
bl_a[nblocks] = a
bl_b[nblocks] = b
nblocks = nblocks + 1
ensure_stats(a)
if b != 0 { ensure_stats(b) }
lo = hi + 1
}
let side_mod: i64 = side % MOD
let side2_mod: i64 = side_mod * side_mod % MOD
let mut collinear: i64 = 0
let mut bi: i64 = 0
while bi < nblocks {
let a: i64 = bl_a[bi]
let b: i64 = bl_b[bi]
let c1: i64 = get_stat_count(a)
let xy1: i64 = get_stat_xy(a)
let pr1: i64 = get_stat_pr(a)
let c2: i64 = 0
let xy2: i64 = 0
let pr2: i64 = 0
if b != 0 {
c2 = get_stat_count(b)
xy2 = get_stat_xy(b)
pr2 = get_stat_pr(b)
}
let q2: i64 = norm(pr1 - pr2)
let q1: i64 = norm(side_mod * norm(xy2 - xy1) % MOD - 2 * pr2 % MOD)
let q0: i64 = norm(side2_mod * norm(c1 - c2) % MOD + side_mod * xy2 % MOD - pr2)
let p2: i64 = 2 * q2 % MOD
let p1: i64 = 2 * q1 % MOD
let p0: i64 = (2 * q0 + 2 * side_mod) % MOD
let blo: i64 = bl_lo[bi]
let bhi: i64 = bl_hi[bi]
let pow_lo: i64 = mod_pow_64(2, blo)
let pow_after_hi: i64 = mod_pow_64(2, bhi + 1)
let e0: i64 = norm(pow_after_hi - pow_lo)
let e1: i64 = norm(pref_k_pow2(bhi, pow_after_hi) - pref_k_pow2(blo - 1, pow_lo))
let e2: i64 = norm(pref_k2_pow2(bhi, pow_after_hi) - pref_k2_pow2(blo - 1, pow_lo))
let poly_exp: i64 = (p2 * e2 + p1 * e1 + p0 * e0) % MOD
let r1: i64 = range_s1(blo, bhi)
let r2: i64 = range_s2(blo, bhi)
let r3: i64 = range_s3(blo, bhi)
let length: i64 = (bhi - blo + 1) % MOD
let poly_plain: i64 = (p2 * ((r3 + r2) % MOD) + p1 * ((r2 + r1) % MOD) + p0 * ((r1 + length) % MOD)) % MOD
collinear = norm(collinear + poly_exp - poly_plain)
bi = bi + 1
}
free(bl_lo as ptr<void>)
free(bl_hi as ptr<void>)
free(bl_a as ptr<void>)
free(bl_b as ptr<void>)
return norm(all_subsets - singleton_part - collinear)
}
function main() -> i32 {
let mut max_n: i64 = DEFAULT_N
if max_n < 100000 { max_n = 100000 }
build_totient_sums(max_n)
printf("%lld\n", titanic_sets(DEFAULT_N))
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t gcd_i64_i64(int64_t a0, int64_t b0);
int64_t lcm_i64_i64(int64_t a, int64_t b);
int64_t isqrt_i64(int64_t n);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
bool is_prime_i64(int64_t n);
int64_t norm_i64(int64_t x);
int64_t mod_pow_128_i64_i128(int64_t a0, __int128 e0);
int64_t mod_pow_64_i64_i64(int64_t a0, int64_t e0);
int64_t s1_i64(int64_t n);
int64_t s2_i64(int64_t n);
int64_t s3_i64(int64_t n);
int64_t range_s1_i64_i64(int64_t lo, int64_t hi);
int64_t range_s2_i64_i64(int64_t lo, int64_t hi);
int64_t range_s3_i64_i64(int64_t lo, int64_t hi);
int64_t pref_k_pow2_i64_i64(int64_t n, int64_t pow2_next);
int64_t pref_k2_pow2_i64_i64(int64_t n, int64_t pow2_next);
int64_t ht_get_ptr_i64_ptr_i64_ptr_i8_i64_i64(int64_t* keys, int64_t* vals, int8_t* used, int64_t cap, int64_t key);
void ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(int64_t* keys, int64_t* vals, int8_t* used, int64_t cap, int64_t key, int64_t val);
void build_totient_sums_i64(int64_t max_n);
int64_t ts_phi_sum_i64(int64_t n);
int64_t ts_i_phi_i64(int64_t n);
int64_t ts_i2_phi_i64(int64_t n);
void ensure_stats_i64(int64_t m);
int64_t get_stat_count_i64(int64_t m);
int64_t get_stat_xy_i64(int64_t m);
int64_t get_stat_pr_i64(int64_t m);
int64_t min64_i64_i64(int64_t a, int64_t b);
int64_t titanic_sets_i64(int64_t n);
int32_t main(void);
static const int64_t MOD = 100000000;
static const int64_t DEFAULT_N = 100000000000;
static const int64_t PRECOMPUTE = 5000000;
/* Module statics */
static int64_t TS_limit = 0;
static int64_t* TS_pref0 = NULL;
static int64_t* TS_pref1 = NULL;
static int64_t* TS_pref2 = NULL;
static int64_t* c0k = NULL;
static int64_t* c0v = NULL;
static int8_t* c0u = NULL;
static int64_t c0cap = 0;
static int64_t* c1k = NULL;
static int64_t* c1v = NULL;
static int8_t* c1u = NULL;
static int64_t c1cap = 0;
static int64_t* c2k = NULL;
static int64_t* c2v = NULL;
static int8_t* c2u = NULL;
static int64_t c2cap = 0;
static int64_t* sk = NULL;
static int64_t* s_count = NULL;
static int64_t* s_xy = NULL;
static int64_t* s_pr = NULL;
static int8_t* su = NULL;
static int64_t scap = 0;
int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t lcm_i64_i64(int64_t a, int64_t b) {
if ((a == 0 || b == 0)) {
return 0;
}
return (FLOW_CHECKED_DIV((a), (gcd_i64_i64(a, b))) * b);
}
int64_t isqrt_i64(int64_t n) {
if (n < 2) {
return n;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod) {
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
int64_t b = FLOW_CHECKED_MOD((b0), (mod));
int64_t result = 0;
while (b > 0) {
if (FLOW_CHECKED_MOD((b), (2)) == 1) {
result = FLOW_CHECKED_MOD(((result + a)), (mod));
}
a = FLOW_CHECKED_MOD(((a * 2)), (mod));
b = FLOW_CHECKED_DIV((b), (2));
}
return result;
}
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
if (mod == 1) {
return 0;
}
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (mod));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mulmod_i64_i64_i64(result, b, mod);
}
b = mulmod_i64_i64_i64(b, b, mod);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
bool is_prime_i64(int64_t n) {
if (n < 2) {
return 0;
}
if (n < 4) {
return 1;
}
if ((FLOW_CHECKED_MOD((n), (2)) == 0 || FLOW_CHECKED_MOD((n), (3)) == 0)) {
return 0;
}
int64_t i = 5;
while ((i * i) <= n) {
if ((FLOW_CHECKED_MOD((n), (i)) == 0 || FLOW_CHECKED_MOD((n), ((i + 2))) == 0)) {
return 0;
}
i = (i + 6);
}
return 1;
}
int64_t norm_i64(int64_t x) {
int64_t v = FLOW_CHECKED_MOD((x), (MOD));
if (v < 0) {
v = (v + MOD);
}
return v;
}
int64_t mod_pow_128_i64_i128(int64_t a0, __int128 e0) {
int64_t r = FLOW_CHECKED_MOD((1), (MOD));
int64_t a = FLOW_CHECKED_MOD((a0), (MOD));
__int128 e = e0;
while (e > 0) {
__int128 eb = (e & ((__int128)(1)));
if (eb != ((__int128)(0))) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(a)))), (((__int128)(MOD))))));
}
a = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(a)))), (((__int128)(MOD))))));
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
int64_t mod_pow_64_i64_i64(int64_t a0, int64_t e0) {
int64_t r = FLOW_CHECKED_MOD((1), (MOD));
int64_t a = FLOW_CHECKED_MOD((a0), (MOD));
int64_t e = e0;
while (e > 0) {
if ((e & 1) == 1) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(a)))), (((__int128)(MOD))))));
}
a = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(a)))), (((__int128)(MOD))))));
e = FLOW_CHECKED_DIV((e), (2));
}
return r;
}
int64_t s1_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t a = n;
int64_t b = (n + 1);
if (FLOW_CHECKED_MOD((a), (2)) == 0) {
a = FLOW_CHECKED_DIV((a), (2));
} else {
b = FLOW_CHECKED_DIV((b), (2));
}
return FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((a), (MOD)) * FLOW_CHECKED_MOD((b), (MOD)))), (MOD));
}
int64_t s2_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t a = n;
int64_t b = (n + 1);
int64_t c = ((2 * n) + 1);
if (FLOW_CHECKED_MOD((a), (2)) == 0) {
a = FLOW_CHECKED_DIV((a), (2));
} else {
b = FLOW_CHECKED_DIV((b), (2));
}
if (FLOW_CHECKED_MOD((a), (3)) == 0) {
a = FLOW_CHECKED_DIV((a), (3));
} else {
if (FLOW_CHECKED_MOD((b), (3)) == 0) {
b = FLOW_CHECKED_DIV((b), (3));
} else {
c = FLOW_CHECKED_DIV((c), (3));
}
}
return FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((a), (MOD)) * FLOW_CHECKED_MOD((b), (MOD)))), (MOD)) * FLOW_CHECKED_MOD((c), (MOD)))), (MOD));
}
int64_t s3_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t t = s1_i64(n);
return FLOW_CHECKED_MOD(((t * t)), (MOD));
}
int64_t range_s1_i64_i64(int64_t lo, int64_t hi) {
return norm_i64((s1_i64(hi) - s1_i64((lo - 1))));
}
int64_t range_s2_i64_i64(int64_t lo, int64_t hi) {
return norm_i64((s2_i64(hi) - s2_i64((lo - 1))));
}
int64_t range_s3_i64_i64(int64_t lo, int64_t hi) {
return norm_i64((s3_i64(hi) - s3_i64((lo - 1))));
}
int64_t pref_k_pow2_i64_i64(int64_t n, int64_t pow2_next) {
if (n < 0) {
return 0;
}
return norm_i64(((FLOW_CHECKED_MOD(((n - 1)), (MOD)) * pow2_next) + 2));
}
int64_t pref_k2_pow2_i64_i64(int64_t n, int64_t pow2_next) {
if (n < 0) {
return 0;
}
int64_t k = FLOW_CHECKED_MOD((n), (MOD));
int64_t inner = FLOW_CHECKED_MOD((((FLOW_CHECKED_MOD(((k * k)), (MOD)) - FLOW_CHECKED_MOD(((2 * k)), (MOD))) + 3)), (MOD));
return norm_i64(((inner * pow2_next) - 6));
}
int64_t ht_get_ptr_i64_ptr_i64_ptr_i8_i64_i64(int64_t* keys, int64_t* vals, int8_t* used, int64_t cap, int64_t key) {
int64_t slot = key;
if (slot < 0) {
slot = (0 - slot);
}
slot = (slot & (cap - 1));
while (used[slot] != 0) {
if (keys[slot] == key) {
return vals[slot];
}
slot = ((slot + 1) & (cap - 1));
}
return (0 - 1);
}
void ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(int64_t* keys, int64_t* vals, int8_t* used, int64_t cap, int64_t key, int64_t val) {
int64_t slot = key;
if (slot < 0) {
slot = (0 - slot);
}
slot = (slot & (cap - 1));
while ((used[slot] != 0 && keys[slot] != key)) {
slot = ((slot + 1) & (cap - 1));
}
used[slot] = 1;
keys[slot] = key;
vals[slot] = val;
}
void build_totient_sums_i64(int64_t max_n) {
int64_t limit = max_n;
if (limit > PRECOMPUTE) {
limit = PRECOMPUTE;
}
if (limit < 1) {
limit = 1;
}
TS_limit = limit;
int64_t* phi = (int64_t*)(calloc((limit + 1), 8));
int8_t* composite = (int8_t*)(calloc((limit + 1), 1));
int32_t* primes = (int32_t*)(calloc((limit + 1), 4));
int64_t pcount = 0;
phi[1] = 1;
int64_t x = 2;
while (x <= limit) {
if (composite[x] == 0) {
primes[pcount] = ((int32_t)(x));
pcount = (pcount + 1);
phi[x] = (x - 1);
}
int64_t phix = phi[x];
int64_t pi = 0;
while (pi < pcount) {
int64_t p = ((int64_t)(primes[pi]));
int64_t y = (x * p);
if (y > limit) {
break;
}
composite[y] = 1;
if (FLOW_CHECKED_MOD((x), (p)) == 0) {
phi[y] = (phix * p);
break;
}
phi[y] = (phix * (p - 1));
pi = (pi + 1);
}
x = (x + 1);
}
TS_pref0 = calloc((limit + 1), 8);
TS_pref1 = calloc((limit + 1), 8);
TS_pref2 = calloc((limit + 1), 8);
int64_t i = 1;
while (i <= limit) {
int64_t ph = FLOW_CHECKED_MOD((phi[i]), (MOD));
int64_t xm = FLOW_CHECKED_MOD((i), (MOD));
TS_pref0[i] = FLOW_CHECKED_MOD(((TS_pref0[(i - 1)] + ph)), (MOD));
TS_pref1[i] = FLOW_CHECKED_MOD(((TS_pref1[(i - 1)] + (xm * ph))), (MOD));
TS_pref2[i] = FLOW_CHECKED_MOD(((TS_pref2[(i - 1)] + (FLOW_CHECKED_MOD(((xm * xm)), (MOD)) * ph))), (MOD));
i = (i + 1);
}
c0cap = FLOW_CHECKED_SHL((1), (21));
c0k = calloc(c0cap, 8);
c0v = calloc(c0cap, 8);
c0u = calloc(c0cap, 1);
c1cap = FLOW_CHECKED_SHL((1), (21));
c1k = calloc(c1cap, 8);
c1v = calloc(c1cap, 8);
c1u = calloc(c1cap, 1);
c2cap = FLOW_CHECKED_SHL((1), (21));
c2k = calloc(c2cap, 8);
c2v = calloc(c2cap, 8);
c2u = calloc(c2cap, 1);
scap = FLOW_CHECKED_SHL((1), (21));
sk = calloc(scap, 8);
s_count = calloc(scap, 8);
s_xy = calloc(scap, 8);
s_pr = calloc(scap, 8);
su = calloc(scap, 1);
free(((void*)(phi)));
free(((void*)(composite)));
free(((void*)(primes)));
}
int64_t ts_phi_sum_i64(int64_t n) {
if (n <= TS_limit) {
return TS_pref0[n];
}
int64_t hit = ht_get_ptr_i64_ptr_i64_ptr_i8_i64_i64(c0k, c0v, c0u, c0cap, n);
if (hit >= 0) {
return hit;
}
int64_t total = s1_i64(n);
int64_t lo = 2;
while (lo <= n) {
int64_t q = FLOW_CHECKED_DIV((n), (lo));
int64_t hi = FLOW_CHECKED_DIV((n), (q));
total = norm_i64((total - FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((hi - lo) + 1)), (MOD)) * ts_phi_sum_i64(q))), (MOD))));
lo = (hi + 1);
}
ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(c0k, c0v, c0u, c0cap, n, total);
return total;
}
int64_t ts_i_phi_i64(int64_t n) {
if (n <= TS_limit) {
return TS_pref1[n];
}
int64_t hit = ht_get_ptr_i64_ptr_i64_ptr_i8_i64_i64(c1k, c1v, c1u, c1cap, n);
if (hit >= 0) {
return hit;
}
int64_t total = s2_i64(n);
int64_t lo = 2;
while (lo <= n) {
int64_t q = FLOW_CHECKED_DIV((n), (lo));
int64_t hi = FLOW_CHECKED_DIV((n), (q));
total = norm_i64((total - FLOW_CHECKED_MOD(((range_s1_i64_i64(lo, hi) * ts_i_phi_i64(q))), (MOD))));
lo = (hi + 1);
}
ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(c1k, c1v, c1u, c1cap, n, total);
return total;
}
int64_t ts_i2_phi_i64(int64_t n) {
if (n <= TS_limit) {
return TS_pref2[n];
}
int64_t hit = ht_get_ptr_i64_ptr_i64_ptr_i8_i64_i64(c2k, c2v, c2u, c2cap, n);
if (hit >= 0) {
return hit;
}
int64_t total = s3_i64(n);
int64_t lo = 2;
while (lo <= n) {
int64_t q = FLOW_CHECKED_DIV((n), (lo));
int64_t hi = FLOW_CHECKED_DIV((n), (q));
total = norm_i64((total - FLOW_CHECKED_MOD(((range_s2_i64_i64(lo, hi) * ts_i2_phi_i64(q))), (MOD))));
lo = (hi + 1);
}
ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(c2k, c2v, c2u, c2cap, n, total);
return total;
}
void ensure_stats_i64(int64_t m) {
int64_t hit = ht_get_ptr_i64_ptr_i64_ptr_i8_i64_i64(sk, s_count, su, scap, m);
if (hit >= 0) {
return;
}
int64_t count = 0;
int64_t coord_sum = 0;
int64_t product_sum = 0;
if (m > 0) {
int64_t c = norm_i64(((2 * ts_phi_sum_i64(m)) - 1));
int64_t xy = norm_i64(((3 * ts_i_phi_i64(m)) - 1));
int64_t pr = ts_i2_phi_i64(m);
ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(sk, s_count, su, scap, m, c);
ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(sk, s_xy, su, scap, m, xy);
ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(sk, s_pr, su, scap, m, pr);
} else {
ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(sk, s_count, su, scap, m, 0);
ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(sk, s_xy, su, scap, m, 0);
ht_put_ptr_i64_ptr_i64_ptr_i8_i64_i64_i64(sk, s_pr, su, scap, m, 0);
}
}
int64_t get_stat_count_i64(int64_t m) {
return ht_get_ptr_i64_ptr_i64_ptr_i8_i64_i64(sk, s_count, su, scap, m);
}
int64_t get_stat_xy_i64(int64_t m) {
return ht_get_ptr_i64_ptr_i64_ptr_i8_i64_i64(sk, s_xy, su, scap, m);
}
int64_t get_stat_pr_i64(int64_t m) {
return ht_get_ptr_i64_ptr_i64_ptr_i8_i64_i64(sk, s_pr, su, scap, m);
}
int64_t min64_i64_i64(int64_t a, int64_t b) {
if (a < b) {
return a;
}
return b;
}
int64_t titanic_sets_i64(int64_t n) {
int64_t side = (n + 1);
__int128 point_count = (((__int128)(side)) * ((__int128)(side)));
int64_t all_subsets = mod_pow_128_i64_i128(2, point_count);
int64_t singleton_part = norm_i64((1 + ((int64_t)(FLOW_CHECKED_MOD((point_count), (((__int128)(MOD))))))));
if (n < 2) {
return norm_i64((all_subsets - singleton_part));
}
int64_t max_blocks = 2000000;
int64_t* bl_lo = (int64_t*)(calloc(max_blocks, 8));
int64_t* bl_hi = (int64_t*)(calloc(max_blocks, 8));
int64_t* bl_a = (int64_t*)(calloc(max_blocks, 8));
int64_t* bl_b = (int64_t*)(calloc(max_blocks, 8));
int64_t nblocks = 0;
int64_t lo = 2;
while (lo <= n) {
int64_t a = FLOW_CHECKED_DIV((n), (lo));
int64_t b = 0;
if (lo < n) {
b = FLOW_CHECKED_DIV((n), ((lo + 1)));
}
int64_t hi_a = FLOW_CHECKED_DIV((n), (a));
int64_t hi_b = 0;
if (b != 0) {
hi_b = (FLOW_CHECKED_DIV((n), (b)) - 1);
} else {
hi_b = n;
}
int64_t hi = min64_i64_i64(hi_a, hi_b);
bl_lo[nblocks] = lo;
bl_hi[nblocks] = hi;
bl_a[nblocks] = a;
bl_b[nblocks] = b;
nblocks = (nblocks + 1);
ensure_stats_i64(a);
if (b != 0) {
ensure_stats_i64(b);
}
lo = (hi + 1);
}
int64_t side_mod = FLOW_CHECKED_MOD((side), (MOD));
int64_t side2_mod = FLOW_CHECKED_MOD(((side_mod * side_mod)), (MOD));
int64_t collinear = 0;
int64_t bi = 0;
while (bi < nblocks) {
int64_t a = bl_a[bi];
int64_t b = bl_b[bi];
int64_t c1 = get_stat_count_i64(a);
int64_t xy1 = get_stat_xy_i64(a);
int64_t pr1 = get_stat_pr_i64(a);
int64_t c2 = 0;
int64_t xy2 = 0;
int64_t pr2 = 0;
if (b != 0) {
c2 = get_stat_count_i64(b);
xy2 = get_stat_xy_i64(b);
pr2 = get_stat_pr_i64(b);
}
int64_t q2 = norm_i64((pr1 - pr2));
int64_t q1 = norm_i64((FLOW_CHECKED_MOD(((side_mod * norm_i64((xy2 - xy1)))), (MOD)) - FLOW_CHECKED_MOD(((2 * pr2)), (MOD))));
int64_t q0 = norm_i64(((FLOW_CHECKED_MOD(((side2_mod * norm_i64((c1 - c2)))), (MOD)) + FLOW_CHECKED_MOD(((side_mod * xy2)), (MOD))) - pr2));
int64_t p2 = FLOW_CHECKED_MOD(((2 * q2)), (MOD));
int64_t p1 = FLOW_CHECKED_MOD(((2 * q1)), (MOD));
int64_t p0 = FLOW_CHECKED_MOD((((2 * q0) + (2 * side_mod))), (MOD));
int64_t blo = bl_lo[bi];
int64_t bhi = bl_hi[bi];
int64_t pow_lo = mod_pow_64_i64_i64(2, blo);
int64_t pow_after_hi = mod_pow_64_i64_i64(2, (bhi + 1));
int64_t e0 = norm_i64((pow_after_hi - pow_lo));
int64_t e1 = norm_i64((pref_k_pow2_i64_i64(bhi, pow_after_hi) - pref_k_pow2_i64_i64((blo - 1), pow_lo)));
int64_t e2 = norm_i64((pref_k2_pow2_i64_i64(bhi, pow_after_hi) - pref_k2_pow2_i64_i64((blo - 1), pow_lo)));
int64_t poly_exp = FLOW_CHECKED_MOD(((((p2 * e2) + (p1 * e1)) + (p0 * e0))), (MOD));
int64_t r1 = range_s1_i64_i64(blo, bhi);
int64_t r2 = range_s2_i64_i64(blo, bhi);
int64_t r3 = range_s3_i64_i64(blo, bhi);
int64_t length = FLOW_CHECKED_MOD((((bhi - blo) + 1)), (MOD));
int64_t poly_plain = FLOW_CHECKED_MOD(((((p2 * FLOW_CHECKED_MOD(((r3 + r2)), (MOD))) + (p1 * FLOW_CHECKED_MOD(((r2 + r1)), (MOD)))) + (p0 * FLOW_CHECKED_MOD(((r1 + length)), (MOD))))), (MOD));
collinear = norm_i64(((collinear + poly_exp) - poly_plain));
bi = (bi + 1);
}
free(((void*)(bl_lo)));
free(((void*)(bl_hi)));
free(((void*)(bl_a)));
free(((void*)(bl_b)));
return norm_i64(((all_subsets - singleton_part) - collinear));
}
int32_t main(void) {
int64_t max_n = DEFAULT_N;
if (max_n < 100000) {
max_n = 100000;
}
build_totient_sums_i64(max_n);
printf("%lld\n", titanic_sets_i64(DEFAULT_N));
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func @gcd(%arg0: i64, %arg1: i64) -> i64 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%4 = llvm.load %3 : !llvm.ptr -> i64
%5 = arith.constant 0 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi ne, %4, %7 : i64
cf.cond_br %6, ^bb1, ^bb2
^bb1:
%8 = llvm.load %1 : !llvm.ptr -> i64
%9 = llvm.load %3 : !llvm.ptr -> i64
%10 = arith.remsi %8, %9 : i64
%11 = llvm.load %3 : !llvm.ptr -> i64
llvm.store %11, %1 : i64, !llvm.ptr
llvm.store %10, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%12 = llvm.load %1 : !llvm.ptr -> i64
func.return %12 : i64
}
func.func @lcm(%arg0: i64, %arg1: i64) -> i64 {
%13 = arith.constant 0 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.cmpi eq, %arg0, %15 : i64
%16 = scf.if %14 -> (i1) {
%17 = arith.constant true
scf.yield %17 : i1
} else {
%18 = arith.constant 0 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.cmpi eq, %arg1, %20 : i64
scf.yield %19 : i1
}
cf.cond_br %16, ^bb3, ^bb4
^bb3:
%21 = arith.constant 0 : i32
%22 = arith.extsi %21 : i32 to i64
func.return %22 : i64
^bb4:
cf.br ^bb5
^bb5:
%23 = func.call @gcd(%arg0, %arg1) : (i64, i64) -> i64
%24 = arith.divsi %arg0, %23 : i64
%25 = arith.muli %24, %arg1 : i64
func.return %25 : i64
}
func.func @isqrt(%arg0: i64) -> i64 {
%26 = arith.constant 2 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.cmpi slt, %arg0, %28 : i64
cf.cond_br %27, ^bb6, ^bb7
^bb6:
func.return %arg0 : i64
^bb7:
cf.br ^bb8
^bb8:
%29 = llvm.mlir.constant(1 : i64) : i64
%30 = llvm.alloca %29 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %30 : i64, !llvm.ptr
%31 = llvm.load %30 : !llvm.ptr -> i64
%32 = arith.constant 1 : i32
%34 = arith.extsi %32 : i32 to i64
%33 = arith.addi %31, %34 : i64
%35 = arith.constant 2 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.divsi %33, %37 : i64
%38 = llvm.mlir.constant(1 : i64) : i64
%39 = llvm.alloca %38 x i64 : (i64) -> !llvm.ptr
llvm.store %36, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%40 = llvm.load %39 : !llvm.ptr -> i64
%41 = llvm.load %30 : !llvm.ptr -> i64
%42 = arith.cmpi slt, %40, %41 : i64
cf.cond_br %42, ^bb10, ^bb11
^bb10:
%43 = llvm.load %39 : !llvm.ptr -> i64
llvm.store %43, %30 : i64, !llvm.ptr
%44 = llvm.load %30 : !llvm.ptr -> i64
%45 = llvm.load %30 : !llvm.ptr -> i64
%46 = arith.divsi %arg0, %45 : i64
%47 = arith.addi %44, %46 : i64
%48 = arith.constant 2 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.divsi %47, %50 : i64
llvm.store %49, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%51 = llvm.load %30 : !llvm.ptr -> i64
func.return %51 : i64
}
func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%52 = arith.remsi %arg0, %arg2 : i64
%53 = llvm.mlir.constant(1 : i64) : i64
%54 = llvm.alloca %53 x i64 : (i64) -> !llvm.ptr
llvm.store %52, %54 : i64, !llvm.ptr
%55 = arith.remsi %arg1, %arg2 : i64
%56 = llvm.mlir.constant(1 : i64) : i64
%57 = llvm.alloca %56 x i64 : (i64) -> !llvm.ptr
llvm.store %55, %57 : i64, !llvm.ptr
%58 = arith.constant 0 : i32
%59 = arith.extsi %58 : i32 to i64
%60 = llvm.mlir.constant(1 : i64) : i64
%61 = llvm.alloca %60 x i64 : (i64) -> !llvm.ptr
llvm.store %59, %61 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%62 = llvm.load %57 : !llvm.ptr -> i64
%63 = arith.constant 0 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.cmpi sgt, %62, %65 : i64
cf.cond_br %64, ^bb13, ^bb14
^bb13:
%66 = llvm.load %57 : !llvm.ptr -> i64
%67 = arith.constant 2 : i32
%69 = arith.extsi %67 : i32 to i64
%68 = arith.remsi %66, %69 : i64
%70 = arith.constant 1 : i32
%72 = arith.extsi %70 : i32 to i64
%71 = arith.cmpi eq, %68, %72 : i64
cf.cond_br %71, ^bb15, ^bb16
^bb15:
%73 = llvm.load %61 : !llvm.ptr -> i64
%74 = llvm.load %54 : !llvm.ptr -> i64
%75 = arith.addi %73, %74 : i64
%76 = arith.remsi %75, %arg2 : i64
llvm.store %76, %61 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%77 = llvm.load %54 : !llvm.ptr -> i64
%78 = arith.constant 2 : i32
%80 = arith.extsi %78 : i32 to i64
%79 = arith.muli %77, %80 : i64
%81 = arith.remsi %79, %arg2 : i64
llvm.store %81, %54 : i64, !llvm.ptr
%82 = llvm.load %57 : !llvm.ptr -> i64
%83 = arith.constant 2 : i32
%85 = arith.extsi %83 : i32 to i64
%84 = arith.divsi %82, %85 : i64
llvm.store %84, %57 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%86 = llvm.load %61 : !llvm.ptr -> i64
func.return %86 : i64
}
func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%87 = arith.constant 1 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.cmpi eq, %arg2, %89 : i64
cf.cond_br %88, ^bb18, ^bb19
^bb18:
%90 = arith.constant 0 : i32
%91 = arith.extsi %90 : i32 to i64
func.return %91 : i64
^bb19:
cf.br ^bb20
^bb20:
%92 = arith.constant 1 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i64, !llvm.ptr
%96 = arith.remsi %arg0, %arg2 : i64
%97 = llvm.mlir.constant(1 : i64) : i64
%98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
llvm.store %96, %98 : i64, !llvm.ptr
%99 = llvm.mlir.constant(1 : i64) : i64
%100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%101 = llvm.load %100 : !llvm.ptr -> i64
%102 = arith.constant 0 : i32
%104 = arith.extsi %102 : i32 to i64
%103 = arith.cmpi sgt, %101, %104 : i64
cf.cond_br %103, ^bb22, ^bb23
^bb22:
%105 = llvm.load %100 : !llvm.ptr -> i64
%106 = arith.constant 2 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.remsi %105, %108 : i64
%109 = arith.constant 1 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.cmpi eq, %107, %111 : i64
cf.cond_br %110, ^bb24, ^bb25
^bb24:
%113 = llvm.load %95 : !llvm.ptr -> i64
%114 = llvm.load %98 : !llvm.ptr -> i64
%112 = func.call @mulmod(%113, %114, %arg2) : (i64, i64, i64) -> i64
llvm.store %112, %95 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%116 = llvm.load %98 : !llvm.ptr -> i64
%117 = llvm.load %98 : !llvm.ptr -> i64
%115 = func.call @mulmod(%116, %117, %arg2) : (i64, i64, i64) -> i64
llvm.store %115, %98 : i64, !llvm.ptr
%118 = llvm.load %100 : !llvm.ptr -> i64
%119 = arith.constant 2 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.divsi %118, %121 : i64
llvm.store %120, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%122 = llvm.load %95 : !llvm.ptr -> i64
func.return %122 : i64
}
func.func @is_prime(%arg0: i64) -> i1 {
%123 = arith.constant 2 : i32
%125 = arith.extsi %123 : i32 to i64
%124 = arith.cmpi slt, %arg0, %125 : i64
cf.cond_br %124, ^bb27, ^bb28
^bb27:
%126 = arith.constant 0 : i1
func.return %126 : i1
^bb28:
cf.br ^bb29
^bb29:
%127 = arith.constant 4 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.cmpi slt, %arg0, %129 : i64
cf.cond_br %128, ^bb30, ^bb31
^bb30:
%130 = arith.constant 1 : i1
func.return %130 : i1
^bb31:
cf.br ^bb32
^bb32:
%131 = arith.constant 2 : i32
%133 = arith.extsi %131 : i32 to i64
%132 = arith.remsi %arg0, %133 : i64
%134 = arith.constant 0 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.cmpi eq, %132, %136 : i64
%137 = scf.if %135 -> (i1) {
%138 = arith.constant true
scf.yield %138 : i1
} else {
%139 = arith.constant 3 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.remsi %arg0, %141 : i64
%142 = arith.constant 0 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.cmpi eq, %140, %144 : i64
scf.yield %143 : i1
}
cf.cond_br %137, ^bb33, ^bb34
^bb33:
%145 = arith.constant 0 : i1
func.return %145 : i1
^bb34:
cf.br ^bb35
^bb35:
%146 = arith.constant 5 : i32
%147 = arith.extsi %146 : i32 to i64
%148 = llvm.mlir.constant(1 : i64) : i64
%149 = llvm.alloca %148 x i64 : (i64) -> !llvm.ptr
llvm.store %147, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.load %149 : !llvm.ptr -> i64
%152 = arith.muli %150, %151 : i64
%153 = arith.cmpi sle, %152, %arg0 : i64
cf.cond_br %153, ^bb37, ^bb38
^bb37:
%154 = llvm.load %149 : !llvm.ptr -> i64
%155 = arith.remsi %arg0, %154 : i64
%156 = arith.constant 0 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.cmpi eq, %155, %158 : i64
%159 = scf.if %157 -> (i1) {
%160 = arith.constant true
scf.yield %160 : i1
} else {
%161 = llvm.load %149 : !llvm.ptr -> i64
%162 = arith.constant 2 : i32
%164 = arith.extsi %162 : i32 to i64
%163 = arith.addi %161, %164 : i64
%165 = arith.remsi %arg0, %163 : i64
%166 = arith.constant 0 : i32
%168 = arith.extsi %166 : i32 to i64
%167 = arith.cmpi eq, %165, %168 : i64
scf.yield %167 : i1
}
cf.cond_br %159, ^bb39, ^bb40
^bb39:
%169 = arith.constant 0 : i1
func.return %169 : i1
^bb40:
cf.br ^bb41
^bb41:
%170 = llvm.load %149 : !llvm.ptr -> i64
%171 = arith.constant 6 : i32
%173 = arith.extsi %171 : i32 to i64
%172 = arith.addi %170, %173 : i64
llvm.store %172, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%174 = arith.constant 1 : i1
func.return %174 : i1
}
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(100000000 : i64) : i64
// Constant: DEFAULT_N
llvm.mlir.global internal constant @DEFAULT_N(100000000000 : i64) : i64
// Constant: PRECOMPUTE
llvm.mlir.global internal constant @PRECOMPUTE(5000000 : i64) : i64
// Module static: TS_limit
llvm.mlir.global internal @TS_limit(0 : i64) : i64
// Module static: TS_pref0
llvm.mlir.global internal @TS_pref0() {addr_space = 0 : i32} : !llvm.ptr {
%175 = llvm.mlir.zero : !llvm.ptr
llvm.return %175 : !llvm.ptr
}
// Module static: TS_pref1
llvm.mlir.global internal @TS_pref1() {addr_space = 0 : i32} : !llvm.ptr {
%176 = llvm.mlir.zero : !llvm.ptr
llvm.return %176 : !llvm.ptr
}
// Module static: TS_pref2
llvm.mlir.global internal @TS_pref2() {addr_space = 0 : i32} : !llvm.ptr {
%177 = llvm.mlir.zero : !llvm.ptr
llvm.return %177 : !llvm.ptr
}
// Module static: c0k
llvm.mlir.global internal @c0k() {addr_space = 0 : i32} : !llvm.ptr {
%178 = llvm.mlir.zero : !llvm.ptr
llvm.return %178 : !llvm.ptr
}
// Module static: c0v
llvm.mlir.global internal @c0v() {addr_space = 0 : i32} : !llvm.ptr {
%179 = llvm.mlir.zero : !llvm.ptr
llvm.return %179 : !llvm.ptr
}
// Module static: c0u
llvm.mlir.global internal @c0u() {addr_space = 0 : i32} : !llvm.ptr {
%180 = llvm.mlir.zero : !llvm.ptr
llvm.return %180 : !llvm.ptr
}
// Module static: c0cap
llvm.mlir.global internal @c0cap(0 : i64) : i64
// Module static: c1k
llvm.mlir.global internal @c1k() {addr_space = 0 : i32} : !llvm.ptr {
%181 = llvm.mlir.zero : !llvm.ptr
llvm.return %181 : !llvm.ptr
}
// Module static: c1v
llvm.mlir.global internal @c1v() {addr_space = 0 : i32} : !llvm.ptr {
%182 = llvm.mlir.zero : !llvm.ptr
llvm.return %182 : !llvm.ptr
}
// Module static: c1u
llvm.mlir.global internal @c1u() {addr_space = 0 : i32} : !llvm.ptr {
%183 = llvm.mlir.zero : !llvm.ptr
llvm.return %183 : !llvm.ptr
}
// Module static: c1cap
llvm.mlir.global internal @c1cap(0 : i64) : i64
// Module static: c2k
llvm.mlir.global internal @c2k() {addr_space = 0 : i32} : !llvm.ptr {
%184 = llvm.mlir.zero : !llvm.ptr
llvm.return %184 : !llvm.ptr
}
// Module static: c2v
llvm.mlir.global internal @c2v() {addr_space = 0 : i32} : !llvm.ptr {
%185 = llvm.mlir.zero : !llvm.ptr
llvm.return %185 : !llvm.ptr
}
// Module static: c2u
llvm.mlir.global internal @c2u() {addr_space = 0 : i32} : !llvm.ptr {
%186 = llvm.mlir.zero : !llvm.ptr
llvm.return %186 : !llvm.ptr
}
// Module static: c2cap
llvm.mlir.global internal @c2cap(0 : i64) : i64
// Module static: sk
llvm.mlir.global internal @sk() {addr_space = 0 : i32} : !llvm.ptr {
%187 = llvm.mlir.zero : !llvm.ptr
llvm.return %187 : !llvm.ptr
}
// Module static: s_count
llvm.mlir.global internal @s_count() {addr_space = 0 : i32} : !llvm.ptr {
%188 = llvm.mlir.zero : !llvm.ptr
llvm.return %188 : !llvm.ptr
}
// Module static: s_xy
llvm.mlir.global internal @s_xy() {addr_space = 0 : i32} : !llvm.ptr {
%189 = llvm.mlir.zero : !llvm.ptr
llvm.return %189 : !llvm.ptr
}
// Module static: s_pr
llvm.mlir.global internal @s_pr() {addr_space = 0 : i32} : !llvm.ptr {
%190 = llvm.mlir.zero : !llvm.ptr
llvm.return %190 : !llvm.ptr
}
// Module static: su
llvm.mlir.global internal @su() {addr_space = 0 : i32} : !llvm.ptr {
%191 = llvm.mlir.zero : !llvm.ptr
llvm.return %191 : !llvm.ptr
}
// Module static: scap
llvm.mlir.global internal @scap(0 : i64) : i64
func.func @norm(%arg0: i64) -> i64 {
%192 = llvm.mlir.addressof @MOD : !llvm.ptr
%193 = llvm.load %192 : !llvm.ptr -> i64
%194 = arith.remsi %arg0, %193 : i64
%195 = llvm.mlir.constant(1 : i64) : i64
%196 = llvm.alloca %195 x i64 : (i64) -> !llvm.ptr
llvm.store %194, %196 : i64, !llvm.ptr
%197 = llvm.load %196 : !llvm.ptr -> i64
%198 = arith.constant 0 : i32
%200 = arith.extsi %198 : i32 to i64
%199 = arith.cmpi slt, %197, %200 : i64
cf.cond_br %199, ^bb42, ^bb43
^bb42:
%201 = llvm.load %196 : !llvm.ptr -> i64
%202 = llvm.mlir.addressof @MOD : !llvm.ptr
%203 = llvm.load %202 : !llvm.ptr -> i64
%204 = arith.addi %201, %203 : i64
llvm.store %204, %196 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%205 = llvm.load %196 : !llvm.ptr -> i64
func.return %205 : i64
}
func.func @mod_pow_128(%arg0: i64, %arg1: i128) -> i64 {
%206 = arith.constant 1 : i32
%207 = llvm.mlir.addressof @MOD : !llvm.ptr
%208 = llvm.load %207 : !llvm.ptr -> i64
%210 = arith.extsi %206 : i32 to i64
%209 = arith.remsi %210, %208 : i64
%211 = llvm.mlir.constant(1 : i64) : i64
%212 = llvm.alloca %211 x i64 : (i64) -> !llvm.ptr
llvm.store %209, %212 : i64, !llvm.ptr
%213 = llvm.mlir.addressof @MOD : !llvm.ptr
%214 = llvm.load %213 : !llvm.ptr -> i64
%215 = arith.remsi %arg0, %214 : i64
%216 = llvm.mlir.constant(1 : i64) : i64
%217 = llvm.alloca %216 x i64 : (i64) -> !llvm.ptr
llvm.store %215, %217 : i64, !llvm.ptr
%218 = llvm.mlir.constant(1 : i64) : i64
%219 = llvm.alloca %218 x i128 : (i64) -> !llvm.ptr
llvm.store %arg1, %219 : i128, !llvm.ptr
cf.br ^bb45
^bb45:
%220 = llvm.load %219 : !llvm.ptr -> i128
%221 = arith.constant 0 : i32
%223 = arith.trunci %220 : i128 to i64
%224 = arith.extsi %221 : i32 to i64
%222 = arith.cmpi sgt, %223, %224 : i64
cf.cond_br %222, ^bb46, ^bb47
^bb46:
%225 = llvm.load %219 : !llvm.ptr -> i128
%226 = arith.constant 1 : i32
%227 = arith.extsi %226 : i32 to i128
%229 = arith.trunci %225 : i128 to i64
%230 = arith.trunci %227 : i128 to i64
%228 = arith.andi %229, %230 : i64
%231 = arith.extsi %228 : i64 to i128
%232 = arith.constant 0 : i32
%233 = arith.extsi %232 : i32 to i128
%235 = arith.trunci %231 : i128 to i64
%236 = arith.trunci %233 : i128 to i64
%234 = arith.cmpi ne, %235, %236 : i64
cf.cond_br %234, ^bb48, ^bb49
^bb48:
%237 = llvm.load %212 : !llvm.ptr -> i64
%238 = arith.extsi %237 : i64 to i128
%239 = llvm.load %217 : !llvm.ptr -> i64
%240 = arith.extsi %239 : i64 to i128
%242 = arith.trunci %238 : i128 to i64
%243 = arith.trunci %240 : i128 to i64
%241 = arith.muli %242, %243 : i64
%244 = llvm.mlir.addressof @MOD : !llvm.ptr
%245 = llvm.load %244 : !llvm.ptr -> i64
%246 = arith.extsi %245 : i64 to i128
%248 = arith.trunci %246 : i128 to i64
%247 = arith.remsi %241, %248 : i64
llvm.store %247, %212 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%249 = llvm.load %217 : !llvm.ptr -> i64
%250 = arith.extsi %249 : i64 to i128
%251 = llvm.load %217 : !llvm.ptr -> i64
%252 = arith.extsi %251 : i64 to i128
%254 = arith.trunci %250 : i128 to i64
%255 = arith.trunci %252 : i128 to i64
%253 = arith.muli %254, %255 : i64
%256 = llvm.mlir.addressof @MOD : !llvm.ptr
%257 = llvm.load %256 : !llvm.ptr -> i64
%258 = arith.extsi %257 : i64 to i128
%260 = arith.trunci %258 : i128 to i64
%259 = arith.remsi %253, %260 : i64
llvm.store %259, %217 : i64, !llvm.ptr
%261 = llvm.load %219 : !llvm.ptr -> i128
%262 = arith.constant 1 : i32
%264 = arith.trunci %261 : i128 to i64
%265 = arith.extsi %262 : i32 to i64
%263 = arith.shrsi %264, %265 : i64
%266 = arith.extsi %263 : i64 to i128
llvm.store %266, %219 : i128, !llvm.ptr
cf.br ^bb45
^bb47:
%267 = llvm.load %212 : !llvm.ptr -> i64
func.return %267 : i64
}
func.func @mod_pow_64(%arg0: i64, %arg1: i64) -> i64 {
%268 = arith.constant 1 : i32
%269 = llvm.mlir.addressof @MOD : !llvm.ptr
%270 = llvm.load %269 : !llvm.ptr -> i64
%272 = arith.extsi %268 : i32 to i64
%271 = arith.remsi %272, %270 : i64
%273 = llvm.mlir.constant(1 : i64) : i64
%274 = llvm.alloca %273 x i64 : (i64) -> !llvm.ptr
llvm.store %271, %274 : i64, !llvm.ptr
%275 = llvm.mlir.addressof @MOD : !llvm.ptr
%276 = llvm.load %275 : !llvm.ptr -> i64
%277 = arith.remsi %arg0, %276 : i64
%278 = llvm.mlir.constant(1 : i64) : i64
%279 = llvm.alloca %278 x i64 : (i64) -> !llvm.ptr
llvm.store %277, %279 : i64, !llvm.ptr
%280 = llvm.mlir.constant(1 : i64) : i64
%281 = llvm.alloca %280 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %281 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%282 = llvm.load %281 : !llvm.ptr -> i64
%283 = arith.constant 0 : i32
%285 = arith.extsi %283 : i32 to i64
%284 = arith.cmpi sgt, %282, %285 : i64
cf.cond_br %284, ^bb52, ^bb53
^bb52:
%286 = llvm.load %281 : !llvm.ptr -> i64
%287 = arith.constant 1 : i32
%289 = arith.extsi %287 : i32 to i64
%288 = arith.andi %286, %289 : i64
%290 = arith.constant 1 : i32
%292 = arith.extsi %290 : i32 to i64
%291 = arith.cmpi eq, %288, %292 : i64
cf.cond_br %291, ^bb54, ^bb55
^bb54:
%293 = llvm.load %274 : !llvm.ptr -> i64
%294 = arith.extsi %293 : i64 to i128
%295 = llvm.load %279 : !llvm.ptr -> i64
%296 = arith.extsi %295 : i64 to i128
%298 = arith.trunci %294 : i128 to i64
%299 = arith.trunci %296 : i128 to i64
%297 = arith.muli %298, %299 : i64
%300 = llvm.mlir.addressof @MOD : !llvm.ptr
%301 = llvm.load %300 : !llvm.ptr -> i64
%302 = arith.extsi %301 : i64 to i128
%304 = arith.trunci %302 : i128 to i64
%303 = arith.remsi %297, %304 : i64
llvm.store %303, %274 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%305 = llvm.load %279 : !llvm.ptr -> i64
%306 = arith.extsi %305 : i64 to i128
%307 = llvm.load %279 : !llvm.ptr -> i64
%308 = arith.extsi %307 : i64 to i128
%310 = arith.trunci %306 : i128 to i64
%311 = arith.trunci %308 : i128 to i64
%309 = arith.muli %310, %311 : i64
%312 = llvm.mlir.addressof @MOD : !llvm.ptr
%313 = llvm.load %312 : !llvm.ptr -> i64
%314 = arith.extsi %313 : i64 to i128
%316 = arith.trunci %314 : i128 to i64
%315 = arith.remsi %309, %316 : i64
llvm.store %315, %279 : i64, !llvm.ptr
%317 = llvm.load %281 : !llvm.ptr -> i64
%318 = arith.constant 2 : i32
%320 = arith.extsi %318 : i32 to i64
%319 = arith.divsi %317, %320 : i64
llvm.store %319, %281 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%321 = llvm.load %274 : !llvm.ptr -> i64
func.return %321 : i64
}
func.func @s1(%arg0: i64) -> i64 {
%322 = arith.constant 0 : i32
%324 = arith.extsi %322 : i32 to i64
%323 = arith.cmpi sle, %arg0, %324 : i64
cf.cond_br %323, ^bb57, ^bb58
^bb57:
%325 = arith.constant 0 : i32
%326 = arith.extsi %325 : i32 to i64
func.return %326 : i64
^bb58:
cf.br ^bb59
^bb59:
%327 = llvm.mlir.constant(1 : i64) : i64
%328 = llvm.alloca %327 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %328 : i64, !llvm.ptr
%329 = arith.constant 1 : i32
%331 = arith.extsi %329 : i32 to i64
%330 = arith.addi %arg0, %331 : i64
%332 = llvm.mlir.constant(1 : i64) : i64
%333 = llvm.alloca %332 x i64 : (i64) -> !llvm.ptr
llvm.store %330, %333 : i64, !llvm.ptr
%334 = llvm.load %328 : !llvm.ptr -> i64
%335 = arith.constant 2 : i32
%337 = arith.extsi %335 : i32 to i64
%336 = arith.remsi %334, %337 : i64
%338 = arith.constant 0 : i32
%340 = arith.extsi %338 : i32 to i64
%339 = arith.cmpi eq, %336, %340 : i64
cf.cond_br %339, ^bb60, ^bb61
^bb60:
%341 = llvm.load %328 : !llvm.ptr -> i64
%342 = arith.constant 2 : i32
%344 = arith.extsi %342 : i32 to i64
%343 = arith.divsi %341, %344 : i64
llvm.store %343, %328 : i64, !llvm.ptr
cf.br ^bb62
^bb61:
%345 = llvm.load %333 : !llvm.ptr -> i64
%346 = arith.constant 2 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.divsi %345, %348 : i64
llvm.store %347, %333 : i64, !llvm.ptr
cf.br ^bb62
^bb62:
%349 = llvm.load %328 : !llvm.ptr -> i64
%350 = llvm.mlir.addressof @MOD : !llvm.ptr
%351 = llvm.load %350 : !llvm.ptr -> i64
%352 = arith.remsi %349, %351 : i64
%353 = llvm.load %333 : !llvm.ptr -> i64
%354 = llvm.mlir.addressof @MOD : !llvm.ptr
%355 = llvm.load %354 : !llvm.ptr -> i64
%356 = arith.remsi %353, %355 : i64
%357 = arith.muli %352, %356 : i64
%358 = llvm.mlir.addressof @MOD : !llvm.ptr
%359 = llvm.load %358 : !llvm.ptr -> i64
%360 = arith.remsi %357, %359 : i64
func.return %360 : i64
}
func.func @s2(%arg0: i64) -> i64 {
%361 = arith.constant 0 : i32
%363 = arith.extsi %361 : i32 to i64
%362 = arith.cmpi sle, %arg0, %363 : i64
cf.cond_br %362, ^bb63, ^bb64
^bb63:
%364 = arith.constant 0 : i32
%365 = arith.extsi %364 : i32 to i64
func.return %365 : i64
^bb64:
cf.br ^bb65
^bb65:
%366 = llvm.mlir.constant(1 : i64) : i64
%367 = llvm.alloca %366 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %367 : i64, !llvm.ptr
%368 = arith.constant 1 : i32
%370 = arith.extsi %368 : i32 to i64
%369 = arith.addi %arg0, %370 : i64
%371 = llvm.mlir.constant(1 : i64) : i64
%372 = llvm.alloca %371 x i64 : (i64) -> !llvm.ptr
llvm.store %369, %372 : i64, !llvm.ptr
%373 = arith.constant 2 : i32
%375 = arith.extsi %373 : i32 to i64
%374 = arith.muli %375, %arg0 : i64
%376 = arith.constant 1 : i32
%378 = arith.extsi %376 : i32 to i64
%377 = arith.addi %374, %378 : i64
%379 = llvm.mlir.constant(1 : i64) : i64
%380 = llvm.alloca %379 x i64 : (i64) -> !llvm.ptr
llvm.store %377, %380 : i64, !llvm.ptr
%381 = llvm.load %367 : !llvm.ptr -> i64
%382 = arith.constant 2 : i32
%384 = arith.extsi %382 : i32 to i64
%383 = arith.remsi %381, %384 : i64
%385 = arith.constant 0 : i32
%387 = arith.extsi %385 : i32 to i64
%386 = arith.cmpi eq, %383, %387 : i64
cf.cond_br %386, ^bb66, ^bb67
^bb66:
%388 = llvm.load %367 : !llvm.ptr -> i64
%389 = arith.constant 2 : i32
%391 = arith.extsi %389 : i32 to i64
%390 = arith.divsi %388, %391 : i64
llvm.store %390, %367 : i64, !llvm.ptr
cf.br ^bb68
^bb67:
%392 = llvm.load %372 : !llvm.ptr -> i64
%393 = arith.constant 2 : i32
%395 = arith.extsi %393 : i32 to i64
%394 = arith.divsi %392, %395 : i64
llvm.store %394, %372 : i64, !llvm.ptr
cf.br ^bb68
^bb68:
%396 = llvm.load %367 : !llvm.ptr -> i64
%397 = arith.constant 3 : i32
%399 = arith.extsi %397 : i32 to i64
%398 = arith.remsi %396, %399 : i64
%400 = arith.constant 0 : i32
%402 = arith.extsi %400 : i32 to i64
%401 = arith.cmpi eq, %398, %402 : i64
cf.cond_br %401, ^bb69, ^bb70
^bb69:
%403 = llvm.load %367 : !llvm.ptr -> i64
%404 = arith.constant 3 : i32
%406 = arith.extsi %404 : i32 to i64
%405 = arith.divsi %403, %406 : i64
llvm.store %405, %367 : i64, !llvm.ptr
cf.br ^bb71
^bb70:
%407 = llvm.load %372 : !llvm.ptr -> i64
%408 = arith.constant 3 : i32
%410 = arith.extsi %408 : i32 to i64
%409 = arith.remsi %407, %410 : i64
%411 = arith.constant 0 : i32
%413 = arith.extsi %411 : i32 to i64
%412 = arith.cmpi eq, %409, %413 : i64
cf.cond_br %412, ^bb72, ^bb73
^bb72:
%414 = llvm.load %372 : !llvm.ptr -> i64
%415 = arith.constant 3 : i32
%417 = arith.extsi %415 : i32 to i64
%416 = arith.divsi %414, %417 : i64
llvm.store %416, %372 : i64, !llvm.ptr
cf.br ^bb74
^bb73:
%418 = llvm.load %380 : !llvm.ptr -> i64
%419 = arith.constant 3 : i32
%421 = arith.extsi %419 : i32 to i64
%420 = arith.divsi %418, %421 : i64
llvm.store %420, %380 : i64, !llvm.ptr
cf.br ^bb74
^bb74:
cf.br ^bb71
^bb71:
%422 = llvm.load %367 : !llvm.ptr -> i64
%423 = llvm.mlir.addressof @MOD : !llvm.ptr
%424 = llvm.load %423 : !llvm.ptr -> i64
%425 = arith.remsi %422, %424 : i64
%426 = llvm.load %372 : !llvm.ptr -> i64
%427 = llvm.mlir.addressof @MOD : !llvm.ptr
%428 = llvm.load %427 : !llvm.ptr -> i64
%429 = arith.remsi %426, %428 : i64
%430 = arith.muli %425, %429 : i64
%431 = llvm.mlir.addressof @MOD : !llvm.ptr
%432 = llvm.load %431 : !llvm.ptr -> i64
%433 = arith.remsi %430, %432 : i64
%434 = llvm.load %380 : !llvm.ptr -> i64
%435 = llvm.mlir.addressof @MOD : !llvm.ptr
%436 = llvm.load %435 : !llvm.ptr -> i64
%437 = arith.remsi %434, %436 : i64
%438 = arith.muli %433, %437 : i64
%439 = llvm.mlir.addressof @MOD : !llvm.ptr
%440 = llvm.load %439 : !llvm.ptr -> i64
%441 = arith.remsi %438, %440 : i64
func.return %441 : i64
}
func.func @s3(%arg0: i64) -> i64 {
%442 = arith.constant 0 : i32
%444 = arith.extsi %442 : i32 to i64
%443 = arith.cmpi sle, %arg0, %444 : i64
cf.cond_br %443, ^bb75, ^bb76
^bb75:
%445 = arith.constant 0 : i32
%446 = arith.extsi %445 : i32 to i64
func.return %446 : i64
^bb76:
cf.br ^bb77
^bb77:
%447 = func.call @s1(%arg0) : (i64) -> i64
%448 = arith.muli %447, %447 : i64
%449 = llvm.mlir.addressof @MOD : !llvm.ptr
%450 = llvm.load %449 : !llvm.ptr -> i64
%451 = arith.remsi %448, %450 : i64
func.return %451 : i64
}
func.func @range_s1(%arg0: i64, %arg1: i64) -> i64 {
%453 = func.call @s1(%arg1) : (i64) -> i64
%455 = arith.constant 1 : i32
%457 = arith.extsi %455 : i32 to i64
%456 = arith.subi %arg0, %457 : i64
%454 = func.call @s1(%456) : (i64) -> i64
%458 = arith.subi %453, %454 : i64
%452 = func.call @norm(%458) : (i64) -> i64
func.return %452 : i64
}
func.func @range_s2(%arg0: i64, %arg1: i64) -> i64 {
%460 = func.call @s2(%arg1) : (i64) -> i64
%462 = arith.constant 1 : i32
%464 = arith.extsi %462 : i32 to i64
%463 = arith.subi %arg0, %464 : i64
%461 = func.call @s2(%463) : (i64) -> i64
%465 = arith.subi %460, %461 : i64
%459 = func.call @norm(%465) : (i64) -> i64
func.return %459 : i64
}
func.func @range_s3(%arg0: i64, %arg1: i64) -> i64 {
%467 = func.call @s3(%arg1) : (i64) -> i64
%469 = arith.constant 1 : i32
%471 = arith.extsi %469 : i32 to i64
%470 = arith.subi %arg0, %471 : i64
%468 = func.call @s3(%470) : (i64) -> i64
%472 = arith.subi %467, %468 : i64
%466 = func.call @norm(%472) : (i64) -> i64
func.return %466 : i64
}
func.func @pref_k_pow2(%arg0: i64, %arg1: i64) -> i64 {
%473 = arith.constant 0 : i32
%475 = arith.extsi %473 : i32 to i64
%474 = arith.cmpi slt, %arg0, %475 : i64
cf.cond_br %474, ^bb78, ^bb79
^bb78:
%476 = arith.constant 0 : i32
%477 = arith.extsi %476 : i32 to i64
func.return %477 : i64
^bb79:
cf.br ^bb80
^bb80:
%479 = arith.constant 1 : i32
%481 = arith.extsi %479 : i32 to i64
%480 = arith.subi %arg0, %481 : i64
%482 = llvm.mlir.addressof @MOD : !llvm.ptr
%483 = llvm.load %482 : !llvm.ptr -> i64
%484 = arith.remsi %480, %483 : i64
%485 = arith.muli %484, %arg1 : i64
%486 = arith.constant 2 : i32
%488 = arith.extsi %486 : i32 to i64
%487 = arith.addi %485, %488 : i64
%478 = func.call @norm(%487) : (i64) -> i64
func.return %478 : i64
}
func.func @pref_k2_pow2(%arg0: i64, %arg1: i64) -> i64 {
%489 = arith.constant 0 : i32
%491 = arith.extsi %489 : i32 to i64
%490 = arith.cmpi slt, %arg0, %491 : i64
cf.cond_br %490, ^bb81, ^bb82
^bb81:
%492 = arith.constant 0 : i32
%493 = arith.extsi %492 : i32 to i64
func.return %493 : i64
^bb82:
cf.br ^bb83
^bb83:
%494 = llvm.mlir.addressof @MOD : !llvm.ptr
%495 = llvm.load %494 : !llvm.ptr -> i64
%496 = arith.remsi %arg0, %495 : i64
%497 = arith.muli %496, %496 : i64
%498 = llvm.mlir.addressof @MOD : !llvm.ptr
%499 = llvm.load %498 : !llvm.ptr -> i64
%500 = arith.remsi %497, %499 : i64
%501 = arith.constant 2 : i32
%503 = arith.extsi %501 : i32 to i64
%502 = arith.muli %503, %496 : i64
%504 = llvm.mlir.addressof @MOD : !llvm.ptr
%505 = llvm.load %504 : !llvm.ptr -> i64
%506 = arith.remsi %502, %505 : i64
%507 = arith.subi %500, %506 : i64
%508 = arith.constant 3 : i32
%510 = arith.extsi %508 : i32 to i64
%509 = arith.addi %507, %510 : i64
%511 = llvm.mlir.addressof @MOD : !llvm.ptr
%512 = llvm.load %511 : !llvm.ptr -> i64
%513 = arith.remsi %509, %512 : i64
%515 = arith.muli %513, %arg1 : i64
%516 = arith.constant 6 : i32
%518 = arith.extsi %516 : i32 to i64
%517 = arith.subi %515, %518 : i64
%514 = func.call @norm(%517) : (i64) -> i64
func.return %514 : i64
}
func.func @ht_get(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: i64, %arg4: i64) -> i64 {
%519 = llvm.mlir.constant(1 : i64) : i64
%520 = llvm.alloca %519 x i64 : (i64) -> !llvm.ptr
llvm.store %arg4, %520 : i64, !llvm.ptr
%521 = llvm.load %520 : !llvm.ptr -> i64
%522 = arith.constant 0 : i32
%524 = arith.extsi %522 : i32 to i64
%523 = arith.cmpi slt, %521, %524 : i64
cf.cond_br %523, ^bb84, ^bb85
^bb84:
%525 = arith.constant 0 : i32
%526 = llvm.load %520 : !llvm.ptr -> i64
%528 = arith.extsi %525 : i32 to i64
%527 = arith.subi %528, %526 : i64
llvm.store %527, %520 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
%529 = llvm.load %520 : !llvm.ptr -> i64
%530 = arith.constant 1 : i32
%532 = arith.extsi %530 : i32 to i64
%531 = arith.subi %arg3, %532 : i64
%533 = arith.andi %529, %531 : i64
llvm.store %533, %520 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%535 = llvm.load %520 : !llvm.ptr -> i64
%536 = llvm.getelementptr %arg2[%535] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%534 = llvm.load %536 : !llvm.ptr -> i8
%537 = arith.constant 0 : i32
%539 = arith.extsi %534 : i8 to i32
%538 = arith.cmpi ne, %539, %537 : i32
cf.cond_br %538, ^bb88, ^bb89
^bb88:
%541 = llvm.load %520 : !llvm.ptr -> i64
%542 = llvm.getelementptr %arg0[%541] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%540 = llvm.load %542 : !llvm.ptr -> i64
%543 = arith.cmpi eq, %540, %arg4 : i64
cf.cond_br %543, ^bb90, ^bb91
^bb90:
%545 = llvm.load %520 : !llvm.ptr -> i64
%546 = llvm.getelementptr %arg1[%545] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%544 = llvm.load %546 : !llvm.ptr -> i64
func.return %544 : i64
^bb91:
cf.br ^bb92
^bb92:
%547 = llvm.load %520 : !llvm.ptr -> i64
%548 = arith.constant 1 : i32
%550 = arith.extsi %548 : i32 to i64
%549 = arith.addi %547, %550 : i64
%551 = arith.constant 1 : i32
%553 = arith.extsi %551 : i32 to i64
%552 = arith.subi %arg3, %553 : i64
%554 = arith.andi %549, %552 : i64
llvm.store %554, %520 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%555 = arith.constant 0 : i32
%556 = arith.constant 1 : i32
%557 = arith.subi %555, %556 : i32
%558 = arith.extsi %557 : i32 to i64
func.return %558 : i64
}
func.func @ht_put(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: i64, %arg4: i64, %arg5: i64) -> () {
%559 = llvm.mlir.constant(1 : i64) : i64
%560 = llvm.alloca %559 x i64 : (i64) -> !llvm.ptr
llvm.store %arg4, %560 : i64, !llvm.ptr
%561 = llvm.load %560 : !llvm.ptr -> i64
%562 = arith.constant 0 : i32
%564 = arith.extsi %562 : i32 to i64
%563 = arith.cmpi slt, %561, %564 : i64
cf.cond_br %563, ^bb93, ^bb94
^bb93:
%565 = arith.constant 0 : i32
%566 = llvm.load %560 : !llvm.ptr -> i64
%568 = arith.extsi %565 : i32 to i64
%567 = arith.subi %568, %566 : i64
llvm.store %567, %560 : i64, !llvm.ptr
cf.br ^bb95
^bb94:
cf.br ^bb95
^bb95:
%569 = llvm.load %560 : !llvm.ptr -> i64
%570 = arith.constant 1 : i32
%572 = arith.extsi %570 : i32 to i64
%571 = arith.subi %arg3, %572 : i64
%573 = arith.andi %569, %571 : i64
llvm.store %573, %560 : i64, !llvm.ptr
cf.br ^bb96
^bb96:
%575 = llvm.load %560 : !llvm.ptr -> i64
%576 = llvm.getelementptr %arg2[%575] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%574 = llvm.load %576 : !llvm.ptr -> i8
%577 = arith.constant 0 : i32
%579 = arith.extsi %574 : i8 to i32
%578 = arith.cmpi ne, %579, %577 : i32
%580 = scf.if %578 -> (i1) {
%582 = llvm.load %560 : !llvm.ptr -> i64
%583 = llvm.getelementptr %arg0[%582] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%581 = llvm.load %583 : !llvm.ptr -> i64
%584 = arith.cmpi ne, %581, %arg4 : i64
scf.yield %584 : i1
} else {
%585 = arith.constant false
scf.yield %585 : i1
}
cf.cond_br %580, ^bb97, ^bb98
^bb97:
%586 = llvm.load %560 : !llvm.ptr -> i64
%587 = arith.constant 1 : i32
%589 = arith.extsi %587 : i32 to i64
%588 = arith.addi %586, %589 : i64
%590 = arith.constant 1 : i32
%592 = arith.extsi %590 : i32 to i64
%591 = arith.subi %arg3, %592 : i64
%593 = arith.andi %588, %591 : i64
llvm.store %593, %560 : i64, !llvm.ptr
cf.br ^bb96
^bb98:
%594 = arith.constant 1 : i32
%595 = llvm.load %560 : !llvm.ptr -> i64
%596 = arith.trunci %594 : i32 to i8
%597 = llvm.getelementptr %arg2[%595] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %596, %597 : i8, !llvm.ptr
%598 = llvm.load %560 : !llvm.ptr -> i64
%599 = llvm.getelementptr %arg0[%598] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg4, %599 : i64, !llvm.ptr
%600 = llvm.load %560 : !llvm.ptr -> i64
%601 = llvm.getelementptr %arg1[%600] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg5, %601 : i64, !llvm.ptr
func.return
}
func.func @build_totient_sums(%arg0: i64) -> () {
%602 = llvm.mlir.constant(1 : i64) : i64
%603 = llvm.alloca %602 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %603 : i64, !llvm.ptr
%604 = llvm.load %603 : !llvm.ptr -> i64
%605 = llvm.mlir.addressof @PRECOMPUTE : !llvm.ptr
%606 = llvm.load %605 : !llvm.ptr -> i64
%607 = arith.cmpi sgt, %604, %606 : i64
cf.cond_br %607, ^bb99, ^bb100
^bb99:
%608 = llvm.mlir.addressof @PRECOMPUTE : !llvm.ptr
%609 = llvm.load %608 : !llvm.ptr -> i64
llvm.store %609, %603 : i64, !llvm.ptr
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
%610 = llvm.load %603 : !llvm.ptr -> i64
%611 = arith.constant 1 : i32
%613 = arith.extsi %611 : i32 to i64
%612 = arith.cmpi slt, %610, %613 : i64
cf.cond_br %612, ^bb102, ^bb103
^bb102:
%614 = arith.constant 1 : i32
%615 = arith.extsi %614 : i32 to i64
llvm.store %615, %603 : i64, !llvm.ptr
cf.br ^bb104
^bb103:
cf.br ^bb104
^bb104:
%616 = llvm.load %603 : !llvm.ptr -> i64
%617 = llvm.mlir.addressof @TS_limit : !llvm.ptr
llvm.store %616, %617 : i64, !llvm.ptr
%619 = llvm.load %603 : !llvm.ptr -> i64
%620 = arith.constant 1 : i32
%622 = arith.extsi %620 : i32 to i64
%621 = arith.addi %619, %622 : i64
%623 = arith.constant 8 : i32
%624 = arith.extsi %623 : i32 to i64
%618 = func.call @calloc(%621, %624) : (i64, i64) -> !llvm.ptr
%626 = llvm.load %603 : !llvm.ptr -> i64
%627 = arith.constant 1 : i32
%629 = arith.extsi %627 : i32 to i64
%628 = arith.addi %626, %629 : i64
%630 = arith.constant 1 : i32
%631 = arith.extsi %630 : i32 to i64
%625 = func.call @calloc(%628, %631) : (i64, i64) -> !llvm.ptr
%633 = llvm.load %603 : !llvm.ptr -> i64
%634 = arith.constant 1 : i32
%636 = arith.extsi %634 : i32 to i64
%635 = arith.addi %633, %636 : i64
%637 = arith.constant 4 : i32
%638 = arith.extsi %637 : i32 to i64
%632 = func.call @calloc(%635, %638) : (i64, i64) -> !llvm.ptr
%639 = arith.constant 0 : i32
%640 = arith.extsi %639 : i32 to i64
%641 = llvm.mlir.constant(1 : i64) : i64
%642 = llvm.alloca %641 x i64 : (i64) -> !llvm.ptr
llvm.store %640, %642 : i64, !llvm.ptr
%643 = arith.constant 1 : i32
%644 = arith.constant 1 : i32
%645 = arith.extsi %643 : i32 to i64
%646 = arith.extsi %644 : i32 to i64
%647 = llvm.getelementptr %618[%646] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %645, %647 : i64, !llvm.ptr
%648 = arith.constant 2 : i32
%649 = arith.extsi %648 : i32 to i64
%650 = llvm.mlir.constant(1 : i64) : i64
%651 = llvm.alloca %650 x i64 : (i64) -> !llvm.ptr
llvm.store %649, %651 : i64, !llvm.ptr
cf.br ^bb105
^bb105:
%652 = llvm.load %651 : !llvm.ptr -> i64
%653 = llvm.load %603 : !llvm.ptr -> i64
%654 = arith.cmpi sle, %652, %653 : i64
cf.cond_br %654, ^bb106, ^bb107
^bb106:
%656 = llvm.load %651 : !llvm.ptr -> i64
%657 = llvm.getelementptr %625[%656] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%655 = llvm.load %657 : !llvm.ptr -> i8
%658 = arith.constant 0 : i32
%660 = arith.extsi %655 : i8 to i32
%659 = arith.cmpi eq, %660, %658 : i32
cf.cond_br %659, ^bb108, ^bb109
^bb108:
%661 = llvm.load %651 : !llvm.ptr -> i64
%662 = arith.trunci %661 : i64 to i32
%663 = llvm.load %642 : !llvm.ptr -> i64
%664 = llvm.getelementptr %632[%663] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %662, %664 : i32, !llvm.ptr
%665 = llvm.load %642 : !llvm.ptr -> i64
%666 = arith.constant 1 : i32
%668 = arith.extsi %666 : i32 to i64
%667 = arith.addi %665, %668 : i64
llvm.store %667, %642 : i64, !llvm.ptr
%669 = llvm.load %651 : !llvm.ptr -> i64
%670 = arith.constant 1 : i32
%672 = arith.extsi %670 : i32 to i64
%671 = arith.subi %669, %672 : i64
%673 = llvm.load %651 : !llvm.ptr -> i64
%674 = llvm.getelementptr %618[%673] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %671, %674 : i64, !llvm.ptr
cf.br ^bb110
^bb109:
cf.br ^bb110
^bb110:
%676 = llvm.load %651 : !llvm.ptr -> i64
%677 = llvm.getelementptr %618[%676] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%675 = llvm.load %677 : !llvm.ptr -> i64
%678 = arith.constant 0 : i32
%679 = arith.extsi %678 : i32 to i64
%680 = llvm.mlir.constant(1 : i64) : i64
%681 = llvm.alloca %680 x i64 : (i64) -> !llvm.ptr
llvm.store %679, %681 : i64, !llvm.ptr
cf.br ^bb111
^bb111:
%682 = llvm.load %681 : !llvm.ptr -> i64
%683 = llvm.load %642 : !llvm.ptr -> i64
%684 = arith.cmpi slt, %682, %683 : i64
cf.cond_br %684, ^bb112, ^bb113
^bb112:
%686 = llvm.load %681 : !llvm.ptr -> i64
%687 = llvm.getelementptr %632[%686] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%685 = llvm.load %687 : !llvm.ptr -> i32
%688 = arith.extsi %685 : i32 to i64
%689 = llvm.load %651 : !llvm.ptr -> i64
%690 = arith.muli %689, %688 : i64
%691 = llvm.load %603 : !llvm.ptr -> i64
%692 = arith.cmpi sgt, %690, %691 : i64
cf.cond_br %692, ^bb114, ^bb115
^bb114:
cf.br ^bb113
^bb115:
cf.br ^bb116
^bb116:
%693 = arith.constant 1 : i32
%694 = arith.trunci %693 : i32 to i8
%695 = llvm.getelementptr %625[%690] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %694, %695 : i8, !llvm.ptr
%696 = llvm.load %651 : !llvm.ptr -> i64
%697 = arith.remsi %696, %688 : i64
%698 = arith.constant 0 : i32
%700 = arith.extsi %698 : i32 to i64
%699 = arith.cmpi eq, %697, %700 : i64
cf.cond_br %699, ^bb117, ^bb118
^bb117:
%701 = arith.muli %675, %688 : i64
%702 = llvm.getelementptr %618[%690] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %701, %702 : i64, !llvm.ptr
cf.br ^bb113
^bb118:
cf.br ^bb119
^bb119:
%703 = arith.constant 1 : i32
%705 = arith.extsi %703 : i32 to i64
%704 = arith.subi %688, %705 : i64
%706 = arith.muli %675, %704 : i64
%707 = llvm.getelementptr %618[%690] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %706, %707 : i64, !llvm.ptr
%708 = llvm.load %681 : !llvm.ptr -> i64
%709 = arith.constant 1 : i32
%711 = arith.extsi %709 : i32 to i64
%710 = arith.addi %708, %711 : i64
llvm.store %710, %681 : i64, !llvm.ptr
cf.br ^bb111
^bb113:
%712 = llvm.load %651 : !llvm.ptr -> i64
%713 = arith.constant 1 : i32
%715 = arith.extsi %713 : i32 to i64
%714 = arith.addi %712, %715 : i64
llvm.store %714, %651 : i64, !llvm.ptr
cf.br ^bb105
^bb107:
%717 = llvm.load %603 : !llvm.ptr -> i64
%718 = arith.constant 1 : i32
%720 = arith.extsi %718 : i32 to i64
%719 = arith.addi %717, %720 : i64
%721 = arith.constant 8 : i32
%722 = arith.extsi %721 : i32 to i64
%716 = func.call @calloc(%719, %722) : (i64, i64) -> !llvm.ptr
%723 = llvm.mlir.addressof @TS_pref0 : !llvm.ptr
llvm.store %716, %723 : !llvm.ptr, !llvm.ptr
%725 = llvm.load %603 : !llvm.ptr -> i64
%726 = arith.constant 1 : i32
%728 = arith.extsi %726 : i32 to i64
%727 = arith.addi %725, %728 : i64
%729 = arith.constant 8 : i32
%730 = arith.extsi %729 : i32 to i64
%724 = func.call @calloc(%727, %730) : (i64, i64) -> !llvm.ptr
%731 = llvm.mlir.addressof @TS_pref1 : !llvm.ptr
llvm.store %724, %731 : !llvm.ptr, !llvm.ptr
%733 = llvm.load %603 : !llvm.ptr -> i64
%734 = arith.constant 1 : i32
%736 = arith.extsi %734 : i32 to i64
%735 = arith.addi %733, %736 : i64
%737 = arith.constant 8 : i32
%738 = arith.extsi %737 : i32 to i64
%732 = func.call @calloc(%735, %738) : (i64, i64) -> !llvm.ptr
%739 = llvm.mlir.addressof @TS_pref2 : !llvm.ptr
llvm.store %732, %739 : !llvm.ptr, !llvm.ptr
%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
cf.br ^bb120
^bb120:
%744 = llvm.load %743 : !llvm.ptr -> i64
%745 = llvm.load %603 : !llvm.ptr -> i64
%746 = arith.cmpi sle, %744, %745 : i64
cf.cond_br %746, ^bb121, ^bb122
^bb121:
%748 = llvm.load %743 : !llvm.ptr -> i64
%749 = llvm.getelementptr %618[%748] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%747 = llvm.load %749 : !llvm.ptr -> i64
%750 = llvm.mlir.addressof @MOD : !llvm.ptr
%751 = llvm.load %750 : !llvm.ptr -> i64
%752 = arith.remsi %747, %751 : i64
%753 = llvm.load %743 : !llvm.ptr -> i64
%754 = llvm.mlir.addressof @MOD : !llvm.ptr
%755 = llvm.load %754 : !llvm.ptr -> i64
%756 = arith.remsi %753, %755 : i64
%758 = llvm.mlir.addressof @TS_pref0 : !llvm.ptr
%759 = llvm.load %758 : !llvm.ptr -> !llvm.ptr
%760 = llvm.load %743 : !llvm.ptr -> i64
%761 = arith.constant 1 : i32
%763 = arith.extsi %761 : i32 to i64
%762 = arith.subi %760, %763 : i64
%764 = llvm.getelementptr %759[%762] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%757 = llvm.load %764 : !llvm.ptr -> i64
%765 = arith.addi %757, %752 : i64
%766 = llvm.mlir.addressof @MOD : !llvm.ptr
%767 = llvm.load %766 : !llvm.ptr -> i64
%768 = arith.remsi %765, %767 : i64
%769 = llvm.mlir.addressof @TS_pref0 : !llvm.ptr
%770 = llvm.load %769 : !llvm.ptr -> !llvm.ptr
%771 = llvm.load %743 : !llvm.ptr -> i64
%772 = llvm.getelementptr %770[%771] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %768, %772 : i64, !llvm.ptr
%774 = llvm.mlir.addressof @TS_pref1 : !llvm.ptr
%775 = llvm.load %774 : !llvm.ptr -> !llvm.ptr
%776 = llvm.load %743 : !llvm.ptr -> i64
%777 = arith.constant 1 : i32
%779 = arith.extsi %777 : i32 to i64
%778 = arith.subi %776, %779 : i64
%780 = llvm.getelementptr %775[%778] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%773 = llvm.load %780 : !llvm.ptr -> i64
%781 = arith.muli %756, %752 : i64
%782 = arith.addi %773, %781 : i64
%783 = llvm.mlir.addressof @MOD : !llvm.ptr
%784 = llvm.load %783 : !llvm.ptr -> i64
%785 = arith.remsi %782, %784 : i64
%786 = llvm.mlir.addressof @TS_pref1 : !llvm.ptr
%787 = llvm.load %786 : !llvm.ptr -> !llvm.ptr
%788 = llvm.load %743 : !llvm.ptr -> i64
%789 = llvm.getelementptr %787[%788] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %785, %789 : i64, !llvm.ptr
%791 = llvm.mlir.addressof @TS_pref2 : !llvm.ptr
%792 = llvm.load %791 : !llvm.ptr -> !llvm.ptr
%793 = llvm.load %743 : !llvm.ptr -> i64
%794 = arith.constant 1 : i32
%796 = arith.extsi %794 : i32 to i64
%795 = arith.subi %793, %796 : i64
%797 = llvm.getelementptr %792[%795] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%790 = llvm.load %797 : !llvm.ptr -> i64
%798 = arith.muli %756, %756 : i64
%799 = llvm.mlir.addressof @MOD : !llvm.ptr
%800 = llvm.load %799 : !llvm.ptr -> i64
%801 = arith.remsi %798, %800 : i64
%802 = arith.muli %801, %752 : i64
%803 = arith.addi %790, %802 : i64
%804 = llvm.mlir.addressof @MOD : !llvm.ptr
%805 = llvm.load %804 : !llvm.ptr -> i64
%806 = arith.remsi %803, %805 : i64
%807 = llvm.mlir.addressof @TS_pref2 : !llvm.ptr
%808 = llvm.load %807 : !llvm.ptr -> !llvm.ptr
%809 = llvm.load %743 : !llvm.ptr -> i64
%810 = llvm.getelementptr %808[%809] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %806, %810 : i64, !llvm.ptr
%811 = llvm.load %743 : !llvm.ptr -> i64
%812 = arith.constant 1 : i32
%814 = arith.extsi %812 : i32 to i64
%813 = arith.addi %811, %814 : i64
llvm.store %813, %743 : i64, !llvm.ptr
cf.br ^bb120
^bb122:
%815 = arith.constant 1 : i32
%816 = arith.constant 21 : i32
%817 = arith.shli %815, %816 : i32
%818 = arith.extsi %817 : i32 to i64
%819 = llvm.mlir.addressof @c0cap : !llvm.ptr
llvm.store %818, %819 : i64, !llvm.ptr
%821 = llvm.mlir.addressof @c0cap : !llvm.ptr
%822 = llvm.load %821 : !llvm.ptr -> i64
%823 = arith.constant 8 : i32
%824 = arith.extsi %823 : i32 to i64
%820 = func.call @calloc(%822, %824) : (i64, i64) -> !llvm.ptr
%825 = llvm.mlir.addressof @c0k : !llvm.ptr
llvm.store %820, %825 : !llvm.ptr, !llvm.ptr
%827 = llvm.mlir.addressof @c0cap : !llvm.ptr
%828 = llvm.load %827 : !llvm.ptr -> i64
%829 = arith.constant 8 : i32
%830 = arith.extsi %829 : i32 to i64
%826 = func.call @calloc(%828, %830) : (i64, i64) -> !llvm.ptr
%831 = llvm.mlir.addressof @c0v : !llvm.ptr
llvm.store %826, %831 : !llvm.ptr, !llvm.ptr
%833 = llvm.mlir.addressof @c0cap : !llvm.ptr
%834 = llvm.load %833 : !llvm.ptr -> i64
%835 = arith.constant 1 : i32
%836 = arith.extsi %835 : i32 to i64
%832 = func.call @calloc(%834, %836) : (i64, i64) -> !llvm.ptr
%837 = llvm.mlir.addressof @c0u : !llvm.ptr
llvm.store %832, %837 : !llvm.ptr, !llvm.ptr
%838 = arith.constant 1 : i32
%839 = arith.constant 21 : i32
%840 = arith.shli %838, %839 : i32
%841 = arith.extsi %840 : i32 to i64
%842 = llvm.mlir.addressof @c1cap : !llvm.ptr
llvm.store %841, %842 : i64, !llvm.ptr
%844 = llvm.mlir.addressof @c1cap : !llvm.ptr
%845 = llvm.load %844 : !llvm.ptr -> i64
%846 = arith.constant 8 : i32
%847 = arith.extsi %846 : i32 to i64
%843 = func.call @calloc(%845, %847) : (i64, i64) -> !llvm.ptr
%848 = llvm.mlir.addressof @c1k : !llvm.ptr
llvm.store %843, %848 : !llvm.ptr, !llvm.ptr
%850 = llvm.mlir.addressof @c1cap : !llvm.ptr
%851 = llvm.load %850 : !llvm.ptr -> i64
%852 = arith.constant 8 : i32
%853 = arith.extsi %852 : i32 to i64
%849 = func.call @calloc(%851, %853) : (i64, i64) -> !llvm.ptr
%854 = llvm.mlir.addressof @c1v : !llvm.ptr
llvm.store %849, %854 : !llvm.ptr, !llvm.ptr
%856 = llvm.mlir.addressof @c1cap : !llvm.ptr
%857 = llvm.load %856 : !llvm.ptr -> i64
%858 = arith.constant 1 : i32
%859 = arith.extsi %858 : i32 to i64
%855 = func.call @calloc(%857, %859) : (i64, i64) -> !llvm.ptr
%860 = llvm.mlir.addressof @c1u : !llvm.ptr
llvm.store %855, %860 : !llvm.ptr, !llvm.ptr
%861 = arith.constant 1 : i32
%862 = arith.constant 21 : i32
%863 = arith.shli %861, %862 : i32
%864 = arith.extsi %863 : i32 to i64
%865 = llvm.mlir.addressof @c2cap : !llvm.ptr
llvm.store %864, %865 : i64, !llvm.ptr
%867 = llvm.mlir.addressof @c2cap : !llvm.ptr
%868 = llvm.load %867 : !llvm.ptr -> i64
%869 = arith.constant 8 : i32
%870 = arith.extsi %869 : i32 to i64
%866 = func.call @calloc(%868, %870) : (i64, i64) -> !llvm.ptr
%871 = llvm.mlir.addressof @c2k : !llvm.ptr
llvm.store %866, %871 : !llvm.ptr, !llvm.ptr
%873 = llvm.mlir.addressof @c2cap : !llvm.ptr
%874 = llvm.load %873 : !llvm.ptr -> i64
%875 = arith.constant 8 : i32
%876 = arith.extsi %875 : i32 to i64
%872 = func.call @calloc(%874, %876) : (i64, i64) -> !llvm.ptr
%877 = llvm.mlir.addressof @c2v : !llvm.ptr
llvm.store %872, %877 : !llvm.ptr, !llvm.ptr
%879 = llvm.mlir.addressof @c2cap : !llvm.ptr
%880 = llvm.load %879 : !llvm.ptr -> i64
%881 = arith.constant 1 : i32
%882 = arith.extsi %881 : i32 to i64
%878 = func.call @calloc(%880, %882) : (i64, i64) -> !llvm.ptr
%883 = llvm.mlir.addressof @c2u : !llvm.ptr
llvm.store %878, %883 : !llvm.ptr, !llvm.ptr
%884 = arith.constant 1 : i32
%885 = arith.constant 21 : i32
%886 = arith.shli %884, %885 : i32
%887 = arith.extsi %886 : i32 to i64
%888 = llvm.mlir.addressof @scap : !llvm.ptr
llvm.store %887, %888 : i64, !llvm.ptr
%890 = llvm.mlir.addressof @scap : !llvm.ptr
%891 = llvm.load %890 : !llvm.ptr -> i64
%892 = arith.constant 8 : i32
%893 = arith.extsi %892 : i32 to i64
%889 = func.call @calloc(%891, %893) : (i64, i64) -> !llvm.ptr
%894 = llvm.mlir.addressof @sk : !llvm.ptr
llvm.store %889, %894 : !llvm.ptr, !llvm.ptr
%896 = llvm.mlir.addressof @scap : !llvm.ptr
%897 = llvm.load %896 : !llvm.ptr -> i64
%898 = arith.constant 8 : i32
%899 = arith.extsi %898 : i32 to i64
%895 = func.call @calloc(%897, %899) : (i64, i64) -> !llvm.ptr
%900 = llvm.mlir.addressof @s_count : !llvm.ptr
llvm.store %895, %900 : !llvm.ptr, !llvm.ptr
%902 = llvm.mlir.addressof @scap : !llvm.ptr
%903 = llvm.load %902 : !llvm.ptr -> i64
%904 = arith.constant 8 : i32
%905 = arith.extsi %904 : i32 to i64
%901 = func.call @calloc(%903, %905) : (i64, i64) -> !llvm.ptr
%906 = llvm.mlir.addressof @s_xy : !llvm.ptr
llvm.store %901, %906 : !llvm.ptr, !llvm.ptr
%908 = llvm.mlir.addressof @scap : !llvm.ptr
%909 = llvm.load %908 : !llvm.ptr -> i64
%910 = arith.constant 8 : i32
%911 = arith.extsi %910 : i32 to i64
%907 = func.call @calloc(%909, %911) : (i64, i64) -> !llvm.ptr
%912 = llvm.mlir.addressof @s_pr : !llvm.ptr
llvm.store %907, %912 : !llvm.ptr, !llvm.ptr
%914 = llvm.mlir.addressof @scap : !llvm.ptr
%915 = llvm.load %914 : !llvm.ptr -> i64
%916 = arith.constant 1 : i32
%917 = arith.extsi %916 : i32 to i64
%913 = func.call @calloc(%915, %917) : (i64, i64) -> !llvm.ptr
%918 = llvm.mlir.addressof @su : !llvm.ptr
llvm.store %913, %918 : !llvm.ptr, !llvm.ptr
func.call @free(%618) : (!llvm.ptr) -> ()
func.call @free(%625) : (!llvm.ptr) -> ()
func.call @free(%632) : (!llvm.ptr) -> ()
func.return
}
func.func @ts_phi_sum(%arg0: i64) -> i64 {
%922 = llvm.mlir.addressof @TS_limit : !llvm.ptr
%923 = llvm.load %922 : !llvm.ptr -> i64
%924 = arith.cmpi sle, %arg0, %923 : i64
cf.cond_br %924, ^bb123, ^bb124
^bb123:
%926 = llvm.mlir.addressof @TS_pref0 : !llvm.ptr
%927 = llvm.load %926 : !llvm.ptr -> !llvm.ptr
%928 = llvm.getelementptr %927[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%925 = llvm.load %928 : !llvm.ptr -> i64
func.return %925 : i64
^bb124:
cf.br ^bb125
^bb125:
%930 = llvm.mlir.addressof @c0k : !llvm.ptr
%931 = llvm.load %930 : !llvm.ptr -> !llvm.ptr
%932 = llvm.mlir.addressof @c0v : !llvm.ptr
%933 = llvm.load %932 : !llvm.ptr -> !llvm.ptr
%934 = llvm.mlir.addressof @c0u : !llvm.ptr
%935 = llvm.load %934 : !llvm.ptr -> !llvm.ptr
%936 = llvm.mlir.addressof @c0cap : !llvm.ptr
%937 = llvm.load %936 : !llvm.ptr -> i64
%929 = func.call @ht_get(%931, %933, %935, %937, %arg0) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> i64
%938 = arith.constant 0 : i32
%940 = arith.extsi %938 : i32 to i64
%939 = arith.cmpi sge, %929, %940 : i64
cf.cond_br %939, ^bb126, ^bb127
^bb126:
func.return %929 : i64
^bb127:
cf.br ^bb128
^bb128:
%941 = func.call @s1(%arg0) : (i64) -> i64
%942 = llvm.mlir.constant(1 : i64) : i64
%943 = llvm.alloca %942 x i64 : (i64) -> !llvm.ptr
llvm.store %941, %943 : i64, !llvm.ptr
%944 = arith.constant 2 : i32
%945 = arith.extsi %944 : i32 to i64
%946 = llvm.mlir.constant(1 : i64) : i64
%947 = llvm.alloca %946 x i64 : (i64) -> !llvm.ptr
llvm.store %945, %947 : i64, !llvm.ptr
cf.br ^bb129
^bb129:
%948 = llvm.load %947 : !llvm.ptr -> i64
%949 = arith.cmpi sle, %948, %arg0 : i64
cf.cond_br %949, ^bb130, ^bb131
^bb130:
%950 = llvm.load %947 : !llvm.ptr -> i64
%951 = arith.divsi %arg0, %950 : i64
%952 = arith.divsi %arg0, %951 : i64
%954 = llvm.load %943 : !llvm.ptr -> i64
%955 = llvm.load %947 : !llvm.ptr -> i64
%956 = arith.subi %952, %955 : i64
%957 = arith.constant 1 : i32
%959 = arith.extsi %957 : i32 to i64
%958 = arith.addi %956, %959 : i64
%960 = llvm.mlir.addressof @MOD : !llvm.ptr
%961 = llvm.load %960 : !llvm.ptr -> i64
%962 = arith.remsi %958, %961 : i64
%963 = func.call @ts_phi_sum(%951) : (i64) -> i64
%964 = arith.muli %962, %963 : i64
%965 = llvm.mlir.addressof @MOD : !llvm.ptr
%966 = llvm.load %965 : !llvm.ptr -> i64
%967 = arith.remsi %964, %966 : i64
%968 = arith.subi %954, %967 : i64
%953 = func.call @norm(%968) : (i64) -> i64
llvm.store %953, %943 : i64, !llvm.ptr
%969 = arith.constant 1 : i32
%971 = arith.extsi %969 : i32 to i64
%970 = arith.addi %952, %971 : i64
llvm.store %970, %947 : i64, !llvm.ptr
cf.br ^bb129
^bb131:
%973 = llvm.mlir.addressof @c0k : !llvm.ptr
%974 = llvm.load %973 : !llvm.ptr -> !llvm.ptr
%975 = llvm.mlir.addressof @c0v : !llvm.ptr
%976 = llvm.load %975 : !llvm.ptr -> !llvm.ptr
%977 = llvm.mlir.addressof @c0u : !llvm.ptr
%978 = llvm.load %977 : !llvm.ptr -> !llvm.ptr
%979 = llvm.mlir.addressof @c0cap : !llvm.ptr
%980 = llvm.load %979 : !llvm.ptr -> i64
%981 = llvm.load %943 : !llvm.ptr -> i64
func.call @ht_put(%974, %976, %978, %980, %arg0, %981) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
%982 = llvm.load %943 : !llvm.ptr -> i64
func.return %982 : i64
}
func.func @ts_i_phi(%arg0: i64) -> i64 {
%983 = llvm.mlir.addressof @TS_limit : !llvm.ptr
%984 = llvm.load %983 : !llvm.ptr -> i64
%985 = arith.cmpi sle, %arg0, %984 : i64
cf.cond_br %985, ^bb132, ^bb133
^bb132:
%987 = llvm.mlir.addressof @TS_pref1 : !llvm.ptr
%988 = llvm.load %987 : !llvm.ptr -> !llvm.ptr
%989 = llvm.getelementptr %988[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%986 = llvm.load %989 : !llvm.ptr -> i64
func.return %986 : i64
^bb133:
cf.br ^bb134
^bb134:
%991 = llvm.mlir.addressof @c1k : !llvm.ptr
%992 = llvm.load %991 : !llvm.ptr -> !llvm.ptr
%993 = llvm.mlir.addressof @c1v : !llvm.ptr
%994 = llvm.load %993 : !llvm.ptr -> !llvm.ptr
%995 = llvm.mlir.addressof @c1u : !llvm.ptr
%996 = llvm.load %995 : !llvm.ptr -> !llvm.ptr
%997 = llvm.mlir.addressof @c1cap : !llvm.ptr
%998 = llvm.load %997 : !llvm.ptr -> i64
%990 = func.call @ht_get(%992, %994, %996, %998, %arg0) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> i64
%999 = arith.constant 0 : i32
%1001 = arith.extsi %999 : i32 to i64
%1000 = arith.cmpi sge, %990, %1001 : i64
cf.cond_br %1000, ^bb135, ^bb136
^bb135:
func.return %990 : i64
^bb136:
cf.br ^bb137
^bb137:
%1002 = func.call @s2(%arg0) : (i64) -> i64
%1003 = llvm.mlir.constant(1 : i64) : i64
%1004 = llvm.alloca %1003 x i64 : (i64) -> !llvm.ptr
llvm.store %1002, %1004 : i64, !llvm.ptr
%1005 = arith.constant 2 : i32
%1006 = arith.extsi %1005 : i32 to i64
%1007 = llvm.mlir.constant(1 : i64) : i64
%1008 = llvm.alloca %1007 x i64 : (i64) -> !llvm.ptr
llvm.store %1006, %1008 : i64, !llvm.ptr
cf.br ^bb138
^bb138:
%1009 = llvm.load %1008 : !llvm.ptr -> i64
%1010 = arith.cmpi sle, %1009, %arg0 : i64
cf.cond_br %1010, ^bb139, ^bb140
^bb139:
%1011 = llvm.load %1008 : !llvm.ptr -> i64
%1012 = arith.divsi %arg0, %1011 : i64
%1013 = arith.divsi %arg0, %1012 : i64
%1015 = llvm.load %1004 : !llvm.ptr -> i64
%1017 = llvm.load %1008 : !llvm.ptr -> i64
%1016 = func.call @range_s1(%1017, %1013) : (i64, i64) -> i64
%1018 = func.call @ts_i_phi(%1012) : (i64) -> i64
%1019 = arith.muli %1016, %1018 : i64
%1020 = llvm.mlir.addressof @MOD : !llvm.ptr
%1021 = llvm.load %1020 : !llvm.ptr -> i64
%1022 = arith.remsi %1019, %1021 : i64
%1023 = arith.subi %1015, %1022 : i64
%1014 = func.call @norm(%1023) : (i64) -> i64
llvm.store %1014, %1004 : i64, !llvm.ptr
%1024 = arith.constant 1 : i32
%1026 = arith.extsi %1024 : i32 to i64
%1025 = arith.addi %1013, %1026 : i64
llvm.store %1025, %1008 : i64, !llvm.ptr
cf.br ^bb138
^bb140:
%1028 = llvm.mlir.addressof @c1k : !llvm.ptr
%1029 = llvm.load %1028 : !llvm.ptr -> !llvm.ptr
%1030 = llvm.mlir.addressof @c1v : !llvm.ptr
%1031 = llvm.load %1030 : !llvm.ptr -> !llvm.ptr
%1032 = llvm.mlir.addressof @c1u : !llvm.ptr
%1033 = llvm.load %1032 : !llvm.ptr -> !llvm.ptr
%1034 = llvm.mlir.addressof @c1cap : !llvm.ptr
%1035 = llvm.load %1034 : !llvm.ptr -> i64
%1036 = llvm.load %1004 : !llvm.ptr -> i64
func.call @ht_put(%1029, %1031, %1033, %1035, %arg0, %1036) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
%1037 = llvm.load %1004 : !llvm.ptr -> i64
func.return %1037 : i64
}
func.func @ts_i2_phi(%arg0: i64) -> i64 {
%1038 = llvm.mlir.addressof @TS_limit : !llvm.ptr
%1039 = llvm.load %1038 : !llvm.ptr -> i64
%1040 = arith.cmpi sle, %arg0, %1039 : i64
cf.cond_br %1040, ^bb141, ^bb142
^bb141:
%1042 = llvm.mlir.addressof @TS_pref2 : !llvm.ptr
%1043 = llvm.load %1042 : !llvm.ptr -> !llvm.ptr
%1044 = llvm.getelementptr %1043[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1041 = llvm.load %1044 : !llvm.ptr -> i64
func.return %1041 : i64
^bb142:
cf.br ^bb143
^bb143:
%1046 = llvm.mlir.addressof @c2k : !llvm.ptr
%1047 = llvm.load %1046 : !llvm.ptr -> !llvm.ptr
%1048 = llvm.mlir.addressof @c2v : !llvm.ptr
%1049 = llvm.load %1048 : !llvm.ptr -> !llvm.ptr
%1050 = llvm.mlir.addressof @c2u : !llvm.ptr
%1051 = llvm.load %1050 : !llvm.ptr -> !llvm.ptr
%1052 = llvm.mlir.addressof @c2cap : !llvm.ptr
%1053 = llvm.load %1052 : !llvm.ptr -> i64
%1045 = func.call @ht_get(%1047, %1049, %1051, %1053, %arg0) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> i64
%1054 = arith.constant 0 : i32
%1056 = arith.extsi %1054 : i32 to i64
%1055 = arith.cmpi sge, %1045, %1056 : i64
cf.cond_br %1055, ^bb144, ^bb145
^bb144:
func.return %1045 : i64
^bb145:
cf.br ^bb146
^bb146:
%1057 = func.call @s3(%arg0) : (i64) -> i64
%1058 = llvm.mlir.constant(1 : i64) : i64
%1059 = llvm.alloca %1058 x i64 : (i64) -> !llvm.ptr
llvm.store %1057, %1059 : i64, !llvm.ptr
%1060 = arith.constant 2 : i32
%1061 = arith.extsi %1060 : i32 to i64
%1062 = llvm.mlir.constant(1 : i64) : i64
%1063 = llvm.alloca %1062 x i64 : (i64) -> !llvm.ptr
llvm.store %1061, %1063 : i64, !llvm.ptr
cf.br ^bb147
^bb147:
%1064 = llvm.load %1063 : !llvm.ptr -> i64
%1065 = arith.cmpi sle, %1064, %arg0 : i64
cf.cond_br %1065, ^bb148, ^bb149
^bb148:
%1066 = llvm.load %1063 : !llvm.ptr -> i64
%1067 = arith.divsi %arg0, %1066 : i64
%1068 = arith.divsi %arg0, %1067 : i64
%1070 = llvm.load %1059 : !llvm.ptr -> i64
%1072 = llvm.load %1063 : !llvm.ptr -> i64
%1071 = func.call @range_s2(%1072, %1068) : (i64, i64) -> i64
%1073 = func.call @ts_i2_phi(%1067) : (i64) -> i64
%1074 = arith.muli %1071, %1073 : i64
%1075 = llvm.mlir.addressof @MOD : !llvm.ptr
%1076 = llvm.load %1075 : !llvm.ptr -> i64
%1077 = arith.remsi %1074, %1076 : i64
%1078 = arith.subi %1070, %1077 : i64
%1069 = func.call @norm(%1078) : (i64) -> i64
llvm.store %1069, %1059 : i64, !llvm.ptr
%1079 = arith.constant 1 : i32
%1081 = arith.extsi %1079 : i32 to i64
%1080 = arith.addi %1068, %1081 : i64
llvm.store %1080, %1063 : i64, !llvm.ptr
cf.br ^bb147
^bb149:
%1083 = llvm.mlir.addressof @c2k : !llvm.ptr
%1084 = llvm.load %1083 : !llvm.ptr -> !llvm.ptr
%1085 = llvm.mlir.addressof @c2v : !llvm.ptr
%1086 = llvm.load %1085 : !llvm.ptr -> !llvm.ptr
%1087 = llvm.mlir.addressof @c2u : !llvm.ptr
%1088 = llvm.load %1087 : !llvm.ptr -> !llvm.ptr
%1089 = llvm.mlir.addressof @c2cap : !llvm.ptr
%1090 = llvm.load %1089 : !llvm.ptr -> i64
%1091 = llvm.load %1059 : !llvm.ptr -> i64
func.call @ht_put(%1084, %1086, %1088, %1090, %arg0, %1091) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
%1092 = llvm.load %1059 : !llvm.ptr -> i64
func.return %1092 : i64
}
func.func @ensure_stats(%arg0: i64) -> () {
%1094 = llvm.mlir.addressof @sk : !llvm.ptr
%1095 = llvm.load %1094 : !llvm.ptr -> !llvm.ptr
%1096 = llvm.mlir.addressof @s_count : !llvm.ptr
%1097 = llvm.load %1096 : !llvm.ptr -> !llvm.ptr
%1098 = llvm.mlir.addressof @su : !llvm.ptr
%1099 = llvm.load %1098 : !llvm.ptr -> !llvm.ptr
%1100 = llvm.mlir.addressof @scap : !llvm.ptr
%1101 = llvm.load %1100 : !llvm.ptr -> i64
%1093 = func.call @ht_get(%1095, %1097, %1099, %1101, %arg0) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> i64
%1102 = arith.constant 0 : i32
%1104 = arith.extsi %1102 : i32 to i64
%1103 = arith.cmpi sge, %1093, %1104 : i64
cf.cond_br %1103, ^bb150, ^bb151
^bb150:
func.return
^bb151:
cf.br ^bb152
^bb152:
%1105 = arith.constant 0 : i32
%1106 = arith.extsi %1105 : i32 to i64
%1107 = arith.constant 0 : i32
%1108 = arith.extsi %1107 : i32 to i64
%1109 = arith.constant 0 : i32
%1110 = arith.extsi %1109 : i32 to i64
%1111 = arith.constant 0 : i32
%1113 = arith.extsi %1111 : i32 to i64
%1112 = arith.cmpi sgt, %arg0, %1113 : i64
cf.cond_br %1112, ^bb153, ^bb154
^bb153:
%1115 = arith.constant 2 : i32
%1116 = func.call @ts_phi_sum(%arg0) : (i64) -> i64
%1118 = arith.extsi %1115 : i32 to i64
%1117 = arith.muli %1118, %1116 : i64
%1119 = arith.constant 1 : i32
%1121 = arith.extsi %1119 : i32 to i64
%1120 = arith.subi %1117, %1121 : i64
%1114 = func.call @norm(%1120) : (i64) -> i64
%1123 = arith.constant 3 : i32
%1124 = func.call @ts_i_phi(%arg0) : (i64) -> i64
%1126 = arith.extsi %1123 : i32 to i64
%1125 = arith.muli %1126, %1124 : i64
%1127 = arith.constant 1 : i32
%1129 = arith.extsi %1127 : i32 to i64
%1128 = arith.subi %1125, %1129 : i64
%1122 = func.call @norm(%1128) : (i64) -> i64
%1130 = func.call @ts_i2_phi(%arg0) : (i64) -> i64
%1132 = llvm.mlir.addressof @sk : !llvm.ptr
%1133 = llvm.load %1132 : !llvm.ptr -> !llvm.ptr
%1134 = llvm.mlir.addressof @s_count : !llvm.ptr
%1135 = llvm.load %1134 : !llvm.ptr -> !llvm.ptr
%1136 = llvm.mlir.addressof @su : !llvm.ptr
%1137 = llvm.load %1136 : !llvm.ptr -> !llvm.ptr
%1138 = llvm.mlir.addressof @scap : !llvm.ptr
%1139 = llvm.load %1138 : !llvm.ptr -> i64
func.call @ht_put(%1133, %1135, %1137, %1139, %arg0, %1114) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
%1141 = llvm.mlir.addressof @sk : !llvm.ptr
%1142 = llvm.load %1141 : !llvm.ptr -> !llvm.ptr
%1143 = llvm.mlir.addressof @s_xy : !llvm.ptr
%1144 = llvm.load %1143 : !llvm.ptr -> !llvm.ptr
%1145 = llvm.mlir.addressof @su : !llvm.ptr
%1146 = llvm.load %1145 : !llvm.ptr -> !llvm.ptr
%1147 = llvm.mlir.addressof @scap : !llvm.ptr
%1148 = llvm.load %1147 : !llvm.ptr -> i64
func.call @ht_put(%1142, %1144, %1146, %1148, %arg0, %1122) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
%1150 = llvm.mlir.addressof @sk : !llvm.ptr
%1151 = llvm.load %1150 : !llvm.ptr -> !llvm.ptr
%1152 = llvm.mlir.addressof @s_pr : !llvm.ptr
%1153 = llvm.load %1152 : !llvm.ptr -> !llvm.ptr
%1154 = llvm.mlir.addressof @su : !llvm.ptr
%1155 = llvm.load %1154 : !llvm.ptr -> !llvm.ptr
%1156 = llvm.mlir.addressof @scap : !llvm.ptr
%1157 = llvm.load %1156 : !llvm.ptr -> i64
func.call @ht_put(%1151, %1153, %1155, %1157, %arg0, %1130) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
cf.br ^bb155
^bb154:
%1159 = llvm.mlir.addressof @sk : !llvm.ptr
%1160 = llvm.load %1159 : !llvm.ptr -> !llvm.ptr
%1161 = llvm.mlir.addressof @s_count : !llvm.ptr
%1162 = llvm.load %1161 : !llvm.ptr -> !llvm.ptr
%1163 = llvm.mlir.addressof @su : !llvm.ptr
%1164 = llvm.load %1163 : !llvm.ptr -> !llvm.ptr
%1165 = llvm.mlir.addressof @scap : !llvm.ptr
%1166 = llvm.load %1165 : !llvm.ptr -> i64
%1167 = arith.constant 0 : i32
%1168 = arith.extsi %1167 : i32 to i64
func.call @ht_put(%1160, %1162, %1164, %1166, %arg0, %1168) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
%1170 = llvm.mlir.addressof @sk : !llvm.ptr
%1171 = llvm.load %1170 : !llvm.ptr -> !llvm.ptr
%1172 = llvm.mlir.addressof @s_xy : !llvm.ptr
%1173 = llvm.load %1172 : !llvm.ptr -> !llvm.ptr
%1174 = llvm.mlir.addressof @su : !llvm.ptr
%1175 = llvm.load %1174 : !llvm.ptr -> !llvm.ptr
%1176 = llvm.mlir.addressof @scap : !llvm.ptr
%1177 = llvm.load %1176 : !llvm.ptr -> i64
%1178 = arith.constant 0 : i32
%1179 = arith.extsi %1178 : i32 to i64
func.call @ht_put(%1171, %1173, %1175, %1177, %arg0, %1179) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
%1181 = llvm.mlir.addressof @sk : !llvm.ptr
%1182 = llvm.load %1181 : !llvm.ptr -> !llvm.ptr
%1183 = llvm.mlir.addressof @s_pr : !llvm.ptr
%1184 = llvm.load %1183 : !llvm.ptr -> !llvm.ptr
%1185 = llvm.mlir.addressof @su : !llvm.ptr
%1186 = llvm.load %1185 : !llvm.ptr -> !llvm.ptr
%1187 = llvm.mlir.addressof @scap : !llvm.ptr
%1188 = llvm.load %1187 : !llvm.ptr -> i64
%1189 = arith.constant 0 : i32
%1190 = arith.extsi %1189 : i32 to i64
func.call @ht_put(%1182, %1184, %1186, %1188, %arg0, %1190) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
cf.br ^bb155
^bb155:
func.return
}
func.func @get_stat_count(%arg0: i64) -> i64 {
%1192 = llvm.mlir.addressof @sk : !llvm.ptr
%1193 = llvm.load %1192 : !llvm.ptr -> !llvm.ptr
%1194 = llvm.mlir.addressof @s_count : !llvm.ptr
%1195 = llvm.load %1194 : !llvm.ptr -> !llvm.ptr
%1196 = llvm.mlir.addressof @su : !llvm.ptr
%1197 = llvm.load %1196 : !llvm.ptr -> !llvm.ptr
%1198 = llvm.mlir.addressof @scap : !llvm.ptr
%1199 = llvm.load %1198 : !llvm.ptr -> i64
%1191 = func.call @ht_get(%1193, %1195, %1197, %1199, %arg0) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> i64
func.return %1191 : i64
}
func.func @get_stat_xy(%arg0: i64) -> i64 {
%1201 = llvm.mlir.addressof @sk : !llvm.ptr
%1202 = llvm.load %1201 : !llvm.ptr -> !llvm.ptr
%1203 = llvm.mlir.addressof @s_xy : !llvm.ptr
%1204 = llvm.load %1203 : !llvm.ptr -> !llvm.ptr
%1205 = llvm.mlir.addressof @su : !llvm.ptr
%1206 = llvm.load %1205 : !llvm.ptr -> !llvm.ptr
%1207 = llvm.mlir.addressof @scap : !llvm.ptr
%1208 = llvm.load %1207 : !llvm.ptr -> i64
%1200 = func.call @ht_get(%1202, %1204, %1206, %1208, %arg0) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> i64
func.return %1200 : i64
}
func.func @get_stat_pr(%arg0: i64) -> i64 {
%1210 = llvm.mlir.addressof @sk : !llvm.ptr
%1211 = llvm.load %1210 : !llvm.ptr -> !llvm.ptr
%1212 = llvm.mlir.addressof @s_pr : !llvm.ptr
%1213 = llvm.load %1212 : !llvm.ptr -> !llvm.ptr
%1214 = llvm.mlir.addressof @su : !llvm.ptr
%1215 = llvm.load %1214 : !llvm.ptr -> !llvm.ptr
%1216 = llvm.mlir.addressof @scap : !llvm.ptr
%1217 = llvm.load %1216 : !llvm.ptr -> i64
%1209 = func.call @ht_get(%1211, %1213, %1215, %1217, %arg0) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> i64
func.return %1209 : i64
}
func.func @min64(%arg0: i64, %arg1: i64) -> i64 {
%1218 = arith.cmpi slt, %arg0, %arg1 : i64
cf.cond_br %1218, ^bb156, ^bb157
^bb156:
func.return %arg0 : i64
^bb157:
cf.br ^bb158
^bb158:
func.return %arg1 : i64
}
func.func @titanic_sets(%arg0: i64) -> i64 {
%1219 = arith.constant 1 : i32
%1221 = arith.extsi %1219 : i32 to i64
%1220 = arith.addi %arg0, %1221 : i64
%1222 = arith.extsi %1220 : i64 to i128
%1223 = arith.extsi %1220 : i64 to i128
%1225 = arith.trunci %1222 : i128 to i64
%1226 = arith.trunci %1223 : i128 to i64
%1224 = arith.muli %1225, %1226 : i64
%1227 = arith.extsi %1224 : i64 to i128
%1229 = arith.constant 2 : i32
%1230 = arith.extsi %1229 : i32 to i64
%1228 = func.call @mod_pow_128(%1230, %1227) : (i64, i128) -> i64
%1232 = arith.constant 1 : i32
%1233 = llvm.mlir.addressof @MOD : !llvm.ptr
%1234 = llvm.load %1233 : !llvm.ptr -> i64
%1235 = arith.extsi %1234 : i64 to i128
%1237 = arith.trunci %1227 : i128 to i64
%1238 = arith.trunci %1235 : i128 to i64
%1236 = arith.remsi %1237, %1238 : i64
%1240 = arith.extsi %1232 : i32 to i64
%1239 = arith.addi %1240, %1236 : i64
%1231 = func.call @norm(%1239) : (i64) -> i64
%1241 = arith.constant 2 : i32
%1243 = arith.extsi %1241 : i32 to i64
%1242 = arith.cmpi slt, %arg0, %1243 : i64
cf.cond_br %1242, ^bb159, ^bb160
^bb159:
%1245 = arith.subi %1228, %1231 : i64
%1244 = func.call @norm(%1245) : (i64) -> i64
func.return %1244 : i64
^bb160:
cf.br ^bb161
^bb161:
%1246 = arith.constant 2000000 : i32
%1247 = arith.extsi %1246 : i32 to i64
%1249 = arith.constant 8 : i32
%1250 = arith.extsi %1249 : i32 to i64
%1248 = func.call @calloc(%1247, %1250) : (i64, i64) -> !llvm.ptr
%1252 = arith.constant 8 : i32
%1253 = arith.extsi %1252 : i32 to i64
%1251 = func.call @calloc(%1247, %1253) : (i64, i64) -> !llvm.ptr
%1255 = arith.constant 8 : i32
%1256 = arith.extsi %1255 : i32 to i64
%1254 = func.call @calloc(%1247, %1256) : (i64, i64) -> !llvm.ptr
%1258 = arith.constant 8 : i32
%1259 = arith.extsi %1258 : i32 to i64
%1257 = func.call @calloc(%1247, %1259) : (i64, i64) -> !llvm.ptr
%1260 = arith.constant 0 : i32
%1261 = arith.extsi %1260 : i32 to i64
%1262 = llvm.mlir.constant(1 : i64) : i64
%1263 = llvm.alloca %1262 x i64 : (i64) -> !llvm.ptr
llvm.store %1261, %1263 : i64, !llvm.ptr
%1264 = arith.constant 2 : i32
%1265 = arith.extsi %1264 : i32 to i64
%1266 = llvm.mlir.constant(1 : i64) : i64
%1267 = llvm.alloca %1266 x i64 : (i64) -> !llvm.ptr
llvm.store %1265, %1267 : i64, !llvm.ptr
cf.br ^bb162
^bb162:
%1268 = llvm.load %1267 : !llvm.ptr -> i64
%1269 = arith.cmpi sle, %1268, %arg0 : i64
cf.cond_br %1269, ^bb163, ^bb164
^bb163:
%1270 = llvm.load %1267 : !llvm.ptr -> i64
%1271 = arith.divsi %arg0, %1270 : i64
%1272 = arith.constant 0 : i32
%1273 = arith.extsi %1272 : i32 to i64
%1274 = llvm.load %1267 : !llvm.ptr -> i64
%1275 = arith.cmpi slt, %1274, %arg0 : i64
%1276 = scf.if %1275 -> (i64) {
%1277 = llvm.load %1267 : !llvm.ptr -> i64
%1278 = arith.constant 1 : i32
%1280 = arith.extsi %1278 : i32 to i64
%1279 = arith.addi %1277, %1280 : i64
%1281 = arith.divsi %arg0, %1279 : i64
scf.yield %1281 : i64
} else {
scf.yield %1273 : i64
}
%1282 = arith.divsi %arg0, %1271 : i64
%1283 = arith.constant 0 : i32
%1284 = arith.extsi %1283 : i32 to i64
%1285 = arith.constant 0 : i32
%1287 = arith.extsi %1285 : i32 to i64
%1286 = arith.cmpi ne, %1276, %1287 : i64
%1288 = scf.if %1286 -> (i64) {
%1289 = arith.divsi %arg0, %1276 : i64
%1290 = arith.constant 1 : i32
%1292 = arith.extsi %1290 : i32 to i64
%1291 = arith.subi %1289, %1292 : i64
scf.yield %1291 : i64
} else {
scf.yield %arg0 : i64
}
%1293 = func.call @min64(%1282, %1288) : (i64, i64) -> i64
%1294 = llvm.load %1267 : !llvm.ptr -> i64
%1295 = llvm.load %1263 : !llvm.ptr -> i64
%1296 = llvm.getelementptr %1248[%1295] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1294, %1296 : i64, !llvm.ptr
%1297 = llvm.load %1263 : !llvm.ptr -> i64
%1298 = llvm.getelementptr %1251[%1297] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1293, %1298 : i64, !llvm.ptr
%1299 = llvm.load %1263 : !llvm.ptr -> i64
%1300 = llvm.getelementptr %1254[%1299] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1271, %1300 : i64, !llvm.ptr
%1301 = llvm.load %1263 : !llvm.ptr -> i64
%1302 = llvm.getelementptr %1257[%1301] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1276, %1302 : i64, !llvm.ptr
%1303 = llvm.load %1263 : !llvm.ptr -> i64
%1304 = arith.constant 1 : i32
%1306 = arith.extsi %1304 : i32 to i64
%1305 = arith.addi %1303, %1306 : i64
llvm.store %1305, %1263 : i64, !llvm.ptr
func.call @ensure_stats(%1271) : (i64) -> ()
%1308 = arith.constant 0 : i32
%1310 = arith.extsi %1308 : i32 to i64
%1309 = arith.cmpi ne, %1276, %1310 : i64
cf.cond_br %1309, ^bb165, ^bb166
^bb165:
func.call @ensure_stats(%1276) : (i64) -> ()
cf.br ^bb167
^bb166:
cf.br ^bb167
^bb167:
%1312 = arith.constant 1 : i32
%1314 = arith.extsi %1312 : i32 to i64
%1313 = arith.addi %1293, %1314 : i64
llvm.store %1313, %1267 : i64, !llvm.ptr
cf.br ^bb162
^bb164:
%1315 = llvm.mlir.addressof @MOD : !llvm.ptr
%1316 = llvm.load %1315 : !llvm.ptr -> i64
%1317 = arith.remsi %1220, %1316 : i64
%1318 = arith.muli %1317, %1317 : i64
%1319 = llvm.mlir.addressof @MOD : !llvm.ptr
%1320 = llvm.load %1319 : !llvm.ptr -> i64
%1321 = arith.remsi %1318, %1320 : i64
%1322 = arith.constant 0 : i32
%1323 = arith.extsi %1322 : i32 to i64
%1324 = llvm.mlir.constant(1 : i64) : i64
%1325 = llvm.alloca %1324 x i64 : (i64) -> !llvm.ptr
llvm.store %1323, %1325 : i64, !llvm.ptr
%1326 = arith.constant 0 : i32
%1327 = arith.extsi %1326 : i32 to i64
%1328 = llvm.mlir.constant(1 : i64) : i64
%1329 = llvm.alloca %1328 x i64 : (i64) -> !llvm.ptr
llvm.store %1327, %1329 : i64, !llvm.ptr
cf.br ^bb168
^bb168:
%1330 = llvm.load %1329 : !llvm.ptr -> i64
%1331 = llvm.load %1263 : !llvm.ptr -> i64
%1332 = arith.cmpi slt, %1330, %1331 : i64
cf.cond_br %1332, ^bb169, ^bb170
^bb169:
%1334 = llvm.load %1329 : !llvm.ptr -> i64
%1335 = llvm.getelementptr %1254[%1334] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1333 = llvm.load %1335 : !llvm.ptr -> i64
%1337 = llvm.load %1329 : !llvm.ptr -> i64
%1338 = llvm.getelementptr %1257[%1337] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1336 = llvm.load %1338 : !llvm.ptr -> i64
%1339 = func.call @get_stat_count(%1333) : (i64) -> i64
%1340 = func.call @get_stat_xy(%1333) : (i64) -> i64
%1341 = func.call @get_stat_pr(%1333) : (i64) -> i64
%1342 = arith.constant 0 : i32
%1343 = arith.extsi %1342 : i32 to i64
%1344 = arith.constant 0 : i32
%1345 = arith.extsi %1344 : i32 to i64
%1346 = arith.constant 0 : i32
%1347 = arith.extsi %1346 : i32 to i64
%1348 = arith.constant 0 : i32
%1350 = arith.extsi %1348 : i32 to i64
%1349 = arith.cmpi ne, %1336, %1350 : i64
%1351, %1352, %1353 = scf.if %1349 -> (i64, i64, i64) {
%1354 = func.call @get_stat_count(%1336) : (i64) -> i64
%1355 = func.call @get_stat_xy(%1336) : (i64) -> i64
%1356 = func.call @get_stat_pr(%1336) : (i64) -> i64
scf.yield %1354, %1355, %1356 : i64, i64, i64
} else {
scf.yield %1343, %1345, %1347 : i64, i64, i64
}
%1358 = arith.subi %1341, %1353 : i64
%1357 = func.call @norm(%1358) : (i64) -> i64
%1361 = arith.subi %1352, %1340 : i64
%1360 = func.call @norm(%1361) : (i64) -> i64
%1362 = arith.muli %1317, %1360 : i64
%1363 = llvm.mlir.addressof @MOD : !llvm.ptr
%1364 = llvm.load %1363 : !llvm.ptr -> i64
%1365 = arith.remsi %1362, %1364 : i64
%1366 = arith.constant 2 : i32
%1368 = arith.extsi %1366 : i32 to i64
%1367 = arith.muli %1368, %1353 : i64
%1369 = llvm.mlir.addressof @MOD : !llvm.ptr
%1370 = llvm.load %1369 : !llvm.ptr -> i64
%1371 = arith.remsi %1367, %1370 : i64
%1372 = arith.subi %1365, %1371 : i64
%1359 = func.call @norm(%1372) : (i64) -> i64
%1375 = arith.subi %1339, %1351 : i64
%1374 = func.call @norm(%1375) : (i64) -> i64
%1376 = arith.muli %1321, %1374 : i64
%1377 = llvm.mlir.addressof @MOD : !llvm.ptr
%1378 = llvm.load %1377 : !llvm.ptr -> i64
%1379 = arith.remsi %1376, %1378 : i64
%1380 = arith.muli %1317, %1352 : i64
%1381 = llvm.mlir.addressof @MOD : !llvm.ptr
%1382 = llvm.load %1381 : !llvm.ptr -> i64
%1383 = arith.remsi %1380, %1382 : i64
%1384 = arith.addi %1379, %1383 : i64
%1385 = arith.subi %1384, %1353 : i64
%1373 = func.call @norm(%1385) : (i64) -> i64
%1386 = arith.constant 2 : i32
%1388 = arith.extsi %1386 : i32 to i64
%1387 = arith.muli %1388, %1357 : i64
%1389 = llvm.mlir.addressof @MOD : !llvm.ptr
%1390 = llvm.load %1389 : !llvm.ptr -> i64
%1391 = arith.remsi %1387, %1390 : i64
%1392 = arith.constant 2 : i32
%1394 = arith.extsi %1392 : i32 to i64
%1393 = arith.muli %1394, %1359 : i64
%1395 = llvm.mlir.addressof @MOD : !llvm.ptr
%1396 = llvm.load %1395 : !llvm.ptr -> i64
%1397 = arith.remsi %1393, %1396 : i64
%1398 = arith.constant 2 : i32
%1400 = arith.extsi %1398 : i32 to i64
%1399 = arith.muli %1400, %1373 : i64
%1401 = arith.constant 2 : i32
%1403 = arith.extsi %1401 : i32 to i64
%1402 = arith.muli %1403, %1317 : i64
%1404 = arith.addi %1399, %1402 : i64
%1405 = llvm.mlir.addressof @MOD : !llvm.ptr
%1406 = llvm.load %1405 : !llvm.ptr -> i64
%1407 = arith.remsi %1404, %1406 : i64
%1409 = llvm.load %1329 : !llvm.ptr -> i64
%1410 = llvm.getelementptr %1248[%1409] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1408 = llvm.load %1410 : !llvm.ptr -> i64
%1412 = llvm.load %1329 : !llvm.ptr -> i64
%1413 = llvm.getelementptr %1251[%1412] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1411 = llvm.load %1413 : !llvm.ptr -> i64
%1415 = arith.constant 2 : i32
%1416 = arith.extsi %1415 : i32 to i64
%1414 = func.call @mod_pow_64(%1416, %1408) : (i64, i64) -> i64
%1418 = arith.constant 2 : i32
%1419 = arith.constant 1 : i32
%1421 = arith.extsi %1419 : i32 to i64
%1420 = arith.addi %1411, %1421 : i64
%1422 = arith.extsi %1418 : i32 to i64
%1417 = func.call @mod_pow_64(%1422, %1420) : (i64, i64) -> i64
%1424 = arith.subi %1417, %1414 : i64
%1423 = func.call @norm(%1424) : (i64) -> i64
%1426 = func.call @pref_k_pow2(%1411, %1417) : (i64, i64) -> i64
%1428 = arith.constant 1 : i32
%1430 = arith.extsi %1428 : i32 to i64
%1429 = arith.subi %1408, %1430 : i64
%1427 = func.call @pref_k_pow2(%1429, %1414) : (i64, i64) -> i64
%1431 = arith.subi %1426, %1427 : i64
%1425 = func.call @norm(%1431) : (i64) -> i64
%1433 = func.call @pref_k2_pow2(%1411, %1417) : (i64, i64) -> i64
%1435 = arith.constant 1 : i32
%1437 = arith.extsi %1435 : i32 to i64
%1436 = arith.subi %1408, %1437 : i64
%1434 = func.call @pref_k2_pow2(%1436, %1414) : (i64, i64) -> i64
%1438 = arith.subi %1433, %1434 : i64
%1432 = func.call @norm(%1438) : (i64) -> i64
%1439 = arith.muli %1391, %1432 : i64
%1440 = arith.muli %1397, %1425 : i64
%1441 = arith.addi %1439, %1440 : i64
%1442 = arith.muli %1407, %1423 : i64
%1443 = arith.addi %1441, %1442 : i64
%1444 = llvm.mlir.addressof @MOD : !llvm.ptr
%1445 = llvm.load %1444 : !llvm.ptr -> i64
%1446 = arith.remsi %1443, %1445 : i64
%1447 = func.call @range_s1(%1408, %1411) : (i64, i64) -> i64
%1448 = func.call @range_s2(%1408, %1411) : (i64, i64) -> i64
%1449 = func.call @range_s3(%1408, %1411) : (i64, i64) -> i64
%1450 = arith.subi %1411, %1408 : i64
%1451 = arith.constant 1 : i32
%1453 = arith.extsi %1451 : i32 to i64
%1452 = arith.addi %1450, %1453 : i64
%1454 = llvm.mlir.addressof @MOD : !llvm.ptr
%1455 = llvm.load %1454 : !llvm.ptr -> i64
%1456 = arith.remsi %1452, %1455 : i64
%1457 = arith.addi %1449, %1448 : i64
%1458 = llvm.mlir.addressof @MOD : !llvm.ptr
%1459 = llvm.load %1458 : !llvm.ptr -> i64
%1460 = arith.remsi %1457, %1459 : i64
%1461 = arith.muli %1391, %1460 : i64
%1462 = arith.addi %1448, %1447 : i64
%1463 = llvm.mlir.addressof @MOD : !llvm.ptr
%1464 = llvm.load %1463 : !llvm.ptr -> i64
%1465 = arith.remsi %1462, %1464 : i64
%1466 = arith.muli %1397, %1465 : i64
%1467 = arith.addi %1461, %1466 : i64
%1468 = arith.addi %1447, %1456 : i64
%1469 = llvm.mlir.addressof @MOD : !llvm.ptr
%1470 = llvm.load %1469 : !llvm.ptr -> i64
%1471 = arith.remsi %1468, %1470 : i64
%1472 = arith.muli %1407, %1471 : i64
%1473 = arith.addi %1467, %1472 : i64
%1474 = llvm.mlir.addressof @MOD : !llvm.ptr
%1475 = llvm.load %1474 : !llvm.ptr -> i64
%1476 = arith.remsi %1473, %1475 : i64
%1478 = llvm.load %1325 : !llvm.ptr -> i64
%1479 = arith.addi %1478, %1446 : i64
%1480 = arith.subi %1479, %1476 : i64
%1477 = func.call @norm(%1480) : (i64) -> i64
llvm.store %1477, %1325 : i64, !llvm.ptr
%1481 = llvm.load %1329 : !llvm.ptr -> i64
%1482 = arith.constant 1 : i32
%1484 = arith.extsi %1482 : i32 to i64
%1483 = arith.addi %1481, %1484 : i64
llvm.store %1483, %1329 : i64, !llvm.ptr
cf.br ^bb168
^bb170:
func.call @free(%1248) : (!llvm.ptr) -> ()
func.call @free(%1251) : (!llvm.ptr) -> ()
func.call @free(%1254) : (!llvm.ptr) -> ()
func.call @free(%1257) : (!llvm.ptr) -> ()
%1490 = arith.subi %1228, %1231 : i64
%1491 = llvm.load %1325 : !llvm.ptr -> i64
%1492 = arith.subi %1490, %1491 : i64
%1489 = func.call @norm(%1492) : (i64) -> i64
func.return %1489 : i64
}
func.func @main() -> i32 {
%1493 = llvm.mlir.addressof @DEFAULT_N : !llvm.ptr
%1494 = llvm.load %1493 : !llvm.ptr -> i64
%1495 = llvm.mlir.constant(1 : i64) : i64
%1496 = llvm.alloca %1495 x i64 : (i64) -> !llvm.ptr
llvm.store %1494, %1496 : i64, !llvm.ptr
%1497 = llvm.load %1496 : !llvm.ptr -> i64
%1498 = arith.constant 100000 : i32
%1500 = arith.extsi %1498 : i32 to i64
%1499 = arith.cmpi slt, %1497, %1500 : i64
cf.cond_br %1499, ^bb171, ^bb172
^bb171:
%1501 = arith.constant 100000 : i32
%1502 = arith.extsi %1501 : i32 to i64
llvm.store %1502, %1496 : i64, !llvm.ptr
cf.br ^bb173
^bb172:
cf.br ^bb173
^bb173:
%1504 = llvm.load %1496 : !llvm.ptr -> i64
func.call @build_totient_sums(%1504) : (i64) -> ()
%1505 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1507 = llvm.mlir.addressof @DEFAULT_N : !llvm.ptr
%1508 = llvm.load %1507 : !llvm.ptr -> i64
%1506 = func.call @titanic_sets(%1508) : (i64) -> i64
%1509 = llvm.call @printf(%1505, %1506) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1510 = arith.constant 0 : i32
func.return %1510 : i32
}
}