Problem 907
S(n) satisfies an order-8 linear recurrence for n >= 10. Compute S(10^7) mod 1e9+7 via matrix exponentiation.
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 907: Stacking Cups
# S(n) satisfies an order-8 linear recurrence for n >= 10.
# Compute S(10^7) mod 1e9+7 via matrix exponentiation.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memset(dst: ptr<void>, val: i32, n: i64) -> void
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> void
}
const MOD: i64 = 1000000007
# S(1)..S(9)
function small(n: i32) -> i64 {
if n == 1 { return 2 }
if n == 2 { return 2 }
if n == 3 { return 6 }
if n == 4 { return 12 }
if n == 5 { return 16 }
if n == 6 { return 22 }
if n == 7 { return 36 }
if n == 8 { return 58 }
return 82
}
# Recurrence coefficients
function coeff(j: i32) -> i64 {
if j == 0 { return 2 }
if j == 1 { return -3 }
if j == 2 { return 5 }
if j == 3 { return -4 }
if j == 4 { return 4 }
if j == 5 { return -3 }
if j == 6 { return 1 }
return -1
}
function mat_mul(A: ptr<i64>, B: ptr<i64>, C: ptr<i64>) -> void {
let tmp: ptr<i64> = calloc(64, 8)
let mut i: i32 = 0
while i < 8 {
let mut j: i32 = 0
while j < 8 {
let mut s: i64 = 0
let mut k: i32 = 0
while k < 8 {
s = (s + A[i * 8 + k] * B[k * 8 + j]) % MOD
k = k + 1
}
tmp[i * 8 + j] = (s % MOD + MOD) % MOD
j = j + 1
}
i = i + 1
}
memcpy(C as ptr<void>, tmp as ptr<void>, 64 * 8)
free(tmp)
}
function mat_vec_mul(A: ptr<i64>, v: ptr<i64>, out: ptr<i64>) -> void {
let mut i: i32 = 0
while i < 8 {
let mut s: i64 = 0
let mut j: i32 = 0
while j < 8 {
s = (s + A[i * 8 + j] * v[j]) % MOD
j = j + 1
}
out[i] = (s % MOD + MOD) % MOD
i = i + 1
}
}
function main() -> i32 {
let n: i64 = 10000000
if n <= 9 {
printf("%lld\n", small(n as i32) % MOD)
return 0
}
let M: ptr<i64> = calloc(64, 8)
memset(M as ptr<void>, 0, 64 * 8)
let mut j: i32 = 0
while j < 8 {
M[j] = (coeff(j) % MOD + MOD) % MOD
j = j + 1
}
let mut i: i32 = 1
while i < 8 {
M[i * 8 + i - 1] = 1
i = i + 1
}
let base: ptr<i64> = calloc(8, 8)
base[0] = small(9) % MOD
base[1] = small(8) % MOD
base[2] = small(7) % MOD
base[3] = small(6) % MOD
base[4] = small(5) % MOD
base[5] = small(4) % MOD
base[6] = small(3) % MOD
base[7] = small(2) % MOD
let result: ptr<i64> = calloc(64, 8)
memset(result as ptr<void>, 0, 64 * 8)
i = 0
while i < 8 {
result[i * 8 + i] = 1
i = i + 1
}
let base_pow: ptr<i64> = calloc(64, 8)
memcpy(base_pow as ptr<void>, M as ptr<void>, 64 * 8)
let mut e: i64 = n - 9
while e > 0 {
if (e & 1) != 0 {
mat_mul(result, base_pow, result)
}
e = e >> 1
if e > 0 {
mat_mul(base_pow, base_pow, base_pow)
}
}
let out: ptr<i64> = calloc(8, 8)
mat_vec_mul(result, base, out)
printf("%lld\n", out[0])
free(M)
free(base)
free(result)
free(base_pow)
free(out)
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 small_i32(int32_t n);
int64_t coeff_i32(int32_t j);
void mat_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* A, int64_t* B, int64_t* C);
void mat_vec_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* A, int64_t* v, int64_t* out);
int32_t main(void);
static const int64_t MOD = 1000000007;
int64_t small_i32(int32_t n) {
if (n == 1) {
return 2;
}
if (n == 2) {
return 2;
}
if (n == 3) {
return 6;
}
if (n == 4) {
return 12;
}
if (n == 5) {
return 16;
}
if (n == 6) {
return 22;
}
if (n == 7) {
return 36;
}
if (n == 8) {
return 58;
}
return 82;
}
int64_t coeff_i32(int32_t j) {
if (j == 0) {
return 2;
}
if (j == 1) {
return (-3);
}
if (j == 2) {
return 5;
}
if (j == 3) {
return (-4);
}
if (j == 4) {
return 4;
}
if (j == 5) {
return (-3);
}
if (j == 6) {
return 1;
}
return (-1);
}
void mat_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* A, int64_t* B, int64_t* C) {
int64_t* tmp = (int64_t*)(calloc(64, 8));
int32_t i = 0;
while (i < 8) {
int32_t j = 0;
while (j < 8) {
int64_t s = 0;
int32_t k = 0;
while (k < 8) {
s = FLOW_CHECKED_MOD(((s + (A[((i * 8) + k)] * B[((k * 8) + j)]))), (MOD));
k = (k + 1);
}
tmp[((i * 8) + j)] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((s), (MOD)) + MOD)), (MOD));
j = (j + 1);
}
i = (i + 1);
}
memcpy(((void*)(C)), ((void*)(tmp)), (64 * 8));
free(tmp);
}
void mat_vec_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* A, int64_t* v, int64_t* out) {
int32_t i = 0;
while (i < 8) {
int64_t s = 0;
int32_t j = 0;
while (j < 8) {
s = FLOW_CHECKED_MOD(((s + (A[((i * 8) + j)] * v[j]))), (MOD));
j = (j + 1);
}
out[i] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((s), (MOD)) + MOD)), (MOD));
i = (i + 1);
}
}
int32_t main(void) {
int64_t n = 10000000;
if (n <= 9) {
printf("%lld\n", FLOW_CHECKED_MOD((small_i32(((int32_t)(n)))), (MOD)));
return 0;
}
int64_t* M = (int64_t*)(calloc(64, 8));
memset(((void*)(M)), 0, (64 * 8));
int32_t j = 0;
while (j < 8) {
M[j] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((coeff_i32(j)), (MOD)) + MOD)), (MOD));
j = (j + 1);
}
int32_t i = 1;
while (i < 8) {
M[(((i * 8) + i) - 1)] = 1;
i = (i + 1);
}
int64_t* base = (int64_t*)(calloc(8, 8));
base[0] = FLOW_CHECKED_MOD((small_i32(9)), (MOD));
base[1] = FLOW_CHECKED_MOD((small_i32(8)), (MOD));
base[2] = FLOW_CHECKED_MOD((small_i32(7)), (MOD));
base[3] = FLOW_CHECKED_MOD((small_i32(6)), (MOD));
base[4] = FLOW_CHECKED_MOD((small_i32(5)), (MOD));
base[5] = FLOW_CHECKED_MOD((small_i32(4)), (MOD));
base[6] = FLOW_CHECKED_MOD((small_i32(3)), (MOD));
base[7] = FLOW_CHECKED_MOD((small_i32(2)), (MOD));
int64_t* result = (int64_t*)(calloc(64, 8));
memset(((void*)(result)), 0, (64 * 8));
i = 0;
while (i < 8) {
result[((i * 8) + i)] = 1;
i = (i + 1);
}
int64_t* base_pow = (int64_t*)(calloc(64, 8));
memcpy(((void*)(base_pow)), ((void*)(M)), (64 * 8));
int64_t e = (n - 9);
while (e > 0) {
if ((e & 1) != 0) {
mat_mul_ptr_i64_ptr_i64_ptr_i64(result, base_pow, result);
}
e = FLOW_CHECKED_SHR((e), (1));
if (e > 0) {
mat_mul_ptr_i64_ptr_i64_ptr_i64(base_pow, base_pow, base_pow);
}
}
int64_t* out = (int64_t*)(calloc(8, 8));
mat_vec_mul_ptr_i64_ptr_i64_ptr_i64(result, base, out);
printf("%lld\n", out[0]);
free(M);
free(base);
free(result);
free(base_pow);
free(out);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @memset(!llvm.ptr, i32, i64) -> ()
func.func private @memcpy(!llvm.ptr, !llvm.ptr, i64) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
func.func @small(%arg0: i32) -> i64 {
%0 = arith.constant 1 : i32
%1 = arith.cmpi eq, %arg0, %0 : i32
cf.cond_br %1, ^bb0, ^bb1
^bb0:
%2 = arith.constant 2 : i32
%3 = arith.extsi %2 : i32 to i64
func.return %3 : i64
^bb1:
cf.br ^bb2
^bb2:
%4 = arith.constant 2 : i32
%5 = arith.cmpi eq, %arg0, %4 : i32
cf.cond_br %5, ^bb3, ^bb4
^bb3:
%6 = arith.constant 2 : i32
%7 = arith.extsi %6 : i32 to i64
func.return %7 : i64
^bb4:
cf.br ^bb5
^bb5:
%8 = arith.constant 3 : i32
%9 = arith.cmpi eq, %arg0, %8 : i32
cf.cond_br %9, ^bb6, ^bb7
^bb6:
%10 = arith.constant 6 : i32
%11 = arith.extsi %10 : i32 to i64
func.return %11 : i64
^bb7:
cf.br ^bb8
^bb8:
%12 = arith.constant 4 : i32
%13 = arith.cmpi eq, %arg0, %12 : i32
cf.cond_br %13, ^bb9, ^bb10
^bb9:
%14 = arith.constant 12 : i32
%15 = arith.extsi %14 : i32 to i64
func.return %15 : i64
^bb10:
cf.br ^bb11
^bb11:
%16 = arith.constant 5 : i32
%17 = arith.cmpi eq, %arg0, %16 : i32
cf.cond_br %17, ^bb12, ^bb13
^bb12:
%18 = arith.constant 16 : i32
%19 = arith.extsi %18 : i32 to i64
func.return %19 : i64
^bb13:
cf.br ^bb14
^bb14:
%20 = arith.constant 6 : i32
%21 = arith.cmpi eq, %arg0, %20 : i32
cf.cond_br %21, ^bb15, ^bb16
^bb15:
%22 = arith.constant 22 : i32
%23 = arith.extsi %22 : i32 to i64
func.return %23 : i64
^bb16:
cf.br ^bb17
^bb17:
%24 = arith.constant 7 : i32
%25 = arith.cmpi eq, %arg0, %24 : i32
cf.cond_br %25, ^bb18, ^bb19
^bb18:
%26 = arith.constant 36 : i32
%27 = arith.extsi %26 : i32 to i64
func.return %27 : i64
^bb19:
cf.br ^bb20
^bb20:
%28 = arith.constant 8 : i32
%29 = arith.cmpi eq, %arg0, %28 : i32
cf.cond_br %29, ^bb21, ^bb22
^bb21:
%30 = arith.constant 58 : i32
%31 = arith.extsi %30 : i32 to i64
func.return %31 : i64
^bb22:
cf.br ^bb23
^bb23:
%32 = arith.constant 82 : i32
%33 = arith.extsi %32 : i32 to i64
func.return %33 : i64
}
func.func @coeff(%arg0: i32) -> i64 {
%34 = arith.constant 0 : i32
%35 = arith.cmpi eq, %arg0, %34 : i32
cf.cond_br %35, ^bb24, ^bb25
^bb24:
%36 = arith.constant 2 : i32
%37 = arith.extsi %36 : i32 to i64
func.return %37 : i64
^bb25:
cf.br ^bb26
^bb26:
%38 = arith.constant 1 : i32
%39 = arith.cmpi eq, %arg0, %38 : i32
cf.cond_br %39, ^bb27, ^bb28
^bb27:
%40 = arith.constant 3 : i32
%42 = arith.constant 0 : i32
%41 = arith.subi %42, %40 : i32
%43 = arith.extsi %41 : i32 to i64
func.return %43 : i64
^bb28:
cf.br ^bb29
^bb29:
%44 = arith.constant 2 : i32
%45 = arith.cmpi eq, %arg0, %44 : i32
cf.cond_br %45, ^bb30, ^bb31
^bb30:
%46 = arith.constant 5 : i32
%47 = arith.extsi %46 : i32 to i64
func.return %47 : i64
^bb31:
cf.br ^bb32
^bb32:
%48 = arith.constant 3 : i32
%49 = arith.cmpi eq, %arg0, %48 : i32
cf.cond_br %49, ^bb33, ^bb34
^bb33:
%50 = arith.constant 4 : i32
%52 = arith.constant 0 : i32
%51 = arith.subi %52, %50 : i32
%53 = arith.extsi %51 : i32 to i64
func.return %53 : i64
^bb34:
cf.br ^bb35
^bb35:
%54 = arith.constant 4 : i32
%55 = arith.cmpi eq, %arg0, %54 : i32
cf.cond_br %55, ^bb36, ^bb37
^bb36:
%56 = arith.constant 4 : i32
%57 = arith.extsi %56 : i32 to i64
func.return %57 : i64
^bb37:
cf.br ^bb38
^bb38:
%58 = arith.constant 5 : i32
%59 = arith.cmpi eq, %arg0, %58 : i32
cf.cond_br %59, ^bb39, ^bb40
^bb39:
%60 = arith.constant 3 : i32
%62 = arith.constant 0 : i32
%61 = arith.subi %62, %60 : i32
%63 = arith.extsi %61 : i32 to i64
func.return %63 : i64
^bb40:
cf.br ^bb41
^bb41:
%64 = arith.constant 6 : i32
%65 = arith.cmpi eq, %arg0, %64 : i32
cf.cond_br %65, ^bb42, ^bb43
^bb42:
%66 = arith.constant 1 : i32
%67 = arith.extsi %66 : i32 to i64
func.return %67 : i64
^bb43:
cf.br ^bb44
^bb44:
%68 = arith.constant 1 : i32
%70 = arith.constant 0 : i32
%69 = arith.subi %70, %68 : i32
%71 = arith.extsi %69 : i32 to i64
func.return %71 : i64
}
func.func @mat_mul(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%73 = arith.constant 64 : i32
%74 = arith.constant 8 : i32
%75 = arith.extsi %73 : i32 to i64
%76 = arith.extsi %74 : i32 to i64
%72 = func.call @calloc(%75, %76) : (i64, i64) -> !llvm.ptr
%77 = arith.constant 0 : i32
%78 = llvm.mlir.constant(1 : i64) : i64
%79 = llvm.alloca %78 x i32 : (i64) -> !llvm.ptr
llvm.store %77, %79 : i32, !llvm.ptr
cf.br ^bb45
^bb45:
%80 = llvm.load %79 : !llvm.ptr -> i32
%81 = arith.constant 8 : i32
%82 = arith.cmpi slt, %80, %81 : i32
cf.cond_br %82, ^bb46, ^bb47
^bb46:
%83 = arith.constant 0 : i32
%84 = llvm.mlir.constant(1 : i64) : i64
%85 = llvm.alloca %84 x i32 : (i64) -> !llvm.ptr
llvm.store %83, %85 : i32, !llvm.ptr
cf.br ^bb48
^bb48:
%86 = llvm.load %85 : !llvm.ptr -> i32
%87 = arith.constant 8 : i32
%88 = arith.cmpi slt, %86, %87 : i32
cf.cond_br %88, ^bb49, ^bb50
^bb49:
%89 = arith.constant 0 : i32
%90 = arith.extsi %89 : i32 to i64
%91 = llvm.mlir.constant(1 : i64) : i64
%92 = llvm.alloca %91 x i64 : (i64) -> !llvm.ptr
llvm.store %90, %92 : i64, !llvm.ptr
%93 = arith.constant 0 : i32
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i32 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i32, !llvm.ptr
cf.br ^bb51
^bb51:
%96 = llvm.load %95 : !llvm.ptr -> i32
%97 = arith.constant 8 : i32
%98 = arith.cmpi slt, %96, %97 : i32
cf.cond_br %98, ^bb52, ^bb53
^bb52:
%99 = llvm.load %92 : !llvm.ptr -> i64
%101 = llvm.load %79 : !llvm.ptr -> i32
%102 = arith.constant 8 : i32
%103 = arith.muli %101, %102 : i32
%104 = llvm.load %95 : !llvm.ptr -> i32
%105 = arith.addi %103, %104 : i32
%106 = arith.extsi %105 : i32 to i64
%107 = llvm.getelementptr %arg0[%106] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%100 = llvm.load %107 : !llvm.ptr -> i64
%109 = llvm.load %95 : !llvm.ptr -> i32
%110 = arith.constant 8 : i32
%111 = arith.muli %109, %110 : i32
%112 = llvm.load %85 : !llvm.ptr -> i32
%113 = arith.addi %111, %112 : i32
%114 = arith.extsi %113 : i32 to i64
%115 = llvm.getelementptr %arg1[%114] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%108 = llvm.load %115 : !llvm.ptr -> i64
%116 = arith.muli %100, %108 : i64
%117 = arith.addi %99, %116 : i64
%118 = llvm.mlir.addressof @MOD : !llvm.ptr
%119 = llvm.load %118 : !llvm.ptr -> i64
%120 = arith.remsi %117, %119 : i64
llvm.store %120, %92 : i64, !llvm.ptr
%121 = llvm.load %95 : !llvm.ptr -> i32
%122 = arith.constant 1 : i32
%123 = arith.addi %121, %122 : i32
llvm.store %123, %95 : i32, !llvm.ptr
cf.br ^bb51
^bb53:
%124 = llvm.load %92 : !llvm.ptr -> i64
%125 = llvm.mlir.addressof @MOD : !llvm.ptr
%126 = llvm.load %125 : !llvm.ptr -> i64
%127 = arith.remsi %124, %126 : i64
%128 = llvm.mlir.addressof @MOD : !llvm.ptr
%129 = llvm.load %128 : !llvm.ptr -> i64
%130 = arith.addi %127, %129 : i64
%131 = llvm.mlir.addressof @MOD : !llvm.ptr
%132 = llvm.load %131 : !llvm.ptr -> i64
%133 = arith.remsi %130, %132 : i64
%134 = llvm.load %79 : !llvm.ptr -> i32
%135 = arith.constant 8 : i32
%136 = arith.muli %134, %135 : i32
%137 = llvm.load %85 : !llvm.ptr -> i32
%138 = arith.addi %136, %137 : i32
%139 = arith.extsi %138 : i32 to i64
%140 = llvm.getelementptr %72[%139] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %133, %140 : i64, !llvm.ptr
%141 = llvm.load %85 : !llvm.ptr -> i32
%142 = arith.constant 1 : i32
%143 = arith.addi %141, %142 : i32
llvm.store %143, %85 : i32, !llvm.ptr
cf.br ^bb48
^bb50:
%144 = llvm.load %79 : !llvm.ptr -> i32
%145 = arith.constant 1 : i32
%146 = arith.addi %144, %145 : i32
llvm.store %146, %79 : i32, !llvm.ptr
cf.br ^bb45
^bb47:
%148 = arith.constant 64 : i32
%149 = arith.constant 8 : i32
%150 = arith.muli %148, %149 : i32
%151 = arith.extsi %150 : i32 to i64
func.call @memcpy(%arg2, %72, %151) : (!llvm.ptr, !llvm.ptr, i64) -> ()
func.call @free(%72) : (!llvm.ptr) -> ()
func.return
}
func.func @mat_vec_mul(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%153 = arith.constant 0 : i32
%154 = llvm.mlir.constant(1 : i64) : i64
%155 = llvm.alloca %154 x i32 : (i64) -> !llvm.ptr
llvm.store %153, %155 : i32, !llvm.ptr
cf.br ^bb54
^bb54:
%156 = llvm.load %155 : !llvm.ptr -> i32
%157 = arith.constant 8 : i32
%158 = arith.cmpi slt, %156, %157 : i32
cf.cond_br %158, ^bb55, ^bb56
^bb55:
%159 = arith.constant 0 : i32
%160 = arith.extsi %159 : i32 to i64
%161 = llvm.mlir.constant(1 : i64) : i64
%162 = llvm.alloca %161 x i64 : (i64) -> !llvm.ptr
llvm.store %160, %162 : i64, !llvm.ptr
%163 = arith.constant 0 : i32
%164 = llvm.mlir.constant(1 : i64) : i64
%165 = llvm.alloca %164 x i32 : (i64) -> !llvm.ptr
llvm.store %163, %165 : i32, !llvm.ptr
cf.br ^bb57
^bb57:
%166 = llvm.load %165 : !llvm.ptr -> i32
%167 = arith.constant 8 : i32
%168 = arith.cmpi slt, %166, %167 : i32
cf.cond_br %168, ^bb58, ^bb59
^bb58:
%169 = llvm.load %162 : !llvm.ptr -> i64
%171 = llvm.load %155 : !llvm.ptr -> i32
%172 = arith.constant 8 : i32
%173 = arith.muli %171, %172 : i32
%174 = llvm.load %165 : !llvm.ptr -> i32
%175 = arith.addi %173, %174 : i32
%176 = arith.extsi %175 : i32 to i64
%177 = llvm.getelementptr %arg0[%176] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%170 = llvm.load %177 : !llvm.ptr -> i64
%179 = llvm.load %165 : !llvm.ptr -> i32
%180 = arith.extsi %179 : i32 to i64
%181 = llvm.getelementptr %arg1[%180] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%178 = llvm.load %181 : !llvm.ptr -> i64
%182 = arith.muli %170, %178 : i64
%183 = arith.addi %169, %182 : i64
%184 = llvm.mlir.addressof @MOD : !llvm.ptr
%185 = llvm.load %184 : !llvm.ptr -> i64
%186 = arith.remsi %183, %185 : i64
llvm.store %186, %162 : i64, !llvm.ptr
%187 = llvm.load %165 : !llvm.ptr -> i32
%188 = arith.constant 1 : i32
%189 = arith.addi %187, %188 : i32
llvm.store %189, %165 : i32, !llvm.ptr
cf.br ^bb57
^bb59:
%190 = llvm.load %162 : !llvm.ptr -> i64
%191 = llvm.mlir.addressof @MOD : !llvm.ptr
%192 = llvm.load %191 : !llvm.ptr -> i64
%193 = arith.remsi %190, %192 : i64
%194 = llvm.mlir.addressof @MOD : !llvm.ptr
%195 = llvm.load %194 : !llvm.ptr -> i64
%196 = arith.addi %193, %195 : i64
%197 = llvm.mlir.addressof @MOD : !llvm.ptr
%198 = llvm.load %197 : !llvm.ptr -> i64
%199 = arith.remsi %196, %198 : i64
%200 = llvm.load %155 : !llvm.ptr -> i32
%201 = arith.extsi %200 : i32 to i64
%202 = llvm.getelementptr %arg2[%201] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %199, %202 : i64, !llvm.ptr
%203 = llvm.load %155 : !llvm.ptr -> i32
%204 = arith.constant 1 : i32
%205 = arith.addi %203, %204 : i32
llvm.store %205, %155 : i32, !llvm.ptr
cf.br ^bb54
^bb56:
func.return
}
func.func @main() -> i32 {
%206 = arith.constant 10000000 : i32
%207 = arith.extsi %206 : i32 to i64
%208 = arith.constant 9 : i32
%210 = arith.extsi %208 : i32 to i64
%209 = arith.cmpi sle, %207, %210 : i64
cf.cond_br %209, ^bb60, ^bb61
^bb60:
%211 = llvm.mlir.addressof @str_0 : !llvm.ptr
%213 = arith.trunci %207 : i64 to i32
%212 = func.call @small(%213) : (i32) -> i64
%214 = llvm.mlir.addressof @MOD : !llvm.ptr
%215 = llvm.load %214 : !llvm.ptr -> i64
%216 = arith.remsi %212, %215 : i64
%217 = llvm.call @printf(%211, %216) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%218 = arith.constant 0 : i32
func.return %218 : i32
^bb61:
cf.br ^bb62
^bb62:
%220 = arith.constant 64 : i32
%221 = arith.constant 8 : i32
%222 = arith.extsi %220 : i32 to i64
%223 = arith.extsi %221 : i32 to i64
%219 = func.call @calloc(%222, %223) : (i64, i64) -> !llvm.ptr
%225 = arith.constant 0 : i32
%226 = arith.constant 64 : i32
%227 = arith.constant 8 : i32
%228 = arith.muli %226, %227 : i32
%229 = arith.extsi %228 : i32 to i64
func.call @memset(%219, %225, %229) : (!llvm.ptr, i32, i64) -> ()
%230 = arith.constant 0 : i32
%231 = llvm.mlir.constant(1 : i64) : i64
%232 = llvm.alloca %231 x i32 : (i64) -> !llvm.ptr
llvm.store %230, %232 : i32, !llvm.ptr
cf.br ^bb63
^bb63:
%233 = llvm.load %232 : !llvm.ptr -> i32
%234 = arith.constant 8 : i32
%235 = arith.cmpi slt, %233, %234 : i32
cf.cond_br %235, ^bb64, ^bb65
^bb64:
%237 = llvm.load %232 : !llvm.ptr -> i32
%236 = func.call @coeff(%237) : (i32) -> i64
%238 = llvm.mlir.addressof @MOD : !llvm.ptr
%239 = llvm.load %238 : !llvm.ptr -> i64
%240 = arith.remsi %236, %239 : i64
%241 = llvm.mlir.addressof @MOD : !llvm.ptr
%242 = llvm.load %241 : !llvm.ptr -> i64
%243 = arith.addi %240, %242 : i64
%244 = llvm.mlir.addressof @MOD : !llvm.ptr
%245 = llvm.load %244 : !llvm.ptr -> i64
%246 = arith.remsi %243, %245 : i64
%247 = llvm.load %232 : !llvm.ptr -> i32
%248 = arith.extsi %247 : i32 to i64
%249 = llvm.getelementptr %219[%248] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %246, %249 : i64, !llvm.ptr
%250 = llvm.load %232 : !llvm.ptr -> i32
%251 = arith.constant 1 : i32
%252 = arith.addi %250, %251 : i32
llvm.store %252, %232 : i32, !llvm.ptr
cf.br ^bb63
^bb65:
%253 = arith.constant 1 : i32
%254 = llvm.mlir.constant(1 : i64) : i64
%255 = llvm.alloca %254 x i32 : (i64) -> !llvm.ptr
llvm.store %253, %255 : i32, !llvm.ptr
cf.br ^bb66
^bb66:
%256 = llvm.load %255 : !llvm.ptr -> i32
%257 = arith.constant 8 : i32
%258 = arith.cmpi slt, %256, %257 : i32
cf.cond_br %258, ^bb67, ^bb68
^bb67:
%259 = arith.constant 1 : i32
%260 = llvm.load %255 : !llvm.ptr -> i32
%261 = arith.constant 8 : i32
%262 = arith.muli %260, %261 : i32
%263 = llvm.load %255 : !llvm.ptr -> i32
%264 = arith.addi %262, %263 : i32
%265 = arith.constant 1 : i32
%266 = arith.subi %264, %265 : i32
%267 = arith.extsi %259 : i32 to i64
%268 = arith.extsi %266 : i32 to i64
%269 = llvm.getelementptr %219[%268] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %267, %269 : i64, !llvm.ptr
%270 = llvm.load %255 : !llvm.ptr -> i32
%271 = arith.constant 1 : i32
%272 = arith.addi %270, %271 : i32
llvm.store %272, %255 : i32, !llvm.ptr
cf.br ^bb66
^bb68:
%274 = arith.constant 8 : i32
%275 = arith.constant 8 : i32
%276 = arith.extsi %274 : i32 to i64
%277 = arith.extsi %275 : i32 to i64
%273 = func.call @calloc(%276, %277) : (i64, i64) -> !llvm.ptr
%279 = arith.constant 9 : i32
%278 = func.call @small(%279) : (i32) -> i64
%280 = llvm.mlir.addressof @MOD : !llvm.ptr
%281 = llvm.load %280 : !llvm.ptr -> i64
%282 = arith.remsi %278, %281 : i64
%283 = arith.constant 0 : i32
%284 = arith.extsi %283 : i32 to i64
%285 = llvm.getelementptr %273[%284] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %282, %285 : i64, !llvm.ptr
%287 = arith.constant 8 : i32
%286 = func.call @small(%287) : (i32) -> i64
%288 = llvm.mlir.addressof @MOD : !llvm.ptr
%289 = llvm.load %288 : !llvm.ptr -> i64
%290 = arith.remsi %286, %289 : i64
%291 = arith.constant 1 : i32
%292 = arith.extsi %291 : i32 to i64
%293 = llvm.getelementptr %273[%292] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %290, %293 : i64, !llvm.ptr
%295 = arith.constant 7 : i32
%294 = func.call @small(%295) : (i32) -> i64
%296 = llvm.mlir.addressof @MOD : !llvm.ptr
%297 = llvm.load %296 : !llvm.ptr -> i64
%298 = arith.remsi %294, %297 : i64
%299 = arith.constant 2 : i32
%300 = arith.extsi %299 : i32 to i64
%301 = llvm.getelementptr %273[%300] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %298, %301 : i64, !llvm.ptr
%303 = arith.constant 6 : i32
%302 = func.call @small(%303) : (i32) -> i64
%304 = llvm.mlir.addressof @MOD : !llvm.ptr
%305 = llvm.load %304 : !llvm.ptr -> i64
%306 = arith.remsi %302, %305 : i64
%307 = arith.constant 3 : i32
%308 = arith.extsi %307 : i32 to i64
%309 = llvm.getelementptr %273[%308] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %306, %309 : i64, !llvm.ptr
%311 = arith.constant 5 : i32
%310 = func.call @small(%311) : (i32) -> i64
%312 = llvm.mlir.addressof @MOD : !llvm.ptr
%313 = llvm.load %312 : !llvm.ptr -> i64
%314 = arith.remsi %310, %313 : i64
%315 = arith.constant 4 : i32
%316 = arith.extsi %315 : i32 to i64
%317 = llvm.getelementptr %273[%316] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %314, %317 : i64, !llvm.ptr
%319 = arith.constant 4 : i32
%318 = func.call @small(%319) : (i32) -> i64
%320 = llvm.mlir.addressof @MOD : !llvm.ptr
%321 = llvm.load %320 : !llvm.ptr -> i64
%322 = arith.remsi %318, %321 : i64
%323 = arith.constant 5 : i32
%324 = arith.extsi %323 : i32 to i64
%325 = llvm.getelementptr %273[%324] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %322, %325 : i64, !llvm.ptr
%327 = arith.constant 3 : i32
%326 = func.call @small(%327) : (i32) -> i64
%328 = llvm.mlir.addressof @MOD : !llvm.ptr
%329 = llvm.load %328 : !llvm.ptr -> i64
%330 = arith.remsi %326, %329 : i64
%331 = arith.constant 6 : i32
%332 = arith.extsi %331 : i32 to i64
%333 = llvm.getelementptr %273[%332] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %330, %333 : i64, !llvm.ptr
%335 = arith.constant 2 : i32
%334 = func.call @small(%335) : (i32) -> i64
%336 = llvm.mlir.addressof @MOD : !llvm.ptr
%337 = llvm.load %336 : !llvm.ptr -> i64
%338 = arith.remsi %334, %337 : i64
%339 = arith.constant 7 : i32
%340 = arith.extsi %339 : i32 to i64
%341 = llvm.getelementptr %273[%340] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %338, %341 : i64, !llvm.ptr
%343 = arith.constant 64 : i32
%344 = arith.constant 8 : i32
%345 = arith.extsi %343 : i32 to i64
%346 = arith.extsi %344 : i32 to i64
%342 = func.call @calloc(%345, %346) : (i64, i64) -> !llvm.ptr
%348 = arith.constant 0 : i32
%349 = arith.constant 64 : i32
%350 = arith.constant 8 : i32
%351 = arith.muli %349, %350 : i32
%352 = arith.extsi %351 : i32 to i64
func.call @memset(%342, %348, %352) : (!llvm.ptr, i32, i64) -> ()
%353 = arith.constant 0 : i32
llvm.store %353, %255 : i32, !llvm.ptr
cf.br ^bb69
^bb69:
%354 = llvm.load %255 : !llvm.ptr -> i32
%355 = arith.constant 8 : i32
%356 = arith.cmpi slt, %354, %355 : i32
cf.cond_br %356, ^bb70, ^bb71
^bb70:
%357 = arith.constant 1 : i32
%358 = llvm.load %255 : !llvm.ptr -> i32
%359 = arith.constant 8 : i32
%360 = arith.muli %358, %359 : i32
%361 = llvm.load %255 : !llvm.ptr -> i32
%362 = arith.addi %360, %361 : i32
%363 = arith.extsi %357 : i32 to i64
%364 = arith.extsi %362 : i32 to i64
%365 = llvm.getelementptr %342[%364] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %363, %365 : i64, !llvm.ptr
%366 = llvm.load %255 : !llvm.ptr -> i32
%367 = arith.constant 1 : i32
%368 = arith.addi %366, %367 : i32
llvm.store %368, %255 : i32, !llvm.ptr
cf.br ^bb69
^bb71:
%370 = arith.constant 64 : i32
%371 = arith.constant 8 : i32
%372 = arith.extsi %370 : i32 to i64
%373 = arith.extsi %371 : i32 to i64
%369 = func.call @calloc(%372, %373) : (i64, i64) -> !llvm.ptr
%375 = arith.constant 64 : i32
%376 = arith.constant 8 : i32
%377 = arith.muli %375, %376 : i32
%378 = arith.extsi %377 : i32 to i64
func.call @memcpy(%369, %219, %378) : (!llvm.ptr, !llvm.ptr, i64) -> ()
%379 = arith.constant 9 : i32
%381 = arith.extsi %379 : i32 to i64
%380 = arith.subi %207, %381 : i64
%382 = llvm.mlir.constant(1 : i64) : i64
%383 = llvm.alloca %382 x i64 : (i64) -> !llvm.ptr
llvm.store %380, %383 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%384 = llvm.load %383 : !llvm.ptr -> i64
%385 = arith.constant 0 : i32
%387 = arith.extsi %385 : i32 to i64
%386 = arith.cmpi sgt, %384, %387 : i64
cf.cond_br %386, ^bb73, ^bb74
^bb73:
%388 = llvm.load %383 : !llvm.ptr -> i64
%389 = arith.constant 1 : i32
%391 = arith.extsi %389 : i32 to i64
%390 = arith.andi %388, %391 : i64
%392 = arith.constant 0 : i32
%394 = arith.extsi %392 : i32 to i64
%393 = arith.cmpi ne, %390, %394 : i64
cf.cond_br %393, ^bb75, ^bb76
^bb75:
func.call @mat_mul(%342, %369, %342) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
cf.br ^bb77
^bb76:
cf.br ^bb77
^bb77:
%396 = llvm.load %383 : !llvm.ptr -> i64
%397 = arith.constant 1 : i32
%399 = arith.extsi %397 : i32 to i64
%398 = arith.shrsi %396, %399 : i64
llvm.store %398, %383 : i64, !llvm.ptr
%400 = llvm.load %383 : !llvm.ptr -> i64
%401 = arith.constant 0 : i32
%403 = arith.extsi %401 : i32 to i64
%402 = arith.cmpi sgt, %400, %403 : i64
cf.cond_br %402, ^bb78, ^bb79
^bb78:
func.call @mat_mul(%369, %369, %369) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
cf.br ^bb72
^bb74:
%406 = arith.constant 8 : i32
%407 = arith.constant 8 : i32
%408 = arith.extsi %406 : i32 to i64
%409 = arith.extsi %407 : i32 to i64
%405 = func.call @calloc(%408, %409) : (i64, i64) -> !llvm.ptr
func.call @mat_vec_mul(%342, %273, %405) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%411 = llvm.mlir.addressof @str_0 : !llvm.ptr
%413 = arith.constant 0 : i32
%414 = arith.extsi %413 : i32 to i64
%415 = llvm.getelementptr %405[%414] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%412 = llvm.load %415 : !llvm.ptr -> i64
%416 = llvm.call @printf(%411, %412) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%219) : (!llvm.ptr) -> ()
func.call @free(%273) : (!llvm.ptr) -> ()
func.call @free(%342) : (!llvm.ptr) -> ()
func.call @free(%369) : (!llvm.ptr) -> ()
func.call @free(%405) : (!llvm.ptr) -> ()
%422 = arith.constant 0 : i32
func.return %422 : i32
}
}