Problem 333
Sum of primes q < 1e6 with a unique 2^a*3^b antichain partition.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n * m) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Dynamic programming or generating function |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 333
# Sum of primes q < 1e6 with a unique 2^a*3^b antichain partition.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function ipow2_3(e2: i64, e3: i64) -> i64 {
let mut r: i64 = 1
let mut b: i64 = 3
let mut e: i64 = e3
while e > 0 {
if (e & 1) == 1 { r = r * b }
b = b * b
e = e / 2
}
return r << e2
}
function bit_get(bits: ptr<i8>, base: i64, idx: i64) -> i64 {
let p: i64 = base + idx
return ((bits[p / 8] as i64) >> (p % 8)) & 1
}
function bit_set(bits: ptr<i8>, base: i64, idx: i64) -> i32 {
let p: i64 = base + idx
let byte: i64 = p / 8
let bit: i64 = p % 8
bits[byte] = ((bits[byte] as i64) | (1 << bit)) as i8
return 0
}
function main() -> i32 {
let limit: i64 = 1000000
let mut n2: i64 = 0
while ipow2_3(n2, 0) <= limit { n2 = n2 + 1 }
let mut n3: i64 = 0
while ipow2_3(0, n3) <= limit { n3 = n3 + 1 }
let ids: ptr<i32> = calloc(n2 * n3, 4)
let rev2: ptr<i32> = calloc(256, 4)
let rev3: ptr<i32> = calloc(256, 4)
let mut next_id: i64 = 1
for e2 in 0..n2 {
for e3 in 0..n3 {
let cur: i64 = ipow2_3(e2, e3)
if cur <= limit {
ids[e2 * n3 + e3] = next_id as i32
rev2[next_id] = e2 as i32
rev3[next_id] = e3 as i32
next_id = next_id + 1
}
}
}
let stride: i64 = limit + 1
let reach: ptr<i8> = calloc((next_id * stride + 7) / 8, 1)
let multi: ptr<i8> = calloc((next_id * stride + 7) / 8, 1)
for idx in 1..next_id {
let v: i64 = ipow2_3(rev2[idx] as i64, rev3[idx] as i64)
bit_set(reach, idx * stride, v)
}
let half: i64 = (limit >> 1) + 1
let sieve: ptr<i8> = calloc(half, 1)
for i in 0..half { sieve[i] = 1 }
sieve[0] = 0
let mut i: i64 = 1
while 2 * i * i < half {
if sieve[i] == 1 {
let step: i64 = 2 * i + 1
for cur in (3 * i + 1)..half step step {
sieve[cur] = 0
}
}
i = i + 1
}
let mut total: i64 = 0
for value in 1..(limit + 1) {
let mut possible: i64 = 0
let mut unique: i64 = 1
for idx in 1..next_id {
if bit_get(reach, idx * stride, value) == 0 {
continue
}
if possible == 1 || bit_get(multi, idx * stride, value) == 1 {
unique = 0
}
possible = 1
let exp_two: i64 = rev2[idx] as i64
let exp_three: i64 = rev3[idx] as i64
for ne2 in (exp_two + 1)..n2 {
let mut ne3: i64 = 0
while ne3 < exp_three {
let nid: i64 = ids[ne2 * n3 + ne3] as i64
if nid == 0 { break }
let nv: i64 = value + ipow2_3(ne2, ne3)
if nv > limit { break }
if bit_get(reach, nid * stride, nv) == 1 {
bit_set(multi, nid * stride, nv)
} else {
bit_set(reach, nid * stride, nv)
}
ne3 = ne3 + 1
}
}
}
let mut is_p: i64 = 0
if value == 2 { is_p = 1 }
elif (value & 1) == 1 && sieve[value >> 1] == 1 { is_p = 1 }
if possible == 1 && unique == 1 && is_p == 1 {
total = total + value
}
}
printf("%lld\n", total)
free(ids); free(rev2); free(rev3); free(reach); free(multi); free(sieve)
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 ipow2_3_i64_i64(int64_t e2, int64_t e3);
int64_t bit_get_ptr_i8_i64_i64(int8_t* bits, int64_t base, int64_t idx);
int32_t bit_set_ptr_i8_i64_i64(int8_t* bits, int64_t base, int64_t idx);
int32_t main(void);
int64_t ipow2_3_i64_i64(int64_t e2, int64_t e3) {
int64_t r = 1;
int64_t b = 3;
int64_t e = e3;
while (e > 0) {
if ((e & 1) == 1) {
r = (r * b);
}
b = (b * b);
e = FLOW_CHECKED_DIV((e), (2));
}
return FLOW_CHECKED_SHL((r), (e2));
}
int64_t bit_get_ptr_i8_i64_i64(int8_t* bits, int64_t base, int64_t idx) {
int64_t p = (base + idx);
return (FLOW_CHECKED_SHR((((int64_t)(bits[FLOW_CHECKED_DIV((p), (8))]))), (FLOW_CHECKED_MOD((p), (8)))) & 1);
}
int32_t bit_set_ptr_i8_i64_i64(int8_t* bits, int64_t base, int64_t idx) {
int64_t p = (base + idx);
int64_t byte = FLOW_CHECKED_DIV((p), (8));
int64_t bit = FLOW_CHECKED_MOD((p), (8));
bits[byte] = ((int8_t)((((int64_t)(bits[byte])) | FLOW_CHECKED_SHL((1), (bit)))));
return 0;
}
int32_t main(void) {
int64_t limit = 1000000;
int64_t n2 = 0;
while (ipow2_3_i64_i64(n2, 0) <= limit) {
n2 = (n2 + 1);
}
int64_t n3 = 0;
while (ipow2_3_i64_i64(0, n3) <= limit) {
n3 = (n3 + 1);
}
int32_t* ids = (int32_t*)(calloc((n2 * n3), 4));
int32_t* rev2 = (int32_t*)(calloc(256, 4));
int32_t* rev3 = (int32_t*)(calloc(256, 4));
int64_t next_id = 1;
int32_t __flow_step_1 = 1;
for (int32_t e2 = 0; (0 <= n2) ? e2 < n2 : e2 > n2; e2 += (0 <= n2) ? 1 : -1) {
int32_t __flow_step_2 = 1;
for (int32_t e3 = 0; (0 <= n3) ? e3 < n3 : e3 > n3; e3 += (0 <= n3) ? 1 : -1) {
int64_t cur = ipow2_3_i64_i64(e2, e3);
if (cur <= limit) {
ids[((e2 * n3) + e3)] = ((int32_t)(next_id));
rev2[next_id] = ((int32_t)(e2));
rev3[next_id] = ((int32_t)(e3));
next_id = (next_id + 1);
}
}
}
int64_t stride = (limit + 1);
int8_t* reach = (int8_t*)(calloc(FLOW_CHECKED_DIV((((next_id * stride) + 7)), (8)), 1));
int8_t* multi = (int8_t*)(calloc(FLOW_CHECKED_DIV((((next_id * stride) + 7)), (8)), 1));
int32_t __flow_step_3 = 1;
for (int32_t idx = 1; (1 <= next_id) ? idx < next_id : idx > next_id; idx += (1 <= next_id) ? 1 : -1) {
int64_t v = ipow2_3_i64_i64(((int64_t)(rev2[idx])), ((int64_t)(rev3[idx])));
bit_set_ptr_i8_i64_i64(reach, (idx * stride), v);
}
int64_t half = (FLOW_CHECKED_SHR((limit), (1)) + 1);
int8_t* sieve = (int8_t*)(calloc(half, 1));
int32_t __flow_step_4 = 1;
for (int32_t i = 0; (0 <= half) ? i < half : i > half; i += (0 <= half) ? 1 : -1) {
sieve[i] = 1;
}
sieve[0] = 0;
int64_t i = 1;
while (((2 * i) * i) < half) {
if (sieve[i] == 1) {
int64_t step = ((2 * i) + 1);
int32_t __flow_step_5 = step;
#pragma clang loop vectorize(enable) interleave(enable)
#pragma GCC ivdep
for (int32_t cur = ((3 * i) + 1); (__flow_step_5 > 0) ? cur < half : cur > half; cur += __flow_step_5) {
sieve[cur] = 0;
}
}
i = (i + 1);
}
int64_t total = 0;
int32_t __flow_step_6 = 1;
for (int32_t value = 1; (1 <= (limit + 1)) ? value < (limit + 1) : value > (limit + 1); value += (1 <= (limit + 1)) ? 1 : -1) {
int64_t possible = 0;
int64_t unique = 1;
int32_t __flow_step_7 = 1;
for (int32_t idx = 1; (1 <= next_id) ? idx < next_id : idx > next_id; idx += (1 <= next_id) ? 1 : -1) {
if (bit_get_ptr_i8_i64_i64(reach, (idx * stride), value) == 0) {
continue;
}
if ((possible == 1 || bit_get_ptr_i8_i64_i64(multi, (idx * stride), value) == 1)) {
unique = 0;
}
possible = 1;
int64_t exp_two = ((int64_t)(rev2[idx]));
int64_t exp_three = ((int64_t)(rev3[idx]));
int32_t __flow_step_8 = 1;
for (int32_t ne2 = (exp_two + 1); ((exp_two + 1) <= n2) ? ne2 < n2 : ne2 > n2; ne2 += ((exp_two + 1) <= n2) ? 1 : -1) {
int64_t ne3 = 0;
while (ne3 < exp_three) {
int64_t nid = ((int64_t)(ids[((ne2 * n3) + ne3)]));
if (nid == 0) {
break;
}
int64_t nv = (value + ipow2_3_i64_i64(ne2, ne3));
if (nv > limit) {
break;
}
if (bit_get_ptr_i8_i64_i64(reach, (nid * stride), nv) == 1) {
bit_set_ptr_i8_i64_i64(multi, (nid * stride), nv);
} else {
bit_set_ptr_i8_i64_i64(reach, (nid * stride), nv);
}
ne3 = (ne3 + 1);
}
}
}
int64_t is_p = 0;
if (value == 2) {
is_p = 1;
} else if (((value & 1) == 1 && sieve[FLOW_CHECKED_SHR((value), (1))] == 1)) {
is_p = 1;
}
if (((possible == 1 && unique == 1) && is_p == 1)) {
total = (total + value);
}
}
printf("%lld\n", total);
free(ids);
free(rev2);
free(rev3);
free(reach);
free(multi);
free(sieve);
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 @ipow2_3(%arg0: i64, %arg1: i64) -> i64 {
%0 = arith.constant 1 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i64, !llvm.ptr
%4 = arith.constant 3 : 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 = llvm.mlir.constant(1 : i64) : i64
%9 = llvm.alloca %8 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %9 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%10 = llvm.load %9 : !llvm.ptr -> i64
%11 = arith.constant 0 : i32
%13 = arith.extsi %11 : i32 to i64
%12 = arith.cmpi sgt, %10, %13 : i64
cf.cond_br %12, ^bb1, ^bb2
^bb1:
%14 = llvm.load %9 : !llvm.ptr -> i64
%15 = arith.constant 1 : i32
%17 = arith.extsi %15 : i32 to i64
%16 = arith.andi %14, %17 : i64
%18 = arith.constant 1 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.cmpi eq, %16, %20 : i64
cf.cond_br %19, ^bb3, ^bb4
^bb3:
%21 = llvm.load %3 : !llvm.ptr -> i64
%22 = llvm.load %7 : !llvm.ptr -> i64
%23 = arith.muli %21, %22 : i64
llvm.store %23, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%24 = llvm.load %7 : !llvm.ptr -> i64
%25 = llvm.load %7 : !llvm.ptr -> i64
%26 = arith.muli %24, %25 : i64
llvm.store %26, %7 : i64, !llvm.ptr
%27 = llvm.load %9 : !llvm.ptr -> i64
%28 = arith.constant 2 : i32
%30 = arith.extsi %28 : i32 to i64
%29 = arith.divsi %27, %30 : i64
llvm.store %29, %9 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%31 = llvm.load %3 : !llvm.ptr -> i64
%32 = arith.shli %31, %arg0 : i64
func.return %32 : i64
}
func.func @bit_get(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> i64 {
%33 = arith.addi %arg1, %arg2 : i64
%35 = arith.constant 8 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.divsi %33, %37 : i64
%38 = llvm.getelementptr %arg0[%36] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%34 = llvm.load %38 : !llvm.ptr -> i8
%39 = arith.extsi %34 : i8 to i64
%40 = arith.constant 8 : i32
%42 = arith.extsi %40 : i32 to i64
%41 = arith.remsi %33, %42 : i64
%43 = arith.shrsi %39, %41 : i64
%44 = arith.constant 1 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.andi %43, %46 : i64
func.return %45 : i64
}
func.func @bit_set(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> i32 {
%47 = arith.addi %arg1, %arg2 : i64
%48 = arith.constant 8 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.divsi %47, %50 : i64
%51 = arith.constant 8 : i32
%53 = arith.extsi %51 : i32 to i64
%52 = arith.remsi %47, %53 : i64
%55 = llvm.getelementptr %arg0[%49] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%54 = llvm.load %55 : !llvm.ptr -> i8
%56 = arith.extsi %54 : i8 to i64
%57 = arith.constant 1 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.shli %59, %52 : i64
%60 = arith.ori %56, %58 : i64
%61 = arith.trunci %60 : i64 to i8
%62 = llvm.getelementptr %arg0[%49] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %61, %62 : i8, !llvm.ptr
%63 = arith.constant 0 : i32
func.return %63 : i32
}
func.func @main() -> i32 {
%64 = arith.constant 1000000 : i32
%65 = arith.extsi %64 : i32 to i64
%66 = arith.constant 0 : i32
%67 = arith.extsi %66 : i32 to i64
%68 = llvm.mlir.constant(1 : i64) : i64
%69 = llvm.alloca %68 x i64 : (i64) -> !llvm.ptr
llvm.store %67, %69 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%71 = llvm.load %69 : !llvm.ptr -> i64
%72 = arith.constant 0 : i32
%73 = arith.extsi %72 : i32 to i64
%70 = func.call @ipow2_3(%71, %73) : (i64, i64) -> i64
%74 = arith.cmpi sle, %70, %65 : i64
cf.cond_br %74, ^bb7, ^bb8
^bb7:
%75 = llvm.load %69 : !llvm.ptr -> i64
%76 = arith.constant 1 : i32
%78 = arith.extsi %76 : i32 to i64
%77 = arith.addi %75, %78 : i64
llvm.store %77, %69 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%79 = arith.constant 0 : i32
%80 = arith.extsi %79 : i32 to i64
%81 = llvm.mlir.constant(1 : i64) : i64
%82 = llvm.alloca %81 x i64 : (i64) -> !llvm.ptr
llvm.store %80, %82 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%84 = arith.constant 0 : i32
%85 = llvm.load %82 : !llvm.ptr -> i64
%86 = arith.extsi %84 : i32 to i64
%83 = func.call @ipow2_3(%86, %85) : (i64, i64) -> i64
%87 = arith.cmpi sle, %83, %65 : i64
cf.cond_br %87, ^bb10, ^bb11
^bb10:
%88 = llvm.load %82 : !llvm.ptr -> i64
%89 = arith.constant 1 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.addi %88, %91 : i64
llvm.store %90, %82 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%93 = llvm.load %69 : !llvm.ptr -> i64
%94 = llvm.load %82 : !llvm.ptr -> i64
%95 = arith.muli %93, %94 : i64
%96 = arith.constant 4 : i32
%97 = arith.extsi %96 : i32 to i64
%92 = func.call @calloc(%95, %97) : (i64, i64) -> !llvm.ptr
%99 = arith.constant 256 : i32
%100 = arith.constant 4 : i32
%101 = arith.extsi %99 : i32 to i64
%102 = arith.extsi %100 : i32 to i64
%98 = func.call @calloc(%101, %102) : (i64, i64) -> !llvm.ptr
%104 = arith.constant 256 : i32
%105 = arith.constant 4 : i32
%106 = arith.extsi %104 : i32 to i64
%107 = arith.extsi %105 : i32 to i64
%103 = func.call @calloc(%106, %107) : (i64, i64) -> !llvm.ptr
%108 = arith.constant 1 : i32
%109 = arith.extsi %108 : i32 to i64
%110 = llvm.mlir.constant(1 : i64) : i64
%111 = llvm.alloca %110 x i64 : (i64) -> !llvm.ptr
llvm.store %109, %111 : i64, !llvm.ptr
%112 = arith.constant 0 : i32
%113 = llvm.load %69 : !llvm.ptr -> i64
%114 = arith.index_cast %112 : i32 to index
%115 = arith.index_cast %113 : i32 to index
%117 = arith.constant 1 : index
%118 = arith.constant -1 : index
%119 = arith.cmpi sle, %114, %115 : index
%116 = arith.select %119, %117, %118 : index
cf.br ^bb12(%114 : index)
^bb12(%120: index):
%121 = arith.cmpi slt, %120, %115 : index
%122 = arith.cmpi sgt, %120, %115 : index
%123 = arith.select %119, %121, %122 : i1
cf.cond_br %123, ^bb13(%120 : index), ^bb14(%120 : index)
^bb13(%124: index):
%125 = arith.constant 0 : i32
%126 = llvm.load %82 : !llvm.ptr -> i64
%127 = arith.index_cast %125 : i32 to index
%128 = arith.index_cast %126 : i32 to index
%130 = arith.constant 1 : index
%131 = arith.constant -1 : index
%132 = arith.cmpi sle, %127, %128 : index
%129 = arith.select %132, %130, %131 : index
cf.br ^bb15(%127 : index)
^bb15(%133: index):
%134 = arith.cmpi slt, %133, %128 : index
%135 = arith.cmpi sgt, %133, %128 : index
%136 = arith.select %132, %134, %135 : i1
cf.cond_br %136, ^bb16(%133 : index), ^bb17(%133 : index)
^bb16(%137: index):
%139 = arith.index_cast %124 : index to i64
%140 = arith.index_cast %137 : index to i64
%138 = func.call @ipow2_3(%139, %140) : (i64, i64) -> i64
%141 = arith.cmpi sle, %138, %65 : i64
cf.cond_br %141, ^bb18, ^bb19
^bb18:
%142 = llvm.load %111 : !llvm.ptr -> i64
%143 = arith.trunci %142 : i64 to i32
%144 = llvm.load %82 : !llvm.ptr -> i64
%146 = arith.index_cast %124 : index to i32
%147 = arith.trunci %144 : i64 to i32
%145 = arith.muli %146, %147 : i32
%149 = arith.index_cast %137 : index to i32
%148 = arith.addi %145, %149 : i32
%150 = arith.extsi %148 : i32 to i64
%151 = llvm.getelementptr %92[%150] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %143, %151 : i32, !llvm.ptr
%152 = arith.index_cast %124 : index to i32
%153 = llvm.load %111 : !llvm.ptr -> i64
%154 = llvm.getelementptr %98[%153] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %152, %154 : i32, !llvm.ptr
%155 = arith.index_cast %137 : index to i32
%156 = llvm.load %111 : !llvm.ptr -> i64
%157 = llvm.getelementptr %103[%156] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %155, %157 : i32, !llvm.ptr
%158 = llvm.load %111 : !llvm.ptr -> i64
%159 = arith.constant 1 : i32
%161 = arith.extsi %159 : i32 to i64
%160 = arith.addi %158, %161 : i64
llvm.store %160, %111 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%162 = arith.addi %137, %129 : index
cf.br ^bb15(%162 : index)
^bb17(%163: index):
%164 = arith.addi %124, %116 : index
cf.br ^bb12(%164 : index)
^bb14(%165: index):
%166 = arith.constant 1 : i32
%168 = arith.extsi %166 : i32 to i64
%167 = arith.addi %65, %168 : i64
%170 = llvm.load %111 : !llvm.ptr -> i64
%171 = arith.muli %170, %167 : i64
%172 = arith.constant 7 : i32
%174 = arith.extsi %172 : i32 to i64
%173 = arith.addi %171, %174 : i64
%175 = arith.constant 8 : i32
%177 = arith.extsi %175 : i32 to i64
%176 = arith.divsi %173, %177 : i64
%178 = arith.constant 1 : i32
%179 = arith.extsi %178 : i32 to i64
%169 = func.call @calloc(%176, %179) : (i64, i64) -> !llvm.ptr
%181 = llvm.load %111 : !llvm.ptr -> i64
%182 = arith.muli %181, %167 : i64
%183 = arith.constant 7 : i32
%185 = arith.extsi %183 : i32 to i64
%184 = arith.addi %182, %185 : i64
%186 = arith.constant 8 : i32
%188 = arith.extsi %186 : i32 to i64
%187 = arith.divsi %184, %188 : i64
%189 = arith.constant 1 : i32
%190 = arith.extsi %189 : i32 to i64
%180 = func.call @calloc(%187, %190) : (i64, i64) -> !llvm.ptr
%191 = arith.constant 1 : i32
%192 = llvm.load %111 : !llvm.ptr -> i64
%193 = arith.index_cast %191 : i32 to index
%194 = arith.index_cast %192 : i32 to index
%196 = arith.constant 1 : index
%197 = arith.constant -1 : index
%198 = arith.cmpi sle, %193, %194 : index
%195 = arith.select %198, %196, %197 : index
cf.br ^bb21(%193 : index)
^bb21(%199: index):
%200 = arith.cmpi slt, %199, %194 : index
%201 = arith.cmpi sgt, %199, %194 : index
%202 = arith.select %198, %200, %201 : i1
cf.cond_br %202, ^bb22(%199 : index), ^bb23(%199 : index)
^bb22(%203: index):
%206 = arith.index_cast %203 : index to i64
%207 = llvm.getelementptr %98[%206] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%205 = llvm.load %207 : !llvm.ptr -> i32
%208 = arith.extsi %205 : i32 to i64
%210 = arith.index_cast %203 : index to i64
%211 = llvm.getelementptr %103[%210] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%209 = llvm.load %211 : !llvm.ptr -> i32
%212 = arith.extsi %209 : i32 to i64
%204 = func.call @ipow2_3(%208, %212) : (i64, i64) -> i64
%215 = arith.index_cast %203 : index to i32
%216 = arith.trunci %167 : i64 to i32
%214 = arith.muli %215, %216 : i32
%217 = arith.extsi %214 : i32 to i64
%213 = func.call @bit_set(%169, %217, %204) : (!llvm.ptr, i64, i64) -> i32
%218 = arith.addi %203, %195 : index
cf.br ^bb21(%218 : index)
^bb23(%219: index):
%220 = arith.constant 1 : i32
%222 = arith.extsi %220 : i32 to i64
%221 = arith.shrsi %65, %222 : i64
%223 = arith.constant 1 : i32
%225 = arith.extsi %223 : i32 to i64
%224 = arith.addi %221, %225 : i64
%227 = arith.constant 1 : i32
%228 = arith.extsi %227 : i32 to i64
%226 = func.call @calloc(%224, %228) : (i64, i64) -> !llvm.ptr
%229 = arith.constant 0 : i32
%230 = arith.index_cast %229 : i32 to index
%231 = arith.index_cast %224 : i32 to index
%233 = arith.constant 1 : index
%234 = arith.constant -1 : index
%235 = arith.cmpi sle, %230, %231 : index
%232 = arith.select %235, %233, %234 : index
cf.br ^bb24(%230 : index)
^bb24(%236: index):
%237 = arith.cmpi slt, %236, %231 : index
%238 = arith.cmpi sgt, %236, %231 : index
%239 = arith.select %235, %237, %238 : i1
cf.cond_br %239, ^bb25(%236 : index), ^bb26(%236 : index)
^bb25(%240: index):
%241 = arith.constant 1 : i32
%242 = arith.trunci %241 : i32 to i8
%243 = arith.index_cast %240 : index to i64
%244 = llvm.getelementptr %226[%243] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %242, %244 : i8, !llvm.ptr
%245 = arith.addi %240, %232 : index
cf.br ^bb24(%245 : index)
^bb26(%246: index):
%247 = arith.constant 0 : i32
%248 = arith.constant 0 : i32
%249 = arith.trunci %247 : i32 to i8
%250 = arith.extsi %248 : i32 to i64
%251 = llvm.getelementptr %226[%250] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %249, %251 : i8, !llvm.ptr
%252 = arith.constant 1 : i32
%253 = arith.extsi %252 : i32 to i64
%254 = llvm.mlir.constant(1 : i64) : i64
%255 = llvm.alloca %254 x i64 : (i64) -> !llvm.ptr
llvm.store %253, %255 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%256 = arith.constant 2 : i32
%257 = llvm.load %255 : !llvm.ptr -> i64
%259 = arith.extsi %256 : i32 to i64
%258 = arith.muli %259, %257 : i64
%260 = llvm.load %255 : !llvm.ptr -> i64
%261 = arith.muli %258, %260 : i64
%262 = arith.cmpi slt, %261, %224 : i64
cf.cond_br %262, ^bb28, ^bb29
^bb28:
%264 = llvm.load %255 : !llvm.ptr -> i64
%265 = llvm.getelementptr %226[%264] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%263 = llvm.load %265 : !llvm.ptr -> i8
%266 = arith.constant 1 : i32
%268 = arith.extsi %263 : i8 to i32
%267 = arith.cmpi eq, %268, %266 : i32
cf.cond_br %267, ^bb30, ^bb31
^bb30:
%269 = arith.constant 2 : i32
%270 = llvm.load %255 : !llvm.ptr -> i64
%272 = arith.extsi %269 : i32 to i64
%271 = arith.muli %272, %270 : i64
%273 = arith.constant 1 : i32
%275 = arith.extsi %273 : i32 to i64
%274 = arith.addi %271, %275 : i64
%276 = arith.constant 3 : i32
%277 = llvm.load %255 : !llvm.ptr -> i64
%279 = arith.extsi %276 : i32 to i64
%278 = arith.muli %279, %277 : i64
%280 = arith.constant 1 : i32
%282 = arith.extsi %280 : i32 to i64
%281 = arith.addi %278, %282 : i64
%283 = arith.index_cast %281 : i32 to index
%284 = arith.index_cast %224 : i32 to index
%285 = arith.index_cast %274 : i32 to index
%286 = arith.constant 0 : index
%287 = arith.cmpi sgt, %285, %286 : index
cf.br ^bb33(%283 : index)
^bb33(%288: index):
%289 = arith.cmpi slt, %288, %284 : index
%290 = arith.cmpi sgt, %288, %284 : index
%291 = arith.select %287, %289, %290 : i1
cf.cond_br %291, ^bb34(%288 : index), ^bb35(%288 : index)
^bb34(%292: index):
%293 = arith.constant 0 : i32
%294 = arith.trunci %293 : i32 to i8
%295 = arith.index_cast %292 : index to i64
%296 = llvm.getelementptr %226[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %294, %296 : i8, !llvm.ptr
%297 = arith.addi %292, %285 : index
cf.br ^bb33(%297 : index)
^bb35(%298: index):
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%299 = llvm.load %255 : !llvm.ptr -> i64
%300 = arith.constant 1 : i32
%302 = arith.extsi %300 : i32 to i64
%301 = arith.addi %299, %302 : i64
llvm.store %301, %255 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%303 = arith.constant 0 : i32
%304 = arith.extsi %303 : i32 to i64
%305 = llvm.mlir.constant(1 : i64) : i64
%306 = llvm.alloca %305 x i64 : (i64) -> !llvm.ptr
llvm.store %304, %306 : i64, !llvm.ptr
%307 = arith.constant 1 : i32
%308 = arith.constant 1 : i32
%310 = arith.extsi %308 : i32 to i64
%309 = arith.addi %65, %310 : i64
%311 = arith.index_cast %307 : i32 to index
%312 = arith.index_cast %309 : i32 to index
%314 = arith.constant 1 : index
%315 = arith.constant -1 : index
%316 = arith.cmpi sle, %311, %312 : index
%313 = arith.select %316, %314, %315 : index
cf.br ^bb36(%311 : index)
^bb36(%317: index):
%318 = arith.cmpi slt, %317, %312 : index
%319 = arith.cmpi sgt, %317, %312 : index
%320 = arith.select %316, %318, %319 : i1
cf.cond_br %320, ^bb37(%317 : index), ^bb38(%317 : index)
^bb37(%321: index):
%322 = arith.constant 0 : i32
%323 = arith.extsi %322 : i32 to i64
%324 = llvm.mlir.constant(1 : i64) : i64
%325 = llvm.alloca %324 x i64 : (i64) -> !llvm.ptr
llvm.store %323, %325 : i64, !llvm.ptr
%326 = arith.constant 1 : i32
%327 = arith.extsi %326 : i32 to i64
%328 = llvm.mlir.constant(1 : i64) : i64
%329 = llvm.alloca %328 x i64 : (i64) -> !llvm.ptr
llvm.store %327, %329 : i64, !llvm.ptr
%330 = arith.constant 1 : i32
%331 = llvm.load %111 : !llvm.ptr -> i64
%332 = arith.index_cast %330 : i32 to index
%333 = arith.index_cast %331 : i32 to index
%335 = arith.constant 1 : index
%336 = arith.constant -1 : index
%337 = arith.cmpi sle, %332, %333 : index
%334 = arith.select %337, %335, %336 : index
cf.br ^bb39(%332 : index)
^bb39(%338: index):
%339 = arith.cmpi slt, %338, %333 : index
%340 = arith.cmpi sgt, %338, %333 : index
%341 = arith.select %337, %339, %340 : i1
cf.cond_br %341, ^bb40(%338 : index), ^bb41(%338 : index)
^bb40(%342: index):
%345 = arith.index_cast %342 : index to i32
%346 = arith.trunci %167 : i64 to i32
%344 = arith.muli %345, %346 : i32
%347 = arith.extsi %344 : i32 to i64
%348 = arith.index_cast %321 : index to i64
%343 = func.call @bit_get(%169, %347, %348) : (!llvm.ptr, i64, i64) -> i64
%349 = arith.constant 0 : i32
%351 = arith.extsi %349 : i32 to i64
%350 = arith.cmpi eq, %343, %351 : i64
cf.cond_br %350, ^bb42, ^bb43
^bb42:
%352 = arith.addi %342, %334 : index
cf.br ^bb39(%352 : index)
^bb43:
cf.br ^bb44
^bb44:
%353 = llvm.load %325 : !llvm.ptr -> i64
%354 = arith.constant 1 : i32
%356 = arith.extsi %354 : i32 to i64
%355 = arith.cmpi eq, %353, %356 : i64
%357 = scf.if %355 -> (i1) {
%358 = arith.constant true
scf.yield %358 : i1
} else {
%361 = arith.index_cast %342 : index to i32
%362 = arith.trunci %167 : i64 to i32
%360 = arith.muli %361, %362 : i32
%363 = arith.extsi %360 : i32 to i64
%364 = arith.index_cast %321 : index to i64
%359 = func.call @bit_get(%180, %363, %364) : (!llvm.ptr, i64, i64) -> i64
%365 = arith.constant 1 : i32
%367 = arith.extsi %365 : i32 to i64
%366 = arith.cmpi eq, %359, %367 : i64
scf.yield %366 : i1
}
cf.cond_br %357, ^bb45, ^bb46
^bb45:
%368 = arith.constant 0 : i32
%369 = arith.extsi %368 : i32 to i64
llvm.store %369, %329 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%370 = arith.constant 1 : i32
%371 = arith.extsi %370 : i32 to i64
llvm.store %371, %325 : i64, !llvm.ptr
%373 = arith.index_cast %342 : index to i64
%374 = llvm.getelementptr %98[%373] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%372 = llvm.load %374 : !llvm.ptr -> i32
%375 = arith.extsi %372 : i32 to i64
%377 = arith.index_cast %342 : index to i64
%378 = llvm.getelementptr %103[%377] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%376 = llvm.load %378 : !llvm.ptr -> i32
%379 = arith.extsi %376 : i32 to i64
%380 = arith.constant 1 : i32
%382 = arith.extsi %380 : i32 to i64
%381 = arith.addi %375, %382 : i64
%383 = llvm.load %69 : !llvm.ptr -> i64
%384 = arith.index_cast %381 : i32 to index
%385 = arith.index_cast %383 : i32 to index
%387 = arith.constant 1 : index
%388 = arith.constant -1 : index
%389 = arith.cmpi sle, %384, %385 : index
%386 = arith.select %389, %387, %388 : index
cf.br ^bb48(%384 : index)
^bb48(%390: index):
%391 = arith.cmpi slt, %390, %385 : index
%392 = arith.cmpi sgt, %390, %385 : index
%393 = arith.select %389, %391, %392 : i1
cf.cond_br %393, ^bb49(%390 : index), ^bb50(%390 : index)
^bb49(%394: index):
%395 = arith.constant 0 : i32
%396 = arith.extsi %395 : i32 to i64
%397 = llvm.mlir.constant(1 : i64) : i64
%398 = llvm.alloca %397 x i64 : (i64) -> !llvm.ptr
llvm.store %396, %398 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%399 = llvm.load %398 : !llvm.ptr -> i64
%400 = arith.cmpi slt, %399, %379 : i64
cf.cond_br %400, ^bb52, ^bb53
^bb52:
%402 = llvm.load %82 : !llvm.ptr -> i64
%404 = arith.index_cast %394 : index to i32
%405 = arith.trunci %402 : i64 to i32
%403 = arith.muli %404, %405 : i32
%406 = llvm.load %398 : !llvm.ptr -> i64
%408 = arith.extsi %403 : i32 to i64
%407 = arith.addi %408, %406 : i64
%409 = llvm.getelementptr %92[%407] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%401 = llvm.load %409 : !llvm.ptr -> i32
%410 = arith.extsi %401 : i32 to i64
%411 = arith.constant 0 : i32
%413 = arith.extsi %411 : i32 to i64
%412 = arith.cmpi eq, %410, %413 : i64
cf.cond_br %412, ^bb54, ^bb55
^bb54:
cf.br ^bb53
^bb55:
cf.br ^bb56
^bb56:
%415 = llvm.load %398 : !llvm.ptr -> i64
%416 = arith.index_cast %394 : index to i64
%414 = func.call @ipow2_3(%416, %415) : (i64, i64) -> i64
%418 = arith.index_cast %321 : index to i32
%419 = arith.trunci %414 : i64 to i32
%417 = arith.addi %418, %419 : i32
%420 = arith.extsi %417 : i32 to i64
%421 = arith.cmpi sgt, %420, %65 : i64
cf.cond_br %421, ^bb57, ^bb58
^bb57:
cf.br ^bb53
^bb58:
cf.br ^bb59
^bb59:
%423 = arith.muli %410, %167 : i64
%422 = func.call @bit_get(%169, %423, %420) : (!llvm.ptr, i64, i64) -> i64
%424 = arith.constant 1 : i32
%426 = arith.extsi %424 : i32 to i64
%425 = arith.cmpi eq, %422, %426 : i64
cf.cond_br %425, ^bb60, ^bb61
^bb60:
%428 = arith.muli %410, %167 : i64
%427 = func.call @bit_set(%180, %428, %420) : (!llvm.ptr, i64, i64) -> i32
cf.br ^bb62
^bb61:
%430 = arith.muli %410, %167 : i64
%429 = func.call @bit_set(%169, %430, %420) : (!llvm.ptr, i64, i64) -> i32
cf.br ^bb62
^bb62:
%431 = llvm.load %398 : !llvm.ptr -> i64
%432 = arith.constant 1 : i32
%434 = arith.extsi %432 : i32 to i64
%433 = arith.addi %431, %434 : i64
llvm.store %433, %398 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%435 = arith.addi %394, %386 : index
cf.br ^bb48(%435 : index)
^bb50(%436: index):
%437 = arith.addi %342, %334 : index
cf.br ^bb39(%437 : index)
^bb41(%438: index):
%439 = arith.constant 0 : i32
%440 = arith.extsi %439 : i32 to i64
%441 = llvm.mlir.constant(1 : i64) : i64
%442 = llvm.alloca %441 x i64 : (i64) -> !llvm.ptr
llvm.store %440, %442 : i64, !llvm.ptr
%443 = arith.constant 2 : i32
%445 = arith.index_cast %321 : index to i32
%444 = arith.cmpi eq, %445, %443 : i32
cf.cond_br %444, ^bb63, ^bb64
^bb63:
%446 = arith.constant 1 : i32
%447 = arith.extsi %446 : i32 to i64
llvm.store %447, %442 : i64, !llvm.ptr
cf.br ^bb65
^bb64:
%448 = arith.constant 1 : i32
%450 = arith.index_cast %321 : index to i32
%449 = arith.andi %450, %448 : i32
%451 = arith.constant 1 : i32
%452 = arith.cmpi eq, %449, %451 : i32
%453 = scf.if %452 -> (i1) {
%455 = arith.constant 1 : i32
%457 = arith.index_cast %321 : index to i32
%456 = arith.shrsi %457, %455 : i32
%458 = arith.extsi %456 : i32 to i64
%459 = llvm.getelementptr %226[%458] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%454 = llvm.load %459 : !llvm.ptr -> i8
%460 = arith.constant 1 : i32
%462 = arith.extsi %454 : i8 to i32
%461 = arith.cmpi eq, %462, %460 : i32
scf.yield %461 : i1
} else {
%463 = arith.constant false
scf.yield %463 : i1
}
cf.cond_br %453, ^bb66, ^bb65
^bb66:
%464 = arith.constant 1 : i32
%465 = arith.extsi %464 : i32 to i64
llvm.store %465, %442 : i64, !llvm.ptr
cf.br ^bb65
^bb65:
%466 = llvm.load %325 : !llvm.ptr -> i64
%467 = arith.constant 1 : i32
%469 = arith.extsi %467 : i32 to i64
%468 = arith.cmpi eq, %466, %469 : i64
%470 = scf.if %468 -> (i1) {
%471 = llvm.load %329 : !llvm.ptr -> i64
%472 = arith.constant 1 : i32
%474 = arith.extsi %472 : i32 to i64
%473 = arith.cmpi eq, %471, %474 : i64
scf.yield %473 : i1
} else {
%475 = arith.constant false
scf.yield %475 : i1
}
%476 = scf.if %470 -> (i1) {
%477 = llvm.load %442 : !llvm.ptr -> i64
%478 = arith.constant 1 : i32
%480 = arith.extsi %478 : i32 to i64
%479 = arith.cmpi eq, %477, %480 : i64
scf.yield %479 : i1
} else {
%481 = arith.constant false
scf.yield %481 : i1
}
cf.cond_br %476, ^bb67, ^bb68
^bb67:
%482 = llvm.load %306 : !llvm.ptr -> i64
%484 = arith.trunci %482 : i64 to i32
%485 = arith.index_cast %321 : index to i32
%483 = arith.addi %484, %485 : i32
%486 = arith.extsi %483 : i32 to i64
llvm.store %486, %306 : i64, !llvm.ptr
cf.br ^bb69
^bb68:
cf.br ^bb69
^bb69:
%487 = arith.addi %321, %313 : index
cf.br ^bb36(%487 : index)
^bb38(%488: index):
%489 = llvm.mlir.addressof @str_0 : !llvm.ptr
%490 = llvm.load %306 : !llvm.ptr -> i64
%491 = llvm.call @printf(%489, %490) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%92) : (!llvm.ptr) -> ()
func.call @free(%98) : (!llvm.ptr) -> ()
func.call @free(%103) : (!llvm.ptr) -> ()
func.call @free(%169) : (!llvm.ptr) -> ()
func.call @free(%180) : (!llvm.ptr) -> ()
func.call @free(%226) : (!llvm.ptr) -> ()
%498 = arith.constant 0 : i32
func.return %498 : i32
}
}