← All problems Problem 759
Squared Recurrence — S(10^16) mod 10^9+7. Ported from native C to pure Flow. Uses 3x3 matrix accumulation over bit ranges with a recursive shift-and-add.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^3)O(n log n)Space complexity O(n)O(n)Approach Flow solution Modular DP or matrix exponentiation Verdict Suboptimal
Flow source
# Project Euler 759
# Squared Recurrence — S(10^16) mod 10^9+7.
# Ported from native C to pure Flow. Uses 3x3 matrix accumulation
# over bit ranges with a recursive shift-and-add.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000000007
const MAXB: i64 = 60
# Matrices stored as flat i64 arrays: 9 entries per matrix.
# full is a heap array of (MAXB+1)*9 i64 values.
# Global pointer to precomputed full matrices.
let mut full: ptr<i64> = null
function zero_arr(out: ptr<i64>) -> void {
for i in 0..9 {
out[i] = 0
}
}
function addm(out: ptr<i64>, a: ptr<i64>, b: ptr<i64>) -> void {
for i in 0..9 {
out[i] = (a[i] + b[i]) % MOD
}
}
function copy_mat(dst: ptr<i64>, src: ptr<i64>) -> void {
for i in 0..9 {
dst[i] = src[i]
}
}
# Shift a matrix's range by p: multiply columns by powers of p.
function shift_range(out: ptr<i64>, mat: ptr<i64>, p0: i64) -> void {
let p: i64 = p0 % MOD
let p2: i64 = p * p % MOD
let two_p: i64 = 2 * p % MOD
# mats[t][d] = transformed row t of mat
let mats: array<i64, 9> = [0, 0, 0, 0, 0, 0, 0, 0, 0]
for t in 0..3 {
let s0: i64 = mat[t * 3 + 0] % MOD
let s1: i64 = mat[t * 3 + 1] % MOD
let s2: i64 = mat[t * 3 + 2] % MOD
mats[t * 3 + 0] = s0
mats[t * 3 + 1] = (p * s0 + s1) % MOD
mats[t * 3 + 2] = (p2 * s0 + two_p * s1 + s2) % MOD
}
# coeffs[j][k]
let coeffs: array<i32, 9> = [1, 0, 0, 1, 1, 0, 1, 2, 1]
zero_arr(out)
for j in 0..3 {
for d in 0..3 {
let mut acc: i64 = 0
for k in 0..3 {
let c: i64 = coeffs[j * 3 + k] as i64
acc = (acc + c * mats[k * 3 + d]) % MOD
}
out[j * 3 + d] = acc
}
}
}
function precompute(max_bits: i64) -> void {
full = calloc((max_bits + 1) * 9, 8) as ptr<i64>
# full[0] = identity-like: full[0][0][0] = 1
full[0] = 1
for m in 1..(max_bits + 1) {
let sh: array<i64, 9> = [0, 0, 0, 0, 0, 0, 0, 0, 0]
shift_range(&sh[0], &full[(m - 1) * 9], (1 as i64) << (m - 1))
let fm: ptr<i64> = &full[m * 9]
let fmm1: ptr<i64> = &full[(m - 1) * 9]
addm(fm, fmm1, &sh[0])
}
}
# Returns floor(log2(n)) for n > 0, i.e. the position of the highest set bit.
function highest_bit(n: i64) -> i64 {
let mut k: i64 = 0
let mut x: i64 = n
while x > 1 {
x = x >> 1
k = k + 1
}
return k
}
function calc_upto(out: ptr<i64>, n: i64) -> void {
if n < 0 {
zero_arr(out)
return
}
if n == 0 {
copy_mat(out, &full[0])
return
}
let k: i64 = highest_bit(n)
let p: i64 = (1 as i64) << k
if n == p - 1 {
copy_mat(out, &full[k * 9])
return
}
let left: array<i64, 9> = [0, 0, 0, 0, 0, 0, 0, 0, 0]
copy_mat(&left[0], &full[k * 9])
let right_in: array<i64, 9> = [0, 0, 0, 0, 0, 0, 0, 0, 0]
calc_upto(&right_in[0], n - p)
let sh: array<i64, 9> = [0, 0, 0, 0, 0, 0, 0, 0, 0]
shift_range(&sh[0], &right_in[0], p)
addm(out, &left[0], &sh[0])
}
function main() -> i32 {
let n: i64 = 10000000000000000
precompute(60)
let m: array<i64, 9> = [0, 0, 0, 0, 0, 0, 0, 0, 0]
calc_upto(&m[0], n)
printf("%lld\n", m[8] % MOD)
free(full as ptr<void>)
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; }
void zero_arr_ptr_i64(int64_t* out);
void addm_ptr_i64_ptr_i64_ptr_i64(int64_t* out, int64_t* a, int64_t* b);
void copy_mat_ptr_i64_ptr_i64(int64_t* dst, int64_t* src);
void shift_range_ptr_i64_ptr_i64_i64(int64_t* out, int64_t* mat, int64_t p0);
void precompute_i64(int64_t max_bits);
int64_t highest_bit_i64(int64_t n);
void calc_upto_ptr_i64_i64(int64_t* out, int64_t n);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int64_t MAXB = 60;
/* Module statics */
static int64_t* full = NULL;
void zero_arr_ptr_i64(int64_t* out) {
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= 9) ? i < 9 : i > 9; i += (0 <= 9) ? 1 : -1) {
out[i] = 0;
}
}
void addm_ptr_i64_ptr_i64_ptr_i64(int64_t* out, int64_t* a, int64_t* b) {
int32_t __flow_step_2 = 1;
for (int32_t i = 0; (0 <= 9) ? i < 9 : i > 9; i += (0 <= 9) ? 1 : -1) {
out[i] = FLOW_CHECKED_MOD(((a[i] + b[i])), (MOD));
}
}
void copy_mat_ptr_i64_ptr_i64(int64_t* dst, int64_t* src) {
int32_t __flow_step_3 = 1;
for (int32_t i = 0; (0 <= 9) ? i < 9 : i > 9; i += (0 <= 9) ? 1 : -1) {
dst[i] = src[i];
}
}
void shift_range_ptr_i64_ptr_i64_i64(int64_t* out, int64_t* mat, int64_t p0) {
int64_t p = FLOW_CHECKED_MOD((p0), (MOD));
int64_t p2 = FLOW_CHECKED_MOD(((p * p)), (MOD));
int64_t two_p = FLOW_CHECKED_MOD(((2 * p)), (MOD));
int64_t mats[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
int32_t __flow_step_4 = 1;
for (int32_t t = 0; (0 <= 3) ? t < 3 : t > 3; t += (0 <= 3) ? 1 : -1) {
int64_t s0 = FLOW_CHECKED_MOD((mat[((t * 3) + 0)]), (MOD));
int64_t s1 = FLOW_CHECKED_MOD((mat[((t * 3) + 1)]), (MOD));
int64_t s2 = FLOW_CHECKED_MOD((mat[((t * 3) + 2)]), (MOD));
mats[((t * 3) + 0)] = s0;
mats[((t * 3) + 1)] = FLOW_CHECKED_MOD((((p * s0) + s1)), (MOD));
mats[((t * 3) + 2)] = FLOW_CHECKED_MOD(((((p2 * s0) + (two_p * s1)) + s2)), (MOD));
}
int32_t coeffs[9] = { 1, 0, 0, 1, 1, 0, 1, 2, 1 };
zero_arr_ptr_i64(out);
int32_t __flow_step_5 = 1;
for (int32_t j = 0; (0 <= 3) ? j < 3 : j > 3; j += (0 <= 3) ? 1 : -1) {
int32_t __flow_step_6 = 1;
for (int32_t d = 0; (0 <= 3) ? d < 3 : d > 3; d += (0 <= 3) ? 1 : -1) {
int64_t acc = 0;
int32_t __flow_step_7 = 1;
for (int32_t k = 0; (0 <= 3) ? k < 3 : k > 3; k += (0 <= 3) ? 1 : -1) {
int64_t c = ((int64_t)((((unsigned)(((j * 3) + k)) < 9) ? coeffs[((j * 3) + k)] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(((j * 3) + k)), 9), flow_fault_handler("array index out of bounds"), coeffs[0]))));
acc = FLOW_CHECKED_MOD(((acc + (c * (((unsigned)(((k * 3) + d)) < 9) ? mats[((k * 3) + d)] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(((k * 3) + d)), 9), flow_fault_handler("array index out of bounds"), mats[0]))))), (MOD));
}
out[((j * 3) + d)] = acc;
}
}
}
void precompute_i64(int64_t max_bits) {
full = ((int64_t*)(calloc(((max_bits + 1) * 9), 8)));
full[0] = 1;
int32_t __flow_step_8 = 1;
for (int32_t m = 1; (1 <= (max_bits + 1)) ? m < (max_bits + 1) : m > (max_bits + 1); m += (1 <= (max_bits + 1)) ? 1 : -1) {
int64_t sh[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
shift_range_ptr_i64_ptr_i64_i64((&(sh[0])), (&(full[((m - 1) * 9)])), FLOW_CHECKED_SHL((((int64_t)(1))), ((m - 1))));
int64_t* fm = (int64_t*)((&(full[(m * 9)])));
int64_t* fmm1 = (int64_t*)((&(full[((m - 1) * 9)])));
addm_ptr_i64_ptr_i64_ptr_i64(fm, fmm1, (&(sh[0])));
}
}
int64_t highest_bit_i64(int64_t n) {
int64_t k = 0;
int64_t x = n;
while (x > 1) {
x = FLOW_CHECKED_SHR((x), (1));
k = (k + 1);
}
return k;
}
void calc_upto_ptr_i64_i64(int64_t* out, int64_t n) {
if (n < 0) {
zero_arr_ptr_i64(out);
return;
}
if (n == 0) {
copy_mat_ptr_i64_ptr_i64(out, (&(full[0])));
return;
}
int64_t k = highest_bit_i64(n);
int64_t p = FLOW_CHECKED_SHL((((int64_t)(1))), (k));
if (n == (p - 1)) {
copy_mat_ptr_i64_ptr_i64(out, (&(full[(k * 9)])));
return;
}
int64_t left[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
copy_mat_ptr_i64_ptr_i64((&(left[0])), (&(full[(k * 9)])));
int64_t right_in[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
calc_upto_ptr_i64_i64((&(right_in[0])), (n - p));
int64_t sh[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
shift_range_ptr_i64_ptr_i64_i64((&(sh[0])), (&(right_in[0])), p);
addm_ptr_i64_ptr_i64_ptr_i64(out, (&(left[0])), (&(sh[0])));
}
int32_t main(void) {
int64_t n = 10000000000000000;
precompute_i64(60);
int64_t m[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
calc_upto_ptr_i64_i64((&(m[0])), n);
printf("%lld\n", FLOW_CHECKED_MOD(((((unsigned)(8) < 9) ? m[8] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(8), 9), flow_fault_handler("array index out of bounds"), m[0]))), (MOD)));
free(((void*)(full)));
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: MAXB
llvm.mlir.global internal constant @MAXB(60 : i64) : i64
// Module static: full
llvm.mlir.global internal @full() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
func.func @zero_arr(%arg0: !llvm.ptr) -> () {
%1 = arith.constant 0 : i32
%2 = arith.constant 9 : i32
%3 = arith.index_cast %1 : i32 to index
%4 = arith.index_cast %2 : i32 to index
%6 = arith.constant 1 : index
%7 = arith.constant -1 : index
%8 = arith.cmpi sle, %3, %4 : index
%5 = arith.select %8, %6, %7 : index
cf.br ^bb0(%3 : index)
^bb0(%9: index):
%10 = arith.cmpi slt, %9, %4 : index
%11 = arith.cmpi sgt, %9, %4 : index
%12 = arith.select %8, %10, %11 : i1
cf.cond_br %12, ^bb1(%9 : index), ^bb2(%9 : index)
^bb1(%13: index):
%14 = arith.constant 0 : i32
%15 = arith.extsi %14 : i32 to i64
%16 = arith.index_cast %13 : index to i64
%17 = llvm.getelementptr %arg0[%16] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %15, %17 : i64, !llvm.ptr
%18 = arith.addi %13, %5 : index
cf.br ^bb0(%18 : index)
^bb2(%19: index):
func.return
}
func.func @addm(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%20 = arith.constant 0 : i32
%21 = arith.constant 9 : i32
%22 = arith.index_cast %20 : i32 to index
%23 = arith.index_cast %21 : i32 to index
%25 = arith.constant 1 : index
%26 = arith.constant -1 : index
%27 = arith.cmpi sle, %22, %23 : index
%24 = arith.select %27, %25, %26 : index
cf.br ^bb3(%22 : index)
^bb3(%28: index):
%29 = arith.cmpi slt, %28, %23 : index
%30 = arith.cmpi sgt, %28, %23 : index
%31 = arith.select %27, %29, %30 : i1
cf.cond_br %31, ^bb4(%28 : index), ^bb5(%28 : index)
^bb4(%32: index):
%34 = arith.index_cast %32 : index to i64
%35 = llvm.getelementptr %arg1[%34] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%33 = llvm.load %35 : !llvm.ptr -> i64
%37 = arith.index_cast %32 : index to i64
%38 = llvm.getelementptr %arg2[%37] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%36 = llvm.load %38 : !llvm.ptr -> i64
%39 = arith.addi %33, %36 : i64
%40 = llvm.mlir.addressof @MOD : !llvm.ptr
%41 = llvm.load %40 : !llvm.ptr -> i64
%42 = arith.remsi %39, %41 : i64
%43 = arith.index_cast %32 : index to i64
%44 = llvm.getelementptr %arg0[%43] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %42, %44 : i64, !llvm.ptr
%45 = arith.addi %32, %24 : index
cf.br ^bb3(%45 : index)
^bb5(%46: index):
func.return
}
func.func @copy_mat(%arg0: !llvm.ptr, %arg1: !llvm.ptr) -> () {
%47 = arith.constant 0 : i32
%48 = arith.constant 9 : i32
%49 = arith.index_cast %47 : i32 to index
%50 = arith.index_cast %48 : i32 to index
%52 = arith.constant 1 : index
%53 = arith.constant -1 : index
%54 = arith.cmpi sle, %49, %50 : index
%51 = arith.select %54, %52, %53 : index
cf.br ^bb6(%49 : index)
^bb6(%55: index):
%56 = arith.cmpi slt, %55, %50 : index
%57 = arith.cmpi sgt, %55, %50 : index
%58 = arith.select %54, %56, %57 : i1
cf.cond_br %58, ^bb7(%55 : index), ^bb8(%55 : index)
^bb7(%59: index):
%61 = arith.index_cast %59 : index to i64
%62 = llvm.getelementptr %arg1[%61] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%60 = llvm.load %62 : !llvm.ptr -> i64
%63 = arith.index_cast %59 : index to i64
%64 = llvm.getelementptr %arg0[%63] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %60, %64 : i64, !llvm.ptr
%65 = arith.addi %59, %51 : index
cf.br ^bb6(%65 : index)
^bb8(%66: index):
func.return
}
func.func @shift_range(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i64) -> () {
%67 = llvm.mlir.addressof @MOD : !llvm.ptr
%68 = llvm.load %67 : !llvm.ptr -> i64
%69 = arith.remsi %arg2, %68 : i64
%70 = arith.muli %69, %69 : i64
%71 = llvm.mlir.addressof @MOD : !llvm.ptr
%72 = llvm.load %71 : !llvm.ptr -> i64
%73 = arith.remsi %70, %72 : i64
%74 = arith.constant 2 : i32
%76 = arith.extsi %74 : i32 to i64
%75 = arith.muli %76, %69 : i64
%77 = llvm.mlir.addressof @MOD : !llvm.ptr
%78 = llvm.load %77 : !llvm.ptr -> i64
%79 = arith.remsi %75, %78 : i64
%81 = arith.constant 0 : i32
%82 = arith.constant 0 : i32
%83 = arith.constant 0 : i32
%84 = arith.constant 0 : i32
%85 = arith.constant 0 : i32
%86 = arith.constant 0 : i32
%87 = arith.constant 0 : i32
%88 = arith.constant 0 : i32
%89 = arith.constant 0 : i32
%90 = llvm.mlir.constant(1 : i64) : i64
%91 = llvm.alloca %90 x !llvm.array<9 x i64> : (i64) -> !llvm.ptr
%92 = llvm.mlir.zero : !llvm.array<9 x i64>
llvm.store %92, %91 : !llvm.array<9 x i64>, !llvm.ptr
%93 = arith.extsi %81 : i32 to i64
%94 = arith.extsi %82 : i32 to i64
%95 = arith.extsi %83 : i32 to i64
%96 = arith.extsi %84 : i32 to i64
%97 = arith.extsi %85 : i32 to i64
%98 = arith.extsi %86 : i32 to i64
%99 = arith.extsi %87 : i32 to i64
%100 = arith.extsi %88 : i32 to i64
%101 = arith.extsi %89 : i32 to i64
%102 = llvm.mlir.constant(0 : i64) : i64
%103 = llvm.getelementptr %91[0, %102] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %93, %103 : i64, !llvm.ptr
%104 = llvm.mlir.constant(1 : i64) : i64
%105 = llvm.getelementptr %91[0, %104] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %94, %105 : i64, !llvm.ptr
%106 = llvm.mlir.constant(2 : i64) : i64
%107 = llvm.getelementptr %91[0, %106] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %95, %107 : i64, !llvm.ptr
%108 = llvm.mlir.constant(3 : i64) : i64
%109 = llvm.getelementptr %91[0, %108] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %96, %109 : i64, !llvm.ptr
%110 = llvm.mlir.constant(4 : i64) : i64
%111 = llvm.getelementptr %91[0, %110] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %97, %111 : i64, !llvm.ptr
%112 = llvm.mlir.constant(5 : i64) : i64
%113 = llvm.getelementptr %91[0, %112] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %98, %113 : i64, !llvm.ptr
%114 = llvm.mlir.constant(6 : i64) : i64
%115 = llvm.getelementptr %91[0, %114] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %99, %115 : i64, !llvm.ptr
%116 = llvm.mlir.constant(7 : i64) : i64
%117 = llvm.getelementptr %91[0, %116] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %100, %117 : i64, !llvm.ptr
%118 = llvm.mlir.constant(8 : i64) : i64
%119 = llvm.getelementptr %91[0, %118] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %101, %119 : i64, !llvm.ptr
%120 = arith.constant 0 : i32
%121 = arith.constant 3 : i32
%122 = arith.index_cast %120 : i32 to index
%123 = arith.index_cast %121 : i32 to index
%125 = arith.constant 1 : index
%126 = arith.constant -1 : index
%127 = arith.cmpi sle, %122, %123 : index
%124 = arith.select %127, %125, %126 : index
cf.br ^bb9(%122 : index)
^bb9(%128: index):
%129 = arith.cmpi slt, %128, %123 : index
%130 = arith.cmpi sgt, %128, %123 : index
%131 = arith.select %127, %129, %130 : i1
cf.cond_br %131, ^bb10(%128 : index), ^bb11(%128 : index)
^bb10(%132: index):
%134 = arith.constant 3 : i32
%136 = arith.index_cast %132 : index to i32
%135 = arith.muli %136, %134 : i32
%137 = arith.constant 0 : i32
%138 = arith.addi %135, %137 : i32
%139 = arith.extsi %138 : i32 to i64
%140 = llvm.getelementptr %arg1[%139] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%133 = llvm.load %140 : !llvm.ptr -> i64
%141 = llvm.mlir.addressof @MOD : !llvm.ptr
%142 = llvm.load %141 : !llvm.ptr -> i64
%143 = arith.remsi %133, %142 : i64
%145 = arith.constant 3 : i32
%147 = arith.index_cast %132 : index to i32
%146 = arith.muli %147, %145 : i32
%148 = arith.constant 1 : i32
%149 = arith.addi %146, %148 : i32
%150 = arith.extsi %149 : i32 to i64
%151 = llvm.getelementptr %arg1[%150] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%144 = llvm.load %151 : !llvm.ptr -> i64
%152 = llvm.mlir.addressof @MOD : !llvm.ptr
%153 = llvm.load %152 : !llvm.ptr -> i64
%154 = arith.remsi %144, %153 : i64
%156 = arith.constant 3 : i32
%158 = arith.index_cast %132 : index to i32
%157 = arith.muli %158, %156 : i32
%159 = arith.constant 2 : i32
%160 = arith.addi %157, %159 : i32
%161 = arith.extsi %160 : i32 to i64
%162 = llvm.getelementptr %arg1[%161] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%155 = llvm.load %162 : !llvm.ptr -> i64
%163 = llvm.mlir.addressof @MOD : !llvm.ptr
%164 = llvm.load %163 : !llvm.ptr -> i64
%165 = arith.remsi %155, %164 : i64
%166 = arith.constant 3 : i32
%168 = arith.index_cast %132 : index to i32
%167 = arith.muli %168, %166 : i32
%169 = arith.constant 0 : i32
%170 = arith.addi %167, %169 : i32
%171 = arith.extsi %170 : i32 to i64
%172 = llvm.getelementptr %91[0, %171] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %143, %172 : i64, !llvm.ptr
%173 = arith.muli %69, %143 : i64
%174 = arith.addi %173, %154 : i64
%175 = llvm.mlir.addressof @MOD : !llvm.ptr
%176 = llvm.load %175 : !llvm.ptr -> i64
%177 = arith.remsi %174, %176 : i64
%178 = arith.constant 3 : i32
%180 = arith.index_cast %132 : index to i32
%179 = arith.muli %180, %178 : i32
%181 = arith.constant 1 : i32
%182 = arith.addi %179, %181 : i32
%183 = arith.extsi %182 : i32 to i64
%184 = llvm.getelementptr %91[0, %183] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %177, %184 : i64, !llvm.ptr
%185 = arith.muli %73, %143 : i64
%186 = arith.muli %79, %154 : i64
%187 = arith.addi %185, %186 : i64
%188 = arith.addi %187, %165 : i64
%189 = llvm.mlir.addressof @MOD : !llvm.ptr
%190 = llvm.load %189 : !llvm.ptr -> i64
%191 = arith.remsi %188, %190 : i64
%192 = arith.constant 3 : i32
%194 = arith.index_cast %132 : index to i32
%193 = arith.muli %194, %192 : i32
%195 = arith.constant 2 : i32
%196 = arith.addi %193, %195 : i32
%197 = arith.extsi %196 : i32 to i64
%198 = llvm.getelementptr %91[0, %197] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %191, %198 : i64, !llvm.ptr
%199 = arith.addi %132, %124 : index
cf.br ^bb9(%199 : index)
^bb11(%200: index):
%202 = arith.constant 1 : i32
%203 = arith.constant 0 : i32
%204 = arith.constant 0 : i32
%205 = arith.constant 1 : i32
%206 = arith.constant 1 : i32
%207 = arith.constant 0 : i32
%208 = arith.constant 1 : i32
%209 = arith.constant 2 : i32
%210 = arith.constant 1 : i32
%211 = llvm.mlir.constant(1 : i64) : i64
%212 = llvm.alloca %211 x !llvm.array<9 x i32> : (i64) -> !llvm.ptr
%213 = llvm.mlir.zero : !llvm.array<9 x i32>
llvm.store %213, %212 : !llvm.array<9 x i32>, !llvm.ptr
%214 = llvm.mlir.constant(0 : i64) : i64
%215 = llvm.getelementptr %212[0, %214] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
llvm.store %202, %215 : i32, !llvm.ptr
%216 = llvm.mlir.constant(1 : i64) : i64
%217 = llvm.getelementptr %212[0, %216] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
llvm.store %203, %217 : i32, !llvm.ptr
%218 = llvm.mlir.constant(2 : i64) : i64
%219 = llvm.getelementptr %212[0, %218] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
llvm.store %204, %219 : i32, !llvm.ptr
%220 = llvm.mlir.constant(3 : i64) : i64
%221 = llvm.getelementptr %212[0, %220] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
llvm.store %205, %221 : i32, !llvm.ptr
%222 = llvm.mlir.constant(4 : i64) : i64
%223 = llvm.getelementptr %212[0, %222] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
llvm.store %206, %223 : i32, !llvm.ptr
%224 = llvm.mlir.constant(5 : i64) : i64
%225 = llvm.getelementptr %212[0, %224] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
llvm.store %207, %225 : i32, !llvm.ptr
%226 = llvm.mlir.constant(6 : i64) : i64
%227 = llvm.getelementptr %212[0, %226] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
llvm.store %208, %227 : i32, !llvm.ptr
%228 = llvm.mlir.constant(7 : i64) : i64
%229 = llvm.getelementptr %212[0, %228] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
llvm.store %209, %229 : i32, !llvm.ptr
%230 = llvm.mlir.constant(8 : i64) : i64
%231 = llvm.getelementptr %212[0, %230] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
llvm.store %210, %231 : i32, !llvm.ptr
func.call @zero_arr(%arg0) : (!llvm.ptr) -> ()
%233 = arith.constant 0 : i32
%234 = arith.constant 3 : i32
%235 = arith.index_cast %233 : i32 to index
%236 = arith.index_cast %234 : i32 to index
%238 = arith.constant 1 : index
%239 = arith.constant -1 : index
%240 = arith.cmpi sle, %235, %236 : index
%237 = arith.select %240, %238, %239 : index
cf.br ^bb12(%235 : index)
^bb12(%241: index):
%242 = arith.cmpi slt, %241, %236 : index
%243 = arith.cmpi sgt, %241, %236 : index
%244 = arith.select %240, %242, %243 : i1
cf.cond_br %244, ^bb13(%241 : index), ^bb14(%241 : index)
^bb13(%245: index):
%246 = arith.constant 0 : i32
%247 = arith.constant 3 : i32
%248 = arith.index_cast %246 : i32 to index
%249 = arith.index_cast %247 : i32 to index
%251 = arith.constant 1 : index
%252 = arith.constant -1 : index
%253 = arith.cmpi sle, %248, %249 : index
%250 = arith.select %253, %251, %252 : index
cf.br ^bb15(%248 : index)
^bb15(%254: index):
%255 = arith.cmpi slt, %254, %249 : index
%256 = arith.cmpi sgt, %254, %249 : index
%257 = arith.select %253, %255, %256 : i1
cf.cond_br %257, ^bb16(%254 : index), ^bb17(%254 : index)
^bb16(%258: index):
%259 = arith.constant 0 : i32
%260 = arith.extsi %259 : i32 to i64
%261 = llvm.mlir.constant(1 : i64) : i64
%262 = llvm.alloca %261 x i64 : (i64) -> !llvm.ptr
llvm.store %260, %262 : i64, !llvm.ptr
%263 = arith.constant 0 : i32
%264 = arith.constant 3 : i32
%265 = arith.index_cast %263 : i32 to index
%266 = arith.index_cast %264 : i32 to index
%268 = arith.constant 1 : index
%269 = arith.constant -1 : index
%270 = arith.cmpi sle, %265, %266 : index
%267 = arith.select %270, %268, %269 : index
cf.br ^bb18(%265 : index)
^bb18(%271: index):
%272 = arith.cmpi slt, %271, %266 : index
%273 = arith.cmpi sgt, %271, %266 : index
%274 = arith.select %270, %272, %273 : i1
cf.cond_br %274, ^bb19(%271 : index), ^bb20(%271 : index)
^bb19(%275: index):
%277 = arith.constant 3 : i32
%279 = arith.index_cast %245 : index to i32
%278 = arith.muli %279, %277 : i32
%281 = arith.index_cast %275 : index to i32
%280 = arith.addi %278, %281 : i32
%282 = arith.extsi %280 : i32 to i64
%283 = llvm.getelementptr %212[0, %282] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i32>
%276 = llvm.load %283 : !llvm.ptr -> i32
%284 = arith.extsi %276 : i32 to i64
%285 = llvm.load %262 : !llvm.ptr -> i64
%287 = arith.constant 3 : i32
%289 = arith.index_cast %275 : index to i32
%288 = arith.muli %289, %287 : i32
%291 = arith.index_cast %258 : index to i32
%290 = arith.addi %288, %291 : i32
%292 = arith.extsi %290 : i32 to i64
%293 = llvm.getelementptr %91[0, %292] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
%286 = llvm.load %293 : !llvm.ptr -> i64
%294 = arith.muli %284, %286 : i64
%295 = arith.addi %285, %294 : i64
%296 = llvm.mlir.addressof @MOD : !llvm.ptr
%297 = llvm.load %296 : !llvm.ptr -> i64
%298 = arith.remsi %295, %297 : i64
llvm.store %298, %262 : i64, !llvm.ptr
%299 = arith.addi %275, %267 : index
cf.br ^bb18(%299 : index)
^bb20(%300: index):
%301 = llvm.load %262 : !llvm.ptr -> i64
%302 = arith.constant 3 : i32
%304 = arith.index_cast %245 : index to i32
%303 = arith.muli %304, %302 : i32
%306 = arith.index_cast %258 : index to i32
%305 = arith.addi %303, %306 : i32
%307 = arith.extsi %305 : i32 to i64
%308 = llvm.getelementptr %arg0[%307] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %301, %308 : i64, !llvm.ptr
%309 = arith.addi %258, %250 : index
cf.br ^bb15(%309 : index)
^bb17(%310: index):
%311 = arith.addi %245, %237 : index
cf.br ^bb12(%311 : index)
^bb14(%312: index):
func.return
}
func.func @precompute(%arg0: i64) -> () {
%314 = arith.constant 1 : i32
%316 = arith.extsi %314 : i32 to i64
%315 = arith.addi %arg0, %316 : i64
%317 = arith.constant 9 : i32
%319 = arith.extsi %317 : i32 to i64
%318 = arith.muli %315, %319 : i64
%320 = arith.constant 8 : i32
%321 = arith.extsi %320 : i32 to i64
%313 = func.call @calloc(%318, %321) : (i64, i64) -> !llvm.ptr
%322 = llvm.mlir.addressof @full : !llvm.ptr
llvm.store %313, %322 : !llvm.ptr, !llvm.ptr
%323 = arith.constant 1 : i32
%324 = llvm.mlir.addressof @full : !llvm.ptr
%325 = llvm.load %324 : !llvm.ptr -> !llvm.ptr
%326 = arith.constant 0 : i32
%327 = arith.extsi %323 : i32 to i64
%328 = arith.extsi %326 : i32 to i64
%329 = llvm.getelementptr %325[%328] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %327, %329 : i64, !llvm.ptr
%330 = arith.constant 1 : i32
%331 = arith.constant 1 : i32
%333 = arith.extsi %331 : i32 to i64
%332 = arith.addi %arg0, %333 : i64
%334 = arith.index_cast %330 : i32 to index
%335 = arith.index_cast %332 : i32 to index
%337 = arith.constant 1 : index
%338 = arith.constant -1 : index
%339 = arith.cmpi sle, %334, %335 : index
%336 = arith.select %339, %337, %338 : index
cf.br ^bb21(%334 : index)
^bb21(%340: index):
%341 = arith.cmpi slt, %340, %335 : index
%342 = arith.cmpi sgt, %340, %335 : index
%343 = arith.select %339, %341, %342 : i1
cf.cond_br %343, ^bb22(%340 : index), ^bb23(%340 : index)
^bb22(%344: index):
%346 = arith.constant 0 : i32
%347 = arith.constant 0 : i32
%348 = arith.constant 0 : i32
%349 = arith.constant 0 : i32
%350 = arith.constant 0 : i32
%351 = arith.constant 0 : i32
%352 = arith.constant 0 : i32
%353 = arith.constant 0 : i32
%354 = arith.constant 0 : i32
%355 = llvm.mlir.constant(1 : i64) : i64
%356 = llvm.alloca %355 x !llvm.array<9 x i64> : (i64) -> !llvm.ptr
%357 = llvm.mlir.zero : !llvm.array<9 x i64>
llvm.store %357, %356 : !llvm.array<9 x i64>, !llvm.ptr
%358 = arith.extsi %346 : i32 to i64
%359 = arith.extsi %347 : i32 to i64
%360 = arith.extsi %348 : i32 to i64
%361 = arith.extsi %349 : i32 to i64
%362 = arith.extsi %350 : i32 to i64
%363 = arith.extsi %351 : i32 to i64
%364 = arith.extsi %352 : i32 to i64
%365 = arith.extsi %353 : i32 to i64
%366 = arith.extsi %354 : i32 to i64
%367 = llvm.mlir.constant(0 : i64) : i64
%368 = llvm.getelementptr %356[0, %367] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %358, %368 : i64, !llvm.ptr
%369 = llvm.mlir.constant(1 : i64) : i64
%370 = llvm.getelementptr %356[0, %369] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %359, %370 : i64, !llvm.ptr
%371 = llvm.mlir.constant(2 : i64) : i64
%372 = llvm.getelementptr %356[0, %371] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %360, %372 : i64, !llvm.ptr
%373 = llvm.mlir.constant(3 : i64) : i64
%374 = llvm.getelementptr %356[0, %373] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %361, %374 : i64, !llvm.ptr
%375 = llvm.mlir.constant(4 : i64) : i64
%376 = llvm.getelementptr %356[0, %375] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %362, %376 : i64, !llvm.ptr
%377 = llvm.mlir.constant(5 : i64) : i64
%378 = llvm.getelementptr %356[0, %377] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %363, %378 : i64, !llvm.ptr
%379 = llvm.mlir.constant(6 : i64) : i64
%380 = llvm.getelementptr %356[0, %379] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %364, %380 : i64, !llvm.ptr
%381 = llvm.mlir.constant(7 : i64) : i64
%382 = llvm.getelementptr %356[0, %381] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %365, %382 : i64, !llvm.ptr
%383 = llvm.mlir.constant(8 : i64) : i64
%384 = llvm.getelementptr %356[0, %383] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %366, %384 : i64, !llvm.ptr
%386 = arith.constant 0 : i32
%387 = arith.extsi %386 : i32 to i64
%388 = llvm.getelementptr %356[0, %387] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
%394 = llvm.mlir.addressof @full : !llvm.ptr
%395 = llvm.load %394 : !llvm.ptr -> !llvm.ptr
%389 = arith.constant 1 : i32
%391 = arith.index_cast %344 : index to i32
%390 = arith.subi %391, %389 : i32
%392 = arith.constant 9 : i32
%393 = arith.muli %390, %392 : i32
%396 = arith.extsi %393 : i32 to i64
%397 = llvm.getelementptr %395[%396] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%398 = arith.constant 1 : i32
%399 = arith.extsi %398 : i32 to i64
%400 = arith.constant 1 : i32
%402 = arith.index_cast %344 : index to i32
%401 = arith.subi %402, %400 : i32
%404 = arith.extsi %401 : i32 to i64
%403 = arith.shli %399, %404 : i64
func.call @shift_range(%388, %397, %403) : (!llvm.ptr, !llvm.ptr, i64) -> ()
%408 = llvm.mlir.addressof @full : !llvm.ptr
%409 = llvm.load %408 : !llvm.ptr -> !llvm.ptr
%405 = arith.constant 9 : i32
%407 = arith.index_cast %344 : index to i32
%406 = arith.muli %407, %405 : i32
%410 = arith.extsi %406 : i32 to i64
%411 = llvm.getelementptr %409[%410] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%417 = llvm.mlir.addressof @full : !llvm.ptr
%418 = llvm.load %417 : !llvm.ptr -> !llvm.ptr
%412 = arith.constant 1 : i32
%414 = arith.index_cast %344 : index to i32
%413 = arith.subi %414, %412 : i32
%415 = arith.constant 9 : i32
%416 = arith.muli %413, %415 : i32
%419 = arith.extsi %416 : i32 to i64
%420 = llvm.getelementptr %418[%419] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%422 = arith.constant 0 : i32
%423 = arith.extsi %422 : i32 to i64
%424 = llvm.getelementptr %356[0, %423] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
func.call @addm(%411, %420, %424) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%425 = arith.addi %344, %336 : index
cf.br ^bb21(%425 : index)
^bb23(%426: index):
func.return
}
func.func @highest_bit(%arg0: i64) -> i64 {
%427 = arith.constant 0 : i32
%428 = arith.extsi %427 : i32 to i64
%429 = llvm.mlir.constant(1 : i64) : i64
%430 = llvm.alloca %429 x i64 : (i64) -> !llvm.ptr
llvm.store %428, %430 : i64, !llvm.ptr
%431 = llvm.mlir.constant(1 : i64) : i64
%432 = llvm.alloca %431 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %432 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%433 = llvm.load %432 : !llvm.ptr -> i64
%434 = arith.constant 1 : i32
%436 = arith.extsi %434 : i32 to i64
%435 = arith.cmpi sgt, %433, %436 : i64
cf.cond_br %435, ^bb25, ^bb26
^bb25:
%437 = llvm.load %432 : !llvm.ptr -> i64
%438 = arith.constant 1 : i32
%440 = arith.extsi %438 : i32 to i64
%439 = arith.shrsi %437, %440 : i64
llvm.store %439, %432 : i64, !llvm.ptr
%441 = llvm.load %430 : !llvm.ptr -> i64
%442 = arith.constant 1 : i32
%444 = arith.extsi %442 : i32 to i64
%443 = arith.addi %441, %444 : i64
llvm.store %443, %430 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%445 = llvm.load %430 : !llvm.ptr -> i64
func.return %445 : i64
}
func.func @calc_upto(%arg0: !llvm.ptr, %arg1: i64) -> () {
%446 = arith.constant 0 : i32
%448 = arith.extsi %446 : i32 to i64
%447 = arith.cmpi slt, %arg1, %448 : i64
cf.cond_br %447, ^bb27, ^bb28
^bb27:
func.call @zero_arr(%arg0) : (!llvm.ptr) -> ()
func.return
^bb28:
cf.br ^bb29
^bb29:
%450 = arith.constant 0 : i32
%452 = arith.extsi %450 : i32 to i64
%451 = arith.cmpi eq, %arg1, %452 : i64
cf.cond_br %451, ^bb30, ^bb31
^bb30:
%455 = llvm.mlir.addressof @full : !llvm.ptr
%456 = llvm.load %455 : !llvm.ptr -> !llvm.ptr
%454 = arith.constant 0 : i32
%457 = arith.extsi %454 : i32 to i64
%458 = llvm.getelementptr %456[%457] : (!llvm.ptr, i64) -> !llvm.ptr, i64
func.call @copy_mat(%arg0, %458) : (!llvm.ptr, !llvm.ptr) -> ()
func.return
^bb31:
cf.br ^bb32
^bb32:
%459 = func.call @highest_bit(%arg1) : (i64) -> i64
%460 = arith.constant 1 : i32
%461 = arith.extsi %460 : i32 to i64
%462 = arith.shli %461, %459 : i64
%463 = arith.constant 1 : i32
%465 = arith.extsi %463 : i32 to i64
%464 = arith.subi %462, %465 : i64
%466 = arith.cmpi eq, %arg1, %464 : i64
cf.cond_br %466, ^bb33, ^bb34
^bb33:
%471 = llvm.mlir.addressof @full : !llvm.ptr
%472 = llvm.load %471 : !llvm.ptr -> !llvm.ptr
%468 = arith.constant 9 : i32
%470 = arith.extsi %468 : i32 to i64
%469 = arith.muli %459, %470 : i64
%473 = llvm.getelementptr %472[%469] : (!llvm.ptr, i64) -> !llvm.ptr, i64
func.call @copy_mat(%arg0, %473) : (!llvm.ptr, !llvm.ptr) -> ()
func.return
^bb34:
cf.br ^bb35
^bb35:
%475 = arith.constant 0 : i32
%476 = arith.constant 0 : i32
%477 = arith.constant 0 : i32
%478 = arith.constant 0 : i32
%479 = arith.constant 0 : i32
%480 = arith.constant 0 : i32
%481 = arith.constant 0 : i32
%482 = arith.constant 0 : i32
%483 = arith.constant 0 : i32
%484 = llvm.mlir.constant(1 : i64) : i64
%485 = llvm.alloca %484 x !llvm.array<9 x i64> : (i64) -> !llvm.ptr
%486 = llvm.mlir.zero : !llvm.array<9 x i64>
llvm.store %486, %485 : !llvm.array<9 x i64>, !llvm.ptr
%487 = arith.extsi %475 : i32 to i64
%488 = arith.extsi %476 : i32 to i64
%489 = arith.extsi %477 : i32 to i64
%490 = arith.extsi %478 : i32 to i64
%491 = arith.extsi %479 : i32 to i64
%492 = arith.extsi %480 : i32 to i64
%493 = arith.extsi %481 : i32 to i64
%494 = arith.extsi %482 : i32 to i64
%495 = arith.extsi %483 : i32 to i64
%496 = llvm.mlir.constant(0 : i64) : i64
%497 = llvm.getelementptr %485[0, %496] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %487, %497 : i64, !llvm.ptr
%498 = llvm.mlir.constant(1 : i64) : i64
%499 = llvm.getelementptr %485[0, %498] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %488, %499 : i64, !llvm.ptr
%500 = llvm.mlir.constant(2 : i64) : i64
%501 = llvm.getelementptr %485[0, %500] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %489, %501 : i64, !llvm.ptr
%502 = llvm.mlir.constant(3 : i64) : i64
%503 = llvm.getelementptr %485[0, %502] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %490, %503 : i64, !llvm.ptr
%504 = llvm.mlir.constant(4 : i64) : i64
%505 = llvm.getelementptr %485[0, %504] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %491, %505 : i64, !llvm.ptr
%506 = llvm.mlir.constant(5 : i64) : i64
%507 = llvm.getelementptr %485[0, %506] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %492, %507 : i64, !llvm.ptr
%508 = llvm.mlir.constant(6 : i64) : i64
%509 = llvm.getelementptr %485[0, %508] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %493, %509 : i64, !llvm.ptr
%510 = llvm.mlir.constant(7 : i64) : i64
%511 = llvm.getelementptr %485[0, %510] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %494, %511 : i64, !llvm.ptr
%512 = llvm.mlir.constant(8 : i64) : i64
%513 = llvm.getelementptr %485[0, %512] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %495, %513 : i64, !llvm.ptr
%515 = arith.constant 0 : i32
%516 = arith.extsi %515 : i32 to i64
%517 = llvm.getelementptr %485[0, %516] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
%521 = llvm.mlir.addressof @full : !llvm.ptr
%522 = llvm.load %521 : !llvm.ptr -> !llvm.ptr
%518 = arith.constant 9 : i32
%520 = arith.extsi %518 : i32 to i64
%519 = arith.muli %459, %520 : i64
%523 = llvm.getelementptr %522[%519] : (!llvm.ptr, i64) -> !llvm.ptr, i64
func.call @copy_mat(%517, %523) : (!llvm.ptr, !llvm.ptr) -> ()
%525 = arith.constant 0 : i32
%526 = arith.constant 0 : i32
%527 = arith.constant 0 : i32
%528 = arith.constant 0 : i32
%529 = arith.constant 0 : i32
%530 = arith.constant 0 : i32
%531 = arith.constant 0 : i32
%532 = arith.constant 0 : i32
%533 = arith.constant 0 : i32
%534 = llvm.mlir.constant(1 : i64) : i64
%535 = llvm.alloca %534 x !llvm.array<9 x i64> : (i64) -> !llvm.ptr
%536 = llvm.mlir.zero : !llvm.array<9 x i64>
llvm.store %536, %535 : !llvm.array<9 x i64>, !llvm.ptr
%537 = arith.extsi %525 : i32 to i64
%538 = arith.extsi %526 : i32 to i64
%539 = arith.extsi %527 : i32 to i64
%540 = arith.extsi %528 : i32 to i64
%541 = arith.extsi %529 : i32 to i64
%542 = arith.extsi %530 : i32 to i64
%543 = arith.extsi %531 : i32 to i64
%544 = arith.extsi %532 : i32 to i64
%545 = arith.extsi %533 : i32 to i64
%546 = llvm.mlir.constant(0 : i64) : i64
%547 = llvm.getelementptr %535[0, %546] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %537, %547 : i64, !llvm.ptr
%548 = llvm.mlir.constant(1 : i64) : i64
%549 = llvm.getelementptr %535[0, %548] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %538, %549 : i64, !llvm.ptr
%550 = llvm.mlir.constant(2 : i64) : i64
%551 = llvm.getelementptr %535[0, %550] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %539, %551 : i64, !llvm.ptr
%552 = llvm.mlir.constant(3 : i64) : i64
%553 = llvm.getelementptr %535[0, %552] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %540, %553 : i64, !llvm.ptr
%554 = llvm.mlir.constant(4 : i64) : i64
%555 = llvm.getelementptr %535[0, %554] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %541, %555 : i64, !llvm.ptr
%556 = llvm.mlir.constant(5 : i64) : i64
%557 = llvm.getelementptr %535[0, %556] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %542, %557 : i64, !llvm.ptr
%558 = llvm.mlir.constant(6 : i64) : i64
%559 = llvm.getelementptr %535[0, %558] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %543, %559 : i64, !llvm.ptr
%560 = llvm.mlir.constant(7 : i64) : i64
%561 = llvm.getelementptr %535[0, %560] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %544, %561 : i64, !llvm.ptr
%562 = llvm.mlir.constant(8 : i64) : i64
%563 = llvm.getelementptr %535[0, %562] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %545, %563 : i64, !llvm.ptr
%565 = arith.constant 0 : i32
%566 = arith.extsi %565 : i32 to i64
%567 = llvm.getelementptr %535[0, %566] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
%568 = arith.subi %arg1, %462 : i64
func.call @calc_upto(%567, %568) : (!llvm.ptr, i64) -> ()
%570 = arith.constant 0 : i32
%571 = arith.constant 0 : i32
%572 = arith.constant 0 : i32
%573 = arith.constant 0 : i32
%574 = arith.constant 0 : i32
%575 = arith.constant 0 : i32
%576 = arith.constant 0 : i32
%577 = arith.constant 0 : i32
%578 = arith.constant 0 : i32
%579 = llvm.mlir.constant(1 : i64) : i64
%580 = llvm.alloca %579 x !llvm.array<9 x i64> : (i64) -> !llvm.ptr
%581 = llvm.mlir.zero : !llvm.array<9 x i64>
llvm.store %581, %580 : !llvm.array<9 x i64>, !llvm.ptr
%582 = arith.extsi %570 : i32 to i64
%583 = arith.extsi %571 : i32 to i64
%584 = arith.extsi %572 : i32 to i64
%585 = arith.extsi %573 : i32 to i64
%586 = arith.extsi %574 : i32 to i64
%587 = arith.extsi %575 : i32 to i64
%588 = arith.extsi %576 : i32 to i64
%589 = arith.extsi %577 : i32 to i64
%590 = arith.extsi %578 : i32 to i64
%591 = llvm.mlir.constant(0 : i64) : i64
%592 = llvm.getelementptr %580[0, %591] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %582, %592 : i64, !llvm.ptr
%593 = llvm.mlir.constant(1 : i64) : i64
%594 = llvm.getelementptr %580[0, %593] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %583, %594 : i64, !llvm.ptr
%595 = llvm.mlir.constant(2 : i64) : i64
%596 = llvm.getelementptr %580[0, %595] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %584, %596 : i64, !llvm.ptr
%597 = llvm.mlir.constant(3 : i64) : i64
%598 = llvm.getelementptr %580[0, %597] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %585, %598 : i64, !llvm.ptr
%599 = llvm.mlir.constant(4 : i64) : i64
%600 = llvm.getelementptr %580[0, %599] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %586, %600 : i64, !llvm.ptr
%601 = llvm.mlir.constant(5 : i64) : i64
%602 = llvm.getelementptr %580[0, %601] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %587, %602 : i64, !llvm.ptr
%603 = llvm.mlir.constant(6 : i64) : i64
%604 = llvm.getelementptr %580[0, %603] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %588, %604 : i64, !llvm.ptr
%605 = llvm.mlir.constant(7 : i64) : i64
%606 = llvm.getelementptr %580[0, %605] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %589, %606 : i64, !llvm.ptr
%607 = llvm.mlir.constant(8 : i64) : i64
%608 = llvm.getelementptr %580[0, %607] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %590, %608 : i64, !llvm.ptr
%610 = arith.constant 0 : i32
%611 = arith.extsi %610 : i32 to i64
%612 = llvm.getelementptr %580[0, %611] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
%613 = arith.constant 0 : i32
%614 = arith.extsi %613 : i32 to i64
%615 = llvm.getelementptr %535[0, %614] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
func.call @shift_range(%612, %615, %462) : (!llvm.ptr, !llvm.ptr, i64) -> ()
%617 = arith.constant 0 : i32
%618 = arith.extsi %617 : i32 to i64
%619 = llvm.getelementptr %485[0, %618] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
%620 = arith.constant 0 : i32
%621 = arith.extsi %620 : i32 to i64
%622 = llvm.getelementptr %580[0, %621] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
func.call @addm(%arg0, %619, %622) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.return
}
func.func @main() -> i32 {
%623 = arith.constant 9999995705032704 : i32
%624 = arith.extsi %623 : i32 to i64
%626 = arith.constant 60 : i32
%627 = arith.extsi %626 : i32 to i64
func.call @precompute(%627) : (i64) -> ()
%629 = arith.constant 0 : i32
%630 = arith.constant 0 : i32
%631 = arith.constant 0 : i32
%632 = arith.constant 0 : i32
%633 = arith.constant 0 : i32
%634 = arith.constant 0 : i32
%635 = arith.constant 0 : i32
%636 = arith.constant 0 : i32
%637 = arith.constant 0 : i32
%638 = llvm.mlir.constant(1 : i64) : i64
%639 = llvm.alloca %638 x !llvm.array<9 x i64> : (i64) -> !llvm.ptr
%640 = llvm.mlir.zero : !llvm.array<9 x i64>
llvm.store %640, %639 : !llvm.array<9 x i64>, !llvm.ptr
%641 = arith.extsi %629 : i32 to i64
%642 = arith.extsi %630 : i32 to i64
%643 = arith.extsi %631 : i32 to i64
%644 = arith.extsi %632 : i32 to i64
%645 = arith.extsi %633 : i32 to i64
%646 = arith.extsi %634 : i32 to i64
%647 = arith.extsi %635 : i32 to i64
%648 = arith.extsi %636 : i32 to i64
%649 = arith.extsi %637 : i32 to i64
%650 = llvm.mlir.constant(0 : i64) : i64
%651 = llvm.getelementptr %639[0, %650] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %641, %651 : i64, !llvm.ptr
%652 = llvm.mlir.constant(1 : i64) : i64
%653 = llvm.getelementptr %639[0, %652] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %642, %653 : i64, !llvm.ptr
%654 = llvm.mlir.constant(2 : i64) : i64
%655 = llvm.getelementptr %639[0, %654] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %643, %655 : i64, !llvm.ptr
%656 = llvm.mlir.constant(3 : i64) : i64
%657 = llvm.getelementptr %639[0, %656] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %644, %657 : i64, !llvm.ptr
%658 = llvm.mlir.constant(4 : i64) : i64
%659 = llvm.getelementptr %639[0, %658] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %645, %659 : i64, !llvm.ptr
%660 = llvm.mlir.constant(5 : i64) : i64
%661 = llvm.getelementptr %639[0, %660] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %646, %661 : i64, !llvm.ptr
%662 = llvm.mlir.constant(6 : i64) : i64
%663 = llvm.getelementptr %639[0, %662] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %647, %663 : i64, !llvm.ptr
%664 = llvm.mlir.constant(7 : i64) : i64
%665 = llvm.getelementptr %639[0, %664] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %648, %665 : i64, !llvm.ptr
%666 = llvm.mlir.constant(8 : i64) : i64
%667 = llvm.getelementptr %639[0, %666] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
llvm.store %649, %667 : i64, !llvm.ptr
%669 = arith.constant 0 : i32
%670 = arith.extsi %669 : i32 to i64
%671 = llvm.getelementptr %639[0, %670] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
func.call @calc_upto(%671, %624) : (!llvm.ptr, i64) -> ()
%672 = llvm.mlir.addressof @str_0 : !llvm.ptr
%674 = arith.constant 8 : i32
%675 = arith.extsi %674 : i32 to i64
%676 = llvm.getelementptr %639[0, %675] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<9 x i64>
%673 = llvm.load %676 : !llvm.ptr -> i64
%677 = llvm.mlir.addressof @MOD : !llvm.ptr
%678 = llvm.load %677 : !llvm.ptr -> i64
%679 = arith.remsi %673, %678 : i64
%680 = llvm.call @printf(%672, %679) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%682 = llvm.mlir.addressof @full : !llvm.ptr
%683 = llvm.load %682 : !llvm.ptr -> !llvm.ptr
func.call @free(%683) : (!llvm.ptr) -> ()
%684 = arith.constant 0 : i32
func.return %684 : i32
}
}