Problem 569
Prime Mountain Range S(N)=sum of visible earlier peaks; chain property over first N=2.5e6 peaks.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n log log n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Sieve or enumeration |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 569
# Prime Mountain Range
# S(N)=sum of visible earlier peaks; chain property over first N=2.5e6 peaks.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function realloc(p: ptr<void>, size: i64) -> ptr<void>
function log(x: f64) -> f64
}
function upper_bound_nth_prime(n: i64) -> i64 {
if n < 6 { return 15 }
let nn: f64 = n as f64
return (nn * (log(nn) + log(log(nn))) + 10.0) as i64
}
function solve(n_peaks: i64) -> i64 {
let need: i64 = 2 * n_peaks
let mut limit: i64 = upper_bound_nth_prime(need) + 1000
let X: ptr<i64> = calloc(n_peaks, 8)
let Y: ptr<i64> = calloc(n_peaks, 8)
if X == null || Y == null { return -1 }
while true {
let size: i64 = limit / 2 + 1
let is_prime: ptr<i8> = calloc(size, 1)
if is_prime == null { return -1 }
let mut i: i64 = 0
while i < size {
is_prime[i] = 1
i = i + 1
}
is_prime[0] = 0
let mut rr: i64 = limit
let mut yy: i64 = (rr + 1) / 2
while yy < rr {
rr = yy
yy = (rr + limit / rr) / 2
}
i = 1
while i <= rr / 2 {
if is_prime[i] != 0 {
let p: i64 = 2 * i + 1
let mut start: i64 = (p * p) / 2
while start < size {
is_prime[start] = 0
start = start + p
}
}
i = i + 1
}
let mut x_base: i64 = 0
let mut y_base: i64 = 0
let mut count: i64 = 1
let mut peak_i: i64 = 0
let mut x_peak: i64 = 2
let mut y_peak: i64 = 2
X[0] = 2
Y[0] = 2
peak_i = 1
let mut idx: i64 = 1
let mut done: i32 = 0
while idx < size {
if is_prime[idx] != 0 {
let p: i64 = 2 * idx + 1
count = count + 1
if (count & 1) != 0 {
x_peak = x_base + p
y_peak = y_base + p
X[peak_i] = x_peak
Y[peak_i] = y_peak
peak_i = peak_i + 1
} else {
x_base = x_peak + p
y_base = y_peak - p
}
if count == need {
done = 1
break
}
}
idx = idx + 1
}
free(is_prime)
if done != 0 { break }
limit = limit + limit / 10 + 1000
}
# Visibility via chain property
let offs: ptr<i64> = calloc(n_peaks, 8)
let ln: ptr<i64> = calloc(n_peaks, 8)
let mut vis_cap: i64 = n_peaks * 4
let mut vis: ptr<i32> = calloc(vis_cap, 4)
if offs == null || ln == null || vis == null { return -1 }
let mut vis_len: i64 = 0
let mut total: i64 = 0
let mut k: i64 = 1
while k < n_peaks {
let xk: i64 = X[k]
let yk: i64 = Y[k]
let start_k: i64 = vis_len
offs[k] = start_k
if vis_len + 64 >= vis_cap {
vis_cap = vis_cap * 2
vis = realloc(vis, vis_cap * 4)
if vis == null { return -1 }
}
let mut a: i64 = k - 1
vis[vis_len] = a as i32
vis_len = vis_len + 1
let mut l: i64 = 1
let mut m_num: i64 = yk - Y[a]
let mut m_den: i64 = xk - X[a]
while true {
let offa: i64 = offs[a]
let enda: i64 = offa + ln[a]
let mut found: i32 = 0
let mut pos: i64 = offa
while pos < enda {
let cand: i64 = vis[pos] as i64
let dy: i64 = yk - Y[cand]
let dx: i64 = xk - X[cand]
if dy * m_den < m_num * dx {
if vis_len + 8 >= vis_cap {
vis_cap = vis_cap * 2
vis = realloc(vis, vis_cap * 4)
if vis == null { return -1 }
}
vis[vis_len] = cand as i32
vis_len = vis_len + 1
l = l + 1
a = cand
m_num = dy
m_den = dx
found = 1
break
}
pos = pos + 1
}
if found == 0 { break }
}
ln[k] = l
total = total + l
k = k + 1
}
free(X)
free(Y)
free(offs)
free(ln)
free(vis)
return total
}
function main() -> i32 {
printf("%lld\n", solve(2500000))
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t upper_bound_nth_prime_i64(int64_t n);
int64_t solve_i64(int64_t n_peaks);
int32_t main(void);
int64_t upper_bound_nth_prime_i64(int64_t n) {
if (n < 6) {
return 15;
}
double nn = ((double)(n));
return ((int64_t)(((nn * (log(nn) + log(log(nn)))) + 10.0)));
}
int64_t solve_i64(int64_t n_peaks) {
int64_t need = (2 * n_peaks);
int64_t limit = (upper_bound_nth_prime_i64(need) + 1000);
int64_t* X = (int64_t*)(calloc(n_peaks, 8));
int64_t* Y = (int64_t*)(calloc(n_peaks, 8));
if ((X == NULL || Y == NULL)) {
return (-1);
}
while (1) {
int64_t size = (FLOW_CHECKED_DIV((limit), (2)) + 1);
int8_t* is_prime = (int8_t*)(calloc(size, 1));
if (is_prime == NULL) {
return (-1);
}
int64_t i = 0;
while (i < size) {
is_prime[i] = 1;
i = (i + 1);
}
is_prime[0] = 0;
int64_t rr = limit;
int64_t yy = FLOW_CHECKED_DIV(((rr + 1)), (2));
while (yy < rr) {
rr = yy;
yy = FLOW_CHECKED_DIV(((rr + FLOW_CHECKED_DIV((limit), (rr)))), (2));
}
i = 1;
while (i <= FLOW_CHECKED_DIV((rr), (2))) {
if (is_prime[i] != 0) {
int64_t p = ((2 * i) + 1);
int64_t start = FLOW_CHECKED_DIV(((p * p)), (2));
while (start < size) {
is_prime[start] = 0;
start = (start + p);
}
}
i = (i + 1);
}
int64_t x_base = 0;
int64_t y_base = 0;
int64_t count = 1;
int64_t peak_i = 0;
int64_t x_peak = 2;
int64_t y_peak = 2;
X[0] = 2;
Y[0] = 2;
peak_i = 1;
int64_t idx = 1;
int32_t done = 0;
while (idx < size) {
if (is_prime[idx] != 0) {
int64_t p = ((2 * idx) + 1);
count = (count + 1);
if ((count & 1) != 0) {
x_peak = (x_base + p);
y_peak = (y_base + p);
X[peak_i] = x_peak;
Y[peak_i] = y_peak;
peak_i = (peak_i + 1);
} else {
x_base = (x_peak + p);
y_base = (y_peak - p);
}
if (count == need) {
done = 1;
break;
}
}
idx = (idx + 1);
}
free(is_prime);
if (done != 0) {
break;
}
limit = ((limit + FLOW_CHECKED_DIV((limit), (10))) + 1000);
}
int64_t* offs = (int64_t*)(calloc(n_peaks, 8));
int64_t* ln = (int64_t*)(calloc(n_peaks, 8));
int64_t vis_cap = (n_peaks * 4);
int32_t* vis = (int32_t*)(calloc(vis_cap, 4));
if (((offs == NULL || ln == NULL) || vis == NULL)) {
return (-1);
}
int64_t vis_len = 0;
int64_t total = 0;
int64_t k = 1;
while (k < n_peaks) {
int64_t xk = X[k];
int64_t yk = Y[k];
int64_t start_k = vis_len;
offs[k] = start_k;
if ((vis_len + 64) >= vis_cap) {
vis_cap = (vis_cap * 2);
vis = realloc(vis, (vis_cap * 4));
if (vis == NULL) {
return (-1);
}
}
int64_t a = (k - 1);
vis[vis_len] = ((int32_t)(a));
vis_len = (vis_len + 1);
int64_t l = 1;
int64_t m_num = (yk - Y[a]);
int64_t m_den = (xk - X[a]);
while (1) {
int64_t offa = offs[a];
int64_t enda = (offa + ln[a]);
int32_t found = 0;
int64_t pos = offa;
while (pos < enda) {
int64_t cand = ((int64_t)(vis[pos]));
int64_t dy = (yk - Y[cand]);
int64_t dx = (xk - X[cand]);
if ((dy * m_den) < (m_num * dx)) {
if ((vis_len + 8) >= vis_cap) {
vis_cap = (vis_cap * 2);
vis = realloc(vis, (vis_cap * 4));
if (vis == NULL) {
return (-1);
}
}
vis[vis_len] = ((int32_t)(cand));
vis_len = (vis_len + 1);
l = (l + 1);
a = cand;
m_num = dy;
m_den = dx;
found = 1;
break;
}
pos = (pos + 1);
}
if (found == 0) {
break;
}
}
ln[k] = l;
total = (total + l);
k = (k + 1);
}
free(X);
free(Y);
free(offs);
free(ln);
free(vis);
return total;
}
int32_t main(void) {
printf("%lld\n", solve_i64(2500000));
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 @realloc(!llvm.ptr, i64) -> !llvm.ptr
func.func private @log(f64) -> f64
func.func @upper_bound_nth_prime(%arg0: i64) -> i64 {
%0 = arith.constant 6 : i32
%2 = arith.extsi %0 : i32 to i64
%1 = arith.cmpi slt, %arg0, %2 : i64
cf.cond_br %1, ^bb0, ^bb1
^bb0:
%3 = arith.constant 15 : i32
%4 = arith.extsi %3 : i32 to i64
func.return %4 : i64
^bb1:
cf.br ^bb2
^bb2:
%5 = arith.sitofp %arg0 : i64 to f64
%6 = math.log %5 : f64
%7 = math.log %5 : f64
%8 = math.log %7 : f64
%9 = arith.addf %6, %8 : f64
%10 = arith.mulf %5, %9 : f64
%11 = arith.constant 10.0 : f32
%13 = arith.extf %11 : f32 to f64
%12 = arith.addf %10, %13 : f64
%14 = arith.fptosi %12 : f64 to i64
func.return %14 : i64
}
func.func @solve(%arg0: i64) -> i64 {
%15 = arith.constant 2 : i32
%17 = arith.extsi %15 : i32 to i64
%16 = arith.muli %17, %arg0 : i64
%18 = func.call @upper_bound_nth_prime(%16) : (i64) -> i64
%19 = arith.constant 1000 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.addi %18, %21 : i64
%22 = llvm.mlir.constant(1 : i64) : i64
%23 = llvm.alloca %22 x i64 : (i64) -> !llvm.ptr
llvm.store %20, %23 : i64, !llvm.ptr
%25 = arith.constant 8 : i32
%26 = arith.extsi %25 : i32 to i64
%24 = func.call @calloc(%arg0, %26) : (i64, i64) -> !llvm.ptr
%28 = arith.constant 8 : i32
%29 = arith.extsi %28 : i32 to i64
%27 = func.call @calloc(%arg0, %29) : (i64, i64) -> !llvm.ptr
%30 = llvm.mlir.zero : !llvm.ptr
%31 = llvm.icmp "eq" %24, %30 : !llvm.ptr
%32 = scf.if %31 -> (i1) {
%33 = arith.constant true
scf.yield %33 : i1
} else {
%34 = llvm.mlir.zero : !llvm.ptr
%35 = llvm.icmp "eq" %27, %34 : !llvm.ptr
scf.yield %35 : i1
}
cf.cond_br %32, ^bb3, ^bb4
^bb3:
%36 = arith.constant 1 : i32
%38 = arith.constant 0 : i32
%37 = arith.subi %38, %36 : i32
%39 = arith.extsi %37 : i32 to i64
func.return %39 : i64
^bb4:
cf.br ^bb5
^bb5:
cf.br ^bb6
^bb6:
%40 = arith.constant 1 : i1
cf.cond_br %40, ^bb7, ^bb8
^bb7:
%41 = llvm.load %23 : !llvm.ptr -> i64
%42 = arith.constant 2 : i32
%44 = arith.extsi %42 : i32 to i64
%43 = arith.divsi %41, %44 : i64
%45 = arith.constant 1 : i32
%47 = arith.extsi %45 : i32 to i64
%46 = arith.addi %43, %47 : i64
%49 = arith.constant 1 : i32
%50 = arith.extsi %49 : i32 to i64
%48 = func.call @calloc(%46, %50) : (i64, i64) -> !llvm.ptr
%51 = llvm.mlir.zero : !llvm.ptr
%52 = llvm.icmp "eq" %48, %51 : !llvm.ptr
cf.cond_br %52, ^bb9, ^bb10
^bb9:
%53 = arith.constant 1 : i32
%55 = arith.constant 0 : i32
%54 = arith.subi %55, %53 : i32
%56 = arith.extsi %54 : i32 to i64
func.return %56 : i64
^bb10:
cf.br ^bb11
^bb11:
%57 = arith.constant 0 : i32
%58 = arith.extsi %57 : i32 to i64
%59 = llvm.mlir.constant(1 : i64) : i64
%60 = llvm.alloca %59 x i64 : (i64) -> !llvm.ptr
llvm.store %58, %60 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%61 = llvm.load %60 : !llvm.ptr -> i64
%62 = arith.cmpi slt, %61, %46 : i64
cf.cond_br %62, ^bb13, ^bb14
^bb13:
%63 = arith.constant 1 : i32
%64 = llvm.load %60 : !llvm.ptr -> i64
%65 = arith.trunci %63 : i32 to i8
%66 = llvm.getelementptr %48[%64] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %65, %66 : i8, !llvm.ptr
%67 = llvm.load %60 : !llvm.ptr -> i64
%68 = arith.constant 1 : i32
%70 = arith.extsi %68 : i32 to i64
%69 = arith.addi %67, %70 : i64
llvm.store %69, %60 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%71 = arith.constant 0 : i32
%72 = arith.constant 0 : i32
%73 = arith.trunci %71 : i32 to i8
%74 = arith.extsi %72 : i32 to i64
%75 = llvm.getelementptr %48[%74] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %73, %75 : i8, !llvm.ptr
%76 = llvm.load %23 : !llvm.ptr -> i64
%77 = llvm.mlir.constant(1 : i64) : i64
%78 = llvm.alloca %77 x i64 : (i64) -> !llvm.ptr
llvm.store %76, %78 : i64, !llvm.ptr
%79 = llvm.load %78 : !llvm.ptr -> i64
%80 = arith.constant 1 : i32
%82 = arith.extsi %80 : i32 to i64
%81 = arith.addi %79, %82 : i64
%83 = arith.constant 2 : i32
%85 = arith.extsi %83 : i32 to i64
%84 = arith.divsi %81, %85 : i64
%86 = llvm.mlir.constant(1 : i64) : i64
%87 = llvm.alloca %86 x i64 : (i64) -> !llvm.ptr
llvm.store %84, %87 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%88 = llvm.load %87 : !llvm.ptr -> i64
%89 = llvm.load %78 : !llvm.ptr -> i64
%90 = arith.cmpi slt, %88, %89 : i64
cf.cond_br %90, ^bb16, ^bb17
^bb16:
%91 = llvm.load %87 : !llvm.ptr -> i64
llvm.store %91, %78 : i64, !llvm.ptr
%92 = llvm.load %78 : !llvm.ptr -> i64
%93 = llvm.load %23 : !llvm.ptr -> i64
%94 = llvm.load %78 : !llvm.ptr -> i64
%95 = arith.divsi %93, %94 : i64
%96 = arith.addi %92, %95 : i64
%97 = arith.constant 2 : i32
%99 = arith.extsi %97 : i32 to i64
%98 = arith.divsi %96, %99 : i64
llvm.store %98, %87 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%100 = arith.constant 1 : i32
%101 = arith.extsi %100 : i32 to i64
llvm.store %101, %60 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%102 = llvm.load %60 : !llvm.ptr -> i64
%103 = llvm.load %78 : !llvm.ptr -> i64
%104 = arith.constant 2 : i32
%106 = arith.extsi %104 : i32 to i64
%105 = arith.divsi %103, %106 : i64
%107 = arith.cmpi sle, %102, %105 : i64
cf.cond_br %107, ^bb19, ^bb20
^bb19:
%109 = llvm.load %60 : !llvm.ptr -> i64
%110 = llvm.getelementptr %48[%109] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%108 = llvm.load %110 : !llvm.ptr -> i8
%111 = arith.constant 0 : i32
%113 = arith.extsi %108 : i8 to i32
%112 = arith.cmpi ne, %113, %111 : i32
cf.cond_br %112, ^bb21, ^bb22
^bb21:
%114 = arith.constant 2 : i32
%115 = llvm.load %60 : !llvm.ptr -> i64
%117 = arith.extsi %114 : i32 to i64
%116 = arith.muli %117, %115 : i64
%118 = arith.constant 1 : i32
%120 = arith.extsi %118 : i32 to i64
%119 = arith.addi %116, %120 : i64
%121 = arith.muli %119, %119 : i64
%122 = arith.constant 2 : i32
%124 = arith.extsi %122 : i32 to i64
%123 = arith.divsi %121, %124 : i64
%125 = llvm.mlir.constant(1 : i64) : i64
%126 = llvm.alloca %125 x i64 : (i64) -> !llvm.ptr
llvm.store %123, %126 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%127 = llvm.load %126 : !llvm.ptr -> i64
%128 = arith.cmpi slt, %127, %46 : i64
cf.cond_br %128, ^bb25, ^bb26
^bb25:
%129 = arith.constant 0 : i32
%130 = llvm.load %126 : !llvm.ptr -> i64
%131 = arith.trunci %129 : i32 to i8
%132 = llvm.getelementptr %48[%130] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %131, %132 : i8, !llvm.ptr
%133 = llvm.load %126 : !llvm.ptr -> i64
%134 = arith.addi %133, %119 : i64
llvm.store %134, %126 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%135 = llvm.load %60 : !llvm.ptr -> i64
%136 = arith.constant 1 : i32
%138 = arith.extsi %136 : i32 to i64
%137 = arith.addi %135, %138 : i64
llvm.store %137, %60 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%139 = arith.constant 0 : i32
%140 = arith.extsi %139 : i32 to i64
%141 = llvm.mlir.constant(1 : i64) : i64
%142 = llvm.alloca %141 x i64 : (i64) -> !llvm.ptr
llvm.store %140, %142 : i64, !llvm.ptr
%143 = arith.constant 0 : i32
%144 = arith.extsi %143 : i32 to i64
%145 = llvm.mlir.constant(1 : i64) : i64
%146 = llvm.alloca %145 x i64 : (i64) -> !llvm.ptr
llvm.store %144, %146 : i64, !llvm.ptr
%147 = arith.constant 1 : i32
%148 = arith.extsi %147 : i32 to i64
%149 = llvm.mlir.constant(1 : i64) : i64
%150 = llvm.alloca %149 x i64 : (i64) -> !llvm.ptr
llvm.store %148, %150 : i64, !llvm.ptr
%151 = arith.constant 0 : i32
%152 = arith.extsi %151 : i32 to i64
%153 = llvm.mlir.constant(1 : i64) : i64
%154 = llvm.alloca %153 x i64 : (i64) -> !llvm.ptr
llvm.store %152, %154 : i64, !llvm.ptr
%155 = arith.constant 2 : i32
%156 = arith.extsi %155 : i32 to i64
%157 = llvm.mlir.constant(1 : i64) : i64
%158 = llvm.alloca %157 x i64 : (i64) -> !llvm.ptr
llvm.store %156, %158 : i64, !llvm.ptr
%159 = arith.constant 2 : i32
%160 = arith.extsi %159 : i32 to i64
%161 = llvm.mlir.constant(1 : i64) : i64
%162 = llvm.alloca %161 x i64 : (i64) -> !llvm.ptr
llvm.store %160, %162 : i64, !llvm.ptr
%163 = arith.constant 2 : i32
%164 = arith.constant 0 : i32
%165 = arith.extsi %163 : i32 to i64
%166 = arith.extsi %164 : i32 to i64
%167 = llvm.getelementptr %24[%166] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %165, %167 : i64, !llvm.ptr
%168 = arith.constant 2 : i32
%169 = arith.constant 0 : i32
%170 = arith.extsi %168 : i32 to i64
%171 = arith.extsi %169 : i32 to i64
%172 = llvm.getelementptr %27[%171] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %170, %172 : i64, !llvm.ptr
%173 = arith.constant 1 : i32
%174 = arith.extsi %173 : i32 to i64
llvm.store %174, %154 : i64, !llvm.ptr
%175 = arith.constant 1 : i32
%176 = arith.extsi %175 : i32 to i64
%177 = llvm.mlir.constant(1 : i64) : i64
%178 = llvm.alloca %177 x i64 : (i64) -> !llvm.ptr
llvm.store %176, %178 : i64, !llvm.ptr
%179 = arith.constant 0 : i32
%180 = llvm.mlir.constant(1 : i64) : i64
%181 = llvm.alloca %180 x i32 : (i64) -> !llvm.ptr
llvm.store %179, %181 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%182 = llvm.load %178 : !llvm.ptr -> i64
%183 = arith.cmpi slt, %182, %46 : i64
cf.cond_br %183, ^bb28, ^bb29
^bb28:
%185 = llvm.load %178 : !llvm.ptr -> i64
%186 = llvm.getelementptr %48[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%184 = llvm.load %186 : !llvm.ptr -> i8
%187 = arith.constant 0 : i32
%189 = arith.extsi %184 : i8 to i32
%188 = arith.cmpi ne, %189, %187 : i32
cf.cond_br %188, ^bb30, ^bb31
^bb30:
%190 = arith.constant 2 : i32
%191 = llvm.load %178 : !llvm.ptr -> i64
%193 = arith.extsi %190 : i32 to i64
%192 = arith.muli %193, %191 : i64
%194 = arith.constant 1 : i32
%196 = arith.extsi %194 : i32 to i64
%195 = arith.addi %192, %196 : i64
%197 = llvm.load %150 : !llvm.ptr -> i64
%198 = arith.constant 1 : i32
%200 = arith.extsi %198 : i32 to i64
%199 = arith.addi %197, %200 : i64
llvm.store %199, %150 : i64, !llvm.ptr
%201 = llvm.load %150 : !llvm.ptr -> i64
%202 = arith.constant 1 : i32
%204 = arith.extsi %202 : i32 to i64
%203 = arith.andi %201, %204 : i64
%205 = arith.constant 0 : i32
%207 = arith.extsi %205 : i32 to i64
%206 = arith.cmpi ne, %203, %207 : i64
cf.cond_br %206, ^bb33, ^bb34
^bb33:
%208 = llvm.load %142 : !llvm.ptr -> i64
%209 = arith.addi %208, %195 : i64
llvm.store %209, %158 : i64, !llvm.ptr
%210 = llvm.load %146 : !llvm.ptr -> i64
%211 = arith.addi %210, %195 : i64
llvm.store %211, %162 : i64, !llvm.ptr
%212 = llvm.load %158 : !llvm.ptr -> i64
%213 = llvm.load %154 : !llvm.ptr -> i64
%214 = llvm.getelementptr %24[%213] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %212, %214 : i64, !llvm.ptr
%215 = llvm.load %162 : !llvm.ptr -> i64
%216 = llvm.load %154 : !llvm.ptr -> i64
%217 = llvm.getelementptr %27[%216] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %215, %217 : i64, !llvm.ptr
%218 = llvm.load %154 : !llvm.ptr -> i64
%219 = arith.constant 1 : i32
%221 = arith.extsi %219 : i32 to i64
%220 = arith.addi %218, %221 : i64
llvm.store %220, %154 : i64, !llvm.ptr
cf.br ^bb35
^bb34:
%222 = llvm.load %158 : !llvm.ptr -> i64
%223 = arith.addi %222, %195 : i64
llvm.store %223, %142 : i64, !llvm.ptr
%224 = llvm.load %162 : !llvm.ptr -> i64
%225 = arith.subi %224, %195 : i64
llvm.store %225, %146 : i64, !llvm.ptr
cf.br ^bb35
^bb35:
%226 = llvm.load %150 : !llvm.ptr -> i64
%227 = arith.cmpi eq, %226, %16 : i64
cf.cond_br %227, ^bb36, ^bb37
^bb36:
%228 = arith.constant 1 : i32
llvm.store %228, %181 : i32, !llvm.ptr
cf.br ^bb29
^bb37:
cf.br ^bb38
^bb38:
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%229 = llvm.load %178 : !llvm.ptr -> i64
%230 = arith.constant 1 : i32
%232 = arith.extsi %230 : i32 to i64
%231 = arith.addi %229, %232 : i64
llvm.store %231, %178 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
func.call @free(%48) : (!llvm.ptr) -> ()
%234 = llvm.load %181 : !llvm.ptr -> i32
%235 = arith.constant 0 : i32
%236 = arith.cmpi ne, %234, %235 : i32
cf.cond_br %236, ^bb39, ^bb40
^bb39:
cf.br ^bb8
^bb40:
cf.br ^bb41
^bb41:
%237 = llvm.load %23 : !llvm.ptr -> i64
%238 = llvm.load %23 : !llvm.ptr -> i64
%239 = arith.constant 10 : i32
%241 = arith.extsi %239 : i32 to i64
%240 = arith.divsi %238, %241 : i64
%242 = arith.addi %237, %240 : i64
%243 = arith.constant 1000 : i32
%245 = arith.extsi %243 : i32 to i64
%244 = arith.addi %242, %245 : i64
llvm.store %244, %23 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%247 = arith.constant 8 : i32
%248 = arith.extsi %247 : i32 to i64
%246 = func.call @calloc(%arg0, %248) : (i64, i64) -> !llvm.ptr
%250 = arith.constant 8 : i32
%251 = arith.extsi %250 : i32 to i64
%249 = func.call @calloc(%arg0, %251) : (i64, i64) -> !llvm.ptr
%252 = arith.constant 4 : i32
%254 = arith.extsi %252 : i32 to i64
%253 = arith.muli %arg0, %254 : i64
%255 = llvm.mlir.constant(1 : i64) : i64
%256 = llvm.alloca %255 x i64 : (i64) -> !llvm.ptr
llvm.store %253, %256 : i64, !llvm.ptr
%258 = llvm.load %256 : !llvm.ptr -> i64
%259 = arith.constant 4 : i32
%260 = arith.extsi %259 : i32 to i64
%257 = func.call @calloc(%258, %260) : (i64, i64) -> !llvm.ptr
%261 = llvm.mlir.constant(1 : i64) : i64
%262 = llvm.alloca %261 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %257, %262 : !llvm.ptr, !llvm.ptr
%263 = llvm.mlir.zero : !llvm.ptr
%264 = llvm.icmp "eq" %246, %263 : !llvm.ptr
%265 = scf.if %264 -> (i1) {
%266 = arith.constant true
scf.yield %266 : i1
} else {
%267 = llvm.mlir.zero : !llvm.ptr
%268 = llvm.icmp "eq" %249, %267 : !llvm.ptr
scf.yield %268 : i1
}
%269 = scf.if %265 -> (i1) {
%270 = arith.constant true
scf.yield %270 : i1
} else {
%271 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
%272 = llvm.mlir.zero : !llvm.ptr
%273 = llvm.icmp "eq" %271, %272 : !llvm.ptr
scf.yield %273 : i1
}
cf.cond_br %269, ^bb42, ^bb43
^bb42:
%274 = arith.constant 1 : i32
%276 = arith.constant 0 : i32
%275 = arith.subi %276, %274 : i32
%277 = arith.extsi %275 : i32 to i64
func.return %277 : i64
^bb43:
cf.br ^bb44
^bb44:
%278 = arith.constant 0 : i32
%279 = arith.extsi %278 : i32 to i64
%280 = llvm.mlir.constant(1 : i64) : i64
%281 = llvm.alloca %280 x i64 : (i64) -> !llvm.ptr
llvm.store %279, %281 : i64, !llvm.ptr
%282 = arith.constant 0 : i32
%283 = arith.extsi %282 : i32 to i64
%284 = llvm.mlir.constant(1 : i64) : i64
%285 = llvm.alloca %284 x i64 : (i64) -> !llvm.ptr
llvm.store %283, %285 : i64, !llvm.ptr
%286 = arith.constant 1 : i32
%287 = arith.extsi %286 : i32 to i64
%288 = llvm.mlir.constant(1 : i64) : i64
%289 = llvm.alloca %288 x i64 : (i64) -> !llvm.ptr
llvm.store %287, %289 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%290 = llvm.load %289 : !llvm.ptr -> i64
%291 = arith.cmpi slt, %290, %arg0 : i64
cf.cond_br %291, ^bb46, ^bb47
^bb46:
%293 = llvm.load %289 : !llvm.ptr -> i64
%294 = llvm.getelementptr %24[%293] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%292 = llvm.load %294 : !llvm.ptr -> i64
%296 = llvm.load %289 : !llvm.ptr -> i64
%297 = llvm.getelementptr %27[%296] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%295 = llvm.load %297 : !llvm.ptr -> i64
%298 = llvm.load %281 : !llvm.ptr -> i64
%299 = llvm.load %289 : !llvm.ptr -> i64
%300 = llvm.getelementptr %246[%299] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %298, %300 : i64, !llvm.ptr
%301 = llvm.load %281 : !llvm.ptr -> i64
%302 = arith.constant 64 : i32
%304 = arith.extsi %302 : i32 to i64
%303 = arith.addi %301, %304 : i64
%305 = llvm.load %256 : !llvm.ptr -> i64
%306 = arith.cmpi sge, %303, %305 : i64
cf.cond_br %306, ^bb48, ^bb49
^bb48:
%307 = llvm.load %256 : !llvm.ptr -> i64
%308 = arith.constant 2 : i32
%310 = arith.extsi %308 : i32 to i64
%309 = arith.muli %307, %310 : i64
llvm.store %309, %256 : i64, !llvm.ptr
%312 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
%313 = llvm.load %256 : !llvm.ptr -> i64
%314 = arith.constant 4 : i32
%316 = arith.extsi %314 : i32 to i64
%315 = arith.muli %313, %316 : i64
%311 = func.call @realloc(%312, %315) : (!llvm.ptr, i64) -> !llvm.ptr
llvm.store %311, %262 : !llvm.ptr, !llvm.ptr
%317 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
%318 = llvm.mlir.zero : !llvm.ptr
%319 = llvm.icmp "eq" %317, %318 : !llvm.ptr
cf.cond_br %319, ^bb51, ^bb52
^bb51:
%320 = arith.constant 1 : i32
%322 = arith.constant 0 : i32
%321 = arith.subi %322, %320 : i32
%323 = arith.extsi %321 : i32 to i64
func.return %323 : i64
^bb52:
cf.br ^bb53
^bb53:
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%324 = llvm.load %289 : !llvm.ptr -> i64
%325 = arith.constant 1 : i32
%327 = arith.extsi %325 : i32 to i64
%326 = arith.subi %324, %327 : i64
%328 = llvm.mlir.constant(1 : i64) : i64
%329 = llvm.alloca %328 x i64 : (i64) -> !llvm.ptr
llvm.store %326, %329 : i64, !llvm.ptr
%330 = llvm.load %329 : !llvm.ptr -> i64
%331 = arith.trunci %330 : i64 to i32
%332 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
%333 = llvm.load %281 : !llvm.ptr -> i64
%334 = llvm.getelementptr %332[%333] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %331, %334 : i32, !llvm.ptr
%335 = llvm.load %281 : !llvm.ptr -> i64
%336 = arith.constant 1 : i32
%338 = arith.extsi %336 : i32 to i64
%337 = arith.addi %335, %338 : i64
llvm.store %337, %281 : i64, !llvm.ptr
%339 = arith.constant 1 : i32
%340 = arith.extsi %339 : i32 to i64
%341 = llvm.mlir.constant(1 : i64) : i64
%342 = llvm.alloca %341 x i64 : (i64) -> !llvm.ptr
llvm.store %340, %342 : i64, !llvm.ptr
%344 = llvm.load %329 : !llvm.ptr -> i64
%345 = llvm.getelementptr %27[%344] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%343 = llvm.load %345 : !llvm.ptr -> i64
%346 = arith.subi %295, %343 : i64
%347 = llvm.mlir.constant(1 : i64) : i64
%348 = llvm.alloca %347 x i64 : (i64) -> !llvm.ptr
llvm.store %346, %348 : i64, !llvm.ptr
%350 = llvm.load %329 : !llvm.ptr -> i64
%351 = llvm.getelementptr %24[%350] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%349 = llvm.load %351 : !llvm.ptr -> i64
%352 = arith.subi %292, %349 : i64
%353 = llvm.mlir.constant(1 : i64) : i64
%354 = llvm.alloca %353 x i64 : (i64) -> !llvm.ptr
llvm.store %352, %354 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%355 = arith.constant 1 : i1
cf.cond_br %355, ^bb55, ^bb56
^bb55:
%357 = llvm.load %329 : !llvm.ptr -> i64
%358 = llvm.getelementptr %246[%357] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%356 = llvm.load %358 : !llvm.ptr -> i64
%360 = llvm.load %329 : !llvm.ptr -> i64
%361 = llvm.getelementptr %249[%360] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%359 = llvm.load %361 : !llvm.ptr -> i64
%362 = arith.addi %356, %359 : i64
%363 = arith.constant 0 : i32
%364 = llvm.mlir.constant(1 : i64) : i64
%365 = llvm.alloca %364 x i32 : (i64) -> !llvm.ptr
llvm.store %363, %365 : i32, !llvm.ptr
%366 = llvm.mlir.constant(1 : i64) : i64
%367 = llvm.alloca %366 x i64 : (i64) -> !llvm.ptr
llvm.store %356, %367 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%368 = llvm.load %367 : !llvm.ptr -> i64
%369 = arith.cmpi slt, %368, %362 : i64
cf.cond_br %369, ^bb58, ^bb59
^bb58:
%371 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
%372 = llvm.load %367 : !llvm.ptr -> i64
%373 = llvm.getelementptr %371[%372] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%370 = llvm.load %373 : !llvm.ptr -> i32
%374 = arith.extsi %370 : i32 to i64
%376 = llvm.getelementptr %27[%374] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%375 = llvm.load %376 : !llvm.ptr -> i64
%377 = arith.subi %295, %375 : i64
%379 = llvm.getelementptr %24[%374] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%378 = llvm.load %379 : !llvm.ptr -> i64
%380 = arith.subi %292, %378 : i64
%381 = llvm.load %354 : !llvm.ptr -> i64
%382 = arith.muli %377, %381 : i64
%383 = llvm.load %348 : !llvm.ptr -> i64
%384 = arith.muli %383, %380 : i64
%385 = arith.cmpi slt, %382, %384 : i64
cf.cond_br %385, ^bb60, ^bb61
^bb60:
%386 = llvm.load %281 : !llvm.ptr -> i64
%387 = arith.constant 8 : i32
%389 = arith.extsi %387 : i32 to i64
%388 = arith.addi %386, %389 : i64
%390 = llvm.load %256 : !llvm.ptr -> i64
%391 = arith.cmpi sge, %388, %390 : i64
cf.cond_br %391, ^bb63, ^bb64
^bb63:
%392 = llvm.load %256 : !llvm.ptr -> i64
%393 = arith.constant 2 : i32
%395 = arith.extsi %393 : i32 to i64
%394 = arith.muli %392, %395 : i64
llvm.store %394, %256 : i64, !llvm.ptr
%397 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
%398 = llvm.load %256 : !llvm.ptr -> i64
%399 = arith.constant 4 : i32
%401 = arith.extsi %399 : i32 to i64
%400 = arith.muli %398, %401 : i64
%396 = func.call @realloc(%397, %400) : (!llvm.ptr, i64) -> !llvm.ptr
llvm.store %396, %262 : !llvm.ptr, !llvm.ptr
%402 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
%403 = llvm.mlir.zero : !llvm.ptr
%404 = llvm.icmp "eq" %402, %403 : !llvm.ptr
cf.cond_br %404, ^bb66, ^bb67
^bb66:
%405 = arith.constant 1 : i32
%407 = arith.constant 0 : i32
%406 = arith.subi %407, %405 : i32
%408 = arith.extsi %406 : i32 to i64
func.return %408 : i64
^bb67:
cf.br ^bb68
^bb68:
cf.br ^bb65
^bb64:
cf.br ^bb65
^bb65:
%409 = arith.trunci %374 : i64 to i32
%410 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
%411 = llvm.load %281 : !llvm.ptr -> i64
%412 = llvm.getelementptr %410[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %409, %412 : i32, !llvm.ptr
%413 = llvm.load %281 : !llvm.ptr -> i64
%414 = arith.constant 1 : i32
%416 = arith.extsi %414 : i32 to i64
%415 = arith.addi %413, %416 : i64
llvm.store %415, %281 : i64, !llvm.ptr
%417 = llvm.load %342 : !llvm.ptr -> i64
%418 = arith.constant 1 : i32
%420 = arith.extsi %418 : i32 to i64
%419 = arith.addi %417, %420 : i64
llvm.store %419, %342 : i64, !llvm.ptr
llvm.store %374, %329 : i64, !llvm.ptr
llvm.store %377, %348 : i64, !llvm.ptr
llvm.store %380, %354 : i64, !llvm.ptr
%421 = arith.constant 1 : i32
llvm.store %421, %365 : i32, !llvm.ptr
cf.br ^bb59
^bb61:
cf.br ^bb62
^bb62:
%422 = llvm.load %367 : !llvm.ptr -> i64
%423 = arith.constant 1 : i32
%425 = arith.extsi %423 : i32 to i64
%424 = arith.addi %422, %425 : i64
llvm.store %424, %367 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
%426 = llvm.load %365 : !llvm.ptr -> i32
%427 = arith.constant 0 : i32
%428 = arith.cmpi eq, %426, %427 : i32
cf.cond_br %428, ^bb69, ^bb70
^bb69:
cf.br ^bb56
^bb70:
cf.br ^bb71
^bb71:
cf.br ^bb54
^bb56:
%429 = llvm.load %342 : !llvm.ptr -> i64
%430 = llvm.load %289 : !llvm.ptr -> i64
%431 = llvm.getelementptr %249[%430] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %429, %431 : i64, !llvm.ptr
%432 = llvm.load %285 : !llvm.ptr -> i64
%433 = llvm.load %342 : !llvm.ptr -> i64
%434 = arith.addi %432, %433 : i64
llvm.store %434, %285 : i64, !llvm.ptr
%435 = llvm.load %289 : !llvm.ptr -> i64
%436 = arith.constant 1 : i32
%438 = arith.extsi %436 : i32 to i64
%437 = arith.addi %435, %438 : i64
llvm.store %437, %289 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
func.call @free(%24) : (!llvm.ptr) -> ()
func.call @free(%27) : (!llvm.ptr) -> ()
func.call @free(%246) : (!llvm.ptr) -> ()
func.call @free(%249) : (!llvm.ptr) -> ()
%444 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
func.call @free(%444) : (!llvm.ptr) -> ()
%445 = llvm.load %285 : !llvm.ptr -> i64
func.return %445 : i64
}
func.func @main() -> i32 {
%446 = llvm.mlir.addressof @str_0 : !llvm.ptr
%448 = arith.constant 2500000 : i32
%449 = arith.extsi %448 : i32 to i64
%447 = func.call @solve(%449) : (i64) -> i64
%450 = llvm.call @printf(%446, %447) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%451 = arith.constant 0 : i32
func.return %451 : i32
}
}