; LLVM IR from JanaSabuj/cppdump :: Range Queries/AND_OR.ll (Z5queryii)

; Unoptimized IR (clang -disable-llvm-passes):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@dp = external dso_local global [32 x [500 x i32]], align 16

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #0

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #0

; Function Attrs: mustprogress nounwind uwtable
define dso_local noundef i32 @_Z5queryii(i32 noundef %0, i32 noundef %1) #1 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = alloca i32, align 4
  %6 = alloca i32, align 4
  store i32 %0, ptr %3, align 4, !tbaa !5
  store i32 %1, ptr %4, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %5) #2
  store i32 0, ptr %5, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %6) #2
  store i32 0, ptr %6, align 4, !tbaa !5
  br label %7

7:                                                ; preds = %46, %2
  %8 = load i32, ptr %6, align 4, !tbaa !5
  %9 = icmp slt i32 %8, 32
  br i1 %9, label %11, label %10

10:                                               ; preds = %7
  call void @llvm.lifetime.end.p0(i64 4, ptr %6) #2
  br label %49

11:                                               ; preds = %7
  %12 = load i32, ptr %4, align 4, !tbaa !5
  %13 = sext i32 %12 to i64
  %14 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %13
  %15 = load i32, ptr %6, align 4, !tbaa !5
  %16 = sext i32 %15 to i64
  %17 = getelementptr inbounds [500 x i32], ptr %14, i64 0, i64 %16
  %18 = load i32, ptr %17, align 4, !tbaa !5
  %19 = load i32, ptr %3, align 4, !tbaa !5
  %20 = sub nsw i32 %19, 1
  %21 = icmp sge i32 %20, 0
  br i1 %21, label %22, label %31

22:                                               ; preds = %11
  %23 = load i32, ptr %3, align 4, !tbaa !5
  %24 = sub nsw i32 %23, 1
  %25 = sext i32 %24 to i64
  %26 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %25
  %27 = load i32, ptr %6, align 4, !tbaa !5
  %28 = sext i32 %27 to i64
  %29 = getelementptr inbounds [500 x i32], ptr %26, i64 0, i64 %28
  %30 = load i32, ptr %29, align 4, !tbaa !5
  br label %32

31:                                               ; preds = %11
  br label %32

32:                                               ; preds = %31, %22
  %33 = phi i32 [ %30, %22 ], [ 0, %31 ]
  %34 = sub nsw i32 %18, %33
  %35 = load i32, ptr %4, align 4, !tbaa !5
  %36 = load i32, ptr %3, align 4, !tbaa !5
  %37 = sub nsw i32 %35, %36
  %38 = add nsw i32 %37, 1
  %39 = icmp eq i32 %34, %38
  br i1 %39, label %40, label %45

40:                                               ; preds = %32
  %41 = load i32, ptr %6, align 4, !tbaa !5
  %42 = shl i32 1, %41
  %43 = load i32, ptr %5, align 4, !tbaa !5
  %44 = or i32 %43, %42
  store i32 %44, ptr %5, align 4, !tbaa !5
  br label %45

45:                                               ; preds = %40, %32
  br label %46

46:                                               ; preds = %45
  %47 = load i32, ptr %6, align 4, !tbaa !5
  %48 = add nsw i32 %47, 1
  store i32 %48, ptr %6, align 4, !tbaa !5
  br label %7, !llvm.loop !9

49:                                               ; preds = %10
  %50 = load i32, ptr %5, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr %5) #2
  ret i32 %50
}

attributes #0 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #1 = { mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #2 = { nounwind }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}
!9 = distinct !{!9, !10}
!10 = !{!"llvm.loop.mustprogress"}


; Optimized IR (opt -passes='default<O3>'):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@dp = external dso_local local_unnamed_addr global [32 x [500 x i32]], align 16

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(read, argmem: none, inaccessiblemem: none) uwtable
define dso_local noundef i32 @_Z5queryii(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = sext i32 %1 to i64
  %4 = icmp sgt i32 %0, 0
  %reass.sub = sub i32 %1, %0
  %5 = add i32 %reass.sub, 1
  %6 = add nsw i32 %0, -1
  %7 = zext nneg i32 %6 to i64
  br i1 %4, label %vector.body, label %.split.preheader

vector.body:                                      ; preds = %2
  %broadcast.splatinsert = insertelement <4 x i32> poison, i32 %5, i64 0
  %broadcast.splat = shufflevector <4 x i32> %broadcast.splatinsert, <4 x i32> poison, <4 x i32> zeroinitializer
  %8 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 0
  %9 = getelementptr inbounds i8, ptr %8, i64 16
  %wide.load = load <4 x i32>, ptr %8, align 16, !tbaa !5
  %wide.load23 = load <4 x i32>, ptr %9, align 16, !tbaa !5
  %10 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %7, i64 0
  %11 = getelementptr inbounds i8, ptr %10, i64 16
  %wide.load24 = load <4 x i32>, ptr %10, align 16, !tbaa !5
  %wide.load25 = load <4 x i32>, ptr %11, align 16, !tbaa !5
  %12 = sub nsw <4 x i32> %wide.load, %wide.load24
  %13 = sub nsw <4 x i32> %wide.load23, %wide.load25
  %14 = icmp eq <4 x i32> %12, %broadcast.splat
  %15 = icmp eq <4 x i32> %13, %broadcast.splat
  %16 = select <4 x i1> %14, <4 x i32> <i32 1, i32 2, i32 4, i32 8>, <4 x i32> zeroinitializer
  %17 = select <4 x i1> %15, <4 x i32> <i32 16, i32 32, i32 64, i32 128>, <4 x i32> zeroinitializer
  %18 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 8
  %19 = getelementptr inbounds i8, ptr %18, i64 16
  %wide.load.1 = load <4 x i32>, ptr %18, align 16, !tbaa !5
  %wide.load23.1 = load <4 x i32>, ptr %19, align 16, !tbaa !5
  %20 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %7, i64 8
  %21 = getelementptr inbounds i8, ptr %20, i64 16
  %wide.load24.1 = load <4 x i32>, ptr %20, align 16, !tbaa !5
  %wide.load25.1 = load <4 x i32>, ptr %21, align 16, !tbaa !5
  %22 = sub nsw <4 x i32> %wide.load.1, %wide.load24.1
  %23 = sub nsw <4 x i32> %wide.load23.1, %wide.load25.1
  %24 = icmp eq <4 x i32> %22, %broadcast.splat
  %25 = icmp eq <4 x i32> %23, %broadcast.splat
  %26 = select <4 x i1> %24, <4 x i32> <i32 256, i32 512, i32 1024, i32 2048>, <4 x i32> zeroinitializer
  %27 = select <4 x i1> %25, <4 x i32> <i32 4096, i32 8192, i32 16384, i32 32768>, <4 x i32> zeroinitializer
  %28 = or disjoint <4 x i32> %26, %16
  %29 = or disjoint <4 x i32> %27, %17
  %30 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 16
  %31 = getelementptr inbounds i8, ptr %30, i64 16
  %wide.load.2 = load <4 x i32>, ptr %30, align 16, !tbaa !5
  %wide.load23.2 = load <4 x i32>, ptr %31, align 16, !tbaa !5
  %32 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %7, i64 16
  %33 = getelementptr inbounds i8, ptr %32, i64 16
  %wide.load24.2 = load <4 x i32>, ptr %32, align 16, !tbaa !5
  %wide.load25.2 = load <4 x i32>, ptr %33, align 16, !tbaa !5
  %34 = sub nsw <4 x i32> %wide.load.2, %wide.load24.2
  %35 = sub nsw <4 x i32> %wide.load23.2, %wide.load25.2
  %36 = icmp eq <4 x i32> %34, %broadcast.splat
  %37 = icmp eq <4 x i32> %35, %broadcast.splat
  %38 = select <4 x i1> %36, <4 x i32> <i32 65536, i32 131072, i32 262144, i32 524288>, <4 x i32> zeroinitializer
  %39 = select <4 x i1> %37, <4 x i32> <i32 1048576, i32 2097152, i32 4194304, i32 8388608>, <4 x i32> zeroinitializer
  %40 = or disjoint <4 x i32> %38, %28
  %41 = or disjoint <4 x i32> %39, %29
  %42 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 24
  %43 = getelementptr inbounds i8, ptr %42, i64 16
  %wide.load.3 = load <4 x i32>, ptr %42, align 16, !tbaa !5
  %wide.load23.3 = load <4 x i32>, ptr %43, align 16, !tbaa !5
  %44 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %7, i64 24
  %45 = getelementptr inbounds i8, ptr %44, i64 16
  %wide.load24.3 = load <4 x i32>, ptr %44, align 16, !tbaa !5
  %wide.load25.3 = load <4 x i32>, ptr %45, align 16, !tbaa !5
  %46 = sub nsw <4 x i32> %wide.load.3, %wide.load24.3
  %47 = sub nsw <4 x i32> %wide.load23.3, %wide.load25.3
  %48 = icmp eq <4 x i32> %46, %broadcast.splat
  %49 = icmp eq <4 x i32> %47, %broadcast.splat
  %50 = select <4 x i1> %48, <4 x i32> <i32 16777216, i32 33554432, i32 67108864, i32 134217728>, <4 x i32> zeroinitializer
  %51 = select <4 x i1> %49, <4 x i32> <i32 268435456, i32 536870912, i32 1073741824, i32 -2147483648>, <4 x i32> zeroinitializer
  %52 = or disjoint <4 x i32> %50, %40
  %53 = or disjoint <4 x i32> %51, %41
  %bin.rdx = or disjoint <4 x i32> %53, %52
  %54 = tail call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> %bin.rdx)
  br label %.split17.us

.split.preheader:                                 ; preds = %2
  %55 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 0
  %56 = load i32, ptr %55, align 16, !tbaa !5
  %57 = icmp eq i32 %56, %5
  %58 = zext i1 %57 to i32
  %59 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 1
  %60 = load <16 x i32>, ptr %59, align 4, !tbaa !5
  %61 = insertelement <16 x i32> poison, i32 %5, i64 0
  %62 = shufflevector <16 x i32> %61, <16 x i32> poison, <16 x i32> zeroinitializer
  %63 = icmp eq <16 x i32> %60, %62
  %64 = select <16 x i1> %63, <16 x i32> <i32 2, i32 4, i32 8, i32 16, i32 32, i32 64, i32 128, i32 256, i32 512, i32 1024, i32 2048, i32 4096, i32 8192, i32 16384, i32 32768, i32 65536>, <16 x i32> zeroinitializer
  %65 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 17
  %66 = load <8 x i32>, ptr %65, align 4, !tbaa !5
  %67 = insertelement <8 x i32> poison, i32 %5, i64 0
  %68 = shufflevector <8 x i32> %67, <8 x i32> poison, <8 x i32> zeroinitializer
  %69 = icmp eq <8 x i32> %66, %68
  %70 = select <8 x i1> %69, <8 x i32> <i32 131072, i32 262144, i32 524288, i32 1048576, i32 2097152, i32 4194304, i32 8388608, i32 16777216>, <8 x i32> zeroinitializer
  %71 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 25
  %72 = load <4 x i32>, ptr %71, align 4, !tbaa !5
  %73 = insertelement <4 x i32> poison, i32 %5, i64 0
  %74 = shufflevector <4 x i32> %73, <4 x i32> poison, <4 x i32> zeroinitializer
  %75 = icmp eq <4 x i32> %72, %74
  %76 = select <4 x i1> %75, <4 x i32> <i32 33554432, i32 67108864, i32 134217728, i32 268435456>, <4 x i32> zeroinitializer
  %77 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 29
  %78 = load i32, ptr %77, align 4, !tbaa !5
  %79 = icmp eq i32 %78, %5
  %80 = select i1 %79, i32 536870912, i32 0
  %81 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 30
  %82 = load i32, ptr %81, align 8, !tbaa !5
  %83 = icmp eq i32 %82, %5
  %84 = select i1 %83, i32 1073741824, i32 0
  %85 = getelementptr inbounds [32 x [500 x i32]], ptr @dp, i64 0, i64 %3, i64 31
  %86 = load i32, ptr %85, align 4, !tbaa !5
  %87 = icmp eq i32 %86, %5
  %88 = select i1 %87, i32 -2147483648, i32 0
  %89 = tail call i32 @llvm.vector.reduce.or.v16i32(<16 x i32> %64)
  %90 = tail call i32 @llvm.vector.reduce.or.v8i32(<8 x i32> %70)
  %op.rdx = or disjoint i32 %89, %90
  %91 = tail call i32 @llvm.vector.reduce.or.v4i32(<4 x i32> %76)
  %op.rdx26 = or disjoint i32 %op.rdx, %91
  %op.rdx27 = or disjoint i32 %op.rdx26, %80
  %op.rdx28 = or disjoint i32 %84, %88
  %op.rdx29 = or disjoint i32 %op.rdx27, %op.rdx28
  %op.rdx30 = or i32 %op.rdx29, %58
  br label %.split17.us

.split17.us:                                      ; preds = %vector.body, %.split.preheader
  %.us-phi = phi i32 [ %op.rdx30, %.split.preheader ], [ %54, %vector.body ]
  ret i32 %.us-phi
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.vector.reduce.or.v4i32(<4 x i32>) #1

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.vector.reduce.or.v16i32(<16 x i32>) #1

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.vector.reduce.or.v8i32(<8 x i32>) #1

attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(read, argmem: none, inaccessiblemem: none) uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}


; Effective O3 passes: EarlyCSEPass,GVNPass,GlobalOptPass,IPSCCPPass,IndVarSimplifyPass,InferAlignmentPass,InferFunctionAttrsPass,InstCombinePass,JumpThreadingPass,LCSSAPass,LICMPass,LoopInstSimplifyPass,LoopLoadEliminationPass,LoopRotatePass,LoopSimplifyCFGPass,LoopSimplifyPass,LoopUnrollPass,LoopVectorizePass,PostOrderFunctionAttrsPass,ReassociatePass,SLPVectorizerPass,SROAPass,SimplifyCFGPass,TailCallElimPass