← All problems Problem 615
Numbers with a given number of prime factors: 10^6-th omega=10^6 number mod. Search for numbers with at least `threshold` prime factors (with repetition) whose value is at most 3^threshold. When count >= 10^6, collect, sort, and take the 10^6-th value.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)O(sqrt(n))Space complexity O(n^2)O(1)Approach Flow solution Trial division or Pollard rho Verdict Suboptimal
Flow source
# Project Euler 615
# Numbers with a given number of prime factors: 10^6-th omega=10^6 number mod.
# Search for numbers with at least `threshold` prime factors (with repetition)
# whose value is at most 3^threshold. When count >= 10^6, collect, sort, and
# take the 10^6-th value.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
function log(x: f64) -> f64
}
const MOD: i64 = 123454321
const TARGET_RANK: i64 = 1000000
const TARGET_OMEGA: i64 = 1000000
let mut g_primes: ptr<i64> = null
let mut g_pc: i64 = 0
let mut g_prime_logs: ptr<f64> = null
let mut g_log3: f64 = 0.0
let mut g_values: ptr<i64> = null
let mut g_vcount: i64 = 0
let mut g_vcap: i64 = 0
let mut g_count_only: i64 = 0
let mut g_collect_flag: bool = false
let mut g_limit_i: i64 = 0
let mut g_log_limit: f64 = 0.0
let mut g_threshold: i64 = 0
function search(start_index: i64, product: i64, used: i64, log_product: f64) -> void {
if used >= g_threshold {
g_count_only = g_count_only + 1
if g_collect_flag {
if g_vcount < g_vcap {
g_values[g_vcount] = product
g_vcount = g_vcount + 1
}
}
}
let remaining: i64 = g_threshold - used
let mut index: i64 = start_index
while index < g_pc {
let prime: i64 = g_primes[index]
if product > g_limit_i / prime { break }
let next_product: i64 = product * prime
if remaining > 0 && log_product + (remaining as f64) * g_prime_logs[index] > g_log_limit + 1e-12 {
break
}
search(index, next_product, used + 1, log_product + g_prime_logs[index])
index = index + 1
}
}
function values_count(threshold: i64, collect: bool) -> i64 {
g_threshold = threshold
let mut limit_i: i64 = 1
let mut i: i64 = 0
while i < threshold {
limit_i = limit_i * 3
i = i + 1
}
g_limit_i = limit_i
g_log_limit = (threshold as f64) * g_log3
g_collect_flag = collect
g_count_only = 0
g_vcount = 0
search(0, 1, 0, 0.0)
return g_count_only
}
function heapsort_i64(arr: ptr<i64>, n: i64) -> void {
let mut start: i64 = n / 2
while start > 0 {
start = start - 1
let mut root: i64 = start
while 2 * root + 1 < n {
let child: i64 = 2 * root + 1
let mut swap_idx: i64 = root
if arr[swap_idx] < arr[child] { swap_idx = child }
if child + 1 < n {
if arr[swap_idx] < arr[child + 1] { swap_idx = child + 1 }
}
if swap_idx == root { break }
let tmp: i64 = arr[root]
arr[root] = arr[swap_idx]
arr[swap_idx] = tmp
root = swap_idx
}
}
let mut end: i64 = n - 1
while end > 0 {
let tmp: i64 = arr[0]
arr[0] = arr[end]
arr[end] = tmp
let mut root: i64 = 0
while 2 * root + 1 < end {
let child: i64 = 2 * root + 1
let mut swap_idx: i64 = root
if arr[swap_idx] < arr[child] { swap_idx = child }
if child + 1 < end {
if arr[swap_idx] < arr[child + 1] { swap_idx = child + 1 }
}
if swap_idx == root { break }
let tmp2: i64 = arr[root]
arr[root] = arr[swap_idx]
arr[swap_idx] = tmp2
root = swap_idx
}
end = end - 1
}
}
function mod_pow(a0: i64, e0: i64) -> i64 {
let mut r: i64 = 1
let mut a: i64 = a0 % 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 main() -> i32 {
let lim: i64 = 300000
let sieve: ptr<i8> = calloc(lim + 1, 1)
g_primes = calloc(lim, 8)
g_pc = 0
let mut i: i64 = 2
while i <= lim {
if sieve[i] == 0 {
g_primes[g_pc] = i
g_pc = g_pc + 1
if i * i <= lim {
let mut j: i64 = i * i
while j <= lim {
sieve[j] = 1
j = j + i
}
}
}
i = i + 1
}
g_prime_logs = calloc(g_pc, 8)
let mut pi: i64 = 0
while pi < g_pc {
g_prime_logs[pi] = log((g_primes[pi] as f64))
pi = pi + 1
}
g_log3 = log(3.0)
let mut threshold: i64 = 1
let mut value: i64 = 0
let mut found: bool = false
while !found {
threshold = threshold + 1
let cnt: i64 = values_count(threshold, false)
if cnt >= TARGET_RANK {
g_values = malloc(cnt * 8)
g_vcap = cnt
let cnt2: i64 = values_count(threshold, true)
heapsort_i64(g_values, g_vcount)
value = g_values[TARGET_RANK - 1]
found = true
}
}
let ans: i64 = (((value % MOD) as i128) * (mod_pow(2, TARGET_OMEGA - threshold) as i128) % (MOD as i128)) as i64
printf("%lld\n", ans)
free(sieve)
free(g_primes)
free(g_prime_logs)
free(g_values)
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; }
void search_i64_i64_i64_f64(int64_t start_index, int64_t product, int64_t used, double log_product);
int64_t values_count_i64_bool(int64_t threshold, bool collect);
void heapsort_i64_ptr_i64_i64(int64_t* arr, int64_t n);
int64_t mod_pow_i64_i64(int64_t a0, int64_t e0);
int32_t main(void);
static const int64_t MOD = 123454321;
static const int64_t TARGET_RANK = 1000000;
static const int64_t TARGET_OMEGA = 1000000;
/* Module statics */
static int64_t* g_primes = NULL;
static int64_t g_pc = 0;
static double* g_prime_logs = NULL;
static double g_log3 = 0.0;
static int64_t* g_values = NULL;
static int64_t g_vcount = 0;
static int64_t g_vcap = 0;
static int64_t g_count_only = 0;
static bool g_collect_flag = 0;
static int64_t g_limit_i = 0;
static double g_log_limit = 0.0;
static int64_t g_threshold = 0;
void search_i64_i64_i64_f64(int64_t start_index, int64_t product, int64_t used, double log_product) {
if (used >= g_threshold) {
g_count_only = (g_count_only + 1);
if (g_collect_flag) {
if (g_vcount < g_vcap) {
g_values[g_vcount] = product;
g_vcount = (g_vcount + 1);
}
}
}
int64_t remaining = (g_threshold - used);
int64_t index = start_index;
while (index < g_pc) {
int64_t prime = g_primes[index];
if (product > FLOW_CHECKED_DIV((g_limit_i), (prime))) {
break;
}
int64_t next_product = (product * prime);
if ((remaining > 0 && (log_product + (((double)(remaining)) * g_prime_logs[index])) > (g_log_limit + 1e-12))) {
break;
}
search_i64_i64_i64_f64(index, next_product, (used + 1), (log_product + g_prime_logs[index]));
index = (index + 1);
}
}
int64_t values_count_i64_bool(int64_t threshold, bool collect) {
g_threshold = threshold;
int64_t limit_i = 1;
int64_t i = 0;
while (i < threshold) {
limit_i = (limit_i * 3);
i = (i + 1);
}
g_limit_i = limit_i;
g_log_limit = (((double)(threshold)) * g_log3);
g_collect_flag = collect;
g_count_only = 0;
g_vcount = 0;
search_i64_i64_i64_f64(0, 1, 0, 0.0);
return g_count_only;
}
void heapsort_i64_ptr_i64_i64(int64_t* arr, int64_t n) {
int64_t start = FLOW_CHECKED_DIV((n), (2));
while (start > 0) {
start = (start - 1);
int64_t root = start;
while (((2 * root) + 1) < n) {
int64_t child = ((2 * root) + 1);
int64_t swap_idx = root;
if (arr[swap_idx] < arr[child]) {
swap_idx = child;
}
if ((child + 1) < n) {
if (arr[swap_idx] < arr[(child + 1)]) {
swap_idx = (child + 1);
}
}
if (swap_idx == root) {
break;
}
int64_t tmp = arr[root];
arr[root] = arr[swap_idx];
arr[swap_idx] = tmp;
root = swap_idx;
}
}
int64_t end = (n - 1);
while (end > 0) {
int64_t tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
int64_t root = 0;
while (((2 * root) + 1) < end) {
int64_t child = ((2 * root) + 1);
int64_t swap_idx = root;
if (arr[swap_idx] < arr[child]) {
swap_idx = child;
}
if ((child + 1) < end) {
if (arr[swap_idx] < arr[(child + 1)]) {
swap_idx = (child + 1);
}
}
if (swap_idx == root) {
break;
}
int64_t tmp2 = arr[root];
arr[root] = arr[swap_idx];
arr[swap_idx] = tmp2;
root = swap_idx;
}
end = (end - 1);
}
}
int64_t mod_pow_i64_i64(int64_t a0, int64_t e0) {
int64_t r = 1;
int64_t a = FLOW_CHECKED_MOD((a0), (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;
}
int32_t main(void) {
int64_t lim = 300000;
int8_t* sieve = (int8_t*)(calloc((lim + 1), 1));
g_primes = calloc(lim, 8);
g_pc = 0;
int64_t i = 2;
while (i <= lim) {
if (sieve[i] == 0) {
g_primes[g_pc] = i;
g_pc = (g_pc + 1);
if ((i * i) <= lim) {
int64_t j = (i * i);
while (j <= lim) {
sieve[j] = 1;
j = (j + i);
}
}
}
i = (i + 1);
}
g_prime_logs = calloc(g_pc, 8);
int64_t pi = 0;
while (pi < g_pc) {
g_prime_logs[pi] = log(((double)(g_primes[pi])));
pi = (pi + 1);
}
g_log3 = log(3.0);
int64_t threshold = 1;
int64_t value = 0;
bool found = 0;
while ((!(found))) {
threshold = (threshold + 1);
int64_t cnt = values_count_i64_bool(threshold, 0);
if (cnt >= TARGET_RANK) {
g_values = malloc((cnt * 8));
g_vcap = cnt;
int64_t cnt2 = values_count_i64_bool(threshold, 1);
heapsort_i64_ptr_i64_i64(g_values, g_vcount);
value = g_values[(TARGET_RANK - 1)];
found = 1;
}
}
int64_t ans = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD((value), (MOD)))) * ((__int128)(mod_pow_i64_i64(2, (TARGET_OMEGA - threshold)))))), (((__int128)(MOD))))));
printf("%lld\n", ans);
free(sieve);
free(g_primes);
free(g_prime_logs);
free(g_values);
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 private @log(f64) -> f64
// Constant: MOD
llvm.mlir.global internal constant @MOD(123454321 : i64) : i64
// Constant: TARGET_RANK
llvm.mlir.global internal constant @TARGET_RANK(1000000 : i64) : i64
// Constant: TARGET_OMEGA
llvm.mlir.global internal constant @TARGET_OMEGA(1000000 : i64) : i64
// Module static: g_primes
llvm.mlir.global internal @g_primes() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: g_pc
llvm.mlir.global internal @g_pc(0 : i64) : i64
// Module static: g_prime_logs
llvm.mlir.global internal @g_prime_logs() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
// Module static: g_log3
llvm.mlir.global internal @g_log3(0.0 : f64) : f64
// Module static: g_values
llvm.mlir.global internal @g_values() {addr_space = 0 : i32} : !llvm.ptr {
%2 = llvm.mlir.zero : !llvm.ptr
llvm.return %2 : !llvm.ptr
}
// Module static: g_vcount
llvm.mlir.global internal @g_vcount(0 : i64) : i64
// Module static: g_vcap
llvm.mlir.global internal @g_vcap(0 : i64) : i64
// Module static: g_count_only
llvm.mlir.global internal @g_count_only(0 : i64) : i64
// Module static: g_collect_flag
llvm.mlir.global internal @g_collect_flag(0 : i1) : i1
// Module static: g_limit_i
llvm.mlir.global internal @g_limit_i(0 : i64) : i64
// Module static: g_log_limit
llvm.mlir.global internal @g_log_limit(0.0 : f64) : f64
// Module static: g_threshold
llvm.mlir.global internal @g_threshold(0 : i64) : i64
func.func @search(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: f64) -> () {
%3 = llvm.mlir.addressof @g_threshold : !llvm.ptr
%4 = llvm.load %3 : !llvm.ptr -> i64
%5 = arith.cmpi sge, %arg2, %4 : i64
cf.cond_br %5, ^bb0, ^bb1
^bb0:
%6 = llvm.mlir.addressof @g_count_only : !llvm.ptr
%7 = llvm.load %6 : !llvm.ptr -> i64
%8 = arith.constant 1 : i32
%10 = arith.extsi %8 : i32 to i64
%9 = arith.addi %7, %10 : i64
%11 = llvm.mlir.addressof @g_count_only : !llvm.ptr
llvm.store %9, %11 : i64, !llvm.ptr
%12 = llvm.mlir.addressof @g_collect_flag : !llvm.ptr
%13 = llvm.load %12 : !llvm.ptr -> i1
cf.cond_br %13, ^bb3, ^bb4
^bb3:
%14 = llvm.mlir.addressof @g_vcount : !llvm.ptr
%15 = llvm.load %14 : !llvm.ptr -> i64
%16 = llvm.mlir.addressof @g_vcap : !llvm.ptr
%17 = llvm.load %16 : !llvm.ptr -> i64
%18 = arith.cmpi slt, %15, %17 : i64
cf.cond_br %18, ^bb6, ^bb7
^bb6:
%19 = llvm.mlir.addressof @g_values : !llvm.ptr
%20 = llvm.load %19 : !llvm.ptr -> !llvm.ptr
%21 = llvm.mlir.addressof @g_vcount : !llvm.ptr
%22 = llvm.load %21 : !llvm.ptr -> i64
%23 = llvm.getelementptr %20[%22] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %23 : i64, !llvm.ptr
%24 = llvm.mlir.addressof @g_vcount : !llvm.ptr
%25 = llvm.load %24 : !llvm.ptr -> i64
%26 = arith.constant 1 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.addi %25, %28 : i64
%29 = llvm.mlir.addressof @g_vcount : !llvm.ptr
llvm.store %27, %29 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%30 = llvm.mlir.addressof @g_threshold : !llvm.ptr
%31 = llvm.load %30 : !llvm.ptr -> i64
%32 = arith.subi %31, %arg2 : i64
%33 = llvm.mlir.constant(1 : i64) : i64
%34 = llvm.alloca %33 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %34 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%35 = llvm.load %34 : !llvm.ptr -> i64
%36 = llvm.mlir.addressof @g_pc : !llvm.ptr
%37 = llvm.load %36 : !llvm.ptr -> i64
%38 = arith.cmpi slt, %35, %37 : i64
cf.cond_br %38, ^bb10, ^bb11
^bb10:
%40 = llvm.mlir.addressof @g_primes : !llvm.ptr
%41 = llvm.load %40 : !llvm.ptr -> !llvm.ptr
%42 = llvm.load %34 : !llvm.ptr -> i64
%43 = llvm.getelementptr %41[%42] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%39 = llvm.load %43 : !llvm.ptr -> i64
%44 = llvm.mlir.addressof @g_limit_i : !llvm.ptr
%45 = llvm.load %44 : !llvm.ptr -> i64
%46 = arith.divsi %45, %39 : i64
%47 = arith.cmpi sgt, %arg1, %46 : i64
cf.cond_br %47, ^bb12, ^bb13
^bb12:
cf.br ^bb11
^bb13:
cf.br ^bb14
^bb14:
%48 = arith.muli %arg1, %39 : i64
%49 = arith.constant 0 : i32
%51 = arith.extsi %49 : i32 to i64
%50 = arith.cmpi sgt, %32, %51 : i64
%52 = scf.if %50 -> (i1) {
%53 = arith.sitofp %32 : i64 to f64
%55 = llvm.mlir.addressof @g_prime_logs : !llvm.ptr
%56 = llvm.load %55 : !llvm.ptr -> !llvm.ptr
%57 = llvm.load %34 : !llvm.ptr -> i64
%58 = llvm.getelementptr %56[%57] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%54 = llvm.load %58 : !llvm.ptr -> f64
%59 = arith.mulf %53, %54 : f64
%60 = arith.addf %arg3, %59 : f64
%61 = llvm.mlir.addressof @g_log_limit : !llvm.ptr
%62 = llvm.load %61 : !llvm.ptr -> f64
%63 = arith.constant 0 : f32
%65 = arith.extf %63 : f32 to f64
%64 = arith.addf %62, %65 : f64
%66 = arith.cmpf ogt, %60, %64 : f64
scf.yield %66 : i1
} else {
%67 = arith.constant false
scf.yield %67 : i1
}
cf.cond_br %52, ^bb15, ^bb16
^bb15:
cf.br ^bb11
^bb16:
cf.br ^bb17
^bb17:
%69 = llvm.load %34 : !llvm.ptr -> i64
%70 = arith.constant 1 : i32
%72 = arith.extsi %70 : i32 to i64
%71 = arith.addi %arg2, %72 : i64
%74 = llvm.mlir.addressof @g_prime_logs : !llvm.ptr
%75 = llvm.load %74 : !llvm.ptr -> !llvm.ptr
%76 = llvm.load %34 : !llvm.ptr -> i64
%77 = llvm.getelementptr %75[%76] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%73 = llvm.load %77 : !llvm.ptr -> f64
%78 = arith.addf %arg3, %73 : f64
func.call @search(%69, %48, %71, %78) : (i64, i64, i64, f64) -> ()
%79 = llvm.load %34 : !llvm.ptr -> i64
%80 = arith.constant 1 : i32
%82 = arith.extsi %80 : i32 to i64
%81 = arith.addi %79, %82 : i64
llvm.store %81, %34 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
func.return
}
func.func @values_count(%arg0: i64, %arg1: i1) -> i64 {
%83 = llvm.mlir.addressof @g_threshold : !llvm.ptr
llvm.store %arg0, %83 : i64, !llvm.ptr
%84 = arith.constant 1 : i32
%85 = arith.extsi %84 : i32 to i64
%86 = llvm.mlir.constant(1 : i64) : i64
%87 = llvm.alloca %86 x i64 : (i64) -> !llvm.ptr
llvm.store %85, %87 : i64, !llvm.ptr
%88 = arith.constant 0 : i32
%89 = arith.extsi %88 : i32 to i64
%90 = llvm.mlir.constant(1 : i64) : i64
%91 = llvm.alloca %90 x i64 : (i64) -> !llvm.ptr
llvm.store %89, %91 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%92 = llvm.load %91 : !llvm.ptr -> i64
%93 = arith.cmpi slt, %92, %arg0 : i64
cf.cond_br %93, ^bb19, ^bb20
^bb19:
%94 = llvm.load %87 : !llvm.ptr -> i64
%95 = arith.constant 3 : i32
%97 = arith.extsi %95 : i32 to i64
%96 = arith.muli %94, %97 : i64
llvm.store %96, %87 : i64, !llvm.ptr
%98 = llvm.load %91 : !llvm.ptr -> i64
%99 = arith.constant 1 : i32
%101 = arith.extsi %99 : i32 to i64
%100 = arith.addi %98, %101 : i64
llvm.store %100, %91 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%102 = llvm.load %87 : !llvm.ptr -> i64
%103 = llvm.mlir.addressof @g_limit_i : !llvm.ptr
llvm.store %102, %103 : i64, !llvm.ptr
%104 = arith.sitofp %arg0 : i64 to f64
%105 = llvm.mlir.addressof @g_log3 : !llvm.ptr
%106 = llvm.load %105 : !llvm.ptr -> f64
%107 = arith.mulf %104, %106 : f64
%108 = llvm.mlir.addressof @g_log_limit : !llvm.ptr
llvm.store %107, %108 : f64, !llvm.ptr
%109 = llvm.mlir.addressof @g_collect_flag : !llvm.ptr
llvm.store %arg1, %109 : i1, !llvm.ptr
%110 = arith.constant 0 : i32
%111 = arith.extsi %110 : i32 to i64
%112 = llvm.mlir.addressof @g_count_only : !llvm.ptr
llvm.store %111, %112 : i64, !llvm.ptr
%113 = arith.constant 0 : i32
%114 = arith.extsi %113 : i32 to i64
%115 = llvm.mlir.addressof @g_vcount : !llvm.ptr
llvm.store %114, %115 : i64, !llvm.ptr
%117 = arith.constant 0 : i32
%118 = arith.constant 1 : i32
%119 = arith.constant 0 : i32
%120 = arith.constant 0.0 : f32
%121 = arith.extsi %117 : i32 to i64
%122 = arith.extsi %118 : i32 to i64
%123 = arith.extsi %119 : i32 to i64
%124 = arith.extf %120 : f32 to f64
func.call @search(%121, %122, %123, %124) : (i64, i64, i64, f64) -> ()
%125 = llvm.mlir.addressof @g_count_only : !llvm.ptr
%126 = llvm.load %125 : !llvm.ptr -> i64
func.return %126 : i64
}
func.func @heapsort_i64(%arg0: !llvm.ptr, %arg1: i64) -> () {
%127 = arith.constant 2 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.divsi %arg1, %129 : i64
%130 = llvm.mlir.constant(1 : i64) : i64
%131 = llvm.alloca %130 x i64 : (i64) -> !llvm.ptr
llvm.store %128, %131 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%132 = llvm.load %131 : !llvm.ptr -> i64
%133 = arith.constant 0 : i32
%135 = arith.extsi %133 : i32 to i64
%134 = arith.cmpi sgt, %132, %135 : i64
cf.cond_br %134, ^bb22, ^bb23
^bb22:
%136 = llvm.load %131 : !llvm.ptr -> i64
%137 = arith.constant 1 : i32
%139 = arith.extsi %137 : i32 to i64
%138 = arith.subi %136, %139 : i64
llvm.store %138, %131 : i64, !llvm.ptr
%140 = llvm.load %131 : !llvm.ptr -> i64
%141 = llvm.mlir.constant(1 : i64) : i64
%142 = llvm.alloca %141 x i64 : (i64) -> !llvm.ptr
llvm.store %140, %142 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%143 = arith.constant 2 : i32
%144 = llvm.load %142 : !llvm.ptr -> i64
%146 = arith.extsi %143 : i32 to i64
%145 = arith.muli %146, %144 : i64
%147 = arith.constant 1 : i32
%149 = arith.extsi %147 : i32 to i64
%148 = arith.addi %145, %149 : i64
%150 = arith.cmpi slt, %148, %arg1 : i64
cf.cond_br %150, ^bb25, ^bb26
^bb25:
%151 = arith.constant 2 : i32
%152 = llvm.load %142 : !llvm.ptr -> i64
%154 = arith.extsi %151 : i32 to i64
%153 = arith.muli %154, %152 : i64
%155 = arith.constant 1 : i32
%157 = arith.extsi %155 : i32 to i64
%156 = arith.addi %153, %157 : i64
%158 = llvm.load %142 : !llvm.ptr -> i64
%159 = llvm.mlir.constant(1 : i64) : i64
%160 = llvm.alloca %159 x i64 : (i64) -> !llvm.ptr
llvm.store %158, %160 : i64, !llvm.ptr
%162 = llvm.load %160 : !llvm.ptr -> i64
%163 = llvm.getelementptr %arg0[%162] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%161 = llvm.load %163 : !llvm.ptr -> i64
%165 = llvm.getelementptr %arg0[%156] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%164 = llvm.load %165 : !llvm.ptr -> i64
%166 = arith.cmpi slt, %161, %164 : i64
cf.cond_br %166, ^bb27, ^bb28
^bb27:
llvm.store %156, %160 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%167 = arith.constant 1 : i32
%169 = arith.extsi %167 : i32 to i64
%168 = arith.addi %156, %169 : i64
%170 = arith.cmpi slt, %168, %arg1 : i64
cf.cond_br %170, ^bb30, ^bb31
^bb30:
%172 = llvm.load %160 : !llvm.ptr -> i64
%173 = llvm.getelementptr %arg0[%172] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%171 = llvm.load %173 : !llvm.ptr -> i64
%175 = arith.constant 1 : i32
%177 = arith.extsi %175 : i32 to i64
%176 = arith.addi %156, %177 : i64
%178 = llvm.getelementptr %arg0[%176] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%174 = llvm.load %178 : !llvm.ptr -> i64
%179 = arith.cmpi slt, %171, %174 : i64
cf.cond_br %179, ^bb33, ^bb34
^bb33:
%180 = arith.constant 1 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.addi %156, %182 : i64
llvm.store %181, %160 : i64, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%183 = llvm.load %160 : !llvm.ptr -> i64
%184 = llvm.load %142 : !llvm.ptr -> i64
%185 = arith.cmpi eq, %183, %184 : i64
cf.cond_br %185, ^bb36, ^bb37
^bb36:
cf.br ^bb26
^bb37:
cf.br ^bb38
^bb38:
%187 = llvm.load %142 : !llvm.ptr -> i64
%188 = llvm.getelementptr %arg0[%187] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%186 = llvm.load %188 : !llvm.ptr -> i64
%190 = llvm.load %160 : !llvm.ptr -> i64
%191 = llvm.getelementptr %arg0[%190] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%189 = llvm.load %191 : !llvm.ptr -> i64
%192 = llvm.load %142 : !llvm.ptr -> i64
%193 = llvm.getelementptr %arg0[%192] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %189, %193 : i64, !llvm.ptr
%194 = llvm.load %160 : !llvm.ptr -> i64
%195 = llvm.getelementptr %arg0[%194] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %186, %195 : i64, !llvm.ptr
%196 = llvm.load %160 : !llvm.ptr -> i64
llvm.store %196, %142 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
cf.br ^bb21
^bb23:
%197 = arith.constant 1 : i32
%199 = arith.extsi %197 : i32 to i64
%198 = arith.subi %arg1, %199 : i64
%200 = llvm.mlir.constant(1 : i64) : i64
%201 = llvm.alloca %200 x i64 : (i64) -> !llvm.ptr
llvm.store %198, %201 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%202 = llvm.load %201 : !llvm.ptr -> i64
%203 = arith.constant 0 : i32
%205 = arith.extsi %203 : i32 to i64
%204 = arith.cmpi sgt, %202, %205 : i64
cf.cond_br %204, ^bb40, ^bb41
^bb40:
%207 = arith.constant 0 : i32
%208 = arith.extsi %207 : i32 to i64
%209 = llvm.getelementptr %arg0[%208] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%206 = llvm.load %209 : !llvm.ptr -> i64
%211 = llvm.load %201 : !llvm.ptr -> i64
%212 = llvm.getelementptr %arg0[%211] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%210 = llvm.load %212 : !llvm.ptr -> i64
%213 = arith.constant 0 : i32
%214 = arith.extsi %213 : i32 to i64
%215 = llvm.getelementptr %arg0[%214] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %210, %215 : i64, !llvm.ptr
%216 = llvm.load %201 : !llvm.ptr -> i64
%217 = llvm.getelementptr %arg0[%216] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %206, %217 : i64, !llvm.ptr
%218 = arith.constant 0 : i32
%219 = arith.extsi %218 : i32 to i64
%220 = llvm.mlir.constant(1 : i64) : i64
%221 = llvm.alloca %220 x i64 : (i64) -> !llvm.ptr
llvm.store %219, %221 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%222 = arith.constant 2 : i32
%223 = llvm.load %221 : !llvm.ptr -> i64
%225 = arith.extsi %222 : i32 to i64
%224 = arith.muli %225, %223 : i64
%226 = arith.constant 1 : i32
%228 = arith.extsi %226 : i32 to i64
%227 = arith.addi %224, %228 : i64
%229 = llvm.load %201 : !llvm.ptr -> i64
%230 = arith.cmpi slt, %227, %229 : i64
cf.cond_br %230, ^bb43, ^bb44
^bb43:
%231 = arith.constant 2 : i32
%232 = llvm.load %221 : !llvm.ptr -> i64
%234 = arith.extsi %231 : i32 to i64
%233 = arith.muli %234, %232 : i64
%235 = arith.constant 1 : i32
%237 = arith.extsi %235 : i32 to i64
%236 = arith.addi %233, %237 : i64
%238 = llvm.load %221 : !llvm.ptr -> i64
%239 = llvm.mlir.constant(1 : i64) : i64
%240 = llvm.alloca %239 x i64 : (i64) -> !llvm.ptr
llvm.store %238, %240 : i64, !llvm.ptr
%242 = llvm.load %240 : !llvm.ptr -> i64
%243 = llvm.getelementptr %arg0[%242] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%241 = llvm.load %243 : !llvm.ptr -> i64
%245 = llvm.getelementptr %arg0[%236] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%244 = llvm.load %245 : !llvm.ptr -> i64
%246 = arith.cmpi slt, %241, %244 : i64
cf.cond_br %246, ^bb45, ^bb46
^bb45:
llvm.store %236, %240 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%247 = arith.constant 1 : i32
%249 = arith.extsi %247 : i32 to i64
%248 = arith.addi %236, %249 : i64
%250 = llvm.load %201 : !llvm.ptr -> i64
%251 = arith.cmpi slt, %248, %250 : i64
cf.cond_br %251, ^bb48, ^bb49
^bb48:
%253 = llvm.load %240 : !llvm.ptr -> i64
%254 = llvm.getelementptr %arg0[%253] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%252 = llvm.load %254 : !llvm.ptr -> i64
%256 = arith.constant 1 : i32
%258 = arith.extsi %256 : i32 to i64
%257 = arith.addi %236, %258 : i64
%259 = llvm.getelementptr %arg0[%257] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%255 = llvm.load %259 : !llvm.ptr -> i64
%260 = arith.cmpi slt, %252, %255 : i64
cf.cond_br %260, ^bb51, ^bb52
^bb51:
%261 = arith.constant 1 : i32
%263 = arith.extsi %261 : i32 to i64
%262 = arith.addi %236, %263 : i64
llvm.store %262, %240 : i64, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%264 = llvm.load %240 : !llvm.ptr -> i64
%265 = llvm.load %221 : !llvm.ptr -> i64
%266 = arith.cmpi eq, %264, %265 : i64
cf.cond_br %266, ^bb54, ^bb55
^bb54:
cf.br ^bb44
^bb55:
cf.br ^bb56
^bb56:
%268 = llvm.load %221 : !llvm.ptr -> i64
%269 = llvm.getelementptr %arg0[%268] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%267 = llvm.load %269 : !llvm.ptr -> i64
%271 = llvm.load %240 : !llvm.ptr -> i64
%272 = llvm.getelementptr %arg0[%271] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%270 = llvm.load %272 : !llvm.ptr -> i64
%273 = llvm.load %221 : !llvm.ptr -> i64
%274 = llvm.getelementptr %arg0[%273] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %270, %274 : i64, !llvm.ptr
%275 = llvm.load %240 : !llvm.ptr -> i64
%276 = llvm.getelementptr %arg0[%275] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %267, %276 : i64, !llvm.ptr
%277 = llvm.load %240 : !llvm.ptr -> i64
llvm.store %277, %221 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%278 = llvm.load %201 : !llvm.ptr -> i64
%279 = arith.constant 1 : i32
%281 = arith.extsi %279 : i32 to i64
%280 = arith.subi %278, %281 : i64
llvm.store %280, %201 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
func.return
}
func.func @mod_pow(%arg0: i64, %arg1: i64) -> i64 {
%282 = arith.constant 1 : i32
%283 = arith.extsi %282 : i32 to i64
%284 = llvm.mlir.constant(1 : i64) : i64
%285 = llvm.alloca %284 x i64 : (i64) -> !llvm.ptr
llvm.store %283, %285 : i64, !llvm.ptr
%286 = llvm.mlir.addressof @MOD : !llvm.ptr
%287 = llvm.load %286 : !llvm.ptr -> i64
%288 = arith.remsi %arg0, %287 : i64
%289 = llvm.mlir.constant(1 : i64) : i64
%290 = llvm.alloca %289 x i64 : (i64) -> !llvm.ptr
llvm.store %288, %290 : i64, !llvm.ptr
%291 = llvm.mlir.constant(1 : i64) : i64
%292 = llvm.alloca %291 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %292 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%293 = llvm.load %292 : !llvm.ptr -> i64
%294 = arith.constant 0 : i32
%296 = arith.extsi %294 : i32 to i64
%295 = arith.cmpi sgt, %293, %296 : i64
cf.cond_br %295, ^bb58, ^bb59
^bb58:
%297 = llvm.load %292 : !llvm.ptr -> i64
%298 = arith.constant 1 : i32
%300 = arith.extsi %298 : i32 to i64
%299 = arith.andi %297, %300 : i64
%301 = arith.constant 0 : i32
%303 = arith.extsi %301 : i32 to i64
%302 = arith.cmpi ne, %299, %303 : i64
cf.cond_br %302, ^bb60, ^bb61
^bb60:
%304 = llvm.load %285 : !llvm.ptr -> i64
%305 = arith.extsi %304 : i64 to i128
%306 = llvm.load %290 : !llvm.ptr -> i64
%307 = arith.extsi %306 : i64 to i128
%309 = arith.trunci %305 : i128 to i64
%310 = arith.trunci %307 : i128 to i64
%308 = arith.muli %309, %310 : i64
%311 = llvm.mlir.addressof @MOD : !llvm.ptr
%312 = llvm.load %311 : !llvm.ptr -> i64
%313 = arith.extsi %312 : i64 to i128
%315 = arith.trunci %313 : i128 to i64
%314 = arith.remsi %308, %315 : i64
llvm.store %314, %285 : i64, !llvm.ptr
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
%316 = llvm.load %290 : !llvm.ptr -> i64
%317 = arith.extsi %316 : i64 to i128
%318 = llvm.load %290 : !llvm.ptr -> i64
%319 = arith.extsi %318 : i64 to i128
%321 = arith.trunci %317 : i128 to i64
%322 = arith.trunci %319 : i128 to i64
%320 = arith.muli %321, %322 : i64
%323 = llvm.mlir.addressof @MOD : !llvm.ptr
%324 = llvm.load %323 : !llvm.ptr -> i64
%325 = arith.extsi %324 : i64 to i128
%327 = arith.trunci %325 : i128 to i64
%326 = arith.remsi %320, %327 : i64
llvm.store %326, %290 : i64, !llvm.ptr
%328 = llvm.load %292 : !llvm.ptr -> i64
%329 = arith.constant 1 : i32
%331 = arith.extsi %329 : i32 to i64
%330 = arith.shrsi %328, %331 : i64
llvm.store %330, %292 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
%332 = llvm.load %285 : !llvm.ptr -> i64
func.return %332 : i64
}
func.func @main() -> i32 {
%333 = arith.constant 300000 : i32
%334 = arith.extsi %333 : i32 to i64
%336 = arith.constant 1 : i32
%338 = arith.extsi %336 : i32 to i64
%337 = arith.addi %334, %338 : i64
%339 = arith.constant 1 : i32
%340 = arith.extsi %339 : i32 to i64
%335 = func.call @calloc(%337, %340) : (i64, i64) -> !llvm.ptr
%342 = arith.constant 8 : i32
%343 = arith.extsi %342 : i32 to i64
%341 = func.call @calloc(%334, %343) : (i64, i64) -> !llvm.ptr
%344 = llvm.mlir.addressof @g_primes : !llvm.ptr
llvm.store %341, %344 : !llvm.ptr, !llvm.ptr
%345 = arith.constant 0 : i32
%346 = arith.extsi %345 : i32 to i64
%347 = llvm.mlir.addressof @g_pc : !llvm.ptr
llvm.store %346, %347 : i64, !llvm.ptr
%348 = arith.constant 2 : i32
%349 = arith.extsi %348 : i32 to i64
%350 = llvm.mlir.constant(1 : i64) : i64
%351 = llvm.alloca %350 x i64 : (i64) -> !llvm.ptr
llvm.store %349, %351 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%352 = llvm.load %351 : !llvm.ptr -> i64
%353 = arith.cmpi sle, %352, %334 : i64
cf.cond_br %353, ^bb64, ^bb65
^bb64:
%355 = llvm.load %351 : !llvm.ptr -> i64
%356 = llvm.getelementptr %335[%355] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%354 = llvm.load %356 : !llvm.ptr -> i8
%357 = arith.constant 0 : i32
%359 = arith.extsi %354 : i8 to i32
%358 = arith.cmpi eq, %359, %357 : i32
cf.cond_br %358, ^bb66, ^bb67
^bb66:
%360 = llvm.load %351 : !llvm.ptr -> i64
%361 = llvm.mlir.addressof @g_primes : !llvm.ptr
%362 = llvm.load %361 : !llvm.ptr -> !llvm.ptr
%363 = llvm.mlir.addressof @g_pc : !llvm.ptr
%364 = llvm.load %363 : !llvm.ptr -> i64
%365 = llvm.getelementptr %362[%364] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %360, %365 : i64, !llvm.ptr
%366 = llvm.mlir.addressof @g_pc : !llvm.ptr
%367 = llvm.load %366 : !llvm.ptr -> i64
%368 = arith.constant 1 : i32
%370 = arith.extsi %368 : i32 to i64
%369 = arith.addi %367, %370 : i64
%371 = llvm.mlir.addressof @g_pc : !llvm.ptr
llvm.store %369, %371 : i64, !llvm.ptr
%372 = llvm.load %351 : !llvm.ptr -> i64
%373 = llvm.load %351 : !llvm.ptr -> i64
%374 = arith.muli %372, %373 : i64
%375 = arith.cmpi sle, %374, %334 : i64
cf.cond_br %375, ^bb69, ^bb70
^bb69:
%376 = llvm.load %351 : !llvm.ptr -> i64
%377 = llvm.load %351 : !llvm.ptr -> i64
%378 = arith.muli %376, %377 : 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 ^bb72
^bb72:
%381 = llvm.load %380 : !llvm.ptr -> i64
%382 = arith.cmpi sle, %381, %334 : i64
cf.cond_br %382, ^bb73, ^bb74
^bb73:
%383 = arith.constant 1 : i32
%384 = llvm.load %380 : !llvm.ptr -> i64
%385 = arith.trunci %383 : i32 to i8
%386 = llvm.getelementptr %335[%384] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %385, %386 : i8, !llvm.ptr
%387 = llvm.load %380 : !llvm.ptr -> i64
%388 = llvm.load %351 : !llvm.ptr -> i64
%389 = arith.addi %387, %388 : i64
llvm.store %389, %380 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
%390 = llvm.load %351 : !llvm.ptr -> i64
%391 = arith.constant 1 : i32
%393 = arith.extsi %391 : i32 to i64
%392 = arith.addi %390, %393 : i64
llvm.store %392, %351 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
%395 = llvm.mlir.addressof @g_pc : !llvm.ptr
%396 = llvm.load %395 : !llvm.ptr -> i64
%397 = arith.constant 8 : i32
%398 = arith.extsi %397 : i32 to i64
%394 = func.call @calloc(%396, %398) : (i64, i64) -> !llvm.ptr
%399 = llvm.mlir.addressof @g_prime_logs : !llvm.ptr
llvm.store %394, %399 : !llvm.ptr, !llvm.ptr
%400 = arith.constant 0 : i32
%401 = arith.extsi %400 : i32 to i64
%402 = llvm.mlir.constant(1 : i64) : i64
%403 = llvm.alloca %402 x i64 : (i64) -> !llvm.ptr
llvm.store %401, %403 : i64, !llvm.ptr
cf.br ^bb75
^bb75:
%404 = llvm.load %403 : !llvm.ptr -> i64
%405 = llvm.mlir.addressof @g_pc : !llvm.ptr
%406 = llvm.load %405 : !llvm.ptr -> i64
%407 = arith.cmpi slt, %404, %406 : i64
cf.cond_br %407, ^bb76, ^bb77
^bb76:
%409 = llvm.mlir.addressof @g_primes : !llvm.ptr
%410 = llvm.load %409 : !llvm.ptr -> !llvm.ptr
%411 = llvm.load %403 : !llvm.ptr -> i64
%412 = llvm.getelementptr %410[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%408 = llvm.load %412 : !llvm.ptr -> i64
%413 = arith.sitofp %408 : i64 to f64
%414 = math.log %413 : f64
%415 = llvm.mlir.addressof @g_prime_logs : !llvm.ptr
%416 = llvm.load %415 : !llvm.ptr -> !llvm.ptr
%417 = llvm.load %403 : !llvm.ptr -> i64
%418 = llvm.getelementptr %416[%417] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %414, %418 : f64, !llvm.ptr
%419 = llvm.load %403 : !llvm.ptr -> i64
%420 = arith.constant 1 : i32
%422 = arith.extsi %420 : i32 to i64
%421 = arith.addi %419, %422 : i64
llvm.store %421, %403 : i64, !llvm.ptr
cf.br ^bb75
^bb77:
%423 = arith.constant 3.0 : f32
%424 = math.log %423 : f32
%425 = arith.extf %424 : f32 to f64
%426 = llvm.mlir.addressof @g_log3 : !llvm.ptr
llvm.store %425, %426 : f64, !llvm.ptr
%427 = arith.constant 1 : i32
%428 = arith.extsi %427 : i32 to i64
%429 = llvm.mlir.constant(1 : i64) : i64
%430 = llvm.alloca %429 x i64 : (i64) -> !llvm.ptr
llvm.store %428, %430 : i64, !llvm.ptr
%431 = arith.constant 0 : i32
%432 = arith.extsi %431 : i32 to i64
%433 = llvm.mlir.constant(1 : i64) : i64
%434 = llvm.alloca %433 x i64 : (i64) -> !llvm.ptr
llvm.store %432, %434 : i64, !llvm.ptr
%435 = arith.constant 0 : i1
%436 = llvm.mlir.constant(1 : i64) : i64
%437 = llvm.alloca %436 x i1 : (i64) -> !llvm.ptr
llvm.store %435, %437 : i1, !llvm.ptr
cf.br ^bb78
^bb78:
%438 = llvm.load %437 : !llvm.ptr -> i1
%440 = arith.constant 1 : i1
%439 = arith.xori %438, %440 : i1
cf.cond_br %439, ^bb79, ^bb80
^bb79:
%442 = llvm.load %430 : !llvm.ptr -> i64
%443 = arith.constant 1 : i32
%445 = arith.extsi %443 : i32 to i64
%444 = arith.addi %442, %445 : i64
llvm.store %444, %430 : i64, !llvm.ptr
%447 = llvm.load %430 : !llvm.ptr -> i64
%448 = arith.constant 0 : i1
%446 = func.call @values_count(%447, %448) : (i64, i1) -> i64
%449 = llvm.mlir.addressof @TARGET_RANK : !llvm.ptr
%450 = llvm.load %449 : !llvm.ptr -> i64
%451 = arith.cmpi sge, %446, %450 : i64
cf.cond_br %451, ^bb81, ^bb82
^bb81:
%453 = arith.constant 8 : i32
%455 = arith.extsi %453 : i32 to i64
%454 = arith.muli %446, %455 : i64
%452 = func.call @malloc(%454) : (i64) -> !llvm.ptr
%456 = llvm.mlir.addressof @g_values : !llvm.ptr
llvm.store %452, %456 : !llvm.ptr, !llvm.ptr
%457 = llvm.mlir.addressof @g_vcap : !llvm.ptr
llvm.store %446, %457 : i64, !llvm.ptr
%459 = llvm.load %430 : !llvm.ptr -> i64
%460 = arith.constant 1 : i1
%458 = func.call @values_count(%459, %460) : (i64, i1) -> i64
%462 = llvm.mlir.addressof @g_values : !llvm.ptr
%463 = llvm.load %462 : !llvm.ptr -> !llvm.ptr
%464 = llvm.mlir.addressof @g_vcount : !llvm.ptr
%465 = llvm.load %464 : !llvm.ptr -> i64
func.call @heapsort_i64(%463, %465) : (!llvm.ptr, i64) -> ()
%467 = llvm.mlir.addressof @g_values : !llvm.ptr
%468 = llvm.load %467 : !llvm.ptr -> !llvm.ptr
%469 = llvm.mlir.addressof @TARGET_RANK : !llvm.ptr
%470 = llvm.load %469 : !llvm.ptr -> i64
%471 = arith.constant 1 : i32
%473 = arith.extsi %471 : i32 to i64
%472 = arith.subi %470, %473 : i64
%474 = llvm.getelementptr %468[%472] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%466 = llvm.load %474 : !llvm.ptr -> i64
llvm.store %466, %434 : i64, !llvm.ptr
%475 = arith.constant 1 : i1
llvm.store %475, %437 : i1, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
cf.br ^bb78
^bb80:
%476 = llvm.load %434 : !llvm.ptr -> i64
%477 = llvm.mlir.addressof @MOD : !llvm.ptr
%478 = llvm.load %477 : !llvm.ptr -> i64
%479 = arith.remsi %476, %478 : i64
%480 = arith.extsi %479 : i64 to i128
%482 = arith.constant 2 : i32
%483 = llvm.mlir.addressof @TARGET_OMEGA : !llvm.ptr
%484 = llvm.load %483 : !llvm.ptr -> i64
%485 = llvm.load %430 : !llvm.ptr -> i64
%486 = arith.subi %484, %485 : i64
%487 = arith.extsi %482 : i32 to i64
%481 = func.call @mod_pow(%487, %486) : (i64, i64) -> i64
%488 = arith.extsi %481 : i64 to i128
%490 = arith.trunci %480 : i128 to i64
%491 = arith.trunci %488 : i128 to i64
%489 = arith.muli %490, %491 : i64
%492 = llvm.mlir.addressof @MOD : !llvm.ptr
%493 = llvm.load %492 : !llvm.ptr -> i64
%494 = arith.extsi %493 : i64 to i128
%496 = arith.trunci %494 : i128 to i64
%495 = arith.remsi %489, %496 : i64
%497 = llvm.mlir.addressof @str_0 : !llvm.ptr
%498 = llvm.call @printf(%497, %495) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%335) : (!llvm.ptr) -> ()
%501 = llvm.mlir.addressof @g_primes : !llvm.ptr
%502 = llvm.load %501 : !llvm.ptr -> !llvm.ptr
func.call @free(%502) : (!llvm.ptr) -> ()
%504 = llvm.mlir.addressof @g_prime_logs : !llvm.ptr
%505 = llvm.load %504 : !llvm.ptr -> !llvm.ptr
func.call @free(%505) : (!llvm.ptr) -> ()
%507 = llvm.mlir.addressof @g_values : !llvm.ptr
%508 = llvm.load %507 : !llvm.ptr -> !llvm.ptr
func.call @free(%508) : (!llvm.ptr) -> ()
%509 = arith.constant 0 : i32
func.return %509 : i32
}
}