Problem 546
The Floor's Revenge — sum f_k(10^14) mod 10^9+7.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n log n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Modular DP or matrix exponentiation |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 546
# The Floor's Revenge — sum f_k(10^14) mod 10^9+7.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000000007
const N: i64 = 100000000000000
function modpow(base0: i64, exp0: i64, mod: i64) -> i64 {
let mut result: i64 = 1
let mut base: i64 = base0 % mod
let mut exp: i64 = exp0
while exp > 0 {
if (exp & 1) != 0 {
result = ((result as i128) * (base as i128) % (mod as i128)) as i64
}
base = ((base as i128) * (base as i128) % (mod as i128)) as i64
exp = exp >> 1
}
return result
}
function nCk(n: i64, r: i64, fact: ptr<i64>, invfact: ptr<i64>) -> i64 {
if r < 0 || r > n { return 0 }
let a: i128 = (fact[n] as i128) * (invfact[r] as i128) % (MOD as i128)
return (a * (invfact[n - r] as i128) % (MOD as i128)) as i64
}
function fk_mod(k: i64, N0: i64, fact: ptr<i64>, invfact: ptr<i64>,
coeffs: ptr<i64>, max_depth: i64) -> i64 {
let ns: ptr<i64> = calloc(64, 8)
if ns == null { return 0 }
ns[0] = N0
let mut depth: i64 = 0
while ns[depth] >= k {
depth = depth + 1
ns[depth] = ns[depth - 1] / k
}
let d: i64 = depth
let base: i64 = ns[d]
let state: ptr<i64> = calloc(d + 2, 8)
if state == null { free(ns); return 0 }
let mut j: i64 = 0
while j <= d {
state[j] = nCk(base + j + 1, j + 1, fact, invfact)
j = j + 1
}
let mut i: i64 = d - 1
while i >= 0 {
let r: i64 = ns[i] % k
let new_len: i64 = i + 1
let newv: ptr<i64> = calloc(new_len + 1, 8)
if newv == null { free(state); free(ns); return 0 }
let mut jj: i64 = 0
while jj <= i {
let co_off: i64 = (jj * k + r) * (max_depth + 2)
let mut s: i64 = 0
let mut p: i64 = 0
while p <= jj + 1 {
s = (s + coeffs[co_off + p] * state[p]) % MOD
p = p + 1
}
newv[jj] = s
jj = jj + 1
}
j = 0
while j <= i {
state[j] = newv[j]
j = j + 1
}
free(newv)
i = i - 1
}
let ans: i64 = state[0]
free(state)
free(ns)
return ans
}
function build_coeffs(k: i64, max_j: i64, coeffs: ptr<i64>, max_depth: i64) -> void {
let stride: i64 = max_depth + 2
let mut r: i64 = 0
while r < k {
coeffs[r * stride + 0] = (r + 1 - k) % MOD
coeffs[r * stride + 1] = k % MOD
r = r + 1
}
let mut j: i64 = 1
while j <= max_j {
let mut u: i64 = 0
while u < k {
let totals: ptr<i64> = calloc(j + 1, 8)
let prefix: ptr<i64> = calloc(k * (j + 1), 8)
if totals == null || prefix == null {
if totals != null { free(totals) }
if prefix != null { free(prefix) }
return
}
let mut uu: i64 = 0
while uu < k {
let prev_off: i64 = ((j - 1) * k + uu) * stride
let mut p: i64 = 0
while p <= j {
totals[p] = (totals[p] + coeffs[prev_off + p]) % MOD
p = p + 1
}
uu = uu + 1
}
uu = 0
let run: ptr<i64> = calloc(j + 1, 8)
while uu < k {
let prev_off: i64 = ((j - 1) * k + uu) * stride
let mut p: i64 = 0
while p <= j {
run[p] = (run[p] + coeffs[prev_off + p]) % MOD
prefix[uu * (j + 1) + p] = run[p]
p = p + 1
}
uu = uu + 1
}
free(run)
let mut rr: i64 = 0
while rr < k {
let out_off: i64 = (j * k + rr) * stride
let mut p: i64 = 0
while p <= j + 1 {
coeffs[out_off + p] = 0
p = p + 1
}
coeffs[out_off + 0] = (prefix[rr * (j + 1) + 0] - totals[0]) % MOD
if coeffs[out_off + 0] < 0 { coeffs[out_off + 0] = coeffs[out_off + 0] + MOD }
p = 1
while p <= j {
let mut v: i64 = prefix[rr * (j + 1) + p] - totals[p] + totals[p - 1]
v = v % MOD
if v < 0 { v = v + MOD }
coeffs[out_off + p] = v
p = p + 1
}
coeffs[out_off + j + 1] = totals[j] % MOD
rr = rr + 1
}
free(totals)
free(prefix)
u = u + 1
}
j = j + 1
}
}
function compute_depth(k: i64, N0: i64) -> i64 {
let mut d: i64 = 0
let mut n: i64 = N0
while n >= k {
d = d + 1
n = n / k
}
return d
}
function main() -> i32 {
let fact_max: i64 = 200
let fact: ptr<i64> = calloc(fact_max + 1, 8)
let invfact: ptr<i64> = calloc(fact_max + 1, 8)
if fact == null || invfact == null { return 1 }
fact[0] = 1
let mut i: i64 = 1
while i <= fact_max {
fact[i] = ((fact[i - 1] as i128) * (i as i128) % (MOD as i128)) as i64
i = i + 1
}
invfact[fact_max] = modpow(fact[fact_max], MOD - 2, MOD)
i = fact_max
while i > 0 {
invfact[i - 1] = ((invfact[i] as i128) * (i as i128) % (MOD as i128)) as i64
i = i - 1
}
let mut ans: i64 = 0
let mut k: i64 = 2
while k <= 10 {
let depth: i64 = compute_depth(k, N)
let stride: i64 = depth + 2
let coeffs: ptr<i64> = calloc((depth + 1) * k * stride, 8)
if coeffs == null { break }
build_coeffs(k, depth, coeffs, depth)
ans = (ans + fk_mod(k, N, fact, invfact, coeffs, depth)) % MOD
free(coeffs)
k = k + 1
}
printf("%lld\n", ans)
free(fact)
free(invfact)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod);
int64_t nCk_i64_i64_ptr_i64_ptr_i64(int64_t n, int64_t r, int64_t* fact, int64_t* invfact);
int64_t fk_mod_i64_i64_ptr_i64_ptr_i64_ptr_i64_i64(int64_t k, int64_t N0, int64_t* fact, int64_t* invfact, int64_t* coeffs, int64_t max_depth);
void build_coeffs_i64_i64_ptr_i64_i64(int64_t k, int64_t max_j, int64_t* coeffs, int64_t max_depth);
int64_t compute_depth_i64_i64(int64_t k, int64_t N0);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int64_t N = 100000000000000;
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod) {
int64_t result = 1;
int64_t base = FLOW_CHECKED_MOD((base0), (mod));
int64_t exp = exp0;
while (exp > 0) {
if ((exp & 1) != 0) {
result = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(result)) * ((__int128)(base)))), (((__int128)(mod))))));
}
base = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(base)) * ((__int128)(base)))), (((__int128)(mod))))));
exp = FLOW_CHECKED_SHR((exp), (1));
}
return result;
}
int64_t nCk_i64_i64_ptr_i64_ptr_i64(int64_t n, int64_t r, int64_t* fact, int64_t* invfact) {
if ((r < 0 || r > n)) {
return 0;
}
__int128 a = FLOW_CHECKED_MOD(((((__int128)(fact[n])) * ((__int128)(invfact[r])))), (((__int128)(MOD))));
return ((int64_t)(FLOW_CHECKED_MOD(((a * ((__int128)(invfact[(n - r)])))), (((__int128)(MOD))))));
}
int64_t fk_mod_i64_i64_ptr_i64_ptr_i64_ptr_i64_i64(int64_t k, int64_t N0, int64_t* fact, int64_t* invfact, int64_t* coeffs, int64_t max_depth) {
int64_t* ns = (int64_t*)(calloc(64, 8));
if (ns == NULL) {
return 0;
}
ns[0] = N0;
int64_t depth = 0;
while (ns[depth] >= k) {
depth = (depth + 1);
ns[depth] = FLOW_CHECKED_DIV((ns[(depth - 1)]), (k));
}
int64_t d = depth;
int64_t base = ns[d];
int64_t* state = (int64_t*)(calloc((d + 2), 8));
if (state == NULL) {
free(ns);
return 0;
}
int64_t j = 0;
while (j <= d) {
state[j] = nCk_i64_i64_ptr_i64_ptr_i64(((base + j) + 1), (j + 1), fact, invfact);
j = (j + 1);
}
int64_t i = (d - 1);
while (i >= 0) {
int64_t r = FLOW_CHECKED_MOD((ns[i]), (k));
int64_t new_len = (i + 1);
int64_t* newv = (int64_t*)(calloc((new_len + 1), 8));
if (newv == NULL) {
free(state);
free(ns);
return 0;
}
int64_t jj = 0;
while (jj <= i) {
int64_t co_off = (((jj * k) + r) * (max_depth + 2));
int64_t s = 0;
int64_t p = 0;
while (p <= (jj + 1)) {
s = FLOW_CHECKED_MOD(((s + (coeffs[(co_off + p)] * state[p]))), (MOD));
p = (p + 1);
}
newv[jj] = s;
jj = (jj + 1);
}
j = 0;
while (j <= i) {
state[j] = newv[j];
j = (j + 1);
}
free(newv);
i = (i - 1);
}
int64_t ans = state[0];
free(state);
free(ns);
return ans;
}
void build_coeffs_i64_i64_ptr_i64_i64(int64_t k, int64_t max_j, int64_t* coeffs, int64_t max_depth) {
int64_t stride = (max_depth + 2);
int64_t r = 0;
while (r < k) {
coeffs[((r * stride) + 0)] = FLOW_CHECKED_MOD((((r + 1) - k)), (MOD));
coeffs[((r * stride) + 1)] = FLOW_CHECKED_MOD((k), (MOD));
r = (r + 1);
}
int64_t j = 1;
while (j <= max_j) {
int64_t u = 0;
while (u < k) {
int64_t* totals = (int64_t*)(calloc((j + 1), 8));
int64_t* prefix = (int64_t*)(calloc((k * (j + 1)), 8));
if ((totals == NULL || prefix == NULL)) {
if (totals != NULL) {
free(totals);
}
if (prefix != NULL) {
free(prefix);
}
return;
}
int64_t uu = 0;
while (uu < k) {
int64_t prev_off = ((((j - 1) * k) + uu) * stride);
int64_t p = 0;
while (p <= j) {
totals[p] = FLOW_CHECKED_MOD(((totals[p] + coeffs[(prev_off + p)])), (MOD));
p = (p + 1);
}
uu = (uu + 1);
}
uu = 0;
int64_t* run = (int64_t*)(calloc((j + 1), 8));
while (uu < k) {
int64_t prev_off = ((((j - 1) * k) + uu) * stride);
int64_t p = 0;
while (p <= j) {
run[p] = FLOW_CHECKED_MOD(((run[p] + coeffs[(prev_off + p)])), (MOD));
prefix[((uu * (j + 1)) + p)] = run[p];
p = (p + 1);
}
uu = (uu + 1);
}
free(run);
int64_t rr = 0;
while (rr < k) {
int64_t out_off = (((j * k) + rr) * stride);
int64_t p = 0;
while (p <= (j + 1)) {
coeffs[(out_off + p)] = 0;
p = (p + 1);
}
coeffs[(out_off + 0)] = FLOW_CHECKED_MOD(((prefix[((rr * (j + 1)) + 0)] - totals[0])), (MOD));
if (coeffs[(out_off + 0)] < 0) {
coeffs[(out_off + 0)] = (coeffs[(out_off + 0)] + MOD);
}
p = 1;
while (p <= j) {
int64_t v = ((prefix[((rr * (j + 1)) + p)] - totals[p]) + totals[(p - 1)]);
v = FLOW_CHECKED_MOD((v), (MOD));
if (v < 0) {
v = (v + MOD);
}
coeffs[(out_off + p)] = v;
p = (p + 1);
}
coeffs[((out_off + j) + 1)] = FLOW_CHECKED_MOD((totals[j]), (MOD));
rr = (rr + 1);
}
free(totals);
free(prefix);
u = (u + 1);
}
j = (j + 1);
}
}
int64_t compute_depth_i64_i64(int64_t k, int64_t N0) {
int64_t d = 0;
int64_t n = N0;
while (n >= k) {
d = (d + 1);
n = FLOW_CHECKED_DIV((n), (k));
}
return d;
}
int32_t main(void) {
int64_t fact_max = 200;
int64_t* fact = (int64_t*)(calloc((fact_max + 1), 8));
int64_t* invfact = (int64_t*)(calloc((fact_max + 1), 8));
if ((fact == NULL || invfact == NULL)) {
return 1;
}
fact[0] = 1;
int64_t i = 1;
while (i <= fact_max) {
fact[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(fact[(i - 1)])) * ((__int128)(i)))), (((__int128)(MOD))))));
i = (i + 1);
}
invfact[fact_max] = modpow_i64_i64_i64(fact[fact_max], (MOD - 2), MOD);
i = fact_max;
while (i > 0) {
invfact[(i - 1)] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(invfact[i])) * ((__int128)(i)))), (((__int128)(MOD))))));
i = (i - 1);
}
int64_t ans = 0;
int64_t k = 2;
while (k <= 10) {
int64_t depth = compute_depth_i64_i64(k, N);
int64_t stride = (depth + 2);
int64_t* coeffs = (int64_t*)(calloc((((depth + 1) * k) * stride), 8));
if (coeffs == NULL) {
break;
}
build_coeffs_i64_i64_ptr_i64_i64(k, depth, coeffs, depth);
ans = FLOW_CHECKED_MOD(((ans + fk_mod_i64_i64_ptr_i64_ptr_i64_ptr_i64_i64(k, N, fact, invfact, coeffs, depth))), (MOD));
free(coeffs);
k = (k + 1);
}
printf("%lld\n", ans);
free(fact);
free(invfact);
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(1000000007 : i64) : i64
// Constant: N
llvm.mlir.global internal constant @N(100000000000000 : i64) : i64
func.func @modpow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%0 = arith.constant 1 : 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.remsi %arg0, %arg2 : i64
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i64 : (i64) -> !llvm.ptr
llvm.store %4, %6 : i64, !llvm.ptr
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %8 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%9 = llvm.load %8 : !llvm.ptr -> i64
%10 = arith.constant 0 : i32
%12 = arith.extsi %10 : i32 to i64
%11 = arith.cmpi sgt, %9, %12 : i64
cf.cond_br %11, ^bb1, ^bb2
^bb1:
%13 = llvm.load %8 : !llvm.ptr -> i64
%14 = arith.constant 1 : i32
%16 = arith.extsi %14 : i32 to i64
%15 = arith.andi %13, %16 : i64
%17 = arith.constant 0 : i32
%19 = arith.extsi %17 : i32 to i64
%18 = arith.cmpi ne, %15, %19 : i64
cf.cond_br %18, ^bb3, ^bb4
^bb3:
%20 = llvm.load %3 : !llvm.ptr -> i64
%21 = arith.extsi %20 : i64 to i128
%22 = llvm.load %6 : !llvm.ptr -> i64
%23 = arith.extsi %22 : i64 to i128
%25 = arith.trunci %21 : i128 to i64
%26 = arith.trunci %23 : i128 to i64
%24 = arith.muli %25, %26 : i64
%27 = arith.extsi %arg2 : i64 to i128
%29 = arith.trunci %27 : i128 to i64
%28 = arith.remsi %24, %29 : i64
llvm.store %28, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%30 = llvm.load %6 : !llvm.ptr -> i64
%31 = arith.extsi %30 : i64 to i128
%32 = llvm.load %6 : !llvm.ptr -> i64
%33 = arith.extsi %32 : i64 to i128
%35 = arith.trunci %31 : i128 to i64
%36 = arith.trunci %33 : i128 to i64
%34 = arith.muli %35, %36 : i64
%37 = arith.extsi %arg2 : i64 to i128
%39 = arith.trunci %37 : i128 to i64
%38 = arith.remsi %34, %39 : i64
llvm.store %38, %6 : i64, !llvm.ptr
%40 = llvm.load %8 : !llvm.ptr -> i64
%41 = arith.constant 1 : i32
%43 = arith.extsi %41 : i32 to i64
%42 = arith.shrsi %40, %43 : i64
llvm.store %42, %8 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%44 = llvm.load %3 : !llvm.ptr -> i64
func.return %44 : i64
}
func.func @nCk(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: !llvm.ptr) -> i64 {
%45 = arith.constant 0 : i32
%47 = arith.extsi %45 : i32 to i64
%46 = arith.cmpi slt, %arg1, %47 : i64
%48 = scf.if %46 -> (i1) {
%49 = arith.constant true
scf.yield %49 : i1
} else {
%50 = arith.cmpi sgt, %arg1, %arg0 : i64
scf.yield %50 : i1
}
cf.cond_br %48, ^bb6, ^bb7
^bb6:
%51 = arith.constant 0 : i32
%52 = arith.extsi %51 : i32 to i64
func.return %52 : i64
^bb7:
cf.br ^bb8
^bb8:
%54 = llvm.getelementptr %arg2[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%53 = llvm.load %54 : !llvm.ptr -> i64
%55 = arith.extsi %53 : i64 to i128
%57 = llvm.getelementptr %arg3[%arg1] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%56 = llvm.load %57 : !llvm.ptr -> i64
%58 = arith.extsi %56 : i64 to i128
%60 = arith.trunci %55 : i128 to i64
%61 = arith.trunci %58 : i128 to i64
%59 = arith.muli %60, %61 : i64
%62 = llvm.mlir.addressof @MOD : !llvm.ptr
%63 = llvm.load %62 : !llvm.ptr -> i64
%64 = arith.extsi %63 : i64 to i128
%66 = arith.trunci %64 : i128 to i64
%65 = arith.remsi %59, %66 : i64
%67 = arith.extsi %65 : i64 to i128
%69 = arith.subi %arg0, %arg1 : i64
%70 = llvm.getelementptr %arg3[%69] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%68 = llvm.load %70 : !llvm.ptr -> i64
%71 = arith.extsi %68 : i64 to i128
%73 = arith.trunci %67 : i128 to i64
%74 = arith.trunci %71 : i128 to i64
%72 = arith.muli %73, %74 : i64
%75 = llvm.mlir.addressof @MOD : !llvm.ptr
%76 = llvm.load %75 : !llvm.ptr -> i64
%77 = arith.extsi %76 : i64 to i128
%79 = arith.trunci %77 : i128 to i64
%78 = arith.remsi %72, %79 : i64
func.return %78 : i64
}
func.func @fk_mod(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: i64) -> i64 {
%81 = arith.constant 64 : i32
%82 = arith.constant 8 : i32
%83 = arith.extsi %81 : i32 to i64
%84 = arith.extsi %82 : i32 to i64
%80 = func.call @calloc(%83, %84) : (i64, i64) -> !llvm.ptr
%85 = llvm.mlir.zero : !llvm.ptr
%86 = llvm.icmp "eq" %80, %85 : !llvm.ptr
cf.cond_br %86, ^bb9, ^bb10
^bb9:
%87 = arith.constant 0 : i32
%88 = arith.extsi %87 : i32 to i64
func.return %88 : i64
^bb10:
cf.br ^bb11
^bb11:
%89 = arith.constant 0 : i32
%90 = arith.extsi %89 : i32 to i64
%91 = llvm.getelementptr %80[%90] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %91 : i64, !llvm.ptr
%92 = arith.constant 0 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%97 = llvm.load %95 : !llvm.ptr -> i64
%98 = llvm.getelementptr %80[%97] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%96 = llvm.load %98 : !llvm.ptr -> i64
%99 = arith.cmpi sge, %96, %arg0 : i64
cf.cond_br %99, ^bb13, ^bb14
^bb13:
%100 = llvm.load %95 : !llvm.ptr -> i64
%101 = arith.constant 1 : i32
%103 = arith.extsi %101 : i32 to i64
%102 = arith.addi %100, %103 : i64
llvm.store %102, %95 : i64, !llvm.ptr
%105 = llvm.load %95 : !llvm.ptr -> i64
%106 = arith.constant 1 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.subi %105, %108 : i64
%109 = llvm.getelementptr %80[%107] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%104 = llvm.load %109 : !llvm.ptr -> i64
%110 = arith.divsi %104, %arg0 : i64
%111 = llvm.load %95 : !llvm.ptr -> i64
%112 = llvm.getelementptr %80[%111] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %110, %112 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%113 = llvm.load %95 : !llvm.ptr -> i64
%115 = llvm.getelementptr %80[%113] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%114 = llvm.load %115 : !llvm.ptr -> i64
%117 = arith.constant 2 : i32
%119 = arith.extsi %117 : i32 to i64
%118 = arith.addi %113, %119 : i64
%120 = arith.constant 8 : i32
%121 = arith.extsi %120 : i32 to i64
%116 = func.call @calloc(%118, %121) : (i64, i64) -> !llvm.ptr
%122 = llvm.mlir.zero : !llvm.ptr
%123 = llvm.icmp "eq" %116, %122 : !llvm.ptr
cf.cond_br %123, ^bb15, ^bb16
^bb15:
func.call @free(%80) : (!llvm.ptr) -> ()
%125 = arith.constant 0 : i32
%126 = arith.extsi %125 : i32 to i64
func.return %126 : i64
^bb16:
cf.br ^bb17
^bb17:
%127 = arith.constant 0 : i32
%128 = arith.extsi %127 : i32 to i64
%129 = llvm.mlir.constant(1 : i64) : i64
%130 = llvm.alloca %129 x i64 : (i64) -> !llvm.ptr
llvm.store %128, %130 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%131 = llvm.load %130 : !llvm.ptr -> i64
%132 = arith.cmpi sle, %131, %113 : i64
cf.cond_br %132, ^bb19, ^bb20
^bb19:
%134 = llvm.load %130 : !llvm.ptr -> i64
%135 = arith.addi %114, %134 : i64
%136 = arith.constant 1 : i32
%138 = arith.extsi %136 : i32 to i64
%137 = arith.addi %135, %138 : i64
%139 = llvm.load %130 : !llvm.ptr -> i64
%140 = arith.constant 1 : i32
%142 = arith.extsi %140 : i32 to i64
%141 = arith.addi %139, %142 : i64
%133 = func.call @nCk(%137, %141, %arg2, %arg3) : (i64, i64, !llvm.ptr, !llvm.ptr) -> i64
%143 = llvm.load %130 : !llvm.ptr -> i64
%144 = llvm.getelementptr %116[%143] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %133, %144 : i64, !llvm.ptr
%145 = llvm.load %130 : !llvm.ptr -> i64
%146 = arith.constant 1 : i32
%148 = arith.extsi %146 : i32 to i64
%147 = arith.addi %145, %148 : i64
llvm.store %147, %130 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%149 = arith.constant 1 : i32
%151 = arith.extsi %149 : i32 to i64
%150 = arith.subi %113, %151 : i64
%152 = llvm.mlir.constant(1 : i64) : i64
%153 = llvm.alloca %152 x i64 : (i64) -> !llvm.ptr
llvm.store %150, %153 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%154 = llvm.load %153 : !llvm.ptr -> i64
%155 = arith.constant 0 : i32
%157 = arith.extsi %155 : i32 to i64
%156 = arith.cmpi sge, %154, %157 : i64
cf.cond_br %156, ^bb22, ^bb23
^bb22:
%159 = llvm.load %153 : !llvm.ptr -> i64
%160 = llvm.getelementptr %80[%159] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%158 = llvm.load %160 : !llvm.ptr -> i64
%161 = arith.remsi %158, %arg0 : i64
%162 = llvm.load %153 : !llvm.ptr -> i64
%163 = arith.constant 1 : i32
%165 = arith.extsi %163 : i32 to i64
%164 = arith.addi %162, %165 : i64
%167 = arith.constant 1 : i32
%169 = arith.extsi %167 : i32 to i64
%168 = arith.addi %164, %169 : i64
%170 = arith.constant 8 : i32
%171 = arith.extsi %170 : i32 to i64
%166 = func.call @calloc(%168, %171) : (i64, i64) -> !llvm.ptr
%172 = llvm.mlir.zero : !llvm.ptr
%173 = llvm.icmp "eq" %166, %172 : !llvm.ptr
cf.cond_br %173, ^bb24, ^bb25
^bb24:
func.call @free(%116) : (!llvm.ptr) -> ()
func.call @free(%80) : (!llvm.ptr) -> ()
%176 = arith.constant 0 : i32
%177 = arith.extsi %176 : i32 to i64
func.return %177 : i64
^bb25:
cf.br ^bb26
^bb26:
%178 = arith.constant 0 : i32
%179 = arith.extsi %178 : i32 to i64
%180 = llvm.mlir.constant(1 : i64) : i64
%181 = llvm.alloca %180 x i64 : (i64) -> !llvm.ptr
llvm.store %179, %181 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%182 = llvm.load %181 : !llvm.ptr -> i64
%183 = llvm.load %153 : !llvm.ptr -> i64
%184 = arith.cmpi sle, %182, %183 : i64
cf.cond_br %184, ^bb28, ^bb29
^bb28:
%185 = llvm.load %181 : !llvm.ptr -> i64
%186 = arith.muli %185, %arg0 : i64
%187 = arith.addi %186, %161 : i64
%188 = arith.constant 2 : i32
%190 = arith.extsi %188 : i32 to i64
%189 = arith.addi %arg5, %190 : i64
%191 = arith.muli %187, %189 : i64
%192 = arith.constant 0 : i32
%193 = arith.extsi %192 : i32 to i64
%194 = llvm.mlir.constant(1 : i64) : i64
%195 = llvm.alloca %194 x i64 : (i64) -> !llvm.ptr
llvm.store %193, %195 : i64, !llvm.ptr
%196 = arith.constant 0 : i32
%197 = arith.extsi %196 : i32 to i64
%198 = llvm.mlir.constant(1 : i64) : i64
%199 = llvm.alloca %198 x i64 : (i64) -> !llvm.ptr
llvm.store %197, %199 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%200 = llvm.load %199 : !llvm.ptr -> i64
%201 = llvm.load %181 : !llvm.ptr -> i64
%202 = arith.constant 1 : i32
%204 = arith.extsi %202 : i32 to i64
%203 = arith.addi %201, %204 : i64
%205 = arith.cmpi sle, %200, %203 : i64
cf.cond_br %205, ^bb31, ^bb32
^bb31:
%206 = llvm.load %195 : !llvm.ptr -> i64
%208 = llvm.load %199 : !llvm.ptr -> i64
%209 = arith.addi %191, %208 : i64
%210 = llvm.getelementptr %arg4[%209] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%207 = llvm.load %210 : !llvm.ptr -> i64
%212 = llvm.load %199 : !llvm.ptr -> i64
%213 = llvm.getelementptr %116[%212] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%211 = llvm.load %213 : !llvm.ptr -> i64
%214 = arith.muli %207, %211 : i64
%215 = arith.addi %206, %214 : i64
%216 = llvm.mlir.addressof @MOD : !llvm.ptr
%217 = llvm.load %216 : !llvm.ptr -> i64
%218 = arith.remsi %215, %217 : i64
llvm.store %218, %195 : i64, !llvm.ptr
%219 = llvm.load %199 : !llvm.ptr -> i64
%220 = arith.constant 1 : i32
%222 = arith.extsi %220 : i32 to i64
%221 = arith.addi %219, %222 : i64
llvm.store %221, %199 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%223 = llvm.load %195 : !llvm.ptr -> i64
%224 = llvm.load %181 : !llvm.ptr -> i64
%225 = llvm.getelementptr %166[%224] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %223, %225 : i64, !llvm.ptr
%226 = llvm.load %181 : !llvm.ptr -> i64
%227 = arith.constant 1 : i32
%229 = arith.extsi %227 : i32 to i64
%228 = arith.addi %226, %229 : i64
llvm.store %228, %181 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%230 = arith.constant 0 : i32
%231 = arith.extsi %230 : i32 to i64
llvm.store %231, %130 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%232 = llvm.load %130 : !llvm.ptr -> i64
%233 = llvm.load %153 : !llvm.ptr -> i64
%234 = arith.cmpi sle, %232, %233 : i64
cf.cond_br %234, ^bb34, ^bb35
^bb34:
%236 = llvm.load %130 : !llvm.ptr -> i64
%237 = llvm.getelementptr %166[%236] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%235 = llvm.load %237 : !llvm.ptr -> i64
%238 = llvm.load %130 : !llvm.ptr -> i64
%239 = llvm.getelementptr %116[%238] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %235, %239 : i64, !llvm.ptr
%240 = llvm.load %130 : !llvm.ptr -> i64
%241 = arith.constant 1 : i32
%243 = arith.extsi %241 : i32 to i64
%242 = arith.addi %240, %243 : i64
llvm.store %242, %130 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
func.call @free(%166) : (!llvm.ptr) -> ()
%245 = llvm.load %153 : !llvm.ptr -> i64
%246 = arith.constant 1 : i32
%248 = arith.extsi %246 : i32 to i64
%247 = arith.subi %245, %248 : i64
llvm.store %247, %153 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%250 = arith.constant 0 : i32
%251 = arith.extsi %250 : i32 to i64
%252 = llvm.getelementptr %116[%251] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%249 = llvm.load %252 : !llvm.ptr -> i64
func.call @free(%116) : (!llvm.ptr) -> ()
func.call @free(%80) : (!llvm.ptr) -> ()
func.return %249 : i64
}
func.func @build_coeffs(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: i64) -> () {
%255 = arith.constant 2 : i32
%257 = arith.extsi %255 : i32 to i64
%256 = arith.addi %arg3, %257 : i64
%258 = arith.constant 0 : i32
%259 = arith.extsi %258 : i32 to i64
%260 = llvm.mlir.constant(1 : i64) : i64
%261 = llvm.alloca %260 x i64 : (i64) -> !llvm.ptr
llvm.store %259, %261 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%262 = llvm.load %261 : !llvm.ptr -> i64
%263 = arith.cmpi slt, %262, %arg0 : i64
cf.cond_br %263, ^bb37, ^bb38
^bb37:
%264 = llvm.load %261 : !llvm.ptr -> i64
%265 = arith.constant 1 : i32
%267 = arith.extsi %265 : i32 to i64
%266 = arith.addi %264, %267 : i64
%268 = arith.subi %266, %arg0 : i64
%269 = llvm.mlir.addressof @MOD : !llvm.ptr
%270 = llvm.load %269 : !llvm.ptr -> i64
%271 = arith.remsi %268, %270 : i64
%272 = llvm.load %261 : !llvm.ptr -> i64
%273 = arith.muli %272, %256 : i64
%274 = arith.constant 0 : i32
%276 = arith.extsi %274 : i32 to i64
%275 = arith.addi %273, %276 : i64
%277 = llvm.getelementptr %arg2[%275] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %271, %277 : i64, !llvm.ptr
%278 = llvm.mlir.addressof @MOD : !llvm.ptr
%279 = llvm.load %278 : !llvm.ptr -> i64
%280 = arith.remsi %arg0, %279 : i64
%281 = llvm.load %261 : !llvm.ptr -> i64
%282 = arith.muli %281, %256 : i64
%283 = arith.constant 1 : i32
%285 = arith.extsi %283 : i32 to i64
%284 = arith.addi %282, %285 : i64
%286 = llvm.getelementptr %arg2[%284] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %280, %286 : i64, !llvm.ptr
%287 = llvm.load %261 : !llvm.ptr -> i64
%288 = arith.constant 1 : i32
%290 = arith.extsi %288 : i32 to i64
%289 = arith.addi %287, %290 : i64
llvm.store %289, %261 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%291 = arith.constant 1 : 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
cf.br ^bb39
^bb39:
%295 = llvm.load %294 : !llvm.ptr -> i64
%296 = arith.cmpi sle, %295, %arg1 : i64
cf.cond_br %296, ^bb40, ^bb41
^bb40:
%297 = arith.constant 0 : i32
%298 = arith.extsi %297 : i32 to i64
%299 = llvm.mlir.constant(1 : i64) : i64
%300 = llvm.alloca %299 x i64 : (i64) -> !llvm.ptr
llvm.store %298, %300 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%301 = llvm.load %300 : !llvm.ptr -> i64
%302 = arith.cmpi slt, %301, %arg0 : i64
cf.cond_br %302, ^bb43, ^bb44
^bb43:
%304 = llvm.load %294 : !llvm.ptr -> i64
%305 = arith.constant 1 : i32
%307 = arith.extsi %305 : i32 to i64
%306 = arith.addi %304, %307 : i64
%308 = arith.constant 8 : i32
%309 = arith.extsi %308 : i32 to i64
%303 = func.call @calloc(%306, %309) : (i64, i64) -> !llvm.ptr
%311 = llvm.load %294 : !llvm.ptr -> i64
%312 = arith.constant 1 : i32
%314 = arith.extsi %312 : i32 to i64
%313 = arith.addi %311, %314 : i64
%315 = arith.muli %arg0, %313 : i64
%316 = arith.constant 8 : i32
%317 = arith.extsi %316 : i32 to i64
%310 = func.call @calloc(%315, %317) : (i64, i64) -> !llvm.ptr
%318 = llvm.mlir.zero : !llvm.ptr
%319 = llvm.icmp "eq" %303, %318 : !llvm.ptr
%320 = scf.if %319 -> (i1) {
%321 = arith.constant true
scf.yield %321 : i1
} else {
%322 = llvm.mlir.zero : !llvm.ptr
%323 = llvm.icmp "eq" %310, %322 : !llvm.ptr
scf.yield %323 : i1
}
cf.cond_br %320, ^bb45, ^bb46
^bb45:
%324 = llvm.mlir.zero : !llvm.ptr
%325 = llvm.icmp "ne" %303, %324 : !llvm.ptr
cf.cond_br %325, ^bb48, ^bb49
^bb48:
func.call @free(%303) : (!llvm.ptr) -> ()
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%327 = llvm.mlir.zero : !llvm.ptr
%328 = llvm.icmp "ne" %310, %327 : !llvm.ptr
cf.cond_br %328, ^bb51, ^bb52
^bb51:
func.call @free(%310) : (!llvm.ptr) -> ()
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
func.return
^bb46:
cf.br ^bb47
^bb47:
%330 = arith.constant 0 : i32
%331 = arith.extsi %330 : i32 to i64
%332 = llvm.mlir.constant(1 : i64) : i64
%333 = llvm.alloca %332 x i64 : (i64) -> !llvm.ptr
llvm.store %331, %333 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%334 = llvm.load %333 : !llvm.ptr -> i64
%335 = arith.cmpi slt, %334, %arg0 : i64
cf.cond_br %335, ^bb55, ^bb56
^bb55:
%336 = llvm.load %294 : !llvm.ptr -> i64
%337 = arith.constant 1 : i32
%339 = arith.extsi %337 : i32 to i64
%338 = arith.subi %336, %339 : i64
%340 = arith.muli %338, %arg0 : i64
%341 = llvm.load %333 : !llvm.ptr -> i64
%342 = arith.addi %340, %341 : i64
%343 = arith.muli %342, %256 : i64
%344 = arith.constant 0 : i32
%345 = arith.extsi %344 : i32 to i64
%346 = llvm.mlir.constant(1 : i64) : i64
%347 = llvm.alloca %346 x i64 : (i64) -> !llvm.ptr
llvm.store %345, %347 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%348 = llvm.load %347 : !llvm.ptr -> i64
%349 = llvm.load %294 : !llvm.ptr -> i64
%350 = arith.cmpi sle, %348, %349 : i64
cf.cond_br %350, ^bb58, ^bb59
^bb58:
%352 = llvm.load %347 : !llvm.ptr -> i64
%353 = llvm.getelementptr %303[%352] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%351 = llvm.load %353 : !llvm.ptr -> i64
%355 = llvm.load %347 : !llvm.ptr -> i64
%356 = arith.addi %343, %355 : i64
%357 = llvm.getelementptr %arg2[%356] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%354 = llvm.load %357 : !llvm.ptr -> i64
%358 = arith.addi %351, %354 : i64
%359 = llvm.mlir.addressof @MOD : !llvm.ptr
%360 = llvm.load %359 : !llvm.ptr -> i64
%361 = arith.remsi %358, %360 : i64
%362 = llvm.load %347 : !llvm.ptr -> i64
%363 = llvm.getelementptr %303[%362] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %361, %363 : i64, !llvm.ptr
%364 = llvm.load %347 : !llvm.ptr -> i64
%365 = arith.constant 1 : i32
%367 = arith.extsi %365 : i32 to i64
%366 = arith.addi %364, %367 : i64
llvm.store %366, %347 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
%368 = llvm.load %333 : !llvm.ptr -> i64
%369 = arith.constant 1 : i32
%371 = arith.extsi %369 : i32 to i64
%370 = arith.addi %368, %371 : i64
llvm.store %370, %333 : i64, !llvm.ptr
cf.br ^bb54
^bb56:
%372 = arith.constant 0 : i32
%373 = arith.extsi %372 : i32 to i64
llvm.store %373, %333 : i64, !llvm.ptr
%375 = llvm.load %294 : !llvm.ptr -> i64
%376 = arith.constant 1 : i32
%378 = arith.extsi %376 : i32 to i64
%377 = arith.addi %375, %378 : i64
%379 = arith.constant 8 : i32
%380 = arith.extsi %379 : i32 to i64
%374 = func.call @calloc(%377, %380) : (i64, i64) -> !llvm.ptr
cf.br ^bb60
^bb60:
%381 = llvm.load %333 : !llvm.ptr -> i64
%382 = arith.cmpi slt, %381, %arg0 : i64
cf.cond_br %382, ^bb61, ^bb62
^bb61:
%383 = llvm.load %294 : !llvm.ptr -> i64
%384 = arith.constant 1 : i32
%386 = arith.extsi %384 : i32 to i64
%385 = arith.subi %383, %386 : i64
%387 = arith.muli %385, %arg0 : i64
%388 = llvm.load %333 : !llvm.ptr -> i64
%389 = arith.addi %387, %388 : i64
%390 = arith.muli %389, %256 : i64
%391 = arith.constant 0 : i32
%392 = arith.extsi %391 : i32 to i64
%393 = llvm.mlir.constant(1 : i64) : i64
%394 = llvm.alloca %393 x i64 : (i64) -> !llvm.ptr
llvm.store %392, %394 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%395 = llvm.load %394 : !llvm.ptr -> i64
%396 = llvm.load %294 : !llvm.ptr -> i64
%397 = arith.cmpi sle, %395, %396 : i64
cf.cond_br %397, ^bb64, ^bb65
^bb64:
%399 = llvm.load %394 : !llvm.ptr -> i64
%400 = llvm.getelementptr %374[%399] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%398 = llvm.load %400 : !llvm.ptr -> i64
%402 = llvm.load %394 : !llvm.ptr -> i64
%403 = arith.addi %390, %402 : i64
%404 = llvm.getelementptr %arg2[%403] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%401 = llvm.load %404 : !llvm.ptr -> i64
%405 = arith.addi %398, %401 : i64
%406 = llvm.mlir.addressof @MOD : !llvm.ptr
%407 = llvm.load %406 : !llvm.ptr -> i64
%408 = arith.remsi %405, %407 : i64
%409 = llvm.load %394 : !llvm.ptr -> i64
%410 = llvm.getelementptr %374[%409] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %408, %410 : i64, !llvm.ptr
%412 = llvm.load %394 : !llvm.ptr -> i64
%413 = llvm.getelementptr %374[%412] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%411 = llvm.load %413 : !llvm.ptr -> i64
%414 = llvm.load %333 : !llvm.ptr -> i64
%415 = llvm.load %294 : !llvm.ptr -> i64
%416 = arith.constant 1 : i32
%418 = arith.extsi %416 : i32 to i64
%417 = arith.addi %415, %418 : i64
%419 = arith.muli %414, %417 : i64
%420 = llvm.load %394 : !llvm.ptr -> i64
%421 = arith.addi %419, %420 : i64
%422 = llvm.getelementptr %310[%421] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %411, %422 : i64, !llvm.ptr
%423 = llvm.load %394 : !llvm.ptr -> i64
%424 = arith.constant 1 : i32
%426 = arith.extsi %424 : i32 to i64
%425 = arith.addi %423, %426 : i64
llvm.store %425, %394 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
%427 = llvm.load %333 : !llvm.ptr -> i64
%428 = arith.constant 1 : i32
%430 = arith.extsi %428 : i32 to i64
%429 = arith.addi %427, %430 : i64
llvm.store %429, %333 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
func.call @free(%374) : (!llvm.ptr) -> ()
%432 = arith.constant 0 : i32
%433 = arith.extsi %432 : i32 to i64
%434 = llvm.mlir.constant(1 : i64) : i64
%435 = llvm.alloca %434 x i64 : (i64) -> !llvm.ptr
llvm.store %433, %435 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%436 = llvm.load %435 : !llvm.ptr -> i64
%437 = arith.cmpi slt, %436, %arg0 : i64
cf.cond_br %437, ^bb67, ^bb68
^bb67:
%438 = llvm.load %294 : !llvm.ptr -> i64
%439 = arith.muli %438, %arg0 : i64
%440 = llvm.load %435 : !llvm.ptr -> i64
%441 = arith.addi %439, %440 : i64
%442 = arith.muli %441, %256 : i64
%443 = arith.constant 0 : i32
%444 = arith.extsi %443 : i32 to i64
%445 = llvm.mlir.constant(1 : i64) : i64
%446 = llvm.alloca %445 x i64 : (i64) -> !llvm.ptr
llvm.store %444, %446 : i64, !llvm.ptr
cf.br ^bb69
^bb69:
%447 = llvm.load %446 : !llvm.ptr -> i64
%448 = llvm.load %294 : !llvm.ptr -> i64
%449 = arith.constant 1 : i32
%451 = arith.extsi %449 : i32 to i64
%450 = arith.addi %448, %451 : i64
%452 = arith.cmpi sle, %447, %450 : i64
cf.cond_br %452, ^bb70, ^bb71
^bb70:
%453 = arith.constant 0 : i32
%454 = llvm.load %446 : !llvm.ptr -> i64
%455 = arith.addi %442, %454 : i64
%456 = arith.extsi %453 : i32 to i64
%457 = llvm.getelementptr %arg2[%455] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %456, %457 : i64, !llvm.ptr
%458 = llvm.load %446 : !llvm.ptr -> i64
%459 = arith.constant 1 : i32
%461 = arith.extsi %459 : i32 to i64
%460 = arith.addi %458, %461 : i64
llvm.store %460, %446 : i64, !llvm.ptr
cf.br ^bb69
^bb71:
%463 = llvm.load %435 : !llvm.ptr -> i64
%464 = llvm.load %294 : !llvm.ptr -> i64
%465 = arith.constant 1 : i32
%467 = arith.extsi %465 : i32 to i64
%466 = arith.addi %464, %467 : i64
%468 = arith.muli %463, %466 : i64
%469 = arith.constant 0 : i32
%471 = arith.extsi %469 : i32 to i64
%470 = arith.addi %468, %471 : i64
%472 = llvm.getelementptr %310[%470] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%462 = llvm.load %472 : !llvm.ptr -> i64
%474 = arith.constant 0 : i32
%475 = arith.extsi %474 : i32 to i64
%476 = llvm.getelementptr %303[%475] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%473 = llvm.load %476 : !llvm.ptr -> i64
%477 = arith.subi %462, %473 : i64
%478 = llvm.mlir.addressof @MOD : !llvm.ptr
%479 = llvm.load %478 : !llvm.ptr -> i64
%480 = arith.remsi %477, %479 : i64
%481 = arith.constant 0 : i32
%483 = arith.extsi %481 : i32 to i64
%482 = arith.addi %442, %483 : i64
%484 = llvm.getelementptr %arg2[%482] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %480, %484 : i64, !llvm.ptr
%486 = arith.constant 0 : i32
%488 = arith.extsi %486 : i32 to i64
%487 = arith.addi %442, %488 : i64
%489 = llvm.getelementptr %arg2[%487] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%485 = llvm.load %489 : !llvm.ptr -> i64
%490 = arith.constant 0 : i32
%492 = arith.extsi %490 : i32 to i64
%491 = arith.cmpi slt, %485, %492 : i64
cf.cond_br %491, ^bb72, ^bb73
^bb72:
%494 = arith.constant 0 : i32
%496 = arith.extsi %494 : i32 to i64
%495 = arith.addi %442, %496 : i64
%497 = llvm.getelementptr %arg2[%495] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%493 = llvm.load %497 : !llvm.ptr -> i64
%498 = llvm.mlir.addressof @MOD : !llvm.ptr
%499 = llvm.load %498 : !llvm.ptr -> i64
%500 = arith.addi %493, %499 : i64
%501 = arith.constant 0 : i32
%503 = arith.extsi %501 : i32 to i64
%502 = arith.addi %442, %503 : i64
%504 = llvm.getelementptr %arg2[%502] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %500, %504 : i64, !llvm.ptr
cf.br ^bb74
^bb73:
cf.br ^bb74
^bb74:
%505 = arith.constant 1 : i32
%506 = arith.extsi %505 : i32 to i64
llvm.store %506, %446 : i64, !llvm.ptr
cf.br ^bb75
^bb75:
%507 = llvm.load %446 : !llvm.ptr -> i64
%508 = llvm.load %294 : !llvm.ptr -> i64
%509 = arith.cmpi sle, %507, %508 : i64
cf.cond_br %509, ^bb76, ^bb77
^bb76:
%511 = llvm.load %435 : !llvm.ptr -> i64
%512 = llvm.load %294 : !llvm.ptr -> i64
%513 = arith.constant 1 : i32
%515 = arith.extsi %513 : i32 to i64
%514 = arith.addi %512, %515 : i64
%516 = arith.muli %511, %514 : i64
%517 = llvm.load %446 : !llvm.ptr -> i64
%518 = arith.addi %516, %517 : i64
%519 = llvm.getelementptr %310[%518] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%510 = llvm.load %519 : !llvm.ptr -> i64
%521 = llvm.load %446 : !llvm.ptr -> i64
%522 = llvm.getelementptr %303[%521] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%520 = llvm.load %522 : !llvm.ptr -> i64
%523 = arith.subi %510, %520 : i64
%525 = llvm.load %446 : !llvm.ptr -> i64
%526 = arith.constant 1 : i32
%528 = arith.extsi %526 : i32 to i64
%527 = arith.subi %525, %528 : i64
%529 = llvm.getelementptr %303[%527] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%524 = llvm.load %529 : !llvm.ptr -> i64
%530 = arith.addi %523, %524 : i64
%531 = llvm.mlir.constant(1 : i64) : i64
%532 = llvm.alloca %531 x i64 : (i64) -> !llvm.ptr
llvm.store %530, %532 : i64, !llvm.ptr
%533 = llvm.load %532 : !llvm.ptr -> i64
%534 = llvm.mlir.addressof @MOD : !llvm.ptr
%535 = llvm.load %534 : !llvm.ptr -> i64
%536 = arith.remsi %533, %535 : i64
llvm.store %536, %532 : i64, !llvm.ptr
%537 = llvm.load %532 : !llvm.ptr -> i64
%538 = arith.constant 0 : i32
%540 = arith.extsi %538 : i32 to i64
%539 = arith.cmpi slt, %537, %540 : i64
cf.cond_br %539, ^bb78, ^bb79
^bb78:
%541 = llvm.load %532 : !llvm.ptr -> i64
%542 = llvm.mlir.addressof @MOD : !llvm.ptr
%543 = llvm.load %542 : !llvm.ptr -> i64
%544 = arith.addi %541, %543 : i64
llvm.store %544, %532 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%545 = llvm.load %532 : !llvm.ptr -> i64
%546 = llvm.load %446 : !llvm.ptr -> i64
%547 = arith.addi %442, %546 : i64
%548 = llvm.getelementptr %arg2[%547] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %545, %548 : i64, !llvm.ptr
%549 = llvm.load %446 : !llvm.ptr -> i64
%550 = arith.constant 1 : i32
%552 = arith.extsi %550 : i32 to i64
%551 = arith.addi %549, %552 : i64
llvm.store %551, %446 : i64, !llvm.ptr
cf.br ^bb75
^bb77:
%554 = llvm.load %294 : !llvm.ptr -> i64
%555 = llvm.getelementptr %303[%554] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%553 = llvm.load %555 : !llvm.ptr -> i64
%556 = llvm.mlir.addressof @MOD : !llvm.ptr
%557 = llvm.load %556 : !llvm.ptr -> i64
%558 = arith.remsi %553, %557 : i64
%559 = llvm.load %294 : !llvm.ptr -> i64
%560 = arith.addi %442, %559 : i64
%561 = arith.constant 1 : i32
%563 = arith.extsi %561 : i32 to i64
%562 = arith.addi %560, %563 : i64
%564 = llvm.getelementptr %arg2[%562] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %558, %564 : i64, !llvm.ptr
%565 = llvm.load %435 : !llvm.ptr -> i64
%566 = arith.constant 1 : i32
%568 = arith.extsi %566 : i32 to i64
%567 = arith.addi %565, %568 : i64
llvm.store %567, %435 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
func.call @free(%303) : (!llvm.ptr) -> ()
func.call @free(%310) : (!llvm.ptr) -> ()
%571 = llvm.load %300 : !llvm.ptr -> i64
%572 = arith.constant 1 : i32
%574 = arith.extsi %572 : i32 to i64
%573 = arith.addi %571, %574 : i64
llvm.store %573, %300 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%575 = llvm.load %294 : !llvm.ptr -> i64
%576 = arith.constant 1 : i32
%578 = arith.extsi %576 : i32 to i64
%577 = arith.addi %575, %578 : i64
llvm.store %577, %294 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
func.return
}
func.func @compute_depth(%arg0: i64, %arg1: i64) -> i64 {
%579 = arith.constant 0 : i32
%580 = arith.extsi %579 : i32 to i64
%581 = llvm.mlir.constant(1 : i64) : i64
%582 = llvm.alloca %581 x i64 : (i64) -> !llvm.ptr
llvm.store %580, %582 : i64, !llvm.ptr
%583 = llvm.mlir.constant(1 : i64) : i64
%584 = llvm.alloca %583 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %584 : i64, !llvm.ptr
cf.br ^bb81
^bb81:
%585 = llvm.load %584 : !llvm.ptr -> i64
%586 = arith.cmpi sge, %585, %arg0 : i64
cf.cond_br %586, ^bb82, ^bb83
^bb82:
%587 = llvm.load %582 : !llvm.ptr -> i64
%588 = arith.constant 1 : i32
%590 = arith.extsi %588 : i32 to i64
%589 = arith.addi %587, %590 : i64
llvm.store %589, %582 : i64, !llvm.ptr
%591 = llvm.load %584 : !llvm.ptr -> i64
%592 = arith.divsi %591, %arg0 : i64
llvm.store %592, %584 : i64, !llvm.ptr
cf.br ^bb81
^bb83:
%593 = llvm.load %582 : !llvm.ptr -> i64
func.return %593 : i64
}
func.func @main() -> i32 {
%594 = arith.constant 200 : i32
%595 = arith.extsi %594 : i32 to i64
%597 = arith.constant 1 : i32
%599 = arith.extsi %597 : i32 to i64
%598 = arith.addi %595, %599 : i64
%600 = arith.constant 8 : i32
%601 = arith.extsi %600 : i32 to i64
%596 = func.call @calloc(%598, %601) : (i64, i64) -> !llvm.ptr
%603 = arith.constant 1 : i32
%605 = arith.extsi %603 : i32 to i64
%604 = arith.addi %595, %605 : i64
%606 = arith.constant 8 : i32
%607 = arith.extsi %606 : i32 to i64
%602 = func.call @calloc(%604, %607) : (i64, i64) -> !llvm.ptr
%608 = llvm.mlir.zero : !llvm.ptr
%609 = llvm.icmp "eq" %596, %608 : !llvm.ptr
%610 = scf.if %609 -> (i1) {
%611 = arith.constant true
scf.yield %611 : i1
} else {
%612 = llvm.mlir.zero : !llvm.ptr
%613 = llvm.icmp "eq" %602, %612 : !llvm.ptr
scf.yield %613 : i1
}
cf.cond_br %610, ^bb84, ^bb85
^bb84:
%614 = arith.constant 1 : i32
func.return %614 : i32
^bb85:
cf.br ^bb86
^bb86:
%615 = arith.constant 1 : i32
%616 = arith.constant 0 : i32
%617 = arith.extsi %615 : i32 to i64
%618 = arith.extsi %616 : i32 to i64
%619 = llvm.getelementptr %596[%618] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %617, %619 : i64, !llvm.ptr
%620 = arith.constant 1 : i32
%621 = arith.extsi %620 : i32 to i64
%622 = llvm.mlir.constant(1 : i64) : i64
%623 = llvm.alloca %622 x i64 : (i64) -> !llvm.ptr
llvm.store %621, %623 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%624 = llvm.load %623 : !llvm.ptr -> i64
%625 = arith.cmpi sle, %624, %595 : i64
cf.cond_br %625, ^bb88, ^bb89
^bb88:
%627 = llvm.load %623 : !llvm.ptr -> i64
%628 = arith.constant 1 : i32
%630 = arith.extsi %628 : i32 to i64
%629 = arith.subi %627, %630 : i64
%631 = llvm.getelementptr %596[%629] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%626 = llvm.load %631 : !llvm.ptr -> i64
%632 = arith.extsi %626 : i64 to i128
%633 = llvm.load %623 : !llvm.ptr -> i64
%634 = arith.extsi %633 : i64 to i128
%636 = arith.trunci %632 : i128 to i64
%637 = arith.trunci %634 : i128 to i64
%635 = arith.muli %636, %637 : i64
%638 = llvm.mlir.addressof @MOD : !llvm.ptr
%639 = llvm.load %638 : !llvm.ptr -> i64
%640 = arith.extsi %639 : i64 to i128
%642 = arith.trunci %640 : i128 to i64
%641 = arith.remsi %635, %642 : i64
%643 = llvm.load %623 : !llvm.ptr -> i64
%644 = llvm.getelementptr %596[%643] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %641, %644 : i64, !llvm.ptr
%645 = llvm.load %623 : !llvm.ptr -> i64
%646 = arith.constant 1 : i32
%648 = arith.extsi %646 : i32 to i64
%647 = arith.addi %645, %648 : i64
llvm.store %647, %623 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%651 = llvm.getelementptr %596[%595] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%650 = llvm.load %651 : !llvm.ptr -> i64
%652 = llvm.mlir.addressof @MOD : !llvm.ptr
%653 = llvm.load %652 : !llvm.ptr -> i64
%654 = arith.constant 2 : i32
%656 = arith.extsi %654 : i32 to i64
%655 = arith.subi %653, %656 : i64
%657 = llvm.mlir.addressof @MOD : !llvm.ptr
%658 = llvm.load %657 : !llvm.ptr -> i64
%649 = func.call @modpow(%650, %655, %658) : (i64, i64, i64) -> i64
%659 = llvm.getelementptr %602[%595] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %649, %659 : i64, !llvm.ptr
llvm.store %595, %623 : i64, !llvm.ptr
cf.br ^bb90
^bb90:
%660 = llvm.load %623 : !llvm.ptr -> i64
%661 = arith.constant 0 : i32
%663 = arith.extsi %661 : i32 to i64
%662 = arith.cmpi sgt, %660, %663 : i64
cf.cond_br %662, ^bb91, ^bb92
^bb91:
%665 = llvm.load %623 : !llvm.ptr -> i64
%666 = llvm.getelementptr %602[%665] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%664 = llvm.load %666 : !llvm.ptr -> i64
%667 = arith.extsi %664 : i64 to i128
%668 = llvm.load %623 : !llvm.ptr -> i64
%669 = arith.extsi %668 : i64 to i128
%671 = arith.trunci %667 : i128 to i64
%672 = arith.trunci %669 : i128 to i64
%670 = arith.muli %671, %672 : i64
%673 = llvm.mlir.addressof @MOD : !llvm.ptr
%674 = llvm.load %673 : !llvm.ptr -> i64
%675 = arith.extsi %674 : i64 to i128
%677 = arith.trunci %675 : i128 to i64
%676 = arith.remsi %670, %677 : i64
%678 = llvm.load %623 : !llvm.ptr -> i64
%679 = arith.constant 1 : i32
%681 = arith.extsi %679 : i32 to i64
%680 = arith.subi %678, %681 : i64
%682 = llvm.getelementptr %602[%680] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %676, %682 : i64, !llvm.ptr
%683 = llvm.load %623 : !llvm.ptr -> i64
%684 = arith.constant 1 : i32
%686 = arith.extsi %684 : i32 to i64
%685 = arith.subi %683, %686 : i64
llvm.store %685, %623 : i64, !llvm.ptr
cf.br ^bb90
^bb92:
%687 = arith.constant 0 : i32
%688 = arith.extsi %687 : i32 to i64
%689 = llvm.mlir.constant(1 : i64) : i64
%690 = llvm.alloca %689 x i64 : (i64) -> !llvm.ptr
llvm.store %688, %690 : i64, !llvm.ptr
%691 = arith.constant 2 : i32
%692 = arith.extsi %691 : i32 to i64
%693 = llvm.mlir.constant(1 : i64) : i64
%694 = llvm.alloca %693 x i64 : (i64) -> !llvm.ptr
llvm.store %692, %694 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%695 = llvm.load %694 : !llvm.ptr -> i64
%696 = arith.constant 10 : i32
%698 = arith.extsi %696 : i32 to i64
%697 = arith.cmpi sle, %695, %698 : i64
cf.cond_br %697, ^bb94, ^bb95
^bb94:
%700 = llvm.load %694 : !llvm.ptr -> i64
%701 = llvm.mlir.addressof @N : !llvm.ptr
%702 = llvm.load %701 : !llvm.ptr -> i64
%699 = func.call @compute_depth(%700, %702) : (i64, i64) -> i64
%703 = arith.constant 2 : i32
%705 = arith.extsi %703 : i32 to i64
%704 = arith.addi %699, %705 : i64
%707 = arith.constant 1 : i32
%709 = arith.extsi %707 : i32 to i64
%708 = arith.addi %699, %709 : i64
%710 = llvm.load %694 : !llvm.ptr -> i64
%711 = arith.muli %708, %710 : i64
%712 = arith.muli %711, %704 : i64
%713 = arith.constant 8 : i32
%714 = arith.extsi %713 : i32 to i64
%706 = func.call @calloc(%712, %714) : (i64, i64) -> !llvm.ptr
%715 = llvm.mlir.zero : !llvm.ptr
%716 = llvm.icmp "eq" %706, %715 : !llvm.ptr
cf.cond_br %716, ^bb96, ^bb97
^bb96:
cf.br ^bb95
^bb97:
cf.br ^bb98
^bb98:
%718 = llvm.load %694 : !llvm.ptr -> i64
func.call @build_coeffs(%718, %699, %706, %699) : (i64, i64, !llvm.ptr, i64) -> ()
%719 = llvm.load %690 : !llvm.ptr -> i64
%721 = llvm.load %694 : !llvm.ptr -> i64
%722 = llvm.mlir.addressof @N : !llvm.ptr
%723 = llvm.load %722 : !llvm.ptr -> i64
%720 = func.call @fk_mod(%721, %723, %596, %602, %706, %699) : (i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> i64
%724 = arith.addi %719, %720 : i64
%725 = llvm.mlir.addressof @MOD : !llvm.ptr
%726 = llvm.load %725 : !llvm.ptr -> i64
%727 = arith.remsi %724, %726 : i64
llvm.store %727, %690 : i64, !llvm.ptr
func.call @free(%706) : (!llvm.ptr) -> ()
%729 = llvm.load %694 : !llvm.ptr -> i64
%730 = arith.constant 1 : i32
%732 = arith.extsi %730 : i32 to i64
%731 = arith.addi %729, %732 : i64
llvm.store %731, %694 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%733 = llvm.mlir.addressof @str_0 : !llvm.ptr
%734 = llvm.load %690 : !llvm.ptr -> i64
%735 = llvm.call @printf(%733, %734) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%596) : (!llvm.ptr) -> ()
func.call @free(%602) : (!llvm.ptr) -> ()
%738 = arith.constant 0 : i32
func.return %738 : i32
}
}