Problem 790
Clock Grid: C(10^5) via sweep line with a 12-bucket segment tree. Each rectangle increments the overlap count mod 12 of covered cells.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(2^n) | ? |
|---|
| Space complexity | O(n^2) | ? |
|---|
| Approach | Flow solution | Not curated |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 790
# Clock Grid: C(10^5) via sweep line with a 12-bucket segment tree.
# Each rectangle increments the overlap count mod 12 of covered cells.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
const M_VAL: i64 = 50515093
const S0: i64 = 290797
let mut g_seg: ptr<i64> = null
let mut g_lazy: ptr<i32> = null
let mut g_y_vals: ptr<i64> = null
let mut g_tmp12: ptr<i64> = null
function heapsort_i64(arr: ptr<i64>, n: i64) -> void {
if n < 2 { return }
let mut i: i64 = n / 2 - 1
while i >= 0 {
let mut root: i64 = i
while 2 * root + 1 < n {
let mut child: i64 = 2 * root + 1
if child + 1 < n && arr[child + 1] > arr[child] {
child = child + 1
}
if arr[root] < arr[child] {
let t: i64 = arr[root]
arr[root] = arr[child]
arr[child] = t
root = child
} else {
break
}
}
i = i - 1
}
let mut end: i64 = n - 1
while end > 0 {
let t: i64 = arr[0]
arr[0] = arr[end]
arr[end] = t
let mut root: i64 = 0
while 2 * root + 1 < end {
let mut child: i64 = 2 * root + 1
if child + 1 < end && arr[child + 1] > arr[child] {
child = child + 1
}
if arr[root] < arr[child] {
let t2: i64 = arr[root]
arr[root] = arr[child]
arr[child] = t2
root = child
} else {
break
}
}
end = end - 1
}
}
function heapsort_idx(idx: ptr<i64>, val: ptr<i64>, n: i64) -> void {
if n < 2 { return }
let mut i: i64 = n / 2 - 1
while i >= 0 {
let mut root: i64 = i
while 2 * root + 1 < n {
let mut child: i64 = 2 * root + 1
if child + 1 < n && val[idx[child + 1]] > val[idx[child]] {
child = child + 1
}
if val[idx[root]] < val[idx[child]] {
let t: i64 = idx[root]
idx[root] = idx[child]
idx[child] = t
root = child
} else {
break
}
}
i = i - 1
}
let mut end: i64 = n - 1
while end > 0 {
let t: i64 = idx[0]
idx[0] = idx[end]
idx[end] = t
let mut root: i64 = 0
while 2 * root + 1 < end {
let mut child: i64 = 2 * root + 1
if child + 1 < end && val[idx[child + 1]] > val[idx[child]] {
child = child + 1
}
if val[idx[root]] < val[idx[child]] {
let t2: i64 = idx[root]
idx[root] = idx[child]
idx[child] = t2
root = child
} else {
break
}
}
end = end - 1
}
}
function bsearch_idx(arr: ptr<i64>, n: i64, v: i64) -> i64 {
let mut lo: i64 = 0
let mut hi: i64 = n - 1
while lo < hi {
let mid: i64 = (lo + hi) >> 1
if arr[mid] < v {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
function build_tree(node: i64, l: i64, r: i64) -> void {
let base: i64 = node * 12
if r - l == 1 {
g_seg[base] = g_y_vals[l + 1] - g_y_vals[l]
return
}
let mid: i64 = (l + r) >> 1
let left: i64 = node << 1
build_tree(left, l, mid)
build_tree(left + 1, mid, r)
g_seg[base] = g_seg[left * 12] + g_seg[(left + 1) * 12]
}
function apply_rot(node: i64, shift: i64) -> void {
if shift == 0 { return }
let sh: i64 = shift % 12
let base: i64 = node * 12
for i in 0..12 {
g_tmp12[i] = g_seg[base + ((i - sh + 12) % 12)]
}
for i in 0..12 {
g_seg[base + i] = g_tmp12[i]
}
let v: i64 = g_lazy[node] + sh
if v >= 12 {
g_lazy[node] = (v - 12) as i32
} else {
g_lazy[node] = v as i32
}
}
function push_down(node: i64) -> void {
let s: i64 = g_lazy[node] as i64
if s != 0 {
let left: i64 = node << 1
apply_rot(left, s)
apply_rot(left + 1, s)
g_lazy[node] = 0
}
}
function pull_up(node: i64) -> void {
let base: i64 = node * 12
let bl: i64 = (node << 1) * 12
let br: i64 = ((node << 1) + 1) * 12
for i in 0..12 {
g_seg[base + i] = g_seg[bl + i] + g_seg[br + i]
}
}
function update_tree(node: i64, l: i64, r: i64, ql: i64, qr: i64, shift: i64) -> void {
if ql <= l && r <= qr {
apply_rot(node, shift)
return
}
push_down(node)
let mid: i64 = (l + r) >> 1
let left: i64 = node << 1
if ql < mid { update_tree(left, l, mid, ql, qr, shift) }
if qr > mid { update_tree(left + 1, mid, r, ql, qr, shift) }
pull_up(node)
}
function main() -> i32 {
let t: i64 = 100000
let cap: i64 = 2 + 2 * t
let x_arr: ptr<i64> = malloc(cap * 8) as ptr<i64>
let y_arr: ptr<i64> = malloc(cap * 8) as ptr<i64>
let mut nx: i64 = 0
let mut ny: i64 = 0
x_arr[nx] = 0
nx = nx + 1
x_arr[nx] = M_VAL
nx = nx + 1
y_arr[ny] = 0
ny = ny + 1
y_arr[ny] = M_VAL
ny = ny + 1
let ev_x: ptr<i64> = malloc(2 * t * 8) as ptr<i64>
let ev_shift: ptr<i32> = malloc(2 * t * 4) as ptr<i32>
let ev_yl: ptr<i64> = malloc(2 * t * 8) as ptr<i64>
let ev_yh1: ptr<i64> = malloc(2 * t * 8) as ptr<i64>
let mut nev: i64 = 0
let mut s: i64 = S0
for i in 0..t {
let x1: i64 = s
s = (s * s) % M_VAL
let x2: i64 = s
s = (s * s) % M_VAL
let y1: i64 = s
s = (s * s) % M_VAL
let y2: i64 = s
s = (s * s) % M_VAL
let xl: i64
let xh: i64
if x1 <= x2 {
xl = x1
xh = x2
} else {
xl = x2
xh = x1
}
let yl: i64
let yh: i64
if y1 <= y2 {
yl = y1
yh = y2
} else {
yl = y2
yh = y1
}
let xh1: i64 = xh + 1
let yh1: i64 = yh + 1
x_arr[nx] = xl
nx = nx + 1
x_arr[nx] = xh1
nx = nx + 1
y_arr[ny] = yl
ny = ny + 1
y_arr[ny] = yh1
ny = ny + 1
ev_x[nev] = xl
ev_shift[nev] = 1
ev_yl[nev] = yl
ev_yh1[nev] = yh1
nev = nev + 1
ev_x[nev] = xh1
ev_shift[nev] = 11
ev_yl[nev] = yl
ev_yh1[nev] = yh1
nev = nev + 1
}
# Sort and deduplicate x and y
heapsort_i64(x_arr, nx)
heapsort_i64(y_arr, ny)
let mut num_x: i64 = 1
for i in 1..nx {
if x_arr[i] != x_arr[num_x - 1] {
x_arr[num_x] = x_arr[i]
num_x = num_x + 1
}
}
let mut num_y: i64 = 1
for i in 1..ny {
if y_arr[i] != y_arr[num_y - 1] {
y_arr[num_y] = y_arr[i]
num_y = num_y + 1
}
}
# Map event y-values to compressed indices
for i in 0..nev {
ev_yl[i] = bsearch_idx(y_arr, num_y, ev_yl[i])
ev_yh1[i] = bsearch_idx(y_arr, num_y, ev_yh1[i])
}
# Sort events by x using index array
let ev_idx: ptr<i64> = malloc(nev * 8) as ptr<i64>
for i in 0..nev {
ev_idx[i] = i
}
heapsort_idx(ev_idx, ev_x, nev)
# Build segment tree over y-intervals
let m: i64 = num_y - 1
let tree_size: i64 = 4 * m + 5
g_seg = calloc(12 * tree_size, 8) as ptr<i64>
g_lazy = calloc(tree_size, 4) as ptr<i32>
g_y_vals = y_arr
g_tmp12 = malloc(12 * 8) as ptr<i64>
build_tree(1, 0, m)
# Sweep along x
let counts: ptr<i64> = calloc(12, 8) as ptr<i64>
let mut ev_i: i64 = 0
for i in 0..(num_x - 1) {
let x: i64 = x_arr[i]
while ev_i < nev && ev_x[ev_idx[ev_i]] == x {
update_tree(1, 0, m, ev_yl[ev_idx[ev_i]], ev_yh1[ev_idx[ev_i]], ev_shift[ev_idx[ev_i]] as i64)
ev_i = ev_i + 1
}
let width: i64 = x_arr[i + 1] - x
if width != 0 {
let base: i64 = 12
for r in 0..12 {
counts[r] = counts[r] + width * g_seg[base + r]
}
}
}
# Convert overlap residues to displayed hours
let mut total: i64 = 12 * counts[0]
for r in 1..12 {
total = total + r * counts[r]
}
free(g_seg)
free(g_lazy)
free(g_tmp12)
free(x_arr)
free(y_arr)
free(ev_x)
free(ev_shift)
free(ev_yl)
free(ev_yh1)
free(ev_idx)
free(counts)
printf("%lld\n", total)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
void heapsort_i64_ptr_i64_i64(int64_t* arr, int64_t n);
void heapsort_idx_ptr_i64_ptr_i64_i64(int64_t* idx, int64_t* val, int64_t n);
int64_t bsearch_idx_ptr_i64_i64_i64(int64_t* arr, int64_t n, int64_t v);
void build_tree_i64_i64_i64(int64_t node, int64_t l, int64_t r);
void apply_rot_i64_i64(int64_t node, int64_t shift);
void push_down_i64(int64_t node);
void pull_up_i64(int64_t node);
void update_tree_i64_i64_i64_i64_i64_i64(int64_t node, int64_t l, int64_t r, int64_t ql, int64_t qr, int64_t shift);
int32_t main(void);
static const int64_t M_VAL = 50515093;
static const int64_t S0 = 290797;
/* Module statics */
static int64_t* g_seg = NULL;
static int32_t* g_lazy = NULL;
static int64_t* g_y_vals = NULL;
static int64_t* g_tmp12 = NULL;
void heapsort_i64_ptr_i64_i64(int64_t* arr, int64_t n) {
if (n < 2) {
return;
}
int64_t i = (FLOW_CHECKED_DIV((n), (2)) - 1);
while (i >= 0) {
int64_t root = i;
while (((2 * root) + 1) < n) {
int64_t child = ((2 * root) + 1);
if (((child + 1) < n && arr[(child + 1)] > arr[child])) {
child = (child + 1);
}
if (arr[root] < arr[child]) {
int64_t t = arr[root];
arr[root] = arr[child];
arr[child] = t;
root = child;
} else {
break;
}
}
i = (i - 1);
}
int64_t end = (n - 1);
while (end > 0) {
int64_t t = arr[0];
arr[0] = arr[end];
arr[end] = t;
int64_t root = 0;
while (((2 * root) + 1) < end) {
int64_t child = ((2 * root) + 1);
if (((child + 1) < end && arr[(child + 1)] > arr[child])) {
child = (child + 1);
}
if (arr[root] < arr[child]) {
int64_t t2 = arr[root];
arr[root] = arr[child];
arr[child] = t2;
root = child;
} else {
break;
}
}
end = (end - 1);
}
}
void heapsort_idx_ptr_i64_ptr_i64_i64(int64_t* idx, int64_t* val, int64_t n) {
if (n < 2) {
return;
}
int64_t i = (FLOW_CHECKED_DIV((n), (2)) - 1);
while (i >= 0) {
int64_t root = i;
while (((2 * root) + 1) < n) {
int64_t child = ((2 * root) + 1);
if (((child + 1) < n && val[idx[(child + 1)]] > val[idx[child]])) {
child = (child + 1);
}
if (val[idx[root]] < val[idx[child]]) {
int64_t t = idx[root];
idx[root] = idx[child];
idx[child] = t;
root = child;
} else {
break;
}
}
i = (i - 1);
}
int64_t end = (n - 1);
while (end > 0) {
int64_t t = idx[0];
idx[0] = idx[end];
idx[end] = t;
int64_t root = 0;
while (((2 * root) + 1) < end) {
int64_t child = ((2 * root) + 1);
if (((child + 1) < end && val[idx[(child + 1)]] > val[idx[child]])) {
child = (child + 1);
}
if (val[idx[root]] < val[idx[child]]) {
int64_t t2 = idx[root];
idx[root] = idx[child];
idx[child] = t2;
root = child;
} else {
break;
}
}
end = (end - 1);
}
}
int64_t bsearch_idx_ptr_i64_i64_i64(int64_t* arr, int64_t n, int64_t v) {
int64_t lo = 0;
int64_t hi = (n - 1);
while (lo < hi) {
int64_t mid = FLOW_CHECKED_SHR(((lo + hi)), (1));
if (arr[mid] < v) {
lo = (mid + 1);
} else {
hi = mid;
}
}
return lo;
}
void build_tree_i64_i64_i64(int64_t node, int64_t l, int64_t r) {
int64_t base = (node * 12);
if ((r - l) == 1) {
g_seg[base] = (g_y_vals[(l + 1)] - g_y_vals[l]);
return;
}
int64_t mid = FLOW_CHECKED_SHR(((l + r)), (1));
int64_t left = FLOW_CHECKED_SHL((node), (1));
build_tree_i64_i64_i64(left, l, mid);
build_tree_i64_i64_i64((left + 1), mid, r);
g_seg[base] = (g_seg[(left * 12)] + g_seg[((left + 1) * 12)]);
}
void apply_rot_i64_i64(int64_t node, int64_t shift) {
if (shift == 0) {
return;
}
int64_t sh = FLOW_CHECKED_MOD((shift), (12));
int64_t base = (node * 12);
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= 12) ? i < 12 : i > 12; i += (0 <= 12) ? 1 : -1) {
g_tmp12[i] = g_seg[(base + FLOW_CHECKED_MOD((((i - sh) + 12)), (12)))];
}
int32_t __flow_step_2 = 1;
for (int32_t i = 0; (0 <= 12) ? i < 12 : i > 12; i += (0 <= 12) ? 1 : -1) {
g_seg[(base + i)] = g_tmp12[i];
}
int64_t v = (g_lazy[node] + sh);
if (v >= 12) {
g_lazy[node] = ((int32_t)((v - 12)));
} else {
g_lazy[node] = ((int32_t)(v));
}
}
void push_down_i64(int64_t node) {
int64_t s = ((int64_t)(g_lazy[node]));
if (s != 0) {
int64_t left = FLOW_CHECKED_SHL((node), (1));
apply_rot_i64_i64(left, s);
apply_rot_i64_i64((left + 1), s);
g_lazy[node] = 0;
}
}
void pull_up_i64(int64_t node) {
int64_t base = (node * 12);
int64_t bl = (FLOW_CHECKED_SHL((node), (1)) * 12);
int64_t br = ((FLOW_CHECKED_SHL((node), (1)) + 1) * 12);
int32_t __flow_step_3 = 1;
for (int32_t i = 0; (0 <= 12) ? i < 12 : i > 12; i += (0 <= 12) ? 1 : -1) {
g_seg[(base + i)] = (g_seg[(bl + i)] + g_seg[(br + i)]);
}
}
void update_tree_i64_i64_i64_i64_i64_i64(int64_t node, int64_t l, int64_t r, int64_t ql, int64_t qr, int64_t shift) {
if ((ql <= l && r <= qr)) {
apply_rot_i64_i64(node, shift);
return;
}
push_down_i64(node);
int64_t mid = FLOW_CHECKED_SHR(((l + r)), (1));
int64_t left = FLOW_CHECKED_SHL((node), (1));
if (ql < mid) {
update_tree_i64_i64_i64_i64_i64_i64(left, l, mid, ql, qr, shift);
}
if (qr > mid) {
update_tree_i64_i64_i64_i64_i64_i64((left + 1), mid, r, ql, qr, shift);
}
pull_up_i64(node);
}
int32_t main(void) {
int64_t t = 100000;
int64_t cap = (2 + (2 * t));
int64_t* x_arr = (int64_t*)(((int64_t*)(malloc((cap * 8)))));
int64_t* y_arr = (int64_t*)(((int64_t*)(malloc((cap * 8)))));
int64_t nx = 0;
int64_t ny = 0;
x_arr[nx] = 0;
nx = (nx + 1);
x_arr[nx] = M_VAL;
nx = (nx + 1);
y_arr[ny] = 0;
ny = (ny + 1);
y_arr[ny] = M_VAL;
ny = (ny + 1);
int64_t* ev_x = (int64_t*)(((int64_t*)(malloc(((2 * t) * 8)))));
int32_t* ev_shift = (int32_t*)(((int32_t*)(malloc(((2 * t) * 4)))));
int64_t* ev_yl = (int64_t*)(((int64_t*)(malloc(((2 * t) * 8)))));
int64_t* ev_yh1 = (int64_t*)(((int64_t*)(malloc(((2 * t) * 8)))));
int64_t nev = 0;
int64_t s = S0;
int32_t __flow_step_4 = 1;
for (int32_t i = 0; (0 <= t) ? i < t : i > t; i += (0 <= t) ? 1 : -1) {
int64_t x1 = s;
s = FLOW_CHECKED_MOD(((s * s)), (M_VAL));
int64_t x2 = s;
s = FLOW_CHECKED_MOD(((s * s)), (M_VAL));
int64_t y1 = s;
s = FLOW_CHECKED_MOD(((s * s)), (M_VAL));
int64_t y2 = s;
s = FLOW_CHECKED_MOD(((s * s)), (M_VAL));
int64_t xl;
int64_t xh;
if (x1 <= x2) {
xl = x1;
xh = x2;
} else {
xl = x2;
xh = x1;
}
int64_t yl;
int64_t yh;
if (y1 <= y2) {
yl = y1;
yh = y2;
} else {
yl = y2;
yh = y1;
}
int64_t xh1 = (xh + 1);
int64_t yh1 = (yh + 1);
x_arr[nx] = xl;
nx = (nx + 1);
x_arr[nx] = xh1;
nx = (nx + 1);
y_arr[ny] = yl;
ny = (ny + 1);
y_arr[ny] = yh1;
ny = (ny + 1);
ev_x[nev] = xl;
ev_shift[nev] = 1;
ev_yl[nev] = yl;
ev_yh1[nev] = yh1;
nev = (nev + 1);
ev_x[nev] = xh1;
ev_shift[nev] = 11;
ev_yl[nev] = yl;
ev_yh1[nev] = yh1;
nev = (nev + 1);
}
heapsort_i64_ptr_i64_i64(x_arr, nx);
heapsort_i64_ptr_i64_i64(y_arr, ny);
int64_t num_x = 1;
int32_t __flow_step_5 = 1;
for (int32_t i = 1; (1 <= nx) ? i < nx : i > nx; i += (1 <= nx) ? 1 : -1) {
if (x_arr[i] != x_arr[(num_x - 1)]) {
x_arr[num_x] = x_arr[i];
num_x = (num_x + 1);
}
}
int64_t num_y = 1;
int32_t __flow_step_6 = 1;
for (int32_t i = 1; (1 <= ny) ? i < ny : i > ny; i += (1 <= ny) ? 1 : -1) {
if (y_arr[i] != y_arr[(num_y - 1)]) {
y_arr[num_y] = y_arr[i];
num_y = (num_y + 1);
}
}
int32_t __flow_step_7 = 1;
for (int32_t i = 0; (0 <= nev) ? i < nev : i > nev; i += (0 <= nev) ? 1 : -1) {
ev_yl[i] = bsearch_idx_ptr_i64_i64_i64(y_arr, num_y, ev_yl[i]);
ev_yh1[i] = bsearch_idx_ptr_i64_i64_i64(y_arr, num_y, ev_yh1[i]);
}
int64_t* ev_idx = (int64_t*)(((int64_t*)(malloc((nev * 8)))));
int32_t __flow_step_8 = 1;
for (int32_t i = 0; (0 <= nev) ? i < nev : i > nev; i += (0 <= nev) ? 1 : -1) {
ev_idx[i] = i;
}
heapsort_idx_ptr_i64_ptr_i64_i64(ev_idx, ev_x, nev);
int64_t m = (num_y - 1);
int64_t tree_size = ((4 * m) + 5);
g_seg = ((int64_t*)(calloc((12 * tree_size), 8)));
g_lazy = ((int32_t*)(calloc(tree_size, 4)));
g_y_vals = y_arr;
g_tmp12 = ((int64_t*)(malloc((12 * 8))));
build_tree_i64_i64_i64(1, 0, m);
int64_t* counts = (int64_t*)(((int64_t*)(calloc(12, 8))));
int64_t ev_i = 0;
int32_t __flow_step_9 = 1;
for (int32_t i = 0; (0 <= (num_x - 1)) ? i < (num_x - 1) : i > (num_x - 1); i += (0 <= (num_x - 1)) ? 1 : -1) {
int64_t x = x_arr[i];
while ((ev_i < nev && ev_x[ev_idx[ev_i]] == x)) {
update_tree_i64_i64_i64_i64_i64_i64(1, 0, m, ev_yl[ev_idx[ev_i]], ev_yh1[ev_idx[ev_i]], ((int64_t)(ev_shift[ev_idx[ev_i]])));
ev_i = (ev_i + 1);
}
int64_t width = (x_arr[(i + 1)] - x);
if (width != 0) {
int64_t base = 12;
int32_t __flow_step_10 = 1;
for (int32_t r = 0; (0 <= 12) ? r < 12 : r > 12; r += (0 <= 12) ? 1 : -1) {
counts[r] = (counts[r] + (width * g_seg[(base + r)]));
}
}
}
int64_t total = (12 * counts[0]);
int32_t __flow_step_11 = 1;
for (int32_t r = 1; (1 <= 12) ? r < 12 : r > 12; r += (1 <= 12) ? 1 : -1) {
total = (total + (r * counts[r]));
}
free(g_seg);
free(g_lazy);
free(g_tmp12);
free(x_arr);
free(y_arr);
free(ev_x);
free(ev_shift);
free(ev_yl);
free(ev_yh1);
free(ev_idx);
free(counts);
printf("%lld\n", total);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @malloc(i64) -> !llvm.ptr
// Constant: M_VAL
llvm.mlir.global internal constant @M_VAL(50515093 : i64) : i64
// Constant: S0
llvm.mlir.global internal constant @S0(290797 : i64) : i64
// Module static: g_seg
llvm.mlir.global internal @g_seg() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: g_lazy
llvm.mlir.global internal @g_lazy() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
// Module static: g_y_vals
llvm.mlir.global internal @g_y_vals() {addr_space = 0 : i32} : !llvm.ptr {
%2 = llvm.mlir.zero : !llvm.ptr
llvm.return %2 : !llvm.ptr
}
// Module static: g_tmp12
llvm.mlir.global internal @g_tmp12() {addr_space = 0 : i32} : !llvm.ptr {
%3 = llvm.mlir.zero : !llvm.ptr
llvm.return %3 : !llvm.ptr
}
func.func @heapsort_i64(%arg0: !llvm.ptr, %arg1: i64) -> () {
%4 = arith.constant 2 : i32
%6 = arith.extsi %4 : i32 to i64
%5 = arith.cmpi slt, %arg1, %6 : i64
cf.cond_br %5, ^bb0, ^bb1
^bb0:
func.return
^bb1:
cf.br ^bb2
^bb2:
%7 = arith.constant 2 : i32
%9 = arith.extsi %7 : i32 to i64
%8 = arith.divsi %arg1, %9 : i64
%10 = arith.constant 1 : i32
%12 = arith.extsi %10 : i32 to i64
%11 = arith.subi %8, %12 : i64
%13 = llvm.mlir.constant(1 : i64) : i64
%14 = llvm.alloca %13 x i64 : (i64) -> !llvm.ptr
llvm.store %11, %14 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%15 = llvm.load %14 : !llvm.ptr -> i64
%16 = arith.constant 0 : i32
%18 = arith.extsi %16 : i32 to i64
%17 = arith.cmpi sge, %15, %18 : i64
cf.cond_br %17, ^bb4, ^bb5
^bb4:
%19 = llvm.load %14 : !llvm.ptr -> i64
%20 = llvm.mlir.constant(1 : i64) : i64
%21 = llvm.alloca %20 x i64 : (i64) -> !llvm.ptr
llvm.store %19, %21 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%22 = arith.constant 2 : i32
%23 = llvm.load %21 : !llvm.ptr -> i64
%25 = arith.extsi %22 : i32 to i64
%24 = arith.muli %25, %23 : i64
%26 = arith.constant 1 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.addi %24, %28 : i64
%29 = arith.cmpi slt, %27, %arg1 : i64
cf.cond_br %29, ^bb7, ^bb8
^bb7:
%30 = arith.constant 2 : i32
%31 = llvm.load %21 : !llvm.ptr -> i64
%33 = arith.extsi %30 : i32 to i64
%32 = arith.muli %33, %31 : i64
%34 = arith.constant 1 : i32
%36 = arith.extsi %34 : i32 to i64
%35 = arith.addi %32, %36 : i64
%37 = llvm.mlir.constant(1 : i64) : i64
%38 = llvm.alloca %37 x i64 : (i64) -> !llvm.ptr
llvm.store %35, %38 : i64, !llvm.ptr
%39 = llvm.load %38 : !llvm.ptr -> i64
%40 = arith.constant 1 : i32
%42 = arith.extsi %40 : i32 to i64
%41 = arith.addi %39, %42 : i64
%43 = arith.cmpi slt, %41, %arg1 : i64
%44 = scf.if %43 -> (i1) {
%46 = llvm.load %38 : !llvm.ptr -> i64
%47 = arith.constant 1 : i32
%49 = arith.extsi %47 : i32 to i64
%48 = arith.addi %46, %49 : i64
%50 = llvm.getelementptr %arg0[%48] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%45 = llvm.load %50 : !llvm.ptr -> i64
%52 = llvm.load %38 : !llvm.ptr -> i64
%53 = llvm.getelementptr %arg0[%52] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%51 = llvm.load %53 : !llvm.ptr -> i64
%54 = arith.cmpi sgt, %45, %51 : i64
scf.yield %54 : i1
} else {
%55 = arith.constant false
scf.yield %55 : i1
}
cf.cond_br %44, ^bb9, ^bb10
^bb9:
%56 = llvm.load %38 : !llvm.ptr -> i64
%57 = arith.constant 1 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.addi %56, %59 : i64
llvm.store %58, %38 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%61 = llvm.load %21 : !llvm.ptr -> i64
%62 = llvm.getelementptr %arg0[%61] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%60 = llvm.load %62 : !llvm.ptr -> i64
%64 = llvm.load %38 : !llvm.ptr -> i64
%65 = llvm.getelementptr %arg0[%64] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%63 = llvm.load %65 : !llvm.ptr -> i64
%66 = arith.cmpi slt, %60, %63 : i64
cf.cond_br %66, ^bb12, ^bb13
^bb12:
%68 = llvm.load %21 : !llvm.ptr -> i64
%69 = llvm.getelementptr %arg0[%68] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%67 = llvm.load %69 : !llvm.ptr -> i64
%71 = llvm.load %38 : !llvm.ptr -> i64
%72 = llvm.getelementptr %arg0[%71] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%70 = llvm.load %72 : !llvm.ptr -> i64
%73 = llvm.load %21 : !llvm.ptr -> i64
%74 = llvm.getelementptr %arg0[%73] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %70, %74 : i64, !llvm.ptr
%75 = llvm.load %38 : !llvm.ptr -> i64
%76 = llvm.getelementptr %arg0[%75] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %67, %76 : i64, !llvm.ptr
%77 = llvm.load %38 : !llvm.ptr -> i64
llvm.store %77, %21 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb8
^bb14:
cf.br ^bb6
^bb8:
%78 = llvm.load %14 : !llvm.ptr -> i64
%79 = arith.constant 1 : i32
%81 = arith.extsi %79 : i32 to i64
%80 = arith.subi %78, %81 : i64
llvm.store %80, %14 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%82 = arith.constant 1 : i32
%84 = arith.extsi %82 : i32 to i64
%83 = arith.subi %arg1, %84 : i64
%85 = llvm.mlir.constant(1 : i64) : i64
%86 = llvm.alloca %85 x i64 : (i64) -> !llvm.ptr
llvm.store %83, %86 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%87 = llvm.load %86 : !llvm.ptr -> i64
%88 = arith.constant 0 : i32
%90 = arith.extsi %88 : i32 to i64
%89 = arith.cmpi sgt, %87, %90 : i64
cf.cond_br %89, ^bb16, ^bb17
^bb16:
%92 = arith.constant 0 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.getelementptr %arg0[%93] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%91 = llvm.load %94 : !llvm.ptr -> i64
%96 = llvm.load %86 : !llvm.ptr -> i64
%97 = llvm.getelementptr %arg0[%96] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%95 = llvm.load %97 : !llvm.ptr -> i64
%98 = arith.constant 0 : i32
%99 = arith.extsi %98 : i32 to i64
%100 = llvm.getelementptr %arg0[%99] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %95, %100 : i64, !llvm.ptr
%101 = llvm.load %86 : !llvm.ptr -> i64
%102 = llvm.getelementptr %arg0[%101] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %91, %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
cf.br ^bb18
^bb18:
%107 = arith.constant 2 : i32
%108 = llvm.load %106 : !llvm.ptr -> i64
%110 = arith.extsi %107 : i32 to i64
%109 = arith.muli %110, %108 : i64
%111 = arith.constant 1 : i32
%113 = arith.extsi %111 : i32 to i64
%112 = arith.addi %109, %113 : i64
%114 = llvm.load %86 : !llvm.ptr -> i64
%115 = arith.cmpi slt, %112, %114 : i64
cf.cond_br %115, ^bb19, ^bb20
^bb19:
%116 = arith.constant 2 : i32
%117 = llvm.load %106 : !llvm.ptr -> i64
%119 = arith.extsi %116 : i32 to i64
%118 = arith.muli %119, %117 : i64
%120 = arith.constant 1 : i32
%122 = arith.extsi %120 : i32 to i64
%121 = arith.addi %118, %122 : i64
%123 = llvm.mlir.constant(1 : i64) : i64
%124 = llvm.alloca %123 x i64 : (i64) -> !llvm.ptr
llvm.store %121, %124 : i64, !llvm.ptr
%125 = llvm.load %124 : !llvm.ptr -> i64
%126 = arith.constant 1 : i32
%128 = arith.extsi %126 : i32 to i64
%127 = arith.addi %125, %128 : i64
%129 = llvm.load %86 : !llvm.ptr -> i64
%130 = arith.cmpi slt, %127, %129 : i64
%131 = scf.if %130 -> (i1) {
%133 = llvm.load %124 : !llvm.ptr -> i64
%134 = arith.constant 1 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.addi %133, %136 : i64
%137 = llvm.getelementptr %arg0[%135] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%132 = llvm.load %137 : !llvm.ptr -> i64
%139 = llvm.load %124 : !llvm.ptr -> i64
%140 = llvm.getelementptr %arg0[%139] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%138 = llvm.load %140 : !llvm.ptr -> i64
%141 = arith.cmpi sgt, %132, %138 : i64
scf.yield %141 : i1
} else {
%142 = arith.constant false
scf.yield %142 : i1
}
cf.cond_br %131, ^bb21, ^bb22
^bb21:
%143 = llvm.load %124 : !llvm.ptr -> i64
%144 = arith.constant 1 : i32
%146 = arith.extsi %144 : i32 to i64
%145 = arith.addi %143, %146 : i64
llvm.store %145, %124 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%148 = llvm.load %106 : !llvm.ptr -> i64
%149 = llvm.getelementptr %arg0[%148] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%147 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.load %124 : !llvm.ptr -> i64
%152 = llvm.getelementptr %arg0[%151] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%150 = llvm.load %152 : !llvm.ptr -> i64
%153 = arith.cmpi slt, %147, %150 : i64
cf.cond_br %153, ^bb24, ^bb25
^bb24:
%155 = llvm.load %106 : !llvm.ptr -> i64
%156 = llvm.getelementptr %arg0[%155] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%154 = llvm.load %156 : !llvm.ptr -> i64
%158 = llvm.load %124 : !llvm.ptr -> i64
%159 = llvm.getelementptr %arg0[%158] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%157 = llvm.load %159 : !llvm.ptr -> i64
%160 = llvm.load %106 : !llvm.ptr -> i64
%161 = llvm.getelementptr %arg0[%160] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %157, %161 : i64, !llvm.ptr
%162 = llvm.load %124 : !llvm.ptr -> i64
%163 = llvm.getelementptr %arg0[%162] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %154, %163 : i64, !llvm.ptr
%164 = llvm.load %124 : !llvm.ptr -> i64
llvm.store %164, %106 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb20
^bb26:
cf.br ^bb18
^bb20:
%165 = llvm.load %86 : !llvm.ptr -> i64
%166 = arith.constant 1 : i32
%168 = arith.extsi %166 : i32 to i64
%167 = arith.subi %165, %168 : i64
llvm.store %167, %86 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
func.return
}
func.func @heapsort_idx(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i64) -> () {
%169 = arith.constant 2 : i32
%171 = arith.extsi %169 : i32 to i64
%170 = arith.cmpi slt, %arg2, %171 : i64
cf.cond_br %170, ^bb27, ^bb28
^bb27:
func.return
^bb28:
cf.br ^bb29
^bb29:
%172 = arith.constant 2 : i32
%174 = arith.extsi %172 : i32 to i64
%173 = arith.divsi %arg2, %174 : i64
%175 = arith.constant 1 : i32
%177 = arith.extsi %175 : i32 to i64
%176 = arith.subi %173, %177 : i64
%178 = llvm.mlir.constant(1 : i64) : i64
%179 = llvm.alloca %178 x i64 : (i64) -> !llvm.ptr
llvm.store %176, %179 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%180 = llvm.load %179 : !llvm.ptr -> i64
%181 = arith.constant 0 : i32
%183 = arith.extsi %181 : i32 to i64
%182 = arith.cmpi sge, %180, %183 : i64
cf.cond_br %182, ^bb31, ^bb32
^bb31:
%184 = llvm.load %179 : !llvm.ptr -> i64
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x i64 : (i64) -> !llvm.ptr
llvm.store %184, %186 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%187 = arith.constant 2 : i32
%188 = llvm.load %186 : !llvm.ptr -> i64
%190 = arith.extsi %187 : i32 to i64
%189 = arith.muli %190, %188 : i64
%191 = arith.constant 1 : i32
%193 = arith.extsi %191 : i32 to i64
%192 = arith.addi %189, %193 : i64
%194 = arith.cmpi slt, %192, %arg2 : i64
cf.cond_br %194, ^bb34, ^bb35
^bb34:
%195 = arith.constant 2 : i32
%196 = llvm.load %186 : !llvm.ptr -> i64
%198 = arith.extsi %195 : i32 to i64
%197 = arith.muli %198, %196 : i64
%199 = arith.constant 1 : i32
%201 = arith.extsi %199 : i32 to i64
%200 = arith.addi %197, %201 : i64
%202 = llvm.mlir.constant(1 : i64) : i64
%203 = llvm.alloca %202 x i64 : (i64) -> !llvm.ptr
llvm.store %200, %203 : i64, !llvm.ptr
%204 = llvm.load %203 : !llvm.ptr -> i64
%205 = arith.constant 1 : i32
%207 = arith.extsi %205 : i32 to i64
%206 = arith.addi %204, %207 : i64
%208 = arith.cmpi slt, %206, %arg2 : i64
%209 = scf.if %208 -> (i1) {
%212 = llvm.load %203 : !llvm.ptr -> i64
%213 = arith.constant 1 : i32
%215 = arith.extsi %213 : i32 to i64
%214 = arith.addi %212, %215 : i64
%216 = llvm.getelementptr %arg0[%214] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%211 = llvm.load %216 : !llvm.ptr -> i64
%217 = llvm.getelementptr %arg1[%211] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%210 = llvm.load %217 : !llvm.ptr -> i64
%220 = llvm.load %203 : !llvm.ptr -> i64
%221 = llvm.getelementptr %arg0[%220] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%219 = llvm.load %221 : !llvm.ptr -> i64
%222 = llvm.getelementptr %arg1[%219] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%218 = llvm.load %222 : !llvm.ptr -> i64
%223 = arith.cmpi sgt, %210, %218 : i64
scf.yield %223 : i1
} else {
%224 = arith.constant false
scf.yield %224 : i1
}
cf.cond_br %209, ^bb36, ^bb37
^bb36:
%225 = llvm.load %203 : !llvm.ptr -> i64
%226 = arith.constant 1 : i32
%228 = arith.extsi %226 : i32 to i64
%227 = arith.addi %225, %228 : i64
llvm.store %227, %203 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%231 = llvm.load %186 : !llvm.ptr -> i64
%232 = llvm.getelementptr %arg0[%231] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%230 = llvm.load %232 : !llvm.ptr -> i64
%233 = llvm.getelementptr %arg1[%230] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%229 = llvm.load %233 : !llvm.ptr -> i64
%236 = llvm.load %203 : !llvm.ptr -> i64
%237 = llvm.getelementptr %arg0[%236] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%235 = llvm.load %237 : !llvm.ptr -> i64
%238 = llvm.getelementptr %arg1[%235] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%234 = llvm.load %238 : !llvm.ptr -> i64
%239 = arith.cmpi slt, %229, %234 : i64
cf.cond_br %239, ^bb39, ^bb40
^bb39:
%241 = llvm.load %186 : !llvm.ptr -> i64
%242 = llvm.getelementptr %arg0[%241] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%240 = llvm.load %242 : !llvm.ptr -> i64
%244 = llvm.load %203 : !llvm.ptr -> i64
%245 = llvm.getelementptr %arg0[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%243 = llvm.load %245 : !llvm.ptr -> i64
%246 = llvm.load %186 : !llvm.ptr -> i64
%247 = llvm.getelementptr %arg0[%246] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %243, %247 : i64, !llvm.ptr
%248 = llvm.load %203 : !llvm.ptr -> i64
%249 = llvm.getelementptr %arg0[%248] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %240, %249 : i64, !llvm.ptr
%250 = llvm.load %203 : !llvm.ptr -> i64
llvm.store %250, %186 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb35
^bb41:
cf.br ^bb33
^bb35:
%251 = llvm.load %179 : !llvm.ptr -> i64
%252 = arith.constant 1 : i32
%254 = arith.extsi %252 : i32 to i64
%253 = arith.subi %251, %254 : i64
llvm.store %253, %179 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%255 = arith.constant 1 : i32
%257 = arith.extsi %255 : i32 to i64
%256 = arith.subi %arg2, %257 : i64
%258 = llvm.mlir.constant(1 : i64) : i64
%259 = llvm.alloca %258 x i64 : (i64) -> !llvm.ptr
llvm.store %256, %259 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%260 = llvm.load %259 : !llvm.ptr -> i64
%261 = arith.constant 0 : i32
%263 = arith.extsi %261 : i32 to i64
%262 = arith.cmpi sgt, %260, %263 : i64
cf.cond_br %262, ^bb43, ^bb44
^bb43:
%265 = arith.constant 0 : i32
%266 = arith.extsi %265 : i32 to i64
%267 = llvm.getelementptr %arg0[%266] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%264 = llvm.load %267 : !llvm.ptr -> i64
%269 = llvm.load %259 : !llvm.ptr -> i64
%270 = llvm.getelementptr %arg0[%269] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%268 = llvm.load %270 : !llvm.ptr -> i64
%271 = arith.constant 0 : i32
%272 = arith.extsi %271 : i32 to i64
%273 = llvm.getelementptr %arg0[%272] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %268, %273 : i64, !llvm.ptr
%274 = llvm.load %259 : !llvm.ptr -> i64
%275 = llvm.getelementptr %arg0[%274] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %264, %275 : i64, !llvm.ptr
%276 = arith.constant 0 : i32
%277 = arith.extsi %276 : i32 to i64
%278 = llvm.mlir.constant(1 : i64) : i64
%279 = llvm.alloca %278 x i64 : (i64) -> !llvm.ptr
llvm.store %277, %279 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%280 = arith.constant 2 : i32
%281 = llvm.load %279 : !llvm.ptr -> i64
%283 = arith.extsi %280 : i32 to i64
%282 = arith.muli %283, %281 : i64
%284 = arith.constant 1 : i32
%286 = arith.extsi %284 : i32 to i64
%285 = arith.addi %282, %286 : i64
%287 = llvm.load %259 : !llvm.ptr -> i64
%288 = arith.cmpi slt, %285, %287 : i64
cf.cond_br %288, ^bb46, ^bb47
^bb46:
%289 = arith.constant 2 : i32
%290 = llvm.load %279 : !llvm.ptr -> i64
%292 = arith.extsi %289 : i32 to i64
%291 = arith.muli %292, %290 : i64
%293 = arith.constant 1 : i32
%295 = arith.extsi %293 : i32 to i64
%294 = arith.addi %291, %295 : i64
%296 = llvm.mlir.constant(1 : i64) : i64
%297 = llvm.alloca %296 x i64 : (i64) -> !llvm.ptr
llvm.store %294, %297 : i64, !llvm.ptr
%298 = llvm.load %297 : !llvm.ptr -> i64
%299 = arith.constant 1 : i32
%301 = arith.extsi %299 : i32 to i64
%300 = arith.addi %298, %301 : i64
%302 = llvm.load %259 : !llvm.ptr -> i64
%303 = arith.cmpi slt, %300, %302 : i64
%304 = scf.if %303 -> (i1) {
%307 = llvm.load %297 : !llvm.ptr -> i64
%308 = arith.constant 1 : i32
%310 = arith.extsi %308 : i32 to i64
%309 = arith.addi %307, %310 : i64
%311 = llvm.getelementptr %arg0[%309] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%306 = llvm.load %311 : !llvm.ptr -> i64
%312 = llvm.getelementptr %arg1[%306] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%305 = llvm.load %312 : !llvm.ptr -> i64
%315 = llvm.load %297 : !llvm.ptr -> i64
%316 = llvm.getelementptr %arg0[%315] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%314 = llvm.load %316 : !llvm.ptr -> i64
%317 = llvm.getelementptr %arg1[%314] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%313 = llvm.load %317 : !llvm.ptr -> i64
%318 = arith.cmpi sgt, %305, %313 : i64
scf.yield %318 : i1
} else {
%319 = arith.constant false
scf.yield %319 : i1
}
cf.cond_br %304, ^bb48, ^bb49
^bb48:
%320 = llvm.load %297 : !llvm.ptr -> i64
%321 = arith.constant 1 : i32
%323 = arith.extsi %321 : i32 to i64
%322 = arith.addi %320, %323 : i64
llvm.store %322, %297 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%326 = llvm.load %279 : !llvm.ptr -> i64
%327 = llvm.getelementptr %arg0[%326] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%325 = llvm.load %327 : !llvm.ptr -> i64
%328 = llvm.getelementptr %arg1[%325] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%324 = llvm.load %328 : !llvm.ptr -> i64
%331 = llvm.load %297 : !llvm.ptr -> i64
%332 = llvm.getelementptr %arg0[%331] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%330 = llvm.load %332 : !llvm.ptr -> i64
%333 = llvm.getelementptr %arg1[%330] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%329 = llvm.load %333 : !llvm.ptr -> i64
%334 = arith.cmpi slt, %324, %329 : i64
cf.cond_br %334, ^bb51, ^bb52
^bb51:
%336 = llvm.load %279 : !llvm.ptr -> i64
%337 = llvm.getelementptr %arg0[%336] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%335 = llvm.load %337 : !llvm.ptr -> i64
%339 = llvm.load %297 : !llvm.ptr -> i64
%340 = llvm.getelementptr %arg0[%339] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%338 = llvm.load %340 : !llvm.ptr -> i64
%341 = llvm.load %279 : !llvm.ptr -> i64
%342 = llvm.getelementptr %arg0[%341] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %338, %342 : i64, !llvm.ptr
%343 = llvm.load %297 : !llvm.ptr -> i64
%344 = llvm.getelementptr %arg0[%343] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %335, %344 : i64, !llvm.ptr
%345 = llvm.load %297 : !llvm.ptr -> i64
llvm.store %345, %279 : i64, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb47
^bb53:
cf.br ^bb45
^bb47:
%346 = llvm.load %259 : !llvm.ptr -> i64
%347 = arith.constant 1 : i32
%349 = arith.extsi %347 : i32 to i64
%348 = arith.subi %346, %349 : i64
llvm.store %348, %259 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
func.return
}
func.func @bsearch_idx(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> i64 {
%350 = arith.constant 0 : 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 = arith.constant 1 : i32
%356 = arith.extsi %354 : i32 to i64
%355 = arith.subi %arg1, %356 : i64
%357 = llvm.mlir.constant(1 : i64) : i64
%358 = llvm.alloca %357 x i64 : (i64) -> !llvm.ptr
llvm.store %355, %358 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%359 = llvm.load %353 : !llvm.ptr -> i64
%360 = llvm.load %358 : !llvm.ptr -> i64
%361 = arith.cmpi slt, %359, %360 : i64
cf.cond_br %361, ^bb55, ^bb56
^bb55:
%362 = llvm.load %353 : !llvm.ptr -> i64
%363 = llvm.load %358 : !llvm.ptr -> i64
%364 = arith.addi %362, %363 : i64
%365 = arith.constant 1 : i32
%367 = arith.extsi %365 : i32 to i64
%366 = arith.shrsi %364, %367 : i64
%369 = llvm.getelementptr %arg0[%366] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%368 = llvm.load %369 : !llvm.ptr -> i64
%370 = arith.cmpi slt, %368, %arg2 : i64
cf.cond_br %370, ^bb57, ^bb58
^bb57:
%371 = arith.constant 1 : i32
%373 = arith.extsi %371 : i32 to i64
%372 = arith.addi %366, %373 : i64
llvm.store %372, %353 : i64, !llvm.ptr
cf.br ^bb59
^bb58:
llvm.store %366, %358 : i64, !llvm.ptr
cf.br ^bb59
^bb59:
cf.br ^bb54
^bb56:
%374 = llvm.load %353 : !llvm.ptr -> i64
func.return %374 : i64
}
func.func @build_tree(%arg0: i64, %arg1: i64, %arg2: i64) -> () {
%375 = arith.constant 12 : i32
%377 = arith.extsi %375 : i32 to i64
%376 = arith.muli %arg0, %377 : i64
%378 = arith.subi %arg2, %arg1 : i64
%379 = arith.constant 1 : i32
%381 = arith.extsi %379 : i32 to i64
%380 = arith.cmpi eq, %378, %381 : i64
cf.cond_br %380, ^bb60, ^bb61
^bb60:
%383 = llvm.mlir.addressof @g_y_vals : !llvm.ptr
%384 = llvm.load %383 : !llvm.ptr -> !llvm.ptr
%385 = arith.constant 1 : i32
%387 = arith.extsi %385 : i32 to i64
%386 = arith.addi %arg1, %387 : i64
%388 = llvm.getelementptr %384[%386] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%382 = llvm.load %388 : !llvm.ptr -> i64
%390 = llvm.mlir.addressof @g_y_vals : !llvm.ptr
%391 = llvm.load %390 : !llvm.ptr -> !llvm.ptr
%392 = llvm.getelementptr %391[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%389 = llvm.load %392 : !llvm.ptr -> i64
%393 = arith.subi %382, %389 : i64
%394 = llvm.mlir.addressof @g_seg : !llvm.ptr
%395 = llvm.load %394 : !llvm.ptr -> !llvm.ptr
%396 = llvm.getelementptr %395[%376] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %393, %396 : i64, !llvm.ptr
func.return
^bb61:
cf.br ^bb62
^bb62:
%397 = arith.addi %arg1, %arg2 : i64
%398 = arith.constant 1 : i32
%400 = arith.extsi %398 : i32 to i64
%399 = arith.shrsi %397, %400 : i64
%401 = arith.constant 1 : i32
%403 = arith.extsi %401 : i32 to i64
%402 = arith.shli %arg0, %403 : i64
func.call @build_tree(%402, %arg1, %399) : (i64, i64, i64) -> ()
%406 = arith.constant 1 : i32
%408 = arith.extsi %406 : i32 to i64
%407 = arith.addi %402, %408 : i64
func.call @build_tree(%407, %399, %arg2) : (i64, i64, i64) -> ()
%410 = llvm.mlir.addressof @g_seg : !llvm.ptr
%411 = llvm.load %410 : !llvm.ptr -> !llvm.ptr
%412 = arith.constant 12 : i32
%414 = arith.extsi %412 : i32 to i64
%413 = arith.muli %402, %414 : i64
%415 = llvm.getelementptr %411[%413] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%409 = llvm.load %415 : !llvm.ptr -> i64
%417 = llvm.mlir.addressof @g_seg : !llvm.ptr
%418 = llvm.load %417 : !llvm.ptr -> !llvm.ptr
%419 = arith.constant 1 : i32
%421 = arith.extsi %419 : i32 to i64
%420 = arith.addi %402, %421 : i64
%422 = arith.constant 12 : i32
%424 = arith.extsi %422 : i32 to i64
%423 = arith.muli %420, %424 : i64
%425 = llvm.getelementptr %418[%423] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%416 = llvm.load %425 : !llvm.ptr -> i64
%426 = arith.addi %409, %416 : i64
%427 = llvm.mlir.addressof @g_seg : !llvm.ptr
%428 = llvm.load %427 : !llvm.ptr -> !llvm.ptr
%429 = llvm.getelementptr %428[%376] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %426, %429 : i64, !llvm.ptr
func.return
}
func.func @apply_rot(%arg0: i64, %arg1: i64) -> () {
%430 = arith.constant 0 : i32
%432 = arith.extsi %430 : i32 to i64
%431 = arith.cmpi eq, %arg1, %432 : i64
cf.cond_br %431, ^bb63, ^bb64
^bb63:
func.return
^bb64:
cf.br ^bb65
^bb65:
%433 = arith.constant 12 : i32
%435 = arith.extsi %433 : i32 to i64
%434 = arith.remsi %arg1, %435 : i64
%436 = arith.constant 12 : i32
%438 = arith.extsi %436 : i32 to i64
%437 = arith.muli %arg0, %438 : i64
%439 = arith.constant 0 : i32
%440 = arith.constant 12 : i32
%441 = arith.index_cast %439 : i32 to index
%442 = arith.index_cast %440 : i32 to index
%444 = arith.constant 1 : index
%445 = arith.constant -1 : index
%446 = arith.cmpi sle, %441, %442 : index
%443 = arith.select %446, %444, %445 : index
cf.br ^bb66(%441 : index)
^bb66(%447: index):
%448 = arith.cmpi slt, %447, %442 : index
%449 = arith.cmpi sgt, %447, %442 : index
%450 = arith.select %446, %448, %449 : i1
cf.cond_br %450, ^bb67(%447 : index), ^bb68(%447 : index)
^bb67(%451: index):
%453 = llvm.mlir.addressof @g_seg : !llvm.ptr
%454 = llvm.load %453 : !llvm.ptr -> !llvm.ptr
%456 = arith.index_cast %451 : index to i32
%457 = arith.trunci %434 : i64 to i32
%455 = arith.subi %456, %457 : i32
%458 = arith.constant 12 : i32
%459 = arith.addi %455, %458 : i32
%460 = arith.constant 12 : i32
%461 = arith.remsi %459, %460 : i32
%463 = arith.extsi %461 : i32 to i64
%462 = arith.addi %437, %463 : i64
%464 = llvm.getelementptr %454[%462] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%452 = llvm.load %464 : !llvm.ptr -> i64
%465 = llvm.mlir.addressof @g_tmp12 : !llvm.ptr
%466 = llvm.load %465 : !llvm.ptr -> !llvm.ptr
%467 = arith.index_cast %451 : index to i64
%468 = llvm.getelementptr %466[%467] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %452, %468 : i64, !llvm.ptr
%469 = arith.addi %451, %443 : index
cf.br ^bb66(%469 : index)
^bb68(%470: index):
%471 = arith.constant 0 : i32
%472 = arith.constant 12 : i32
%473 = arith.index_cast %471 : i32 to index
%474 = arith.index_cast %472 : i32 to index
%476 = arith.constant 1 : index
%477 = arith.constant -1 : index
%478 = arith.cmpi sle, %473, %474 : index
%475 = arith.select %478, %476, %477 : index
cf.br ^bb69(%473 : index)
^bb69(%479: index):
%480 = arith.cmpi slt, %479, %474 : index
%481 = arith.cmpi sgt, %479, %474 : index
%482 = arith.select %478, %480, %481 : i1
cf.cond_br %482, ^bb70(%479 : index), ^bb71(%479 : index)
^bb70(%483: index):
%485 = llvm.mlir.addressof @g_tmp12 : !llvm.ptr
%486 = llvm.load %485 : !llvm.ptr -> !llvm.ptr
%487 = arith.index_cast %483 : index to i64
%488 = llvm.getelementptr %486[%487] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%484 = llvm.load %488 : !llvm.ptr -> i64
%489 = llvm.mlir.addressof @g_seg : !llvm.ptr
%490 = llvm.load %489 : !llvm.ptr -> !llvm.ptr
%492 = arith.trunci %437 : i64 to i32
%493 = arith.index_cast %483 : index to i32
%491 = arith.addi %492, %493 : i32
%494 = arith.extsi %491 : i32 to i64
%495 = llvm.getelementptr %490[%494] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %484, %495 : i64, !llvm.ptr
%496 = arith.addi %483, %475 : index
cf.br ^bb69(%496 : index)
^bb71(%497: index):
%499 = llvm.mlir.addressof @g_lazy : !llvm.ptr
%500 = llvm.load %499 : !llvm.ptr -> !llvm.ptr
%501 = llvm.getelementptr %500[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%498 = llvm.load %501 : !llvm.ptr -> i32
%503 = arith.extsi %498 : i32 to i64
%502 = arith.addi %503, %434 : i64
%504 = arith.constant 12 : i32
%506 = arith.extsi %504 : i32 to i64
%505 = arith.cmpi sge, %502, %506 : i64
cf.cond_br %505, ^bb72, ^bb73
^bb72:
%507 = arith.constant 12 : i32
%509 = arith.extsi %507 : i32 to i64
%508 = arith.subi %502, %509 : i64
%510 = arith.trunci %508 : i64 to i32
%511 = llvm.mlir.addressof @g_lazy : !llvm.ptr
%512 = llvm.load %511 : !llvm.ptr -> !llvm.ptr
%513 = llvm.getelementptr %512[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %510, %513 : i32, !llvm.ptr
cf.br ^bb74
^bb73:
%514 = arith.trunci %502 : i64 to i32
%515 = llvm.mlir.addressof @g_lazy : !llvm.ptr
%516 = llvm.load %515 : !llvm.ptr -> !llvm.ptr
%517 = llvm.getelementptr %516[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %514, %517 : i32, !llvm.ptr
cf.br ^bb74
^bb74:
func.return
}
func.func @push_down(%arg0: i64) -> () {
%519 = llvm.mlir.addressof @g_lazy : !llvm.ptr
%520 = llvm.load %519 : !llvm.ptr -> !llvm.ptr
%521 = llvm.getelementptr %520[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%518 = llvm.load %521 : !llvm.ptr -> i32
%522 = arith.extsi %518 : i32 to i64
%523 = arith.constant 0 : i32
%525 = arith.extsi %523 : i32 to i64
%524 = arith.cmpi ne, %522, %525 : i64
cf.cond_br %524, ^bb75, ^bb76
^bb75:
%526 = arith.constant 1 : i32
%528 = arith.extsi %526 : i32 to i64
%527 = arith.shli %arg0, %528 : i64
func.call @apply_rot(%527, %522) : (i64, i64) -> ()
%531 = arith.constant 1 : i32
%533 = arith.extsi %531 : i32 to i64
%532 = arith.addi %527, %533 : i64
func.call @apply_rot(%532, %522) : (i64, i64) -> ()
%534 = arith.constant 0 : i32
%535 = llvm.mlir.addressof @g_lazy : !llvm.ptr
%536 = llvm.load %535 : !llvm.ptr -> !llvm.ptr
%537 = llvm.getelementptr %536[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %534, %537 : i32, !llvm.ptr
cf.br ^bb77
^bb76:
cf.br ^bb77
^bb77:
func.return
}
func.func @pull_up(%arg0: i64) -> () {
%538 = arith.constant 12 : i32
%540 = arith.extsi %538 : i32 to i64
%539 = arith.muli %arg0, %540 : i64
%541 = arith.constant 1 : i32
%543 = arith.extsi %541 : i32 to i64
%542 = arith.shli %arg0, %543 : i64
%544 = arith.constant 12 : i32
%546 = arith.extsi %544 : i32 to i64
%545 = arith.muli %542, %546 : i64
%547 = arith.constant 1 : i32
%549 = arith.extsi %547 : i32 to i64
%548 = arith.shli %arg0, %549 : i64
%550 = arith.constant 1 : i32
%552 = arith.extsi %550 : i32 to i64
%551 = arith.addi %548, %552 : i64
%553 = arith.constant 12 : i32
%555 = arith.extsi %553 : i32 to i64
%554 = arith.muli %551, %555 : i64
%556 = arith.constant 0 : i32
%557 = arith.constant 12 : i32
%558 = arith.index_cast %556 : i32 to index
%559 = arith.index_cast %557 : i32 to index
%561 = arith.constant 1 : index
%562 = arith.constant -1 : index
%563 = arith.cmpi sle, %558, %559 : index
%560 = arith.select %563, %561, %562 : index
cf.br ^bb78(%558 : index)
^bb78(%564: index):
%565 = arith.cmpi slt, %564, %559 : index
%566 = arith.cmpi sgt, %564, %559 : index
%567 = arith.select %563, %565, %566 : i1
cf.cond_br %567, ^bb79(%564 : index), ^bb80(%564 : index)
^bb79(%568: index):
%570 = llvm.mlir.addressof @g_seg : !llvm.ptr
%571 = llvm.load %570 : !llvm.ptr -> !llvm.ptr
%573 = arith.trunci %545 : i64 to i32
%574 = arith.index_cast %568 : index to i32
%572 = arith.addi %573, %574 : i32
%575 = arith.extsi %572 : i32 to i64
%576 = llvm.getelementptr %571[%575] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%569 = llvm.load %576 : !llvm.ptr -> i64
%578 = llvm.mlir.addressof @g_seg : !llvm.ptr
%579 = llvm.load %578 : !llvm.ptr -> !llvm.ptr
%581 = arith.trunci %554 : i64 to i32
%582 = arith.index_cast %568 : index to i32
%580 = arith.addi %581, %582 : i32
%583 = arith.extsi %580 : i32 to i64
%584 = llvm.getelementptr %579[%583] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%577 = llvm.load %584 : !llvm.ptr -> i64
%585 = arith.addi %569, %577 : i64
%586 = llvm.mlir.addressof @g_seg : !llvm.ptr
%587 = llvm.load %586 : !llvm.ptr -> !llvm.ptr
%589 = arith.trunci %539 : i64 to i32
%590 = arith.index_cast %568 : index to i32
%588 = arith.addi %589, %590 : i32
%591 = arith.extsi %588 : i32 to i64
%592 = llvm.getelementptr %587[%591] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %585, %592 : i64, !llvm.ptr
%593 = arith.addi %568, %560 : index
cf.br ^bb78(%593 : index)
^bb80(%594: index):
func.return
}
func.func @update_tree(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64, %arg4: i64, %arg5: i64) -> () {
%595 = arith.cmpi sle, %arg3, %arg1 : i64
%596 = scf.if %595 -> (i1) {
%597 = arith.cmpi sle, %arg2, %arg4 : i64
scf.yield %597 : i1
} else {
%598 = arith.constant false
scf.yield %598 : i1
}
cf.cond_br %596, ^bb81, ^bb82
^bb81:
func.call @apply_rot(%arg0, %arg5) : (i64, i64) -> ()
func.return
^bb82:
cf.br ^bb83
^bb83:
func.call @push_down(%arg0) : (i64) -> ()
%601 = arith.addi %arg1, %arg2 : i64
%602 = arith.constant 1 : i32
%604 = arith.extsi %602 : i32 to i64
%603 = arith.shrsi %601, %604 : i64
%605 = arith.constant 1 : i32
%607 = arith.extsi %605 : i32 to i64
%606 = arith.shli %arg0, %607 : i64
%608 = arith.cmpi slt, %arg3, %603 : i64
cf.cond_br %608, ^bb84, ^bb85
^bb84:
func.call @update_tree(%606, %arg1, %603, %arg3, %arg4, %arg5) : (i64, i64, i64, i64, i64, i64) -> ()
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
%610 = arith.cmpi sgt, %arg4, %603 : i64
cf.cond_br %610, ^bb87, ^bb88
^bb87:
%612 = arith.constant 1 : i32
%614 = arith.extsi %612 : i32 to i64
%613 = arith.addi %606, %614 : i64
func.call @update_tree(%613, %603, %arg2, %arg3, %arg4, %arg5) : (i64, i64, i64, i64, i64, i64) -> ()
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
func.call @pull_up(%arg0) : (i64) -> ()
func.return
}
func.func @main() -> i32 {
%616 = arith.constant 100000 : i32
%617 = arith.extsi %616 : i32 to i64
%618 = arith.constant 2 : i32
%619 = arith.constant 2 : i32
%621 = arith.extsi %619 : i32 to i64
%620 = arith.muli %621, %617 : i64
%623 = arith.extsi %618 : i32 to i64
%622 = arith.addi %623, %620 : i64
%625 = arith.constant 8 : i32
%627 = arith.extsi %625 : i32 to i64
%626 = arith.muli %622, %627 : i64
%624 = func.call @malloc(%626) : (i64) -> !llvm.ptr
%629 = arith.constant 8 : i32
%631 = arith.extsi %629 : i32 to i64
%630 = arith.muli %622, %631 : i64
%628 = func.call @malloc(%630) : (i64) -> !llvm.ptr
%632 = arith.constant 0 : i32
%633 = arith.extsi %632 : i32 to i64
%634 = llvm.mlir.constant(1 : i64) : i64
%635 = llvm.alloca %634 x i64 : (i64) -> !llvm.ptr
llvm.store %633, %635 : i64, !llvm.ptr
%636 = arith.constant 0 : i32
%637 = arith.extsi %636 : i32 to i64
%638 = llvm.mlir.constant(1 : i64) : i64
%639 = llvm.alloca %638 x i64 : (i64) -> !llvm.ptr
llvm.store %637, %639 : i64, !llvm.ptr
%640 = arith.constant 0 : i32
%641 = llvm.load %635 : !llvm.ptr -> i64
%642 = arith.extsi %640 : i32 to i64
%643 = llvm.getelementptr %624[%641] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %642, %643 : i64, !llvm.ptr
%644 = llvm.load %635 : !llvm.ptr -> i64
%645 = arith.constant 1 : i32
%647 = arith.extsi %645 : i32 to i64
%646 = arith.addi %644, %647 : i64
llvm.store %646, %635 : i64, !llvm.ptr
%648 = llvm.mlir.addressof @M_VAL : !llvm.ptr
%649 = llvm.load %648 : !llvm.ptr -> i64
%650 = llvm.load %635 : !llvm.ptr -> i64
%651 = llvm.getelementptr %624[%650] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %649, %651 : i64, !llvm.ptr
%652 = llvm.load %635 : !llvm.ptr -> i64
%653 = arith.constant 1 : i32
%655 = arith.extsi %653 : i32 to i64
%654 = arith.addi %652, %655 : i64
llvm.store %654, %635 : i64, !llvm.ptr
%656 = arith.constant 0 : i32
%657 = llvm.load %639 : !llvm.ptr -> i64
%658 = arith.extsi %656 : i32 to i64
%659 = llvm.getelementptr %628[%657] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %658, %659 : i64, !llvm.ptr
%660 = llvm.load %639 : !llvm.ptr -> i64
%661 = arith.constant 1 : i32
%663 = arith.extsi %661 : i32 to i64
%662 = arith.addi %660, %663 : i64
llvm.store %662, %639 : i64, !llvm.ptr
%664 = llvm.mlir.addressof @M_VAL : !llvm.ptr
%665 = llvm.load %664 : !llvm.ptr -> i64
%666 = llvm.load %639 : !llvm.ptr -> i64
%667 = llvm.getelementptr %628[%666] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %665, %667 : i64, !llvm.ptr
%668 = llvm.load %639 : !llvm.ptr -> i64
%669 = arith.constant 1 : i32
%671 = arith.extsi %669 : i32 to i64
%670 = arith.addi %668, %671 : i64
llvm.store %670, %639 : i64, !llvm.ptr
%673 = arith.constant 2 : i32
%675 = arith.extsi %673 : i32 to i64
%674 = arith.muli %675, %617 : i64
%676 = arith.constant 8 : i32
%678 = arith.extsi %676 : i32 to i64
%677 = arith.muli %674, %678 : i64
%672 = func.call @malloc(%677) : (i64) -> !llvm.ptr
%680 = arith.constant 2 : i32
%682 = arith.extsi %680 : i32 to i64
%681 = arith.muli %682, %617 : i64
%683 = arith.constant 4 : i32
%685 = arith.extsi %683 : i32 to i64
%684 = arith.muli %681, %685 : i64
%679 = func.call @malloc(%684) : (i64) -> !llvm.ptr
%687 = arith.constant 2 : i32
%689 = arith.extsi %687 : i32 to i64
%688 = arith.muli %689, %617 : i64
%690 = arith.constant 8 : i32
%692 = arith.extsi %690 : i32 to i64
%691 = arith.muli %688, %692 : i64
%686 = func.call @malloc(%691) : (i64) -> !llvm.ptr
%694 = arith.constant 2 : i32
%696 = arith.extsi %694 : i32 to i64
%695 = arith.muli %696, %617 : i64
%697 = arith.constant 8 : i32
%699 = arith.extsi %697 : i32 to i64
%698 = arith.muli %695, %699 : i64
%693 = func.call @malloc(%698) : (i64) -> !llvm.ptr
%700 = arith.constant 0 : i32
%701 = arith.extsi %700 : i32 to i64
%702 = llvm.mlir.constant(1 : i64) : i64
%703 = llvm.alloca %702 x i64 : (i64) -> !llvm.ptr
llvm.store %701, %703 : i64, !llvm.ptr
%704 = llvm.mlir.addressof @S0 : !llvm.ptr
%705 = llvm.load %704 : !llvm.ptr -> i64
%706 = llvm.mlir.constant(1 : i64) : i64
%707 = llvm.alloca %706 x i64 : (i64) -> !llvm.ptr
llvm.store %705, %707 : i64, !llvm.ptr
%708 = arith.constant 0 : i32
%709 = arith.index_cast %708 : i32 to index
%710 = arith.index_cast %617 : i32 to index
%712 = arith.constant 1 : index
%713 = arith.constant -1 : index
%714 = arith.cmpi sle, %709, %710 : index
%711 = arith.select %714, %712, %713 : index
cf.br ^bb90(%709 : index)
^bb90(%715: index):
%716 = arith.cmpi slt, %715, %710 : index
%717 = arith.cmpi sgt, %715, %710 : index
%718 = arith.select %714, %716, %717 : i1
cf.cond_br %718, ^bb91(%715 : index), ^bb92(%715 : index)
^bb91(%719: index):
%720 = llvm.load %707 : !llvm.ptr -> i64
%721 = llvm.load %707 : !llvm.ptr -> i64
%722 = llvm.load %707 : !llvm.ptr -> i64
%723 = arith.muli %721, %722 : i64
%724 = llvm.mlir.addressof @M_VAL : !llvm.ptr
%725 = llvm.load %724 : !llvm.ptr -> i64
%726 = arith.remsi %723, %725 : i64
llvm.store %726, %707 : i64, !llvm.ptr
%727 = llvm.load %707 : !llvm.ptr -> i64
%728 = llvm.load %707 : !llvm.ptr -> i64
%729 = llvm.load %707 : !llvm.ptr -> i64
%730 = arith.muli %728, %729 : i64
%731 = llvm.mlir.addressof @M_VAL : !llvm.ptr
%732 = llvm.load %731 : !llvm.ptr -> i64
%733 = arith.remsi %730, %732 : i64
llvm.store %733, %707 : i64, !llvm.ptr
%734 = llvm.load %707 : !llvm.ptr -> i64
%735 = llvm.load %707 : !llvm.ptr -> i64
%736 = llvm.load %707 : !llvm.ptr -> i64
%737 = arith.muli %735, %736 : i64
%738 = llvm.mlir.addressof @M_VAL : !llvm.ptr
%739 = llvm.load %738 : !llvm.ptr -> i64
%740 = arith.remsi %737, %739 : i64
llvm.store %740, %707 : i64, !llvm.ptr
%741 = llvm.load %707 : !llvm.ptr -> i64
%742 = llvm.load %707 : !llvm.ptr -> i64
%743 = llvm.load %707 : !llvm.ptr -> i64
%744 = arith.muli %742, %743 : i64
%745 = llvm.mlir.addressof @M_VAL : !llvm.ptr
%746 = llvm.load %745 : !llvm.ptr -> i64
%747 = arith.remsi %744, %746 : i64
llvm.store %747, %707 : i64, !llvm.ptr
%748 = llvm.mlir.undef : i64
%749 = llvm.mlir.undef : i64
%750 = arith.cmpi sle, %720, %727 : i64
%751, %752 = scf.if %750 -> (i64, i64) {
scf.yield %720, %727 : i64, i64
} else {
scf.yield %727, %720 : i64, i64
}
%753 = llvm.mlir.undef : i64
%754 = llvm.mlir.undef : i64
%755 = arith.cmpi sle, %734, %741 : i64
%756, %757 = scf.if %755 -> (i64, i64) {
scf.yield %734, %741 : i64, i64
} else {
scf.yield %741, %734 : i64, i64
}
%758 = arith.constant 1 : i32
%760 = arith.extsi %758 : i32 to i64
%759 = arith.addi %752, %760 : i64
%761 = arith.constant 1 : i32
%763 = arith.extsi %761 : i32 to i64
%762 = arith.addi %757, %763 : i64
%764 = llvm.load %635 : !llvm.ptr -> i64
%765 = llvm.getelementptr %624[%764] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %751, %765 : i64, !llvm.ptr
%766 = llvm.load %635 : !llvm.ptr -> i64
%767 = arith.constant 1 : i32
%769 = arith.extsi %767 : i32 to i64
%768 = arith.addi %766, %769 : i64
llvm.store %768, %635 : i64, !llvm.ptr
%770 = llvm.load %635 : !llvm.ptr -> i64
%771 = llvm.getelementptr %624[%770] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %759, %771 : i64, !llvm.ptr
%772 = llvm.load %635 : !llvm.ptr -> i64
%773 = arith.constant 1 : i32
%775 = arith.extsi %773 : i32 to i64
%774 = arith.addi %772, %775 : i64
llvm.store %774, %635 : i64, !llvm.ptr
%776 = llvm.load %639 : !llvm.ptr -> i64
%777 = llvm.getelementptr %628[%776] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %756, %777 : i64, !llvm.ptr
%778 = llvm.load %639 : !llvm.ptr -> i64
%779 = arith.constant 1 : i32
%781 = arith.extsi %779 : i32 to i64
%780 = arith.addi %778, %781 : i64
llvm.store %780, %639 : i64, !llvm.ptr
%782 = llvm.load %639 : !llvm.ptr -> i64
%783 = llvm.getelementptr %628[%782] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %762, %783 : i64, !llvm.ptr
%784 = llvm.load %639 : !llvm.ptr -> i64
%785 = arith.constant 1 : i32
%787 = arith.extsi %785 : i32 to i64
%786 = arith.addi %784, %787 : i64
llvm.store %786, %639 : i64, !llvm.ptr
%788 = llvm.load %703 : !llvm.ptr -> i64
%789 = llvm.getelementptr %672[%788] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %751, %789 : i64, !llvm.ptr
%790 = arith.constant 1 : i32
%791 = llvm.load %703 : !llvm.ptr -> i64
%792 = llvm.getelementptr %679[%791] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %790, %792 : i32, !llvm.ptr
%793 = llvm.load %703 : !llvm.ptr -> i64
%794 = llvm.getelementptr %686[%793] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %756, %794 : i64, !llvm.ptr
%795 = llvm.load %703 : !llvm.ptr -> i64
%796 = llvm.getelementptr %693[%795] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %762, %796 : i64, !llvm.ptr
%797 = llvm.load %703 : !llvm.ptr -> i64
%798 = arith.constant 1 : i32
%800 = arith.extsi %798 : i32 to i64
%799 = arith.addi %797, %800 : i64
llvm.store %799, %703 : i64, !llvm.ptr
%801 = llvm.load %703 : !llvm.ptr -> i64
%802 = llvm.getelementptr %672[%801] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %759, %802 : i64, !llvm.ptr
%803 = arith.constant 11 : i32
%804 = llvm.load %703 : !llvm.ptr -> i64
%805 = llvm.getelementptr %679[%804] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %803, %805 : i32, !llvm.ptr
%806 = llvm.load %703 : !llvm.ptr -> i64
%807 = llvm.getelementptr %686[%806] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %756, %807 : i64, !llvm.ptr
%808 = llvm.load %703 : !llvm.ptr -> i64
%809 = llvm.getelementptr %693[%808] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %762, %809 : i64, !llvm.ptr
%810 = llvm.load %703 : !llvm.ptr -> i64
%811 = arith.constant 1 : i32
%813 = arith.extsi %811 : i32 to i64
%812 = arith.addi %810, %813 : i64
llvm.store %812, %703 : i64, !llvm.ptr
%814 = arith.addi %719, %711 : index
cf.br ^bb90(%814 : index)
^bb92(%815: index):
%817 = llvm.load %635 : !llvm.ptr -> i64
func.call @heapsort_i64(%624, %817) : (!llvm.ptr, i64) -> ()
%819 = llvm.load %639 : !llvm.ptr -> i64
func.call @heapsort_i64(%628, %819) : (!llvm.ptr, i64) -> ()
%820 = arith.constant 1 : i32
%821 = arith.extsi %820 : i32 to i64
%822 = llvm.mlir.constant(1 : i64) : i64
%823 = llvm.alloca %822 x i64 : (i64) -> !llvm.ptr
llvm.store %821, %823 : i64, !llvm.ptr
%824 = arith.constant 1 : i32
%825 = llvm.load %635 : !llvm.ptr -> i64
%826 = arith.index_cast %824 : i32 to index
%827 = arith.index_cast %825 : i32 to index
%829 = arith.constant 1 : index
%830 = arith.constant -1 : index
%831 = arith.cmpi sle, %826, %827 : index
%828 = arith.select %831, %829, %830 : index
cf.br ^bb93(%826 : index)
^bb93(%832: index):
%833 = arith.cmpi slt, %832, %827 : index
%834 = arith.cmpi sgt, %832, %827 : index
%835 = arith.select %831, %833, %834 : i1
cf.cond_br %835, ^bb94(%832 : index), ^bb95(%832 : index)
^bb94(%836: index):
%838 = arith.index_cast %836 : index to i64
%839 = llvm.getelementptr %624[%838] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%837 = llvm.load %839 : !llvm.ptr -> i64
%841 = llvm.load %823 : !llvm.ptr -> i64
%842 = arith.constant 1 : i32
%844 = arith.extsi %842 : i32 to i64
%843 = arith.subi %841, %844 : i64
%845 = llvm.getelementptr %624[%843] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%840 = llvm.load %845 : !llvm.ptr -> i64
%846 = arith.cmpi ne, %837, %840 : i64
cf.cond_br %846, ^bb96, ^bb97
^bb96:
%848 = arith.index_cast %836 : index to i64
%849 = llvm.getelementptr %624[%848] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%847 = llvm.load %849 : !llvm.ptr -> i64
%850 = llvm.load %823 : !llvm.ptr -> i64
%851 = llvm.getelementptr %624[%850] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %847, %851 : i64, !llvm.ptr
%852 = llvm.load %823 : !llvm.ptr -> i64
%853 = arith.constant 1 : i32
%855 = arith.extsi %853 : i32 to i64
%854 = arith.addi %852, %855 : i64
llvm.store %854, %823 : i64, !llvm.ptr
cf.br ^bb98
^bb97:
cf.br ^bb98
^bb98:
%856 = arith.addi %836, %828 : index
cf.br ^bb93(%856 : index)
^bb95(%857: index):
%858 = arith.constant 1 : i32
%859 = arith.extsi %858 : i32 to i64
%860 = llvm.mlir.constant(1 : i64) : i64
%861 = llvm.alloca %860 x i64 : (i64) -> !llvm.ptr
llvm.store %859, %861 : i64, !llvm.ptr
%862 = arith.constant 1 : i32
%863 = llvm.load %639 : !llvm.ptr -> i64
%864 = arith.index_cast %862 : i32 to index
%865 = arith.index_cast %863 : i32 to index
%867 = arith.constant 1 : index
%868 = arith.constant -1 : index
%869 = arith.cmpi sle, %864, %865 : index
%866 = arith.select %869, %867, %868 : index
cf.br ^bb99(%864 : index)
^bb99(%870: index):
%871 = arith.cmpi slt, %870, %865 : index
%872 = arith.cmpi sgt, %870, %865 : index
%873 = arith.select %869, %871, %872 : i1
cf.cond_br %873, ^bb100(%870 : index), ^bb101(%870 : index)
^bb100(%874: index):
%876 = arith.index_cast %874 : index to i64
%877 = llvm.getelementptr %628[%876] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%875 = llvm.load %877 : !llvm.ptr -> i64
%879 = llvm.load %861 : !llvm.ptr -> i64
%880 = arith.constant 1 : i32
%882 = arith.extsi %880 : i32 to i64
%881 = arith.subi %879, %882 : i64
%883 = llvm.getelementptr %628[%881] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%878 = llvm.load %883 : !llvm.ptr -> i64
%884 = arith.cmpi ne, %875, %878 : i64
cf.cond_br %884, ^bb102, ^bb103
^bb102:
%886 = arith.index_cast %874 : index to i64
%887 = llvm.getelementptr %628[%886] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%885 = llvm.load %887 : !llvm.ptr -> i64
%888 = llvm.load %861 : !llvm.ptr -> i64
%889 = llvm.getelementptr %628[%888] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %885, %889 : i64, !llvm.ptr
%890 = llvm.load %861 : !llvm.ptr -> i64
%891 = arith.constant 1 : i32
%893 = arith.extsi %891 : i32 to i64
%892 = arith.addi %890, %893 : i64
llvm.store %892, %861 : i64, !llvm.ptr
cf.br ^bb104
^bb103:
cf.br ^bb104
^bb104:
%894 = arith.addi %874, %866 : index
cf.br ^bb99(%894 : index)
^bb101(%895: index):
%896 = arith.constant 0 : i32
%897 = llvm.load %703 : !llvm.ptr -> i64
%898 = arith.index_cast %896 : i32 to index
%899 = arith.index_cast %897 : i32 to index
%901 = arith.constant 1 : index
%902 = arith.constant -1 : index
%903 = arith.cmpi sle, %898, %899 : index
%900 = arith.select %903, %901, %902 : index
cf.br ^bb105(%898 : index)
^bb105(%904: index):
%905 = arith.cmpi slt, %904, %899 : index
%906 = arith.cmpi sgt, %904, %899 : index
%907 = arith.select %903, %905, %906 : i1
cf.cond_br %907, ^bb106(%904 : index), ^bb107(%904 : index)
^bb106(%908: index):
%910 = llvm.load %861 : !llvm.ptr -> i64
%912 = arith.index_cast %908 : index to i64
%913 = llvm.getelementptr %686[%912] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%911 = llvm.load %913 : !llvm.ptr -> i64
%909 = func.call @bsearch_idx(%628, %910, %911) : (!llvm.ptr, i64, i64) -> i64
%914 = arith.index_cast %908 : index to i64
%915 = llvm.getelementptr %686[%914] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %909, %915 : i64, !llvm.ptr
%917 = llvm.load %861 : !llvm.ptr -> i64
%919 = arith.index_cast %908 : index to i64
%920 = llvm.getelementptr %693[%919] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%918 = llvm.load %920 : !llvm.ptr -> i64
%916 = func.call @bsearch_idx(%628, %917, %918) : (!llvm.ptr, i64, i64) -> i64
%921 = arith.index_cast %908 : index to i64
%922 = llvm.getelementptr %693[%921] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %916, %922 : i64, !llvm.ptr
%923 = arith.addi %908, %900 : index
cf.br ^bb105(%923 : index)
^bb107(%924: index):
%926 = llvm.load %703 : !llvm.ptr -> i64
%927 = arith.constant 8 : i32
%929 = arith.extsi %927 : i32 to i64
%928 = arith.muli %926, %929 : i64
%925 = func.call @malloc(%928) : (i64) -> !llvm.ptr
%930 = arith.constant 0 : i32
%931 = llvm.load %703 : !llvm.ptr -> i64
%932 = arith.index_cast %930 : i32 to index
%933 = arith.index_cast %931 : i32 to index
%935 = arith.constant 1 : index
%936 = arith.constant -1 : index
%937 = arith.cmpi sle, %932, %933 : index
%934 = arith.select %937, %935, %936 : index
cf.br ^bb108(%932 : index)
^bb108(%938: index):
%939 = arith.cmpi slt, %938, %933 : index
%940 = arith.cmpi sgt, %938, %933 : index
%941 = arith.select %937, %939, %940 : i1
cf.cond_br %941, ^bb109(%938 : index), ^bb110(%938 : index)
^bb109(%942: index):
%943 = arith.index_cast %942 : index to i64
%944 = arith.index_cast %942 : index to i64
%945 = llvm.getelementptr %925[%944] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %943, %945 : i64, !llvm.ptr
%946 = arith.addi %942, %934 : index
cf.br ^bb108(%946 : index)
^bb110(%947: index):
%949 = llvm.load %703 : !llvm.ptr -> i64
func.call @heapsort_idx(%925, %672, %949) : (!llvm.ptr, !llvm.ptr, i64) -> ()
%950 = llvm.load %861 : !llvm.ptr -> i64
%951 = arith.constant 1 : i32
%953 = arith.extsi %951 : i32 to i64
%952 = arith.subi %950, %953 : i64
%954 = arith.constant 4 : i32
%956 = arith.extsi %954 : i32 to i64
%955 = arith.muli %956, %952 : i64
%957 = arith.constant 5 : i32
%959 = arith.extsi %957 : i32 to i64
%958 = arith.addi %955, %959 : i64
%961 = arith.constant 12 : i32
%963 = arith.extsi %961 : i32 to i64
%962 = arith.muli %963, %958 : i64
%964 = arith.constant 8 : i32
%965 = arith.extsi %964 : i32 to i64
%960 = func.call @calloc(%962, %965) : (i64, i64) -> !llvm.ptr
%966 = llvm.mlir.addressof @g_seg : !llvm.ptr
llvm.store %960, %966 : !llvm.ptr, !llvm.ptr
%968 = arith.constant 4 : i32
%969 = arith.extsi %968 : i32 to i64
%967 = func.call @calloc(%958, %969) : (i64, i64) -> !llvm.ptr
%970 = llvm.mlir.addressof @g_lazy : !llvm.ptr
llvm.store %967, %970 : !llvm.ptr, !llvm.ptr
%971 = llvm.mlir.addressof @g_y_vals : !llvm.ptr
llvm.store %628, %971 : !llvm.ptr, !llvm.ptr
%973 = arith.constant 12 : i32
%974 = arith.constant 8 : i32
%975 = arith.muli %973, %974 : i32
%976 = arith.extsi %975 : i32 to i64
%972 = func.call @malloc(%976) : (i64) -> !llvm.ptr
%977 = llvm.mlir.addressof @g_tmp12 : !llvm.ptr
llvm.store %972, %977 : !llvm.ptr, !llvm.ptr
%979 = arith.constant 1 : i32
%980 = arith.constant 0 : i32
%981 = arith.extsi %979 : i32 to i64
%982 = arith.extsi %980 : i32 to i64
func.call @build_tree(%981, %982, %952) : (i64, i64, i64) -> ()
%984 = arith.constant 12 : i32
%985 = arith.constant 8 : i32
%986 = arith.extsi %984 : i32 to i64
%987 = arith.extsi %985 : i32 to i64
%983 = func.call @calloc(%986, %987) : (i64, i64) -> !llvm.ptr
%988 = arith.constant 0 : i32
%989 = arith.extsi %988 : i32 to i64
%990 = llvm.mlir.constant(1 : i64) : i64
%991 = llvm.alloca %990 x i64 : (i64) -> !llvm.ptr
llvm.store %989, %991 : i64, !llvm.ptr
%992 = arith.constant 0 : i32
%993 = llvm.load %823 : !llvm.ptr -> i64
%994 = arith.constant 1 : i32
%996 = arith.extsi %994 : i32 to i64
%995 = arith.subi %993, %996 : i64
%997 = arith.index_cast %992 : i32 to index
%998 = arith.index_cast %995 : i32 to index
%1000 = arith.constant 1 : index
%1001 = arith.constant -1 : index
%1002 = arith.cmpi sle, %997, %998 : index
%999 = arith.select %1002, %1000, %1001 : index
cf.br ^bb111(%997 : index)
^bb111(%1003: index):
%1004 = arith.cmpi slt, %1003, %998 : index
%1005 = arith.cmpi sgt, %1003, %998 : index
%1006 = arith.select %1002, %1004, %1005 : i1
cf.cond_br %1006, ^bb112(%1003 : index), ^bb113(%1003 : index)
^bb112(%1007: index):
%1009 = arith.index_cast %1007 : index to i64
%1010 = llvm.getelementptr %624[%1009] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1008 = llvm.load %1010 : !llvm.ptr -> i64
cf.br ^bb114
^bb114:
%1011 = llvm.load %991 : !llvm.ptr -> i64
%1012 = llvm.load %703 : !llvm.ptr -> i64
%1013 = arith.cmpi slt, %1011, %1012 : i64
%1014 = scf.if %1013 -> (i1) {
%1017 = llvm.load %991 : !llvm.ptr -> i64
%1018 = llvm.getelementptr %925[%1017] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1016 = llvm.load %1018 : !llvm.ptr -> i64
%1019 = llvm.getelementptr %672[%1016] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1015 = llvm.load %1019 : !llvm.ptr -> i64
%1020 = arith.cmpi eq, %1015, %1008 : i64
scf.yield %1020 : i1
} else {
%1021 = arith.constant false
scf.yield %1021 : i1
}
cf.cond_br %1014, ^bb115, ^bb116
^bb115:
%1023 = arith.constant 1 : i32
%1024 = arith.constant 0 : i32
%1027 = llvm.load %991 : !llvm.ptr -> i64
%1028 = llvm.getelementptr %925[%1027] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1026 = llvm.load %1028 : !llvm.ptr -> i64
%1029 = llvm.getelementptr %686[%1026] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1025 = llvm.load %1029 : !llvm.ptr -> i64
%1032 = llvm.load %991 : !llvm.ptr -> i64
%1033 = llvm.getelementptr %925[%1032] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1031 = llvm.load %1033 : !llvm.ptr -> i64
%1034 = llvm.getelementptr %693[%1031] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1030 = llvm.load %1034 : !llvm.ptr -> i64
%1037 = llvm.load %991 : !llvm.ptr -> i64
%1038 = llvm.getelementptr %925[%1037] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1036 = llvm.load %1038 : !llvm.ptr -> i64
%1039 = llvm.getelementptr %679[%1036] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1035 = llvm.load %1039 : !llvm.ptr -> i32
%1040 = arith.extsi %1035 : i32 to i64
%1041 = arith.extsi %1023 : i32 to i64
%1042 = arith.extsi %1024 : i32 to i64
func.call @update_tree(%1041, %1042, %952, %1025, %1030, %1040) : (i64, i64, i64, i64, i64, i64) -> ()
%1043 = llvm.load %991 : !llvm.ptr -> i64
%1044 = arith.constant 1 : i32
%1046 = arith.extsi %1044 : i32 to i64
%1045 = arith.addi %1043, %1046 : i64
llvm.store %1045, %991 : i64, !llvm.ptr
cf.br ^bb114
^bb116:
%1048 = arith.constant 1 : i32
%1050 = arith.index_cast %1007 : index to i32
%1049 = arith.addi %1050, %1048 : i32
%1051 = arith.extsi %1049 : i32 to i64
%1052 = llvm.getelementptr %624[%1051] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1047 = llvm.load %1052 : !llvm.ptr -> i64
%1053 = arith.subi %1047, %1008 : i64
%1054 = arith.constant 0 : i32
%1056 = arith.extsi %1054 : i32 to i64
%1055 = arith.cmpi ne, %1053, %1056 : i64
cf.cond_br %1055, ^bb117, ^bb118
^bb117:
%1057 = arith.constant 12 : i32
%1058 = arith.extsi %1057 : i32 to i64
%1059 = arith.constant 0 : i32
%1060 = arith.constant 12 : i32
%1061 = arith.index_cast %1059 : i32 to index
%1062 = arith.index_cast %1060 : i32 to index
%1064 = arith.constant 1 : index
%1065 = arith.constant -1 : index
%1066 = arith.cmpi sle, %1061, %1062 : index
%1063 = arith.select %1066, %1064, %1065 : index
cf.br ^bb120(%1061 : index)
^bb120(%1067: index):
%1068 = arith.cmpi slt, %1067, %1062 : index
%1069 = arith.cmpi sgt, %1067, %1062 : index
%1070 = arith.select %1066, %1068, %1069 : i1
cf.cond_br %1070, ^bb121(%1067 : index), ^bb122(%1067 : index)
^bb121(%1071: index):
%1073 = arith.index_cast %1071 : index to i64
%1074 = llvm.getelementptr %983[%1073] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1072 = llvm.load %1074 : !llvm.ptr -> i64
%1076 = llvm.mlir.addressof @g_seg : !llvm.ptr
%1077 = llvm.load %1076 : !llvm.ptr -> !llvm.ptr
%1079 = arith.trunci %1058 : i64 to i32
%1080 = arith.index_cast %1071 : index to i32
%1078 = arith.addi %1079, %1080 : i32
%1081 = arith.extsi %1078 : i32 to i64
%1082 = llvm.getelementptr %1077[%1081] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1075 = llvm.load %1082 : !llvm.ptr -> i64
%1083 = arith.muli %1053, %1075 : i64
%1084 = arith.addi %1072, %1083 : i64
%1085 = arith.index_cast %1071 : index to i64
%1086 = llvm.getelementptr %983[%1085] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1084, %1086 : i64, !llvm.ptr
%1087 = arith.addi %1071, %1063 : index
cf.br ^bb120(%1087 : index)
^bb122(%1088: index):
cf.br ^bb119
^bb118:
cf.br ^bb119
^bb119:
%1089 = arith.addi %1007, %999 : index
cf.br ^bb111(%1089 : index)
^bb113(%1090: index):
%1091 = arith.constant 12 : i32
%1093 = arith.constant 0 : i32
%1094 = arith.extsi %1093 : i32 to i64
%1095 = llvm.getelementptr %983[%1094] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1092 = llvm.load %1095 : !llvm.ptr -> i64
%1097 = arith.extsi %1091 : i32 to i64
%1096 = arith.muli %1097, %1092 : i64
%1098 = llvm.mlir.constant(1 : i64) : i64
%1099 = llvm.alloca %1098 x i64 : (i64) -> !llvm.ptr
llvm.store %1096, %1099 : i64, !llvm.ptr
%1100 = arith.constant 1 : i32
%1101 = arith.constant 12 : i32
%1102 = arith.index_cast %1100 : i32 to index
%1103 = arith.index_cast %1101 : i32 to index
%1105 = arith.constant 1 : index
%1106 = arith.constant -1 : index
%1107 = arith.cmpi sle, %1102, %1103 : index
%1104 = arith.select %1107, %1105, %1106 : index
cf.br ^bb123(%1102 : index)
^bb123(%1108: index):
%1109 = arith.cmpi slt, %1108, %1103 : index
%1110 = arith.cmpi sgt, %1108, %1103 : index
%1111 = arith.select %1107, %1109, %1110 : i1
cf.cond_br %1111, ^bb124(%1108 : index), ^bb125(%1108 : index)
^bb124(%1112: index):
%1113 = llvm.load %1099 : !llvm.ptr -> i64
%1115 = arith.index_cast %1112 : index to i64
%1116 = llvm.getelementptr %983[%1115] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1114 = llvm.load %1116 : !llvm.ptr -> i64
%1118 = arith.index_cast %1112 : index to i32
%1119 = arith.trunci %1114 : i64 to i32
%1117 = arith.muli %1118, %1119 : i32
%1121 = arith.extsi %1117 : i32 to i64
%1120 = arith.addi %1113, %1121 : i64
llvm.store %1120, %1099 : i64, !llvm.ptr
%1122 = arith.addi %1112, %1104 : index
cf.br ^bb123(%1122 : index)
^bb125(%1123: index):
%1125 = llvm.mlir.addressof @g_seg : !llvm.ptr
%1126 = llvm.load %1125 : !llvm.ptr -> !llvm.ptr
func.call @free(%1126) : (!llvm.ptr) -> ()
%1128 = llvm.mlir.addressof @g_lazy : !llvm.ptr
%1129 = llvm.load %1128 : !llvm.ptr -> !llvm.ptr
func.call @free(%1129) : (!llvm.ptr) -> ()
%1131 = llvm.mlir.addressof @g_tmp12 : !llvm.ptr
%1132 = llvm.load %1131 : !llvm.ptr -> !llvm.ptr
func.call @free(%1132) : (!llvm.ptr) -> ()
func.call @free(%624) : (!llvm.ptr) -> ()
func.call @free(%628) : (!llvm.ptr) -> ()
func.call @free(%672) : (!llvm.ptr) -> ()
func.call @free(%679) : (!llvm.ptr) -> ()
func.call @free(%686) : (!llvm.ptr) -> ()
func.call @free(%693) : (!llvm.ptr) -> ()
func.call @free(%925) : (!llvm.ptr) -> ()
func.call @free(%983) : (!llvm.ptr) -> ()
%1141 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1142 = llvm.load %1099 : !llvm.ptr -> i64
%1143 = llvm.call @printf(%1141, %1142) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1144 = arith.constant 0 : i32
func.return %1144 : i32
}
}