Problem 189
Valid 3-colourings of height-8 triangle grid.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(2^n) | O(n^2) |
|---|
| Space complexity | O(n^2) | O(n^2) |
|---|
| Approach | Flow solution | Bottom-up DP |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 189
# Valid 3-colourings of height-8 triangle grid.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
let mut triangles: ptr<i32> = null
let mut cache_key: ptr<i64> = null
let mut cache_val: ptr<i64> = null
let mut cache_used: ptr<i8> = null
const CACHE_SIZE: i64 = 1048576
function cache_get(key: i64) -> i64 {
let mut h: i64 = key % CACHE_SIZE
if h < 0 { h = 0 - h }
while cache_used[h] == 1 {
if cache_key[h] == key { return cache_val[h] }
h = h + 1
if h >= CACHE_SIZE { h = 0 }
}
return 0 - 1
}
function cache_put(key: i64, val: i64) -> void {
let mut h: i64 = key % CACHE_SIZE
if h < 0 { h = 0 - h }
while cache_used[h] == 1 {
if cache_key[h] == key {
cache_val[h] = val
return
}
h = h + 1
if h >= CACHE_SIZE { h = 0 }
}
cache_used[h] = 1
cache_key[h] = key
cache_val[h] = val
}
function cache_clear() -> void {
let mut i: i64 = 0
while i < CACHE_SIZE {
cache_used[i] = 0
i = i + 1
}
}
function get_id(row: i32, num_colors: i32) -> i64 {
let first: i32 = row * row
let width: i32 = 2 * row + 1
let mut result: i64 = row as i64
let mut i: i32 = first + 2
while i < first + width {
let mut diff: i32 = triangles[i - 2] - triangles[i]
if diff < 0 { diff = diff + num_colors }
result = result * (num_colors as i64) + (diff as i64)
i = i + 2
}
let mut reverse: i64 = row as i64
i = first + width - 1
while i >= first + 2 {
let mut diff: i32 = triangles[i - 2] - triangles[i]
if diff < 0 { diff = diff + num_colors }
reverse = reverse * (num_colors as i64) + (diff as i64)
i = i - 2
}
if result > reverse { return reverse }
return result
}
function search(row: i32, column: i32, height: i32, num_colors: i32) -> i64 {
let first: i32 = row * row
let index: i32 = first + column
let width: i32 = 2 * row + 1
let mut next_row: i32 = row
let mut next_column: i32 = column + 1
if next_column == width {
next_row = next_row + 1
next_column = 0
}
let mut prev_id: i64 = 0
if column == 0 {
if row == height { return 1 }
if row == 0 {
cache_clear()
} else {
prev_id = get_id(row - 1, num_colors)
let cached: i64 = cache_get(prev_id)
if cached >= 0 { return cached }
}
}
let mut result: i64 = 0
if column % 2 == 0 {
let mut color: i32 = 1
while color <= num_colors {
if !(column > 0 && triangles[index - 1] == color) {
triangles[index] = color
result = result + search(next_row, next_column, height, num_colors)
}
color = color + 1
}
} else {
let mut color: i32 = 1
while color <= num_colors {
if !(triangles[index - 1] == color || triangles[index - 2 * row] == color) {
triangles[index] = color
result = result + search(next_row, next_column, height, num_colors)
}
color = color + 1
}
}
if column == 0 && row > 0 {
cache_put(prev_id, result)
}
return result
}
function main() -> i32 {
let height: i32 = 8
let num_colors: i32 = 3
triangles = calloc((height * height) as i64, 4)
cache_key = calloc(CACHE_SIZE, 8)
cache_val = calloc(CACHE_SIZE, 8)
cache_used = calloc(CACHE_SIZE, 1)
if triangles == null || cache_key == null || cache_val == null || cache_used == null {
return 1
}
printf("%lld\n", search(0, 0, height, num_colors))
free(triangles); free(cache_key); free(cache_val); free(cache_used)
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 cache_get_i64(int64_t key);
void cache_put_i64_i64(int64_t key, int64_t val);
void cache_clear(void);
int64_t get_id_i32_i32(int32_t row, int32_t num_colors);
int64_t search_i32_i32_i32_i32(int32_t row, int32_t column, int32_t height, int32_t num_colors);
int32_t main(void);
static const int64_t CACHE_SIZE = 1048576;
/* Module statics */
static int32_t* triangles = NULL;
static int64_t* cache_key = NULL;
static int64_t* cache_val = NULL;
static int8_t* cache_used = NULL;
int64_t cache_get_i64(int64_t key) {
int64_t h = FLOW_CHECKED_MOD((key), (CACHE_SIZE));
if (h < 0) {
h = (0 - h);
}
while (cache_used[h] == 1) {
if (cache_key[h] == key) {
return cache_val[h];
}
h = (h + 1);
if (h >= CACHE_SIZE) {
h = 0;
}
}
return (0 - 1);
}
void cache_put_i64_i64(int64_t key, int64_t val) {
int64_t h = FLOW_CHECKED_MOD((key), (CACHE_SIZE));
if (h < 0) {
h = (0 - h);
}
while (cache_used[h] == 1) {
if (cache_key[h] == key) {
cache_val[h] = val;
return;
}
h = (h + 1);
if (h >= CACHE_SIZE) {
h = 0;
}
}
cache_used[h] = 1;
cache_key[h] = key;
cache_val[h] = val;
}
void cache_clear(void) {
int64_t i = 0;
while (i < CACHE_SIZE) {
cache_used[i] = 0;
i = (i + 1);
}
}
int64_t get_id_i32_i32(int32_t row, int32_t num_colors) {
int32_t first = (row * row);
int32_t width = ((2 * row) + 1);
int64_t result = ((int64_t)(row));
int32_t i = (first + 2);
while (i < (first + width)) {
int32_t diff = (triangles[(i - 2)] - triangles[i]);
if (diff < 0) {
diff = (diff + num_colors);
}
result = ((result * ((int64_t)(num_colors))) + ((int64_t)(diff)));
i = (i + 2);
}
int64_t reverse = ((int64_t)(row));
i = ((first + width) - 1);
while (i >= (first + 2)) {
int32_t diff = (triangles[(i - 2)] - triangles[i]);
if (diff < 0) {
diff = (diff + num_colors);
}
reverse = ((reverse * ((int64_t)(num_colors))) + ((int64_t)(diff)));
i = (i - 2);
}
if (result > reverse) {
return reverse;
}
return result;
}
int64_t search_i32_i32_i32_i32(int32_t row, int32_t column, int32_t height, int32_t num_colors) {
int32_t first = (row * row);
int32_t index = (first + column);
int32_t width = ((2 * row) + 1);
int32_t next_row = row;
int32_t next_column = (column + 1);
if (next_column == width) {
next_row = (next_row + 1);
next_column = 0;
}
int64_t prev_id = 0;
if (column == 0) {
if (row == height) {
return 1;
}
if (row == 0) {
cache_clear();
} else {
prev_id = get_id_i32_i32((row - 1), num_colors);
int64_t cached = cache_get_i64(prev_id);
if (cached >= 0) {
return cached;
}
}
}
int64_t result = 0;
if (FLOW_CHECKED_MOD((column), (2)) == 0) {
int32_t color = 1;
while (color <= num_colors) {
if ((!((column > 0 && triangles[(index - 1)] == color)))) {
triangles[index] = color;
result = (result + search_i32_i32_i32_i32(next_row, next_column, height, num_colors));
}
color = (color + 1);
}
} else {
int32_t color = 1;
while (color <= num_colors) {
if ((!((triangles[(index - 1)] == color || triangles[(index - (2 * row))] == color)))) {
triangles[index] = color;
result = (result + search_i32_i32_i32_i32(next_row, next_column, height, num_colors));
}
color = (color + 1);
}
}
if ((column == 0 && row > 0)) {
cache_put_i64_i64(prev_id, result);
}
return result;
}
int32_t main(void) {
int32_t height = 8;
int32_t num_colors = 3;
triangles = calloc(((int64_t)((height * height))), 4);
cache_key = calloc(CACHE_SIZE, 8);
cache_val = calloc(CACHE_SIZE, 8);
cache_used = calloc(CACHE_SIZE, 1);
if ((((triangles == NULL || cache_key == NULL) || cache_val == NULL) || cache_used == NULL)) {
return 1;
}
printf("%lld\n", search_i32_i32_i32_i32(0, 0, height, num_colors));
free(triangles);
free(cache_key);
free(cache_val);
free(cache_used);
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) -> ()
// Module static: triangles
llvm.mlir.global internal @triangles() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: cache_key
llvm.mlir.global internal @cache_key() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
// Module static: cache_val
llvm.mlir.global internal @cache_val() {addr_space = 0 : i32} : !llvm.ptr {
%2 = llvm.mlir.zero : !llvm.ptr
llvm.return %2 : !llvm.ptr
}
// Module static: cache_used
llvm.mlir.global internal @cache_used() {addr_space = 0 : i32} : !llvm.ptr {
%3 = llvm.mlir.zero : !llvm.ptr
llvm.return %3 : !llvm.ptr
}
// Constant: CACHE_SIZE
llvm.mlir.global internal constant @CACHE_SIZE(1048576 : i64) : i64
func.func @cache_get(%arg0: i64) -> i64 {
%4 = llvm.mlir.addressof @CACHE_SIZE : !llvm.ptr
%5 = llvm.load %4 : !llvm.ptr -> i64
%6 = arith.remsi %arg0, %5 : i64
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %6, %8 : i64, !llvm.ptr
%9 = llvm.load %8 : !llvm.ptr -> i64
%10 = arith.constant 0 : i32
%12 = arith.extsi %10 : i32 to i64
%11 = arith.cmpi slt, %9, %12 : i64
cf.cond_br %11, ^bb0, ^bb1
^bb0:
%13 = arith.constant 0 : i32
%14 = llvm.load %8 : !llvm.ptr -> i64
%16 = arith.extsi %13 : i32 to i64
%15 = arith.subi %16, %14 : i64
llvm.store %15, %8 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
cf.br ^bb3
^bb3:
%18 = llvm.mlir.addressof @cache_used : !llvm.ptr
%19 = llvm.load %18 : !llvm.ptr -> !llvm.ptr
%20 = llvm.load %8 : !llvm.ptr -> i64
%21 = llvm.getelementptr %19[%20] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%17 = llvm.load %21 : !llvm.ptr -> i8
%22 = arith.constant 1 : i32
%24 = arith.extsi %17 : i8 to i32
%23 = arith.cmpi eq, %24, %22 : i32
cf.cond_br %23, ^bb4, ^bb5
^bb4:
%26 = llvm.mlir.addressof @cache_key : !llvm.ptr
%27 = llvm.load %26 : !llvm.ptr -> !llvm.ptr
%28 = llvm.load %8 : !llvm.ptr -> i64
%29 = llvm.getelementptr %27[%28] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%25 = llvm.load %29 : !llvm.ptr -> i64
%30 = arith.cmpi eq, %25, %arg0 : i64
cf.cond_br %30, ^bb6, ^bb7
^bb6:
%32 = llvm.mlir.addressof @cache_val : !llvm.ptr
%33 = llvm.load %32 : !llvm.ptr -> !llvm.ptr
%34 = llvm.load %8 : !llvm.ptr -> i64
%35 = llvm.getelementptr %33[%34] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%31 = llvm.load %35 : !llvm.ptr -> i64
func.return %31 : i64
^bb7:
cf.br ^bb8
^bb8:
%36 = llvm.load %8 : !llvm.ptr -> i64
%37 = arith.constant 1 : i32
%39 = arith.extsi %37 : i32 to i64
%38 = arith.addi %36, %39 : i64
llvm.store %38, %8 : i64, !llvm.ptr
%40 = llvm.load %8 : !llvm.ptr -> i64
%41 = llvm.mlir.addressof @CACHE_SIZE : !llvm.ptr
%42 = llvm.load %41 : !llvm.ptr -> i64
%43 = arith.cmpi sge, %40, %42 : i64
cf.cond_br %43, ^bb9, ^bb10
^bb9:
%44 = arith.constant 0 : i32
%45 = arith.extsi %44 : i32 to i64
llvm.store %45, %8 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
cf.br ^bb3
^bb5:
%46 = arith.constant 0 : i32
%47 = arith.constant 1 : i32
%48 = arith.subi %46, %47 : i32
%49 = arith.extsi %48 : i32 to i64
func.return %49 : i64
}
func.func @cache_put(%arg0: i64, %arg1: i64) -> () {
%50 = llvm.mlir.addressof @CACHE_SIZE : !llvm.ptr
%51 = llvm.load %50 : !llvm.ptr -> i64
%52 = arith.remsi %arg0, %51 : i64
%53 = llvm.mlir.constant(1 : i64) : i64
%54 = llvm.alloca %53 x i64 : (i64) -> !llvm.ptr
llvm.store %52, %54 : i64, !llvm.ptr
%55 = llvm.load %54 : !llvm.ptr -> i64
%56 = arith.constant 0 : i32
%58 = arith.extsi %56 : i32 to i64
%57 = arith.cmpi slt, %55, %58 : i64
cf.cond_br %57, ^bb12, ^bb13
^bb12:
%59 = arith.constant 0 : i32
%60 = llvm.load %54 : !llvm.ptr -> i64
%62 = arith.extsi %59 : i32 to i64
%61 = arith.subi %62, %60 : i64
llvm.store %61, %54 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
cf.br ^bb15
^bb15:
%64 = llvm.mlir.addressof @cache_used : !llvm.ptr
%65 = llvm.load %64 : !llvm.ptr -> !llvm.ptr
%66 = llvm.load %54 : !llvm.ptr -> i64
%67 = llvm.getelementptr %65[%66] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%63 = llvm.load %67 : !llvm.ptr -> i8
%68 = arith.constant 1 : i32
%70 = arith.extsi %63 : i8 to i32
%69 = arith.cmpi eq, %70, %68 : i32
cf.cond_br %69, ^bb16, ^bb17
^bb16:
%72 = llvm.mlir.addressof @cache_key : !llvm.ptr
%73 = llvm.load %72 : !llvm.ptr -> !llvm.ptr
%74 = llvm.load %54 : !llvm.ptr -> i64
%75 = llvm.getelementptr %73[%74] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%71 = llvm.load %75 : !llvm.ptr -> i64
%76 = arith.cmpi eq, %71, %arg0 : i64
cf.cond_br %76, ^bb18, ^bb19
^bb18:
%77 = llvm.mlir.addressof @cache_val : !llvm.ptr
%78 = llvm.load %77 : !llvm.ptr -> !llvm.ptr
%79 = llvm.load %54 : !llvm.ptr -> i64
%80 = llvm.getelementptr %78[%79] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %80 : i64, !llvm.ptr
func.return
^bb19:
cf.br ^bb20
^bb20:
%81 = llvm.load %54 : !llvm.ptr -> i64
%82 = arith.constant 1 : i32
%84 = arith.extsi %82 : i32 to i64
%83 = arith.addi %81, %84 : i64
llvm.store %83, %54 : i64, !llvm.ptr
%85 = llvm.load %54 : !llvm.ptr -> i64
%86 = llvm.mlir.addressof @CACHE_SIZE : !llvm.ptr
%87 = llvm.load %86 : !llvm.ptr -> i64
%88 = arith.cmpi sge, %85, %87 : i64
cf.cond_br %88, ^bb21, ^bb22
^bb21:
%89 = arith.constant 0 : i32
%90 = arith.extsi %89 : i32 to i64
llvm.store %90, %54 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
cf.br ^bb15
^bb17:
%91 = arith.constant 1 : i32
%92 = llvm.mlir.addressof @cache_used : !llvm.ptr
%93 = llvm.load %92 : !llvm.ptr -> !llvm.ptr
%94 = llvm.load %54 : !llvm.ptr -> i64
%95 = arith.trunci %91 : i32 to i8
%96 = llvm.getelementptr %93[%94] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %95, %96 : i8, !llvm.ptr
%97 = llvm.mlir.addressof @cache_key : !llvm.ptr
%98 = llvm.load %97 : !llvm.ptr -> !llvm.ptr
%99 = llvm.load %54 : !llvm.ptr -> i64
%100 = llvm.getelementptr %98[%99] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %100 : i64, !llvm.ptr
%101 = llvm.mlir.addressof @cache_val : !llvm.ptr
%102 = llvm.load %101 : !llvm.ptr -> !llvm.ptr
%103 = llvm.load %54 : !llvm.ptr -> i64
%104 = llvm.getelementptr %102[%103] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %104 : i64, !llvm.ptr
func.return
}
func.func @cache_clear() -> () {
%105 = arith.constant 0 : i32
%106 = arith.extsi %105 : i32 to i64
%107 = llvm.mlir.constant(1 : i64) : i64
%108 = llvm.alloca %107 x i64 : (i64) -> !llvm.ptr
llvm.store %106, %108 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%109 = llvm.load %108 : !llvm.ptr -> i64
%110 = llvm.mlir.addressof @CACHE_SIZE : !llvm.ptr
%111 = llvm.load %110 : !llvm.ptr -> i64
%112 = arith.cmpi slt, %109, %111 : i64
cf.cond_br %112, ^bb25, ^bb26
^bb25:
%113 = arith.constant 0 : i32
%114 = llvm.mlir.addressof @cache_used : !llvm.ptr
%115 = llvm.load %114 : !llvm.ptr -> !llvm.ptr
%116 = llvm.load %108 : !llvm.ptr -> i64
%117 = arith.trunci %113 : i32 to i8
%118 = llvm.getelementptr %115[%116] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %117, %118 : i8, !llvm.ptr
%119 = llvm.load %108 : !llvm.ptr -> i64
%120 = arith.constant 1 : i32
%122 = arith.extsi %120 : i32 to i64
%121 = arith.addi %119, %122 : i64
llvm.store %121, %108 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
func.return
}
func.func @get_id(%arg0: i32, %arg1: i32) -> i64 {
%123 = arith.muli %arg0, %arg0 : i32
%124 = arith.constant 2 : i32
%125 = arith.muli %124, %arg0 : i32
%126 = arith.constant 1 : i32
%127 = arith.addi %125, %126 : i32
%128 = arith.extsi %arg0 : i32 to i64
%129 = llvm.mlir.constant(1 : i64) : i64
%130 = llvm.alloca %129 x i64 : (i64) -> !llvm.ptr
llvm.store %128, %130 : i64, !llvm.ptr
%131 = arith.constant 2 : i32
%132 = arith.addi %123, %131 : i32
%133 = llvm.mlir.constant(1 : i64) : i64
%134 = llvm.alloca %133 x i32 : (i64) -> !llvm.ptr
llvm.store %132, %134 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%135 = llvm.load %134 : !llvm.ptr -> i32
%136 = arith.addi %123, %127 : i32
%137 = arith.cmpi slt, %135, %136 : i32
cf.cond_br %137, ^bb28, ^bb29
^bb28:
%139 = llvm.mlir.addressof @triangles : !llvm.ptr
%140 = llvm.load %139 : !llvm.ptr -> !llvm.ptr
%141 = llvm.load %134 : !llvm.ptr -> i32
%142 = arith.constant 2 : i32
%143 = arith.subi %141, %142 : i32
%144 = arith.extsi %143 : i32 to i64
%145 = llvm.getelementptr %140[%144] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%138 = llvm.load %145 : !llvm.ptr -> i32
%147 = llvm.mlir.addressof @triangles : !llvm.ptr
%148 = llvm.load %147 : !llvm.ptr -> !llvm.ptr
%149 = llvm.load %134 : !llvm.ptr -> i32
%150 = arith.extsi %149 : i32 to i64
%151 = llvm.getelementptr %148[%150] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%146 = llvm.load %151 : !llvm.ptr -> i32
%152 = arith.subi %138, %146 : i32
%153 = llvm.mlir.constant(1 : i64) : i64
%154 = llvm.alloca %153 x i32 : (i64) -> !llvm.ptr
llvm.store %152, %154 : i32, !llvm.ptr
%155 = llvm.load %154 : !llvm.ptr -> i32
%156 = arith.constant 0 : i32
%157 = arith.cmpi slt, %155, %156 : i32
cf.cond_br %157, ^bb30, ^bb31
^bb30:
%158 = llvm.load %154 : !llvm.ptr -> i32
%159 = arith.addi %158, %arg1 : i32
llvm.store %159, %154 : i32, !llvm.ptr
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%160 = llvm.load %130 : !llvm.ptr -> i64
%161 = arith.extsi %arg1 : i32 to i64
%162 = arith.muli %160, %161 : i64
%163 = llvm.load %154 : !llvm.ptr -> i32
%164 = arith.extsi %163 : i32 to i64
%165 = arith.addi %162, %164 : i64
llvm.store %165, %130 : i64, !llvm.ptr
%166 = llvm.load %134 : !llvm.ptr -> i32
%167 = arith.constant 2 : i32
%168 = arith.addi %166, %167 : i32
llvm.store %168, %134 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%169 = arith.extsi %arg0 : i32 to i64
%170 = llvm.mlir.constant(1 : i64) : i64
%171 = llvm.alloca %170 x i64 : (i64) -> !llvm.ptr
llvm.store %169, %171 : i64, !llvm.ptr
%172 = arith.addi %123, %127 : i32
%173 = arith.constant 1 : i32
%174 = arith.subi %172, %173 : i32
llvm.store %174, %134 : i32, !llvm.ptr
cf.br ^bb33
^bb33:
%175 = llvm.load %134 : !llvm.ptr -> i32
%176 = arith.constant 2 : i32
%177 = arith.addi %123, %176 : i32
%178 = arith.cmpi sge, %175, %177 : i32
cf.cond_br %178, ^bb34, ^bb35
^bb34:
%180 = llvm.mlir.addressof @triangles : !llvm.ptr
%181 = llvm.load %180 : !llvm.ptr -> !llvm.ptr
%182 = llvm.load %134 : !llvm.ptr -> i32
%183 = arith.constant 2 : i32
%184 = arith.subi %182, %183 : i32
%185 = arith.extsi %184 : i32 to i64
%186 = llvm.getelementptr %181[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%179 = llvm.load %186 : !llvm.ptr -> i32
%188 = llvm.mlir.addressof @triangles : !llvm.ptr
%189 = llvm.load %188 : !llvm.ptr -> !llvm.ptr
%190 = llvm.load %134 : !llvm.ptr -> i32
%191 = arith.extsi %190 : i32 to i64
%192 = llvm.getelementptr %189[%191] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%187 = llvm.load %192 : !llvm.ptr -> i32
%193 = arith.subi %179, %187 : i32
%194 = llvm.mlir.constant(1 : i64) : i64
%195 = llvm.alloca %194 x i32 : (i64) -> !llvm.ptr
llvm.store %193, %195 : i32, !llvm.ptr
%196 = llvm.load %195 : !llvm.ptr -> i32
%197 = arith.constant 0 : i32
%198 = arith.cmpi slt, %196, %197 : i32
cf.cond_br %198, ^bb36, ^bb37
^bb36:
%199 = llvm.load %195 : !llvm.ptr -> i32
%200 = arith.addi %199, %arg1 : i32
llvm.store %200, %195 : i32, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%201 = llvm.load %171 : !llvm.ptr -> i64
%202 = arith.extsi %arg1 : i32 to i64
%203 = arith.muli %201, %202 : i64
%204 = llvm.load %195 : !llvm.ptr -> i32
%205 = arith.extsi %204 : i32 to i64
%206 = arith.addi %203, %205 : i64
llvm.store %206, %171 : i64, !llvm.ptr
%207 = llvm.load %134 : !llvm.ptr -> i32
%208 = arith.constant 2 : i32
%209 = arith.subi %207, %208 : i32
llvm.store %209, %134 : i32, !llvm.ptr
cf.br ^bb33
^bb35:
%210 = llvm.load %130 : !llvm.ptr -> i64
%211 = llvm.load %171 : !llvm.ptr -> i64
%212 = arith.cmpi sgt, %210, %211 : i64
cf.cond_br %212, ^bb39, ^bb40
^bb39:
%213 = llvm.load %171 : !llvm.ptr -> i64
func.return %213 : i64
^bb40:
cf.br ^bb41
^bb41:
%214 = llvm.load %130 : !llvm.ptr -> i64
func.return %214 : i64
}
func.func @search(%arg0: i32, %arg1: i32, %arg2: i32, %arg3: i32) -> i64 {
%215 = arith.muli %arg0, %arg0 : i32
%216 = arith.addi %215, %arg1 : i32
%217 = arith.constant 2 : i32
%218 = arith.muli %217, %arg0 : i32
%219 = arith.constant 1 : i32
%220 = arith.addi %218, %219 : i32
%221 = llvm.mlir.constant(1 : i64) : i64
%222 = llvm.alloca %221 x i32 : (i64) -> !llvm.ptr
llvm.store %arg0, %222 : i32, !llvm.ptr
%223 = arith.constant 1 : i32
%224 = arith.addi %arg1, %223 : i32
%225 = llvm.mlir.constant(1 : i64) : i64
%226 = llvm.alloca %225 x i32 : (i64) -> !llvm.ptr
llvm.store %224, %226 : i32, !llvm.ptr
%227 = llvm.load %226 : !llvm.ptr -> i32
%228 = arith.cmpi eq, %227, %220 : i32
cf.cond_br %228, ^bb42, ^bb43
^bb42:
%229 = llvm.load %222 : !llvm.ptr -> i32
%230 = arith.constant 1 : i32
%231 = arith.addi %229, %230 : i32
llvm.store %231, %222 : i32, !llvm.ptr
%232 = arith.constant 0 : i32
llvm.store %232, %226 : i32, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%233 = arith.constant 0 : i32
%234 = arith.extsi %233 : i32 to i64
%235 = llvm.mlir.constant(1 : i64) : i64
%236 = llvm.alloca %235 x i64 : (i64) -> !llvm.ptr
llvm.store %234, %236 : i64, !llvm.ptr
%237 = arith.constant 0 : i32
%238 = arith.cmpi eq, %arg1, %237 : i32
cf.cond_br %238, ^bb45, ^bb46
^bb45:
%239 = arith.cmpi eq, %arg0, %arg2 : i32
cf.cond_br %239, ^bb48, ^bb49
^bb48:
%240 = arith.constant 1 : i32
%241 = arith.extsi %240 : i32 to i64
func.return %241 : i64
^bb49:
cf.br ^bb50
^bb50:
%242 = arith.constant 0 : i32
%243 = arith.cmpi eq, %arg0, %242 : i32
cf.cond_br %243, ^bb51, ^bb52
^bb51:
func.call @cache_clear() : () -> ()
cf.br ^bb53
^bb52:
%246 = arith.constant 1 : i32
%247 = arith.subi %arg0, %246 : i32
%245 = func.call @get_id(%247, %arg3) : (i32, i32) -> i64
llvm.store %245, %236 : i64, !llvm.ptr
%249 = llvm.load %236 : !llvm.ptr -> i64
%248 = func.call @cache_get(%249) : (i64) -> i64
%250 = arith.constant 0 : i32
%252 = arith.extsi %250 : i32 to i64
%251 = arith.cmpi sge, %248, %252 : i64
cf.cond_br %251, ^bb54, ^bb55
^bb54:
func.return %248 : i64
^bb55:
cf.br ^bb56
^bb56:
cf.br ^bb53
^bb53:
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%253 = arith.constant 0 : i32
%254 = arith.extsi %253 : i32 to i64
%255 = llvm.mlir.constant(1 : i64) : i64
%256 = llvm.alloca %255 x i64 : (i64) -> !llvm.ptr
llvm.store %254, %256 : i64, !llvm.ptr
%257 = arith.constant 2 : i32
%258 = arith.remsi %arg1, %257 : i32
%259 = arith.constant 0 : i32
%260 = arith.cmpi eq, %258, %259 : i32
cf.cond_br %260, ^bb57, ^bb58
^bb57:
%261 = arith.constant 1 : i32
%262 = llvm.mlir.constant(1 : i64) : i64
%263 = llvm.alloca %262 x i32 : (i64) -> !llvm.ptr
llvm.store %261, %263 : i32, !llvm.ptr
cf.br ^bb60
^bb60:
%264 = llvm.load %263 : !llvm.ptr -> i32
%265 = arith.cmpi sle, %264, %arg3 : i32
cf.cond_br %265, ^bb61, ^bb62
^bb61:
%266 = arith.constant 0 : i32
%267 = arith.cmpi sgt, %arg1, %266 : i32
%268 = scf.if %267 -> (i1) {
%270 = llvm.mlir.addressof @triangles : !llvm.ptr
%271 = llvm.load %270 : !llvm.ptr -> !llvm.ptr
%272 = arith.constant 1 : i32
%273 = arith.subi %216, %272 : i32
%274 = arith.extsi %273 : i32 to i64
%275 = llvm.getelementptr %271[%274] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%269 = llvm.load %275 : !llvm.ptr -> i32
%276 = llvm.load %263 : !llvm.ptr -> i32
%277 = arith.cmpi eq, %269, %276 : i32
scf.yield %277 : i1
} else {
%278 = arith.constant false
scf.yield %278 : i1
}
%280 = arith.constant 1 : i1
%279 = arith.xori %268, %280 : i1
cf.cond_br %279, ^bb63, ^bb64
^bb63:
%282 = llvm.load %263 : !llvm.ptr -> i32
%283 = llvm.mlir.addressof @triangles : !llvm.ptr
%284 = llvm.load %283 : !llvm.ptr -> !llvm.ptr
%285 = arith.extsi %216 : i32 to i64
%286 = llvm.getelementptr %284[%285] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %282, %286 : i32, !llvm.ptr
%287 = llvm.load %256 : !llvm.ptr -> i64
%289 = llvm.load %222 : !llvm.ptr -> i32
%290 = llvm.load %226 : !llvm.ptr -> i32
%288 = func.call @search(%289, %290, %arg2, %arg3) : (i32, i32, i32, i32) -> i64
%291 = arith.addi %287, %288 : i64
llvm.store %291, %256 : i64, !llvm.ptr
cf.br ^bb65
^bb64:
cf.br ^bb65
^bb65:
%292 = llvm.load %263 : !llvm.ptr -> i32
%293 = arith.constant 1 : i32
%294 = arith.addi %292, %293 : i32
llvm.store %294, %263 : i32, !llvm.ptr
cf.br ^bb60
^bb62:
cf.br ^bb59
^bb58:
%295 = arith.constant 1 : i32
%296 = llvm.mlir.constant(1 : i64) : i64
%297 = llvm.alloca %296 x i32 : (i64) -> !llvm.ptr
llvm.store %295, %297 : i32, !llvm.ptr
cf.br ^bb66
^bb66:
%298 = llvm.load %297 : !llvm.ptr -> i32
%299 = arith.cmpi sle, %298, %arg3 : i32
cf.cond_br %299, ^bb67, ^bb68
^bb67:
%301 = llvm.mlir.addressof @triangles : !llvm.ptr
%302 = llvm.load %301 : !llvm.ptr -> !llvm.ptr
%303 = arith.constant 1 : i32
%304 = arith.subi %216, %303 : i32
%305 = arith.extsi %304 : i32 to i64
%306 = llvm.getelementptr %302[%305] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%300 = llvm.load %306 : !llvm.ptr -> i32
%307 = llvm.load %297 : !llvm.ptr -> i32
%308 = arith.cmpi eq, %300, %307 : i32
%309 = scf.if %308 -> (i1) {
%310 = arith.constant true
scf.yield %310 : i1
} else {
%312 = llvm.mlir.addressof @triangles : !llvm.ptr
%313 = llvm.load %312 : !llvm.ptr -> !llvm.ptr
%314 = arith.constant 2 : i32
%315 = arith.muli %314, %arg0 : i32
%316 = arith.subi %216, %315 : i32
%317 = arith.extsi %316 : i32 to i64
%318 = llvm.getelementptr %313[%317] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%311 = llvm.load %318 : !llvm.ptr -> i32
%319 = llvm.load %297 : !llvm.ptr -> i32
%320 = arith.cmpi eq, %311, %319 : i32
scf.yield %320 : i1
}
%322 = arith.constant 1 : i1
%321 = arith.xori %309, %322 : i1
cf.cond_br %321, ^bb69, ^bb70
^bb69:
%324 = llvm.load %297 : !llvm.ptr -> i32
%325 = llvm.mlir.addressof @triangles : !llvm.ptr
%326 = llvm.load %325 : !llvm.ptr -> !llvm.ptr
%327 = arith.extsi %216 : i32 to i64
%328 = llvm.getelementptr %326[%327] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %324, %328 : i32, !llvm.ptr
%329 = llvm.load %256 : !llvm.ptr -> i64
%331 = llvm.load %222 : !llvm.ptr -> i32
%332 = llvm.load %226 : !llvm.ptr -> i32
%330 = func.call @search(%331, %332, %arg2, %arg3) : (i32, i32, i32, i32) -> i64
%333 = arith.addi %329, %330 : i64
llvm.store %333, %256 : i64, !llvm.ptr
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
%334 = llvm.load %297 : !llvm.ptr -> i32
%335 = arith.constant 1 : i32
%336 = arith.addi %334, %335 : i32
llvm.store %336, %297 : i32, !llvm.ptr
cf.br ^bb66
^bb68:
cf.br ^bb59
^bb59:
%337 = arith.constant 0 : i32
%338 = arith.cmpi eq, %arg1, %337 : i32
%339 = scf.if %338 -> (i1) {
%340 = arith.constant 0 : i32
%341 = arith.cmpi sgt, %arg0, %340 : i32
scf.yield %341 : i1
} else {
%342 = arith.constant false
scf.yield %342 : i1
}
cf.cond_br %339, ^bb72, ^bb73
^bb72:
%344 = llvm.load %236 : !llvm.ptr -> i64
%345 = llvm.load %256 : !llvm.ptr -> i64
func.call @cache_put(%344, %345) : (i64, i64) -> ()
cf.br ^bb74
^bb73:
cf.br ^bb74
^bb74:
%346 = llvm.load %256 : !llvm.ptr -> i64
func.return %346 : i64
}
func.func @main() -> i32 {
%347 = arith.constant 8 : i32
%348 = arith.constant 3 : i32
%350 = arith.muli %347, %347 : i32
%351 = arith.extsi %350 : i32 to i64
%352 = arith.constant 4 : i32
%353 = arith.extsi %352 : i32 to i64
%349 = func.call @calloc(%351, %353) : (i64, i64) -> !llvm.ptr
%354 = llvm.mlir.addressof @triangles : !llvm.ptr
llvm.store %349, %354 : !llvm.ptr, !llvm.ptr
%356 = llvm.mlir.addressof @CACHE_SIZE : !llvm.ptr
%357 = llvm.load %356 : !llvm.ptr -> i64
%358 = arith.constant 8 : i32
%359 = arith.extsi %358 : i32 to i64
%355 = func.call @calloc(%357, %359) : (i64, i64) -> !llvm.ptr
%360 = llvm.mlir.addressof @cache_key : !llvm.ptr
llvm.store %355, %360 : !llvm.ptr, !llvm.ptr
%362 = llvm.mlir.addressof @CACHE_SIZE : !llvm.ptr
%363 = llvm.load %362 : !llvm.ptr -> i64
%364 = arith.constant 8 : i32
%365 = arith.extsi %364 : i32 to i64
%361 = func.call @calloc(%363, %365) : (i64, i64) -> !llvm.ptr
%366 = llvm.mlir.addressof @cache_val : !llvm.ptr
llvm.store %361, %366 : !llvm.ptr, !llvm.ptr
%368 = llvm.mlir.addressof @CACHE_SIZE : !llvm.ptr
%369 = llvm.load %368 : !llvm.ptr -> i64
%370 = arith.constant 1 : i32
%371 = arith.extsi %370 : i32 to i64
%367 = func.call @calloc(%369, %371) : (i64, i64) -> !llvm.ptr
%372 = llvm.mlir.addressof @cache_used : !llvm.ptr
llvm.store %367, %372 : !llvm.ptr, !llvm.ptr
%373 = llvm.mlir.addressof @triangles : !llvm.ptr
%374 = llvm.load %373 : !llvm.ptr -> !llvm.ptr
%375 = llvm.mlir.zero : !llvm.ptr
%376 = llvm.icmp "eq" %374, %375 : !llvm.ptr
%377 = scf.if %376 -> (i1) {
%378 = arith.constant true
scf.yield %378 : i1
} else {
%379 = llvm.mlir.addressof @cache_key : !llvm.ptr
%380 = llvm.load %379 : !llvm.ptr -> !llvm.ptr
%381 = llvm.mlir.zero : !llvm.ptr
%382 = llvm.icmp "eq" %380, %381 : !llvm.ptr
scf.yield %382 : i1
}
%383 = scf.if %377 -> (i1) {
%384 = arith.constant true
scf.yield %384 : i1
} else {
%385 = llvm.mlir.addressof @cache_val : !llvm.ptr
%386 = llvm.load %385 : !llvm.ptr -> !llvm.ptr
%387 = llvm.mlir.zero : !llvm.ptr
%388 = llvm.icmp "eq" %386, %387 : !llvm.ptr
scf.yield %388 : i1
}
%389 = scf.if %383 -> (i1) {
%390 = arith.constant true
scf.yield %390 : i1
} else {
%391 = llvm.mlir.addressof @cache_used : !llvm.ptr
%392 = llvm.load %391 : !llvm.ptr -> !llvm.ptr
%393 = llvm.mlir.zero : !llvm.ptr
%394 = llvm.icmp "eq" %392, %393 : !llvm.ptr
scf.yield %394 : i1
}
cf.cond_br %389, ^bb75, ^bb76
^bb75:
%395 = arith.constant 1 : i32
func.return %395 : i32
^bb76:
cf.br ^bb77
^bb77:
%396 = llvm.mlir.addressof @str_0 : !llvm.ptr
%398 = arith.constant 0 : i32
%399 = arith.constant 0 : i32
%397 = func.call @search(%398, %399, %347, %348) : (i32, i32, i32, i32) -> i64
%400 = llvm.call @printf(%396, %397) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%402 = llvm.mlir.addressof @triangles : !llvm.ptr
%403 = llvm.load %402 : !llvm.ptr -> !llvm.ptr
func.call @free(%403) : (!llvm.ptr) -> ()
%405 = llvm.mlir.addressof @cache_key : !llvm.ptr
%406 = llvm.load %405 : !llvm.ptr -> !llvm.ptr
func.call @free(%406) : (!llvm.ptr) -> ()
%408 = llvm.mlir.addressof @cache_val : !llvm.ptr
%409 = llvm.load %408 : !llvm.ptr -> !llvm.ptr
func.call @free(%409) : (!llvm.ptr) -> ()
%411 = llvm.mlir.addressof @cache_used : !llvm.ptr
%412 = llvm.load %411 : !llvm.ptr -> !llvm.ptr
func.call @free(%412) : (!llvm.ptr) -> ()
%413 = arith.constant 0 : i32
func.return %413 : i32
}
}