Problem 988
frog_sum(19, 53) = 2727531976556215755 DP keyed by height (0..~48). Each entry holds (count, total).
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 988
# frog_sum(19, 53) = 2727531976556215755
# DP keyed by height (0..~48). Each entry holds (count, total).
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memset(p: ptr<void>, c: i32, n: i64) -> ptr<void>
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
}
const MAXW: i64 = 64
const MAXH: i64 = 64
function main() -> i32 {
let mut a: i64 = 19
let mut b: i64 = 53
if a > b {
let t: i64 = a
a = b
b = t
}
if a == 1 {
printf("%lld\n", 0)
return 0
}
let width: i64 = b - 1
let h: ptr<i64> = calloc(MAXW + 1, 8)
for i in 1..(width + 1) {
h[i] = (a * b - a * i - 1) / b
}
let cnt: ptr<i64> = calloc(MAXH + 1, 8)
let tot: ptr<i64> = calloc(MAXH + 1, 8)
let ncnt: ptr<i64> = calloc(MAXH + 1, 8)
let ntot: ptr<i64> = calloc(MAXH + 1, 8)
for t in 0..(h[1] + 1) {
cnt[t] = 1
tot[t] = 0
}
for i in 2..(width + 1) {
memset(ncnt, 0, (MAXH + 1) * 8)
memset(ntot, 0, (MAXH + 1) * 8)
for prev in 0..(MAXH + 1) {
if cnt[prev] == 0 && tot[prev] == 0 {
continue
}
let count: i64 = cnt[prev]
let total: i64 = tot[prev]
let limit: i64 = if prev < h[i] { prev } else { h[i] }
for cur in 0..(limit + 1) {
let mut add: i64 = 0
if prev > cur && prev > 0 {
add = a * b - a * (i - 1) - b * prev
}
ncnt[cur] = ncnt[cur] + count
ntot[cur] = ntot[cur] + total + count * add
}
}
memcpy(cnt, ncnt, (MAXH + 1) * 8)
memcpy(tot, ntot, (MAXH + 1) * 8)
}
let mut answer: i64 = 0
let last_column: i64 = width
for prev in 0..(MAXH + 1) {
if cnt[prev] == 0 && tot[prev] == 0 {
continue
}
let mut add: i64 = 0
if prev > 0 {
add = a * b - a * last_column - b * prev
}
answer = answer + tot[prev] + cnt[prev] * add
}
printf("%lld\n", answer)
free(h)
free(cnt)
free(tot)
free(ncnt)
free(ntot)
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);
static const int64_t MAXW = 64;
static const int64_t MAXH = 64;
int32_t main(void) {
int64_t a = 19;
int64_t b = 53;
if (a > b) {
int64_t t = a;
a = b;
b = t;
}
if (a == 1) {
printf("%lld\n", 0);
return 0;
}
int64_t width = (b - 1);
int64_t* h = (int64_t*)(calloc((MAXW + 1), 8));
int32_t __flow_step_1 = 1;
for (int32_t i = 1; (1 <= (width + 1)) ? i < (width + 1) : i > (width + 1); i += (1 <= (width + 1)) ? 1 : -1) {
h[i] = FLOW_CHECKED_DIV(((((a * b) - (a * i)) - 1)), (b));
}
int64_t* cnt = (int64_t*)(calloc((MAXH + 1), 8));
int64_t* tot = (int64_t*)(calloc((MAXH + 1), 8));
int64_t* ncnt = (int64_t*)(calloc((MAXH + 1), 8));
int64_t* ntot = (int64_t*)(calloc((MAXH + 1), 8));
int32_t __flow_step_2 = 1;
for (int32_t t = 0; (0 <= (h[1] + 1)) ? t < (h[1] + 1) : t > (h[1] + 1); t += (0 <= (h[1] + 1)) ? 1 : -1) {
cnt[t] = 1;
tot[t] = 0;
}
int32_t __flow_step_3 = 1;
for (int32_t i = 2; (2 <= (width + 1)) ? i < (width + 1) : i > (width + 1); i += (2 <= (width + 1)) ? 1 : -1) {
memset(ncnt, 0, ((MAXH + 1) * 8));
memset(ntot, 0, ((MAXH + 1) * 8));
int32_t __flow_step_4 = 1;
for (int32_t prev = 0; (0 <= (MAXH + 1)) ? prev < (MAXH + 1) : prev > (MAXH + 1); prev += (0 <= (MAXH + 1)) ? 1 : -1) {
if ((cnt[prev] == 0 && tot[prev] == 0)) {
continue;
}
int64_t count = cnt[prev];
int64_t total = tot[prev];
int64_t limit = ((prev < h[i]) ? (prev) : (h[i]));
int32_t __flow_step_5 = 1;
for (int32_t cur = 0; (0 <= (limit + 1)) ? cur < (limit + 1) : cur > (limit + 1); cur += (0 <= (limit + 1)) ? 1 : -1) {
int64_t add = 0;
if ((prev > cur && prev > 0)) {
add = (((a * b) - (a * (i - 1))) - (b * prev));
}
ncnt[cur] = (ncnt[cur] + count);
ntot[cur] = ((ntot[cur] + total) + (count * add));
}
}
memcpy(cnt, ncnt, ((MAXH + 1) * 8));
memcpy(tot, ntot, ((MAXH + 1) * 8));
}
int64_t answer = 0;
int64_t last_column = width;
int32_t __flow_step_6 = 1;
for (int32_t prev = 0; (0 <= (MAXH + 1)) ? prev < (MAXH + 1) : prev > (MAXH + 1); prev += (0 <= (MAXH + 1)) ? 1 : -1) {
if ((cnt[prev] == 0 && tot[prev] == 0)) {
continue;
}
int64_t add = 0;
if (prev > 0) {
add = (((a * b) - (a * last_column)) - (b * prev));
}
answer = ((answer + tot[prev]) + (cnt[prev] * add));
}
printf("%lld\n", answer);
free(h);
free(cnt);
free(tot);
free(ncnt);
free(ntot);
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 @memset(!llvm.ptr, i32, i64) -> !llvm.ptr
func.func private @memcpy(!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
// Constant: MAXW
llvm.mlir.global internal constant @MAXW(64 : i64) : i64
// Constant: MAXH
llvm.mlir.global internal constant @MAXH(64 : i64) : i64
func.func @main() -> i32 {
%0 = arith.constant 19 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i64, !llvm.ptr
%4 = arith.constant 53 : i32
%5 = arith.extsi %4 : i32 to i64
%6 = llvm.mlir.constant(1 : i64) : i64
%7 = llvm.alloca %6 x i64 : (i64) -> !llvm.ptr
llvm.store %5, %7 : i64, !llvm.ptr
%8 = llvm.load %3 : !llvm.ptr -> i64
%9 = llvm.load %7 : !llvm.ptr -> i64
%10 = arith.cmpi sgt, %8, %9 : i64
cf.cond_br %10, ^bb0, ^bb1
^bb0:
%11 = llvm.load %3 : !llvm.ptr -> i64
%12 = llvm.load %7 : !llvm.ptr -> i64
llvm.store %12, %3 : i64, !llvm.ptr
llvm.store %11, %7 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%13 = llvm.load %3 : !llvm.ptr -> i64
%14 = arith.constant 1 : i32
%16 = arith.extsi %14 : i32 to i64
%15 = arith.cmpi eq, %13, %16 : i64
cf.cond_br %15, ^bb3, ^bb4
^bb3:
%17 = llvm.mlir.addressof @str_0 : !llvm.ptr
%18 = arith.constant 0 : i32
%19 = llvm.call @printf(%17, %18) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i32) -> i32
%20 = arith.constant 0 : i32
func.return %20 : i32
^bb4:
cf.br ^bb5
^bb5:
%21 = llvm.load %7 : !llvm.ptr -> i64
%22 = arith.constant 1 : i32
%24 = arith.extsi %22 : i32 to i64
%23 = arith.subi %21, %24 : i64
%26 = llvm.mlir.addressof @MAXW : !llvm.ptr
%27 = llvm.load %26 : !llvm.ptr -> i64
%28 = arith.constant 1 : i32
%30 = arith.extsi %28 : i32 to i64
%29 = arith.addi %27, %30 : i64
%31 = arith.constant 8 : i32
%32 = arith.extsi %31 : i32 to i64
%25 = func.call @calloc(%29, %32) : (i64, i64) -> !llvm.ptr
%33 = arith.constant 1 : i32
%34 = arith.constant 1 : i32
%36 = arith.extsi %34 : i32 to i64
%35 = arith.addi %23, %36 : i64
%37 = arith.index_cast %33 : i32 to index
%38 = arith.index_cast %35 : i32 to index
%40 = arith.constant 1 : index
%41 = arith.constant -1 : index
%42 = arith.cmpi sle, %37, %38 : index
%39 = arith.select %42, %40, %41 : index
cf.br ^bb6(%37 : index)
^bb6(%43: index):
%44 = arith.cmpi slt, %43, %38 : index
%45 = arith.cmpi sgt, %43, %38 : index
%46 = arith.select %42, %44, %45 : i1
cf.cond_br %46, ^bb7(%43 : index), ^bb8(%43 : index)
^bb7(%47: index):
%48 = llvm.load %3 : !llvm.ptr -> i64
%49 = llvm.load %7 : !llvm.ptr -> i64
%50 = arith.muli %48, %49 : i64
%51 = llvm.load %3 : !llvm.ptr -> i64
%53 = arith.trunci %51 : i64 to i32
%54 = arith.index_cast %47 : index to i32
%52 = arith.muli %53, %54 : i32
%56 = arith.extsi %52 : i32 to i64
%55 = arith.subi %50, %56 : i64
%57 = arith.constant 1 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.subi %55, %59 : i64
%60 = llvm.load %7 : !llvm.ptr -> i64
%61 = arith.divsi %58, %60 : i64
%62 = arith.index_cast %47 : index to i64
%63 = llvm.getelementptr %25[%62] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %61, %63 : i64, !llvm.ptr
%64 = arith.addi %47, %39 : index
cf.br ^bb6(%64 : index)
^bb8(%65: index):
%67 = llvm.mlir.addressof @MAXH : !llvm.ptr
%68 = llvm.load %67 : !llvm.ptr -> i64
%69 = arith.constant 1 : i32
%71 = arith.extsi %69 : i32 to i64
%70 = arith.addi %68, %71 : i64
%72 = arith.constant 8 : i32
%73 = arith.extsi %72 : i32 to i64
%66 = func.call @calloc(%70, %73) : (i64, i64) -> !llvm.ptr
%75 = llvm.mlir.addressof @MAXH : !llvm.ptr
%76 = llvm.load %75 : !llvm.ptr -> i64
%77 = arith.constant 1 : i32
%79 = arith.extsi %77 : i32 to i64
%78 = arith.addi %76, %79 : i64
%80 = arith.constant 8 : i32
%81 = arith.extsi %80 : i32 to i64
%74 = func.call @calloc(%78, %81) : (i64, i64) -> !llvm.ptr
%83 = llvm.mlir.addressof @MAXH : !llvm.ptr
%84 = llvm.load %83 : !llvm.ptr -> i64
%85 = arith.constant 1 : i32
%87 = arith.extsi %85 : i32 to i64
%86 = arith.addi %84, %87 : i64
%88 = arith.constant 8 : i32
%89 = arith.extsi %88 : i32 to i64
%82 = func.call @calloc(%86, %89) : (i64, i64) -> !llvm.ptr
%91 = llvm.mlir.addressof @MAXH : !llvm.ptr
%92 = llvm.load %91 : !llvm.ptr -> i64
%93 = arith.constant 1 : i32
%95 = arith.extsi %93 : i32 to i64
%94 = arith.addi %92, %95 : i64
%96 = arith.constant 8 : i32
%97 = arith.extsi %96 : i32 to i64
%90 = func.call @calloc(%94, %97) : (i64, i64) -> !llvm.ptr
%98 = arith.constant 0 : i32
%100 = arith.constant 1 : i32
%101 = arith.extsi %100 : i32 to i64
%102 = llvm.getelementptr %25[%101] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%99 = llvm.load %102 : !llvm.ptr -> i64
%103 = arith.constant 1 : i32
%105 = arith.extsi %103 : i32 to i64
%104 = arith.addi %99, %105 : i64
%106 = arith.index_cast %98 : i32 to index
%107 = arith.index_cast %104 : i32 to index
%109 = arith.constant 1 : index
%110 = arith.constant -1 : index
%111 = arith.cmpi sle, %106, %107 : index
%108 = arith.select %111, %109, %110 : index
cf.br ^bb9(%106 : index)
^bb9(%112: index):
%113 = arith.cmpi slt, %112, %107 : index
%114 = arith.cmpi sgt, %112, %107 : index
%115 = arith.select %111, %113, %114 : i1
cf.cond_br %115, ^bb10(%112 : index), ^bb11(%112 : index)
^bb10(%116: index):
%117 = arith.constant 1 : i32
%118 = arith.extsi %117 : i32 to i64
%119 = arith.index_cast %116 : index to i64
%120 = llvm.getelementptr %66[%119] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %118, %120 : i64, !llvm.ptr
%121 = arith.constant 0 : i32
%122 = arith.extsi %121 : i32 to i64
%123 = arith.index_cast %116 : index to i64
%124 = llvm.getelementptr %74[%123] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %122, %124 : i64, !llvm.ptr
%125 = arith.addi %116, %108 : index
cf.br ^bb9(%125 : index)
^bb11(%126: index):
%127 = arith.constant 2 : i32
%128 = arith.constant 1 : i32
%130 = arith.extsi %128 : i32 to i64
%129 = arith.addi %23, %130 : i64
%131 = arith.index_cast %127 : i32 to index
%132 = arith.index_cast %129 : i32 to index
%134 = arith.constant 1 : index
%135 = arith.constant -1 : index
%136 = arith.cmpi sle, %131, %132 : index
%133 = arith.select %136, %134, %135 : index
cf.br ^bb12(%131 : index)
^bb12(%137: index):
%138 = arith.cmpi slt, %137, %132 : index
%139 = arith.cmpi sgt, %137, %132 : index
%140 = arith.select %136, %138, %139 : i1
cf.cond_br %140, ^bb13(%137 : index), ^bb14(%137 : index)
^bb13(%141: index):
%143 = arith.constant 0 : i32
%144 = llvm.mlir.addressof @MAXH : !llvm.ptr
%145 = llvm.load %144 : !llvm.ptr -> i64
%146 = arith.constant 1 : i32
%148 = arith.extsi %146 : i32 to i64
%147 = arith.addi %145, %148 : i64
%149 = arith.constant 8 : i32
%151 = arith.extsi %149 : i32 to i64
%150 = arith.muli %147, %151 : i64
%142 = func.call @memset(%82, %143, %150) : (!llvm.ptr, i32, i64) -> !llvm.ptr
%153 = arith.constant 0 : i32
%154 = llvm.mlir.addressof @MAXH : !llvm.ptr
%155 = llvm.load %154 : !llvm.ptr -> i64
%156 = arith.constant 1 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.addi %155, %158 : i64
%159 = arith.constant 8 : i32
%161 = arith.extsi %159 : i32 to i64
%160 = arith.muli %157, %161 : i64
%152 = func.call @memset(%90, %153, %160) : (!llvm.ptr, i32, i64) -> !llvm.ptr
%162 = arith.constant 0 : i32
%163 = llvm.mlir.addressof @MAXH : !llvm.ptr
%164 = llvm.load %163 : !llvm.ptr -> i64
%165 = arith.constant 1 : i32
%167 = arith.extsi %165 : i32 to i64
%166 = arith.addi %164, %167 : i64
%168 = arith.index_cast %162 : i32 to index
%169 = arith.index_cast %166 : i32 to index
%171 = arith.constant 1 : index
%172 = arith.constant -1 : index
%173 = arith.cmpi sle, %168, %169 : index
%170 = arith.select %173, %171, %172 : index
cf.br ^bb15(%168 : index)
^bb15(%174: index):
%175 = arith.cmpi slt, %174, %169 : index
%176 = arith.cmpi sgt, %174, %169 : index
%177 = arith.select %173, %175, %176 : i1
cf.cond_br %177, ^bb16(%174 : index), ^bb17(%174 : index)
^bb16(%178: index):
%180 = arith.index_cast %178 : index to i64
%181 = llvm.getelementptr %66[%180] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%179 = llvm.load %181 : !llvm.ptr -> i64
%182 = arith.constant 0 : i32
%184 = arith.extsi %182 : i32 to i64
%183 = arith.cmpi eq, %179, %184 : i64
%185 = scf.if %183 -> (i1) {
%187 = arith.index_cast %178 : index to i64
%188 = llvm.getelementptr %74[%187] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%186 = llvm.load %188 : !llvm.ptr -> i64
%189 = arith.constant 0 : i32
%191 = arith.extsi %189 : i32 to i64
%190 = arith.cmpi eq, %186, %191 : i64
scf.yield %190 : i1
} else {
%192 = arith.constant false
scf.yield %192 : i1
}
cf.cond_br %185, ^bb18, ^bb19
^bb18:
%193 = arith.addi %178, %170 : index
cf.br ^bb15(%193 : index)
^bb19:
cf.br ^bb20
^bb20:
%195 = arith.index_cast %178 : index to i64
%196 = llvm.getelementptr %66[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%194 = llvm.load %196 : !llvm.ptr -> i64
%198 = arith.index_cast %178 : index to i64
%199 = llvm.getelementptr %74[%198] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%197 = llvm.load %199 : !llvm.ptr -> i64
%201 = arith.index_cast %141 : index to i64
%202 = llvm.getelementptr %25[%201] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%200 = llvm.load %202 : !llvm.ptr -> i64
%204 = arith.index_cast %178 : index to i32
%205 = arith.trunci %200 : i64 to i32
%203 = arith.cmpi slt, %204, %205 : i32
%206 = scf.if %203 -> (index) {
scf.yield %178 : index
} else {
%208 = arith.index_cast %141 : index to i64
%209 = llvm.getelementptr %25[%208] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%207 = llvm.load %209 : !llvm.ptr -> i64
scf.yield %207 : i64
}
%210 = arith.index_cast %206 : index to i64
%211 = arith.constant 0 : i32
%212 = arith.constant 1 : i32
%214 = arith.extsi %212 : i32 to i64
%213 = arith.addi %210, %214 : i64
%215 = arith.index_cast %211 : i32 to index
%216 = arith.index_cast %213 : i32 to index
%218 = arith.constant 1 : index
%219 = arith.constant -1 : index
%220 = arith.cmpi sle, %215, %216 : index
%217 = arith.select %220, %218, %219 : index
cf.br ^bb21(%215 : index)
^bb21(%221: index):
%222 = arith.cmpi slt, %221, %216 : index
%223 = arith.cmpi sgt, %221, %216 : index
%224 = arith.select %220, %222, %223 : i1
cf.cond_br %224, ^bb22(%221 : index), ^bb23(%221 : index)
^bb22(%225: index):
%226 = arith.constant 0 : i32
%227 = arith.extsi %226 : i32 to i64
%228 = llvm.mlir.constant(1 : i64) : i64
%229 = llvm.alloca %228 x i64 : (i64) -> !llvm.ptr
llvm.store %227, %229 : i64, !llvm.ptr
%230 = arith.cmpi sgt, %178, %225 : index
%231 = scf.if %230 -> (i1) {
%232 = arith.constant 0 : i32
%234 = arith.index_cast %178 : index to i32
%233 = arith.cmpi sgt, %234, %232 : i32
scf.yield %233 : i1
} else {
%235 = arith.constant false
scf.yield %235 : i1
}
cf.cond_br %231, ^bb24, ^bb25
^bb24:
%236 = llvm.load %3 : !llvm.ptr -> i64
%237 = llvm.load %7 : !llvm.ptr -> i64
%238 = arith.muli %236, %237 : i64
%239 = llvm.load %3 : !llvm.ptr -> i64
%240 = arith.constant 1 : i32
%242 = arith.index_cast %141 : index to i32
%241 = arith.subi %242, %240 : i32
%244 = arith.extsi %241 : i32 to i64
%243 = arith.muli %239, %244 : i64
%245 = arith.subi %238, %243 : i64
%246 = llvm.load %7 : !llvm.ptr -> i64
%248 = arith.trunci %246 : i64 to i32
%249 = arith.index_cast %178 : index to i32
%247 = arith.muli %248, %249 : i32
%251 = arith.extsi %247 : i32 to i64
%250 = arith.subi %245, %251 : i64
llvm.store %250, %229 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%253 = arith.index_cast %225 : index to i64
%254 = llvm.getelementptr %82[%253] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%252 = llvm.load %254 : !llvm.ptr -> i64
%255 = arith.addi %252, %194 : i64
%256 = arith.index_cast %225 : index to i64
%257 = llvm.getelementptr %82[%256] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %255, %257 : i64, !llvm.ptr
%259 = arith.index_cast %225 : index to i64
%260 = llvm.getelementptr %90[%259] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%258 = llvm.load %260 : !llvm.ptr -> i64
%261 = arith.addi %258, %197 : i64
%262 = llvm.load %229 : !llvm.ptr -> i64
%263 = arith.muli %194, %262 : i64
%264 = arith.addi %261, %263 : i64
%265 = arith.index_cast %225 : index to i64
%266 = llvm.getelementptr %90[%265] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %264, %266 : i64, !llvm.ptr
%267 = arith.addi %225, %217 : index
cf.br ^bb21(%267 : index)
^bb23(%268: index):
%269 = arith.addi %178, %170 : index
cf.br ^bb15(%269 : index)
^bb17(%270: index):
%272 = llvm.mlir.addressof @MAXH : !llvm.ptr
%273 = llvm.load %272 : !llvm.ptr -> i64
%274 = arith.constant 1 : i32
%276 = arith.extsi %274 : i32 to i64
%275 = arith.addi %273, %276 : i64
%277 = arith.constant 8 : i32
%279 = arith.extsi %277 : i32 to i64
%278 = arith.muli %275, %279 : i64
%271 = func.call @memcpy(%66, %82, %278) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
%281 = llvm.mlir.addressof @MAXH : !llvm.ptr
%282 = llvm.load %281 : !llvm.ptr -> i64
%283 = arith.constant 1 : i32
%285 = arith.extsi %283 : i32 to i64
%284 = arith.addi %282, %285 : i64
%286 = arith.constant 8 : i32
%288 = arith.extsi %286 : i32 to i64
%287 = arith.muli %284, %288 : i64
%280 = func.call @memcpy(%74, %90, %287) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
%289 = arith.addi %141, %133 : index
cf.br ^bb12(%289 : index)
^bb14(%290: index):
%291 = arith.constant 0 : i32
%292 = arith.extsi %291 : i32 to i64
%293 = llvm.mlir.constant(1 : i64) : i64
%294 = llvm.alloca %293 x i64 : (i64) -> !llvm.ptr
llvm.store %292, %294 : i64, !llvm.ptr
%295 = arith.constant 0 : i32
%296 = llvm.mlir.addressof @MAXH : !llvm.ptr
%297 = llvm.load %296 : !llvm.ptr -> i64
%298 = arith.constant 1 : i32
%300 = arith.extsi %298 : i32 to i64
%299 = arith.addi %297, %300 : i64
%301 = arith.index_cast %295 : i32 to index
%302 = arith.index_cast %299 : i32 to index
%304 = arith.constant 1 : index
%305 = arith.constant -1 : index
%306 = arith.cmpi sle, %301, %302 : index
%303 = arith.select %306, %304, %305 : index
cf.br ^bb27(%301 : index)
^bb27(%307: index):
%308 = arith.cmpi slt, %307, %302 : index
%309 = arith.cmpi sgt, %307, %302 : index
%310 = arith.select %306, %308, %309 : i1
cf.cond_br %310, ^bb28(%307 : index), ^bb29(%307 : index)
^bb28(%311: index):
%313 = arith.index_cast %311 : index to i64
%314 = llvm.getelementptr %66[%313] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%312 = llvm.load %314 : !llvm.ptr -> i64
%315 = arith.constant 0 : i32
%317 = arith.extsi %315 : i32 to i64
%316 = arith.cmpi eq, %312, %317 : i64
%318 = scf.if %316 -> (i1) {
%320 = arith.index_cast %311 : index to i64
%321 = llvm.getelementptr %74[%320] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%319 = llvm.load %321 : !llvm.ptr -> i64
%322 = arith.constant 0 : i32
%324 = arith.extsi %322 : i32 to i64
%323 = arith.cmpi eq, %319, %324 : i64
scf.yield %323 : i1
} else {
%325 = arith.constant false
scf.yield %325 : i1
}
cf.cond_br %318, ^bb30, ^bb31
^bb30:
%326 = arith.addi %311, %303 : index
cf.br ^bb27(%326 : index)
^bb31:
cf.br ^bb32
^bb32:
%327 = arith.constant 0 : i32
%328 = arith.extsi %327 : i32 to i64
%329 = llvm.mlir.constant(1 : i64) : i64
%330 = llvm.alloca %329 x i64 : (i64) -> !llvm.ptr
llvm.store %328, %330 : i64, !llvm.ptr
%331 = arith.constant 0 : i32
%333 = arith.index_cast %311 : index to i32
%332 = arith.cmpi sgt, %333, %331 : i32
cf.cond_br %332, ^bb33, ^bb34
^bb33:
%334 = llvm.load %3 : !llvm.ptr -> i64
%335 = llvm.load %7 : !llvm.ptr -> i64
%336 = arith.muli %334, %335 : i64
%337 = llvm.load %3 : !llvm.ptr -> i64
%338 = arith.muli %337, %23 : i64
%339 = arith.subi %336, %338 : i64
%340 = llvm.load %7 : !llvm.ptr -> i64
%342 = arith.trunci %340 : i64 to i32
%343 = arith.index_cast %311 : index to i32
%341 = arith.muli %342, %343 : i32
%345 = arith.extsi %341 : i32 to i64
%344 = arith.subi %339, %345 : i64
llvm.store %344, %330 : i64, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%346 = llvm.load %294 : !llvm.ptr -> i64
%348 = arith.index_cast %311 : index to i64
%349 = llvm.getelementptr %74[%348] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%347 = llvm.load %349 : !llvm.ptr -> i64
%350 = arith.addi %346, %347 : i64
%352 = arith.index_cast %311 : index to i64
%353 = llvm.getelementptr %66[%352] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%351 = llvm.load %353 : !llvm.ptr -> i64
%354 = llvm.load %330 : !llvm.ptr -> i64
%355 = arith.muli %351, %354 : i64
%356 = arith.addi %350, %355 : i64
llvm.store %356, %294 : i64, !llvm.ptr
%357 = arith.addi %311, %303 : index
cf.br ^bb27(%357 : index)
^bb29(%358: index):
%359 = llvm.mlir.addressof @str_0 : !llvm.ptr
%360 = llvm.load %294 : !llvm.ptr -> i64
%361 = llvm.call @printf(%359, %360) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%25) : (!llvm.ptr) -> ()
func.call @free(%66) : (!llvm.ptr) -> ()
func.call @free(%74) : (!llvm.ptr) -> ()
func.call @free(%82) : (!llvm.ptr) -> ()
func.call @free(%90) : (!llvm.ptr) -> ()
%367 = arith.constant 0 : i32
func.return %367 : i32
}
}