← All problems Problem 963
F(N) for N = 10^5. For each n, compute a key (L_tuple, parity, B_value). Count occurrences, combine pairs, sum v^2/4. Ported from C. Uses i128 for the final sum, f64 for B values.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)?Space complexity O(n^2)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 963: A Gated Town
# F(N) for N = 10^5. For each n, compute a key (L_tuple, parity, B_value).
# Count occurrences, combine pairs, sum v^2/4.
# Ported from C. Uses i128 for the final sum, f64 for B values.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>)
function printf(fmt: ptr<i8>, ...) -> i32
function log(x: f64) -> f64
function ceil(x: f64) -> f64
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
}
const N: i64 = 100000
const MAX_KEY_LEN: i32 = 24
# B table
let mut g_B: ptr<f64> = null
function build_B(m: i32) -> void {
g_B = calloc(((m + 1) as i64), 8)
let mut i: i32 = 1
while i <= m {
let h: f64 = g_B[i >> 1]
if (i & 1) == 1 { g_B[i] = h + 1.0 }
else {
if h < 2.0 { g_B[i] = h / 2.0 }
else { g_B[i] = h - 1.0 }
}
i = i + 1
}
}
# Key fields as parallel arrays (for all_keys, size N)
# key_len: ptr<i32>
# key_L: ptr<i32> (flat N * MAX_KEY_LEN)
# key_parity: ptr<i32>
# key_bval: ptr<f64>
function compute_key(n: i64, klen: ptr<i32>, kL: ptr<i32>, kparity: ptr<i32>, kbval: ptr<f64>) -> void {
let s: ptr<i8> = calloc(32, 1)
let mut slen: i32 = 0
let mut x: i64 = n
while x > 0 {
s[slen] = ((x % 3) as i8) + 48
slen = slen + 1
x = x / 3
}
# Reverse s
let mut i: i32 = 0
while i < slen / 2 {
let t: i8 = s[i]
s[i] = s[slen - 1 - i]
s[slen - 1 - i] = t
i = i + 1
}
if slen == 0 {
s[0] = 48
slen = 1
}
# Find l = last position before first '1' where digit < '1' (digit is '0')
let mut l: i32 = -1
let mut j: i32 = 0
while j < slen {
if s[j] == 49 { break }
if s[j] < 49 { l = j }
j = j + 1
}
# Compute L tuple
klen[0] = 0
if l > -1 {
let mut k: i32 = 0
let mut j2: i32 = l - 1
while j2 >= 0 {
if s[j2] < 49 { k = k + 1 }
else {
kL[klen[0]] = k
klen[0] = klen[0] + 1
}
j2 = j2 - 1
}
}
# Count 2s for parity
let mut cnt2: i32 = 0
let mut j3: i32 = 0
while j3 < slen {
if s[j3] == 50 { cnt2 = cnt2 + 1 }
j3 = j3 + 1
}
kparity[0] = cnt2 & 1
# Compute bval from digits < 2 (0s and 1s)
let u: ptr<i8> = calloc(32, 1)
let mut ulen: i32 = 0
let mut j4: i32 = 0
while j4 < slen {
if s[j4] < 50 {
u[ulen] = s[j4]
ulen = ulen + 1
}
j4 = j4 + 1
}
if ulen == 0 {
kbval[0] = 0.0
} else {
let mut val: i64 = 0
let mut j5: i32 = 0
while j5 < ulen {
val = val * 2 + ((u[j5] - 48) as i64)
j5 = j5 + 1
}
kbval[0] = g_B[val]
}
# Zero-fill remaining L
let mut j6: i32 = klen[0]
while j6 < MAX_KEY_LEN {
kL[j6] = 0
j6 = j6 + 1
}
free(s as ptr<void>)
free(u as ptr<void>)
}
# Compare two keys by index. Returns -1, 0, or 1.
function cmp_key(a_len: ptr<i32>, a_L: ptr<i32>, a_parity: ptr<i32>, a_bval: ptr<f64>,
ia: i64,
b_len: ptr<i32>, b_L: ptr<i32>, b_parity: ptr<i32>, b_bval: ptr<f64>,
ib: i64) -> i32 {
let la: i32 = a_len[ia]
let lb: i32 = b_len[ib]
if la != lb {
if la < lb { return -1 }
return 1
}
let mut i: i32 = 0
while i < la {
let va: i32 = a_L[ia * (MAX_KEY_LEN as i64) + i]
let vb: i32 = b_L[ib * (MAX_KEY_LEN as i64) + i]
if va != vb {
if va < vb { return -1 }
return 1
}
i = i + 1
}
let pa: i32 = a_parity[ia]
let pb: i32 = b_parity[ib]
if pa != pb {
if pa < pb { return -1 }
return 1
}
let ba: f64 = a_bval[ia]
let bb: f64 = b_bval[ib]
if ba < bb { return -1 }
if ba > bb { return 1 }
return 0
}
# Merge sort on indices. Uses temp arrays.
function merge_sort(indices: ptr<i64>, lo: i32, hi: i32,
klen: ptr<i32>, kL: ptr<i32>, kparity: ptr<i32>, kbval: ptr<f64>,
tmp: ptr<i64>) -> void {
if hi - lo <= 1 { return }
let mid: i32 = (lo + hi) / 2
merge_sort(indices, lo, mid, klen, kL, kparity, kbval, tmp)
merge_sort(indices, mid, hi, klen, kL, kparity, kbval, tmp)
# Merge
let mut i: i32 = lo
let mut j: i32 = mid
let mut k: i32 = lo
while i < mid && j < hi {
let c: i32 = cmp_key(klen, kL, kparity, kbval, indices[i],
klen, kL, kparity, kbval, indices[j])
if c <= 0 {
tmp[k] = indices[i]
i = i + 1
} else {
tmp[k] = indices[j]
j = j + 1
}
k = k + 1
}
while i < mid {
tmp[k] = indices[i]
i = i + 1
k = k + 1
}
while j < hi {
tmp[k] = indices[j]
j = j + 1
k = k + 1
}
let mut x: i32 = lo
while x < hi {
indices[x] = tmp[x]
x = x + 1
}
}
function keys_equal(a_len: ptr<i32>, a_L: ptr<i32>, a_parity: ptr<i32>, a_bval: ptr<f64>, ia: i64,
b_len: ptr<i32>, b_L: ptr<i32>, b_parity: ptr<i32>, b_bval: ptr<f64>, ib: i64) -> i32 {
if a_len[ia] != b_len[ib] { return 0 }
let la: i32 = a_len[ia]
let mut i: i32 = 0
while i < la {
if a_L[ia * (MAX_KEY_LEN as i64) + i] != b_L[ib * (MAX_KEY_LEN as i64) + i] { return 0 }
i = i + 1
}
if a_parity[ia] != b_parity[ib] { return 0 }
return if a_bval[ia] == b_bval[ib] { 1 } else { 0 }
}
# Combine two keys into a result key
function combine_key(a_len: ptr<i32>, a_L: ptr<i32>, a_parity: ptr<i32>, a_bval: ptr<f64>, ia: i64,
b_len: ptr<i32>, b_L: ptr<i32>, b_parity: ptr<i32>, b_bval: ptr<f64>, ib: i64,
out_len: ptr<i32>, out_L: ptr<i32>, out_parity: ptr<i32>, out_bval: ptr<f64>) -> void {
let la: i32 = a_len[ia]
let lb: i32 = b_len[ib]
out_len[0] = la + lb
let mut idx: i32 = 0
let mut i: i32 = 0
while i < la {
out_L[idx] = a_L[ia * (MAX_KEY_LEN as i64) + i]
idx = idx + 1
i = i + 1
}
let mut j: i32 = 0
while j < lb {
out_L[idx] = b_L[ib * (MAX_KEY_LEN as i64) + j]
idx = idx + 1
j = j + 1
}
# Sort ascending (insertion sort, len <= 24)
let mut p: i32 = 0
while p < out_len[0] {
let mut q: i32 = p + 1
while q < out_len[0] {
if out_L[p] > out_L[q] {
let t: i32 = out_L[p]
out_L[p] = out_L[q]
out_L[q] = t
}
q = q + 1
}
p = p + 1
}
out_parity[0] = a_parity[ia] ^ b_parity[ib]
out_bval[0] = a_bval[ia] + b_bval[ib]
# Zero-fill
let mut r: i32 = out_len[0]
while r < MAX_KEY_LEN {
out_L[r] = 0
r = r + 1
}
}
function main() -> i32 {
let m: i32 = 1 << ((ceil(log((N as f64)) / log(3.0))) as i32)
if m < 1 { build_B(1) } else { build_B(m) }
# Build all keys for n=1..N
let all_len: ptr<i32> = calloc(N, 4)
let all_L: ptr<i32> = calloc(N * (MAX_KEY_LEN as i64), 4)
let all_parity: ptr<i32> = calloc(N, 4)
let all_bval: ptr<f64> = calloc(N, 8)
let mut n: i64 = 1
while n <= N {
let idx: i64 = n - 1
compute_key(n, all_len + idx, all_L + idx * (MAX_KEY_LEN as i64), all_parity + idx, all_bval + idx)
n = n + 1
}
# Sort keys using merge sort on indices
let indices: ptr<i64> = calloc(N, 8)
let tmp: ptr<i64> = calloc(N, 8)
let mut i: i64 = 0
while i < N {
indices[i] = i
i = i + 1
}
merge_sort(indices, 0, N as i32, all_len, all_L, all_parity, all_bval, tmp)
# Extract unique keys and counts
let u_len: ptr<i32> = calloc(N, 4)
let u_L: ptr<i32> = calloc(N * (MAX_KEY_LEN as i64), 4)
let u_parity: ptr<i32> = calloc(N, 4)
let u_bval: ptr<f64> = calloc(N, 8)
let u_count: ptr<i64> = calloc(N, 8)
let mut nkeys: i64 = 0
let mut i2: i64 = 0
while i2 < N {
let ia: i64 = indices[i2]
let mut j: i64 = i2 + 1
while j < N {
let ib: i64 = indices[j]
if keys_equal(all_len, all_L, all_parity, all_bval, ia,
all_len, all_L, all_parity, all_bval, ib) == 0 { break }
j = j + 1
}
# Copy key to unique
u_len[nkeys] = all_len[ia]
let mut k: i32 = 0
let la: i32 = all_len[ia]
while k < MAX_KEY_LEN {
u_L[nkeys * (MAX_KEY_LEN as i64) + k] = all_L[ia * (MAX_KEY_LEN as i64) + k]
k = k + 1
}
u_parity[nkeys] = all_parity[ia]
u_bval[nkeys] = all_bval[ia]
u_count[nkeys] = j - i2
nkeys = nkeys + 1
i2 = j
}
free(indices as ptr<void>)
free(tmp as ptr<void>)
free(all_len as ptr<void>)
free(all_L as ptr<void>)
free(all_parity as ptr<void>)
free(all_bval as ptr<void>)
# Generate all combined keys
let total_combos: i64 = nkeys * nkeys
let c_len: ptr<i32> = calloc(total_combos, 4)
let c_L: ptr<i32> = calloc(total_combos * (MAX_KEY_LEN as i64), 4)
let c_parity: ptr<i32> = calloc(total_combos, 4)
let c_bval: ptr<f64> = calloc(total_combos, 8)
let c_count: ptr<i64> = calloc(total_combos, 8)
let mut ci: i64 = 0
let mut ai: i64 = 0
while ai < nkeys {
let mut bi: i64 = 0
while bi < nkeys {
combine_key(u_len, u_L, u_parity, u_bval, ai,
u_len, u_L, u_parity, u_bval, bi,
c_len + ci, c_L + ci * (MAX_KEY_LEN as i64), c_parity + ci, c_bval + ci)
let extra: i64 = if ai == bi { 1 } else { 0 }
c_count[ci] = u_count[ai] * (u_count[bi] + extra)
ci = ci + 1
bi = bi + 1
}
ai = ai + 1
}
free(u_len as ptr<void>)
free(u_L as ptr<void>)
free(u_parity as ptr<void>)
free(u_bval as ptr<void>)
free(u_count as ptr<void>)
# Sort combos by key using merge sort
let c_indices: ptr<i64> = calloc(total_combos, 8)
let c_tmp: ptr<i64> = calloc(total_combos, 8)
let mut ci2: i64 = 0
while ci2 < total_combos {
c_indices[ci2] = ci2
ci2 = ci2 + 1
}
merge_sort(c_indices, 0, total_combos as i32, c_len, c_L, c_parity, c_bval, c_tmp)
# Merge identical keys and sum counts, accumulate v^2
let mut ans: i128 = 0
let mut k: i64 = 0
while k < total_combos {
let ik: i64 = c_indices[k]
let mut j: i64 = k + 1
while j < total_combos {
let ij: i64 = c_indices[j]
if keys_equal(c_len, c_L, c_parity, c_bval, ik,
c_len, c_L, c_parity, c_bval, ij) == 0 { break }
j = j + 1
}
let mut v: i128 = 0
let mut x: i64 = k
while x < j {
v = v + (c_count[c_indices[x]] as i128)
x = x + 1
}
ans = ans + v * v
k = j
}
ans = ans / 4
free(c_len as ptr<void>)
free(c_L as ptr<void>)
free(c_parity as ptr<void>)
free(c_bval as ptr<void>)
free(c_count as ptr<void>)
free(c_indices as ptr<void>)
free(c_tmp as ptr<void>)
free(g_B as ptr<void>)
printf("%lld\n", ans as i64)
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 build_B_i32(int32_t m);
void compute_key_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64(int64_t n, int32_t* klen, int32_t* kL, int32_t* kparity, double* kbval);
int32_t cmp_key_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64(int32_t* a_len, int32_t* a_L, int32_t* a_parity, double* a_bval, int64_t ia, int32_t* b_len, int32_t* b_L, int32_t* b_parity, double* b_bval, int64_t ib);
void merge_sort_ptr_i64_i32_i32_ptr_i32_ptr_i32_ptr_i32_ptr_f64_ptr_i64(int64_t* indices, int32_t lo, int32_t hi, int32_t* klen, int32_t* kL, int32_t* kparity, double* kbval, int64_t* tmp);
int32_t keys_equal_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64(int32_t* a_len, int32_t* a_L, int32_t* a_parity, double* a_bval, int64_t ia, int32_t* b_len, int32_t* b_L, int32_t* b_parity, double* b_bval, int64_t ib);
void combine_key_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64(int32_t* a_len, int32_t* a_L, int32_t* a_parity, double* a_bval, int64_t ia, int32_t* b_len, int32_t* b_L, int32_t* b_parity, double* b_bval, int64_t ib, int32_t* out_len, int32_t* out_L, int32_t* out_parity, double* out_bval);
int32_t main(void);
static const int64_t N = 100000;
static const int32_t MAX_KEY_LEN = 24;
/* Module statics */
static double* g_B = NULL;
void build_B_i32(int32_t m) {
g_B = calloc(((int64_t)((m + 1))), 8);
int32_t i = 1;
while (i <= m) {
double h = g_B[FLOW_CHECKED_SHR((i), (1))];
if ((i & 1) == 1) {
g_B[i] = (h + 1.0);
} else {
if (h < 2.0) {
g_B[i] = (h / 2.0);
} else {
g_B[i] = (h - 1.0);
}
}
i = (i + 1);
}
}
void compute_key_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64(int64_t n, int32_t* klen, int32_t* kL, int32_t* kparity, double* kbval) {
int8_t* s = (int8_t*)(calloc(32, 1));
int32_t slen = 0;
int64_t x = n;
while (x > 0) {
s[slen] = (((int8_t)(FLOW_CHECKED_MOD((x), (3)))) + 48);
slen = (slen + 1);
x = FLOW_CHECKED_DIV((x), (3));
}
int32_t i = 0;
while (i < FLOW_CHECKED_DIV((slen), (2))) {
int8_t t = s[i];
s[i] = s[((slen - 1) - i)];
s[((slen - 1) - i)] = t;
i = (i + 1);
}
if (slen == 0) {
s[0] = 48;
slen = 1;
}
int32_t l = (-1);
int32_t j = 0;
while (j < slen) {
if (s[j] == 49) {
break;
}
if (s[j] < 49) {
l = j;
}
j = (j + 1);
}
klen[0] = 0;
if (l > (-1)) {
int32_t k = 0;
int32_t j2 = (l - 1);
while (j2 >= 0) {
if (s[j2] < 49) {
k = (k + 1);
} else {
kL[klen[0]] = k;
klen[0] = (klen[0] + 1);
}
j2 = (j2 - 1);
}
}
int32_t cnt2 = 0;
int32_t j3 = 0;
while (j3 < slen) {
if (s[j3] == 50) {
cnt2 = (cnt2 + 1);
}
j3 = (j3 + 1);
}
kparity[0] = (cnt2 & 1);
int8_t* u = (int8_t*)(calloc(32, 1));
int32_t ulen = 0;
int32_t j4 = 0;
while (j4 < slen) {
if (s[j4] < 50) {
u[ulen] = s[j4];
ulen = (ulen + 1);
}
j4 = (j4 + 1);
}
if (ulen == 0) {
kbval[0] = 0.0;
} else {
int64_t val = 0;
int32_t j5 = 0;
while (j5 < ulen) {
val = ((val * 2) + ((int64_t)((u[j5] - 48))));
j5 = (j5 + 1);
}
kbval[0] = g_B[val];
}
int32_t j6 = klen[0];
while (j6 < MAX_KEY_LEN) {
kL[j6] = 0;
j6 = (j6 + 1);
}
free(((void*)(s)));
free(((void*)(u)));
}
int32_t cmp_key_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64(int32_t* a_len, int32_t* a_L, int32_t* a_parity, double* a_bval, int64_t ia, int32_t* b_len, int32_t* b_L, int32_t* b_parity, double* b_bval, int64_t ib) {
int32_t la = a_len[ia];
int32_t lb = b_len[ib];
if (la != lb) {
if (la < lb) {
return (-1);
}
return 1;
}
int32_t i = 0;
while (i < la) {
int32_t va = a_L[((ia * ((int64_t)(MAX_KEY_LEN))) + i)];
int32_t vb = b_L[((ib * ((int64_t)(MAX_KEY_LEN))) + i)];
if (va != vb) {
if (va < vb) {
return (-1);
}
return 1;
}
i = (i + 1);
}
int32_t pa = a_parity[ia];
int32_t pb = b_parity[ib];
if (pa != pb) {
if (pa < pb) {
return (-1);
}
return 1;
}
double ba = a_bval[ia];
double bb = b_bval[ib];
if (ba < bb) {
return (-1);
}
if (ba > bb) {
return 1;
}
return 0;
}
void merge_sort_ptr_i64_i32_i32_ptr_i32_ptr_i32_ptr_i32_ptr_f64_ptr_i64(int64_t* indices, int32_t lo, int32_t hi, int32_t* klen, int32_t* kL, int32_t* kparity, double* kbval, int64_t* tmp) {
if ((hi - lo) <= 1) {
return;
}
int32_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
merge_sort_ptr_i64_i32_i32_ptr_i32_ptr_i32_ptr_i32_ptr_f64_ptr_i64(indices, lo, mid, klen, kL, kparity, kbval, tmp);
merge_sort_ptr_i64_i32_i32_ptr_i32_ptr_i32_ptr_i32_ptr_f64_ptr_i64(indices, mid, hi, klen, kL, kparity, kbval, tmp);
int32_t i = lo;
int32_t j = mid;
int32_t k = lo;
while ((i < mid && j < hi)) {
int32_t c = cmp_key_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64(klen, kL, kparity, kbval, indices[i], klen, kL, kparity, kbval, indices[j]);
if (c <= 0) {
tmp[k] = indices[i];
i = (i + 1);
} else {
tmp[k] = indices[j];
j = (j + 1);
}
k = (k + 1);
}
while (i < mid) {
tmp[k] = indices[i];
i = (i + 1);
k = (k + 1);
}
while (j < hi) {
tmp[k] = indices[j];
j = (j + 1);
k = (k + 1);
}
int32_t x = lo;
while (x < hi) {
indices[x] = tmp[x];
x = (x + 1);
}
}
int32_t keys_equal_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64(int32_t* a_len, int32_t* a_L, int32_t* a_parity, double* a_bval, int64_t ia, int32_t* b_len, int32_t* b_L, int32_t* b_parity, double* b_bval, int64_t ib) {
if (a_len[ia] != b_len[ib]) {
return 0;
}
int32_t la = a_len[ia];
int32_t i = 0;
while (i < la) {
if (a_L[((ia * ((int64_t)(MAX_KEY_LEN))) + i)] != b_L[((ib * ((int64_t)(MAX_KEY_LEN))) + i)]) {
return 0;
}
i = (i + 1);
}
if (a_parity[ia] != b_parity[ib]) {
return 0;
}
return ((a_bval[ia] == b_bval[ib]) ? (1) : (0));
}
void combine_key_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64(int32_t* a_len, int32_t* a_L, int32_t* a_parity, double* a_bval, int64_t ia, int32_t* b_len, int32_t* b_L, int32_t* b_parity, double* b_bval, int64_t ib, int32_t* out_len, int32_t* out_L, int32_t* out_parity, double* out_bval) {
int32_t la = a_len[ia];
int32_t lb = b_len[ib];
out_len[0] = (la + lb);
int32_t idx = 0;
int32_t i = 0;
while (i < la) {
out_L[idx] = a_L[((ia * ((int64_t)(MAX_KEY_LEN))) + i)];
idx = (idx + 1);
i = (i + 1);
}
int32_t j = 0;
while (j < lb) {
out_L[idx] = b_L[((ib * ((int64_t)(MAX_KEY_LEN))) + j)];
idx = (idx + 1);
j = (j + 1);
}
int32_t p = 0;
while (p < out_len[0]) {
int32_t q = (p + 1);
while (q < out_len[0]) {
if (out_L[p] > out_L[q]) {
int32_t t = out_L[p];
out_L[p] = out_L[q];
out_L[q] = t;
}
q = (q + 1);
}
p = (p + 1);
}
out_parity[0] = (a_parity[ia] ^ b_parity[ib]);
out_bval[0] = (a_bval[ia] + b_bval[ib]);
int32_t r = out_len[0];
while (r < MAX_KEY_LEN) {
out_L[r] = 0;
r = (r + 1);
}
}
int32_t main(void) {
int32_t m = FLOW_CHECKED_SHL((1), (((int32_t)(ceil((log(((double)(N))) / log(3.0)))))));
if (m < 1) {
build_B_i32(1);
} else {
build_B_i32(m);
}
int32_t* all_len = (int32_t*)(calloc(N, 4));
int32_t* all_L = (int32_t*)(calloc((N * ((int64_t)(MAX_KEY_LEN))), 4));
int32_t* all_parity = (int32_t*)(calloc(N, 4));
double* all_bval = (double*)(calloc(N, 8));
int64_t n = 1;
while (n <= N) {
int64_t idx = (n - 1);
compute_key_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64(n, (all_len + idx), (all_L + (idx * ((int64_t)(MAX_KEY_LEN)))), (all_parity + idx), (all_bval + idx));
n = (n + 1);
}
int64_t* indices = (int64_t*)(calloc(N, 8));
int64_t* tmp = (int64_t*)(calloc(N, 8));
int64_t i = 0;
while (i < N) {
indices[i] = i;
i = (i + 1);
}
merge_sort_ptr_i64_i32_i32_ptr_i32_ptr_i32_ptr_i32_ptr_f64_ptr_i64(indices, 0, ((int32_t)(N)), all_len, all_L, all_parity, all_bval, tmp);
int32_t* u_len = (int32_t*)(calloc(N, 4));
int32_t* u_L = (int32_t*)(calloc((N * ((int64_t)(MAX_KEY_LEN))), 4));
int32_t* u_parity = (int32_t*)(calloc(N, 4));
double* u_bval = (double*)(calloc(N, 8));
int64_t* u_count = (int64_t*)(calloc(N, 8));
int64_t nkeys = 0;
int64_t i2 = 0;
while (i2 < N) {
int64_t ia = indices[i2];
int64_t j = (i2 + 1);
while (j < N) {
int64_t ib = indices[j];
if (keys_equal_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64(all_len, all_L, all_parity, all_bval, ia, all_len, all_L, all_parity, all_bval, ib) == 0) {
break;
}
j = (j + 1);
}
u_len[nkeys] = all_len[ia];
int32_t k = 0;
int32_t la = all_len[ia];
while (k < MAX_KEY_LEN) {
u_L[((nkeys * ((int64_t)(MAX_KEY_LEN))) + k)] = all_L[((ia * ((int64_t)(MAX_KEY_LEN))) + k)];
k = (k + 1);
}
u_parity[nkeys] = all_parity[ia];
u_bval[nkeys] = all_bval[ia];
u_count[nkeys] = (j - i2);
nkeys = (nkeys + 1);
i2 = j;
}
free(((void*)(indices)));
free(((void*)(tmp)));
free(((void*)(all_len)));
free(((void*)(all_L)));
free(((void*)(all_parity)));
free(((void*)(all_bval)));
int64_t total_combos = (nkeys * nkeys);
int32_t* c_len = (int32_t*)(calloc(total_combos, 4));
int32_t* c_L = (int32_t*)(calloc((total_combos * ((int64_t)(MAX_KEY_LEN))), 4));
int32_t* c_parity = (int32_t*)(calloc(total_combos, 4));
double* c_bval = (double*)(calloc(total_combos, 8));
int64_t* c_count = (int64_t*)(calloc(total_combos, 8));
int64_t ci = 0;
int64_t ai = 0;
while (ai < nkeys) {
int64_t bi = 0;
while (bi < nkeys) {
combine_key_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64(u_len, u_L, u_parity, u_bval, ai, u_len, u_L, u_parity, u_bval, bi, (c_len + ci), (c_L + (ci * ((int64_t)(MAX_KEY_LEN)))), (c_parity + ci), (c_bval + ci));
int64_t extra = ((ai == bi) ? (1) : (0));
c_count[ci] = (u_count[ai] * (u_count[bi] + extra));
ci = (ci + 1);
bi = (bi + 1);
}
ai = (ai + 1);
}
free(((void*)(u_len)));
free(((void*)(u_L)));
free(((void*)(u_parity)));
free(((void*)(u_bval)));
free(((void*)(u_count)));
int64_t* c_indices = (int64_t*)(calloc(total_combos, 8));
int64_t* c_tmp = (int64_t*)(calloc(total_combos, 8));
int64_t ci2 = 0;
while (ci2 < total_combos) {
c_indices[ci2] = ci2;
ci2 = (ci2 + 1);
}
merge_sort_ptr_i64_i32_i32_ptr_i32_ptr_i32_ptr_i32_ptr_f64_ptr_i64(c_indices, 0, ((int32_t)(total_combos)), c_len, c_L, c_parity, c_bval, c_tmp);
__int128 ans = 0;
int64_t k = 0;
while (k < total_combos) {
int64_t ik = c_indices[k];
int64_t j = (k + 1);
while (j < total_combos) {
int64_t ij = c_indices[j];
if (keys_equal_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64_ptr_i32_ptr_i32_ptr_i32_ptr_f64_i64(c_len, c_L, c_parity, c_bval, ik, c_len, c_L, c_parity, c_bval, ij) == 0) {
break;
}
j = (j + 1);
}
__int128 v = 0;
int64_t x = k;
while (x < j) {
v = (v + ((__int128)(c_count[c_indices[x]])));
x = (x + 1);
}
ans = (ans + (v * v));
k = j;
}
ans = FLOW_CHECKED_DIV((ans), (4));
free(((void*)(c_len)));
free(((void*)(c_L)));
free(((void*)(c_parity)));
free(((void*)(c_bval)));
free(((void*)(c_count)));
free(((void*)(c_indices)));
free(((void*)(c_tmp)));
free(((void*)(g_B)));
printf("%lld\n", ((int64_t)(ans)));
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 @log(f64) -> f64
func.func private @ceil(f64) -> f64
func.func private @memcpy(!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
// Constant: N
llvm.mlir.global internal constant @N(100000 : i64) : i64
// Constant: MAX_KEY_LEN
llvm.mlir.global internal constant @MAX_KEY_LEN(24 : i32) : i32
// Module static: g_B
llvm.mlir.global internal @g_B() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
func.func @build_B(%arg0: i32) -> () {
%2 = arith.constant 1 : i32
%3 = arith.addi %arg0, %2 : i32
%4 = arith.extsi %3 : i32 to i64
%5 = arith.constant 8 : i32
%6 = arith.extsi %5 : i32 to i64
%1 = func.call @calloc(%4, %6) : (i64, i64) -> !llvm.ptr
%7 = llvm.mlir.addressof @g_B : !llvm.ptr
llvm.store %1, %7 : !llvm.ptr, !llvm.ptr
%8 = arith.constant 1 : i32
%9 = llvm.mlir.constant(1 : i64) : i64
%10 = llvm.alloca %9 x i32 : (i64) -> !llvm.ptr
llvm.store %8, %10 : i32, !llvm.ptr
cf.br ^bb0
^bb0:
%11 = llvm.load %10 : !llvm.ptr -> i32
%12 = arith.cmpi sle, %11, %arg0 : i32
cf.cond_br %12, ^bb1, ^bb2
^bb1:
%14 = llvm.mlir.addressof @g_B : !llvm.ptr
%15 = llvm.load %14 : !llvm.ptr -> !llvm.ptr
%16 = llvm.load %10 : !llvm.ptr -> i32
%17 = arith.constant 1 : i32
%18 = arith.shrsi %16, %17 : i32
%19 = arith.extsi %18 : i32 to i64
%20 = llvm.getelementptr %15[%19] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%13 = llvm.load %20 : !llvm.ptr -> f64
%21 = llvm.load %10 : !llvm.ptr -> i32
%22 = arith.constant 1 : i32
%23 = arith.andi %21, %22 : i32
%24 = arith.constant 1 : i32
%25 = arith.cmpi eq, %23, %24 : i32
cf.cond_br %25, ^bb3, ^bb4
^bb3:
%26 = arith.constant 1.0 : f32
%28 = arith.extf %26 : f32 to f64
%27 = arith.addf %13, %28 : f64
%29 = llvm.mlir.addressof @g_B : !llvm.ptr
%30 = llvm.load %29 : !llvm.ptr -> !llvm.ptr
%31 = llvm.load %10 : !llvm.ptr -> i32
%32 = arith.extsi %31 : i32 to i64
%33 = llvm.getelementptr %30[%32] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %27, %33 : f64, !llvm.ptr
cf.br ^bb5
^bb4:
%34 = arith.constant 2.0 : f32
%36 = arith.extf %34 : f32 to f64
%35 = arith.cmpf olt, %13, %36 : f64
cf.cond_br %35, ^bb6, ^bb7
^bb6:
%37 = arith.constant 2.0 : f32
%39 = arith.extf %37 : f32 to f64
%38 = arith.divf %13, %39 : f64
%40 = llvm.mlir.addressof @g_B : !llvm.ptr
%41 = llvm.load %40 : !llvm.ptr -> !llvm.ptr
%42 = llvm.load %10 : !llvm.ptr -> i32
%43 = arith.extsi %42 : i32 to i64
%44 = llvm.getelementptr %41[%43] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %38, %44 : f64, !llvm.ptr
cf.br ^bb8
^bb7:
%45 = arith.constant 1.0 : f32
%47 = arith.extf %45 : f32 to f64
%46 = arith.subf %13, %47 : f64
%48 = llvm.mlir.addressof @g_B : !llvm.ptr
%49 = llvm.load %48 : !llvm.ptr -> !llvm.ptr
%50 = llvm.load %10 : !llvm.ptr -> i32
%51 = arith.extsi %50 : i32 to i64
%52 = llvm.getelementptr %49[%51] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %46, %52 : f64, !llvm.ptr
cf.br ^bb8
^bb8:
cf.br ^bb5
^bb5:
%53 = llvm.load %10 : !llvm.ptr -> i32
%54 = arith.constant 1 : i32
%55 = arith.addi %53, %54 : i32
llvm.store %55, %10 : i32, !llvm.ptr
cf.br ^bb0
^bb2:
func.return
}
func.func @compute_key(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: !llvm.ptr) -> () {
%57 = arith.constant 32 : i32
%58 = arith.constant 1 : i32
%59 = arith.extsi %57 : i32 to i64
%60 = arith.extsi %58 : i32 to i64
%56 = func.call @calloc(%59, %60) : (i64, i64) -> !llvm.ptr
%61 = arith.constant 0 : i32
%62 = llvm.mlir.constant(1 : i64) : i64
%63 = llvm.alloca %62 x i32 : (i64) -> !llvm.ptr
llvm.store %61, %63 : i32, !llvm.ptr
%64 = llvm.mlir.constant(1 : i64) : i64
%65 = llvm.alloca %64 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %65 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%66 = llvm.load %65 : !llvm.ptr -> i64
%67 = arith.constant 0 : i32
%69 = arith.extsi %67 : i32 to i64
%68 = arith.cmpi sgt, %66, %69 : i64
cf.cond_br %68, ^bb10, ^bb11
^bb10:
%70 = llvm.load %65 : !llvm.ptr -> i64
%71 = arith.constant 3 : i32
%73 = arith.extsi %71 : i32 to i64
%72 = arith.remsi %70, %73 : i64
%74 = arith.trunci %72 : i64 to i8
%75 = arith.constant 48 : i32
%77 = arith.extsi %74 : i8 to i32
%76 = arith.addi %77, %75 : i32
%78 = llvm.load %63 : !llvm.ptr -> i32
%79 = arith.trunci %76 : i32 to i8
%80 = arith.extsi %78 : i32 to i64
%81 = llvm.getelementptr %56[%80] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %79, %81 : i8, !llvm.ptr
%82 = llvm.load %63 : !llvm.ptr -> i32
%83 = arith.constant 1 : i32
%84 = arith.addi %82, %83 : i32
llvm.store %84, %63 : i32, !llvm.ptr
%85 = llvm.load %65 : !llvm.ptr -> i64
%86 = arith.constant 3 : i32
%88 = arith.extsi %86 : i32 to i64
%87 = arith.divsi %85, %88 : i64
llvm.store %87, %65 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%89 = arith.constant 0 : i32
%90 = llvm.mlir.constant(1 : i64) : i64
%91 = llvm.alloca %90 x i32 : (i64) -> !llvm.ptr
llvm.store %89, %91 : i32, !llvm.ptr
cf.br ^bb12
^bb12:
%92 = llvm.load %91 : !llvm.ptr -> i32
%93 = llvm.load %63 : !llvm.ptr -> i32
%94 = arith.constant 2 : i32
%95 = arith.divsi %93, %94 : i32
%96 = arith.cmpi slt, %92, %95 : i32
cf.cond_br %96, ^bb13, ^bb14
^bb13:
%98 = llvm.load %91 : !llvm.ptr -> i32
%99 = arith.extsi %98 : i32 to i64
%100 = llvm.getelementptr %56[%99] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%97 = llvm.load %100 : !llvm.ptr -> i8
%102 = llvm.load %63 : !llvm.ptr -> i32
%103 = arith.constant 1 : i32
%104 = arith.subi %102, %103 : i32
%105 = llvm.load %91 : !llvm.ptr -> i32
%106 = arith.subi %104, %105 : i32
%107 = arith.extsi %106 : i32 to i64
%108 = llvm.getelementptr %56[%107] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%101 = llvm.load %108 : !llvm.ptr -> i8
%109 = llvm.load %91 : !llvm.ptr -> i32
%110 = arith.extsi %109 : i32 to i64
%111 = llvm.getelementptr %56[%110] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %101, %111 : i8, !llvm.ptr
%112 = llvm.load %63 : !llvm.ptr -> i32
%113 = arith.constant 1 : i32
%114 = arith.subi %112, %113 : i32
%115 = llvm.load %91 : !llvm.ptr -> i32
%116 = arith.subi %114, %115 : i32
%117 = arith.extsi %116 : i32 to i64
%118 = llvm.getelementptr %56[%117] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %97, %118 : i8, !llvm.ptr
%119 = llvm.load %91 : !llvm.ptr -> i32
%120 = arith.constant 1 : i32
%121 = arith.addi %119, %120 : i32
llvm.store %121, %91 : i32, !llvm.ptr
cf.br ^bb12
^bb14:
%122 = llvm.load %63 : !llvm.ptr -> i32
%123 = arith.constant 0 : i32
%124 = arith.cmpi eq, %122, %123 : i32
cf.cond_br %124, ^bb15, ^bb16
^bb15:
%125 = arith.constant 48 : i32
%126 = arith.constant 0 : i32
%127 = arith.trunci %125 : i32 to i8
%128 = arith.extsi %126 : i32 to i64
%129 = llvm.getelementptr %56[%128] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %127, %129 : i8, !llvm.ptr
%130 = arith.constant 1 : i32
llvm.store %130, %63 : i32, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%131 = arith.constant 1 : i32
%133 = arith.constant 0 : i32
%132 = arith.subi %133, %131 : i32
%134 = llvm.mlir.constant(1 : i64) : i64
%135 = llvm.alloca %134 x i32 : (i64) -> !llvm.ptr
llvm.store %132, %135 : i32, !llvm.ptr
%136 = arith.constant 0 : i32
%137 = llvm.mlir.constant(1 : i64) : i64
%138 = llvm.alloca %137 x i32 : (i64) -> !llvm.ptr
llvm.store %136, %138 : i32, !llvm.ptr
cf.br ^bb18
^bb18:
%139 = llvm.load %138 : !llvm.ptr -> i32
%140 = llvm.load %63 : !llvm.ptr -> i32
%141 = arith.cmpi slt, %139, %140 : i32
cf.cond_br %141, ^bb19, ^bb20
^bb19:
%143 = llvm.load %138 : !llvm.ptr -> i32
%144 = arith.extsi %143 : i32 to i64
%145 = llvm.getelementptr %56[%144] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%142 = llvm.load %145 : !llvm.ptr -> i8
%146 = arith.constant 49 : i32
%148 = arith.extsi %142 : i8 to i32
%147 = arith.cmpi eq, %148, %146 : i32
cf.cond_br %147, ^bb21, ^bb22
^bb21:
cf.br ^bb20
^bb22:
cf.br ^bb23
^bb23:
%150 = llvm.load %138 : !llvm.ptr -> i32
%151 = arith.extsi %150 : i32 to i64
%152 = llvm.getelementptr %56[%151] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%149 = llvm.load %152 : !llvm.ptr -> i8
%153 = arith.constant 49 : i32
%155 = arith.extsi %149 : i8 to i32
%154 = arith.cmpi slt, %155, %153 : i32
cf.cond_br %154, ^bb24, ^bb25
^bb24:
%156 = llvm.load %138 : !llvm.ptr -> i32
llvm.store %156, %135 : i32, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%157 = llvm.load %138 : !llvm.ptr -> i32
%158 = arith.constant 1 : i32
%159 = arith.addi %157, %158 : i32
llvm.store %159, %138 : i32, !llvm.ptr
cf.br ^bb18
^bb20:
%160 = arith.constant 0 : i32
%161 = arith.constant 0 : i32
%162 = arith.extsi %161 : i32 to i64
%163 = llvm.getelementptr %arg1[%162] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %160, %163 : i32, !llvm.ptr
%164 = llvm.load %135 : !llvm.ptr -> i32
%165 = arith.constant 1 : i32
%167 = arith.constant 0 : i32
%166 = arith.subi %167, %165 : i32
%168 = arith.cmpi sgt, %164, %166 : i32
cf.cond_br %168, ^bb27, ^bb28
^bb27:
%169 = arith.constant 0 : i32
%170 = llvm.mlir.constant(1 : i64) : i64
%171 = llvm.alloca %170 x i32 : (i64) -> !llvm.ptr
llvm.store %169, %171 : i32, !llvm.ptr
%172 = llvm.load %135 : !llvm.ptr -> i32
%173 = arith.constant 1 : i32
%174 = arith.subi %172, %173 : i32
%175 = llvm.mlir.constant(1 : i64) : i64
%176 = llvm.alloca %175 x i32 : (i64) -> !llvm.ptr
llvm.store %174, %176 : i32, !llvm.ptr
cf.br ^bb30
^bb30:
%177 = llvm.load %176 : !llvm.ptr -> i32
%178 = arith.constant 0 : i32
%179 = arith.cmpi sge, %177, %178 : i32
cf.cond_br %179, ^bb31, ^bb32
^bb31:
%181 = llvm.load %176 : !llvm.ptr -> i32
%182 = arith.extsi %181 : i32 to i64
%183 = llvm.getelementptr %56[%182] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%180 = llvm.load %183 : !llvm.ptr -> i8
%184 = arith.constant 49 : i32
%186 = arith.extsi %180 : i8 to i32
%185 = arith.cmpi slt, %186, %184 : i32
cf.cond_br %185, ^bb33, ^bb34
^bb33:
%187 = llvm.load %171 : !llvm.ptr -> i32
%188 = arith.constant 1 : i32
%189 = arith.addi %187, %188 : i32
llvm.store %189, %171 : i32, !llvm.ptr
cf.br ^bb35
^bb34:
%190 = llvm.load %171 : !llvm.ptr -> i32
%192 = arith.constant 0 : i32
%193 = arith.extsi %192 : i32 to i64
%194 = llvm.getelementptr %arg1[%193] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%191 = llvm.load %194 : !llvm.ptr -> i32
%195 = arith.extsi %191 : i32 to i64
%196 = llvm.getelementptr %arg2[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %190, %196 : i32, !llvm.ptr
%198 = arith.constant 0 : i32
%199 = arith.extsi %198 : i32 to i64
%200 = llvm.getelementptr %arg1[%199] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%197 = llvm.load %200 : !llvm.ptr -> i32
%201 = arith.constant 1 : i32
%202 = arith.addi %197, %201 : i32
%203 = arith.constant 0 : i32
%204 = arith.extsi %203 : i32 to i64
%205 = llvm.getelementptr %arg1[%204] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %202, %205 : i32, !llvm.ptr
cf.br ^bb35
^bb35:
%206 = llvm.load %176 : !llvm.ptr -> i32
%207 = arith.constant 1 : i32
%208 = arith.subi %206, %207 : i32
llvm.store %208, %176 : i32, !llvm.ptr
cf.br ^bb30
^bb32:
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%209 = arith.constant 0 : i32
%210 = llvm.mlir.constant(1 : i64) : i64
%211 = llvm.alloca %210 x i32 : (i64) -> !llvm.ptr
llvm.store %209, %211 : i32, !llvm.ptr
%212 = arith.constant 0 : i32
%213 = llvm.mlir.constant(1 : i64) : i64
%214 = llvm.alloca %213 x i32 : (i64) -> !llvm.ptr
llvm.store %212, %214 : i32, !llvm.ptr
cf.br ^bb36
^bb36:
%215 = llvm.load %214 : !llvm.ptr -> i32
%216 = llvm.load %63 : !llvm.ptr -> i32
%217 = arith.cmpi slt, %215, %216 : i32
cf.cond_br %217, ^bb37, ^bb38
^bb37:
%219 = llvm.load %214 : !llvm.ptr -> i32
%220 = arith.extsi %219 : i32 to i64
%221 = llvm.getelementptr %56[%220] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%218 = llvm.load %221 : !llvm.ptr -> i8
%222 = arith.constant 50 : i32
%224 = arith.extsi %218 : i8 to i32
%223 = arith.cmpi eq, %224, %222 : i32
cf.cond_br %223, ^bb39, ^bb40
^bb39:
%225 = llvm.load %211 : !llvm.ptr -> i32
%226 = arith.constant 1 : i32
%227 = arith.addi %225, %226 : i32
llvm.store %227, %211 : i32, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%228 = llvm.load %214 : !llvm.ptr -> i32
%229 = arith.constant 1 : i32
%230 = arith.addi %228, %229 : i32
llvm.store %230, %214 : i32, !llvm.ptr
cf.br ^bb36
^bb38:
%231 = llvm.load %211 : !llvm.ptr -> i32
%232 = arith.constant 1 : i32
%233 = arith.andi %231, %232 : i32
%234 = arith.constant 0 : i32
%235 = arith.extsi %234 : i32 to i64
%236 = llvm.getelementptr %arg3[%235] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %233, %236 : i32, !llvm.ptr
%238 = arith.constant 32 : i32
%239 = arith.constant 1 : i32
%240 = arith.extsi %238 : i32 to i64
%241 = arith.extsi %239 : i32 to i64
%237 = func.call @calloc(%240, %241) : (i64, i64) -> !llvm.ptr
%242 = arith.constant 0 : i32
%243 = llvm.mlir.constant(1 : i64) : i64
%244 = llvm.alloca %243 x i32 : (i64) -> !llvm.ptr
llvm.store %242, %244 : i32, !llvm.ptr
%245 = arith.constant 0 : i32
%246 = llvm.mlir.constant(1 : i64) : i64
%247 = llvm.alloca %246 x i32 : (i64) -> !llvm.ptr
llvm.store %245, %247 : i32, !llvm.ptr
cf.br ^bb42
^bb42:
%248 = llvm.load %247 : !llvm.ptr -> i32
%249 = llvm.load %63 : !llvm.ptr -> i32
%250 = arith.cmpi slt, %248, %249 : i32
cf.cond_br %250, ^bb43, ^bb44
^bb43:
%252 = llvm.load %247 : !llvm.ptr -> i32
%253 = arith.extsi %252 : i32 to i64
%254 = llvm.getelementptr %56[%253] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%251 = llvm.load %254 : !llvm.ptr -> i8
%255 = arith.constant 50 : i32
%257 = arith.extsi %251 : i8 to i32
%256 = arith.cmpi slt, %257, %255 : i32
cf.cond_br %256, ^bb45, ^bb46
^bb45:
%259 = llvm.load %247 : !llvm.ptr -> i32
%260 = arith.extsi %259 : i32 to i64
%261 = llvm.getelementptr %56[%260] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%258 = llvm.load %261 : !llvm.ptr -> i8
%262 = llvm.load %244 : !llvm.ptr -> i32
%263 = arith.extsi %262 : i32 to i64
%264 = llvm.getelementptr %237[%263] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %258, %264 : i8, !llvm.ptr
%265 = llvm.load %244 : !llvm.ptr -> i32
%266 = arith.constant 1 : i32
%267 = arith.addi %265, %266 : i32
llvm.store %267, %244 : i32, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%268 = llvm.load %247 : !llvm.ptr -> i32
%269 = arith.constant 1 : i32
%270 = arith.addi %268, %269 : i32
llvm.store %270, %247 : i32, !llvm.ptr
cf.br ^bb42
^bb44:
%271 = llvm.load %244 : !llvm.ptr -> i32
%272 = arith.constant 0 : i32
%273 = arith.cmpi eq, %271, %272 : i32
cf.cond_br %273, ^bb48, ^bb49
^bb48:
%274 = arith.constant 0.0 : f32
%275 = arith.constant 0 : i32
%276 = arith.extf %274 : f32 to f64
%277 = arith.extsi %275 : i32 to i64
%278 = llvm.getelementptr %arg4[%277] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %276, %278 : f64, !llvm.ptr
cf.br ^bb50
^bb49:
%279 = arith.constant 0 : i32
%280 = arith.extsi %279 : i32 to i64
%281 = llvm.mlir.constant(1 : i64) : i64
%282 = llvm.alloca %281 x i64 : (i64) -> !llvm.ptr
llvm.store %280, %282 : i64, !llvm.ptr
%283 = arith.constant 0 : i32
%284 = llvm.mlir.constant(1 : i64) : i64
%285 = llvm.alloca %284 x i32 : (i64) -> !llvm.ptr
llvm.store %283, %285 : i32, !llvm.ptr
cf.br ^bb51
^bb51:
%286 = llvm.load %285 : !llvm.ptr -> i32
%287 = llvm.load %244 : !llvm.ptr -> i32
%288 = arith.cmpi slt, %286, %287 : i32
cf.cond_br %288, ^bb52, ^bb53
^bb52:
%289 = llvm.load %282 : !llvm.ptr -> i64
%290 = arith.constant 2 : i32
%292 = arith.extsi %290 : i32 to i64
%291 = arith.muli %289, %292 : i64
%294 = llvm.load %285 : !llvm.ptr -> i32
%295 = arith.extsi %294 : i32 to i64
%296 = llvm.getelementptr %237[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%293 = llvm.load %296 : !llvm.ptr -> i8
%297 = arith.constant 48 : i32
%299 = arith.extsi %293 : i8 to i32
%298 = arith.subi %299, %297 : i32
%300 = arith.extsi %298 : i32 to i64
%301 = arith.addi %291, %300 : i64
llvm.store %301, %282 : i64, !llvm.ptr
%302 = llvm.load %285 : !llvm.ptr -> i32
%303 = arith.constant 1 : i32
%304 = arith.addi %302, %303 : i32
llvm.store %304, %285 : i32, !llvm.ptr
cf.br ^bb51
^bb53:
%306 = llvm.mlir.addressof @g_B : !llvm.ptr
%307 = llvm.load %306 : !llvm.ptr -> !llvm.ptr
%308 = llvm.load %282 : !llvm.ptr -> i64
%309 = llvm.getelementptr %307[%308] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%305 = llvm.load %309 : !llvm.ptr -> f64
%310 = arith.constant 0 : i32
%311 = arith.extsi %310 : i32 to i64
%312 = llvm.getelementptr %arg4[%311] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %305, %312 : f64, !llvm.ptr
cf.br ^bb50
^bb50:
%314 = arith.constant 0 : i32
%315 = arith.extsi %314 : i32 to i64
%316 = llvm.getelementptr %arg1[%315] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%313 = llvm.load %316 : !llvm.ptr -> i32
%317 = llvm.mlir.constant(1 : i64) : i64
%318 = llvm.alloca %317 x i32 : (i64) -> !llvm.ptr
llvm.store %313, %318 : i32, !llvm.ptr
cf.br ^bb54
^bb54:
%319 = llvm.load %318 : !llvm.ptr -> i32
%320 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%321 = llvm.load %320 : !llvm.ptr -> i32
%322 = arith.cmpi slt, %319, %321 : i32
cf.cond_br %322, ^bb55, ^bb56
^bb55:
%323 = arith.constant 0 : i32
%324 = llvm.load %318 : !llvm.ptr -> i32
%325 = arith.extsi %324 : i32 to i64
%326 = llvm.getelementptr %arg2[%325] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %323, %326 : i32, !llvm.ptr
%327 = llvm.load %318 : !llvm.ptr -> i32
%328 = arith.constant 1 : i32
%329 = arith.addi %327, %328 : i32
llvm.store %329, %318 : i32, !llvm.ptr
cf.br ^bb54
^bb56:
func.call @free(%56) : (!llvm.ptr) -> ()
func.call @free(%237) : (!llvm.ptr) -> ()
func.return
}
func.func @cmp_key(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: i64, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: !llvm.ptr, %arg9: i64) -> i32 {
%333 = llvm.getelementptr %arg0[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%332 = llvm.load %333 : !llvm.ptr -> i32
%335 = llvm.getelementptr %arg5[%arg9] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%334 = llvm.load %335 : !llvm.ptr -> i32
%336 = arith.cmpi ne, %332, %334 : i32
cf.cond_br %336, ^bb57, ^bb58
^bb57:
%337 = arith.cmpi slt, %332, %334 : i32
cf.cond_br %337, ^bb60, ^bb61
^bb60:
%338 = arith.constant 1 : i32
%340 = arith.constant 0 : i32
%339 = arith.subi %340, %338 : i32
func.return %339 : i32
^bb61:
cf.br ^bb62
^bb62:
%341 = arith.constant 1 : i32
func.return %341 : i32
^bb58:
cf.br ^bb59
^bb59:
%342 = arith.constant 0 : i32
%343 = llvm.mlir.constant(1 : i64) : i64
%344 = llvm.alloca %343 x i32 : (i64) -> !llvm.ptr
llvm.store %342, %344 : i32, !llvm.ptr
cf.br ^bb63
^bb63:
%345 = llvm.load %344 : !llvm.ptr -> i32
%346 = arith.cmpi slt, %345, %332 : i32
cf.cond_br %346, ^bb64, ^bb65
^bb64:
%348 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%349 = llvm.load %348 : !llvm.ptr -> i32
%350 = arith.extsi %349 : i32 to i64
%351 = arith.muli %arg4, %350 : i64
%352 = llvm.load %344 : !llvm.ptr -> i32
%354 = arith.extsi %352 : i32 to i64
%353 = arith.addi %351, %354 : i64
%355 = llvm.getelementptr %arg1[%353] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%347 = llvm.load %355 : !llvm.ptr -> i32
%357 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%358 = llvm.load %357 : !llvm.ptr -> i32
%359 = arith.extsi %358 : i32 to i64
%360 = arith.muli %arg9, %359 : i64
%361 = llvm.load %344 : !llvm.ptr -> i32
%363 = arith.extsi %361 : i32 to i64
%362 = arith.addi %360, %363 : i64
%364 = llvm.getelementptr %arg6[%362] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%356 = llvm.load %364 : !llvm.ptr -> i32
%365 = arith.cmpi ne, %347, %356 : i32
cf.cond_br %365, ^bb66, ^bb67
^bb66:
%366 = arith.cmpi slt, %347, %356 : i32
cf.cond_br %366, ^bb69, ^bb70
^bb69:
%367 = arith.constant 1 : i32
%369 = arith.constant 0 : i32
%368 = arith.subi %369, %367 : i32
func.return %368 : i32
^bb70:
cf.br ^bb71
^bb71:
%370 = arith.constant 1 : i32
func.return %370 : i32
^bb67:
cf.br ^bb68
^bb68:
%371 = llvm.load %344 : !llvm.ptr -> i32
%372 = arith.constant 1 : i32
%373 = arith.addi %371, %372 : i32
llvm.store %373, %344 : i32, !llvm.ptr
cf.br ^bb63
^bb65:
%375 = llvm.getelementptr %arg2[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%374 = llvm.load %375 : !llvm.ptr -> i32
%377 = llvm.getelementptr %arg7[%arg9] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%376 = llvm.load %377 : !llvm.ptr -> i32
%378 = arith.cmpi ne, %374, %376 : i32
cf.cond_br %378, ^bb72, ^bb73
^bb72:
%379 = arith.cmpi slt, %374, %376 : i32
cf.cond_br %379, ^bb75, ^bb76
^bb75:
%380 = arith.constant 1 : i32
%382 = arith.constant 0 : i32
%381 = arith.subi %382, %380 : i32
func.return %381 : i32
^bb76:
cf.br ^bb77
^bb77:
%383 = arith.constant 1 : i32
func.return %383 : i32
^bb73:
cf.br ^bb74
^bb74:
%385 = llvm.getelementptr %arg3[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%384 = llvm.load %385 : !llvm.ptr -> f64
%387 = llvm.getelementptr %arg8[%arg9] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%386 = llvm.load %387 : !llvm.ptr -> f64
%388 = arith.cmpf olt, %384, %386 : f64
cf.cond_br %388, ^bb78, ^bb79
^bb78:
%389 = arith.constant 1 : i32
%391 = arith.constant 0 : i32
%390 = arith.subi %391, %389 : i32
func.return %390 : i32
^bb79:
cf.br ^bb80
^bb80:
%392 = arith.cmpf ogt, %384, %386 : f64
cf.cond_br %392, ^bb81, ^bb82
^bb81:
%393 = arith.constant 1 : i32
func.return %393 : i32
^bb82:
cf.br ^bb83
^bb83:
%394 = arith.constant 0 : i32
func.return %394 : i32
}
func.func @merge_sort(%arg0: !llvm.ptr, %arg1: i32, %arg2: i32, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr) -> () {
%395 = arith.subi %arg2, %arg1 : i32
%396 = arith.constant 1 : i32
%397 = arith.cmpi sle, %395, %396 : i32
cf.cond_br %397, ^bb84, ^bb85
^bb84:
func.return
^bb85:
cf.br ^bb86
^bb86:
%398 = arith.addi %arg1, %arg2 : i32
%399 = arith.constant 2 : i32
%400 = arith.divsi %398, %399 : i32
func.call @merge_sort(%arg0, %arg1, %400, %arg3, %arg4, %arg5, %arg6, %arg7) : (!llvm.ptr, i32, i32, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @merge_sort(%arg0, %400, %arg2, %arg3, %arg4, %arg5, %arg6, %arg7) : (!llvm.ptr, i32, i32, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%403 = llvm.mlir.constant(1 : i64) : i64
%404 = llvm.alloca %403 x i32 : (i64) -> !llvm.ptr
llvm.store %arg1, %404 : i32, !llvm.ptr
%405 = llvm.mlir.constant(1 : i64) : i64
%406 = llvm.alloca %405 x i32 : (i64) -> !llvm.ptr
llvm.store %400, %406 : i32, !llvm.ptr
%407 = llvm.mlir.constant(1 : i64) : i64
%408 = llvm.alloca %407 x i32 : (i64) -> !llvm.ptr
llvm.store %arg1, %408 : i32, !llvm.ptr
cf.br ^bb87
^bb87:
%409 = llvm.load %404 : !llvm.ptr -> i32
%410 = arith.cmpi slt, %409, %400 : i32
%411 = scf.if %410 -> (i1) {
%412 = llvm.load %406 : !llvm.ptr -> i32
%413 = arith.cmpi slt, %412, %arg2 : i32
scf.yield %413 : i1
} else {
%414 = arith.constant false
scf.yield %414 : i1
}
cf.cond_br %411, ^bb88, ^bb89
^bb88:
%417 = llvm.load %404 : !llvm.ptr -> i32
%418 = arith.extsi %417 : i32 to i64
%419 = llvm.getelementptr %arg0[%418] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%416 = llvm.load %419 : !llvm.ptr -> i64
%421 = llvm.load %406 : !llvm.ptr -> i32
%422 = arith.extsi %421 : i32 to i64
%423 = llvm.getelementptr %arg0[%422] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%420 = llvm.load %423 : !llvm.ptr -> i64
%415 = func.call @cmp_key(%arg3, %arg4, %arg5, %arg6, %416, %arg3, %arg4, %arg5, %arg6, %420) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> i32
%424 = arith.constant 0 : i32
%425 = arith.cmpi sle, %415, %424 : i32
cf.cond_br %425, ^bb90, ^bb91
^bb90:
%427 = llvm.load %404 : !llvm.ptr -> i32
%428 = arith.extsi %427 : i32 to i64
%429 = llvm.getelementptr %arg0[%428] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%426 = llvm.load %429 : !llvm.ptr -> i64
%430 = llvm.load %408 : !llvm.ptr -> i32
%431 = arith.extsi %430 : i32 to i64
%432 = llvm.getelementptr %arg7[%431] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %426, %432 : i64, !llvm.ptr
%433 = llvm.load %404 : !llvm.ptr -> i32
%434 = arith.constant 1 : i32
%435 = arith.addi %433, %434 : i32
llvm.store %435, %404 : i32, !llvm.ptr
cf.br ^bb92
^bb91:
%437 = llvm.load %406 : !llvm.ptr -> i32
%438 = arith.extsi %437 : i32 to i64
%439 = llvm.getelementptr %arg0[%438] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%436 = llvm.load %439 : !llvm.ptr -> i64
%440 = llvm.load %408 : !llvm.ptr -> i32
%441 = arith.extsi %440 : i32 to i64
%442 = llvm.getelementptr %arg7[%441] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %436, %442 : i64, !llvm.ptr
%443 = llvm.load %406 : !llvm.ptr -> i32
%444 = arith.constant 1 : i32
%445 = arith.addi %443, %444 : i32
llvm.store %445, %406 : i32, !llvm.ptr
cf.br ^bb92
^bb92:
%446 = llvm.load %408 : !llvm.ptr -> i32
%447 = arith.constant 1 : i32
%448 = arith.addi %446, %447 : i32
llvm.store %448, %408 : i32, !llvm.ptr
cf.br ^bb87
^bb89:
cf.br ^bb93
^bb93:
%449 = llvm.load %404 : !llvm.ptr -> i32
%450 = arith.cmpi slt, %449, %400 : i32
cf.cond_br %450, ^bb94, ^bb95
^bb94:
%452 = llvm.load %404 : !llvm.ptr -> i32
%453 = arith.extsi %452 : i32 to i64
%454 = llvm.getelementptr %arg0[%453] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%451 = llvm.load %454 : !llvm.ptr -> i64
%455 = llvm.load %408 : !llvm.ptr -> i32
%456 = arith.extsi %455 : i32 to i64
%457 = llvm.getelementptr %arg7[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %451, %457 : i64, !llvm.ptr
%458 = llvm.load %404 : !llvm.ptr -> i32
%459 = arith.constant 1 : i32
%460 = arith.addi %458, %459 : i32
llvm.store %460, %404 : i32, !llvm.ptr
%461 = llvm.load %408 : !llvm.ptr -> i32
%462 = arith.constant 1 : i32
%463 = arith.addi %461, %462 : i32
llvm.store %463, %408 : i32, !llvm.ptr
cf.br ^bb93
^bb95:
cf.br ^bb96
^bb96:
%464 = llvm.load %406 : !llvm.ptr -> i32
%465 = arith.cmpi slt, %464, %arg2 : i32
cf.cond_br %465, ^bb97, ^bb98
^bb97:
%467 = llvm.load %406 : !llvm.ptr -> i32
%468 = arith.extsi %467 : i32 to i64
%469 = llvm.getelementptr %arg0[%468] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%466 = llvm.load %469 : !llvm.ptr -> i64
%470 = llvm.load %408 : !llvm.ptr -> i32
%471 = arith.extsi %470 : i32 to i64
%472 = llvm.getelementptr %arg7[%471] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %466, %472 : i64, !llvm.ptr
%473 = llvm.load %406 : !llvm.ptr -> i32
%474 = arith.constant 1 : i32
%475 = arith.addi %473, %474 : i32
llvm.store %475, %406 : i32, !llvm.ptr
%476 = llvm.load %408 : !llvm.ptr -> i32
%477 = arith.constant 1 : i32
%478 = arith.addi %476, %477 : i32
llvm.store %478, %408 : i32, !llvm.ptr
cf.br ^bb96
^bb98:
%479 = llvm.mlir.constant(1 : i64) : i64
%480 = llvm.alloca %479 x i32 : (i64) -> !llvm.ptr
llvm.store %arg1, %480 : i32, !llvm.ptr
cf.br ^bb99
^bb99:
%481 = llvm.load %480 : !llvm.ptr -> i32
%482 = arith.cmpi slt, %481, %arg2 : i32
cf.cond_br %482, ^bb100, ^bb101
^bb100:
%484 = llvm.load %480 : !llvm.ptr -> i32
%485 = arith.extsi %484 : i32 to i64
%486 = llvm.getelementptr %arg7[%485] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%483 = llvm.load %486 : !llvm.ptr -> i64
%487 = llvm.load %480 : !llvm.ptr -> i32
%488 = arith.extsi %487 : i32 to i64
%489 = llvm.getelementptr %arg0[%488] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %483, %489 : i64, !llvm.ptr
%490 = llvm.load %480 : !llvm.ptr -> i32
%491 = arith.constant 1 : i32
%492 = arith.addi %490, %491 : i32
llvm.store %492, %480 : i32, !llvm.ptr
cf.br ^bb99
^bb101:
func.return
}
func.func @keys_equal(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: i64, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: !llvm.ptr, %arg9: i64) -> i32 {
%494 = llvm.getelementptr %arg0[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%493 = llvm.load %494 : !llvm.ptr -> i32
%496 = llvm.getelementptr %arg5[%arg9] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%495 = llvm.load %496 : !llvm.ptr -> i32
%497 = arith.cmpi ne, %493, %495 : i32
cf.cond_br %497, ^bb102, ^bb103
^bb102:
%498 = arith.constant 0 : i32
func.return %498 : i32
^bb103:
cf.br ^bb104
^bb104:
%500 = llvm.getelementptr %arg0[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%499 = llvm.load %500 : !llvm.ptr -> i32
%501 = arith.constant 0 : i32
%502 = llvm.mlir.constant(1 : i64) : i64
%503 = llvm.alloca %502 x i32 : (i64) -> !llvm.ptr
llvm.store %501, %503 : i32, !llvm.ptr
cf.br ^bb105
^bb105:
%504 = llvm.load %503 : !llvm.ptr -> i32
%505 = arith.cmpi slt, %504, %499 : i32
cf.cond_br %505, ^bb106, ^bb107
^bb106:
%507 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%508 = llvm.load %507 : !llvm.ptr -> i32
%509 = arith.extsi %508 : i32 to i64
%510 = arith.muli %arg4, %509 : i64
%511 = llvm.load %503 : !llvm.ptr -> i32
%513 = arith.extsi %511 : i32 to i64
%512 = arith.addi %510, %513 : i64
%514 = llvm.getelementptr %arg1[%512] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%506 = llvm.load %514 : !llvm.ptr -> i32
%516 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%517 = llvm.load %516 : !llvm.ptr -> i32
%518 = arith.extsi %517 : i32 to i64
%519 = arith.muli %arg9, %518 : i64
%520 = llvm.load %503 : !llvm.ptr -> i32
%522 = arith.extsi %520 : i32 to i64
%521 = arith.addi %519, %522 : i64
%523 = llvm.getelementptr %arg6[%521] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%515 = llvm.load %523 : !llvm.ptr -> i32
%524 = arith.cmpi ne, %506, %515 : i32
cf.cond_br %524, ^bb108, ^bb109
^bb108:
%525 = arith.constant 0 : i32
func.return %525 : i32
^bb109:
cf.br ^bb110
^bb110:
%526 = llvm.load %503 : !llvm.ptr -> i32
%527 = arith.constant 1 : i32
%528 = arith.addi %526, %527 : i32
llvm.store %528, %503 : i32, !llvm.ptr
cf.br ^bb105
^bb107:
%530 = llvm.getelementptr %arg2[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%529 = llvm.load %530 : !llvm.ptr -> i32
%532 = llvm.getelementptr %arg7[%arg9] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%531 = llvm.load %532 : !llvm.ptr -> i32
%533 = arith.cmpi ne, %529, %531 : i32
cf.cond_br %533, ^bb111, ^bb112
^bb111:
%534 = arith.constant 0 : i32
func.return %534 : i32
^bb112:
cf.br ^bb113
^bb113:
%536 = llvm.getelementptr %arg3[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%535 = llvm.load %536 : !llvm.ptr -> f64
%538 = llvm.getelementptr %arg8[%arg9] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%537 = llvm.load %538 : !llvm.ptr -> f64
%539 = arith.cmpf oeq, %535, %537 : f64
%540 = scf.if %539 -> (i32) {
%541 = arith.constant 1 : i32
scf.yield %541 : i32
} else {
%542 = arith.constant 0 : i32
scf.yield %542 : i32
}
func.return %540 : i32
}
func.func @combine_key(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: i64, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: !llvm.ptr, %arg9: i64, %arg10: !llvm.ptr, %arg11: !llvm.ptr, %arg12: !llvm.ptr, %arg13: !llvm.ptr) -> () {
%544 = llvm.getelementptr %arg0[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%543 = llvm.load %544 : !llvm.ptr -> i32
%546 = llvm.getelementptr %arg5[%arg9] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%545 = llvm.load %546 : !llvm.ptr -> i32
%547 = arith.addi %543, %545 : i32
%548 = arith.constant 0 : i32
%549 = arith.extsi %548 : i32 to i64
%550 = llvm.getelementptr %arg10[%549] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %547, %550 : i32, !llvm.ptr
%551 = arith.constant 0 : i32
%552 = llvm.mlir.constant(1 : i64) : i64
%553 = llvm.alloca %552 x i32 : (i64) -> !llvm.ptr
llvm.store %551, %553 : i32, !llvm.ptr
%554 = arith.constant 0 : i32
%555 = llvm.mlir.constant(1 : i64) : i64
%556 = llvm.alloca %555 x i32 : (i64) -> !llvm.ptr
llvm.store %554, %556 : i32, !llvm.ptr
cf.br ^bb114
^bb114:
%557 = llvm.load %556 : !llvm.ptr -> i32
%558 = arith.cmpi slt, %557, %543 : i32
cf.cond_br %558, ^bb115, ^bb116
^bb115:
%560 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%561 = llvm.load %560 : !llvm.ptr -> i32
%562 = arith.extsi %561 : i32 to i64
%563 = arith.muli %arg4, %562 : i64
%564 = llvm.load %556 : !llvm.ptr -> i32
%566 = arith.extsi %564 : i32 to i64
%565 = arith.addi %563, %566 : i64
%567 = llvm.getelementptr %arg1[%565] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%559 = llvm.load %567 : !llvm.ptr -> i32
%568 = llvm.load %553 : !llvm.ptr -> i32
%569 = arith.extsi %568 : i32 to i64
%570 = llvm.getelementptr %arg11[%569] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %559, %570 : i32, !llvm.ptr
%571 = llvm.load %553 : !llvm.ptr -> i32
%572 = arith.constant 1 : i32
%573 = arith.addi %571, %572 : i32
llvm.store %573, %553 : i32, !llvm.ptr
%574 = llvm.load %556 : !llvm.ptr -> i32
%575 = arith.constant 1 : i32
%576 = arith.addi %574, %575 : i32
llvm.store %576, %556 : i32, !llvm.ptr
cf.br ^bb114
^bb116:
%577 = arith.constant 0 : i32
%578 = llvm.mlir.constant(1 : i64) : i64
%579 = llvm.alloca %578 x i32 : (i64) -> !llvm.ptr
llvm.store %577, %579 : i32, !llvm.ptr
cf.br ^bb117
^bb117:
%580 = llvm.load %579 : !llvm.ptr -> i32
%581 = arith.cmpi slt, %580, %545 : i32
cf.cond_br %581, ^bb118, ^bb119
^bb118:
%583 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%584 = llvm.load %583 : !llvm.ptr -> i32
%585 = arith.extsi %584 : i32 to i64
%586 = arith.muli %arg9, %585 : i64
%587 = llvm.load %579 : !llvm.ptr -> i32
%589 = arith.extsi %587 : i32 to i64
%588 = arith.addi %586, %589 : i64
%590 = llvm.getelementptr %arg6[%588] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%582 = llvm.load %590 : !llvm.ptr -> i32
%591 = llvm.load %553 : !llvm.ptr -> i32
%592 = arith.extsi %591 : i32 to i64
%593 = llvm.getelementptr %arg11[%592] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %582, %593 : i32, !llvm.ptr
%594 = llvm.load %553 : !llvm.ptr -> i32
%595 = arith.constant 1 : i32
%596 = arith.addi %594, %595 : i32
llvm.store %596, %553 : i32, !llvm.ptr
%597 = llvm.load %579 : !llvm.ptr -> i32
%598 = arith.constant 1 : i32
%599 = arith.addi %597, %598 : i32
llvm.store %599, %579 : i32, !llvm.ptr
cf.br ^bb117
^bb119:
%600 = arith.constant 0 : i32
%601 = llvm.mlir.constant(1 : i64) : i64
%602 = llvm.alloca %601 x i32 : (i64) -> !llvm.ptr
llvm.store %600, %602 : i32, !llvm.ptr
cf.br ^bb120
^bb120:
%603 = llvm.load %602 : !llvm.ptr -> i32
%605 = arith.constant 0 : i32
%606 = arith.extsi %605 : i32 to i64
%607 = llvm.getelementptr %arg10[%606] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%604 = llvm.load %607 : !llvm.ptr -> i32
%608 = arith.cmpi slt, %603, %604 : i32
cf.cond_br %608, ^bb121, ^bb122
^bb121:
%609 = llvm.load %602 : !llvm.ptr -> i32
%610 = arith.constant 1 : i32
%611 = arith.addi %609, %610 : i32
%612 = llvm.mlir.constant(1 : i64) : i64
%613 = llvm.alloca %612 x i32 : (i64) -> !llvm.ptr
llvm.store %611, %613 : i32, !llvm.ptr
cf.br ^bb123
^bb123:
%614 = llvm.load %613 : !llvm.ptr -> i32
%616 = arith.constant 0 : i32
%617 = arith.extsi %616 : i32 to i64
%618 = llvm.getelementptr %arg10[%617] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%615 = llvm.load %618 : !llvm.ptr -> i32
%619 = arith.cmpi slt, %614, %615 : i32
cf.cond_br %619, ^bb124, ^bb125
^bb124:
%621 = llvm.load %602 : !llvm.ptr -> i32
%622 = arith.extsi %621 : i32 to i64
%623 = llvm.getelementptr %arg11[%622] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%620 = llvm.load %623 : !llvm.ptr -> i32
%625 = llvm.load %613 : !llvm.ptr -> i32
%626 = arith.extsi %625 : i32 to i64
%627 = llvm.getelementptr %arg11[%626] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%624 = llvm.load %627 : !llvm.ptr -> i32
%628 = arith.cmpi sgt, %620, %624 : i32
cf.cond_br %628, ^bb126, ^bb127
^bb126:
%630 = llvm.load %602 : !llvm.ptr -> i32
%631 = arith.extsi %630 : i32 to i64
%632 = llvm.getelementptr %arg11[%631] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%629 = llvm.load %632 : !llvm.ptr -> i32
%634 = llvm.load %613 : !llvm.ptr -> i32
%635 = arith.extsi %634 : i32 to i64
%636 = llvm.getelementptr %arg11[%635] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%633 = llvm.load %636 : !llvm.ptr -> i32
%637 = llvm.load %602 : !llvm.ptr -> i32
%638 = arith.extsi %637 : i32 to i64
%639 = llvm.getelementptr %arg11[%638] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %633, %639 : i32, !llvm.ptr
%640 = llvm.load %613 : !llvm.ptr -> i32
%641 = arith.extsi %640 : i32 to i64
%642 = llvm.getelementptr %arg11[%641] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %629, %642 : i32, !llvm.ptr
cf.br ^bb128
^bb127:
cf.br ^bb128
^bb128:
%643 = llvm.load %613 : !llvm.ptr -> i32
%644 = arith.constant 1 : i32
%645 = arith.addi %643, %644 : i32
llvm.store %645, %613 : i32, !llvm.ptr
cf.br ^bb123
^bb125:
%646 = llvm.load %602 : !llvm.ptr -> i32
%647 = arith.constant 1 : i32
%648 = arith.addi %646, %647 : i32
llvm.store %648, %602 : i32, !llvm.ptr
cf.br ^bb120
^bb122:
%650 = llvm.getelementptr %arg2[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%649 = llvm.load %650 : !llvm.ptr -> i32
%652 = llvm.getelementptr %arg7[%arg9] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%651 = llvm.load %652 : !llvm.ptr -> i32
%653 = arith.xori %649, %651 : i32
%654 = arith.constant 0 : i32
%655 = arith.extsi %654 : i32 to i64
%656 = llvm.getelementptr %arg12[%655] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %653, %656 : i32, !llvm.ptr
%658 = llvm.getelementptr %arg3[%arg4] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%657 = llvm.load %658 : !llvm.ptr -> f64
%660 = llvm.getelementptr %arg8[%arg9] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%659 = llvm.load %660 : !llvm.ptr -> f64
%661 = arith.addf %657, %659 : f64
%662 = arith.constant 0 : i32
%663 = arith.extsi %662 : i32 to i64
%664 = llvm.getelementptr %arg13[%663] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %661, %664 : f64, !llvm.ptr
%666 = arith.constant 0 : i32
%667 = arith.extsi %666 : i32 to i64
%668 = llvm.getelementptr %arg10[%667] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%665 = llvm.load %668 : !llvm.ptr -> i32
%669 = llvm.mlir.constant(1 : i64) : i64
%670 = llvm.alloca %669 x i32 : (i64) -> !llvm.ptr
llvm.store %665, %670 : i32, !llvm.ptr
cf.br ^bb129
^bb129:
%671 = llvm.load %670 : !llvm.ptr -> i32
%672 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%673 = llvm.load %672 : !llvm.ptr -> i32
%674 = arith.cmpi slt, %671, %673 : i32
cf.cond_br %674, ^bb130, ^bb131
^bb130:
%675 = arith.constant 0 : i32
%676 = llvm.load %670 : !llvm.ptr -> i32
%677 = arith.extsi %676 : i32 to i64
%678 = llvm.getelementptr %arg11[%677] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %675, %678 : i32, !llvm.ptr
%679 = llvm.load %670 : !llvm.ptr -> i32
%680 = arith.constant 1 : i32
%681 = arith.addi %679, %680 : i32
llvm.store %681, %670 : i32, !llvm.ptr
cf.br ^bb129
^bb131:
func.return
}
func.func @main() -> i32 {
%682 = arith.constant 1 : i32
%684 = llvm.mlir.addressof @N : !llvm.ptr
%685 = llvm.load %684 : !llvm.ptr -> i64
%686 = arith.sitofp %685 : i64 to f64
%687 = math.log %686 : f64
%688 = arith.constant 3.0 : f32
%689 = math.log %688 : f32
%690 = arith.divf %687, %689 : f64
%683 = func.call @ceil(%690) : (f64) -> f64
%691 = arith.fptosi %683 : f64 to i32
%692 = arith.shli %682, %691 : i32
%693 = arith.constant 1 : i32
%694 = arith.cmpi slt, %692, %693 : i32
cf.cond_br %694, ^bb132, ^bb133
^bb132:
%696 = arith.constant 1 : i32
func.call @build_B(%696) : (i32) -> ()
cf.br ^bb134
^bb133:
func.call @build_B(%692) : (i32) -> ()
cf.br ^bb134
^bb134:
%699 = llvm.mlir.addressof @N : !llvm.ptr
%700 = llvm.load %699 : !llvm.ptr -> i64
%701 = arith.constant 4 : i32
%702 = arith.extsi %701 : i32 to i64
%698 = func.call @calloc(%700, %702) : (i64, i64) -> !llvm.ptr
%704 = llvm.mlir.addressof @N : !llvm.ptr
%705 = llvm.load %704 : !llvm.ptr -> i64
%706 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%707 = llvm.load %706 : !llvm.ptr -> i32
%708 = arith.extsi %707 : i32 to i64
%709 = arith.muli %705, %708 : i64
%710 = arith.constant 4 : i32
%711 = arith.extsi %710 : i32 to i64
%703 = func.call @calloc(%709, %711) : (i64, i64) -> !llvm.ptr
%713 = llvm.mlir.addressof @N : !llvm.ptr
%714 = llvm.load %713 : !llvm.ptr -> i64
%715 = arith.constant 4 : i32
%716 = arith.extsi %715 : i32 to i64
%712 = func.call @calloc(%714, %716) : (i64, i64) -> !llvm.ptr
%718 = llvm.mlir.addressof @N : !llvm.ptr
%719 = llvm.load %718 : !llvm.ptr -> i64
%720 = arith.constant 8 : i32
%721 = arith.extsi %720 : i32 to i64
%717 = func.call @calloc(%719, %721) : (i64, i64) -> !llvm.ptr
%722 = arith.constant 1 : i32
%723 = arith.extsi %722 : i32 to i64
%724 = llvm.mlir.constant(1 : i64) : i64
%725 = llvm.alloca %724 x i64 : (i64) -> !llvm.ptr
llvm.store %723, %725 : i64, !llvm.ptr
cf.br ^bb135
^bb135:
%726 = llvm.load %725 : !llvm.ptr -> i64
%727 = llvm.mlir.addressof @N : !llvm.ptr
%728 = llvm.load %727 : !llvm.ptr -> i64
%729 = arith.cmpi sle, %726, %728 : i64
cf.cond_br %729, ^bb136, ^bb137
^bb136:
%730 = llvm.load %725 : !llvm.ptr -> i64
%731 = arith.constant 1 : i32
%733 = arith.extsi %731 : i32 to i64
%732 = arith.subi %730, %733 : i64
%735 = llvm.load %725 : !llvm.ptr -> i64
# String concatenation: !llvm.ptr + i64
# String concatenation: !llvm.ptr + i64
# String concatenation: !llvm.ptr + i64
# String concatenation: !llvm.ptr + i64
func.call @compute_key(%735, %736, %737, %738, %739) : (i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%740 = llvm.load %725 : !llvm.ptr -> i64
%741 = arith.constant 1 : i32
%743 = arith.extsi %741 : i32 to i64
%742 = arith.addi %740, %743 : i64
llvm.store %742, %725 : i64, !llvm.ptr
cf.br ^bb135
^bb137:
%745 = llvm.mlir.addressof @N : !llvm.ptr
%746 = llvm.load %745 : !llvm.ptr -> i64
%747 = arith.constant 8 : i32
%748 = arith.extsi %747 : i32 to i64
%744 = func.call @calloc(%746, %748) : (i64, i64) -> !llvm.ptr
%750 = llvm.mlir.addressof @N : !llvm.ptr
%751 = llvm.load %750 : !llvm.ptr -> i64
%752 = arith.constant 8 : i32
%753 = arith.extsi %752 : i32 to i64
%749 = func.call @calloc(%751, %753) : (i64, i64) -> !llvm.ptr
%754 = arith.constant 0 : i32
%755 = arith.extsi %754 : i32 to i64
%756 = llvm.mlir.constant(1 : i64) : i64
%757 = llvm.alloca %756 x i64 : (i64) -> !llvm.ptr
llvm.store %755, %757 : i64, !llvm.ptr
cf.br ^bb138
^bb138:
%758 = llvm.load %757 : !llvm.ptr -> i64
%759 = llvm.mlir.addressof @N : !llvm.ptr
%760 = llvm.load %759 : !llvm.ptr -> i64
%761 = arith.cmpi slt, %758, %760 : i64
cf.cond_br %761, ^bb139, ^bb140
^bb139:
%762 = llvm.load %757 : !llvm.ptr -> i64
%763 = llvm.load %757 : !llvm.ptr -> i64
%764 = llvm.getelementptr %744[%763] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %762, %764 : i64, !llvm.ptr
%765 = llvm.load %757 : !llvm.ptr -> i64
%766 = arith.constant 1 : i32
%768 = arith.extsi %766 : i32 to i64
%767 = arith.addi %765, %768 : i64
llvm.store %767, %757 : i64, !llvm.ptr
cf.br ^bb138
^bb140:
%770 = arith.constant 0 : i32
%771 = llvm.mlir.addressof @N : !llvm.ptr
%772 = llvm.load %771 : !llvm.ptr -> i64
%773 = arith.trunci %772 : i64 to i32
func.call @merge_sort(%744, %770, %773, %698, %703, %712, %717, %749) : (!llvm.ptr, i32, i32, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%775 = llvm.mlir.addressof @N : !llvm.ptr
%776 = llvm.load %775 : !llvm.ptr -> i64
%777 = arith.constant 4 : i32
%778 = arith.extsi %777 : i32 to i64
%774 = func.call @calloc(%776, %778) : (i64, i64) -> !llvm.ptr
%780 = llvm.mlir.addressof @N : !llvm.ptr
%781 = llvm.load %780 : !llvm.ptr -> i64
%782 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%783 = llvm.load %782 : !llvm.ptr -> i32
%784 = arith.extsi %783 : i32 to i64
%785 = arith.muli %781, %784 : i64
%786 = arith.constant 4 : i32
%787 = arith.extsi %786 : i32 to i64
%779 = func.call @calloc(%785, %787) : (i64, i64) -> !llvm.ptr
%789 = llvm.mlir.addressof @N : !llvm.ptr
%790 = llvm.load %789 : !llvm.ptr -> i64
%791 = arith.constant 4 : i32
%792 = arith.extsi %791 : i32 to i64
%788 = func.call @calloc(%790, %792) : (i64, i64) -> !llvm.ptr
%794 = llvm.mlir.addressof @N : !llvm.ptr
%795 = llvm.load %794 : !llvm.ptr -> i64
%796 = arith.constant 8 : i32
%797 = arith.extsi %796 : i32 to i64
%793 = func.call @calloc(%795, %797) : (i64, i64) -> !llvm.ptr
%799 = llvm.mlir.addressof @N : !llvm.ptr
%800 = llvm.load %799 : !llvm.ptr -> i64
%801 = arith.constant 8 : i32
%802 = arith.extsi %801 : i32 to i64
%798 = func.call @calloc(%800, %802) : (i64, i64) -> !llvm.ptr
%803 = arith.constant 0 : i32
%804 = arith.extsi %803 : i32 to i64
%805 = llvm.mlir.constant(1 : i64) : i64
%806 = llvm.alloca %805 x i64 : (i64) -> !llvm.ptr
llvm.store %804, %806 : i64, !llvm.ptr
%807 = arith.constant 0 : i32
%808 = arith.extsi %807 : i32 to i64
%809 = llvm.mlir.constant(1 : i64) : i64
%810 = llvm.alloca %809 x i64 : (i64) -> !llvm.ptr
llvm.store %808, %810 : i64, !llvm.ptr
cf.br ^bb141
^bb141:
%811 = llvm.load %810 : !llvm.ptr -> i64
%812 = llvm.mlir.addressof @N : !llvm.ptr
%813 = llvm.load %812 : !llvm.ptr -> i64
%814 = arith.cmpi slt, %811, %813 : i64
cf.cond_br %814, ^bb142, ^bb143
^bb142:
%816 = llvm.load %810 : !llvm.ptr -> i64
%817 = llvm.getelementptr %744[%816] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%815 = llvm.load %817 : !llvm.ptr -> i64
%818 = llvm.load %810 : !llvm.ptr -> i64
%819 = arith.constant 1 : i32
%821 = arith.extsi %819 : i32 to i64
%820 = arith.addi %818, %821 : i64
%822 = llvm.mlir.constant(1 : i64) : i64
%823 = llvm.alloca %822 x i64 : (i64) -> !llvm.ptr
llvm.store %820, %823 : i64, !llvm.ptr
cf.br ^bb144
^bb144:
%824 = llvm.load %823 : !llvm.ptr -> i64
%825 = llvm.mlir.addressof @N : !llvm.ptr
%826 = llvm.load %825 : !llvm.ptr -> i64
%827 = arith.cmpi slt, %824, %826 : i64
cf.cond_br %827, ^bb145, ^bb146
^bb145:
%829 = llvm.load %823 : !llvm.ptr -> i64
%830 = llvm.getelementptr %744[%829] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%828 = llvm.load %830 : !llvm.ptr -> i64
%831 = func.call @keys_equal(%698, %703, %712, %717, %815, %698, %703, %712, %717, %828) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> i32
%832 = arith.constant 0 : i32
%833 = arith.cmpi eq, %831, %832 : i32
cf.cond_br %833, ^bb147, ^bb148
^bb147:
cf.br ^bb146
^bb148:
cf.br ^bb149
^bb149:
%834 = llvm.load %823 : !llvm.ptr -> i64
%835 = arith.constant 1 : i32
%837 = arith.extsi %835 : i32 to i64
%836 = arith.addi %834, %837 : i64
llvm.store %836, %823 : i64, !llvm.ptr
cf.br ^bb144
^bb146:
%839 = llvm.getelementptr %698[%815] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%838 = llvm.load %839 : !llvm.ptr -> i32
%840 = llvm.load %806 : !llvm.ptr -> i64
%841 = llvm.getelementptr %774[%840] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %838, %841 : i32, !llvm.ptr
%842 = arith.constant 0 : i32
%843 = llvm.mlir.constant(1 : i64) : i64
%844 = llvm.alloca %843 x i32 : (i64) -> !llvm.ptr
llvm.store %842, %844 : i32, !llvm.ptr
%846 = llvm.getelementptr %698[%815] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%845 = llvm.load %846 : !llvm.ptr -> i32
cf.br ^bb150
^bb150:
%847 = llvm.load %844 : !llvm.ptr -> i32
%848 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%849 = llvm.load %848 : !llvm.ptr -> i32
%850 = arith.cmpi slt, %847, %849 : i32
cf.cond_br %850, ^bb151, ^bb152
^bb151:
%852 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%853 = llvm.load %852 : !llvm.ptr -> i32
%854 = arith.extsi %853 : i32 to i64
%855 = arith.muli %815, %854 : i64
%856 = llvm.load %844 : !llvm.ptr -> i32
%858 = arith.extsi %856 : i32 to i64
%857 = arith.addi %855, %858 : i64
%859 = llvm.getelementptr %703[%857] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%851 = llvm.load %859 : !llvm.ptr -> i32
%860 = llvm.load %806 : !llvm.ptr -> i64
%861 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%862 = llvm.load %861 : !llvm.ptr -> i32
%863 = arith.extsi %862 : i32 to i64
%864 = arith.muli %860, %863 : i64
%865 = llvm.load %844 : !llvm.ptr -> i32
%867 = arith.extsi %865 : i32 to i64
%866 = arith.addi %864, %867 : i64
%868 = llvm.getelementptr %779[%866] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %851, %868 : i32, !llvm.ptr
%869 = llvm.load %844 : !llvm.ptr -> i32
%870 = arith.constant 1 : i32
%871 = arith.addi %869, %870 : i32
llvm.store %871, %844 : i32, !llvm.ptr
cf.br ^bb150
^bb152:
%873 = llvm.getelementptr %712[%815] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%872 = llvm.load %873 : !llvm.ptr -> i32
%874 = llvm.load %806 : !llvm.ptr -> i64
%875 = llvm.getelementptr %788[%874] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %872, %875 : i32, !llvm.ptr
%877 = llvm.getelementptr %717[%815] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%876 = llvm.load %877 : !llvm.ptr -> f64
%878 = llvm.load %806 : !llvm.ptr -> i64
%879 = llvm.getelementptr %793[%878] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %876, %879 : f64, !llvm.ptr
%880 = llvm.load %823 : !llvm.ptr -> i64
%881 = llvm.load %810 : !llvm.ptr -> i64
%882 = arith.subi %880, %881 : i64
%883 = llvm.load %806 : !llvm.ptr -> i64
%884 = llvm.getelementptr %798[%883] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %882, %884 : i64, !llvm.ptr
%885 = llvm.load %806 : !llvm.ptr -> i64
%886 = arith.constant 1 : i32
%888 = arith.extsi %886 : i32 to i64
%887 = arith.addi %885, %888 : i64
llvm.store %887, %806 : i64, !llvm.ptr
%889 = llvm.load %823 : !llvm.ptr -> i64
llvm.store %889, %810 : i64, !llvm.ptr
cf.br ^bb141
^bb143:
func.call @free(%744) : (!llvm.ptr) -> ()
func.call @free(%749) : (!llvm.ptr) -> ()
func.call @free(%698) : (!llvm.ptr) -> ()
func.call @free(%703) : (!llvm.ptr) -> ()
func.call @free(%712) : (!llvm.ptr) -> ()
func.call @free(%717) : (!llvm.ptr) -> ()
%896 = llvm.load %806 : !llvm.ptr -> i64
%897 = llvm.load %806 : !llvm.ptr -> i64
%898 = arith.muli %896, %897 : i64
%900 = arith.constant 4 : i32
%901 = arith.extsi %900 : i32 to i64
%899 = func.call @calloc(%898, %901) : (i64, i64) -> !llvm.ptr
%903 = llvm.mlir.addressof @MAX_KEY_LEN : !llvm.ptr
%904 = llvm.load %903 : !llvm.ptr -> i32
%905 = arith.extsi %904 : i32 to i64
%906 = arith.muli %898, %905 : i64
%907 = arith.constant 4 : i32
%908 = arith.extsi %907 : i32 to i64
%902 = func.call @calloc(%906, %908) : (i64, i64) -> !llvm.ptr
%910 = arith.constant 4 : i32
%911 = arith.extsi %910 : i32 to i64
%909 = func.call @calloc(%898, %911) : (i64, i64) -> !llvm.ptr
%913 = arith.constant 8 : i32
%914 = arith.extsi %913 : i32 to i64
%912 = func.call @calloc(%898, %914) : (i64, i64) -> !llvm.ptr
%916 = arith.constant 8 : i32
%917 = arith.extsi %916 : i32 to i64
%915 = func.call @calloc(%898, %917) : (i64, i64) -> !llvm.ptr
%918 = arith.constant 0 : i32
%919 = arith.extsi %918 : i32 to i64
%920 = llvm.mlir.constant(1 : i64) : i64
%921 = llvm.alloca %920 x i64 : (i64) -> !llvm.ptr
llvm.store %919, %921 : i64, !llvm.ptr
%922 = arith.constant 0 : i32
%923 = arith.extsi %922 : i32 to i64
%924 = llvm.mlir.constant(1 : i64) : i64
%925 = llvm.alloca %924 x i64 : (i64) -> !llvm.ptr
llvm.store %923, %925 : i64, !llvm.ptr
cf.br ^bb153
^bb153:
%926 = llvm.load %925 : !llvm.ptr -> i64
%927 = llvm.load %806 : !llvm.ptr -> i64
%928 = arith.cmpi slt, %926, %927 : i64
cf.cond_br %928, ^bb154, ^bb155
^bb154:
%929 = arith.constant 0 : i32
%930 = arith.extsi %929 : i32 to i64
%931 = llvm.mlir.constant(1 : i64) : i64
%932 = llvm.alloca %931 x i64 : (i64) -> !llvm.ptr
llvm.store %930, %932 : i64, !llvm.ptr
cf.br ^bb156
^bb156:
%933 = llvm.load %932 : !llvm.ptr -> i64
%934 = llvm.load %806 : !llvm.ptr -> i64
%935 = arith.cmpi slt, %933, %934 : i64
cf.cond_br %935, ^bb157, ^bb158
^bb157:
%937 = llvm.load %925 : !llvm.ptr -> i64
%938 = llvm.load %932 : !llvm.ptr -> i64
# String concatenation: !llvm.ptr + i64
# String concatenation: !llvm.ptr + i64
# String concatenation: !llvm.ptr + i64
# String concatenation: !llvm.ptr + i64
func.call @combine_key(%774, %779, %788, %793, %937, %774, %779, %788, %793, %938, %939, %940, %941, %942) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%943 = llvm.load %925 : !llvm.ptr -> i64
%944 = llvm.load %932 : !llvm.ptr -> i64
%945 = arith.cmpi eq, %943, %944 : i64
%946 = scf.if %945 -> (i32) {
%947 = arith.constant 1 : i32
scf.yield %947 : i32
} else {
%948 = arith.constant 0 : i32
scf.yield %948 : i32
}
%949 = arith.extsi %946 : i32 to i64
%951 = llvm.load %925 : !llvm.ptr -> i64
%952 = llvm.getelementptr %798[%951] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%950 = llvm.load %952 : !llvm.ptr -> i64
%954 = llvm.load %932 : !llvm.ptr -> i64
%955 = llvm.getelementptr %798[%954] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%953 = llvm.load %955 : !llvm.ptr -> i64
%956 = arith.addi %953, %949 : i64
%957 = arith.muli %950, %956 : i64
%958 = llvm.load %921 : !llvm.ptr -> i64
%959 = llvm.getelementptr %915[%958] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %957, %959 : i64, !llvm.ptr
%960 = llvm.load %921 : !llvm.ptr -> i64
%961 = arith.constant 1 : i32
%963 = arith.extsi %961 : i32 to i64
%962 = arith.addi %960, %963 : i64
llvm.store %962, %921 : i64, !llvm.ptr
%964 = llvm.load %932 : !llvm.ptr -> i64
%965 = arith.constant 1 : i32
%967 = arith.extsi %965 : i32 to i64
%966 = arith.addi %964, %967 : i64
llvm.store %966, %932 : i64, !llvm.ptr
cf.br ^bb156
^bb158:
%968 = llvm.load %925 : !llvm.ptr -> i64
%969 = arith.constant 1 : i32
%971 = arith.extsi %969 : i32 to i64
%970 = arith.addi %968, %971 : i64
llvm.store %970, %925 : i64, !llvm.ptr
cf.br ^bb153
^bb155:
func.call @free(%774) : (!llvm.ptr) -> ()
func.call @free(%779) : (!llvm.ptr) -> ()
func.call @free(%788) : (!llvm.ptr) -> ()
func.call @free(%793) : (!llvm.ptr) -> ()
func.call @free(%798) : (!llvm.ptr) -> ()
%978 = arith.constant 8 : i32
%979 = arith.extsi %978 : i32 to i64
%977 = func.call @calloc(%898, %979) : (i64, i64) -> !llvm.ptr
%981 = arith.constant 8 : i32
%982 = arith.extsi %981 : i32 to i64
%980 = func.call @calloc(%898, %982) : (i64, i64) -> !llvm.ptr
%983 = arith.constant 0 : i32
%984 = arith.extsi %983 : i32 to i64
%985 = llvm.mlir.constant(1 : i64) : i64
%986 = llvm.alloca %985 x i64 : (i64) -> !llvm.ptr
llvm.store %984, %986 : i64, !llvm.ptr
cf.br ^bb159
^bb159:
%987 = llvm.load %986 : !llvm.ptr -> i64
%988 = arith.cmpi slt, %987, %898 : i64
cf.cond_br %988, ^bb160, ^bb161
^bb160:
%989 = llvm.load %986 : !llvm.ptr -> i64
%990 = llvm.load %986 : !llvm.ptr -> i64
%991 = llvm.getelementptr %977[%990] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %989, %991 : i64, !llvm.ptr
%992 = llvm.load %986 : !llvm.ptr -> i64
%993 = arith.constant 1 : i32
%995 = arith.extsi %993 : i32 to i64
%994 = arith.addi %992, %995 : i64
llvm.store %994, %986 : i64, !llvm.ptr
cf.br ^bb159
^bb161:
%997 = arith.constant 0 : i32
%998 = arith.trunci %898 : i64 to i32
func.call @merge_sort(%977, %997, %998, %899, %902, %909, %912, %980) : (!llvm.ptr, i32, i32, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%999 = arith.constant 0 : i32
%1000 = arith.extsi %999 : i32 to i128
%1001 = llvm.mlir.constant(1 : i64) : i64
%1002 = llvm.alloca %1001 x i128 : (i64) -> !llvm.ptr
llvm.store %1000, %1002 : i128, !llvm.ptr
%1003 = arith.constant 0 : i32
%1004 = arith.extsi %1003 : i32 to i64
%1005 = llvm.mlir.constant(1 : i64) : i64
%1006 = llvm.alloca %1005 x i64 : (i64) -> !llvm.ptr
llvm.store %1004, %1006 : i64, !llvm.ptr
cf.br ^bb162
^bb162:
%1007 = llvm.load %1006 : !llvm.ptr -> i64
%1008 = arith.cmpi slt, %1007, %898 : i64
cf.cond_br %1008, ^bb163, ^bb164
^bb163:
%1010 = llvm.load %1006 : !llvm.ptr -> i64
%1011 = llvm.getelementptr %977[%1010] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1009 = llvm.load %1011 : !llvm.ptr -> i64
%1012 = llvm.load %1006 : !llvm.ptr -> i64
%1013 = arith.constant 1 : i32
%1015 = arith.extsi %1013 : i32 to i64
%1014 = arith.addi %1012, %1015 : i64
%1016 = llvm.mlir.constant(1 : i64) : i64
%1017 = llvm.alloca %1016 x i64 : (i64) -> !llvm.ptr
llvm.store %1014, %1017 : i64, !llvm.ptr
cf.br ^bb165
^bb165:
%1018 = llvm.load %1017 : !llvm.ptr -> i64
%1019 = arith.cmpi slt, %1018, %898 : i64
cf.cond_br %1019, ^bb166, ^bb167
^bb166:
%1021 = llvm.load %1017 : !llvm.ptr -> i64
%1022 = llvm.getelementptr %977[%1021] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1020 = llvm.load %1022 : !llvm.ptr -> i64
%1023 = func.call @keys_equal(%899, %902, %909, %912, %1009, %899, %902, %909, %912, %1020) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> i32
%1024 = arith.constant 0 : i32
%1025 = arith.cmpi eq, %1023, %1024 : i32
cf.cond_br %1025, ^bb168, ^bb169
^bb168:
cf.br ^bb167
^bb169:
cf.br ^bb170
^bb170:
%1026 = llvm.load %1017 : !llvm.ptr -> i64
%1027 = arith.constant 1 : i32
%1029 = arith.extsi %1027 : i32 to i64
%1028 = arith.addi %1026, %1029 : i64
llvm.store %1028, %1017 : i64, !llvm.ptr
cf.br ^bb165
^bb167:
%1030 = arith.constant 0 : i32
%1031 = arith.extsi %1030 : i32 to i128
%1032 = llvm.mlir.constant(1 : i64) : i64
%1033 = llvm.alloca %1032 x i128 : (i64) -> !llvm.ptr
llvm.store %1031, %1033 : i128, !llvm.ptr
%1034 = llvm.load %1006 : !llvm.ptr -> i64
%1035 = llvm.mlir.constant(1 : i64) : i64
%1036 = llvm.alloca %1035 x i64 : (i64) -> !llvm.ptr
llvm.store %1034, %1036 : i64, !llvm.ptr
cf.br ^bb171
^bb171:
%1037 = llvm.load %1036 : !llvm.ptr -> i64
%1038 = llvm.load %1017 : !llvm.ptr -> i64
%1039 = arith.cmpi slt, %1037, %1038 : i64
cf.cond_br %1039, ^bb172, ^bb173
^bb172:
%1040 = llvm.load %1033 : !llvm.ptr -> i128
%1043 = llvm.load %1036 : !llvm.ptr -> i64
%1044 = llvm.getelementptr %977[%1043] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1042 = llvm.load %1044 : !llvm.ptr -> i64
%1045 = llvm.getelementptr %915[%1042] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1041 = llvm.load %1045 : !llvm.ptr -> i64
%1046 = arith.extsi %1041 : i64 to i128
%1048 = arith.trunci %1040 : i128 to i64
%1049 = arith.trunci %1046 : i128 to i64
%1047 = arith.addi %1048, %1049 : i64
%1050 = arith.extsi %1047 : i64 to i128
llvm.store %1050, %1033 : i128, !llvm.ptr
%1051 = llvm.load %1036 : !llvm.ptr -> i64
%1052 = arith.constant 1 : i32
%1054 = arith.extsi %1052 : i32 to i64
%1053 = arith.addi %1051, %1054 : i64
llvm.store %1053, %1036 : i64, !llvm.ptr
cf.br ^bb171
^bb173:
%1055 = llvm.load %1002 : !llvm.ptr -> i128
%1056 = llvm.load %1033 : !llvm.ptr -> i128
%1057 = llvm.load %1033 : !llvm.ptr -> i128
%1059 = arith.trunci %1056 : i128 to i64
%1060 = arith.trunci %1057 : i128 to i64
%1058 = arith.muli %1059, %1060 : i64
%1062 = arith.trunci %1055 : i128 to i64
%1061 = arith.addi %1062, %1058 : i64
%1063 = arith.extsi %1061 : i64 to i128
llvm.store %1063, %1002 : i128, !llvm.ptr
%1064 = llvm.load %1017 : !llvm.ptr -> i64
llvm.store %1064, %1006 : i64, !llvm.ptr
cf.br ^bb162
^bb164:
%1065 = llvm.load %1002 : !llvm.ptr -> i128
%1066 = arith.constant 4 : i32
%1068 = arith.trunci %1065 : i128 to i64
%1069 = arith.extsi %1066 : i32 to i64
%1067 = arith.divsi %1068, %1069 : i64
%1070 = arith.extsi %1067 : i64 to i128
llvm.store %1070, %1002 : i128, !llvm.ptr
func.call @free(%899) : (!llvm.ptr) -> ()
func.call @free(%902) : (!llvm.ptr) -> ()
func.call @free(%909) : (!llvm.ptr) -> ()
func.call @free(%912) : (!llvm.ptr) -> ()
func.call @free(%915) : (!llvm.ptr) -> ()
func.call @free(%977) : (!llvm.ptr) -> ()
func.call @free(%980) : (!llvm.ptr) -> ()
%1079 = llvm.mlir.addressof @g_B : !llvm.ptr
%1080 = llvm.load %1079 : !llvm.ptr -> !llvm.ptr
func.call @free(%1080) : (!llvm.ptr) -> ()
%1081 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1082 = llvm.load %1002 : !llvm.ptr -> i128
%1083 = arith.trunci %1082 : i128 to i64
%1084 = llvm.call @printf(%1081, %1083) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%1085 = arith.constant 0 : i32
func.return %1085 : i32
}
}