Problem 426
Box-ball soliton sum of squares for t_0..t_{10^7}.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n) | O(n log log n) |
|---|
| Space complexity | O(n) | O(n) |
|---|
| Approach | Flow solution | Sieve-based representation count |
|---|
| Verdict | Optimal |
|---|
Flow source
# Project Euler 426
# Box-ball soliton sum of squares for t_0..t_{10^7}.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function main() -> i32 {
let N: i64 = 10000000
let cap: i64 = N + 1000
let stack_sym: ptr<i8> = calloc(cap, 1)
let stack_len: ptr<i64> = calloc(cap, 8)
if stack_sym == null || stack_len == null { return 1 }
let mut top: i64 = 0
stack_sym[0] = 0
stack_len[0] = 1000000000000000000
top = 1
let mut sum_sq: i64 = 0
let mut total_balls: i64 = 0
let mut cur_sym: i32 = 1
let mut s: i64 = 290797
let mut idx: i64 = 0
while idx <= N {
let L: i64 = (s % 64) + 1
s = (s * s) % 50515093
if cur_sym == 1 {
total_balls = total_balls + L
}
if (stack_sym[top - 1] as i32) == cur_sym {
stack_len[top - 1] = stack_len[top - 1] + L
} else {
stack_sym[top] = cur_sym as i8
stack_len[top] = L
top = top + 1
}
while top >= 2 && stack_len[top - 1] >= stack_len[top - 2] {
let k: i64 = stack_len[top - 2]
sum_sq = sum_sq + k * k
let cur_s: i32 = stack_sym[top - 1] as i32
let cur_l: i64 = stack_len[top - 1] - k
top = top - 2
if cur_l > 0 {
if (stack_sym[top - 1] as i32) == cur_s {
stack_len[top - 1] = stack_len[top - 1] + cur_l
} else {
stack_sym[top] = cur_s as i8
stack_len[top] = cur_l
top = top + 1
}
}
}
cur_sym = 1 - cur_sym
idx = idx + 1
}
let trailing: i64 = total_balls + 100
if (stack_sym[top - 1] as i32) == 0 {
stack_len[top - 1] = stack_len[top - 1] + trailing
} else {
stack_sym[top] = 0
stack_len[top] = trailing
top = top + 1
}
while top >= 2 && stack_len[top - 1] >= stack_len[top - 2] {
let k: i64 = stack_len[top - 2]
sum_sq = sum_sq + k * k
let cur_s: i32 = stack_sym[top - 1] as i32
let cur_l: i64 = stack_len[top - 1] - k
top = top - 2
if cur_l > 0 {
if (stack_sym[top - 1] as i32) == cur_s {
stack_len[top - 1] = stack_len[top - 1] + cur_l
} else {
stack_sym[top] = cur_s as i8
stack_len[top] = cur_l
top = top + 1
}
}
}
printf("%lld\n", sum_sq)
free(stack_len)
free(stack_sym)
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; }
int32_t main(void);
int32_t main(void) {
int64_t N = 10000000;
int64_t cap = (N + 1000);
int8_t* stack_sym = (int8_t*)(calloc(cap, 1));
int64_t* stack_len = (int64_t*)(calloc(cap, 8));
if ((stack_sym == NULL || stack_len == NULL)) {
return 1;
}
int64_t top = 0;
stack_sym[0] = 0;
stack_len[0] = 1000000000000000000;
top = 1;
int64_t sum_sq = 0;
int64_t total_balls = 0;
int32_t cur_sym = 1;
int64_t s = 290797;
int64_t idx = 0;
while (idx <= N) {
int64_t L = (FLOW_CHECKED_MOD((s), (64)) + 1);
s = FLOW_CHECKED_MOD(((s * s)), (50515093));
if (cur_sym == 1) {
total_balls = (total_balls + L);
}
if (((int32_t)(stack_sym[(top - 1)])) == cur_sym) {
stack_len[(top - 1)] = (stack_len[(top - 1)] + L);
} else {
stack_sym[top] = ((int8_t)(cur_sym));
stack_len[top] = L;
top = (top + 1);
}
while ((top >= 2 && stack_len[(top - 1)] >= stack_len[(top - 2)])) {
int64_t k = stack_len[(top - 2)];
sum_sq = (sum_sq + (k * k));
int32_t cur_s = ((int32_t)(stack_sym[(top - 1)]));
int64_t cur_l = (stack_len[(top - 1)] - k);
top = (top - 2);
if (cur_l > 0) {
if (((int32_t)(stack_sym[(top - 1)])) == cur_s) {
stack_len[(top - 1)] = (stack_len[(top - 1)] + cur_l);
} else {
stack_sym[top] = ((int8_t)(cur_s));
stack_len[top] = cur_l;
top = (top + 1);
}
}
}
cur_sym = (1 - cur_sym);
idx = (idx + 1);
}
int64_t trailing = (total_balls + 100);
if (((int32_t)(stack_sym[(top - 1)])) == 0) {
stack_len[(top - 1)] = (stack_len[(top - 1)] + trailing);
} else {
stack_sym[top] = 0;
stack_len[top] = trailing;
top = (top + 1);
}
while ((top >= 2 && stack_len[(top - 1)] >= stack_len[(top - 2)])) {
int64_t k = stack_len[(top - 2)];
sum_sq = (sum_sq + (k * k));
int32_t cur_s = ((int32_t)(stack_sym[(top - 1)]));
int64_t cur_l = (stack_len[(top - 1)] - k);
top = (top - 2);
if (cur_l > 0) {
if (((int32_t)(stack_sym[(top - 1)])) == cur_s) {
stack_len[(top - 1)] = (stack_len[(top - 1)] + cur_l);
} else {
stack_sym[top] = ((int8_t)(cur_s));
stack_len[top] = cur_l;
top = (top + 1);
}
}
}
printf("%lld\n", sum_sq);
free(stack_len);
free(stack_sym);
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 @main() -> i32 {
%0 = arith.constant 10000000 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = arith.constant 1000 : i32
%4 = arith.extsi %2 : i32 to i64
%3 = arith.addi %1, %4 : i64
%6 = arith.constant 1 : i32
%7 = arith.extsi %6 : i32 to i64
%5 = func.call @calloc(%3, %7) : (i64, i64) -> !llvm.ptr
%9 = arith.constant 8 : i32
%10 = arith.extsi %9 : i32 to i64
%8 = func.call @calloc(%3, %10) : (i64, i64) -> !llvm.ptr
%11 = llvm.mlir.zero : !llvm.ptr
%12 = llvm.icmp "eq" %5, %11 : !llvm.ptr
%13 = scf.if %12 -> (i1) {
%14 = arith.constant true
scf.yield %14 : i1
} else {
%15 = llvm.mlir.zero : !llvm.ptr
%16 = llvm.icmp "eq" %8, %15 : !llvm.ptr
scf.yield %16 : i1
}
cf.cond_br %13, ^bb0, ^bb1
^bb0:
%17 = arith.constant 1 : i32
func.return %17 : i32
^bb1:
cf.br ^bb2
^bb2:
%18 = arith.constant 0 : i32
%19 = arith.extsi %18 : i32 to i64
%20 = llvm.mlir.constant(1 : i64) : i64
%21 = llvm.alloca %20 x i64 : (i64) -> !llvm.ptr
llvm.store %19, %21 : i64, !llvm.ptr
%22 = arith.constant 0 : i32
%23 = arith.constant 0 : i32
%24 = arith.trunci %22 : i32 to i8
%25 = arith.extsi %23 : i32 to i64
%26 = llvm.getelementptr %5[%25] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %24, %26 : i8, !llvm.ptr
%27 = arith.constant 999999995705032704 : i32
%28 = arith.constant 0 : i32
%29 = arith.extsi %27 : i32 to i64
%30 = arith.extsi %28 : i32 to i64
%31 = llvm.getelementptr %8[%30] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %29, %31 : i64, !llvm.ptr
%32 = arith.constant 1 : i32
%33 = arith.extsi %32 : i32 to i64
llvm.store %33, %21 : i64, !llvm.ptr
%34 = arith.constant 0 : i32
%35 = arith.extsi %34 : i32 to i64
%36 = llvm.mlir.constant(1 : i64) : i64
%37 = llvm.alloca %36 x i64 : (i64) -> !llvm.ptr
llvm.store %35, %37 : i64, !llvm.ptr
%38 = arith.constant 0 : i32
%39 = arith.extsi %38 : i32 to i64
%40 = llvm.mlir.constant(1 : i64) : i64
%41 = llvm.alloca %40 x i64 : (i64) -> !llvm.ptr
llvm.store %39, %41 : i64, !llvm.ptr
%42 = arith.constant 1 : i32
%43 = llvm.mlir.constant(1 : i64) : i64
%44 = llvm.alloca %43 x i32 : (i64) -> !llvm.ptr
llvm.store %42, %44 : i32, !llvm.ptr
%45 = arith.constant 290797 : i32
%46 = arith.extsi %45 : i32 to i64
%47 = llvm.mlir.constant(1 : i64) : i64
%48 = llvm.alloca %47 x i64 : (i64) -> !llvm.ptr
llvm.store %46, %48 : i64, !llvm.ptr
%49 = arith.constant 0 : i32
%50 = arith.extsi %49 : i32 to i64
%51 = llvm.mlir.constant(1 : i64) : i64
%52 = llvm.alloca %51 x i64 : (i64) -> !llvm.ptr
llvm.store %50, %52 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%53 = llvm.load %52 : !llvm.ptr -> i64
%54 = arith.cmpi sle, %53, %1 : i64
cf.cond_br %54, ^bb4, ^bb5
^bb4:
%55 = llvm.load %48 : !llvm.ptr -> i64
%56 = arith.constant 64 : i32
%58 = arith.extsi %56 : i32 to i64
%57 = arith.remsi %55, %58 : i64
%59 = arith.constant 1 : i32
%61 = arith.extsi %59 : i32 to i64
%60 = arith.addi %57, %61 : i64
%62 = llvm.load %48 : !llvm.ptr -> i64
%63 = llvm.load %48 : !llvm.ptr -> i64
%64 = arith.muli %62, %63 : i64
%65 = arith.constant 50515093 : i32
%67 = arith.extsi %65 : i32 to i64
%66 = arith.remsi %64, %67 : i64
llvm.store %66, %48 : i64, !llvm.ptr
%68 = llvm.load %44 : !llvm.ptr -> i32
%69 = arith.constant 1 : i32
%70 = arith.cmpi eq, %68, %69 : i32
cf.cond_br %70, ^bb6, ^bb7
^bb6:
%71 = llvm.load %41 : !llvm.ptr -> i64
%72 = arith.addi %71, %60 : i64
llvm.store %72, %41 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%74 = llvm.load %21 : !llvm.ptr -> i64
%75 = arith.constant 1 : i32
%77 = arith.extsi %75 : i32 to i64
%76 = arith.subi %74, %77 : i64
%78 = llvm.getelementptr %5[%76] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%73 = llvm.load %78 : !llvm.ptr -> i8
%79 = arith.extsi %73 : i8 to i32
%80 = llvm.load %44 : !llvm.ptr -> i32
%81 = arith.cmpi eq, %79, %80 : i32
cf.cond_br %81, ^bb9, ^bb10
^bb9:
%83 = llvm.load %21 : !llvm.ptr -> i64
%84 = arith.constant 1 : i32
%86 = arith.extsi %84 : i32 to i64
%85 = arith.subi %83, %86 : i64
%87 = llvm.getelementptr %8[%85] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%82 = llvm.load %87 : !llvm.ptr -> i64
%88 = arith.addi %82, %60 : i64
%89 = llvm.load %21 : !llvm.ptr -> i64
%90 = arith.constant 1 : i32
%92 = arith.extsi %90 : i32 to i64
%91 = arith.subi %89, %92 : i64
%93 = llvm.getelementptr %8[%91] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %88, %93 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
%94 = llvm.load %44 : !llvm.ptr -> i32
%95 = arith.trunci %94 : i32 to i8
%96 = llvm.load %21 : !llvm.ptr -> i64
%97 = llvm.getelementptr %5[%96] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %95, %97 : i8, !llvm.ptr
%98 = llvm.load %21 : !llvm.ptr -> i64
%99 = llvm.getelementptr %8[%98] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %60, %99 : i64, !llvm.ptr
%100 = llvm.load %21 : !llvm.ptr -> i64
%101 = arith.constant 1 : i32
%103 = arith.extsi %101 : i32 to i64
%102 = arith.addi %100, %103 : i64
llvm.store %102, %21 : i64, !llvm.ptr
cf.br ^bb11
^bb11:
cf.br ^bb12
^bb12:
%104 = llvm.load %21 : !llvm.ptr -> i64
%105 = arith.constant 2 : i32
%107 = arith.extsi %105 : i32 to i64
%106 = arith.cmpi sge, %104, %107 : i64
%108 = scf.if %106 -> (i1) {
%110 = llvm.load %21 : !llvm.ptr -> i64
%111 = arith.constant 1 : i32
%113 = arith.extsi %111 : i32 to i64
%112 = arith.subi %110, %113 : i64
%114 = llvm.getelementptr %8[%112] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%109 = llvm.load %114 : !llvm.ptr -> i64
%116 = llvm.load %21 : !llvm.ptr -> i64
%117 = arith.constant 2 : i32
%119 = arith.extsi %117 : i32 to i64
%118 = arith.subi %116, %119 : i64
%120 = llvm.getelementptr %8[%118] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%115 = llvm.load %120 : !llvm.ptr -> i64
%121 = arith.cmpi sge, %109, %115 : i64
scf.yield %121 : i1
} else {
%122 = arith.constant false
scf.yield %122 : i1
}
cf.cond_br %108, ^bb13, ^bb14
^bb13:
%124 = llvm.load %21 : !llvm.ptr -> i64
%125 = arith.constant 2 : i32
%127 = arith.extsi %125 : i32 to i64
%126 = arith.subi %124, %127 : i64
%128 = llvm.getelementptr %8[%126] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%123 = llvm.load %128 : !llvm.ptr -> i64
%129 = llvm.load %37 : !llvm.ptr -> i64
%130 = arith.muli %123, %123 : i64
%131 = arith.addi %129, %130 : i64
llvm.store %131, %37 : i64, !llvm.ptr
%133 = llvm.load %21 : !llvm.ptr -> i64
%134 = arith.constant 1 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.subi %133, %136 : i64
%137 = llvm.getelementptr %5[%135] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%132 = llvm.load %137 : !llvm.ptr -> i8
%138 = arith.extsi %132 : i8 to i32
%140 = llvm.load %21 : !llvm.ptr -> i64
%141 = arith.constant 1 : i32
%143 = arith.extsi %141 : i32 to i64
%142 = arith.subi %140, %143 : i64
%144 = llvm.getelementptr %8[%142] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%139 = llvm.load %144 : !llvm.ptr -> i64
%145 = arith.subi %139, %123 : i64
%146 = llvm.load %21 : !llvm.ptr -> i64
%147 = arith.constant 2 : i32
%149 = arith.extsi %147 : i32 to i64
%148 = arith.subi %146, %149 : i64
llvm.store %148, %21 : i64, !llvm.ptr
%150 = arith.constant 0 : i32
%152 = arith.extsi %150 : i32 to i64
%151 = arith.cmpi sgt, %145, %152 : i64
cf.cond_br %151, ^bb15, ^bb16
^bb15:
%154 = llvm.load %21 : !llvm.ptr -> i64
%155 = arith.constant 1 : i32
%157 = arith.extsi %155 : i32 to i64
%156 = arith.subi %154, %157 : i64
%158 = llvm.getelementptr %5[%156] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%153 = llvm.load %158 : !llvm.ptr -> i8
%159 = arith.extsi %153 : i8 to i32
%160 = arith.cmpi eq, %159, %138 : i32
cf.cond_br %160, ^bb18, ^bb19
^bb18:
%162 = llvm.load %21 : !llvm.ptr -> i64
%163 = arith.constant 1 : i32
%165 = arith.extsi %163 : i32 to i64
%164 = arith.subi %162, %165 : i64
%166 = llvm.getelementptr %8[%164] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%161 = llvm.load %166 : !llvm.ptr -> i64
%167 = arith.addi %161, %145 : i64
%168 = llvm.load %21 : !llvm.ptr -> i64
%169 = arith.constant 1 : i32
%171 = arith.extsi %169 : i32 to i64
%170 = arith.subi %168, %171 : i64
%172 = llvm.getelementptr %8[%170] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %167, %172 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
%173 = arith.trunci %138 : i32 to i8
%174 = llvm.load %21 : !llvm.ptr -> i64
%175 = llvm.getelementptr %5[%174] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %173, %175 : i8, !llvm.ptr
%176 = llvm.load %21 : !llvm.ptr -> i64
%177 = llvm.getelementptr %8[%176] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %145, %177 : i64, !llvm.ptr
%178 = llvm.load %21 : !llvm.ptr -> i64
%179 = arith.constant 1 : i32
%181 = arith.extsi %179 : i32 to i64
%180 = arith.addi %178, %181 : i64
llvm.store %180, %21 : i64, !llvm.ptr
cf.br ^bb20
^bb20:
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
cf.br ^bb12
^bb14:
%182 = arith.constant 1 : i32
%183 = llvm.load %44 : !llvm.ptr -> i32
%184 = arith.subi %182, %183 : i32
llvm.store %184, %44 : i32, !llvm.ptr
%185 = llvm.load %52 : !llvm.ptr -> i64
%186 = arith.constant 1 : i32
%188 = arith.extsi %186 : i32 to i64
%187 = arith.addi %185, %188 : i64
llvm.store %187, %52 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%189 = llvm.load %41 : !llvm.ptr -> i64
%190 = arith.constant 100 : i32
%192 = arith.extsi %190 : i32 to i64
%191 = arith.addi %189, %192 : i64
%194 = llvm.load %21 : !llvm.ptr -> i64
%195 = arith.constant 1 : i32
%197 = arith.extsi %195 : i32 to i64
%196 = arith.subi %194, %197 : i64
%198 = llvm.getelementptr %5[%196] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%193 = llvm.load %198 : !llvm.ptr -> i8
%199 = arith.extsi %193 : i8 to i32
%200 = arith.constant 0 : i32
%201 = arith.cmpi eq, %199, %200 : i32
cf.cond_br %201, ^bb21, ^bb22
^bb21:
%203 = llvm.load %21 : !llvm.ptr -> i64
%204 = arith.constant 1 : i32
%206 = arith.extsi %204 : i32 to i64
%205 = arith.subi %203, %206 : i64
%207 = llvm.getelementptr %8[%205] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%202 = llvm.load %207 : !llvm.ptr -> i64
%208 = arith.addi %202, %191 : i64
%209 = llvm.load %21 : !llvm.ptr -> i64
%210 = arith.constant 1 : i32
%212 = arith.extsi %210 : i32 to i64
%211 = arith.subi %209, %212 : i64
%213 = llvm.getelementptr %8[%211] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %208, %213 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
%214 = arith.constant 0 : i32
%215 = llvm.load %21 : !llvm.ptr -> i64
%216 = arith.trunci %214 : i32 to i8
%217 = llvm.getelementptr %5[%215] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %216, %217 : i8, !llvm.ptr
%218 = llvm.load %21 : !llvm.ptr -> i64
%219 = llvm.getelementptr %8[%218] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %191, %219 : i64, !llvm.ptr
%220 = llvm.load %21 : !llvm.ptr -> i64
%221 = arith.constant 1 : i32
%223 = arith.extsi %221 : i32 to i64
%222 = arith.addi %220, %223 : i64
llvm.store %222, %21 : i64, !llvm.ptr
cf.br ^bb23
^bb23:
cf.br ^bb24
^bb24:
%224 = llvm.load %21 : !llvm.ptr -> i64
%225 = arith.constant 2 : i32
%227 = arith.extsi %225 : i32 to i64
%226 = arith.cmpi sge, %224, %227 : i64
%228 = scf.if %226 -> (i1) {
%230 = llvm.load %21 : !llvm.ptr -> i64
%231 = arith.constant 1 : i32
%233 = arith.extsi %231 : i32 to i64
%232 = arith.subi %230, %233 : i64
%234 = llvm.getelementptr %8[%232] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%229 = llvm.load %234 : !llvm.ptr -> i64
%236 = llvm.load %21 : !llvm.ptr -> i64
%237 = arith.constant 2 : i32
%239 = arith.extsi %237 : i32 to i64
%238 = arith.subi %236, %239 : i64
%240 = llvm.getelementptr %8[%238] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%235 = llvm.load %240 : !llvm.ptr -> i64
%241 = arith.cmpi sge, %229, %235 : i64
scf.yield %241 : i1
} else {
%242 = arith.constant false
scf.yield %242 : i1
}
cf.cond_br %228, ^bb25, ^bb26
^bb25:
%244 = llvm.load %21 : !llvm.ptr -> i64
%245 = arith.constant 2 : i32
%247 = arith.extsi %245 : i32 to i64
%246 = arith.subi %244, %247 : i64
%248 = llvm.getelementptr %8[%246] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%243 = llvm.load %248 : !llvm.ptr -> i64
%249 = llvm.load %37 : !llvm.ptr -> i64
%250 = arith.muli %243, %243 : i64
%251 = arith.addi %249, %250 : i64
llvm.store %251, %37 : i64, !llvm.ptr
%253 = llvm.load %21 : !llvm.ptr -> i64
%254 = arith.constant 1 : i32
%256 = arith.extsi %254 : i32 to i64
%255 = arith.subi %253, %256 : i64
%257 = llvm.getelementptr %5[%255] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%252 = llvm.load %257 : !llvm.ptr -> i8
%258 = arith.extsi %252 : i8 to i32
%260 = llvm.load %21 : !llvm.ptr -> i64
%261 = arith.constant 1 : i32
%263 = arith.extsi %261 : i32 to i64
%262 = arith.subi %260, %263 : i64
%264 = llvm.getelementptr %8[%262] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%259 = llvm.load %264 : !llvm.ptr -> i64
%265 = arith.subi %259, %243 : i64
%266 = llvm.load %21 : !llvm.ptr -> i64
%267 = arith.constant 2 : i32
%269 = arith.extsi %267 : i32 to i64
%268 = arith.subi %266, %269 : i64
llvm.store %268, %21 : i64, !llvm.ptr
%270 = arith.constant 0 : i32
%272 = arith.extsi %270 : i32 to i64
%271 = arith.cmpi sgt, %265, %272 : i64
cf.cond_br %271, ^bb27, ^bb28
^bb27:
%274 = llvm.load %21 : !llvm.ptr -> i64
%275 = arith.constant 1 : i32
%277 = arith.extsi %275 : i32 to i64
%276 = arith.subi %274, %277 : i64
%278 = llvm.getelementptr %5[%276] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%273 = llvm.load %278 : !llvm.ptr -> i8
%279 = arith.extsi %273 : i8 to i32
%280 = arith.cmpi eq, %279, %258 : i32
cf.cond_br %280, ^bb30, ^bb31
^bb30:
%282 = llvm.load %21 : !llvm.ptr -> i64
%283 = arith.constant 1 : i32
%285 = arith.extsi %283 : i32 to i64
%284 = arith.subi %282, %285 : i64
%286 = llvm.getelementptr %8[%284] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%281 = llvm.load %286 : !llvm.ptr -> i64
%287 = arith.addi %281, %265 : i64
%288 = llvm.load %21 : !llvm.ptr -> i64
%289 = arith.constant 1 : i32
%291 = arith.extsi %289 : i32 to i64
%290 = arith.subi %288, %291 : i64
%292 = llvm.getelementptr %8[%290] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %287, %292 : i64, !llvm.ptr
cf.br ^bb32
^bb31:
%293 = arith.trunci %258 : i32 to i8
%294 = llvm.load %21 : !llvm.ptr -> i64
%295 = llvm.getelementptr %5[%294] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %293, %295 : i8, !llvm.ptr
%296 = llvm.load %21 : !llvm.ptr -> i64
%297 = llvm.getelementptr %8[%296] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %265, %297 : i64, !llvm.ptr
%298 = llvm.load %21 : !llvm.ptr -> i64
%299 = arith.constant 1 : i32
%301 = arith.extsi %299 : i32 to i64
%300 = arith.addi %298, %301 : i64
llvm.store %300, %21 : i64, !llvm.ptr
cf.br ^bb32
^bb32:
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
cf.br ^bb24
^bb26:
%302 = llvm.mlir.addressof @str_0 : !llvm.ptr
%303 = llvm.load %37 : !llvm.ptr -> i64
%304 = llvm.call @printf(%302, %303) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%8) : (!llvm.ptr) -> ()
func.call @free(%5) : (!llvm.ptr) -> ()
%307 = arith.constant 0 : i32
func.return %307 : i32
}
}