Problem 891
Count ambiguous moments in a 12-hour cycle with three identical hands.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n) | O(n) |
|---|
| Space complexity | O(n) | O(1) |
|---|
| Approach | Flow solution | Direct hand evaluation or enumeration |
|---|
| Verdict | Optimal |
|---|
Flow source
# Project Euler 891: Ambiguous Clock
# Count ambiguous moments in a 12-hour cycle with three identical hands.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const L: i64 = 43200
const SHIFT: i64 = 1048576
struct Range {
lo: i64
hi: i64
}
function gcd(a0: i64, b0: i64) -> i64 {
let mut a: i64 = a0
if a < 0 { a = 0 - a }
let mut b: i64 = b0
if b < 0 { b = 0 - b }
while b != 0 {
let t: i64 = a % b
a = b
b = t
}
return a
}
function ceil_div(n: i64, d: i64) -> i64 {
if n >= 0 {
return (n + d - 1) / d
}
return 0 - ((0 - n) / d)
}
function floor_div(n: i64, d: i64) -> i64 {
if n >= 0 {
return n / d
}
return 0 - ((0 - n + d - 1) / d)
}
function k2_range(u: i64, v: i64, D: i64) -> Range {
if v > 0 {
return Range { lo: ceil_div(u - D + 1, v), hi: floor_div(u, v) }
} else {
let vp: i64 = 0 - v
return Range { lo: ceil_div(0 - u, vp), hi: floor_div(D - 1 - u, vp) }
}
}
function sift_down(arr: ptr<i64>, start: i64, end: i64) -> void {
let mut root: i64 = start
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 {
return
}
let tmp: i64 = arr[root]
arr[root] = arr[swap_idx]
arr[swap_idx] = tmp
root = swap_idx
}
}
function heapsort(arr: ptr<i64>, n: i64) -> void {
let mut i: i64 = n / 2
while i > 0 {
i = i - 1
sift_down(arr, i, n)
}
let mut end: i64 = n
while end > 1 {
end = end - 1
let tmp: i64 = arr[0]
arr[0] = arr[end]
arr[end] = tmp
sift_down(arr, 0, end)
}
}
function abs_val(x: i64) -> i64 {
if x < 0 {
return 0 - x
}
return x
}
function main() -> i32 {
let V: array<i64, 3> = [1, 12, 720]
let a: i64 = V[0] - V[1]
let c: i64 = V[0] - V[2]
let perms: array<i32, 15> = [
0, 2, 1, 1, 0, 2, 1, 2, 0, 2, 0, 1, 2, 1, 0
]
let cap: i64 = 5000000
let keys: ptr<i64> = calloc(cap, 8)
let mut nkeys: i64 = 0
let mut pi: i32 = 0
while pi < 5 {
let s0: i32 = perms[pi * 3]
let s1: i32 = perms[pi * 3 + 1]
let s2: i32 = perms[pi * 3 + 2]
let b: i64 = 0 - (V[s0] - V[s1])
let d: i64 = 0 - (V[s0] - V[s2])
let mut det: i64 = a * d - c * b
let mut sign: i64 = 1
if det < 0 {
sign = 0 - 1
det = 0 - det
}
let D: i64 = det
let K1: i64 = abs_val(a) + abs_val(b)
let K2: i64 = abs_val(c) + abs_val(d)
let g0: i64 = gcd(L, D)
let l1: i64 = L / g0
let d1: i64 = D / g0
let mut k1: i64 = 0 - K1
while k1 <= K1 {
let u1: i64 = sign * k1 * d
let v1: i64 = sign * b
let u2: i64 = sign * 719 * k1
let v2: i64 = sign * 11
let r1: Range = k2_range(u1, v1, D)
let r2: Range = k2_range(u2, v2, D)
let mut lo: i64 = r1.lo
if (0 - K2) > lo {
lo = 0 - K2
}
if r2.lo > lo {
lo = r2.lo
}
let mut hi: i64 = r1.hi
if K2 < hi {
hi = K2
}
if r2.hi < hi {
hi = r2.hi
}
if lo > hi {
k1 = k1 + 1
continue
}
let mut k2: i64 = lo
while k2 <= hi {
let num_t: i64 = u1 - v1 * k2
let num_tp: i64 = u2 - v2 * k2
if num_t != num_tp {
let g: i64 = gcd(num_t, d1)
let n: i64 = l1 * (num_t / g)
let den: i64 = d1 / g
keys[nkeys] = n * SHIFT + den
nkeys = nkeys + 1
let g2: i64 = gcd(num_tp, d1)
let n2: i64 = l1 * (num_tp / g2)
let den2: i64 = d1 / g2
keys[nkeys] = n2 * SHIFT + den2
nkeys = nkeys + 1
}
k2 = k2 + 1
}
k1 = k1 + 1
}
pi = pi + 1
}
heapsort(keys, nkeys)
let mut unique: i64 = 0
let mut i: i64 = 0
while i < nkeys {
if i == 0 {
unique = unique + 1
} else {
if keys[i] != keys[i - 1] {
unique = unique + 1
}
}
i = i + 1
}
free(keys)
printf("%lld\n", unique)
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; }
typedef struct Range Range;
struct Range {
int64_t lo;
int64_t hi;
};
int64_t gcd_i64_i64(int64_t a0, int64_t b0);
int64_t ceil_div_i64_i64(int64_t n, int64_t d);
int64_t floor_div_i64_i64(int64_t n, int64_t d);
Range k2_range_i64_i64_i64(int64_t u, int64_t v, int64_t D);
void sift_down_ptr_i64_i64_i64(int64_t* arr, int64_t start, int64_t end);
void heapsort_ptr_i64_i64(int64_t* arr, int64_t n);
int64_t abs_val_i64(int64_t x);
int32_t main(void);
static const int64_t L = 43200;
static const int64_t SHIFT = 1048576;
int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
if (a < 0) {
a = (0 - a);
}
int64_t b = b0;
if (b < 0) {
b = (0 - b);
}
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t ceil_div_i64_i64(int64_t n, int64_t d) {
if (n >= 0) {
return FLOW_CHECKED_DIV((((n + d) - 1)), (d));
}
return (0 - FLOW_CHECKED_DIV(((0 - n)), (d)));
}
int64_t floor_div_i64_i64(int64_t n, int64_t d) {
if (n >= 0) {
return FLOW_CHECKED_DIV((n), (d));
}
return (0 - FLOW_CHECKED_DIV(((((0 - n) + d) - 1)), (d)));
}
Range k2_range_i64_i64_i64(int64_t u, int64_t v, int64_t D) {
if (v > 0) {
return (Range){ .lo = ceil_div_i64_i64(((u - D) + 1), v), .hi = floor_div_i64_i64(u, v) };
} else {
int64_t vp = (0 - v);
return (Range){ .lo = ceil_div_i64_i64((0 - u), vp), .hi = floor_div_i64_i64(((D - 1) - u), vp) };
}
}
void sift_down_ptr_i64_i64_i64(int64_t* arr, int64_t start, int64_t end) {
int64_t root = start;
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) {
return;
}
int64_t tmp = arr[root];
arr[root] = arr[swap_idx];
arr[swap_idx] = tmp;
root = swap_idx;
}
}
void heapsort_ptr_i64_i64(int64_t* arr, int64_t n) {
int64_t i = FLOW_CHECKED_DIV((n), (2));
while (i > 0) {
i = (i - 1);
sift_down_ptr_i64_i64_i64(arr, i, n);
}
int64_t end = n;
while (end > 1) {
end = (end - 1);
int64_t tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
sift_down_ptr_i64_i64_i64(arr, 0, end);
}
}
int64_t abs_val_i64(int64_t x) {
if (x < 0) {
return (0 - x);
}
return x;
}
int32_t main(void) {
int64_t V[3] = { 1, 12, 720 };
int64_t a = ((((unsigned)(0) < 3) ? V[0] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(0), 3), flow_fault_handler("array index out of bounds"), V[0])) - (((unsigned)(1) < 3) ? V[1] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(1), 3), flow_fault_handler("array index out of bounds"), V[0])));
int64_t c = ((((unsigned)(0) < 3) ? V[0] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(0), 3), flow_fault_handler("array index out of bounds"), V[0])) - (((unsigned)(2) < 3) ? V[2] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(2), 3), flow_fault_handler("array index out of bounds"), V[0])));
int32_t perms[15] = { 0, 2, 1, 1, 0, 2, 1, 2, 0, 2, 0, 1, 2, 1, 0 };
int64_t cap = 5000000;
int64_t* keys = (int64_t*)(calloc(cap, 8));
int64_t nkeys = 0;
int32_t pi = 0;
while (pi < 5) {
int32_t s0 = (((unsigned)((pi * 3)) < 15) ? perms[(pi * 3)] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)((pi * 3)), 15), flow_fault_handler("array index out of bounds"), perms[0]));
int32_t s1 = (((unsigned)(((pi * 3) + 1)) < 15) ? perms[((pi * 3) + 1)] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(((pi * 3) + 1)), 15), flow_fault_handler("array index out of bounds"), perms[0]));
int32_t s2 = (((unsigned)(((pi * 3) + 2)) < 15) ? perms[((pi * 3) + 2)] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(((pi * 3) + 2)), 15), flow_fault_handler("array index out of bounds"), perms[0]));
int64_t b = (0 - ((((unsigned)(s0) < 3) ? V[s0] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(s0), 3), flow_fault_handler("array index out of bounds"), V[0])) - (((unsigned)(s1) < 3) ? V[s1] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(s1), 3), flow_fault_handler("array index out of bounds"), V[0]))));
int64_t d = (0 - ((((unsigned)(s0) < 3) ? V[s0] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(s0), 3), flow_fault_handler("array index out of bounds"), V[0])) - (((unsigned)(s2) < 3) ? V[s2] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(s2), 3), flow_fault_handler("array index out of bounds"), V[0]))));
int64_t det = ((a * d) - (c * b));
int64_t sign = 1;
if (det < 0) {
sign = (0 - 1);
det = (0 - det);
}
int64_t D = det;
int64_t K1 = (abs_val_i64(a) + abs_val_i64(b));
int64_t K2 = (abs_val_i64(c) + abs_val_i64(d));
int64_t g0 = gcd_i64_i64(L, D);
int64_t l1 = FLOW_CHECKED_DIV((L), (g0));
int64_t d1 = FLOW_CHECKED_DIV((D), (g0));
int64_t k1 = (0 - K1);
while (k1 <= K1) {
int64_t u1 = ((sign * k1) * d);
int64_t v1 = (sign * b);
int64_t u2 = ((sign * 719) * k1);
int64_t v2 = (sign * 11);
Range r1 = k2_range_i64_i64_i64(u1, v1, D);
Range r2 = k2_range_i64_i64_i64(u2, v2, D);
int64_t lo = r1.lo;
if ((0 - K2) > lo) {
lo = (0 - K2);
}
if (r2.lo > lo) {
lo = r2.lo;
}
int64_t hi = r1.hi;
if (K2 < hi) {
hi = K2;
}
if (r2.hi < hi) {
hi = r2.hi;
}
if (lo > hi) {
k1 = (k1 + 1);
continue;
}
int64_t k2 = lo;
while (k2 <= hi) {
int64_t num_t = (u1 - (v1 * k2));
int64_t num_tp = (u2 - (v2 * k2));
if (num_t != num_tp) {
int64_t g = gcd_i64_i64(num_t, d1);
int64_t n = (l1 * FLOW_CHECKED_DIV((num_t), (g)));
int64_t den = FLOW_CHECKED_DIV((d1), (g));
keys[nkeys] = ((n * SHIFT) + den);
nkeys = (nkeys + 1);
int64_t g2 = gcd_i64_i64(num_tp, d1);
int64_t n2 = (l1 * FLOW_CHECKED_DIV((num_tp), (g2)));
int64_t den2 = FLOW_CHECKED_DIV((d1), (g2));
keys[nkeys] = ((n2 * SHIFT) + den2);
nkeys = (nkeys + 1);
}
k2 = (k2 + 1);
}
k1 = (k1 + 1);
}
pi = (pi + 1);
}
heapsort_ptr_i64_i64(keys, nkeys);
int64_t unique = 0;
int64_t i = 0;
while (i < nkeys) {
if (i == 0) {
unique = (unique + 1);
} else {
if (keys[i] != keys[(i - 1)]) {
unique = (unique + 1);
}
}
i = (i + 1);
}
free(keys);
printf("%lld\n", unique);
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) -> ()
// Constant: L
llvm.mlir.global internal constant @L(43200 : i64) : i64
// Constant: SHIFT
llvm.mlir.global internal constant @SHIFT(1048576 : i64) : i64
// Struct: Range
// Fields:
// lo: i64
// hi: i64
func.func @gcd(%arg0: i64, %arg1: i64) -> i64 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = llvm.load %1 : !llvm.ptr -> i64
%3 = arith.constant 0 : i32
%5 = arith.extsi %3 : i32 to i64
%4 = arith.cmpi slt, %2, %5 : i64
cf.cond_br %4, ^bb0, ^bb1
^bb0:
%6 = arith.constant 0 : i32
%7 = llvm.load %1 : !llvm.ptr -> i64
%9 = arith.extsi %6 : i32 to i64
%8 = arith.subi %9, %7 : i64
llvm.store %8, %1 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%10 = llvm.mlir.constant(1 : i64) : i64
%11 = llvm.alloca %10 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %11 : i64, !llvm.ptr
%12 = llvm.load %11 : !llvm.ptr -> i64
%13 = arith.constant 0 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.cmpi slt, %12, %15 : i64
cf.cond_br %14, ^bb3, ^bb4
^bb3:
%16 = arith.constant 0 : i32
%17 = llvm.load %11 : !llvm.ptr -> i64
%19 = arith.extsi %16 : i32 to i64
%18 = arith.subi %19, %17 : i64
llvm.store %18, %11 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
cf.br ^bb6
^bb6:
%20 = llvm.load %11 : !llvm.ptr -> i64
%21 = arith.constant 0 : i32
%23 = arith.extsi %21 : i32 to i64
%22 = arith.cmpi ne, %20, %23 : i64
cf.cond_br %22, ^bb7, ^bb8
^bb7:
%24 = llvm.load %1 : !llvm.ptr -> i64
%25 = llvm.load %11 : !llvm.ptr -> i64
%26 = arith.remsi %24, %25 : i64
%27 = llvm.load %11 : !llvm.ptr -> i64
llvm.store %27, %1 : i64, !llvm.ptr
llvm.store %26, %11 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%28 = llvm.load %1 : !llvm.ptr -> i64
func.return %28 : i64
}
func.func @ceil_div(%arg0: i64, %arg1: i64) -> i64 {
%29 = arith.constant 0 : i32
%31 = arith.extsi %29 : i32 to i64
%30 = arith.cmpi sge, %arg0, %31 : i64
cf.cond_br %30, ^bb9, ^bb10
^bb9:
%32 = arith.addi %arg0, %arg1 : i64
%33 = arith.constant 1 : i32
%35 = arith.extsi %33 : i32 to i64
%34 = arith.subi %32, %35 : i64
%36 = arith.divsi %34, %arg1 : i64
func.return %36 : i64
^bb10:
cf.br ^bb11
^bb11:
%37 = arith.constant 0 : i32
%38 = arith.constant 0 : i32
%40 = arith.extsi %38 : i32 to i64
%39 = arith.subi %40, %arg0 : i64
%41 = arith.divsi %39, %arg1 : i64
%43 = arith.extsi %37 : i32 to i64
%42 = arith.subi %43, %41 : i64
func.return %42 : i64
}
func.func @floor_div(%arg0: i64, %arg1: i64) -> i64 {
%44 = arith.constant 0 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.cmpi sge, %arg0, %46 : i64
cf.cond_br %45, ^bb12, ^bb13
^bb12:
%47 = arith.divsi %arg0, %arg1 : i64
func.return %47 : i64
^bb13:
cf.br ^bb14
^bb14:
%48 = arith.constant 0 : i32
%49 = arith.constant 0 : i32
%51 = arith.extsi %49 : i32 to i64
%50 = arith.subi %51, %arg0 : i64
%52 = arith.addi %50, %arg1 : i64
%53 = arith.constant 1 : i32
%55 = arith.extsi %53 : i32 to i64
%54 = arith.subi %52, %55 : i64
%56 = arith.divsi %54, %arg1 : i64
%58 = arith.extsi %48 : i32 to i64
%57 = arith.subi %58, %56 : i64
func.return %57 : i64
}
func.func @k2_range(%arg0: i64, %arg1: i64, %arg2: i64) -> !llvm.struct<(i64, i64)> {
%59 = arith.constant 0 : i32
%61 = arith.extsi %59 : i32 to i64
%60 = arith.cmpi sgt, %arg1, %61 : i64
cf.cond_br %60, ^bb15, ^bb16
^bb15:
%62 = llvm.mlir.undef : !llvm.struct<(i64, i64)>
%64 = arith.subi %arg0, %arg2 : i64
%65 = arith.constant 1 : i32
%67 = arith.extsi %65 : i32 to i64
%66 = arith.addi %64, %67 : i64
%63 = func.call @ceil_div(%66, %arg1) : (i64, i64) -> i64
%68 = llvm.insertvalue %63, %62[0] : !llvm.struct<(i64, i64)>
%69 = func.call @floor_div(%arg0, %arg1) : (i64, i64) -> i64
%70 = llvm.insertvalue %69, %68[1] : !llvm.struct<(i64, i64)>
%71 = llvm.mlir.undef : !llvm.struct<(i64, i64)>
%72 = llvm.extractvalue %70[0] : !llvm.struct<(i64, i64)>
%73 = llvm.insertvalue %72, %71[0] : !llvm.struct<(i64, i64)>
%74 = llvm.extractvalue %70[1] : !llvm.struct<(i64, i64)>
%75 = llvm.insertvalue %74, %73[1] : !llvm.struct<(i64, i64)>
%76 = llvm.mlir.constant(1 : i64) : i64
%77 = llvm.alloca %76 x !llvm.struct<(i64, i64)> : (i64) -> !llvm.ptr
llvm.store %75, %77 : !llvm.struct<(i64, i64)>, !llvm.ptr
%78 = llvm.load %77 : !llvm.ptr -> !llvm.struct<(i64, i64)>
func.return %78 : !llvm.struct<(i64, i64)>
^bb16:
%79 = arith.constant 0 : i32
%81 = arith.extsi %79 : i32 to i64
%80 = arith.subi %81, %arg1 : i64
%82 = llvm.mlir.undef : !llvm.struct<(i64, i64)>
%84 = arith.constant 0 : i32
%86 = arith.extsi %84 : i32 to i64
%85 = arith.subi %86, %arg0 : i64
%83 = func.call @ceil_div(%85, %80) : (i64, i64) -> i64
%87 = llvm.insertvalue %83, %82[0] : !llvm.struct<(i64, i64)>
%89 = arith.constant 1 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.subi %arg2, %91 : i64
%92 = arith.subi %90, %arg0 : i64
%88 = func.call @floor_div(%92, %80) : (i64, i64) -> i64
%93 = llvm.insertvalue %88, %87[1] : !llvm.struct<(i64, i64)>
%94 = llvm.mlir.undef : !llvm.struct<(i64, i64)>
%95 = llvm.extractvalue %93[0] : !llvm.struct<(i64, i64)>
%96 = llvm.insertvalue %95, %94[0] : !llvm.struct<(i64, i64)>
%97 = llvm.extractvalue %93[1] : !llvm.struct<(i64, i64)>
%98 = llvm.insertvalue %97, %96[1] : !llvm.struct<(i64, i64)>
%99 = llvm.mlir.constant(1 : i64) : i64
%100 = llvm.alloca %99 x !llvm.struct<(i64, i64)> : (i64) -> !llvm.ptr
llvm.store %98, %100 : !llvm.struct<(i64, i64)>, !llvm.ptr
%101 = llvm.load %100 : !llvm.ptr -> !llvm.struct<(i64, i64)>
func.return %101 : !llvm.struct<(i64, i64)>
}
func.func @sift_down(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> () {
%102 = llvm.mlir.constant(1 : i64) : i64
%103 = llvm.alloca %102 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %103 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%104 = arith.constant 2 : i32
%105 = llvm.load %103 : !llvm.ptr -> i64
%107 = arith.extsi %104 : i32 to i64
%106 = arith.muli %107, %105 : i64
%108 = arith.constant 1 : i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.addi %106, %110 : i64
%111 = arith.cmpi slt, %109, %arg2 : i64
cf.cond_br %111, ^bb19, ^bb20
^bb19:
%112 = arith.constant 2 : i32
%113 = llvm.load %103 : !llvm.ptr -> i64
%115 = arith.extsi %112 : i32 to i64
%114 = arith.muli %115, %113 : i64
%116 = arith.constant 1 : i32
%118 = arith.extsi %116 : i32 to i64
%117 = arith.addi %114, %118 : i64
%119 = llvm.load %103 : !llvm.ptr -> i64
%120 = llvm.mlir.constant(1 : i64) : i64
%121 = llvm.alloca %120 x i64 : (i64) -> !llvm.ptr
llvm.store %119, %121 : i64, !llvm.ptr
%123 = llvm.load %121 : !llvm.ptr -> i64
%124 = llvm.getelementptr %arg0[%123] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%122 = llvm.load %124 : !llvm.ptr -> i64
%126 = llvm.getelementptr %arg0[%117] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%125 = llvm.load %126 : !llvm.ptr -> i64
%127 = arith.cmpi slt, %122, %125 : i64
cf.cond_br %127, ^bb21, ^bb22
^bb21:
llvm.store %117, %121 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%128 = arith.constant 1 : i32
%130 = arith.extsi %128 : i32 to i64
%129 = arith.addi %117, %130 : i64
%131 = arith.cmpi slt, %129, %arg2 : i64
cf.cond_br %131, ^bb24, ^bb25
^bb24:
%133 = llvm.load %121 : !llvm.ptr -> i64
%134 = llvm.getelementptr %arg0[%133] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%132 = llvm.load %134 : !llvm.ptr -> i64
%136 = arith.constant 1 : i32
%138 = arith.extsi %136 : i32 to i64
%137 = arith.addi %117, %138 : i64
%139 = llvm.getelementptr %arg0[%137] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%135 = llvm.load %139 : !llvm.ptr -> i64
%140 = arith.cmpi slt, %132, %135 : i64
cf.cond_br %140, ^bb27, ^bb28
^bb27:
%141 = arith.constant 1 : i32
%143 = arith.extsi %141 : i32 to i64
%142 = arith.addi %117, %143 : i64
llvm.store %142, %121 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%144 = llvm.load %121 : !llvm.ptr -> i64
%145 = llvm.load %103 : !llvm.ptr -> i64
%146 = arith.cmpi eq, %144, %145 : i64
cf.cond_br %146, ^bb30, ^bb31
^bb30:
func.return
^bb31:
cf.br ^bb32
^bb32:
%148 = llvm.load %103 : !llvm.ptr -> i64
%149 = llvm.getelementptr %arg0[%148] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%147 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.load %121 : !llvm.ptr -> i64
%152 = llvm.getelementptr %arg0[%151] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%150 = llvm.load %152 : !llvm.ptr -> i64
%153 = llvm.load %103 : !llvm.ptr -> i64
%154 = llvm.getelementptr %arg0[%153] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %150, %154 : i64, !llvm.ptr
%155 = llvm.load %121 : !llvm.ptr -> i64
%156 = llvm.getelementptr %arg0[%155] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %147, %156 : i64, !llvm.ptr
%157 = llvm.load %121 : !llvm.ptr -> i64
llvm.store %157, %103 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
func.return
}
func.func @heapsort(%arg0: !llvm.ptr, %arg1: i64) -> () {
%158 = arith.constant 2 : i32
%160 = arith.extsi %158 : i32 to i64
%159 = arith.divsi %arg1, %160 : i64
%161 = llvm.mlir.constant(1 : i64) : i64
%162 = llvm.alloca %161 x i64 : (i64) -> !llvm.ptr
llvm.store %159, %162 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%163 = llvm.load %162 : !llvm.ptr -> i64
%164 = arith.constant 0 : i32
%166 = arith.extsi %164 : i32 to i64
%165 = arith.cmpi sgt, %163, %166 : i64
cf.cond_br %165, ^bb34, ^bb35
^bb34:
%167 = llvm.load %162 : !llvm.ptr -> i64
%168 = arith.constant 1 : i32
%170 = arith.extsi %168 : i32 to i64
%169 = arith.subi %167, %170 : i64
llvm.store %169, %162 : i64, !llvm.ptr
%172 = llvm.load %162 : !llvm.ptr -> i64
func.call @sift_down(%arg0, %172, %arg1) : (!llvm.ptr, i64, i64) -> ()
cf.br ^bb33
^bb35:
%173 = llvm.mlir.constant(1 : i64) : i64
%174 = llvm.alloca %173 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %174 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%175 = llvm.load %174 : !llvm.ptr -> i64
%176 = arith.constant 1 : i32
%178 = arith.extsi %176 : i32 to i64
%177 = arith.cmpi sgt, %175, %178 : i64
cf.cond_br %177, ^bb37, ^bb38
^bb37:
%179 = llvm.load %174 : !llvm.ptr -> i64
%180 = arith.constant 1 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.subi %179, %182 : i64
llvm.store %181, %174 : i64, !llvm.ptr
%184 = arith.constant 0 : i32
%185 = arith.extsi %184 : i32 to i64
%186 = llvm.getelementptr %arg0[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%183 = llvm.load %186 : !llvm.ptr -> i64
%188 = llvm.load %174 : !llvm.ptr -> i64
%189 = llvm.getelementptr %arg0[%188] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%187 = llvm.load %189 : !llvm.ptr -> i64
%190 = arith.constant 0 : i32
%191 = arith.extsi %190 : i32 to i64
%192 = llvm.getelementptr %arg0[%191] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %187, %192 : i64, !llvm.ptr
%193 = llvm.load %174 : !llvm.ptr -> i64
%194 = llvm.getelementptr %arg0[%193] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %183, %194 : i64, !llvm.ptr
%196 = arith.constant 0 : i32
%197 = llvm.load %174 : !llvm.ptr -> i64
%198 = arith.extsi %196 : i32 to i64
func.call @sift_down(%arg0, %198, %197) : (!llvm.ptr, i64, i64) -> ()
cf.br ^bb36
^bb38:
func.return
}
func.func @abs_val(%arg0: i64) -> i64 {
%199 = arith.constant 0 : i32
%201 = arith.extsi %199 : i32 to i64
%200 = arith.cmpi slt, %arg0, %201 : i64
cf.cond_br %200, ^bb39, ^bb40
^bb39:
%202 = arith.constant 0 : i32
%204 = arith.extsi %202 : i32 to i64
%203 = arith.subi %204, %arg0 : i64
func.return %203 : i64
^bb40:
cf.br ^bb41
^bb41:
func.return %arg0 : i64
}
func.func @main() -> i32 {
%206 = arith.constant 1 : i32
%207 = arith.constant 12 : i32
%208 = arith.constant 720 : i32
%209 = llvm.mlir.constant(1 : i64) : i64
%210 = llvm.alloca %209 x !llvm.array<3 x i64> : (i64) -> !llvm.ptr
%211 = llvm.mlir.zero : !llvm.array<3 x i64>
llvm.store %211, %210 : !llvm.array<3 x i64>, !llvm.ptr
%212 = arith.extsi %206 : i32 to i64
%213 = arith.extsi %207 : i32 to i64
%214 = arith.extsi %208 : i32 to i64
%215 = llvm.mlir.constant(0 : i64) : i64
%216 = llvm.getelementptr %210[0, %215] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
llvm.store %212, %216 : i64, !llvm.ptr
%217 = llvm.mlir.constant(1 : i64) : i64
%218 = llvm.getelementptr %210[0, %217] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
llvm.store %213, %218 : i64, !llvm.ptr
%219 = llvm.mlir.constant(2 : i64) : i64
%220 = llvm.getelementptr %210[0, %219] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
llvm.store %214, %220 : i64, !llvm.ptr
%222 = arith.constant 0 : i32
%223 = arith.extsi %222 : i32 to i64
%224 = llvm.getelementptr %210[0, %223] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
%221 = llvm.load %224 : !llvm.ptr -> i64
%226 = arith.constant 1 : i32
%227 = arith.extsi %226 : i32 to i64
%228 = llvm.getelementptr %210[0, %227] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
%225 = llvm.load %228 : !llvm.ptr -> i64
%229 = arith.subi %221, %225 : i64
%231 = arith.constant 0 : i32
%232 = arith.extsi %231 : i32 to i64
%233 = llvm.getelementptr %210[0, %232] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
%230 = llvm.load %233 : !llvm.ptr -> i64
%235 = arith.constant 2 : i32
%236 = arith.extsi %235 : i32 to i64
%237 = llvm.getelementptr %210[0, %236] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
%234 = llvm.load %237 : !llvm.ptr -> i64
%238 = arith.subi %230, %234 : i64
%240 = arith.constant 0 : i32
%241 = arith.constant 2 : i32
%242 = arith.constant 1 : i32
%243 = arith.constant 1 : i32
%244 = arith.constant 0 : i32
%245 = arith.constant 2 : i32
%246 = arith.constant 1 : i32
%247 = arith.constant 2 : i32
%248 = arith.constant 0 : i32
%249 = arith.constant 2 : i32
%250 = arith.constant 0 : i32
%251 = arith.constant 1 : i32
%252 = arith.constant 2 : i32
%253 = arith.constant 1 : i32
%254 = arith.constant 0 : i32
%255 = llvm.mlir.constant(1 : i64) : i64
%256 = llvm.alloca %255 x !llvm.array<15 x i32> : (i64) -> !llvm.ptr
%257 = llvm.mlir.zero : !llvm.array<15 x i32>
llvm.store %257, %256 : !llvm.array<15 x i32>, !llvm.ptr
%258 = llvm.mlir.constant(0 : i64) : i64
%259 = llvm.getelementptr %256[0, %258] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %240, %259 : i32, !llvm.ptr
%260 = llvm.mlir.constant(1 : i64) : i64
%261 = llvm.getelementptr %256[0, %260] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %241, %261 : i32, !llvm.ptr
%262 = llvm.mlir.constant(2 : i64) : i64
%263 = llvm.getelementptr %256[0, %262] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %242, %263 : i32, !llvm.ptr
%264 = llvm.mlir.constant(3 : i64) : i64
%265 = llvm.getelementptr %256[0, %264] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %243, %265 : i32, !llvm.ptr
%266 = llvm.mlir.constant(4 : i64) : i64
%267 = llvm.getelementptr %256[0, %266] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %244, %267 : i32, !llvm.ptr
%268 = llvm.mlir.constant(5 : i64) : i64
%269 = llvm.getelementptr %256[0, %268] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %245, %269 : i32, !llvm.ptr
%270 = llvm.mlir.constant(6 : i64) : i64
%271 = llvm.getelementptr %256[0, %270] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %246, %271 : i32, !llvm.ptr
%272 = llvm.mlir.constant(7 : i64) : i64
%273 = llvm.getelementptr %256[0, %272] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %247, %273 : i32, !llvm.ptr
%274 = llvm.mlir.constant(8 : i64) : i64
%275 = llvm.getelementptr %256[0, %274] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %248, %275 : i32, !llvm.ptr
%276 = llvm.mlir.constant(9 : i64) : i64
%277 = llvm.getelementptr %256[0, %276] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %249, %277 : i32, !llvm.ptr
%278 = llvm.mlir.constant(10 : i64) : i64
%279 = llvm.getelementptr %256[0, %278] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %250, %279 : i32, !llvm.ptr
%280 = llvm.mlir.constant(11 : i64) : i64
%281 = llvm.getelementptr %256[0, %280] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %251, %281 : i32, !llvm.ptr
%282 = llvm.mlir.constant(12 : i64) : i64
%283 = llvm.getelementptr %256[0, %282] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %252, %283 : i32, !llvm.ptr
%284 = llvm.mlir.constant(13 : i64) : i64
%285 = llvm.getelementptr %256[0, %284] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %253, %285 : i32, !llvm.ptr
%286 = llvm.mlir.constant(14 : i64) : i64
%287 = llvm.getelementptr %256[0, %286] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
llvm.store %254, %287 : i32, !llvm.ptr
%288 = arith.constant 5000000 : i32
%289 = arith.extsi %288 : i32 to i64
%291 = arith.constant 8 : i32
%292 = arith.extsi %291 : i32 to i64
%290 = func.call @calloc(%289, %292) : (i64, i64) -> !llvm.ptr
%293 = arith.constant 0 : i32
%294 = arith.extsi %293 : i32 to i64
%295 = llvm.mlir.constant(1 : i64) : i64
%296 = llvm.alloca %295 x i64 : (i64) -> !llvm.ptr
llvm.store %294, %296 : i64, !llvm.ptr
%297 = arith.constant 0 : i32
%298 = llvm.mlir.constant(1 : i64) : i64
%299 = llvm.alloca %298 x i32 : (i64) -> !llvm.ptr
llvm.store %297, %299 : i32, !llvm.ptr
cf.br ^bb42
^bb42:
%300 = llvm.load %299 : !llvm.ptr -> i32
%301 = arith.constant 5 : i32
%302 = arith.cmpi slt, %300, %301 : i32
cf.cond_br %302, ^bb43, ^bb44
^bb43:
%304 = llvm.load %299 : !llvm.ptr -> i32
%305 = arith.constant 3 : i32
%306 = arith.muli %304, %305 : i32
%307 = arith.extsi %306 : i32 to i64
%308 = llvm.getelementptr %256[0, %307] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
%303 = llvm.load %308 : !llvm.ptr -> i32
%310 = llvm.load %299 : !llvm.ptr -> i32
%311 = arith.constant 3 : i32
%312 = arith.muli %310, %311 : i32
%313 = arith.constant 1 : i32
%314 = arith.addi %312, %313 : i32
%315 = arith.extsi %314 : i32 to i64
%316 = llvm.getelementptr %256[0, %315] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
%309 = llvm.load %316 : !llvm.ptr -> i32
%318 = llvm.load %299 : !llvm.ptr -> i32
%319 = arith.constant 3 : i32
%320 = arith.muli %318, %319 : i32
%321 = arith.constant 2 : i32
%322 = arith.addi %320, %321 : i32
%323 = arith.extsi %322 : i32 to i64
%324 = llvm.getelementptr %256[0, %323] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<15 x i32>
%317 = llvm.load %324 : !llvm.ptr -> i32
%325 = arith.constant 0 : i32
%327 = arith.extsi %303 : i32 to i64
%328 = llvm.getelementptr %210[0, %327] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
%326 = llvm.load %328 : !llvm.ptr -> i64
%330 = arith.extsi %309 : i32 to i64
%331 = llvm.getelementptr %210[0, %330] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
%329 = llvm.load %331 : !llvm.ptr -> i64
%332 = arith.subi %326, %329 : i64
%334 = arith.extsi %325 : i32 to i64
%333 = arith.subi %334, %332 : i64
%335 = arith.constant 0 : i32
%337 = arith.extsi %303 : i32 to i64
%338 = llvm.getelementptr %210[0, %337] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
%336 = llvm.load %338 : !llvm.ptr -> i64
%340 = arith.extsi %317 : i32 to i64
%341 = llvm.getelementptr %210[0, %340] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
%339 = llvm.load %341 : !llvm.ptr -> i64
%342 = arith.subi %336, %339 : i64
%344 = arith.extsi %335 : i32 to i64
%343 = arith.subi %344, %342 : i64
%345 = arith.muli %229, %343 : i64
%346 = arith.muli %238, %333 : i64
%347 = arith.subi %345, %346 : i64
%348 = llvm.mlir.constant(1 : i64) : i64
%349 = llvm.alloca %348 x i64 : (i64) -> !llvm.ptr
llvm.store %347, %349 : i64, !llvm.ptr
%350 = arith.constant 1 : i32
%351 = arith.extsi %350 : i32 to i64
%352 = llvm.mlir.constant(1 : i64) : i64
%353 = llvm.alloca %352 x i64 : (i64) -> !llvm.ptr
llvm.store %351, %353 : i64, !llvm.ptr
%354 = llvm.load %349 : !llvm.ptr -> i64
%355 = arith.constant 0 : i32
%357 = arith.extsi %355 : i32 to i64
%356 = arith.cmpi slt, %354, %357 : i64
cf.cond_br %356, ^bb45, ^bb46
^bb45:
%358 = arith.constant 0 : i32
%359 = arith.constant 1 : i32
%360 = arith.subi %358, %359 : i32
%361 = arith.extsi %360 : i32 to i64
llvm.store %361, %353 : i64, !llvm.ptr
%362 = arith.constant 0 : i32
%363 = llvm.load %349 : !llvm.ptr -> i64
%365 = arith.extsi %362 : i32 to i64
%364 = arith.subi %365, %363 : i64
llvm.store %364, %349 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%366 = llvm.load %349 : !llvm.ptr -> i64
%367 = func.call @abs_val(%229) : (i64) -> i64
%368 = func.call @abs_val(%333) : (i64) -> i64
%369 = arith.addi %367, %368 : i64
%370 = func.call @abs_val(%238) : (i64) -> i64
%371 = func.call @abs_val(%343) : (i64) -> i64
%372 = arith.addi %370, %371 : i64
%374 = llvm.mlir.addressof @L : !llvm.ptr
%375 = llvm.load %374 : !llvm.ptr -> i64
%373 = func.call @gcd(%375, %366) : (i64, i64) -> i64
%376 = llvm.mlir.addressof @L : !llvm.ptr
%377 = llvm.load %376 : !llvm.ptr -> i64
%378 = arith.divsi %377, %373 : i64
%379 = arith.divsi %366, %373 : i64
%380 = arith.constant 0 : i32
%382 = arith.extsi %380 : i32 to i64
%381 = arith.subi %382, %369 : i64
%383 = llvm.mlir.constant(1 : i64) : i64
%384 = llvm.alloca %383 x i64 : (i64) -> !llvm.ptr
llvm.store %381, %384 : i64, !llvm.ptr
cf.br ^bb48
^bb48:
%385 = llvm.load %384 : !llvm.ptr -> i64
%386 = arith.cmpi sle, %385, %369 : i64
cf.cond_br %386, ^bb49, ^bb50
^bb49:
%387 = llvm.load %353 : !llvm.ptr -> i64
%388 = llvm.load %384 : !llvm.ptr -> i64
%389 = arith.muli %387, %388 : i64
%390 = arith.muli %389, %343 : i64
%391 = llvm.load %353 : !llvm.ptr -> i64
%392 = arith.muli %391, %333 : i64
%393 = llvm.load %353 : !llvm.ptr -> i64
%394 = arith.constant 719 : i32
%396 = arith.extsi %394 : i32 to i64
%395 = arith.muli %393, %396 : i64
%397 = llvm.load %384 : !llvm.ptr -> i64
%398 = arith.muli %395, %397 : i64
%399 = llvm.load %353 : !llvm.ptr -> i64
%400 = arith.constant 11 : i32
%402 = arith.extsi %400 : i32 to i64
%401 = arith.muli %399, %402 : i64
%403 = func.call @k2_range(%390, %392, %366) : (i64, i64, i64) -> !llvm.struct<(i64, i64)>
%404 = llvm.mlir.undef : !llvm.struct<(i64, i64)>
%405 = llvm.extractvalue %403[0] : !llvm.struct<(i64, i64)>
%406 = llvm.insertvalue %405, %404[0] : !llvm.struct<(i64, i64)>
%407 = llvm.extractvalue %403[1] : !llvm.struct<(i64, i64)>
%408 = llvm.insertvalue %407, %406[1] : !llvm.struct<(i64, i64)>
%409 = llvm.mlir.constant(1 : i64) : i64
%410 = llvm.alloca %409 x !llvm.struct<(i64, i64)> : (i64) -> !llvm.ptr
llvm.store %408, %410 : !llvm.struct<(i64, i64)>, !llvm.ptr
%411 = llvm.load %410 : !llvm.ptr -> !llvm.struct<(i64, i64)>
%412 = llvm.mlir.constant(1 : i64) : i64
%413 = llvm.alloca %412 x !llvm.struct<(i64, i64)> : (i64) -> !llvm.ptr
llvm.store %411, %413 : !llvm.struct<(i64, i64)>, !llvm.ptr
%414 = func.call @k2_range(%398, %401, %366) : (i64, i64, i64) -> !llvm.struct<(i64, i64)>
%415 = llvm.mlir.undef : !llvm.struct<(i64, i64)>
%416 = llvm.extractvalue %414[0] : !llvm.struct<(i64, i64)>
%417 = llvm.insertvalue %416, %415[0] : !llvm.struct<(i64, i64)>
%418 = llvm.extractvalue %414[1] : !llvm.struct<(i64, i64)>
%419 = llvm.insertvalue %418, %417[1] : !llvm.struct<(i64, i64)>
%420 = llvm.mlir.constant(1 : i64) : i64
%421 = llvm.alloca %420 x !llvm.struct<(i64, i64)> : (i64) -> !llvm.ptr
llvm.store %419, %421 : !llvm.struct<(i64, i64)>, !llvm.ptr
%422 = llvm.load %421 : !llvm.ptr -> !llvm.struct<(i64, i64)>
%423 = llvm.mlir.constant(1 : i64) : i64
%424 = llvm.alloca %423 x !llvm.struct<(i64, i64)> : (i64) -> !llvm.ptr
llvm.store %422, %424 : !llvm.struct<(i64, i64)>, !llvm.ptr
%425 = llvm.load %413 : !llvm.ptr -> !llvm.struct<(i64, i64)>
%426 = llvm.getelementptr %413[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64)>
%427 = llvm.load %426 : !llvm.ptr -> i64
%428 = llvm.mlir.constant(1 : i64) : i64
%429 = llvm.alloca %428 x i64 : (i64) -> !llvm.ptr
llvm.store %427, %429 : i64, !llvm.ptr
%430 = arith.constant 0 : i32
%432 = arith.extsi %430 : i32 to i64
%431 = arith.subi %432, %372 : i64
%433 = llvm.load %429 : !llvm.ptr -> i64
%434 = arith.cmpi sgt, %431, %433 : i64
cf.cond_br %434, ^bb51, ^bb52
^bb51:
%435 = arith.constant 0 : i32
%437 = arith.extsi %435 : i32 to i64
%436 = arith.subi %437, %372 : i64
llvm.store %436, %429 : i64, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
%438 = llvm.load %424 : !llvm.ptr -> !llvm.struct<(i64, i64)>
%439 = llvm.getelementptr %424[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64)>
%440 = llvm.load %439 : !llvm.ptr -> i64
%441 = llvm.load %429 : !llvm.ptr -> i64
%442 = arith.cmpi sgt, %440, %441 : i64
cf.cond_br %442, ^bb54, ^bb55
^bb54:
%443 = llvm.load %424 : !llvm.ptr -> !llvm.struct<(i64, i64)>
%444 = llvm.getelementptr %424[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64)>
%445 = llvm.load %444 : !llvm.ptr -> i64
llvm.store %445, %429 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%446 = llvm.load %413 : !llvm.ptr -> !llvm.struct<(i64, i64)>
%447 = llvm.getelementptr %413[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64)>
%448 = llvm.load %447 : !llvm.ptr -> i64
%449 = llvm.mlir.constant(1 : i64) : i64
%450 = llvm.alloca %449 x i64 : (i64) -> !llvm.ptr
llvm.store %448, %450 : i64, !llvm.ptr
%451 = llvm.load %450 : !llvm.ptr -> i64
%452 = arith.cmpi slt, %372, %451 : i64
cf.cond_br %452, ^bb57, ^bb58
^bb57:
llvm.store %372, %450 : i64, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%453 = llvm.load %424 : !llvm.ptr -> !llvm.struct<(i64, i64)>
%454 = llvm.getelementptr %424[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64)>
%455 = llvm.load %454 : !llvm.ptr -> i64
%456 = llvm.load %450 : !llvm.ptr -> i64
%457 = arith.cmpi slt, %455, %456 : i64
cf.cond_br %457, ^bb60, ^bb61
^bb60:
%458 = llvm.load %424 : !llvm.ptr -> !llvm.struct<(i64, i64)>
%459 = llvm.getelementptr %424[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64)>
%460 = llvm.load %459 : !llvm.ptr -> i64
llvm.store %460, %450 : i64, !llvm.ptr
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
%461 = llvm.load %429 : !llvm.ptr -> i64
%462 = llvm.load %450 : !llvm.ptr -> i64
%463 = arith.cmpi sgt, %461, %462 : i64
cf.cond_br %463, ^bb63, ^bb64
^bb63:
%464 = llvm.load %384 : !llvm.ptr -> i64
%465 = arith.constant 1 : i32
%467 = arith.extsi %465 : i32 to i64
%466 = arith.addi %464, %467 : i64
llvm.store %466, %384 : i64, !llvm.ptr
cf.br ^bb48
^bb64:
cf.br ^bb65
^bb65:
%468 = llvm.load %429 : !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
cf.br ^bb66
^bb66:
%471 = llvm.load %470 : !llvm.ptr -> i64
%472 = llvm.load %450 : !llvm.ptr -> i64
%473 = arith.cmpi sle, %471, %472 : i64
cf.cond_br %473, ^bb67, ^bb68
^bb67:
%474 = llvm.load %470 : !llvm.ptr -> i64
%475 = arith.muli %392, %474 : i64
%476 = arith.subi %390, %475 : i64
%477 = llvm.load %470 : !llvm.ptr -> i64
%478 = arith.muli %401, %477 : i64
%479 = arith.subi %398, %478 : i64
%480 = arith.cmpi ne, %476, %479 : i64
cf.cond_br %480, ^bb69, ^bb70
^bb69:
%481 = func.call @gcd(%476, %379) : (i64, i64) -> i64
%482 = arith.divsi %476, %481 : i64
%483 = arith.muli %378, %482 : i64
%484 = arith.divsi %379, %481 : i64
%485 = llvm.mlir.addressof @SHIFT : !llvm.ptr
%486 = llvm.load %485 : !llvm.ptr -> i64
%487 = arith.muli %483, %486 : i64
%488 = arith.addi %487, %484 : i64
%489 = llvm.load %296 : !llvm.ptr -> i64
%490 = llvm.getelementptr %290[%489] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %488, %490 : i64, !llvm.ptr
%491 = llvm.load %296 : !llvm.ptr -> i64
%492 = arith.constant 1 : i32
%494 = arith.extsi %492 : i32 to i64
%493 = arith.addi %491, %494 : i64
llvm.store %493, %296 : i64, !llvm.ptr
%495 = func.call @gcd(%479, %379) : (i64, i64) -> i64
%496 = arith.divsi %479, %495 : i64
%497 = arith.muli %378, %496 : i64
%498 = arith.divsi %379, %495 : i64
%499 = llvm.mlir.addressof @SHIFT : !llvm.ptr
%500 = llvm.load %499 : !llvm.ptr -> i64
%501 = arith.muli %497, %500 : i64
%502 = arith.addi %501, %498 : i64
%503 = llvm.load %296 : !llvm.ptr -> i64
%504 = llvm.getelementptr %290[%503] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %502, %504 : i64, !llvm.ptr
%505 = llvm.load %296 : !llvm.ptr -> i64
%506 = arith.constant 1 : i32
%508 = arith.extsi %506 : i32 to i64
%507 = arith.addi %505, %508 : i64
llvm.store %507, %296 : i64, !llvm.ptr
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
%509 = llvm.load %470 : !llvm.ptr -> i64
%510 = arith.constant 1 : i32
%512 = arith.extsi %510 : i32 to i64
%511 = arith.addi %509, %512 : i64
llvm.store %511, %470 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
%513 = llvm.load %384 : !llvm.ptr -> i64
%514 = arith.constant 1 : i32
%516 = arith.extsi %514 : i32 to i64
%515 = arith.addi %513, %516 : i64
llvm.store %515, %384 : i64, !llvm.ptr
cf.br ^bb48
^bb50:
%517 = llvm.load %299 : !llvm.ptr -> i32
%518 = arith.constant 1 : i32
%519 = arith.addi %517, %518 : i32
llvm.store %519, %299 : i32, !llvm.ptr
cf.br ^bb42
^bb44:
%521 = llvm.load %296 : !llvm.ptr -> i64
func.call @heapsort(%290, %521) : (!llvm.ptr, i64) -> ()
%522 = arith.constant 0 : i32
%523 = arith.extsi %522 : i32 to i64
%524 = llvm.mlir.constant(1 : i64) : i64
%525 = llvm.alloca %524 x i64 : (i64) -> !llvm.ptr
llvm.store %523, %525 : i64, !llvm.ptr
%526 = arith.constant 0 : i32
%527 = arith.extsi %526 : i32 to i64
%528 = llvm.mlir.constant(1 : i64) : i64
%529 = llvm.alloca %528 x i64 : (i64) -> !llvm.ptr
llvm.store %527, %529 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%530 = llvm.load %529 : !llvm.ptr -> i64
%531 = llvm.load %296 : !llvm.ptr -> i64
%532 = arith.cmpi slt, %530, %531 : i64
cf.cond_br %532, ^bb73, ^bb74
^bb73:
%533 = llvm.load %529 : !llvm.ptr -> i64
%534 = arith.constant 0 : i32
%536 = arith.extsi %534 : i32 to i64
%535 = arith.cmpi eq, %533, %536 : i64
cf.cond_br %535, ^bb75, ^bb76
^bb75:
%537 = llvm.load %525 : !llvm.ptr -> i64
%538 = arith.constant 1 : i32
%540 = arith.extsi %538 : i32 to i64
%539 = arith.addi %537, %540 : i64
llvm.store %539, %525 : i64, !llvm.ptr
cf.br ^bb77
^bb76:
%542 = llvm.load %529 : !llvm.ptr -> i64
%543 = llvm.getelementptr %290[%542] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%541 = llvm.load %543 : !llvm.ptr -> i64
%545 = llvm.load %529 : !llvm.ptr -> i64
%546 = arith.constant 1 : i32
%548 = arith.extsi %546 : i32 to i64
%547 = arith.subi %545, %548 : i64
%549 = llvm.getelementptr %290[%547] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%544 = llvm.load %549 : !llvm.ptr -> i64
%550 = arith.cmpi ne, %541, %544 : i64
cf.cond_br %550, ^bb78, ^bb79
^bb78:
%551 = llvm.load %525 : !llvm.ptr -> i64
%552 = arith.constant 1 : i32
%554 = arith.extsi %552 : i32 to i64
%553 = arith.addi %551, %554 : i64
llvm.store %553, %525 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
cf.br ^bb77
^bb77:
%555 = llvm.load %529 : !llvm.ptr -> i64
%556 = arith.constant 1 : i32
%558 = arith.extsi %556 : i32 to i64
%557 = arith.addi %555, %558 : i64
llvm.store %557, %529 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
func.call @free(%290) : (!llvm.ptr) -> ()
%560 = llvm.mlir.addressof @str_0 : !llvm.ptr
%561 = llvm.load %525 : !llvm.ptr -> i64
%562 = llvm.call @printf(%560, %561) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%563 = arith.constant 0 : i32
func.return %563 : i32
}
}