Problem 672
H(K) = S((7^K - 1)/11) mod 1117117717, K=10^9. Uses 4x4 matrix exponentiation over base-7 digits of 1/11.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^3) | O(log n) |
|---|
| Space complexity | O(1) | O(n^2) |
|---|
| Approach | Flow solution | Matrix exponentiation |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 672: One More One
# H(K) = S((7^K - 1)/11) mod 1117117717, K=10^9.
# Uses 4x4 matrix exponentiation over base-7 digits of 1/11.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1117117717
# 4x4 matrix multiply: R = A * B (mod MOD)
function mat_mul(a: ptr<i64>, b: ptr<i64>, r: ptr<i64>) -> void {
for i in 0..4 {
for j in 0..4 {
let mut s: i64 = 0
for k in 0..4 {
s = (s + a[i * 4 + k] * b[k * 4 + j]) % MOD
}
r[i * 4 + j] = s
}
}
}
# 4x4 matrix power: R = M^e (mod MOD)
function mat_pow(m: ptr<i64>, e: i64, r: ptr<i64>) -> void {
# Initialize r = identity
for i in 0..4 {
for j in 0..4 {
if i == j { r[i * 4 + j] = 1 } else { r[i * 4 + j] = 0 }
}
}
# Copy m to base
let base: ptr<i64> = calloc(16, 8)
for i in 0..16 { base[i] = m[i] }
let mut e_local: i64 = e
while e_local > 0 {
if e_local & 1 == 1 {
let tmp: ptr<i64> = calloc(16, 8)
mat_mul(r, base, tmp)
for i in 0..16 { r[i] = tmp[i] }
free(tmp)
}
let tmp2: ptr<i64> = calloc(16, 8)
mat_mul(base, base, tmp2)
for i in 0..16 { base[i] = tmp2[i] }
free(tmp2)
e_local = e_local >> 1
}
free(base)
}
# Matrix-vector multiply: v = M * v (mod MOD), v is length 4
function mat_vec(m: ptr<i64>, v: ptr<i64>, out: ptr<i64>) -> void {
for i in 0..4 {
let mut s: i64 = 0
for k in 0..4 {
s = (s + m[i * 4 + k] * v[k]) % MOD
}
out[i] = s
}
}
# Build digit matrix for appending base-7 digit r
function digit_matrix(r: i64, out: ptr<i64>) -> void {
let c1: i64 = (-6 + 7 * r - (r * (r + 1)) / 2) % MOD
if c1 < 0 { c1 = c1 + MOD }
let c2: i64
if r == 6 { c2 = 0 } else { c2 = (6 - r) % MOD }
if c2 < 0 { c2 = c2 + MOD }
# Row 0: [7, r, 21, c1]
out[0] = 7 % MOD
out[1] = r % MOD
out[2] = 21 % MOD
out[3] = c1
# Row 1: [0, 1, 0, c2]
out[4] = 0
out[5] = 1
out[6] = 0
out[7] = c2
# Row 2: [0, 0, 7, r]
out[8] = 0
out[9] = 0
out[10] = 7 % MOD
out[11] = r % MOD
# Row 3: [0, 0, 0, 1]
out[12] = 0
out[13] = 0
out[14] = 0
out[15] = 1
}
function main() -> i32 {
# Base-7 digits of 1/11 with period 10
# A = [0,4,3,1,1,6,2,3,5,5]
# B = A[1:] + A[:1] = [4,3,1,1,6,2,3,5,5,0]
let B: ptr<i64> = calloc(10, 8)
B[0] = 4; B[1] = 3; B[2] = 1; B[3] = 1; B[4] = 6
B[5] = 2; B[6] = 3; B[7] = 5; B[8] = 5; B[9] = 0
let K: i64 = 1000000000 # 10^9
let total_digits: i64 = K - 1
let full_blocks: i64 = total_digits / 10
let rem: i64 = total_digits % 10
# Build block matrix M_block = product of digit_matrix(B[i]) for i=0..9
let M_block: ptr<i64> = calloc(16, 8)
# Initialize as identity
for i in 0..4 {
for j in 0..4 {
if i == j { M_block[i * 4 + j] = 1 } else { M_block[i * 4 + j] = 0 }
}
}
let dm: ptr<i64> = calloc(16, 8)
let tmp: ptr<i64> = calloc(16, 8)
for i in 0..10 {
digit_matrix(B[i], dm)
mat_mul(dm, M_block, tmp)
for j in 0..16 { M_block[j] = tmp[j] }
}
free(dm)
free(tmp)
# v = [0, 0, 0, 1]
let v: ptr<i64> = calloc(4, 8)
v[0] = 0; v[1] = 0; v[2] = 0; v[3] = 1
# Apply M_block^full_blocks
if full_blocks > 0 {
let mp: ptr<i64> = calloc(16, 8)
mat_pow(M_block, full_blocks, mp)
let vv: ptr<i64> = calloc(4, 8)
mat_vec(mp, v, vv)
for i in 0..4 { v[i] = vv[i] }
free(vv)
free(mp)
}
# Apply remaining digits
let dm2: ptr<i64> = calloc(16, 8)
let vv2: ptr<i64> = calloc(4, 8)
for i in 0..rem {
digit_matrix(B[i], dm2)
mat_vec(dm2, v, vv2)
for j in 0..4 { v[j] = vv2[j] }
}
free(dm2)
free(vv2)
let ans: i64 = v[0] % MOD
if ans < 0 { ans = ans + MOD }
printf("%lld\n", ans)
free(v)
free(M_block)
free(B)
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 mat_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* a, int64_t* b, int64_t* r);
void mat_pow_ptr_i64_i64_ptr_i64(int64_t* m, int64_t e, int64_t* r);
void mat_vec_ptr_i64_ptr_i64_ptr_i64(int64_t* m, int64_t* v, int64_t* out);
void digit_matrix_i64_ptr_i64(int64_t r, int64_t* out);
int32_t main(void);
static const int64_t MOD = 1117117717;
void mat_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* a, int64_t* b, int64_t* r) {
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= 4) ? i < 4 : i > 4; i += (0 <= 4) ? 1 : -1) {
int32_t __flow_step_2 = 1;
for (int32_t j = 0; (0 <= 4) ? j < 4 : j > 4; j += (0 <= 4) ? 1 : -1) {
int64_t s = 0;
int32_t __flow_step_3 = 1;
for (int32_t k = 0; (0 <= 4) ? k < 4 : k > 4; k += (0 <= 4) ? 1 : -1) {
s = FLOW_CHECKED_MOD(((s + (a[((i * 4) + k)] * b[((k * 4) + j)]))), (MOD));
}
r[((i * 4) + j)] = s;
}
}
}
void mat_pow_ptr_i64_i64_ptr_i64(int64_t* m, int64_t e, int64_t* r) {
int32_t __flow_step_4 = 1;
for (int32_t i = 0; (0 <= 4) ? i < 4 : i > 4; i += (0 <= 4) ? 1 : -1) {
int32_t __flow_step_5 = 1;
for (int32_t j = 0; (0 <= 4) ? j < 4 : j > 4; j += (0 <= 4) ? 1 : -1) {
if (i == j) {
r[((i * 4) + j)] = 1;
} else {
r[((i * 4) + j)] = 0;
}
}
}
int64_t* base = (int64_t*)(calloc(16, 8));
int32_t __flow_step_6 = 1;
for (int32_t i = 0; (0 <= 16) ? i < 16 : i > 16; i += (0 <= 16) ? 1 : -1) {
base[i] = m[i];
}
int64_t e_local = e;
while (e_local > 0) {
if ((e_local & 1 == 1)) {
int64_t* tmp = (int64_t*)(calloc(16, 8));
mat_mul_ptr_i64_ptr_i64_ptr_i64(r, base, tmp);
int32_t __flow_step_7 = 1;
for (int32_t i = 0; (0 <= 16) ? i < 16 : i > 16; i += (0 <= 16) ? 1 : -1) {
r[i] = tmp[i];
}
free(tmp);
}
int64_t* tmp2 = (int64_t*)(calloc(16, 8));
mat_mul_ptr_i64_ptr_i64_ptr_i64(base, base, tmp2);
int32_t __flow_step_8 = 1;
for (int32_t i = 0; (0 <= 16) ? i < 16 : i > 16; i += (0 <= 16) ? 1 : -1) {
base[i] = tmp2[i];
}
free(tmp2);
e_local = FLOW_CHECKED_SHR((e_local), (1));
}
free(base);
}
void mat_vec_ptr_i64_ptr_i64_ptr_i64(int64_t* m, int64_t* v, int64_t* out) {
int32_t __flow_step_9 = 1;
for (int32_t i = 0; (0 <= 4) ? i < 4 : i > 4; i += (0 <= 4) ? 1 : -1) {
int64_t s = 0;
int32_t __flow_step_10 = 1;
for (int32_t k = 0; (0 <= 4) ? k < 4 : k > 4; k += (0 <= 4) ? 1 : -1) {
s = FLOW_CHECKED_MOD(((s + (m[((i * 4) + k)] * v[k]))), (MOD));
}
out[i] = s;
}
}
void digit_matrix_i64_ptr_i64(int64_t r, int64_t* out) {
int64_t c1 = FLOW_CHECKED_MOD(((((-6) + (7 * r)) - FLOW_CHECKED_DIV(((r * (r + 1))), (2)))), (MOD));
if (c1 < 0) {
c1 = (c1 + MOD);
}
int64_t c2;
if (r == 6) {
c2 = 0;
} else {
c2 = FLOW_CHECKED_MOD(((6 - r)), (MOD));
}
if (c2 < 0) {
c2 = (c2 + MOD);
}
out[0] = FLOW_CHECKED_MOD((7), (MOD));
out[1] = FLOW_CHECKED_MOD((r), (MOD));
out[2] = FLOW_CHECKED_MOD((21), (MOD));
out[3] = c1;
out[4] = 0;
out[5] = 1;
out[6] = 0;
out[7] = c2;
out[8] = 0;
out[9] = 0;
out[10] = FLOW_CHECKED_MOD((7), (MOD));
out[11] = FLOW_CHECKED_MOD((r), (MOD));
out[12] = 0;
out[13] = 0;
out[14] = 0;
out[15] = 1;
}
int32_t main(void) {
int64_t* B = (int64_t*)(calloc(10, 8));
B[0] = 4;
B[1] = 3;
B[2] = 1;
B[3] = 1;
B[4] = 6;
B[5] = 2;
B[6] = 3;
B[7] = 5;
B[8] = 5;
B[9] = 0;
int64_t K = 1000000000;
int64_t total_digits = (K - 1);
int64_t full_blocks = FLOW_CHECKED_DIV((total_digits), (10));
int64_t rem = FLOW_CHECKED_MOD((total_digits), (10));
int64_t* M_block = (int64_t*)(calloc(16, 8));
int32_t __flow_step_11 = 1;
for (int32_t i = 0; (0 <= 4) ? i < 4 : i > 4; i += (0 <= 4) ? 1 : -1) {
int32_t __flow_step_12 = 1;
for (int32_t j = 0; (0 <= 4) ? j < 4 : j > 4; j += (0 <= 4) ? 1 : -1) {
if (i == j) {
M_block[((i * 4) + j)] = 1;
} else {
M_block[((i * 4) + j)] = 0;
}
}
}
int64_t* dm = (int64_t*)(calloc(16, 8));
int64_t* tmp = (int64_t*)(calloc(16, 8));
int32_t __flow_step_13 = 1;
for (int32_t i = 0; (0 <= 10) ? i < 10 : i > 10; i += (0 <= 10) ? 1 : -1) {
digit_matrix_i64_ptr_i64(B[i], dm);
mat_mul_ptr_i64_ptr_i64_ptr_i64(dm, M_block, tmp);
int32_t __flow_step_14 = 1;
for (int32_t j = 0; (0 <= 16) ? j < 16 : j > 16; j += (0 <= 16) ? 1 : -1) {
M_block[j] = tmp[j];
}
}
free(dm);
free(tmp);
int64_t* v = (int64_t*)(calloc(4, 8));
v[0] = 0;
v[1] = 0;
v[2] = 0;
v[3] = 1;
if (full_blocks > 0) {
int64_t* mp = (int64_t*)(calloc(16, 8));
mat_pow_ptr_i64_i64_ptr_i64(M_block, full_blocks, mp);
int64_t* vv = (int64_t*)(calloc(4, 8));
mat_vec_ptr_i64_ptr_i64_ptr_i64(mp, v, vv);
int32_t __flow_step_15 = 1;
for (int32_t i = 0; (0 <= 4) ? i < 4 : i > 4; i += (0 <= 4) ? 1 : -1) {
v[i] = vv[i];
}
free(vv);
free(mp);
}
int64_t* dm2 = (int64_t*)(calloc(16, 8));
int64_t* vv2 = (int64_t*)(calloc(4, 8));
int32_t __flow_step_16 = 1;
for (int32_t i = 0; (0 <= rem) ? i < rem : i > rem; i += (0 <= rem) ? 1 : -1) {
digit_matrix_i64_ptr_i64(B[i], dm2);
mat_vec_ptr_i64_ptr_i64_ptr_i64(dm2, v, vv2);
int32_t __flow_step_17 = 1;
for (int32_t j = 0; (0 <= 4) ? j < 4 : j > 4; j += (0 <= 4) ? 1 : -1) {
v[j] = vv2[j];
}
}
free(dm2);
free(vv2);
int64_t ans = FLOW_CHECKED_MOD((v[0]), (MOD));
if (ans < 0) {
ans = (ans + MOD);
}
printf("%lld\n", ans);
free(v);
free(M_block);
free(B);
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(1117117717 : i64) : i64
func.func @mat_mul(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%0 = arith.constant 0 : i32
%1 = arith.constant 4 : i32
%2 = arith.index_cast %0 : i32 to index
%3 = arith.index_cast %1 : i32 to index
%5 = arith.constant 1 : index
%6 = arith.constant -1 : index
%7 = arith.cmpi sle, %2, %3 : index
%4 = arith.select %7, %5, %6 : index
cf.br ^bb0(%2 : index)
^bb0(%8: index):
%9 = arith.cmpi slt, %8, %3 : index
%10 = arith.cmpi sgt, %8, %3 : index
%11 = arith.select %7, %9, %10 : i1
cf.cond_br %11, ^bb1(%8 : index), ^bb2(%8 : index)
^bb1(%12: index):
%13 = arith.constant 0 : i32
%14 = arith.constant 4 : i32
%15 = arith.index_cast %13 : i32 to index
%16 = arith.index_cast %14 : i32 to index
%18 = arith.constant 1 : index
%19 = arith.constant -1 : index
%20 = arith.cmpi sle, %15, %16 : index
%17 = arith.select %20, %18, %19 : index
cf.br ^bb3(%15 : index)
^bb3(%21: index):
%22 = arith.cmpi slt, %21, %16 : index
%23 = arith.cmpi sgt, %21, %16 : index
%24 = arith.select %20, %22, %23 : i1
cf.cond_br %24, ^bb4(%21 : index), ^bb5(%21 : index)
^bb4(%25: index):
%26 = arith.constant 0 : i32
%27 = arith.extsi %26 : i32 to i64
%28 = llvm.mlir.constant(1 : i64) : i64
%29 = llvm.alloca %28 x i64 : (i64) -> !llvm.ptr
llvm.store %27, %29 : i64, !llvm.ptr
%30 = arith.constant 0 : i32
%31 = arith.constant 4 : i32
%32 = arith.index_cast %30 : i32 to index
%33 = arith.index_cast %31 : i32 to index
%35 = arith.constant 1 : index
%36 = arith.constant -1 : index
%37 = arith.cmpi sle, %32, %33 : index
%34 = arith.select %37, %35, %36 : index
cf.br ^bb6(%32 : index)
^bb6(%38: index):
%39 = arith.cmpi slt, %38, %33 : index
%40 = arith.cmpi sgt, %38, %33 : index
%41 = arith.select %37, %39, %40 : i1
cf.cond_br %41, ^bb7(%38 : index), ^bb8(%38 : index)
^bb7(%42: index):
%43 = llvm.load %29 : !llvm.ptr -> i64
%45 = arith.constant 4 : i32
%47 = arith.index_cast %12 : index to i32
%46 = arith.muli %47, %45 : i32
%49 = arith.index_cast %42 : index to i32
%48 = arith.addi %46, %49 : i32
%50 = arith.extsi %48 : i32 to i64
%51 = llvm.getelementptr %arg0[%50] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%44 = llvm.load %51 : !llvm.ptr -> i64
%53 = arith.constant 4 : i32
%55 = arith.index_cast %42 : index to i32
%54 = arith.muli %55, %53 : i32
%57 = arith.index_cast %25 : index to i32
%56 = arith.addi %54, %57 : i32
%58 = arith.extsi %56 : i32 to i64
%59 = llvm.getelementptr %arg1[%58] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%52 = llvm.load %59 : !llvm.ptr -> i64
%60 = arith.muli %44, %52 : i64
%61 = arith.addi %43, %60 : i64
%62 = llvm.mlir.addressof @MOD : !llvm.ptr
%63 = llvm.load %62 : !llvm.ptr -> i64
%64 = arith.remsi %61, %63 : i64
llvm.store %64, %29 : i64, !llvm.ptr
%65 = arith.addi %42, %34 : index
cf.br ^bb6(%65 : index)
^bb8(%66: index):
%67 = llvm.load %29 : !llvm.ptr -> i64
%68 = arith.constant 4 : i32
%70 = arith.index_cast %12 : index to i32
%69 = arith.muli %70, %68 : i32
%72 = arith.index_cast %25 : index to i32
%71 = arith.addi %69, %72 : i32
%73 = arith.extsi %71 : i32 to i64
%74 = llvm.getelementptr %arg2[%73] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %67, %74 : i64, !llvm.ptr
%75 = arith.addi %25, %17 : index
cf.br ^bb3(%75 : index)
^bb5(%76: index):
%77 = arith.addi %12, %4 : index
cf.br ^bb0(%77 : index)
^bb2(%78: index):
func.return
}
func.func @mat_pow(%arg0: !llvm.ptr, %arg1: i64, %arg2: !llvm.ptr) -> () {
%79 = arith.constant 0 : i32
%80 = arith.constant 4 : i32
%81 = arith.index_cast %79 : i32 to index
%82 = arith.index_cast %80 : i32 to index
%84 = arith.constant 1 : index
%85 = arith.constant -1 : index
%86 = arith.cmpi sle, %81, %82 : index
%83 = arith.select %86, %84, %85 : index
cf.br ^bb9(%81 : index)
^bb9(%87: index):
%88 = arith.cmpi slt, %87, %82 : index
%89 = arith.cmpi sgt, %87, %82 : index
%90 = arith.select %86, %88, %89 : i1
cf.cond_br %90, ^bb10(%87 : index), ^bb11(%87 : index)
^bb10(%91: index):
%92 = arith.constant 0 : i32
%93 = arith.constant 4 : i32
%94 = arith.index_cast %92 : i32 to index
%95 = arith.index_cast %93 : i32 to index
%97 = arith.constant 1 : index
%98 = arith.constant -1 : index
%99 = arith.cmpi sle, %94, %95 : index
%96 = arith.select %99, %97, %98 : index
cf.br ^bb12(%94 : index)
^bb12(%100: index):
%101 = arith.cmpi slt, %100, %95 : index
%102 = arith.cmpi sgt, %100, %95 : index
%103 = arith.select %99, %101, %102 : i1
cf.cond_br %103, ^bb13(%100 : index), ^bb14(%100 : index)
^bb13(%104: index):
%105 = arith.cmpi eq, %91, %104 : index
cf.cond_br %105, ^bb15, ^bb16
^bb15:
%106 = arith.constant 1 : i32
%107 = arith.constant 4 : i32
%109 = arith.index_cast %91 : index to i32
%108 = arith.muli %109, %107 : i32
%111 = arith.index_cast %104 : index to i32
%110 = arith.addi %108, %111 : i32
%112 = arith.extsi %106 : i32 to i64
%113 = arith.extsi %110 : i32 to i64
%114 = llvm.getelementptr %arg2[%113] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %112, %114 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
%115 = arith.constant 0 : i32
%116 = arith.constant 4 : i32
%118 = arith.index_cast %91 : index to i32
%117 = arith.muli %118, %116 : i32
%120 = arith.index_cast %104 : index to i32
%119 = arith.addi %117, %120 : i32
%121 = arith.extsi %115 : i32 to i64
%122 = arith.extsi %119 : i32 to i64
%123 = llvm.getelementptr %arg2[%122] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %121, %123 : i64, !llvm.ptr
cf.br ^bb17
^bb17:
%124 = arith.addi %104, %96 : index
cf.br ^bb12(%124 : index)
^bb14(%125: index):
%126 = arith.addi %91, %83 : index
cf.br ^bb9(%126 : index)
^bb11(%127: index):
%129 = arith.constant 16 : i32
%130 = arith.constant 8 : i32
%131 = arith.extsi %129 : i32 to i64
%132 = arith.extsi %130 : i32 to i64
%128 = func.call @calloc(%131, %132) : (i64, i64) -> !llvm.ptr
%133 = arith.constant 0 : i32
%134 = arith.constant 16 : i32
%135 = arith.index_cast %133 : i32 to index
%136 = arith.index_cast %134 : i32 to index
%138 = arith.constant 1 : index
%139 = arith.constant -1 : index
%140 = arith.cmpi sle, %135, %136 : index
%137 = arith.select %140, %138, %139 : index
cf.br ^bb18(%135 : index)
^bb18(%141: index):
%142 = arith.cmpi slt, %141, %136 : index
%143 = arith.cmpi sgt, %141, %136 : index
%144 = arith.select %140, %142, %143 : i1
cf.cond_br %144, ^bb19(%141 : index), ^bb20(%141 : index)
^bb19(%145: index):
%147 = arith.index_cast %145 : index to i64
%148 = llvm.getelementptr %arg0[%147] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%146 = llvm.load %148 : !llvm.ptr -> i64
%149 = arith.index_cast %145 : index to i64
%150 = llvm.getelementptr %128[%149] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %146, %150 : i64, !llvm.ptr
%151 = arith.addi %145, %137 : index
cf.br ^bb18(%151 : index)
^bb20(%152: index):
%153 = llvm.mlir.constant(1 : i64) : i64
%154 = llvm.alloca %153 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %154 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%155 = llvm.load %154 : !llvm.ptr -> i64
%156 = arith.constant 0 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.cmpi sgt, %155, %158 : i64
cf.cond_br %157, ^bb22, ^bb23
^bb22:
%159 = llvm.load %154 : !llvm.ptr -> i64
%160 = arith.constant 1 : i32
%161 = arith.constant 1 : i32
%162 = arith.cmpi eq, %160, %161 : i32
%164 = arith.trunci %159 : i64 to i1
%163 = arith.andi %164, %162 : i1
cf.cond_br %163, ^bb24, ^bb25
^bb24:
%166 = arith.constant 16 : i32
%167 = arith.constant 8 : i32
%168 = arith.extsi %166 : i32 to i64
%169 = arith.extsi %167 : i32 to i64
%165 = func.call @calloc(%168, %169) : (i64, i64) -> !llvm.ptr
func.call @mat_mul(%arg2, %128, %165) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%171 = arith.constant 0 : i32
%172 = arith.constant 16 : i32
%173 = arith.index_cast %171 : i32 to index
%174 = arith.index_cast %172 : i32 to index
%176 = arith.constant 1 : index
%177 = arith.constant -1 : index
%178 = arith.cmpi sle, %173, %174 : index
%175 = arith.select %178, %176, %177 : index
cf.br ^bb27(%173 : index)
^bb27(%179: index):
%180 = arith.cmpi slt, %179, %174 : index
%181 = arith.cmpi sgt, %179, %174 : index
%182 = arith.select %178, %180, %181 : i1
cf.cond_br %182, ^bb28(%179 : index), ^bb29(%179 : index)
^bb28(%183: index):
%185 = arith.index_cast %183 : index to i64
%186 = llvm.getelementptr %165[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%184 = llvm.load %186 : !llvm.ptr -> i64
%187 = arith.index_cast %183 : index to i64
%188 = llvm.getelementptr %arg2[%187] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %184, %188 : i64, !llvm.ptr
%189 = arith.addi %183, %175 : index
cf.br ^bb27(%189 : index)
^bb29(%190: index):
func.call @free(%165) : (!llvm.ptr) -> ()
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%193 = arith.constant 16 : i32
%194 = arith.constant 8 : i32
%195 = arith.extsi %193 : i32 to i64
%196 = arith.extsi %194 : i32 to i64
%192 = func.call @calloc(%195, %196) : (i64, i64) -> !llvm.ptr
func.call @mat_mul(%128, %128, %192) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%198 = arith.constant 0 : i32
%199 = arith.constant 16 : i32
%200 = arith.index_cast %198 : i32 to index
%201 = arith.index_cast %199 : i32 to index
%203 = arith.constant 1 : index
%204 = arith.constant -1 : index
%205 = arith.cmpi sle, %200, %201 : index
%202 = arith.select %205, %203, %204 : index
cf.br ^bb30(%200 : index)
^bb30(%206: index):
%207 = arith.cmpi slt, %206, %201 : index
%208 = arith.cmpi sgt, %206, %201 : index
%209 = arith.select %205, %207, %208 : i1
cf.cond_br %209, ^bb31(%206 : index), ^bb32(%206 : index)
^bb31(%210: index):
%212 = arith.index_cast %210 : index to i64
%213 = llvm.getelementptr %192[%212] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%211 = llvm.load %213 : !llvm.ptr -> i64
%214 = arith.index_cast %210 : index to i64
%215 = llvm.getelementptr %128[%214] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %211, %215 : i64, !llvm.ptr
%216 = arith.addi %210, %202 : index
cf.br ^bb30(%216 : index)
^bb32(%217: index):
func.call @free(%192) : (!llvm.ptr) -> ()
%219 = llvm.load %154 : !llvm.ptr -> i64
%220 = arith.constant 1 : i32
%222 = arith.extsi %220 : i32 to i64
%221 = arith.shrsi %219, %222 : i64
llvm.store %221, %154 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
func.call @free(%128) : (!llvm.ptr) -> ()
func.return
}
func.func @mat_vec(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%224 = arith.constant 0 : i32
%225 = arith.constant 4 : i32
%226 = arith.index_cast %224 : i32 to index
%227 = arith.index_cast %225 : i32 to index
%229 = arith.constant 1 : index
%230 = arith.constant -1 : index
%231 = arith.cmpi sle, %226, %227 : index
%228 = arith.select %231, %229, %230 : index
cf.br ^bb33(%226 : index)
^bb33(%232: index):
%233 = arith.cmpi slt, %232, %227 : index
%234 = arith.cmpi sgt, %232, %227 : index
%235 = arith.select %231, %233, %234 : i1
cf.cond_br %235, ^bb34(%232 : index), ^bb35(%232 : index)
^bb34(%236: index):
%237 = arith.constant 0 : i32
%238 = arith.extsi %237 : i32 to i64
%239 = llvm.mlir.constant(1 : i64) : i64
%240 = llvm.alloca %239 x i64 : (i64) -> !llvm.ptr
llvm.store %238, %240 : i64, !llvm.ptr
%241 = arith.constant 0 : i32
%242 = arith.constant 4 : i32
%243 = arith.index_cast %241 : i32 to index
%244 = arith.index_cast %242 : i32 to index
%246 = arith.constant 1 : index
%247 = arith.constant -1 : index
%248 = arith.cmpi sle, %243, %244 : index
%245 = arith.select %248, %246, %247 : index
cf.br ^bb36(%243 : index)
^bb36(%249: index):
%250 = arith.cmpi slt, %249, %244 : index
%251 = arith.cmpi sgt, %249, %244 : index
%252 = arith.select %248, %250, %251 : i1
cf.cond_br %252, ^bb37(%249 : index), ^bb38(%249 : index)
^bb37(%253: index):
%254 = llvm.load %240 : !llvm.ptr -> i64
%256 = arith.constant 4 : i32
%258 = arith.index_cast %236 : index to i32
%257 = arith.muli %258, %256 : i32
%260 = arith.index_cast %253 : index to i32
%259 = arith.addi %257, %260 : i32
%261 = arith.extsi %259 : i32 to i64
%262 = llvm.getelementptr %arg0[%261] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%255 = llvm.load %262 : !llvm.ptr -> i64
%264 = arith.index_cast %253 : index to i64
%265 = llvm.getelementptr %arg1[%264] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%263 = llvm.load %265 : !llvm.ptr -> i64
%266 = arith.muli %255, %263 : i64
%267 = arith.addi %254, %266 : i64
%268 = llvm.mlir.addressof @MOD : !llvm.ptr
%269 = llvm.load %268 : !llvm.ptr -> i64
%270 = arith.remsi %267, %269 : i64
llvm.store %270, %240 : i64, !llvm.ptr
%271 = arith.addi %253, %245 : index
cf.br ^bb36(%271 : index)
^bb38(%272: index):
%273 = llvm.load %240 : !llvm.ptr -> i64
%274 = arith.index_cast %236 : index to i64
%275 = llvm.getelementptr %arg2[%274] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %273, %275 : i64, !llvm.ptr
%276 = arith.addi %236, %228 : index
cf.br ^bb33(%276 : index)
^bb35(%277: index):
func.return
}
func.func @digit_matrix(%arg0: i64, %arg1: !llvm.ptr) -> () {
%278 = arith.constant 6 : i32
%280 = arith.constant 0 : i32
%279 = arith.subi %280, %278 : i32
%281 = arith.constant 7 : i32
%283 = arith.extsi %281 : i32 to i64
%282 = arith.muli %283, %arg0 : i64
%285 = arith.extsi %279 : i32 to i64
%284 = arith.addi %285, %282 : i64
%286 = arith.constant 1 : i32
%288 = arith.extsi %286 : i32 to i64
%287 = arith.addi %arg0, %288 : i64
%289 = arith.muli %arg0, %287 : i64
%290 = arith.constant 2 : i32
%292 = arith.extsi %290 : i32 to i64
%291 = arith.divsi %289, %292 : i64
%293 = arith.subi %284, %291 : i64
%294 = llvm.mlir.addressof @MOD : !llvm.ptr
%295 = llvm.load %294 : !llvm.ptr -> i64
%296 = arith.remsi %293, %295 : i64
%297 = arith.constant 0 : i32
%299 = arith.extsi %297 : i32 to i64
%298 = arith.cmpi slt, %296, %299 : i64
%300 = scf.if %298 -> (i64) {
%301 = llvm.mlir.addressof @MOD : !llvm.ptr
%302 = llvm.load %301 : !llvm.ptr -> i64
%303 = arith.addi %296, %302 : i64
scf.yield %303 : i64
} else {
scf.yield %296 : i64
}
%304 = llvm.mlir.undef : i64
%305 = arith.constant 6 : i32
%307 = arith.extsi %305 : i32 to i64
%306 = arith.cmpi eq, %arg0, %307 : i64
%308 = scf.if %306 -> (i64) {
%309 = arith.constant 0 : i32
%310 = arith.extsi %309 : i32 to i64
scf.yield %310 : i64
} else {
%311 = arith.constant 6 : i32
%313 = arith.extsi %311 : i32 to i64
%312 = arith.subi %313, %arg0 : i64
%314 = llvm.mlir.addressof @MOD : !llvm.ptr
%315 = llvm.load %314 : !llvm.ptr -> i64
%316 = arith.remsi %312, %315 : i64
scf.yield %316 : i64
}
%317 = arith.constant 0 : i32
%319 = arith.extsi %317 : i32 to i64
%318 = arith.cmpi slt, %308, %319 : i64
%320 = scf.if %318 -> (i64) {
%321 = llvm.mlir.addressof @MOD : !llvm.ptr
%322 = llvm.load %321 : !llvm.ptr -> i64
%323 = arith.addi %308, %322 : i64
scf.yield %323 : i64
} else {
scf.yield %308 : i64
}
%324 = arith.constant 7 : i32
%325 = llvm.mlir.addressof @MOD : !llvm.ptr
%326 = llvm.load %325 : !llvm.ptr -> i64
%328 = arith.extsi %324 : i32 to i64
%327 = arith.remsi %328, %326 : i64
%329 = arith.constant 0 : i32
%330 = arith.extsi %329 : i32 to i64
%331 = llvm.getelementptr %arg1[%330] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %327, %331 : i64, !llvm.ptr
%332 = llvm.mlir.addressof @MOD : !llvm.ptr
%333 = llvm.load %332 : !llvm.ptr -> i64
%334 = arith.remsi %arg0, %333 : i64
%335 = arith.constant 1 : i32
%336 = arith.extsi %335 : i32 to i64
%337 = llvm.getelementptr %arg1[%336] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %334, %337 : i64, !llvm.ptr
%338 = arith.constant 21 : i32
%339 = llvm.mlir.addressof @MOD : !llvm.ptr
%340 = llvm.load %339 : !llvm.ptr -> i64
%342 = arith.extsi %338 : i32 to i64
%341 = arith.remsi %342, %340 : i64
%343 = arith.constant 2 : i32
%344 = arith.extsi %343 : i32 to i64
%345 = llvm.getelementptr %arg1[%344] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %341, %345 : i64, !llvm.ptr
%346 = arith.constant 3 : i32
%347 = arith.extsi %346 : i32 to i64
%348 = llvm.getelementptr %arg1[%347] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %300, %348 : i64, !llvm.ptr
%349 = arith.constant 0 : i32
%350 = arith.constant 4 : i32
%351 = arith.extsi %349 : i32 to i64
%352 = arith.extsi %350 : i32 to i64
%353 = llvm.getelementptr %arg1[%352] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %351, %353 : i64, !llvm.ptr
%354 = arith.constant 1 : i32
%355 = arith.constant 5 : i32
%356 = arith.extsi %354 : i32 to i64
%357 = arith.extsi %355 : i32 to i64
%358 = llvm.getelementptr %arg1[%357] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %356, %358 : i64, !llvm.ptr
%359 = arith.constant 0 : i32
%360 = arith.constant 6 : i32
%361 = arith.extsi %359 : i32 to i64
%362 = arith.extsi %360 : i32 to i64
%363 = llvm.getelementptr %arg1[%362] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %361, %363 : i64, !llvm.ptr
%364 = arith.constant 7 : i32
%365 = arith.extsi %364 : i32 to i64
%366 = llvm.getelementptr %arg1[%365] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %320, %366 : i64, !llvm.ptr
%367 = arith.constant 0 : i32
%368 = arith.constant 8 : i32
%369 = arith.extsi %367 : i32 to i64
%370 = arith.extsi %368 : i32 to i64
%371 = llvm.getelementptr %arg1[%370] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %369, %371 : i64, !llvm.ptr
%372 = arith.constant 0 : i32
%373 = arith.constant 9 : i32
%374 = arith.extsi %372 : i32 to i64
%375 = arith.extsi %373 : i32 to i64
%376 = llvm.getelementptr %arg1[%375] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %374, %376 : i64, !llvm.ptr
%377 = arith.constant 7 : i32
%378 = llvm.mlir.addressof @MOD : !llvm.ptr
%379 = llvm.load %378 : !llvm.ptr -> i64
%381 = arith.extsi %377 : i32 to i64
%380 = arith.remsi %381, %379 : i64
%382 = arith.constant 10 : i32
%383 = arith.extsi %382 : i32 to i64
%384 = llvm.getelementptr %arg1[%383] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %380, %384 : i64, !llvm.ptr
%385 = llvm.mlir.addressof @MOD : !llvm.ptr
%386 = llvm.load %385 : !llvm.ptr -> i64
%387 = arith.remsi %arg0, %386 : i64
%388 = arith.constant 11 : i32
%389 = arith.extsi %388 : i32 to i64
%390 = llvm.getelementptr %arg1[%389] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %387, %390 : i64, !llvm.ptr
%391 = arith.constant 0 : i32
%392 = arith.constant 12 : i32
%393 = arith.extsi %391 : i32 to i64
%394 = arith.extsi %392 : i32 to i64
%395 = llvm.getelementptr %arg1[%394] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %393, %395 : i64, !llvm.ptr
%396 = arith.constant 0 : i32
%397 = arith.constant 13 : i32
%398 = arith.extsi %396 : i32 to i64
%399 = arith.extsi %397 : i32 to i64
%400 = llvm.getelementptr %arg1[%399] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %398, %400 : i64, !llvm.ptr
%401 = arith.constant 0 : i32
%402 = arith.constant 14 : i32
%403 = arith.extsi %401 : i32 to i64
%404 = arith.extsi %402 : i32 to i64
%405 = llvm.getelementptr %arg1[%404] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %403, %405 : i64, !llvm.ptr
%406 = arith.constant 1 : i32
%407 = arith.constant 15 : i32
%408 = arith.extsi %406 : i32 to i64
%409 = arith.extsi %407 : i32 to i64
%410 = llvm.getelementptr %arg1[%409] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %408, %410 : i64, !llvm.ptr
func.return
}
func.func @main() -> i32 {
%412 = arith.constant 10 : i32
%413 = arith.constant 8 : i32
%414 = arith.extsi %412 : i32 to i64
%415 = arith.extsi %413 : i32 to i64
%411 = func.call @calloc(%414, %415) : (i64, i64) -> !llvm.ptr
%416 = arith.constant 4 : i32
%417 = arith.constant 0 : i32
%418 = arith.extsi %416 : i32 to i64
%419 = arith.extsi %417 : i32 to i64
%420 = llvm.getelementptr %411[%419] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %418, %420 : i64, !llvm.ptr
%421 = arith.constant 3 : i32
%422 = arith.constant 1 : i32
%423 = arith.extsi %421 : i32 to i64
%424 = arith.extsi %422 : i32 to i64
%425 = llvm.getelementptr %411[%424] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %423, %425 : i64, !llvm.ptr
%426 = arith.constant 1 : i32
%427 = arith.constant 2 : i32
%428 = arith.extsi %426 : i32 to i64
%429 = arith.extsi %427 : i32 to i64
%430 = llvm.getelementptr %411[%429] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %428, %430 : i64, !llvm.ptr
%431 = arith.constant 1 : i32
%432 = arith.constant 3 : i32
%433 = arith.extsi %431 : i32 to i64
%434 = arith.extsi %432 : i32 to i64
%435 = llvm.getelementptr %411[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %433, %435 : i64, !llvm.ptr
%436 = arith.constant 6 : i32
%437 = arith.constant 4 : i32
%438 = arith.extsi %436 : i32 to i64
%439 = arith.extsi %437 : i32 to i64
%440 = llvm.getelementptr %411[%439] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %438, %440 : i64, !llvm.ptr
%441 = arith.constant 2 : i32
%442 = arith.constant 5 : i32
%443 = arith.extsi %441 : i32 to i64
%444 = arith.extsi %442 : i32 to i64
%445 = llvm.getelementptr %411[%444] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %443, %445 : i64, !llvm.ptr
%446 = arith.constant 3 : i32
%447 = arith.constant 6 : i32
%448 = arith.extsi %446 : i32 to i64
%449 = arith.extsi %447 : i32 to i64
%450 = llvm.getelementptr %411[%449] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %448, %450 : i64, !llvm.ptr
%451 = arith.constant 5 : i32
%452 = arith.constant 7 : i32
%453 = arith.extsi %451 : i32 to i64
%454 = arith.extsi %452 : i32 to i64
%455 = llvm.getelementptr %411[%454] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %453, %455 : i64, !llvm.ptr
%456 = arith.constant 5 : i32
%457 = arith.constant 8 : i32
%458 = arith.extsi %456 : i32 to i64
%459 = arith.extsi %457 : i32 to i64
%460 = llvm.getelementptr %411[%459] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %458, %460 : i64, !llvm.ptr
%461 = arith.constant 0 : i32
%462 = arith.constant 9 : i32
%463 = arith.extsi %461 : i32 to i64
%464 = arith.extsi %462 : i32 to i64
%465 = llvm.getelementptr %411[%464] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %463, %465 : i64, !llvm.ptr
%466 = arith.constant 1000000000 : i32
%467 = arith.extsi %466 : i32 to i64
%468 = arith.constant 1 : i32
%470 = arith.extsi %468 : i32 to i64
%469 = arith.subi %467, %470 : i64
%471 = arith.constant 10 : i32
%473 = arith.extsi %471 : i32 to i64
%472 = arith.divsi %469, %473 : i64
%474 = arith.constant 10 : i32
%476 = arith.extsi %474 : i32 to i64
%475 = arith.remsi %469, %476 : i64
%478 = arith.constant 16 : i32
%479 = arith.constant 8 : i32
%480 = arith.extsi %478 : i32 to i64
%481 = arith.extsi %479 : i32 to i64
%477 = func.call @calloc(%480, %481) : (i64, i64) -> !llvm.ptr
%482 = arith.constant 0 : i32
%483 = arith.constant 4 : i32
%484 = arith.index_cast %482 : i32 to index
%485 = arith.index_cast %483 : i32 to index
%487 = arith.constant 1 : index
%488 = arith.constant -1 : index
%489 = arith.cmpi sle, %484, %485 : index
%486 = arith.select %489, %487, %488 : index
cf.br ^bb39(%484 : index)
^bb39(%490: index):
%491 = arith.cmpi slt, %490, %485 : index
%492 = arith.cmpi sgt, %490, %485 : index
%493 = arith.select %489, %491, %492 : i1
cf.cond_br %493, ^bb40(%490 : index), ^bb41(%490 : index)
^bb40(%494: index):
%495 = arith.constant 0 : i32
%496 = arith.constant 4 : i32
%497 = arith.index_cast %495 : i32 to index
%498 = arith.index_cast %496 : i32 to index
%500 = arith.constant 1 : index
%501 = arith.constant -1 : index
%502 = arith.cmpi sle, %497, %498 : index
%499 = arith.select %502, %500, %501 : index
cf.br ^bb42(%497 : index)
^bb42(%503: index):
%504 = arith.cmpi slt, %503, %498 : index
%505 = arith.cmpi sgt, %503, %498 : index
%506 = arith.select %502, %504, %505 : i1
cf.cond_br %506, ^bb43(%503 : index), ^bb44(%503 : index)
^bb43(%507: index):
%508 = arith.cmpi eq, %494, %507 : index
cf.cond_br %508, ^bb45, ^bb46
^bb45:
%509 = arith.constant 1 : i32
%510 = arith.constant 4 : i32
%512 = arith.index_cast %494 : index to i32
%511 = arith.muli %512, %510 : i32
%514 = arith.index_cast %507 : index to i32
%513 = arith.addi %511, %514 : i32
%515 = arith.extsi %509 : i32 to i64
%516 = arith.extsi %513 : i32 to i64
%517 = llvm.getelementptr %477[%516] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %515, %517 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
%518 = arith.constant 0 : i32
%519 = arith.constant 4 : i32
%521 = arith.index_cast %494 : index to i32
%520 = arith.muli %521, %519 : i32
%523 = arith.index_cast %507 : index to i32
%522 = arith.addi %520, %523 : i32
%524 = arith.extsi %518 : i32 to i64
%525 = arith.extsi %522 : i32 to i64
%526 = llvm.getelementptr %477[%525] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %524, %526 : i64, !llvm.ptr
cf.br ^bb47
^bb47:
%527 = arith.addi %507, %499 : index
cf.br ^bb42(%527 : index)
^bb44(%528: index):
%529 = arith.addi %494, %486 : index
cf.br ^bb39(%529 : index)
^bb41(%530: index):
%532 = arith.constant 16 : i32
%533 = arith.constant 8 : i32
%534 = arith.extsi %532 : i32 to i64
%535 = arith.extsi %533 : i32 to i64
%531 = func.call @calloc(%534, %535) : (i64, i64) -> !llvm.ptr
%537 = arith.constant 16 : i32
%538 = arith.constant 8 : i32
%539 = arith.extsi %537 : i32 to i64
%540 = arith.extsi %538 : i32 to i64
%536 = func.call @calloc(%539, %540) : (i64, i64) -> !llvm.ptr
%541 = arith.constant 0 : i32
%542 = arith.constant 10 : i32
%543 = arith.index_cast %541 : i32 to index
%544 = arith.index_cast %542 : i32 to index
%546 = arith.constant 1 : index
%547 = arith.constant -1 : index
%548 = arith.cmpi sle, %543, %544 : index
%545 = arith.select %548, %546, %547 : index
cf.br ^bb48(%543 : index)
^bb48(%549: index):
%550 = arith.cmpi slt, %549, %544 : index
%551 = arith.cmpi sgt, %549, %544 : index
%552 = arith.select %548, %550, %551 : i1
cf.cond_br %552, ^bb49(%549 : index), ^bb50(%549 : index)
^bb49(%553: index):
%556 = arith.index_cast %553 : index to i64
%557 = llvm.getelementptr %411[%556] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%555 = llvm.load %557 : !llvm.ptr -> i64
func.call @digit_matrix(%555, %531) : (i64, !llvm.ptr) -> ()
func.call @mat_mul(%531, %477, %536) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%559 = arith.constant 0 : i32
%560 = arith.constant 16 : i32
%561 = arith.index_cast %559 : i32 to index
%562 = arith.index_cast %560 : i32 to index
%564 = arith.constant 1 : index
%565 = arith.constant -1 : index
%566 = arith.cmpi sle, %561, %562 : index
%563 = arith.select %566, %564, %565 : index
cf.br ^bb51(%561 : index)
^bb51(%567: index):
%568 = arith.cmpi slt, %567, %562 : index
%569 = arith.cmpi sgt, %567, %562 : index
%570 = arith.select %566, %568, %569 : i1
cf.cond_br %570, ^bb52(%567 : index), ^bb53(%567 : index)
^bb52(%571: index):
%573 = arith.index_cast %571 : index to i64
%574 = llvm.getelementptr %536[%573] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%572 = llvm.load %574 : !llvm.ptr -> i64
%575 = arith.index_cast %571 : index to i64
%576 = llvm.getelementptr %477[%575] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %572, %576 : i64, !llvm.ptr
%577 = arith.addi %571, %563 : index
cf.br ^bb51(%577 : index)
^bb53(%578: index):
%579 = arith.addi %553, %545 : index
cf.br ^bb48(%579 : index)
^bb50(%580: index):
func.call @free(%531) : (!llvm.ptr) -> ()
func.call @free(%536) : (!llvm.ptr) -> ()
%584 = arith.constant 4 : i32
%585 = arith.constant 8 : i32
%586 = arith.extsi %584 : i32 to i64
%587 = arith.extsi %585 : i32 to i64
%583 = func.call @calloc(%586, %587) : (i64, i64) -> !llvm.ptr
%588 = arith.constant 0 : i32
%589 = arith.constant 0 : i32
%590 = arith.extsi %588 : i32 to i64
%591 = arith.extsi %589 : i32 to i64
%592 = llvm.getelementptr %583[%591] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %590, %592 : i64, !llvm.ptr
%593 = arith.constant 0 : i32
%594 = arith.constant 1 : i32
%595 = arith.extsi %593 : i32 to i64
%596 = arith.extsi %594 : i32 to i64
%597 = llvm.getelementptr %583[%596] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %595, %597 : i64, !llvm.ptr
%598 = arith.constant 0 : i32
%599 = arith.constant 2 : i32
%600 = arith.extsi %598 : i32 to i64
%601 = arith.extsi %599 : i32 to i64
%602 = llvm.getelementptr %583[%601] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %600, %602 : i64, !llvm.ptr
%603 = arith.constant 1 : i32
%604 = arith.constant 3 : i32
%605 = arith.extsi %603 : i32 to i64
%606 = arith.extsi %604 : i32 to i64
%607 = llvm.getelementptr %583[%606] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %605, %607 : i64, !llvm.ptr
%608 = arith.constant 0 : i32
%610 = arith.extsi %608 : i32 to i64
%609 = arith.cmpi sgt, %472, %610 : i64
cf.cond_br %609, ^bb54, ^bb55
^bb54:
%612 = arith.constant 16 : i32
%613 = arith.constant 8 : i32
%614 = arith.extsi %612 : i32 to i64
%615 = arith.extsi %613 : i32 to i64
%611 = func.call @calloc(%614, %615) : (i64, i64) -> !llvm.ptr
func.call @mat_pow(%477, %472, %611) : (!llvm.ptr, i64, !llvm.ptr) -> ()
%618 = arith.constant 4 : i32
%619 = arith.constant 8 : i32
%620 = arith.extsi %618 : i32 to i64
%621 = arith.extsi %619 : i32 to i64
%617 = func.call @calloc(%620, %621) : (i64, i64) -> !llvm.ptr
func.call @mat_vec(%611, %583, %617) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%623 = arith.constant 0 : i32
%624 = arith.constant 4 : i32
%625 = arith.index_cast %623 : i32 to index
%626 = arith.index_cast %624 : i32 to index
%628 = arith.constant 1 : index
%629 = arith.constant -1 : index
%630 = arith.cmpi sle, %625, %626 : index
%627 = arith.select %630, %628, %629 : index
cf.br ^bb57(%625 : index)
^bb57(%631: index):
%632 = arith.cmpi slt, %631, %626 : index
%633 = arith.cmpi sgt, %631, %626 : index
%634 = arith.select %630, %632, %633 : i1
cf.cond_br %634, ^bb58(%631 : index), ^bb59(%631 : index)
^bb58(%635: index):
%637 = arith.index_cast %635 : index to i64
%638 = llvm.getelementptr %617[%637] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%636 = llvm.load %638 : !llvm.ptr -> i64
%639 = arith.index_cast %635 : index to i64
%640 = llvm.getelementptr %583[%639] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %636, %640 : i64, !llvm.ptr
%641 = arith.addi %635, %627 : index
cf.br ^bb57(%641 : index)
^bb59(%642: index):
func.call @free(%617) : (!llvm.ptr) -> ()
func.call @free(%611) : (!llvm.ptr) -> ()
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%646 = arith.constant 16 : i32
%647 = arith.constant 8 : i32
%648 = arith.extsi %646 : i32 to i64
%649 = arith.extsi %647 : i32 to i64
%645 = func.call @calloc(%648, %649) : (i64, i64) -> !llvm.ptr
%651 = arith.constant 4 : i32
%652 = arith.constant 8 : i32
%653 = arith.extsi %651 : i32 to i64
%654 = arith.extsi %652 : i32 to i64
%650 = func.call @calloc(%653, %654) : (i64, i64) -> !llvm.ptr
%655 = arith.constant 0 : i32
%656 = arith.index_cast %655 : i32 to index
%657 = arith.index_cast %475 : i32 to index
%659 = arith.constant 1 : index
%660 = arith.constant -1 : index
%661 = arith.cmpi sle, %656, %657 : index
%658 = arith.select %661, %659, %660 : index
cf.br ^bb60(%656 : index)
^bb60(%662: index):
%663 = arith.cmpi slt, %662, %657 : index
%664 = arith.cmpi sgt, %662, %657 : index
%665 = arith.select %661, %663, %664 : i1
cf.cond_br %665, ^bb61(%662 : index), ^bb62(%662 : index)
^bb61(%666: index):
%669 = arith.index_cast %666 : index to i64
%670 = llvm.getelementptr %411[%669] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%668 = llvm.load %670 : !llvm.ptr -> i64
func.call @digit_matrix(%668, %645) : (i64, !llvm.ptr) -> ()
func.call @mat_vec(%645, %583, %650) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%672 = arith.constant 0 : i32
%673 = arith.constant 4 : i32
%674 = arith.index_cast %672 : i32 to index
%675 = arith.index_cast %673 : i32 to index
%677 = arith.constant 1 : index
%678 = arith.constant -1 : index
%679 = arith.cmpi sle, %674, %675 : index
%676 = arith.select %679, %677, %678 : index
cf.br ^bb63(%674 : index)
^bb63(%680: index):
%681 = arith.cmpi slt, %680, %675 : index
%682 = arith.cmpi sgt, %680, %675 : index
%683 = arith.select %679, %681, %682 : i1
cf.cond_br %683, ^bb64(%680 : index), ^bb65(%680 : index)
^bb64(%684: index):
%686 = arith.index_cast %684 : index to i64
%687 = llvm.getelementptr %650[%686] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%685 = llvm.load %687 : !llvm.ptr -> i64
%688 = arith.index_cast %684 : index to i64
%689 = llvm.getelementptr %583[%688] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %685, %689 : i64, !llvm.ptr
%690 = arith.addi %684, %676 : index
cf.br ^bb63(%690 : index)
^bb65(%691: index):
%692 = arith.addi %666, %658 : index
cf.br ^bb60(%692 : index)
^bb62(%693: index):
func.call @free(%645) : (!llvm.ptr) -> ()
func.call @free(%650) : (!llvm.ptr) -> ()
%697 = arith.constant 0 : i32
%698 = arith.extsi %697 : i32 to i64
%699 = llvm.getelementptr %583[%698] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%696 = llvm.load %699 : !llvm.ptr -> i64
%700 = llvm.mlir.addressof @MOD : !llvm.ptr
%701 = llvm.load %700 : !llvm.ptr -> i64
%702 = arith.remsi %696, %701 : i64
%703 = arith.constant 0 : i32
%705 = arith.extsi %703 : i32 to i64
%704 = arith.cmpi slt, %702, %705 : i64
%706 = scf.if %704 -> (i64) {
%707 = llvm.mlir.addressof @MOD : !llvm.ptr
%708 = llvm.load %707 : !llvm.ptr -> i64
%709 = arith.addi %702, %708 : i64
scf.yield %709 : i64
} else {
scf.yield %702 : i64
}
%710 = llvm.mlir.addressof @str_0 : !llvm.ptr
%711 = llvm.call @printf(%710, %706) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%583) : (!llvm.ptr) -> ()
func.call @free(%477) : (!llvm.ptr) -> ()
func.call @free(%411) : (!llvm.ptr) -> ()
%715 = arith.constant 0 : i32
func.return %715 : i32
}
}