← All problems Problem 472
Comfortable Distance II — sum f(N) for N<=10^12, last 8 digits. Recursive bit-block prefix sums with open-address hash memo.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n)O(n)Space complexity O(n^2)O(n)Approach Flow solution Big-integer arithmetic Verdict Optimal
Flow source
# Project Euler 472
# Comfortable Distance II — sum f(N) for N<=10^12, last 8 digits.
# Recursive bit-block prefix sums with open-address hash memo.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 100000000
const BASE: i64 = 64
const MEMO_CAP: i64 = 200003
let mut G_fbase: ptr<i64> = null
let mut G_pref: ptr<i64> = null
let mut G_memo_k: ptr<i64> = null
let mut G_memo_v: ptr<i64> = null
let mut G_memo_u: ptr<i8> = null
function bit_length(n0: i64) -> i32 {
let mut n: i64 = n0
let mut b: i32 = 0
while n > 0 {
b = b + 1
n = n / 2
}
if b == 0 { return 1 }
return b
}
function A_seg(n: i64) -> i64 {
if n <= 0 { return 0 }
let t: i64 = n + 1
let p: i64 = (1 as i64) << (bit_length(t) - 1)
let a: i64 = p >> 1
let b: i64 = t - p
if a > b { return a }
return b
}
function brute_f(N: i64) -> i64 {
if N == 1 { return 1 }
if N == 2 { return 2 }
let edge: i64 = A_seg(N - 2)
let M: i64 = N - 3
let mut best: i64 = -1
let mut cnt: i64 = 0
let mut x: i64 = 0
while x <= M {
let val: i64 = A_seg(x) + A_seg(M - x)
if val > best {
best = val
cnt = 1
} else {
if val == best {
cnt = cnt + 1
}
}
x = x + 1
}
let mut mx: i64 = best
if edge > mx { mx = edge }
let mut ans: i64 = 0
if edge == mx { ans = ans + 2 }
if best == mx { ans = ans + cnt }
return ans
}
function mod_norm(x: i128) -> i64 {
let mut r: i64 = (x % (MOD as i128)) as i64
if r < 0 { r = r + MOD }
return r
}
function prefix_sum_11_block(half: i64, length0: i64) -> i64 {
if length0 <= 0 { return 0 }
let k: i32 = bit_length(half) - 1
if k < 3 {
let mut s: i64 = 0
let start: i64 = 3 * half
let mut n: i64 = 0
while n < length0 {
s = s + brute_f(start + n)
n = n + 1
}
return s % MOD
}
let m: i64 = half >> 1
let mut length: i64 = length0
let mut s: i128 = 0
let mut j: i64 = 0
s = s + 4
length = length - 1
if length == 0 { return mod_norm(s) }
let mut take: i64 = m
if length < take { take = length }
s = s + (take as i128) * ((take + 1) as i128)
length = length - take
j = j + take
if length == 0 { return mod_norm(s) }
if j == m {
s = s + (3 * m + 3) as i128
length = length - 1
j = j + 1
if length == 0 { return mod_norm(s) }
}
let a1: i64 = m + 2
let cnt: i64 = length
s = s + (cnt as i128) * ((2 * a1 - (cnt - 1)) as i128) / 2
return mod_norm(s)
}
function memo_get(N: i64, out: ptr<i64>) -> bool {
let mut slot: i64 = (N % MEMO_CAP + MEMO_CAP) % MEMO_CAP
while G_memo_u[slot] != 0 {
if G_memo_k[slot] == N {
out[0] = G_memo_v[slot]
return true
}
slot = slot + 1
if slot == MEMO_CAP { slot = 0 }
}
out[0] = slot
return false
}
function memo_put(N: i64, slot: i64, val: i64) -> void {
G_memo_u[slot] = 1
G_memo_k[slot] = N
G_memo_v[slot] = val
}
function sum_upto(N: i64) -> i64 {
if N <= 0 { return 0 }
if N <= BASE { return G_pref[N] % MOD }
let slot_or_val: ptr<i64> = calloc(1, 8)
if slot_or_val == null { return 0 }
if memo_get(N, slot_or_val) {
let v: i64 = slot_or_val[0]
free(slot_or_val)
return v
}
let slot: i64 = slot_or_val[0]
free(slot_or_val)
let pow2: i64 = (1 as i64) << (bit_length(N) - 1)
let half: i64 = pow2 >> 1
let split: i64 = pow2 + half
let mut res: i64 = sum_upto(pow2 - 1)
if N < split {
let u_max: i64 = N - pow2
let mut mapped_sum: i64 = sum_upto(half + u_max) - sum_upto(half - 1)
mapped_sum = mapped_sum % MOD
if mapped_sum < 0 { mapped_sum = mapped_sum + MOD }
let k: i32 = bit_length(half) - 1
if k >= 4 {
let u0: i64 = half - (half >> 2) + 1
if u_max >= u0 {
let a: i64 = u0
let b: i64 = u_max
let cnt: i64 = b - a + 1
let corr: i128 = (cnt as i128) * (half as i128) - ((a + b) as i128) * (cnt as i128) / 2
mapped_sum = mod_norm((mapped_sum as i128) + corr)
}
}
res = (res + mapped_sum) % MOD
memo_put(N, slot, res)
return res
}
let mut sum_small: i64 = sum_upto(pow2 - 1) - sum_upto(half - 1)
sum_small = sum_small % MOD
if sum_small < 0 { sum_small = sum_small + MOD }
let k2: i32 = bit_length(half) - 1
let mut sum10: i64 = 0
if k2 >= 4 {
let tail_len: i64 = (half >> 2) - 1
let corr_full: i128 = (tail_len as i128) * ((tail_len + 1) as i128) / 2
sum10 = mod_norm((sum_small as i128) + corr_full)
} else {
let mut n: i64 = pow2
while n < split {
sum10 = sum10 + brute_f(n)
n = n + 1
}
sum10 = sum10 % MOD
}
res = (res + sum10) % MOD
let len11: i64 = N - split + 1
res = (res + prefix_sum_11_block(half, len11)) % MOD
memo_put(N, slot, res)
return res
}
function main() -> i32 {
G_fbase = calloc(BASE + 1, 8)
G_pref = calloc(BASE + 1, 8)
G_memo_k = calloc(MEMO_CAP, 8)
G_memo_v = calloc(MEMO_CAP, 8)
G_memo_u = calloc(MEMO_CAP, 1)
if G_fbase == null || G_pref == null || G_memo_k == null || G_memo_v == null || G_memo_u == null {
return 1
}
let mut n: i64 = 1
while n <= BASE {
G_fbase[n] = brute_f(n)
G_pref[n] = G_pref[n - 1] + G_fbase[n]
n = n + 1
}
let LIMIT: i64 = 1000000000000
let ans: i64 = sum_upto(LIMIT) % MOD
printf("%lld\n", ans)
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 bit_length_i64(int64_t n0);
int64_t A_seg_i64(int64_t n);
int64_t brute_f_i64(int64_t N);
int64_t mod_norm_i128(__int128 x);
int64_t prefix_sum_11_block_i64_i64(int64_t half, int64_t length0);
bool memo_get_i64_ptr_i64(int64_t N, int64_t* out);
void memo_put_i64_i64_i64(int64_t N, int64_t slot, int64_t val);
int64_t sum_upto_i64(int64_t N);
int32_t main(void);
static const int64_t MOD = 100000000;
static const int64_t BASE = 64;
static const int64_t MEMO_CAP = 200003;
/* Module statics */
static int64_t* G_fbase = NULL;
static int64_t* G_pref = NULL;
static int64_t* G_memo_k = NULL;
static int64_t* G_memo_v = NULL;
static int8_t* G_memo_u = NULL;
int32_t bit_length_i64(int64_t n0) {
int64_t n = n0;
int32_t b = 0;
while (n > 0) {
b = (b + 1);
n = FLOW_CHECKED_DIV((n), (2));
}
if (b == 0) {
return 1;
}
return b;
}
int64_t A_seg_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t t = (n + 1);
int64_t p = FLOW_CHECKED_SHL((((int64_t)(1))), ((bit_length_i64(t) - 1)));
int64_t a = FLOW_CHECKED_SHR((p), (1));
int64_t b = (t - p);
if (a > b) {
return a;
}
return b;
}
int64_t brute_f_i64(int64_t N) {
if (N == 1) {
return 1;
}
if (N == 2) {
return 2;
}
int64_t edge = A_seg_i64((N - 2));
int64_t M = (N - 3);
int64_t best = (-1);
int64_t cnt = 0;
int64_t x = 0;
while (x <= M) {
int64_t val = (A_seg_i64(x) + A_seg_i64((M - x)));
if (val > best) {
best = val;
cnt = 1;
} else {
if (val == best) {
cnt = (cnt + 1);
}
}
x = (x + 1);
}
int64_t mx = best;
if (edge > mx) {
mx = edge;
}
int64_t ans = 0;
if (edge == mx) {
ans = (ans + 2);
}
if (best == mx) {
ans = (ans + cnt);
}
return ans;
}
int64_t mod_norm_i128(__int128 x) {
int64_t r = ((int64_t)(FLOW_CHECKED_MOD((x), (((__int128)(MOD))))));
if (r < 0) {
r = (r + MOD);
}
return r;
}
int64_t prefix_sum_11_block_i64_i64(int64_t half, int64_t length0) {
if (length0 <= 0) {
return 0;
}
int32_t k = (bit_length_i64(half) - 1);
if (k < 3) {
int64_t s = 0;
int64_t start = (3 * half);
int64_t n = 0;
while (n < length0) {
s = (s + brute_f_i64((start + n)));
n = (n + 1);
}
return FLOW_CHECKED_MOD((s), (MOD));
}
int64_t m = FLOW_CHECKED_SHR((half), (1));
int64_t length = length0;
__int128 s = 0;
int64_t j = 0;
s = (s + 4);
length = (length - 1);
if (length == 0) {
return mod_norm_i128(s);
}
int64_t take = m;
if (length < take) {
take = length;
}
s = (s + (((__int128)(take)) * ((__int128)((take + 1)))));
length = (length - take);
j = (j + take);
if (length == 0) {
return mod_norm_i128(s);
}
if (j == m) {
s = (s + ((__int128)(((3 * m) + 3))));
length = (length - 1);
j = (j + 1);
if (length == 0) {
return mod_norm_i128(s);
}
}
int64_t a1 = (m + 2);
int64_t cnt = length;
s = (s + FLOW_CHECKED_DIV(((((__int128)(cnt)) * ((__int128)(((2 * a1) - (cnt - 1)))))), (2)));
return mod_norm_i128(s);
}
bool memo_get_i64_ptr_i64(int64_t N, int64_t* out) {
int64_t slot = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((N), (MEMO_CAP)) + MEMO_CAP)), (MEMO_CAP));
while (G_memo_u[slot] != 0) {
if (G_memo_k[slot] == N) {
out[0] = G_memo_v[slot];
return 1;
}
slot = (slot + 1);
if (slot == MEMO_CAP) {
slot = 0;
}
}
out[0] = slot;
return 0;
}
void memo_put_i64_i64_i64(int64_t N, int64_t slot, int64_t val) {
G_memo_u[slot] = 1;
G_memo_k[slot] = N;
G_memo_v[slot] = val;
}
int64_t sum_upto_i64(int64_t N) {
if (N <= 0) {
return 0;
}
if (N <= BASE) {
return FLOW_CHECKED_MOD((G_pref[N]), (MOD));
}
int64_t* slot_or_val = (int64_t*)(calloc(1, 8));
if (slot_or_val == NULL) {
return 0;
}
if (memo_get_i64_ptr_i64(N, slot_or_val)) {
int64_t v = slot_or_val[0];
free(slot_or_val);
return v;
}
int64_t slot = slot_or_val[0];
free(slot_or_val);
int64_t pow2 = FLOW_CHECKED_SHL((((int64_t)(1))), ((bit_length_i64(N) - 1)));
int64_t half = FLOW_CHECKED_SHR((pow2), (1));
int64_t split = (pow2 + half);
int64_t res = sum_upto_i64((pow2 - 1));
if (N < split) {
int64_t u_max = (N - pow2);
int64_t mapped_sum = (sum_upto_i64((half + u_max)) - sum_upto_i64((half - 1)));
mapped_sum = FLOW_CHECKED_MOD((mapped_sum), (MOD));
if (mapped_sum < 0) {
mapped_sum = (mapped_sum + MOD);
}
int32_t k = (bit_length_i64(half) - 1);
if (k >= 4) {
int64_t u0 = ((half - FLOW_CHECKED_SHR((half), (2))) + 1);
if (u_max >= u0) {
int64_t a = u0;
int64_t b = u_max;
int64_t cnt = ((b - a) + 1);
__int128 corr = ((((__int128)(cnt)) * ((__int128)(half))) - FLOW_CHECKED_DIV(((((__int128)((a + b))) * ((__int128)(cnt)))), (2)));
mapped_sum = mod_norm_i128((((__int128)(mapped_sum)) + corr));
}
}
res = FLOW_CHECKED_MOD(((res + mapped_sum)), (MOD));
memo_put_i64_i64_i64(N, slot, res);
return res;
}
int64_t sum_small = (sum_upto_i64((pow2 - 1)) - sum_upto_i64((half - 1)));
sum_small = FLOW_CHECKED_MOD((sum_small), (MOD));
if (sum_small < 0) {
sum_small = (sum_small + MOD);
}
int32_t k2 = (bit_length_i64(half) - 1);
int64_t sum10 = 0;
if (k2 >= 4) {
int64_t tail_len = (FLOW_CHECKED_SHR((half), (2)) - 1);
__int128 corr_full = FLOW_CHECKED_DIV(((((__int128)(tail_len)) * ((__int128)((tail_len + 1))))), (2));
sum10 = mod_norm_i128((((__int128)(sum_small)) + corr_full));
} else {
int64_t n = pow2;
while (n < split) {
sum10 = (sum10 + brute_f_i64(n));
n = (n + 1);
}
sum10 = FLOW_CHECKED_MOD((sum10), (MOD));
}
res = FLOW_CHECKED_MOD(((res + sum10)), (MOD));
int64_t len11 = ((N - split) + 1);
res = FLOW_CHECKED_MOD(((res + prefix_sum_11_block_i64_i64(half, len11))), (MOD));
memo_put_i64_i64_i64(N, slot, res);
return res;
}
int32_t main(void) {
G_fbase = calloc((BASE + 1), 8);
G_pref = calloc((BASE + 1), 8);
G_memo_k = calloc(MEMO_CAP, 8);
G_memo_v = calloc(MEMO_CAP, 8);
G_memo_u = calloc(MEMO_CAP, 1);
if (((((G_fbase == NULL || G_pref == NULL) || G_memo_k == NULL) || G_memo_v == NULL) || G_memo_u == NULL)) {
return 1;
}
int64_t n = 1;
while (n <= BASE) {
G_fbase[n] = brute_f_i64(n);
G_pref[n] = (G_pref[(n - 1)] + G_fbase[n]);
n = (n + 1);
}
int64_t LIMIT = 1000000000000;
int64_t ans = FLOW_CHECKED_MOD((sum_upto_i64(LIMIT)), (MOD));
printf("%lld\n", 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) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(100000000 : i64) : i64
// Constant: BASE
llvm.mlir.global internal constant @BASE(64 : i64) : i64
// Constant: MEMO_CAP
llvm.mlir.global internal constant @MEMO_CAP(200003 : i64) : i64
// Module static: G_fbase
llvm.mlir.global internal @G_fbase() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: G_pref
llvm.mlir.global internal @G_pref() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
// Module static: G_memo_k
llvm.mlir.global internal @G_memo_k() {addr_space = 0 : i32} : !llvm.ptr {
%2 = llvm.mlir.zero : !llvm.ptr
llvm.return %2 : !llvm.ptr
}
// Module static: G_memo_v
llvm.mlir.global internal @G_memo_v() {addr_space = 0 : i32} : !llvm.ptr {
%3 = llvm.mlir.zero : !llvm.ptr
llvm.return %3 : !llvm.ptr
}
// Module static: G_memo_u
llvm.mlir.global internal @G_memo_u() {addr_space = 0 : i32} : !llvm.ptr {
%4 = llvm.mlir.zero : !llvm.ptr
llvm.return %4 : !llvm.ptr
}
func.func @bit_length(%arg0: i64) -> i32 {
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %6 : i64, !llvm.ptr
%7 = arith.constant 0 : i32
%8 = llvm.mlir.constant(1 : i64) : i64
%9 = llvm.alloca %8 x i32 : (i64) -> !llvm.ptr
llvm.store %7, %9 : i32, !llvm.ptr
cf.br ^bb0
^bb0:
%10 = llvm.load %6 : !llvm.ptr -> i64
%11 = arith.constant 0 : i32
%13 = arith.extsi %11 : i32 to i64
%12 = arith.cmpi sgt, %10, %13 : i64
cf.cond_br %12, ^bb1, ^bb2
^bb1:
%14 = llvm.load %9 : !llvm.ptr -> i32
%15 = arith.constant 1 : i32
%16 = arith.addi %14, %15 : i32
llvm.store %16, %9 : i32, !llvm.ptr
%17 = llvm.load %6 : !llvm.ptr -> i64
%18 = arith.constant 2 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.divsi %17, %20 : i64
llvm.store %19, %6 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%21 = llvm.load %9 : !llvm.ptr -> i32
%22 = arith.constant 0 : i32
%23 = arith.cmpi eq, %21, %22 : i32
cf.cond_br %23, ^bb3, ^bb4
^bb3:
%24 = arith.constant 1 : i32
func.return %24 : i32
^bb4:
cf.br ^bb5
^bb5:
%25 = llvm.load %9 : !llvm.ptr -> i32
func.return %25 : i32
}
func.func @A_seg(%arg0: i64) -> i64 {
%26 = arith.constant 0 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.cmpi sle, %arg0, %28 : i64
cf.cond_br %27, ^bb6, ^bb7
^bb6:
%29 = arith.constant 0 : i32
%30 = arith.extsi %29 : i32 to i64
func.return %30 : i64
^bb7:
cf.br ^bb8
^bb8:
%31 = arith.constant 1 : i32
%33 = arith.extsi %31 : i32 to i64
%32 = arith.addi %arg0, %33 : i64
%34 = arith.constant 1 : i32
%35 = arith.extsi %34 : i32 to i64
%36 = func.call @bit_length(%32) : (i64) -> i32
%37 = arith.constant 1 : i32
%38 = arith.subi %36, %37 : i32
%40 = arith.extsi %38 : i32 to i64
%39 = arith.shli %35, %40 : i64
%41 = arith.constant 1 : i32
%43 = arith.extsi %41 : i32 to i64
%42 = arith.shrsi %39, %43 : i64
%44 = arith.subi %32, %39 : i64
%45 = arith.cmpi sgt, %42, %44 : i64
cf.cond_br %45, ^bb9, ^bb10
^bb9:
func.return %42 : i64
^bb10:
cf.br ^bb11
^bb11:
func.return %44 : i64
}
func.func @brute_f(%arg0: i64) -> i64 {
%46 = arith.constant 1 : i32
%48 = arith.extsi %46 : i32 to i64
%47 = arith.cmpi eq, %arg0, %48 : i64
cf.cond_br %47, ^bb12, ^bb13
^bb12:
%49 = arith.constant 1 : i32
%50 = arith.extsi %49 : i32 to i64
func.return %50 : i64
^bb13:
cf.br ^bb14
^bb14:
%51 = arith.constant 2 : i32
%53 = arith.extsi %51 : i32 to i64
%52 = arith.cmpi eq, %arg0, %53 : i64
cf.cond_br %52, ^bb15, ^bb16
^bb15:
%54 = arith.constant 2 : i32
%55 = arith.extsi %54 : i32 to i64
func.return %55 : i64
^bb16:
cf.br ^bb17
^bb17:
%57 = arith.constant 2 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.subi %arg0, %59 : i64
%56 = func.call @A_seg(%58) : (i64) -> i64
%60 = arith.constant 3 : i32
%62 = arith.extsi %60 : i32 to i64
%61 = arith.subi %arg0, %62 : i64
%63 = arith.constant 1 : i32
%65 = arith.constant 0 : i32
%64 = arith.subi %65, %63 : i32
%66 = arith.extsi %64 : i32 to i64
%67 = llvm.mlir.constant(1 : i64) : i64
%68 = llvm.alloca %67 x i64 : (i64) -> !llvm.ptr
llvm.store %66, %68 : i64, !llvm.ptr
%69 = arith.constant 0 : i32
%70 = arith.extsi %69 : i32 to i64
%71 = llvm.mlir.constant(1 : i64) : i64
%72 = llvm.alloca %71 x i64 : (i64) -> !llvm.ptr
llvm.store %70, %72 : i64, !llvm.ptr
%73 = arith.constant 0 : i32
%74 = arith.extsi %73 : i32 to i64
%75 = llvm.mlir.constant(1 : i64) : i64
%76 = llvm.alloca %75 x i64 : (i64) -> !llvm.ptr
llvm.store %74, %76 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%77 = llvm.load %76 : !llvm.ptr -> i64
%78 = arith.cmpi sle, %77, %61 : i64
cf.cond_br %78, ^bb19, ^bb20
^bb19:
%80 = llvm.load %76 : !llvm.ptr -> i64
%79 = func.call @A_seg(%80) : (i64) -> i64
%82 = llvm.load %76 : !llvm.ptr -> i64
%83 = arith.subi %61, %82 : i64
%81 = func.call @A_seg(%83) : (i64) -> i64
%84 = arith.addi %79, %81 : i64
%85 = llvm.load %68 : !llvm.ptr -> i64
%86 = arith.cmpi sgt, %84, %85 : i64
cf.cond_br %86, ^bb21, ^bb22
^bb21:
llvm.store %84, %68 : i64, !llvm.ptr
%87 = arith.constant 1 : i32
%88 = arith.extsi %87 : i32 to i64
llvm.store %88, %72 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
%89 = llvm.load %68 : !llvm.ptr -> i64
%90 = arith.cmpi eq, %84, %89 : i64
cf.cond_br %90, ^bb24, ^bb25
^bb24:
%91 = llvm.load %72 : !llvm.ptr -> i64
%92 = arith.constant 1 : i32
%94 = arith.extsi %92 : i32 to i64
%93 = arith.addi %91, %94 : i64
llvm.store %93, %72 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
cf.br ^bb23
^bb23:
%95 = llvm.load %76 : !llvm.ptr -> i64
%96 = arith.constant 1 : i32
%98 = arith.extsi %96 : i32 to i64
%97 = arith.addi %95, %98 : i64
llvm.store %97, %76 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%99 = llvm.load %68 : !llvm.ptr -> i64
%100 = llvm.mlir.constant(1 : i64) : i64
%101 = llvm.alloca %100 x i64 : (i64) -> !llvm.ptr
llvm.store %99, %101 : i64, !llvm.ptr
%102 = llvm.load %101 : !llvm.ptr -> i64
%103 = arith.cmpi sgt, %56, %102 : i64
cf.cond_br %103, ^bb27, ^bb28
^bb27:
llvm.store %56, %101 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%104 = arith.constant 0 : i32
%105 = arith.extsi %104 : i32 to i64
%106 = llvm.mlir.constant(1 : i64) : i64
%107 = llvm.alloca %106 x i64 : (i64) -> !llvm.ptr
llvm.store %105, %107 : i64, !llvm.ptr
%108 = llvm.load %101 : !llvm.ptr -> i64
%109 = arith.cmpi eq, %56, %108 : i64
cf.cond_br %109, ^bb30, ^bb31
^bb30:
%110 = llvm.load %107 : !llvm.ptr -> i64
%111 = arith.constant 2 : i32
%113 = arith.extsi %111 : i32 to i64
%112 = arith.addi %110, %113 : i64
llvm.store %112, %107 : i64, !llvm.ptr
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%114 = llvm.load %68 : !llvm.ptr -> i64
%115 = llvm.load %101 : !llvm.ptr -> i64
%116 = arith.cmpi eq, %114, %115 : i64
cf.cond_br %116, ^bb33, ^bb34
^bb33:
%117 = llvm.load %107 : !llvm.ptr -> i64
%118 = llvm.load %72 : !llvm.ptr -> i64
%119 = arith.addi %117, %118 : i64
llvm.store %119, %107 : i64, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%120 = llvm.load %107 : !llvm.ptr -> i64
func.return %120 : i64
}
func.func @mod_norm(%arg0: i128) -> i64 {
%121 = llvm.mlir.addressof @MOD : !llvm.ptr
%122 = llvm.load %121 : !llvm.ptr -> i64
%123 = arith.extsi %122 : i64 to i128
%125 = arith.trunci %arg0 : i128 to i64
%126 = arith.trunci %123 : i128 to i64
%124 = arith.remsi %125, %126 : i64
%127 = llvm.mlir.constant(1 : i64) : i64
%128 = llvm.alloca %127 x i64 : (i64) -> !llvm.ptr
llvm.store %124, %128 : i64, !llvm.ptr
%129 = llvm.load %128 : !llvm.ptr -> i64
%130 = arith.constant 0 : i32
%132 = arith.extsi %130 : i32 to i64
%131 = arith.cmpi slt, %129, %132 : i64
cf.cond_br %131, ^bb36, ^bb37
^bb36:
%133 = llvm.load %128 : !llvm.ptr -> i64
%134 = llvm.mlir.addressof @MOD : !llvm.ptr
%135 = llvm.load %134 : !llvm.ptr -> i64
%136 = arith.addi %133, %135 : i64
llvm.store %136, %128 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%137 = llvm.load %128 : !llvm.ptr -> i64
func.return %137 : i64
}
func.func @prefix_sum_11_block(%arg0: i64, %arg1: i64) -> i64 {
%138 = arith.constant 0 : i32
%140 = arith.extsi %138 : i32 to i64
%139 = arith.cmpi sle, %arg1, %140 : i64
cf.cond_br %139, ^bb39, ^bb40
^bb39:
%141 = arith.constant 0 : i32
%142 = arith.extsi %141 : i32 to i64
func.return %142 : i64
^bb40:
cf.br ^bb41
^bb41:
%143 = func.call @bit_length(%arg0) : (i64) -> i32
%144 = arith.constant 1 : i32
%145 = arith.subi %143, %144 : i32
%146 = arith.constant 3 : i32
%147 = arith.cmpi slt, %145, %146 : i32
cf.cond_br %147, ^bb42, ^bb43
^bb42:
%148 = arith.constant 0 : i32
%149 = arith.extsi %148 : i32 to i64
%150 = llvm.mlir.constant(1 : i64) : i64
%151 = llvm.alloca %150 x i64 : (i64) -> !llvm.ptr
llvm.store %149, %151 : i64, !llvm.ptr
%152 = arith.constant 3 : i32
%154 = arith.extsi %152 : i32 to i64
%153 = arith.muli %154, %arg0 : i64
%155 = arith.constant 0 : 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
cf.br ^bb45
^bb45:
%159 = llvm.load %158 : !llvm.ptr -> i64
%160 = arith.cmpi slt, %159, %arg1 : i64
cf.cond_br %160, ^bb46, ^bb47
^bb46:
%161 = llvm.load %151 : !llvm.ptr -> i64
%163 = llvm.load %158 : !llvm.ptr -> i64
%164 = arith.addi %153, %163 : i64
%162 = func.call @brute_f(%164) : (i64) -> i64
%165 = arith.addi %161, %162 : i64
llvm.store %165, %151 : i64, !llvm.ptr
%166 = llvm.load %158 : !llvm.ptr -> i64
%167 = arith.constant 1 : i32
%169 = arith.extsi %167 : i32 to i64
%168 = arith.addi %166, %169 : i64
llvm.store %168, %158 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%170 = llvm.load %151 : !llvm.ptr -> i64
%171 = llvm.mlir.addressof @MOD : !llvm.ptr
%172 = llvm.load %171 : !llvm.ptr -> i64
%173 = arith.remsi %170, %172 : i64
func.return %173 : i64
^bb43:
cf.br ^bb44
^bb44:
%174 = arith.constant 1 : i32
%176 = arith.extsi %174 : i32 to i64
%175 = arith.shrsi %arg0, %176 : i64
%177 = llvm.mlir.constant(1 : i64) : i64
%178 = llvm.alloca %177 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %178 : i64, !llvm.ptr
%179 = arith.constant 0 : i32
%180 = arith.extsi %179 : i32 to i128
%181 = llvm.mlir.constant(1 : i64) : i64
%182 = llvm.alloca %181 x i128 : (i64) -> !llvm.ptr
llvm.store %180, %182 : i128, !llvm.ptr
%183 = arith.constant 0 : i32
%184 = arith.extsi %183 : i32 to i64
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x i64 : (i64) -> !llvm.ptr
llvm.store %184, %186 : i64, !llvm.ptr
%187 = llvm.load %182 : !llvm.ptr -> i128
%188 = arith.constant 4 : i32
%190 = arith.trunci %187 : i128 to i64
%191 = arith.extsi %188 : i32 to i64
%189 = arith.addi %190, %191 : i64
%192 = arith.extsi %189 : i64 to i128
llvm.store %192, %182 : i128, !llvm.ptr
%193 = llvm.load %178 : !llvm.ptr -> i64
%194 = arith.constant 1 : i32
%196 = arith.extsi %194 : i32 to i64
%195 = arith.subi %193, %196 : i64
llvm.store %195, %178 : i64, !llvm.ptr
%197 = llvm.load %178 : !llvm.ptr -> i64
%198 = arith.constant 0 : i32
%200 = arith.extsi %198 : i32 to i64
%199 = arith.cmpi eq, %197, %200 : i64
cf.cond_br %199, ^bb48, ^bb49
^bb48:
%202 = llvm.load %182 : !llvm.ptr -> i128
%201 = func.call @mod_norm(%202) : (i128) -> i64
func.return %201 : i64
^bb49:
cf.br ^bb50
^bb50:
%203 = llvm.mlir.constant(1 : i64) : i64
%204 = llvm.alloca %203 x i64 : (i64) -> !llvm.ptr
llvm.store %175, %204 : i64, !llvm.ptr
%205 = llvm.load %178 : !llvm.ptr -> i64
%206 = llvm.load %204 : !llvm.ptr -> i64
%207 = arith.cmpi slt, %205, %206 : i64
cf.cond_br %207, ^bb51, ^bb52
^bb51:
%208 = llvm.load %178 : !llvm.ptr -> i64
llvm.store %208, %204 : i64, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
%209 = llvm.load %182 : !llvm.ptr -> i128
%210 = llvm.load %204 : !llvm.ptr -> i64
%211 = arith.extsi %210 : i64 to i128
%212 = llvm.load %204 : !llvm.ptr -> i64
%213 = arith.constant 1 : i32
%215 = arith.extsi %213 : i32 to i64
%214 = arith.addi %212, %215 : i64
%216 = arith.extsi %214 : i64 to i128
%218 = arith.trunci %211 : i128 to i64
%219 = arith.trunci %216 : i128 to i64
%217 = arith.muli %218, %219 : i64
%221 = arith.trunci %209 : i128 to i64
%220 = arith.addi %221, %217 : i64
%222 = arith.extsi %220 : i64 to i128
llvm.store %222, %182 : i128, !llvm.ptr
%223 = llvm.load %178 : !llvm.ptr -> i64
%224 = llvm.load %204 : !llvm.ptr -> i64
%225 = arith.subi %223, %224 : i64
llvm.store %225, %178 : i64, !llvm.ptr
%226 = llvm.load %186 : !llvm.ptr -> i64
%227 = llvm.load %204 : !llvm.ptr -> i64
%228 = arith.addi %226, %227 : i64
llvm.store %228, %186 : i64, !llvm.ptr
%229 = llvm.load %178 : !llvm.ptr -> i64
%230 = arith.constant 0 : i32
%232 = arith.extsi %230 : i32 to i64
%231 = arith.cmpi eq, %229, %232 : i64
cf.cond_br %231, ^bb54, ^bb55
^bb54:
%234 = llvm.load %182 : !llvm.ptr -> i128
%233 = func.call @mod_norm(%234) : (i128) -> i64
func.return %233 : i64
^bb55:
cf.br ^bb56
^bb56:
%235 = llvm.load %186 : !llvm.ptr -> i64
%236 = arith.cmpi eq, %235, %175 : i64
cf.cond_br %236, ^bb57, ^bb58
^bb57:
%237 = llvm.load %182 : !llvm.ptr -> i128
%238 = arith.constant 3 : i32
%240 = arith.extsi %238 : i32 to i64
%239 = arith.muli %240, %175 : i64
%241 = arith.constant 3 : i32
%243 = arith.extsi %241 : i32 to i64
%242 = arith.addi %239, %243 : i64
%244 = arith.extsi %242 : i64 to i128
%246 = arith.trunci %237 : i128 to i64
%247 = arith.trunci %244 : i128 to i64
%245 = arith.addi %246, %247 : i64
%248 = arith.extsi %245 : i64 to i128
llvm.store %248, %182 : i128, !llvm.ptr
%249 = llvm.load %178 : !llvm.ptr -> i64
%250 = arith.constant 1 : i32
%252 = arith.extsi %250 : i32 to i64
%251 = arith.subi %249, %252 : i64
llvm.store %251, %178 : i64, !llvm.ptr
%253 = llvm.load %186 : !llvm.ptr -> i64
%254 = arith.constant 1 : i32
%256 = arith.extsi %254 : i32 to i64
%255 = arith.addi %253, %256 : i64
llvm.store %255, %186 : i64, !llvm.ptr
%257 = llvm.load %178 : !llvm.ptr -> i64
%258 = arith.constant 0 : i32
%260 = arith.extsi %258 : i32 to i64
%259 = arith.cmpi eq, %257, %260 : i64
cf.cond_br %259, ^bb60, ^bb61
^bb60:
%262 = llvm.load %182 : !llvm.ptr -> i128
%261 = func.call @mod_norm(%262) : (i128) -> i64
func.return %261 : i64
^bb61:
cf.br ^bb62
^bb62:
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%263 = arith.constant 2 : i32
%265 = arith.extsi %263 : i32 to i64
%264 = arith.addi %175, %265 : i64
%266 = llvm.load %178 : !llvm.ptr -> i64
%267 = llvm.load %182 : !llvm.ptr -> i128
%268 = arith.extsi %266 : i64 to i128
%269 = arith.constant 2 : i32
%271 = arith.extsi %269 : i32 to i64
%270 = arith.muli %271, %264 : i64
%272 = arith.constant 1 : i32
%274 = arith.extsi %272 : i32 to i64
%273 = arith.subi %266, %274 : i64
%275 = arith.subi %270, %273 : i64
%276 = arith.extsi %275 : i64 to i128
%278 = arith.trunci %268 : i128 to i64
%279 = arith.trunci %276 : i128 to i64
%277 = arith.muli %278, %279 : i64
%280 = arith.constant 2 : i32
%282 = arith.extsi %280 : i32 to i64
%281 = arith.divsi %277, %282 : i64
%284 = arith.trunci %267 : i128 to i64
%283 = arith.addi %284, %281 : i64
%285 = arith.extsi %283 : i64 to i128
llvm.store %285, %182 : i128, !llvm.ptr
%287 = llvm.load %182 : !llvm.ptr -> i128
%286 = func.call @mod_norm(%287) : (i128) -> i64
func.return %286 : i64
}
func.func @memo_get(%arg0: i64, %arg1: !llvm.ptr) -> i1 {
%288 = llvm.mlir.addressof @MEMO_CAP : !llvm.ptr
%289 = llvm.load %288 : !llvm.ptr -> i64
%290 = arith.remsi %arg0, %289 : i64
%291 = llvm.mlir.addressof @MEMO_CAP : !llvm.ptr
%292 = llvm.load %291 : !llvm.ptr -> i64
%293 = arith.addi %290, %292 : i64
%294 = llvm.mlir.addressof @MEMO_CAP : !llvm.ptr
%295 = llvm.load %294 : !llvm.ptr -> i64
%296 = arith.remsi %293, %295 : i64
%297 = llvm.mlir.constant(1 : i64) : i64
%298 = llvm.alloca %297 x i64 : (i64) -> !llvm.ptr
llvm.store %296, %298 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%300 = llvm.mlir.addressof @G_memo_u : !llvm.ptr
%301 = llvm.load %300 : !llvm.ptr -> !llvm.ptr
%302 = llvm.load %298 : !llvm.ptr -> i64
%303 = llvm.getelementptr %301[%302] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%299 = llvm.load %303 : !llvm.ptr -> i8
%304 = arith.constant 0 : i32
%306 = arith.extsi %299 : i8 to i32
%305 = arith.cmpi ne, %306, %304 : i32
cf.cond_br %305, ^bb64, ^bb65
^bb64:
%308 = llvm.mlir.addressof @G_memo_k : !llvm.ptr
%309 = llvm.load %308 : !llvm.ptr -> !llvm.ptr
%310 = llvm.load %298 : !llvm.ptr -> i64
%311 = llvm.getelementptr %309[%310] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%307 = llvm.load %311 : !llvm.ptr -> i64
%312 = arith.cmpi eq, %307, %arg0 : i64
cf.cond_br %312, ^bb66, ^bb67
^bb66:
%314 = llvm.mlir.addressof @G_memo_v : !llvm.ptr
%315 = llvm.load %314 : !llvm.ptr -> !llvm.ptr
%316 = llvm.load %298 : !llvm.ptr -> i64
%317 = llvm.getelementptr %315[%316] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%313 = llvm.load %317 : !llvm.ptr -> i64
%318 = arith.constant 0 : i32
%319 = arith.extsi %318 : i32 to i64
%320 = llvm.getelementptr %arg1[%319] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %313, %320 : i64, !llvm.ptr
%321 = arith.constant 1 : i1
func.return %321 : i1
^bb67:
cf.br ^bb68
^bb68:
%322 = llvm.load %298 : !llvm.ptr -> i64
%323 = arith.constant 1 : i32
%325 = arith.extsi %323 : i32 to i64
%324 = arith.addi %322, %325 : i64
llvm.store %324, %298 : i64, !llvm.ptr
%326 = llvm.load %298 : !llvm.ptr -> i64
%327 = llvm.mlir.addressof @MEMO_CAP : !llvm.ptr
%328 = llvm.load %327 : !llvm.ptr -> i64
%329 = arith.cmpi eq, %326, %328 : i64
cf.cond_br %329, ^bb69, ^bb70
^bb69:
%330 = arith.constant 0 : i32
%331 = arith.extsi %330 : i32 to i64
llvm.store %331, %298 : i64, !llvm.ptr
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
cf.br ^bb63
^bb65:
%332 = llvm.load %298 : !llvm.ptr -> i64
%333 = arith.constant 0 : i32
%334 = arith.extsi %333 : i32 to i64
%335 = llvm.getelementptr %arg1[%334] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %332, %335 : i64, !llvm.ptr
%336 = arith.constant 0 : i1
func.return %336 : i1
}
func.func @memo_put(%arg0: i64, %arg1: i64, %arg2: i64) -> () {
%337 = arith.constant 1 : i32
%338 = llvm.mlir.addressof @G_memo_u : !llvm.ptr
%339 = llvm.load %338 : !llvm.ptr -> !llvm.ptr
%340 = arith.trunci %337 : i32 to i8
%341 = llvm.getelementptr %339[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %340, %341 : i8, !llvm.ptr
%342 = llvm.mlir.addressof @G_memo_k : !llvm.ptr
%343 = llvm.load %342 : !llvm.ptr -> !llvm.ptr
%344 = llvm.getelementptr %343[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %344 : i64, !llvm.ptr
%345 = llvm.mlir.addressof @G_memo_v : !llvm.ptr
%346 = llvm.load %345 : !llvm.ptr -> !llvm.ptr
%347 = llvm.getelementptr %346[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg2, %347 : i64, !llvm.ptr
func.return
}
func.func @sum_upto(%arg0: i64) -> i64 {
%348 = arith.constant 0 : i32
%350 = arith.extsi %348 : i32 to i64
%349 = arith.cmpi sle, %arg0, %350 : i64
cf.cond_br %349, ^bb72, ^bb73
^bb72:
%351 = arith.constant 0 : i32
%352 = arith.extsi %351 : i32 to i64
func.return %352 : i64
^bb73:
cf.br ^bb74
^bb74:
%353 = llvm.mlir.addressof @BASE : !llvm.ptr
%354 = llvm.load %353 : !llvm.ptr -> i64
%355 = arith.cmpi sle, %arg0, %354 : i64
cf.cond_br %355, ^bb75, ^bb76
^bb75:
%357 = llvm.mlir.addressof @G_pref : !llvm.ptr
%358 = llvm.load %357 : !llvm.ptr -> !llvm.ptr
%359 = llvm.getelementptr %358[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%356 = llvm.load %359 : !llvm.ptr -> i64
%360 = llvm.mlir.addressof @MOD : !llvm.ptr
%361 = llvm.load %360 : !llvm.ptr -> i64
%362 = arith.remsi %356, %361 : i64
func.return %362 : i64
^bb76:
cf.br ^bb77
^bb77:
%364 = arith.constant 1 : i32
%365 = arith.constant 8 : i32
%366 = arith.extsi %364 : i32 to i64
%367 = arith.extsi %365 : i32 to i64
%363 = func.call @calloc(%366, %367) : (i64, i64) -> !llvm.ptr
%368 = llvm.mlir.zero : !llvm.ptr
%369 = llvm.icmp "eq" %363, %368 : !llvm.ptr
cf.cond_br %369, ^bb78, ^bb79
^bb78:
%370 = arith.constant 0 : i32
%371 = arith.extsi %370 : i32 to i64
func.return %371 : i64
^bb79:
cf.br ^bb80
^bb80:
%372 = func.call @memo_get(%arg0, %363) : (i64, !llvm.ptr) -> i1
cf.cond_br %372, ^bb81, ^bb82
^bb81:
%374 = arith.constant 0 : i32
%375 = arith.extsi %374 : i32 to i64
%376 = llvm.getelementptr %363[%375] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%373 = llvm.load %376 : !llvm.ptr -> i64
func.call @free(%363) : (!llvm.ptr) -> ()
func.return %373 : i64
^bb82:
cf.br ^bb83
^bb83:
%379 = arith.constant 0 : i32
%380 = arith.extsi %379 : i32 to i64
%381 = llvm.getelementptr %363[%380] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%378 = llvm.load %381 : !llvm.ptr -> i64
func.call @free(%363) : (!llvm.ptr) -> ()
%383 = arith.constant 1 : i32
%384 = arith.extsi %383 : i32 to i64
%385 = func.call @bit_length(%arg0) : (i64) -> i32
%386 = arith.constant 1 : i32
%387 = arith.subi %385, %386 : i32
%389 = arith.extsi %387 : i32 to i64
%388 = arith.shli %384, %389 : i64
%390 = arith.constant 1 : i32
%392 = arith.extsi %390 : i32 to i64
%391 = arith.shrsi %388, %392 : i64
%393 = arith.addi %388, %391 : i64
%395 = arith.constant 1 : i32
%397 = arith.extsi %395 : i32 to i64
%396 = arith.subi %388, %397 : i64
%394 = func.call @sum_upto(%396) : (i64) -> i64
%398 = llvm.mlir.constant(1 : i64) : i64
%399 = llvm.alloca %398 x i64 : (i64) -> !llvm.ptr
llvm.store %394, %399 : i64, !llvm.ptr
%400 = arith.cmpi slt, %arg0, %393 : i64
cf.cond_br %400, ^bb84, ^bb85
^bb84:
%401 = arith.subi %arg0, %388 : i64
%403 = arith.addi %391, %401 : i64
%402 = func.call @sum_upto(%403) : (i64) -> i64
%405 = arith.constant 1 : i32
%407 = arith.extsi %405 : i32 to i64
%406 = arith.subi %391, %407 : i64
%404 = func.call @sum_upto(%406) : (i64) -> i64
%408 = arith.subi %402, %404 : i64
%409 = llvm.mlir.constant(1 : i64) : i64
%410 = llvm.alloca %409 x i64 : (i64) -> !llvm.ptr
llvm.store %408, %410 : i64, !llvm.ptr
%411 = llvm.load %410 : !llvm.ptr -> i64
%412 = llvm.mlir.addressof @MOD : !llvm.ptr
%413 = llvm.load %412 : !llvm.ptr -> i64
%414 = arith.remsi %411, %413 : i64
llvm.store %414, %410 : i64, !llvm.ptr
%415 = llvm.load %410 : !llvm.ptr -> i64
%416 = arith.constant 0 : i32
%418 = arith.extsi %416 : i32 to i64
%417 = arith.cmpi slt, %415, %418 : i64
cf.cond_br %417, ^bb87, ^bb88
^bb87:
%419 = llvm.load %410 : !llvm.ptr -> i64
%420 = llvm.mlir.addressof @MOD : !llvm.ptr
%421 = llvm.load %420 : !llvm.ptr -> i64
%422 = arith.addi %419, %421 : i64
llvm.store %422, %410 : i64, !llvm.ptr
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
%423 = func.call @bit_length(%391) : (i64) -> i32
%424 = arith.constant 1 : i32
%425 = arith.subi %423, %424 : i32
%426 = arith.constant 4 : i32
%427 = arith.cmpi sge, %425, %426 : i32
cf.cond_br %427, ^bb90, ^bb91
^bb90:
%428 = arith.constant 2 : i32
%430 = arith.extsi %428 : i32 to i64
%429 = arith.shrsi %391, %430 : i64
%431 = arith.subi %391, %429 : i64
%432 = arith.constant 1 : i32
%434 = arith.extsi %432 : i32 to i64
%433 = arith.addi %431, %434 : i64
%435 = arith.cmpi sge, %401, %433 : i64
cf.cond_br %435, ^bb93, ^bb94
^bb93:
%436 = arith.subi %401, %433 : i64
%437 = arith.constant 1 : i32
%439 = arith.extsi %437 : i32 to i64
%438 = arith.addi %436, %439 : i64
%440 = arith.extsi %438 : i64 to i128
%441 = arith.extsi %391 : i64 to i128
%443 = arith.trunci %440 : i128 to i64
%444 = arith.trunci %441 : i128 to i64
%442 = arith.muli %443, %444 : i64
%445 = arith.addi %433, %401 : i64
%446 = arith.extsi %445 : i64 to i128
%447 = arith.extsi %438 : i64 to i128
%449 = arith.trunci %446 : i128 to i64
%450 = arith.trunci %447 : i128 to i64
%448 = arith.muli %449, %450 : i64
%451 = arith.constant 2 : i32
%453 = arith.extsi %451 : i32 to i64
%452 = arith.divsi %448, %453 : i64
%454 = arith.subi %442, %452 : i64
%455 = arith.extsi %454 : i64 to i128
%457 = llvm.load %410 : !llvm.ptr -> i64
%458 = arith.extsi %457 : i64 to i128
%460 = arith.trunci %458 : i128 to i64
%461 = arith.trunci %455 : i128 to i64
%459 = arith.addi %460, %461 : i64
%462 = arith.extsi %459 : i64 to i128
%456 = func.call @mod_norm(%462) : (i128) -> i64
llvm.store %456, %410 : i64, !llvm.ptr
cf.br ^bb95
^bb94:
cf.br ^bb95
^bb95:
cf.br ^bb92
^bb91:
cf.br ^bb92
^bb92:
%463 = llvm.load %399 : !llvm.ptr -> i64
%464 = llvm.load %410 : !llvm.ptr -> i64
%465 = arith.addi %463, %464 : i64
%466 = llvm.mlir.addressof @MOD : !llvm.ptr
%467 = llvm.load %466 : !llvm.ptr -> i64
%468 = arith.remsi %465, %467 : i64
llvm.store %468, %399 : i64, !llvm.ptr
%470 = llvm.load %399 : !llvm.ptr -> i64
func.call @memo_put(%arg0, %378, %470) : (i64, i64, i64) -> ()
%471 = llvm.load %399 : !llvm.ptr -> i64
func.return %471 : i64
^bb85:
cf.br ^bb86
^bb86:
%473 = arith.constant 1 : i32
%475 = arith.extsi %473 : i32 to i64
%474 = arith.subi %388, %475 : i64
%472 = func.call @sum_upto(%474) : (i64) -> i64
%477 = arith.constant 1 : i32
%479 = arith.extsi %477 : i32 to i64
%478 = arith.subi %391, %479 : i64
%476 = func.call @sum_upto(%478) : (i64) -> i64
%480 = arith.subi %472, %476 : i64
%481 = llvm.mlir.constant(1 : i64) : i64
%482 = llvm.alloca %481 x i64 : (i64) -> !llvm.ptr
llvm.store %480, %482 : i64, !llvm.ptr
%483 = llvm.load %482 : !llvm.ptr -> i64
%484 = llvm.mlir.addressof @MOD : !llvm.ptr
%485 = llvm.load %484 : !llvm.ptr -> i64
%486 = arith.remsi %483, %485 : i64
llvm.store %486, %482 : i64, !llvm.ptr
%487 = llvm.load %482 : !llvm.ptr -> i64
%488 = arith.constant 0 : i32
%490 = arith.extsi %488 : i32 to i64
%489 = arith.cmpi slt, %487, %490 : i64
cf.cond_br %489, ^bb96, ^bb97
^bb96:
%491 = llvm.load %482 : !llvm.ptr -> i64
%492 = llvm.mlir.addressof @MOD : !llvm.ptr
%493 = llvm.load %492 : !llvm.ptr -> i64
%494 = arith.addi %491, %493 : i64
llvm.store %494, %482 : i64, !llvm.ptr
cf.br ^bb98
^bb97:
cf.br ^bb98
^bb98:
%495 = func.call @bit_length(%391) : (i64) -> i32
%496 = arith.constant 1 : i32
%497 = arith.subi %495, %496 : i32
%498 = arith.constant 0 : i32
%499 = arith.extsi %498 : i32 to i64
%500 = llvm.mlir.constant(1 : i64) : i64
%501 = llvm.alloca %500 x i64 : (i64) -> !llvm.ptr
llvm.store %499, %501 : i64, !llvm.ptr
%502 = arith.constant 4 : i32
%503 = arith.cmpi sge, %497, %502 : i32
cf.cond_br %503, ^bb99, ^bb100
^bb99:
%504 = arith.constant 2 : i32
%506 = arith.extsi %504 : i32 to i64
%505 = arith.shrsi %391, %506 : i64
%507 = arith.constant 1 : i32
%509 = arith.extsi %507 : i32 to i64
%508 = arith.subi %505, %509 : i64
%510 = arith.extsi %508 : i64 to i128
%511 = arith.constant 1 : i32
%513 = arith.extsi %511 : i32 to i64
%512 = arith.addi %508, %513 : i64
%514 = arith.extsi %512 : i64 to i128
%516 = arith.trunci %510 : i128 to i64
%517 = arith.trunci %514 : i128 to i64
%515 = arith.muli %516, %517 : i64
%518 = arith.constant 2 : i32
%520 = arith.extsi %518 : i32 to i64
%519 = arith.divsi %515, %520 : i64
%521 = arith.extsi %519 : i64 to i128
%523 = llvm.load %482 : !llvm.ptr -> i64
%524 = arith.extsi %523 : i64 to i128
%526 = arith.trunci %524 : i128 to i64
%527 = arith.trunci %521 : i128 to i64
%525 = arith.addi %526, %527 : i64
%528 = arith.extsi %525 : i64 to i128
%522 = func.call @mod_norm(%528) : (i128) -> i64
llvm.store %522, %501 : i64, !llvm.ptr
cf.br ^bb101
^bb100:
%529 = llvm.mlir.constant(1 : i64) : i64
%530 = llvm.alloca %529 x i64 : (i64) -> !llvm.ptr
llvm.store %388, %530 : i64, !llvm.ptr
cf.br ^bb102
^bb102:
%531 = llvm.load %530 : !llvm.ptr -> i64
%532 = arith.cmpi slt, %531, %393 : i64
cf.cond_br %532, ^bb103, ^bb104
^bb103:
%533 = llvm.load %501 : !llvm.ptr -> i64
%535 = llvm.load %530 : !llvm.ptr -> i64
%534 = func.call @brute_f(%535) : (i64) -> i64
%536 = arith.addi %533, %534 : i64
llvm.store %536, %501 : i64, !llvm.ptr
%537 = llvm.load %530 : !llvm.ptr -> i64
%538 = arith.constant 1 : i32
%540 = arith.extsi %538 : i32 to i64
%539 = arith.addi %537, %540 : i64
llvm.store %539, %530 : i64, !llvm.ptr
cf.br ^bb102
^bb104:
%541 = llvm.load %501 : !llvm.ptr -> i64
%542 = llvm.mlir.addressof @MOD : !llvm.ptr
%543 = llvm.load %542 : !llvm.ptr -> i64
%544 = arith.remsi %541, %543 : i64
llvm.store %544, %501 : i64, !llvm.ptr
cf.br ^bb101
^bb101:
%545 = llvm.load %399 : !llvm.ptr -> i64
%546 = llvm.load %501 : !llvm.ptr -> i64
%547 = arith.addi %545, %546 : i64
%548 = llvm.mlir.addressof @MOD : !llvm.ptr
%549 = llvm.load %548 : !llvm.ptr -> i64
%550 = arith.remsi %547, %549 : i64
llvm.store %550, %399 : i64, !llvm.ptr
%551 = arith.subi %arg0, %393 : i64
%552 = arith.constant 1 : i32
%554 = arith.extsi %552 : i32 to i64
%553 = arith.addi %551, %554 : i64
%555 = llvm.load %399 : !llvm.ptr -> i64
%556 = func.call @prefix_sum_11_block(%391, %553) : (i64, i64) -> i64
%557 = arith.addi %555, %556 : i64
%558 = llvm.mlir.addressof @MOD : !llvm.ptr
%559 = llvm.load %558 : !llvm.ptr -> i64
%560 = arith.remsi %557, %559 : i64
llvm.store %560, %399 : i64, !llvm.ptr
%562 = llvm.load %399 : !llvm.ptr -> i64
func.call @memo_put(%arg0, %378, %562) : (i64, i64, i64) -> ()
%563 = llvm.load %399 : !llvm.ptr -> i64
func.return %563 : i64
}
func.func @main() -> i32 {
%565 = llvm.mlir.addressof @BASE : !llvm.ptr
%566 = llvm.load %565 : !llvm.ptr -> i64
%567 = arith.constant 1 : i32
%569 = arith.extsi %567 : i32 to i64
%568 = arith.addi %566, %569 : i64
%570 = arith.constant 8 : i32
%571 = arith.extsi %570 : i32 to i64
%564 = func.call @calloc(%568, %571) : (i64, i64) -> !llvm.ptr
%572 = llvm.mlir.addressof @G_fbase : !llvm.ptr
llvm.store %564, %572 : !llvm.ptr, !llvm.ptr
%574 = llvm.mlir.addressof @BASE : !llvm.ptr
%575 = llvm.load %574 : !llvm.ptr -> i64
%576 = arith.constant 1 : i32
%578 = arith.extsi %576 : i32 to i64
%577 = arith.addi %575, %578 : i64
%579 = arith.constant 8 : i32
%580 = arith.extsi %579 : i32 to i64
%573 = func.call @calloc(%577, %580) : (i64, i64) -> !llvm.ptr
%581 = llvm.mlir.addressof @G_pref : !llvm.ptr
llvm.store %573, %581 : !llvm.ptr, !llvm.ptr
%583 = llvm.mlir.addressof @MEMO_CAP : !llvm.ptr
%584 = llvm.load %583 : !llvm.ptr -> i64
%585 = arith.constant 8 : i32
%586 = arith.extsi %585 : i32 to i64
%582 = func.call @calloc(%584, %586) : (i64, i64) -> !llvm.ptr
%587 = llvm.mlir.addressof @G_memo_k : !llvm.ptr
llvm.store %582, %587 : !llvm.ptr, !llvm.ptr
%589 = llvm.mlir.addressof @MEMO_CAP : !llvm.ptr
%590 = llvm.load %589 : !llvm.ptr -> i64
%591 = arith.constant 8 : i32
%592 = arith.extsi %591 : i32 to i64
%588 = func.call @calloc(%590, %592) : (i64, i64) -> !llvm.ptr
%593 = llvm.mlir.addressof @G_memo_v : !llvm.ptr
llvm.store %588, %593 : !llvm.ptr, !llvm.ptr
%595 = llvm.mlir.addressof @MEMO_CAP : !llvm.ptr
%596 = llvm.load %595 : !llvm.ptr -> i64
%597 = arith.constant 1 : i32
%598 = arith.extsi %597 : i32 to i64
%594 = func.call @calloc(%596, %598) : (i64, i64) -> !llvm.ptr
%599 = llvm.mlir.addressof @G_memo_u : !llvm.ptr
llvm.store %594, %599 : !llvm.ptr, !llvm.ptr
%600 = llvm.mlir.addressof @G_fbase : !llvm.ptr
%601 = llvm.load %600 : !llvm.ptr -> !llvm.ptr
%602 = llvm.mlir.zero : !llvm.ptr
%603 = llvm.icmp "eq" %601, %602 : !llvm.ptr
%604 = scf.if %603 -> (i1) {
%605 = arith.constant true
scf.yield %605 : i1
} else {
%606 = llvm.mlir.addressof @G_pref : !llvm.ptr
%607 = llvm.load %606 : !llvm.ptr -> !llvm.ptr
%608 = llvm.mlir.zero : !llvm.ptr
%609 = llvm.icmp "eq" %607, %608 : !llvm.ptr
scf.yield %609 : i1
}
%610 = scf.if %604 -> (i1) {
%611 = arith.constant true
scf.yield %611 : i1
} else {
%612 = llvm.mlir.addressof @G_memo_k : !llvm.ptr
%613 = llvm.load %612 : !llvm.ptr -> !llvm.ptr
%614 = llvm.mlir.zero : !llvm.ptr
%615 = llvm.icmp "eq" %613, %614 : !llvm.ptr
scf.yield %615 : i1
}
%616 = scf.if %610 -> (i1) {
%617 = arith.constant true
scf.yield %617 : i1
} else {
%618 = llvm.mlir.addressof @G_memo_v : !llvm.ptr
%619 = llvm.load %618 : !llvm.ptr -> !llvm.ptr
%620 = llvm.mlir.zero : !llvm.ptr
%621 = llvm.icmp "eq" %619, %620 : !llvm.ptr
scf.yield %621 : i1
}
%622 = scf.if %616 -> (i1) {
%623 = arith.constant true
scf.yield %623 : i1
} else {
%624 = llvm.mlir.addressof @G_memo_u : !llvm.ptr
%625 = llvm.load %624 : !llvm.ptr -> !llvm.ptr
%626 = llvm.mlir.zero : !llvm.ptr
%627 = llvm.icmp "eq" %625, %626 : !llvm.ptr
scf.yield %627 : i1
}
cf.cond_br %622, ^bb105, ^bb106
^bb105:
%628 = arith.constant 1 : i32
func.return %628 : i32
^bb106:
cf.br ^bb107
^bb107:
%629 = arith.constant 1 : i32
%630 = arith.extsi %629 : i32 to i64
%631 = llvm.mlir.constant(1 : i64) : i64
%632 = llvm.alloca %631 x i64 : (i64) -> !llvm.ptr
llvm.store %630, %632 : i64, !llvm.ptr
cf.br ^bb108
^bb108:
%633 = llvm.load %632 : !llvm.ptr -> i64
%634 = llvm.mlir.addressof @BASE : !llvm.ptr
%635 = llvm.load %634 : !llvm.ptr -> i64
%636 = arith.cmpi sle, %633, %635 : i64
cf.cond_br %636, ^bb109, ^bb110
^bb109:
%638 = llvm.load %632 : !llvm.ptr -> i64
%637 = func.call @brute_f(%638) : (i64) -> i64
%639 = llvm.mlir.addressof @G_fbase : !llvm.ptr
%640 = llvm.load %639 : !llvm.ptr -> !llvm.ptr
%641 = llvm.load %632 : !llvm.ptr -> i64
%642 = llvm.getelementptr %640[%641] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %637, %642 : i64, !llvm.ptr
%644 = llvm.mlir.addressof @G_pref : !llvm.ptr
%645 = llvm.load %644 : !llvm.ptr -> !llvm.ptr
%646 = llvm.load %632 : !llvm.ptr -> i64
%647 = arith.constant 1 : i32
%649 = arith.extsi %647 : i32 to i64
%648 = arith.subi %646, %649 : i64
%650 = llvm.getelementptr %645[%648] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%643 = llvm.load %650 : !llvm.ptr -> i64
%652 = llvm.mlir.addressof @G_fbase : !llvm.ptr
%653 = llvm.load %652 : !llvm.ptr -> !llvm.ptr
%654 = llvm.load %632 : !llvm.ptr -> i64
%655 = llvm.getelementptr %653[%654] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%651 = llvm.load %655 : !llvm.ptr -> i64
%656 = arith.addi %643, %651 : i64
%657 = llvm.mlir.addressof @G_pref : !llvm.ptr
%658 = llvm.load %657 : !llvm.ptr -> !llvm.ptr
%659 = llvm.load %632 : !llvm.ptr -> i64
%660 = llvm.getelementptr %658[%659] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %656, %660 : i64, !llvm.ptr
%661 = llvm.load %632 : !llvm.ptr -> i64
%662 = arith.constant 1 : i32
%664 = arith.extsi %662 : i32 to i64
%663 = arith.addi %661, %664 : i64
llvm.store %663, %632 : i64, !llvm.ptr
cf.br ^bb108
^bb110:
%665 = arith.constant 995705032704 : i32
%666 = arith.extsi %665 : i32 to i64
%667 = func.call @sum_upto(%666) : (i64) -> i64
%668 = llvm.mlir.addressof @MOD : !llvm.ptr
%669 = llvm.load %668 : !llvm.ptr -> i64
%670 = arith.remsi %667, %669 : i64
%671 = llvm.mlir.addressof @str_0 : !llvm.ptr
%672 = llvm.call @printf(%671, %670) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%673 = arith.constant 0 : i32
func.return %673 : i32
}
}