← All problems Problem 867
Tiling Dodecagon - T(10) mod 1e9+7.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^3)O(n * s)Space complexity O(n^2)O(s)Approach Flow solution Tiling DP with state Verdict Unknown
Flow source
# Project Euler 867
# Tiling Dodecagon - T(10) mod 1e9+7.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
}
const MOD: i64 = 1000000007
const MAX_L: i64 = 19
const ROWCAP: i64 = 32768
let mut indep_count: ptr<i64> = null
let mut indep_lists: ptr<i64> = null
let mut R_cache: ptr<i64> = null
let mut R_computed: ptr<i32> = null
function modpow(base0: i64, exp0: i64, mod0: i64) -> i64 {
let mut r: i64 = 1
let mut base: i64 = base0 % mod0
let mut exp: i64 = exp0
while exp > 0 {
if (exp & 1) != 0 {
r = ((r as i128) * (base as i128) % (mod0 as i128)) as i64
}
base = ((base as i128) * (base as i128) % (mod0 as i128)) as i64
exp = exp >> 1
}
return r
}
function init_indep() -> void {
indep_count = calloc(MAX_L + 1, 8)
indep_lists = calloc((MAX_L + 1) * ROWCAP, 8)
let mut L: i64 = 0
while L <= MAX_L {
let mut cnt: i64 = 0
let mut m: i64 = 0
let limit: i64 = 1 << L
while m < limit {
if (m & (m << 1)) == 0 {
indep_lists[L * ROWCAP + cnt] = m
cnt = cnt + 1
}
m = m + 1
}
indep_count[L] = cnt
L = L + 1
}
}
function subset_sums(out: ptr<i64>, values: ptr<i64>, L: i64) -> void {
let size: i64 = 1 << L
memcpy(out, values, size * 8)
let mut i: i64 = 0
while i < L {
let step: i64 = 1 << i
let block: i64 = step << 1
let mut start: i64 = 0
while start < size {
let mid: i64 = start + step
let end: i64 = start + block
let mut m: i64 = mid
while m < end {
let s: i64 = out[m] + out[m - step]
if s >= MOD {
out[m] = s - MOD
} else {
out[m] = s
}
m = m + 1
}
start = start + block
}
i = i + 1
}
}
function count_independent_sets(row_lengths: ptr<i32>, nrows: i64) -> i64 {
if nrows == 0 {
return 1
}
let L0: i64 = row_lengths[0] as i64
let size0: i64 = 1 << L0
let mut dp: ptr<i64> = calloc(size0, 8)
let mut c: i64 = 0
while c < indep_count[L0] {
dp[indep_lists[L0 * ROWCAP + c]] = 1
c = c + 1
}
let mut i: i64 = 1
while i < nrows {
let Lc: i64 = row_lengths[i - 1] as i64
let Ln: i64 = row_lengths[i] as i64
let size_c: i64 = 1 << Lc
let size_n: i64 = 1 << Ln
let subs: ptr<i64> = calloc(size_c, 8)
subset_sums(subs, dp, Lc)
let dp2: ptr<i64> = calloc(size_n, 8)
let fullmask: i64 = size_c - 1
if Ln == Lc + 1 {
let mut c2: i64 = 0
while c2 < indep_count[Ln] {
let b: i64 = indep_lists[Ln * ROWCAP + c2]
let forb: i64 = (b | (b >> 1)) & fullmask
let allowed: i64 = fullmask ^ forb
dp2[b] = subs[allowed]
c2 = c2 + 1
}
} else {
let mut c2: i64 = 0
while c2 < indep_count[Ln] {
let b: i64 = indep_lists[Ln * ROWCAP + c2]
let forb: i64 = (b | (b << 1)) & fullmask
let allowed: i64 = fullmask ^ forb
dp2[b] = subs[allowed]
c2 = c2 + 1
}
}
free(subs)
free(dp)
dp = dp2
i = i + 1
}
let last_L: i64 = row_lengths[nrows - 1] as i64
let mut total: i64 = 0
let mut c3: i64 = 0
while c3 < indep_count[last_L] {
total = total + dp[indep_lists[last_L * ROWCAP + c3]]
if total >= MOD {
total = total - MOD
}
c3 = c3 + 1
}
free(dp)
return total % MOD
}
function H(n: i64) -> i64 {
let rows: ptr<i32> = calloc(64, 4)
let mut ni: i64 = 0
let mut i: i64 = n
while i < 2 * n {
rows[ni] = i as i32
ni = ni + 1
i = i + 1
}
let mut nd: i64 = 0
i = 2 * n - 2
while i >= n {
rows[ni + nd] = i as i32
nd = nd + 1
i = i - 1
}
let ans: i64 = count_independent_sets(rows, ni + nd)
free(rows)
return ans
}
function F(n: i64, h: i64) -> i64 {
let nrows: i64 = h - 1
if nrows <= 0 {
return 1
}
let lengths: ptr<i32> = calloc(64, 4)
let mut i: i64 = 0
while i < nrows {
let v: i64 = (n - 2) - i
if v > 0 {
lengths[i] = v as i32
} else {
lengths[i] = 0
}
i = i + 1
}
let mut eff_rows: i64 = nrows
i = 0
while i < nrows {
if lengths[i] == 0 {
eff_rows = i
break
}
i = i + 1
}
let ans: i64 = count_independent_sets(lengths, eff_rows)
free(lengths)
return ans
}
function R(u: i64, v: i64) -> i64 {
if v == 0 {
return H(u)
}
if R_computed[u * 16 + v] != 0 {
return R_cache[u * 16 + v]
}
let mut res: i64 = 0
if u == 1 && v == 1 {
res = 1
}
let mut w: i64 = 0
while w < u {
let corner: i64 = F(u, u - w)
let r_vw: i64 = R(v, w)
let c6: i64 = modpow(corner, 6, MOD)
res = (res + ((r_vw as i128) * (c6 as i128) % (MOD as i128)) as i64) % MOD
w = w + 1
}
R_computed[u * 16 + v] = 1
R_cache[u * 16 + v] = res
return res
}
function T(n: i64) -> i64 {
let mut ans: i64 = (2 * R(n, n)) % MOD
if n == 1 {
ans = ans - 1
}
if ans < 0 {
ans = ans + MOD
}
return ans
}
function main() -> i32 {
R_cache = calloc(16 * 16, 8)
R_computed = calloc(16 * 16, 4)
init_indep()
printf("%lld\n", T(10))
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod0);
void init_indep(void);
void subset_sums_ptr_i64_ptr_i64_i64(int64_t* out, int64_t* values, int64_t L);
int64_t count_independent_sets_ptr_i32_i64(int32_t* row_lengths, int64_t nrows);
int64_t H_i64(int64_t n);
int64_t F_i64_i64(int64_t n, int64_t h);
int64_t R_i64_i64(int64_t u, int64_t v);
int64_t T_i64(int64_t n);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int64_t MAX_L = 19;
static const int64_t ROWCAP = 32768;
/* Module statics */
static int64_t* indep_count = NULL;
static int64_t* indep_lists = NULL;
static int64_t* R_cache = NULL;
static int32_t* R_computed = NULL;
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod0) {
int64_t r = 1;
int64_t base = FLOW_CHECKED_MOD((base0), (mod0));
int64_t exp = exp0;
while (exp > 0) {
if ((exp & 1) != 0) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(base)))), (((__int128)(mod0))))));
}
base = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(base)) * ((__int128)(base)))), (((__int128)(mod0))))));
exp = FLOW_CHECKED_SHR((exp), (1));
}
return r;
}
void init_indep(void) {
indep_count = calloc((MAX_L + 1), 8);
indep_lists = calloc(((MAX_L + 1) * ROWCAP), 8);
int64_t L = 0;
while (L <= MAX_L) {
int64_t cnt = 0;
int64_t m = 0;
int64_t limit = FLOW_CHECKED_SHL((1), (L));
while (m < limit) {
if ((m & FLOW_CHECKED_SHL((m), (1))) == 0) {
indep_lists[((L * ROWCAP) + cnt)] = m;
cnt = (cnt + 1);
}
m = (m + 1);
}
indep_count[L] = cnt;
L = (L + 1);
}
}
void subset_sums_ptr_i64_ptr_i64_i64(int64_t* out, int64_t* values, int64_t L) {
int64_t size = FLOW_CHECKED_SHL((1), (L));
memcpy(out, values, (size * 8));
int64_t i = 0;
while (i < L) {
int64_t step = FLOW_CHECKED_SHL((1), (i));
int64_t block = FLOW_CHECKED_SHL((step), (1));
int64_t start = 0;
while (start < size) {
int64_t mid = (start + step);
int64_t end = (start + block);
int64_t m = mid;
while (m < end) {
int64_t s = (out[m] + out[(m - step)]);
if (s >= MOD) {
out[m] = (s - MOD);
} else {
out[m] = s;
}
m = (m + 1);
}
start = (start + block);
}
i = (i + 1);
}
}
int64_t count_independent_sets_ptr_i32_i64(int32_t* row_lengths, int64_t nrows) {
if (nrows == 0) {
return 1;
}
int64_t L0 = ((int64_t)(row_lengths[0]));
int64_t size0 = FLOW_CHECKED_SHL((1), (L0));
int64_t* dp = (int64_t*)(calloc(size0, 8));
int64_t c = 0;
while (c < indep_count[L0]) {
dp[indep_lists[((L0 * ROWCAP) + c)]] = 1;
c = (c + 1);
}
int64_t i = 1;
while (i < nrows) {
int64_t Lc = ((int64_t)(row_lengths[(i - 1)]));
int64_t Ln = ((int64_t)(row_lengths[i]));
int64_t size_c = FLOW_CHECKED_SHL((1), (Lc));
int64_t size_n = FLOW_CHECKED_SHL((1), (Ln));
int64_t* subs = (int64_t*)(calloc(size_c, 8));
subset_sums_ptr_i64_ptr_i64_i64(subs, dp, Lc);
int64_t* dp2 = (int64_t*)(calloc(size_n, 8));
int64_t fullmask = (size_c - 1);
if (Ln == (Lc + 1)) {
int64_t c2 = 0;
while (c2 < indep_count[Ln]) {
int64_t b = indep_lists[((Ln * ROWCAP) + c2)];
int64_t forb = ((b | FLOW_CHECKED_SHR((b), (1))) & fullmask);
int64_t allowed = (fullmask ^ forb);
dp2[b] = subs[allowed];
c2 = (c2 + 1);
}
} else {
int64_t c2 = 0;
while (c2 < indep_count[Ln]) {
int64_t b = indep_lists[((Ln * ROWCAP) + c2)];
int64_t forb = ((b | FLOW_CHECKED_SHL((b), (1))) & fullmask);
int64_t allowed = (fullmask ^ forb);
dp2[b] = subs[allowed];
c2 = (c2 + 1);
}
}
free(subs);
free(dp);
dp = dp2;
i = (i + 1);
}
int64_t last_L = ((int64_t)(row_lengths[(nrows - 1)]));
int64_t total = 0;
int64_t c3 = 0;
while (c3 < indep_count[last_L]) {
total = (total + dp[indep_lists[((last_L * ROWCAP) + c3)]]);
if (total >= MOD) {
total = (total - MOD);
}
c3 = (c3 + 1);
}
free(dp);
return FLOW_CHECKED_MOD((total), (MOD));
}
int64_t H_i64(int64_t n) {
int32_t* rows = (int32_t*)(calloc(64, 4));
int64_t ni = 0;
int64_t i = n;
while (i < (2 * n)) {
rows[ni] = ((int32_t)(i));
ni = (ni + 1);
i = (i + 1);
}
int64_t nd = 0;
i = ((2 * n) - 2);
while (i >= n) {
rows[(ni + nd)] = ((int32_t)(i));
nd = (nd + 1);
i = (i - 1);
}
int64_t ans = count_independent_sets_ptr_i32_i64(rows, (ni + nd));
free(rows);
return ans;
}
int64_t F_i64_i64(int64_t n, int64_t h) {
int64_t nrows = (h - 1);
if (nrows <= 0) {
return 1;
}
int32_t* lengths = (int32_t*)(calloc(64, 4));
int64_t i = 0;
while (i < nrows) {
int64_t v = ((n - 2) - i);
if (v > 0) {
lengths[i] = ((int32_t)(v));
} else {
lengths[i] = 0;
}
i = (i + 1);
}
int64_t eff_rows = nrows;
i = 0;
while (i < nrows) {
if (lengths[i] == 0) {
eff_rows = i;
break;
}
i = (i + 1);
}
int64_t ans = count_independent_sets_ptr_i32_i64(lengths, eff_rows);
free(lengths);
return ans;
}
int64_t R_i64_i64(int64_t u, int64_t v) {
if (v == 0) {
return H_i64(u);
}
if (R_computed[((u * 16) + v)] != 0) {
return R_cache[((u * 16) + v)];
}
int64_t res = 0;
if ((u == 1 && v == 1)) {
res = 1;
}
int64_t w = 0;
while (w < u) {
int64_t corner = F_i64_i64(u, (u - w));
int64_t r_vw = R_i64_i64(v, w);
int64_t c6 = modpow_i64_i64_i64(corner, 6, MOD);
res = FLOW_CHECKED_MOD(((res + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r_vw)) * ((__int128)(c6)))), (((__int128)(MOD)))))))), (MOD));
w = (w + 1);
}
R_computed[((u * 16) + v)] = 1;
R_cache[((u * 16) + v)] = res;
return res;
}
int64_t T_i64(int64_t n) {
int64_t ans = FLOW_CHECKED_MOD(((2 * R_i64_i64(n, n))), (MOD));
if (n == 1) {
ans = (ans - 1);
}
if (ans < 0) {
ans = (ans + MOD);
}
return ans;
}
int32_t main(void) {
R_cache = calloc((16 * 16), 8);
R_computed = calloc((16 * 16), 4);
init_indep();
printf("%lld\n", T_i64(10));
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 @memcpy(!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
// Constant: MAX_L
llvm.mlir.global internal constant @MAX_L(19 : i64) : i64
// Constant: ROWCAP
llvm.mlir.global internal constant @ROWCAP(32768 : i64) : i64
// Module static: indep_count
llvm.mlir.global internal @indep_count() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: indep_lists
llvm.mlir.global internal @indep_lists() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
// Module static: R_cache
llvm.mlir.global internal @R_cache() {addr_space = 0 : i32} : !llvm.ptr {
%2 = llvm.mlir.zero : !llvm.ptr
llvm.return %2 : !llvm.ptr
}
// Module static: R_computed
llvm.mlir.global internal @R_computed() {addr_space = 0 : i32} : !llvm.ptr {
%3 = llvm.mlir.zero : !llvm.ptr
llvm.return %3 : !llvm.ptr
}
func.func @modpow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%4 = arith.constant 1 : i32
%5 = arith.extsi %4 : i32 to i64
%6 = llvm.mlir.constant(1 : i64) : i64
%7 = llvm.alloca %6 x i64 : (i64) -> !llvm.ptr
llvm.store %5, %7 : i64, !llvm.ptr
%8 = arith.remsi %arg0, %arg2 : i64
%9 = llvm.mlir.constant(1 : i64) : i64
%10 = llvm.alloca %9 x i64 : (i64) -> !llvm.ptr
llvm.store %8, %10 : i64, !llvm.ptr
%11 = llvm.mlir.constant(1 : i64) : i64
%12 = llvm.alloca %11 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %12 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%13 = llvm.load %12 : !llvm.ptr -> i64
%14 = arith.constant 0 : i32
%16 = arith.extsi %14 : i32 to i64
%15 = arith.cmpi sgt, %13, %16 : i64
cf.cond_br %15, ^bb1, ^bb2
^bb1:
%17 = llvm.load %12 : !llvm.ptr -> i64
%18 = arith.constant 1 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.andi %17, %20 : i64
%21 = arith.constant 0 : i32
%23 = arith.extsi %21 : i32 to i64
%22 = arith.cmpi ne, %19, %23 : i64
cf.cond_br %22, ^bb3, ^bb4
^bb3:
%24 = llvm.load %7 : !llvm.ptr -> i64
%25 = arith.extsi %24 : i64 to i128
%26 = llvm.load %10 : !llvm.ptr -> i64
%27 = arith.extsi %26 : i64 to i128
%29 = arith.trunci %25 : i128 to i64
%30 = arith.trunci %27 : i128 to i64
%28 = arith.muli %29, %30 : i64
%31 = arith.extsi %arg2 : i64 to i128
%33 = arith.trunci %31 : i128 to i64
%32 = arith.remsi %28, %33 : i64
llvm.store %32, %7 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%34 = llvm.load %10 : !llvm.ptr -> i64
%35 = arith.extsi %34 : i64 to i128
%36 = llvm.load %10 : !llvm.ptr -> i64
%37 = arith.extsi %36 : i64 to i128
%39 = arith.trunci %35 : i128 to i64
%40 = arith.trunci %37 : i128 to i64
%38 = arith.muli %39, %40 : i64
%41 = arith.extsi %arg2 : i64 to i128
%43 = arith.trunci %41 : i128 to i64
%42 = arith.remsi %38, %43 : i64
llvm.store %42, %10 : i64, !llvm.ptr
%44 = llvm.load %12 : !llvm.ptr -> i64
%45 = arith.constant 1 : i32
%47 = arith.extsi %45 : i32 to i64
%46 = arith.shrsi %44, %47 : i64
llvm.store %46, %12 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%48 = llvm.load %7 : !llvm.ptr -> i64
func.return %48 : i64
}
func.func @init_indep() -> () {
%50 = llvm.mlir.addressof @MAX_L : !llvm.ptr
%51 = llvm.load %50 : !llvm.ptr -> i64
%52 = arith.constant 1 : i32
%54 = arith.extsi %52 : i32 to i64
%53 = arith.addi %51, %54 : i64
%55 = arith.constant 8 : i32
%56 = arith.extsi %55 : i32 to i64
%49 = func.call @calloc(%53, %56) : (i64, i64) -> !llvm.ptr
%57 = llvm.mlir.addressof @indep_count : !llvm.ptr
llvm.store %49, %57 : !llvm.ptr, !llvm.ptr
%59 = llvm.mlir.addressof @MAX_L : !llvm.ptr
%60 = llvm.load %59 : !llvm.ptr -> i64
%61 = arith.constant 1 : i32
%63 = arith.extsi %61 : i32 to i64
%62 = arith.addi %60, %63 : i64
%64 = llvm.mlir.addressof @ROWCAP : !llvm.ptr
%65 = llvm.load %64 : !llvm.ptr -> i64
%66 = arith.muli %62, %65 : i64
%67 = arith.constant 8 : i32
%68 = arith.extsi %67 : i32 to i64
%58 = func.call @calloc(%66, %68) : (i64, i64) -> !llvm.ptr
%69 = llvm.mlir.addressof @indep_lists : !llvm.ptr
llvm.store %58, %69 : !llvm.ptr, !llvm.ptr
%70 = arith.constant 0 : i32
%71 = arith.extsi %70 : i32 to i64
%72 = llvm.mlir.constant(1 : i64) : i64
%73 = llvm.alloca %72 x i64 : (i64) -> !llvm.ptr
llvm.store %71, %73 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%74 = llvm.load %73 : !llvm.ptr -> i64
%75 = llvm.mlir.addressof @MAX_L : !llvm.ptr
%76 = llvm.load %75 : !llvm.ptr -> i64
%77 = arith.cmpi sle, %74, %76 : i64
cf.cond_br %77, ^bb7, ^bb8
^bb7:
%78 = arith.constant 0 : i32
%79 = arith.extsi %78 : i32 to i64
%80 = llvm.mlir.constant(1 : i64) : i64
%81 = llvm.alloca %80 x i64 : (i64) -> !llvm.ptr
llvm.store %79, %81 : i64, !llvm.ptr
%82 = arith.constant 0 : i32
%83 = arith.extsi %82 : i32 to i64
%84 = llvm.mlir.constant(1 : i64) : i64
%85 = llvm.alloca %84 x i64 : (i64) -> !llvm.ptr
llvm.store %83, %85 : i64, !llvm.ptr
%86 = arith.constant 1 : i32
%87 = llvm.load %73 : !llvm.ptr -> i64
%89 = arith.extsi %86 : i32 to i64
%88 = arith.shli %89, %87 : i64
cf.br ^bb9
^bb9:
%90 = llvm.load %85 : !llvm.ptr -> i64
%91 = arith.cmpi slt, %90, %88 : i64
cf.cond_br %91, ^bb10, ^bb11
^bb10:
%92 = llvm.load %85 : !llvm.ptr -> i64
%93 = llvm.load %85 : !llvm.ptr -> i64
%94 = arith.constant 1 : i32
%96 = arith.extsi %94 : i32 to i64
%95 = arith.shli %93, %96 : i64
%97 = arith.andi %92, %95 : i64
%98 = arith.constant 0 : i32
%100 = arith.extsi %98 : i32 to i64
%99 = arith.cmpi eq, %97, %100 : i64
cf.cond_br %99, ^bb12, ^bb13
^bb12:
%101 = llvm.load %85 : !llvm.ptr -> i64
%102 = llvm.mlir.addressof @indep_lists : !llvm.ptr
%103 = llvm.load %102 : !llvm.ptr -> !llvm.ptr
%104 = llvm.load %73 : !llvm.ptr -> i64
%105 = llvm.mlir.addressof @ROWCAP : !llvm.ptr
%106 = llvm.load %105 : !llvm.ptr -> i64
%107 = arith.muli %104, %106 : i64
%108 = llvm.load %81 : !llvm.ptr -> i64
%109 = arith.addi %107, %108 : i64
%110 = llvm.getelementptr %103[%109] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %101, %110 : i64, !llvm.ptr
%111 = llvm.load %81 : !llvm.ptr -> i64
%112 = arith.constant 1 : i32
%114 = arith.extsi %112 : i32 to i64
%113 = arith.addi %111, %114 : i64
llvm.store %113, %81 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%115 = llvm.load %85 : !llvm.ptr -> i64
%116 = arith.constant 1 : i32
%118 = arith.extsi %116 : i32 to i64
%117 = arith.addi %115, %118 : i64
llvm.store %117, %85 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%119 = llvm.load %81 : !llvm.ptr -> i64
%120 = llvm.mlir.addressof @indep_count : !llvm.ptr
%121 = llvm.load %120 : !llvm.ptr -> !llvm.ptr
%122 = llvm.load %73 : !llvm.ptr -> i64
%123 = llvm.getelementptr %121[%122] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %119, %123 : i64, !llvm.ptr
%124 = llvm.load %73 : !llvm.ptr -> i64
%125 = arith.constant 1 : i32
%127 = arith.extsi %125 : i32 to i64
%126 = arith.addi %124, %127 : i64
llvm.store %126, %73 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
func.return
}
func.func @subset_sums(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i64) -> () {
%128 = arith.constant 1 : i32
%130 = arith.extsi %128 : i32 to i64
%129 = arith.shli %130, %arg2 : i64
%132 = arith.constant 8 : i32
%134 = arith.extsi %132 : i32 to i64
%133 = arith.muli %129, %134 : i64
%131 = func.call @memcpy(%arg0, %arg1, %133) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
%135 = arith.constant 0 : i32
%136 = arith.extsi %135 : i32 to i64
%137 = llvm.mlir.constant(1 : i64) : i64
%138 = llvm.alloca %137 x i64 : (i64) -> !llvm.ptr
llvm.store %136, %138 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%139 = llvm.load %138 : !llvm.ptr -> i64
%140 = arith.cmpi slt, %139, %arg2 : i64
cf.cond_br %140, ^bb16, ^bb17
^bb16:
%141 = arith.constant 1 : i32
%142 = llvm.load %138 : !llvm.ptr -> i64
%144 = arith.extsi %141 : i32 to i64
%143 = arith.shli %144, %142 : i64
%145 = arith.constant 1 : i32
%147 = arith.extsi %145 : i32 to i64
%146 = arith.shli %143, %147 : i64
%148 = arith.constant 0 : i32
%149 = arith.extsi %148 : i32 to i64
%150 = llvm.mlir.constant(1 : i64) : i64
%151 = llvm.alloca %150 x i64 : (i64) -> !llvm.ptr
llvm.store %149, %151 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%152 = llvm.load %151 : !llvm.ptr -> i64
%153 = arith.cmpi slt, %152, %129 : i64
cf.cond_br %153, ^bb19, ^bb20
^bb19:
%154 = llvm.load %151 : !llvm.ptr -> i64
%155 = arith.addi %154, %143 : i64
%156 = llvm.load %151 : !llvm.ptr -> i64
%157 = arith.addi %156, %146 : i64
%158 = llvm.mlir.constant(1 : i64) : i64
%159 = llvm.alloca %158 x i64 : (i64) -> !llvm.ptr
llvm.store %155, %159 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%160 = llvm.load %159 : !llvm.ptr -> i64
%161 = arith.cmpi slt, %160, %157 : i64
cf.cond_br %161, ^bb22, ^bb23
^bb22:
%163 = llvm.load %159 : !llvm.ptr -> i64
%164 = llvm.getelementptr %arg0[%163] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%162 = llvm.load %164 : !llvm.ptr -> i64
%166 = llvm.load %159 : !llvm.ptr -> i64
%167 = arith.subi %166, %143 : i64
%168 = llvm.getelementptr %arg0[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%165 = llvm.load %168 : !llvm.ptr -> i64
%169 = arith.addi %162, %165 : i64
%170 = llvm.mlir.addressof @MOD : !llvm.ptr
%171 = llvm.load %170 : !llvm.ptr -> i64
%172 = arith.cmpi sge, %169, %171 : i64
cf.cond_br %172, ^bb24, ^bb25
^bb24:
%173 = llvm.mlir.addressof @MOD : !llvm.ptr
%174 = llvm.load %173 : !llvm.ptr -> i64
%175 = arith.subi %169, %174 : i64
%176 = llvm.load %159 : !llvm.ptr -> i64
%177 = llvm.getelementptr %arg0[%176] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %175, %177 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
%178 = llvm.load %159 : !llvm.ptr -> i64
%179 = llvm.getelementptr %arg0[%178] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %169, %179 : i64, !llvm.ptr
cf.br ^bb26
^bb26:
%180 = llvm.load %159 : !llvm.ptr -> i64
%181 = arith.constant 1 : i32
%183 = arith.extsi %181 : i32 to i64
%182 = arith.addi %180, %183 : i64
llvm.store %182, %159 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%184 = llvm.load %151 : !llvm.ptr -> i64
%185 = arith.addi %184, %146 : i64
llvm.store %185, %151 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%186 = llvm.load %138 : !llvm.ptr -> i64
%187 = arith.constant 1 : i32
%189 = arith.extsi %187 : i32 to i64
%188 = arith.addi %186, %189 : i64
llvm.store %188, %138 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
func.return
}
func.func @count_independent_sets(%arg0: !llvm.ptr, %arg1: i64) -> i64 {
%190 = arith.constant 0 : i32
%192 = arith.extsi %190 : i32 to i64
%191 = arith.cmpi eq, %arg1, %192 : i64
cf.cond_br %191, ^bb27, ^bb28
^bb27:
%193 = arith.constant 1 : i32
%194 = arith.extsi %193 : i32 to i64
func.return %194 : i64
^bb28:
cf.br ^bb29
^bb29:
%196 = arith.constant 0 : i32
%197 = arith.extsi %196 : i32 to i64
%198 = llvm.getelementptr %arg0[%197] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%195 = llvm.load %198 : !llvm.ptr -> i32
%199 = arith.extsi %195 : i32 to i64
%200 = arith.constant 1 : i32
%202 = arith.extsi %200 : i32 to i64
%201 = arith.shli %202, %199 : i64
%204 = arith.constant 8 : i32
%205 = arith.extsi %204 : i32 to i64
%203 = func.call @calloc(%201, %205) : (i64, i64) -> !llvm.ptr
%206 = llvm.mlir.constant(1 : i64) : i64
%207 = llvm.alloca %206 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %203, %207 : !llvm.ptr, !llvm.ptr
%208 = arith.constant 0 : i32
%209 = arith.extsi %208 : i32 to i64
%210 = llvm.mlir.constant(1 : i64) : i64
%211 = llvm.alloca %210 x i64 : (i64) -> !llvm.ptr
llvm.store %209, %211 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%212 = llvm.load %211 : !llvm.ptr -> i64
%214 = llvm.mlir.addressof @indep_count : !llvm.ptr
%215 = llvm.load %214 : !llvm.ptr -> !llvm.ptr
%216 = llvm.getelementptr %215[%199] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%213 = llvm.load %216 : !llvm.ptr -> i64
%217 = arith.cmpi slt, %212, %213 : i64
cf.cond_br %217, ^bb31, ^bb32
^bb31:
%218 = arith.constant 1 : i32
%219 = llvm.load %207 : !llvm.ptr -> !llvm.ptr
%221 = llvm.mlir.addressof @indep_lists : !llvm.ptr
%222 = llvm.load %221 : !llvm.ptr -> !llvm.ptr
%223 = llvm.mlir.addressof @ROWCAP : !llvm.ptr
%224 = llvm.load %223 : !llvm.ptr -> i64
%225 = arith.muli %199, %224 : i64
%226 = llvm.load %211 : !llvm.ptr -> i64
%227 = arith.addi %225, %226 : i64
%228 = llvm.getelementptr %222[%227] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%220 = llvm.load %228 : !llvm.ptr -> i64
%229 = arith.extsi %218 : i32 to i64
%230 = llvm.getelementptr %219[%220] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %229, %230 : i64, !llvm.ptr
%231 = llvm.load %211 : !llvm.ptr -> i64
%232 = arith.constant 1 : i32
%234 = arith.extsi %232 : i32 to i64
%233 = arith.addi %231, %234 : i64
llvm.store %233, %211 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%235 = arith.constant 1 : i32
%236 = arith.extsi %235 : i32 to i64
%237 = llvm.mlir.constant(1 : i64) : i64
%238 = llvm.alloca %237 x i64 : (i64) -> !llvm.ptr
llvm.store %236, %238 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%239 = llvm.load %238 : !llvm.ptr -> i64
%240 = arith.cmpi slt, %239, %arg1 : i64
cf.cond_br %240, ^bb34, ^bb35
^bb34:
%242 = llvm.load %238 : !llvm.ptr -> i64
%243 = arith.constant 1 : i32
%245 = arith.extsi %243 : i32 to i64
%244 = arith.subi %242, %245 : i64
%246 = llvm.getelementptr %arg0[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%241 = llvm.load %246 : !llvm.ptr -> i32
%247 = arith.extsi %241 : i32 to i64
%249 = llvm.load %238 : !llvm.ptr -> i64
%250 = llvm.getelementptr %arg0[%249] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%248 = llvm.load %250 : !llvm.ptr -> i32
%251 = arith.extsi %248 : i32 to i64
%252 = arith.constant 1 : i32
%254 = arith.extsi %252 : i32 to i64
%253 = arith.shli %254, %247 : i64
%255 = arith.constant 1 : i32
%257 = arith.extsi %255 : i32 to i64
%256 = arith.shli %257, %251 : i64
%259 = arith.constant 8 : i32
%260 = arith.extsi %259 : i32 to i64
%258 = func.call @calloc(%253, %260) : (i64, i64) -> !llvm.ptr
%262 = llvm.load %207 : !llvm.ptr -> !llvm.ptr
func.call @subset_sums(%258, %262, %247) : (!llvm.ptr, !llvm.ptr, i64) -> ()
%264 = arith.constant 8 : i32
%265 = arith.extsi %264 : i32 to i64
%263 = func.call @calloc(%256, %265) : (i64, i64) -> !llvm.ptr
%266 = arith.constant 1 : i32
%268 = arith.extsi %266 : i32 to i64
%267 = arith.subi %253, %268 : i64
%269 = arith.constant 1 : i32
%271 = arith.extsi %269 : i32 to i64
%270 = arith.addi %247, %271 : i64
%272 = arith.cmpi eq, %251, %270 : i64
cf.cond_br %272, ^bb36, ^bb37
^bb36:
%273 = arith.constant 0 : i32
%274 = arith.extsi %273 : i32 to i64
%275 = llvm.mlir.constant(1 : i64) : i64
%276 = llvm.alloca %275 x i64 : (i64) -> !llvm.ptr
llvm.store %274, %276 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%277 = llvm.load %276 : !llvm.ptr -> i64
%279 = llvm.mlir.addressof @indep_count : !llvm.ptr
%280 = llvm.load %279 : !llvm.ptr -> !llvm.ptr
%281 = llvm.getelementptr %280[%251] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%278 = llvm.load %281 : !llvm.ptr -> i64
%282 = arith.cmpi slt, %277, %278 : i64
cf.cond_br %282, ^bb40, ^bb41
^bb40:
%284 = llvm.mlir.addressof @indep_lists : !llvm.ptr
%285 = llvm.load %284 : !llvm.ptr -> !llvm.ptr
%286 = llvm.mlir.addressof @ROWCAP : !llvm.ptr
%287 = llvm.load %286 : !llvm.ptr -> i64
%288 = arith.muli %251, %287 : i64
%289 = llvm.load %276 : !llvm.ptr -> i64
%290 = arith.addi %288, %289 : i64
%291 = llvm.getelementptr %285[%290] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%283 = llvm.load %291 : !llvm.ptr -> i64
%292 = arith.constant 1 : i32
%294 = arith.extsi %292 : i32 to i64
%293 = arith.shrsi %283, %294 : i64
%295 = arith.ori %283, %293 : i64
%296 = arith.andi %295, %267 : i64
%297 = arith.xori %267, %296 : i64
%299 = llvm.getelementptr %258[%297] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%298 = llvm.load %299 : !llvm.ptr -> i64
%300 = llvm.getelementptr %263[%283] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %298, %300 : i64, !llvm.ptr
%301 = llvm.load %276 : !llvm.ptr -> i64
%302 = arith.constant 1 : i32
%304 = arith.extsi %302 : i32 to i64
%303 = arith.addi %301, %304 : i64
llvm.store %303, %276 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
cf.br ^bb38
^bb37:
%305 = arith.constant 0 : i32
%306 = arith.extsi %305 : i32 to i64
%307 = llvm.mlir.constant(1 : i64) : i64
%308 = llvm.alloca %307 x i64 : (i64) -> !llvm.ptr
llvm.store %306, %308 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%309 = llvm.load %308 : !llvm.ptr -> i64
%311 = llvm.mlir.addressof @indep_count : !llvm.ptr
%312 = llvm.load %311 : !llvm.ptr -> !llvm.ptr
%313 = llvm.getelementptr %312[%251] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%310 = llvm.load %313 : !llvm.ptr -> i64
%314 = arith.cmpi slt, %309, %310 : i64
cf.cond_br %314, ^bb43, ^bb44
^bb43:
%316 = llvm.mlir.addressof @indep_lists : !llvm.ptr
%317 = llvm.load %316 : !llvm.ptr -> !llvm.ptr
%318 = llvm.mlir.addressof @ROWCAP : !llvm.ptr
%319 = llvm.load %318 : !llvm.ptr -> i64
%320 = arith.muli %251, %319 : i64
%321 = llvm.load %308 : !llvm.ptr -> i64
%322 = arith.addi %320, %321 : i64
%323 = llvm.getelementptr %317[%322] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%315 = llvm.load %323 : !llvm.ptr -> i64
%324 = arith.constant 1 : i32
%326 = arith.extsi %324 : i32 to i64
%325 = arith.shli %315, %326 : i64
%327 = arith.ori %315, %325 : i64
%328 = arith.andi %327, %267 : i64
%329 = arith.xori %267, %328 : i64
%331 = llvm.getelementptr %258[%329] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%330 = llvm.load %331 : !llvm.ptr -> i64
%332 = llvm.getelementptr %263[%315] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %330, %332 : i64, !llvm.ptr
%333 = llvm.load %308 : !llvm.ptr -> i64
%334 = arith.constant 1 : i32
%336 = arith.extsi %334 : i32 to i64
%335 = arith.addi %333, %336 : i64
llvm.store %335, %308 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
cf.br ^bb38
^bb38:
func.call @free(%258) : (!llvm.ptr) -> ()
%339 = llvm.load %207 : !llvm.ptr -> !llvm.ptr
func.call @free(%339) : (!llvm.ptr) -> ()
llvm.store %263, %207 : !llvm.ptr, !llvm.ptr
%340 = llvm.load %238 : !llvm.ptr -> i64
%341 = arith.constant 1 : i32
%343 = arith.extsi %341 : i32 to i64
%342 = arith.addi %340, %343 : i64
llvm.store %342, %238 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
%345 = arith.constant 1 : i32
%347 = arith.extsi %345 : i32 to i64
%346 = arith.subi %arg1, %347 : i64
%348 = llvm.getelementptr %arg0[%346] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%344 = llvm.load %348 : !llvm.ptr -> i32
%349 = arith.extsi %344 : i32 to i64
%350 = arith.constant 0 : i32
%351 = arith.extsi %350 : i32 to i64
%352 = llvm.mlir.constant(1 : i64) : i64
%353 = llvm.alloca %352 x i64 : (i64) -> !llvm.ptr
llvm.store %351, %353 : i64, !llvm.ptr
%354 = arith.constant 0 : i32
%355 = arith.extsi %354 : i32 to i64
%356 = llvm.mlir.constant(1 : i64) : i64
%357 = llvm.alloca %356 x i64 : (i64) -> !llvm.ptr
llvm.store %355, %357 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%358 = llvm.load %357 : !llvm.ptr -> i64
%360 = llvm.mlir.addressof @indep_count : !llvm.ptr
%361 = llvm.load %360 : !llvm.ptr -> !llvm.ptr
%362 = llvm.getelementptr %361[%349] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%359 = llvm.load %362 : !llvm.ptr -> i64
%363 = arith.cmpi slt, %358, %359 : i64
cf.cond_br %363, ^bb46, ^bb47
^bb46:
%364 = llvm.load %353 : !llvm.ptr -> i64
%366 = llvm.load %207 : !llvm.ptr -> !llvm.ptr
%368 = llvm.mlir.addressof @indep_lists : !llvm.ptr
%369 = llvm.load %368 : !llvm.ptr -> !llvm.ptr
%370 = llvm.mlir.addressof @ROWCAP : !llvm.ptr
%371 = llvm.load %370 : !llvm.ptr -> i64
%372 = arith.muli %349, %371 : i64
%373 = llvm.load %357 : !llvm.ptr -> i64
%374 = arith.addi %372, %373 : i64
%375 = llvm.getelementptr %369[%374] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%367 = llvm.load %375 : !llvm.ptr -> i64
%376 = llvm.getelementptr %366[%367] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%365 = llvm.load %376 : !llvm.ptr -> i64
%377 = arith.addi %364, %365 : i64
llvm.store %377, %353 : i64, !llvm.ptr
%378 = llvm.load %353 : !llvm.ptr -> i64
%379 = llvm.mlir.addressof @MOD : !llvm.ptr
%380 = llvm.load %379 : !llvm.ptr -> i64
%381 = arith.cmpi sge, %378, %380 : i64
cf.cond_br %381, ^bb48, ^bb49
^bb48:
%382 = llvm.load %353 : !llvm.ptr -> i64
%383 = llvm.mlir.addressof @MOD : !llvm.ptr
%384 = llvm.load %383 : !llvm.ptr -> i64
%385 = arith.subi %382, %384 : i64
llvm.store %385, %353 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%386 = llvm.load %357 : !llvm.ptr -> i64
%387 = arith.constant 1 : i32
%389 = arith.extsi %387 : i32 to i64
%388 = arith.addi %386, %389 : i64
llvm.store %388, %357 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%391 = llvm.load %207 : !llvm.ptr -> !llvm.ptr
func.call @free(%391) : (!llvm.ptr) -> ()
%392 = llvm.load %353 : !llvm.ptr -> i64
%393 = llvm.mlir.addressof @MOD : !llvm.ptr
%394 = llvm.load %393 : !llvm.ptr -> i64
%395 = arith.remsi %392, %394 : i64
func.return %395 : i64
}
func.func @H(%arg0: i64) -> i64 {
%397 = arith.constant 64 : i32
%398 = arith.constant 4 : i32
%399 = arith.extsi %397 : i32 to i64
%400 = arith.extsi %398 : i32 to i64
%396 = func.call @calloc(%399, %400) : (i64, i64) -> !llvm.ptr
%401 = arith.constant 0 : i32
%402 = arith.extsi %401 : i32 to i64
%403 = llvm.mlir.constant(1 : i64) : i64
%404 = llvm.alloca %403 x i64 : (i64) -> !llvm.ptr
llvm.store %402, %404 : i64, !llvm.ptr
%405 = llvm.mlir.constant(1 : i64) : i64
%406 = llvm.alloca %405 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %406 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%407 = llvm.load %406 : !llvm.ptr -> i64
%408 = arith.constant 2 : i32
%410 = arith.extsi %408 : i32 to i64
%409 = arith.muli %410, %arg0 : i64
%411 = arith.cmpi slt, %407, %409 : i64
cf.cond_br %411, ^bb52, ^bb53
^bb52:
%412 = llvm.load %406 : !llvm.ptr -> i64
%413 = arith.trunci %412 : i64 to i32
%414 = llvm.load %404 : !llvm.ptr -> i64
%415 = llvm.getelementptr %396[%414] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %413, %415 : i32, !llvm.ptr
%416 = llvm.load %404 : !llvm.ptr -> i64
%417 = arith.constant 1 : i32
%419 = arith.extsi %417 : i32 to i64
%418 = arith.addi %416, %419 : i64
llvm.store %418, %404 : i64, !llvm.ptr
%420 = llvm.load %406 : !llvm.ptr -> i64
%421 = arith.constant 1 : i32
%423 = arith.extsi %421 : i32 to i64
%422 = arith.addi %420, %423 : i64
llvm.store %422, %406 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%424 = arith.constant 0 : i32
%425 = arith.extsi %424 : i32 to i64
%426 = llvm.mlir.constant(1 : i64) : i64
%427 = llvm.alloca %426 x i64 : (i64) -> !llvm.ptr
llvm.store %425, %427 : i64, !llvm.ptr
%428 = arith.constant 2 : i32
%430 = arith.extsi %428 : i32 to i64
%429 = arith.muli %430, %arg0 : i64
%431 = arith.constant 2 : i32
%433 = arith.extsi %431 : i32 to i64
%432 = arith.subi %429, %433 : i64
llvm.store %432, %406 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%434 = llvm.load %406 : !llvm.ptr -> i64
%435 = arith.cmpi sge, %434, %arg0 : i64
cf.cond_br %435, ^bb55, ^bb56
^bb55:
%436 = llvm.load %406 : !llvm.ptr -> i64
%437 = arith.trunci %436 : i64 to i32
%438 = llvm.load %404 : !llvm.ptr -> i64
%439 = llvm.load %427 : !llvm.ptr -> i64
%440 = arith.addi %438, %439 : i64
%441 = llvm.getelementptr %396[%440] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %437, %441 : i32, !llvm.ptr
%442 = llvm.load %427 : !llvm.ptr -> i64
%443 = arith.constant 1 : i32
%445 = arith.extsi %443 : i32 to i64
%444 = arith.addi %442, %445 : i64
llvm.store %444, %427 : i64, !llvm.ptr
%446 = llvm.load %406 : !llvm.ptr -> i64
%447 = arith.constant 1 : i32
%449 = arith.extsi %447 : i32 to i64
%448 = arith.subi %446, %449 : i64
llvm.store %448, %406 : i64, !llvm.ptr
cf.br ^bb54
^bb56:
%451 = llvm.load %404 : !llvm.ptr -> i64
%452 = llvm.load %427 : !llvm.ptr -> i64
%453 = arith.addi %451, %452 : i64
%450 = func.call @count_independent_sets(%396, %453) : (!llvm.ptr, i64) -> i64
func.call @free(%396) : (!llvm.ptr) -> ()
func.return %450 : i64
}
func.func @F(%arg0: i64, %arg1: i64) -> i64 {
%455 = arith.constant 1 : i32
%457 = arith.extsi %455 : i32 to i64
%456 = arith.subi %arg1, %457 : i64
%458 = arith.constant 0 : i32
%460 = arith.extsi %458 : i32 to i64
%459 = arith.cmpi sle, %456, %460 : i64
cf.cond_br %459, ^bb57, ^bb58
^bb57:
%461 = arith.constant 1 : i32
%462 = arith.extsi %461 : i32 to i64
func.return %462 : i64
^bb58:
cf.br ^bb59
^bb59:
%464 = arith.constant 64 : i32
%465 = arith.constant 4 : i32
%466 = arith.extsi %464 : i32 to i64
%467 = arith.extsi %465 : i32 to i64
%463 = func.call @calloc(%466, %467) : (i64, i64) -> !llvm.ptr
%468 = arith.constant 0 : i32
%469 = arith.extsi %468 : i32 to i64
%470 = llvm.mlir.constant(1 : i64) : i64
%471 = llvm.alloca %470 x i64 : (i64) -> !llvm.ptr
llvm.store %469, %471 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%472 = llvm.load %471 : !llvm.ptr -> i64
%473 = arith.cmpi slt, %472, %456 : i64
cf.cond_br %473, ^bb61, ^bb62
^bb61:
%474 = arith.constant 2 : i32
%476 = arith.extsi %474 : i32 to i64
%475 = arith.subi %arg0, %476 : i64
%477 = llvm.load %471 : !llvm.ptr -> i64
%478 = arith.subi %475, %477 : i64
%479 = arith.constant 0 : i32
%481 = arith.extsi %479 : i32 to i64
%480 = arith.cmpi sgt, %478, %481 : i64
cf.cond_br %480, ^bb63, ^bb64
^bb63:
%482 = arith.trunci %478 : i64 to i32
%483 = llvm.load %471 : !llvm.ptr -> i64
%484 = llvm.getelementptr %463[%483] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %482, %484 : i32, !llvm.ptr
cf.br ^bb65
^bb64:
%485 = arith.constant 0 : i32
%486 = llvm.load %471 : !llvm.ptr -> i64
%487 = llvm.getelementptr %463[%486] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %485, %487 : i32, !llvm.ptr
cf.br ^bb65
^bb65:
%488 = llvm.load %471 : !llvm.ptr -> i64
%489 = arith.constant 1 : i32
%491 = arith.extsi %489 : i32 to i64
%490 = arith.addi %488, %491 : i64
llvm.store %490, %471 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
%492 = llvm.mlir.constant(1 : i64) : i64
%493 = llvm.alloca %492 x i64 : (i64) -> !llvm.ptr
llvm.store %456, %493 : i64, !llvm.ptr
%494 = arith.constant 0 : i32
%495 = arith.extsi %494 : i32 to i64
llvm.store %495, %471 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%496 = llvm.load %471 : !llvm.ptr -> i64
%497 = arith.cmpi slt, %496, %456 : i64
cf.cond_br %497, ^bb67, ^bb68
^bb67:
%499 = llvm.load %471 : !llvm.ptr -> i64
%500 = llvm.getelementptr %463[%499] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%498 = llvm.load %500 : !llvm.ptr -> i32
%501 = arith.constant 0 : i32
%502 = arith.cmpi eq, %498, %501 : i32
cf.cond_br %502, ^bb69, ^bb70
^bb69:
%503 = llvm.load %471 : !llvm.ptr -> i64
llvm.store %503, %493 : i64, !llvm.ptr
cf.br ^bb68
^bb70:
cf.br ^bb71
^bb71:
%504 = llvm.load %471 : !llvm.ptr -> i64
%505 = arith.constant 1 : i32
%507 = arith.extsi %505 : i32 to i64
%506 = arith.addi %504, %507 : i64
llvm.store %506, %471 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
%509 = llvm.load %493 : !llvm.ptr -> i64
%508 = func.call @count_independent_sets(%463, %509) : (!llvm.ptr, i64) -> i64
func.call @free(%463) : (!llvm.ptr) -> ()
func.return %508 : i64
}
func.func @R(%arg0: i64, %arg1: i64) -> i64 {
%511 = arith.constant 0 : i32
%513 = arith.extsi %511 : i32 to i64
%512 = arith.cmpi eq, %arg1, %513 : i64
cf.cond_br %512, ^bb72, ^bb73
^bb72:
%514 = func.call @H(%arg0) : (i64) -> i64
func.return %514 : i64
^bb73:
cf.br ^bb74
^bb74:
%516 = llvm.mlir.addressof @R_computed : !llvm.ptr
%517 = llvm.load %516 : !llvm.ptr -> !llvm.ptr
%518 = arith.constant 16 : i32
%520 = arith.extsi %518 : i32 to i64
%519 = arith.muli %arg0, %520 : i64
%521 = arith.addi %519, %arg1 : i64
%522 = llvm.getelementptr %517[%521] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%515 = llvm.load %522 : !llvm.ptr -> i32
%523 = arith.constant 0 : i32
%524 = arith.cmpi ne, %515, %523 : i32
cf.cond_br %524, ^bb75, ^bb76
^bb75:
%526 = llvm.mlir.addressof @R_cache : !llvm.ptr
%527 = llvm.load %526 : !llvm.ptr -> !llvm.ptr
%528 = arith.constant 16 : i32
%530 = arith.extsi %528 : i32 to i64
%529 = arith.muli %arg0, %530 : i64
%531 = arith.addi %529, %arg1 : i64
%532 = llvm.getelementptr %527[%531] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%525 = llvm.load %532 : !llvm.ptr -> i64
func.return %525 : i64
^bb76:
cf.br ^bb77
^bb77:
%533 = arith.constant 0 : i32
%534 = arith.extsi %533 : i32 to i64
%535 = llvm.mlir.constant(1 : i64) : i64
%536 = llvm.alloca %535 x i64 : (i64) -> !llvm.ptr
llvm.store %534, %536 : i64, !llvm.ptr
%537 = arith.constant 1 : i32
%539 = arith.extsi %537 : i32 to i64
%538 = arith.cmpi eq, %arg0, %539 : i64
%540 = scf.if %538 -> (i1) {
%541 = arith.constant 1 : i32
%543 = arith.extsi %541 : i32 to i64
%542 = arith.cmpi eq, %arg1, %543 : i64
scf.yield %542 : i1
} else {
%544 = arith.constant false
scf.yield %544 : i1
}
cf.cond_br %540, ^bb78, ^bb79
^bb78:
%545 = arith.constant 1 : i32
%546 = arith.extsi %545 : i32 to i64
llvm.store %546, %536 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%547 = arith.constant 0 : i32
%548 = arith.extsi %547 : i32 to i64
%549 = llvm.mlir.constant(1 : i64) : i64
%550 = llvm.alloca %549 x i64 : (i64) -> !llvm.ptr
llvm.store %548, %550 : i64, !llvm.ptr
cf.br ^bb81
^bb81:
%551 = llvm.load %550 : !llvm.ptr -> i64
%552 = arith.cmpi slt, %551, %arg0 : i64
cf.cond_br %552, ^bb82, ^bb83
^bb82:
%554 = llvm.load %550 : !llvm.ptr -> i64
%555 = arith.subi %arg0, %554 : i64
%553 = func.call @F(%arg0, %555) : (i64, i64) -> i64
%557 = llvm.load %550 : !llvm.ptr -> i64
%556 = func.call @R(%arg1, %557) : (i64, i64) -> i64
%559 = arith.constant 6 : i32
%560 = llvm.mlir.addressof @MOD : !llvm.ptr
%561 = llvm.load %560 : !llvm.ptr -> i64
%562 = arith.extsi %559 : i32 to i64
%558 = func.call @modpow(%553, %562, %561) : (i64, i64, i64) -> i64
%563 = llvm.load %536 : !llvm.ptr -> i64
%564 = arith.extsi %556 : i64 to i128
%565 = arith.extsi %558 : i64 to i128
%567 = arith.trunci %564 : i128 to i64
%568 = arith.trunci %565 : i128 to i64
%566 = arith.muli %567, %568 : i64
%569 = llvm.mlir.addressof @MOD : !llvm.ptr
%570 = llvm.load %569 : !llvm.ptr -> i64
%571 = arith.extsi %570 : i64 to i128
%573 = arith.trunci %571 : i128 to i64
%572 = arith.remsi %566, %573 : i64
%574 = arith.addi %563, %572 : i64
%575 = llvm.mlir.addressof @MOD : !llvm.ptr
%576 = llvm.load %575 : !llvm.ptr -> i64
%577 = arith.remsi %574, %576 : i64
llvm.store %577, %536 : i64, !llvm.ptr
%578 = llvm.load %550 : !llvm.ptr -> i64
%579 = arith.constant 1 : i32
%581 = arith.extsi %579 : i32 to i64
%580 = arith.addi %578, %581 : i64
llvm.store %580, %550 : i64, !llvm.ptr
cf.br ^bb81
^bb83:
%582 = arith.constant 1 : i32
%583 = llvm.mlir.addressof @R_computed : !llvm.ptr
%584 = llvm.load %583 : !llvm.ptr -> !llvm.ptr
%585 = arith.constant 16 : i32
%587 = arith.extsi %585 : i32 to i64
%586 = arith.muli %arg0, %587 : i64
%588 = arith.addi %586, %arg1 : i64
%589 = llvm.getelementptr %584[%588] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %582, %589 : i32, !llvm.ptr
%590 = llvm.load %536 : !llvm.ptr -> i64
%591 = llvm.mlir.addressof @R_cache : !llvm.ptr
%592 = llvm.load %591 : !llvm.ptr -> !llvm.ptr
%593 = arith.constant 16 : i32
%595 = arith.extsi %593 : i32 to i64
%594 = arith.muli %arg0, %595 : i64
%596 = arith.addi %594, %arg1 : i64
%597 = llvm.getelementptr %592[%596] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %590, %597 : i64, !llvm.ptr
%598 = llvm.load %536 : !llvm.ptr -> i64
func.return %598 : i64
}
func.func @T(%arg0: i64) -> i64 {
%599 = arith.constant 2 : i32
%600 = func.call @R(%arg0, %arg0) : (i64, i64) -> i64
%602 = arith.extsi %599 : i32 to i64
%601 = arith.muli %602, %600 : i64
%603 = llvm.mlir.addressof @MOD : !llvm.ptr
%604 = llvm.load %603 : !llvm.ptr -> i64
%605 = arith.remsi %601, %604 : i64
%606 = llvm.mlir.constant(1 : i64) : i64
%607 = llvm.alloca %606 x i64 : (i64) -> !llvm.ptr
llvm.store %605, %607 : i64, !llvm.ptr
%608 = arith.constant 1 : i32
%610 = arith.extsi %608 : i32 to i64
%609 = arith.cmpi eq, %arg0, %610 : i64
cf.cond_br %609, ^bb84, ^bb85
^bb84:
%611 = llvm.load %607 : !llvm.ptr -> i64
%612 = arith.constant 1 : i32
%614 = arith.extsi %612 : i32 to i64
%613 = arith.subi %611, %614 : i64
llvm.store %613, %607 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
%615 = llvm.load %607 : !llvm.ptr -> i64
%616 = arith.constant 0 : i32
%618 = arith.extsi %616 : i32 to i64
%617 = arith.cmpi slt, %615, %618 : i64
cf.cond_br %617, ^bb87, ^bb88
^bb87:
%619 = llvm.load %607 : !llvm.ptr -> i64
%620 = llvm.mlir.addressof @MOD : !llvm.ptr
%621 = llvm.load %620 : !llvm.ptr -> i64
%622 = arith.addi %619, %621 : i64
llvm.store %622, %607 : i64, !llvm.ptr
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
%623 = llvm.load %607 : !llvm.ptr -> i64
func.return %623 : i64
}
func.func @main() -> i32 {
%625 = arith.constant 16 : i32
%626 = arith.constant 16 : i32
%627 = arith.muli %625, %626 : i32
%628 = arith.constant 8 : i32
%629 = arith.extsi %627 : i32 to i64
%630 = arith.extsi %628 : i32 to i64
%624 = func.call @calloc(%629, %630) : (i64, i64) -> !llvm.ptr
%631 = llvm.mlir.addressof @R_cache : !llvm.ptr
llvm.store %624, %631 : !llvm.ptr, !llvm.ptr
%633 = arith.constant 16 : i32
%634 = arith.constant 16 : i32
%635 = arith.muli %633, %634 : i32
%636 = arith.constant 4 : i32
%637 = arith.extsi %635 : i32 to i64
%638 = arith.extsi %636 : i32 to i64
%632 = func.call @calloc(%637, %638) : (i64, i64) -> !llvm.ptr
%639 = llvm.mlir.addressof @R_computed : !llvm.ptr
llvm.store %632, %639 : !llvm.ptr, !llvm.ptr
func.call @init_indep() : () -> ()
%641 = llvm.mlir.addressof @str_0 : !llvm.ptr
%643 = arith.constant 10 : i32
%644 = arith.extsi %643 : i32 to i64
%642 = func.call @T(%644) : (i64) -> i64
%645 = llvm.call @printf(%641, %642) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%646 = arith.constant 0 : i32
func.return %646 : i32
}
}