Problem 637
g(10^7, 10, 3) = sum of n where f(n,10) == f(n,3). f(n,B) = minimum steps to reduce n to single digit by partitioning digits.
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 637: Flexible Digit Sum
# g(10^7, 10, 3) = sum of n where f(n,10) == f(n,3).
# f(n,B) = minimum steps to reduce n to single digit by partitioning digits.
import euler.nt { isqrt }
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MAX_LEN10: i64 = 8
const MAX_LEN3: i64 = 15
# Digit sum tables
let mut g_ds10: ptr<i32> = null
let mut g_ds3: ptr<i32> = null
# Powers
let mut g_pow10: ptr<i64> = null
let mut g_pow3: ptr<i64> = null
# Blocks: for each length, list of partitions (start, len, start, len, ...)
# Stored as flat arrays: blocks10_start[len][idx], blocks10_len[len][idx], blocks10_count[len]
let mut g_blocks10_start: ptr<i64> = null
let mut g_blocks10_len: ptr<i64> = null
let mut g_blocks10_count: ptr<i64> = null
let mut g_blocks3_start: ptr<i64> = null
let mut g_blocks3_len: ptr<i64> = null
let mut g_blocks3_count: ptr<i64> = null
# Precomputed blocks for each length: blocks[len] = list of (start, len) pairs
# Max partitions for length L = 2^(L-1). For L=8, that's 128 partitions.
# Each partition has up to L pairs. Total storage: 128 * 8 * 2 = 2048 entries per length.
# For 8 lengths: 16384 entries. For base 3: 15 lengths, 2^14=16384 partitions * 15 * 2 = 491520 entries.
# Let's use a simpler approach: store blocks as bitmasks and compute partitions on the fly.
# For each length L, iterate over all 2^(L-1) masks in order of decreasing popcount.
function popcount(x: i64) -> i64 {
let mut v: i64 = x
let mut c: i64 = 0
while v > 0 {
c = c + 1
v = v & (v - 1)
}
return c
}
# For a given mask and length, compute the partition sum using prefix values
function partition_sum(prefix: ptr<i64>, mask: i64, length: i64, base_pow: ptr<i64>) -> i64 {
let mut s: i64 = 0
let mut start: i64 = 0
let mut i: i64 = 0
while i < length - 1 {
if ((mask >> (length - 2 - i)) & 1) == 1 {
let ln: i64 = i - start + 1
s = s + prefix[start + ln] - prefix[start] * base_pow[ln]
start = i + 1
}
i = i + 1
}
let ln: i64 = length - start
s = s + prefix[start + ln] - prefix[start] * base_pow[ln]
return s
}
# Sort masks by popcount descending using simple counting sort
function sort_masks_by_popcount(masks: ptr<i64>, count: i64) -> void {
# Counting sort by popcount, descending order
let buckets: ptr<i64> = calloc(64, 8)
for i in 0..count {
let pc: i64 = popcount(masks[i])
buckets[pc] = buckets[pc] + 1
}
# Compute offsets in descending popcount order
let offsets: ptr<i64> = calloc(64, 8)
let mut pos: i64 = 0
let mut pc: i64 = 63
while pc >= 0 {
offsets[pc] = pos
pos = pos + buckets[pc]
pc = pc - 1
}
let output: ptr<i64> = calloc(count, 8)
for i in 0..count {
let pc: i64 = popcount(masks[i])
output[offsets[pc]] = masks[i]
offsets[pc] = offsets[pc] + 1
}
for i in 0..count { masks[i] = output[i] }
free(output)
free(offsets)
free(buckets)
}
# Precompute sorted masks for each length
let mut g_sorted_masks10: ptr<i64> = null # [len * 128]
let mut g_mask_count10: ptr<i64> = null # [len]
let mut g_sorted_masks3: ptr<i64> = null # [len * 16384]
let mut g_mask_count3: ptr<i64> = null # [len]
function precompute_masks() -> void {
# Base 10: lengths 2..8
g_sorted_masks10 = calloc(9 * 128, 8)
g_mask_count10 = calloc(9, 8)
for length in 2..9 {
let count: i64 = 1 << (length - 1)
let base: i64 = length * 128
for m in 0..count {
g_sorted_masks10[base + m] = m
}
sort_masks_by_popcount(g_sorted_masks10 + base, count)
g_mask_count10[length] = count
}
# Base 3: lengths 2..15
g_sorted_masks3 = calloc(16 * 16384, 8)
g_mask_count3 = calloc(16, 8)
for length in 2..16 {
let count: i64 = 1 << (length - 1)
let base: i64 = length * 16384
for m in 0..count {
g_sorted_masks3[base + m] = m
}
sort_masks_by_popcount(g_sorted_masks3 + base, count)
g_mask_count3[length] = count
}
}
function main() -> i32 {
let limit: i64 = 10000000
# Digit sum tables
g_ds10 = calloc(limit + 1, 4)
g_ds3 = calloc(limit + 1, 4)
for i in 1..(limit + 1) {
g_ds10[i] = g_ds10[i / 10] + (i % 10) as i32
g_ds3[i] = g_ds3[i / 3] + (i % 3) as i32
}
# Powers
g_pow10 = calloc(9, 8)
g_pow3 = calloc(16, 8)
g_pow10[0] = 1
for i in 0..8 { g_pow10[i + 1] = g_pow10[i] * 10 }
g_pow3[0] = 1
for i in 0..15 { g_pow3[i + 1] = g_pow3[i] * 3 }
# Precompute sorted masks
precompute_masks()
# Iterate over all n from 1 to limit
let digits10: ptr<i64> = calloc(8, 8)
let digits3: ptr<i64> = calloc(15, 8)
let prefix10: ptr<i64> = calloc(9, 8)
let prefix3: ptr<i64> = calloc(16, 8)
let mut len10: i64 = 1
let mut len3: i64 = 1
let mut sum10: i64 = 0
let mut sum3: i64 = 0
let mut total: i64 = 0
for n in 1..(limit + 1) {
# Increment base-10 digits
let mut i: i64 = 0
while i < len10 && digits10[i] == 9 {
sum10 = sum10 - 9
digits10[i] = 0
i = i + 1
}
if i == len10 {
digits10[i] = 1
len10 = len10 + 1
sum10 = sum10 + 1
} else {
digits10[i] = digits10[i] + 1
sum10 = sum10 + 1
}
# Increment base-3 digits
i = 0
while i < len3 && digits3[i] == 2 {
sum3 = sum3 - 2
digits3[i] = 0
i = i + 1
}
if i == len3 {
digits3[i] = 1
len3 = len3 + 1
sum3 = sum3 + 1
} else {
digits3[i] = digits3[i] + 1
sum3 = sum3 + 1
}
# Compute f10
let f10: i64
if len10 == 1 {
f10 = 0
} else { if sum10 < 10 {
f10 = 1
} else {
# Build prefix values (MSD first)
let mut p: i64 = 0
prefix10[0] = 0
let mut pos: i64 = 0
let mut idx: i64 = len10 - 1
while idx >= 0 {
p = p * 10 + digits10[idx]
pos = pos + 1
prefix10[pos] = p
idx = idx - 1
}
let mut good: i64 = 0
let base: i64 = len10 * 128
for mi in 0..g_mask_count10[len10] {
let mask: i64 = g_sorted_masks10[base + mi]
let s: i64 = partition_sum(prefix10, mask, len10, g_pow10)
if (g_ds10[s] as i64) < 10 {
good = 1
break
}
}
if good == 1 { f10 = 2 } else { f10 = 3 }
} }
# Compute f3
let f3: i64
if len3 == 1 {
f3 = 0
} else { if sum3 < 3 {
f3 = 1
} else {
let mut p: i64 = 0
prefix3[0] = 0
let mut pos: i64 = 0
let mut idx: i64 = len3 - 1
while idx >= 0 {
p = p * 3 + digits3[idx]
pos = pos + 1
prefix3[pos] = p
idx = idx - 1
}
let mut good: i64 = 0
let base: i64 = len3 * 16384
for mi in 0..g_mask_count3[len3] {
let mask: i64 = g_sorted_masks3[base + mi]
let s: i64 = partition_sum(prefix3, mask, len3, g_pow3)
if (g_ds3[s] as i64) < 3 {
good = 1
break
}
}
if good == 1 { f3 = 2 } else { f3 = 3 }
} }
if f10 == f3 {
total = total + n
}
}
printf("%lld\n", total)
free(prefix3)
free(prefix10)
free(digits3)
free(digits10)
free(g_mask_count3)
free(g_sorted_masks3)
free(g_mask_count10)
free(g_sorted_masks10)
free(g_pow3)
free(g_pow10)
free(g_ds3)
free(g_ds10)
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 gcd_i64_i64(int64_t a0, int64_t b0);
int64_t lcm_i64_i64(int64_t a, int64_t b);
int64_t isqrt_i64(int64_t n);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
bool is_prime_i64(int64_t n);
int64_t popcount_i64(int64_t x);
int64_t partition_sum_ptr_i64_i64_i64_ptr_i64(int64_t* prefix, int64_t mask, int64_t length, int64_t* base_pow);
void sort_masks_by_popcount_ptr_i64_i64(int64_t* masks, int64_t count);
void precompute_masks(void);
int32_t main(void);
static const int64_t MAX_LEN10 = 8;
static const int64_t MAX_LEN3 = 15;
/* Module statics */
static int32_t* g_ds10 = NULL;
static int32_t* g_ds3 = NULL;
static int64_t* g_pow10 = NULL;
static int64_t* g_pow3 = NULL;
static int64_t* g_blocks10_start = NULL;
static int64_t* g_blocks10_len = NULL;
static int64_t* g_blocks10_count = NULL;
static int64_t* g_blocks3_start = NULL;
static int64_t* g_blocks3_len = NULL;
static int64_t* g_blocks3_count = NULL;
static int64_t* g_sorted_masks10 = NULL;
static int64_t* g_mask_count10 = NULL;
static int64_t* g_sorted_masks3 = NULL;
static int64_t* g_mask_count3 = NULL;
int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t lcm_i64_i64(int64_t a, int64_t b) {
if ((a == 0 || b == 0)) {
return 0;
}
return (FLOW_CHECKED_DIV((a), (gcd_i64_i64(a, b))) * b);
}
int64_t isqrt_i64(int64_t n) {
if (n < 2) {
return n;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod) {
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
int64_t b = FLOW_CHECKED_MOD((b0), (mod));
int64_t result = 0;
while (b > 0) {
if (FLOW_CHECKED_MOD((b), (2)) == 1) {
result = FLOW_CHECKED_MOD(((result + a)), (mod));
}
a = FLOW_CHECKED_MOD(((a * 2)), (mod));
b = FLOW_CHECKED_DIV((b), (2));
}
return result;
}
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
if (mod == 1) {
return 0;
}
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (mod));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mulmod_i64_i64_i64(result, b, mod);
}
b = mulmod_i64_i64_i64(b, b, mod);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
bool is_prime_i64(int64_t n) {
if (n < 2) {
return 0;
}
if (n < 4) {
return 1;
}
if ((FLOW_CHECKED_MOD((n), (2)) == 0 || FLOW_CHECKED_MOD((n), (3)) == 0)) {
return 0;
}
int64_t i = 5;
while ((i * i) <= n) {
if ((FLOW_CHECKED_MOD((n), (i)) == 0 || FLOW_CHECKED_MOD((n), ((i + 2))) == 0)) {
return 0;
}
i = (i + 6);
}
return 1;
}
int64_t popcount_i64(int64_t x) {
int64_t v = x;
int64_t c = 0;
while (v > 0) {
c = (c + 1);
v = (v & (v - 1));
}
return c;
}
int64_t partition_sum_ptr_i64_i64_i64_ptr_i64(int64_t* prefix, int64_t mask, int64_t length, int64_t* base_pow) {
int64_t s = 0;
int64_t start = 0;
int64_t i = 0;
while (i < (length - 1)) {
if ((FLOW_CHECKED_SHR((mask), (((length - 2) - i))) & 1) == 1) {
int64_t ln = ((i - start) + 1);
s = ((s + prefix[(start + ln)]) - (prefix[start] * base_pow[ln]));
start = (i + 1);
}
i = (i + 1);
}
int64_t ln = (length - start);
s = ((s + prefix[(start + ln)]) - (prefix[start] * base_pow[ln]));
return s;
}
void sort_masks_by_popcount_ptr_i64_i64(int64_t* masks, int64_t count) {
int64_t* buckets = (int64_t*)(calloc(64, 8));
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= count) ? i < count : i > count; i += (0 <= count) ? 1 : -1) {
int64_t pc = popcount_i64(masks[i]);
buckets[pc] = (buckets[pc] + 1);
}
int64_t* offsets = (int64_t*)(calloc(64, 8));
int64_t pos = 0;
int64_t pc = 63;
while (pc >= 0) {
offsets[pc] = pos;
pos = (pos + buckets[pc]);
pc = (pc - 1);
}
int64_t* output = (int64_t*)(calloc(count, 8));
int32_t __flow_step_2 = 1;
for (int32_t i = 0; (0 <= count) ? i < count : i > count; i += (0 <= count) ? 1 : -1) {
int64_t pc = popcount_i64(masks[i]);
output[offsets[pc]] = masks[i];
offsets[pc] = (offsets[pc] + 1);
}
int32_t __flow_step_3 = 1;
for (int32_t i = 0; (0 <= count) ? i < count : i > count; i += (0 <= count) ? 1 : -1) {
masks[i] = output[i];
}
free(output);
free(offsets);
free(buckets);
}
void precompute_masks(void) {
g_sorted_masks10 = calloc((9 * 128), 8);
g_mask_count10 = calloc(9, 8);
int32_t __flow_step_4 = 1;
for (int32_t length = 2; (2 <= 9) ? length < 9 : length > 9; length += (2 <= 9) ? 1 : -1) {
int64_t count = FLOW_CHECKED_SHL((1), ((length - 1)));
int64_t base = (length * 128);
int32_t __flow_step_5 = 1;
for (int32_t m = 0; (0 <= count) ? m < count : m > count; m += (0 <= count) ? 1 : -1) {
g_sorted_masks10[(base + m)] = m;
}
sort_masks_by_popcount_ptr_i64_i64((g_sorted_masks10 + base), count);
g_mask_count10[length] = count;
}
g_sorted_masks3 = calloc((16 * 16384), 8);
g_mask_count3 = calloc(16, 8);
int32_t __flow_step_6 = 1;
for (int32_t length = 2; (2 <= 16) ? length < 16 : length > 16; length += (2 <= 16) ? 1 : -1) {
int64_t count = FLOW_CHECKED_SHL((1), ((length - 1)));
int64_t base = (length * 16384);
int32_t __flow_step_7 = 1;
for (int32_t m = 0; (0 <= count) ? m < count : m > count; m += (0 <= count) ? 1 : -1) {
g_sorted_masks3[(base + m)] = m;
}
sort_masks_by_popcount_ptr_i64_i64((g_sorted_masks3 + base), count);
g_mask_count3[length] = count;
}
}
int32_t main(void) {
int64_t limit = 10000000;
g_ds10 = calloc((limit + 1), 4);
g_ds3 = calloc((limit + 1), 4);
int32_t __flow_step_8 = 1;
for (int32_t i = 1; (1 <= (limit + 1)) ? i < (limit + 1) : i > (limit + 1); i += (1 <= (limit + 1)) ? 1 : -1) {
g_ds10[i] = (g_ds10[FLOW_CHECKED_DIV((i), (10))] + ((int32_t)(FLOW_CHECKED_MOD((i), (10)))));
g_ds3[i] = (g_ds3[FLOW_CHECKED_DIV((i), (3))] + ((int32_t)(FLOW_CHECKED_MOD((i), (3)))));
}
g_pow10 = calloc(9, 8);
g_pow3 = calloc(16, 8);
g_pow10[0] = 1;
int32_t __flow_step_9 = 1;
for (int32_t i = 0; (0 <= 8) ? i < 8 : i > 8; i += (0 <= 8) ? 1 : -1) {
g_pow10[(i + 1)] = (g_pow10[i] * 10);
}
g_pow3[0] = 1;
int32_t __flow_step_10 = 1;
for (int32_t i = 0; (0 <= 15) ? i < 15 : i > 15; i += (0 <= 15) ? 1 : -1) {
g_pow3[(i + 1)] = (g_pow3[i] * 3);
}
precompute_masks();
int64_t* digits10 = (int64_t*)(calloc(8, 8));
int64_t* digits3 = (int64_t*)(calloc(15, 8));
int64_t* prefix10 = (int64_t*)(calloc(9, 8));
int64_t* prefix3 = (int64_t*)(calloc(16, 8));
int64_t len10 = 1;
int64_t len3 = 1;
int64_t sum10 = 0;
int64_t sum3 = 0;
int64_t total = 0;
int32_t __flow_step_11 = 1;
for (int32_t n = 1; (1 <= (limit + 1)) ? n < (limit + 1) : n > (limit + 1); n += (1 <= (limit + 1)) ? 1 : -1) {
int64_t i = 0;
while ((i < len10 && digits10[i] == 9)) {
sum10 = (sum10 - 9);
digits10[i] = 0;
i = (i + 1);
}
if (i == len10) {
digits10[i] = 1;
len10 = (len10 + 1);
sum10 = (sum10 + 1);
} else {
digits10[i] = (digits10[i] + 1);
sum10 = (sum10 + 1);
}
i = 0;
while ((i < len3 && digits3[i] == 2)) {
sum3 = (sum3 - 2);
digits3[i] = 0;
i = (i + 1);
}
if (i == len3) {
digits3[i] = 1;
len3 = (len3 + 1);
sum3 = (sum3 + 1);
} else {
digits3[i] = (digits3[i] + 1);
sum3 = (sum3 + 1);
}
int64_t f10;
if (len10 == 1) {
f10 = 0;
} else {
if (sum10 < 10) {
f10 = 1;
} else {
int64_t p = 0;
prefix10[0] = 0;
int64_t pos = 0;
int64_t idx = (len10 - 1);
while (idx >= 0) {
p = ((p * 10) + digits10[idx]);
pos = (pos + 1);
prefix10[pos] = p;
idx = (idx - 1);
}
int64_t good = 0;
int64_t base = (len10 * 128);
int32_t __flow_step_12 = 1;
for (int32_t mi = 0; (0 <= g_mask_count10[len10]) ? mi < g_mask_count10[len10] : mi > g_mask_count10[len10]; mi += (0 <= g_mask_count10[len10]) ? 1 : -1) {
int64_t mask = g_sorted_masks10[(base + mi)];
int64_t s = partition_sum_ptr_i64_i64_i64_ptr_i64(prefix10, mask, len10, g_pow10);
if (((int64_t)(g_ds10[s])) < 10) {
good = 1;
break;
}
}
if (good == 1) {
f10 = 2;
} else {
f10 = 3;
}
}
}
int64_t f3;
if (len3 == 1) {
f3 = 0;
} else {
if (sum3 < 3) {
f3 = 1;
} else {
int64_t p = 0;
prefix3[0] = 0;
int64_t pos = 0;
int64_t idx = (len3 - 1);
while (idx >= 0) {
p = ((p * 3) + digits3[idx]);
pos = (pos + 1);
prefix3[pos] = p;
idx = (idx - 1);
}
int64_t good = 0;
int64_t base = (len3 * 16384);
int32_t __flow_step_13 = 1;
for (int32_t mi = 0; (0 <= g_mask_count3[len3]) ? mi < g_mask_count3[len3] : mi > g_mask_count3[len3]; mi += (0 <= g_mask_count3[len3]) ? 1 : -1) {
int64_t mask = g_sorted_masks3[(base + mi)];
int64_t s = partition_sum_ptr_i64_i64_i64_ptr_i64(prefix3, mask, len3, g_pow3);
if (((int64_t)(g_ds3[s])) < 3) {
good = 1;
break;
}
}
if (good == 1) {
f3 = 2;
} else {
f3 = 3;
}
}
}
if (f10 == f3) {
total = (total + n);
}
}
printf("%lld\n", total);
free(prefix3);
free(prefix10);
free(digits3);
free(digits10);
free(g_mask_count3);
free(g_sorted_masks3);
free(g_mask_count10);
free(g_sorted_masks10);
free(g_pow3);
free(g_pow10);
free(g_ds3);
free(g_ds10);
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 @gcd(%arg0: i64, %arg1: i64) -> i64 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%4 = llvm.load %3 : !llvm.ptr -> i64
%5 = arith.constant 0 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi ne, %4, %7 : i64
cf.cond_br %6, ^bb1, ^bb2
^bb1:
%8 = llvm.load %1 : !llvm.ptr -> i64
%9 = llvm.load %3 : !llvm.ptr -> i64
%10 = arith.remsi %8, %9 : i64
%11 = llvm.load %3 : !llvm.ptr -> i64
llvm.store %11, %1 : i64, !llvm.ptr
llvm.store %10, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%12 = llvm.load %1 : !llvm.ptr -> i64
func.return %12 : i64
}
func.func @lcm(%arg0: i64, %arg1: i64) -> i64 {
%13 = arith.constant 0 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.cmpi eq, %arg0, %15 : i64
%16 = scf.if %14 -> (i1) {
%17 = arith.constant true
scf.yield %17 : i1
} else {
%18 = arith.constant 0 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.cmpi eq, %arg1, %20 : i64
scf.yield %19 : i1
}
cf.cond_br %16, ^bb3, ^bb4
^bb3:
%21 = arith.constant 0 : i32
%22 = arith.extsi %21 : i32 to i64
func.return %22 : i64
^bb4:
cf.br ^bb5
^bb5:
%23 = func.call @gcd(%arg0, %arg1) : (i64, i64) -> i64
%24 = arith.divsi %arg0, %23 : i64
%25 = arith.muli %24, %arg1 : i64
func.return %25 : i64
}
func.func @isqrt(%arg0: i64) -> i64 {
%26 = arith.constant 2 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.cmpi slt, %arg0, %28 : i64
cf.cond_br %27, ^bb6, ^bb7
^bb6:
func.return %arg0 : i64
^bb7:
cf.br ^bb8
^bb8:
%29 = llvm.mlir.constant(1 : i64) : i64
%30 = llvm.alloca %29 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %30 : i64, !llvm.ptr
%31 = llvm.load %30 : !llvm.ptr -> i64
%32 = arith.constant 1 : i32
%34 = arith.extsi %32 : i32 to i64
%33 = arith.addi %31, %34 : i64
%35 = arith.constant 2 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.divsi %33, %37 : i64
%38 = llvm.mlir.constant(1 : i64) : i64
%39 = llvm.alloca %38 x i64 : (i64) -> !llvm.ptr
llvm.store %36, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%40 = llvm.load %39 : !llvm.ptr -> i64
%41 = llvm.load %30 : !llvm.ptr -> i64
%42 = arith.cmpi slt, %40, %41 : i64
cf.cond_br %42, ^bb10, ^bb11
^bb10:
%43 = llvm.load %39 : !llvm.ptr -> i64
llvm.store %43, %30 : i64, !llvm.ptr
%44 = llvm.load %30 : !llvm.ptr -> i64
%45 = llvm.load %30 : !llvm.ptr -> i64
%46 = arith.divsi %arg0, %45 : i64
%47 = arith.addi %44, %46 : i64
%48 = arith.constant 2 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.divsi %47, %50 : i64
llvm.store %49, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%51 = llvm.load %30 : !llvm.ptr -> i64
func.return %51 : i64
}
func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%52 = arith.remsi %arg0, %arg2 : 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 = arith.remsi %arg1, %arg2 : i64
%56 = llvm.mlir.constant(1 : i64) : i64
%57 = llvm.alloca %56 x i64 : (i64) -> !llvm.ptr
llvm.store %55, %57 : i64, !llvm.ptr
%58 = arith.constant 0 : i32
%59 = arith.extsi %58 : i32 to i64
%60 = llvm.mlir.constant(1 : i64) : i64
%61 = llvm.alloca %60 x i64 : (i64) -> !llvm.ptr
llvm.store %59, %61 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%62 = llvm.load %57 : !llvm.ptr -> i64
%63 = arith.constant 0 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.cmpi sgt, %62, %65 : i64
cf.cond_br %64, ^bb13, ^bb14
^bb13:
%66 = llvm.load %57 : !llvm.ptr -> i64
%67 = arith.constant 2 : i32
%69 = arith.extsi %67 : i32 to i64
%68 = arith.remsi %66, %69 : i64
%70 = arith.constant 1 : i32
%72 = arith.extsi %70 : i32 to i64
%71 = arith.cmpi eq, %68, %72 : i64
cf.cond_br %71, ^bb15, ^bb16
^bb15:
%73 = llvm.load %61 : !llvm.ptr -> i64
%74 = llvm.load %54 : !llvm.ptr -> i64
%75 = arith.addi %73, %74 : i64
%76 = arith.remsi %75, %arg2 : i64
llvm.store %76, %61 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%77 = llvm.load %54 : !llvm.ptr -> i64
%78 = arith.constant 2 : i32
%80 = arith.extsi %78 : i32 to i64
%79 = arith.muli %77, %80 : i64
%81 = arith.remsi %79, %arg2 : i64
llvm.store %81, %54 : i64, !llvm.ptr
%82 = llvm.load %57 : !llvm.ptr -> i64
%83 = arith.constant 2 : i32
%85 = arith.extsi %83 : i32 to i64
%84 = arith.divsi %82, %85 : i64
llvm.store %84, %57 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%86 = llvm.load %61 : !llvm.ptr -> i64
func.return %86 : i64
}
func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%87 = arith.constant 1 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.cmpi eq, %arg2, %89 : i64
cf.cond_br %88, ^bb18, ^bb19
^bb18:
%90 = arith.constant 0 : i32
%91 = arith.extsi %90 : i32 to i64
func.return %91 : i64
^bb19:
cf.br ^bb20
^bb20:
%92 = arith.constant 1 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i64, !llvm.ptr
%96 = arith.remsi %arg0, %arg2 : i64
%97 = llvm.mlir.constant(1 : i64) : i64
%98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
llvm.store %96, %98 : i64, !llvm.ptr
%99 = llvm.mlir.constant(1 : i64) : i64
%100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%101 = llvm.load %100 : !llvm.ptr -> i64
%102 = arith.constant 0 : i32
%104 = arith.extsi %102 : i32 to i64
%103 = arith.cmpi sgt, %101, %104 : i64
cf.cond_br %103, ^bb22, ^bb23
^bb22:
%105 = llvm.load %100 : !llvm.ptr -> i64
%106 = arith.constant 2 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.remsi %105, %108 : i64
%109 = arith.constant 1 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.cmpi eq, %107, %111 : i64
cf.cond_br %110, ^bb24, ^bb25
^bb24:
%113 = llvm.load %95 : !llvm.ptr -> i64
%114 = llvm.load %98 : !llvm.ptr -> i64
%112 = func.call @mulmod(%113, %114, %arg2) : (i64, i64, i64) -> i64
llvm.store %112, %95 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%116 = llvm.load %98 : !llvm.ptr -> i64
%117 = llvm.load %98 : !llvm.ptr -> i64
%115 = func.call @mulmod(%116, %117, %arg2) : (i64, i64, i64) -> i64
llvm.store %115, %98 : i64, !llvm.ptr
%118 = llvm.load %100 : !llvm.ptr -> i64
%119 = arith.constant 2 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.divsi %118, %121 : i64
llvm.store %120, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%122 = llvm.load %95 : !llvm.ptr -> i64
func.return %122 : i64
}
func.func @is_prime(%arg0: i64) -> i1 {
%123 = arith.constant 2 : i32
%125 = arith.extsi %123 : i32 to i64
%124 = arith.cmpi slt, %arg0, %125 : i64
cf.cond_br %124, ^bb27, ^bb28
^bb27:
%126 = arith.constant 0 : i1
func.return %126 : i1
^bb28:
cf.br ^bb29
^bb29:
%127 = arith.constant 4 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.cmpi slt, %arg0, %129 : i64
cf.cond_br %128, ^bb30, ^bb31
^bb30:
%130 = arith.constant 1 : i1
func.return %130 : i1
^bb31:
cf.br ^bb32
^bb32:
%131 = arith.constant 2 : i32
%133 = arith.extsi %131 : i32 to i64
%132 = arith.remsi %arg0, %133 : i64
%134 = arith.constant 0 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.cmpi eq, %132, %136 : i64
%137 = scf.if %135 -> (i1) {
%138 = arith.constant true
scf.yield %138 : i1
} else {
%139 = arith.constant 3 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.remsi %arg0, %141 : i64
%142 = arith.constant 0 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.cmpi eq, %140, %144 : i64
scf.yield %143 : i1
}
cf.cond_br %137, ^bb33, ^bb34
^bb33:
%145 = arith.constant 0 : i1
func.return %145 : i1
^bb34:
cf.br ^bb35
^bb35:
%146 = arith.constant 5 : i32
%147 = arith.extsi %146 : i32 to i64
%148 = llvm.mlir.constant(1 : i64) : i64
%149 = llvm.alloca %148 x i64 : (i64) -> !llvm.ptr
llvm.store %147, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.load %149 : !llvm.ptr -> i64
%152 = arith.muli %150, %151 : i64
%153 = arith.cmpi sle, %152, %arg0 : i64
cf.cond_br %153, ^bb37, ^bb38
^bb37:
%154 = llvm.load %149 : !llvm.ptr -> i64
%155 = arith.remsi %arg0, %154 : i64
%156 = arith.constant 0 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.cmpi eq, %155, %158 : i64
%159 = scf.if %157 -> (i1) {
%160 = arith.constant true
scf.yield %160 : i1
} else {
%161 = llvm.load %149 : !llvm.ptr -> i64
%162 = arith.constant 2 : i32
%164 = arith.extsi %162 : i32 to i64
%163 = arith.addi %161, %164 : i64
%165 = arith.remsi %arg0, %163 : i64
%166 = arith.constant 0 : i32
%168 = arith.extsi %166 : i32 to i64
%167 = arith.cmpi eq, %165, %168 : i64
scf.yield %167 : i1
}
cf.cond_br %159, ^bb39, ^bb40
^bb39:
%169 = arith.constant 0 : i1
func.return %169 : i1
^bb40:
cf.br ^bb41
^bb41:
%170 = llvm.load %149 : !llvm.ptr -> i64
%171 = arith.constant 6 : i32
%173 = arith.extsi %171 : i32 to i64
%172 = arith.addi %170, %173 : i64
llvm.store %172, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%174 = arith.constant 1 : i1
func.return %174 : i1
}
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MAX_LEN10
llvm.mlir.global internal constant @MAX_LEN10(8 : i64) : i64
// Constant: MAX_LEN3
llvm.mlir.global internal constant @MAX_LEN3(15 : i64) : i64
// Module static: g_ds10
llvm.mlir.global internal @g_ds10() {addr_space = 0 : i32} : !llvm.ptr {
%175 = llvm.mlir.zero : !llvm.ptr
llvm.return %175 : !llvm.ptr
}
// Module static: g_ds3
llvm.mlir.global internal @g_ds3() {addr_space = 0 : i32} : !llvm.ptr {
%176 = llvm.mlir.zero : !llvm.ptr
llvm.return %176 : !llvm.ptr
}
// Module static: g_pow10
llvm.mlir.global internal @g_pow10() {addr_space = 0 : i32} : !llvm.ptr {
%177 = llvm.mlir.zero : !llvm.ptr
llvm.return %177 : !llvm.ptr
}
// Module static: g_pow3
llvm.mlir.global internal @g_pow3() {addr_space = 0 : i32} : !llvm.ptr {
%178 = llvm.mlir.zero : !llvm.ptr
llvm.return %178 : !llvm.ptr
}
// Module static: g_blocks10_start
llvm.mlir.global internal @g_blocks10_start() {addr_space = 0 : i32} : !llvm.ptr {
%179 = llvm.mlir.zero : !llvm.ptr
llvm.return %179 : !llvm.ptr
}
// Module static: g_blocks10_len
llvm.mlir.global internal @g_blocks10_len() {addr_space = 0 : i32} : !llvm.ptr {
%180 = llvm.mlir.zero : !llvm.ptr
llvm.return %180 : !llvm.ptr
}
// Module static: g_blocks10_count
llvm.mlir.global internal @g_blocks10_count() {addr_space = 0 : i32} : !llvm.ptr {
%181 = llvm.mlir.zero : !llvm.ptr
llvm.return %181 : !llvm.ptr
}
// Module static: g_blocks3_start
llvm.mlir.global internal @g_blocks3_start() {addr_space = 0 : i32} : !llvm.ptr {
%182 = llvm.mlir.zero : !llvm.ptr
llvm.return %182 : !llvm.ptr
}
// Module static: g_blocks3_len
llvm.mlir.global internal @g_blocks3_len() {addr_space = 0 : i32} : !llvm.ptr {
%183 = llvm.mlir.zero : !llvm.ptr
llvm.return %183 : !llvm.ptr
}
// Module static: g_blocks3_count
llvm.mlir.global internal @g_blocks3_count() {addr_space = 0 : i32} : !llvm.ptr {
%184 = llvm.mlir.zero : !llvm.ptr
llvm.return %184 : !llvm.ptr
}
func.func @popcount(%arg0: i64) -> i64 {
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %186 : i64, !llvm.ptr
%187 = arith.constant 0 : i32
%188 = arith.extsi %187 : i32 to i64
%189 = llvm.mlir.constant(1 : i64) : i64
%190 = llvm.alloca %189 x i64 : (i64) -> !llvm.ptr
llvm.store %188, %190 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%191 = llvm.load %186 : !llvm.ptr -> i64
%192 = arith.constant 0 : i32
%194 = arith.extsi %192 : i32 to i64
%193 = arith.cmpi sgt, %191, %194 : i64
cf.cond_br %193, ^bb43, ^bb44
^bb43:
%195 = llvm.load %190 : !llvm.ptr -> i64
%196 = arith.constant 1 : i32
%198 = arith.extsi %196 : i32 to i64
%197 = arith.addi %195, %198 : i64
llvm.store %197, %190 : i64, !llvm.ptr
%199 = llvm.load %186 : !llvm.ptr -> i64
%200 = llvm.load %186 : !llvm.ptr -> i64
%201 = arith.constant 1 : i32
%203 = arith.extsi %201 : i32 to i64
%202 = arith.subi %200, %203 : i64
%204 = arith.andi %199, %202 : i64
llvm.store %204, %186 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%205 = llvm.load %190 : !llvm.ptr -> i64
func.return %205 : i64
}
func.func @partition_sum(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64, %arg3: !llvm.ptr) -> i64 {
%206 = arith.constant 0 : i32
%207 = arith.extsi %206 : i32 to i64
%208 = llvm.mlir.constant(1 : i64) : i64
%209 = llvm.alloca %208 x i64 : (i64) -> !llvm.ptr
llvm.store %207, %209 : i64, !llvm.ptr
%210 = arith.constant 0 : i32
%211 = arith.extsi %210 : i32 to i64
%212 = llvm.mlir.constant(1 : i64) : i64
%213 = llvm.alloca %212 x i64 : (i64) -> !llvm.ptr
llvm.store %211, %213 : i64, !llvm.ptr
%214 = arith.constant 0 : i32
%215 = arith.extsi %214 : i32 to i64
%216 = llvm.mlir.constant(1 : i64) : i64
%217 = llvm.alloca %216 x i64 : (i64) -> !llvm.ptr
llvm.store %215, %217 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%218 = llvm.load %217 : !llvm.ptr -> i64
%219 = arith.constant 1 : i32
%221 = arith.extsi %219 : i32 to i64
%220 = arith.subi %arg2, %221 : i64
%222 = arith.cmpi slt, %218, %220 : i64
cf.cond_br %222, ^bb46, ^bb47
^bb46:
%223 = arith.constant 2 : i32
%225 = arith.extsi %223 : i32 to i64
%224 = arith.subi %arg2, %225 : i64
%226 = llvm.load %217 : !llvm.ptr -> i64
%227 = arith.subi %224, %226 : i64
%228 = arith.shrsi %arg1, %227 : i64
%229 = arith.constant 1 : i32
%231 = arith.extsi %229 : i32 to i64
%230 = arith.andi %228, %231 : i64
%232 = arith.constant 1 : i32
%234 = arith.extsi %232 : i32 to i64
%233 = arith.cmpi eq, %230, %234 : i64
cf.cond_br %233, ^bb48, ^bb49
^bb48:
%235 = llvm.load %217 : !llvm.ptr -> i64
%236 = llvm.load %213 : !llvm.ptr -> i64
%237 = arith.subi %235, %236 : i64
%238 = arith.constant 1 : i32
%240 = arith.extsi %238 : i32 to i64
%239 = arith.addi %237, %240 : i64
%241 = llvm.load %209 : !llvm.ptr -> i64
%243 = llvm.load %213 : !llvm.ptr -> i64
%244 = arith.addi %243, %239 : i64
%245 = llvm.getelementptr %arg0[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%242 = llvm.load %245 : !llvm.ptr -> i64
%246 = arith.addi %241, %242 : i64
%248 = llvm.load %213 : !llvm.ptr -> i64
%249 = llvm.getelementptr %arg0[%248] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%247 = llvm.load %249 : !llvm.ptr -> i64
%251 = llvm.getelementptr %arg3[%239] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%250 = llvm.load %251 : !llvm.ptr -> i64
%252 = arith.muli %247, %250 : i64
%253 = arith.subi %246, %252 : i64
llvm.store %253, %209 : i64, !llvm.ptr
%254 = llvm.load %217 : !llvm.ptr -> i64
%255 = arith.constant 1 : i32
%257 = arith.extsi %255 : i32 to i64
%256 = arith.addi %254, %257 : i64
llvm.store %256, %213 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%258 = llvm.load %217 : !llvm.ptr -> i64
%259 = arith.constant 1 : i32
%261 = arith.extsi %259 : i32 to i64
%260 = arith.addi %258, %261 : i64
llvm.store %260, %217 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%262 = llvm.load %213 : !llvm.ptr -> i64
%263 = arith.subi %arg2, %262 : i64
%264 = llvm.load %209 : !llvm.ptr -> i64
%266 = llvm.load %213 : !llvm.ptr -> i64
%267 = arith.addi %266, %263 : i64
%268 = llvm.getelementptr %arg0[%267] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%265 = llvm.load %268 : !llvm.ptr -> i64
%269 = arith.addi %264, %265 : i64
%271 = llvm.load %213 : !llvm.ptr -> i64
%272 = llvm.getelementptr %arg0[%271] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%270 = llvm.load %272 : !llvm.ptr -> i64
%274 = llvm.getelementptr %arg3[%263] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%273 = llvm.load %274 : !llvm.ptr -> i64
%275 = arith.muli %270, %273 : i64
%276 = arith.subi %269, %275 : i64
llvm.store %276, %209 : i64, !llvm.ptr
%277 = llvm.load %209 : !llvm.ptr -> i64
func.return %277 : i64
}
func.func @sort_masks_by_popcount(%arg0: !llvm.ptr, %arg1: i64) -> () {
%279 = arith.constant 64 : i32
%280 = arith.constant 8 : i32
%281 = arith.extsi %279 : i32 to i64
%282 = arith.extsi %280 : i32 to i64
%278 = func.call @calloc(%281, %282) : (i64, i64) -> !llvm.ptr
%283 = arith.constant 0 : i32
%284 = arith.index_cast %283 : i32 to index
%285 = arith.index_cast %arg1 : i32 to index
%287 = arith.constant 1 : index
%288 = arith.constant -1 : index
%289 = arith.cmpi sle, %284, %285 : index
%286 = arith.select %289, %287, %288 : index
cf.br ^bb51(%284 : index)
^bb51(%290: index):
%291 = arith.cmpi slt, %290, %285 : index
%292 = arith.cmpi sgt, %290, %285 : index
%293 = arith.select %289, %291, %292 : i1
cf.cond_br %293, ^bb52(%290 : index), ^bb53(%290 : index)
^bb52(%294: index):
%297 = arith.index_cast %294 : index to i64
%298 = llvm.getelementptr %arg0[%297] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%296 = llvm.load %298 : !llvm.ptr -> i64
%295 = func.call @popcount(%296) : (i64) -> i64
%300 = llvm.getelementptr %278[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%299 = llvm.load %300 : !llvm.ptr -> i64
%301 = arith.constant 1 : i32
%303 = arith.extsi %301 : i32 to i64
%302 = arith.addi %299, %303 : i64
%304 = llvm.getelementptr %278[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %302, %304 : i64, !llvm.ptr
%305 = arith.addi %294, %286 : index
cf.br ^bb51(%305 : index)
^bb53(%306: index):
%308 = arith.constant 64 : i32
%309 = arith.constant 8 : i32
%310 = arith.extsi %308 : i32 to i64
%311 = arith.extsi %309 : i32 to i64
%307 = func.call @calloc(%310, %311) : (i64, i64) -> !llvm.ptr
%312 = arith.constant 0 : i32
%313 = arith.extsi %312 : i32 to i64
%314 = llvm.mlir.constant(1 : i64) : i64
%315 = llvm.alloca %314 x i64 : (i64) -> !llvm.ptr
llvm.store %313, %315 : i64, !llvm.ptr
%316 = arith.constant 63 : i32
%317 = arith.extsi %316 : i32 to i64
%318 = llvm.mlir.constant(1 : i64) : i64
%319 = llvm.alloca %318 x i64 : (i64) -> !llvm.ptr
llvm.store %317, %319 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%320 = llvm.load %319 : !llvm.ptr -> i64
%321 = arith.constant 0 : i32
%323 = arith.extsi %321 : i32 to i64
%322 = arith.cmpi sge, %320, %323 : i64
cf.cond_br %322, ^bb55, ^bb56
^bb55:
%324 = llvm.load %315 : !llvm.ptr -> i64
%325 = llvm.load %319 : !llvm.ptr -> i64
%326 = llvm.getelementptr %307[%325] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %324, %326 : i64, !llvm.ptr
%327 = llvm.load %315 : !llvm.ptr -> i64
%329 = llvm.load %319 : !llvm.ptr -> i64
%330 = llvm.getelementptr %278[%329] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%328 = llvm.load %330 : !llvm.ptr -> i64
%331 = arith.addi %327, %328 : i64
llvm.store %331, %315 : i64, !llvm.ptr
%332 = llvm.load %319 : !llvm.ptr -> i64
%333 = arith.constant 1 : i32
%335 = arith.extsi %333 : i32 to i64
%334 = arith.subi %332, %335 : i64
llvm.store %334, %319 : i64, !llvm.ptr
cf.br ^bb54
^bb56:
%337 = arith.constant 8 : i32
%338 = arith.extsi %337 : i32 to i64
%336 = func.call @calloc(%arg1, %338) : (i64, i64) -> !llvm.ptr
%339 = arith.constant 0 : i32
%340 = arith.index_cast %339 : i32 to index
%341 = arith.index_cast %arg1 : i32 to index
%343 = arith.constant 1 : index
%344 = arith.constant -1 : index
%345 = arith.cmpi sle, %340, %341 : index
%342 = arith.select %345, %343, %344 : index
cf.br ^bb57(%340 : index)
^bb57(%346: index):
%347 = arith.cmpi slt, %346, %341 : index
%348 = arith.cmpi sgt, %346, %341 : index
%349 = arith.select %345, %347, %348 : i1
cf.cond_br %349, ^bb58(%346 : index), ^bb59(%346 : index)
^bb58(%350: index):
%353 = arith.index_cast %350 : index to i64
%354 = llvm.getelementptr %arg0[%353] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%352 = llvm.load %354 : !llvm.ptr -> i64
%351 = func.call @popcount(%352) : (i64) -> i64
%356 = arith.index_cast %350 : index to i64
%357 = llvm.getelementptr %arg0[%356] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%355 = llvm.load %357 : !llvm.ptr -> i64
%359 = llvm.getelementptr %307[%351] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%358 = llvm.load %359 : !llvm.ptr -> i64
%360 = llvm.getelementptr %336[%358] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %355, %360 : i64, !llvm.ptr
%362 = llvm.getelementptr %307[%351] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%361 = llvm.load %362 : !llvm.ptr -> i64
%363 = arith.constant 1 : i32
%365 = arith.extsi %363 : i32 to i64
%364 = arith.addi %361, %365 : i64
%366 = llvm.getelementptr %307[%351] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %364, %366 : i64, !llvm.ptr
%367 = arith.addi %350, %342 : index
cf.br ^bb57(%367 : index)
^bb59(%368: index):
%369 = arith.constant 0 : i32
%370 = arith.index_cast %369 : i32 to index
%371 = arith.index_cast %arg1 : i32 to index
%373 = arith.constant 1 : index
%374 = arith.constant -1 : index
%375 = arith.cmpi sle, %370, %371 : index
%372 = arith.select %375, %373, %374 : index
cf.br ^bb60(%370 : index)
^bb60(%376: index):
%377 = arith.cmpi slt, %376, %371 : index
%378 = arith.cmpi sgt, %376, %371 : index
%379 = arith.select %375, %377, %378 : i1
cf.cond_br %379, ^bb61(%376 : index), ^bb62(%376 : index)
^bb61(%380: index):
%382 = arith.index_cast %380 : index to i64
%383 = llvm.getelementptr %336[%382] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%381 = llvm.load %383 : !llvm.ptr -> i64
%384 = arith.index_cast %380 : index to i64
%385 = llvm.getelementptr %arg0[%384] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %381, %385 : i64, !llvm.ptr
%386 = arith.addi %380, %372 : index
cf.br ^bb60(%386 : index)
^bb62(%387: index):
func.call @free(%336) : (!llvm.ptr) -> ()
func.call @free(%307) : (!llvm.ptr) -> ()
func.call @free(%278) : (!llvm.ptr) -> ()
func.return
}
// Module static: g_sorted_masks10
llvm.mlir.global internal @g_sorted_masks10() {addr_space = 0 : i32} : !llvm.ptr {
%391 = llvm.mlir.zero : !llvm.ptr
llvm.return %391 : !llvm.ptr
}
// Module static: g_mask_count10
llvm.mlir.global internal @g_mask_count10() {addr_space = 0 : i32} : !llvm.ptr {
%392 = llvm.mlir.zero : !llvm.ptr
llvm.return %392 : !llvm.ptr
}
// Module static: g_sorted_masks3
llvm.mlir.global internal @g_sorted_masks3() {addr_space = 0 : i32} : !llvm.ptr {
%393 = llvm.mlir.zero : !llvm.ptr
llvm.return %393 : !llvm.ptr
}
// Module static: g_mask_count3
llvm.mlir.global internal @g_mask_count3() {addr_space = 0 : i32} : !llvm.ptr {
%394 = llvm.mlir.zero : !llvm.ptr
llvm.return %394 : !llvm.ptr
}
func.func @precompute_masks() -> () {
%396 = arith.constant 9 : i32
%397 = arith.constant 128 : i32
%398 = arith.muli %396, %397 : i32
%399 = arith.constant 8 : i32
%400 = arith.extsi %398 : i32 to i64
%401 = arith.extsi %399 : i32 to i64
%395 = func.call @calloc(%400, %401) : (i64, i64) -> !llvm.ptr
%402 = llvm.mlir.addressof @g_sorted_masks10 : !llvm.ptr
llvm.store %395, %402 : !llvm.ptr, !llvm.ptr
%404 = arith.constant 9 : i32
%405 = arith.constant 8 : i32
%406 = arith.extsi %404 : i32 to i64
%407 = arith.extsi %405 : i32 to i64
%403 = func.call @calloc(%406, %407) : (i64, i64) -> !llvm.ptr
%408 = llvm.mlir.addressof @g_mask_count10 : !llvm.ptr
llvm.store %403, %408 : !llvm.ptr, !llvm.ptr
%409 = arith.constant 2 : i32
%410 = arith.constant 9 : i32
%411 = arith.index_cast %409 : i32 to index
%412 = arith.index_cast %410 : i32 to index
%414 = arith.constant 1 : index
%415 = arith.constant -1 : index
%416 = arith.cmpi sle, %411, %412 : index
%413 = arith.select %416, %414, %415 : index
cf.br ^bb63(%411 : index)
^bb63(%417: index):
%418 = arith.cmpi slt, %417, %412 : index
%419 = arith.cmpi sgt, %417, %412 : index
%420 = arith.select %416, %418, %419 : i1
cf.cond_br %420, ^bb64(%417 : index), ^bb65(%417 : index)
^bb64(%421: index):
%422 = arith.constant 1 : i32
%423 = arith.constant 1 : i32
%425 = arith.index_cast %421 : index to i32
%424 = arith.subi %425, %423 : i32
%426 = arith.shli %422, %424 : i32
%427 = arith.extsi %426 : i32 to i64
%428 = arith.constant 128 : i32
%430 = arith.index_cast %421 : index to i32
%429 = arith.muli %430, %428 : i32
%431 = arith.extsi %429 : i32 to i64
%432 = arith.constant 0 : i32
%433 = arith.index_cast %432 : i32 to index
%434 = arith.index_cast %427 : i32 to index
%436 = arith.constant 1 : index
%437 = arith.constant -1 : index
%438 = arith.cmpi sle, %433, %434 : index
%435 = arith.select %438, %436, %437 : index
cf.br ^bb66(%433 : index)
^bb66(%439: index):
%440 = arith.cmpi slt, %439, %434 : index
%441 = arith.cmpi sgt, %439, %434 : index
%442 = arith.select %438, %440, %441 : i1
cf.cond_br %442, ^bb67(%439 : index), ^bb68(%439 : index)
^bb67(%443: index):
%444 = llvm.mlir.addressof @g_sorted_masks10 : !llvm.ptr
%445 = llvm.load %444 : !llvm.ptr -> !llvm.ptr
%447 = arith.trunci %431 : i64 to i32
%448 = arith.index_cast %443 : index to i32
%446 = arith.addi %447, %448 : i32
%449 = arith.index_cast %443 : index to i64
%450 = arith.extsi %446 : i32 to i64
%451 = llvm.getelementptr %445[%450] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %449, %451 : i64, !llvm.ptr
%452 = arith.addi %443, %435 : index
cf.br ^bb66(%452 : index)
^bb68(%453: index):
# String concatenation: !llvm.ptr + i64
func.call @sort_masks_by_popcount(%455, %427) : (!llvm.ptr, i64) -> ()
%456 = llvm.mlir.addressof @g_mask_count10 : !llvm.ptr
%457 = llvm.load %456 : !llvm.ptr -> !llvm.ptr
%458 = arith.index_cast %421 : index to i64
%459 = llvm.getelementptr %457[%458] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %427, %459 : i64, !llvm.ptr
%460 = arith.addi %421, %413 : index
cf.br ^bb63(%460 : index)
^bb65(%461: index):
%463 = arith.constant 16 : i32
%464 = arith.constant 16384 : i32
%465 = arith.muli %463, %464 : i32
%466 = arith.constant 8 : i32
%467 = arith.extsi %465 : i32 to i64
%468 = arith.extsi %466 : i32 to i64
%462 = func.call @calloc(%467, %468) : (i64, i64) -> !llvm.ptr
%469 = llvm.mlir.addressof @g_sorted_masks3 : !llvm.ptr
llvm.store %462, %469 : !llvm.ptr, !llvm.ptr
%471 = arith.constant 16 : i32
%472 = arith.constant 8 : i32
%473 = arith.extsi %471 : i32 to i64
%474 = arith.extsi %472 : i32 to i64
%470 = func.call @calloc(%473, %474) : (i64, i64) -> !llvm.ptr
%475 = llvm.mlir.addressof @g_mask_count3 : !llvm.ptr
llvm.store %470, %475 : !llvm.ptr, !llvm.ptr
%476 = arith.constant 2 : i32
%477 = arith.constant 16 : i32
%478 = arith.index_cast %476 : i32 to index
%479 = arith.index_cast %477 : i32 to index
%481 = arith.constant 1 : index
%482 = arith.constant -1 : index
%483 = arith.cmpi sle, %478, %479 : index
%480 = arith.select %483, %481, %482 : index
cf.br ^bb69(%478 : index)
^bb69(%484: index):
%485 = arith.cmpi slt, %484, %479 : index
%486 = arith.cmpi sgt, %484, %479 : index
%487 = arith.select %483, %485, %486 : i1
cf.cond_br %487, ^bb70(%484 : index), ^bb71(%484 : index)
^bb70(%488: index):
%489 = arith.constant 1 : i32
%490 = arith.constant 1 : i32
%492 = arith.index_cast %488 : index to i32
%491 = arith.subi %492, %490 : i32
%493 = arith.shli %489, %491 : i32
%494 = arith.extsi %493 : i32 to i64
%495 = arith.constant 16384 : i32
%497 = arith.index_cast %488 : index to i32
%496 = arith.muli %497, %495 : i32
%498 = arith.extsi %496 : i32 to i64
%499 = arith.constant 0 : i32
%500 = arith.index_cast %499 : i32 to index
%501 = arith.index_cast %494 : i32 to index
%503 = arith.constant 1 : index
%504 = arith.constant -1 : index
%505 = arith.cmpi sle, %500, %501 : index
%502 = arith.select %505, %503, %504 : index
cf.br ^bb72(%500 : index)
^bb72(%506: index):
%507 = arith.cmpi slt, %506, %501 : index
%508 = arith.cmpi sgt, %506, %501 : index
%509 = arith.select %505, %507, %508 : i1
cf.cond_br %509, ^bb73(%506 : index), ^bb74(%506 : index)
^bb73(%510: index):
%511 = llvm.mlir.addressof @g_sorted_masks3 : !llvm.ptr
%512 = llvm.load %511 : !llvm.ptr -> !llvm.ptr
%514 = arith.trunci %498 : i64 to i32
%515 = arith.index_cast %510 : index to i32
%513 = arith.addi %514, %515 : i32
%516 = arith.index_cast %510 : index to i64
%517 = arith.extsi %513 : i32 to i64
%518 = llvm.getelementptr %512[%517] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %516, %518 : i64, !llvm.ptr
%519 = arith.addi %510, %502 : index
cf.br ^bb72(%519 : index)
^bb74(%520: index):
# String concatenation: !llvm.ptr + i64
func.call @sort_masks_by_popcount(%522, %494) : (!llvm.ptr, i64) -> ()
%523 = llvm.mlir.addressof @g_mask_count3 : !llvm.ptr
%524 = llvm.load %523 : !llvm.ptr -> !llvm.ptr
%525 = arith.index_cast %488 : index to i64
%526 = llvm.getelementptr %524[%525] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %494, %526 : i64, !llvm.ptr
%527 = arith.addi %488, %480 : index
cf.br ^bb69(%527 : index)
^bb71(%528: index):
func.return
}
func.func @main() -> i32 {
%529 = arith.constant 10000000 : i32
%530 = arith.extsi %529 : i32 to i64
%532 = arith.constant 1 : i32
%534 = arith.extsi %532 : i32 to i64
%533 = arith.addi %530, %534 : i64
%535 = arith.constant 4 : i32
%536 = arith.extsi %535 : i32 to i64
%531 = func.call @calloc(%533, %536) : (i64, i64) -> !llvm.ptr
%537 = llvm.mlir.addressof @g_ds10 : !llvm.ptr
llvm.store %531, %537 : !llvm.ptr, !llvm.ptr
%539 = arith.constant 1 : i32
%541 = arith.extsi %539 : i32 to i64
%540 = arith.addi %530, %541 : i64
%542 = arith.constant 4 : i32
%543 = arith.extsi %542 : i32 to i64
%538 = func.call @calloc(%540, %543) : (i64, i64) -> !llvm.ptr
%544 = llvm.mlir.addressof @g_ds3 : !llvm.ptr
llvm.store %538, %544 : !llvm.ptr, !llvm.ptr
%545 = arith.constant 1 : i32
%546 = arith.constant 1 : i32
%548 = arith.extsi %546 : i32 to i64
%547 = arith.addi %530, %548 : i64
%549 = arith.index_cast %545 : i32 to index
%550 = arith.index_cast %547 : i32 to index
%552 = arith.constant 1 : index
%553 = arith.constant -1 : index
%554 = arith.cmpi sle, %549, %550 : index
%551 = arith.select %554, %552, %553 : index
cf.br ^bb75(%549 : index)
^bb75(%555: index):
%556 = arith.cmpi slt, %555, %550 : index
%557 = arith.cmpi sgt, %555, %550 : index
%558 = arith.select %554, %556, %557 : i1
cf.cond_br %558, ^bb76(%555 : index), ^bb77(%555 : index)
^bb76(%559: index):
%561 = llvm.mlir.addressof @g_ds10 : !llvm.ptr
%562 = llvm.load %561 : !llvm.ptr -> !llvm.ptr
%563 = arith.constant 10 : i32
%565 = arith.index_cast %559 : index to i32
%564 = arith.divsi %565, %563 : i32
%566 = arith.extsi %564 : i32 to i64
%567 = llvm.getelementptr %562[%566] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%560 = llvm.load %567 : !llvm.ptr -> i32
%568 = arith.constant 10 : i32
%570 = arith.index_cast %559 : index to i32
%569 = arith.remsi %570, %568 : i32
%571 = arith.addi %560, %569 : i32
%572 = llvm.mlir.addressof @g_ds10 : !llvm.ptr
%573 = llvm.load %572 : !llvm.ptr -> !llvm.ptr
%574 = arith.index_cast %559 : index to i64
%575 = llvm.getelementptr %573[%574] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %571, %575 : i32, !llvm.ptr
%577 = llvm.mlir.addressof @g_ds3 : !llvm.ptr
%578 = llvm.load %577 : !llvm.ptr -> !llvm.ptr
%579 = arith.constant 3 : i32
%581 = arith.index_cast %559 : index to i32
%580 = arith.divsi %581, %579 : i32
%582 = arith.extsi %580 : i32 to i64
%583 = llvm.getelementptr %578[%582] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%576 = llvm.load %583 : !llvm.ptr -> i32
%584 = arith.constant 3 : i32
%586 = arith.index_cast %559 : index to i32
%585 = arith.remsi %586, %584 : i32
%587 = arith.addi %576, %585 : i32
%588 = llvm.mlir.addressof @g_ds3 : !llvm.ptr
%589 = llvm.load %588 : !llvm.ptr -> !llvm.ptr
%590 = arith.index_cast %559 : index to i64
%591 = llvm.getelementptr %589[%590] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %587, %591 : i32, !llvm.ptr
%592 = arith.addi %559, %551 : index
cf.br ^bb75(%592 : index)
^bb77(%593: index):
%595 = arith.constant 9 : i32
%596 = arith.constant 8 : i32
%597 = arith.extsi %595 : i32 to i64
%598 = arith.extsi %596 : i32 to i64
%594 = func.call @calloc(%597, %598) : (i64, i64) -> !llvm.ptr
%599 = llvm.mlir.addressof @g_pow10 : !llvm.ptr
llvm.store %594, %599 : !llvm.ptr, !llvm.ptr
%601 = arith.constant 16 : i32
%602 = arith.constant 8 : i32
%603 = arith.extsi %601 : i32 to i64
%604 = arith.extsi %602 : i32 to i64
%600 = func.call @calloc(%603, %604) : (i64, i64) -> !llvm.ptr
%605 = llvm.mlir.addressof @g_pow3 : !llvm.ptr
llvm.store %600, %605 : !llvm.ptr, !llvm.ptr
%606 = arith.constant 1 : i32
%607 = llvm.mlir.addressof @g_pow10 : !llvm.ptr
%608 = llvm.load %607 : !llvm.ptr -> !llvm.ptr
%609 = arith.constant 0 : i32
%610 = arith.extsi %606 : i32 to i64
%611 = arith.extsi %609 : i32 to i64
%612 = llvm.getelementptr %608[%611] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %610, %612 : i64, !llvm.ptr
%613 = arith.constant 0 : i32
%614 = arith.constant 8 : i32
%615 = arith.index_cast %613 : i32 to index
%616 = arith.index_cast %614 : i32 to index
%618 = arith.constant 1 : index
%619 = arith.constant -1 : index
%620 = arith.cmpi sle, %615, %616 : index
%617 = arith.select %620, %618, %619 : index
cf.br ^bb78(%615 : index)
^bb78(%621: index):
%622 = arith.cmpi slt, %621, %616 : index
%623 = arith.cmpi sgt, %621, %616 : index
%624 = arith.select %620, %622, %623 : i1
cf.cond_br %624, ^bb79(%621 : index), ^bb80(%621 : index)
^bb79(%625: index):
%627 = llvm.mlir.addressof @g_pow10 : !llvm.ptr
%628 = llvm.load %627 : !llvm.ptr -> !llvm.ptr
%629 = arith.index_cast %625 : index to i64
%630 = llvm.getelementptr %628[%629] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%626 = llvm.load %630 : !llvm.ptr -> i64
%631 = arith.constant 10 : i32
%633 = arith.extsi %631 : i32 to i64
%632 = arith.muli %626, %633 : i64
%634 = llvm.mlir.addressof @g_pow10 : !llvm.ptr
%635 = llvm.load %634 : !llvm.ptr -> !llvm.ptr
%636 = arith.constant 1 : i32
%638 = arith.index_cast %625 : index to i32
%637 = arith.addi %638, %636 : i32
%639 = arith.extsi %637 : i32 to i64
%640 = llvm.getelementptr %635[%639] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %632, %640 : i64, !llvm.ptr
%641 = arith.addi %625, %617 : index
cf.br ^bb78(%641 : index)
^bb80(%642: index):
%643 = arith.constant 1 : i32
%644 = llvm.mlir.addressof @g_pow3 : !llvm.ptr
%645 = llvm.load %644 : !llvm.ptr -> !llvm.ptr
%646 = arith.constant 0 : i32
%647 = arith.extsi %643 : i32 to i64
%648 = arith.extsi %646 : i32 to i64
%649 = llvm.getelementptr %645[%648] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %647, %649 : i64, !llvm.ptr
%650 = arith.constant 0 : i32
%651 = arith.constant 15 : i32
%652 = arith.index_cast %650 : i32 to index
%653 = arith.index_cast %651 : i32 to index
%655 = arith.constant 1 : index
%656 = arith.constant -1 : index
%657 = arith.cmpi sle, %652, %653 : index
%654 = arith.select %657, %655, %656 : index
cf.br ^bb81(%652 : index)
^bb81(%658: index):
%659 = arith.cmpi slt, %658, %653 : index
%660 = arith.cmpi sgt, %658, %653 : index
%661 = arith.select %657, %659, %660 : i1
cf.cond_br %661, ^bb82(%658 : index), ^bb83(%658 : index)
^bb82(%662: index):
%664 = llvm.mlir.addressof @g_pow3 : !llvm.ptr
%665 = llvm.load %664 : !llvm.ptr -> !llvm.ptr
%666 = arith.index_cast %662 : index to i64
%667 = llvm.getelementptr %665[%666] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%663 = llvm.load %667 : !llvm.ptr -> i64
%668 = arith.constant 3 : i32
%670 = arith.extsi %668 : i32 to i64
%669 = arith.muli %663, %670 : i64
%671 = llvm.mlir.addressof @g_pow3 : !llvm.ptr
%672 = llvm.load %671 : !llvm.ptr -> !llvm.ptr
%673 = arith.constant 1 : i32
%675 = arith.index_cast %662 : index to i32
%674 = arith.addi %675, %673 : i32
%676 = arith.extsi %674 : i32 to i64
%677 = llvm.getelementptr %672[%676] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %669, %677 : i64, !llvm.ptr
%678 = arith.addi %662, %654 : index
cf.br ^bb81(%678 : index)
^bb83(%679: index):
func.call @precompute_masks() : () -> ()
%682 = arith.constant 8 : i32
%683 = arith.constant 8 : i32
%684 = arith.extsi %682 : i32 to i64
%685 = arith.extsi %683 : i32 to i64
%681 = func.call @calloc(%684, %685) : (i64, i64) -> !llvm.ptr
%687 = arith.constant 15 : i32
%688 = arith.constant 8 : i32
%689 = arith.extsi %687 : i32 to i64
%690 = arith.extsi %688 : i32 to i64
%686 = func.call @calloc(%689, %690) : (i64, i64) -> !llvm.ptr
%692 = arith.constant 9 : i32
%693 = arith.constant 8 : i32
%694 = arith.extsi %692 : i32 to i64
%695 = arith.extsi %693 : i32 to i64
%691 = func.call @calloc(%694, %695) : (i64, i64) -> !llvm.ptr
%697 = arith.constant 16 : i32
%698 = arith.constant 8 : i32
%699 = arith.extsi %697 : i32 to i64
%700 = arith.extsi %698 : i32 to i64
%696 = func.call @calloc(%699, %700) : (i64, i64) -> !llvm.ptr
%701 = arith.constant 1 : i32
%702 = arith.extsi %701 : i32 to i64
%703 = llvm.mlir.constant(1 : i64) : i64
%704 = llvm.alloca %703 x i64 : (i64) -> !llvm.ptr
llvm.store %702, %704 : i64, !llvm.ptr
%705 = arith.constant 1 : i32
%706 = arith.extsi %705 : i32 to i64
%707 = llvm.mlir.constant(1 : i64) : i64
%708 = llvm.alloca %707 x i64 : (i64) -> !llvm.ptr
llvm.store %706, %708 : i64, !llvm.ptr
%709 = arith.constant 0 : i32
%710 = arith.extsi %709 : i32 to i64
%711 = llvm.mlir.constant(1 : i64) : i64
%712 = llvm.alloca %711 x i64 : (i64) -> !llvm.ptr
llvm.store %710, %712 : i64, !llvm.ptr
%713 = arith.constant 0 : i32
%714 = arith.extsi %713 : i32 to i64
%715 = llvm.mlir.constant(1 : i64) : i64
%716 = llvm.alloca %715 x i64 : (i64) -> !llvm.ptr
llvm.store %714, %716 : i64, !llvm.ptr
%717 = arith.constant 0 : i32
%718 = arith.extsi %717 : i32 to i64
%719 = llvm.mlir.constant(1 : i64) : i64
%720 = llvm.alloca %719 x i64 : (i64) -> !llvm.ptr
llvm.store %718, %720 : i64, !llvm.ptr
%721 = arith.constant 1 : i32
%722 = arith.constant 1 : i32
%724 = arith.extsi %722 : i32 to i64
%723 = arith.addi %530, %724 : i64
%725 = arith.index_cast %721 : i32 to index
%726 = arith.index_cast %723 : i32 to index
%728 = arith.constant 1 : index
%729 = arith.constant -1 : index
%730 = arith.cmpi sle, %725, %726 : index
%727 = arith.select %730, %728, %729 : index
cf.br ^bb84(%725 : index)
^bb84(%731: index):
%732 = arith.cmpi slt, %731, %726 : index
%733 = arith.cmpi sgt, %731, %726 : index
%734 = arith.select %730, %732, %733 : i1
cf.cond_br %734, ^bb85(%731 : index), ^bb86(%731 : index)
^bb85(%735: index):
%736 = arith.constant 0 : i32
%737 = arith.extsi %736 : i32 to i64
%738 = llvm.mlir.constant(1 : i64) : i64
%739 = llvm.alloca %738 x i64 : (i64) -> !llvm.ptr
llvm.store %737, %739 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%740 = llvm.load %739 : !llvm.ptr -> i64
%741 = llvm.load %704 : !llvm.ptr -> i64
%742 = arith.cmpi slt, %740, %741 : i64
%743 = scf.if %742 -> (i1) {
%745 = llvm.load %739 : !llvm.ptr -> i64
%746 = llvm.getelementptr %681[%745] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%744 = llvm.load %746 : !llvm.ptr -> i64
%747 = arith.constant 9 : i32
%749 = arith.extsi %747 : i32 to i64
%748 = arith.cmpi eq, %744, %749 : i64
scf.yield %748 : i1
} else {
%750 = arith.constant false
scf.yield %750 : i1
}
cf.cond_br %743, ^bb88, ^bb89
^bb88:
%751 = llvm.load %712 : !llvm.ptr -> i64
%752 = arith.constant 9 : i32
%754 = arith.extsi %752 : i32 to i64
%753 = arith.subi %751, %754 : i64
llvm.store %753, %712 : i64, !llvm.ptr
%755 = arith.constant 0 : i32
%756 = llvm.load %739 : !llvm.ptr -> i64
%757 = arith.extsi %755 : i32 to i64
%758 = llvm.getelementptr %681[%756] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %757, %758 : i64, !llvm.ptr
%759 = llvm.load %739 : !llvm.ptr -> i64
%760 = arith.constant 1 : i32
%762 = arith.extsi %760 : i32 to i64
%761 = arith.addi %759, %762 : i64
llvm.store %761, %739 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%763 = llvm.load %739 : !llvm.ptr -> i64
%764 = llvm.load %704 : !llvm.ptr -> i64
%765 = arith.cmpi eq, %763, %764 : i64
cf.cond_br %765, ^bb90, ^bb91
^bb90:
%766 = arith.constant 1 : i32
%767 = llvm.load %739 : !llvm.ptr -> i64
%768 = arith.extsi %766 : i32 to i64
%769 = llvm.getelementptr %681[%767] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %768, %769 : i64, !llvm.ptr
%770 = llvm.load %704 : !llvm.ptr -> i64
%771 = arith.constant 1 : i32
%773 = arith.extsi %771 : i32 to i64
%772 = arith.addi %770, %773 : i64
llvm.store %772, %704 : i64, !llvm.ptr
%774 = llvm.load %712 : !llvm.ptr -> i64
%775 = arith.constant 1 : i32
%777 = arith.extsi %775 : i32 to i64
%776 = arith.addi %774, %777 : i64
llvm.store %776, %712 : i64, !llvm.ptr
cf.br ^bb92
^bb91:
%779 = llvm.load %739 : !llvm.ptr -> i64
%780 = llvm.getelementptr %681[%779] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%778 = llvm.load %780 : !llvm.ptr -> i64
%781 = arith.constant 1 : i32
%783 = arith.extsi %781 : i32 to i64
%782 = arith.addi %778, %783 : i64
%784 = llvm.load %739 : !llvm.ptr -> i64
%785 = llvm.getelementptr %681[%784] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %782, %785 : i64, !llvm.ptr
%786 = llvm.load %712 : !llvm.ptr -> i64
%787 = arith.constant 1 : i32
%789 = arith.extsi %787 : i32 to i64
%788 = arith.addi %786, %789 : i64
llvm.store %788, %712 : i64, !llvm.ptr
cf.br ^bb92
^bb92:
%790 = arith.constant 0 : i32
%791 = arith.extsi %790 : i32 to i64
llvm.store %791, %739 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%792 = llvm.load %739 : !llvm.ptr -> i64
%793 = llvm.load %708 : !llvm.ptr -> i64
%794 = arith.cmpi slt, %792, %793 : i64
%795 = scf.if %794 -> (i1) {
%797 = llvm.load %739 : !llvm.ptr -> i64
%798 = llvm.getelementptr %686[%797] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%796 = llvm.load %798 : !llvm.ptr -> i64
%799 = arith.constant 2 : i32
%801 = arith.extsi %799 : i32 to i64
%800 = arith.cmpi eq, %796, %801 : i64
scf.yield %800 : i1
} else {
%802 = arith.constant false
scf.yield %802 : i1
}
cf.cond_br %795, ^bb94, ^bb95
^bb94:
%803 = llvm.load %716 : !llvm.ptr -> i64
%804 = arith.constant 2 : i32
%806 = arith.extsi %804 : i32 to i64
%805 = arith.subi %803, %806 : i64
llvm.store %805, %716 : i64, !llvm.ptr
%807 = arith.constant 0 : i32
%808 = llvm.load %739 : !llvm.ptr -> i64
%809 = arith.extsi %807 : i32 to i64
%810 = llvm.getelementptr %686[%808] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %809, %810 : i64, !llvm.ptr
%811 = llvm.load %739 : !llvm.ptr -> i64
%812 = arith.constant 1 : i32
%814 = arith.extsi %812 : i32 to i64
%813 = arith.addi %811, %814 : i64
llvm.store %813, %739 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%815 = llvm.load %739 : !llvm.ptr -> i64
%816 = llvm.load %708 : !llvm.ptr -> i64
%817 = arith.cmpi eq, %815, %816 : i64
cf.cond_br %817, ^bb96, ^bb97
^bb96:
%818 = arith.constant 1 : i32
%819 = llvm.load %739 : !llvm.ptr -> i64
%820 = arith.extsi %818 : i32 to i64
%821 = llvm.getelementptr %686[%819] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %820, %821 : i64, !llvm.ptr
%822 = llvm.load %708 : !llvm.ptr -> i64
%823 = arith.constant 1 : i32
%825 = arith.extsi %823 : i32 to i64
%824 = arith.addi %822, %825 : i64
llvm.store %824, %708 : i64, !llvm.ptr
%826 = llvm.load %716 : !llvm.ptr -> i64
%827 = arith.constant 1 : i32
%829 = arith.extsi %827 : i32 to i64
%828 = arith.addi %826, %829 : i64
llvm.store %828, %716 : i64, !llvm.ptr
cf.br ^bb98
^bb97:
%831 = llvm.load %739 : !llvm.ptr -> i64
%832 = llvm.getelementptr %686[%831] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%830 = llvm.load %832 : !llvm.ptr -> i64
%833 = arith.constant 1 : i32
%835 = arith.extsi %833 : i32 to i64
%834 = arith.addi %830, %835 : i64
%836 = llvm.load %739 : !llvm.ptr -> i64
%837 = llvm.getelementptr %686[%836] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %834, %837 : i64, !llvm.ptr
%838 = llvm.load %716 : !llvm.ptr -> i64
%839 = arith.constant 1 : i32
%841 = arith.extsi %839 : i32 to i64
%840 = arith.addi %838, %841 : i64
llvm.store %840, %716 : i64, !llvm.ptr
cf.br ^bb98
^bb98:
%842 = llvm.mlir.undef : i64
%843 = llvm.load %704 : !llvm.ptr -> i64
%844 = arith.constant 1 : i32
%846 = arith.extsi %844 : i32 to i64
%845 = arith.cmpi eq, %843, %846 : i64
cf.cond_br %845, ^bb99, ^bb100
^bb99:
%847 = arith.constant 0 : i32
%848 = arith.extsi %847 : i32 to i64
cf.br ^bb101(%848 : i64)
^bb100:
%849 = llvm.load %712 : !llvm.ptr -> i64
%850 = arith.constant 10 : i32
%852 = arith.extsi %850 : i32 to i64
%851 = arith.cmpi slt, %849, %852 : i64
cf.cond_br %851, ^bb102, ^bb103
^bb102:
%853 = arith.constant 1 : i32
%854 = arith.extsi %853 : i32 to i64
cf.br ^bb104(%854 : i64)
^bb103:
%855 = arith.constant 0 : i32
%856 = arith.extsi %855 : i32 to i64
%857 = llvm.mlir.constant(1 : i64) : i64
%858 = llvm.alloca %857 x i64 : (i64) -> !llvm.ptr
llvm.store %856, %858 : i64, !llvm.ptr
%859 = arith.constant 0 : i32
%860 = arith.constant 0 : i32
%861 = arith.extsi %859 : i32 to i64
%862 = arith.extsi %860 : i32 to i64
%863 = llvm.getelementptr %691[%862] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %861, %863 : i64, !llvm.ptr
%864 = arith.constant 0 : i32
%865 = arith.extsi %864 : i32 to i64
%866 = llvm.mlir.constant(1 : i64) : i64
%867 = llvm.alloca %866 x i64 : (i64) -> !llvm.ptr
llvm.store %865, %867 : i64, !llvm.ptr
%868 = llvm.load %704 : !llvm.ptr -> i64
%869 = arith.constant 1 : i32
%871 = arith.extsi %869 : i32 to i64
%870 = arith.subi %868, %871 : i64
%872 = llvm.mlir.constant(1 : i64) : i64
%873 = llvm.alloca %872 x i64 : (i64) -> !llvm.ptr
llvm.store %870, %873 : i64, !llvm.ptr
cf.br ^bb105
^bb105:
%874 = llvm.load %873 : !llvm.ptr -> i64
%875 = arith.constant 0 : i32
%877 = arith.extsi %875 : i32 to i64
%876 = arith.cmpi sge, %874, %877 : i64
cf.cond_br %876, ^bb106, ^bb107
^bb106:
%878 = llvm.load %858 : !llvm.ptr -> i64
%879 = arith.constant 10 : i32
%881 = arith.extsi %879 : i32 to i64
%880 = arith.muli %878, %881 : i64
%883 = llvm.load %873 : !llvm.ptr -> i64
%884 = llvm.getelementptr %681[%883] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%882 = llvm.load %884 : !llvm.ptr -> i64
%885 = arith.addi %880, %882 : i64
llvm.store %885, %858 : i64, !llvm.ptr
%886 = llvm.load %867 : !llvm.ptr -> i64
%887 = arith.constant 1 : i32
%889 = arith.extsi %887 : i32 to i64
%888 = arith.addi %886, %889 : i64
llvm.store %888, %867 : i64, !llvm.ptr
%890 = llvm.load %858 : !llvm.ptr -> i64
%891 = llvm.load %867 : !llvm.ptr -> i64
%892 = llvm.getelementptr %691[%891] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %890, %892 : i64, !llvm.ptr
%893 = llvm.load %873 : !llvm.ptr -> i64
%894 = arith.constant 1 : i32
%896 = arith.extsi %894 : i32 to i64
%895 = arith.subi %893, %896 : i64
llvm.store %895, %873 : i64, !llvm.ptr
cf.br ^bb105
^bb107:
%897 = arith.constant 0 : i32
%898 = arith.extsi %897 : i32 to i64
%899 = llvm.mlir.constant(1 : i64) : i64
%900 = llvm.alloca %899 x i64 : (i64) -> !llvm.ptr
llvm.store %898, %900 : i64, !llvm.ptr
%901 = llvm.load %704 : !llvm.ptr -> i64
%902 = arith.constant 128 : i32
%904 = arith.extsi %902 : i32 to i64
%903 = arith.muli %901, %904 : i64
%905 = arith.constant 0 : i32
%907 = llvm.mlir.addressof @g_mask_count10 : !llvm.ptr
%908 = llvm.load %907 : !llvm.ptr -> !llvm.ptr
%909 = llvm.load %704 : !llvm.ptr -> i64
%910 = llvm.getelementptr %908[%909] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%906 = llvm.load %910 : !llvm.ptr -> i64
%911 = arith.index_cast %905 : i32 to index
%912 = arith.index_cast %906 : i32 to index
%914 = arith.constant 1 : index
%915 = arith.constant -1 : index
%916 = arith.cmpi sle, %911, %912 : index
%913 = arith.select %916, %914, %915 : index
cf.br ^bb108(%911 : index)
^bb108(%917: index):
%918 = arith.cmpi slt, %917, %912 : index
%919 = arith.cmpi sgt, %917, %912 : index
%920 = arith.select %916, %918, %919 : i1
cf.cond_br %920, ^bb109(%917 : index), ^bb110(%917 : index)
^bb109(%921: index):
%923 = llvm.mlir.addressof @g_sorted_masks10 : !llvm.ptr
%924 = llvm.load %923 : !llvm.ptr -> !llvm.ptr
%926 = arith.trunci %903 : i64 to i32
%927 = arith.index_cast %921 : index to i32
%925 = arith.addi %926, %927 : i32
%928 = arith.extsi %925 : i32 to i64
%929 = llvm.getelementptr %924[%928] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%922 = llvm.load %929 : !llvm.ptr -> i64
%931 = llvm.load %704 : !llvm.ptr -> i64
%932 = llvm.mlir.addressof @g_pow10 : !llvm.ptr
%933 = llvm.load %932 : !llvm.ptr -> !llvm.ptr
%930 = func.call @partition_sum(%691, %922, %931, %933) : (!llvm.ptr, i64, i64, !llvm.ptr) -> i64
%935 = llvm.mlir.addressof @g_ds10 : !llvm.ptr
%936 = llvm.load %935 : !llvm.ptr -> !llvm.ptr
%937 = llvm.getelementptr %936[%930] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%934 = llvm.load %937 : !llvm.ptr -> i32
%938 = arith.extsi %934 : i32 to i64
%939 = arith.constant 10 : i32
%941 = arith.extsi %939 : i32 to i64
%940 = arith.cmpi slt, %938, %941 : i64
cf.cond_br %940, ^bb111, ^bb112
^bb111:
%942 = arith.constant 1 : i32
%943 = arith.extsi %942 : i32 to i64
llvm.store %943, %900 : i64, !llvm.ptr
cf.br ^bb110(%921 : index)
^bb112:
cf.br ^bb113
^bb113:
%944 = arith.addi %921, %913 : index
cf.br ^bb108(%944 : index)
^bb110(%945: index):
%946 = llvm.load %900 : !llvm.ptr -> i64
%947 = arith.constant 1 : i32
%949 = arith.extsi %947 : i32 to i64
%948 = arith.cmpi eq, %946, %949 : i64
%950 = scf.if %948 -> (i64) {
%951 = arith.constant 2 : i32
%952 = arith.extsi %951 : i32 to i64
scf.yield %952 : i64
} else {
%953 = arith.constant 3 : i32
%954 = arith.extsi %953 : i32 to i64
scf.yield %954 : i64
}
cf.br ^bb104(%950 : i64)
^bb104(%955: i64):
cf.br ^bb101(%955 : i64)
^bb101(%956: i64):
%957 = llvm.mlir.undef : i64
%958 = llvm.load %708 : !llvm.ptr -> i64
%959 = arith.constant 1 : i32
%961 = arith.extsi %959 : i32 to i64
%960 = arith.cmpi eq, %958, %961 : i64
cf.cond_br %960, ^bb114, ^bb115
^bb114:
%962 = arith.constant 0 : i32
%963 = arith.extsi %962 : i32 to i64
cf.br ^bb116(%963 : i64)
^bb115:
%964 = llvm.load %716 : !llvm.ptr -> i64
%965 = arith.constant 3 : i32
%967 = arith.extsi %965 : i32 to i64
%966 = arith.cmpi slt, %964, %967 : i64
cf.cond_br %966, ^bb117, ^bb118
^bb117:
%968 = arith.constant 1 : i32
%969 = arith.extsi %968 : i32 to i64
cf.br ^bb119(%969 : i64)
^bb118:
%970 = arith.constant 0 : i32
%971 = arith.extsi %970 : i32 to i64
%972 = llvm.mlir.constant(1 : i64) : i64
%973 = llvm.alloca %972 x i64 : (i64) -> !llvm.ptr
llvm.store %971, %973 : i64, !llvm.ptr
%974 = arith.constant 0 : i32
%975 = arith.constant 0 : i32
%976 = arith.extsi %974 : i32 to i64
%977 = arith.extsi %975 : i32 to i64
%978 = llvm.getelementptr %696[%977] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %976, %978 : i64, !llvm.ptr
%979 = arith.constant 0 : i32
%980 = arith.extsi %979 : i32 to i64
%981 = llvm.mlir.constant(1 : i64) : i64
%982 = llvm.alloca %981 x i64 : (i64) -> !llvm.ptr
llvm.store %980, %982 : i64, !llvm.ptr
%983 = llvm.load %708 : !llvm.ptr -> i64
%984 = arith.constant 1 : i32
%986 = arith.extsi %984 : i32 to i64
%985 = arith.subi %983, %986 : i64
%987 = llvm.mlir.constant(1 : i64) : i64
%988 = llvm.alloca %987 x i64 : (i64) -> !llvm.ptr
llvm.store %985, %988 : i64, !llvm.ptr
cf.br ^bb120
^bb120:
%989 = llvm.load %988 : !llvm.ptr -> i64
%990 = arith.constant 0 : i32
%992 = arith.extsi %990 : i32 to i64
%991 = arith.cmpi sge, %989, %992 : i64
cf.cond_br %991, ^bb121, ^bb122
^bb121:
%993 = llvm.load %973 : !llvm.ptr -> i64
%994 = arith.constant 3 : i32
%996 = arith.extsi %994 : i32 to i64
%995 = arith.muli %993, %996 : i64
%998 = llvm.load %988 : !llvm.ptr -> i64
%999 = llvm.getelementptr %686[%998] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%997 = llvm.load %999 : !llvm.ptr -> i64
%1000 = arith.addi %995, %997 : i64
llvm.store %1000, %973 : i64, !llvm.ptr
%1001 = llvm.load %982 : !llvm.ptr -> i64
%1002 = arith.constant 1 : i32
%1004 = arith.extsi %1002 : i32 to i64
%1003 = arith.addi %1001, %1004 : i64
llvm.store %1003, %982 : i64, !llvm.ptr
%1005 = llvm.load %973 : !llvm.ptr -> i64
%1006 = llvm.load %982 : !llvm.ptr -> i64
%1007 = llvm.getelementptr %696[%1006] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1005, %1007 : i64, !llvm.ptr
%1008 = llvm.load %988 : !llvm.ptr -> i64
%1009 = arith.constant 1 : i32
%1011 = arith.extsi %1009 : i32 to i64
%1010 = arith.subi %1008, %1011 : i64
llvm.store %1010, %988 : i64, !llvm.ptr
cf.br ^bb120
^bb122:
%1012 = arith.constant 0 : i32
%1013 = arith.extsi %1012 : i32 to i64
%1014 = llvm.mlir.constant(1 : i64) : i64
%1015 = llvm.alloca %1014 x i64 : (i64) -> !llvm.ptr
llvm.store %1013, %1015 : i64, !llvm.ptr
%1016 = llvm.load %708 : !llvm.ptr -> i64
%1017 = arith.constant 16384 : i32
%1019 = arith.extsi %1017 : i32 to i64
%1018 = arith.muli %1016, %1019 : i64
%1020 = arith.constant 0 : i32
%1022 = llvm.mlir.addressof @g_mask_count3 : !llvm.ptr
%1023 = llvm.load %1022 : !llvm.ptr -> !llvm.ptr
%1024 = llvm.load %708 : !llvm.ptr -> i64
%1025 = llvm.getelementptr %1023[%1024] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1021 = llvm.load %1025 : !llvm.ptr -> i64
%1026 = arith.index_cast %1020 : i32 to index
%1027 = arith.index_cast %1021 : i32 to index
%1029 = arith.constant 1 : index
%1030 = arith.constant -1 : index
%1031 = arith.cmpi sle, %1026, %1027 : index
%1028 = arith.select %1031, %1029, %1030 : index
cf.br ^bb123(%1026 : index)
^bb123(%1032: index):
%1033 = arith.cmpi slt, %1032, %1027 : index
%1034 = arith.cmpi sgt, %1032, %1027 : index
%1035 = arith.select %1031, %1033, %1034 : i1
cf.cond_br %1035, ^bb124(%1032 : index), ^bb125(%1032 : index)
^bb124(%1036: index):
%1038 = llvm.mlir.addressof @g_sorted_masks3 : !llvm.ptr
%1039 = llvm.load %1038 : !llvm.ptr -> !llvm.ptr
%1041 = arith.trunci %1018 : i64 to i32
%1042 = arith.index_cast %1036 : index to i32
%1040 = arith.addi %1041, %1042 : i32
%1043 = arith.extsi %1040 : i32 to i64
%1044 = llvm.getelementptr %1039[%1043] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1037 = llvm.load %1044 : !llvm.ptr -> i64
%1046 = llvm.load %708 : !llvm.ptr -> i64
%1047 = llvm.mlir.addressof @g_pow3 : !llvm.ptr
%1048 = llvm.load %1047 : !llvm.ptr -> !llvm.ptr
%1045 = func.call @partition_sum(%696, %1037, %1046, %1048) : (!llvm.ptr, i64, i64, !llvm.ptr) -> i64
%1050 = llvm.mlir.addressof @g_ds3 : !llvm.ptr
%1051 = llvm.load %1050 : !llvm.ptr -> !llvm.ptr
%1052 = llvm.getelementptr %1051[%1045] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1049 = llvm.load %1052 : !llvm.ptr -> i32
%1053 = arith.extsi %1049 : i32 to i64
%1054 = arith.constant 3 : i32
%1056 = arith.extsi %1054 : i32 to i64
%1055 = arith.cmpi slt, %1053, %1056 : i64
cf.cond_br %1055, ^bb126, ^bb127
^bb126:
%1057 = arith.constant 1 : i32
%1058 = arith.extsi %1057 : i32 to i64
llvm.store %1058, %1015 : i64, !llvm.ptr
cf.br ^bb125(%1036 : index)
^bb127:
cf.br ^bb128
^bb128:
%1059 = arith.addi %1036, %1028 : index
cf.br ^bb123(%1059 : index)
^bb125(%1060: index):
%1061 = llvm.load %1015 : !llvm.ptr -> i64
%1062 = arith.constant 1 : i32
%1064 = arith.extsi %1062 : i32 to i64
%1063 = arith.cmpi eq, %1061, %1064 : i64
%1065 = scf.if %1063 -> (i64) {
%1066 = arith.constant 2 : i32
%1067 = arith.extsi %1066 : i32 to i64
scf.yield %1067 : i64
} else {
%1068 = arith.constant 3 : i32
%1069 = arith.extsi %1068 : i32 to i64
scf.yield %1069 : i64
}
cf.br ^bb119(%1065 : i64)
^bb119(%1070: i64):
cf.br ^bb116(%1070 : i64)
^bb116(%1071: i64):
%1072 = arith.cmpi eq, %956, %1071 : i64
cf.cond_br %1072, ^bb129, ^bb130
^bb129:
%1073 = llvm.load %720 : !llvm.ptr -> i64
%1075 = arith.trunci %1073 : i64 to i32
%1076 = arith.index_cast %735 : index to i32
%1074 = arith.addi %1075, %1076 : i32
%1077 = arith.extsi %1074 : i32 to i64
llvm.store %1077, %720 : i64, !llvm.ptr
cf.br ^bb131
^bb130:
cf.br ^bb131
^bb131:
%1078 = arith.addi %735, %727 : index
cf.br ^bb84(%1078 : index)
^bb86(%1079: index):
%1080 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1081 = llvm.load %720 : !llvm.ptr -> i64
%1082 = llvm.call @printf(%1080, %1081) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%696) : (!llvm.ptr) -> ()
func.call @free(%691) : (!llvm.ptr) -> ()
func.call @free(%686) : (!llvm.ptr) -> ()
func.call @free(%681) : (!llvm.ptr) -> ()
%1088 = llvm.mlir.addressof @g_mask_count3 : !llvm.ptr
%1089 = llvm.load %1088 : !llvm.ptr -> !llvm.ptr
func.call @free(%1089) : (!llvm.ptr) -> ()
%1091 = llvm.mlir.addressof @g_sorted_masks3 : !llvm.ptr
%1092 = llvm.load %1091 : !llvm.ptr -> !llvm.ptr
func.call @free(%1092) : (!llvm.ptr) -> ()
%1094 = llvm.mlir.addressof @g_mask_count10 : !llvm.ptr
%1095 = llvm.load %1094 : !llvm.ptr -> !llvm.ptr
func.call @free(%1095) : (!llvm.ptr) -> ()
%1097 = llvm.mlir.addressof @g_sorted_masks10 : !llvm.ptr
%1098 = llvm.load %1097 : !llvm.ptr -> !llvm.ptr
func.call @free(%1098) : (!llvm.ptr) -> ()
%1100 = llvm.mlir.addressof @g_pow3 : !llvm.ptr
%1101 = llvm.load %1100 : !llvm.ptr -> !llvm.ptr
func.call @free(%1101) : (!llvm.ptr) -> ()
%1103 = llvm.mlir.addressof @g_pow10 : !llvm.ptr
%1104 = llvm.load %1103 : !llvm.ptr -> !llvm.ptr
func.call @free(%1104) : (!llvm.ptr) -> ()
%1106 = llvm.mlir.addressof @g_ds3 : !llvm.ptr
%1107 = llvm.load %1106 : !llvm.ptr -> !llvm.ptr
func.call @free(%1107) : (!llvm.ptr) -> ()
%1109 = llvm.mlir.addressof @g_ds10 : !llvm.ptr
%1110 = llvm.load %1109 : !llvm.ptr -> !llvm.ptr
func.call @free(%1110) : (!llvm.ptr) -> ()
%1111 = arith.constant 0 : i32
func.return %1111 : i32
}
}