Problem 247
Least square index with >=3 below and >=3 left on xy=1 hyperbola packing.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n) | O(n log n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Geometric enumeration |
|---|
| Verdict | Optimal |
|---|
Flow source
# Project Euler 247
# Least square index with >=3 below and >=3 left on xy=1 hyperbola packing.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function sqrt(x: f64) -> f64
}
# Max-heap of candidates by side length; store parallel arrays
const CAP: i64 = 5000000
let mut HX: ptr<f64> = null
let mut HY: ptr<f64> = null
let mut HL: ptr<i32> = null
let mut HB: ptr<i32> = null
let mut HS: ptr<f64> = null
let mut HN: i64 = 0
function side_of(x: f64, y: f64) -> f64 {
return 0.5 * (sqrt((x - y) * (x - y) + 4.0) - x - y)
}
function heap_swap(i: i64, j: i64) -> void {
let tx: f64 = HX[i]; HX[i] = HX[j]; HX[j] = tx
let ty: f64 = HY[i]; HY[i] = HY[j]; HY[j] = ty
let tl: i32 = HL[i]; HL[i] = HL[j]; HL[j] = tl
let tb: i32 = HB[i]; HB[i] = HB[j]; HB[j] = tb
let ts: f64 = HS[i]; HS[i] = HS[j]; HS[j] = ts
}
function heap_up(i0: i64) -> void {
let mut i: i64 = i0
while i > 0 {
let p: i64 = (i - 1) / 2
if HS[p] >= HS[i] { break }
heap_swap(p, i)
i = p
}
}
function heap_down(i0: i64) -> void {
let mut i: i64 = i0
while true {
let l: i64 = 2 * i + 1
let r: i64 = 2 * i + 2
let mut best: i64 = i
if l < HN && HS[l] > HS[best] { best = l }
if r < HN && HS[r] > HS[best] { best = r }
if best == i { break }
heap_swap(i, best)
i = best
}
}
function heap_push(x: f64, y: f64, left: i32, below: i32) -> void {
let s: f64 = side_of(x, y)
HX[HN] = x; HY[HN] = y; HL[HN] = left; HB[HN] = below; HS[HN] = s
heap_up(HN)
HN = HN + 1
}
function main() -> i32 {
let IL: i32 = 3
let IB: i32 = 3
HX = calloc(CAP, 8); HY = calloc(CAP, 8); HS = calloc(CAP, 8)
HL = calloc(CAP, 4); HB = calloc(CAP, 4)
if HX == null || HY == null { return 1 }
heap_push(1.0, 0.0, 0, 0)
let mut candidates: i32 = 1
let mut result: i64 = 0
while candidates > 0 {
result = result + 1
# pop max
let x: f64 = HX[0]
let y: f64 = HY[0]
let left: i32 = HL[0]
let below: i32 = HB[0]
let s: f64 = HS[0]
HN = HN - 1
if HN > 0 {
HX[0] = HX[HN]; HY[0] = HY[HN]; HL[0] = HL[HN]; HB[0] = HB[HN]; HS[0] = HS[HN]
heap_down(0)
}
let top_y: f64 = y + s
let right_x: f64 = x + s
heap_push(x, top_y, left, below + 1)
heap_push(right_x, y, left + 1, below)
if left <= IL && (below + 1) <= IB { candidates = candidates + 1 }
if (left + 1) <= IL && below <= IB { candidates = candidates + 1 }
if left <= IL && below <= IB { candidates = candidates - 1 }
}
printf("%lld\n", result)
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; }
double side_of_f64_f64(double x, double y);
void heap_swap_i64_i64(int64_t i, int64_t j);
void heap_up_i64(int64_t i0);
void heap_down_i64(int64_t i0);
void heap_push_f64_f64_i32_i32(double x, double y, int32_t left, int32_t below);
int32_t main(void);
static const int64_t CAP = 5000000;
/* Module statics */
static double* HX = NULL;
static double* HY = NULL;
static int32_t* HL = NULL;
static int32_t* HB = NULL;
static double* HS = NULL;
static int64_t HN = 0;
double side_of_f64_f64(double x, double y) {
return (0.5 * ((sqrt((((x - y) * (x - y)) + 4.0)) - x) - y));
}
void heap_swap_i64_i64(int64_t i, int64_t j) {
double tx = HX[i];
HX[i] = HX[j];
HX[j] = tx;
double ty = HY[i];
HY[i] = HY[j];
HY[j] = ty;
int32_t tl = HL[i];
HL[i] = HL[j];
HL[j] = tl;
int32_t tb = HB[i];
HB[i] = HB[j];
HB[j] = tb;
double ts = HS[i];
HS[i] = HS[j];
HS[j] = ts;
}
void heap_up_i64(int64_t i0) {
int64_t i = i0;
while (i > 0) {
int64_t p = FLOW_CHECKED_DIV(((i - 1)), (2));
if (HS[p] >= HS[i]) {
break;
}
heap_swap_i64_i64(p, i);
i = p;
}
}
void heap_down_i64(int64_t i0) {
int64_t i = i0;
while (1) {
int64_t l = ((2 * i) + 1);
int64_t r = ((2 * i) + 2);
int64_t best = i;
if ((l < HN && HS[l] > HS[best])) {
best = l;
}
if ((r < HN && HS[r] > HS[best])) {
best = r;
}
if (best == i) {
break;
}
heap_swap_i64_i64(i, best);
i = best;
}
}
void heap_push_f64_f64_i32_i32(double x, double y, int32_t left, int32_t below) {
double s = side_of_f64_f64(x, y);
HX[HN] = x;
HY[HN] = y;
HL[HN] = left;
HB[HN] = below;
HS[HN] = s;
heap_up_i64(HN);
HN = (HN + 1);
}
int32_t main(void) {
int32_t IL = 3;
int32_t IB = 3;
HX = calloc(CAP, 8);
HY = calloc(CAP, 8);
HS = calloc(CAP, 8);
HL = calloc(CAP, 4);
HB = calloc(CAP, 4);
if ((HX == NULL || HY == NULL)) {
return 1;
}
heap_push_f64_f64_i32_i32(1.0, 0.0, 0, 0);
int32_t candidates = 1;
int64_t result = 0;
while (candidates > 0) {
result = (result + 1);
double x = HX[0];
double y = HY[0];
int32_t left = HL[0];
int32_t below = HB[0];
double s = HS[0];
HN = (HN - 1);
if (HN > 0) {
HX[0] = HX[HN];
HY[0] = HY[HN];
HL[0] = HL[HN];
HB[0] = HB[HN];
HS[0] = HS[HN];
heap_down_i64(0);
}
double top_y = (y + s);
double right_x = (x + s);
heap_push_f64_f64_i32_i32(x, top_y, left, (below + 1));
heap_push_f64_f64_i32_i32(right_x, y, (left + 1), below);
if ((left <= IL && (below + 1) <= IB)) {
candidates = (candidates + 1);
}
if (((left + 1) <= IL && below <= IB)) {
candidates = (candidates + 1);
}
if ((left <= IL && below <= IB)) {
candidates = (candidates - 1);
}
}
printf("%lld\n", result);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @sqrt(f64) -> f64
// Constant: CAP
llvm.mlir.global internal constant @CAP(5000000 : i64) : i64
// Module static: HX
llvm.mlir.global internal @HX() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: HY
llvm.mlir.global internal @HY() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
// Module static: HL
llvm.mlir.global internal @HL() {addr_space = 0 : i32} : !llvm.ptr {
%2 = llvm.mlir.zero : !llvm.ptr
llvm.return %2 : !llvm.ptr
}
// Module static: HB
llvm.mlir.global internal @HB() {addr_space = 0 : i32} : !llvm.ptr {
%3 = llvm.mlir.zero : !llvm.ptr
llvm.return %3 : !llvm.ptr
}
// Module static: HS
llvm.mlir.global internal @HS() {addr_space = 0 : i32} : !llvm.ptr {
%4 = llvm.mlir.zero : !llvm.ptr
llvm.return %4 : !llvm.ptr
}
// Module static: HN
llvm.mlir.global internal @HN(0 : i64) : i64
func.func @side_of(%arg0: f64, %arg1: f64) -> f64 {
%5 = arith.constant 0.5 : f32
%6 = arith.subf %arg0, %arg1 : f64
%7 = arith.subf %arg0, %arg1 : f64
%8 = arith.mulf %6, %7 : f64
%9 = arith.constant 4.0 : f32
%11 = arith.extf %9 : f32 to f64
%10 = arith.addf %8, %11 : f64
%12 = math.sqrt %10 : f64
%13 = arith.subf %12, %arg0 : f64
%14 = arith.subf %13, %arg1 : f64
%16 = arith.extf %5 : f32 to f64
%15 = arith.mulf %16, %14 : f64
func.return %15 : f64
}
func.func @heap_swap(%arg0: i64, %arg1: i64) -> () {
%18 = llvm.mlir.addressof @HX : !llvm.ptr
%19 = llvm.load %18 : !llvm.ptr -> !llvm.ptr
%20 = llvm.getelementptr %19[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%17 = llvm.load %20 : !llvm.ptr -> f64
%22 = llvm.mlir.addressof @HX : !llvm.ptr
%23 = llvm.load %22 : !llvm.ptr -> !llvm.ptr
%24 = llvm.getelementptr %23[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%21 = llvm.load %24 : !llvm.ptr -> f64
%25 = llvm.mlir.addressof @HX : !llvm.ptr
%26 = llvm.load %25 : !llvm.ptr -> !llvm.ptr
%27 = llvm.getelementptr %26[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %21, %27 : f64, !llvm.ptr
%28 = llvm.mlir.addressof @HX : !llvm.ptr
%29 = llvm.load %28 : !llvm.ptr -> !llvm.ptr
%30 = llvm.getelementptr %29[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %17, %30 : f64, !llvm.ptr
%32 = llvm.mlir.addressof @HY : !llvm.ptr
%33 = llvm.load %32 : !llvm.ptr -> !llvm.ptr
%34 = llvm.getelementptr %33[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%31 = llvm.load %34 : !llvm.ptr -> f64
%36 = llvm.mlir.addressof @HY : !llvm.ptr
%37 = llvm.load %36 : !llvm.ptr -> !llvm.ptr
%38 = llvm.getelementptr %37[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%35 = llvm.load %38 : !llvm.ptr -> f64
%39 = llvm.mlir.addressof @HY : !llvm.ptr
%40 = llvm.load %39 : !llvm.ptr -> !llvm.ptr
%41 = llvm.getelementptr %40[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %35, %41 : f64, !llvm.ptr
%42 = llvm.mlir.addressof @HY : !llvm.ptr
%43 = llvm.load %42 : !llvm.ptr -> !llvm.ptr
%44 = llvm.getelementptr %43[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %31, %44 : f64, !llvm.ptr
%46 = llvm.mlir.addressof @HL : !llvm.ptr
%47 = llvm.load %46 : !llvm.ptr -> !llvm.ptr
%48 = llvm.getelementptr %47[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%45 = llvm.load %48 : !llvm.ptr -> i32
%50 = llvm.mlir.addressof @HL : !llvm.ptr
%51 = llvm.load %50 : !llvm.ptr -> !llvm.ptr
%52 = llvm.getelementptr %51[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%49 = llvm.load %52 : !llvm.ptr -> i32
%53 = llvm.mlir.addressof @HL : !llvm.ptr
%54 = llvm.load %53 : !llvm.ptr -> !llvm.ptr
%55 = llvm.getelementptr %54[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %49, %55 : i32, !llvm.ptr
%56 = llvm.mlir.addressof @HL : !llvm.ptr
%57 = llvm.load %56 : !llvm.ptr -> !llvm.ptr
%58 = llvm.getelementptr %57[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %45, %58 : i32, !llvm.ptr
%60 = llvm.mlir.addressof @HB : !llvm.ptr
%61 = llvm.load %60 : !llvm.ptr -> !llvm.ptr
%62 = llvm.getelementptr %61[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%59 = llvm.load %62 : !llvm.ptr -> i32
%64 = llvm.mlir.addressof @HB : !llvm.ptr
%65 = llvm.load %64 : !llvm.ptr -> !llvm.ptr
%66 = llvm.getelementptr %65[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%63 = llvm.load %66 : !llvm.ptr -> i32
%67 = llvm.mlir.addressof @HB : !llvm.ptr
%68 = llvm.load %67 : !llvm.ptr -> !llvm.ptr
%69 = llvm.getelementptr %68[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %63, %69 : i32, !llvm.ptr
%70 = llvm.mlir.addressof @HB : !llvm.ptr
%71 = llvm.load %70 : !llvm.ptr -> !llvm.ptr
%72 = llvm.getelementptr %71[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %59, %72 : i32, !llvm.ptr
%74 = llvm.mlir.addressof @HS : !llvm.ptr
%75 = llvm.load %74 : !llvm.ptr -> !llvm.ptr
%76 = llvm.getelementptr %75[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%73 = llvm.load %76 : !llvm.ptr -> f64
%78 = llvm.mlir.addressof @HS : !llvm.ptr
%79 = llvm.load %78 : !llvm.ptr -> !llvm.ptr
%80 = llvm.getelementptr %79[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%77 = llvm.load %80 : !llvm.ptr -> f64
%81 = llvm.mlir.addressof @HS : !llvm.ptr
%82 = llvm.load %81 : !llvm.ptr -> !llvm.ptr
%83 = llvm.getelementptr %82[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %77, %83 : f64, !llvm.ptr
%84 = llvm.mlir.addressof @HS : !llvm.ptr
%85 = llvm.load %84 : !llvm.ptr -> !llvm.ptr
%86 = llvm.getelementptr %85[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %73, %86 : f64, !llvm.ptr
func.return
}
func.func @heap_up(%arg0: i64) -> () {
%87 = llvm.mlir.constant(1 : i64) : i64
%88 = llvm.alloca %87 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %88 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%89 = llvm.load %88 : !llvm.ptr -> i64
%90 = arith.constant 0 : i32
%92 = arith.extsi %90 : i32 to i64
%91 = arith.cmpi sgt, %89, %92 : i64
cf.cond_br %91, ^bb1, ^bb2
^bb1:
%93 = llvm.load %88 : !llvm.ptr -> i64
%94 = arith.constant 1 : i32
%96 = arith.extsi %94 : i32 to i64
%95 = arith.subi %93, %96 : i64
%97 = arith.constant 2 : i32
%99 = arith.extsi %97 : i32 to i64
%98 = arith.divsi %95, %99 : i64
%101 = llvm.mlir.addressof @HS : !llvm.ptr
%102 = llvm.load %101 : !llvm.ptr -> !llvm.ptr
%103 = llvm.getelementptr %102[%98] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%100 = llvm.load %103 : !llvm.ptr -> f64
%105 = llvm.mlir.addressof @HS : !llvm.ptr
%106 = llvm.load %105 : !llvm.ptr -> !llvm.ptr
%107 = llvm.load %88 : !llvm.ptr -> i64
%108 = llvm.getelementptr %106[%107] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%104 = llvm.load %108 : !llvm.ptr -> f64
%109 = arith.cmpf oge, %100, %104 : f64
cf.cond_br %109, ^bb3, ^bb4
^bb3:
cf.br ^bb2
^bb4:
cf.br ^bb5
^bb5:
%111 = llvm.load %88 : !llvm.ptr -> i64
func.call @heap_swap(%98, %111) : (i64, i64) -> ()
llvm.store %98, %88 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
func.return
}
func.func @heap_down(%arg0: i64) -> () {
%112 = llvm.mlir.constant(1 : i64) : i64
%113 = llvm.alloca %112 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %113 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%114 = arith.constant 1 : i1
cf.cond_br %114, ^bb7, ^bb8
^bb7:
%115 = arith.constant 2 : i32
%116 = llvm.load %113 : !llvm.ptr -> i64
%118 = arith.extsi %115 : i32 to i64
%117 = arith.muli %118, %116 : i64
%119 = arith.constant 1 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.addi %117, %121 : i64
%122 = arith.constant 2 : i32
%123 = llvm.load %113 : !llvm.ptr -> i64
%125 = arith.extsi %122 : i32 to i64
%124 = arith.muli %125, %123 : i64
%126 = arith.constant 2 : i32
%128 = arith.extsi %126 : i32 to i64
%127 = arith.addi %124, %128 : i64
%129 = llvm.load %113 : !llvm.ptr -> i64
%130 = llvm.mlir.constant(1 : i64) : i64
%131 = llvm.alloca %130 x i64 : (i64) -> !llvm.ptr
llvm.store %129, %131 : i64, !llvm.ptr
%132 = llvm.mlir.addressof @HN : !llvm.ptr
%133 = llvm.load %132 : !llvm.ptr -> i64
%134 = arith.cmpi slt, %120, %133 : i64
%135 = scf.if %134 -> (i1) {
%137 = llvm.mlir.addressof @HS : !llvm.ptr
%138 = llvm.load %137 : !llvm.ptr -> !llvm.ptr
%139 = llvm.getelementptr %138[%120] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%136 = llvm.load %139 : !llvm.ptr -> f64
%141 = llvm.mlir.addressof @HS : !llvm.ptr
%142 = llvm.load %141 : !llvm.ptr -> !llvm.ptr
%143 = llvm.load %131 : !llvm.ptr -> i64
%144 = llvm.getelementptr %142[%143] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%140 = llvm.load %144 : !llvm.ptr -> f64
%145 = arith.cmpf ogt, %136, %140 : f64
scf.yield %145 : i1
} else {
%146 = arith.constant false
scf.yield %146 : i1
}
cf.cond_br %135, ^bb9, ^bb10
^bb9:
llvm.store %120, %131 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%147 = llvm.mlir.addressof @HN : !llvm.ptr
%148 = llvm.load %147 : !llvm.ptr -> i64
%149 = arith.cmpi slt, %127, %148 : i64
%150 = scf.if %149 -> (i1) {
%152 = llvm.mlir.addressof @HS : !llvm.ptr
%153 = llvm.load %152 : !llvm.ptr -> !llvm.ptr
%154 = llvm.getelementptr %153[%127] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%151 = llvm.load %154 : !llvm.ptr -> f64
%156 = llvm.mlir.addressof @HS : !llvm.ptr
%157 = llvm.load %156 : !llvm.ptr -> !llvm.ptr
%158 = llvm.load %131 : !llvm.ptr -> i64
%159 = llvm.getelementptr %157[%158] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%155 = llvm.load %159 : !llvm.ptr -> f64
%160 = arith.cmpf ogt, %151, %155 : f64
scf.yield %160 : i1
} else {
%161 = arith.constant false
scf.yield %161 : i1
}
cf.cond_br %150, ^bb12, ^bb13
^bb12:
llvm.store %127, %131 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%162 = llvm.load %131 : !llvm.ptr -> i64
%163 = llvm.load %113 : !llvm.ptr -> i64
%164 = arith.cmpi eq, %162, %163 : i64
cf.cond_br %164, ^bb15, ^bb16
^bb15:
cf.br ^bb8
^bb16:
cf.br ^bb17
^bb17:
%166 = llvm.load %113 : !llvm.ptr -> i64
%167 = llvm.load %131 : !llvm.ptr -> i64
func.call @heap_swap(%166, %167) : (i64, i64) -> ()
%168 = llvm.load %131 : !llvm.ptr -> i64
llvm.store %168, %113 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
func.return
}
func.func @heap_push(%arg0: f64, %arg1: f64, %arg2: i32, %arg3: i32) -> () {
%169 = func.call @side_of(%arg0, %arg1) : (f64, f64) -> f64
%170 = llvm.mlir.addressof @HX : !llvm.ptr
%171 = llvm.load %170 : !llvm.ptr -> !llvm.ptr
%172 = llvm.mlir.addressof @HN : !llvm.ptr
%173 = llvm.load %172 : !llvm.ptr -> i64
%174 = llvm.getelementptr %171[%173] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %arg0, %174 : f64, !llvm.ptr
%175 = llvm.mlir.addressof @HY : !llvm.ptr
%176 = llvm.load %175 : !llvm.ptr -> !llvm.ptr
%177 = llvm.mlir.addressof @HN : !llvm.ptr
%178 = llvm.load %177 : !llvm.ptr -> i64
%179 = llvm.getelementptr %176[%178] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %arg1, %179 : f64, !llvm.ptr
%180 = llvm.mlir.addressof @HL : !llvm.ptr
%181 = llvm.load %180 : !llvm.ptr -> !llvm.ptr
%182 = llvm.mlir.addressof @HN : !llvm.ptr
%183 = llvm.load %182 : !llvm.ptr -> i64
%184 = llvm.getelementptr %181[%183] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %arg2, %184 : i32, !llvm.ptr
%185 = llvm.mlir.addressof @HB : !llvm.ptr
%186 = llvm.load %185 : !llvm.ptr -> !llvm.ptr
%187 = llvm.mlir.addressof @HN : !llvm.ptr
%188 = llvm.load %187 : !llvm.ptr -> i64
%189 = llvm.getelementptr %186[%188] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %arg3, %189 : i32, !llvm.ptr
%190 = llvm.mlir.addressof @HS : !llvm.ptr
%191 = llvm.load %190 : !llvm.ptr -> !llvm.ptr
%192 = llvm.mlir.addressof @HN : !llvm.ptr
%193 = llvm.load %192 : !llvm.ptr -> i64
%194 = llvm.getelementptr %191[%193] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %169, %194 : f64, !llvm.ptr
%196 = llvm.mlir.addressof @HN : !llvm.ptr
%197 = llvm.load %196 : !llvm.ptr -> i64
func.call @heap_up(%197) : (i64) -> ()
%198 = llvm.mlir.addressof @HN : !llvm.ptr
%199 = llvm.load %198 : !llvm.ptr -> i64
%200 = arith.constant 1 : i32
%202 = arith.extsi %200 : i32 to i64
%201 = arith.addi %199, %202 : i64
%203 = llvm.mlir.addressof @HN : !llvm.ptr
llvm.store %201, %203 : i64, !llvm.ptr
func.return
}
func.func @main() -> i32 {
%204 = arith.constant 3 : i32
%205 = arith.constant 3 : i32
%207 = llvm.mlir.addressof @CAP : !llvm.ptr
%208 = llvm.load %207 : !llvm.ptr -> i64
%209 = arith.constant 8 : i32
%210 = arith.extsi %209 : i32 to i64
%206 = func.call @calloc(%208, %210) : (i64, i64) -> !llvm.ptr
%211 = llvm.mlir.addressof @HX : !llvm.ptr
llvm.store %206, %211 : !llvm.ptr, !llvm.ptr
%213 = llvm.mlir.addressof @CAP : !llvm.ptr
%214 = llvm.load %213 : !llvm.ptr -> i64
%215 = arith.constant 8 : i32
%216 = arith.extsi %215 : i32 to i64
%212 = func.call @calloc(%214, %216) : (i64, i64) -> !llvm.ptr
%217 = llvm.mlir.addressof @HY : !llvm.ptr
llvm.store %212, %217 : !llvm.ptr, !llvm.ptr
%219 = llvm.mlir.addressof @CAP : !llvm.ptr
%220 = llvm.load %219 : !llvm.ptr -> i64
%221 = arith.constant 8 : i32
%222 = arith.extsi %221 : i32 to i64
%218 = func.call @calloc(%220, %222) : (i64, i64) -> !llvm.ptr
%223 = llvm.mlir.addressof @HS : !llvm.ptr
llvm.store %218, %223 : !llvm.ptr, !llvm.ptr
%225 = llvm.mlir.addressof @CAP : !llvm.ptr
%226 = llvm.load %225 : !llvm.ptr -> i64
%227 = arith.constant 4 : i32
%228 = arith.extsi %227 : i32 to i64
%224 = func.call @calloc(%226, %228) : (i64, i64) -> !llvm.ptr
%229 = llvm.mlir.addressof @HL : !llvm.ptr
llvm.store %224, %229 : !llvm.ptr, !llvm.ptr
%231 = llvm.mlir.addressof @CAP : !llvm.ptr
%232 = llvm.load %231 : !llvm.ptr -> i64
%233 = arith.constant 4 : i32
%234 = arith.extsi %233 : i32 to i64
%230 = func.call @calloc(%232, %234) : (i64, i64) -> !llvm.ptr
%235 = llvm.mlir.addressof @HB : !llvm.ptr
llvm.store %230, %235 : !llvm.ptr, !llvm.ptr
%236 = llvm.mlir.addressof @HX : !llvm.ptr
%237 = llvm.load %236 : !llvm.ptr -> !llvm.ptr
%238 = llvm.mlir.zero : !llvm.ptr
%239 = llvm.icmp "eq" %237, %238 : !llvm.ptr
%240 = scf.if %239 -> (i1) {
%241 = arith.constant true
scf.yield %241 : i1
} else {
%242 = llvm.mlir.addressof @HY : !llvm.ptr
%243 = llvm.load %242 : !llvm.ptr -> !llvm.ptr
%244 = llvm.mlir.zero : !llvm.ptr
%245 = llvm.icmp "eq" %243, %244 : !llvm.ptr
scf.yield %245 : i1
}
cf.cond_br %240, ^bb18, ^bb19
^bb18:
%246 = arith.constant 1 : i32
func.return %246 : i32
^bb19:
cf.br ^bb20
^bb20:
%248 = arith.constant 1.0 : f32
%249 = arith.constant 0.0 : f32
%250 = arith.constant 0 : i32
%251 = arith.constant 0 : i32
%252 = arith.extf %248 : f32 to f64
%253 = arith.extf %249 : f32 to f64
func.call @heap_push(%252, %253, %250, %251) : (f64, f64, i32, i32) -> ()
%254 = arith.constant 1 : i32
%255 = llvm.mlir.constant(1 : i64) : i64
%256 = llvm.alloca %255 x i32 : (i64) -> !llvm.ptr
llvm.store %254, %256 : i32, !llvm.ptr
%257 = arith.constant 0 : i32
%258 = arith.extsi %257 : i32 to i64
%259 = llvm.mlir.constant(1 : i64) : i64
%260 = llvm.alloca %259 x i64 : (i64) -> !llvm.ptr
llvm.store %258, %260 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%261 = llvm.load %256 : !llvm.ptr -> i32
%262 = arith.constant 0 : i32
%263 = arith.cmpi sgt, %261, %262 : i32
cf.cond_br %263, ^bb22, ^bb23
^bb22:
%264 = llvm.load %260 : !llvm.ptr -> i64
%265 = arith.constant 1 : i32
%267 = arith.extsi %265 : i32 to i64
%266 = arith.addi %264, %267 : i64
llvm.store %266, %260 : i64, !llvm.ptr
%269 = llvm.mlir.addressof @HX : !llvm.ptr
%270 = llvm.load %269 : !llvm.ptr -> !llvm.ptr
%271 = arith.constant 0 : i32
%272 = arith.extsi %271 : i32 to i64
%273 = llvm.getelementptr %270[%272] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%268 = llvm.load %273 : !llvm.ptr -> f64
%275 = llvm.mlir.addressof @HY : !llvm.ptr
%276 = llvm.load %275 : !llvm.ptr -> !llvm.ptr
%277 = arith.constant 0 : i32
%278 = arith.extsi %277 : i32 to i64
%279 = llvm.getelementptr %276[%278] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%274 = llvm.load %279 : !llvm.ptr -> f64
%281 = llvm.mlir.addressof @HL : !llvm.ptr
%282 = llvm.load %281 : !llvm.ptr -> !llvm.ptr
%283 = arith.constant 0 : i32
%284 = arith.extsi %283 : i32 to i64
%285 = llvm.getelementptr %282[%284] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%280 = llvm.load %285 : !llvm.ptr -> i32
%287 = llvm.mlir.addressof @HB : !llvm.ptr
%288 = llvm.load %287 : !llvm.ptr -> !llvm.ptr
%289 = arith.constant 0 : i32
%290 = arith.extsi %289 : i32 to i64
%291 = llvm.getelementptr %288[%290] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%286 = llvm.load %291 : !llvm.ptr -> i32
%293 = llvm.mlir.addressof @HS : !llvm.ptr
%294 = llvm.load %293 : !llvm.ptr -> !llvm.ptr
%295 = arith.constant 0 : i32
%296 = arith.extsi %295 : i32 to i64
%297 = llvm.getelementptr %294[%296] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%292 = llvm.load %297 : !llvm.ptr -> f64
%298 = llvm.mlir.addressof @HN : !llvm.ptr
%299 = llvm.load %298 : !llvm.ptr -> i64
%300 = arith.constant 1 : i32
%302 = arith.extsi %300 : i32 to i64
%301 = arith.subi %299, %302 : i64
%303 = llvm.mlir.addressof @HN : !llvm.ptr
llvm.store %301, %303 : i64, !llvm.ptr
%304 = llvm.mlir.addressof @HN : !llvm.ptr
%305 = llvm.load %304 : !llvm.ptr -> i64
%306 = arith.constant 0 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.cmpi sgt, %305, %308 : i64
cf.cond_br %307, ^bb24, ^bb25
^bb24:
%310 = llvm.mlir.addressof @HX : !llvm.ptr
%311 = llvm.load %310 : !llvm.ptr -> !llvm.ptr
%312 = llvm.mlir.addressof @HN : !llvm.ptr
%313 = llvm.load %312 : !llvm.ptr -> i64
%314 = llvm.getelementptr %311[%313] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%309 = llvm.load %314 : !llvm.ptr -> f64
%315 = llvm.mlir.addressof @HX : !llvm.ptr
%316 = llvm.load %315 : !llvm.ptr -> !llvm.ptr
%317 = arith.constant 0 : i32
%318 = arith.extsi %317 : i32 to i64
%319 = llvm.getelementptr %316[%318] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %309, %319 : f64, !llvm.ptr
%321 = llvm.mlir.addressof @HY : !llvm.ptr
%322 = llvm.load %321 : !llvm.ptr -> !llvm.ptr
%323 = llvm.mlir.addressof @HN : !llvm.ptr
%324 = llvm.load %323 : !llvm.ptr -> i64
%325 = llvm.getelementptr %322[%324] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%320 = llvm.load %325 : !llvm.ptr -> f64
%326 = llvm.mlir.addressof @HY : !llvm.ptr
%327 = llvm.load %326 : !llvm.ptr -> !llvm.ptr
%328 = arith.constant 0 : i32
%329 = arith.extsi %328 : i32 to i64
%330 = llvm.getelementptr %327[%329] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %320, %330 : f64, !llvm.ptr
%332 = llvm.mlir.addressof @HL : !llvm.ptr
%333 = llvm.load %332 : !llvm.ptr -> !llvm.ptr
%334 = llvm.mlir.addressof @HN : !llvm.ptr
%335 = llvm.load %334 : !llvm.ptr -> i64
%336 = llvm.getelementptr %333[%335] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%331 = llvm.load %336 : !llvm.ptr -> i32
%337 = llvm.mlir.addressof @HL : !llvm.ptr
%338 = llvm.load %337 : !llvm.ptr -> !llvm.ptr
%339 = arith.constant 0 : i32
%340 = arith.extsi %339 : i32 to i64
%341 = llvm.getelementptr %338[%340] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %331, %341 : i32, !llvm.ptr
%343 = llvm.mlir.addressof @HB : !llvm.ptr
%344 = llvm.load %343 : !llvm.ptr -> !llvm.ptr
%345 = llvm.mlir.addressof @HN : !llvm.ptr
%346 = llvm.load %345 : !llvm.ptr -> i64
%347 = llvm.getelementptr %344[%346] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%342 = llvm.load %347 : !llvm.ptr -> i32
%348 = llvm.mlir.addressof @HB : !llvm.ptr
%349 = llvm.load %348 : !llvm.ptr -> !llvm.ptr
%350 = arith.constant 0 : i32
%351 = arith.extsi %350 : i32 to i64
%352 = llvm.getelementptr %349[%351] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %342, %352 : i32, !llvm.ptr
%354 = llvm.mlir.addressof @HS : !llvm.ptr
%355 = llvm.load %354 : !llvm.ptr -> !llvm.ptr
%356 = llvm.mlir.addressof @HN : !llvm.ptr
%357 = llvm.load %356 : !llvm.ptr -> i64
%358 = llvm.getelementptr %355[%357] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%353 = llvm.load %358 : !llvm.ptr -> f64
%359 = llvm.mlir.addressof @HS : !llvm.ptr
%360 = llvm.load %359 : !llvm.ptr -> !llvm.ptr
%361 = arith.constant 0 : i32
%362 = arith.extsi %361 : i32 to i64
%363 = llvm.getelementptr %360[%362] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %353, %363 : f64, !llvm.ptr
%365 = arith.constant 0 : i32
%366 = arith.extsi %365 : i32 to i64
func.call @heap_down(%366) : (i64) -> ()
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%367 = arith.addf %274, %292 : f64
%368 = arith.addf %268, %292 : f64
%370 = arith.constant 1 : i32
%371 = arith.addi %286, %370 : i32
func.call @heap_push(%268, %367, %280, %371) : (f64, f64, i32, i32) -> ()
%373 = arith.constant 1 : i32
%374 = arith.addi %280, %373 : i32
func.call @heap_push(%368, %274, %374, %286) : (f64, f64, i32, i32) -> ()
%375 = arith.cmpi sle, %280, %204 : i32
%376 = scf.if %375 -> (i1) {
%377 = arith.constant 1 : i32
%378 = arith.addi %286, %377 : i32
%379 = arith.cmpi sle, %378, %205 : i32
scf.yield %379 : i1
} else {
%380 = arith.constant false
scf.yield %380 : i1
}
cf.cond_br %376, ^bb27, ^bb28
^bb27:
%381 = llvm.load %256 : !llvm.ptr -> i32
%382 = arith.constant 1 : i32
%383 = arith.addi %381, %382 : i32
llvm.store %383, %256 : i32, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%384 = arith.constant 1 : i32
%385 = arith.addi %280, %384 : i32
%386 = arith.cmpi sle, %385, %204 : i32
%387 = scf.if %386 -> (i1) {
%388 = arith.cmpi sle, %286, %205 : i32
scf.yield %388 : i1
} else {
%389 = arith.constant false
scf.yield %389 : i1
}
cf.cond_br %387, ^bb30, ^bb31
^bb30:
%390 = llvm.load %256 : !llvm.ptr -> i32
%391 = arith.constant 1 : i32
%392 = arith.addi %390, %391 : i32
llvm.store %392, %256 : i32, !llvm.ptr
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%393 = arith.cmpi sle, %280, %204 : i32
%394 = scf.if %393 -> (i1) {
%395 = arith.cmpi sle, %286, %205 : i32
scf.yield %395 : i1
} else {
%396 = arith.constant false
scf.yield %396 : i1
}
cf.cond_br %394, ^bb33, ^bb34
^bb33:
%397 = llvm.load %256 : !llvm.ptr -> i32
%398 = arith.constant 1 : i32
%399 = arith.subi %397, %398 : i32
llvm.store %399, %256 : i32, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
cf.br ^bb21
^bb23:
%400 = llvm.mlir.addressof @str_0 : !llvm.ptr
%401 = llvm.load %260 : !llvm.ptr -> i64
%402 = llvm.call @printf(%400, %401) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%403 = arith.constant 0 : i32
func.return %403 : i32
}
}