← All problems Problem 947
Ported from native C to pure Flow. Compute S(10^6) modulo 999999893.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^4)?Space complexity O(n^2)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 947: Fibonacci Residues
# Ported from native C to pure Flow.
# Compute S(10^6) modulo 999999893.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
const MOD: i64 = 999999893
const N: i64 = 1000000
# SPF sieve
let mut spf: ptr<i32> = null
# Precomputed pi(p) and k for primes
let mut pi_prime: ptr<i64> = null
let mut k_prime: ptr<i64> = null
# Distribution cache
let mut dc_p: ptr<i64> = null
let mut dc_e: ptr<i64> = null
let mut dc_ne: ptr<i64> = null
let mut dc_period: ptr<i64> = null
let mut dc_count: ptr<i64> = null
let mut dc_size: i64 = 0
# fib_pair outputs
let mut g_fn: i64 = 0
let mut g_fn1: i64 = 0
# Dict arrays for CRT combination
let mut cur_key: ptr<i64> = null
let mut cur_val: ptr<i64> = null
let mut new_key: ptr<i64> = null
let mut new_val: ptr<i64> = null
function clzll(n: i64) -> i64 {
if n <= 0 {
return 64
}
let mut count: i64 = 0
let mut v: i64 = n
while v > 0 {
v = v >> 1
count = count + 1
}
return 64 - count
}
function mod_pow(a0: i64, e0: i64, mod: i64) -> i64 {
let mut r: i64 = 1 % mod
let mut a: i64 = a0 % mod
if a < 0 {
a = a + mod
}
let mut e: i64 = e0
while e > 0 {
if (e & 1) != 0 {
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 sieve_spf(limit: i64) -> void {
spf = calloc(limit + 1, 4) as ptr<i32>
let mut i: i64 = 0
while i <= limit {
spf[i] = i as i32
i = i + 1
}
spf[0] = 0
spf[1] = 1
let mut i2: i64 = 2
while i2 * i2 <= limit {
if spf[i2] == i2 as i32 {
let mut j: i64 = i2 * i2
while j <= limit {
if spf[j] == j as i32 {
spf[j] = i2 as i32
}
j = j + i2
}
}
i2 = i2 + 1
}
}
function fib_pair(n: i64, mod: i64) -> void {
let mut a: i64 = 0
let mut b: i64 = 1 % mod
if n == 0 {
g_fn = 0
g_fn1 = b
return
}
let nbits: i64 = 64 - clzll(n)
let mut i: i64 = nbits - 1
while i >= 0 {
let mut two_b_minus_a: i64 = (2 * b - a) % mod
if two_b_minus_a < 0 {
two_b_minus_a = two_b_minus_a + mod
}
let c: i64 = (((a as i128) * (two_b_minus_a as i128)) % (mod as i128)) as i64
let mut d: i64 = (((((a as i128) * (a as i128)) % (mod as i128)) + (((b as i128) * (b as i128)) % (mod as i128))) % (mod as i128)) as i64
if d < 0 {
d = d + mod
}
if ((n >> i) & 1) != 0 {
a = d
b = (c + d) % mod
} else {
a = c
b = d
}
i = i - 1
}
g_fn = a
g_fn1 = b
}
function check_A_order(n: i64, p: i64) -> bool {
fib_pair(n, p)
return g_fn == 0 && g_fn1 == 1
}
function pisano_prime(p: i64) -> i64 {
if p == 2 {
return 3
}
if p == 5 {
return 20
}
let residue: i64 = mod_pow(5, (p - 1) / 2, p)
let mut candidate: i64 = 0
if residue == 1 {
candidate = p - 1
} else {
candidate = 2 * (p + 1)
}
# Factor candidate using SPF
let mut x: i64 = candidate
let mut distinct_primes: array<i64, 32> = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
let mut ndp: i64 = 0
while x > 1 {
let q: i64 = spf[x] as i64
distinct_primes[ndp] = q
ndp = ndp + 1
while x % q == 0 {
x = x / q
}
}
let mut d: i64 = candidate
let mut i: i64 = 0
while i < ndp {
let q: i64 = distinct_primes[i]
while d % q == 0 {
let nd: i64 = d / q
if check_A_order(nd, p) {
d = nd
} else {
break
}
}
i = i + 1
}
return d
}
function has_short_period_factor(p: i64, pi_p: i64) -> i64 {
if p == 5 {
return 5
}
if p == 2 {
return 1
}
if mod_pow(5, (p - 1) / 2, p) != 1 {
return 1
}
if pi_p % 2 != 0 {
return 1
}
let n: i64 = pi_p / 2
fib_pair(n, p)
let mut ln: i64 = (2 * g_fn1 - g_fn) % p
if ln < 0 {
ln = ln + p
}
let mut det: i64 = 0
if n % 2 == 0 {
det = (1 + 1 - ln) % p
} else {
det = (1 + (p - 1) - ln) % p
}
if det < 0 {
det = det + p
}
if det == 0 {
return 2
}
return 1
}
function gcd_i64(a0: i64, b0: i64) -> i64 {
let mut a: i64 = a0
let mut b: i64 = b0
while b != 0 {
let t: i64 = a % b
a = b
b = t
}
return a
}
# Returns cache index for (p, e), sets g_dist_ne
let mut g_dist_ne: i64 = 0
function get_distribution(p: i64, e: i64, pi_p: i64, k: i64) -> i64 {
# Check cache
let mut i: i64 = 0
while i < dc_size {
if dc_p[i] == p && dc_e[i] == e {
g_dist_ne = dc_ne[i]
return i
}
i = i + 1
}
# Compute distribution
let mut pe1: i64 = 1
let mut j: i64 = 0
while j < e - 1 {
pe1 = pe1 * p
j = j + 1
}
let T: i64 = pi_p * pe1
let p2: i64 = p * p
let mut total: i64 = 1
j = 0
while j < e - 1 {
total = total * p2
j = j + 1
}
total = total * (p2 - 1)
let idx: i64 = dc_size
dc_p[idx] = p
dc_e[idx] = e
if k == 1 {
dc_period[idx * 2] = T
dc_count[idx * 2] = total % MOD
dc_ne[idx] = 1
g_dist_ne = 1
} else {
if k == 2 {
let small_period: i64 = T / 2
let small_count: i64 = (p - 1) * pe1
let big_count: i64 = total - small_count
dc_period[idx * 2] = small_period
dc_count[idx * 2] = small_count % MOD
dc_period[idx * 2 + 1] = T
dc_count[idx * 2 + 1] = big_count % MOD
dc_ne[idx] = 2
g_dist_ne = 2
} else {
# k == 5 (only for p=5)
let small_period: i64 = T / 5
let mut small_count: i64 = (p - 1)
j = 0
while j < e - 1 {
small_count = small_count * p2
j = j + 1
}
let big_count: i64 = total - small_count
dc_period[idx * 2] = small_period
dc_count[idx * 2] = small_count % MOD
dc_period[idx * 2 + 1] = T
dc_count[idx * 2 + 1] = big_count % MOD
dc_ne[idx] = 2
g_dist_ne = 2
}
}
dc_size = dc_size + 1
return idx
}
function main() -> i32 {
let max_spf: i64 = 2 * N + 2
sieve_spf(max_spf)
pi_prime = calloc(N + 1, 8) as ptr<i64>
k_prime = malloc((N + 1) * 8) as ptr<i64>
let mut i: i64 = 0
while i <= N {
k_prime[i] = 1
i = i + 1
}
let mut p: i64 = 2
while p <= N {
if spf[p] == p as i32 {
let pi_p: i64 = pisano_prime(p)
pi_prime[p] = pi_p
k_prime[p] = has_short_period_factor(p, pi_p)
}
p = p + 1
}
# Allocate distribution cache
dc_p = malloc(100000 * 8) as ptr<i64>
dc_e = malloc(100000 * 8) as ptr<i64>
dc_ne = malloc(100000 * 8) as ptr<i64>
dc_period = malloc(200000 * 8) as ptr<i64>
dc_count = malloc(200000 * 8) as ptr<i64>
dc_size = 0
# Allocate dict arrays
cur_key = malloc(256 * 8) as ptr<i64>
cur_val = malloc(256 * 8) as ptr<i64>
new_key = malloc(256 * 8) as ptr<i64>
new_val = malloc(256 * 8) as ptr<i64>
let mut ans: i64 = 0
let mut n: i64 = 1
while n <= N {
let mut x: i64 = n
# Collect distributions for each prime power
let mut dist_indices: array<i64, 8> = [0, 0, 0, 0, 0, 0, 0, 0]
let mut dist_counts: array<i64, 8> = [0, 0, 0, 0, 0, 0, 0, 0]
let mut num_dists: i64 = 0
while x > 1 {
let pp: i64 = spf[x] as i64
let mut e: i64 = 0
while x % pp == 0 {
x = x / pp
e = e + 1
}
let didx: i64 = get_distribution(pp, e, pi_prime[pp], k_prime[pp])
dist_indices[num_dists] = didx
dist_counts[num_dists] = g_dist_ne
num_dists = num_dists + 1
}
# Combine distributions via CRT
let mut cur_size: i64 = 1
cur_key[0] = 1
cur_val[0] = 1
let mut di: i64 = 0
while di < num_dists {
let mut new_size: i64 = 0
let didx: i64 = dist_indices[di]
let dcnt: i64 = dist_counts[di]
let mut ci: i64 = 0
while ci < cur_size {
let mut ei: i64 = 0
while ei < dcnt {
let per1: i64 = cur_key[ci]
let per2: i64 = dc_period[didx * 2 + ei]
let g: i64 = gcd_i64(per1, per2)
let l: i128 = ((per1 as i128) / (g as i128)) * (per2 as i128)
let l_i64: i64 = l as i64
let v: i64 = (((cur_val[ci] as i128) * (dc_count[didx * 2 + ei] as i128)) % (MOD as i128)) as i64
# Find or insert l in new_dict
let mut found: i64 = -1
let mut j: i64 = 0
while j < new_size {
if new_key[j] == l_i64 {
found = j
break
}
j = j + 1
}
if found >= 0 {
new_val[found] = (new_val[found] + v) % MOD
} else {
new_key[new_size] = l_i64
new_val[new_size] = v
new_size = new_size + 1
}
ei = ei + 1
}
ci = ci + 1
}
# Copy new_dict to cur_dict, removing zeros
cur_size = 0
let mut j: i64 = 0
while j < new_size {
if new_val[j] != 0 {
cur_key[cur_size] = new_key[j]
cur_val[cur_size] = new_val[j]
cur_size = cur_size + 1
}
j = j + 1
}
di = di + 1
}
# Compute Pn = sum of per^2 * count mod MOD
let mut Pn: i64 = 0
let mut j: i64 = 0
while j < cur_size {
let per2: i64 = (((cur_key[j] as i128) * (cur_key[j] as i128)) % (MOD as i128)) as i64
Pn = (((Pn as i128) + (((per2 as i128) * (cur_val[j] as i128)) % (MOD as i128))) % (MOD as i128)) as i64
j = j + 1
}
ans = (((ans as i128) + (((Pn as i128) * ((N / n) as i128)) % (MOD as i128))) % (MOD as i128)) as i64
n = n + 1
}
printf("%lld\n", ans)
free(spf as ptr<void>)
free(pi_prime as ptr<void>)
free(k_prime as ptr<void>)
free(dc_p as ptr<void>)
free(dc_e as ptr<void>)
free(dc_ne as ptr<void>)
free(dc_period as ptr<void>)
free(dc_count as ptr<void>)
free(cur_key as ptr<void>)
free(cur_val as ptr<void>)
free(new_key as ptr<void>)
free(new_val 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 clzll_i64(int64_t n);
int64_t mod_pow_i64_i64_i64(int64_t a0, int64_t e0, int64_t mod);
void sieve_spf_i64(int64_t limit);
void fib_pair_i64_i64(int64_t n, int64_t mod);
bool check_A_order_i64_i64(int64_t n, int64_t p);
int64_t pisano_prime_i64(int64_t p);
int64_t has_short_period_factor_i64_i64(int64_t p, int64_t pi_p);
int64_t gcd_i64_i64_i64(int64_t a0, int64_t b0);
int64_t get_distribution_i64_i64_i64_i64(int64_t p, int64_t e, int64_t pi_p, int64_t k);
int32_t main(void);
static const int64_t MOD = 999999893;
static const int64_t N = 1000000;
/* Module statics */
static int32_t* spf = NULL;
static int64_t* pi_prime = NULL;
static int64_t* k_prime = NULL;
static int64_t* dc_p = NULL;
static int64_t* dc_e = NULL;
static int64_t* dc_ne = NULL;
static int64_t* dc_period = NULL;
static int64_t* dc_count = NULL;
static int64_t dc_size = 0;
static int64_t g_fn = 0;
static int64_t g_fn1 = 0;
static int64_t* cur_key = NULL;
static int64_t* cur_val = NULL;
static int64_t* new_key = NULL;
static int64_t* new_val = NULL;
static int64_t g_dist_ne = 0;
int64_t clzll_i64(int64_t n) {
if (n <= 0) {
return 64;
}
int64_t count = 0;
int64_t v = n;
while (v > 0) {
v = FLOW_CHECKED_SHR((v), (1));
count = (count + 1);
}
return (64 - count);
}
int64_t mod_pow_i64_i64_i64(int64_t a0, int64_t e0, int64_t mod) {
int64_t r = FLOW_CHECKED_MOD((1), (mod));
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
if (a < 0) {
a = (a + mod);
}
int64_t e = e0;
while (e > 0) {
if ((e & 1) != 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;
}
void sieve_spf_i64(int64_t limit) {
spf = ((int32_t*)(calloc((limit + 1), 4)));
int64_t i = 0;
while (i <= limit) {
spf[i] = ((int32_t)(i));
i = (i + 1);
}
spf[0] = 0;
spf[1] = 1;
int64_t i2 = 2;
while ((i2 * i2) <= limit) {
if (spf[i2] == ((int32_t)(i2))) {
int64_t j = (i2 * i2);
while (j <= limit) {
if (spf[j] == ((int32_t)(j))) {
spf[j] = ((int32_t)(i2));
}
j = (j + i2);
}
}
i2 = (i2 + 1);
}
}
void fib_pair_i64_i64(int64_t n, int64_t mod) {
int64_t a = 0;
int64_t b = FLOW_CHECKED_MOD((1), (mod));
if (n == 0) {
g_fn = 0;
g_fn1 = b;
return;
}
int64_t nbits = (64 - clzll_i64(n));
int64_t i = (nbits - 1);
while (i >= 0) {
int64_t two_b_minus_a = FLOW_CHECKED_MOD((((2 * b) - a)), (mod));
if (two_b_minus_a < 0) {
two_b_minus_a = (two_b_minus_a + mod);
}
int64_t c = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(two_b_minus_a)))), (((__int128)(mod))))));
int64_t d = ((int64_t)(FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(a)))), (((__int128)(mod)))) + FLOW_CHECKED_MOD(((((__int128)(b)) * ((__int128)(b)))), (((__int128)(mod)))))), (((__int128)(mod))))));
if (d < 0) {
d = (d + mod);
}
if ((FLOW_CHECKED_SHR((n), (i)) & 1) != 0) {
a = d;
b = FLOW_CHECKED_MOD(((c + d)), (mod));
} else {
a = c;
b = d;
}
i = (i - 1);
}
g_fn = a;
g_fn1 = b;
}
bool check_A_order_i64_i64(int64_t n, int64_t p) {
fib_pair_i64_i64(n, p);
return (g_fn == 0 && g_fn1 == 1);
}
int64_t pisano_prime_i64(int64_t p) {
if (p == 2) {
return 3;
}
if (p == 5) {
return 20;
}
int64_t residue = mod_pow_i64_i64_i64(5, FLOW_CHECKED_DIV(((p - 1)), (2)), p);
int64_t candidate = 0;
if (residue == 1) {
candidate = (p - 1);
} else {
candidate = (2 * (p + 1));
}
int64_t x = candidate;
int64_t distinct_primes[32] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
int64_t ndp = 0;
while (x > 1) {
int64_t q = ((int64_t)(spf[x]));
distinct_primes[ndp] = q;
ndp = (ndp + 1);
while (FLOW_CHECKED_MOD((x), (q)) == 0) {
x = FLOW_CHECKED_DIV((x), (q));
}
}
int64_t d = candidate;
int64_t i = 0;
while (i < ndp) {
int64_t q = (((unsigned)(i) < 32) ? distinct_primes[i] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(i), 32), flow_fault_handler("array index out of bounds"), distinct_primes[0]));
while (FLOW_CHECKED_MOD((d), (q)) == 0) {
int64_t nd = FLOW_CHECKED_DIV((d), (q));
if (check_A_order_i64_i64(nd, p)) {
d = nd;
} else {
break;
}
}
i = (i + 1);
}
return d;
}
int64_t has_short_period_factor_i64_i64(int64_t p, int64_t pi_p) {
if (p == 5) {
return 5;
}
if (p == 2) {
return 1;
}
if (mod_pow_i64_i64_i64(5, FLOW_CHECKED_DIV(((p - 1)), (2)), p) != 1) {
return 1;
}
if (FLOW_CHECKED_MOD((pi_p), (2)) != 0) {
return 1;
}
int64_t n = FLOW_CHECKED_DIV((pi_p), (2));
fib_pair_i64_i64(n, p);
int64_t ln = FLOW_CHECKED_MOD((((2 * g_fn1) - g_fn)), (p));
if (ln < 0) {
ln = (ln + p);
}
int64_t det = 0;
if (FLOW_CHECKED_MOD((n), (2)) == 0) {
det = FLOW_CHECKED_MOD((((1 + 1) - ln)), (p));
} else {
det = FLOW_CHECKED_MOD((((1 + (p - 1)) - ln)), (p));
}
if (det < 0) {
det = (det + p);
}
if (det == 0) {
return 2;
}
return 1;
}
int64_t gcd_i64_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 get_distribution_i64_i64_i64_i64(int64_t p, int64_t e, int64_t pi_p, int64_t k) {
int64_t i = 0;
while (i < dc_size) {
if ((dc_p[i] == p && dc_e[i] == e)) {
g_dist_ne = dc_ne[i];
return i;
}
i = (i + 1);
}
int64_t pe1 = 1;
int64_t j = 0;
while (j < (e - 1)) {
pe1 = (pe1 * p);
j = (j + 1);
}
int64_t T = (pi_p * pe1);
int64_t p2 = (p * p);
int64_t total = 1;
j = 0;
while (j < (e - 1)) {
total = (total * p2);
j = (j + 1);
}
total = (total * (p2 - 1));
int64_t idx = dc_size;
dc_p[idx] = p;
dc_e[idx] = e;
if (k == 1) {
dc_period[(idx * 2)] = T;
dc_count[(idx * 2)] = FLOW_CHECKED_MOD((total), (MOD));
dc_ne[idx] = 1;
g_dist_ne = 1;
} else {
if (k == 2) {
int64_t small_period = FLOW_CHECKED_DIV((T), (2));
int64_t small_count = ((p - 1) * pe1);
int64_t big_count = (total - small_count);
dc_period[(idx * 2)] = small_period;
dc_count[(idx * 2)] = FLOW_CHECKED_MOD((small_count), (MOD));
dc_period[((idx * 2) + 1)] = T;
dc_count[((idx * 2) + 1)] = FLOW_CHECKED_MOD((big_count), (MOD));
dc_ne[idx] = 2;
g_dist_ne = 2;
} else {
int64_t small_period = FLOW_CHECKED_DIV((T), (5));
int64_t small_count = (p - 1);
j = 0;
while (j < (e - 1)) {
small_count = (small_count * p2);
j = (j + 1);
}
int64_t big_count = (total - small_count);
dc_period[(idx * 2)] = small_period;
dc_count[(idx * 2)] = FLOW_CHECKED_MOD((small_count), (MOD));
dc_period[((idx * 2) + 1)] = T;
dc_count[((idx * 2) + 1)] = FLOW_CHECKED_MOD((big_count), (MOD));
dc_ne[idx] = 2;
g_dist_ne = 2;
}
}
dc_size = (dc_size + 1);
return idx;
}
int32_t main(void) {
int64_t max_spf = ((2 * N) + 2);
sieve_spf_i64(max_spf);
pi_prime = ((int64_t*)(calloc((N + 1), 8)));
k_prime = ((int64_t*)(malloc(((N + 1) * 8))));
int64_t i = 0;
while (i <= N) {
k_prime[i] = 1;
i = (i + 1);
}
int64_t p = 2;
while (p <= N) {
if (spf[p] == ((int32_t)(p))) {
int64_t pi_p = pisano_prime_i64(p);
pi_prime[p] = pi_p;
k_prime[p] = has_short_period_factor_i64_i64(p, pi_p);
}
p = (p + 1);
}
dc_p = ((int64_t*)(malloc((100000 * 8))));
dc_e = ((int64_t*)(malloc((100000 * 8))));
dc_ne = ((int64_t*)(malloc((100000 * 8))));
dc_period = ((int64_t*)(malloc((200000 * 8))));
dc_count = ((int64_t*)(malloc((200000 * 8))));
dc_size = 0;
cur_key = ((int64_t*)(malloc((256 * 8))));
cur_val = ((int64_t*)(malloc((256 * 8))));
new_key = ((int64_t*)(malloc((256 * 8))));
new_val = ((int64_t*)(malloc((256 * 8))));
int64_t ans = 0;
int64_t n = 1;
while (n <= N) {
int64_t x = n;
int64_t dist_indices[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
int64_t dist_counts[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
int64_t num_dists = 0;
while (x > 1) {
int64_t pp = ((int64_t)(spf[x]));
int64_t e = 0;
while (FLOW_CHECKED_MOD((x), (pp)) == 0) {
x = FLOW_CHECKED_DIV((x), (pp));
e = (e + 1);
}
int64_t didx = get_distribution_i64_i64_i64_i64(pp, e, pi_prime[pp], k_prime[pp]);
dist_indices[num_dists] = didx;
dist_counts[num_dists] = g_dist_ne;
num_dists = (num_dists + 1);
}
int64_t cur_size = 1;
cur_key[0] = 1;
cur_val[0] = 1;
int64_t di = 0;
while (di < num_dists) {
int64_t new_size = 0;
int64_t didx = (((unsigned)(di) < 8) ? dist_indices[di] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(di), 8), flow_fault_handler("array index out of bounds"), dist_indices[0]));
int64_t dcnt = (((unsigned)(di) < 8) ? dist_counts[di] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(di), 8), flow_fault_handler("array index out of bounds"), dist_counts[0]));
int64_t ci = 0;
while (ci < cur_size) {
int64_t ei = 0;
while (ei < dcnt) {
int64_t per1 = cur_key[ci];
int64_t per2 = dc_period[((didx * 2) + ei)];
int64_t g = gcd_i64_i64_i64(per1, per2);
__int128 l = (FLOW_CHECKED_DIV((((__int128)(per1))), (((__int128)(g)))) * ((__int128)(per2)));
int64_t l_i64 = ((int64_t)(l));
int64_t v = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(cur_val[ci])) * ((__int128)(dc_count[((didx * 2) + ei)])))), (((__int128)(MOD))))));
int64_t found = (-1);
int64_t j = 0;
while (j < new_size) {
if (new_key[j] == l_i64) {
found = j;
break;
}
j = (j + 1);
}
if (found >= 0) {
new_val[found] = FLOW_CHECKED_MOD(((new_val[found] + v)), (MOD));
} else {
new_key[new_size] = l_i64;
new_val[new_size] = v;
new_size = (new_size + 1);
}
ei = (ei + 1);
}
ci = (ci + 1);
}
cur_size = 0;
int64_t j = 0;
while (j < new_size) {
if (new_val[j] != 0) {
cur_key[cur_size] = new_key[j];
cur_val[cur_size] = new_val[j];
cur_size = (cur_size + 1);
}
j = (j + 1);
}
di = (di + 1);
}
int64_t Pn = 0;
int64_t j = 0;
while (j < cur_size) {
int64_t per2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(cur_key[j])) * ((__int128)(cur_key[j])))), (((__int128)(MOD))))));
Pn = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(Pn)) + FLOW_CHECKED_MOD(((((__int128)(per2)) * ((__int128)(cur_val[j])))), (((__int128)(MOD)))))), (((__int128)(MOD))))));
j = (j + 1);
}
ans = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(ans)) + FLOW_CHECKED_MOD(((((__int128)(Pn)) * ((__int128)(FLOW_CHECKED_DIV((N), (n)))))), (((__int128)(MOD)))))), (((__int128)(MOD))))));
n = (n + 1);
}
printf("%lld\n", ans);
free(((void*)(spf)));
free(((void*)(pi_prime)));
free(((void*)(k_prime)));
free(((void*)(dc_p)));
free(((void*)(dc_e)));
free(((void*)(dc_ne)));
free(((void*)(dc_period)));
free(((void*)(dc_count)));
free(((void*)(cur_key)));
free(((void*)(cur_val)));
free(((void*)(new_key)));
free(((void*)(new_val)));
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(999999893 : i64) : i64
// Constant: N
llvm.mlir.global internal constant @N(1000000 : i64) : i64
// Module static: spf
llvm.mlir.global internal @spf() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: pi_prime
llvm.mlir.global internal @pi_prime() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
// Module static: k_prime
llvm.mlir.global internal @k_prime() {addr_space = 0 : i32} : !llvm.ptr {
%2 = llvm.mlir.zero : !llvm.ptr
llvm.return %2 : !llvm.ptr
}
// Module static: dc_p
llvm.mlir.global internal @dc_p() {addr_space = 0 : i32} : !llvm.ptr {
%3 = llvm.mlir.zero : !llvm.ptr
llvm.return %3 : !llvm.ptr
}
// Module static: dc_e
llvm.mlir.global internal @dc_e() {addr_space = 0 : i32} : !llvm.ptr {
%4 = llvm.mlir.zero : !llvm.ptr
llvm.return %4 : !llvm.ptr
}
// Module static: dc_ne
llvm.mlir.global internal @dc_ne() {addr_space = 0 : i32} : !llvm.ptr {
%5 = llvm.mlir.zero : !llvm.ptr
llvm.return %5 : !llvm.ptr
}
// Module static: dc_period
llvm.mlir.global internal @dc_period() {addr_space = 0 : i32} : !llvm.ptr {
%6 = llvm.mlir.zero : !llvm.ptr
llvm.return %6 : !llvm.ptr
}
// Module static: dc_count
llvm.mlir.global internal @dc_count() {addr_space = 0 : i32} : !llvm.ptr {
%7 = llvm.mlir.zero : !llvm.ptr
llvm.return %7 : !llvm.ptr
}
// Module static: dc_size
llvm.mlir.global internal @dc_size(0 : i64) : i64
// Module static: g_fn
llvm.mlir.global internal @g_fn(0 : i64) : i64
// Module static: g_fn1
llvm.mlir.global internal @g_fn1(0 : i64) : i64
// Module static: cur_key
llvm.mlir.global internal @cur_key() {addr_space = 0 : i32} : !llvm.ptr {
%8 = llvm.mlir.zero : !llvm.ptr
llvm.return %8 : !llvm.ptr
}
// Module static: cur_val
llvm.mlir.global internal @cur_val() {addr_space = 0 : i32} : !llvm.ptr {
%9 = llvm.mlir.zero : !llvm.ptr
llvm.return %9 : !llvm.ptr
}
// Module static: new_key
llvm.mlir.global internal @new_key() {addr_space = 0 : i32} : !llvm.ptr {
%10 = llvm.mlir.zero : !llvm.ptr
llvm.return %10 : !llvm.ptr
}
// Module static: new_val
llvm.mlir.global internal @new_val() {addr_space = 0 : i32} : !llvm.ptr {
%11 = llvm.mlir.zero : !llvm.ptr
llvm.return %11 : !llvm.ptr
}
func.func @clzll(%arg0: i64) -> i64 {
%12 = arith.constant 0 : i32
%14 = arith.extsi %12 : i32 to i64
%13 = arith.cmpi sle, %arg0, %14 : i64
cf.cond_br %13, ^bb0, ^bb1
^bb0:
%15 = arith.constant 64 : i32
%16 = arith.extsi %15 : i32 to i64
func.return %16 : i64
^bb1:
cf.br ^bb2
^bb2:
%17 = arith.constant 0 : i32
%18 = arith.extsi %17 : i32 to i64
%19 = llvm.mlir.constant(1 : i64) : i64
%20 = llvm.alloca %19 x i64 : (i64) -> !llvm.ptr
llvm.store %18, %20 : i64, !llvm.ptr
%21 = llvm.mlir.constant(1 : i64) : i64
%22 = llvm.alloca %21 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %22 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%23 = llvm.load %22 : !llvm.ptr -> i64
%24 = arith.constant 0 : i32
%26 = arith.extsi %24 : i32 to i64
%25 = arith.cmpi sgt, %23, %26 : i64
cf.cond_br %25, ^bb4, ^bb5
^bb4:
%27 = llvm.load %22 : !llvm.ptr -> i64
%28 = arith.constant 1 : i32
%30 = arith.extsi %28 : i32 to i64
%29 = arith.shrsi %27, %30 : i64
llvm.store %29, %22 : i64, !llvm.ptr
%31 = llvm.load %20 : !llvm.ptr -> i64
%32 = arith.constant 1 : i32
%34 = arith.extsi %32 : i32 to i64
%33 = arith.addi %31, %34 : i64
llvm.store %33, %20 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%35 = arith.constant 64 : i32
%36 = llvm.load %20 : !llvm.ptr -> i64
%38 = arith.extsi %35 : i32 to i64
%37 = arith.subi %38, %36 : i64
func.return %37 : i64
}
func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%39 = arith.constant 1 : i32
%41 = arith.extsi %39 : i32 to i64
%40 = arith.remsi %41, %arg2 : i64
%42 = llvm.mlir.constant(1 : i64) : i64
%43 = llvm.alloca %42 x i64 : (i64) -> !llvm.ptr
llvm.store %40, %43 : i64, !llvm.ptr
%44 = arith.remsi %arg0, %arg2 : i64
%45 = llvm.mlir.constant(1 : i64) : i64
%46 = llvm.alloca %45 x i64 : (i64) -> !llvm.ptr
llvm.store %44, %46 : i64, !llvm.ptr
%47 = llvm.load %46 : !llvm.ptr -> i64
%48 = arith.constant 0 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.cmpi slt, %47, %50 : i64
cf.cond_br %49, ^bb6, ^bb7
^bb6:
%51 = llvm.load %46 : !llvm.ptr -> i64
%52 = arith.addi %51, %arg2 : i64
llvm.store %52, %46 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%53 = llvm.mlir.constant(1 : i64) : i64
%54 = llvm.alloca %53 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %54 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%55 = llvm.load %54 : !llvm.ptr -> i64
%56 = arith.constant 0 : i32
%58 = arith.extsi %56 : i32 to i64
%57 = arith.cmpi sgt, %55, %58 : i64
cf.cond_br %57, ^bb10, ^bb11
^bb10:
%59 = llvm.load %54 : !llvm.ptr -> i64
%60 = arith.constant 1 : i32
%62 = arith.extsi %60 : i32 to i64
%61 = arith.andi %59, %62 : i64
%63 = arith.constant 0 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.cmpi ne, %61, %65 : i64
cf.cond_br %64, ^bb12, ^bb13
^bb12:
%66 = llvm.load %43 : !llvm.ptr -> i64
%67 = arith.extsi %66 : i64 to i128
%68 = llvm.load %46 : !llvm.ptr -> i64
%69 = arith.extsi %68 : i64 to i128
%71 = arith.trunci %67 : i128 to i64
%72 = arith.trunci %69 : i128 to i64
%70 = arith.muli %71, %72 : i64
%73 = arith.extsi %arg2 : i64 to i128
%75 = arith.trunci %73 : i128 to i64
%74 = arith.remsi %70, %75 : i64
llvm.store %74, %43 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%76 = llvm.load %46 : !llvm.ptr -> i64
%77 = arith.extsi %76 : i64 to i128
%78 = llvm.load %46 : !llvm.ptr -> i64
%79 = arith.extsi %78 : i64 to i128
%81 = arith.trunci %77 : i128 to i64
%82 = arith.trunci %79 : i128 to i64
%80 = arith.muli %81, %82 : i64
%83 = arith.extsi %arg2 : i64 to i128
%85 = arith.trunci %83 : i128 to i64
%84 = arith.remsi %80, %85 : i64
llvm.store %84, %46 : i64, !llvm.ptr
%86 = llvm.load %54 : !llvm.ptr -> i64
%87 = arith.constant 1 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.shrsi %86, %89 : i64
llvm.store %88, %54 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%90 = llvm.load %43 : !llvm.ptr -> i64
func.return %90 : i64
}
func.func @sieve_spf(%arg0: i64) -> () {
%92 = arith.constant 1 : i32
%94 = arith.extsi %92 : i32 to i64
%93 = arith.addi %arg0, %94 : i64
%95 = arith.constant 4 : i32
%96 = arith.extsi %95 : i32 to i64
%91 = func.call @calloc(%93, %96) : (i64, i64) -> !llvm.ptr
%97 = llvm.mlir.addressof @spf : !llvm.ptr
llvm.store %91, %97 : !llvm.ptr, !llvm.ptr
%98 = arith.constant 0 : i32
%99 = arith.extsi %98 : i32 to i64
%100 = llvm.mlir.constant(1 : i64) : i64
%101 = llvm.alloca %100 x i64 : (i64) -> !llvm.ptr
llvm.store %99, %101 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%102 = llvm.load %101 : !llvm.ptr -> i64
%103 = arith.cmpi sle, %102, %arg0 : i64
cf.cond_br %103, ^bb16, ^bb17
^bb16:
%104 = llvm.load %101 : !llvm.ptr -> i64
%105 = arith.trunci %104 : i64 to i32
%106 = llvm.mlir.addressof @spf : !llvm.ptr
%107 = llvm.load %106 : !llvm.ptr -> !llvm.ptr
%108 = llvm.load %101 : !llvm.ptr -> i64
%109 = llvm.getelementptr %107[%108] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %105, %109 : i32, !llvm.ptr
%110 = llvm.load %101 : !llvm.ptr -> i64
%111 = arith.constant 1 : i32
%113 = arith.extsi %111 : i32 to i64
%112 = arith.addi %110, %113 : i64
llvm.store %112, %101 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%114 = arith.constant 0 : i32
%115 = llvm.mlir.addressof @spf : !llvm.ptr
%116 = llvm.load %115 : !llvm.ptr -> !llvm.ptr
%117 = arith.constant 0 : i32
%118 = arith.extsi %117 : i32 to i64
%119 = llvm.getelementptr %116[%118] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %114, %119 : i32, !llvm.ptr
%120 = arith.constant 1 : i32
%121 = llvm.mlir.addressof @spf : !llvm.ptr
%122 = llvm.load %121 : !llvm.ptr -> !llvm.ptr
%123 = arith.constant 1 : i32
%124 = arith.extsi %123 : i32 to i64
%125 = llvm.getelementptr %122[%124] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %120, %125 : i32, !llvm.ptr
%126 = arith.constant 2 : i32
%127 = arith.extsi %126 : i32 to i64
%128 = llvm.mlir.constant(1 : i64) : i64
%129 = llvm.alloca %128 x i64 : (i64) -> !llvm.ptr
llvm.store %127, %129 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%130 = llvm.load %129 : !llvm.ptr -> i64
%131 = llvm.load %129 : !llvm.ptr -> i64
%132 = arith.muli %130, %131 : i64
%133 = arith.cmpi sle, %132, %arg0 : i64
cf.cond_br %133, ^bb19, ^bb20
^bb19:
%135 = llvm.mlir.addressof @spf : !llvm.ptr
%136 = llvm.load %135 : !llvm.ptr -> !llvm.ptr
%137 = llvm.load %129 : !llvm.ptr -> i64
%138 = llvm.getelementptr %136[%137] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%134 = llvm.load %138 : !llvm.ptr -> i32
%139 = llvm.load %129 : !llvm.ptr -> i64
%140 = arith.trunci %139 : i64 to i32
%141 = arith.cmpi eq, %134, %140 : i32
cf.cond_br %141, ^bb21, ^bb22
^bb21:
%142 = llvm.load %129 : !llvm.ptr -> i64
%143 = llvm.load %129 : !llvm.ptr -> i64
%144 = arith.muli %142, %143 : i64
%145 = llvm.mlir.constant(1 : i64) : i64
%146 = llvm.alloca %145 x i64 : (i64) -> !llvm.ptr
llvm.store %144, %146 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%147 = llvm.load %146 : !llvm.ptr -> i64
%148 = arith.cmpi sle, %147, %arg0 : i64
cf.cond_br %148, ^bb25, ^bb26
^bb25:
%150 = llvm.mlir.addressof @spf : !llvm.ptr
%151 = llvm.load %150 : !llvm.ptr -> !llvm.ptr
%152 = llvm.load %146 : !llvm.ptr -> i64
%153 = llvm.getelementptr %151[%152] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%149 = llvm.load %153 : !llvm.ptr -> i32
%154 = llvm.load %146 : !llvm.ptr -> i64
%155 = arith.trunci %154 : i64 to i32
%156 = arith.cmpi eq, %149, %155 : i32
cf.cond_br %156, ^bb27, ^bb28
^bb27:
%157 = llvm.load %129 : !llvm.ptr -> i64
%158 = arith.trunci %157 : i64 to i32
%159 = llvm.mlir.addressof @spf : !llvm.ptr
%160 = llvm.load %159 : !llvm.ptr -> !llvm.ptr
%161 = llvm.load %146 : !llvm.ptr -> i64
%162 = llvm.getelementptr %160[%161] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %158, %162 : i32, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%163 = llvm.load %146 : !llvm.ptr -> i64
%164 = llvm.load %129 : !llvm.ptr -> i64
%165 = arith.addi %163, %164 : i64
llvm.store %165, %146 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%166 = llvm.load %129 : !llvm.ptr -> i64
%167 = arith.constant 1 : i32
%169 = arith.extsi %167 : i32 to i64
%168 = arith.addi %166, %169 : i64
llvm.store %168, %129 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
func.return
}
func.func @fib_pair(%arg0: i64, %arg1: i64) -> () {
%170 = arith.constant 0 : i32
%171 = arith.extsi %170 : i32 to i64
%172 = llvm.mlir.constant(1 : i64) : i64
%173 = llvm.alloca %172 x i64 : (i64) -> !llvm.ptr
llvm.store %171, %173 : i64, !llvm.ptr
%174 = arith.constant 1 : i32
%176 = arith.extsi %174 : i32 to i64
%175 = arith.remsi %176, %arg1 : i64
%177 = llvm.mlir.constant(1 : i64) : i64
%178 = llvm.alloca %177 x i64 : (i64) -> !llvm.ptr
llvm.store %175, %178 : i64, !llvm.ptr
%179 = arith.constant 0 : i32
%181 = arith.extsi %179 : i32 to i64
%180 = arith.cmpi eq, %arg0, %181 : i64
cf.cond_br %180, ^bb30, ^bb31
^bb30:
%182 = arith.constant 0 : i32
%183 = arith.extsi %182 : i32 to i64
%184 = llvm.mlir.addressof @g_fn : !llvm.ptr
llvm.store %183, %184 : i64, !llvm.ptr
%185 = llvm.load %178 : !llvm.ptr -> i64
%186 = llvm.mlir.addressof @g_fn1 : !llvm.ptr
llvm.store %185, %186 : i64, !llvm.ptr
func.return
^bb31:
cf.br ^bb32
^bb32:
%187 = arith.constant 64 : i32
%188 = func.call @clzll(%arg0) : (i64) -> i64
%190 = arith.extsi %187 : i32 to i64
%189 = arith.subi %190, %188 : i64
%191 = arith.constant 1 : i32
%193 = arith.extsi %191 : i32 to i64
%192 = arith.subi %189, %193 : i64
%194 = llvm.mlir.constant(1 : i64) : i64
%195 = llvm.alloca %194 x i64 : (i64) -> !llvm.ptr
llvm.store %192, %195 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%196 = llvm.load %195 : !llvm.ptr -> i64
%197 = arith.constant 0 : i32
%199 = arith.extsi %197 : i32 to i64
%198 = arith.cmpi sge, %196, %199 : i64
cf.cond_br %198, ^bb34, ^bb35
^bb34:
%200 = arith.constant 2 : i32
%201 = llvm.load %178 : !llvm.ptr -> i64
%203 = arith.extsi %200 : i32 to i64
%202 = arith.muli %203, %201 : i64
%204 = llvm.load %173 : !llvm.ptr -> i64
%205 = arith.subi %202, %204 : i64
%206 = arith.remsi %205, %arg1 : i64
%207 = llvm.mlir.constant(1 : i64) : i64
%208 = llvm.alloca %207 x i64 : (i64) -> !llvm.ptr
llvm.store %206, %208 : i64, !llvm.ptr
%209 = llvm.load %208 : !llvm.ptr -> i64
%210 = arith.constant 0 : i32
%212 = arith.extsi %210 : i32 to i64
%211 = arith.cmpi slt, %209, %212 : i64
cf.cond_br %211, ^bb36, ^bb37
^bb36:
%213 = llvm.load %208 : !llvm.ptr -> i64
%214 = arith.addi %213, %arg1 : i64
llvm.store %214, %208 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%215 = llvm.load %173 : !llvm.ptr -> i64
%216 = arith.extsi %215 : i64 to i128
%217 = llvm.load %208 : !llvm.ptr -> i64
%218 = arith.extsi %217 : i64 to i128
%220 = arith.trunci %216 : i128 to i64
%221 = arith.trunci %218 : i128 to i64
%219 = arith.muli %220, %221 : i64
%222 = arith.extsi %arg1 : i64 to i128
%224 = arith.trunci %222 : i128 to i64
%223 = arith.remsi %219, %224 : i64
%225 = llvm.load %173 : !llvm.ptr -> i64
%226 = arith.extsi %225 : i64 to i128
%227 = llvm.load %173 : !llvm.ptr -> i64
%228 = arith.extsi %227 : i64 to i128
%230 = arith.trunci %226 : i128 to i64
%231 = arith.trunci %228 : i128 to i64
%229 = arith.muli %230, %231 : i64
%232 = arith.extsi %arg1 : i64 to i128
%234 = arith.trunci %232 : i128 to i64
%233 = arith.remsi %229, %234 : i64
%235 = llvm.load %178 : !llvm.ptr -> i64
%236 = arith.extsi %235 : i64 to i128
%237 = llvm.load %178 : !llvm.ptr -> i64
%238 = arith.extsi %237 : i64 to i128
%240 = arith.trunci %236 : i128 to i64
%241 = arith.trunci %238 : i128 to i64
%239 = arith.muli %240, %241 : i64
%242 = arith.extsi %arg1 : i64 to i128
%244 = arith.trunci %242 : i128 to i64
%243 = arith.remsi %239, %244 : i64
%245 = arith.addi %233, %243 : i64
%246 = arith.extsi %arg1 : i64 to i128
%248 = arith.trunci %246 : i128 to i64
%247 = arith.remsi %245, %248 : i64
%249 = llvm.mlir.constant(1 : i64) : i64
%250 = llvm.alloca %249 x i64 : (i64) -> !llvm.ptr
llvm.store %247, %250 : i64, !llvm.ptr
%251 = llvm.load %250 : !llvm.ptr -> i64
%252 = arith.constant 0 : i32
%254 = arith.extsi %252 : i32 to i64
%253 = arith.cmpi slt, %251, %254 : i64
cf.cond_br %253, ^bb39, ^bb40
^bb39:
%255 = llvm.load %250 : !llvm.ptr -> i64
%256 = arith.addi %255, %arg1 : i64
llvm.store %256, %250 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%257 = llvm.load %195 : !llvm.ptr -> i64
%258 = arith.shrsi %arg0, %257 : i64
%259 = arith.constant 1 : i32
%261 = arith.extsi %259 : i32 to i64
%260 = arith.andi %258, %261 : i64
%262 = arith.constant 0 : i32
%264 = arith.extsi %262 : i32 to i64
%263 = arith.cmpi ne, %260, %264 : i64
cf.cond_br %263, ^bb42, ^bb43
^bb42:
%265 = llvm.load %250 : !llvm.ptr -> i64
llvm.store %265, %173 : i64, !llvm.ptr
%266 = llvm.load %250 : !llvm.ptr -> i64
%267 = arith.addi %223, %266 : i64
%268 = arith.remsi %267, %arg1 : i64
llvm.store %268, %178 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
llvm.store %223, %173 : i64, !llvm.ptr
%269 = llvm.load %250 : !llvm.ptr -> i64
llvm.store %269, %178 : i64, !llvm.ptr
cf.br ^bb44
^bb44:
%270 = llvm.load %195 : !llvm.ptr -> i64
%271 = arith.constant 1 : i32
%273 = arith.extsi %271 : i32 to i64
%272 = arith.subi %270, %273 : i64
llvm.store %272, %195 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
%274 = llvm.load %173 : !llvm.ptr -> i64
%275 = llvm.mlir.addressof @g_fn : !llvm.ptr
llvm.store %274, %275 : i64, !llvm.ptr
%276 = llvm.load %178 : !llvm.ptr -> i64
%277 = llvm.mlir.addressof @g_fn1 : !llvm.ptr
llvm.store %276, %277 : i64, !llvm.ptr
func.return
}
func.func @check_A_order(%arg0: i64, %arg1: i64) -> i1 {
func.call @fib_pair(%arg0, %arg1) : (i64, i64) -> ()
%279 = llvm.mlir.addressof @g_fn : !llvm.ptr
%280 = llvm.load %279 : !llvm.ptr -> i64
%281 = arith.constant 0 : i32
%283 = arith.extsi %281 : i32 to i64
%282 = arith.cmpi eq, %280, %283 : i64
%284 = scf.if %282 -> (i1) {
%285 = llvm.mlir.addressof @g_fn1 : !llvm.ptr
%286 = llvm.load %285 : !llvm.ptr -> i64
%287 = arith.constant 1 : i32
%289 = arith.extsi %287 : i32 to i64
%288 = arith.cmpi eq, %286, %289 : i64
scf.yield %288 : i1
} else {
%290 = arith.constant false
scf.yield %290 : i1
}
func.return %284 : i1
}
func.func @pisano_prime(%arg0: i64) -> i64 {
%291 = arith.constant 2 : i32
%293 = arith.extsi %291 : i32 to i64
%292 = arith.cmpi eq, %arg0, %293 : i64
cf.cond_br %292, ^bb45, ^bb46
^bb45:
%294 = arith.constant 3 : i32
%295 = arith.extsi %294 : i32 to i64
func.return %295 : i64
^bb46:
cf.br ^bb47
^bb47:
%296 = arith.constant 5 : i32
%298 = arith.extsi %296 : i32 to i64
%297 = arith.cmpi eq, %arg0, %298 : i64
cf.cond_br %297, ^bb48, ^bb49
^bb48:
%299 = arith.constant 20 : i32
%300 = arith.extsi %299 : i32 to i64
func.return %300 : i64
^bb49:
cf.br ^bb50
^bb50:
%302 = arith.constant 5 : i32
%303 = arith.constant 1 : i32
%305 = arith.extsi %303 : i32 to i64
%304 = arith.subi %arg0, %305 : i64
%306 = arith.constant 2 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.divsi %304, %308 : i64
%309 = arith.extsi %302 : i32 to i64
%301 = func.call @mod_pow(%309, %307, %arg0) : (i64, i64, i64) -> i64
%310 = arith.constant 0 : i32
%311 = arith.extsi %310 : i32 to i64
%312 = llvm.mlir.constant(1 : i64) : i64
%313 = llvm.alloca %312 x i64 : (i64) -> !llvm.ptr
llvm.store %311, %313 : i64, !llvm.ptr
%314 = arith.constant 1 : i32
%316 = arith.extsi %314 : i32 to i64
%315 = arith.cmpi eq, %301, %316 : i64
cf.cond_br %315, ^bb51, ^bb52
^bb51:
%317 = arith.constant 1 : i32
%319 = arith.extsi %317 : i32 to i64
%318 = arith.subi %arg0, %319 : i64
llvm.store %318, %313 : i64, !llvm.ptr
cf.br ^bb53
^bb52:
%320 = arith.constant 2 : i32
%321 = arith.constant 1 : i32
%323 = arith.extsi %321 : i32 to i64
%322 = arith.addi %arg0, %323 : i64
%325 = arith.extsi %320 : i32 to i64
%324 = arith.muli %325, %322 : i64
llvm.store %324, %313 : i64, !llvm.ptr
cf.br ^bb53
^bb53:
%326 = llvm.load %313 : !llvm.ptr -> i64
%327 = llvm.mlir.constant(1 : i64) : i64
%328 = llvm.alloca %327 x i64 : (i64) -> !llvm.ptr
llvm.store %326, %328 : i64, !llvm.ptr
%330 = arith.constant 0 : i32
%331 = arith.constant 0 : i32
%332 = arith.constant 0 : i32
%333 = arith.constant 0 : i32
%334 = arith.constant 0 : i32
%335 = arith.constant 0 : i32
%336 = arith.constant 0 : i32
%337 = arith.constant 0 : i32
%338 = arith.constant 0 : i32
%339 = arith.constant 0 : i32
%340 = arith.constant 0 : i32
%341 = arith.constant 0 : i32
%342 = arith.constant 0 : i32
%343 = arith.constant 0 : i32
%344 = arith.constant 0 : i32
%345 = arith.constant 0 : i32
%346 = arith.constant 0 : i32
%347 = arith.constant 0 : i32
%348 = arith.constant 0 : i32
%349 = arith.constant 0 : i32
%350 = arith.constant 0 : i32
%351 = arith.constant 0 : i32
%352 = arith.constant 0 : i32
%353 = arith.constant 0 : i32
%354 = arith.constant 0 : i32
%355 = arith.constant 0 : i32
%356 = arith.constant 0 : i32
%357 = arith.constant 0 : i32
%358 = arith.constant 0 : i32
%359 = arith.constant 0 : i32
%360 = arith.constant 0 : i32
%361 = arith.constant 0 : i32
%362 = llvm.mlir.constant(1 : i64) : i64
%363 = llvm.alloca %362 x !llvm.array<32 x i64> : (i64) -> !llvm.ptr
%364 = llvm.mlir.zero : !llvm.array<32 x i64>
llvm.store %364, %363 : !llvm.array<32 x i64>, !llvm.ptr
%365 = arith.extsi %330 : i32 to i64
%366 = arith.extsi %331 : i32 to i64
%367 = arith.extsi %332 : i32 to i64
%368 = arith.extsi %333 : i32 to i64
%369 = arith.extsi %334 : i32 to i64
%370 = arith.extsi %335 : i32 to i64
%371 = arith.extsi %336 : i32 to i64
%372 = arith.extsi %337 : i32 to i64
%373 = arith.extsi %338 : i32 to i64
%374 = arith.extsi %339 : i32 to i64
%375 = arith.extsi %340 : i32 to i64
%376 = arith.extsi %341 : i32 to i64
%377 = arith.extsi %342 : i32 to i64
%378 = arith.extsi %343 : i32 to i64
%379 = arith.extsi %344 : i32 to i64
%380 = arith.extsi %345 : i32 to i64
%381 = arith.extsi %346 : i32 to i64
%382 = arith.extsi %347 : i32 to i64
%383 = arith.extsi %348 : i32 to i64
%384 = arith.extsi %349 : i32 to i64
%385 = arith.extsi %350 : i32 to i64
%386 = arith.extsi %351 : i32 to i64
%387 = arith.extsi %352 : i32 to i64
%388 = arith.extsi %353 : i32 to i64
%389 = arith.extsi %354 : i32 to i64
%390 = arith.extsi %355 : i32 to i64
%391 = arith.extsi %356 : i32 to i64
%392 = arith.extsi %357 : i32 to i64
%393 = arith.extsi %358 : i32 to i64
%394 = arith.extsi %359 : i32 to i64
%395 = arith.extsi %360 : i32 to i64
%396 = arith.extsi %361 : i32 to i64
%397 = llvm.mlir.constant(0 : i64) : i64
%398 = llvm.getelementptr %363[0, %397] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %365, %398 : i64, !llvm.ptr
%399 = llvm.mlir.constant(1 : i64) : i64
%400 = llvm.getelementptr %363[0, %399] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %366, %400 : i64, !llvm.ptr
%401 = llvm.mlir.constant(2 : i64) : i64
%402 = llvm.getelementptr %363[0, %401] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %367, %402 : i64, !llvm.ptr
%403 = llvm.mlir.constant(3 : i64) : i64
%404 = llvm.getelementptr %363[0, %403] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %368, %404 : i64, !llvm.ptr
%405 = llvm.mlir.constant(4 : i64) : i64
%406 = llvm.getelementptr %363[0, %405] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %369, %406 : i64, !llvm.ptr
%407 = llvm.mlir.constant(5 : i64) : i64
%408 = llvm.getelementptr %363[0, %407] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %370, %408 : i64, !llvm.ptr
%409 = llvm.mlir.constant(6 : i64) : i64
%410 = llvm.getelementptr %363[0, %409] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %371, %410 : i64, !llvm.ptr
%411 = llvm.mlir.constant(7 : i64) : i64
%412 = llvm.getelementptr %363[0, %411] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %372, %412 : i64, !llvm.ptr
%413 = llvm.mlir.constant(8 : i64) : i64
%414 = llvm.getelementptr %363[0, %413] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %373, %414 : i64, !llvm.ptr
%415 = llvm.mlir.constant(9 : i64) : i64
%416 = llvm.getelementptr %363[0, %415] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %374, %416 : i64, !llvm.ptr
%417 = llvm.mlir.constant(10 : i64) : i64
%418 = llvm.getelementptr %363[0, %417] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %375, %418 : i64, !llvm.ptr
%419 = llvm.mlir.constant(11 : i64) : i64
%420 = llvm.getelementptr %363[0, %419] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %376, %420 : i64, !llvm.ptr
%421 = llvm.mlir.constant(12 : i64) : i64
%422 = llvm.getelementptr %363[0, %421] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %377, %422 : i64, !llvm.ptr
%423 = llvm.mlir.constant(13 : i64) : i64
%424 = llvm.getelementptr %363[0, %423] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %378, %424 : i64, !llvm.ptr
%425 = llvm.mlir.constant(14 : i64) : i64
%426 = llvm.getelementptr %363[0, %425] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %379, %426 : i64, !llvm.ptr
%427 = llvm.mlir.constant(15 : i64) : i64
%428 = llvm.getelementptr %363[0, %427] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %380, %428 : i64, !llvm.ptr
%429 = llvm.mlir.constant(16 : i64) : i64
%430 = llvm.getelementptr %363[0, %429] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %381, %430 : i64, !llvm.ptr
%431 = llvm.mlir.constant(17 : i64) : i64
%432 = llvm.getelementptr %363[0, %431] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %382, %432 : i64, !llvm.ptr
%433 = llvm.mlir.constant(18 : i64) : i64
%434 = llvm.getelementptr %363[0, %433] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %383, %434 : i64, !llvm.ptr
%435 = llvm.mlir.constant(19 : i64) : i64
%436 = llvm.getelementptr %363[0, %435] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %384, %436 : i64, !llvm.ptr
%437 = llvm.mlir.constant(20 : i64) : i64
%438 = llvm.getelementptr %363[0, %437] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %385, %438 : i64, !llvm.ptr
%439 = llvm.mlir.constant(21 : i64) : i64
%440 = llvm.getelementptr %363[0, %439] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %386, %440 : i64, !llvm.ptr
%441 = llvm.mlir.constant(22 : i64) : i64
%442 = llvm.getelementptr %363[0, %441] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %387, %442 : i64, !llvm.ptr
%443 = llvm.mlir.constant(23 : i64) : i64
%444 = llvm.getelementptr %363[0, %443] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %388, %444 : i64, !llvm.ptr
%445 = llvm.mlir.constant(24 : i64) : i64
%446 = llvm.getelementptr %363[0, %445] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %389, %446 : i64, !llvm.ptr
%447 = llvm.mlir.constant(25 : i64) : i64
%448 = llvm.getelementptr %363[0, %447] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %390, %448 : i64, !llvm.ptr
%449 = llvm.mlir.constant(26 : i64) : i64
%450 = llvm.getelementptr %363[0, %449] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %391, %450 : i64, !llvm.ptr
%451 = llvm.mlir.constant(27 : i64) : i64
%452 = llvm.getelementptr %363[0, %451] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %392, %452 : i64, !llvm.ptr
%453 = llvm.mlir.constant(28 : i64) : i64
%454 = llvm.getelementptr %363[0, %453] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %393, %454 : i64, !llvm.ptr
%455 = llvm.mlir.constant(29 : i64) : i64
%456 = llvm.getelementptr %363[0, %455] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %394, %456 : i64, !llvm.ptr
%457 = llvm.mlir.constant(30 : i64) : i64
%458 = llvm.getelementptr %363[0, %457] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %395, %458 : i64, !llvm.ptr
%459 = llvm.mlir.constant(31 : i64) : i64
%460 = llvm.getelementptr %363[0, %459] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %396, %460 : i64, !llvm.ptr
%461 = arith.constant 0 : i32
%462 = arith.extsi %461 : i32 to i64
%463 = llvm.mlir.constant(1 : i64) : i64
%464 = llvm.alloca %463 x i64 : (i64) -> !llvm.ptr
llvm.store %462, %464 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%465 = llvm.load %328 : !llvm.ptr -> i64
%466 = arith.constant 1 : i32
%468 = arith.extsi %466 : i32 to i64
%467 = arith.cmpi sgt, %465, %468 : i64
cf.cond_br %467, ^bb55, ^bb56
^bb55:
%470 = llvm.mlir.addressof @spf : !llvm.ptr
%471 = llvm.load %470 : !llvm.ptr -> !llvm.ptr
%472 = llvm.load %328 : !llvm.ptr -> i64
%473 = llvm.getelementptr %471[%472] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%469 = llvm.load %473 : !llvm.ptr -> i32
%474 = arith.extsi %469 : i32 to i64
%475 = llvm.load %464 : !llvm.ptr -> i64
%476 = llvm.getelementptr %363[0, %475] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
llvm.store %474, %476 : i64, !llvm.ptr
%477 = llvm.load %464 : !llvm.ptr -> i64
%478 = arith.constant 1 : i32
%480 = arith.extsi %478 : i32 to i64
%479 = arith.addi %477, %480 : i64
llvm.store %479, %464 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%481 = llvm.load %328 : !llvm.ptr -> i64
%482 = arith.remsi %481, %474 : i64
%483 = arith.constant 0 : i32
%485 = arith.extsi %483 : i32 to i64
%484 = arith.cmpi eq, %482, %485 : i64
cf.cond_br %484, ^bb58, ^bb59
^bb58:
%486 = llvm.load %328 : !llvm.ptr -> i64
%487 = arith.divsi %486, %474 : i64
llvm.store %487, %328 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
cf.br ^bb54
^bb56:
%488 = llvm.load %313 : !llvm.ptr -> i64
%489 = llvm.mlir.constant(1 : i64) : i64
%490 = llvm.alloca %489 x i64 : (i64) -> !llvm.ptr
llvm.store %488, %490 : i64, !llvm.ptr
%491 = arith.constant 0 : i32
%492 = arith.extsi %491 : i32 to i64
%493 = llvm.mlir.constant(1 : i64) : i64
%494 = llvm.alloca %493 x i64 : (i64) -> !llvm.ptr
llvm.store %492, %494 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%495 = llvm.load %494 : !llvm.ptr -> i64
%496 = llvm.load %464 : !llvm.ptr -> i64
%497 = arith.cmpi slt, %495, %496 : i64
cf.cond_br %497, ^bb61, ^bb62
^bb61:
%499 = llvm.load %494 : !llvm.ptr -> i64
%500 = llvm.getelementptr %363[0, %499] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<32 x i64>
%498 = llvm.load %500 : !llvm.ptr -> i64
cf.br ^bb63
^bb63:
%501 = llvm.load %490 : !llvm.ptr -> i64
%502 = arith.remsi %501, %498 : i64
%503 = arith.constant 0 : i32
%505 = arith.extsi %503 : i32 to i64
%504 = arith.cmpi eq, %502, %505 : i64
cf.cond_br %504, ^bb64, ^bb65
^bb64:
%506 = llvm.load %490 : !llvm.ptr -> i64
%507 = arith.divsi %506, %498 : i64
%508 = func.call @check_A_order(%507, %arg0) : (i64, i64) -> i1
cf.cond_br %508, ^bb66, ^bb67
^bb66:
llvm.store %507, %490 : i64, !llvm.ptr
cf.br ^bb68
^bb67:
cf.br ^bb65
^bb68:
cf.br ^bb63
^bb65:
%509 = llvm.load %494 : !llvm.ptr -> i64
%510 = arith.constant 1 : i32
%512 = arith.extsi %510 : i32 to i64
%511 = arith.addi %509, %512 : i64
llvm.store %511, %494 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
%513 = llvm.load %490 : !llvm.ptr -> i64
func.return %513 : i64
}
func.func @has_short_period_factor(%arg0: i64, %arg1: i64) -> i64 {
%514 = arith.constant 5 : i32
%516 = arith.extsi %514 : i32 to i64
%515 = arith.cmpi eq, %arg0, %516 : i64
cf.cond_br %515, ^bb69, ^bb70
^bb69:
%517 = arith.constant 5 : i32
%518 = arith.extsi %517 : i32 to i64
func.return %518 : i64
^bb70:
cf.br ^bb71
^bb71:
%519 = arith.constant 2 : i32
%521 = arith.extsi %519 : i32 to i64
%520 = arith.cmpi eq, %arg0, %521 : i64
cf.cond_br %520, ^bb72, ^bb73
^bb72:
%522 = arith.constant 1 : i32
%523 = arith.extsi %522 : i32 to i64
func.return %523 : i64
^bb73:
cf.br ^bb74
^bb74:
%525 = arith.constant 5 : i32
%526 = arith.constant 1 : i32
%528 = arith.extsi %526 : i32 to i64
%527 = arith.subi %arg0, %528 : i64
%529 = arith.constant 2 : i32
%531 = arith.extsi %529 : i32 to i64
%530 = arith.divsi %527, %531 : i64
%532 = arith.extsi %525 : i32 to i64
%524 = func.call @mod_pow(%532, %530, %arg0) : (i64, i64, i64) -> i64
%533 = arith.constant 1 : i32
%535 = arith.extsi %533 : i32 to i64
%534 = arith.cmpi ne, %524, %535 : i64
cf.cond_br %534, ^bb75, ^bb76
^bb75:
%536 = arith.constant 1 : i32
%537 = arith.extsi %536 : i32 to i64
func.return %537 : i64
^bb76:
cf.br ^bb77
^bb77:
%538 = arith.constant 2 : i32
%540 = arith.extsi %538 : i32 to i64
%539 = arith.remsi %arg1, %540 : i64
%541 = arith.constant 0 : i32
%543 = arith.extsi %541 : i32 to i64
%542 = arith.cmpi ne, %539, %543 : i64
cf.cond_br %542, ^bb78, ^bb79
^bb78:
%544 = arith.constant 1 : i32
%545 = arith.extsi %544 : i32 to i64
func.return %545 : i64
^bb79:
cf.br ^bb80
^bb80:
%546 = arith.constant 2 : i32
%548 = arith.extsi %546 : i32 to i64
%547 = arith.divsi %arg1, %548 : i64
func.call @fib_pair(%547, %arg0) : (i64, i64) -> ()
%550 = arith.constant 2 : i32
%551 = llvm.mlir.addressof @g_fn1 : !llvm.ptr
%552 = llvm.load %551 : !llvm.ptr -> i64
%554 = arith.extsi %550 : i32 to i64
%553 = arith.muli %554, %552 : i64
%555 = llvm.mlir.addressof @g_fn : !llvm.ptr
%556 = llvm.load %555 : !llvm.ptr -> i64
%557 = arith.subi %553, %556 : i64
%558 = arith.remsi %557, %arg0 : i64
%559 = llvm.mlir.constant(1 : i64) : i64
%560 = llvm.alloca %559 x i64 : (i64) -> !llvm.ptr
llvm.store %558, %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, ^bb81, ^bb82
^bb81:
%565 = llvm.load %560 : !llvm.ptr -> i64
%566 = arith.addi %565, %arg0 : i64
llvm.store %566, %560 : i64, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%567 = arith.constant 0 : i32
%568 = arith.extsi %567 : i32 to i64
%569 = llvm.mlir.constant(1 : i64) : i64
%570 = llvm.alloca %569 x i64 : (i64) -> !llvm.ptr
llvm.store %568, %570 : i64, !llvm.ptr
%571 = arith.constant 2 : i32
%573 = arith.extsi %571 : i32 to i64
%572 = arith.remsi %547, %573 : i64
%574 = arith.constant 0 : i32
%576 = arith.extsi %574 : i32 to i64
%575 = arith.cmpi eq, %572, %576 : i64
cf.cond_br %575, ^bb84, ^bb85
^bb84:
%577 = arith.constant 1 : i32
%578 = arith.constant 1 : i32
%579 = arith.addi %577, %578 : i32
%580 = llvm.load %560 : !llvm.ptr -> i64
%582 = arith.extsi %579 : i32 to i64
%581 = arith.subi %582, %580 : i64
%583 = arith.remsi %581, %arg0 : i64
llvm.store %583, %570 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
%584 = arith.constant 1 : i32
%585 = arith.constant 1 : i32
%587 = arith.extsi %585 : i32 to i64
%586 = arith.subi %arg0, %587 : i64
%589 = arith.extsi %584 : i32 to i64
%588 = arith.addi %589, %586 : i64
%590 = llvm.load %560 : !llvm.ptr -> i64
%591 = arith.subi %588, %590 : i64
%592 = arith.remsi %591, %arg0 : i64
llvm.store %592, %570 : i64, !llvm.ptr
cf.br ^bb86
^bb86:
%593 = llvm.load %570 : !llvm.ptr -> i64
%594 = arith.constant 0 : i32
%596 = arith.extsi %594 : i32 to i64
%595 = arith.cmpi slt, %593, %596 : i64
cf.cond_br %595, ^bb87, ^bb88
^bb87:
%597 = llvm.load %570 : !llvm.ptr -> i64
%598 = arith.addi %597, %arg0 : i64
llvm.store %598, %570 : i64, !llvm.ptr
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
%599 = llvm.load %570 : !llvm.ptr -> i64
%600 = arith.constant 0 : i32
%602 = arith.extsi %600 : i32 to i64
%601 = arith.cmpi eq, %599, %602 : i64
cf.cond_br %601, ^bb90, ^bb91
^bb90:
%603 = arith.constant 2 : i32
%604 = arith.extsi %603 : i32 to i64
func.return %604 : i64
^bb91:
cf.br ^bb92
^bb92:
%605 = arith.constant 1 : i32
%606 = arith.extsi %605 : i32 to i64
func.return %606 : i64
}
func.func @gcd_i64(%arg0: i64, %arg1: i64) -> i64 {
%607 = llvm.mlir.constant(1 : i64) : i64
%608 = llvm.alloca %607 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %608 : i64, !llvm.ptr
%609 = llvm.mlir.constant(1 : i64) : i64
%610 = llvm.alloca %609 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %610 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%611 = llvm.load %610 : !llvm.ptr -> i64
%612 = arith.constant 0 : i32
%614 = arith.extsi %612 : i32 to i64
%613 = arith.cmpi ne, %611, %614 : i64
cf.cond_br %613, ^bb94, ^bb95
^bb94:
%615 = llvm.load %608 : !llvm.ptr -> i64
%616 = llvm.load %610 : !llvm.ptr -> i64
%617 = arith.remsi %615, %616 : i64
%618 = llvm.load %610 : !llvm.ptr -> i64
llvm.store %618, %608 : i64, !llvm.ptr
llvm.store %617, %610 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%619 = llvm.load %608 : !llvm.ptr -> i64
func.return %619 : i64
}
// Module static: g_dist_ne
llvm.mlir.global internal @g_dist_ne(0 : i64) : i64
func.func @get_distribution(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> i64 {
%620 = arith.constant 0 : i32
%621 = arith.extsi %620 : i32 to i64
%622 = llvm.mlir.constant(1 : i64) : i64
%623 = llvm.alloca %622 x i64 : (i64) -> !llvm.ptr
llvm.store %621, %623 : i64, !llvm.ptr
cf.br ^bb96
^bb96:
%624 = llvm.load %623 : !llvm.ptr -> i64
%625 = llvm.mlir.addressof @dc_size : !llvm.ptr
%626 = llvm.load %625 : !llvm.ptr -> i64
%627 = arith.cmpi slt, %624, %626 : i64
cf.cond_br %627, ^bb97, ^bb98
^bb97:
%629 = llvm.mlir.addressof @dc_p : !llvm.ptr
%630 = llvm.load %629 : !llvm.ptr -> !llvm.ptr
%631 = llvm.load %623 : !llvm.ptr -> i64
%632 = llvm.getelementptr %630[%631] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%628 = llvm.load %632 : !llvm.ptr -> i64
%633 = arith.cmpi eq, %628, %arg0 : i64
%634 = scf.if %633 -> (i1) {
%636 = llvm.mlir.addressof @dc_e : !llvm.ptr
%637 = llvm.load %636 : !llvm.ptr -> !llvm.ptr
%638 = llvm.load %623 : !llvm.ptr -> i64
%639 = llvm.getelementptr %637[%638] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%635 = llvm.load %639 : !llvm.ptr -> i64
%640 = arith.cmpi eq, %635, %arg1 : i64
scf.yield %640 : i1
} else {
%641 = arith.constant false
scf.yield %641 : i1
}
cf.cond_br %634, ^bb99, ^bb100
^bb99:
%643 = llvm.mlir.addressof @dc_ne : !llvm.ptr
%644 = llvm.load %643 : !llvm.ptr -> !llvm.ptr
%645 = llvm.load %623 : !llvm.ptr -> i64
%646 = llvm.getelementptr %644[%645] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%642 = llvm.load %646 : !llvm.ptr -> i64
%647 = llvm.mlir.addressof @g_dist_ne : !llvm.ptr
llvm.store %642, %647 : i64, !llvm.ptr
%648 = llvm.load %623 : !llvm.ptr -> i64
func.return %648 : i64
^bb100:
cf.br ^bb101
^bb101:
%649 = llvm.load %623 : !llvm.ptr -> i64
%650 = arith.constant 1 : i32
%652 = arith.extsi %650 : i32 to i64
%651 = arith.addi %649, %652 : i64
llvm.store %651, %623 : i64, !llvm.ptr
cf.br ^bb96
^bb98:
%653 = arith.constant 1 : i32
%654 = arith.extsi %653 : i32 to i64
%655 = llvm.mlir.constant(1 : i64) : i64
%656 = llvm.alloca %655 x i64 : (i64) -> !llvm.ptr
llvm.store %654, %656 : i64, !llvm.ptr
%657 = arith.constant 0 : i32
%658 = arith.extsi %657 : i32 to i64
%659 = llvm.mlir.constant(1 : i64) : i64
%660 = llvm.alloca %659 x i64 : (i64) -> !llvm.ptr
llvm.store %658, %660 : i64, !llvm.ptr
cf.br ^bb102
^bb102:
%661 = llvm.load %660 : !llvm.ptr -> i64
%662 = arith.constant 1 : i32
%664 = arith.extsi %662 : i32 to i64
%663 = arith.subi %arg1, %664 : i64
%665 = arith.cmpi slt, %661, %663 : i64
cf.cond_br %665, ^bb103, ^bb104
^bb103:
%666 = llvm.load %656 : !llvm.ptr -> i64
%667 = arith.muli %666, %arg0 : i64
llvm.store %667, %656 : i64, !llvm.ptr
%668 = llvm.load %660 : !llvm.ptr -> i64
%669 = arith.constant 1 : i32
%671 = arith.extsi %669 : i32 to i64
%670 = arith.addi %668, %671 : i64
llvm.store %670, %660 : i64, !llvm.ptr
cf.br ^bb102
^bb104:
%672 = llvm.load %656 : !llvm.ptr -> i64
%673 = arith.muli %arg2, %672 : i64
%674 = arith.muli %arg0, %arg0 : i64
%675 = arith.constant 1 : i32
%676 = arith.extsi %675 : i32 to i64
%677 = llvm.mlir.constant(1 : i64) : i64
%678 = llvm.alloca %677 x i64 : (i64) -> !llvm.ptr
llvm.store %676, %678 : i64, !llvm.ptr
%679 = arith.constant 0 : i32
%680 = arith.extsi %679 : i32 to i64
llvm.store %680, %660 : i64, !llvm.ptr
cf.br ^bb105
^bb105:
%681 = llvm.load %660 : !llvm.ptr -> i64
%682 = arith.constant 1 : i32
%684 = arith.extsi %682 : i32 to i64
%683 = arith.subi %arg1, %684 : i64
%685 = arith.cmpi slt, %681, %683 : i64
cf.cond_br %685, ^bb106, ^bb107
^bb106:
%686 = llvm.load %678 : !llvm.ptr -> i64
%687 = arith.muli %686, %674 : i64
llvm.store %687, %678 : i64, !llvm.ptr
%688 = llvm.load %660 : !llvm.ptr -> i64
%689 = arith.constant 1 : i32
%691 = arith.extsi %689 : i32 to i64
%690 = arith.addi %688, %691 : i64
llvm.store %690, %660 : i64, !llvm.ptr
cf.br ^bb105
^bb107:
%692 = llvm.load %678 : !llvm.ptr -> i64
%693 = arith.constant 1 : i32
%695 = arith.extsi %693 : i32 to i64
%694 = arith.subi %674, %695 : i64
%696 = arith.muli %692, %694 : i64
llvm.store %696, %678 : i64, !llvm.ptr
%697 = llvm.mlir.addressof @dc_size : !llvm.ptr
%698 = llvm.load %697 : !llvm.ptr -> i64
%699 = llvm.mlir.addressof @dc_p : !llvm.ptr
%700 = llvm.load %699 : !llvm.ptr -> !llvm.ptr
%701 = llvm.getelementptr %700[%698] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %701 : i64, !llvm.ptr
%702 = llvm.mlir.addressof @dc_e : !llvm.ptr
%703 = llvm.load %702 : !llvm.ptr -> !llvm.ptr
%704 = llvm.getelementptr %703[%698] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %704 : i64, !llvm.ptr
%705 = arith.constant 1 : i32
%707 = arith.extsi %705 : i32 to i64
%706 = arith.cmpi eq, %arg3, %707 : i64
cf.cond_br %706, ^bb108, ^bb109
^bb108:
%708 = llvm.mlir.addressof @dc_period : !llvm.ptr
%709 = llvm.load %708 : !llvm.ptr -> !llvm.ptr
%710 = arith.constant 2 : i32
%712 = arith.extsi %710 : i32 to i64
%711 = arith.muli %698, %712 : i64
%713 = llvm.getelementptr %709[%711] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %673, %713 : i64, !llvm.ptr
%714 = llvm.load %678 : !llvm.ptr -> i64
%715 = llvm.mlir.addressof @MOD : !llvm.ptr
%716 = llvm.load %715 : !llvm.ptr -> i64
%717 = arith.remsi %714, %716 : i64
%718 = llvm.mlir.addressof @dc_count : !llvm.ptr
%719 = llvm.load %718 : !llvm.ptr -> !llvm.ptr
%720 = arith.constant 2 : i32
%722 = arith.extsi %720 : i32 to i64
%721 = arith.muli %698, %722 : i64
%723 = llvm.getelementptr %719[%721] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %717, %723 : i64, !llvm.ptr
%724 = arith.constant 1 : i32
%725 = llvm.mlir.addressof @dc_ne : !llvm.ptr
%726 = llvm.load %725 : !llvm.ptr -> !llvm.ptr
%727 = arith.extsi %724 : i32 to i64
%728 = llvm.getelementptr %726[%698] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %727, %728 : i64, !llvm.ptr
%729 = arith.constant 1 : i32
%730 = arith.extsi %729 : i32 to i64
%731 = llvm.mlir.addressof @g_dist_ne : !llvm.ptr
llvm.store %730, %731 : i64, !llvm.ptr
cf.br ^bb110
^bb109:
%732 = arith.constant 2 : i32
%734 = arith.extsi %732 : i32 to i64
%733 = arith.cmpi eq, %arg3, %734 : i64
cf.cond_br %733, ^bb111, ^bb112
^bb111:
%735 = arith.constant 2 : i32
%737 = arith.extsi %735 : i32 to i64
%736 = arith.divsi %673, %737 : i64
%738 = arith.constant 1 : i32
%740 = arith.extsi %738 : i32 to i64
%739 = arith.subi %arg0, %740 : i64
%741 = llvm.load %656 : !llvm.ptr -> i64
%742 = arith.muli %739, %741 : i64
%743 = llvm.load %678 : !llvm.ptr -> i64
%744 = arith.subi %743, %742 : i64
%745 = llvm.mlir.addressof @dc_period : !llvm.ptr
%746 = llvm.load %745 : !llvm.ptr -> !llvm.ptr
%747 = arith.constant 2 : i32
%749 = arith.extsi %747 : i32 to i64
%748 = arith.muli %698, %749 : i64
%750 = llvm.getelementptr %746[%748] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %736, %750 : i64, !llvm.ptr
%751 = llvm.mlir.addressof @MOD : !llvm.ptr
%752 = llvm.load %751 : !llvm.ptr -> i64
%753 = arith.remsi %742, %752 : i64
%754 = llvm.mlir.addressof @dc_count : !llvm.ptr
%755 = llvm.load %754 : !llvm.ptr -> !llvm.ptr
%756 = arith.constant 2 : i32
%758 = arith.extsi %756 : i32 to i64
%757 = arith.muli %698, %758 : i64
%759 = llvm.getelementptr %755[%757] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %753, %759 : i64, !llvm.ptr
%760 = llvm.mlir.addressof @dc_period : !llvm.ptr
%761 = llvm.load %760 : !llvm.ptr -> !llvm.ptr
%762 = arith.constant 2 : i32
%764 = arith.extsi %762 : i32 to i64
%763 = arith.muli %698, %764 : i64
%765 = arith.constant 1 : i32
%767 = arith.extsi %765 : i32 to i64
%766 = arith.addi %763, %767 : i64
%768 = llvm.getelementptr %761[%766] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %673, %768 : i64, !llvm.ptr
%769 = llvm.mlir.addressof @MOD : !llvm.ptr
%770 = llvm.load %769 : !llvm.ptr -> i64
%771 = arith.remsi %744, %770 : i64
%772 = llvm.mlir.addressof @dc_count : !llvm.ptr
%773 = llvm.load %772 : !llvm.ptr -> !llvm.ptr
%774 = arith.constant 2 : i32
%776 = arith.extsi %774 : i32 to i64
%775 = arith.muli %698, %776 : i64
%777 = arith.constant 1 : i32
%779 = arith.extsi %777 : i32 to i64
%778 = arith.addi %775, %779 : i64
%780 = llvm.getelementptr %773[%778] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %771, %780 : i64, !llvm.ptr
%781 = arith.constant 2 : i32
%782 = llvm.mlir.addressof @dc_ne : !llvm.ptr
%783 = llvm.load %782 : !llvm.ptr -> !llvm.ptr
%784 = arith.extsi %781 : i32 to i64
%785 = llvm.getelementptr %783[%698] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %784, %785 : i64, !llvm.ptr
%786 = arith.constant 2 : i32
%787 = arith.extsi %786 : i32 to i64
%788 = llvm.mlir.addressof @g_dist_ne : !llvm.ptr
llvm.store %787, %788 : i64, !llvm.ptr
cf.br ^bb113
^bb112:
%789 = arith.constant 5 : i32
%791 = arith.extsi %789 : i32 to i64
%790 = arith.divsi %673, %791 : i64
%792 = arith.constant 1 : i32
%794 = arith.extsi %792 : i32 to i64
%793 = arith.subi %arg0, %794 : i64
%795 = llvm.mlir.constant(1 : i64) : i64
%796 = llvm.alloca %795 x i64 : (i64) -> !llvm.ptr
llvm.store %793, %796 : i64, !llvm.ptr
%797 = arith.constant 0 : i32
%798 = arith.extsi %797 : i32 to i64
llvm.store %798, %660 : i64, !llvm.ptr
cf.br ^bb114
^bb114:
%799 = llvm.load %660 : !llvm.ptr -> i64
%800 = arith.constant 1 : i32
%802 = arith.extsi %800 : i32 to i64
%801 = arith.subi %arg1, %802 : i64
%803 = arith.cmpi slt, %799, %801 : i64
cf.cond_br %803, ^bb115, ^bb116
^bb115:
%804 = llvm.load %796 : !llvm.ptr -> i64
%805 = arith.muli %804, %674 : i64
llvm.store %805, %796 : i64, !llvm.ptr
%806 = llvm.load %660 : !llvm.ptr -> i64
%807 = arith.constant 1 : i32
%809 = arith.extsi %807 : i32 to i64
%808 = arith.addi %806, %809 : i64
llvm.store %808, %660 : i64, !llvm.ptr
cf.br ^bb114
^bb116:
%810 = llvm.load %678 : !llvm.ptr -> i64
%811 = llvm.load %796 : !llvm.ptr -> i64
%812 = arith.subi %810, %811 : i64
%813 = llvm.mlir.addressof @dc_period : !llvm.ptr
%814 = llvm.load %813 : !llvm.ptr -> !llvm.ptr
%815 = arith.constant 2 : i32
%817 = arith.extsi %815 : i32 to i64
%816 = arith.muli %698, %817 : i64
%818 = llvm.getelementptr %814[%816] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %790, %818 : i64, !llvm.ptr
%819 = llvm.load %796 : !llvm.ptr -> i64
%820 = llvm.mlir.addressof @MOD : !llvm.ptr
%821 = llvm.load %820 : !llvm.ptr -> i64
%822 = arith.remsi %819, %821 : i64
%823 = llvm.mlir.addressof @dc_count : !llvm.ptr
%824 = llvm.load %823 : !llvm.ptr -> !llvm.ptr
%825 = arith.constant 2 : i32
%827 = arith.extsi %825 : i32 to i64
%826 = arith.muli %698, %827 : i64
%828 = llvm.getelementptr %824[%826] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %822, %828 : i64, !llvm.ptr
%829 = llvm.mlir.addressof @dc_period : !llvm.ptr
%830 = llvm.load %829 : !llvm.ptr -> !llvm.ptr
%831 = arith.constant 2 : i32
%833 = arith.extsi %831 : i32 to i64
%832 = arith.muli %698, %833 : i64
%834 = arith.constant 1 : i32
%836 = arith.extsi %834 : i32 to i64
%835 = arith.addi %832, %836 : i64
%837 = llvm.getelementptr %830[%835] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %673, %837 : i64, !llvm.ptr
%838 = llvm.mlir.addressof @MOD : !llvm.ptr
%839 = llvm.load %838 : !llvm.ptr -> i64
%840 = arith.remsi %812, %839 : i64
%841 = llvm.mlir.addressof @dc_count : !llvm.ptr
%842 = llvm.load %841 : !llvm.ptr -> !llvm.ptr
%843 = arith.constant 2 : i32
%845 = arith.extsi %843 : i32 to i64
%844 = arith.muli %698, %845 : i64
%846 = arith.constant 1 : i32
%848 = arith.extsi %846 : i32 to i64
%847 = arith.addi %844, %848 : i64
%849 = llvm.getelementptr %842[%847] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %840, %849 : i64, !llvm.ptr
%850 = arith.constant 2 : i32
%851 = llvm.mlir.addressof @dc_ne : !llvm.ptr
%852 = llvm.load %851 : !llvm.ptr -> !llvm.ptr
%853 = arith.extsi %850 : i32 to i64
%854 = llvm.getelementptr %852[%698] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %853, %854 : i64, !llvm.ptr
%855 = arith.constant 2 : i32
%856 = arith.extsi %855 : i32 to i64
%857 = llvm.mlir.addressof @g_dist_ne : !llvm.ptr
llvm.store %856, %857 : i64, !llvm.ptr
cf.br ^bb113
^bb113:
cf.br ^bb110
^bb110:
%858 = llvm.mlir.addressof @dc_size : !llvm.ptr
%859 = llvm.load %858 : !llvm.ptr -> i64
%860 = arith.constant 1 : i32
%862 = arith.extsi %860 : i32 to i64
%861 = arith.addi %859, %862 : i64
%863 = llvm.mlir.addressof @dc_size : !llvm.ptr
llvm.store %861, %863 : i64, !llvm.ptr
func.return %698 : i64
}
func.func @main() -> i32 {
%864 = arith.constant 2 : i32
%865 = llvm.mlir.addressof @N : !llvm.ptr
%866 = llvm.load %865 : !llvm.ptr -> i64
%868 = arith.extsi %864 : i32 to i64
%867 = arith.muli %868, %866 : i64
%869 = arith.constant 2 : i32
%871 = arith.extsi %869 : i32 to i64
%870 = arith.addi %867, %871 : i64
func.call @sieve_spf(%870) : (i64) -> ()
%874 = llvm.mlir.addressof @N : !llvm.ptr
%875 = llvm.load %874 : !llvm.ptr -> i64
%876 = arith.constant 1 : i32
%878 = arith.extsi %876 : i32 to i64
%877 = arith.addi %875, %878 : i64
%879 = arith.constant 8 : i32
%880 = arith.extsi %879 : i32 to i64
%873 = func.call @calloc(%877, %880) : (i64, i64) -> !llvm.ptr
%881 = llvm.mlir.addressof @pi_prime : !llvm.ptr
llvm.store %873, %881 : !llvm.ptr, !llvm.ptr
%883 = llvm.mlir.addressof @N : !llvm.ptr
%884 = llvm.load %883 : !llvm.ptr -> i64
%885 = arith.constant 1 : i32
%887 = arith.extsi %885 : i32 to i64
%886 = arith.addi %884, %887 : i64
%888 = arith.constant 8 : i32
%890 = arith.extsi %888 : i32 to i64
%889 = arith.muli %886, %890 : i64
%882 = func.call @malloc(%889) : (i64) -> !llvm.ptr
%891 = llvm.mlir.addressof @k_prime : !llvm.ptr
llvm.store %882, %891 : !llvm.ptr, !llvm.ptr
%892 = arith.constant 0 : i32
%893 = arith.extsi %892 : i32 to i64
%894 = llvm.mlir.constant(1 : i64) : i64
%895 = llvm.alloca %894 x i64 : (i64) -> !llvm.ptr
llvm.store %893, %895 : i64, !llvm.ptr
cf.br ^bb117
^bb117:
%896 = llvm.load %895 : !llvm.ptr -> i64
%897 = llvm.mlir.addressof @N : !llvm.ptr
%898 = llvm.load %897 : !llvm.ptr -> i64
%899 = arith.cmpi sle, %896, %898 : i64
cf.cond_br %899, ^bb118, ^bb119
^bb118:
%900 = arith.constant 1 : i32
%901 = llvm.mlir.addressof @k_prime : !llvm.ptr
%902 = llvm.load %901 : !llvm.ptr -> !llvm.ptr
%903 = llvm.load %895 : !llvm.ptr -> i64
%904 = arith.extsi %900 : i32 to i64
%905 = llvm.getelementptr %902[%903] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %904, %905 : i64, !llvm.ptr
%906 = llvm.load %895 : !llvm.ptr -> i64
%907 = arith.constant 1 : i32
%909 = arith.extsi %907 : i32 to i64
%908 = arith.addi %906, %909 : i64
llvm.store %908, %895 : i64, !llvm.ptr
cf.br ^bb117
^bb119:
%910 = arith.constant 2 : i32
%911 = arith.extsi %910 : i32 to i64
%912 = llvm.mlir.constant(1 : i64) : i64
%913 = llvm.alloca %912 x i64 : (i64) -> !llvm.ptr
llvm.store %911, %913 : i64, !llvm.ptr
cf.br ^bb120
^bb120:
%914 = llvm.load %913 : !llvm.ptr -> i64
%915 = llvm.mlir.addressof @N : !llvm.ptr
%916 = llvm.load %915 : !llvm.ptr -> i64
%917 = arith.cmpi sle, %914, %916 : i64
cf.cond_br %917, ^bb121, ^bb122
^bb121:
%919 = llvm.mlir.addressof @spf : !llvm.ptr
%920 = llvm.load %919 : !llvm.ptr -> !llvm.ptr
%921 = llvm.load %913 : !llvm.ptr -> i64
%922 = llvm.getelementptr %920[%921] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%918 = llvm.load %922 : !llvm.ptr -> i32
%923 = llvm.load %913 : !llvm.ptr -> i64
%924 = arith.trunci %923 : i64 to i32
%925 = arith.cmpi eq, %918, %924 : i32
cf.cond_br %925, ^bb123, ^bb124
^bb123:
%927 = llvm.load %913 : !llvm.ptr -> i64
%926 = func.call @pisano_prime(%927) : (i64) -> i64
%928 = llvm.mlir.addressof @pi_prime : !llvm.ptr
%929 = llvm.load %928 : !llvm.ptr -> !llvm.ptr
%930 = llvm.load %913 : !llvm.ptr -> i64
%931 = llvm.getelementptr %929[%930] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %926, %931 : i64, !llvm.ptr
%933 = llvm.load %913 : !llvm.ptr -> i64
%932 = func.call @has_short_period_factor(%933, %926) : (i64, i64) -> i64
%934 = llvm.mlir.addressof @k_prime : !llvm.ptr
%935 = llvm.load %934 : !llvm.ptr -> !llvm.ptr
%936 = llvm.load %913 : !llvm.ptr -> i64
%937 = llvm.getelementptr %935[%936] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %932, %937 : i64, !llvm.ptr
cf.br ^bb125
^bb124:
cf.br ^bb125
^bb125:
%938 = llvm.load %913 : !llvm.ptr -> i64
%939 = arith.constant 1 : i32
%941 = arith.extsi %939 : i32 to i64
%940 = arith.addi %938, %941 : i64
llvm.store %940, %913 : i64, !llvm.ptr
cf.br ^bb120
^bb122:
%943 = arith.constant 100000 : i32
%944 = arith.constant 8 : i32
%945 = arith.muli %943, %944 : i32
%946 = arith.extsi %945 : i32 to i64
%942 = func.call @malloc(%946) : (i64) -> !llvm.ptr
%947 = llvm.mlir.addressof @dc_p : !llvm.ptr
llvm.store %942, %947 : !llvm.ptr, !llvm.ptr
%949 = arith.constant 100000 : i32
%950 = arith.constant 8 : i32
%951 = arith.muli %949, %950 : i32
%952 = arith.extsi %951 : i32 to i64
%948 = func.call @malloc(%952) : (i64) -> !llvm.ptr
%953 = llvm.mlir.addressof @dc_e : !llvm.ptr
llvm.store %948, %953 : !llvm.ptr, !llvm.ptr
%955 = arith.constant 100000 : i32
%956 = arith.constant 8 : i32
%957 = arith.muli %955, %956 : i32
%958 = arith.extsi %957 : i32 to i64
%954 = func.call @malloc(%958) : (i64) -> !llvm.ptr
%959 = llvm.mlir.addressof @dc_ne : !llvm.ptr
llvm.store %954, %959 : !llvm.ptr, !llvm.ptr
%961 = arith.constant 200000 : i32
%962 = arith.constant 8 : i32
%963 = arith.muli %961, %962 : i32
%964 = arith.extsi %963 : i32 to i64
%960 = func.call @malloc(%964) : (i64) -> !llvm.ptr
%965 = llvm.mlir.addressof @dc_period : !llvm.ptr
llvm.store %960, %965 : !llvm.ptr, !llvm.ptr
%967 = arith.constant 200000 : i32
%968 = arith.constant 8 : i32
%969 = arith.muli %967, %968 : i32
%970 = arith.extsi %969 : i32 to i64
%966 = func.call @malloc(%970) : (i64) -> !llvm.ptr
%971 = llvm.mlir.addressof @dc_count : !llvm.ptr
llvm.store %966, %971 : !llvm.ptr, !llvm.ptr
%972 = arith.constant 0 : i32
%973 = arith.extsi %972 : i32 to i64
%974 = llvm.mlir.addressof @dc_size : !llvm.ptr
llvm.store %973, %974 : i64, !llvm.ptr
%976 = arith.constant 256 : i32
%977 = arith.constant 8 : i32
%978 = arith.muli %976, %977 : i32
%979 = arith.extsi %978 : i32 to i64
%975 = func.call @malloc(%979) : (i64) -> !llvm.ptr
%980 = llvm.mlir.addressof @cur_key : !llvm.ptr
llvm.store %975, %980 : !llvm.ptr, !llvm.ptr
%982 = arith.constant 256 : i32
%983 = arith.constant 8 : i32
%984 = arith.muli %982, %983 : i32
%985 = arith.extsi %984 : i32 to i64
%981 = func.call @malloc(%985) : (i64) -> !llvm.ptr
%986 = llvm.mlir.addressof @cur_val : !llvm.ptr
llvm.store %981, %986 : !llvm.ptr, !llvm.ptr
%988 = arith.constant 256 : i32
%989 = arith.constant 8 : i32
%990 = arith.muli %988, %989 : i32
%991 = arith.extsi %990 : i32 to i64
%987 = func.call @malloc(%991) : (i64) -> !llvm.ptr
%992 = llvm.mlir.addressof @new_key : !llvm.ptr
llvm.store %987, %992 : !llvm.ptr, !llvm.ptr
%994 = arith.constant 256 : i32
%995 = arith.constant 8 : i32
%996 = arith.muli %994, %995 : i32
%997 = arith.extsi %996 : i32 to i64
%993 = func.call @malloc(%997) : (i64) -> !llvm.ptr
%998 = llvm.mlir.addressof @new_val : !llvm.ptr
llvm.store %993, %998 : !llvm.ptr, !llvm.ptr
%999 = arith.constant 0 : i32
%1000 = arith.extsi %999 : i32 to i64
%1001 = llvm.mlir.constant(1 : i64) : i64
%1002 = llvm.alloca %1001 x i64 : (i64) -> !llvm.ptr
llvm.store %1000, %1002 : i64, !llvm.ptr
%1003 = arith.constant 1 : i32
%1004 = arith.extsi %1003 : i32 to i64
%1005 = llvm.mlir.constant(1 : i64) : i64
%1006 = llvm.alloca %1005 x i64 : (i64) -> !llvm.ptr
llvm.store %1004, %1006 : i64, !llvm.ptr
cf.br ^bb126
^bb126:
%1007 = llvm.load %1006 : !llvm.ptr -> i64
%1008 = llvm.mlir.addressof @N : !llvm.ptr
%1009 = llvm.load %1008 : !llvm.ptr -> i64
%1010 = arith.cmpi sle, %1007, %1009 : i64
cf.cond_br %1010, ^bb127, ^bb128
^bb127:
%1011 = llvm.load %1006 : !llvm.ptr -> i64
%1012 = llvm.mlir.constant(1 : i64) : i64
%1013 = llvm.alloca %1012 x i64 : (i64) -> !llvm.ptr
llvm.store %1011, %1013 : i64, !llvm.ptr
%1015 = arith.constant 0 : i32
%1016 = arith.constant 0 : i32
%1017 = arith.constant 0 : i32
%1018 = arith.constant 0 : i32
%1019 = arith.constant 0 : i32
%1020 = arith.constant 0 : i32
%1021 = arith.constant 0 : i32
%1022 = arith.constant 0 : i32
%1023 = llvm.mlir.constant(1 : i64) : i64
%1024 = llvm.alloca %1023 x !llvm.array<8 x i64> : (i64) -> !llvm.ptr
%1025 = llvm.mlir.zero : !llvm.array<8 x i64>
llvm.store %1025, %1024 : !llvm.array<8 x i64>, !llvm.ptr
%1026 = arith.extsi %1015 : i32 to i64
%1027 = arith.extsi %1016 : i32 to i64
%1028 = arith.extsi %1017 : i32 to i64
%1029 = arith.extsi %1018 : i32 to i64
%1030 = arith.extsi %1019 : i32 to i64
%1031 = arith.extsi %1020 : i32 to i64
%1032 = arith.extsi %1021 : i32 to i64
%1033 = arith.extsi %1022 : i32 to i64
%1034 = llvm.mlir.constant(0 : i64) : i64
%1035 = llvm.getelementptr %1024[0, %1034] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1026, %1035 : i64, !llvm.ptr
%1036 = llvm.mlir.constant(1 : i64) : i64
%1037 = llvm.getelementptr %1024[0, %1036] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1027, %1037 : i64, !llvm.ptr
%1038 = llvm.mlir.constant(2 : i64) : i64
%1039 = llvm.getelementptr %1024[0, %1038] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1028, %1039 : i64, !llvm.ptr
%1040 = llvm.mlir.constant(3 : i64) : i64
%1041 = llvm.getelementptr %1024[0, %1040] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1029, %1041 : i64, !llvm.ptr
%1042 = llvm.mlir.constant(4 : i64) : i64
%1043 = llvm.getelementptr %1024[0, %1042] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1030, %1043 : i64, !llvm.ptr
%1044 = llvm.mlir.constant(5 : i64) : i64
%1045 = llvm.getelementptr %1024[0, %1044] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1031, %1045 : i64, !llvm.ptr
%1046 = llvm.mlir.constant(6 : i64) : i64
%1047 = llvm.getelementptr %1024[0, %1046] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1032, %1047 : i64, !llvm.ptr
%1048 = llvm.mlir.constant(7 : i64) : i64
%1049 = llvm.getelementptr %1024[0, %1048] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1033, %1049 : i64, !llvm.ptr
%1051 = arith.constant 0 : i32
%1052 = arith.constant 0 : i32
%1053 = arith.constant 0 : i32
%1054 = arith.constant 0 : i32
%1055 = arith.constant 0 : i32
%1056 = arith.constant 0 : i32
%1057 = arith.constant 0 : i32
%1058 = arith.constant 0 : i32
%1059 = llvm.mlir.constant(1 : i64) : i64
%1060 = llvm.alloca %1059 x !llvm.array<8 x i64> : (i64) -> !llvm.ptr
%1061 = llvm.mlir.zero : !llvm.array<8 x i64>
llvm.store %1061, %1060 : !llvm.array<8 x i64>, !llvm.ptr
%1062 = arith.extsi %1051 : i32 to i64
%1063 = arith.extsi %1052 : i32 to i64
%1064 = arith.extsi %1053 : i32 to i64
%1065 = arith.extsi %1054 : i32 to i64
%1066 = arith.extsi %1055 : i32 to i64
%1067 = arith.extsi %1056 : i32 to i64
%1068 = arith.extsi %1057 : i32 to i64
%1069 = arith.extsi %1058 : i32 to i64
%1070 = llvm.mlir.constant(0 : i64) : i64
%1071 = llvm.getelementptr %1060[0, %1070] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1062, %1071 : i64, !llvm.ptr
%1072 = llvm.mlir.constant(1 : i64) : i64
%1073 = llvm.getelementptr %1060[0, %1072] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1063, %1073 : i64, !llvm.ptr
%1074 = llvm.mlir.constant(2 : i64) : i64
%1075 = llvm.getelementptr %1060[0, %1074] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1064, %1075 : i64, !llvm.ptr
%1076 = llvm.mlir.constant(3 : i64) : i64
%1077 = llvm.getelementptr %1060[0, %1076] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1065, %1077 : i64, !llvm.ptr
%1078 = llvm.mlir.constant(4 : i64) : i64
%1079 = llvm.getelementptr %1060[0, %1078] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1066, %1079 : i64, !llvm.ptr
%1080 = llvm.mlir.constant(5 : i64) : i64
%1081 = llvm.getelementptr %1060[0, %1080] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1067, %1081 : i64, !llvm.ptr
%1082 = llvm.mlir.constant(6 : i64) : i64
%1083 = llvm.getelementptr %1060[0, %1082] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1068, %1083 : i64, !llvm.ptr
%1084 = llvm.mlir.constant(7 : i64) : i64
%1085 = llvm.getelementptr %1060[0, %1084] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1069, %1085 : i64, !llvm.ptr
%1086 = arith.constant 0 : i32
%1087 = arith.extsi %1086 : i32 to i64
%1088 = llvm.mlir.constant(1 : i64) : i64
%1089 = llvm.alloca %1088 x i64 : (i64) -> !llvm.ptr
llvm.store %1087, %1089 : i64, !llvm.ptr
cf.br ^bb129
^bb129:
%1090 = llvm.load %1013 : !llvm.ptr -> i64
%1091 = arith.constant 1 : i32
%1093 = arith.extsi %1091 : i32 to i64
%1092 = arith.cmpi sgt, %1090, %1093 : i64
cf.cond_br %1092, ^bb130, ^bb131
^bb130:
%1095 = llvm.mlir.addressof @spf : !llvm.ptr
%1096 = llvm.load %1095 : !llvm.ptr -> !llvm.ptr
%1097 = llvm.load %1013 : !llvm.ptr -> i64
%1098 = llvm.getelementptr %1096[%1097] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1094 = llvm.load %1098 : !llvm.ptr -> i32
%1099 = arith.extsi %1094 : i32 to i64
%1100 = arith.constant 0 : i32
%1101 = arith.extsi %1100 : i32 to i64
%1102 = llvm.mlir.constant(1 : i64) : i64
%1103 = llvm.alloca %1102 x i64 : (i64) -> !llvm.ptr
llvm.store %1101, %1103 : i64, !llvm.ptr
cf.br ^bb132
^bb132:
%1104 = llvm.load %1013 : !llvm.ptr -> i64
%1105 = arith.remsi %1104, %1099 : i64
%1106 = arith.constant 0 : i32
%1108 = arith.extsi %1106 : i32 to i64
%1107 = arith.cmpi eq, %1105, %1108 : i64
cf.cond_br %1107, ^bb133, ^bb134
^bb133:
%1109 = llvm.load %1013 : !llvm.ptr -> i64
%1110 = arith.divsi %1109, %1099 : i64
llvm.store %1110, %1013 : i64, !llvm.ptr
%1111 = llvm.load %1103 : !llvm.ptr -> i64
%1112 = arith.constant 1 : i32
%1114 = arith.extsi %1112 : i32 to i64
%1113 = arith.addi %1111, %1114 : i64
llvm.store %1113, %1103 : i64, !llvm.ptr
cf.br ^bb132
^bb134:
%1116 = llvm.load %1103 : !llvm.ptr -> i64
%1118 = llvm.mlir.addressof @pi_prime : !llvm.ptr
%1119 = llvm.load %1118 : !llvm.ptr -> !llvm.ptr
%1120 = llvm.getelementptr %1119[%1099] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1117 = llvm.load %1120 : !llvm.ptr -> i64
%1122 = llvm.mlir.addressof @k_prime : !llvm.ptr
%1123 = llvm.load %1122 : !llvm.ptr -> !llvm.ptr
%1124 = llvm.getelementptr %1123[%1099] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1121 = llvm.load %1124 : !llvm.ptr -> i64
%1115 = func.call @get_distribution(%1099, %1116, %1117, %1121) : (i64, i64, i64, i64) -> i64
%1125 = llvm.load %1089 : !llvm.ptr -> i64
%1126 = llvm.getelementptr %1024[0, %1125] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1115, %1126 : i64, !llvm.ptr
%1127 = llvm.mlir.addressof @g_dist_ne : !llvm.ptr
%1128 = llvm.load %1127 : !llvm.ptr -> i64
%1129 = llvm.load %1089 : !llvm.ptr -> i64
%1130 = llvm.getelementptr %1060[0, %1129] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
llvm.store %1128, %1130 : i64, !llvm.ptr
%1131 = llvm.load %1089 : !llvm.ptr -> i64
%1132 = arith.constant 1 : i32
%1134 = arith.extsi %1132 : i32 to i64
%1133 = arith.addi %1131, %1134 : i64
llvm.store %1133, %1089 : i64, !llvm.ptr
cf.br ^bb129
^bb131:
%1135 = arith.constant 1 : i32
%1136 = arith.extsi %1135 : i32 to i64
%1137 = llvm.mlir.constant(1 : i64) : i64
%1138 = llvm.alloca %1137 x i64 : (i64) -> !llvm.ptr
llvm.store %1136, %1138 : i64, !llvm.ptr
%1139 = arith.constant 1 : i32
%1140 = llvm.mlir.addressof @cur_key : !llvm.ptr
%1141 = llvm.load %1140 : !llvm.ptr -> !llvm.ptr
%1142 = arith.constant 0 : i32
%1143 = arith.extsi %1139 : i32 to i64
%1144 = arith.extsi %1142 : i32 to i64
%1145 = llvm.getelementptr %1141[%1144] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1143, %1145 : i64, !llvm.ptr
%1146 = arith.constant 1 : i32
%1147 = llvm.mlir.addressof @cur_val : !llvm.ptr
%1148 = llvm.load %1147 : !llvm.ptr -> !llvm.ptr
%1149 = arith.constant 0 : i32
%1150 = arith.extsi %1146 : i32 to i64
%1151 = arith.extsi %1149 : i32 to i64
%1152 = llvm.getelementptr %1148[%1151] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1150, %1152 : i64, !llvm.ptr
%1153 = arith.constant 0 : i32
%1154 = arith.extsi %1153 : i32 to i64
%1155 = llvm.mlir.constant(1 : i64) : i64
%1156 = llvm.alloca %1155 x i64 : (i64) -> !llvm.ptr
llvm.store %1154, %1156 : i64, !llvm.ptr
cf.br ^bb135
^bb135:
%1157 = llvm.load %1156 : !llvm.ptr -> i64
%1158 = llvm.load %1089 : !llvm.ptr -> i64
%1159 = arith.cmpi slt, %1157, %1158 : i64
cf.cond_br %1159, ^bb136, ^bb137
^bb136:
%1160 = arith.constant 0 : i32
%1161 = arith.extsi %1160 : i32 to i64
%1162 = llvm.mlir.constant(1 : i64) : i64
%1163 = llvm.alloca %1162 x i64 : (i64) -> !llvm.ptr
llvm.store %1161, %1163 : i64, !llvm.ptr
%1165 = llvm.load %1156 : !llvm.ptr -> i64
%1166 = llvm.getelementptr %1024[0, %1165] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
%1164 = llvm.load %1166 : !llvm.ptr -> i64
%1168 = llvm.load %1156 : !llvm.ptr -> i64
%1169 = llvm.getelementptr %1060[0, %1168] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<8 x i64>
%1167 = llvm.load %1169 : !llvm.ptr -> i64
%1170 = arith.constant 0 : i32
%1171 = arith.extsi %1170 : i32 to i64
%1172 = llvm.mlir.constant(1 : i64) : i64
%1173 = llvm.alloca %1172 x i64 : (i64) -> !llvm.ptr
llvm.store %1171, %1173 : i64, !llvm.ptr
cf.br ^bb138
^bb138:
%1174 = llvm.load %1173 : !llvm.ptr -> i64
%1175 = llvm.load %1138 : !llvm.ptr -> i64
%1176 = arith.cmpi slt, %1174, %1175 : i64
cf.cond_br %1176, ^bb139, ^bb140
^bb139:
%1177 = arith.constant 0 : i32
%1178 = arith.extsi %1177 : i32 to i64
%1179 = llvm.mlir.constant(1 : i64) : i64
%1180 = llvm.alloca %1179 x i64 : (i64) -> !llvm.ptr
llvm.store %1178, %1180 : i64, !llvm.ptr
cf.br ^bb141
^bb141:
%1181 = llvm.load %1180 : !llvm.ptr -> i64
%1182 = arith.cmpi slt, %1181, %1167 : i64
cf.cond_br %1182, ^bb142, ^bb143
^bb142:
%1184 = llvm.mlir.addressof @cur_key : !llvm.ptr
%1185 = llvm.load %1184 : !llvm.ptr -> !llvm.ptr
%1186 = llvm.load %1173 : !llvm.ptr -> i64
%1187 = llvm.getelementptr %1185[%1186] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1183 = llvm.load %1187 : !llvm.ptr -> i64
%1189 = llvm.mlir.addressof @dc_period : !llvm.ptr
%1190 = llvm.load %1189 : !llvm.ptr -> !llvm.ptr
%1191 = arith.constant 2 : i32
%1193 = arith.extsi %1191 : i32 to i64
%1192 = arith.muli %1164, %1193 : i64
%1194 = llvm.load %1180 : !llvm.ptr -> i64
%1195 = arith.addi %1192, %1194 : i64
%1196 = llvm.getelementptr %1190[%1195] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1188 = llvm.load %1196 : !llvm.ptr -> i64
%1197 = func.call @gcd_i64(%1183, %1188) : (i64, i64) -> i64
%1198 = arith.extsi %1183 : i64 to i128
%1199 = arith.extsi %1197 : i64 to i128
%1201 = arith.trunci %1198 : i128 to i64
%1202 = arith.trunci %1199 : i128 to i64
%1200 = arith.divsi %1201, %1202 : i64
%1203 = arith.extsi %1188 : i64 to i128
%1205 = arith.trunci %1203 : i128 to i64
%1204 = arith.muli %1200, %1205 : i64
%1206 = arith.extsi %1204 : i64 to i128
%1207 = arith.trunci %1206 : i128 to i64
%1209 = llvm.mlir.addressof @cur_val : !llvm.ptr
%1210 = llvm.load %1209 : !llvm.ptr -> !llvm.ptr
%1211 = llvm.load %1173 : !llvm.ptr -> i64
%1212 = llvm.getelementptr %1210[%1211] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1208 = llvm.load %1212 : !llvm.ptr -> i64
%1213 = arith.extsi %1208 : i64 to i128
%1215 = llvm.mlir.addressof @dc_count : !llvm.ptr
%1216 = llvm.load %1215 : !llvm.ptr -> !llvm.ptr
%1217 = arith.constant 2 : i32
%1219 = arith.extsi %1217 : i32 to i64
%1218 = arith.muli %1164, %1219 : i64
%1220 = llvm.load %1180 : !llvm.ptr -> i64
%1221 = arith.addi %1218, %1220 : i64
%1222 = llvm.getelementptr %1216[%1221] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1214 = llvm.load %1222 : !llvm.ptr -> i64
%1223 = arith.extsi %1214 : i64 to i128
%1225 = arith.trunci %1213 : i128 to i64
%1226 = arith.trunci %1223 : i128 to i64
%1224 = arith.muli %1225, %1226 : i64
%1227 = llvm.mlir.addressof @MOD : !llvm.ptr
%1228 = llvm.load %1227 : !llvm.ptr -> i64
%1229 = arith.extsi %1228 : i64 to i128
%1231 = arith.trunci %1229 : i128 to i64
%1230 = arith.remsi %1224, %1231 : i64
%1232 = arith.constant 1 : i32
%1234 = arith.constant 0 : i32
%1233 = arith.subi %1234, %1232 : i32
%1235 = arith.extsi %1233 : i32 to i64
%1236 = llvm.mlir.constant(1 : i64) : i64
%1237 = llvm.alloca %1236 x i64 : (i64) -> !llvm.ptr
llvm.store %1235, %1237 : i64, !llvm.ptr
%1238 = arith.constant 0 : i32
%1239 = arith.extsi %1238 : i32 to i64
%1240 = llvm.mlir.constant(1 : i64) : i64
%1241 = llvm.alloca %1240 x i64 : (i64) -> !llvm.ptr
llvm.store %1239, %1241 : i64, !llvm.ptr
cf.br ^bb144
^bb144:
%1242 = llvm.load %1241 : !llvm.ptr -> i64
%1243 = llvm.load %1163 : !llvm.ptr -> i64
%1244 = arith.cmpi slt, %1242, %1243 : i64
cf.cond_br %1244, ^bb145, ^bb146
^bb145:
%1246 = llvm.mlir.addressof @new_key : !llvm.ptr
%1247 = llvm.load %1246 : !llvm.ptr -> !llvm.ptr
%1248 = llvm.load %1241 : !llvm.ptr -> i64
%1249 = llvm.getelementptr %1247[%1248] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1245 = llvm.load %1249 : !llvm.ptr -> i64
%1250 = arith.cmpi eq, %1245, %1207 : i64
cf.cond_br %1250, ^bb147, ^bb148
^bb147:
%1251 = llvm.load %1241 : !llvm.ptr -> i64
llvm.store %1251, %1237 : i64, !llvm.ptr
cf.br ^bb146
^bb148:
cf.br ^bb149
^bb149:
%1252 = llvm.load %1241 : !llvm.ptr -> i64
%1253 = arith.constant 1 : i32
%1255 = arith.extsi %1253 : i32 to i64
%1254 = arith.addi %1252, %1255 : i64
llvm.store %1254, %1241 : i64, !llvm.ptr
cf.br ^bb144
^bb146:
%1256 = llvm.load %1237 : !llvm.ptr -> i64
%1257 = arith.constant 0 : i32
%1259 = arith.extsi %1257 : i32 to i64
%1258 = arith.cmpi sge, %1256, %1259 : i64
cf.cond_br %1258, ^bb150, ^bb151
^bb150:
%1261 = llvm.mlir.addressof @new_val : !llvm.ptr
%1262 = llvm.load %1261 : !llvm.ptr -> !llvm.ptr
%1263 = llvm.load %1237 : !llvm.ptr -> i64
%1264 = llvm.getelementptr %1262[%1263] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1260 = llvm.load %1264 : !llvm.ptr -> i64
%1265 = arith.addi %1260, %1230 : i64
%1266 = llvm.mlir.addressof @MOD : !llvm.ptr
%1267 = llvm.load %1266 : !llvm.ptr -> i64
%1268 = arith.remsi %1265, %1267 : i64
%1269 = llvm.mlir.addressof @new_val : !llvm.ptr
%1270 = llvm.load %1269 : !llvm.ptr -> !llvm.ptr
%1271 = llvm.load %1237 : !llvm.ptr -> i64
%1272 = llvm.getelementptr %1270[%1271] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1268, %1272 : i64, !llvm.ptr
cf.br ^bb152
^bb151:
%1273 = llvm.mlir.addressof @new_key : !llvm.ptr
%1274 = llvm.load %1273 : !llvm.ptr -> !llvm.ptr
%1275 = llvm.load %1163 : !llvm.ptr -> i64
%1276 = llvm.getelementptr %1274[%1275] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1207, %1276 : i64, !llvm.ptr
%1277 = llvm.mlir.addressof @new_val : !llvm.ptr
%1278 = llvm.load %1277 : !llvm.ptr -> !llvm.ptr
%1279 = llvm.load %1163 : !llvm.ptr -> i64
%1280 = llvm.getelementptr %1278[%1279] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1230, %1280 : i64, !llvm.ptr
%1281 = llvm.load %1163 : !llvm.ptr -> i64
%1282 = arith.constant 1 : i32
%1284 = arith.extsi %1282 : i32 to i64
%1283 = arith.addi %1281, %1284 : i64
llvm.store %1283, %1163 : i64, !llvm.ptr
cf.br ^bb152
^bb152:
%1285 = llvm.load %1180 : !llvm.ptr -> i64
%1286 = arith.constant 1 : i32
%1288 = arith.extsi %1286 : i32 to i64
%1287 = arith.addi %1285, %1288 : i64
llvm.store %1287, %1180 : i64, !llvm.ptr
cf.br ^bb141
^bb143:
%1289 = llvm.load %1173 : !llvm.ptr -> i64
%1290 = arith.constant 1 : i32
%1292 = arith.extsi %1290 : i32 to i64
%1291 = arith.addi %1289, %1292 : i64
llvm.store %1291, %1173 : i64, !llvm.ptr
cf.br ^bb138
^bb140:
%1293 = arith.constant 0 : i32
%1294 = arith.extsi %1293 : i32 to i64
llvm.store %1294, %1138 : i64, !llvm.ptr
%1295 = arith.constant 0 : i32
%1296 = arith.extsi %1295 : i32 to i64
%1297 = llvm.mlir.constant(1 : i64) : i64
%1298 = llvm.alloca %1297 x i64 : (i64) -> !llvm.ptr
llvm.store %1296, %1298 : i64, !llvm.ptr
cf.br ^bb153
^bb153:
%1299 = llvm.load %1298 : !llvm.ptr -> i64
%1300 = llvm.load %1163 : !llvm.ptr -> i64
%1301 = arith.cmpi slt, %1299, %1300 : i64
cf.cond_br %1301, ^bb154, ^bb155
^bb154:
%1303 = llvm.mlir.addressof @new_val : !llvm.ptr
%1304 = llvm.load %1303 : !llvm.ptr -> !llvm.ptr
%1305 = llvm.load %1298 : !llvm.ptr -> i64
%1306 = llvm.getelementptr %1304[%1305] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1302 = llvm.load %1306 : !llvm.ptr -> i64
%1307 = arith.constant 0 : i32
%1309 = arith.extsi %1307 : i32 to i64
%1308 = arith.cmpi ne, %1302, %1309 : i64
cf.cond_br %1308, ^bb156, ^bb157
^bb156:
%1311 = llvm.mlir.addressof @new_key : !llvm.ptr
%1312 = llvm.load %1311 : !llvm.ptr -> !llvm.ptr
%1313 = llvm.load %1298 : !llvm.ptr -> i64
%1314 = llvm.getelementptr %1312[%1313] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1310 = llvm.load %1314 : !llvm.ptr -> i64
%1315 = llvm.mlir.addressof @cur_key : !llvm.ptr
%1316 = llvm.load %1315 : !llvm.ptr -> !llvm.ptr
%1317 = llvm.load %1138 : !llvm.ptr -> i64
%1318 = llvm.getelementptr %1316[%1317] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1310, %1318 : i64, !llvm.ptr
%1320 = llvm.mlir.addressof @new_val : !llvm.ptr
%1321 = llvm.load %1320 : !llvm.ptr -> !llvm.ptr
%1322 = llvm.load %1298 : !llvm.ptr -> i64
%1323 = llvm.getelementptr %1321[%1322] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1319 = llvm.load %1323 : !llvm.ptr -> i64
%1324 = llvm.mlir.addressof @cur_val : !llvm.ptr
%1325 = llvm.load %1324 : !llvm.ptr -> !llvm.ptr
%1326 = llvm.load %1138 : !llvm.ptr -> i64
%1327 = llvm.getelementptr %1325[%1326] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1319, %1327 : i64, !llvm.ptr
%1328 = llvm.load %1138 : !llvm.ptr -> i64
%1329 = arith.constant 1 : i32
%1331 = arith.extsi %1329 : i32 to i64
%1330 = arith.addi %1328, %1331 : i64
llvm.store %1330, %1138 : i64, !llvm.ptr
cf.br ^bb158
^bb157:
cf.br ^bb158
^bb158:
%1332 = llvm.load %1298 : !llvm.ptr -> i64
%1333 = arith.constant 1 : i32
%1335 = arith.extsi %1333 : i32 to i64
%1334 = arith.addi %1332, %1335 : i64
llvm.store %1334, %1298 : i64, !llvm.ptr
cf.br ^bb153
^bb155:
%1336 = llvm.load %1156 : !llvm.ptr -> i64
%1337 = arith.constant 1 : i32
%1339 = arith.extsi %1337 : i32 to i64
%1338 = arith.addi %1336, %1339 : i64
llvm.store %1338, %1156 : i64, !llvm.ptr
cf.br ^bb135
^bb137:
%1340 = arith.constant 0 : i32
%1341 = arith.extsi %1340 : i32 to i64
%1342 = llvm.mlir.constant(1 : i64) : i64
%1343 = llvm.alloca %1342 x i64 : (i64) -> !llvm.ptr
llvm.store %1341, %1343 : i64, !llvm.ptr
%1344 = arith.constant 0 : i32
%1345 = arith.extsi %1344 : i32 to i64
%1346 = llvm.mlir.constant(1 : i64) : i64
%1347 = llvm.alloca %1346 x i64 : (i64) -> !llvm.ptr
llvm.store %1345, %1347 : i64, !llvm.ptr
cf.br ^bb159
^bb159:
%1348 = llvm.load %1347 : !llvm.ptr -> i64
%1349 = llvm.load %1138 : !llvm.ptr -> i64
%1350 = arith.cmpi slt, %1348, %1349 : i64
cf.cond_br %1350, ^bb160, ^bb161
^bb160:
%1352 = llvm.mlir.addressof @cur_key : !llvm.ptr
%1353 = llvm.load %1352 : !llvm.ptr -> !llvm.ptr
%1354 = llvm.load %1347 : !llvm.ptr -> i64
%1355 = llvm.getelementptr %1353[%1354] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1351 = llvm.load %1355 : !llvm.ptr -> i64
%1356 = arith.extsi %1351 : i64 to i128
%1358 = llvm.mlir.addressof @cur_key : !llvm.ptr
%1359 = llvm.load %1358 : !llvm.ptr -> !llvm.ptr
%1360 = llvm.load %1347 : !llvm.ptr -> i64
%1361 = llvm.getelementptr %1359[%1360] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1357 = llvm.load %1361 : !llvm.ptr -> i64
%1362 = arith.extsi %1357 : i64 to i128
%1364 = arith.trunci %1356 : i128 to i64
%1365 = arith.trunci %1362 : i128 to i64
%1363 = arith.muli %1364, %1365 : i64
%1366 = llvm.mlir.addressof @MOD : !llvm.ptr
%1367 = llvm.load %1366 : !llvm.ptr -> i64
%1368 = arith.extsi %1367 : i64 to i128
%1370 = arith.trunci %1368 : i128 to i64
%1369 = arith.remsi %1363, %1370 : i64
%1371 = llvm.load %1343 : !llvm.ptr -> i64
%1372 = arith.extsi %1371 : i64 to i128
%1373 = arith.extsi %1369 : i64 to i128
%1375 = llvm.mlir.addressof @cur_val : !llvm.ptr
%1376 = llvm.load %1375 : !llvm.ptr -> !llvm.ptr
%1377 = llvm.load %1347 : !llvm.ptr -> i64
%1378 = llvm.getelementptr %1376[%1377] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1374 = llvm.load %1378 : !llvm.ptr -> i64
%1379 = arith.extsi %1374 : i64 to i128
%1381 = arith.trunci %1373 : i128 to i64
%1382 = arith.trunci %1379 : i128 to i64
%1380 = arith.muli %1381, %1382 : i64
%1383 = llvm.mlir.addressof @MOD : !llvm.ptr
%1384 = llvm.load %1383 : !llvm.ptr -> i64
%1385 = arith.extsi %1384 : i64 to i128
%1387 = arith.trunci %1385 : i128 to i64
%1386 = arith.remsi %1380, %1387 : i64
%1389 = arith.trunci %1372 : i128 to i64
%1388 = arith.addi %1389, %1386 : i64
%1390 = llvm.mlir.addressof @MOD : !llvm.ptr
%1391 = llvm.load %1390 : !llvm.ptr -> i64
%1392 = arith.extsi %1391 : i64 to i128
%1394 = arith.trunci %1392 : i128 to i64
%1393 = arith.remsi %1388, %1394 : i64
llvm.store %1393, %1343 : i64, !llvm.ptr
%1395 = llvm.load %1347 : !llvm.ptr -> i64
%1396 = arith.constant 1 : i32
%1398 = arith.extsi %1396 : i32 to i64
%1397 = arith.addi %1395, %1398 : i64
llvm.store %1397, %1347 : i64, !llvm.ptr
cf.br ^bb159
^bb161:
%1399 = llvm.load %1002 : !llvm.ptr -> i64
%1400 = arith.extsi %1399 : i64 to i128
%1401 = llvm.load %1343 : !llvm.ptr -> i64
%1402 = arith.extsi %1401 : i64 to i128
%1403 = llvm.mlir.addressof @N : !llvm.ptr
%1404 = llvm.load %1403 : !llvm.ptr -> i64
%1405 = llvm.load %1006 : !llvm.ptr -> i64
%1406 = arith.divsi %1404, %1405 : i64
%1407 = arith.extsi %1406 : i64 to i128
%1409 = arith.trunci %1402 : i128 to i64
%1410 = arith.trunci %1407 : i128 to i64
%1408 = arith.muli %1409, %1410 : i64
%1411 = llvm.mlir.addressof @MOD : !llvm.ptr
%1412 = llvm.load %1411 : !llvm.ptr -> i64
%1413 = arith.extsi %1412 : i64 to i128
%1415 = arith.trunci %1413 : i128 to i64
%1414 = arith.remsi %1408, %1415 : i64
%1417 = arith.trunci %1400 : i128 to i64
%1416 = arith.addi %1417, %1414 : i64
%1418 = llvm.mlir.addressof @MOD : !llvm.ptr
%1419 = llvm.load %1418 : !llvm.ptr -> i64
%1420 = arith.extsi %1419 : i64 to i128
%1422 = arith.trunci %1420 : i128 to i64
%1421 = arith.remsi %1416, %1422 : i64
llvm.store %1421, %1002 : i64, !llvm.ptr
%1423 = llvm.load %1006 : !llvm.ptr -> i64
%1424 = arith.constant 1 : i32
%1426 = arith.extsi %1424 : i32 to i64
%1425 = arith.addi %1423, %1426 : i64
llvm.store %1425, %1006 : i64, !llvm.ptr
cf.br ^bb126
^bb128:
%1427 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1428 = llvm.load %1002 : !llvm.ptr -> i64
%1429 = llvm.call @printf(%1427, %1428) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1431 = llvm.mlir.addressof @spf : !llvm.ptr
%1432 = llvm.load %1431 : !llvm.ptr -> !llvm.ptr
func.call @free(%1432) : (!llvm.ptr) -> ()
%1434 = llvm.mlir.addressof @pi_prime : !llvm.ptr
%1435 = llvm.load %1434 : !llvm.ptr -> !llvm.ptr
func.call @free(%1435) : (!llvm.ptr) -> ()
%1437 = llvm.mlir.addressof @k_prime : !llvm.ptr
%1438 = llvm.load %1437 : !llvm.ptr -> !llvm.ptr
func.call @free(%1438) : (!llvm.ptr) -> ()
%1440 = llvm.mlir.addressof @dc_p : !llvm.ptr
%1441 = llvm.load %1440 : !llvm.ptr -> !llvm.ptr
func.call @free(%1441) : (!llvm.ptr) -> ()
%1443 = llvm.mlir.addressof @dc_e : !llvm.ptr
%1444 = llvm.load %1443 : !llvm.ptr -> !llvm.ptr
func.call @free(%1444) : (!llvm.ptr) -> ()
%1446 = llvm.mlir.addressof @dc_ne : !llvm.ptr
%1447 = llvm.load %1446 : !llvm.ptr -> !llvm.ptr
func.call @free(%1447) : (!llvm.ptr) -> ()
%1449 = llvm.mlir.addressof @dc_period : !llvm.ptr
%1450 = llvm.load %1449 : !llvm.ptr -> !llvm.ptr
func.call @free(%1450) : (!llvm.ptr) -> ()
%1452 = llvm.mlir.addressof @dc_count : !llvm.ptr
%1453 = llvm.load %1452 : !llvm.ptr -> !llvm.ptr
func.call @free(%1453) : (!llvm.ptr) -> ()
%1455 = llvm.mlir.addressof @cur_key : !llvm.ptr
%1456 = llvm.load %1455 : !llvm.ptr -> !llvm.ptr
func.call @free(%1456) : (!llvm.ptr) -> ()
%1458 = llvm.mlir.addressof @cur_val : !llvm.ptr
%1459 = llvm.load %1458 : !llvm.ptr -> !llvm.ptr
func.call @free(%1459) : (!llvm.ptr) -> ()
%1461 = llvm.mlir.addressof @new_key : !llvm.ptr
%1462 = llvm.load %1461 : !llvm.ptr -> !llvm.ptr
func.call @free(%1462) : (!llvm.ptr) -> ()
%1464 = llvm.mlir.addressof @new_val : !llvm.ptr
%1465 = llvm.load %1464 : !llvm.ptr -> !llvm.ptr
func.call @free(%1465) : (!llvm.ptr) -> ()
%1466 = arith.constant 0 : i32
func.return %1466 : i32
}
}