← All problems Problem 955
Index of the 70th triangular term in the sequence. Uses i128 arithmetic, Miller-Rabin, Pollard's rho factorization.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^3)O(sqrt(n))Space complexity O(1)O(1)Approach Flow solution Trial division or Pollard rho Verdict Suboptimal
Flow source
# Project Euler 955: Finding Triangles
# Index of the 70th triangular term in the sequence.
# Uses i128 arithmetic, Miller-Rabin, Pollard's rho factorization.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
# gcd for i128
function gcd128(a0: i128, b0: i128) -> i128 {
let mut a: i128 = a0
if a < 0 { a = 0 - a }
let mut b: i128 = b0
if b < 0 { b = 0 - b }
while b != 0 {
let t: i128 = a % b
a = b
b = t
}
return a
}
# (a * b) mod n for i128, overflow-safe
function mulmod128(a0: i128, b0: i128, n: i128) -> i128 {
# If both fit in 62 bits, direct multiply fits in i128
if a0 >= 0 - ((1 as i128) << 62) && a0 < ((1 as i128) << 62) &&
b0 >= 0 - ((1 as i128) << 62) && b0 < ((1 as i128) << 62) {
return a0 * b0 % n
}
# Binary multiplication, overflow-safe
let mut a: i128 = a0 % n
if a < 0 { a = a + n }
let mut b: i128 = b0 % n
if b < 0 { b = b + n }
let mut result: i128 = 0
while b > 0 {
if (b & 1) != 0 {
if result >= n - a {
result = result - (n - a)
} else {
result = result + a
}
}
if a >= n - a {
a = a - (n - a)
} else {
a = a + a
}
b = b >> 1
}
return result
}
function powmod128(base0: i128, exp0: i128, n: i128) -> i128 {
let mut r: i128 = 1 % n
let mut b: i128 = base0 % n
if b < 0 { b = b + n }
let mut exp: i128 = exp0
while exp > 0 {
if (exp & 1) != 0 {
r = mulmod128(r, b, n)
}
b = mulmod128(b, b, n)
exp = exp >> 1
}
return r
}
function is_prime128(n: i128) -> bool {
if n < 2 { return false }
let small: array<i64, 10> = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
let mut i: i64 = 0
while i < 10 {
if n % (small[i] as i128) == 0 { return n == (small[i] as i128) }
i = i + 1
}
let mut d: i128 = n - 1
let mut s: i64 = 0
while (d & 1) == 0 {
s = s + 1
d = d >> 1
}
let bases: array<i64, 7> = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
let mut bi: i64 = 0
while bi < 7 {
let a: i128 = (bases[bi] as i128) % n
if a == 0 {
bi = bi + 1
continue
}
let mut x: i128 = powmod128(a, d, n)
if x == 1 || x == n - 1 {
bi = bi + 1
continue
}
let mut composite: bool = true
let mut j: i64 = 0
while j < s - 1 {
x = mulmod128(x, x, n)
if x == n - 1 {
composite = false
break
}
j = j + 1
}
if composite { return false }
bi = bi + 1
}
return true
}
let mut rng_state: i64 = 123456789
function rng_next(modv: i64) -> i64 {
rng_state = rng_state * 6364136223846793005 + 1
let mut v: i64 = rng_state
if v < 0 { v = 0 - v }
return v % modv
}
function pollard_rho(n: i128) -> i128 {
if n % 2 == 0 { return 2 }
if n % 3 == 0 { return 3 }
while true {
let mut x: i128 = (2 + rng_next(1000000007)) as i128 % n
let mut y: i128 = x
let c: i128 = (1 + rng_next(1000000007)) as i128 % n
let mut d: i128 = 1
while d == 1 {
x = mulmod128(x, x, n)
x = x + c
if x >= n { x = x - n }
y = mulmod128(y, y, n)
y = y + c
if y >= n { y = y - n }
y = mulmod128(y, y, n)
y = y + c
if y >= n { y = y - n }
let mut diff: i128 = x - y
if diff < 0 { diff = 0 - diff }
d = gcd128(diff, n)
}
if d != n { return d }
}
return 0
}
# Factorization storage
let mut fac_p: ptr<i128> = null
let mut fac_e: ptr<i64> = null
let mut fac_count: i64 = 0
function factor_rec(n: i128) -> void {
if n == 1 { return }
if is_prime128(n) {
let mut i: i64 = 0
while i < fac_count {
if fac_p[i] == n {
fac_e[i] = fac_e[i] + 1
return
}
i = i + 1
}
fac_p[fac_count] = n
fac_e[fac_count] = 1
fac_count = fac_count + 1
return
}
let d: i128 = pollard_rho(n)
factor_rec(d)
factor_rec(n / d)
}
# Heapsort for i128
function sift_down(arr: ptr<i128>, start: i64, end: i64) -> void {
let mut root: i64 = start
while 2 * root + 1 <= end {
let mut child: i64 = 2 * root + 1
if child + 1 <= end && arr[child] < arr[child + 1] {
child = child + 1
}
if arr[root] < arr[child] {
let tmp: i128 = arr[root]
arr[root] = arr[child]
arr[child] = tmp
root = child
} else {
break
}
}
}
function heapsort_i128(arr: ptr<i128>, n: i64) -> void {
if n <= 1 { return }
let mut start: i64 = n / 2 - 1
while start >= 0 {
sift_down(arr, start, n - 1)
start = start - 1
}
let mut end: i64 = n - 1
while end > 0 {
let tmp: i128 = arr[0]
arr[0] = arr[end]
arr[end] = tmp
end = end - 1
sift_down(arr, 0, end)
}
}
let mut g_divisors: ptr<i128> = null
let mut g_nd: i64 = 0
function all_divisors(n: i128) -> void {
fac_p = malloc(64 * 16)
fac_e = malloc(64 * 8)
fac_count = 0
factor_rec(n)
g_divisors = malloc(50000 * 16)
let mut nd: i64 = 1
g_divisors[0] = 1
let mut i: i64 = 0
while i < fac_count {
let old: i64 = nd
let mut pe: i128 = 1
let mut e: i64 = 0
while e < fac_e[i] {
pe = pe * fac_p[i]
let mut j: i64 = 0
while j < old {
g_divisors[nd] = g_divisors[j] * pe
nd = nd + 1
j = j + 1
}
e = e + 1
}
i = i + 1
}
heapsort_i128(g_divisors, nd)
g_nd = nd
free(fac_p)
free(fac_e)
}
let mut out_k: i128 = 0
let mut out_a: i128 = 0
function next_triangle_jump(a_tri: i128) -> void {
let M: i128 = 2 * a_tri
all_divisors(M)
let mut i: i64 = 0
while i < g_nd {
let x: i128 = g_divisors[i]
let y: i128 = M / x
if (x - y) & 1 != 0 {
let k: i128 = (x - y - 1) / 2
if k > 0 {
out_k = k
out_a = a_tri + k * (k + 1) / 2
free(g_divisors)
return
}
}
i = i + 1
}
free(g_divisors)
out_k = 0 - 1
out_a = 0 - 1
}
function main() -> i32 {
let mut n: i128 = 0
let mut a: i128 = 3
let mut i: i64 = 0
while i < 69 {
next_triangle_jump(a)
n = n + out_k
a = out_a
i = i + 1
}
printf("%lld\n", n as i64)
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; }
__int128 gcd128_i128_i128(__int128 a0, __int128 b0);
__int128 mulmod128_i128_i128_i128(__int128 a0, __int128 b0, __int128 n);
__int128 powmod128_i128_i128_i128(__int128 base0, __int128 exp0, __int128 n);
bool is_prime128_i128(__int128 n);
int64_t rng_next_i64(int64_t modv);
__int128 pollard_rho_i128(__int128 n);
void factor_rec_i128(__int128 n);
void sift_down_ptr_i128_i64_i64(__int128* arr, int64_t start, int64_t end);
void heapsort_i128_ptr_i128_i64(__int128* arr, int64_t n);
void all_divisors_i128(__int128 n);
void next_triangle_jump_i128(__int128 a_tri);
int32_t main(void);
/* Module statics */
static int64_t rng_state = 123456789;
static __int128* fac_p = NULL;
static int64_t* fac_e = NULL;
static int64_t fac_count = 0;
static __int128* g_divisors = NULL;
static int64_t g_nd = 0;
static __int128 out_k = 0;
static __int128 out_a = 0;
__int128 gcd128_i128_i128(__int128 a0, __int128 b0) {
__int128 a = a0;
if (a < 0) {
a = (0 - a);
}
__int128 b = b0;
if (b < 0) {
b = (0 - b);
}
while (b != 0) {
__int128 t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
__int128 mulmod128_i128_i128_i128(__int128 a0, __int128 b0, __int128 n) {
if ((((a0 >= (0 - FLOW_CHECKED_SHL((((__int128)(1))), (62))) && a0 < FLOW_CHECKED_SHL((((__int128)(1))), (62))) && b0 >= (0 - FLOW_CHECKED_SHL((((__int128)(1))), (62)))) && b0 < FLOW_CHECKED_SHL((((__int128)(1))), (62)))) {
return FLOW_CHECKED_MOD(((a0 * b0)), (n));
}
__int128 a = FLOW_CHECKED_MOD((a0), (n));
if (a < 0) {
a = (a + n);
}
__int128 b = FLOW_CHECKED_MOD((b0), (n));
if (b < 0) {
b = (b + n);
}
__int128 result = 0;
while (b > 0) {
if ((b & 1) != 0) {
if (result >= (n - a)) {
result = (result - (n - a));
} else {
result = (result + a);
}
}
if (a >= (n - a)) {
a = (a - (n - a));
} else {
a = (a + a);
}
b = FLOW_CHECKED_SHR((b), (1));
}
return result;
}
__int128 powmod128_i128_i128_i128(__int128 base0, __int128 exp0, __int128 n) {
__int128 r = FLOW_CHECKED_MOD((1), (n));
__int128 b = FLOW_CHECKED_MOD((base0), (n));
if (b < 0) {
b = (b + n);
}
__int128 exp = exp0;
while (exp > 0) {
if ((exp & 1) != 0) {
r = mulmod128_i128_i128_i128(r, b, n);
}
b = mulmod128_i128_i128_i128(b, b, n);
exp = FLOW_CHECKED_SHR((exp), (1));
}
return r;
}
bool is_prime128_i128(__int128 n) {
if (n < 2) {
return 0;
}
int64_t small[10] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
int64_t i = 0;
while (i < 10) {
if (FLOW_CHECKED_MOD((n), (((__int128)((((unsigned)(i) < 10) ? small[i] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(i), 10), flow_fault_handler("array index out of bounds"), small[0])))))) == 0) {
return n == ((__int128)((((unsigned)(i) < 10) ? small[i] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(i), 10), flow_fault_handler("array index out of bounds"), small[0]))));
}
i = (i + 1);
}
__int128 d = (n - 1);
int64_t s = 0;
while ((d & 1) == 0) {
s = (s + 1);
d = FLOW_CHECKED_SHR((d), (1));
}
int64_t bases[7] = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
int64_t bi = 0;
while (bi < 7) {
__int128 a = FLOW_CHECKED_MOD((((__int128)((((unsigned)(bi) < 7) ? bases[bi] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(bi), 7), flow_fault_handler("array index out of bounds"), bases[0]))))), (n));
if (a == 0) {
bi = (bi + 1);
continue;
}
__int128 x = powmod128_i128_i128_i128(a, d, n);
if ((x == 1 || x == (n - 1))) {
bi = (bi + 1);
continue;
}
bool composite = 1;
int64_t j = 0;
while (j < (s - 1)) {
x = mulmod128_i128_i128_i128(x, x, n);
if (x == (n - 1)) {
composite = 0;
break;
}
j = (j + 1);
}
if (composite) {
return 0;
}
bi = (bi + 1);
}
return 1;
}
int64_t rng_next_i64(int64_t modv) {
rng_state = ((rng_state * 6364136223846793005) + 1);
int64_t v = rng_state;
if (v < 0) {
v = (0 - v);
}
return FLOW_CHECKED_MOD((v), (modv));
}
__int128 pollard_rho_i128(__int128 n) {
if (FLOW_CHECKED_MOD((n), (2)) == 0) {
return 2;
}
if (FLOW_CHECKED_MOD((n), (3)) == 0) {
return 3;
}
while (1) {
__int128 x = FLOW_CHECKED_MOD((((__int128)((2 + rng_next_i64(1000000007))))), (n));
__int128 y = x;
__int128 c = FLOW_CHECKED_MOD((((__int128)((1 + rng_next_i64(1000000007))))), (n));
__int128 d = 1;
while (d == 1) {
x = mulmod128_i128_i128_i128(x, x, n);
x = (x + c);
if (x >= n) {
x = (x - n);
}
y = mulmod128_i128_i128_i128(y, y, n);
y = (y + c);
if (y >= n) {
y = (y - n);
}
y = mulmod128_i128_i128_i128(y, y, n);
y = (y + c);
if (y >= n) {
y = (y - n);
}
__int128 diff = (x - y);
if (diff < 0) {
diff = (0 - diff);
}
d = gcd128_i128_i128(diff, n);
}
if (d != n) {
return d;
}
}
return 0;
}
void factor_rec_i128(__int128 n) {
if (n == 1) {
return;
}
if (is_prime128_i128(n)) {
int64_t i = 0;
while (i < fac_count) {
if (fac_p[i] == n) {
fac_e[i] = (fac_e[i] + 1);
return;
}
i = (i + 1);
}
fac_p[fac_count] = n;
fac_e[fac_count] = 1;
fac_count = (fac_count + 1);
return;
}
__int128 d = pollard_rho_i128(n);
factor_rec_i128(d);
factor_rec_i128(FLOW_CHECKED_DIV((n), (d)));
}
void sift_down_ptr_i128_i64_i64(__int128* arr, int64_t start, int64_t end) {
int64_t root = start;
while (((2 * root) + 1) <= end) {
int64_t child = ((2 * root) + 1);
if (((child + 1) <= end && arr[child] < arr[(child + 1)])) {
child = (child + 1);
}
if (arr[root] < arr[child]) {
__int128 tmp = arr[root];
arr[root] = arr[child];
arr[child] = tmp;
root = child;
} else {
break;
}
}
}
void heapsort_i128_ptr_i128_i64(__int128* arr, int64_t n) {
if (n <= 1) {
return;
}
int64_t start = (FLOW_CHECKED_DIV((n), (2)) - 1);
while (start >= 0) {
sift_down_ptr_i128_i64_i64(arr, start, (n - 1));
start = (start - 1);
}
int64_t end = (n - 1);
while (end > 0) {
__int128 tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
end = (end - 1);
sift_down_ptr_i128_i64_i64(arr, 0, end);
}
}
void all_divisors_i128(__int128 n) {
fac_p = malloc((64 * 16));
fac_e = malloc((64 * 8));
fac_count = 0;
factor_rec_i128(n);
g_divisors = malloc((50000 * 16));
int64_t nd = 1;
g_divisors[0] = 1;
int64_t i = 0;
while (i < fac_count) {
int64_t old = nd;
__int128 pe = 1;
int64_t e = 0;
while (e < fac_e[i]) {
pe = (pe * fac_p[i]);
int64_t j = 0;
while (j < old) {
g_divisors[nd] = (g_divisors[j] * pe);
nd = (nd + 1);
j = (j + 1);
}
e = (e + 1);
}
i = (i + 1);
}
heapsort_i128_ptr_i128_i64(g_divisors, nd);
g_nd = nd;
free(fac_p);
free(fac_e);
}
void next_triangle_jump_i128(__int128 a_tri) {
__int128 M = (2 * a_tri);
all_divisors_i128(M);
int64_t i = 0;
while (i < g_nd) {
__int128 x = g_divisors[i];
__int128 y = FLOW_CHECKED_DIV((M), (x));
if (((x - y) & 1 != 0)) {
__int128 k = FLOW_CHECKED_DIV((((x - y) - 1)), (2));
if (k > 0) {
out_k = k;
out_a = (a_tri + FLOW_CHECKED_DIV(((k * (k + 1))), (2)));
free(g_divisors);
return;
}
}
i = (i + 1);
}
free(g_divisors);
out_k = (0 - 1);
out_a = (0 - 1);
}
int32_t main(void) {
__int128 n = 0;
__int128 a = 3;
int64_t i = 0;
while (i < 69) {
next_triangle_jump_i128(a);
n = (n + out_k);
a = out_a;
i = (i + 1);
}
printf("%lld\n", ((int64_t)(n)));
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @malloc(i64) -> !llvm.ptr
func.func @gcd128(%arg0: i128, %arg1: i128) -> i128 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i128 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i128, !llvm.ptr
%2 = llvm.load %1 : !llvm.ptr -> i128
%3 = arith.constant 0 : i32
%5 = arith.trunci %2 : i128 to i64
%6 = arith.extsi %3 : i32 to i64
%4 = arith.cmpi slt, %5, %6 : i64
cf.cond_br %4, ^bb0, ^bb1
^bb0:
%7 = arith.constant 0 : i32
%8 = llvm.load %1 : !llvm.ptr -> i128
%10 = arith.extsi %7 : i32 to i64
%11 = arith.trunci %8 : i128 to i64
%9 = arith.subi %10, %11 : i64
%12 = arith.extsi %9 : i64 to i128
llvm.store %12, %1 : i128, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%13 = llvm.mlir.constant(1 : i64) : i64
%14 = llvm.alloca %13 x i128 : (i64) -> !llvm.ptr
llvm.store %arg1, %14 : i128, !llvm.ptr
%15 = llvm.load %14 : !llvm.ptr -> i128
%16 = arith.constant 0 : i32
%18 = arith.trunci %15 : i128 to i64
%19 = arith.extsi %16 : i32 to i64
%17 = arith.cmpi slt, %18, %19 : i64
cf.cond_br %17, ^bb3, ^bb4
^bb3:
%20 = arith.constant 0 : i32
%21 = llvm.load %14 : !llvm.ptr -> i128
%23 = arith.extsi %20 : i32 to i64
%24 = arith.trunci %21 : i128 to i64
%22 = arith.subi %23, %24 : i64
%25 = arith.extsi %22 : i64 to i128
llvm.store %25, %14 : i128, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
cf.br ^bb6
^bb6:
%26 = llvm.load %14 : !llvm.ptr -> i128
%27 = arith.constant 0 : i32
%29 = arith.trunci %26 : i128 to i64
%30 = arith.extsi %27 : i32 to i64
%28 = arith.cmpi ne, %29, %30 : i64
cf.cond_br %28, ^bb7, ^bb8
^bb7:
%31 = llvm.load %1 : !llvm.ptr -> i128
%32 = llvm.load %14 : !llvm.ptr -> i128
%34 = arith.trunci %31 : i128 to i64
%35 = arith.trunci %32 : i128 to i64
%33 = arith.remsi %34, %35 : i64
%36 = arith.extsi %33 : i64 to i128
%37 = llvm.load %14 : !llvm.ptr -> i128
llvm.store %37, %1 : i128, !llvm.ptr
llvm.store %36, %14 : i128, !llvm.ptr
cf.br ^bb6
^bb8:
%38 = llvm.load %1 : !llvm.ptr -> i128
func.return %38 : i128
}
func.func @mulmod128(%arg0: i128, %arg1: i128, %arg2: i128) -> i128 {
%39 = arith.constant 0 : i32
%40 = arith.constant 1 : i32
%41 = arith.extsi %40 : i32 to i128
%42 = arith.constant 62 : i32
%44 = arith.trunci %41 : i128 to i64
%45 = arith.extsi %42 : i32 to i64
%43 = arith.shli %44, %45 : i64
%47 = arith.extsi %39 : i32 to i64
%46 = arith.subi %47, %43 : i64
%49 = arith.trunci %arg0 : i128 to i64
%48 = arith.cmpi sge, %49, %46 : i64
%50 = scf.if %48 -> (i1) {
%51 = arith.constant 1 : i32
%52 = arith.extsi %51 : i32 to i128
%53 = arith.constant 62 : i32
%55 = arith.trunci %52 : i128 to i64
%56 = arith.extsi %53 : i32 to i64
%54 = arith.shli %55, %56 : i64
%58 = arith.trunci %arg0 : i128 to i64
%57 = arith.cmpi slt, %58, %54 : i64
scf.yield %57 : i1
} else {
%59 = arith.constant false
scf.yield %59 : i1
}
%60 = scf.if %50 -> (i1) {
%61 = arith.constant 0 : i32
%62 = arith.constant 1 : i32
%63 = arith.extsi %62 : i32 to i128
%64 = arith.constant 62 : i32
%66 = arith.trunci %63 : i128 to i64
%67 = arith.extsi %64 : i32 to i64
%65 = arith.shli %66, %67 : i64
%69 = arith.extsi %61 : i32 to i64
%68 = arith.subi %69, %65 : i64
%71 = arith.trunci %arg1 : i128 to i64
%70 = arith.cmpi sge, %71, %68 : i64
scf.yield %70 : i1
} else {
%72 = arith.constant false
scf.yield %72 : i1
}
%73 = scf.if %60 -> (i1) {
%74 = arith.constant 1 : i32
%75 = arith.extsi %74 : i32 to i128
%76 = arith.constant 62 : i32
%78 = arith.trunci %75 : i128 to i64
%79 = arith.extsi %76 : i32 to i64
%77 = arith.shli %78, %79 : i64
%81 = arith.trunci %arg1 : i128 to i64
%80 = arith.cmpi slt, %81, %77 : i64
scf.yield %80 : i1
} else {
%82 = arith.constant false
scf.yield %82 : i1
}
cf.cond_br %73, ^bb9, ^bb10
^bb9:
%84 = arith.trunci %arg0 : i128 to i64
%85 = arith.trunci %arg1 : i128 to i64
%83 = arith.muli %84, %85 : i64
%87 = arith.trunci %arg2 : i128 to i64
%86 = arith.remsi %83, %87 : i64
%88 = arith.extsi %86 : i64 to i128
func.return %88 : i128
^bb10:
cf.br ^bb11
^bb11:
%90 = arith.trunci %arg0 : i128 to i64
%91 = arith.trunci %arg2 : i128 to i64
%89 = arith.remsi %90, %91 : i64
%92 = arith.extsi %89 : i64 to i128
%93 = llvm.mlir.constant(1 : i64) : i64
%94 = llvm.alloca %93 x i128 : (i64) -> !llvm.ptr
llvm.store %92, %94 : i128, !llvm.ptr
%95 = llvm.load %94 : !llvm.ptr -> i128
%96 = arith.constant 0 : i32
%98 = arith.trunci %95 : i128 to i64
%99 = arith.extsi %96 : i32 to i64
%97 = arith.cmpi slt, %98, %99 : i64
cf.cond_br %97, ^bb12, ^bb13
^bb12:
%100 = llvm.load %94 : !llvm.ptr -> i128
%102 = arith.trunci %100 : i128 to i64
%103 = arith.trunci %arg2 : i128 to i64
%101 = arith.addi %102, %103 : i64
%104 = arith.extsi %101 : i64 to i128
llvm.store %104, %94 : i128, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%106 = arith.trunci %arg1 : i128 to i64
%107 = arith.trunci %arg2 : i128 to i64
%105 = arith.remsi %106, %107 : i64
%108 = arith.extsi %105 : i64 to i128
%109 = llvm.mlir.constant(1 : i64) : i64
%110 = llvm.alloca %109 x i128 : (i64) -> !llvm.ptr
llvm.store %108, %110 : i128, !llvm.ptr
%111 = llvm.load %110 : !llvm.ptr -> i128
%112 = arith.constant 0 : i32
%114 = arith.trunci %111 : i128 to i64
%115 = arith.extsi %112 : i32 to i64
%113 = arith.cmpi slt, %114, %115 : i64
cf.cond_br %113, ^bb15, ^bb16
^bb15:
%116 = llvm.load %110 : !llvm.ptr -> i128
%118 = arith.trunci %116 : i128 to i64
%119 = arith.trunci %arg2 : i128 to i64
%117 = arith.addi %118, %119 : i64
%120 = arith.extsi %117 : i64 to i128
llvm.store %120, %110 : i128, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%121 = arith.constant 0 : i32
%122 = arith.extsi %121 : i32 to i128
%123 = llvm.mlir.constant(1 : i64) : i64
%124 = llvm.alloca %123 x i128 : (i64) -> !llvm.ptr
llvm.store %122, %124 : i128, !llvm.ptr
cf.br ^bb18
^bb18:
%125 = llvm.load %110 : !llvm.ptr -> i128
%126 = arith.constant 0 : i32
%128 = arith.trunci %125 : i128 to i64
%129 = arith.extsi %126 : i32 to i64
%127 = arith.cmpi sgt, %128, %129 : i64
cf.cond_br %127, ^bb19, ^bb20
^bb19:
%130 = llvm.load %110 : !llvm.ptr -> i128
%131 = arith.constant 1 : i32
%133 = arith.trunci %130 : i128 to i64
%134 = arith.extsi %131 : i32 to i64
%132 = arith.andi %133, %134 : i64
%135 = arith.constant 0 : i32
%137 = arith.extsi %135 : i32 to i64
%136 = arith.cmpi ne, %132, %137 : i64
cf.cond_br %136, ^bb21, ^bb22
^bb21:
%138 = llvm.load %124 : !llvm.ptr -> i128
%139 = llvm.load %94 : !llvm.ptr -> i128
%141 = arith.trunci %arg2 : i128 to i64
%142 = arith.trunci %139 : i128 to i64
%140 = arith.subi %141, %142 : i64
%144 = arith.trunci %138 : i128 to i64
%143 = arith.cmpi sge, %144, %140 : i64
cf.cond_br %143, ^bb24, ^bb25
^bb24:
%145 = llvm.load %124 : !llvm.ptr -> i128
%146 = llvm.load %94 : !llvm.ptr -> i128
%148 = arith.trunci %arg2 : i128 to i64
%149 = arith.trunci %146 : i128 to i64
%147 = arith.subi %148, %149 : i64
%151 = arith.trunci %145 : i128 to i64
%150 = arith.subi %151, %147 : i64
%152 = arith.extsi %150 : i64 to i128
llvm.store %152, %124 : i128, !llvm.ptr
cf.br ^bb26
^bb25:
%153 = llvm.load %124 : !llvm.ptr -> i128
%154 = llvm.load %94 : !llvm.ptr -> i128
%156 = arith.trunci %153 : i128 to i64
%157 = arith.trunci %154 : i128 to i64
%155 = arith.addi %156, %157 : i64
%158 = arith.extsi %155 : i64 to i128
llvm.store %158, %124 : i128, !llvm.ptr
cf.br ^bb26
^bb26:
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%159 = llvm.load %94 : !llvm.ptr -> i128
%160 = llvm.load %94 : !llvm.ptr -> i128
%162 = arith.trunci %arg2 : i128 to i64
%163 = arith.trunci %160 : i128 to i64
%161 = arith.subi %162, %163 : i64
%165 = arith.trunci %159 : i128 to i64
%164 = arith.cmpi sge, %165, %161 : i64
cf.cond_br %164, ^bb27, ^bb28
^bb27:
%166 = llvm.load %94 : !llvm.ptr -> i128
%167 = llvm.load %94 : !llvm.ptr -> i128
%169 = arith.trunci %arg2 : i128 to i64
%170 = arith.trunci %167 : i128 to i64
%168 = arith.subi %169, %170 : i64
%172 = arith.trunci %166 : i128 to i64
%171 = arith.subi %172, %168 : i64
%173 = arith.extsi %171 : i64 to i128
llvm.store %173, %94 : i128, !llvm.ptr
cf.br ^bb29
^bb28:
%174 = llvm.load %94 : !llvm.ptr -> i128
%175 = llvm.load %94 : !llvm.ptr -> i128
%177 = arith.trunci %174 : i128 to i64
%178 = arith.trunci %175 : i128 to i64
%176 = arith.addi %177, %178 : i64
%179 = arith.extsi %176 : i64 to i128
llvm.store %179, %94 : i128, !llvm.ptr
cf.br ^bb29
^bb29:
%180 = llvm.load %110 : !llvm.ptr -> i128
%181 = arith.constant 1 : i32
%183 = arith.trunci %180 : i128 to i64
%184 = arith.extsi %181 : i32 to i64
%182 = arith.shrsi %183, %184 : i64
%185 = arith.extsi %182 : i64 to i128
llvm.store %185, %110 : i128, !llvm.ptr
cf.br ^bb18
^bb20:
%186 = llvm.load %124 : !llvm.ptr -> i128
func.return %186 : i128
}
func.func @powmod128(%arg0: i128, %arg1: i128, %arg2: i128) -> i128 {
%187 = arith.constant 1 : i32
%189 = arith.extsi %187 : i32 to i64
%190 = arith.trunci %arg2 : i128 to i64
%188 = arith.remsi %189, %190 : i64
%191 = arith.extsi %188 : i64 to i128
%192 = llvm.mlir.constant(1 : i64) : i64
%193 = llvm.alloca %192 x i128 : (i64) -> !llvm.ptr
llvm.store %191, %193 : i128, !llvm.ptr
%195 = arith.trunci %arg0 : i128 to i64
%196 = arith.trunci %arg2 : i128 to i64
%194 = arith.remsi %195, %196 : i64
%197 = arith.extsi %194 : i64 to i128
%198 = llvm.mlir.constant(1 : i64) : i64
%199 = llvm.alloca %198 x i128 : (i64) -> !llvm.ptr
llvm.store %197, %199 : i128, !llvm.ptr
%200 = llvm.load %199 : !llvm.ptr -> i128
%201 = arith.constant 0 : i32
%203 = arith.trunci %200 : i128 to i64
%204 = arith.extsi %201 : i32 to i64
%202 = arith.cmpi slt, %203, %204 : i64
cf.cond_br %202, ^bb30, ^bb31
^bb30:
%205 = llvm.load %199 : !llvm.ptr -> i128
%207 = arith.trunci %205 : i128 to i64
%208 = arith.trunci %arg2 : i128 to i64
%206 = arith.addi %207, %208 : i64
%209 = arith.extsi %206 : i64 to i128
llvm.store %209, %199 : i128, !llvm.ptr
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%210 = llvm.mlir.constant(1 : i64) : i64
%211 = llvm.alloca %210 x i128 : (i64) -> !llvm.ptr
llvm.store %arg1, %211 : i128, !llvm.ptr
cf.br ^bb33
^bb33:
%212 = llvm.load %211 : !llvm.ptr -> i128
%213 = arith.constant 0 : i32
%215 = arith.trunci %212 : i128 to i64
%216 = arith.extsi %213 : i32 to i64
%214 = arith.cmpi sgt, %215, %216 : i64
cf.cond_br %214, ^bb34, ^bb35
^bb34:
%217 = llvm.load %211 : !llvm.ptr -> i128
%218 = arith.constant 1 : i32
%220 = arith.trunci %217 : i128 to i64
%221 = arith.extsi %218 : i32 to i64
%219 = arith.andi %220, %221 : i64
%222 = arith.constant 0 : i32
%224 = arith.extsi %222 : i32 to i64
%223 = arith.cmpi ne, %219, %224 : i64
cf.cond_br %223, ^bb36, ^bb37
^bb36:
%226 = llvm.load %193 : !llvm.ptr -> i128
%227 = llvm.load %199 : !llvm.ptr -> i128
%225 = func.call @mulmod128(%226, %227, %arg2) : (i128, i128, i128) -> i128
llvm.store %225, %193 : i128, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%229 = llvm.load %199 : !llvm.ptr -> i128
%230 = llvm.load %199 : !llvm.ptr -> i128
%228 = func.call @mulmod128(%229, %230, %arg2) : (i128, i128, i128) -> i128
llvm.store %228, %199 : i128, !llvm.ptr
%231 = llvm.load %211 : !llvm.ptr -> i128
%232 = arith.constant 1 : i32
%234 = arith.trunci %231 : i128 to i64
%235 = arith.extsi %232 : i32 to i64
%233 = arith.shrsi %234, %235 : i64
%236 = arith.extsi %233 : i64 to i128
llvm.store %236, %211 : i128, !llvm.ptr
cf.br ^bb33
^bb35:
%237 = llvm.load %193 : !llvm.ptr -> i128
func.return %237 : i128
}
func.func @is_prime128(%arg0: i128) -> i1 {
%238 = arith.constant 2 : i32
%240 = arith.trunci %arg0 : i128 to i64
%241 = arith.extsi %238 : i32 to i64
%239 = arith.cmpi slt, %240, %241 : i64
cf.cond_br %239, ^bb39, ^bb40
^bb39:
%242 = arith.constant 0 : i1
func.return %242 : i1
^bb40:
cf.br ^bb41
^bb41:
%244 = arith.constant 2 : i32
%245 = arith.constant 3 : i32
%246 = arith.constant 5 : i32
%247 = arith.constant 7 : i32
%248 = arith.constant 11 : i32
%249 = arith.constant 13 : i32
%250 = arith.constant 17 : i32
%251 = arith.constant 19 : i32
%252 = arith.constant 23 : i32
%253 = arith.constant 29 : i32
%254 = llvm.mlir.constant(1 : i64) : i64
%255 = llvm.alloca %254 x !llvm.array<10 x i64> : (i64) -> !llvm.ptr
%256 = llvm.mlir.zero : !llvm.array<10 x i64>
llvm.store %256, %255 : !llvm.array<10 x i64>, !llvm.ptr
%257 = arith.extsi %244 : i32 to i64
%258 = arith.extsi %245 : i32 to i64
%259 = arith.extsi %246 : i32 to i64
%260 = arith.extsi %247 : i32 to i64
%261 = arith.extsi %248 : i32 to i64
%262 = arith.extsi %249 : i32 to i64
%263 = arith.extsi %250 : i32 to i64
%264 = arith.extsi %251 : i32 to i64
%265 = arith.extsi %252 : i32 to i64
%266 = arith.extsi %253 : i32 to i64
%267 = llvm.mlir.constant(0 : i64) : i64
%268 = llvm.getelementptr %255[0, %267] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %257, %268 : i64, !llvm.ptr
%269 = llvm.mlir.constant(1 : i64) : i64
%270 = llvm.getelementptr %255[0, %269] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %258, %270 : i64, !llvm.ptr
%271 = llvm.mlir.constant(2 : i64) : i64
%272 = llvm.getelementptr %255[0, %271] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %259, %272 : i64, !llvm.ptr
%273 = llvm.mlir.constant(3 : i64) : i64
%274 = llvm.getelementptr %255[0, %273] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %260, %274 : i64, !llvm.ptr
%275 = llvm.mlir.constant(4 : i64) : i64
%276 = llvm.getelementptr %255[0, %275] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %261, %276 : i64, !llvm.ptr
%277 = llvm.mlir.constant(5 : i64) : i64
%278 = llvm.getelementptr %255[0, %277] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %262, %278 : i64, !llvm.ptr
%279 = llvm.mlir.constant(6 : i64) : i64
%280 = llvm.getelementptr %255[0, %279] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %263, %280 : i64, !llvm.ptr
%281 = llvm.mlir.constant(7 : i64) : i64
%282 = llvm.getelementptr %255[0, %281] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %264, %282 : i64, !llvm.ptr
%283 = llvm.mlir.constant(8 : i64) : i64
%284 = llvm.getelementptr %255[0, %283] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %265, %284 : i64, !llvm.ptr
%285 = llvm.mlir.constant(9 : i64) : i64
%286 = llvm.getelementptr %255[0, %285] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
llvm.store %266, %286 : i64, !llvm.ptr
%287 = arith.constant 0 : i32
%288 = arith.extsi %287 : i32 to i64
%289 = llvm.mlir.constant(1 : i64) : i64
%290 = llvm.alloca %289 x i64 : (i64) -> !llvm.ptr
llvm.store %288, %290 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%291 = llvm.load %290 : !llvm.ptr -> i64
%292 = arith.constant 10 : i32
%294 = arith.extsi %292 : i32 to i64
%293 = arith.cmpi slt, %291, %294 : i64
cf.cond_br %293, ^bb43, ^bb44
^bb43:
%296 = llvm.load %290 : !llvm.ptr -> i64
%297 = llvm.getelementptr %255[0, %296] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
%295 = llvm.load %297 : !llvm.ptr -> i64
%298 = arith.extsi %295 : i64 to i128
%300 = arith.trunci %arg0 : i128 to i64
%301 = arith.trunci %298 : i128 to i64
%299 = arith.remsi %300, %301 : i64
%302 = arith.constant 0 : i32
%304 = arith.extsi %302 : i32 to i64
%303 = arith.cmpi eq, %299, %304 : i64
cf.cond_br %303, ^bb45, ^bb46
^bb45:
%306 = llvm.load %290 : !llvm.ptr -> i64
%307 = llvm.getelementptr %255[0, %306] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<10 x i64>
%305 = llvm.load %307 : !llvm.ptr -> i64
%308 = arith.extsi %305 : i64 to i128
%310 = arith.trunci %arg0 : i128 to i64
%311 = arith.trunci %308 : i128 to i64
%309 = arith.cmpi eq, %310, %311 : i64
func.return %309 : i1
^bb46:
cf.br ^bb47
^bb47:
%312 = llvm.load %290 : !llvm.ptr -> i64
%313 = arith.constant 1 : i32
%315 = arith.extsi %313 : i32 to i64
%314 = arith.addi %312, %315 : i64
llvm.store %314, %290 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%316 = arith.constant 1 : i32
%318 = arith.trunci %arg0 : i128 to i64
%319 = arith.extsi %316 : i32 to i64
%317 = arith.subi %318, %319 : i64
%320 = arith.extsi %317 : i64 to i128
%321 = llvm.mlir.constant(1 : i64) : i64
%322 = llvm.alloca %321 x i128 : (i64) -> !llvm.ptr
llvm.store %320, %322 : i128, !llvm.ptr
%323 = arith.constant 0 : i32
%324 = arith.extsi %323 : i32 to i64
%325 = llvm.mlir.constant(1 : i64) : i64
%326 = llvm.alloca %325 x i64 : (i64) -> !llvm.ptr
llvm.store %324, %326 : i64, !llvm.ptr
cf.br ^bb48
^bb48:
%327 = llvm.load %322 : !llvm.ptr -> i128
%328 = arith.constant 1 : i32
%330 = arith.trunci %327 : i128 to i64
%331 = arith.extsi %328 : i32 to i64
%329 = arith.andi %330, %331 : i64
%332 = arith.constant 0 : i32
%334 = arith.extsi %332 : i32 to i64
%333 = arith.cmpi eq, %329, %334 : i64
cf.cond_br %333, ^bb49, ^bb50
^bb49:
%335 = llvm.load %326 : !llvm.ptr -> i64
%336 = arith.constant 1 : i32
%338 = arith.extsi %336 : i32 to i64
%337 = arith.addi %335, %338 : i64
llvm.store %337, %326 : i64, !llvm.ptr
%339 = llvm.load %322 : !llvm.ptr -> i128
%340 = arith.constant 1 : i32
%342 = arith.trunci %339 : i128 to i64
%343 = arith.extsi %340 : i32 to i64
%341 = arith.shrsi %342, %343 : i64
%344 = arith.extsi %341 : i64 to i128
llvm.store %344, %322 : i128, !llvm.ptr
cf.br ^bb48
^bb50:
%346 = arith.constant 2 : i32
%347 = arith.constant 325 : i32
%348 = arith.constant 9375 : i32
%349 = arith.constant 28178 : i32
%350 = arith.constant 450775 : i32
%351 = arith.constant 9780504 : i32
%352 = arith.constant 1795265022 : i32
%353 = llvm.mlir.constant(1 : i64) : i64
%354 = llvm.alloca %353 x !llvm.array<7 x i64> : (i64) -> !llvm.ptr
%355 = llvm.mlir.zero : !llvm.array<7 x i64>
llvm.store %355, %354 : !llvm.array<7 x i64>, !llvm.ptr
%356 = arith.extsi %346 : i32 to i64
%357 = arith.extsi %347 : i32 to i64
%358 = arith.extsi %348 : i32 to i64
%359 = arith.extsi %349 : i32 to i64
%360 = arith.extsi %350 : i32 to i64
%361 = arith.extsi %351 : i32 to i64
%362 = arith.extsi %352 : i32 to i64
%363 = llvm.mlir.constant(0 : i64) : i64
%364 = llvm.getelementptr %354[0, %363] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %356, %364 : i64, !llvm.ptr
%365 = llvm.mlir.constant(1 : i64) : i64
%366 = llvm.getelementptr %354[0, %365] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %357, %366 : i64, !llvm.ptr
%367 = llvm.mlir.constant(2 : i64) : i64
%368 = llvm.getelementptr %354[0, %367] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %358, %368 : i64, !llvm.ptr
%369 = llvm.mlir.constant(3 : i64) : i64
%370 = llvm.getelementptr %354[0, %369] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %359, %370 : i64, !llvm.ptr
%371 = llvm.mlir.constant(4 : i64) : i64
%372 = llvm.getelementptr %354[0, %371] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %360, %372 : i64, !llvm.ptr
%373 = llvm.mlir.constant(5 : i64) : i64
%374 = llvm.getelementptr %354[0, %373] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %361, %374 : i64, !llvm.ptr
%375 = llvm.mlir.constant(6 : i64) : i64
%376 = llvm.getelementptr %354[0, %375] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
llvm.store %362, %376 : i64, !llvm.ptr
%377 = arith.constant 0 : i32
%378 = arith.extsi %377 : i32 to i64
%379 = llvm.mlir.constant(1 : i64) : i64
%380 = llvm.alloca %379 x i64 : (i64) -> !llvm.ptr
llvm.store %378, %380 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%381 = llvm.load %380 : !llvm.ptr -> i64
%382 = arith.constant 7 : i32
%384 = arith.extsi %382 : i32 to i64
%383 = arith.cmpi slt, %381, %384 : i64
cf.cond_br %383, ^bb52, ^bb53
^bb52:
%386 = llvm.load %380 : !llvm.ptr -> i64
%387 = llvm.getelementptr %354[0, %386] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<7 x i64>
%385 = llvm.load %387 : !llvm.ptr -> i64
%388 = arith.extsi %385 : i64 to i128
%390 = arith.trunci %388 : i128 to i64
%391 = arith.trunci %arg0 : i128 to i64
%389 = arith.remsi %390, %391 : i64
%392 = arith.extsi %389 : i64 to i128
%393 = arith.constant 0 : i32
%395 = arith.trunci %392 : i128 to i64
%396 = arith.extsi %393 : i32 to i64
%394 = arith.cmpi eq, %395, %396 : i64
cf.cond_br %394, ^bb54, ^bb55
^bb54:
%397 = llvm.load %380 : !llvm.ptr -> i64
%398 = arith.constant 1 : i32
%400 = arith.extsi %398 : i32 to i64
%399 = arith.addi %397, %400 : i64
llvm.store %399, %380 : i64, !llvm.ptr
cf.br ^bb51
^bb55:
cf.br ^bb56
^bb56:
%402 = llvm.load %322 : !llvm.ptr -> i128
%401 = func.call @powmod128(%392, %402, %arg0) : (i128, i128, i128) -> i128
%403 = llvm.mlir.constant(1 : i64) : i64
%404 = llvm.alloca %403 x i128 : (i64) -> !llvm.ptr
llvm.store %401, %404 : i128, !llvm.ptr
%405 = llvm.load %404 : !llvm.ptr -> i128
%406 = arith.constant 1 : i32
%408 = arith.trunci %405 : i128 to i64
%409 = arith.extsi %406 : i32 to i64
%407 = arith.cmpi eq, %408, %409 : i64
%410 = scf.if %407 -> (i1) {
%411 = arith.constant true
scf.yield %411 : i1
} else {
%412 = llvm.load %404 : !llvm.ptr -> i128
%413 = arith.constant 1 : i32
%415 = arith.trunci %arg0 : i128 to i64
%416 = arith.extsi %413 : i32 to i64
%414 = arith.subi %415, %416 : i64
%418 = arith.trunci %412 : i128 to i64
%417 = arith.cmpi eq, %418, %414 : i64
scf.yield %417 : i1
}
cf.cond_br %410, ^bb57, ^bb58
^bb57:
%419 = llvm.load %380 : !llvm.ptr -> i64
%420 = arith.constant 1 : i32
%422 = arith.extsi %420 : i32 to i64
%421 = arith.addi %419, %422 : i64
llvm.store %421, %380 : i64, !llvm.ptr
cf.br ^bb51
^bb58:
cf.br ^bb59
^bb59:
%423 = arith.constant 1 : i1
%424 = llvm.mlir.constant(1 : i64) : i64
%425 = llvm.alloca %424 x i1 : (i64) -> !llvm.ptr
llvm.store %423, %425 : i1, !llvm.ptr
%426 = arith.constant 0 : i32
%427 = arith.extsi %426 : i32 to i64
%428 = llvm.mlir.constant(1 : i64) : i64
%429 = llvm.alloca %428 x i64 : (i64) -> !llvm.ptr
llvm.store %427, %429 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%430 = llvm.load %429 : !llvm.ptr -> i64
%431 = llvm.load %326 : !llvm.ptr -> i64
%432 = arith.constant 1 : i32
%434 = arith.extsi %432 : i32 to i64
%433 = arith.subi %431, %434 : i64
%435 = arith.cmpi slt, %430, %433 : i64
cf.cond_br %435, ^bb61, ^bb62
^bb61:
%437 = llvm.load %404 : !llvm.ptr -> i128
%438 = llvm.load %404 : !llvm.ptr -> i128
%436 = func.call @mulmod128(%437, %438, %arg0) : (i128, i128, i128) -> i128
llvm.store %436, %404 : i128, !llvm.ptr
%439 = llvm.load %404 : !llvm.ptr -> i128
%440 = arith.constant 1 : i32
%442 = arith.trunci %arg0 : i128 to i64
%443 = arith.extsi %440 : i32 to i64
%441 = arith.subi %442, %443 : i64
%445 = arith.trunci %439 : i128 to i64
%444 = arith.cmpi eq, %445, %441 : i64
cf.cond_br %444, ^bb63, ^bb64
^bb63:
%446 = arith.constant 0 : i1
llvm.store %446, %425 : i1, !llvm.ptr
cf.br ^bb62
^bb64:
cf.br ^bb65
^bb65:
%447 = llvm.load %429 : !llvm.ptr -> i64
%448 = arith.constant 1 : i32
%450 = arith.extsi %448 : i32 to i64
%449 = arith.addi %447, %450 : i64
llvm.store %449, %429 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
%451 = llvm.load %425 : !llvm.ptr -> i1
cf.cond_br %451, ^bb66, ^bb67
^bb66:
%452 = arith.constant 0 : i1
func.return %452 : i1
^bb67:
cf.br ^bb68
^bb68:
%453 = llvm.load %380 : !llvm.ptr -> i64
%454 = arith.constant 1 : i32
%456 = arith.extsi %454 : i32 to i64
%455 = arith.addi %453, %456 : i64
llvm.store %455, %380 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%457 = arith.constant 1 : i1
func.return %457 : i1
}
// Module static: rng_state
llvm.mlir.global internal @rng_state(123456789 : i64) : i64
func.func @rng_next(%arg0: i64) -> i64 {
%458 = llvm.mlir.addressof @rng_state : !llvm.ptr
%459 = llvm.load %458 : !llvm.ptr -> i64
%460 = arith.constant 6364136219551825709 : i32
%462 = arith.extsi %460 : i32 to i64
%461 = arith.muli %459, %462 : i64
%463 = arith.constant 1 : i32
%465 = arith.extsi %463 : i32 to i64
%464 = arith.addi %461, %465 : i64
%466 = llvm.mlir.addressof @rng_state : !llvm.ptr
llvm.store %464, %466 : i64, !llvm.ptr
%467 = llvm.mlir.addressof @rng_state : !llvm.ptr
%468 = llvm.load %467 : !llvm.ptr -> i64
%469 = llvm.mlir.constant(1 : i64) : i64
%470 = llvm.alloca %469 x i64 : (i64) -> !llvm.ptr
llvm.store %468, %470 : i64, !llvm.ptr
%471 = llvm.load %470 : !llvm.ptr -> i64
%472 = arith.constant 0 : i32
%474 = arith.extsi %472 : i32 to i64
%473 = arith.cmpi slt, %471, %474 : i64
cf.cond_br %473, ^bb69, ^bb70
^bb69:
%475 = arith.constant 0 : i32
%476 = llvm.load %470 : !llvm.ptr -> i64
%478 = arith.extsi %475 : i32 to i64
%477 = arith.subi %478, %476 : i64
llvm.store %477, %470 : i64, !llvm.ptr
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
%479 = llvm.load %470 : !llvm.ptr -> i64
%480 = arith.remsi %479, %arg0 : i64
func.return %480 : i64
}
func.func @pollard_rho(%arg0: i128) -> i128 {
%481 = arith.constant 2 : i32
%483 = arith.trunci %arg0 : i128 to i64
%484 = arith.extsi %481 : i32 to i64
%482 = arith.remsi %483, %484 : i64
%485 = arith.constant 0 : i32
%487 = arith.extsi %485 : i32 to i64
%486 = arith.cmpi eq, %482, %487 : i64
cf.cond_br %486, ^bb72, ^bb73
^bb72:
%488 = arith.constant 2 : i32
%489 = arith.extsi %488 : i32 to i128
func.return %489 : i128
^bb73:
cf.br ^bb74
^bb74:
%490 = arith.constant 3 : i32
%492 = arith.trunci %arg0 : i128 to i64
%493 = arith.extsi %490 : i32 to i64
%491 = arith.remsi %492, %493 : i64
%494 = arith.constant 0 : i32
%496 = arith.extsi %494 : i32 to i64
%495 = arith.cmpi eq, %491, %496 : i64
cf.cond_br %495, ^bb75, ^bb76
^bb75:
%497 = arith.constant 3 : i32
%498 = arith.extsi %497 : i32 to i128
func.return %498 : i128
^bb76:
cf.br ^bb77
^bb77:
cf.br ^bb78
^bb78:
%499 = arith.constant 1 : i1
cf.cond_br %499, ^bb79, ^bb80
^bb79:
%500 = arith.constant 2 : i32
%502 = arith.constant 1000000007 : i32
%503 = arith.extsi %502 : i32 to i64
%501 = func.call @rng_next(%503) : (i64) -> i64
%505 = arith.extsi %500 : i32 to i64
%504 = arith.addi %505, %501 : i64
%506 = arith.extsi %504 : i64 to i128
%508 = arith.trunci %506 : i128 to i64
%509 = arith.trunci %arg0 : i128 to i64
%507 = arith.remsi %508, %509 : i64
%510 = arith.extsi %507 : i64 to i128
%511 = llvm.mlir.constant(1 : i64) : i64
%512 = llvm.alloca %511 x i128 : (i64) -> !llvm.ptr
llvm.store %510, %512 : i128, !llvm.ptr
%513 = llvm.load %512 : !llvm.ptr -> i128
%514 = llvm.mlir.constant(1 : i64) : i64
%515 = llvm.alloca %514 x i128 : (i64) -> !llvm.ptr
llvm.store %513, %515 : i128, !llvm.ptr
%516 = arith.constant 1 : i32
%518 = arith.constant 1000000007 : i32
%519 = arith.extsi %518 : i32 to i64
%517 = func.call @rng_next(%519) : (i64) -> i64
%521 = arith.extsi %516 : i32 to i64
%520 = arith.addi %521, %517 : i64
%522 = arith.extsi %520 : i64 to i128
%524 = arith.trunci %522 : i128 to i64
%525 = arith.trunci %arg0 : i128 to i64
%523 = arith.remsi %524, %525 : i64
%526 = arith.extsi %523 : i64 to i128
%527 = arith.constant 1 : i32
%528 = arith.extsi %527 : i32 to i128
%529 = llvm.mlir.constant(1 : i64) : i64
%530 = llvm.alloca %529 x i128 : (i64) -> !llvm.ptr
llvm.store %528, %530 : i128, !llvm.ptr
cf.br ^bb81
^bb81:
%531 = llvm.load %530 : !llvm.ptr -> i128
%532 = arith.constant 1 : i32
%534 = arith.trunci %531 : i128 to i64
%535 = arith.extsi %532 : i32 to i64
%533 = arith.cmpi eq, %534, %535 : i64
cf.cond_br %533, ^bb82, ^bb83
^bb82:
%537 = llvm.load %512 : !llvm.ptr -> i128
%538 = llvm.load %512 : !llvm.ptr -> i128
%536 = func.call @mulmod128(%537, %538, %arg0) : (i128, i128, i128) -> i128
llvm.store %536, %512 : i128, !llvm.ptr
%539 = llvm.load %512 : !llvm.ptr -> i128
%541 = arith.trunci %539 : i128 to i64
%542 = arith.trunci %526 : i128 to i64
%540 = arith.addi %541, %542 : i64
%543 = arith.extsi %540 : i64 to i128
llvm.store %543, %512 : i128, !llvm.ptr
%544 = llvm.load %512 : !llvm.ptr -> i128
%546 = arith.trunci %544 : i128 to i64
%547 = arith.trunci %arg0 : i128 to i64
%545 = arith.cmpi sge, %546, %547 : i64
cf.cond_br %545, ^bb84, ^bb85
^bb84:
%548 = llvm.load %512 : !llvm.ptr -> i128
%550 = arith.trunci %548 : i128 to i64
%551 = arith.trunci %arg0 : i128 to i64
%549 = arith.subi %550, %551 : i64
%552 = arith.extsi %549 : i64 to i128
llvm.store %552, %512 : i128, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
%554 = llvm.load %515 : !llvm.ptr -> i128
%555 = llvm.load %515 : !llvm.ptr -> i128
%553 = func.call @mulmod128(%554, %555, %arg0) : (i128, i128, i128) -> i128
llvm.store %553, %515 : i128, !llvm.ptr
%556 = llvm.load %515 : !llvm.ptr -> i128
%558 = arith.trunci %556 : i128 to i64
%559 = arith.trunci %526 : i128 to i64
%557 = arith.addi %558, %559 : i64
%560 = arith.extsi %557 : i64 to i128
llvm.store %560, %515 : i128, !llvm.ptr
%561 = llvm.load %515 : !llvm.ptr -> i128
%563 = arith.trunci %561 : i128 to i64
%564 = arith.trunci %arg0 : i128 to i64
%562 = arith.cmpi sge, %563, %564 : i64
cf.cond_br %562, ^bb87, ^bb88
^bb87:
%565 = llvm.load %515 : !llvm.ptr -> i128
%567 = arith.trunci %565 : i128 to i64
%568 = arith.trunci %arg0 : i128 to i64
%566 = arith.subi %567, %568 : i64
%569 = arith.extsi %566 : i64 to i128
llvm.store %569, %515 : i128, !llvm.ptr
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
%571 = llvm.load %515 : !llvm.ptr -> i128
%572 = llvm.load %515 : !llvm.ptr -> i128
%570 = func.call @mulmod128(%571, %572, %arg0) : (i128, i128, i128) -> i128
llvm.store %570, %515 : i128, !llvm.ptr
%573 = llvm.load %515 : !llvm.ptr -> i128
%575 = arith.trunci %573 : i128 to i64
%576 = arith.trunci %526 : i128 to i64
%574 = arith.addi %575, %576 : i64
%577 = arith.extsi %574 : i64 to i128
llvm.store %577, %515 : i128, !llvm.ptr
%578 = llvm.load %515 : !llvm.ptr -> i128
%580 = arith.trunci %578 : i128 to i64
%581 = arith.trunci %arg0 : i128 to i64
%579 = arith.cmpi sge, %580, %581 : i64
cf.cond_br %579, ^bb90, ^bb91
^bb90:
%582 = llvm.load %515 : !llvm.ptr -> i128
%584 = arith.trunci %582 : i128 to i64
%585 = arith.trunci %arg0 : i128 to i64
%583 = arith.subi %584, %585 : i64
%586 = arith.extsi %583 : i64 to i128
llvm.store %586, %515 : i128, !llvm.ptr
cf.br ^bb92
^bb91:
cf.br ^bb92
^bb92:
%587 = llvm.load %512 : !llvm.ptr -> i128
%588 = llvm.load %515 : !llvm.ptr -> i128
%590 = arith.trunci %587 : i128 to i64
%591 = arith.trunci %588 : i128 to i64
%589 = arith.subi %590, %591 : i64
%592 = arith.extsi %589 : i64 to i128
%593 = llvm.mlir.constant(1 : i64) : i64
%594 = llvm.alloca %593 x i128 : (i64) -> !llvm.ptr
llvm.store %592, %594 : i128, !llvm.ptr
%595 = llvm.load %594 : !llvm.ptr -> i128
%596 = arith.constant 0 : i32
%598 = arith.trunci %595 : i128 to i64
%599 = arith.extsi %596 : i32 to i64
%597 = arith.cmpi slt, %598, %599 : i64
cf.cond_br %597, ^bb93, ^bb94
^bb93:
%600 = arith.constant 0 : i32
%601 = llvm.load %594 : !llvm.ptr -> i128
%603 = arith.extsi %600 : i32 to i64
%604 = arith.trunci %601 : i128 to i64
%602 = arith.subi %603, %604 : i64
%605 = arith.extsi %602 : i64 to i128
llvm.store %605, %594 : i128, !llvm.ptr
cf.br ^bb95
^bb94:
cf.br ^bb95
^bb95:
%607 = llvm.load %594 : !llvm.ptr -> i128
%606 = func.call @gcd128(%607, %arg0) : (i128, i128) -> i128
llvm.store %606, %530 : i128, !llvm.ptr
cf.br ^bb81
^bb83:
%608 = llvm.load %530 : !llvm.ptr -> i128
%610 = arith.trunci %608 : i128 to i64
%611 = arith.trunci %arg0 : i128 to i64
%609 = arith.cmpi ne, %610, %611 : i64
cf.cond_br %609, ^bb96, ^bb97
^bb96:
%612 = llvm.load %530 : !llvm.ptr -> i128
func.return %612 : i128
^bb97:
cf.br ^bb98
^bb98:
cf.br ^bb78
^bb80:
%613 = arith.constant 0 : i32
%614 = arith.extsi %613 : i32 to i128
func.return %614 : i128
}
// Module static: fac_p
llvm.mlir.global internal @fac_p() {addr_space = 0 : i32} : !llvm.ptr {
%615 = llvm.mlir.zero : !llvm.ptr
llvm.return %615 : !llvm.ptr
}
// Module static: fac_e
llvm.mlir.global internal @fac_e() {addr_space = 0 : i32} : !llvm.ptr {
%616 = llvm.mlir.zero : !llvm.ptr
llvm.return %616 : !llvm.ptr
}
// Module static: fac_count
llvm.mlir.global internal @fac_count(0 : i64) : i64
func.func @factor_rec(%arg0: i128) -> () {
%617 = arith.constant 1 : i32
%619 = arith.trunci %arg0 : i128 to i64
%620 = arith.extsi %617 : i32 to i64
%618 = arith.cmpi eq, %619, %620 : i64
cf.cond_br %618, ^bb99, ^bb100
^bb99:
func.return
^bb100:
cf.br ^bb101
^bb101:
%621 = func.call @is_prime128(%arg0) : (i128) -> i1
cf.cond_br %621, ^bb102, ^bb103
^bb102:
%622 = arith.constant 0 : i32
%623 = arith.extsi %622 : i32 to i64
%624 = llvm.mlir.constant(1 : i64) : i64
%625 = llvm.alloca %624 x i64 : (i64) -> !llvm.ptr
llvm.store %623, %625 : i64, !llvm.ptr
cf.br ^bb105
^bb105:
%626 = llvm.load %625 : !llvm.ptr -> i64
%627 = llvm.mlir.addressof @fac_count : !llvm.ptr
%628 = llvm.load %627 : !llvm.ptr -> i64
%629 = arith.cmpi slt, %626, %628 : i64
cf.cond_br %629, ^bb106, ^bb107
^bb106:
%631 = llvm.mlir.addressof @fac_p : !llvm.ptr
%632 = llvm.load %631 : !llvm.ptr -> !llvm.ptr
%633 = llvm.load %625 : !llvm.ptr -> i64
%634 = llvm.getelementptr %632[%633] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%630 = llvm.load %634 : !llvm.ptr -> i128
%636 = arith.trunci %630 : i128 to i64
%637 = arith.trunci %arg0 : i128 to i64
%635 = arith.cmpi eq, %636, %637 : i64
cf.cond_br %635, ^bb108, ^bb109
^bb108:
%639 = llvm.mlir.addressof @fac_e : !llvm.ptr
%640 = llvm.load %639 : !llvm.ptr -> !llvm.ptr
%641 = llvm.load %625 : !llvm.ptr -> i64
%642 = llvm.getelementptr %640[%641] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%638 = llvm.load %642 : !llvm.ptr -> i64
%643 = arith.constant 1 : i32
%645 = arith.extsi %643 : i32 to i64
%644 = arith.addi %638, %645 : i64
%646 = llvm.mlir.addressof @fac_e : !llvm.ptr
%647 = llvm.load %646 : !llvm.ptr -> !llvm.ptr
%648 = llvm.load %625 : !llvm.ptr -> i64
%649 = llvm.getelementptr %647[%648] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %644, %649 : i64, !llvm.ptr
func.return
^bb109:
cf.br ^bb110
^bb110:
%650 = llvm.load %625 : !llvm.ptr -> i64
%651 = arith.constant 1 : i32
%653 = arith.extsi %651 : i32 to i64
%652 = arith.addi %650, %653 : i64
llvm.store %652, %625 : i64, !llvm.ptr
cf.br ^bb105
^bb107:
%654 = llvm.mlir.addressof @fac_p : !llvm.ptr
%655 = llvm.load %654 : !llvm.ptr -> !llvm.ptr
%656 = llvm.mlir.addressof @fac_count : !llvm.ptr
%657 = llvm.load %656 : !llvm.ptr -> i64
%658 = llvm.getelementptr %655[%657] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %arg0, %658 : i128, !llvm.ptr
%659 = arith.constant 1 : i32
%660 = llvm.mlir.addressof @fac_e : !llvm.ptr
%661 = llvm.load %660 : !llvm.ptr -> !llvm.ptr
%662 = llvm.mlir.addressof @fac_count : !llvm.ptr
%663 = llvm.load %662 : !llvm.ptr -> i64
%664 = arith.extsi %659 : i32 to i64
%665 = llvm.getelementptr %661[%663] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %664, %665 : i64, !llvm.ptr
%666 = llvm.mlir.addressof @fac_count : !llvm.ptr
%667 = llvm.load %666 : !llvm.ptr -> i64
%668 = arith.constant 1 : i32
%670 = arith.extsi %668 : i32 to i64
%669 = arith.addi %667, %670 : i64
%671 = llvm.mlir.addressof @fac_count : !llvm.ptr
llvm.store %669, %671 : i64, !llvm.ptr
func.return
^bb103:
cf.br ^bb104
^bb104:
%672 = func.call @pollard_rho(%arg0) : (i128) -> i128
func.call @factor_rec(%672) : (i128) -> ()
%676 = arith.trunci %arg0 : i128 to i64
%677 = arith.trunci %672 : i128 to i64
%675 = arith.divsi %676, %677 : i64
%678 = arith.extsi %675 : i64 to i128
func.call @factor_rec(%678) : (i128) -> ()
func.return
}
func.func @sift_down(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> () {
%679 = llvm.mlir.constant(1 : i64) : i64
%680 = llvm.alloca %679 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %680 : i64, !llvm.ptr
cf.br ^bb111
^bb111:
%681 = arith.constant 2 : i32
%682 = llvm.load %680 : !llvm.ptr -> i64
%684 = arith.extsi %681 : i32 to i64
%683 = arith.muli %684, %682 : i64
%685 = arith.constant 1 : i32
%687 = arith.extsi %685 : i32 to i64
%686 = arith.addi %683, %687 : i64
%688 = arith.cmpi sle, %686, %arg2 : i64
cf.cond_br %688, ^bb112, ^bb113
^bb112:
%689 = arith.constant 2 : i32
%690 = llvm.load %680 : !llvm.ptr -> i64
%692 = arith.extsi %689 : i32 to i64
%691 = arith.muli %692, %690 : i64
%693 = arith.constant 1 : i32
%695 = arith.extsi %693 : i32 to i64
%694 = arith.addi %691, %695 : i64
%696 = llvm.mlir.constant(1 : i64) : i64
%697 = llvm.alloca %696 x i64 : (i64) -> !llvm.ptr
llvm.store %694, %697 : i64, !llvm.ptr
%698 = llvm.load %697 : !llvm.ptr -> i64
%699 = arith.constant 1 : i32
%701 = arith.extsi %699 : i32 to i64
%700 = arith.addi %698, %701 : i64
%702 = arith.cmpi sle, %700, %arg2 : i64
%703 = scf.if %702 -> (i1) {
%705 = llvm.load %697 : !llvm.ptr -> i64
%706 = llvm.getelementptr %arg0[%705] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%704 = llvm.load %706 : !llvm.ptr -> i128
%708 = llvm.load %697 : !llvm.ptr -> i64
%709 = arith.constant 1 : i32
%711 = arith.extsi %709 : i32 to i64
%710 = arith.addi %708, %711 : i64
%712 = llvm.getelementptr %arg0[%710] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%707 = llvm.load %712 : !llvm.ptr -> i128
%714 = arith.trunci %704 : i128 to i64
%715 = arith.trunci %707 : i128 to i64
%713 = arith.cmpi slt, %714, %715 : i64
scf.yield %713 : i1
} else {
%716 = arith.constant false
scf.yield %716 : i1
}
cf.cond_br %703, ^bb114, ^bb115
^bb114:
%717 = llvm.load %697 : !llvm.ptr -> i64
%718 = arith.constant 1 : i32
%720 = arith.extsi %718 : i32 to i64
%719 = arith.addi %717, %720 : i64
llvm.store %719, %697 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
%722 = llvm.load %680 : !llvm.ptr -> i64
%723 = llvm.getelementptr %arg0[%722] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%721 = llvm.load %723 : !llvm.ptr -> i128
%725 = llvm.load %697 : !llvm.ptr -> i64
%726 = llvm.getelementptr %arg0[%725] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%724 = llvm.load %726 : !llvm.ptr -> i128
%728 = arith.trunci %721 : i128 to i64
%729 = arith.trunci %724 : i128 to i64
%727 = arith.cmpi slt, %728, %729 : i64
cf.cond_br %727, ^bb117, ^bb118
^bb117:
%731 = llvm.load %680 : !llvm.ptr -> i64
%732 = llvm.getelementptr %arg0[%731] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%730 = llvm.load %732 : !llvm.ptr -> i128
%734 = llvm.load %697 : !llvm.ptr -> i64
%735 = llvm.getelementptr %arg0[%734] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%733 = llvm.load %735 : !llvm.ptr -> i128
%736 = llvm.load %680 : !llvm.ptr -> i64
%737 = llvm.getelementptr %arg0[%736] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %733, %737 : i128, !llvm.ptr
%738 = llvm.load %697 : !llvm.ptr -> i64
%739 = llvm.getelementptr %arg0[%738] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %730, %739 : i128, !llvm.ptr
%740 = llvm.load %697 : !llvm.ptr -> i64
llvm.store %740, %680 : i64, !llvm.ptr
cf.br ^bb119
^bb118:
cf.br ^bb113
^bb119:
cf.br ^bb111
^bb113:
func.return
}
func.func @heapsort_i128(%arg0: !llvm.ptr, %arg1: i64) -> () {
%741 = arith.constant 1 : i32
%743 = arith.extsi %741 : i32 to i64
%742 = arith.cmpi sle, %arg1, %743 : i64
cf.cond_br %742, ^bb120, ^bb121
^bb120:
func.return
^bb121:
cf.br ^bb122
^bb122:
%744 = arith.constant 2 : i32
%746 = arith.extsi %744 : i32 to i64
%745 = arith.divsi %arg1, %746 : i64
%747 = arith.constant 1 : i32
%749 = arith.extsi %747 : i32 to i64
%748 = arith.subi %745, %749 : i64
%750 = llvm.mlir.constant(1 : i64) : i64
%751 = llvm.alloca %750 x i64 : (i64) -> !llvm.ptr
llvm.store %748, %751 : i64, !llvm.ptr
cf.br ^bb123
^bb123:
%752 = llvm.load %751 : !llvm.ptr -> i64
%753 = arith.constant 0 : i32
%755 = arith.extsi %753 : i32 to i64
%754 = arith.cmpi sge, %752, %755 : i64
cf.cond_br %754, ^bb124, ^bb125
^bb124:
%757 = llvm.load %751 : !llvm.ptr -> i64
%758 = arith.constant 1 : i32
%760 = arith.extsi %758 : i32 to i64
%759 = arith.subi %arg1, %760 : i64
func.call @sift_down(%arg0, %757, %759) : (!llvm.ptr, i64, i64) -> ()
%761 = llvm.load %751 : !llvm.ptr -> i64
%762 = arith.constant 1 : i32
%764 = arith.extsi %762 : i32 to i64
%763 = arith.subi %761, %764 : i64
llvm.store %763, %751 : i64, !llvm.ptr
cf.br ^bb123
^bb125:
%765 = arith.constant 1 : i32
%767 = arith.extsi %765 : i32 to i64
%766 = arith.subi %arg1, %767 : i64
%768 = llvm.mlir.constant(1 : i64) : i64
%769 = llvm.alloca %768 x i64 : (i64) -> !llvm.ptr
llvm.store %766, %769 : i64, !llvm.ptr
cf.br ^bb126
^bb126:
%770 = llvm.load %769 : !llvm.ptr -> i64
%771 = arith.constant 0 : i32
%773 = arith.extsi %771 : i32 to i64
%772 = arith.cmpi sgt, %770, %773 : i64
cf.cond_br %772, ^bb127, ^bb128
^bb127:
%775 = arith.constant 0 : i32
%776 = arith.extsi %775 : i32 to i64
%777 = llvm.getelementptr %arg0[%776] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%774 = llvm.load %777 : !llvm.ptr -> i128
%779 = llvm.load %769 : !llvm.ptr -> i64
%780 = llvm.getelementptr %arg0[%779] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%778 = llvm.load %780 : !llvm.ptr -> i128
%781 = arith.constant 0 : i32
%782 = arith.extsi %781 : i32 to i64
%783 = llvm.getelementptr %arg0[%782] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %778, %783 : i128, !llvm.ptr
%784 = llvm.load %769 : !llvm.ptr -> i64
%785 = llvm.getelementptr %arg0[%784] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %774, %785 : i128, !llvm.ptr
%786 = llvm.load %769 : !llvm.ptr -> i64
%787 = arith.constant 1 : i32
%789 = arith.extsi %787 : i32 to i64
%788 = arith.subi %786, %789 : i64
llvm.store %788, %769 : i64, !llvm.ptr
%791 = arith.constant 0 : i32
%792 = llvm.load %769 : !llvm.ptr -> i64
%793 = arith.extsi %791 : i32 to i64
func.call @sift_down(%arg0, %793, %792) : (!llvm.ptr, i64, i64) -> ()
cf.br ^bb126
^bb128:
func.return
}
// Module static: g_divisors
llvm.mlir.global internal @g_divisors() {addr_space = 0 : i32} : !llvm.ptr {
%794 = llvm.mlir.zero : !llvm.ptr
llvm.return %794 : !llvm.ptr
}
// Module static: g_nd
llvm.mlir.global internal @g_nd(0 : i64) : i64
func.func @all_divisors(%arg0: i128) -> () {
%796 = arith.constant 64 : i32
%797 = arith.constant 16 : i32
%798 = arith.muli %796, %797 : i32
%799 = arith.extsi %798 : i32 to i64
%795 = func.call @malloc(%799) : (i64) -> !llvm.ptr
%800 = llvm.mlir.addressof @fac_p : !llvm.ptr
llvm.store %795, %800 : !llvm.ptr, !llvm.ptr
%802 = arith.constant 64 : i32
%803 = arith.constant 8 : i32
%804 = arith.muli %802, %803 : i32
%805 = arith.extsi %804 : i32 to i64
%801 = func.call @malloc(%805) : (i64) -> !llvm.ptr
%806 = llvm.mlir.addressof @fac_e : !llvm.ptr
llvm.store %801, %806 : !llvm.ptr, !llvm.ptr
%807 = arith.constant 0 : i32
%808 = arith.extsi %807 : i32 to i64
%809 = llvm.mlir.addressof @fac_count : !llvm.ptr
llvm.store %808, %809 : i64, !llvm.ptr
func.call @factor_rec(%arg0) : (i128) -> ()
%812 = arith.constant 50000 : i32
%813 = arith.constant 16 : i32
%814 = arith.muli %812, %813 : i32
%815 = arith.extsi %814 : i32 to i64
%811 = func.call @malloc(%815) : (i64) -> !llvm.ptr
%816 = llvm.mlir.addressof @g_divisors : !llvm.ptr
llvm.store %811, %816 : !llvm.ptr, !llvm.ptr
%817 = arith.constant 1 : i32
%818 = arith.extsi %817 : i32 to i64
%819 = llvm.mlir.constant(1 : i64) : i64
%820 = llvm.alloca %819 x i64 : (i64) -> !llvm.ptr
llvm.store %818, %820 : i64, !llvm.ptr
%821 = arith.constant 1 : i32
%822 = llvm.mlir.addressof @g_divisors : !llvm.ptr
%823 = llvm.load %822 : !llvm.ptr -> !llvm.ptr
%824 = arith.constant 0 : i32
%825 = arith.extsi %821 : i32 to i128
%826 = arith.extsi %824 : i32 to i64
%827 = llvm.getelementptr %823[%826] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %825, %827 : i128, !llvm.ptr
%828 = arith.constant 0 : i32
%829 = arith.extsi %828 : i32 to i64
%830 = llvm.mlir.constant(1 : i64) : i64
%831 = llvm.alloca %830 x i64 : (i64) -> !llvm.ptr
llvm.store %829, %831 : i64, !llvm.ptr
cf.br ^bb129
^bb129:
%832 = llvm.load %831 : !llvm.ptr -> i64
%833 = llvm.mlir.addressof @fac_count : !llvm.ptr
%834 = llvm.load %833 : !llvm.ptr -> i64
%835 = arith.cmpi slt, %832, %834 : i64
cf.cond_br %835, ^bb130, ^bb131
^bb130:
%836 = llvm.load %820 : !llvm.ptr -> i64
%837 = arith.constant 1 : i32
%838 = arith.extsi %837 : i32 to i128
%839 = llvm.mlir.constant(1 : i64) : i64
%840 = llvm.alloca %839 x i128 : (i64) -> !llvm.ptr
llvm.store %838, %840 : i128, !llvm.ptr
%841 = arith.constant 0 : i32
%842 = arith.extsi %841 : i32 to i64
%843 = llvm.mlir.constant(1 : i64) : i64
%844 = llvm.alloca %843 x i64 : (i64) -> !llvm.ptr
llvm.store %842, %844 : i64, !llvm.ptr
cf.br ^bb132
^bb132:
%845 = llvm.load %844 : !llvm.ptr -> i64
%847 = llvm.mlir.addressof @fac_e : !llvm.ptr
%848 = llvm.load %847 : !llvm.ptr -> !llvm.ptr
%849 = llvm.load %831 : !llvm.ptr -> i64
%850 = llvm.getelementptr %848[%849] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%846 = llvm.load %850 : !llvm.ptr -> i64
%851 = arith.cmpi slt, %845, %846 : i64
cf.cond_br %851, ^bb133, ^bb134
^bb133:
%852 = llvm.load %840 : !llvm.ptr -> i128
%854 = llvm.mlir.addressof @fac_p : !llvm.ptr
%855 = llvm.load %854 : !llvm.ptr -> !llvm.ptr
%856 = llvm.load %831 : !llvm.ptr -> i64
%857 = llvm.getelementptr %855[%856] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%853 = llvm.load %857 : !llvm.ptr -> i128
%859 = arith.trunci %852 : i128 to i64
%860 = arith.trunci %853 : i128 to i64
%858 = arith.muli %859, %860 : i64
%861 = arith.extsi %858 : i64 to i128
llvm.store %861, %840 : i128, !llvm.ptr
%862 = arith.constant 0 : i32
%863 = arith.extsi %862 : i32 to i64
%864 = llvm.mlir.constant(1 : i64) : i64
%865 = llvm.alloca %864 x i64 : (i64) -> !llvm.ptr
llvm.store %863, %865 : i64, !llvm.ptr
cf.br ^bb135
^bb135:
%866 = llvm.load %865 : !llvm.ptr -> i64
%867 = arith.cmpi slt, %866, %836 : i64
cf.cond_br %867, ^bb136, ^bb137
^bb136:
%869 = llvm.mlir.addressof @g_divisors : !llvm.ptr
%870 = llvm.load %869 : !llvm.ptr -> !llvm.ptr
%871 = llvm.load %865 : !llvm.ptr -> i64
%872 = llvm.getelementptr %870[%871] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%868 = llvm.load %872 : !llvm.ptr -> i128
%873 = llvm.load %840 : !llvm.ptr -> i128
%875 = arith.trunci %868 : i128 to i64
%876 = arith.trunci %873 : i128 to i64
%874 = arith.muli %875, %876 : i64
%877 = llvm.mlir.addressof @g_divisors : !llvm.ptr
%878 = llvm.load %877 : !llvm.ptr -> !llvm.ptr
%879 = llvm.load %820 : !llvm.ptr -> i64
%880 = arith.extsi %874 : i64 to i128
%881 = llvm.getelementptr %878[%879] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %880, %881 : i128, !llvm.ptr
%882 = llvm.load %820 : !llvm.ptr -> i64
%883 = arith.constant 1 : i32
%885 = arith.extsi %883 : i32 to i64
%884 = arith.addi %882, %885 : i64
llvm.store %884, %820 : i64, !llvm.ptr
%886 = llvm.load %865 : !llvm.ptr -> i64
%887 = arith.constant 1 : i32
%889 = arith.extsi %887 : i32 to i64
%888 = arith.addi %886, %889 : i64
llvm.store %888, %865 : i64, !llvm.ptr
cf.br ^bb135
^bb137:
%890 = llvm.load %844 : !llvm.ptr -> i64
%891 = arith.constant 1 : i32
%893 = arith.extsi %891 : i32 to i64
%892 = arith.addi %890, %893 : i64
llvm.store %892, %844 : i64, !llvm.ptr
cf.br ^bb132
^bb134:
%894 = llvm.load %831 : !llvm.ptr -> i64
%895 = arith.constant 1 : i32
%897 = arith.extsi %895 : i32 to i64
%896 = arith.addi %894, %897 : i64
llvm.store %896, %831 : i64, !llvm.ptr
cf.br ^bb129
^bb131:
%899 = llvm.mlir.addressof @g_divisors : !llvm.ptr
%900 = llvm.load %899 : !llvm.ptr -> !llvm.ptr
%901 = llvm.load %820 : !llvm.ptr -> i64
func.call @heapsort_i128(%900, %901) : (!llvm.ptr, i64) -> ()
%902 = llvm.load %820 : !llvm.ptr -> i64
%903 = llvm.mlir.addressof @g_nd : !llvm.ptr
llvm.store %902, %903 : i64, !llvm.ptr
%905 = llvm.mlir.addressof @fac_p : !llvm.ptr
%906 = llvm.load %905 : !llvm.ptr -> !llvm.ptr
func.call @free(%906) : (!llvm.ptr) -> ()
%908 = llvm.mlir.addressof @fac_e : !llvm.ptr
%909 = llvm.load %908 : !llvm.ptr -> !llvm.ptr
func.call @free(%909) : (!llvm.ptr) -> ()
func.return
}
// Module static: out_k
llvm.mlir.global internal @out_k(0 : i128) : i128
// Module static: out_a
llvm.mlir.global internal @out_a(0 : i128) : i128
func.func @next_triangle_jump(%arg0: i128) -> () {
%910 = arith.constant 2 : i32
%912 = arith.extsi %910 : i32 to i64
%913 = arith.trunci %arg0 : i128 to i64
%911 = arith.muli %912, %913 : i64
%914 = arith.extsi %911 : i64 to i128
func.call @all_divisors(%914) : (i128) -> ()
%916 = arith.constant 0 : i32
%917 = arith.extsi %916 : i32 to i64
%918 = llvm.mlir.constant(1 : i64) : i64
%919 = llvm.alloca %918 x i64 : (i64) -> !llvm.ptr
llvm.store %917, %919 : i64, !llvm.ptr
cf.br ^bb138
^bb138:
%920 = llvm.load %919 : !llvm.ptr -> i64
%921 = llvm.mlir.addressof @g_nd : !llvm.ptr
%922 = llvm.load %921 : !llvm.ptr -> i64
%923 = arith.cmpi slt, %920, %922 : i64
cf.cond_br %923, ^bb139, ^bb140
^bb139:
%925 = llvm.mlir.addressof @g_divisors : !llvm.ptr
%926 = llvm.load %925 : !llvm.ptr -> !llvm.ptr
%927 = llvm.load %919 : !llvm.ptr -> i64
%928 = llvm.getelementptr %926[%927] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%924 = llvm.load %928 : !llvm.ptr -> i128
%930 = arith.trunci %914 : i128 to i64
%931 = arith.trunci %924 : i128 to i64
%929 = arith.divsi %930, %931 : i64
%932 = arith.extsi %929 : i64 to i128
%934 = arith.trunci %924 : i128 to i64
%935 = arith.trunci %932 : i128 to i64
%933 = arith.subi %934, %935 : i64
%936 = arith.constant 1 : i32
%937 = arith.constant 0 : i32
%938 = arith.cmpi ne, %936, %937 : i32
%940 = arith.trunci %933 : i64 to i1
%939 = arith.andi %940, %938 : i1
cf.cond_br %939, ^bb141, ^bb142
^bb141:
%942 = arith.trunci %924 : i128 to i64
%943 = arith.trunci %932 : i128 to i64
%941 = arith.subi %942, %943 : i64
%944 = arith.constant 1 : i32
%946 = arith.extsi %944 : i32 to i64
%945 = arith.subi %941, %946 : i64
%947 = arith.constant 2 : i32
%949 = arith.extsi %947 : i32 to i64
%948 = arith.divsi %945, %949 : i64
%950 = arith.extsi %948 : i64 to i128
%951 = arith.constant 0 : i32
%953 = arith.trunci %950 : i128 to i64
%954 = arith.extsi %951 : i32 to i64
%952 = arith.cmpi sgt, %953, %954 : i64
cf.cond_br %952, ^bb144, ^bb145
^bb144:
%955 = llvm.mlir.addressof @out_k : !llvm.ptr
llvm.store %950, %955 : i128, !llvm.ptr
%956 = arith.constant 1 : i32
%958 = arith.trunci %950 : i128 to i64
%959 = arith.extsi %956 : i32 to i64
%957 = arith.addi %958, %959 : i64
%961 = arith.trunci %950 : i128 to i64
%960 = arith.muli %961, %957 : i64
%962 = arith.constant 2 : i32
%964 = arith.extsi %962 : i32 to i64
%963 = arith.divsi %960, %964 : i64
%966 = arith.trunci %arg0 : i128 to i64
%965 = arith.addi %966, %963 : i64
%967 = arith.extsi %965 : i64 to i128
%968 = llvm.mlir.addressof @out_a : !llvm.ptr
llvm.store %967, %968 : i128, !llvm.ptr
%970 = llvm.mlir.addressof @g_divisors : !llvm.ptr
%971 = llvm.load %970 : !llvm.ptr -> !llvm.ptr
func.call @free(%971) : (!llvm.ptr) -> ()
func.return
^bb145:
cf.br ^bb146
^bb146:
cf.br ^bb143
^bb142:
cf.br ^bb143
^bb143:
%972 = llvm.load %919 : !llvm.ptr -> i64
%973 = arith.constant 1 : i32
%975 = arith.extsi %973 : i32 to i64
%974 = arith.addi %972, %975 : i64
llvm.store %974, %919 : i64, !llvm.ptr
cf.br ^bb138
^bb140:
%977 = llvm.mlir.addressof @g_divisors : !llvm.ptr
%978 = llvm.load %977 : !llvm.ptr -> !llvm.ptr
func.call @free(%978) : (!llvm.ptr) -> ()
%979 = arith.constant 0 : i32
%980 = arith.constant 1 : i32
%981 = arith.subi %979, %980 : i32
%982 = arith.extsi %981 : i32 to i128
%983 = llvm.mlir.addressof @out_k : !llvm.ptr
llvm.store %982, %983 : i128, !llvm.ptr
%984 = arith.constant 0 : i32
%985 = arith.constant 1 : i32
%986 = arith.subi %984, %985 : i32
%987 = arith.extsi %986 : i32 to i128
%988 = llvm.mlir.addressof @out_a : !llvm.ptr
llvm.store %987, %988 : i128, !llvm.ptr
func.return
}
func.func @main() -> i32 {
%989 = arith.constant 0 : i32
%990 = arith.extsi %989 : i32 to i128
%991 = llvm.mlir.constant(1 : i64) : i64
%992 = llvm.alloca %991 x i128 : (i64) -> !llvm.ptr
llvm.store %990, %992 : i128, !llvm.ptr
%993 = arith.constant 3 : i32
%994 = arith.extsi %993 : i32 to i128
%995 = llvm.mlir.constant(1 : i64) : i64
%996 = llvm.alloca %995 x i128 : (i64) -> !llvm.ptr
llvm.store %994, %996 : i128, !llvm.ptr
%997 = arith.constant 0 : i32
%998 = arith.extsi %997 : i32 to i64
%999 = llvm.mlir.constant(1 : i64) : i64
%1000 = llvm.alloca %999 x i64 : (i64) -> !llvm.ptr
llvm.store %998, %1000 : i64, !llvm.ptr
cf.br ^bb147
^bb147:
%1001 = llvm.load %1000 : !llvm.ptr -> i64
%1002 = arith.constant 69 : i32
%1004 = arith.extsi %1002 : i32 to i64
%1003 = arith.cmpi slt, %1001, %1004 : i64
cf.cond_br %1003, ^bb148, ^bb149
^bb148:
%1006 = llvm.load %996 : !llvm.ptr -> i128
func.call @next_triangle_jump(%1006) : (i128) -> ()
%1007 = llvm.load %992 : !llvm.ptr -> i128
%1008 = llvm.mlir.addressof @out_k : !llvm.ptr
%1009 = llvm.load %1008 : !llvm.ptr -> i128
%1011 = arith.trunci %1007 : i128 to i64
%1012 = arith.trunci %1009 : i128 to i64
%1010 = arith.addi %1011, %1012 : i64
%1013 = arith.extsi %1010 : i64 to i128
llvm.store %1013, %992 : i128, !llvm.ptr
%1014 = llvm.mlir.addressof @out_a : !llvm.ptr
%1015 = llvm.load %1014 : !llvm.ptr -> i128
llvm.store %1015, %996 : i128, !llvm.ptr
%1016 = llvm.load %1000 : !llvm.ptr -> i64
%1017 = arith.constant 1 : i32
%1019 = arith.extsi %1017 : i32 to i64
%1018 = arith.addi %1016, %1019 : i64
llvm.store %1018, %1000 : i64, !llvm.ptr
cf.br ^bb147
^bb149:
%1020 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1021 = llvm.load %992 : !llvm.ptr -> i128
%1022 = arith.trunci %1021 : i128 to i64
%1023 = llvm.call @printf(%1020, %1022) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1024 = arith.constant 0 : i32
func.return %1024 : i32
}
}