Problem 994
T(1234*10^8, 2345*10^8) mod 1e9+7. Totient sieve and Du Jiao summatory recursion.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n log log n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Sieve-based totient computation |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 994: Counting Triangles
# T(1234*10^8, 2345*10^8) mod 1e9+7.
# Totient sieve and Du Jiao summatory recursion.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
const MOD: i64 = 1000000007
let mut INV2: i64 = 0
let mut INV6: i64 = 0
# Totient prefix global state
let mut tp_limit: i64 = 0
let mut tp_pref0: ptr<i32> = null
let mut tp_pref1: ptr<i32> = null
let mut tp_pref2: ptr<i32> = null
let mut tp_scratch: ptr<i64> = null
let mut tp_depth: i64 = 0
# Cache (open addressing hash table)
let mut cache_key: ptr<i64> = null
let mut cache_f0: ptr<i64> = null
let mut cache_f1: ptr<i64> = null
let mut cache_f2: ptr<i64> = null
let mut cache_used: ptr<i8> = null
let mut cache_size: i64 = 0
let mut cache_count: i64 = 0
# MOD < 2^30, so a*b < 2^60 fits in i64 (avoids slow i128 division).
function mulmod(a: i64, b: i64) -> i64 {
return (a * b) % MOD
}
function mod_pow(a0: i64, e0: i64) -> i64 {
let mut a: i64 = a0 % MOD
if a < 0 { a = a + MOD }
let mut r: i64 = 1
let mut e: i64 = e0
while e > 0 {
if (e & 1) != 0 { r = mulmod(r, a) }
a = mulmod(a, a)
e = e >> 1
}
return r
}
function p1_func(n: i64) -> i64 {
let a: i64 = n % MOD
let b: i64 = (a + 1) % MOD
return mulmod(mulmod(a, b), INV2)
}
function p2_func(n: i64) -> i64 {
let a: i64 = n % MOD
let b: i64 = (a + 1) % MOD
let c: i64 = (2 * a + 1) % MOD
return mulmod(mulmod(mulmod(a, b), c), INV6)
}
function p3_func(n: i64) -> i64 {
let s: i64 = p1_func(n)
return mulmod(s, s)
}
function c2_mod(x: i64) -> i64 {
let a: i64 = x % MOD
let b: i64 = (a - 1 + MOD) % MOD
return mulmod(mulmod(a, b), INV2)
}
function c3_mod(x: i64) -> i64 {
let a: i64 = x % MOD
let b: i64 = (a - 1 + MOD) % MOD
let c: i64 = (a - 2 + MOD) % MOD
return mulmod(mulmod(mulmod(a, b), c), INV6)
}
function cache_hash(key: i64, size: i64) -> i64 {
# i64 wrapping multiply (C semantics) avoids slow i128 division.
let mut r: i64 = (key * 2654435761) % size
if r < 0 { r = r + size }
return r
}
function cache_resize(new_size: i64) -> void {
let old_key: ptr<i64> = cache_key
let old_f0: ptr<i64> = cache_f0
let old_f1: ptr<i64> = cache_f1
let old_f2: ptr<i64> = cache_f2
let old_used: ptr<i8> = cache_used
let old_s: i64 = cache_size
cache_key = calloc(new_size, 8) as ptr<i64>
cache_f0 = calloc(new_size, 8) as ptr<i64>
cache_f1 = calloc(new_size, 8) as ptr<i64>
cache_f2 = calloc(new_size, 8) as ptr<i64>
cache_used = calloc(new_size, 1) as ptr<i8>
cache_size = new_size
cache_count = 0
let mut i: i64 = 0
while i < old_s {
if old_used[i] != 0 {
cache_put(old_key[i], old_f0[i], old_f1[i], old_f2[i])
}
i = i + 1
}
free(old_key as ptr<void>)
free(old_f0 as ptr<void>)
free(old_f1 as ptr<void>)
free(old_f2 as ptr<void>)
free(old_used as ptr<void>)
}
function cache_put(key: i64, f0: i64, f1: i64, f2: i64) -> void {
if cache_count * 2 >= cache_size {
cache_resize(cache_size * 2)
}
let mut idx: i64 = cache_hash(key, cache_size)
while cache_used[idx] != 0 {
if cache_key[idx] == key {
cache_f0[idx] = f0
cache_f1[idx] = f1
cache_f2[idx] = f2
return
}
idx = idx + 1
if idx >= cache_size { idx = 0 }
}
cache_key[idx] = key
cache_f0[idx] = f0
cache_f1[idx] = f1
cache_f2[idx] = f2
cache_used[idx] = 1
cache_count = cache_count + 1
}
function cache_get(key: i64, out: ptr<i64>) -> bool {
let mut idx: i64 = cache_hash(key, cache_size)
while cache_used[idx] != 0 {
if cache_key[idx] == key {
out[0] = cache_f0[idx]
out[1] = cache_f1[idx]
out[2] = cache_f2[idx]
return true
}
idx = idx + 1
if idx >= cache_size { idx = 0 }
}
return false
}
function tp_values(n: i64, out: ptr<i64>) -> void {
if n <= tp_limit {
out[0] = tp_pref0[n] as i64
out[1] = tp_pref1[n] as i64
out[2] = tp_pref2[n] as i64
return
}
if cache_get(n, out) { return }
let mut f0: i64 = p1_func(n)
let mut f1: i64 = p2_func(n)
let mut f2: i64 = p3_func(n)
let mut l: i64 = 2
while l <= n {
let q: i64 = n / l
let r: i64 = n / q
let sum0: i64 = (r - l + 1) % MOD
let sum1: i64 = (p1_func(r) - p1_func(l - 1) + MOD) % MOD
let sum2: i64 = (p2_func(r) - p2_func(l - 1) + MOD) % MOD
let depth: i64 = tp_depth
let sub_out: ptr<i64> = tp_scratch + depth * 3
tp_depth = tp_depth + 1
tp_values(q, sub_out)
tp_depth = tp_depth - 1
f0 = (f0 - mulmod(sum0, sub_out[0]) + MOD) % MOD
f1 = (f1 - mulmod(sum1, sub_out[1]) + MOD) % MOD
f2 = (f2 - mulmod(sum2, sub_out[2]) + MOD) % MOD
l = r + 1
}
out[0] = f0
out[1] = f1
out[2] = f2
cache_put(n, f0, f1, f2)
}
function tp_init(limit: i64) -> void {
tp_limit = limit
let phi: ptr<i32> = malloc((limit + 1) * 4) as ptr<i32>
let mut i: i64 = 0
while i <= limit {
phi[i] = i as i32
i = i + 1
}
let mut p: i64 = 2
while p <= limit {
if phi[p] as i64 == p {
let mut j: i64 = p
while j <= limit {
phi[j] = phi[j] - phi[j] / (p as i32)
j = j + p
}
}
p = p + 1
}
tp_pref0 = calloc(limit + 1, 4) as ptr<i32>
tp_pref1 = calloc(limit + 1, 4) as ptr<i32>
tp_pref2 = calloc(limit + 1, 4) as ptr<i32>
let mut s0: i64 = 0
let mut s1: i64 = 0
let mut s2: i64 = 0
i = 1
while i <= limit {
let ph: i64 = phi[i] as i64
let im: i64 = i % MOD
s0 = (s0 + ph) % MOD
s1 = (s1 + im * ph % MOD) % MOD
s2 = (s2 + im * im % MOD * ph % MOD) % MOD
tp_pref0[i] = s0 as i32
tp_pref1[i] = s1 as i32
tp_pref2[i] = s2 as i32
i = i + 1
}
free(phi as ptr<void>)
cache_size = 1 << 20
cache_count = 0
cache_key = calloc(cache_size, 8) as ptr<i64>
cache_f0 = calloc(cache_size, 8) as ptr<i64>
cache_f1 = calloc(cache_size, 8) as ptr<i64>
cache_f2 = calloc(cache_size, 8) as ptr<i64>
cache_used = calloc(cache_size, 1) as ptr<i8>
tp_scratch = calloc(768, 8) as ptr<i64>
tp_depth = 0
}
function nonconcurrent_candidate_count(m: i64, n: i64) -> i64 {
let mm: i64 = m % MOD
let mm1: i64 = (mm - 1 + MOD) % MOD
let nn: i64 = n % MOD
let nn1: i64 = (nn - 1 + MOD) % MOD
let nn1p: i64 = (nn + 1) % MOD
let two_same: i64 = mulmod(mulmod(mulmod(mulmod(mulmod(mm, mm1), nn), nn1), nn1p), INV6)
let diff: i64 = (c3_mod(n + 2) - (n % MOD) + MOD) % MOD
let distinct_val: i64 = mulmod(c3_mod(m), diff)
return (two_same + distinct_val) % MOD
}
function weighted_gcd_sum(m: i64, n: i64) -> i64 {
let m1: i64 = m - 1
let n1: i64 = n - 1
let upper: i64 = if m1 < n1 { m1 } else { n1 }
let mut total: i64 = 0
let r_out: ptr<i64> = tp_scratch + 0 * 3
let l_out: ptr<i64> = tp_scratch + 1 * 3
tp_depth = 2
let mut l: i64 = 1
while l <= upper {
let qm: i64 = m1 / l
let qn: i64 = n1 / l
let mut r: i64 = m1 / qm
if n1 / qn < r { r = n1 / qn }
if upper < r { r = upper }
tp_values(r, r_out)
tp_values(l - 1, l_out)
let s0: i64 = (r_out[0] - l_out[0] + MOD) % MOD
let s1: i64 = (r_out[1] - l_out[1] + MOD) % MOD
let s2: i64 = (r_out[2] - l_out[2] + MOD) % MOD
let qm_mod: i64 = qm % MOD
let qn_mod: i64 = qn % MOD
let a0m: i64 = mulmod(qm_mod, m % MOD)
let a1m: i64 = mulmod(mulmod(-qm_mod + MOD, (qm + 1) % MOD), INV2)
let a0n: i64 = mulmod(qn_mod, n % MOD)
let a1n: i64 = mulmod(mulmod(-qn_mod + MOD, (qn + 1) % MOD), INV2)
let c0: i64 = mulmod(a0m, a0n)
let c1: i64 = (mulmod(a0m, a1n) + mulmod(a1m, a0n)) % MOD
let c2: i64 = mulmod(a1m, a1n)
let sum_val: i64 = c0 * s0 + c1 * s1 + c2 * s2
let mut sum_mod: i64 = sum_val % MOD
total = (total + sum_mod) % MOD
l = r + 1
}
return total
}
function concurrent_triple_count(m: i64, n: i64) -> i64 {
let gcd_part: i64 = weighted_gcd_sum(m, n)
let endpoint: i64 = mulmod(c2_mod(m), c2_mod(n))
return (gcd_part - endpoint + MOD) % MOD
}
function main() -> i32 {
INV2 = (MOD + 1) / 2
INV6 = mod_pow(6, MOD - 2)
let sieve_limit: i64 = 12000000
tp_init(sieve_limit)
let m: i64 = (1234 as i64) * 100000000
let n: i64 = (2345 as i64) * 100000000
let nc: i64 = nonconcurrent_candidate_count(m, n)
let ct: i64 = concurrent_triple_count(m, n)
let result: i64 = (nc - ct + MOD) % MOD
printf("%lld\n", result)
free(tp_pref0 as ptr<void>)
free(tp_pref1 as ptr<void>)
free(tp_pref2 as ptr<void>)
free(tp_scratch as ptr<void>)
free(cache_key as ptr<void>)
free(cache_f0 as ptr<void>)
free(cache_f1 as ptr<void>)
free(cache_f2 as ptr<void>)
free(cache_used as ptr<void>)
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 mulmod_i64_i64(int64_t a, int64_t b);
int64_t mod_pow_i64_i64(int64_t a0, int64_t e0);
int64_t p1_func_i64(int64_t n);
int64_t p2_func_i64(int64_t n);
int64_t p3_func_i64(int64_t n);
int64_t c2_mod_i64(int64_t x);
int64_t c3_mod_i64(int64_t x);
int64_t cache_hash_i64_i64(int64_t key, int64_t size);
void cache_resize_i64(int64_t new_size);
void cache_put_i64_i64_i64_i64(int64_t key, int64_t f0, int64_t f1, int64_t f2);
bool cache_get_i64_ptr_i64(int64_t key, int64_t* out);
void tp_values_i64_ptr_i64(int64_t n, int64_t* out);
void tp_init_i64(int64_t limit);
int64_t nonconcurrent_candidate_count_i64_i64(int64_t m, int64_t n);
int64_t weighted_gcd_sum_i64_i64(int64_t m, int64_t n);
int64_t concurrent_triple_count_i64_i64(int64_t m, int64_t n);
int32_t main(void);
static const int64_t MOD = 1000000007;
/* Module statics */
static int64_t INV2 = 0;
static int64_t INV6 = 0;
static int64_t tp_limit = 0;
static int32_t* tp_pref0 = NULL;
static int32_t* tp_pref1 = NULL;
static int32_t* tp_pref2 = NULL;
static int64_t* tp_scratch = NULL;
static int64_t tp_depth = 0;
static int64_t* cache_key = NULL;
static int64_t* cache_f0 = NULL;
static int64_t* cache_f1 = NULL;
static int64_t* cache_f2 = NULL;
static int8_t* cache_used = NULL;
static int64_t cache_size = 0;
static int64_t cache_count = 0;
int64_t mulmod_i64_i64(int64_t a, int64_t b) {
return FLOW_CHECKED_MOD(((a * b)), (MOD));
}
int64_t mod_pow_i64_i64(int64_t a0, int64_t e0) {
int64_t a = FLOW_CHECKED_MOD((a0), (MOD));
if (a < 0) {
a = (a + MOD);
}
int64_t r = 1;
int64_t e = e0;
while (e > 0) {
if ((e & 1) != 0) {
r = mulmod_i64_i64(r, a);
}
a = mulmod_i64_i64(a, a);
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
int64_t p1_func_i64(int64_t n) {
int64_t a = FLOW_CHECKED_MOD((n), (MOD));
int64_t b = FLOW_CHECKED_MOD(((a + 1)), (MOD));
return mulmod_i64_i64(mulmod_i64_i64(a, b), INV2);
}
int64_t p2_func_i64(int64_t n) {
int64_t a = FLOW_CHECKED_MOD((n), (MOD));
int64_t b = FLOW_CHECKED_MOD(((a + 1)), (MOD));
int64_t c = FLOW_CHECKED_MOD((((2 * a) + 1)), (MOD));
return mulmod_i64_i64(mulmod_i64_i64(mulmod_i64_i64(a, b), c), INV6);
}
int64_t p3_func_i64(int64_t n) {
int64_t s = p1_func_i64(n);
return mulmod_i64_i64(s, s);
}
int64_t c2_mod_i64(int64_t x) {
int64_t a = FLOW_CHECKED_MOD((x), (MOD));
int64_t b = FLOW_CHECKED_MOD((((a - 1) + MOD)), (MOD));
return mulmod_i64_i64(mulmod_i64_i64(a, b), INV2);
}
int64_t c3_mod_i64(int64_t x) {
int64_t a = FLOW_CHECKED_MOD((x), (MOD));
int64_t b = FLOW_CHECKED_MOD((((a - 1) + MOD)), (MOD));
int64_t c = FLOW_CHECKED_MOD((((a - 2) + MOD)), (MOD));
return mulmod_i64_i64(mulmod_i64_i64(mulmod_i64_i64(a, b), c), INV6);
}
int64_t cache_hash_i64_i64(int64_t key, int64_t size) {
int64_t r = FLOW_CHECKED_MOD(((key * 2654435761)), (size));
if (r < 0) {
r = (r + size);
}
return r;
}
void cache_resize_i64(int64_t new_size) {
int64_t* old_key = (int64_t*)(cache_key);
int64_t* old_f0 = (int64_t*)(cache_f0);
int64_t* old_f1 = (int64_t*)(cache_f1);
int64_t* old_f2 = (int64_t*)(cache_f2);
int8_t* old_used = (int8_t*)(cache_used);
int64_t old_s = cache_size;
cache_key = ((int64_t*)(calloc(new_size, 8)));
cache_f0 = ((int64_t*)(calloc(new_size, 8)));
cache_f1 = ((int64_t*)(calloc(new_size, 8)));
cache_f2 = ((int64_t*)(calloc(new_size, 8)));
cache_used = ((int8_t*)(calloc(new_size, 1)));
cache_size = new_size;
cache_count = 0;
int64_t i = 0;
while (i < old_s) {
if (old_used[i] != 0) {
cache_put_i64_i64_i64_i64(old_key[i], old_f0[i], old_f1[i], old_f2[i]);
}
i = (i + 1);
}
free(((void*)(old_key)));
free(((void*)(old_f0)));
free(((void*)(old_f1)));
free(((void*)(old_f2)));
free(((void*)(old_used)));
}
void cache_put_i64_i64_i64_i64(int64_t key, int64_t f0, int64_t f1, int64_t f2) {
if ((cache_count * 2) >= cache_size) {
cache_resize_i64((cache_size * 2));
}
int64_t idx = cache_hash_i64_i64(key, cache_size);
while (cache_used[idx] != 0) {
if (cache_key[idx] == key) {
cache_f0[idx] = f0;
cache_f1[idx] = f1;
cache_f2[idx] = f2;
return;
}
idx = (idx + 1);
if (idx >= cache_size) {
idx = 0;
}
}
cache_key[idx] = key;
cache_f0[idx] = f0;
cache_f1[idx] = f1;
cache_f2[idx] = f2;
cache_used[idx] = 1;
cache_count = (cache_count + 1);
}
bool cache_get_i64_ptr_i64(int64_t key, int64_t* out) {
int64_t idx = cache_hash_i64_i64(key, cache_size);
while (cache_used[idx] != 0) {
if (cache_key[idx] == key) {
out[0] = cache_f0[idx];
out[1] = cache_f1[idx];
out[2] = cache_f2[idx];
return 1;
}
idx = (idx + 1);
if (idx >= cache_size) {
idx = 0;
}
}
return 0;
}
void tp_values_i64_ptr_i64(int64_t n, int64_t* out) {
if (n <= tp_limit) {
out[0] = ((int64_t)(tp_pref0[n]));
out[1] = ((int64_t)(tp_pref1[n]));
out[2] = ((int64_t)(tp_pref2[n]));
return;
}
if (cache_get_i64_ptr_i64(n, out)) {
return;
}
int64_t f0 = p1_func_i64(n);
int64_t f1 = p2_func_i64(n);
int64_t f2 = p3_func_i64(n);
int64_t l = 2;
while (l <= n) {
int64_t q = FLOW_CHECKED_DIV((n), (l));
int64_t r = FLOW_CHECKED_DIV((n), (q));
int64_t sum0 = FLOW_CHECKED_MOD((((r - l) + 1)), (MOD));
int64_t sum1 = FLOW_CHECKED_MOD((((p1_func_i64(r) - p1_func_i64((l - 1))) + MOD)), (MOD));
int64_t sum2 = FLOW_CHECKED_MOD((((p2_func_i64(r) - p2_func_i64((l - 1))) + MOD)), (MOD));
int64_t depth = tp_depth;
int64_t* sub_out = (int64_t*)((tp_scratch + (depth * 3)));
tp_depth = (tp_depth + 1);
tp_values_i64_ptr_i64(q, sub_out);
tp_depth = (tp_depth - 1);
f0 = FLOW_CHECKED_MOD((((f0 - mulmod_i64_i64(sum0, sub_out[0])) + MOD)), (MOD));
f1 = FLOW_CHECKED_MOD((((f1 - mulmod_i64_i64(sum1, sub_out[1])) + MOD)), (MOD));
f2 = FLOW_CHECKED_MOD((((f2 - mulmod_i64_i64(sum2, sub_out[2])) + MOD)), (MOD));
l = (r + 1);
}
out[0] = f0;
out[1] = f1;
out[2] = f2;
cache_put_i64_i64_i64_i64(n, f0, f1, f2);
}
void tp_init_i64(int64_t limit) {
tp_limit = limit;
int32_t* phi = (int32_t*)(((int32_t*)(malloc(((limit + 1) * 4)))));
int64_t i = 0;
while (i <= limit) {
phi[i] = ((int32_t)(i));
i = (i + 1);
}
int64_t p = 2;
while (p <= limit) {
if (((int64_t)(phi[p])) == p) {
int64_t j = p;
while (j <= limit) {
phi[j] = (phi[j] - FLOW_CHECKED_DIV((phi[j]), (((int32_t)(p)))));
j = (j + p);
}
}
p = (p + 1);
}
tp_pref0 = ((int32_t*)(calloc((limit + 1), 4)));
tp_pref1 = ((int32_t*)(calloc((limit + 1), 4)));
tp_pref2 = ((int32_t*)(calloc((limit + 1), 4)));
int64_t s0 = 0;
int64_t s1 = 0;
int64_t s2 = 0;
i = 1;
while (i <= limit) {
int64_t ph = ((int64_t)(phi[i]));
int64_t im = FLOW_CHECKED_MOD((i), (MOD));
s0 = FLOW_CHECKED_MOD(((s0 + ph)), (MOD));
s1 = FLOW_CHECKED_MOD(((s1 + FLOW_CHECKED_MOD(((im * ph)), (MOD)))), (MOD));
s2 = FLOW_CHECKED_MOD(((s2 + FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((im * im)), (MOD)) * ph)), (MOD)))), (MOD));
tp_pref0[i] = ((int32_t)(s0));
tp_pref1[i] = ((int32_t)(s1));
tp_pref2[i] = ((int32_t)(s2));
i = (i + 1);
}
free(((void*)(phi)));
cache_size = FLOW_CHECKED_SHL((1), (20));
cache_count = 0;
cache_key = ((int64_t*)(calloc(cache_size, 8)));
cache_f0 = ((int64_t*)(calloc(cache_size, 8)));
cache_f1 = ((int64_t*)(calloc(cache_size, 8)));
cache_f2 = ((int64_t*)(calloc(cache_size, 8)));
cache_used = ((int8_t*)(calloc(cache_size, 1)));
tp_scratch = ((int64_t*)(calloc(768, 8)));
tp_depth = 0;
}
int64_t nonconcurrent_candidate_count_i64_i64(int64_t m, int64_t n) {
int64_t mm = FLOW_CHECKED_MOD((m), (MOD));
int64_t mm1 = FLOW_CHECKED_MOD((((mm - 1) + MOD)), (MOD));
int64_t nn = FLOW_CHECKED_MOD((n), (MOD));
int64_t nn1 = FLOW_CHECKED_MOD((((nn - 1) + MOD)), (MOD));
int64_t nn1p = FLOW_CHECKED_MOD(((nn + 1)), (MOD));
int64_t two_same = mulmod_i64_i64(mulmod_i64_i64(mulmod_i64_i64(mulmod_i64_i64(mulmod_i64_i64(mm, mm1), nn), nn1), nn1p), INV6);
int64_t diff = FLOW_CHECKED_MOD((((c3_mod_i64((n + 2)) - FLOW_CHECKED_MOD((n), (MOD))) + MOD)), (MOD));
int64_t distinct_val = mulmod_i64_i64(c3_mod_i64(m), diff);
return FLOW_CHECKED_MOD(((two_same + distinct_val)), (MOD));
}
int64_t weighted_gcd_sum_i64_i64(int64_t m, int64_t n) {
int64_t m1 = (m - 1);
int64_t n1 = (n - 1);
int64_t upper = ((m1 < n1) ? (m1) : (n1));
int64_t total = 0;
int64_t* r_out = (int64_t*)((tp_scratch + (0 * 3)));
int64_t* l_out = (int64_t*)((tp_scratch + (1 * 3)));
tp_depth = 2;
int64_t l = 1;
while (l <= upper) {
int64_t qm = FLOW_CHECKED_DIV((m1), (l));
int64_t qn = FLOW_CHECKED_DIV((n1), (l));
int64_t r = FLOW_CHECKED_DIV((m1), (qm));
if (FLOW_CHECKED_DIV((n1), (qn)) < r) {
r = FLOW_CHECKED_DIV((n1), (qn));
}
if (upper < r) {
r = upper;
}
tp_values_i64_ptr_i64(r, r_out);
tp_values_i64_ptr_i64((l - 1), l_out);
int64_t s0 = FLOW_CHECKED_MOD((((r_out[0] - l_out[0]) + MOD)), (MOD));
int64_t s1 = FLOW_CHECKED_MOD((((r_out[1] - l_out[1]) + MOD)), (MOD));
int64_t s2 = FLOW_CHECKED_MOD((((r_out[2] - l_out[2]) + MOD)), (MOD));
int64_t qm_mod = FLOW_CHECKED_MOD((qm), (MOD));
int64_t qn_mod = FLOW_CHECKED_MOD((qn), (MOD));
int64_t a0m = mulmod_i64_i64(qm_mod, FLOW_CHECKED_MOD((m), (MOD)));
int64_t a1m = mulmod_i64_i64(mulmod_i64_i64(((-qm_mod) + MOD), FLOW_CHECKED_MOD(((qm + 1)), (MOD))), INV2);
int64_t a0n = mulmod_i64_i64(qn_mod, FLOW_CHECKED_MOD((n), (MOD)));
int64_t a1n = mulmod_i64_i64(mulmod_i64_i64(((-qn_mod) + MOD), FLOW_CHECKED_MOD(((qn + 1)), (MOD))), INV2);
int64_t c0 = mulmod_i64_i64(a0m, a0n);
int64_t c1 = FLOW_CHECKED_MOD(((mulmod_i64_i64(a0m, a1n) + mulmod_i64_i64(a1m, a0n))), (MOD));
int64_t c2 = mulmod_i64_i64(a1m, a1n);
int64_t sum_val = (((c0 * s0) + (c1 * s1)) + (c2 * s2));
int64_t sum_mod = FLOW_CHECKED_MOD((sum_val), (MOD));
total = FLOW_CHECKED_MOD(((total + sum_mod)), (MOD));
l = (r + 1);
}
return total;
}
int64_t concurrent_triple_count_i64_i64(int64_t m, int64_t n) {
int64_t gcd_part = weighted_gcd_sum_i64_i64(m, n);
int64_t endpoint = mulmod_i64_i64(c2_mod_i64(m), c2_mod_i64(n));
return FLOW_CHECKED_MOD((((gcd_part - endpoint) + MOD)), (MOD));
}
int32_t main(void) {
INV2 = FLOW_CHECKED_DIV(((MOD + 1)), (2));
INV6 = mod_pow_i64_i64(6, (MOD - 2));
int64_t sieve_limit = 12000000;
tp_init_i64(sieve_limit);
int64_t m = (((int64_t)(1234)) * 100000000);
int64_t n = (((int64_t)(2345)) * 100000000);
int64_t nc = nonconcurrent_candidate_count_i64_i64(m, n);
int64_t ct = concurrent_triple_count_i64_i64(m, n);
int64_t result = FLOW_CHECKED_MOD((((nc - ct) + MOD)), (MOD));
printf("%lld\n", result);
free(((void*)(tp_pref0)));
free(((void*)(tp_pref1)));
free(((void*)(tp_pref2)));
free(((void*)(tp_scratch)));
free(((void*)(cache_key)));
free(((void*)(cache_f0)));
free(((void*)(cache_f1)));
free(((void*)(cache_f2)));
free(((void*)(cache_used)));
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @malloc(i64) -> !llvm.ptr
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
// Module static: INV2
llvm.mlir.global internal @INV2(0 : i64) : i64
// Module static: INV6
llvm.mlir.global internal @INV6(0 : i64) : i64
// Module static: tp_limit
llvm.mlir.global internal @tp_limit(0 : i64) : i64
// Module static: tp_pref0
llvm.mlir.global internal @tp_pref0() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: tp_pref1
llvm.mlir.global internal @tp_pref1() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
// Module static: tp_pref2
llvm.mlir.global internal @tp_pref2() {addr_space = 0 : i32} : !llvm.ptr {
%2 = llvm.mlir.zero : !llvm.ptr
llvm.return %2 : !llvm.ptr
}
// Module static: tp_scratch
llvm.mlir.global internal @tp_scratch() {addr_space = 0 : i32} : !llvm.ptr {
%3 = llvm.mlir.zero : !llvm.ptr
llvm.return %3 : !llvm.ptr
}
// Module static: tp_depth
llvm.mlir.global internal @tp_depth(0 : i64) : i64
// Module static: cache_key
llvm.mlir.global internal @cache_key() {addr_space = 0 : i32} : !llvm.ptr {
%4 = llvm.mlir.zero : !llvm.ptr
llvm.return %4 : !llvm.ptr
}
// Module static: cache_f0
llvm.mlir.global internal @cache_f0() {addr_space = 0 : i32} : !llvm.ptr {
%5 = llvm.mlir.zero : !llvm.ptr
llvm.return %5 : !llvm.ptr
}
// Module static: cache_f1
llvm.mlir.global internal @cache_f1() {addr_space = 0 : i32} : !llvm.ptr {
%6 = llvm.mlir.zero : !llvm.ptr
llvm.return %6 : !llvm.ptr
}
// Module static: cache_f2
llvm.mlir.global internal @cache_f2() {addr_space = 0 : i32} : !llvm.ptr {
%7 = llvm.mlir.zero : !llvm.ptr
llvm.return %7 : !llvm.ptr
}
// Module static: cache_used
llvm.mlir.global internal @cache_used() {addr_space = 0 : i32} : !llvm.ptr {
%8 = llvm.mlir.zero : !llvm.ptr
llvm.return %8 : !llvm.ptr
}
// Module static: cache_size
llvm.mlir.global internal @cache_size(0 : i64) : i64
// Module static: cache_count
llvm.mlir.global internal @cache_count(0 : i64) : i64
func.func @mulmod(%arg0: i64, %arg1: i64) -> i64 {
%9 = arith.muli %arg0, %arg1 : i64
%10 = llvm.mlir.addressof @MOD : !llvm.ptr
%11 = llvm.load %10 : !llvm.ptr -> i64
%12 = arith.remsi %9, %11 : i64
func.return %12 : i64
}
func.func @mod_pow(%arg0: i64, %arg1: i64) -> i64 {
%13 = llvm.mlir.addressof @MOD : !llvm.ptr
%14 = llvm.load %13 : !llvm.ptr -> i64
%15 = arith.remsi %arg0, %14 : i64
%16 = llvm.mlir.constant(1 : i64) : i64
%17 = llvm.alloca %16 x i64 : (i64) -> !llvm.ptr
llvm.store %15, %17 : i64, !llvm.ptr
%18 = llvm.load %17 : !llvm.ptr -> i64
%19 = arith.constant 0 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.cmpi slt, %18, %21 : i64
cf.cond_br %20, ^bb0, ^bb1
^bb0:
%22 = llvm.load %17 : !llvm.ptr -> i64
%23 = llvm.mlir.addressof @MOD : !llvm.ptr
%24 = llvm.load %23 : !llvm.ptr -> i64
%25 = arith.addi %22, %24 : i64
llvm.store %25, %17 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%26 = arith.constant 1 : i32
%27 = arith.extsi %26 : i32 to i64
%28 = llvm.mlir.constant(1 : i64) : i64
%29 = llvm.alloca %28 x i64 : (i64) -> !llvm.ptr
llvm.store %27, %29 : i64, !llvm.ptr
%30 = llvm.mlir.constant(1 : i64) : i64
%31 = llvm.alloca %30 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %31 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%32 = llvm.load %31 : !llvm.ptr -> i64
%33 = arith.constant 0 : i32
%35 = arith.extsi %33 : i32 to i64
%34 = arith.cmpi sgt, %32, %35 : i64
cf.cond_br %34, ^bb4, ^bb5
^bb4:
%36 = llvm.load %31 : !llvm.ptr -> i64
%37 = arith.constant 1 : i32
%39 = arith.extsi %37 : i32 to i64
%38 = arith.andi %36, %39 : i64
%40 = arith.constant 0 : i32
%42 = arith.extsi %40 : i32 to i64
%41 = arith.cmpi ne, %38, %42 : i64
cf.cond_br %41, ^bb6, ^bb7
^bb6:
%44 = llvm.load %29 : !llvm.ptr -> i64
%45 = llvm.load %17 : !llvm.ptr -> i64
%43 = func.call @mulmod(%44, %45) : (i64, i64) -> i64
llvm.store %43, %29 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%47 = llvm.load %17 : !llvm.ptr -> i64
%48 = llvm.load %17 : !llvm.ptr -> i64
%46 = func.call @mulmod(%47, %48) : (i64, i64) -> i64
llvm.store %46, %17 : i64, !llvm.ptr
%49 = llvm.load %31 : !llvm.ptr -> i64
%50 = arith.constant 1 : i32
%52 = arith.extsi %50 : i32 to i64
%51 = arith.shrsi %49, %52 : i64
llvm.store %51, %31 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%53 = llvm.load %29 : !llvm.ptr -> i64
func.return %53 : i64
}
func.func @p1_func(%arg0: i64) -> i64 {
%54 = llvm.mlir.addressof @MOD : !llvm.ptr
%55 = llvm.load %54 : !llvm.ptr -> i64
%56 = arith.remsi %arg0, %55 : i64
%57 = arith.constant 1 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.addi %56, %59 : i64
%60 = llvm.mlir.addressof @MOD : !llvm.ptr
%61 = llvm.load %60 : !llvm.ptr -> i64
%62 = arith.remsi %58, %61 : i64
%64 = func.call @mulmod(%56, %62) : (i64, i64) -> i64
%65 = llvm.mlir.addressof @INV2 : !llvm.ptr
%66 = llvm.load %65 : !llvm.ptr -> i64
%63 = func.call @mulmod(%64, %66) : (i64, i64) -> i64
func.return %63 : i64
}
func.func @p2_func(%arg0: i64) -> i64 {
%67 = llvm.mlir.addressof @MOD : !llvm.ptr
%68 = llvm.load %67 : !llvm.ptr -> i64
%69 = arith.remsi %arg0, %68 : i64
%70 = arith.constant 1 : i32
%72 = arith.extsi %70 : i32 to i64
%71 = arith.addi %69, %72 : i64
%73 = llvm.mlir.addressof @MOD : !llvm.ptr
%74 = llvm.load %73 : !llvm.ptr -> i64
%75 = arith.remsi %71, %74 : i64
%76 = arith.constant 2 : i32
%78 = arith.extsi %76 : i32 to i64
%77 = arith.muli %78, %69 : i64
%79 = arith.constant 1 : i32
%81 = arith.extsi %79 : i32 to i64
%80 = arith.addi %77, %81 : i64
%82 = llvm.mlir.addressof @MOD : !llvm.ptr
%83 = llvm.load %82 : !llvm.ptr -> i64
%84 = arith.remsi %80, %83 : i64
%87 = func.call @mulmod(%69, %75) : (i64, i64) -> i64
%86 = func.call @mulmod(%87, %84) : (i64, i64) -> i64
%88 = llvm.mlir.addressof @INV6 : !llvm.ptr
%89 = llvm.load %88 : !llvm.ptr -> i64
%85 = func.call @mulmod(%86, %89) : (i64, i64) -> i64
func.return %85 : i64
}
func.func @p3_func(%arg0: i64) -> i64 {
%90 = func.call @p1_func(%arg0) : (i64) -> i64
%91 = func.call @mulmod(%90, %90) : (i64, i64) -> i64
func.return %91 : i64
}
func.func @c2_mod(%arg0: i64) -> i64 {
%92 = llvm.mlir.addressof @MOD : !llvm.ptr
%93 = llvm.load %92 : !llvm.ptr -> i64
%94 = arith.remsi %arg0, %93 : i64
%95 = arith.constant 1 : i32
%97 = arith.extsi %95 : i32 to i64
%96 = arith.subi %94, %97 : i64
%98 = llvm.mlir.addressof @MOD : !llvm.ptr
%99 = llvm.load %98 : !llvm.ptr -> i64
%100 = arith.addi %96, %99 : i64
%101 = llvm.mlir.addressof @MOD : !llvm.ptr
%102 = llvm.load %101 : !llvm.ptr -> i64
%103 = arith.remsi %100, %102 : i64
%105 = func.call @mulmod(%94, %103) : (i64, i64) -> i64
%106 = llvm.mlir.addressof @INV2 : !llvm.ptr
%107 = llvm.load %106 : !llvm.ptr -> i64
%104 = func.call @mulmod(%105, %107) : (i64, i64) -> i64
func.return %104 : i64
}
func.func @c3_mod(%arg0: i64) -> i64 {
%108 = llvm.mlir.addressof @MOD : !llvm.ptr
%109 = llvm.load %108 : !llvm.ptr -> i64
%110 = arith.remsi %arg0, %109 : i64
%111 = arith.constant 1 : i32
%113 = arith.extsi %111 : i32 to i64
%112 = arith.subi %110, %113 : i64
%114 = llvm.mlir.addressof @MOD : !llvm.ptr
%115 = llvm.load %114 : !llvm.ptr -> i64
%116 = arith.addi %112, %115 : i64
%117 = llvm.mlir.addressof @MOD : !llvm.ptr
%118 = llvm.load %117 : !llvm.ptr -> i64
%119 = arith.remsi %116, %118 : i64
%120 = arith.constant 2 : i32
%122 = arith.extsi %120 : i32 to i64
%121 = arith.subi %110, %122 : i64
%123 = llvm.mlir.addressof @MOD : !llvm.ptr
%124 = llvm.load %123 : !llvm.ptr -> i64
%125 = arith.addi %121, %124 : i64
%126 = llvm.mlir.addressof @MOD : !llvm.ptr
%127 = llvm.load %126 : !llvm.ptr -> i64
%128 = arith.remsi %125, %127 : i64
%131 = func.call @mulmod(%110, %119) : (i64, i64) -> i64
%130 = func.call @mulmod(%131, %128) : (i64, i64) -> i64
%132 = llvm.mlir.addressof @INV6 : !llvm.ptr
%133 = llvm.load %132 : !llvm.ptr -> i64
%129 = func.call @mulmod(%130, %133) : (i64, i64) -> i64
func.return %129 : i64
}
func.func @cache_hash(%arg0: i64, %arg1: i64) -> i64 {
%134 = arith.constant -1640531535 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.muli %arg0, %136 : i64
%137 = arith.remsi %135, %arg1 : i64
%138 = llvm.mlir.constant(1 : i64) : i64
%139 = llvm.alloca %138 x i64 : (i64) -> !llvm.ptr
llvm.store %137, %139 : i64, !llvm.ptr
%140 = llvm.load %139 : !llvm.ptr -> i64
%141 = arith.constant 0 : i32
%143 = arith.extsi %141 : i32 to i64
%142 = arith.cmpi slt, %140, %143 : i64
cf.cond_br %142, ^bb9, ^bb10
^bb9:
%144 = llvm.load %139 : !llvm.ptr -> i64
%145 = arith.addi %144, %arg1 : i64
llvm.store %145, %139 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%146 = llvm.load %139 : !llvm.ptr -> i64
func.return %146 : i64
}
func.func @cache_resize(%arg0: i64) -> () {
%147 = llvm.mlir.addressof @cache_key : !llvm.ptr
%148 = llvm.load %147 : !llvm.ptr -> !llvm.ptr
%149 = llvm.mlir.addressof @cache_f0 : !llvm.ptr
%150 = llvm.load %149 : !llvm.ptr -> !llvm.ptr
%151 = llvm.mlir.addressof @cache_f1 : !llvm.ptr
%152 = llvm.load %151 : !llvm.ptr -> !llvm.ptr
%153 = llvm.mlir.addressof @cache_f2 : !llvm.ptr
%154 = llvm.load %153 : !llvm.ptr -> !llvm.ptr
%155 = llvm.mlir.addressof @cache_used : !llvm.ptr
%156 = llvm.load %155 : !llvm.ptr -> !llvm.ptr
%157 = llvm.mlir.addressof @cache_size : !llvm.ptr
%158 = llvm.load %157 : !llvm.ptr -> i64
%160 = arith.constant 8 : i32
%161 = arith.extsi %160 : i32 to i64
%159 = func.call @calloc(%arg0, %161) : (i64, i64) -> !llvm.ptr
%162 = llvm.mlir.addressof @cache_key : !llvm.ptr
llvm.store %159, %162 : !llvm.ptr, !llvm.ptr
%164 = arith.constant 8 : i32
%165 = arith.extsi %164 : i32 to i64
%163 = func.call @calloc(%arg0, %165) : (i64, i64) -> !llvm.ptr
%166 = llvm.mlir.addressof @cache_f0 : !llvm.ptr
llvm.store %163, %166 : !llvm.ptr, !llvm.ptr
%168 = arith.constant 8 : i32
%169 = arith.extsi %168 : i32 to i64
%167 = func.call @calloc(%arg0, %169) : (i64, i64) -> !llvm.ptr
%170 = llvm.mlir.addressof @cache_f1 : !llvm.ptr
llvm.store %167, %170 : !llvm.ptr, !llvm.ptr
%172 = arith.constant 8 : i32
%173 = arith.extsi %172 : i32 to i64
%171 = func.call @calloc(%arg0, %173) : (i64, i64) -> !llvm.ptr
%174 = llvm.mlir.addressof @cache_f2 : !llvm.ptr
llvm.store %171, %174 : !llvm.ptr, !llvm.ptr
%176 = arith.constant 1 : i32
%177 = arith.extsi %176 : i32 to i64
%175 = func.call @calloc(%arg0, %177) : (i64, i64) -> !llvm.ptr
%178 = llvm.mlir.addressof @cache_used : !llvm.ptr
llvm.store %175, %178 : !llvm.ptr, !llvm.ptr
%179 = llvm.mlir.addressof @cache_size : !llvm.ptr
llvm.store %arg0, %179 : i64, !llvm.ptr
%180 = arith.constant 0 : i32
%181 = arith.extsi %180 : i32 to i64
%182 = llvm.mlir.addressof @cache_count : !llvm.ptr
llvm.store %181, %182 : i64, !llvm.ptr
%183 = arith.constant 0 : i32
%184 = arith.extsi %183 : i32 to i64
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x i64 : (i64) -> !llvm.ptr
llvm.store %184, %186 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%187 = llvm.load %186 : !llvm.ptr -> i64
%188 = arith.cmpi slt, %187, %158 : i64
cf.cond_br %188, ^bb13, ^bb14
^bb13:
%190 = llvm.load %186 : !llvm.ptr -> i64
%191 = llvm.getelementptr %156[%190] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%189 = llvm.load %191 : !llvm.ptr -> i8
%192 = arith.constant 0 : i32
%194 = arith.extsi %189 : i8 to i32
%193 = arith.cmpi ne, %194, %192 : i32
cf.cond_br %193, ^bb15, ^bb16
^bb15:
%197 = llvm.load %186 : !llvm.ptr -> i64
%198 = llvm.getelementptr %148[%197] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%196 = llvm.load %198 : !llvm.ptr -> i64
%200 = llvm.load %186 : !llvm.ptr -> i64
%201 = llvm.getelementptr %150[%200] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%199 = llvm.load %201 : !llvm.ptr -> i64
%203 = llvm.load %186 : !llvm.ptr -> i64
%204 = llvm.getelementptr %152[%203] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%202 = llvm.load %204 : !llvm.ptr -> i64
%206 = llvm.load %186 : !llvm.ptr -> i64
%207 = llvm.getelementptr %154[%206] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%205 = llvm.load %207 : !llvm.ptr -> i64
func.call @cache_put(%196, %199, %202, %205) : (i64, i64, i64, i64) -> ()
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%208 = llvm.load %186 : !llvm.ptr -> i64
%209 = arith.constant 1 : i32
%211 = arith.extsi %209 : i32 to i64
%210 = arith.addi %208, %211 : i64
llvm.store %210, %186 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
func.call @free(%148) : (!llvm.ptr) -> ()
func.call @free(%150) : (!llvm.ptr) -> ()
func.call @free(%152) : (!llvm.ptr) -> ()
func.call @free(%154) : (!llvm.ptr) -> ()
func.call @free(%156) : (!llvm.ptr) -> ()
func.return
}
func.func @cache_put(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> () {
%217 = llvm.mlir.addressof @cache_count : !llvm.ptr
%218 = llvm.load %217 : !llvm.ptr -> i64
%219 = arith.constant 2 : i32
%221 = arith.extsi %219 : i32 to i64
%220 = arith.muli %218, %221 : i64
%222 = llvm.mlir.addressof @cache_size : !llvm.ptr
%223 = llvm.load %222 : !llvm.ptr -> i64
%224 = arith.cmpi sge, %220, %223 : i64
cf.cond_br %224, ^bb18, ^bb19
^bb18:
%226 = llvm.mlir.addressof @cache_size : !llvm.ptr
%227 = llvm.load %226 : !llvm.ptr -> i64
%228 = arith.constant 2 : i32
%230 = arith.extsi %228 : i32 to i64
%229 = arith.muli %227, %230 : i64
func.call @cache_resize(%229) : (i64) -> ()
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%232 = llvm.mlir.addressof @cache_size : !llvm.ptr
%233 = llvm.load %232 : !llvm.ptr -> i64
%231 = func.call @cache_hash(%arg0, %233) : (i64, i64) -> i64
%234 = llvm.mlir.constant(1 : i64) : i64
%235 = llvm.alloca %234 x i64 : (i64) -> !llvm.ptr
llvm.store %231, %235 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%237 = llvm.mlir.addressof @cache_used : !llvm.ptr
%238 = llvm.load %237 : !llvm.ptr -> !llvm.ptr
%239 = llvm.load %235 : !llvm.ptr -> i64
%240 = llvm.getelementptr %238[%239] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%236 = llvm.load %240 : !llvm.ptr -> i8
%241 = arith.constant 0 : i32
%243 = arith.extsi %236 : i8 to i32
%242 = arith.cmpi ne, %243, %241 : i32
cf.cond_br %242, ^bb22, ^bb23
^bb22:
%245 = llvm.mlir.addressof @cache_key : !llvm.ptr
%246 = llvm.load %245 : !llvm.ptr -> !llvm.ptr
%247 = llvm.load %235 : !llvm.ptr -> i64
%248 = llvm.getelementptr %246[%247] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%244 = llvm.load %248 : !llvm.ptr -> i64
%249 = arith.cmpi eq, %244, %arg0 : i64
cf.cond_br %249, ^bb24, ^bb25
^bb24:
%250 = llvm.mlir.addressof @cache_f0 : !llvm.ptr
%251 = llvm.load %250 : !llvm.ptr -> !llvm.ptr
%252 = llvm.load %235 : !llvm.ptr -> i64
%253 = llvm.getelementptr %251[%252] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %253 : i64, !llvm.ptr
%254 = llvm.mlir.addressof @cache_f1 : !llvm.ptr
%255 = llvm.load %254 : !llvm.ptr -> !llvm.ptr
%256 = llvm.load %235 : !llvm.ptr -> i64
%257 = llvm.getelementptr %255[%256] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg2, %257 : i64, !llvm.ptr
%258 = llvm.mlir.addressof @cache_f2 : !llvm.ptr
%259 = llvm.load %258 : !llvm.ptr -> !llvm.ptr
%260 = llvm.load %235 : !llvm.ptr -> i64
%261 = llvm.getelementptr %259[%260] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg3, %261 : i64, !llvm.ptr
func.return
^bb25:
cf.br ^bb26
^bb26:
%262 = llvm.load %235 : !llvm.ptr -> i64
%263 = arith.constant 1 : i32
%265 = arith.extsi %263 : i32 to i64
%264 = arith.addi %262, %265 : i64
llvm.store %264, %235 : i64, !llvm.ptr
%266 = llvm.load %235 : !llvm.ptr -> i64
%267 = llvm.mlir.addressof @cache_size : !llvm.ptr
%268 = llvm.load %267 : !llvm.ptr -> i64
%269 = arith.cmpi sge, %266, %268 : i64
cf.cond_br %269, ^bb27, ^bb28
^bb27:
%270 = arith.constant 0 : i32
%271 = arith.extsi %270 : i32 to i64
llvm.store %271, %235 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
cf.br ^bb21
^bb23:
%272 = llvm.mlir.addressof @cache_key : !llvm.ptr
%273 = llvm.load %272 : !llvm.ptr -> !llvm.ptr
%274 = llvm.load %235 : !llvm.ptr -> i64
%275 = llvm.getelementptr %273[%274] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %275 : i64, !llvm.ptr
%276 = llvm.mlir.addressof @cache_f0 : !llvm.ptr
%277 = llvm.load %276 : !llvm.ptr -> !llvm.ptr
%278 = llvm.load %235 : !llvm.ptr -> i64
%279 = llvm.getelementptr %277[%278] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %279 : i64, !llvm.ptr
%280 = llvm.mlir.addressof @cache_f1 : !llvm.ptr
%281 = llvm.load %280 : !llvm.ptr -> !llvm.ptr
%282 = llvm.load %235 : !llvm.ptr -> i64
%283 = llvm.getelementptr %281[%282] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg2, %283 : i64, !llvm.ptr
%284 = llvm.mlir.addressof @cache_f2 : !llvm.ptr
%285 = llvm.load %284 : !llvm.ptr -> !llvm.ptr
%286 = llvm.load %235 : !llvm.ptr -> i64
%287 = llvm.getelementptr %285[%286] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg3, %287 : i64, !llvm.ptr
%288 = arith.constant 1 : i32
%289 = llvm.mlir.addressof @cache_used : !llvm.ptr
%290 = llvm.load %289 : !llvm.ptr -> !llvm.ptr
%291 = llvm.load %235 : !llvm.ptr -> i64
%292 = arith.trunci %288 : i32 to i8
%293 = llvm.getelementptr %290[%291] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %292, %293 : i8, !llvm.ptr
%294 = llvm.mlir.addressof @cache_count : !llvm.ptr
%295 = llvm.load %294 : !llvm.ptr -> i64
%296 = arith.constant 1 : i32
%298 = arith.extsi %296 : i32 to i64
%297 = arith.addi %295, %298 : i64
%299 = llvm.mlir.addressof @cache_count : !llvm.ptr
llvm.store %297, %299 : i64, !llvm.ptr
func.return
}
func.func @cache_get(%arg0: i64, %arg1: !llvm.ptr) -> i1 {
%301 = llvm.mlir.addressof @cache_size : !llvm.ptr
%302 = llvm.load %301 : !llvm.ptr -> i64
%300 = func.call @cache_hash(%arg0, %302) : (i64, i64) -> i64
%303 = llvm.mlir.constant(1 : i64) : i64
%304 = llvm.alloca %303 x i64 : (i64) -> !llvm.ptr
llvm.store %300, %304 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%306 = llvm.mlir.addressof @cache_used : !llvm.ptr
%307 = llvm.load %306 : !llvm.ptr -> !llvm.ptr
%308 = llvm.load %304 : !llvm.ptr -> i64
%309 = llvm.getelementptr %307[%308] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%305 = llvm.load %309 : !llvm.ptr -> i8
%310 = arith.constant 0 : i32
%312 = arith.extsi %305 : i8 to i32
%311 = arith.cmpi ne, %312, %310 : i32
cf.cond_br %311, ^bb31, ^bb32
^bb31:
%314 = llvm.mlir.addressof @cache_key : !llvm.ptr
%315 = llvm.load %314 : !llvm.ptr -> !llvm.ptr
%316 = llvm.load %304 : !llvm.ptr -> i64
%317 = llvm.getelementptr %315[%316] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%313 = llvm.load %317 : !llvm.ptr -> i64
%318 = arith.cmpi eq, %313, %arg0 : i64
cf.cond_br %318, ^bb33, ^bb34
^bb33:
%320 = llvm.mlir.addressof @cache_f0 : !llvm.ptr
%321 = llvm.load %320 : !llvm.ptr -> !llvm.ptr
%322 = llvm.load %304 : !llvm.ptr -> i64
%323 = llvm.getelementptr %321[%322] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%319 = llvm.load %323 : !llvm.ptr -> i64
%324 = arith.constant 0 : i32
%325 = arith.extsi %324 : i32 to i64
%326 = llvm.getelementptr %arg1[%325] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %319, %326 : i64, !llvm.ptr
%328 = llvm.mlir.addressof @cache_f1 : !llvm.ptr
%329 = llvm.load %328 : !llvm.ptr -> !llvm.ptr
%330 = llvm.load %304 : !llvm.ptr -> i64
%331 = llvm.getelementptr %329[%330] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%327 = llvm.load %331 : !llvm.ptr -> i64
%332 = arith.constant 1 : i32
%333 = arith.extsi %332 : i32 to i64
%334 = llvm.getelementptr %arg1[%333] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %327, %334 : i64, !llvm.ptr
%336 = llvm.mlir.addressof @cache_f2 : !llvm.ptr
%337 = llvm.load %336 : !llvm.ptr -> !llvm.ptr
%338 = llvm.load %304 : !llvm.ptr -> i64
%339 = llvm.getelementptr %337[%338] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%335 = llvm.load %339 : !llvm.ptr -> i64
%340 = arith.constant 2 : i32
%341 = arith.extsi %340 : i32 to i64
%342 = llvm.getelementptr %arg1[%341] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %335, %342 : i64, !llvm.ptr
%343 = arith.constant 1 : i1
func.return %343 : i1
^bb34:
cf.br ^bb35
^bb35:
%344 = llvm.load %304 : !llvm.ptr -> i64
%345 = arith.constant 1 : i32
%347 = arith.extsi %345 : i32 to i64
%346 = arith.addi %344, %347 : i64
llvm.store %346, %304 : i64, !llvm.ptr
%348 = llvm.load %304 : !llvm.ptr -> i64
%349 = llvm.mlir.addressof @cache_size : !llvm.ptr
%350 = llvm.load %349 : !llvm.ptr -> i64
%351 = arith.cmpi sge, %348, %350 : i64
cf.cond_br %351, ^bb36, ^bb37
^bb36:
%352 = arith.constant 0 : i32
%353 = arith.extsi %352 : i32 to i64
llvm.store %353, %304 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
cf.br ^bb30
^bb32:
%354 = arith.constant 0 : i1
func.return %354 : i1
}
func.func @tp_values(%arg0: i64, %arg1: !llvm.ptr) -> () {
%355 = llvm.mlir.addressof @tp_limit : !llvm.ptr
%356 = llvm.load %355 : !llvm.ptr -> i64
%357 = arith.cmpi sle, %arg0, %356 : i64
cf.cond_br %357, ^bb39, ^bb40
^bb39:
%359 = llvm.mlir.addressof @tp_pref0 : !llvm.ptr
%360 = llvm.load %359 : !llvm.ptr -> !llvm.ptr
%361 = llvm.getelementptr %360[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%358 = llvm.load %361 : !llvm.ptr -> i32
%362 = arith.extsi %358 : i32 to i64
%363 = arith.constant 0 : i32
%364 = arith.extsi %363 : i32 to i64
%365 = llvm.getelementptr %arg1[%364] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %362, %365 : i64, !llvm.ptr
%367 = llvm.mlir.addressof @tp_pref1 : !llvm.ptr
%368 = llvm.load %367 : !llvm.ptr -> !llvm.ptr
%369 = llvm.getelementptr %368[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%366 = llvm.load %369 : !llvm.ptr -> i32
%370 = arith.extsi %366 : i32 to i64
%371 = arith.constant 1 : i32
%372 = arith.extsi %371 : i32 to i64
%373 = llvm.getelementptr %arg1[%372] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %370, %373 : i64, !llvm.ptr
%375 = llvm.mlir.addressof @tp_pref2 : !llvm.ptr
%376 = llvm.load %375 : !llvm.ptr -> !llvm.ptr
%377 = llvm.getelementptr %376[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%374 = llvm.load %377 : !llvm.ptr -> i32
%378 = arith.extsi %374 : i32 to i64
%379 = arith.constant 2 : i32
%380 = arith.extsi %379 : i32 to i64
%381 = llvm.getelementptr %arg1[%380] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %378, %381 : i64, !llvm.ptr
func.return
^bb40:
cf.br ^bb41
^bb41:
%382 = func.call @cache_get(%arg0, %arg1) : (i64, !llvm.ptr) -> i1
cf.cond_br %382, ^bb42, ^bb43
^bb42:
func.return
^bb43:
cf.br ^bb44
^bb44:
%383 = func.call @p1_func(%arg0) : (i64) -> i64
%384 = llvm.mlir.constant(1 : i64) : i64
%385 = llvm.alloca %384 x i64 : (i64) -> !llvm.ptr
llvm.store %383, %385 : i64, !llvm.ptr
%386 = func.call @p2_func(%arg0) : (i64) -> i64
%387 = llvm.mlir.constant(1 : i64) : i64
%388 = llvm.alloca %387 x i64 : (i64) -> !llvm.ptr
llvm.store %386, %388 : i64, !llvm.ptr
%389 = func.call @p3_func(%arg0) : (i64) -> i64
%390 = llvm.mlir.constant(1 : i64) : i64
%391 = llvm.alloca %390 x i64 : (i64) -> !llvm.ptr
llvm.store %389, %391 : i64, !llvm.ptr
%392 = arith.constant 2 : i32
%393 = arith.extsi %392 : i32 to i64
%394 = llvm.mlir.constant(1 : i64) : i64
%395 = llvm.alloca %394 x i64 : (i64) -> !llvm.ptr
llvm.store %393, %395 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%396 = llvm.load %395 : !llvm.ptr -> i64
%397 = arith.cmpi sle, %396, %arg0 : i64
cf.cond_br %397, ^bb46, ^bb47
^bb46:
%398 = llvm.load %395 : !llvm.ptr -> i64
%399 = arith.divsi %arg0, %398 : i64
%400 = arith.divsi %arg0, %399 : i64
%401 = llvm.load %395 : !llvm.ptr -> i64
%402 = arith.subi %400, %401 : i64
%403 = arith.constant 1 : i32
%405 = arith.extsi %403 : i32 to i64
%404 = arith.addi %402, %405 : i64
%406 = llvm.mlir.addressof @MOD : !llvm.ptr
%407 = llvm.load %406 : !llvm.ptr -> i64
%408 = arith.remsi %404, %407 : i64
%409 = func.call @p1_func(%400) : (i64) -> i64
%411 = llvm.load %395 : !llvm.ptr -> i64
%412 = arith.constant 1 : i32
%414 = arith.extsi %412 : i32 to i64
%413 = arith.subi %411, %414 : i64
%410 = func.call @p1_func(%413) : (i64) -> i64
%415 = arith.subi %409, %410 : i64
%416 = llvm.mlir.addressof @MOD : !llvm.ptr
%417 = llvm.load %416 : !llvm.ptr -> i64
%418 = arith.addi %415, %417 : i64
%419 = llvm.mlir.addressof @MOD : !llvm.ptr
%420 = llvm.load %419 : !llvm.ptr -> i64
%421 = arith.remsi %418, %420 : i64
%422 = func.call @p2_func(%400) : (i64) -> i64
%424 = llvm.load %395 : !llvm.ptr -> i64
%425 = arith.constant 1 : i32
%427 = arith.extsi %425 : i32 to i64
%426 = arith.subi %424, %427 : i64
%423 = func.call @p2_func(%426) : (i64) -> i64
%428 = arith.subi %422, %423 : i64
%429 = llvm.mlir.addressof @MOD : !llvm.ptr
%430 = llvm.load %429 : !llvm.ptr -> i64
%431 = arith.addi %428, %430 : i64
%432 = llvm.mlir.addressof @MOD : !llvm.ptr
%433 = llvm.load %432 : !llvm.ptr -> i64
%434 = arith.remsi %431, %433 : i64
%435 = llvm.mlir.addressof @tp_depth : !llvm.ptr
%436 = llvm.load %435 : !llvm.ptr -> i64
# String concatenation: !llvm.ptr + i64
%438 = llvm.mlir.addressof @tp_depth : !llvm.ptr
%439 = llvm.load %438 : !llvm.ptr -> i64
%440 = arith.constant 1 : i32
%442 = arith.extsi %440 : i32 to i64
%441 = arith.addi %439, %442 : i64
%443 = llvm.mlir.addressof @tp_depth : !llvm.ptr
llvm.store %441, %443 : i64, !llvm.ptr
func.call @tp_values(%399, %437) : (i64, !llvm.ptr) -> ()
%445 = llvm.mlir.addressof @tp_depth : !llvm.ptr
%446 = llvm.load %445 : !llvm.ptr -> i64
%447 = arith.constant 1 : i32
%449 = arith.extsi %447 : i32 to i64
%448 = arith.subi %446, %449 : i64
%450 = llvm.mlir.addressof @tp_depth : !llvm.ptr
llvm.store %448, %450 : i64, !llvm.ptr
%451 = llvm.load %385 : !llvm.ptr -> i64
%454 = arith.constant 0 : i32
%455 = arith.extsi %454 : i32 to i64
%456 = llvm.getelementptr %437[%455] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%453 = llvm.load %456 : !llvm.ptr -> i64
%452 = func.call @mulmod(%408, %453) : (i64, i64) -> i64
%457 = arith.subi %451, %452 : i64
%458 = llvm.mlir.addressof @MOD : !llvm.ptr
%459 = llvm.load %458 : !llvm.ptr -> i64
%460 = arith.addi %457, %459 : i64
%461 = llvm.mlir.addressof @MOD : !llvm.ptr
%462 = llvm.load %461 : !llvm.ptr -> i64
%463 = arith.remsi %460, %462 : i64
llvm.store %463, %385 : i64, !llvm.ptr
%464 = llvm.load %388 : !llvm.ptr -> i64
%467 = arith.constant 1 : i32
%468 = arith.extsi %467 : i32 to i64
%469 = llvm.getelementptr %437[%468] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%466 = llvm.load %469 : !llvm.ptr -> i64
%465 = func.call @mulmod(%421, %466) : (i64, i64) -> i64
%470 = arith.subi %464, %465 : i64
%471 = llvm.mlir.addressof @MOD : !llvm.ptr
%472 = llvm.load %471 : !llvm.ptr -> i64
%473 = arith.addi %470, %472 : i64
%474 = llvm.mlir.addressof @MOD : !llvm.ptr
%475 = llvm.load %474 : !llvm.ptr -> i64
%476 = arith.remsi %473, %475 : i64
llvm.store %476, %388 : i64, !llvm.ptr
%477 = llvm.load %391 : !llvm.ptr -> i64
%480 = arith.constant 2 : i32
%481 = arith.extsi %480 : i32 to i64
%482 = llvm.getelementptr %437[%481] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%479 = llvm.load %482 : !llvm.ptr -> i64
%478 = func.call @mulmod(%434, %479) : (i64, i64) -> i64
%483 = arith.subi %477, %478 : i64
%484 = llvm.mlir.addressof @MOD : !llvm.ptr
%485 = llvm.load %484 : !llvm.ptr -> i64
%486 = arith.addi %483, %485 : i64
%487 = llvm.mlir.addressof @MOD : !llvm.ptr
%488 = llvm.load %487 : !llvm.ptr -> i64
%489 = arith.remsi %486, %488 : i64
llvm.store %489, %391 : i64, !llvm.ptr
%490 = arith.constant 1 : i32
%492 = arith.extsi %490 : i32 to i64
%491 = arith.addi %400, %492 : i64
llvm.store %491, %395 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%493 = llvm.load %385 : !llvm.ptr -> i64
%494 = arith.constant 0 : i32
%495 = arith.extsi %494 : i32 to i64
%496 = llvm.getelementptr %arg1[%495] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %493, %496 : i64, !llvm.ptr
%497 = llvm.load %388 : !llvm.ptr -> i64
%498 = arith.constant 1 : i32
%499 = arith.extsi %498 : i32 to i64
%500 = llvm.getelementptr %arg1[%499] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %497, %500 : i64, !llvm.ptr
%501 = llvm.load %391 : !llvm.ptr -> i64
%502 = arith.constant 2 : i32
%503 = arith.extsi %502 : i32 to i64
%504 = llvm.getelementptr %arg1[%503] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %501, %504 : i64, !llvm.ptr
%506 = llvm.load %385 : !llvm.ptr -> i64
%507 = llvm.load %388 : !llvm.ptr -> i64
%508 = llvm.load %391 : !llvm.ptr -> i64
func.call @cache_put(%arg0, %506, %507, %508) : (i64, i64, i64, i64) -> ()
func.return
}
func.func @tp_init(%arg0: i64) -> () {
%509 = llvm.mlir.addressof @tp_limit : !llvm.ptr
llvm.store %arg0, %509 : i64, !llvm.ptr
%511 = arith.constant 1 : i32
%513 = arith.extsi %511 : i32 to i64
%512 = arith.addi %arg0, %513 : i64
%514 = arith.constant 4 : i32
%516 = arith.extsi %514 : i32 to i64
%515 = arith.muli %512, %516 : i64
%510 = func.call @malloc(%515) : (i64) -> !llvm.ptr
%517 = arith.constant 0 : i32
%518 = arith.extsi %517 : i32 to i64
%519 = llvm.mlir.constant(1 : i64) : i64
%520 = llvm.alloca %519 x i64 : (i64) -> !llvm.ptr
llvm.store %518, %520 : i64, !llvm.ptr
cf.br ^bb48
^bb48:
%521 = llvm.load %520 : !llvm.ptr -> i64
%522 = arith.cmpi sle, %521, %arg0 : i64
cf.cond_br %522, ^bb49, ^bb50
^bb49:
%523 = llvm.load %520 : !llvm.ptr -> i64
%524 = arith.trunci %523 : i64 to i32
%525 = llvm.load %520 : !llvm.ptr -> i64
%526 = llvm.getelementptr %510[%525] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %524, %526 : i32, !llvm.ptr
%527 = llvm.load %520 : !llvm.ptr -> i64
%528 = arith.constant 1 : i32
%530 = arith.extsi %528 : i32 to i64
%529 = arith.addi %527, %530 : i64
llvm.store %529, %520 : i64, !llvm.ptr
cf.br ^bb48
^bb50:
%531 = arith.constant 2 : i32
%532 = arith.extsi %531 : i32 to i64
%533 = llvm.mlir.constant(1 : i64) : i64
%534 = llvm.alloca %533 x i64 : (i64) -> !llvm.ptr
llvm.store %532, %534 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%535 = llvm.load %534 : !llvm.ptr -> i64
%536 = arith.cmpi sle, %535, %arg0 : i64
cf.cond_br %536, ^bb52, ^bb53
^bb52:
%538 = llvm.load %534 : !llvm.ptr -> i64
%539 = llvm.getelementptr %510[%538] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%537 = llvm.load %539 : !llvm.ptr -> i32
%540 = arith.extsi %537 : i32 to i64
%541 = llvm.load %534 : !llvm.ptr -> i64
%542 = arith.cmpi eq, %540, %541 : i64
cf.cond_br %542, ^bb54, ^bb55
^bb54:
%543 = llvm.load %534 : !llvm.ptr -> i64
%544 = llvm.mlir.constant(1 : i64) : i64
%545 = llvm.alloca %544 x i64 : (i64) -> !llvm.ptr
llvm.store %543, %545 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%546 = llvm.load %545 : !llvm.ptr -> i64
%547 = arith.cmpi sle, %546, %arg0 : i64
cf.cond_br %547, ^bb58, ^bb59
^bb58:
%549 = llvm.load %545 : !llvm.ptr -> i64
%550 = llvm.getelementptr %510[%549] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%548 = llvm.load %550 : !llvm.ptr -> i32
%552 = llvm.load %545 : !llvm.ptr -> i64
%553 = llvm.getelementptr %510[%552] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%551 = llvm.load %553 : !llvm.ptr -> i32
%554 = llvm.load %534 : !llvm.ptr -> i64
%555 = arith.trunci %554 : i64 to i32
%556 = arith.divsi %551, %555 : i32
%557 = arith.subi %548, %556 : i32
%558 = llvm.load %545 : !llvm.ptr -> i64
%559 = llvm.getelementptr %510[%558] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %557, %559 : i32, !llvm.ptr
%560 = llvm.load %545 : !llvm.ptr -> i64
%561 = llvm.load %534 : !llvm.ptr -> i64
%562 = arith.addi %560, %561 : i64
llvm.store %562, %545 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%563 = llvm.load %534 : !llvm.ptr -> i64
%564 = arith.constant 1 : i32
%566 = arith.extsi %564 : i32 to i64
%565 = arith.addi %563, %566 : i64
llvm.store %565, %534 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%568 = arith.constant 1 : i32
%570 = arith.extsi %568 : i32 to i64
%569 = arith.addi %arg0, %570 : i64
%571 = arith.constant 4 : i32
%572 = arith.extsi %571 : i32 to i64
%567 = func.call @calloc(%569, %572) : (i64, i64) -> !llvm.ptr
%573 = llvm.mlir.addressof @tp_pref0 : !llvm.ptr
llvm.store %567, %573 : !llvm.ptr, !llvm.ptr
%575 = arith.constant 1 : i32
%577 = arith.extsi %575 : i32 to i64
%576 = arith.addi %arg0, %577 : i64
%578 = arith.constant 4 : i32
%579 = arith.extsi %578 : i32 to i64
%574 = func.call @calloc(%576, %579) : (i64, i64) -> !llvm.ptr
%580 = llvm.mlir.addressof @tp_pref1 : !llvm.ptr
llvm.store %574, %580 : !llvm.ptr, !llvm.ptr
%582 = arith.constant 1 : i32
%584 = arith.extsi %582 : i32 to i64
%583 = arith.addi %arg0, %584 : i64
%585 = arith.constant 4 : i32
%586 = arith.extsi %585 : i32 to i64
%581 = func.call @calloc(%583, %586) : (i64, i64) -> !llvm.ptr
%587 = llvm.mlir.addressof @tp_pref2 : !llvm.ptr
llvm.store %581, %587 : !llvm.ptr, !llvm.ptr
%588 = arith.constant 0 : i32
%589 = arith.extsi %588 : i32 to i64
%590 = llvm.mlir.constant(1 : i64) : i64
%591 = llvm.alloca %590 x i64 : (i64) -> !llvm.ptr
llvm.store %589, %591 : i64, !llvm.ptr
%592 = arith.constant 0 : i32
%593 = arith.extsi %592 : i32 to i64
%594 = llvm.mlir.constant(1 : i64) : i64
%595 = llvm.alloca %594 x i64 : (i64) -> !llvm.ptr
llvm.store %593, %595 : i64, !llvm.ptr
%596 = arith.constant 0 : i32
%597 = arith.extsi %596 : i32 to i64
%598 = llvm.mlir.constant(1 : i64) : i64
%599 = llvm.alloca %598 x i64 : (i64) -> !llvm.ptr
llvm.store %597, %599 : i64, !llvm.ptr
%600 = arith.constant 1 : i32
%601 = arith.extsi %600 : i32 to i64
llvm.store %601, %520 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%602 = llvm.load %520 : !llvm.ptr -> i64
%603 = arith.cmpi sle, %602, %arg0 : i64
cf.cond_br %603, ^bb61, ^bb62
^bb61:
%605 = llvm.load %520 : !llvm.ptr -> i64
%606 = llvm.getelementptr %510[%605] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%604 = llvm.load %606 : !llvm.ptr -> i32
%607 = arith.extsi %604 : i32 to i64
%608 = llvm.load %520 : !llvm.ptr -> i64
%609 = llvm.mlir.addressof @MOD : !llvm.ptr
%610 = llvm.load %609 : !llvm.ptr -> i64
%611 = arith.remsi %608, %610 : i64
%612 = llvm.load %591 : !llvm.ptr -> i64
%613 = arith.addi %612, %607 : i64
%614 = llvm.mlir.addressof @MOD : !llvm.ptr
%615 = llvm.load %614 : !llvm.ptr -> i64
%616 = arith.remsi %613, %615 : i64
llvm.store %616, %591 : i64, !llvm.ptr
%617 = llvm.load %595 : !llvm.ptr -> i64
%618 = arith.muli %611, %607 : i64
%619 = llvm.mlir.addressof @MOD : !llvm.ptr
%620 = llvm.load %619 : !llvm.ptr -> i64
%621 = arith.remsi %618, %620 : i64
%622 = arith.addi %617, %621 : i64
%623 = llvm.mlir.addressof @MOD : !llvm.ptr
%624 = llvm.load %623 : !llvm.ptr -> i64
%625 = arith.remsi %622, %624 : i64
llvm.store %625, %595 : i64, !llvm.ptr
%626 = llvm.load %599 : !llvm.ptr -> i64
%627 = arith.muli %611, %611 : i64
%628 = llvm.mlir.addressof @MOD : !llvm.ptr
%629 = llvm.load %628 : !llvm.ptr -> i64
%630 = arith.remsi %627, %629 : i64
%631 = arith.muli %630, %607 : i64
%632 = llvm.mlir.addressof @MOD : !llvm.ptr
%633 = llvm.load %632 : !llvm.ptr -> i64
%634 = arith.remsi %631, %633 : i64
%635 = arith.addi %626, %634 : i64
%636 = llvm.mlir.addressof @MOD : !llvm.ptr
%637 = llvm.load %636 : !llvm.ptr -> i64
%638 = arith.remsi %635, %637 : i64
llvm.store %638, %599 : i64, !llvm.ptr
%639 = llvm.load %591 : !llvm.ptr -> i64
%640 = arith.trunci %639 : i64 to i32
%641 = llvm.mlir.addressof @tp_pref0 : !llvm.ptr
%642 = llvm.load %641 : !llvm.ptr -> !llvm.ptr
%643 = llvm.load %520 : !llvm.ptr -> i64
%644 = llvm.getelementptr %642[%643] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %640, %644 : i32, !llvm.ptr
%645 = llvm.load %595 : !llvm.ptr -> i64
%646 = arith.trunci %645 : i64 to i32
%647 = llvm.mlir.addressof @tp_pref1 : !llvm.ptr
%648 = llvm.load %647 : !llvm.ptr -> !llvm.ptr
%649 = llvm.load %520 : !llvm.ptr -> i64
%650 = llvm.getelementptr %648[%649] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %646, %650 : i32, !llvm.ptr
%651 = llvm.load %599 : !llvm.ptr -> i64
%652 = arith.trunci %651 : i64 to i32
%653 = llvm.mlir.addressof @tp_pref2 : !llvm.ptr
%654 = llvm.load %653 : !llvm.ptr -> !llvm.ptr
%655 = llvm.load %520 : !llvm.ptr -> i64
%656 = llvm.getelementptr %654[%655] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %652, %656 : i32, !llvm.ptr
%657 = llvm.load %520 : !llvm.ptr -> i64
%658 = arith.constant 1 : i32
%660 = arith.extsi %658 : i32 to i64
%659 = arith.addi %657, %660 : i64
llvm.store %659, %520 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
func.call @free(%510) : (!llvm.ptr) -> ()
%662 = arith.constant 1 : i32
%663 = arith.constant 20 : i32
%664 = arith.shli %662, %663 : i32
%665 = arith.extsi %664 : i32 to i64
%666 = llvm.mlir.addressof @cache_size : !llvm.ptr
llvm.store %665, %666 : i64, !llvm.ptr
%667 = arith.constant 0 : i32
%668 = arith.extsi %667 : i32 to i64
%669 = llvm.mlir.addressof @cache_count : !llvm.ptr
llvm.store %668, %669 : i64, !llvm.ptr
%671 = llvm.mlir.addressof @cache_size : !llvm.ptr
%672 = llvm.load %671 : !llvm.ptr -> i64
%673 = arith.constant 8 : i32
%674 = arith.extsi %673 : i32 to i64
%670 = func.call @calloc(%672, %674) : (i64, i64) -> !llvm.ptr
%675 = llvm.mlir.addressof @cache_key : !llvm.ptr
llvm.store %670, %675 : !llvm.ptr, !llvm.ptr
%677 = llvm.mlir.addressof @cache_size : !llvm.ptr
%678 = llvm.load %677 : !llvm.ptr -> i64
%679 = arith.constant 8 : i32
%680 = arith.extsi %679 : i32 to i64
%676 = func.call @calloc(%678, %680) : (i64, i64) -> !llvm.ptr
%681 = llvm.mlir.addressof @cache_f0 : !llvm.ptr
llvm.store %676, %681 : !llvm.ptr, !llvm.ptr
%683 = llvm.mlir.addressof @cache_size : !llvm.ptr
%684 = llvm.load %683 : !llvm.ptr -> i64
%685 = arith.constant 8 : i32
%686 = arith.extsi %685 : i32 to i64
%682 = func.call @calloc(%684, %686) : (i64, i64) -> !llvm.ptr
%687 = llvm.mlir.addressof @cache_f1 : !llvm.ptr
llvm.store %682, %687 : !llvm.ptr, !llvm.ptr
%689 = llvm.mlir.addressof @cache_size : !llvm.ptr
%690 = llvm.load %689 : !llvm.ptr -> i64
%691 = arith.constant 8 : i32
%692 = arith.extsi %691 : i32 to i64
%688 = func.call @calloc(%690, %692) : (i64, i64) -> !llvm.ptr
%693 = llvm.mlir.addressof @cache_f2 : !llvm.ptr
llvm.store %688, %693 : !llvm.ptr, !llvm.ptr
%695 = llvm.mlir.addressof @cache_size : !llvm.ptr
%696 = llvm.load %695 : !llvm.ptr -> i64
%697 = arith.constant 1 : i32
%698 = arith.extsi %697 : i32 to i64
%694 = func.call @calloc(%696, %698) : (i64, i64) -> !llvm.ptr
%699 = llvm.mlir.addressof @cache_used : !llvm.ptr
llvm.store %694, %699 : !llvm.ptr, !llvm.ptr
%701 = arith.constant 768 : i32
%702 = arith.constant 8 : i32
%703 = arith.extsi %701 : i32 to i64
%704 = arith.extsi %702 : i32 to i64
%700 = func.call @calloc(%703, %704) : (i64, i64) -> !llvm.ptr
%705 = llvm.mlir.addressof @tp_scratch : !llvm.ptr
llvm.store %700, %705 : !llvm.ptr, !llvm.ptr
%706 = arith.constant 0 : i32
%707 = arith.extsi %706 : i32 to i64
%708 = llvm.mlir.addressof @tp_depth : !llvm.ptr
llvm.store %707, %708 : i64, !llvm.ptr
func.return
}
func.func @nonconcurrent_candidate_count(%arg0: i64, %arg1: i64) -> i64 {
%709 = llvm.mlir.addressof @MOD : !llvm.ptr
%710 = llvm.load %709 : !llvm.ptr -> i64
%711 = arith.remsi %arg0, %710 : i64
%712 = arith.constant 1 : i32
%714 = arith.extsi %712 : i32 to i64
%713 = arith.subi %711, %714 : i64
%715 = llvm.mlir.addressof @MOD : !llvm.ptr
%716 = llvm.load %715 : !llvm.ptr -> i64
%717 = arith.addi %713, %716 : i64
%718 = llvm.mlir.addressof @MOD : !llvm.ptr
%719 = llvm.load %718 : !llvm.ptr -> i64
%720 = arith.remsi %717, %719 : i64
%721 = llvm.mlir.addressof @MOD : !llvm.ptr
%722 = llvm.load %721 : !llvm.ptr -> i64
%723 = arith.remsi %arg1, %722 : i64
%724 = arith.constant 1 : i32
%726 = arith.extsi %724 : i32 to i64
%725 = arith.subi %723, %726 : i64
%727 = llvm.mlir.addressof @MOD : !llvm.ptr
%728 = llvm.load %727 : !llvm.ptr -> i64
%729 = arith.addi %725, %728 : i64
%730 = llvm.mlir.addressof @MOD : !llvm.ptr
%731 = llvm.load %730 : !llvm.ptr -> i64
%732 = arith.remsi %729, %731 : i64
%733 = arith.constant 1 : i32
%735 = arith.extsi %733 : i32 to i64
%734 = arith.addi %723, %735 : i64
%736 = llvm.mlir.addressof @MOD : !llvm.ptr
%737 = llvm.load %736 : !llvm.ptr -> i64
%738 = arith.remsi %734, %737 : i64
%743 = func.call @mulmod(%711, %720) : (i64, i64) -> i64
%742 = func.call @mulmod(%743, %723) : (i64, i64) -> i64
%741 = func.call @mulmod(%742, %732) : (i64, i64) -> i64
%740 = func.call @mulmod(%741, %738) : (i64, i64) -> i64
%744 = llvm.mlir.addressof @INV6 : !llvm.ptr
%745 = llvm.load %744 : !llvm.ptr -> i64
%739 = func.call @mulmod(%740, %745) : (i64, i64) -> i64
%747 = arith.constant 2 : i32
%749 = arith.extsi %747 : i32 to i64
%748 = arith.addi %arg1, %749 : i64
%746 = func.call @c3_mod(%748) : (i64) -> i64
%750 = llvm.mlir.addressof @MOD : !llvm.ptr
%751 = llvm.load %750 : !llvm.ptr -> i64
%752 = arith.remsi %arg1, %751 : i64
%753 = arith.subi %746, %752 : i64
%754 = llvm.mlir.addressof @MOD : !llvm.ptr
%755 = llvm.load %754 : !llvm.ptr -> i64
%756 = arith.addi %753, %755 : i64
%757 = llvm.mlir.addressof @MOD : !llvm.ptr
%758 = llvm.load %757 : !llvm.ptr -> i64
%759 = arith.remsi %756, %758 : i64
%761 = func.call @c3_mod(%arg0) : (i64) -> i64
%760 = func.call @mulmod(%761, %759) : (i64, i64) -> i64
%762 = arith.addi %739, %760 : i64
%763 = llvm.mlir.addressof @MOD : !llvm.ptr
%764 = llvm.load %763 : !llvm.ptr -> i64
%765 = arith.remsi %762, %764 : i64
func.return %765 : i64
}
func.func @weighted_gcd_sum(%arg0: i64, %arg1: i64) -> i64 {
%766 = arith.constant 1 : i32
%768 = arith.extsi %766 : i32 to i64
%767 = arith.subi %arg0, %768 : i64
%769 = arith.constant 1 : i32
%771 = arith.extsi %769 : i32 to i64
%770 = arith.subi %arg1, %771 : i64
%772 = arith.cmpi slt, %767, %770 : i64
%773 = scf.if %772 -> (i64) {
scf.yield %767 : i64
} else {
scf.yield %770 : i64
}
%774 = arith.constant 0 : i32
%775 = arith.extsi %774 : i32 to i64
%776 = llvm.mlir.constant(1 : i64) : i64
%777 = llvm.alloca %776 x i64 : (i64) -> !llvm.ptr
llvm.store %775, %777 : i64, !llvm.ptr
# String concatenation: !llvm.ptr + i32
# String concatenation: !llvm.ptr + i32
%780 = arith.constant 2 : i32
%781 = arith.extsi %780 : i32 to i64
%782 = llvm.mlir.addressof @tp_depth : !llvm.ptr
llvm.store %781, %782 : i64, !llvm.ptr
%783 = arith.constant 1 : i32
%784 = arith.extsi %783 : i32 to i64
%785 = llvm.mlir.constant(1 : i64) : i64
%786 = llvm.alloca %785 x i64 : (i64) -> !llvm.ptr
llvm.store %784, %786 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%787 = llvm.load %786 : !llvm.ptr -> i64
%788 = arith.cmpi sle, %787, %773 : i64
cf.cond_br %788, ^bb64, ^bb65
^bb64:
%789 = llvm.load %786 : !llvm.ptr -> i64
%790 = arith.divsi %767, %789 : i64
%791 = llvm.load %786 : !llvm.ptr -> i64
%792 = arith.divsi %770, %791 : i64
%793 = arith.divsi %767, %790 : i64
%794 = llvm.mlir.constant(1 : i64) : i64
%795 = llvm.alloca %794 x i64 : (i64) -> !llvm.ptr
llvm.store %793, %795 : i64, !llvm.ptr
%796 = arith.divsi %770, %792 : i64
%797 = llvm.load %795 : !llvm.ptr -> i64
%798 = arith.cmpi slt, %796, %797 : i64
cf.cond_br %798, ^bb66, ^bb67
^bb66:
%799 = arith.divsi %770, %792 : i64
llvm.store %799, %795 : i64, !llvm.ptr
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
%800 = llvm.load %795 : !llvm.ptr -> i64
%801 = arith.cmpi slt, %773, %800 : i64
cf.cond_br %801, ^bb69, ^bb70
^bb69:
llvm.store %773, %795 : i64, !llvm.ptr
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
%803 = llvm.load %795 : !llvm.ptr -> i64
func.call @tp_values(%803, %778) : (i64, !llvm.ptr) -> ()
%805 = llvm.load %786 : !llvm.ptr -> i64
%806 = arith.constant 1 : i32
%808 = arith.extsi %806 : i32 to i64
%807 = arith.subi %805, %808 : i64
func.call @tp_values(%807, %779) : (i64, !llvm.ptr) -> ()
%810 = arith.constant 0 : i32
%811 = arith.extsi %810 : i32 to i64
%812 = llvm.getelementptr %778[%811] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%809 = llvm.load %812 : !llvm.ptr -> i64
%814 = arith.constant 0 : i32
%815 = arith.extsi %814 : i32 to i64
%816 = llvm.getelementptr %779[%815] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%813 = llvm.load %816 : !llvm.ptr -> i64
%817 = arith.subi %809, %813 : i64
%818 = llvm.mlir.addressof @MOD : !llvm.ptr
%819 = llvm.load %818 : !llvm.ptr -> i64
%820 = arith.addi %817, %819 : i64
%821 = llvm.mlir.addressof @MOD : !llvm.ptr
%822 = llvm.load %821 : !llvm.ptr -> i64
%823 = arith.remsi %820, %822 : i64
%825 = arith.constant 1 : i32
%826 = arith.extsi %825 : i32 to i64
%827 = llvm.getelementptr %778[%826] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%824 = llvm.load %827 : !llvm.ptr -> i64
%829 = arith.constant 1 : i32
%830 = arith.extsi %829 : i32 to i64
%831 = llvm.getelementptr %779[%830] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%828 = llvm.load %831 : !llvm.ptr -> i64
%832 = arith.subi %824, %828 : i64
%833 = llvm.mlir.addressof @MOD : !llvm.ptr
%834 = llvm.load %833 : !llvm.ptr -> i64
%835 = arith.addi %832, %834 : i64
%836 = llvm.mlir.addressof @MOD : !llvm.ptr
%837 = llvm.load %836 : !llvm.ptr -> i64
%838 = arith.remsi %835, %837 : i64
%840 = arith.constant 2 : i32
%841 = arith.extsi %840 : i32 to i64
%842 = llvm.getelementptr %778[%841] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%839 = llvm.load %842 : !llvm.ptr -> i64
%844 = arith.constant 2 : i32
%845 = arith.extsi %844 : i32 to i64
%846 = llvm.getelementptr %779[%845] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%843 = llvm.load %846 : !llvm.ptr -> i64
%847 = arith.subi %839, %843 : i64
%848 = llvm.mlir.addressof @MOD : !llvm.ptr
%849 = llvm.load %848 : !llvm.ptr -> i64
%850 = arith.addi %847, %849 : i64
%851 = llvm.mlir.addressof @MOD : !llvm.ptr
%852 = llvm.load %851 : !llvm.ptr -> i64
%853 = arith.remsi %850, %852 : i64
%854 = llvm.mlir.addressof @MOD : !llvm.ptr
%855 = llvm.load %854 : !llvm.ptr -> i64
%856 = arith.remsi %790, %855 : i64
%857 = llvm.mlir.addressof @MOD : !llvm.ptr
%858 = llvm.load %857 : !llvm.ptr -> i64
%859 = arith.remsi %792, %858 : i64
%861 = llvm.mlir.addressof @MOD : !llvm.ptr
%862 = llvm.load %861 : !llvm.ptr -> i64
%863 = arith.remsi %arg0, %862 : i64
%860 = func.call @mulmod(%856, %863) : (i64, i64) -> i64
%867 = arith.constant 0 : i64
%866 = arith.subi %867, %856 : i64
%868 = llvm.mlir.addressof @MOD : !llvm.ptr
%869 = llvm.load %868 : !llvm.ptr -> i64
%870 = arith.addi %866, %869 : i64
%871 = arith.constant 1 : i32
%873 = arith.extsi %871 : i32 to i64
%872 = arith.addi %790, %873 : i64
%874 = llvm.mlir.addressof @MOD : !llvm.ptr
%875 = llvm.load %874 : !llvm.ptr -> i64
%876 = arith.remsi %872, %875 : i64
%865 = func.call @mulmod(%870, %876) : (i64, i64) -> i64
%877 = llvm.mlir.addressof @INV2 : !llvm.ptr
%878 = llvm.load %877 : !llvm.ptr -> i64
%864 = func.call @mulmod(%865, %878) : (i64, i64) -> i64
%880 = llvm.mlir.addressof @MOD : !llvm.ptr
%881 = llvm.load %880 : !llvm.ptr -> i64
%882 = arith.remsi %arg1, %881 : i64
%879 = func.call @mulmod(%859, %882) : (i64, i64) -> i64
%886 = arith.constant 0 : i64
%885 = arith.subi %886, %859 : i64
%887 = llvm.mlir.addressof @MOD : !llvm.ptr
%888 = llvm.load %887 : !llvm.ptr -> i64
%889 = arith.addi %885, %888 : i64
%890 = arith.constant 1 : i32
%892 = arith.extsi %890 : i32 to i64
%891 = arith.addi %792, %892 : i64
%893 = llvm.mlir.addressof @MOD : !llvm.ptr
%894 = llvm.load %893 : !llvm.ptr -> i64
%895 = arith.remsi %891, %894 : i64
%884 = func.call @mulmod(%889, %895) : (i64, i64) -> i64
%896 = llvm.mlir.addressof @INV2 : !llvm.ptr
%897 = llvm.load %896 : !llvm.ptr -> i64
%883 = func.call @mulmod(%884, %897) : (i64, i64) -> i64
%898 = func.call @mulmod(%860, %879) : (i64, i64) -> i64
%899 = func.call @mulmod(%860, %883) : (i64, i64) -> i64
%900 = func.call @mulmod(%864, %879) : (i64, i64) -> i64
%901 = arith.addi %899, %900 : i64
%902 = llvm.mlir.addressof @MOD : !llvm.ptr
%903 = llvm.load %902 : !llvm.ptr -> i64
%904 = arith.remsi %901, %903 : i64
%905 = func.call @mulmod(%864, %883) : (i64, i64) -> i64
%906 = arith.muli %898, %823 : i64
%907 = arith.muli %904, %838 : i64
%908 = arith.addi %906, %907 : i64
%909 = arith.muli %905, %853 : i64
%910 = arith.addi %908, %909 : i64
%911 = llvm.mlir.addressof @MOD : !llvm.ptr
%912 = llvm.load %911 : !llvm.ptr -> i64
%913 = arith.remsi %910, %912 : i64
%914 = llvm.mlir.constant(1 : i64) : i64
%915 = llvm.alloca %914 x i64 : (i64) -> !llvm.ptr
llvm.store %913, %915 : i64, !llvm.ptr
%916 = llvm.load %777 : !llvm.ptr -> i64
%917 = llvm.load %915 : !llvm.ptr -> i64
%918 = arith.addi %916, %917 : i64
%919 = llvm.mlir.addressof @MOD : !llvm.ptr
%920 = llvm.load %919 : !llvm.ptr -> i64
%921 = arith.remsi %918, %920 : i64
llvm.store %921, %777 : i64, !llvm.ptr
%922 = llvm.load %795 : !llvm.ptr -> i64
%923 = arith.constant 1 : i32
%925 = arith.extsi %923 : i32 to i64
%924 = arith.addi %922, %925 : i64
llvm.store %924, %786 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
%926 = llvm.load %777 : !llvm.ptr -> i64
func.return %926 : i64
}
func.func @concurrent_triple_count(%arg0: i64, %arg1: i64) -> i64 {
%927 = func.call @weighted_gcd_sum(%arg0, %arg1) : (i64, i64) -> i64
%929 = func.call @c2_mod(%arg0) : (i64) -> i64
%930 = func.call @c2_mod(%arg1) : (i64) -> i64
%928 = func.call @mulmod(%929, %930) : (i64, i64) -> i64
%931 = arith.subi %927, %928 : i64
%932 = llvm.mlir.addressof @MOD : !llvm.ptr
%933 = llvm.load %932 : !llvm.ptr -> i64
%934 = arith.addi %931, %933 : i64
%935 = llvm.mlir.addressof @MOD : !llvm.ptr
%936 = llvm.load %935 : !llvm.ptr -> i64
%937 = arith.remsi %934, %936 : i64
func.return %937 : i64
}
func.func @main() -> i32 {
%938 = llvm.mlir.addressof @MOD : !llvm.ptr
%939 = llvm.load %938 : !llvm.ptr -> i64
%940 = arith.constant 1 : i32
%942 = arith.extsi %940 : i32 to i64
%941 = arith.addi %939, %942 : i64
%943 = arith.constant 2 : i32
%945 = arith.extsi %943 : i32 to i64
%944 = arith.divsi %941, %945 : i64
%946 = llvm.mlir.addressof @INV2 : !llvm.ptr
llvm.store %944, %946 : i64, !llvm.ptr
%948 = arith.constant 6 : i32
%949 = llvm.mlir.addressof @MOD : !llvm.ptr
%950 = llvm.load %949 : !llvm.ptr -> i64
%951 = arith.constant 2 : i32
%953 = arith.extsi %951 : i32 to i64
%952 = arith.subi %950, %953 : i64
%954 = arith.extsi %948 : i32 to i64
%947 = func.call @mod_pow(%954, %952) : (i64, i64) -> i64
%955 = llvm.mlir.addressof @INV6 : !llvm.ptr
llvm.store %947, %955 : i64, !llvm.ptr
%956 = arith.constant 12000000 : i32
%957 = arith.extsi %956 : i32 to i64
func.call @tp_init(%957) : (i64) -> ()
%959 = arith.constant 1234 : i32
%960 = arith.extsi %959 : i32 to i64
%961 = arith.constant 100000000 : i32
%963 = arith.extsi %961 : i32 to i64
%962 = arith.muli %960, %963 : i64
%964 = arith.constant 2345 : i32
%965 = arith.extsi %964 : i32 to i64
%966 = arith.constant 100000000 : i32
%968 = arith.extsi %966 : i32 to i64
%967 = arith.muli %965, %968 : i64
%969 = func.call @nonconcurrent_candidate_count(%962, %967) : (i64, i64) -> i64
%970 = func.call @concurrent_triple_count(%962, %967) : (i64, i64) -> i64
%971 = arith.subi %969, %970 : i64
%972 = llvm.mlir.addressof @MOD : !llvm.ptr
%973 = llvm.load %972 : !llvm.ptr -> i64
%974 = arith.addi %971, %973 : i64
%975 = llvm.mlir.addressof @MOD : !llvm.ptr
%976 = llvm.load %975 : !llvm.ptr -> i64
%977 = arith.remsi %974, %976 : i64
%978 = llvm.mlir.addressof @str_0 : !llvm.ptr
%979 = llvm.call @printf(%978, %977) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%981 = llvm.mlir.addressof @tp_pref0 : !llvm.ptr
%982 = llvm.load %981 : !llvm.ptr -> !llvm.ptr
func.call @free(%982) : (!llvm.ptr) -> ()
%984 = llvm.mlir.addressof @tp_pref1 : !llvm.ptr
%985 = llvm.load %984 : !llvm.ptr -> !llvm.ptr
func.call @free(%985) : (!llvm.ptr) -> ()
%987 = llvm.mlir.addressof @tp_pref2 : !llvm.ptr
%988 = llvm.load %987 : !llvm.ptr -> !llvm.ptr
func.call @free(%988) : (!llvm.ptr) -> ()
%990 = llvm.mlir.addressof @tp_scratch : !llvm.ptr
%991 = llvm.load %990 : !llvm.ptr -> !llvm.ptr
func.call @free(%991) : (!llvm.ptr) -> ()
%993 = llvm.mlir.addressof @cache_key : !llvm.ptr
%994 = llvm.load %993 : !llvm.ptr -> !llvm.ptr
func.call @free(%994) : (!llvm.ptr) -> ()
%996 = llvm.mlir.addressof @cache_f0 : !llvm.ptr
%997 = llvm.load %996 : !llvm.ptr -> !llvm.ptr
func.call @free(%997) : (!llvm.ptr) -> ()
%999 = llvm.mlir.addressof @cache_f1 : !llvm.ptr
%1000 = llvm.load %999 : !llvm.ptr -> !llvm.ptr
func.call @free(%1000) : (!llvm.ptr) -> ()
%1002 = llvm.mlir.addressof @cache_f2 : !llvm.ptr
%1003 = llvm.load %1002 : !llvm.ptr -> !llvm.ptr
func.call @free(%1003) : (!llvm.ptr) -> ()
%1005 = llvm.mlir.addressof @cache_used : !llvm.ptr
%1006 = llvm.load %1005 : !llvm.ptr -> !llvm.ptr
func.call @free(%1006) : (!llvm.ptr) -> ()
%1007 = arith.constant 0 : i32
func.return %1007 : i32
}
}