Problem 755

Not Zeckendorf — S(10^13). Ported from native C to pure Flow. Uses i128 for counts and a hash table.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 755
# Not Zeckendorf — S(10^13).
# Ported from native C to pure Flow. Uses i128 for counts and a hash table.

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

struct Ent {
    k: i64
    cap: i64
    val_lo: i64
    val_hi: i64
    used: i32
}

const HSIZE: i64 = 1 << 22

let mut H: ptr<Ent> = null
let mut F: ptr<i64> = null

# sum_all(k) = F[k+2] - 2
function sum_all(k: i64) -> i64 {
    if k <= 0 {
        return 0
    }
    return F[k + 2] - 2
}

# i128 count stored as (hi, lo) pair. We split i128 into two i64s.
# count returns i128 as a pair via out parameters.
# Instead, we return i128 directly.

function count(k: i64, cap: i64) -> i128 {
    if cap < 0 {
        return 0
    }
    if k == 0 {
        return 1
    }
    let h: i64 = (k * 11400714819323198485) ^ cap
    let mask: i64 = HSIZE - 1
    for probe in 0..64 {
        let e: ptr<Ent> = &H[(h + probe) & mask]
        if e[0].used == 1 && e[0].k == k && e[0].cap == cap {
            return ((e[0].val_hi as i128) << 64) | (e[0].val_lo as i128)
        }
        if e[0].used == 0 {
            let mut res: i128 = 0
            if cap >= sum_all(k) {
                res = (1 as i128) << k
            } else {
                if cap < F[k] {
                    res = count(k - 1, cap)
                } else {
                    res = count(k - 1, cap) + count(k - 1, cap - F[k])
                }
            }
            e[0].used = 1
            e[0].k = k
            e[0].cap = cap
            e[0].val_lo = (res & 0xFFFFFFFFFFFFFFFF) as i64
            e[0].val_hi = (res >> 64) as i64
            return res
        }
    }
    # Fallback without cache.
    if cap >= sum_all(k) {
        return (1 as i128) << k
    }
    if cap < F[k] {
        return count(k - 1, cap)
    }
    return count(k - 1, cap) + count(k - 1, cap - F[k])
}

function main() -> i32 {
    let n: i64 = 10000000000000
    F = calloc(200, 8) as ptr<i64>
    F[1] = 1
    F[2] = 2
    let mut len: i64 = 2
    while F[len] <= n {
        len = len + 1
        F[len] = F[len - 1] + F[len - 2]
    }
    let k: i64 = len - 1
    while len <= k + 2 {
        len = len + 1
        F[len] = F[len - 1] + F[len - 2]
    }
    H = calloc(HSIZE, 40) as ptr<Ent>
    let ans: i128 = count(k, n)
    free(H as ptr<void>)
    free(F as ptr<void>)
    printf("%lld\n", ans as i64)
    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; }

typedef struct Ent Ent;

struct Ent {
    int64_t k;
    int64_t cap;
    int64_t val_lo;
    int64_t val_hi;
    int32_t used;
};

int64_t sum_all_i64(int64_t k);
__int128 count_i64_i64(int64_t k, int64_t cap);
int32_t main(void);

static const int64_t HSIZE = FLOW_CHECKED_SHL((1), (22));

/* Module statics */
static Ent* H = NULL;
static int64_t* F = NULL;



int64_t sum_all_i64(int64_t k) {
    if (k <= 0) {
        return 0;
    }
    return (F[(k + 2)] - 2);
}

__int128 count_i64_i64(int64_t k, int64_t cap) {
    if (cap < 0) {
        return 0;
    }
    if (k == 0) {
        return 1;
    }
    int64_t h = ((k * ((__int128)0x9E3779B97F4A7C15ULL)) ^ cap);
    int64_t mask = (HSIZE - 1);
    int32_t __flow_step_1 = 1;
    for (int32_t probe = 0; (0 <= 64) ? probe < 64 : probe > 64; probe += (0 <= 64) ? 1 : -1) {
        Ent* e = (Ent*)((&(H[((h + probe) & mask)])));
        if (((e[0].used == 1 && e[0].k == k) && e[0].cap == cap)) {
            return (FLOW_CHECKED_SHL((((__int128)(e[0].val_hi))), (64)) | ((__int128)(e[0].val_lo)));
        }
        if (e[0].used == 0) {
            __int128 res = 0;
            if (cap >= sum_all_i64(k)) {
                res = FLOW_CHECKED_SHL((((__int128)(1))), (k));
            } else {
                if (cap < F[k]) {
                    res = count_i64_i64((k - 1), cap);
                } else {
                    res = (count_i64_i64((k - 1), cap) + count_i64_i64((k - 1), (cap - F[k])));
                }
            }
            e[0].used = 1;
            e[0].k = k;
            e[0].cap = cap;
            e[0].val_lo = ((int64_t)((res & ((__int128)0xFFFFFFFFFFFFFFFFULL))));
            e[0].val_hi = ((int64_t)(FLOW_CHECKED_SHR((res), (64))));
            return res;
        }
    }
    if (cap >= sum_all_i64(k)) {
        return FLOW_CHECKED_SHL((((__int128)(1))), (k));
    }
    if (cap < F[k]) {
        return count_i64_i64((k - 1), cap);
    }
    return (count_i64_i64((k - 1), cap) + count_i64_i64((k - 1), (cap - F[k])));
}

int32_t main(void) {
    int64_t n = 10000000000000;
    F = ((int64_t*)(calloc(200, 8)));
    F[1] = 1;
    F[2] = 2;
    int64_t len = 2;
    while (F[len] <= n) {
        len = (len + 1);
        F[len] = (F[(len - 1)] + F[(len - 2)]);
    }
    int64_t k = (len - 1);
    while (len <= (k + 2)) {
        len = (len + 1);
        F[len] = (F[(len - 1)] + F[(len - 2)]);
    }
    H = ((Ent*)(calloc(HSIZE, 40)));
    __int128 ans = count_i64_i64(k, n);
    free(((void*)(H)));
    free(((void*)(F)));
    printf("%lld\n", ((int64_t)(ans)));
    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) -> ()
  // Struct: Ent
  // Fields:
  //   k: i64
  //   cap: i64
  //   val_lo: i64
  //   val_hi: i64
  //   used: i32
  // Constant: HSIZE
  llvm.mlir.global internal constant @HSIZE(4194304 : i64) : i64
  // Module static: H
  llvm.mlir.global internal @H() {addr_space = 0 : i32} : !llvm.ptr {
    %0 = llvm.mlir.zero : !llvm.ptr
    llvm.return %0 : !llvm.ptr
  }
  // Module static: F
  llvm.mlir.global internal @F() {addr_space = 0 : i32} : !llvm.ptr {
    %1 = llvm.mlir.zero : !llvm.ptr
    llvm.return %1 : !llvm.ptr
  }
  func.func @sum_all(%arg0: i64) -> i64 {
    %2 = arith.constant 0 : i32
    %4 = arith.extsi %2 : i32 to i64
    %3 = arith.cmpi sle, %arg0, %4 : i64
    cf.cond_br %3, ^bb0, ^bb1
    ^bb0:
      %5 = arith.constant 0 : i32
      %6 = arith.extsi %5 : i32 to i64
      func.return %6 : i64
    ^bb1:
      cf.br ^bb2
    ^bb2:
    %8 = llvm.mlir.addressof @F : !llvm.ptr
    %9 = llvm.load %8 : !llvm.ptr -> !llvm.ptr
    %10 = arith.constant 2 : i32
    %12 = arith.extsi %10 : i32 to i64
    %11 = arith.addi %arg0, %12 : i64
    %13 = llvm.getelementptr %9[%11] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %7 = llvm.load %13 : !llvm.ptr -> i64
    %14 = arith.constant 2 : i32
    %16 = arith.extsi %14 : i32 to i64
    %15 = arith.subi %7, %16 : i64
    func.return %15 : i64
  }
  func.func @count(%arg0: i64, %arg1: i64) -> i128 {
    %17 = arith.constant 0 : i32
    %19 = arith.extsi %17 : i32 to i64
    %18 = arith.cmpi slt, %arg1, %19 : i64
    cf.cond_br %18, ^bb3, ^bb4
    ^bb3:
      %20 = arith.constant 0 : i32
      %21 = arith.extsi %20 : i32 to i128
      func.return %21 : i128
    ^bb4:
      cf.br ^bb5
    ^bb5:
    %22 = arith.constant 0 : i32
    %24 = arith.extsi %22 : i32 to i64
    %23 = arith.cmpi eq, %arg0, %24 : i64
    cf.cond_br %23, ^bb6, ^bb7
    ^bb6:
      %25 = arith.constant 1 : i32
      %26 = arith.extsi %25 : i32 to i128
      func.return %26 : i128
    ^bb7:
      cf.br ^bb8
    ^bb8:
    %27 = arith.constant 11400714815028231189 : i32
    %29 = arith.extsi %27 : i32 to i64
    %28 = arith.muli %arg0, %29 : i64
    %30 = arith.xori %28, %arg1 : i64
    %31 = llvm.mlir.addressof @HSIZE : !llvm.ptr
    %32 = llvm.load %31 : !llvm.ptr -> i64
    %33 = arith.constant 1 : i32
    %35 = arith.extsi %33 : i32 to i64
    %34 = arith.subi %32, %35 : i64
    %36 = arith.constant 0 : i32
    %37 = arith.constant 64 : i32
    %38 = arith.index_cast %36 : i32 to index
    %39 = arith.index_cast %37 : i32 to index
    %41 = arith.constant 1 : index
    %42 = arith.constant -1 : index
    %43 = arith.cmpi sle, %38, %39 : index
    %40 = arith.select %43, %41, %42 : index
    cf.br ^bb9(%38 : index)
    ^bb9(%44: index):
    %45 = arith.cmpi slt, %44, %39 : index
    %46 = arith.cmpi sgt, %44, %39 : index
    %47 = arith.select %43, %45, %46 : i1
    cf.cond_br %47, ^bb10(%44 : index), ^bb11(%44 : index)
    ^bb10(%48: index):
      %54 = llvm.mlir.addressof @H : !llvm.ptr
      %55 = llvm.load %54 : !llvm.ptr -> !llvm.ptr
      %50 = arith.trunci %30 : i64 to i32
      %51 = arith.index_cast %48 : index to i32
      %49 = arith.addi %50, %51 : i32
      %53 = arith.extsi %49 : i32 to i64
      %52 = arith.andi %53, %34 : i64
      %56 = llvm.getelementptr %55[%52] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
      %58 = arith.constant 0 : i32
      %59 = arith.extsi %58 : i32 to i64
      %60 = llvm.getelementptr %56[%59] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
      %57 = llvm.load %60 : !llvm.ptr -> !llvm.struct<(i64, i64, i64, i64, i32)>
      %61 = arith.constant 0 : i32
      %62 = arith.extsi %61 : i32 to i64
      %63 = llvm.getelementptr %56[%62] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
      %64 = llvm.getelementptr %63[0, 4] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
      %65 = llvm.load %64 : !llvm.ptr -> i32
      %66 = arith.constant 1 : i32
      %67 = arith.cmpi eq, %65, %66 : i32
      %68 = scf.if %67 -> (i1) {
        %70 = arith.constant 0 : i32
        %71 = arith.extsi %70 : i32 to i64
        %72 = llvm.getelementptr %56[%71] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %69 = llvm.load %72 : !llvm.ptr -> !llvm.struct<(i64, i64, i64, i64, i32)>
        %73 = arith.constant 0 : i32
        %74 = arith.extsi %73 : i32 to i64
        %75 = llvm.getelementptr %56[%74] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %76 = llvm.getelementptr %75[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %77 = llvm.load %76 : !llvm.ptr -> i64
        %78 = arith.cmpi eq, %77, %arg0 : i64
        scf.yield %78 : i1
      } else {
        %79 = arith.constant false
        scf.yield %79 : i1
      }
      %80 = scf.if %68 -> (i1) {
        %82 = arith.constant 0 : i32
        %83 = arith.extsi %82 : i32 to i64
        %84 = llvm.getelementptr %56[%83] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %81 = llvm.load %84 : !llvm.ptr -> !llvm.struct<(i64, i64, i64, i64, i32)>
        %85 = arith.constant 0 : i32
        %86 = arith.extsi %85 : i32 to i64
        %87 = llvm.getelementptr %56[%86] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %88 = llvm.getelementptr %87[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %89 = llvm.load %88 : !llvm.ptr -> i64
        %90 = arith.cmpi eq, %89, %arg1 : i64
        scf.yield %90 : i1
      } else {
        %91 = arith.constant false
        scf.yield %91 : i1
      }
      cf.cond_br %80, ^bb12, ^bb13
      ^bb12:
        %93 = arith.constant 0 : i32
        %94 = arith.extsi %93 : i32 to i64
        %95 = llvm.getelementptr %56[%94] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %92 = llvm.load %95 : !llvm.ptr -> !llvm.struct<(i64, i64, i64, i64, i32)>
        %96 = arith.constant 0 : i32
        %97 = arith.extsi %96 : i32 to i64
        %98 = llvm.getelementptr %56[%97] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %99 = llvm.getelementptr %98[0, 3] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %100 = llvm.load %99 : !llvm.ptr -> i64
        %101 = arith.extsi %100 : i64 to i128
        %102 = arith.constant 64 : i32
        %104 = arith.trunci %101 : i128 to i64
        %105 = arith.extsi %102 : i32 to i64
        %103 = arith.shli %104, %105 : i64
        %107 = arith.constant 0 : i32
        %108 = arith.extsi %107 : i32 to i64
        %109 = llvm.getelementptr %56[%108] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %106 = llvm.load %109 : !llvm.ptr -> !llvm.struct<(i64, i64, i64, i64, i32)>
        %110 = arith.constant 0 : i32
        %111 = arith.extsi %110 : i32 to i64
        %112 = llvm.getelementptr %56[%111] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %113 = llvm.getelementptr %112[0, 2] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %114 = llvm.load %113 : !llvm.ptr -> i64
        %115 = arith.extsi %114 : i64 to i128
        %117 = arith.trunci %115 : i128 to i64
        %116 = arith.ori %103, %117 : i64
        %118 = arith.extsi %116 : i64 to i128
        func.return %118 : i128
      ^bb13:
        cf.br ^bb14
      ^bb14:
      %120 = arith.constant 0 : i32
      %121 = arith.extsi %120 : i32 to i64
      %122 = llvm.getelementptr %56[%121] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
      %119 = llvm.load %122 : !llvm.ptr -> !llvm.struct<(i64, i64, i64, i64, i32)>
      %123 = arith.constant 0 : i32
      %124 = arith.extsi %123 : i32 to i64
      %125 = llvm.getelementptr %56[%124] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
      %126 = llvm.getelementptr %125[0, 4] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
      %127 = llvm.load %126 : !llvm.ptr -> i32
      %128 = arith.constant 0 : i32
      %129 = arith.cmpi eq, %127, %128 : i32
      cf.cond_br %129, ^bb15, ^bb16
      ^bb15:
        %130 = arith.constant 0 : i32
        %131 = arith.extsi %130 : i32 to i128
        %132 = llvm.mlir.constant(1 : i64) : i64
        %133 = llvm.alloca %132 x i128 : (i64) -> !llvm.ptr
        llvm.store %131, %133 : i128, !llvm.ptr
        %134 = func.call @sum_all(%arg0) : (i64) -> i64
        %135 = arith.cmpi sge, %arg1, %134 : i64
        cf.cond_br %135, ^bb18, ^bb19
        ^bb18:
          %136 = arith.constant 1 : i32
          %137 = arith.extsi %136 : i32 to i128
          %139 = arith.trunci %137 : i128 to i64
          %138 = arith.shli %139, %arg0 : i64
          %140 = arith.extsi %138 : i64 to i128
          llvm.store %140, %133 : i128, !llvm.ptr
          cf.br ^bb20
        ^bb19:
          %142 = llvm.mlir.addressof @F : !llvm.ptr
          %143 = llvm.load %142 : !llvm.ptr -> !llvm.ptr
          %144 = llvm.getelementptr %143[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %141 = llvm.load %144 : !llvm.ptr -> i64
          %145 = arith.cmpi slt, %arg1, %141 : i64
          cf.cond_br %145, ^bb21, ^bb22
          ^bb21:
            %147 = arith.constant 1 : i32
            %149 = arith.extsi %147 : i32 to i64
            %148 = arith.subi %arg0, %149 : i64
            %146 = func.call @count(%148, %arg1) : (i64, i64) -> i128
            llvm.store %146, %133 : i128, !llvm.ptr
            cf.br ^bb23
          ^bb22:
            %151 = arith.constant 1 : i32
            %153 = arith.extsi %151 : i32 to i64
            %152 = arith.subi %arg0, %153 : i64
            %150 = func.call @count(%152, %arg1) : (i64, i64) -> i128
            %155 = arith.constant 1 : i32
            %157 = arith.extsi %155 : i32 to i64
            %156 = arith.subi %arg0, %157 : i64
            %159 = llvm.mlir.addressof @F : !llvm.ptr
            %160 = llvm.load %159 : !llvm.ptr -> !llvm.ptr
            %161 = llvm.getelementptr %160[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
            %158 = llvm.load %161 : !llvm.ptr -> i64
            %162 = arith.subi %arg1, %158 : i64
            %154 = func.call @count(%156, %162) : (i64, i64) -> i128
            %164 = arith.trunci %150 : i128 to i64
            %165 = arith.trunci %154 : i128 to i64
            %163 = arith.addi %164, %165 : i64
            %166 = arith.extsi %163 : i64 to i128
            llvm.store %166, %133 : i128, !llvm.ptr
            cf.br ^bb23
          ^bb23:
          cf.br ^bb20
        ^bb20:
        %167 = arith.constant 1 : i32
        %168 = arith.constant 0 : i32
        %169 = arith.extsi %168 : i32 to i64
        %170 = llvm.getelementptr %56[%169] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %171 = llvm.getelementptr %170[0, 4] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        llvm.store %167, %171 : i32, !llvm.ptr
        %172 = arith.constant 0 : i32
        %173 = arith.extsi %172 : i32 to i64
        %174 = llvm.getelementptr %56[%173] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %175 = llvm.getelementptr %174[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        llvm.store %arg0, %175 : i64, !llvm.ptr
        %176 = arith.constant 0 : i32
        %177 = arith.extsi %176 : i32 to i64
        %178 = llvm.getelementptr %56[%177] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %179 = llvm.getelementptr %178[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        llvm.store %arg1, %179 : i64, !llvm.ptr
        %180 = llvm.load %133 : !llvm.ptr -> i128
        %181 = arith.constant 18446744069414584319 : i32
        %183 = arith.trunci %180 : i128 to i64
        %184 = arith.extsi %181 : i32 to i64
        %182 = arith.andi %183, %184 : i64
        %185 = arith.constant 0 : i32
        %186 = arith.extsi %185 : i32 to i64
        %187 = llvm.getelementptr %56[%186] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %188 = llvm.getelementptr %187[0, 2] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        llvm.store %182, %188 : i64, !llvm.ptr
        %189 = llvm.load %133 : !llvm.ptr -> i128
        %190 = arith.constant 64 : i32
        %192 = arith.trunci %189 : i128 to i64
        %193 = arith.extsi %190 : i32 to i64
        %191 = arith.shrsi %192, %193 : i64
        %194 = arith.constant 0 : i32
        %195 = arith.extsi %194 : i32 to i64
        %196 = llvm.getelementptr %56[%195] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        %197 = llvm.getelementptr %196[0, 3] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i64, i64, i64, i64, i32)>
        llvm.store %191, %197 : i64, !llvm.ptr
        %198 = llvm.load %133 : !llvm.ptr -> i128
        func.return %198 : i128
      ^bb16:
        cf.br ^bb17
      ^bb17:
      %199 = arith.addi %48, %40 : index
      cf.br ^bb9(%199 : index)
    ^bb11(%200: index):
    %201 = func.call @sum_all(%arg0) : (i64) -> i64
    %202 = arith.cmpi sge, %arg1, %201 : i64
    cf.cond_br %202, ^bb24, ^bb25
    ^bb24:
      %203 = arith.constant 1 : i32
      %204 = arith.extsi %203 : i32 to i128
      %206 = arith.trunci %204 : i128 to i64
      %205 = arith.shli %206, %arg0 : i64
      %207 = arith.extsi %205 : i64 to i128
      func.return %207 : i128
    ^bb25:
      cf.br ^bb26
    ^bb26:
    %209 = llvm.mlir.addressof @F : !llvm.ptr
    %210 = llvm.load %209 : !llvm.ptr -> !llvm.ptr
    %211 = llvm.getelementptr %210[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %208 = llvm.load %211 : !llvm.ptr -> i64
    %212 = arith.cmpi slt, %arg1, %208 : i64
    cf.cond_br %212, ^bb27, ^bb28
    ^bb27:
      %214 = arith.constant 1 : i32
      %216 = arith.extsi %214 : i32 to i64
      %215 = arith.subi %arg0, %216 : i64
      %213 = func.call @count(%215, %arg1) : (i64, i64) -> i128
      func.return %213 : i128
    ^bb28:
      cf.br ^bb29
    ^bb29:
    %218 = arith.constant 1 : i32
    %220 = arith.extsi %218 : i32 to i64
    %219 = arith.subi %arg0, %220 : i64
    %217 = func.call @count(%219, %arg1) : (i64, i64) -> i128
    %222 = arith.constant 1 : i32
    %224 = arith.extsi %222 : i32 to i64
    %223 = arith.subi %arg0, %224 : i64
    %226 = llvm.mlir.addressof @F : !llvm.ptr
    %227 = llvm.load %226 : !llvm.ptr -> !llvm.ptr
    %228 = llvm.getelementptr %227[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %225 = llvm.load %228 : !llvm.ptr -> i64
    %229 = arith.subi %arg1, %225 : i64
    %221 = func.call @count(%223, %229) : (i64, i64) -> i128
    %231 = arith.trunci %217 : i128 to i64
    %232 = arith.trunci %221 : i128 to i64
    %230 = arith.addi %231, %232 : i64
    %233 = arith.extsi %230 : i64 to i128
    func.return %233 : i128
  }
  func.func @main() -> i32 {
    %234 = arith.constant 9995705032704 : i32
    %235 = arith.extsi %234 : i32 to i64
    %237 = arith.constant 200 : i32
    %238 = arith.constant 8 : i32
    %239 = arith.extsi %237 : i32 to i64
    %240 = arith.extsi %238 : i32 to i64
    %236 = func.call @calloc(%239, %240) : (i64, i64) -> !llvm.ptr
    %241 = llvm.mlir.addressof @F : !llvm.ptr
    llvm.store %236, %241 : !llvm.ptr, !llvm.ptr
    %242 = arith.constant 1 : i32
    %243 = llvm.mlir.addressof @F : !llvm.ptr
    %244 = llvm.load %243 : !llvm.ptr -> !llvm.ptr
    %245 = arith.constant 1 : i32
    %246 = arith.extsi %242 : i32 to i64
    %247 = arith.extsi %245 : i32 to i64
    %248 = llvm.getelementptr %244[%247] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %246, %248 : i64, !llvm.ptr
    %249 = arith.constant 2 : i32
    %250 = llvm.mlir.addressof @F : !llvm.ptr
    %251 = llvm.load %250 : !llvm.ptr -> !llvm.ptr
    %252 = arith.constant 2 : i32
    %253 = arith.extsi %249 : i32 to i64
    %254 = arith.extsi %252 : i32 to i64
    %255 = llvm.getelementptr %251[%254] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %253, %255 : i64, !llvm.ptr
    %256 = arith.constant 2 : i32
    %257 = arith.extsi %256 : i32 to i64
    %258 = llvm.mlir.constant(1 : i64) : i64
    %259 = llvm.alloca %258 x i64 : (i64) -> !llvm.ptr
    llvm.store %257, %259 : i64, !llvm.ptr
    cf.br ^bb30
    ^bb30:
    %261 = llvm.mlir.addressof @F : !llvm.ptr
    %262 = llvm.load %261 : !llvm.ptr -> !llvm.ptr
    %263 = llvm.load %259 : !llvm.ptr -> i64
    %264 = llvm.getelementptr %262[%263] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %260 = llvm.load %264 : !llvm.ptr -> i64
    %265 = arith.cmpi sle, %260, %235 : i64
    cf.cond_br %265, ^bb31, ^bb32
    ^bb31:
      %266 = llvm.load %259 : !llvm.ptr -> i64
      %267 = arith.constant 1 : i32
      %269 = arith.extsi %267 : i32 to i64
      %268 = arith.addi %266, %269 : i64
      llvm.store %268, %259 : i64, !llvm.ptr
      %271 = llvm.mlir.addressof @F : !llvm.ptr
      %272 = llvm.load %271 : !llvm.ptr -> !llvm.ptr
      %273 = llvm.load %259 : !llvm.ptr -> i64
      %274 = arith.constant 1 : i32
      %276 = arith.extsi %274 : i32 to i64
      %275 = arith.subi %273, %276 : i64
      %277 = llvm.getelementptr %272[%275] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %270 = llvm.load %277 : !llvm.ptr -> i64
      %279 = llvm.mlir.addressof @F : !llvm.ptr
      %280 = llvm.load %279 : !llvm.ptr -> !llvm.ptr
      %281 = llvm.load %259 : !llvm.ptr -> i64
      %282 = arith.constant 2 : i32
      %284 = arith.extsi %282 : i32 to i64
      %283 = arith.subi %281, %284 : i64
      %285 = llvm.getelementptr %280[%283] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %278 = llvm.load %285 : !llvm.ptr -> i64
      %286 = arith.addi %270, %278 : i64
      %287 = llvm.mlir.addressof @F : !llvm.ptr
      %288 = llvm.load %287 : !llvm.ptr -> !llvm.ptr
      %289 = llvm.load %259 : !llvm.ptr -> i64
      %290 = llvm.getelementptr %288[%289] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %286, %290 : i64, !llvm.ptr
      cf.br ^bb30
    ^bb32:
    %291 = llvm.load %259 : !llvm.ptr -> i64
    %292 = arith.constant 1 : i32
    %294 = arith.extsi %292 : i32 to i64
    %293 = arith.subi %291, %294 : i64
    cf.br ^bb33
    ^bb33:
    %295 = llvm.load %259 : !llvm.ptr -> i64
    %296 = arith.constant 2 : i32
    %298 = arith.extsi %296 : i32 to i64
    %297 = arith.addi %293, %298 : i64
    %299 = arith.cmpi sle, %295, %297 : i64
    cf.cond_br %299, ^bb34, ^bb35
    ^bb34:
      %300 = llvm.load %259 : !llvm.ptr -> i64
      %301 = arith.constant 1 : i32
      %303 = arith.extsi %301 : i32 to i64
      %302 = arith.addi %300, %303 : i64
      llvm.store %302, %259 : i64, !llvm.ptr
      %305 = llvm.mlir.addressof @F : !llvm.ptr
      %306 = llvm.load %305 : !llvm.ptr -> !llvm.ptr
      %307 = llvm.load %259 : !llvm.ptr -> i64
      %308 = arith.constant 1 : i32
      %310 = arith.extsi %308 : i32 to i64
      %309 = arith.subi %307, %310 : i64
      %311 = llvm.getelementptr %306[%309] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %304 = llvm.load %311 : !llvm.ptr -> i64
      %313 = llvm.mlir.addressof @F : !llvm.ptr
      %314 = llvm.load %313 : !llvm.ptr -> !llvm.ptr
      %315 = llvm.load %259 : !llvm.ptr -> i64
      %316 = arith.constant 2 : i32
      %318 = arith.extsi %316 : i32 to i64
      %317 = arith.subi %315, %318 : i64
      %319 = llvm.getelementptr %314[%317] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %312 = llvm.load %319 : !llvm.ptr -> i64
      %320 = arith.addi %304, %312 : i64
      %321 = llvm.mlir.addressof @F : !llvm.ptr
      %322 = llvm.load %321 : !llvm.ptr -> !llvm.ptr
      %323 = llvm.load %259 : !llvm.ptr -> i64
      %324 = llvm.getelementptr %322[%323] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %320, %324 : i64, !llvm.ptr
      cf.br ^bb33
    ^bb35:
    %326 = llvm.mlir.addressof @HSIZE : !llvm.ptr
    %327 = llvm.load %326 : !llvm.ptr -> i64
    %328 = arith.constant 40 : i32
    %329 = arith.extsi %328 : i32 to i64
    %325 = func.call @calloc(%327, %329) : (i64, i64) -> !llvm.ptr
    %330 = llvm.mlir.addressof @H : !llvm.ptr
    llvm.store %325, %330 : !llvm.ptr, !llvm.ptr
    %331 = func.call @count(%293, %235) : (i64, i64) -> i128
    %333 = llvm.mlir.addressof @H : !llvm.ptr
    %334 = llvm.load %333 : !llvm.ptr -> !llvm.ptr
    func.call @free(%334) : (!llvm.ptr) -> ()
    %336 = llvm.mlir.addressof @F : !llvm.ptr
    %337 = llvm.load %336 : !llvm.ptr -> !llvm.ptr
    func.call @free(%337) : (!llvm.ptr) -> ()
    %338 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %339 = arith.trunci %331 : i128 to i64
    %340 = llvm.call @printf(%338, %339) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    %341 = arith.constant 0 : i32
    func.return %341 : i32
  }
}