Problem 531

Chinese Leftovers — sum f(n,m) for 10^6 <= n < m < 10^6+5000.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 531
# Chinese Leftovers — sum f(n,m) for 10^6 <= n < m < 10^6+5000.

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

function egcd(a0: i64, b0: i64, out_s: ptr<i64>, out_t: ptr<i64>) -> i64 {
    let mut old_r: i64 = a0
    let mut r: i64 = b0
    let mut old_s: i64 = 1
    let mut s: i64 = 0
    while r != 0 {
        let q: i64 = old_r / r
        let nr: i64 = old_r - q * r
        old_r = r
        r = nr
        let ns: i64 = old_s - q * s
        old_s = s
        s = ns
    }
    let mut bezout_t: i64 = 0
    if b0 != 0 {
        bezout_t = (old_r - old_s * a0) / b0
    }
    out_s[0] = old_s
    out_t[0] = bezout_t
    return old_r
}

function gen_crt(a1: i64, a2: i64, n1: i64, n2: i64, tmp: ptr<i64>) -> i64 {
    let g: i64 = egcd(n1, n2, tmp, tmp + 1)
    let u: i64 = tmp[0]
    let v: i64 = tmp[1]
    if g == 1 {
        let mut x: i64 = a1 * v * n2 + a2 * u * n1
        let m: i64 = n1 * n2
        x = x % m
        if x < 0 { x = x + m }
        return x
    }
    if a1 % g != a2 % g { return 0 }
    let M: i64 = (n1 * n2) / g
    # Use i128 for intermediate
    let t: i128 = ((a1 as i128) * (v as i128) * (n2 as i128)
        + (a2 as i128) * (u as i128) * (n1 as i128)) / (g as i128)
    let mut x: i64 = (t % (M as i128)) as i64
    if x < 0 { x = x + M }
    return x
}

function main() -> i32 {
    let start: i64 = 1000000
    let limit: i64 = 1005000
    let phi: ptr<i32> = calloc(limit + 1, 4)
    let tmp: ptr<i64> = calloc(4, 8)
    if phi == null || tmp == null { return 1 }
    let mut i: i64 = 0
    while i <= limit {
        phi[i] = i as i32
        i = i + 1
    }
    let mut p: i64 = 2
    while p <= limit {
        if (phi[p] as i64) == p {
            phi[p] = (p - 1) as i32
            let mut j: i64 = 2 * p
            while j <= limit {
                phi[j] = (phi[j] as i64 - (phi[j] as i64) / p) as i32
                j = j + p
            }
        }
        p = p + 1
    }
    let mut total: i64 = 0
    let mut n: i64 = start
    while n < limit {
        let mut m: i64 = n + 1
        while m < limit {
            total = total + gen_crt(phi[n] as i64, phi[m] as i64, n, m, tmp)
            m = m + 1
        }
        n = n + 1
    }
    printf("%lld\n", total)
    free(phi)
    free(tmp)
    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 egcd_i64_i64_ptr_i64_ptr_i64(int64_t a0, int64_t b0, int64_t* out_s, int64_t* out_t);
int64_t gen_crt_i64_i64_i64_i64_ptr_i64(int64_t a1, int64_t a2, int64_t n1, int64_t n2, int64_t* tmp);
int32_t main(void);



int64_t egcd_i64_i64_ptr_i64_ptr_i64(int64_t a0, int64_t b0, int64_t* out_s, int64_t* out_t) {
    int64_t old_r = a0;
    int64_t r = b0;
    int64_t old_s = 1;
    int64_t s = 0;
    while (r != 0) {
        int64_t q = FLOW_CHECKED_DIV((old_r), (r));
        int64_t nr = (old_r - (q * r));
        old_r = r;
        r = nr;
        int64_t ns = (old_s - (q * s));
        old_s = s;
        s = ns;
    }
    int64_t bezout_t = 0;
    if (b0 != 0) {
        bezout_t = FLOW_CHECKED_DIV(((old_r - (old_s * a0))), (b0));
    }
    out_s[0] = old_s;
    out_t[0] = bezout_t;
    return old_r;
}

int64_t gen_crt_i64_i64_i64_i64_ptr_i64(int64_t a1, int64_t a2, int64_t n1, int64_t n2, int64_t* tmp) {
    int64_t g = egcd_i64_i64_ptr_i64_ptr_i64(n1, n2, tmp, (tmp + 1));
    int64_t u = tmp[0];
    int64_t v = tmp[1];
    if (g == 1) {
        int64_t x = (((a1 * v) * n2) + ((a2 * u) * n1));
        int64_t m = (n1 * n2);
        x = FLOW_CHECKED_MOD((x), (m));
        if (x < 0) {
            x = (x + m);
        }
        return x;
    }
    if (FLOW_CHECKED_MOD((a1), (g)) != FLOW_CHECKED_MOD((a2), (g))) {
        return 0;
    }
    int64_t M = FLOW_CHECKED_DIV(((n1 * n2)), (g));
    __int128 t = FLOW_CHECKED_DIV(((((((__int128)(a1)) * ((__int128)(v))) * ((__int128)(n2))) + ((((__int128)(a2)) * ((__int128)(u))) * ((__int128)(n1))))), (((__int128)(g))));
    int64_t x = ((int64_t)(FLOW_CHECKED_MOD((t), (((__int128)(M))))));
    if (x < 0) {
        x = (x + M);
    }
    return x;
}

int32_t main(void) {
    int64_t start = 1000000;
    int64_t limit = 1005000;
    int32_t* phi = (int32_t*)(calloc((limit + 1), 4));
    int64_t* tmp = (int64_t*)(calloc(4, 8));
    if ((phi == NULL || tmp == NULL)) {
        return 1;
    }
    int64_t i = 0;
    while (i <= limit) {
        phi[i] = ((int32_t)(i));
        i = (i + 1);
    }
    int64_t p = 2;
    while (p <= limit) {
        if (((int64_t)(phi[p])) == p) {
            phi[p] = ((int32_t)((p - 1)));
            int64_t j = (2 * p);
            while (j <= limit) {
                phi[j] = ((int32_t)((((int64_t)(phi[j])) - FLOW_CHECKED_DIV((((int64_t)(phi[j]))), (p)))));
                j = (j + p);
            }
        }
        p = (p + 1);
    }
    int64_t total = 0;
    int64_t n = start;
    while (n < limit) {
        int64_t m = (n + 1);
        while (m < limit) {
            total = (total + gen_crt_i64_i64_i64_i64_ptr_i64(((int64_t)(phi[n])), ((int64_t)(phi[m])), n, m, tmp));
            m = (m + 1);
        }
        n = (n + 1);
    }
    printf("%lld\n", total);
    free(phi);
    free(tmp);
    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 @egcd(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: !llvm.ptr) -> 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
    %4 = arith.constant 1 : i32
    %5 = arith.extsi %4 : i32 to i64
    %6 = llvm.mlir.constant(1 : i64) : i64
    %7 = llvm.alloca %6 x i64 : (i64) -> !llvm.ptr
    llvm.store %5, %7 : i64, !llvm.ptr
    %8 = arith.constant 0 : i32
    %9 = arith.extsi %8 : i32 to i64
    %10 = llvm.mlir.constant(1 : i64) : i64
    %11 = llvm.alloca %10 x i64 : (i64) -> !llvm.ptr
    llvm.store %9, %11 : i64, !llvm.ptr
    cf.br ^bb0
    ^bb0:
    %12 = llvm.load %3 : !llvm.ptr -> i64
    %13 = arith.constant 0 : i32
    %15 = arith.extsi %13 : i32 to i64
    %14 = arith.cmpi ne, %12, %15 : i64
    cf.cond_br %14, ^bb1, ^bb2
    ^bb1:
      %16 = llvm.load %1 : !llvm.ptr -> i64
      %17 = llvm.load %3 : !llvm.ptr -> i64
      %18 = arith.divsi %16, %17 : i64
      %19 = llvm.load %1 : !llvm.ptr -> i64
      %20 = llvm.load %3 : !llvm.ptr -> i64
      %21 = arith.muli %18, %20 : i64
      %22 = arith.subi %19, %21 : i64
      %23 = llvm.load %3 : !llvm.ptr -> i64
      llvm.store %23, %1 : i64, !llvm.ptr
      llvm.store %22, %3 : i64, !llvm.ptr
      %24 = llvm.load %7 : !llvm.ptr -> i64
      %25 = llvm.load %11 : !llvm.ptr -> i64
      %26 = arith.muli %18, %25 : i64
      %27 = arith.subi %24, %26 : i64
      %28 = llvm.load %11 : !llvm.ptr -> i64
      llvm.store %28, %7 : i64, !llvm.ptr
      llvm.store %27, %11 : i64, !llvm.ptr
      cf.br ^bb0
    ^bb2:
    %29 = arith.constant 0 : i32
    %30 = arith.extsi %29 : i32 to i64
    %31 = llvm.mlir.constant(1 : i64) : i64
    %32 = llvm.alloca %31 x i64 : (i64) -> !llvm.ptr
    llvm.store %30, %32 : i64, !llvm.ptr
    %33 = arith.constant 0 : i32
    %35 = arith.extsi %33 : i32 to i64
    %34 = arith.cmpi ne, %arg1, %35 : i64
    cf.cond_br %34, ^bb3, ^bb4
    ^bb3:
      %36 = llvm.load %1 : !llvm.ptr -> i64
      %37 = llvm.load %7 : !llvm.ptr -> i64
      %38 = arith.muli %37, %arg0 : i64
      %39 = arith.subi %36, %38 : i64
      %40 = arith.divsi %39, %arg1 : i64
      llvm.store %40, %32 : i64, !llvm.ptr
      cf.br ^bb5
    ^bb4:
      cf.br ^bb5
    ^bb5:
    %41 = llvm.load %7 : !llvm.ptr -> i64
    %42 = arith.constant 0 : i32
    %43 = arith.extsi %42 : i32 to i64
    %44 = llvm.getelementptr %arg2[%43] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %41, %44 : i64, !llvm.ptr
    %45 = llvm.load %32 : !llvm.ptr -> i64
    %46 = arith.constant 0 : i32
    %47 = arith.extsi %46 : i32 to i64
    %48 = llvm.getelementptr %arg3[%47] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %45, %48 : i64, !llvm.ptr
    %49 = llvm.load %1 : !llvm.ptr -> i64
    func.return %49 : i64
  }
  func.func @gen_crt(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64, %arg4: !llvm.ptr) -> i64 {
    # String concatenation: !llvm.ptr + i32
    %50 = func.call @egcd(%arg2, %arg3, %arg4, %51) : (i64, i64, !llvm.ptr, !llvm.ptr) -> i64
    %53 = arith.constant 0 : i32
    %54 = arith.extsi %53 : i32 to i64
    %55 = llvm.getelementptr %arg4[%54] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %52 = llvm.load %55 : !llvm.ptr -> i64
    %57 = arith.constant 1 : i32
    %58 = arith.extsi %57 : i32 to i64
    %59 = llvm.getelementptr %arg4[%58] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %56 = llvm.load %59 : !llvm.ptr -> i64
    %60 = arith.constant 1 : i32
    %62 = arith.extsi %60 : i32 to i64
    %61 = arith.cmpi eq, %50, %62 : i64
    cf.cond_br %61, ^bb6, ^bb7
    ^bb6:
      %63 = arith.muli %arg0, %56 : i64
      %64 = arith.muli %63, %arg3 : i64
      %65 = arith.muli %arg1, %52 : i64
      %66 = arith.muli %65, %arg2 : i64
      %67 = arith.addi %64, %66 : i64
      %68 = llvm.mlir.constant(1 : i64) : i64
      %69 = llvm.alloca %68 x i64 : (i64) -> !llvm.ptr
      llvm.store %67, %69 : i64, !llvm.ptr
      %70 = arith.muli %arg2, %arg3 : i64
      %71 = llvm.load %69 : !llvm.ptr -> i64
      %72 = arith.remsi %71, %70 : i64
      llvm.store %72, %69 : i64, !llvm.ptr
      %73 = llvm.load %69 : !llvm.ptr -> i64
      %74 = arith.constant 0 : i32
      %76 = arith.extsi %74 : i32 to i64
      %75 = arith.cmpi slt, %73, %76 : i64
      cf.cond_br %75, ^bb9, ^bb10
      ^bb9:
        %77 = llvm.load %69 : !llvm.ptr -> i64
        %78 = arith.addi %77, %70 : i64
        llvm.store %78, %69 : i64, !llvm.ptr
        cf.br ^bb11
      ^bb10:
        cf.br ^bb11
      ^bb11:
      %79 = llvm.load %69 : !llvm.ptr -> i64
      func.return %79 : i64
    ^bb7:
      cf.br ^bb8
    ^bb8:
    %80 = arith.remsi %arg0, %50 : i64
    %81 = arith.remsi %arg1, %50 : i64
    %82 = arith.cmpi ne, %80, %81 : i64
    cf.cond_br %82, ^bb12, ^bb13
    ^bb12:
      %83 = arith.constant 0 : i32
      %84 = arith.extsi %83 : i32 to i64
      func.return %84 : i64
    ^bb13:
      cf.br ^bb14
    ^bb14:
    %85 = arith.muli %arg2, %arg3 : i64
    %86 = arith.divsi %85, %50 : i64
    %87 = arith.extsi %arg0 : i64 to i128
    %88 = arith.extsi %56 : i64 to i128
    %90 = arith.trunci %87 : i128 to i64
    %91 = arith.trunci %88 : i128 to i64
    %89 = arith.muli %90, %91 : i64
    %92 = arith.extsi %arg3 : i64 to i128
    %94 = arith.trunci %92 : i128 to i64
    %93 = arith.muli %89, %94 : i64
    %95 = arith.extsi %arg1 : i64 to i128
    %96 = arith.extsi %52 : i64 to i128
    %98 = arith.trunci %95 : i128 to i64
    %99 = arith.trunci %96 : i128 to i64
    %97 = arith.muli %98, %99 : i64
    %100 = arith.extsi %arg2 : i64 to i128
    %102 = arith.trunci %100 : i128 to i64
    %101 = arith.muli %97, %102 : i64
    %103 = arith.addi %93, %101 : i64
    %104 = arith.extsi %50 : i64 to i128
    %106 = arith.trunci %104 : i128 to i64
    %105 = arith.divsi %103, %106 : i64
    %107 = arith.extsi %105 : i64 to i128
    %108 = arith.extsi %86 : i64 to i128
    %110 = arith.trunci %107 : i128 to i64
    %111 = arith.trunci %108 : i128 to i64
    %109 = arith.remsi %110, %111 : i64
    %112 = llvm.mlir.constant(1 : i64) : i64
    %113 = llvm.alloca %112 x i64 : (i64) -> !llvm.ptr
    llvm.store %109, %113 : i64, !llvm.ptr
    %114 = llvm.load %113 : !llvm.ptr -> i64
    %115 = arith.constant 0 : i32
    %117 = arith.extsi %115 : i32 to i64
    %116 = arith.cmpi slt, %114, %117 : i64
    cf.cond_br %116, ^bb15, ^bb16
    ^bb15:
      %118 = llvm.load %113 : !llvm.ptr -> i64
      %119 = arith.addi %118, %86 : i64
      llvm.store %119, %113 : i64, !llvm.ptr
      cf.br ^bb17
    ^bb16:
      cf.br ^bb17
    ^bb17:
    %120 = llvm.load %113 : !llvm.ptr -> i64
    func.return %120 : i64
  }
  func.func @main() -> i32 {
    %121 = arith.constant 1000000 : i32
    %122 = arith.extsi %121 : i32 to i64
    %123 = arith.constant 1005000 : i32
    %124 = arith.extsi %123 : i32 to i64
    %126 = arith.constant 1 : i32
    %128 = arith.extsi %126 : i32 to i64
    %127 = arith.addi %124, %128 : i64
    %129 = arith.constant 4 : i32
    %130 = arith.extsi %129 : i32 to i64
    %125 = func.call @calloc(%127, %130) : (i64, i64) -> !llvm.ptr
    %132 = arith.constant 4 : i32
    %133 = arith.constant 8 : i32
    %134 = arith.extsi %132 : i32 to i64
    %135 = arith.extsi %133 : i32 to i64
    %131 = func.call @calloc(%134, %135) : (i64, i64) -> !llvm.ptr
    %136 = llvm.mlir.zero : !llvm.ptr
    %137 = llvm.icmp "eq" %125, %136 : !llvm.ptr
    %138 = scf.if %137 -> (i1) {
      %139 = arith.constant true
      scf.yield %139 : i1
    } else {
      %140 = llvm.mlir.zero : !llvm.ptr
      %141 = llvm.icmp "eq" %131, %140 : !llvm.ptr
      scf.yield %141 : i1
    }
    cf.cond_br %138, ^bb18, ^bb19
    ^bb18:
      %142 = arith.constant 1 : i32
      func.return %142 : i32
    ^bb19:
      cf.br ^bb20
    ^bb20:
    %143 = arith.constant 0 : i32
    %144 = arith.extsi %143 : i32 to i64
    %145 = llvm.mlir.constant(1 : i64) : i64
    %146 = llvm.alloca %145 x i64 : (i64) -> !llvm.ptr
    llvm.store %144, %146 : i64, !llvm.ptr
    cf.br ^bb21
    ^bb21:
    %147 = llvm.load %146 : !llvm.ptr -> i64
    %148 = arith.cmpi sle, %147, %124 : i64
    cf.cond_br %148, ^bb22, ^bb23
    ^bb22:
      %149 = llvm.load %146 : !llvm.ptr -> i64
      %150 = arith.trunci %149 : i64 to i32
      %151 = llvm.load %146 : !llvm.ptr -> i64
      %152 = llvm.getelementptr %125[%151] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      llvm.store %150, %152 : i32, !llvm.ptr
      %153 = llvm.load %146 : !llvm.ptr -> i64
      %154 = arith.constant 1 : i32
      %156 = arith.extsi %154 : i32 to i64
      %155 = arith.addi %153, %156 : i64
      llvm.store %155, %146 : i64, !llvm.ptr
      cf.br ^bb21
    ^bb23:
    %157 = arith.constant 2 : i32
    %158 = arith.extsi %157 : i32 to i64
    %159 = llvm.mlir.constant(1 : i64) : i64
    %160 = llvm.alloca %159 x i64 : (i64) -> !llvm.ptr
    llvm.store %158, %160 : i64, !llvm.ptr
    cf.br ^bb24
    ^bb24:
    %161 = llvm.load %160 : !llvm.ptr -> i64
    %162 = arith.cmpi sle, %161, %124 : i64
    cf.cond_br %162, ^bb25, ^bb26
    ^bb25:
      %164 = llvm.load %160 : !llvm.ptr -> i64
      %165 = llvm.getelementptr %125[%164] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %163 = llvm.load %165 : !llvm.ptr -> i32
      %166 = arith.extsi %163 : i32 to i64
      %167 = llvm.load %160 : !llvm.ptr -> i64
      %168 = arith.cmpi eq, %166, %167 : i64
      cf.cond_br %168, ^bb27, ^bb28
      ^bb27:
        %169 = llvm.load %160 : !llvm.ptr -> i64
        %170 = arith.constant 1 : i32
        %172 = arith.extsi %170 : i32 to i64
        %171 = arith.subi %169, %172 : i64
        %173 = arith.trunci %171 : i64 to i32
        %174 = llvm.load %160 : !llvm.ptr -> i64
        %175 = llvm.getelementptr %125[%174] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        llvm.store %173, %175 : i32, !llvm.ptr
        %176 = arith.constant 2 : i32
        %177 = llvm.load %160 : !llvm.ptr -> i64
        %179 = arith.extsi %176 : i32 to i64
        %178 = arith.muli %179, %177 : i64
        %180 = llvm.mlir.constant(1 : i64) : i64
        %181 = llvm.alloca %180 x i64 : (i64) -> !llvm.ptr
        llvm.store %178, %181 : i64, !llvm.ptr
        cf.br ^bb30
        ^bb30:
        %182 = llvm.load %181 : !llvm.ptr -> i64
        %183 = arith.cmpi sle, %182, %124 : i64
        cf.cond_br %183, ^bb31, ^bb32
        ^bb31:
          %185 = llvm.load %181 : !llvm.ptr -> i64
          %186 = llvm.getelementptr %125[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i32
          %184 = llvm.load %186 : !llvm.ptr -> i32
          %187 = arith.extsi %184 : i32 to i64
          %189 = llvm.load %181 : !llvm.ptr -> i64
          %190 = llvm.getelementptr %125[%189] : (!llvm.ptr, i64) -> !llvm.ptr, i32
          %188 = llvm.load %190 : !llvm.ptr -> i32
          %191 = arith.extsi %188 : i32 to i64
          %192 = llvm.load %160 : !llvm.ptr -> i64
          %193 = arith.divsi %191, %192 : i64
          %194 = arith.subi %187, %193 : i64
          %195 = arith.trunci %194 : i64 to i32
          %196 = llvm.load %181 : !llvm.ptr -> i64
          %197 = llvm.getelementptr %125[%196] : (!llvm.ptr, i64) -> !llvm.ptr, i32
          llvm.store %195, %197 : i32, !llvm.ptr
          %198 = llvm.load %181 : !llvm.ptr -> i64
          %199 = llvm.load %160 : !llvm.ptr -> i64
          %200 = arith.addi %198, %199 : i64
          llvm.store %200, %181 : i64, !llvm.ptr
          cf.br ^bb30
        ^bb32:
        cf.br ^bb29
      ^bb28:
        cf.br ^bb29
      ^bb29:
      %201 = llvm.load %160 : !llvm.ptr -> i64
      %202 = arith.constant 1 : i32
      %204 = arith.extsi %202 : i32 to i64
      %203 = arith.addi %201, %204 : i64
      llvm.store %203, %160 : i64, !llvm.ptr
      cf.br ^bb24
    ^bb26:
    %205 = arith.constant 0 : i32
    %206 = arith.extsi %205 : i32 to i64
    %207 = llvm.mlir.constant(1 : i64) : i64
    %208 = llvm.alloca %207 x i64 : (i64) -> !llvm.ptr
    llvm.store %206, %208 : i64, !llvm.ptr
    %209 = llvm.mlir.constant(1 : i64) : i64
    %210 = llvm.alloca %209 x i64 : (i64) -> !llvm.ptr
    llvm.store %122, %210 : i64, !llvm.ptr
    cf.br ^bb33
    ^bb33:
    %211 = llvm.load %210 : !llvm.ptr -> i64
    %212 = arith.cmpi slt, %211, %124 : i64
    cf.cond_br %212, ^bb34, ^bb35
    ^bb34:
      %213 = llvm.load %210 : !llvm.ptr -> i64
      %214 = arith.constant 1 : i32
      %216 = arith.extsi %214 : i32 to i64
      %215 = arith.addi %213, %216 : i64
      %217 = llvm.mlir.constant(1 : i64) : i64
      %218 = llvm.alloca %217 x i64 : (i64) -> !llvm.ptr
      llvm.store %215, %218 : i64, !llvm.ptr
      cf.br ^bb36
      ^bb36:
      %219 = llvm.load %218 : !llvm.ptr -> i64
      %220 = arith.cmpi slt, %219, %124 : i64
      cf.cond_br %220, ^bb37, ^bb38
      ^bb37:
        %221 = llvm.load %208 : !llvm.ptr -> i64
        %224 = llvm.load %210 : !llvm.ptr -> i64
        %225 = llvm.getelementptr %125[%224] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %223 = llvm.load %225 : !llvm.ptr -> i32
        %226 = arith.extsi %223 : i32 to i64
        %228 = llvm.load %218 : !llvm.ptr -> i64
        %229 = llvm.getelementptr %125[%228] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %227 = llvm.load %229 : !llvm.ptr -> i32
        %230 = arith.extsi %227 : i32 to i64
        %231 = llvm.load %210 : !llvm.ptr -> i64
        %232 = llvm.load %218 : !llvm.ptr -> i64
        %222 = func.call @gen_crt(%226, %230, %231, %232, %131) : (i64, i64, i64, i64, !llvm.ptr) -> i64
        %233 = arith.addi %221, %222 : i64
        llvm.store %233, %208 : i64, !llvm.ptr
        %234 = llvm.load %218 : !llvm.ptr -> i64
        %235 = arith.constant 1 : i32
        %237 = arith.extsi %235 : i32 to i64
        %236 = arith.addi %234, %237 : i64
        llvm.store %236, %218 : i64, !llvm.ptr
        cf.br ^bb36
      ^bb38:
      %238 = llvm.load %210 : !llvm.ptr -> i64
      %239 = arith.constant 1 : i32
      %241 = arith.extsi %239 : i32 to i64
      %240 = arith.addi %238, %241 : i64
      llvm.store %240, %210 : i64, !llvm.ptr
      cf.br ^bb33
    ^bb35:
    %242 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %243 = llvm.load %208 : !llvm.ptr -> i64
    %244 = llvm.call @printf(%242, %243) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    func.call @free(%125) : (!llvm.ptr) -> ()
    func.call @free(%131) : (!llvm.ptr) -> ()
    %247 = arith.constant 0 : i32
    func.return %247 : i32
  }
}