; ModuleID = 'optimized.bc'
source_filename = "./build/test_compiler/performance/03_sort1.ll"

@a = global [30000010 x i32] zeroinitializer
@ans = local_unnamed_addr global i32 0

declare i32 @getarray(ptr) local_unnamed_addr

declare void @putint(i32) local_unnamed_addr

declare void @putch(i32) local_unnamed_addr

declare void @starttime() local_unnamed_addr

declare void @stoptime() local_unnamed_addr

declare ptr @sysy_alloc_i32(i32) local_unnamed_addr

declare void @sysy_free_i32(ptr) local_unnamed_addr

declare void @sysy_zero_i32(ptr, i32) local_unnamed_addr

; Function Attrs: nofree norecurse nosync nounwind memory(argmem: read)
define i32 @getMaxNum(i32 %n, ptr nocapture readonly %arr) local_unnamed_addr #0 {
entry:
  %t95 = icmp sgt i32 %n, 0
  br i1 %t95, label %while.body.t5, label %while.exit.t6

while.body.t5:                                    ; preds = %entry, %while.body.t5
  %t3_i.07 = phi i32 [ %t21, %while.body.t5 ], [ 0, %entry ]
  %t2_ret.06 = phi i32 [ %spec.select, %while.body.t5 ], [ 0, %entry ]
  %0 = zext nneg i32 %t3_i.07 to i64
  %t13 = getelementptr i32, ptr %arr, i64 %0
  %t14 = load i32, ptr %t13, align 4
  %spec.select = tail call i32 @llvm.smax.i32(i32 %t14, i32 %t2_ret.06)
  %t21 = add nuw nsw i32 %t3_i.07, 1
  %t9 = icmp slt i32 %t21, %n
  br i1 %t9, label %while.body.t5, label %while.exit.t6

while.exit.t6:                                    ; preds = %while.body.t5, %entry
  %t2_ret.0.lcssa = phi i32 [ 0, %entry ], [ %spec.select, %while.body.t5 ]
  ret i32 %t2_ret.0.lcssa
}

; Function Attrs: nofree norecurse nosync nounwind memory(none)
define i32 @getNumPos(i32 %num, i32 %pos) local_unnamed_addr #1 {
entry:
  %t333 = icmp sgt i32 %pos, 0
  br i1 %t333, label %while.body.t29, label %while.exit.t30

while.body.t29:                                   ; preds = %entry, %while.body.t29
  %t27_i.05 = phi i32 [ %t37, %while.body.t29 ], [ 0, %entry ]
  %t24.04 = phi i32 [ %t35, %while.body.t29 ], [ %num, %entry ]
  %t35 = sdiv i32 %t24.04, 16
  %t37 = add nuw nsw i32 %t27_i.05, 1
  %t33 = icmp slt i32 %t37, %pos
  br i1 %t33, label %while.body.t29, label %while.exit.t30

while.exit.t30:                                   ; preds = %while.body.t29, %entry
  %t24.0.lcssa = phi i32 [ %num, %entry ], [ %t35, %while.body.t29 ]
  %t39 = srem i32 %t24.0.lcssa, 16
  ret i32 %t39
}

define void @radixSort(i32 %bitround, ptr nocapture %a, i32 %l, i32 %r) local_unnamed_addr {
entry:
  %t43 = tail call ptr @sysy_alloc_i32(i32 16)
  tail call void @sysy_zero_i32(ptr %t43, i32 16)
  %t46 = tail call ptr @sysy_alloc_i32(i32 16)
  tail call void @sysy_zero_i32(ptr %t46, i32 16)
  %t48 = tail call ptr @sysy_alloc_i32(i32 16)
  tail call void @sysy_zero_i32(ptr %t48, i32 16)
  %t54 = icmp eq i32 %bitround, -1
  %t56 = add i32 %l, 1
  %t58 = icmp sge i32 %t56, %r
  %t59 = or i1 %t54, %t58
  br i1 %t59, label %cleanup.t44, label %while.cond.t62.preheader

while.cond.t62.preheader:                         ; preds = %entry
  %t6796 = icmp slt i32 %l, %r
  br i1 %t6796, label %while.body.t63.lr.ph, label %while.exit.t64

while.body.t63.lr.ph:                             ; preds = %while.cond.t62.preheader
  %t333.i = icmp sgt i32 %bitround, 0
  br label %while.body.t63

cleanup.t44:                                      ; preds = %merge.t196, %entry
  tail call void @sysy_free_i32(ptr %t48)
  tail call void @sysy_free_i32(ptr %t46)
  tail call void @sysy_free_i32(ptr %t43)
  ret void

while.body.t63:                                   ; preds = %while.body.t63.lr.ph, %getNumPos.exit28
  %storemerge97 = phi i32 [ %l, %while.body.t63.lr.ph ], [ %t83, %getNumPos.exit28 ]
  %0 = sext i32 %storemerge97 to i64
  %t69 = getelementptr i32, ptr %a, i64 %0
  %t70 = load i32, ptr %t69, align 4
  br i1 %t333.i, label %while.body.t29.i, label %getNumPos.exit.thread

getNumPos.exit.thread:                            ; preds = %while.body.t63
  %t39.i80 = srem i32 %t70, 16
  %1 = sext i32 %t39.i80 to i64
  %t7381 = getelementptr i32, ptr %t48, i64 %1
  %t7482 = load i32, ptr %t7381, align 4
  br label %getNumPos.exit28

while.body.t29.i:                                 ; preds = %while.body.t63, %while.body.t29.i
  %t27_i.05.i = phi i32 [ %t37.i, %while.body.t29.i ], [ 0, %while.body.t63 ]
  %t24.04.i = phi i32 [ %t35.i, %while.body.t29.i ], [ %t70, %while.body.t63 ]
  %t35.i = sdiv i32 %t24.04.i, 16
  %t37.i = add nuw nsw i32 %t27_i.05.i, 1
  %t33.i = icmp slt i32 %t37.i, %bitround
  br i1 %t33.i, label %while.body.t29.i, label %getNumPos.exit

getNumPos.exit:                                   ; preds = %while.body.t29.i
  %t39.i = srem i32 %t35.i, 16
  %2 = sext i32 %t39.i to i64
  %t73 = getelementptr i32, ptr %t48, i64 %2
  %t74 = load i32, ptr %t73, align 4
  br label %while.body.t29.i22

while.body.t29.i22:                               ; preds = %getNumPos.exit, %while.body.t29.i22
  %t27_i.05.i23 = phi i32 [ %t37.i26, %while.body.t29.i22 ], [ 0, %getNumPos.exit ]
  %t24.04.i24 = phi i32 [ %t35.i25, %while.body.t29.i22 ], [ %t70, %getNumPos.exit ]
  %t35.i25 = sdiv i32 %t24.04.i24, 16
  %t37.i26 = add nuw nsw i32 %t27_i.05.i23, 1
  %t33.i27 = icmp slt i32 %t37.i26, %bitround
  br i1 %t33.i27, label %while.body.t29.i22, label %getNumPos.exit28.loopexit

getNumPos.exit28.loopexit:                        ; preds = %while.body.t29.i22
  %.pre114 = srem i32 %t35.i25, 16
  %.pre115 = sext i32 %.pre114 to i64
  br label %getNumPos.exit28

getNumPos.exit28:                                 ; preds = %getNumPos.exit28.loopexit, %getNumPos.exit.thread
  %.pre-phi116 = phi i64 [ %.pre115, %getNumPos.exit28.loopexit ], [ %1, %getNumPos.exit.thread ]
  %t7584.in = phi i32 [ %t74, %getNumPos.exit28.loopexit ], [ %t7482, %getNumPos.exit.thread ]
  %t7584 = add i32 %t7584.in, 1
  %t81 = getelementptr i32, ptr %t48, i64 %.pre-phi116
  store i32 %t7584, ptr %t81, align 4
  %t83 = add nsw i32 %storemerge97, 1
  %t67 = icmp slt i32 %t83, %r
  br i1 %t67, label %while.body.t63, label %while.exit.t64

while.exit.t64:                                   ; preds = %getNumPos.exit28, %while.cond.t62.preheader
  store i32 %l, ptr %t43, align 4
  %t88 = load i32, ptr %t48, align 4
  %t89 = add i32 %t88, %l
  store i32 %t89, ptr %t46, align 4
  %invariant.gep = getelementptr i32, ptr %t46, i64 -1
  %t101 = getelementptr i32, ptr %t43, i64 1
  store i32 %t89, ptr %t101, align 4
  %t106 = getelementptr i32, ptr %t48, i64 1
  %t107 = load i32, ptr %t106, align 4
  %t108 = add i32 %t107, %t89
  %t110 = getelementptr i32, ptr %t46, i64 1
  store i32 %t108, ptr %t110, align 4
  %t101.1 = getelementptr i32, ptr %t43, i64 2
  store i32 %t108, ptr %t101.1, align 4
  %t106.1 = getelementptr i32, ptr %t48, i64 2
  %t107.1 = load i32, ptr %t106.1, align 4
  %t108.1 = add i32 %t107.1, %t108
  %t110.1 = getelementptr i32, ptr %t46, i64 2
  store i32 %t108.1, ptr %t110.1, align 4
  %t101.2 = getelementptr i32, ptr %t43, i64 3
  store i32 %t108.1, ptr %t101.2, align 4
  %t106.2 = getelementptr i32, ptr %t48, i64 3
  %t107.2 = load i32, ptr %t106.2, align 4
  %t108.2 = add i32 %t107.2, %t108.1
  %t110.2 = getelementptr i32, ptr %t46, i64 3
  store i32 %t108.2, ptr %t110.2, align 4
  %t101.3 = getelementptr i32, ptr %t43, i64 4
  store i32 %t108.2, ptr %t101.3, align 4
  %t106.3 = getelementptr i32, ptr %t48, i64 4
  %t107.3 = load i32, ptr %t106.3, align 4
  %t108.3 = add i32 %t107.3, %t108.2
  %t110.3 = getelementptr i32, ptr %t46, i64 4
  store i32 %t108.3, ptr %t110.3, align 4
  %t101.4 = getelementptr i32, ptr %t43, i64 5
  store i32 %t108.3, ptr %t101.4, align 4
  %t106.4 = getelementptr i32, ptr %t48, i64 5
  %t107.4 = load i32, ptr %t106.4, align 4
  %t108.4 = add i32 %t107.4, %t108.3
  %t110.4 = getelementptr i32, ptr %t46, i64 5
  store i32 %t108.4, ptr %t110.4, align 4
  %t101.5 = getelementptr i32, ptr %t43, i64 6
  store i32 %t108.4, ptr %t101.5, align 4
  %t106.5 = getelementptr i32, ptr %t48, i64 6
  %t107.5 = load i32, ptr %t106.5, align 4
  %t108.5 = add i32 %t107.5, %t108.4
  %t110.5 = getelementptr i32, ptr %t46, i64 6
  store i32 %t108.5, ptr %t110.5, align 4
  %t101.6 = getelementptr i32, ptr %t43, i64 7
  store i32 %t108.5, ptr %t101.6, align 4
  %t106.6 = getelementptr i32, ptr %t48, i64 7
  %t107.6 = load i32, ptr %t106.6, align 4
  %t108.6 = add i32 %t107.6, %t108.5
  %t110.6 = getelementptr i32, ptr %t46, i64 7
  store i32 %t108.6, ptr %t110.6, align 4
  %t101.7 = getelementptr i32, ptr %t43, i64 8
  store i32 %t108.6, ptr %t101.7, align 4
  %t106.7 = getelementptr i32, ptr %t48, i64 8
  %t107.7 = load i32, ptr %t106.7, align 4
  %t108.7 = add i32 %t107.7, %t108.6
  %t110.7 = getelementptr i32, ptr %t46, i64 8
  store i32 %t108.7, ptr %t110.7, align 4
  %t101.8 = getelementptr i32, ptr %t43, i64 9
  store i32 %t108.7, ptr %t101.8, align 4
  %t106.8 = getelementptr i32, ptr %t48, i64 9
  %t107.8 = load i32, ptr %t106.8, align 4
  %t108.8 = add i32 %t107.8, %t108.7
  %t110.8 = getelementptr i32, ptr %t46, i64 9
  store i32 %t108.8, ptr %t110.8, align 4
  %t101.9 = getelementptr i32, ptr %t43, i64 10
  store i32 %t108.8, ptr %t101.9, align 4
  %t106.9 = getelementptr i32, ptr %t48, i64 10
  %t107.9 = load i32, ptr %t106.9, align 4
  %t108.9 = add i32 %t107.9, %t108.8
  %t110.9 = getelementptr i32, ptr %t46, i64 10
  store i32 %t108.9, ptr %t110.9, align 4
  %t101.10 = getelementptr i32, ptr %t43, i64 11
  store i32 %t108.9, ptr %t101.10, align 4
  %t106.10 = getelementptr i32, ptr %t48, i64 11
  %t107.10 = load i32, ptr %t106.10, align 4
  %t108.10 = add i32 %t107.10, %t108.9
  %t110.10 = getelementptr i32, ptr %t46, i64 11
  store i32 %t108.10, ptr %t110.10, align 4
  %t101.11 = getelementptr i32, ptr %t43, i64 12
  store i32 %t108.10, ptr %t101.11, align 4
  %t106.11 = getelementptr i32, ptr %t48, i64 12
  %t107.11 = load i32, ptr %t106.11, align 4
  %t108.11 = add i32 %t107.11, %t108.10
  %t110.11 = getelementptr i32, ptr %t46, i64 12
  store i32 %t108.11, ptr %t110.11, align 4
  %t101.12 = getelementptr i32, ptr %t43, i64 13
  store i32 %t108.11, ptr %t101.12, align 4
  %t106.12 = getelementptr i32, ptr %t48, i64 13
  %t107.12 = load i32, ptr %t106.12, align 4
  %t108.12 = add i32 %t107.12, %t108.11
  %t110.12 = getelementptr i32, ptr %t46, i64 13
  store i32 %t108.12, ptr %t110.12, align 4
  %t101.13 = getelementptr i32, ptr %t43, i64 14
  store i32 %t108.12, ptr %t101.13, align 4
  %t106.13 = getelementptr i32, ptr %t48, i64 14
  %t107.13 = load i32, ptr %t106.13, align 4
  %t108.13 = add i32 %t107.13, %t108.12
  %t110.13 = getelementptr i32, ptr %t46, i64 14
  store i32 %t108.13, ptr %t110.13, align 4
  %t101.14 = getelementptr i32, ptr %t43, i64 15
  store i32 %t108.13, ptr %t101.14, align 4
  %t106.14 = getelementptr i32, ptr %t48, i64 15
  %t107.14 = load i32, ptr %t106.14, align 4
  %t108.14 = add i32 %t107.14, %t108.13
  %t110.14 = getelementptr i32, ptr %t46, i64 15
  store i32 %t108.14, ptr %t110.14, align 4
  %t333.i29 = icmp sgt i32 %bitround, 0
  br label %while.cond.t118.preheader

while.cond.t118.preheader:                        ; preds = %while.exit.t64, %while.exit.t120
  %storemerge17104 = phi i32 [ 0, %while.exit.t64 ], [ %t180, %while.exit.t120 ]
  %3 = zext nneg i32 %storemerge17104 to i64
  %t122 = getelementptr i32, ptr %t43, i64 %3
  %t125 = getelementptr i32, ptr %t46, i64 %3
  %t123100 = load i32, ptr %t122, align 4
  %t126101 = load i32, ptr %t125, align 4
  %t127102 = icmp slt i32 %t123100, %t126101
  br i1 %t127102, label %while.body.t119, label %while.exit.t120

while.body.t191.peel.next:                        ; preds = %while.exit.t120
  store i32 %l, ptr %t43, align 4
  %t187 = load i32, ptr %t48, align 4
  %t188 = add i32 %t187, %l
  store i32 %t188, ptr %t46, align 4
  %t215 = add i32 %bitround, -1
  %t218.peel.pre = load i32, ptr %t43, align 4
  tail call void @radixSort(i32 %t215, ptr %a, i32 %t218.peel.pre, i32 %t188)
  br label %merge.t196

while.body.t119:                                  ; preds = %while.cond.t118.preheader, %while.exit.t136
  %t123103 = phi i32 [ %t176, %while.exit.t136 ], [ %t123100, %while.cond.t118.preheader ]
  %4 = sext i32 %t123103 to i64
  %t132 = getelementptr i32, ptr %a, i64 %4
  %t133 = load i32, ptr %t132, align 4
  br label %while.cond.t134

while.exit.t120:                                  ; preds = %while.exit.t136, %while.cond.t118.preheader
  %t180 = add nuw nsw i32 %storemerge17104, 1
  %t117 = icmp ult i32 %storemerge17104, 15
  br i1 %t117, label %while.cond.t118.preheader, label %while.body.t191.peel.next

while.cond.t134:                                  ; preds = %getNumPos.exit78, %while.body.t119
  %t15099 = phi i32 [ %t150129, %getNumPos.exit78 ], [ %t133, %while.body.t119 ]
  br i1 %t333.i29, label %while.body.t29.i32, label %getNumPos.exit38.thread

while.body.t29.i32:                               ; preds = %while.cond.t134, %while.body.t29.i32
  %t27_i.05.i33 = phi i32 [ %t37.i36, %while.body.t29.i32 ], [ 0, %while.cond.t134 ]
  %t24.04.i34 = phi i32 [ %t35.i35, %while.body.t29.i32 ], [ %t15099, %while.cond.t134 ]
  %t35.i35 = sdiv i32 %t24.04.i34, 16
  %t37.i36 = add nuw nsw i32 %t27_i.05.i33, 1
  %t33.i37 = icmp slt i32 %t37.i36, %bitround
  br i1 %t33.i37, label %while.body.t29.i32, label %getNumPos.exit38

getNumPos.exit38:                                 ; preds = %while.body.t29.i32
  %t39.i31 = srem i32 %t35.i35, 16
  %t141.not = icmp eq i32 %t39.i31, %storemerge17104
  br i1 %t141.not, label %while.exit.t136, label %while.body.t29.i42

getNumPos.exit38.thread:                          ; preds = %while.cond.t134
  %t39.i3186 = srem i32 %t15099, 16
  %t141.not87 = icmp eq i32 %t39.i3186, %storemerge17104
  br i1 %t141.not87, label %while.exit.t136, label %getNumPos.exit48.thread

getNumPos.exit48.thread:                          ; preds = %getNumPos.exit38.thread
  %5 = sext i32 %t39.i3186 to i64
  %t147125 = getelementptr i32, ptr %t43, i64 %5
  %t148126 = load i32, ptr %t147125, align 4
  %6 = sext i32 %t148126 to i64
  %t149127 = getelementptr i32, ptr %a, i64 %6
  %t150128 = load i32, ptr %t149127, align 4
  br label %getNumPos.exit68.thread

while.body.t29.i42:                               ; preds = %getNumPos.exit38, %while.body.t29.i42
  %t27_i.05.i43 = phi i32 [ %t37.i46, %while.body.t29.i42 ], [ 0, %getNumPos.exit38 ]
  %t24.04.i44 = phi i32 [ %t35.i45, %while.body.t29.i42 ], [ %t15099, %getNumPos.exit38 ]
  %t35.i45 = sdiv i32 %t24.04.i44, 16
  %t37.i46 = add nuw nsw i32 %t27_i.05.i43, 1
  %t33.i47 = icmp slt i32 %t37.i46, %bitround
  br i1 %t33.i47, label %while.body.t29.i42, label %getNumPos.exit48

getNumPos.exit48:                                 ; preds = %while.body.t29.i42
  %.pre117 = srem i32 %t35.i45, 16
  %7 = sext i32 %.pre117 to i64
  %t147 = getelementptr i32, ptr %t43, i64 %7
  %t148 = load i32, ptr %t147, align 4
  %8 = sext i32 %t148 to i64
  %t149 = getelementptr i32, ptr %a, i64 %8
  %t150 = load i32, ptr %t149, align 4
  br i1 %t333.i29, label %while.body.t29.i52, label %getNumPos.exit68.thread

while.body.t29.i52:                               ; preds = %getNumPos.exit48, %while.body.t29.i52
  %t27_i.05.i53 = phi i32 [ %t37.i56, %while.body.t29.i52 ], [ 0, %getNumPos.exit48 ]
  %t24.04.i54 = phi i32 [ %t35.i55, %while.body.t29.i52 ], [ %t15099, %getNumPos.exit48 ]
  %t35.i55 = sdiv i32 %t24.04.i54, 16
  %t37.i56 = add nuw nsw i32 %t27_i.05.i53, 1
  %t33.i57 = icmp slt i32 %t37.i56, %bitround
  br i1 %t33.i57, label %while.body.t29.i52, label %while.body.t29.i62.preheader

while.body.t29.i62.preheader:                     ; preds = %while.body.t29.i52
  %t39.i51 = srem i32 %t35.i55, 16
  %9 = sext i32 %t39.i51 to i64
  %t155 = getelementptr i32, ptr %t43, i64 %9
  %t156 = load i32, ptr %t155, align 4
  %10 = sext i32 %t156 to i64
  %t157 = getelementptr i32, ptr %a, i64 %10
  store i32 %t15099, ptr %t157, align 4
  br label %while.body.t29.i62

getNumPos.exit68.thread:                          ; preds = %getNumPos.exit48, %getNumPos.exit48.thread
  %t150130 = phi i32 [ %t150128, %getNumPos.exit48.thread ], [ %t150, %getNumPos.exit48 ]
  %t39.i51.c = srem i32 %t15099, 16
  %11 = sext i32 %t39.i51.c to i64
  %t155.c = getelementptr i32, ptr %t43, i64 %11
  %t156.c = load i32, ptr %t155.c, align 4
  %12 = sext i32 %t156.c to i64
  %t157.c = getelementptr i32, ptr %a, i64 %12
  store i32 %t15099, ptr %t157.c, align 4
  %t16191 = getelementptr i32, ptr %t43, i64 %11
  %t16292 = load i32, ptr %t16191, align 4
  br label %getNumPos.exit78

while.body.t29.i62:                               ; preds = %while.body.t29.i62.preheader, %while.body.t29.i62
  %t27_i.05.i63 = phi i32 [ %t37.i66, %while.body.t29.i62 ], [ 0, %while.body.t29.i62.preheader ]
  %t24.04.i64 = phi i32 [ %t35.i65, %while.body.t29.i62 ], [ %t15099, %while.body.t29.i62.preheader ]
  %t35.i65 = sdiv i32 %t24.04.i64, 16
  %t37.i66 = add nuw nsw i32 %t27_i.05.i63, 1
  %t33.i67 = icmp slt i32 %t37.i66, %bitround
  br i1 %t33.i67, label %while.body.t29.i62, label %getNumPos.exit68

getNumPos.exit68:                                 ; preds = %while.body.t29.i62
  %t39.i61 = srem i32 %t35.i65, 16
  %13 = sext i32 %t39.i61 to i64
  %t161 = getelementptr i32, ptr %t43, i64 %13
  %t162 = load i32, ptr %t161, align 4
  br label %while.body.t29.i72

while.body.t29.i72:                               ; preds = %getNumPos.exit68, %while.body.t29.i72
  %t27_i.05.i73 = phi i32 [ %t37.i76, %while.body.t29.i72 ], [ 0, %getNumPos.exit68 ]
  %t24.04.i74 = phi i32 [ %t35.i75, %while.body.t29.i72 ], [ %t15099, %getNumPos.exit68 ]
  %t35.i75 = sdiv i32 %t24.04.i74, 16
  %t37.i76 = add nuw nsw i32 %t27_i.05.i73, 1
  %t33.i77 = icmp slt i32 %t37.i76, %bitround
  br i1 %t33.i77, label %while.body.t29.i72, label %getNumPos.exit78.loopexit

getNumPos.exit78.loopexit:                        ; preds = %while.body.t29.i72
  %.pre118 = srem i32 %t35.i75, 16
  %.pre119 = sext i32 %.pre118 to i64
  br label %getNumPos.exit78

getNumPos.exit78:                                 ; preds = %getNumPos.exit78.loopexit, %getNumPos.exit68.thread
  %t150129 = phi i32 [ %t150, %getNumPos.exit78.loopexit ], [ %t150130, %getNumPos.exit68.thread ]
  %.pre-phi120 = phi i64 [ %.pre119, %getNumPos.exit78.loopexit ], [ %11, %getNumPos.exit68.thread ]
  %t16394.in = phi i32 [ %t162, %getNumPos.exit78.loopexit ], [ %t16292, %getNumPos.exit68.thread ]
  %t16394 = add i32 %t16394.in, 1
  %t167 = getelementptr i32, ptr %t43, i64 %.pre-phi120
  store i32 %t16394, ptr %t167, align 4
  br label %while.cond.t134

while.exit.t136:                                  ; preds = %getNumPos.exit38.thread, %getNumPos.exit38
  %t171 = load i32, ptr %t122, align 4
  %14 = sext i32 %t171 to i64
  %t172 = getelementptr i32, ptr %a, i64 %14
  store i32 %t15099, ptr %t172, align 4
  %t175 = load i32, ptr %t122, align 4
  %t176 = add i32 %t175, 1
  store i32 %t176, ptr %t122, align 4
  %t126 = load i32, ptr %t125, align 4
  %t127 = icmp slt i32 %t176, %t126
  br i1 %t127, label %while.body.t119, label %while.exit.t120

merge.t196:                                       ; preds = %while.body.t191.peel.next, %merge.t196
  %storemerge18107 = phi i32 [ 1, %while.body.t191.peel.next ], [ %t224, %merge.t196 ]
  %15 = zext nneg i32 %storemerge18107 to i64
  %gep106 = getelementptr i32, ptr %invariant.gep, i64 %15
  %t202 = load i32, ptr %gep106, align 4
  %t204 = getelementptr i32, ptr %t43, i64 %15
  store i32 %t202, ptr %t204, align 4
  %t209 = getelementptr i32, ptr %t48, i64 %15
  %t210 = load i32, ptr %t209, align 4
  %t211 = add i32 %t210, %t202
  %t213 = getelementptr i32, ptr %t46, i64 %15
  store i32 %t211, ptr %t213, align 4
  %t218.pre = load i32, ptr %t204, align 4
  tail call void @radixSort(i32 %t215, ptr %a, i32 %t218.pre, i32 %t211)
  %t224 = add nuw nsw i32 %storemerge18107, 1
  %t194 = icmp ult i32 %storemerge18107, 15
  br i1 %t194, label %merge.t196, label %cleanup.t44, !llvm.loop !0
}

define noundef i32 @main() local_unnamed_addr {
entry:
  %t231 = tail call i32 @getarray(ptr nonnull @a)
  tail call void @starttime()
  tail call void @radixSort(i32 8, ptr nonnull @a, i32 0, i32 %t231)
  %ans.promoted = load i32, ptr @ans, align 4
  %t2427 = icmp sgt i32 %t231, 0
  br i1 %t2427, label %while.body.t238, label %while.exit.t239

while.body.t238:                                  ; preds = %entry, %while.body.t238
  %t236_i.09 = phi i32 [ %t254, %while.body.t238 ], [ 0, %entry ]
  %t25268 = phi i32 [ %t252, %while.body.t238 ], [ %ans.promoted, %entry ]
  %0 = zext nneg i32 %t236_i.09 to i64
  %t246 = getelementptr [30000010 x i32], ptr @a, i64 0, i64 %0
  %t247 = load i32, ptr %t246, align 4
  %t249 = add nuw i32 %t236_i.09, 2
  %t250 = srem i32 %t247, %t249
  %t251 = mul i32 %t250, %t236_i.09
  %t252 = add i32 %t251, %t25268
  %t254 = add nuw nsw i32 %t236_i.09, 1
  %t242 = icmp slt i32 %t254, %t231
  br i1 %t242, label %while.body.t238, label %while.cond.t237.while.exit.t239_crit_edge

while.cond.t237.while.exit.t239_crit_edge:        ; preds = %while.body.t238
  store i32 %t252, ptr @ans, align 4
  br label %while.exit.t239

while.exit.t239:                                  ; preds = %while.cond.t237.while.exit.t239_crit_edge, %entry
  %t257 = phi i32 [ %t252, %while.cond.t237.while.exit.t239_crit_edge ], [ %ans.promoted, %entry ]
  %t258 = icmp slt i32 %t257, 0
  br i1 %t258, label %then.t255, label %merge.t256

then.t255:                                        ; preds = %while.exit.t239
  %t260 = sub i32 0, %t257
  store i32 %t260, ptr @ans, align 4
  br label %merge.t256

merge.t256:                                       ; preds = %then.t255, %while.exit.t239
  tail call void @stoptime()
  %t262 = load i32, ptr @ans, align 4
  tail call void @putint(i32 %t262)
  tail call void @putch(i32 10)
  ret i32 0
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.smax.i32(i32, i32) #2

attributes #0 = { nofree norecurse nosync nounwind memory(argmem: read) }
attributes #1 = { nofree norecurse nosync nounwind memory(none) }
attributes #2 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }

!0 = distinct !{!0, !1}
!1 = !{!"llvm.loop.peeled.count", i32 1}