Problem 986

Sum of G(c,d) for 1<=c,d<=160 via cellular automaton thresholds. Port of the C reference solver to pure Flow.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 986
# Sum of G(c,d) for 1<=c,d<=160 via cellular automaton thresholds.
# Port of the C reference solver to pure Flow.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function free(p: ptr<void>) -> void
    function malloc(n: i64) -> ptr<void>
    function memset(p: ptr<void>, c: i64, n: i64) -> ptr<void>
}

function extinct_for_k1(n: i64, k: i64) -> i64 {
    if k == 0 { return 1 }

    let size: i64 = n + 1
    let last: i64 = size - 1
    let cells: ptr<i64> = calloc(size, 8) as ptr<i64>
    cells[last] = k
    let mut zero_count: i64 = last

    while 1 != 0 {
        let mut i: i64 = 0
        while i < last {
            let old: i64 = cells[i]
            let nxt: i64 = (old + cells[i + 1]) >> 1
            cells[i] = nxt
            if old != 0 {
                if nxt == 0 { zero_count = zero_count + 1 }
            } else {
                if nxt != 0 { zero_count = zero_count - 1 }
            }
            i = i + 1
        }

        let old2: i64 = cells[last]
        let nxt2: i64 = (old2 + cells[0]) >> 1
        cells[last] = nxt2
        if old2 != 0 {
            if nxt2 == 0 { zero_count = zero_count + 1 }
        } else {
            if nxt2 != 0 { zero_count = zero_count - 1 }
        }

        if zero_count == size {
            free(cells as ptr<void>)
            return 1
        }
        if zero_count == 0 {
            free(cells as ptr<void>)
            return 0
        }
    }
    return 0
}

function threshold_k1_plain(n: i64) -> i64 {
    let mut lo: i64 = 0
    let mut hi: i64 = 1
    while extinct_for_k1(n, hi) != 0 {
        lo = hi
        hi = hi * 2
    }
    while lo + 1 < hi {
        let mid: i64 = (lo + hi) / 2
        if extinct_for_k1(n, mid) != 0 {
            lo = mid
        } else {
            hi = mid
        }
    }
    return lo
}

function predict_k1_from_previous(s: ptr<i64>, n: i64) -> i64 {
    let a: i64 = s[n - 32]
    let b: i64 = s[n - 24]
    let c: i64 = s[n - 16]
    let d: i64 = s[n - 8]
    return d + (d - c) + (d - 2 * c + b) + (d - 3 * c + 3 * b - a)
}

function threshold_k1_with_guess(n: i64, guess: i64) -> i64 {
    let mut lo: i64 = guess - 4096
    if lo < 0 { lo = 0 }
    let mut hi: i64 = guess + 4096

    # while (lo > 0 && !extinct_for_k1(n, lo)) { hi = lo; lo /= 2; }
    let mut done_lo: i64 = 0
    while done_lo == 0 {
        if lo == 0 {
            done_lo = 1
        } else {
            if extinct_for_k1(n, lo) == 0 {
                hi = lo
                lo = lo / 2
            } else {
                done_lo = 1
            }
        }
    }

    while extinct_for_k1(n, hi) != 0 {
        lo = hi
        hi = hi * 2
    }
    while lo + 1 < hi {
        let mid: i64 = (lo + hi) / 2
        if extinct_for_k1(n, mid) != 0 {
            lo = mid
        } else {
            hi = mid
        }
    }
    return lo
}

function gcd_ll(a: i64, b: i64) -> i64 {
    let mut aa: i64 = a
    let mut bb: i64 = b
    while bb != 0 {
        let t: i64 = aa % bb
        aa = bb
        bb = t
    }
    return aa
}

function get_exception(c: i64) -> i64 {
    # exc_c = {2,3,4,5,6,8,10}, exc_h = {3,5,7,11,13,21,31}
    if c == 2 { return 3 }
    if c == 3 { return 5 }
    if c == 4 { return 7 }
    if c == 5 { return 11 }
    if c == 6 { return 13 }
    if c == 8 { return 21 }
    if c == 10 { return 31 }
    return -1
}

function main() -> i32 {
    let limit: i64 = 160
    let max_n: i64 = limit + (limit - 1) / 2

    let s: ptr<i64> = calloc(max_n + 1, 8) as ptr<i64>

    let mut n: i64 = 1
    while n <= max_n {
        if n < 33 {
            s[n] = threshold_k1_plain(n)
        } else {
            let guess: i64 = predict_k1_from_previous(s, n)
            s[n] = threshold_k1_with_guess(n, guess)
        }
        n = n + 1
    }

    let dim: i64 = limit + 1
    let memo: ptr<i64> = malloc(dim * dim * 8) as ptr<i64>
    # memset to -1 (all bytes 0xFF = -1 for i64)
    memset(memo as ptr<void>, -1, dim * dim * 8)

    let mut total: i64 = 0
    let mut c: i64 = 1
    while c <= limit {
        let mut d: i64 = 1
        while d <= limit {
            let g: i64 = gcd_ll(c, d)
            let cr: i64 = c / g
            let dr: i64 = d / g
            let slot_idx: i64 = cr * dim + dr
            let mut val: i64 = memo[slot_idx]
            if val < 0 {
                let mut h: i64 = 0
                if dr == 1 {
                    let exc: i64 = get_exception(cr)
                    if exc >= 0 {
                        h = exc
                    } else {
                        h = s[dr + (cr - 1) / 2]
                    }
                } else {
                    h = s[dr + (cr - 1) / 2]
                }
                val = 2 * h + 1
                memo[slot_idx] = val
            }
            total = total + val
            d = d + 1
        }
        c = c + 1
    }

    free(s as ptr<void>)
    free(memo as ptr<void>)
    printf("%lld\n", total)
    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 extinct_for_k1_i64_i64(int64_t n, int64_t k);
int64_t threshold_k1_plain_i64(int64_t n);
int64_t predict_k1_from_previous_ptr_i64_i64(int64_t* s, int64_t n);
int64_t threshold_k1_with_guess_i64_i64(int64_t n, int64_t guess);
int64_t gcd_ll_i64_i64(int64_t a, int64_t b);
int64_t get_exception_i64(int64_t c);
int32_t main(void);





int64_t extinct_for_k1_i64_i64(int64_t n, int64_t k) {
    if (k == 0) {
        return 1;
    }
    int64_t size = (n + 1);
    int64_t last = (size - 1);
    int64_t* cells = (int64_t*)(((int64_t*)(calloc(size, 8))));
    cells[last] = k;
    int64_t zero_count = last;
    while (1 != 0) {
        int64_t i = 0;
        while (i < last) {
            int64_t old = cells[i];
            int64_t nxt = FLOW_CHECKED_SHR(((old + cells[(i + 1)])), (1));
            cells[i] = nxt;
            if (old != 0) {
                if (nxt == 0) {
                    zero_count = (zero_count + 1);
                }
            } else {
                if (nxt != 0) {
                    zero_count = (zero_count - 1);
                }
            }
            i = (i + 1);
        }
        int64_t old2 = cells[last];
        int64_t nxt2 = FLOW_CHECKED_SHR(((old2 + cells[0])), (1));
        cells[last] = nxt2;
        if (old2 != 0) {
            if (nxt2 == 0) {
                zero_count = (zero_count + 1);
            }
        } else {
            if (nxt2 != 0) {
                zero_count = (zero_count - 1);
            }
        }
        if (zero_count == size) {
            free(((void*)(cells)));
            return 1;
        }
        if (zero_count == 0) {
            free(((void*)(cells)));
            return 0;
        }
    }
    return 0;
}

int64_t threshold_k1_plain_i64(int64_t n) {
    int64_t lo = 0;
    int64_t hi = 1;
    while (extinct_for_k1_i64_i64(n, hi) != 0) {
        lo = hi;
        hi = (hi * 2);
    }
    while ((lo + 1) < hi) {
        int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
        if (extinct_for_k1_i64_i64(n, mid) != 0) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int64_t predict_k1_from_previous_ptr_i64_i64(int64_t* s, int64_t n) {
    int64_t a = s[(n - 32)];
    int64_t b = s[(n - 24)];
    int64_t c = s[(n - 16)];
    int64_t d = s[(n - 8)];
    return (((d + (d - c)) + ((d - (2 * c)) + b)) + (((d - (3 * c)) + (3 * b)) - a));
}

int64_t threshold_k1_with_guess_i64_i64(int64_t n, int64_t guess) {
    int64_t lo = (guess - 4096);
    if (lo < 0) {
        lo = 0;
    }
    int64_t hi = (guess + 4096);
    int64_t done_lo = 0;
    while (done_lo == 0) {
        if (lo == 0) {
            done_lo = 1;
        } else {
            if (extinct_for_k1_i64_i64(n, lo) == 0) {
                hi = lo;
                lo = FLOW_CHECKED_DIV((lo), (2));
            } else {
                done_lo = 1;
            }
        }
    }
    while (extinct_for_k1_i64_i64(n, hi) != 0) {
        lo = hi;
        hi = (hi * 2);
    }
    while ((lo + 1) < hi) {
        int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
        if (extinct_for_k1_i64_i64(n, mid) != 0) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int64_t gcd_ll_i64_i64(int64_t a, int64_t b) {
    int64_t aa = a;
    int64_t bb = b;
    while (bb != 0) {
        int64_t t = FLOW_CHECKED_MOD((aa), (bb));
        aa = bb;
        bb = t;
    }
    return aa;
}

int64_t get_exception_i64(int64_t c) {
    if (c == 2) {
        return 3;
    }
    if (c == 3) {
        return 5;
    }
    if (c == 4) {
        return 7;
    }
    if (c == 5) {
        return 11;
    }
    if (c == 6) {
        return 13;
    }
    if (c == 8) {
        return 21;
    }
    if (c == 10) {
        return 31;
    }
    return (-1);
}

int32_t main(void) {
    int64_t limit = 160;
    int64_t max_n = (limit + FLOW_CHECKED_DIV(((limit - 1)), (2)));
    int64_t* s = (int64_t*)(((int64_t*)(calloc((max_n + 1), 8))));
    int64_t n = 1;
    while (n <= max_n) {
        if (n < 33) {
            s[n] = threshold_k1_plain_i64(n);
        } else {
            int64_t guess = predict_k1_from_previous_ptr_i64_i64(s, n);
            s[n] = threshold_k1_with_guess_i64_i64(n, guess);
        }
        n = (n + 1);
    }
    int64_t dim = (limit + 1);
    int64_t* memo = (int64_t*)(((int64_t*)(malloc(((dim * dim) * 8)))));
    memset(((void*)(memo)), (-1), ((dim * dim) * 8));
    int64_t total = 0;
    int64_t c = 1;
    while (c <= limit) {
        int64_t d = 1;
        while (d <= limit) {
            int64_t g = gcd_ll_i64_i64(c, d);
            int64_t cr = FLOW_CHECKED_DIV((c), (g));
            int64_t dr = FLOW_CHECKED_DIV((d), (g));
            int64_t slot_idx = ((cr * dim) + dr);
            int64_t val = memo[slot_idx];
            if (val < 0) {
                int64_t h = 0;
                if (dr == 1) {
                    int64_t exc = get_exception_i64(cr);
                    if (exc >= 0) {
                        h = exc;
                    } else {
                        h = s[(dr + FLOW_CHECKED_DIV(((cr - 1)), (2)))];
                    }
                } else {
                    h = s[(dr + FLOW_CHECKED_DIV(((cr - 1)), (2)))];
                }
                val = ((2 * h) + 1);
                memo[slot_idx] = val;
            }
            total = (total + val);
            d = (d + 1);
        }
        c = (c + 1);
    }
    free(((void*)(s)));
    free(((void*)(memo)));
    printf("%lld\n", total);
    return 0;
}

Generated MLIR

module {
  llvm.func @printf(!llvm.ptr, ...) -> i32
  llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
  func.func private @calloc(i64, i64) -> !llvm.ptr
  func.func private @free(!llvm.ptr) -> ()
  func.func private @malloc(i64) -> !llvm.ptr
  func.func private @memset(!llvm.ptr, i64, i64) -> !llvm.ptr
  func.func @extinct_for_k1(%arg0: i64, %arg1: i64) -> i64 {
    %0 = arith.constant 0 : i32
    %2 = arith.extsi %0 : i32 to i64
    %1 = arith.cmpi eq, %arg1, %2 : i64
    cf.cond_br %1, ^bb0, ^bb1
    ^bb0:
      %3 = arith.constant 1 : i32
      %4 = arith.extsi %3 : i32 to i64
      func.return %4 : i64
    ^bb1:
      cf.br ^bb2
    ^bb2:
    %5 = arith.constant 1 : i32
    %7 = arith.extsi %5 : i32 to i64
    %6 = arith.addi %arg0, %7 : i64
    %8 = arith.constant 1 : i32
    %10 = arith.extsi %8 : i32 to i64
    %9 = arith.subi %6, %10 : i64
    %12 = arith.constant 8 : i32
    %13 = arith.extsi %12 : i32 to i64
    %11 = func.call @calloc(%6, %13) : (i64, i64) -> !llvm.ptr
    %14 = llvm.getelementptr %11[%9] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %arg1, %14 : i64, !llvm.ptr
    %15 = llvm.mlir.constant(1 : i64) : i64
    %16 = llvm.alloca %15 x i64 : (i64) -> !llvm.ptr
    llvm.store %9, %16 : i64, !llvm.ptr
    cf.br ^bb3
    ^bb3:
    %17 = arith.constant 1 : i32
    %18 = arith.constant 0 : i32
    %19 = arith.cmpi ne, %17, %18 : i32
    cf.cond_br %19, ^bb4, ^bb5
    ^bb4:
      %20 = arith.constant 0 : i32
      %21 = arith.extsi %20 : i32 to i64
      %22 = llvm.mlir.constant(1 : i64) : i64
      %23 = llvm.alloca %22 x i64 : (i64) -> !llvm.ptr
      llvm.store %21, %23 : i64, !llvm.ptr
      cf.br ^bb6
      ^bb6:
      %24 = llvm.load %23 : !llvm.ptr -> i64
      %25 = arith.cmpi slt, %24, %9 : i64
      cf.cond_br %25, ^bb7, ^bb8
      ^bb7:
        %27 = llvm.load %23 : !llvm.ptr -> i64
        %28 = llvm.getelementptr %11[%27] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %26 = llvm.load %28 : !llvm.ptr -> i64
        %30 = llvm.load %23 : !llvm.ptr -> i64
        %31 = arith.constant 1 : i32
        %33 = arith.extsi %31 : i32 to i64
        %32 = arith.addi %30, %33 : i64
        %34 = llvm.getelementptr %11[%32] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %29 = llvm.load %34 : !llvm.ptr -> i64
        %35 = arith.addi %26, %29 : i64
        %36 = arith.constant 1 : i32
        %38 = arith.extsi %36 : i32 to i64
        %37 = arith.shrsi %35, %38 : i64
        %39 = llvm.load %23 : !llvm.ptr -> i64
        %40 = llvm.getelementptr %11[%39] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %37, %40 : i64, !llvm.ptr
        %41 = arith.constant 0 : i32
        %43 = arith.extsi %41 : i32 to i64
        %42 = arith.cmpi ne, %26, %43 : i64
        cf.cond_br %42, ^bb9, ^bb10
        ^bb9:
          %44 = arith.constant 0 : i32
          %46 = arith.extsi %44 : i32 to i64
          %45 = arith.cmpi eq, %37, %46 : i64
          cf.cond_br %45, ^bb12, ^bb13
          ^bb12:
            %47 = llvm.load %16 : !llvm.ptr -> i64
            %48 = arith.constant 1 : i32
            %50 = arith.extsi %48 : i32 to i64
            %49 = arith.addi %47, %50 : i64
            llvm.store %49, %16 : i64, !llvm.ptr
            cf.br ^bb14
          ^bb13:
            cf.br ^bb14
          ^bb14:
          cf.br ^bb11
        ^bb10:
          %51 = arith.constant 0 : i32
          %53 = arith.extsi %51 : i32 to i64
          %52 = arith.cmpi ne, %37, %53 : i64
          cf.cond_br %52, ^bb15, ^bb16
          ^bb15:
            %54 = llvm.load %16 : !llvm.ptr -> i64
            %55 = arith.constant 1 : i32
            %57 = arith.extsi %55 : i32 to i64
            %56 = arith.subi %54, %57 : i64
            llvm.store %56, %16 : i64, !llvm.ptr
            cf.br ^bb17
          ^bb16:
            cf.br ^bb17
          ^bb17:
          cf.br ^bb11
        ^bb11:
        %58 = llvm.load %23 : !llvm.ptr -> i64
        %59 = arith.constant 1 : i32
        %61 = arith.extsi %59 : i32 to i64
        %60 = arith.addi %58, %61 : i64
        llvm.store %60, %23 : i64, !llvm.ptr
        cf.br ^bb6
      ^bb8:
      %63 = llvm.getelementptr %11[%9] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %62 = llvm.load %63 : !llvm.ptr -> i64
      %65 = arith.constant 0 : i32
      %66 = arith.extsi %65 : i32 to i64
      %67 = llvm.getelementptr %11[%66] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %64 = llvm.load %67 : !llvm.ptr -> i64
      %68 = arith.addi %62, %64 : i64
      %69 = arith.constant 1 : i32
      %71 = arith.extsi %69 : i32 to i64
      %70 = arith.shrsi %68, %71 : i64
      %72 = llvm.getelementptr %11[%9] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %70, %72 : i64, !llvm.ptr
      %73 = arith.constant 0 : i32
      %75 = arith.extsi %73 : i32 to i64
      %74 = arith.cmpi ne, %62, %75 : i64
      cf.cond_br %74, ^bb18, ^bb19
      ^bb18:
        %76 = arith.constant 0 : i32
        %78 = arith.extsi %76 : i32 to i64
        %77 = arith.cmpi eq, %70, %78 : i64
        cf.cond_br %77, ^bb21, ^bb22
        ^bb21:
          %79 = llvm.load %16 : !llvm.ptr -> i64
          %80 = arith.constant 1 : i32
          %82 = arith.extsi %80 : i32 to i64
          %81 = arith.addi %79, %82 : i64
          llvm.store %81, %16 : i64, !llvm.ptr
          cf.br ^bb23
        ^bb22:
          cf.br ^bb23
        ^bb23:
        cf.br ^bb20
      ^bb19:
        %83 = arith.constant 0 : i32
        %85 = arith.extsi %83 : i32 to i64
        %84 = arith.cmpi ne, %70, %85 : i64
        cf.cond_br %84, ^bb24, ^bb25
        ^bb24:
          %86 = llvm.load %16 : !llvm.ptr -> i64
          %87 = arith.constant 1 : i32
          %89 = arith.extsi %87 : i32 to i64
          %88 = arith.subi %86, %89 : i64
          llvm.store %88, %16 : i64, !llvm.ptr
          cf.br ^bb26
        ^bb25:
          cf.br ^bb26
        ^bb26:
        cf.br ^bb20
      ^bb20:
      %90 = llvm.load %16 : !llvm.ptr -> i64
      %91 = arith.cmpi eq, %90, %6 : i64
      cf.cond_br %91, ^bb27, ^bb28
      ^bb27:
        func.call @free(%11) : (!llvm.ptr) -> ()
        %93 = arith.constant 1 : i32
        %94 = arith.extsi %93 : i32 to i64
        func.return %94 : i64
      ^bb28:
        cf.br ^bb29
      ^bb29:
      %95 = llvm.load %16 : !llvm.ptr -> i64
      %96 = arith.constant 0 : i32
      %98 = arith.extsi %96 : i32 to i64
      %97 = arith.cmpi eq, %95, %98 : i64
      cf.cond_br %97, ^bb30, ^bb31
      ^bb30:
        func.call @free(%11) : (!llvm.ptr) -> ()
        %100 = arith.constant 0 : i32
        %101 = arith.extsi %100 : i32 to i64
        func.return %101 : i64
      ^bb31:
        cf.br ^bb32
      ^bb32:
      cf.br ^bb3
    ^bb5:
    %102 = arith.constant 0 : i32
    %103 = arith.extsi %102 : i32 to i64
    func.return %103 : i64
  }
  func.func @threshold_k1_plain(%arg0: i64) -> i64 {
    %104 = arith.constant 0 : i32
    %105 = arith.extsi %104 : i32 to i64
    %106 = llvm.mlir.constant(1 : i64) : i64
    %107 = llvm.alloca %106 x i64 : (i64) -> !llvm.ptr
    llvm.store %105, %107 : 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
    cf.br ^bb33
    ^bb33:
    %113 = llvm.load %111 : !llvm.ptr -> i64
    %112 = func.call @extinct_for_k1(%arg0, %113) : (i64, i64) -> i64
    %114 = arith.constant 0 : i32
    %116 = arith.extsi %114 : i32 to i64
    %115 = arith.cmpi ne, %112, %116 : i64
    cf.cond_br %115, ^bb34, ^bb35
    ^bb34:
      %117 = llvm.load %111 : !llvm.ptr -> i64
      llvm.store %117, %107 : i64, !llvm.ptr
      %118 = llvm.load %111 : !llvm.ptr -> i64
      %119 = arith.constant 2 : i32
      %121 = arith.extsi %119 : i32 to i64
      %120 = arith.muli %118, %121 : i64
      llvm.store %120, %111 : i64, !llvm.ptr
      cf.br ^bb33
    ^bb35:
    cf.br ^bb36
    ^bb36:
    %122 = llvm.load %107 : !llvm.ptr -> i64
    %123 = arith.constant 1 : i32
    %125 = arith.extsi %123 : i32 to i64
    %124 = arith.addi %122, %125 : i64
    %126 = llvm.load %111 : !llvm.ptr -> i64
    %127 = arith.cmpi slt, %124, %126 : i64
    cf.cond_br %127, ^bb37, ^bb38
    ^bb37:
      %128 = llvm.load %107 : !llvm.ptr -> i64
      %129 = llvm.load %111 : !llvm.ptr -> i64
      %130 = arith.addi %128, %129 : i64
      %131 = arith.constant 2 : i32
      %133 = arith.extsi %131 : i32 to i64
      %132 = arith.divsi %130, %133 : i64
      %134 = func.call @extinct_for_k1(%arg0, %132) : (i64, i64) -> i64
      %135 = arith.constant 0 : i32
      %137 = arith.extsi %135 : i32 to i64
      %136 = arith.cmpi ne, %134, %137 : i64
      cf.cond_br %136, ^bb39, ^bb40
      ^bb39:
        llvm.store %132, %107 : i64, !llvm.ptr
        cf.br ^bb41
      ^bb40:
        llvm.store %132, %111 : i64, !llvm.ptr
        cf.br ^bb41
      ^bb41:
      cf.br ^bb36
    ^bb38:
    %138 = llvm.load %107 : !llvm.ptr -> i64
    func.return %138 : i64
  }
  func.func @predict_k1_from_previous(%arg0: !llvm.ptr, %arg1: i64) -> i64 {
    %140 = arith.constant 32 : i32
    %142 = arith.extsi %140 : i32 to i64
    %141 = arith.subi %arg1, %142 : i64
    %143 = llvm.getelementptr %arg0[%141] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %139 = llvm.load %143 : !llvm.ptr -> i64
    %145 = arith.constant 24 : i32
    %147 = arith.extsi %145 : i32 to i64
    %146 = arith.subi %arg1, %147 : i64
    %148 = llvm.getelementptr %arg0[%146] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %144 = llvm.load %148 : !llvm.ptr -> i64
    %150 = arith.constant 16 : i32
    %152 = arith.extsi %150 : i32 to i64
    %151 = arith.subi %arg1, %152 : i64
    %153 = llvm.getelementptr %arg0[%151] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %149 = llvm.load %153 : !llvm.ptr -> i64
    %155 = arith.constant 8 : i32
    %157 = arith.extsi %155 : i32 to i64
    %156 = arith.subi %arg1, %157 : i64
    %158 = llvm.getelementptr %arg0[%156] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %154 = llvm.load %158 : !llvm.ptr -> i64
    %159 = arith.subi %154, %149 : i64
    %160 = arith.addi %154, %159 : i64
    %161 = arith.constant 2 : i32
    %163 = arith.extsi %161 : i32 to i64
    %162 = arith.muli %163, %149 : i64
    %164 = arith.subi %154, %162 : i64
    %165 = arith.addi %164, %144 : i64
    %166 = arith.addi %160, %165 : i64
    %167 = arith.constant 3 : i32
    %169 = arith.extsi %167 : i32 to i64
    %168 = arith.muli %169, %149 : i64
    %170 = arith.subi %154, %168 : i64
    %171 = arith.constant 3 : i32
    %173 = arith.extsi %171 : i32 to i64
    %172 = arith.muli %173, %144 : i64
    %174 = arith.addi %170, %172 : i64
    %175 = arith.subi %174, %139 : i64
    %176 = arith.addi %166, %175 : i64
    func.return %176 : i64
  }
  func.func @threshold_k1_with_guess(%arg0: i64, %arg1: i64) -> i64 {
    %177 = arith.constant 4096 : i32
    %179 = arith.extsi %177 : i32 to i64
    %178 = arith.subi %arg1, %179 : i64
    %180 = llvm.mlir.constant(1 : i64) : i64
    %181 = llvm.alloca %180 x i64 : (i64) -> !llvm.ptr
    llvm.store %178, %181 : i64, !llvm.ptr
    %182 = llvm.load %181 : !llvm.ptr -> i64
    %183 = arith.constant 0 : i32
    %185 = arith.extsi %183 : i32 to i64
    %184 = arith.cmpi slt, %182, %185 : i64
    cf.cond_br %184, ^bb42, ^bb43
    ^bb42:
      %186 = arith.constant 0 : i32
      %187 = arith.extsi %186 : i32 to i64
      llvm.store %187, %181 : i64, !llvm.ptr
      cf.br ^bb44
    ^bb43:
      cf.br ^bb44
    ^bb44:
    %188 = arith.constant 4096 : i32
    %190 = arith.extsi %188 : i32 to i64
    %189 = arith.addi %arg1, %190 : i64
    %191 = llvm.mlir.constant(1 : i64) : i64
    %192 = llvm.alloca %191 x i64 : (i64) -> !llvm.ptr
    llvm.store %189, %192 : i64, !llvm.ptr
    %193 = arith.constant 0 : i32
    %194 = arith.extsi %193 : i32 to i64
    %195 = llvm.mlir.constant(1 : i64) : i64
    %196 = llvm.alloca %195 x i64 : (i64) -> !llvm.ptr
    llvm.store %194, %196 : i64, !llvm.ptr
    cf.br ^bb45
    ^bb45:
    %197 = llvm.load %196 : !llvm.ptr -> i64
    %198 = arith.constant 0 : i32
    %200 = arith.extsi %198 : i32 to i64
    %199 = arith.cmpi eq, %197, %200 : i64
    cf.cond_br %199, ^bb46, ^bb47
    ^bb46:
      %201 = llvm.load %181 : !llvm.ptr -> i64
      %202 = arith.constant 0 : i32
      %204 = arith.extsi %202 : i32 to i64
      %203 = arith.cmpi eq, %201, %204 : i64
      cf.cond_br %203, ^bb48, ^bb49
      ^bb48:
        %205 = arith.constant 1 : i32
        %206 = arith.extsi %205 : i32 to i64
        llvm.store %206, %196 : i64, !llvm.ptr
        cf.br ^bb50
      ^bb49:
        %208 = llvm.load %181 : !llvm.ptr -> i64
        %207 = func.call @extinct_for_k1(%arg0, %208) : (i64, i64) -> i64
        %209 = arith.constant 0 : i32
        %211 = arith.extsi %209 : i32 to i64
        %210 = arith.cmpi eq, %207, %211 : i64
        cf.cond_br %210, ^bb51, ^bb52
        ^bb51:
          %212 = llvm.load %181 : !llvm.ptr -> i64
          llvm.store %212, %192 : i64, !llvm.ptr
          %213 = llvm.load %181 : !llvm.ptr -> i64
          %214 = arith.constant 2 : i32
          %216 = arith.extsi %214 : i32 to i64
          %215 = arith.divsi %213, %216 : i64
          llvm.store %215, %181 : i64, !llvm.ptr
          cf.br ^bb53
        ^bb52:
          %217 = arith.constant 1 : i32
          %218 = arith.extsi %217 : i32 to i64
          llvm.store %218, %196 : i64, !llvm.ptr
          cf.br ^bb53
        ^bb53:
        cf.br ^bb50
      ^bb50:
      cf.br ^bb45
    ^bb47:
    cf.br ^bb54
    ^bb54:
    %220 = llvm.load %192 : !llvm.ptr -> i64
    %219 = func.call @extinct_for_k1(%arg0, %220) : (i64, i64) -> i64
    %221 = arith.constant 0 : i32
    %223 = arith.extsi %221 : i32 to i64
    %222 = arith.cmpi ne, %219, %223 : i64
    cf.cond_br %222, ^bb55, ^bb56
    ^bb55:
      %224 = llvm.load %192 : !llvm.ptr -> i64
      llvm.store %224, %181 : i64, !llvm.ptr
      %225 = llvm.load %192 : !llvm.ptr -> i64
      %226 = arith.constant 2 : i32
      %228 = arith.extsi %226 : i32 to i64
      %227 = arith.muli %225, %228 : i64
      llvm.store %227, %192 : i64, !llvm.ptr
      cf.br ^bb54
    ^bb56:
    cf.br ^bb57
    ^bb57:
    %229 = llvm.load %181 : !llvm.ptr -> i64
    %230 = arith.constant 1 : i32
    %232 = arith.extsi %230 : i32 to i64
    %231 = arith.addi %229, %232 : i64
    %233 = llvm.load %192 : !llvm.ptr -> i64
    %234 = arith.cmpi slt, %231, %233 : i64
    cf.cond_br %234, ^bb58, ^bb59
    ^bb58:
      %235 = llvm.load %181 : !llvm.ptr -> i64
      %236 = llvm.load %192 : !llvm.ptr -> i64
      %237 = arith.addi %235, %236 : i64
      %238 = arith.constant 2 : i32
      %240 = arith.extsi %238 : i32 to i64
      %239 = arith.divsi %237, %240 : i64
      %241 = func.call @extinct_for_k1(%arg0, %239) : (i64, i64) -> i64
      %242 = arith.constant 0 : i32
      %244 = arith.extsi %242 : i32 to i64
      %243 = arith.cmpi ne, %241, %244 : i64
      cf.cond_br %243, ^bb60, ^bb61
      ^bb60:
        llvm.store %239, %181 : i64, !llvm.ptr
        cf.br ^bb62
      ^bb61:
        llvm.store %239, %192 : i64, !llvm.ptr
        cf.br ^bb62
      ^bb62:
      cf.br ^bb57
    ^bb59:
    %245 = llvm.load %181 : !llvm.ptr -> i64
    func.return %245 : i64
  }
  func.func @gcd_ll(%arg0: i64, %arg1: i64) -> i64 {
    %246 = llvm.mlir.constant(1 : i64) : i64
    %247 = llvm.alloca %246 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %247 : i64, !llvm.ptr
    %248 = llvm.mlir.constant(1 : i64) : i64
    %249 = llvm.alloca %248 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %249 : i64, !llvm.ptr
    cf.br ^bb63
    ^bb63:
    %250 = llvm.load %249 : !llvm.ptr -> i64
    %251 = arith.constant 0 : i32
    %253 = arith.extsi %251 : i32 to i64
    %252 = arith.cmpi ne, %250, %253 : i64
    cf.cond_br %252, ^bb64, ^bb65
    ^bb64:
      %254 = llvm.load %247 : !llvm.ptr -> i64
      %255 = llvm.load %249 : !llvm.ptr -> i64
      %256 = arith.remsi %254, %255 : i64
      %257 = llvm.load %249 : !llvm.ptr -> i64
      llvm.store %257, %247 : i64, !llvm.ptr
      llvm.store %256, %249 : i64, !llvm.ptr
      cf.br ^bb63
    ^bb65:
    %258 = llvm.load %247 : !llvm.ptr -> i64
    func.return %258 : i64
  }
  func.func @get_exception(%arg0: i64) -> i64 {
    %259 = arith.constant 2 : i32
    %261 = arith.extsi %259 : i32 to i64
    %260 = arith.cmpi eq, %arg0, %261 : i64
    cf.cond_br %260, ^bb66, ^bb67
    ^bb66:
      %262 = arith.constant 3 : i32
      %263 = arith.extsi %262 : i32 to i64
      func.return %263 : i64
    ^bb67:
      cf.br ^bb68
    ^bb68:
    %264 = arith.constant 3 : i32
    %266 = arith.extsi %264 : i32 to i64
    %265 = arith.cmpi eq, %arg0, %266 : i64
    cf.cond_br %265, ^bb69, ^bb70
    ^bb69:
      %267 = arith.constant 5 : i32
      %268 = arith.extsi %267 : i32 to i64
      func.return %268 : i64
    ^bb70:
      cf.br ^bb71
    ^bb71:
    %269 = arith.constant 4 : i32
    %271 = arith.extsi %269 : i32 to i64
    %270 = arith.cmpi eq, %arg0, %271 : i64
    cf.cond_br %270, ^bb72, ^bb73
    ^bb72:
      %272 = arith.constant 7 : i32
      %273 = arith.extsi %272 : i32 to i64
      func.return %273 : i64
    ^bb73:
      cf.br ^bb74
    ^bb74:
    %274 = arith.constant 5 : i32
    %276 = arith.extsi %274 : i32 to i64
    %275 = arith.cmpi eq, %arg0, %276 : i64
    cf.cond_br %275, ^bb75, ^bb76
    ^bb75:
      %277 = arith.constant 11 : i32
      %278 = arith.extsi %277 : i32 to i64
      func.return %278 : i64
    ^bb76:
      cf.br ^bb77
    ^bb77:
    %279 = arith.constant 6 : i32
    %281 = arith.extsi %279 : i32 to i64
    %280 = arith.cmpi eq, %arg0, %281 : i64
    cf.cond_br %280, ^bb78, ^bb79
    ^bb78:
      %282 = arith.constant 13 : i32
      %283 = arith.extsi %282 : i32 to i64
      func.return %283 : i64
    ^bb79:
      cf.br ^bb80
    ^bb80:
    %284 = arith.constant 8 : i32
    %286 = arith.extsi %284 : i32 to i64
    %285 = arith.cmpi eq, %arg0, %286 : i64
    cf.cond_br %285, ^bb81, ^bb82
    ^bb81:
      %287 = arith.constant 21 : i32
      %288 = arith.extsi %287 : i32 to i64
      func.return %288 : i64
    ^bb82:
      cf.br ^bb83
    ^bb83:
    %289 = arith.constant 10 : i32
    %291 = arith.extsi %289 : i32 to i64
    %290 = arith.cmpi eq, %arg0, %291 : i64
    cf.cond_br %290, ^bb84, ^bb85
    ^bb84:
      %292 = arith.constant 31 : i32
      %293 = arith.extsi %292 : i32 to i64
      func.return %293 : i64
    ^bb85:
      cf.br ^bb86
    ^bb86:
    %294 = arith.constant 1 : i32
    %296 = arith.constant 0 : i32
    %295 = arith.subi %296, %294 : i32
    %297 = arith.extsi %295 : i32 to i64
    func.return %297 : i64
  }
  func.func @main() -> i32 {
    %298 = arith.constant 160 : i32
    %299 = arith.extsi %298 : i32 to i64
    %300 = arith.constant 1 : i32
    %302 = arith.extsi %300 : i32 to i64
    %301 = arith.subi %299, %302 : i64
    %303 = arith.constant 2 : i32
    %305 = arith.extsi %303 : i32 to i64
    %304 = arith.divsi %301, %305 : i64
    %306 = arith.addi %299, %304 : i64
    %308 = arith.constant 1 : i32
    %310 = arith.extsi %308 : i32 to i64
    %309 = arith.addi %306, %310 : i64
    %311 = arith.constant 8 : i32
    %312 = arith.extsi %311 : i32 to i64
    %307 = func.call @calloc(%309, %312) : (i64, i64) -> !llvm.ptr
    %313 = arith.constant 1 : i32
    %314 = arith.extsi %313 : i32 to i64
    %315 = llvm.mlir.constant(1 : i64) : i64
    %316 = llvm.alloca %315 x i64 : (i64) -> !llvm.ptr
    llvm.store %314, %316 : i64, !llvm.ptr
    cf.br ^bb87
    ^bb87:
    %317 = llvm.load %316 : !llvm.ptr -> i64
    %318 = arith.cmpi sle, %317, %306 : i64
    cf.cond_br %318, ^bb88, ^bb89
    ^bb88:
      %319 = llvm.load %316 : !llvm.ptr -> i64
      %320 = arith.constant 33 : i32
      %322 = arith.extsi %320 : i32 to i64
      %321 = arith.cmpi slt, %319, %322 : i64
      cf.cond_br %321, ^bb90, ^bb91
      ^bb90:
        %324 = llvm.load %316 : !llvm.ptr -> i64
        %323 = func.call @threshold_k1_plain(%324) : (i64) -> i64
        %325 = llvm.load %316 : !llvm.ptr -> i64
        %326 = llvm.getelementptr %307[%325] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %323, %326 : i64, !llvm.ptr
        cf.br ^bb92
      ^bb91:
        %328 = llvm.load %316 : !llvm.ptr -> i64
        %327 = func.call @predict_k1_from_previous(%307, %328) : (!llvm.ptr, i64) -> i64
        %330 = llvm.load %316 : !llvm.ptr -> i64
        %329 = func.call @threshold_k1_with_guess(%330, %327) : (i64, i64) -> i64
        %331 = llvm.load %316 : !llvm.ptr -> i64
        %332 = llvm.getelementptr %307[%331] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %329, %332 : i64, !llvm.ptr
        cf.br ^bb92
      ^bb92:
      %333 = llvm.load %316 : !llvm.ptr -> i64
      %334 = arith.constant 1 : i32
      %336 = arith.extsi %334 : i32 to i64
      %335 = arith.addi %333, %336 : i64
      llvm.store %335, %316 : i64, !llvm.ptr
      cf.br ^bb87
    ^bb89:
    %337 = arith.constant 1 : i32
    %339 = arith.extsi %337 : i32 to i64
    %338 = arith.addi %299, %339 : i64
    %341 = arith.muli %338, %338 : i64
    %342 = arith.constant 8 : i32
    %344 = arith.extsi %342 : i32 to i64
    %343 = arith.muli %341, %344 : i64
    %340 = func.call @malloc(%343) : (i64) -> !llvm.ptr
    %346 = arith.constant 1 : i32
    %348 = arith.constant 0 : i32
    %347 = arith.subi %348, %346 : i32
    %349 = arith.muli %338, %338 : i64
    %350 = arith.constant 8 : i32
    %352 = arith.extsi %350 : i32 to i64
    %351 = arith.muli %349, %352 : i64
    %353 = arith.extsi %347 : i32 to i64
    %345 = func.call @memset(%340, %353, %351) : (!llvm.ptr, i64, i64) -> !llvm.ptr
    %354 = arith.constant 0 : i32
    %355 = arith.extsi %354 : i32 to i64
    %356 = llvm.mlir.constant(1 : i64) : i64
    %357 = llvm.alloca %356 x i64 : (i64) -> !llvm.ptr
    llvm.store %355, %357 : i64, !llvm.ptr
    %358 = arith.constant 1 : i32
    %359 = arith.extsi %358 : i32 to i64
    %360 = llvm.mlir.constant(1 : i64) : i64
    %361 = llvm.alloca %360 x i64 : (i64) -> !llvm.ptr
    llvm.store %359, %361 : i64, !llvm.ptr
    cf.br ^bb93
    ^bb93:
    %362 = llvm.load %361 : !llvm.ptr -> i64
    %363 = arith.cmpi sle, %362, %299 : i64
    cf.cond_br %363, ^bb94, ^bb95
    ^bb94:
      %364 = arith.constant 1 : i32
      %365 = arith.extsi %364 : i32 to i64
      %366 = llvm.mlir.constant(1 : i64) : i64
      %367 = llvm.alloca %366 x i64 : (i64) -> !llvm.ptr
      llvm.store %365, %367 : i64, !llvm.ptr
      cf.br ^bb96
      ^bb96:
      %368 = llvm.load %367 : !llvm.ptr -> i64
      %369 = arith.cmpi sle, %368, %299 : i64
      cf.cond_br %369, ^bb97, ^bb98
      ^bb97:
        %371 = llvm.load %361 : !llvm.ptr -> i64
        %372 = llvm.load %367 : !llvm.ptr -> i64
        %370 = func.call @gcd_ll(%371, %372) : (i64, i64) -> i64
        %373 = llvm.load %361 : !llvm.ptr -> i64
        %374 = arith.divsi %373, %370 : i64
        %375 = llvm.load %367 : !llvm.ptr -> i64
        %376 = arith.divsi %375, %370 : i64
        %377 = arith.muli %374, %338 : i64
        %378 = arith.addi %377, %376 : i64
        %380 = llvm.getelementptr %340[%378] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %379 = llvm.load %380 : !llvm.ptr -> i64
        %381 = llvm.mlir.constant(1 : i64) : i64
        %382 = llvm.alloca %381 x i64 : (i64) -> !llvm.ptr
        llvm.store %379, %382 : i64, !llvm.ptr
        %383 = llvm.load %382 : !llvm.ptr -> i64
        %384 = arith.constant 0 : i32
        %386 = arith.extsi %384 : i32 to i64
        %385 = arith.cmpi slt, %383, %386 : i64
        cf.cond_br %385, ^bb99, ^bb100
        ^bb99:
          %387 = arith.constant 0 : i32
          %388 = arith.extsi %387 : i32 to i64
          %389 = llvm.mlir.constant(1 : i64) : i64
          %390 = llvm.alloca %389 x i64 : (i64) -> !llvm.ptr
          llvm.store %388, %390 : i64, !llvm.ptr
          %391 = arith.constant 1 : i32
          %393 = arith.extsi %391 : i32 to i64
          %392 = arith.cmpi eq, %376, %393 : i64
          cf.cond_br %392, ^bb102, ^bb103
          ^bb102:
            %394 = func.call @get_exception(%374) : (i64) -> i64
            %395 = arith.constant 0 : i32
            %397 = arith.extsi %395 : i32 to i64
            %396 = arith.cmpi sge, %394, %397 : i64
            cf.cond_br %396, ^bb105, ^bb106
            ^bb105:
              llvm.store %394, %390 : i64, !llvm.ptr
              cf.br ^bb107
            ^bb106:
              %399 = arith.constant 1 : i32
              %401 = arith.extsi %399 : i32 to i64
              %400 = arith.subi %374, %401 : i64
              %402 = arith.constant 2 : i32
              %404 = arith.extsi %402 : i32 to i64
              %403 = arith.divsi %400, %404 : i64
              %405 = arith.addi %376, %403 : i64
              %406 = llvm.getelementptr %307[%405] : (!llvm.ptr, i64) -> !llvm.ptr, i64
              %398 = llvm.load %406 : !llvm.ptr -> i64
              llvm.store %398, %390 : i64, !llvm.ptr
              cf.br ^bb107
            ^bb107:
            cf.br ^bb104
          ^bb103:
            %408 = arith.constant 1 : i32
            %410 = arith.extsi %408 : i32 to i64
            %409 = arith.subi %374, %410 : i64
            %411 = arith.constant 2 : i32
            %413 = arith.extsi %411 : i32 to i64
            %412 = arith.divsi %409, %413 : i64
            %414 = arith.addi %376, %412 : i64
            %415 = llvm.getelementptr %307[%414] : (!llvm.ptr, i64) -> !llvm.ptr, i64
            %407 = llvm.load %415 : !llvm.ptr -> i64
            llvm.store %407, %390 : i64, !llvm.ptr
            cf.br ^bb104
          ^bb104:
          %416 = arith.constant 2 : i32
          %417 = llvm.load %390 : !llvm.ptr -> i64
          %419 = arith.extsi %416 : i32 to i64
          %418 = arith.muli %419, %417 : i64
          %420 = arith.constant 1 : i32
          %422 = arith.extsi %420 : i32 to i64
          %421 = arith.addi %418, %422 : i64
          llvm.store %421, %382 : i64, !llvm.ptr
          %423 = llvm.load %382 : !llvm.ptr -> i64
          %424 = llvm.getelementptr %340[%378] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          llvm.store %423, %424 : i64, !llvm.ptr
          cf.br ^bb101
        ^bb100:
          cf.br ^bb101
        ^bb101:
        %425 = llvm.load %357 : !llvm.ptr -> i64
        %426 = llvm.load %382 : !llvm.ptr -> i64
        %427 = arith.addi %425, %426 : i64
        llvm.store %427, %357 : i64, !llvm.ptr
        %428 = llvm.load %367 : !llvm.ptr -> i64
        %429 = arith.constant 1 : i32
        %431 = arith.extsi %429 : i32 to i64
        %430 = arith.addi %428, %431 : i64
        llvm.store %430, %367 : i64, !llvm.ptr
        cf.br ^bb96
      ^bb98:
      %432 = llvm.load %361 : !llvm.ptr -> i64
      %433 = arith.constant 1 : i32
      %435 = arith.extsi %433 : i32 to i64
      %434 = arith.addi %432, %435 : i64
      llvm.store %434, %361 : i64, !llvm.ptr
      cf.br ^bb93
    ^bb95:
    func.call @free(%307) : (!llvm.ptr) -> ()
    func.call @free(%340) : (!llvm.ptr) -> ()
    %438 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %439 = llvm.load %357 : !llvm.ptr -> i64
    %440 = llvm.call @printf(%438, %439) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    %441 = arith.constant 0 : i32
    func.return %441 : i32
  }
}