← All problems Problem 821
123-Separable: F(10^16). Smooth numbers (2^a * 3^b), holes, and DP over small values.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^3)?Space complexity O(1)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 821
# 123-Separable: F(10^16).
# Smooth numbers (2^a * 3^b), holes, and DP over small values.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function coprime6(m: i64) -> i64 {
if m <= 0 {
return 0
}
return m - m / 2 - m / 3 + m / 6
}
function sort_i64(arr: ptr<i64>, n: i64) -> void {
# insertion sort
let mut i: i64 = 1
while i < n {
let key: i64 = arr[i]
let mut j: i64 = i - 1
while j >= 0 && arr[j] > key {
arr[j + 1] = arr[j]
j = j - 1
}
arr[j + 1] = key
i = i + 1
}
}
function best_covered_small(limit: i64, vals: ptr<i64>, m: i64) -> i32 {
let mut best: i32 = 0
let S: ptr<i64> = calloc(32, 8)
let D: ptr<i64> = calloc(32, 8)
let T: ptr<i64> = calloc(32, 8)
let u: ptr<i64> = calloc(96, 8)
let mut mask: i64 = 0
while mask < (1 << m) {
let mut ns: i64 = 0
let mut nd: i64 = 0
let mut nt: i64 = 0
let mut ok: i32 = 1
for i in 0..m {
if ((mask >> i) & 1) != 0 {
let v: i64 = vals[i]
let dv: i64 = 2 * v
let tv: i64 = 3 * v
# check v not already in S, D, or T
for j in 0..nd {
if S[j] == v || D[j] == v || T[j] == v {
ok = 0
}
}
# check disjoint: dv, tv not in S
for j in 0..ns {
if S[j] == dv || S[j] == tv {
ok = 0
}
}
# check v, tv not in D
for j in 0..nd {
if D[j] == v || D[j] == tv {
ok = 0
}
}
# check v, dv not in T
for j in 0..nt {
if T[j] == v || T[j] == dv {
ok = 0
}
}
if ok == 0 {
break
}
S[ns] = v
ns = ns + 1
D[nd] = dv
nd = nd + 1
T[nt] = tv
nt = nt + 1
}
}
if ok != 0 {
# count unique <= limit
let mut nu: i64 = 0
for i in 0..ns {
u[nu] = S[i]
nu = nu + 1
}
for i in 0..nd {
u[nu] = D[i]
nu = nu + 1
}
for i in 0..nt {
u[nu] = T[i]
nu = nu + 1
}
sort_i64(u, nu)
let mut covered: i32 = 0
for i in 0..nu {
if u[i] <= limit {
if i == 0 || u[i] != u[i - 1] {
covered = covered + 1
}
}
}
if covered > best {
best = covered
}
}
mask = mask + 1
}
free(S)
free(D)
free(T)
free(u)
return best
}
function main() -> i32 {
let n: i64 = 10000000000000000
let smooth: ptr<i64> = calloc(4096, 8)
let mut ns: i64 = 0
let mut p2: i64 = 1
while p2 <= n {
let mut p3: i64 = 1
while p2 * p3 <= n {
smooth[ns] = p2 * p3
ns = ns + 1
p3 = p3 * 3
}
if p2 > n / 2 {
break
}
p2 = p2 * 2
}
sort_i64(smooth, ns)
# unique
let mut w: i64 = 0
for i in 0..ns {
if i == 0 || smooth[i] != smooth[i - 1] {
smooth[w] = smooth[i]
w = w + 1
}
}
ns = w
let small_H: ptr<i32> = calloc(64, 4)
let vals: ptr<i64> = calloc(32, 8)
for i in 0..ns {
if smooth[i] > 48 {
break
}
let mut m: i64 = 0
for j in 0..(i + 1) {
vals[m] = smooth[j]
m = m + 1
}
small_H[i] = best_covered_small(smooth[i], vals, m)
}
let holes: ptr<i64> = calloc(256, 8)
let mut nh: i64 = 0
# fixed list: 6, 24, 54
holes[nh] = 6
nh = nh + 1
holes[nh] = 24
nh = nh + 1
holes[nh] = 54
nh = nh + 1
let mut x: i64 = 384
while x <= n {
holes[nh] = x
nh = nh + 1
x = x * 8
}
x = 243
while x <= n {
holes[nh] = x
nh = nh + 1
x = x * 27
}
sort_i64(holes, nh)
let hole_prefix: ptr<i32> = calloc(4096, 4)
let mut j: i64 = 0
let mut cnt: i64 = 0
for i in 0..ns {
while j < nh && holes[j] <= smooth[i] {
cnt = cnt + 1
j = j + 1
}
hole_prefix[i] = cnt as i32
}
let mut ans: i64 = 0
for i in 0..ns {
let L: i64 = smooth[i]
let R: i64 = if i + 1 == ns { n } else { if smooth[i + 1] - 1 < n { smooth[i + 1] - 1 } else { n } }
let k_low: i64 = n / (R + 1) + 1
let k_high: i64 = n / L
if k_low > k_high {
continue
}
let count_k: i64 = coprime6(k_high) - coprime6(k_low - 1)
let H: i64 = if L <= 48 { small_H[i] as i64 } else { (i + 1) - (hole_prefix[i] as i64) }
ans = ans + H * count_k
}
printf("%lld\n", ans)
free(smooth)
free(small_H)
free(vals)
free(holes)
free(hole_prefix)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t coprime6_i64(int64_t m);
void sort_i64_ptr_i64_i64(int64_t* arr, int64_t n);
int32_t best_covered_small_i64_ptr_i64_i64(int64_t limit, int64_t* vals, int64_t m);
int32_t main(void);
int64_t coprime6_i64(int64_t m) {
if (m <= 0) {
return 0;
}
return (((m - FLOW_CHECKED_DIV((m), (2))) - FLOW_CHECKED_DIV((m), (3))) + FLOW_CHECKED_DIV((m), (6)));
}
void sort_i64_ptr_i64_i64(int64_t* arr, int64_t n) {
int64_t i = 1;
while (i < n) {
int64_t key = arr[i];
int64_t j = (i - 1);
while ((j >= 0 && arr[j] > key)) {
arr[(j + 1)] = arr[j];
j = (j - 1);
}
arr[(j + 1)] = key;
i = (i + 1);
}
}
int32_t best_covered_small_i64_ptr_i64_i64(int64_t limit, int64_t* vals, int64_t m) {
int32_t best = 0;
int64_t* S = (int64_t*)(calloc(32, 8));
int64_t* D = (int64_t*)(calloc(32, 8));
int64_t* T = (int64_t*)(calloc(32, 8));
int64_t* u = (int64_t*)(calloc(96, 8));
int64_t mask = 0;
while (mask < FLOW_CHECKED_SHL((1), (m))) {
int64_t ns = 0;
int64_t nd = 0;
int64_t nt = 0;
int32_t ok = 1;
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= m) ? i < m : i > m; i += (0 <= m) ? 1 : -1) {
if ((FLOW_CHECKED_SHR((mask), (i)) & 1) != 0) {
int64_t v = vals[i];
int64_t dv = (2 * v);
int64_t tv = (3 * v);
int32_t __flow_step_2 = 1;
for (int32_t j = 0; (0 <= nd) ? j < nd : j > nd; j += (0 <= nd) ? 1 : -1) {
if (((S[j] == v || D[j] == v) || T[j] == v)) {
ok = 0;
}
}
int32_t __flow_step_3 = 1;
for (int32_t j = 0; (0 <= ns) ? j < ns : j > ns; j += (0 <= ns) ? 1 : -1) {
if ((S[j] == dv || S[j] == tv)) {
ok = 0;
}
}
int32_t __flow_step_4 = 1;
for (int32_t j = 0; (0 <= nd) ? j < nd : j > nd; j += (0 <= nd) ? 1 : -1) {
if ((D[j] == v || D[j] == tv)) {
ok = 0;
}
}
int32_t __flow_step_5 = 1;
for (int32_t j = 0; (0 <= nt) ? j < nt : j > nt; j += (0 <= nt) ? 1 : -1) {
if ((T[j] == v || T[j] == dv)) {
ok = 0;
}
}
if (ok == 0) {
break;
}
S[ns] = v;
ns = (ns + 1);
D[nd] = dv;
nd = (nd + 1);
T[nt] = tv;
nt = (nt + 1);
}
}
if (ok != 0) {
int64_t nu = 0;
int32_t __flow_step_6 = 1;
for (int32_t i = 0; (0 <= ns) ? i < ns : i > ns; i += (0 <= ns) ? 1 : -1) {
u[nu] = S[i];
nu = (nu + 1);
}
int32_t __flow_step_7 = 1;
for (int32_t i = 0; (0 <= nd) ? i < nd : i > nd; i += (0 <= nd) ? 1 : -1) {
u[nu] = D[i];
nu = (nu + 1);
}
int32_t __flow_step_8 = 1;
for (int32_t i = 0; (0 <= nt) ? i < nt : i > nt; i += (0 <= nt) ? 1 : -1) {
u[nu] = T[i];
nu = (nu + 1);
}
sort_i64_ptr_i64_i64(u, nu);
int32_t covered = 0;
int32_t __flow_step_9 = 1;
for (int32_t i = 0; (0 <= nu) ? i < nu : i > nu; i += (0 <= nu) ? 1 : -1) {
if (u[i] <= limit) {
if ((i == 0 || u[i] != u[(i - 1)])) {
covered = (covered + 1);
}
}
}
if (covered > best) {
best = covered;
}
}
mask = (mask + 1);
}
free(S);
free(D);
free(T);
free(u);
return best;
}
int32_t main(void) {
int64_t n = 10000000000000000;
int64_t* smooth = (int64_t*)(calloc(4096, 8));
int64_t ns = 0;
int64_t p2 = 1;
while (p2 <= n) {
int64_t p3 = 1;
while ((p2 * p3) <= n) {
smooth[ns] = (p2 * p3);
ns = (ns + 1);
p3 = (p3 * 3);
}
if (p2 > FLOW_CHECKED_DIV((n), (2))) {
break;
}
p2 = (p2 * 2);
}
sort_i64_ptr_i64_i64(smooth, ns);
int64_t w = 0;
int32_t __flow_step_10 = 1;
for (int32_t i = 0; (0 <= ns) ? i < ns : i > ns; i += (0 <= ns) ? 1 : -1) {
if ((i == 0 || smooth[i] != smooth[(i - 1)])) {
smooth[w] = smooth[i];
w = (w + 1);
}
}
ns = w;
int32_t* small_H = (int32_t*)(calloc(64, 4));
int64_t* vals = (int64_t*)(calloc(32, 8));
int32_t __flow_step_11 = 1;
for (int32_t i = 0; (0 <= ns) ? i < ns : i > ns; i += (0 <= ns) ? 1 : -1) {
if (smooth[i] > 48) {
break;
}
int64_t m = 0;
int32_t __flow_step_12 = 1;
for (int32_t j = 0; (0 <= (i + 1)) ? j < (i + 1) : j > (i + 1); j += (0 <= (i + 1)) ? 1 : -1) {
vals[m] = smooth[j];
m = (m + 1);
}
small_H[i] = best_covered_small_i64_ptr_i64_i64(smooth[i], vals, m);
}
int64_t* holes = (int64_t*)(calloc(256, 8));
int64_t nh = 0;
holes[nh] = 6;
nh = (nh + 1);
holes[nh] = 24;
nh = (nh + 1);
holes[nh] = 54;
nh = (nh + 1);
int64_t x = 384;
while (x <= n) {
holes[nh] = x;
nh = (nh + 1);
x = (x * 8);
}
x = 243;
while (x <= n) {
holes[nh] = x;
nh = (nh + 1);
x = (x * 27);
}
sort_i64_ptr_i64_i64(holes, nh);
int32_t* hole_prefix = (int32_t*)(calloc(4096, 4));
int64_t j = 0;
int64_t cnt = 0;
int32_t __flow_step_13 = 1;
for (int32_t i = 0; (0 <= ns) ? i < ns : i > ns; i += (0 <= ns) ? 1 : -1) {
while ((j < nh && holes[j] <= smooth[i])) {
cnt = (cnt + 1);
j = (j + 1);
}
hole_prefix[i] = ((int32_t)(cnt));
}
int64_t ans = 0;
int32_t __flow_step_14 = 1;
for (int32_t i = 0; (0 <= ns) ? i < ns : i > ns; i += (0 <= ns) ? 1 : -1) {
int64_t L = smooth[i];
int64_t R = (((i + 1) == ns) ? (n) : ((((smooth[(i + 1)] - 1) < n) ? ((smooth[(i + 1)] - 1)) : (n))));
int64_t k_low = (FLOW_CHECKED_DIV((n), ((R + 1))) + 1);
int64_t k_high = FLOW_CHECKED_DIV((n), (L));
if (k_low > k_high) {
continue;
}
int64_t count_k = (coprime6_i64(k_high) - coprime6_i64((k_low - 1)));
int64_t H = ((L <= 48) ? (((int64_t)(small_H[i]))) : (((i + 1) - ((int64_t)(hole_prefix[i])))));
ans = (ans + (H * count_k));
}
printf("%lld\n", ans);
free(smooth);
free(small_H);
free(vals);
free(holes);
free(hole_prefix);
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 @coprime6(%arg0: i64) -> i64 {
%0 = arith.constant 0 : i32
%2 = arith.extsi %0 : i32 to i64
%1 = arith.cmpi sle, %arg0, %2 : i64
cf.cond_br %1, ^bb0, ^bb1
^bb0:
%3 = arith.constant 0 : i32
%4 = arith.extsi %3 : i32 to i64
func.return %4 : i64
^bb1:
cf.br ^bb2
^bb2:
%5 = arith.constant 2 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.divsi %arg0, %7 : i64
%8 = arith.subi %arg0, %6 : i64
%9 = arith.constant 3 : i32
%11 = arith.extsi %9 : i32 to i64
%10 = arith.divsi %arg0, %11 : i64
%12 = arith.subi %8, %10 : i64
%13 = arith.constant 6 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.divsi %arg0, %15 : i64
%16 = arith.addi %12, %14 : i64
func.return %16 : i64
}
func.func @sort_i64(%arg0: !llvm.ptr, %arg1: i64) -> () {
%17 = arith.constant 1 : i32
%18 = arith.extsi %17 : i32 to i64
%19 = llvm.mlir.constant(1 : i64) : i64
%20 = llvm.alloca %19 x i64 : (i64) -> !llvm.ptr
llvm.store %18, %20 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%21 = llvm.load %20 : !llvm.ptr -> i64
%22 = arith.cmpi slt, %21, %arg1 : i64
cf.cond_br %22, ^bb4, ^bb5
^bb4:
%24 = llvm.load %20 : !llvm.ptr -> i64
%25 = llvm.getelementptr %arg0[%24] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%23 = llvm.load %25 : !llvm.ptr -> i64
%26 = llvm.load %20 : !llvm.ptr -> i64
%27 = arith.constant 1 : i32
%29 = arith.extsi %27 : i32 to i64
%28 = arith.subi %26, %29 : i64
%30 = llvm.mlir.constant(1 : i64) : i64
%31 = llvm.alloca %30 x i64 : (i64) -> !llvm.ptr
llvm.store %28, %31 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%32 = llvm.load %31 : !llvm.ptr -> i64
%33 = arith.constant 0 : i32
%35 = arith.extsi %33 : i32 to i64
%34 = arith.cmpi sge, %32, %35 : i64
%36 = scf.if %34 -> (i1) {
%38 = llvm.load %31 : !llvm.ptr -> i64
%39 = llvm.getelementptr %arg0[%38] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%37 = llvm.load %39 : !llvm.ptr -> i64
%40 = arith.cmpi sgt, %37, %23 : i64
scf.yield %40 : i1
} else {
%41 = arith.constant false
scf.yield %41 : i1
}
cf.cond_br %36, ^bb7, ^bb8
^bb7:
%43 = llvm.load %31 : !llvm.ptr -> i64
%44 = llvm.getelementptr %arg0[%43] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%42 = llvm.load %44 : !llvm.ptr -> i64
%45 = llvm.load %31 : !llvm.ptr -> i64
%46 = arith.constant 1 : i32
%48 = arith.extsi %46 : i32 to i64
%47 = arith.addi %45, %48 : i64
%49 = llvm.getelementptr %arg0[%47] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %42, %49 : i64, !llvm.ptr
%50 = llvm.load %31 : !llvm.ptr -> i64
%51 = arith.constant 1 : i32
%53 = arith.extsi %51 : i32 to i64
%52 = arith.subi %50, %53 : i64
llvm.store %52, %31 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%54 = llvm.load %31 : !llvm.ptr -> i64
%55 = arith.constant 1 : i32
%57 = arith.extsi %55 : i32 to i64
%56 = arith.addi %54, %57 : i64
%58 = llvm.getelementptr %arg0[%56] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %23, %58 : i64, !llvm.ptr
%59 = llvm.load %20 : !llvm.ptr -> i64
%60 = arith.constant 1 : i32
%62 = arith.extsi %60 : i32 to i64
%61 = arith.addi %59, %62 : i64
llvm.store %61, %20 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
func.return
}
func.func @best_covered_small(%arg0: i64, %arg1: !llvm.ptr, %arg2: i64) -> i32 {
%63 = arith.constant 0 : i32
%64 = llvm.mlir.constant(1 : i64) : i64
%65 = llvm.alloca %64 x i32 : (i64) -> !llvm.ptr
llvm.store %63, %65 : i32, !llvm.ptr
%67 = arith.constant 32 : i32
%68 = arith.constant 8 : i32
%69 = arith.extsi %67 : i32 to i64
%70 = arith.extsi %68 : i32 to i64
%66 = func.call @calloc(%69, %70) : (i64, i64) -> !llvm.ptr
%72 = arith.constant 32 : i32
%73 = arith.constant 8 : i32
%74 = arith.extsi %72 : i32 to i64
%75 = arith.extsi %73 : i32 to i64
%71 = func.call @calloc(%74, %75) : (i64, i64) -> !llvm.ptr
%77 = arith.constant 32 : i32
%78 = arith.constant 8 : i32
%79 = arith.extsi %77 : i32 to i64
%80 = arith.extsi %78 : i32 to i64
%76 = func.call @calloc(%79, %80) : (i64, i64) -> !llvm.ptr
%82 = arith.constant 96 : i32
%83 = arith.constant 8 : i32
%84 = arith.extsi %82 : i32 to i64
%85 = arith.extsi %83 : i32 to i64
%81 = func.call @calloc(%84, %85) : (i64, i64) -> !llvm.ptr
%86 = arith.constant 0 : i32
%87 = arith.extsi %86 : i32 to i64
%88 = llvm.mlir.constant(1 : i64) : i64
%89 = llvm.alloca %88 x i64 : (i64) -> !llvm.ptr
llvm.store %87, %89 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%90 = llvm.load %89 : !llvm.ptr -> i64
%91 = arith.constant 1 : i32
%93 = arith.extsi %91 : i32 to i64
%92 = arith.shli %93, %arg2 : i64
%94 = arith.cmpi slt, %90, %92 : i64
cf.cond_br %94, ^bb10, ^bb11
^bb10:
%95 = arith.constant 0 : i32
%96 = arith.extsi %95 : i32 to i64
%97 = llvm.mlir.constant(1 : i64) : i64
%98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
llvm.store %96, %98 : i64, !llvm.ptr
%99 = arith.constant 0 : i32
%100 = arith.extsi %99 : i32 to i64
%101 = llvm.mlir.constant(1 : i64) : i64
%102 = llvm.alloca %101 x i64 : (i64) -> !llvm.ptr
llvm.store %100, %102 : i64, !llvm.ptr
%103 = arith.constant 0 : i32
%104 = arith.extsi %103 : i32 to i64
%105 = llvm.mlir.constant(1 : i64) : i64
%106 = llvm.alloca %105 x i64 : (i64) -> !llvm.ptr
llvm.store %104, %106 : i64, !llvm.ptr
%107 = arith.constant 1 : i32
%108 = llvm.mlir.constant(1 : i64) : i64
%109 = llvm.alloca %108 x i32 : (i64) -> !llvm.ptr
llvm.store %107, %109 : i32, !llvm.ptr
%110 = arith.constant 0 : i32
%111 = arith.index_cast %110 : i32 to index
%112 = arith.index_cast %arg2 : i32 to index
%114 = arith.constant 1 : index
%115 = arith.constant -1 : index
%116 = arith.cmpi sle, %111, %112 : index
%113 = arith.select %116, %114, %115 : index
cf.br ^bb12(%111 : index)
^bb12(%117: index):
%118 = arith.cmpi slt, %117, %112 : index
%119 = arith.cmpi sgt, %117, %112 : index
%120 = arith.select %116, %118, %119 : i1
cf.cond_br %120, ^bb13(%117 : index), ^bb14(%117 : index)
^bb13(%121: index):
%122 = llvm.load %89 : !llvm.ptr -> i64
%124 = arith.trunci %122 : i64 to i32
%125 = arith.index_cast %121 : index to i32
%123 = arith.shrsi %124, %125 : i32
%126 = arith.constant 1 : i32
%127 = arith.andi %123, %126 : i32
%128 = arith.constant 0 : i32
%129 = arith.cmpi ne, %127, %128 : i32
cf.cond_br %129, ^bb15, ^bb16
^bb15:
%131 = arith.index_cast %121 : index to i64
%132 = llvm.getelementptr %arg1[%131] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%130 = llvm.load %132 : !llvm.ptr -> i64
%133 = arith.constant 2 : i32
%135 = arith.extsi %133 : i32 to i64
%134 = arith.muli %135, %130 : i64
%136 = arith.constant 3 : i32
%138 = arith.extsi %136 : i32 to i64
%137 = arith.muli %138, %130 : i64
%139 = arith.constant 0 : i32
%140 = llvm.load %102 : !llvm.ptr -> i64
%141 = arith.index_cast %139 : i32 to index
%142 = arith.index_cast %140 : i32 to index
%144 = arith.constant 1 : index
%145 = arith.constant -1 : index
%146 = arith.cmpi sle, %141, %142 : index
%143 = arith.select %146, %144, %145 : index
cf.br ^bb18(%141 : index)
^bb18(%147: index):
%148 = arith.cmpi slt, %147, %142 : index
%149 = arith.cmpi sgt, %147, %142 : index
%150 = arith.select %146, %148, %149 : i1
cf.cond_br %150, ^bb19(%147 : index), ^bb20(%147 : index)
^bb19(%151: index):
%153 = arith.index_cast %151 : index to i64
%154 = llvm.getelementptr %66[%153] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%152 = llvm.load %154 : !llvm.ptr -> i64
%155 = arith.cmpi eq, %152, %130 : i64
%156 = scf.if %155 -> (i1) {
%157 = arith.constant true
scf.yield %157 : i1
} else {
%159 = arith.index_cast %151 : index to i64
%160 = llvm.getelementptr %71[%159] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%158 = llvm.load %160 : !llvm.ptr -> i64
%161 = arith.cmpi eq, %158, %130 : i64
scf.yield %161 : i1
}
%162 = scf.if %156 -> (i1) {
%163 = arith.constant true
scf.yield %163 : i1
} else {
%165 = arith.index_cast %151 : index to i64
%166 = llvm.getelementptr %76[%165] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%164 = llvm.load %166 : !llvm.ptr -> i64
%167 = arith.cmpi eq, %164, %130 : i64
scf.yield %167 : i1
}
cf.cond_br %162, ^bb21, ^bb22
^bb21:
%168 = arith.constant 0 : i32
llvm.store %168, %109 : i32, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%169 = arith.addi %151, %143 : index
cf.br ^bb18(%169 : index)
^bb20(%170: index):
%171 = arith.constant 0 : i32
%172 = llvm.load %98 : !llvm.ptr -> i64
%173 = arith.index_cast %171 : i32 to index
%174 = arith.index_cast %172 : i32 to index
%176 = arith.constant 1 : index
%177 = arith.constant -1 : index
%178 = arith.cmpi sle, %173, %174 : index
%175 = arith.select %178, %176, %177 : index
cf.br ^bb24(%173 : index)
^bb24(%179: index):
%180 = arith.cmpi slt, %179, %174 : index
%181 = arith.cmpi sgt, %179, %174 : index
%182 = arith.select %178, %180, %181 : i1
cf.cond_br %182, ^bb25(%179 : index), ^bb26(%179 : index)
^bb25(%183: index):
%185 = arith.index_cast %183 : index to i64
%186 = llvm.getelementptr %66[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%184 = llvm.load %186 : !llvm.ptr -> i64
%187 = arith.cmpi eq, %184, %134 : i64
%188 = scf.if %187 -> (i1) {
%189 = arith.constant true
scf.yield %189 : i1
} else {
%191 = arith.index_cast %183 : index to i64
%192 = llvm.getelementptr %66[%191] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%190 = llvm.load %192 : !llvm.ptr -> i64
%193 = arith.cmpi eq, %190, %137 : i64
scf.yield %193 : i1
}
cf.cond_br %188, ^bb27, ^bb28
^bb27:
%194 = arith.constant 0 : i32
llvm.store %194, %109 : i32, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%195 = arith.addi %183, %175 : index
cf.br ^bb24(%195 : index)
^bb26(%196: index):
%197 = arith.constant 0 : i32
%198 = llvm.load %102 : !llvm.ptr -> i64
%199 = arith.index_cast %197 : i32 to index
%200 = arith.index_cast %198 : i32 to index
%202 = arith.constant 1 : index
%203 = arith.constant -1 : index
%204 = arith.cmpi sle, %199, %200 : index
%201 = arith.select %204, %202, %203 : index
cf.br ^bb30(%199 : index)
^bb30(%205: index):
%206 = arith.cmpi slt, %205, %200 : index
%207 = arith.cmpi sgt, %205, %200 : index
%208 = arith.select %204, %206, %207 : i1
cf.cond_br %208, ^bb31(%205 : index), ^bb32(%205 : index)
^bb31(%209: index):
%211 = arith.index_cast %209 : index to i64
%212 = llvm.getelementptr %71[%211] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%210 = llvm.load %212 : !llvm.ptr -> i64
%213 = arith.cmpi eq, %210, %130 : i64
%214 = scf.if %213 -> (i1) {
%215 = arith.constant true
scf.yield %215 : i1
} else {
%217 = arith.index_cast %209 : index to i64
%218 = llvm.getelementptr %71[%217] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%216 = llvm.load %218 : !llvm.ptr -> i64
%219 = arith.cmpi eq, %216, %137 : i64
scf.yield %219 : i1
}
cf.cond_br %214, ^bb33, ^bb34
^bb33:
%220 = arith.constant 0 : i32
llvm.store %220, %109 : i32, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%221 = arith.addi %209, %201 : index
cf.br ^bb30(%221 : index)
^bb32(%222: index):
%223 = arith.constant 0 : i32
%224 = llvm.load %106 : !llvm.ptr -> i64
%225 = arith.index_cast %223 : i32 to index
%226 = arith.index_cast %224 : i32 to index
%228 = arith.constant 1 : index
%229 = arith.constant -1 : index
%230 = arith.cmpi sle, %225, %226 : index
%227 = arith.select %230, %228, %229 : index
cf.br ^bb36(%225 : index)
^bb36(%231: index):
%232 = arith.cmpi slt, %231, %226 : index
%233 = arith.cmpi sgt, %231, %226 : index
%234 = arith.select %230, %232, %233 : i1
cf.cond_br %234, ^bb37(%231 : index), ^bb38(%231 : index)
^bb37(%235: index):
%237 = arith.index_cast %235 : index to i64
%238 = llvm.getelementptr %76[%237] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%236 = llvm.load %238 : !llvm.ptr -> i64
%239 = arith.cmpi eq, %236, %130 : i64
%240 = scf.if %239 -> (i1) {
%241 = arith.constant true
scf.yield %241 : i1
} else {
%243 = arith.index_cast %235 : index to i64
%244 = llvm.getelementptr %76[%243] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%242 = llvm.load %244 : !llvm.ptr -> i64
%245 = arith.cmpi eq, %242, %134 : i64
scf.yield %245 : i1
}
cf.cond_br %240, ^bb39, ^bb40
^bb39:
%246 = arith.constant 0 : i32
llvm.store %246, %109 : i32, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%247 = arith.addi %235, %227 : index
cf.br ^bb36(%247 : index)
^bb38(%248: index):
%249 = llvm.load %109 : !llvm.ptr -> i32
%250 = arith.constant 0 : i32
%251 = arith.cmpi eq, %249, %250 : i32
cf.cond_br %251, ^bb42, ^bb43
^bb42:
cf.br ^bb14(%121 : index)
^bb43:
cf.br ^bb44
^bb44:
%252 = llvm.load %98 : !llvm.ptr -> i64
%253 = llvm.getelementptr %66[%252] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %130, %253 : i64, !llvm.ptr
%254 = llvm.load %98 : !llvm.ptr -> i64
%255 = arith.constant 1 : i32
%257 = arith.extsi %255 : i32 to i64
%256 = arith.addi %254, %257 : i64
llvm.store %256, %98 : i64, !llvm.ptr
%258 = llvm.load %102 : !llvm.ptr -> i64
%259 = llvm.getelementptr %71[%258] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %134, %259 : i64, !llvm.ptr
%260 = llvm.load %102 : !llvm.ptr -> i64
%261 = arith.constant 1 : i32
%263 = arith.extsi %261 : i32 to i64
%262 = arith.addi %260, %263 : i64
llvm.store %262, %102 : i64, !llvm.ptr
%264 = llvm.load %106 : !llvm.ptr -> i64
%265 = llvm.getelementptr %76[%264] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %137, %265 : i64, !llvm.ptr
%266 = llvm.load %106 : !llvm.ptr -> i64
%267 = arith.constant 1 : i32
%269 = arith.extsi %267 : i32 to i64
%268 = arith.addi %266, %269 : i64
llvm.store %268, %106 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%270 = arith.addi %121, %113 : index
cf.br ^bb12(%270 : index)
^bb14(%271: index):
%272 = llvm.load %109 : !llvm.ptr -> i32
%273 = arith.constant 0 : i32
%274 = arith.cmpi ne, %272, %273 : i32
cf.cond_br %274, ^bb45, ^bb46
^bb45:
%275 = arith.constant 0 : i32
%276 = arith.extsi %275 : i32 to i64
%277 = llvm.mlir.constant(1 : i64) : i64
%278 = llvm.alloca %277 x i64 : (i64) -> !llvm.ptr
llvm.store %276, %278 : i64, !llvm.ptr
%279 = arith.constant 0 : i32
%280 = llvm.load %98 : !llvm.ptr -> i64
%281 = arith.index_cast %279 : i32 to index
%282 = arith.index_cast %280 : i32 to index
%284 = arith.constant 1 : index
%285 = arith.constant -1 : index
%286 = arith.cmpi sle, %281, %282 : index
%283 = arith.select %286, %284, %285 : index
cf.br ^bb48(%281 : index)
^bb48(%287: index):
%288 = arith.cmpi slt, %287, %282 : index
%289 = arith.cmpi sgt, %287, %282 : index
%290 = arith.select %286, %288, %289 : i1
cf.cond_br %290, ^bb49(%287 : index), ^bb50(%287 : index)
^bb49(%291: index):
%293 = arith.index_cast %291 : index to i64
%294 = llvm.getelementptr %66[%293] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%292 = llvm.load %294 : !llvm.ptr -> i64
%295 = llvm.load %278 : !llvm.ptr -> i64
%296 = llvm.getelementptr %81[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %292, %296 : i64, !llvm.ptr
%297 = llvm.load %278 : !llvm.ptr -> i64
%298 = arith.constant 1 : i32
%300 = arith.extsi %298 : i32 to i64
%299 = arith.addi %297, %300 : i64
llvm.store %299, %278 : i64, !llvm.ptr
%301 = arith.addi %291, %283 : index
cf.br ^bb48(%301 : index)
^bb50(%302: index):
%303 = arith.constant 0 : i32
%304 = llvm.load %102 : !llvm.ptr -> i64
%305 = arith.index_cast %303 : i32 to index
%306 = arith.index_cast %304 : i32 to index
%308 = arith.constant 1 : index
%309 = arith.constant -1 : index
%310 = arith.cmpi sle, %305, %306 : index
%307 = arith.select %310, %308, %309 : index
cf.br ^bb51(%305 : index)
^bb51(%311: index):
%312 = arith.cmpi slt, %311, %306 : index
%313 = arith.cmpi sgt, %311, %306 : index
%314 = arith.select %310, %312, %313 : i1
cf.cond_br %314, ^bb52(%311 : index), ^bb53(%311 : index)
^bb52(%315: index):
%317 = arith.index_cast %315 : index to i64
%318 = llvm.getelementptr %71[%317] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%316 = llvm.load %318 : !llvm.ptr -> i64
%319 = llvm.load %278 : !llvm.ptr -> i64
%320 = llvm.getelementptr %81[%319] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %316, %320 : i64, !llvm.ptr
%321 = llvm.load %278 : !llvm.ptr -> i64
%322 = arith.constant 1 : i32
%324 = arith.extsi %322 : i32 to i64
%323 = arith.addi %321, %324 : i64
llvm.store %323, %278 : i64, !llvm.ptr
%325 = arith.addi %315, %307 : index
cf.br ^bb51(%325 : index)
^bb53(%326: index):
%327 = arith.constant 0 : i32
%328 = llvm.load %106 : !llvm.ptr -> i64
%329 = arith.index_cast %327 : i32 to index
%330 = arith.index_cast %328 : i32 to index
%332 = arith.constant 1 : index
%333 = arith.constant -1 : index
%334 = arith.cmpi sle, %329, %330 : index
%331 = arith.select %334, %332, %333 : index
cf.br ^bb54(%329 : index)
^bb54(%335: index):
%336 = arith.cmpi slt, %335, %330 : index
%337 = arith.cmpi sgt, %335, %330 : index
%338 = arith.select %334, %336, %337 : i1
cf.cond_br %338, ^bb55(%335 : index), ^bb56(%335 : index)
^bb55(%339: index):
%341 = arith.index_cast %339 : index to i64
%342 = llvm.getelementptr %76[%341] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%340 = llvm.load %342 : !llvm.ptr -> i64
%343 = llvm.load %278 : !llvm.ptr -> i64
%344 = llvm.getelementptr %81[%343] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %340, %344 : i64, !llvm.ptr
%345 = llvm.load %278 : !llvm.ptr -> i64
%346 = arith.constant 1 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.addi %345, %348 : i64
llvm.store %347, %278 : i64, !llvm.ptr
%349 = arith.addi %339, %331 : index
cf.br ^bb54(%349 : index)
^bb56(%350: index):
%352 = llvm.load %278 : !llvm.ptr -> i64
func.call @sort_i64(%81, %352) : (!llvm.ptr, i64) -> ()
%353 = arith.constant 0 : i32
%354 = llvm.mlir.constant(1 : i64) : i64
%355 = llvm.alloca %354 x i32 : (i64) -> !llvm.ptr
llvm.store %353, %355 : i32, !llvm.ptr
%356 = arith.constant 0 : i32
%357 = llvm.load %278 : !llvm.ptr -> i64
%358 = arith.index_cast %356 : i32 to index
%359 = arith.index_cast %357 : i32 to index
%361 = arith.constant 1 : index
%362 = arith.constant -1 : index
%363 = arith.cmpi sle, %358, %359 : index
%360 = arith.select %363, %361, %362 : index
cf.br ^bb57(%358 : index)
^bb57(%364: index):
%365 = arith.cmpi slt, %364, %359 : index
%366 = arith.cmpi sgt, %364, %359 : index
%367 = arith.select %363, %365, %366 : i1
cf.cond_br %367, ^bb58(%364 : index), ^bb59(%364 : index)
^bb58(%368: index):
%370 = arith.index_cast %368 : index to i64
%371 = llvm.getelementptr %81[%370] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%369 = llvm.load %371 : !llvm.ptr -> i64
%372 = arith.cmpi sle, %369, %arg0 : i64
cf.cond_br %372, ^bb60, ^bb61
^bb60:
%373 = arith.constant 0 : i32
%375 = arith.index_cast %368 : index to i32
%374 = arith.cmpi eq, %375, %373 : i32
%376 = scf.if %374 -> (i1) {
%377 = arith.constant true
scf.yield %377 : i1
} else {
%379 = arith.index_cast %368 : index to i64
%380 = llvm.getelementptr %81[%379] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%378 = llvm.load %380 : !llvm.ptr -> i64
%382 = arith.constant 1 : i32
%384 = arith.index_cast %368 : index to i32
%383 = arith.subi %384, %382 : i32
%385 = arith.extsi %383 : i32 to i64
%386 = llvm.getelementptr %81[%385] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%381 = llvm.load %386 : !llvm.ptr -> i64
%387 = arith.cmpi ne, %378, %381 : i64
scf.yield %387 : i1
}
cf.cond_br %376, ^bb63, ^bb64
^bb63:
%388 = llvm.load %355 : !llvm.ptr -> i32
%389 = arith.constant 1 : i32
%390 = arith.addi %388, %389 : i32
llvm.store %390, %355 : i32, !llvm.ptr
cf.br ^bb65
^bb64:
cf.br ^bb65
^bb65:
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
%391 = arith.addi %368, %360 : index
cf.br ^bb57(%391 : index)
^bb59(%392: index):
%393 = llvm.load %355 : !llvm.ptr -> i32
%394 = llvm.load %65 : !llvm.ptr -> i32
%395 = arith.cmpi sgt, %393, %394 : i32
cf.cond_br %395, ^bb66, ^bb67
^bb66:
%396 = llvm.load %355 : !llvm.ptr -> i32
llvm.store %396, %65 : i32, !llvm.ptr
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%397 = llvm.load %89 : !llvm.ptr -> i64
%398 = arith.constant 1 : i32
%400 = arith.extsi %398 : i32 to i64
%399 = arith.addi %397, %400 : i64
llvm.store %399, %89 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
func.call @free(%66) : (!llvm.ptr) -> ()
func.call @free(%71) : (!llvm.ptr) -> ()
func.call @free(%76) : (!llvm.ptr) -> ()
func.call @free(%81) : (!llvm.ptr) -> ()
%405 = llvm.load %65 : !llvm.ptr -> i32
func.return %405 : i32
}
func.func @main() -> i32 {
%406 = arith.constant 9999995705032704 : i32
%407 = arith.extsi %406 : i32 to i64
%409 = arith.constant 4096 : i32
%410 = arith.constant 8 : i32
%411 = arith.extsi %409 : i32 to i64
%412 = arith.extsi %410 : i32 to i64
%408 = func.call @calloc(%411, %412) : (i64, i64) -> !llvm.ptr
%413 = arith.constant 0 : i32
%414 = arith.extsi %413 : i32 to i64
%415 = llvm.mlir.constant(1 : i64) : i64
%416 = llvm.alloca %415 x i64 : (i64) -> !llvm.ptr
llvm.store %414, %416 : i64, !llvm.ptr
%417 = arith.constant 1 : i32
%418 = arith.extsi %417 : i32 to i64
%419 = llvm.mlir.constant(1 : i64) : i64
%420 = llvm.alloca %419 x i64 : (i64) -> !llvm.ptr
llvm.store %418, %420 : i64, !llvm.ptr
cf.br ^bb69
^bb69:
%421 = llvm.load %420 : !llvm.ptr -> i64
%422 = arith.cmpi sle, %421, %407 : i64
cf.cond_br %422, ^bb70, ^bb71
^bb70:
%423 = arith.constant 1 : i32
%424 = arith.extsi %423 : i32 to i64
%425 = llvm.mlir.constant(1 : i64) : i64
%426 = llvm.alloca %425 x i64 : (i64) -> !llvm.ptr
llvm.store %424, %426 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%427 = llvm.load %420 : !llvm.ptr -> i64
%428 = llvm.load %426 : !llvm.ptr -> i64
%429 = arith.muli %427, %428 : i64
%430 = arith.cmpi sle, %429, %407 : i64
cf.cond_br %430, ^bb73, ^bb74
^bb73:
%431 = llvm.load %420 : !llvm.ptr -> i64
%432 = llvm.load %426 : !llvm.ptr -> i64
%433 = arith.muli %431, %432 : i64
%434 = llvm.load %416 : !llvm.ptr -> i64
%435 = llvm.getelementptr %408[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %433, %435 : i64, !llvm.ptr
%436 = llvm.load %416 : !llvm.ptr -> i64
%437 = arith.constant 1 : i32
%439 = arith.extsi %437 : i32 to i64
%438 = arith.addi %436, %439 : i64
llvm.store %438, %416 : i64, !llvm.ptr
%440 = llvm.load %426 : !llvm.ptr -> i64
%441 = arith.constant 3 : i32
%443 = arith.extsi %441 : i32 to i64
%442 = arith.muli %440, %443 : i64
llvm.store %442, %426 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
%444 = llvm.load %420 : !llvm.ptr -> i64
%445 = arith.constant 2 : i32
%447 = arith.extsi %445 : i32 to i64
%446 = arith.divsi %407, %447 : i64
%448 = arith.cmpi sgt, %444, %446 : i64
cf.cond_br %448, ^bb75, ^bb76
^bb75:
cf.br ^bb71
^bb76:
cf.br ^bb77
^bb77:
%449 = llvm.load %420 : !llvm.ptr -> i64
%450 = arith.constant 2 : i32
%452 = arith.extsi %450 : i32 to i64
%451 = arith.muli %449, %452 : i64
llvm.store %451, %420 : i64, !llvm.ptr
cf.br ^bb69
^bb71:
%454 = llvm.load %416 : !llvm.ptr -> i64
func.call @sort_i64(%408, %454) : (!llvm.ptr, i64) -> ()
%455 = arith.constant 0 : i32
%456 = arith.extsi %455 : i32 to i64
%457 = llvm.mlir.constant(1 : i64) : i64
%458 = llvm.alloca %457 x i64 : (i64) -> !llvm.ptr
llvm.store %456, %458 : i64, !llvm.ptr
%459 = arith.constant 0 : i32
%460 = llvm.load %416 : !llvm.ptr -> i64
%461 = arith.index_cast %459 : i32 to index
%462 = arith.index_cast %460 : i32 to index
%464 = arith.constant 1 : index
%465 = arith.constant -1 : index
%466 = arith.cmpi sle, %461, %462 : index
%463 = arith.select %466, %464, %465 : index
cf.br ^bb78(%461 : index)
^bb78(%467: index):
%468 = arith.cmpi slt, %467, %462 : index
%469 = arith.cmpi sgt, %467, %462 : index
%470 = arith.select %466, %468, %469 : i1
cf.cond_br %470, ^bb79(%467 : index), ^bb80(%467 : index)
^bb79(%471: index):
%472 = arith.constant 0 : i32
%474 = arith.index_cast %471 : index to i32
%473 = arith.cmpi eq, %474, %472 : i32
%475 = scf.if %473 -> (i1) {
%476 = arith.constant true
scf.yield %476 : i1
} else {
%478 = arith.index_cast %471 : index to i64
%479 = llvm.getelementptr %408[%478] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%477 = llvm.load %479 : !llvm.ptr -> i64
%481 = arith.constant 1 : i32
%483 = arith.index_cast %471 : index to i32
%482 = arith.subi %483, %481 : i32
%484 = arith.extsi %482 : i32 to i64
%485 = llvm.getelementptr %408[%484] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%480 = llvm.load %485 : !llvm.ptr -> i64
%486 = arith.cmpi ne, %477, %480 : i64
scf.yield %486 : i1
}
cf.cond_br %475, ^bb81, ^bb82
^bb81:
%488 = arith.index_cast %471 : index to i64
%489 = llvm.getelementptr %408[%488] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%487 = llvm.load %489 : !llvm.ptr -> i64
%490 = llvm.load %458 : !llvm.ptr -> i64
%491 = llvm.getelementptr %408[%490] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %487, %491 : i64, !llvm.ptr
%492 = llvm.load %458 : !llvm.ptr -> i64
%493 = arith.constant 1 : i32
%495 = arith.extsi %493 : i32 to i64
%494 = arith.addi %492, %495 : i64
llvm.store %494, %458 : i64, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%496 = arith.addi %471, %463 : index
cf.br ^bb78(%496 : index)
^bb80(%497: index):
%498 = llvm.load %458 : !llvm.ptr -> i64
llvm.store %498, %416 : i64, !llvm.ptr
%500 = arith.constant 64 : i32
%501 = arith.constant 4 : i32
%502 = arith.extsi %500 : i32 to i64
%503 = arith.extsi %501 : i32 to i64
%499 = func.call @calloc(%502, %503) : (i64, i64) -> !llvm.ptr
%505 = arith.constant 32 : i32
%506 = arith.constant 8 : i32
%507 = arith.extsi %505 : i32 to i64
%508 = arith.extsi %506 : i32 to i64
%504 = func.call @calloc(%507, %508) : (i64, i64) -> !llvm.ptr
%509 = arith.constant 0 : i32
%510 = llvm.load %416 : !llvm.ptr -> i64
%511 = arith.index_cast %509 : i32 to index
%512 = arith.index_cast %510 : i32 to index
%514 = arith.constant 1 : index
%515 = arith.constant -1 : index
%516 = arith.cmpi sle, %511, %512 : index
%513 = arith.select %516, %514, %515 : index
cf.br ^bb84(%511 : index)
^bb84(%517: index):
%518 = arith.cmpi slt, %517, %512 : index
%519 = arith.cmpi sgt, %517, %512 : index
%520 = arith.select %516, %518, %519 : i1
cf.cond_br %520, ^bb85(%517 : index), ^bb86(%517 : index)
^bb85(%521: index):
%523 = arith.index_cast %521 : index to i64
%524 = llvm.getelementptr %408[%523] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%522 = llvm.load %524 : !llvm.ptr -> i64
%525 = arith.constant 48 : i32
%527 = arith.extsi %525 : i32 to i64
%526 = arith.cmpi sgt, %522, %527 : i64
cf.cond_br %526, ^bb87, ^bb88
^bb87:
cf.br ^bb86(%521 : index)
^bb88:
cf.br ^bb89
^bb89:
%528 = arith.constant 0 : i32
%529 = arith.extsi %528 : i32 to i64
%530 = llvm.mlir.constant(1 : i64) : i64
%531 = llvm.alloca %530 x i64 : (i64) -> !llvm.ptr
llvm.store %529, %531 : i64, !llvm.ptr
%532 = arith.constant 0 : i32
%533 = arith.constant 1 : i32
%535 = arith.index_cast %521 : index to i32
%534 = arith.addi %535, %533 : i32
%536 = arith.index_cast %532 : i32 to index
%537 = arith.index_cast %534 : i32 to index
%539 = arith.constant 1 : index
%540 = arith.constant -1 : index
%541 = arith.cmpi sle, %536, %537 : index
%538 = arith.select %541, %539, %540 : index
cf.br ^bb90(%536 : index)
^bb90(%542: index):
%543 = arith.cmpi slt, %542, %537 : index
%544 = arith.cmpi sgt, %542, %537 : index
%545 = arith.select %541, %543, %544 : i1
cf.cond_br %545, ^bb91(%542 : index), ^bb92(%542 : index)
^bb91(%546: index):
%548 = arith.index_cast %546 : index to i64
%549 = llvm.getelementptr %408[%548] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%547 = llvm.load %549 : !llvm.ptr -> i64
%550 = llvm.load %531 : !llvm.ptr -> i64
%551 = llvm.getelementptr %504[%550] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %547, %551 : i64, !llvm.ptr
%552 = llvm.load %531 : !llvm.ptr -> i64
%553 = arith.constant 1 : i32
%555 = arith.extsi %553 : i32 to i64
%554 = arith.addi %552, %555 : i64
llvm.store %554, %531 : i64, !llvm.ptr
%556 = arith.addi %546, %538 : index
cf.br ^bb90(%556 : index)
^bb92(%557: index):
%560 = arith.index_cast %521 : index to i64
%561 = llvm.getelementptr %408[%560] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%559 = llvm.load %561 : !llvm.ptr -> i64
%562 = llvm.load %531 : !llvm.ptr -> i64
%558 = func.call @best_covered_small(%559, %504, %562) : (i64, !llvm.ptr, i64) -> i32
%563 = arith.index_cast %521 : index to i64
%564 = llvm.getelementptr %499[%563] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %558, %564 : i32, !llvm.ptr
%565 = arith.addi %521, %513 : index
cf.br ^bb84(%565 : index)
^bb86(%566: index):
%568 = arith.constant 256 : i32
%569 = arith.constant 8 : i32
%570 = arith.extsi %568 : i32 to i64
%571 = arith.extsi %569 : i32 to i64
%567 = func.call @calloc(%570, %571) : (i64, i64) -> !llvm.ptr
%572 = arith.constant 0 : i32
%573 = arith.extsi %572 : i32 to i64
%574 = llvm.mlir.constant(1 : i64) : i64
%575 = llvm.alloca %574 x i64 : (i64) -> !llvm.ptr
llvm.store %573, %575 : i64, !llvm.ptr
%576 = arith.constant 6 : i32
%577 = llvm.load %575 : !llvm.ptr -> i64
%578 = arith.extsi %576 : i32 to i64
%579 = llvm.getelementptr %567[%577] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %578, %579 : i64, !llvm.ptr
%580 = llvm.load %575 : !llvm.ptr -> i64
%581 = arith.constant 1 : i32
%583 = arith.extsi %581 : i32 to i64
%582 = arith.addi %580, %583 : i64
llvm.store %582, %575 : i64, !llvm.ptr
%584 = arith.constant 24 : i32
%585 = llvm.load %575 : !llvm.ptr -> i64
%586 = arith.extsi %584 : i32 to i64
%587 = llvm.getelementptr %567[%585] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %586, %587 : i64, !llvm.ptr
%588 = llvm.load %575 : !llvm.ptr -> i64
%589 = arith.constant 1 : i32
%591 = arith.extsi %589 : i32 to i64
%590 = arith.addi %588, %591 : i64
llvm.store %590, %575 : i64, !llvm.ptr
%592 = arith.constant 54 : i32
%593 = llvm.load %575 : !llvm.ptr -> i64
%594 = arith.extsi %592 : i32 to i64
%595 = llvm.getelementptr %567[%593] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %594, %595 : i64, !llvm.ptr
%596 = llvm.load %575 : !llvm.ptr -> i64
%597 = arith.constant 1 : i32
%599 = arith.extsi %597 : i32 to i64
%598 = arith.addi %596, %599 : i64
llvm.store %598, %575 : i64, !llvm.ptr
%600 = arith.constant 384 : i32
%601 = arith.extsi %600 : i32 to i64
%602 = llvm.mlir.constant(1 : i64) : i64
%603 = llvm.alloca %602 x i64 : (i64) -> !llvm.ptr
llvm.store %601, %603 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%604 = llvm.load %603 : !llvm.ptr -> i64
%605 = arith.cmpi sle, %604, %407 : i64
cf.cond_br %605, ^bb94, ^bb95
^bb94:
%606 = llvm.load %603 : !llvm.ptr -> i64
%607 = llvm.load %575 : !llvm.ptr -> i64
%608 = llvm.getelementptr %567[%607] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %606, %608 : i64, !llvm.ptr
%609 = llvm.load %575 : !llvm.ptr -> i64
%610 = arith.constant 1 : i32
%612 = arith.extsi %610 : i32 to i64
%611 = arith.addi %609, %612 : i64
llvm.store %611, %575 : i64, !llvm.ptr
%613 = llvm.load %603 : !llvm.ptr -> i64
%614 = arith.constant 8 : i32
%616 = arith.extsi %614 : i32 to i64
%615 = arith.muli %613, %616 : i64
llvm.store %615, %603 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%617 = arith.constant 243 : i32
%618 = arith.extsi %617 : i32 to i64
llvm.store %618, %603 : i64, !llvm.ptr
cf.br ^bb96
^bb96:
%619 = llvm.load %603 : !llvm.ptr -> i64
%620 = arith.cmpi sle, %619, %407 : i64
cf.cond_br %620, ^bb97, ^bb98
^bb97:
%621 = llvm.load %603 : !llvm.ptr -> i64
%622 = llvm.load %575 : !llvm.ptr -> i64
%623 = llvm.getelementptr %567[%622] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %621, %623 : i64, !llvm.ptr
%624 = llvm.load %575 : !llvm.ptr -> i64
%625 = arith.constant 1 : i32
%627 = arith.extsi %625 : i32 to i64
%626 = arith.addi %624, %627 : i64
llvm.store %626, %575 : i64, !llvm.ptr
%628 = llvm.load %603 : !llvm.ptr -> i64
%629 = arith.constant 27 : i32
%631 = arith.extsi %629 : i32 to i64
%630 = arith.muli %628, %631 : i64
llvm.store %630, %603 : i64, !llvm.ptr
cf.br ^bb96
^bb98:
%633 = llvm.load %575 : !llvm.ptr -> i64
func.call @sort_i64(%567, %633) : (!llvm.ptr, i64) -> ()
%635 = arith.constant 4096 : i32
%636 = arith.constant 4 : i32
%637 = arith.extsi %635 : i32 to i64
%638 = arith.extsi %636 : i32 to i64
%634 = func.call @calloc(%637, %638) : (i64, i64) -> !llvm.ptr
%639 = arith.constant 0 : i32
%640 = arith.extsi %639 : i32 to i64
%641 = llvm.mlir.constant(1 : i64) : i64
%642 = llvm.alloca %641 x i64 : (i64) -> !llvm.ptr
llvm.store %640, %642 : i64, !llvm.ptr
%643 = arith.constant 0 : i32
%644 = arith.extsi %643 : i32 to i64
%645 = llvm.mlir.constant(1 : i64) : i64
%646 = llvm.alloca %645 x i64 : (i64) -> !llvm.ptr
llvm.store %644, %646 : i64, !llvm.ptr
%647 = arith.constant 0 : i32
%648 = llvm.load %416 : !llvm.ptr -> i64
%649 = arith.index_cast %647 : i32 to index
%650 = arith.index_cast %648 : i32 to index
%652 = arith.constant 1 : index
%653 = arith.constant -1 : index
%654 = arith.cmpi sle, %649, %650 : index
%651 = arith.select %654, %652, %653 : index
cf.br ^bb99(%649 : index)
^bb99(%655: index):
%656 = arith.cmpi slt, %655, %650 : index
%657 = arith.cmpi sgt, %655, %650 : index
%658 = arith.select %654, %656, %657 : i1
cf.cond_br %658, ^bb100(%655 : index), ^bb101(%655 : index)
^bb100(%659: index):
cf.br ^bb102
^bb102:
%660 = llvm.load %642 : !llvm.ptr -> i64
%661 = llvm.load %575 : !llvm.ptr -> i64
%662 = arith.cmpi slt, %660, %661 : i64
%663 = scf.if %662 -> (i1) {
%665 = llvm.load %642 : !llvm.ptr -> i64
%666 = llvm.getelementptr %567[%665] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%664 = llvm.load %666 : !llvm.ptr -> i64
%668 = arith.index_cast %659 : index to i64
%669 = llvm.getelementptr %408[%668] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%667 = llvm.load %669 : !llvm.ptr -> i64
%670 = arith.cmpi sle, %664, %667 : i64
scf.yield %670 : i1
} else {
%671 = arith.constant false
scf.yield %671 : i1
}
cf.cond_br %663, ^bb103, ^bb104
^bb103:
%672 = llvm.load %646 : !llvm.ptr -> i64
%673 = arith.constant 1 : i32
%675 = arith.extsi %673 : i32 to i64
%674 = arith.addi %672, %675 : i64
llvm.store %674, %646 : i64, !llvm.ptr
%676 = llvm.load %642 : !llvm.ptr -> i64
%677 = arith.constant 1 : i32
%679 = arith.extsi %677 : i32 to i64
%678 = arith.addi %676, %679 : i64
llvm.store %678, %642 : i64, !llvm.ptr
cf.br ^bb102
^bb104:
%680 = llvm.load %646 : !llvm.ptr -> i64
%681 = arith.trunci %680 : i64 to i32
%682 = arith.index_cast %659 : index to i64
%683 = llvm.getelementptr %634[%682] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %681, %683 : i32, !llvm.ptr
%684 = arith.addi %659, %651 : index
cf.br ^bb99(%684 : index)
^bb101(%685: index):
%686 = arith.constant 0 : i32
%687 = arith.extsi %686 : i32 to i64
%688 = llvm.mlir.constant(1 : i64) : i64
%689 = llvm.alloca %688 x i64 : (i64) -> !llvm.ptr
llvm.store %687, %689 : i64, !llvm.ptr
%690 = arith.constant 0 : i32
%691 = llvm.load %416 : !llvm.ptr -> i64
%692 = arith.index_cast %690 : i32 to index
%693 = arith.index_cast %691 : i32 to index
%695 = arith.constant 1 : index
%696 = arith.constant -1 : index
%697 = arith.cmpi sle, %692, %693 : index
%694 = arith.select %697, %695, %696 : index
cf.br ^bb105(%692 : index)
^bb105(%698: index):
%699 = arith.cmpi slt, %698, %693 : index
%700 = arith.cmpi sgt, %698, %693 : index
%701 = arith.select %697, %699, %700 : i1
cf.cond_br %701, ^bb106(%698 : index), ^bb107(%698 : index)
^bb106(%702: index):
%704 = arith.index_cast %702 : index to i64
%705 = llvm.getelementptr %408[%704] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%703 = llvm.load %705 : !llvm.ptr -> i64
%706 = arith.constant 1 : i32
%708 = arith.index_cast %702 : index to i32
%707 = arith.addi %708, %706 : i32
%709 = llvm.load %416 : !llvm.ptr -> i64
%711 = arith.extsi %707 : i32 to i64
%710 = arith.cmpi eq, %711, %709 : i64
%712 = scf.if %710 -> (i64) {
scf.yield %407 : i64
} else {
%714 = arith.constant 1 : i32
%716 = arith.index_cast %702 : index to i32
%715 = arith.addi %716, %714 : i32
%717 = arith.extsi %715 : i32 to i64
%718 = llvm.getelementptr %408[%717] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%713 = llvm.load %718 : !llvm.ptr -> i64
%719 = arith.constant 1 : i32
%721 = arith.extsi %719 : i32 to i64
%720 = arith.subi %713, %721 : i64
%722 = arith.cmpi slt, %720, %407 : i64
%723 = scf.if %722 -> (i64) {
%725 = arith.constant 1 : i32
%727 = arith.index_cast %702 : index to i32
%726 = arith.addi %727, %725 : i32
%728 = arith.extsi %726 : i32 to i64
%729 = llvm.getelementptr %408[%728] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%724 = llvm.load %729 : !llvm.ptr -> i64
%730 = arith.constant 1 : i32
%732 = arith.extsi %730 : i32 to i64
%731 = arith.subi %724, %732 : i64
scf.yield %731 : i64
} else {
scf.yield %407 : i64
}
scf.yield %723 : i64
}
%733 = arith.constant 1 : i32
%735 = arith.extsi %733 : i32 to i64
%734 = arith.addi %712, %735 : i64
%736 = arith.divsi %407, %734 : i64
%737 = arith.constant 1 : i32
%739 = arith.extsi %737 : i32 to i64
%738 = arith.addi %736, %739 : i64
%740 = arith.divsi %407, %703 : i64
%741 = arith.cmpi sgt, %738, %740 : i64
cf.cond_br %741, ^bb108, ^bb109
^bb108:
%742 = arith.addi %702, %694 : index
cf.br ^bb105(%742 : index)
^bb109:
cf.br ^bb110
^bb110:
%743 = func.call @coprime6(%740) : (i64) -> i64
%745 = arith.constant 1 : i32
%747 = arith.extsi %745 : i32 to i64
%746 = arith.subi %738, %747 : i64
%744 = func.call @coprime6(%746) : (i64) -> i64
%748 = arith.subi %743, %744 : i64
%749 = arith.constant 48 : i32
%751 = arith.extsi %749 : i32 to i64
%750 = arith.cmpi sle, %703, %751 : i64
%752 = scf.if %750 -> (i64) {
%754 = arith.index_cast %702 : index to i64
%755 = llvm.getelementptr %499[%754] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%753 = llvm.load %755 : !llvm.ptr -> i32
%756 = arith.extsi %753 : i32 to i64
scf.yield %756 : i64
} else {
%757 = arith.constant 1 : i32
%759 = arith.index_cast %702 : index to i32
%758 = arith.addi %759, %757 : i32
%761 = arith.index_cast %702 : index to i64
%762 = llvm.getelementptr %634[%761] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%760 = llvm.load %762 : !llvm.ptr -> i32
%763 = arith.extsi %760 : i32 to i64
%765 = arith.extsi %758 : i32 to i64
%764 = arith.subi %765, %763 : i64
scf.yield %764 : i64
}
%766 = llvm.load %689 : !llvm.ptr -> i64
%767 = arith.muli %752, %748 : i64
%768 = arith.addi %766, %767 : i64
llvm.store %768, %689 : i64, !llvm.ptr
%769 = arith.addi %702, %694 : index
cf.br ^bb105(%769 : index)
^bb107(%770: index):
%771 = llvm.mlir.addressof @str_0 : !llvm.ptr
%772 = llvm.load %689 : !llvm.ptr -> i64
%773 = llvm.call @printf(%771, %772) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%408) : (!llvm.ptr) -> ()
func.call @free(%499) : (!llvm.ptr) -> ()
func.call @free(%504) : (!llvm.ptr) -> ()
func.call @free(%567) : (!llvm.ptr) -> ()
func.call @free(%634) : (!llvm.ptr) -> ()
%779 = arith.constant 0 : i32
func.return %779 : i32
}
}