; LLVM IR from davidesantangelo/krep :: krep (kmp_search)

; 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"

%struct.search_params = type { ptr, i64, ptr, ptr, i64, i8, i8, i8, i8, i8, i8, ptr, ptr, i64 }

@lower_table = external dso_local global [256 x i8], align 16
@stderr = external global ptr, align 8
@.str.73 = external hidden unnamed_addr constant [32 x i8], align 1
@.str.74 = external hidden unnamed_addr constant [46 x i8], align 1

; 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: nounwind allocsize(0)
declare noalias ptr @malloc(i64 noundef) #1

declare void @perror(ptr noundef) #2

; Function Attrs: nounwind
declare i32 @fprintf(ptr noundef, ptr noundef, ...) #3

; Function Attrs: nounwind
declare void @free(ptr noundef) #3

; Function Attrs: inlinehint nounwind uwtable
declare dso_local zeroext i1 @match_result_add(ptr noundef, i64 noundef, i64 noundef) #4

; Function Attrs: nounwind uwtable
declare dso_local i64 @find_line_start(ptr noundef, i64 noundef, i64 noundef) #5

; Function Attrs: nounwind uwtable
declare dso_local i64 @find_line_end(ptr noundef, i64 noundef, i64 noundef) #5

; Function Attrs: inlinehint nounwind uwtable
declare hidden zeroext i1 @is_whole_word_match(ptr noundef, i64 noundef, i64 noundef, i64 noundef) #4

; Function Attrs: nounwind uwtable
define dso_local i64 @kmp_search(ptr noundef %0, ptr noundef %1, i64 noundef %2, ptr noundef %3) #5 {
  %5 = alloca i64, align 8
  %6 = alloca ptr, align 8
  %7 = alloca ptr, align 8
  %8 = alloca i64, align 8
  %9 = alloca ptr, align 8
  %10 = alloca i64, align 8
  %11 = alloca ptr, align 8
  %12 = alloca i64, align 8
  %13 = alloca i8, align 1
  %14 = alloca i8, align 1
  %15 = alloca i8, align 1
  %16 = alloca i64, align 8
  %17 = alloca i32, align 4
  %18 = alloca ptr, align 8
  %19 = alloca i64, align 8
  %20 = alloca i64, align 8
  %21 = alloca ptr, align 8
  %22 = alloca i64, align 8
  %23 = alloca i8, align 1
  %24 = alloca i8, align 1
  %25 = alloca i64, align 8
  %26 = alloca i64, align 8
  %27 = alloca i64, align 8
  store ptr %0, ptr %6, align 8, !tbaa !5
  store ptr %1, ptr %7, align 8, !tbaa !5
  store i64 %2, ptr %8, align 8, !tbaa !9
  store ptr %3, ptr %9, align 8, !tbaa !5
  %28 = load ptr, ptr %6, align 8, !tbaa !5
  %29 = getelementptr inbounds %struct.search_params, ptr %28, i32 0, i32 13
  %30 = load i64, ptr %29, align 8, !tbaa !11
  %31 = icmp eq i64 %30, 0
  br i1 %31, label %32, label %33

32:                                               ; preds = %4
  store i64 0, ptr %5, align 8
  br label %278

33:                                               ; preds = %4
  call void @llvm.lifetime.start.p0(i64 8, ptr %10) #6
  store i64 0, ptr %10, align 8, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 8, ptr %11) #6
  %34 = load ptr, ptr %6, align 8, !tbaa !5
  %35 = getelementptr inbounds %struct.search_params, ptr %34, i32 0, i32 0
  %36 = load ptr, ptr %35, align 8, !tbaa !14
  store ptr %36, ptr %11, align 8, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 8, ptr %12) #6
  %37 = load ptr, ptr %6, align 8, !tbaa !5
  %38 = getelementptr inbounds %struct.search_params, ptr %37, i32 0, i32 1
  %39 = load i64, ptr %38, align 8, !tbaa !15
  store i64 %39, ptr %12, align 8, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 1, ptr %13) #6
  %40 = load ptr, ptr %6, align 8, !tbaa !5
  %41 = getelementptr inbounds %struct.search_params, ptr %40, i32 0, i32 5
  %42 = load i8, ptr %41, align 8, !tbaa !16, !range !17, !noundef !18
  %43 = trunc i8 %42 to i1
  %44 = zext i1 %43 to i8
  store i8 %44, ptr %13, align 1, !tbaa !19
  call void @llvm.lifetime.start.p0(i64 1, ptr %14) #6
  %45 = load ptr, ptr %6, align 8, !tbaa !5
  %46 = getelementptr inbounds %struct.search_params, ptr %45, i32 0, i32 7
  %47 = load i8, ptr %46, align 2, !tbaa !20, !range !17, !noundef !18
  %48 = trunc i8 %47 to i1
  %49 = zext i1 %48 to i8
  store i8 %49, ptr %14, align 1, !tbaa !19
  call void @llvm.lifetime.start.p0(i64 1, ptr %15) #6
  %50 = load ptr, ptr %6, align 8, !tbaa !5
  %51 = getelementptr inbounds %struct.search_params, ptr %50, i32 0, i32 9
  %52 = load i8, ptr %51, align 4, !tbaa !21, !range !17, !noundef !18
  %53 = trunc i8 %52 to i1
  %54 = zext i1 %53 to i8
  store i8 %54, ptr %15, align 1, !tbaa !19
  call void @llvm.lifetime.start.p0(i64 8, ptr %16) #6
  %55 = load ptr, ptr %6, align 8, !tbaa !5
  %56 = getelementptr inbounds %struct.search_params, ptr %55, i32 0, i32 13
  %57 = load i64, ptr %56, align 8, !tbaa !11
  store i64 %57, ptr %16, align 8, !tbaa !9
  %58 = load i64, ptr %12, align 8, !tbaa !9
  %59 = icmp eq i64 %58, 0
  br i1 %59, label %64, label %60

60:                                               ; preds = %33
  %61 = load i64, ptr %8, align 8, !tbaa !9
  %62 = load i64, ptr %12, align 8, !tbaa !9
  %63 = icmp ult i64 %61, %62
  br i1 %63, label %64, label %65

64:                                               ; preds = %60, %33
  store i64 0, ptr %5, align 8
  store i32 1, ptr %17, align 4
  br label %277

65:                                               ; preds = %60
  call void @llvm.lifetime.start.p0(i64 8, ptr %18) #6
  %66 = load i64, ptr %12, align 8, !tbaa !9
  %67 = mul i64 %66, 4
  %68 = call noalias ptr @malloc(i64 noundef %67) #7
  store ptr %68, ptr %18, align 8, !tbaa !5
  %69 = load ptr, ptr %18, align 8, !tbaa !5
  %70 = icmp ne ptr %69, null
  br i1 %70, label %72, label %71

71:                                               ; preds = %65
  call void @perror(ptr noundef @.str.73)
  store i64 0, ptr %5, align 8
  store i32 1, ptr %17, align 4
  br label %276

72:                                               ; preds = %65
  %73 = load ptr, ptr %11, align 8, !tbaa !5
  %74 = load i64, ptr %12, align 8, !tbaa !9
  %75 = load ptr, ptr %18, align 8, !tbaa !5
  %76 = load i8, ptr %13, align 1, !tbaa !19, !range !17, !noundef !18
  %77 = trunc i8 %76 to i1
  call void @compute_lps_array(ptr noundef %73, i64 noundef %74, ptr noundef %75, i1 noundef zeroext %77)
  call void @llvm.lifetime.start.p0(i64 8, ptr %19) #6
  store i64 0, ptr %19, align 8, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 8, ptr %20) #6
  store i64 0, ptr %20, align 8, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 8, ptr %21) #6
  %78 = load ptr, ptr %7, align 8, !tbaa !5
  store ptr %78, ptr %21, align 8, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 8, ptr %22) #6
  store i64 -1, ptr %22, align 8, !tbaa !9
  br label %79

79:                                               ; preds = %272, %270, %72
  %80 = load i64, ptr %19, align 8, !tbaa !9
  %81 = load i64, ptr %8, align 8, !tbaa !9
  %82 = icmp ult i64 %80, %81
  br i1 %82, label %83, label %273

83:                                               ; preds = %79
  call void @llvm.lifetime.start.p0(i64 1, ptr %23) #6
  %84 = load i8, ptr %13, align 1, !tbaa !19, !range !17, !noundef !18
  %85 = trunc i8 %84 to i1
  br i1 %85, label %86, label %92

86:                                               ; preds = %83
  %87 = load ptr, ptr %21, align 8, !tbaa !5
  %88 = load i64, ptr %19, align 8, !tbaa !9
  %89 = getelementptr inbounds i8, ptr %87, i64 %88
  %90 = load i8, ptr %89, align 1, !tbaa !22
  %91 = zext i8 %90 to i32
  br label %101

92:                                               ; preds = %83
  %93 = load ptr, ptr %21, align 8, !tbaa !5
  %94 = load i64, ptr %19, align 8, !tbaa !9
  %95 = getelementptr inbounds i8, ptr %93, i64 %94
  %96 = load i8, ptr %95, align 1, !tbaa !22
  %97 = zext i8 %96 to i64
  %98 = getelementptr inbounds [256 x i8], ptr @lower_table, i64 0, i64 %97
  %99 = load i8, ptr %98, align 1, !tbaa !22
  %100 = zext i8 %99 to i32
  br label %101

101:                                              ; preds = %92, %86
  %102 = phi i32 [ %91, %86 ], [ %100, %92 ]
  %103 = trunc i32 %102 to i8
  store i8 %103, ptr %23, align 1, !tbaa !22
  call void @llvm.lifetime.start.p0(i64 1, ptr %24) #6
  %104 = load i8, ptr %13, align 1, !tbaa !19, !range !17, !noundef !18
  %105 = trunc i8 %104 to i1
  br i1 %105, label %106, label %112

106:                                              ; preds = %101
  %107 = load ptr, ptr %11, align 8, !tbaa !5
  %108 = load i64, ptr %20, align 8, !tbaa !9
  %109 = getelementptr inbounds i8, ptr %107, i64 %108
  %110 = load i8, ptr %109, align 1, !tbaa !22
  %111 = zext i8 %110 to i32
  br label %121

112:                                              ; preds = %101
  %113 = load ptr, ptr %11, align 8, !tbaa !5
  %114 = load i64, ptr %20, align 8, !tbaa !9
  %115 = getelementptr inbounds i8, ptr %113, i64 %114
  %116 = load i8, ptr %115, align 1, !tbaa !22
  %117 = zext i8 %116 to i64
  %118 = getelementptr inbounds [256 x i8], ptr @lower_table, i64 0, i64 %117
  %119 = load i8, ptr %118, align 1, !tbaa !22
  %120 = zext i8 %119 to i32
  br label %121

121:                                              ; preds = %112, %106
  %122 = phi i32 [ %111, %106 ], [ %120, %112 ]
  %123 = trunc i32 %122 to i8
  store i8 %123, ptr %24, align 1, !tbaa !22
  %124 = load i8, ptr %24, align 1, !tbaa !22
  %125 = zext i8 %124 to i32
  %126 = load i8, ptr %23, align 1, !tbaa !22
  %127 = zext i8 %126 to i32
  %128 = icmp eq i32 %125, %127
  br i1 %128, label %129, label %134

129:                                              ; preds = %121
  %130 = load i64, ptr %19, align 8, !tbaa !9
  %131 = add i64 %130, 1
  store i64 %131, ptr %19, align 8, !tbaa !9
  %132 = load i64, ptr %20, align 8, !tbaa !9
  %133 = add i64 %132, 1
  store i64 %133, ptr %20, align 8, !tbaa !9
  br label %134

134:                                              ; preds = %129, %121
  %135 = load i64, ptr %20, align 8, !tbaa !9
  %136 = load i64, ptr %12, align 8, !tbaa !9
  %137 = icmp eq i64 %135, %136
  br i1 %137, label %138, label %244

138:                                              ; preds = %134
  call void @llvm.lifetime.start.p0(i64 8, ptr %25) #6
  %139 = load i64, ptr %19, align 8, !tbaa !9
  %140 = load i64, ptr %20, align 8, !tbaa !9
  %141 = sub i64 %139, %140
  store i64 %141, ptr %25, align 8, !tbaa !9
  %142 = load ptr, ptr %6, align 8, !tbaa !5
  %143 = getelementptr inbounds %struct.search_params, ptr %142, i32 0, i32 10
  %144 = load i8, ptr %143, align 1, !tbaa !23, !range !17, !noundef !18
  %145 = trunc i8 %144 to i1
  br i1 %145, label %146, label %155

146:                                              ; preds = %138
  %147 = load ptr, ptr %7, align 8, !tbaa !5
  %148 = load i64, ptr %8, align 8, !tbaa !9
  %149 = load i64, ptr %25, align 8, !tbaa !9
  %150 = load i64, ptr %25, align 8, !tbaa !9
  %151 = load i64, ptr %12, align 8, !tbaa !9
  %152 = add i64 %150, %151
  %153 = call zeroext i1 @is_whole_word_match(ptr noundef %147, i64 noundef %148, i64 noundef %149, i64 noundef %152)
  br i1 %153, label %155, label %154

154:                                              ; preds = %146
  store i64 0, ptr %20, align 8, !tbaa !9
  store i32 2, ptr %17, align 4
  br label %241, !llvm.loop !24

155:                                              ; preds = %146, %138
  %156 = load i8, ptr %14, align 1, !tbaa !19, !range !17, !noundef !18
  %157 = trunc i8 %156 to i1
  br i1 %157, label %158, label %196

158:                                              ; preds = %155
  call void @llvm.lifetime.start.p0(i64 8, ptr %26) #6
  %159 = load ptr, ptr %7, align 8, !tbaa !5
  %160 = load i64, ptr %8, align 8, !tbaa !9
  %161 = load i64, ptr %25, align 8, !tbaa !9
  %162 = call i64 @find_line_start(ptr noundef %159, i64 noundef %160, i64 noundef %161)
  store i64 %162, ptr %26, align 8, !tbaa !9
  %163 = load i64, ptr %26, align 8, !tbaa !9
  %164 = load i64, ptr %22, align 8, !tbaa !9
  %165 = icmp ne i64 %163, %164
  br i1 %165, label %166, label %192

166:                                              ; preds = %158
  %167 = load i64, ptr %16, align 8, !tbaa !9
  %168 = icmp ne i64 %167, -1
  br i1 %168, label %169, label %174

169:                                              ; preds = %166
  %170 = load i64, ptr %10, align 8, !tbaa !9
  %171 = load i64, ptr %16, align 8, !tbaa !9
  %172 = icmp uge i64 %170, %171
  br i1 %172, label %173, label %174

173:                                              ; preds = %169
  store i32 3, ptr %17, align 4
  br label %193

174:                                              ; preds = %169, %166
  %175 = load i64, ptr %10, align 8, !tbaa !9
  %176 = add i64 %175, 1
  store i64 %176, ptr %10, align 8, !tbaa !9
  %177 = load i64, ptr %26, align 8, !tbaa !9
  store i64 %177, ptr %22, align 8, !tbaa !9
  call void @llvm.lifetime.start.p0(i64 8, ptr %27) #6
  %178 = load ptr, ptr %7, align 8, !tbaa !5
  %179 = load i64, ptr %8, align 8, !tbaa !9
  %180 = load i64, ptr %26, align 8, !tbaa !9
  %181 = call i64 @find_line_end(ptr noundef %178, i64 noundef %179, i64 noundef %180)
  store i64 %181, ptr %27, align 8, !tbaa !9
  %182 = load i64, ptr %27, align 8, !tbaa !9
  %183 = load i64, ptr %8, align 8, !tbaa !9
  %184 = icmp ult i64 %182, %183
  br i1 %184, label %185, label %188

185:                                              ; preds = %174
  %186 = load i64, ptr %27, align 8, !tbaa !9
  %187 = add i64 %186, 1
  br label %190

188:                                              ; preds = %174
  %189 = load i64, ptr %8, align 8, !tbaa !9
  br label %190

190:                                              ; preds = %188, %185
  %191 = phi i64 [ %187, %185 ], [ %189, %188 ]
  store i64 %191, ptr %19, align 8, !tbaa !9
  store i64 0, ptr %20, align 8, !tbaa !9
  store i32 2, ptr %17, align 4
  call void @llvm.lifetime.end.p0(i64 8, ptr %27) #6
  br label %193

192:                                              ; preds = %158
  store i64 0, ptr %20, align 8, !tbaa !9
  store i32 0, ptr %17, align 4
  br label %193

193:                                              ; preds = %192, %190, %173
  call void @llvm.lifetime.end.p0(i64 8, ptr %26) #6
  %194 = load i32, ptr %17, align 4
  switch i32 %194, label %241 [
    i32 0, label %195
  ]

195:                                              ; preds = %193
  br label %240

196:                                              ; preds = %155
  %197 = load i64, ptr %16, align 8, !tbaa !9
  %198 = icmp ne i64 %197, -1
  br i1 %198, label %199, label %217

199:                                              ; preds = %196
  %200 = load i64, ptr %10, align 8, !tbaa !9
  %201 = load i64, ptr %16, align 8, !tbaa !9
  %202 = icmp uge i64 %200, %201
  br i1 %202, label %203, label %217

203:                                              ; preds = %199
  %204 = load i8, ptr %15, align 1, !tbaa !19, !range !17, !noundef !18
  %205 = trunc i8 %204 to i1
  br i1 %205, label %206, label %216

206:                                              ; preds = %203
  %207 = load ptr, ptr %9, align 8, !tbaa !5
  %208 = icmp ne ptr %207, null
  br i1 %208, label %209, label %216

209:                                              ; preds = %206
  %210 = load ptr, ptr %9, align 8, !tbaa !5
  %211 = load i64, ptr %25, align 8, !tbaa !9
  %212 = load i64, ptr %25, align 8, !tbaa !9
  %213 = load i64, ptr %12, align 8, !tbaa !9
  %214 = add i64 %212, %213
  %215 = call zeroext i1 @match_result_add(ptr noundef %210, i64 noundef %211, i64 noundef %214)
  br label %216

216:                                              ; preds = %209, %206, %203
  store i32 3, ptr %17, align 4
  br label %241

217:                                              ; preds = %199, %196
  %218 = load i64, ptr %10, align 8, !tbaa !9
  %219 = add i64 %218, 1
  store i64 %219, ptr %10, align 8, !tbaa !9
  %220 = load i8, ptr %15, align 1, !tbaa !19, !range !17, !noundef !18
  %221 = trunc i8 %220 to i1
  br i1 %221, label %222, label %236

222:                                              ; preds = %217
  %223 = load ptr, ptr %9, align 8, !tbaa !5
  %224 = icmp ne ptr %223, null
  br i1 %224, label %225, label %236

225:                                              ; preds = %222
  %226 = load ptr, ptr %9, align 8, !tbaa !5
  %227 = load i64, ptr %25, align 8, !tbaa !9
  %228 = load i64, ptr %25, align 8, !tbaa !9
  %229 = load i64, ptr %12, align 8, !tbaa !9
  %230 = add i64 %228, %229
  %231 = call zeroext i1 @match_result_add(ptr noundef %226, i64 noundef %227, i64 noundef %230)
  br i1 %231, label %235, label %232

232:                                              ; preds = %225
  %233 = load ptr, ptr @stderr, align 8, !tbaa !5
  %234 = call i32 (ptr, ptr, ...) @fprintf(ptr noundef %233, ptr noundef @.str.74) #6
  br label %235

235:                                              ; preds = %232, %225
  br label %236

236:                                              ; preds = %235, %222, %217
  %237 = load i64, ptr %25, align 8, !tbaa !9
  %238 = load i64, ptr %12, align 8, !tbaa !9
  %239 = add i64 %237, %238
  store i64 %239, ptr %19, align 8, !tbaa !9
  store i64 0, ptr %20, align 8, !tbaa !9
  br label %240

240:                                              ; preds = %236, %195
  store i32 0, ptr %17, align 4
  br label %241

241:                                              ; preds = %240, %216, %193, %154
  call void @llvm.lifetime.end.p0(i64 8, ptr %25) #6
  %242 = load i32, ptr %17, align 4
  switch i32 %242, label %270 [
    i32 0, label %243
  ]

243:                                              ; preds = %241
  br label %269

244:                                              ; preds = %134
  %245 = load i64, ptr %19, align 8, !tbaa !9
  %246 = load i64, ptr %8, align 8, !tbaa !9
  %247 = icmp ult i64 %245, %246
  br i1 %247, label %248, label %268

248:                                              ; preds = %244
  %249 = load i8, ptr %24, align 1, !tbaa !22
  %250 = zext i8 %249 to i32
  %251 = load i8, ptr %23, align 1, !tbaa !22
  %252 = zext i8 %251 to i32
  %253 = icmp ne i32 %250, %252
  br i1 %253, label %254, label %268

254:                                              ; preds = %248
  %255 = load i64, ptr %20, align 8, !tbaa !9
  %256 = icmp ne i64 %255, 0
  br i1 %256, label %257, label %264

257:                                              ; preds = %254
  %258 = load ptr, ptr %18, align 8, !tbaa !5
  %259 = load i64, ptr %20, align 8, !tbaa !9
  %260 = sub i64 %259, 1
  %261 = getelementptr inbounds i32, ptr %258, i64 %260
  %262 = load i32, ptr %261, align 4, !tbaa !26
  %263 = sext i32 %262 to i64
  store i64 %263, ptr %20, align 8, !tbaa !9
  br label %267

264:                                              ; preds = %254
  %265 = load i64, ptr %19, align 8, !tbaa !9
  %266 = add i64 %265, 1
  store i64 %266, ptr %19, align 8, !tbaa !9
  br label %267

267:                                              ; preds = %264, %257
  br label %268

268:                                              ; preds = %267, %248, %244
  br label %269

269:                                              ; preds = %268, %243
  store i32 0, ptr %17, align 4
  br label %270

270:                                              ; preds = %269, %241
  call void @llvm.lifetime.end.p0(i64 1, ptr %24) #6
  call void @llvm.lifetime.end.p0(i64 1, ptr %23) #6
  %271 = load i32, ptr %17, align 4
  switch i32 %271, label %280 [
    i32 0, label %272
    i32 2, label %79
    i32 3, label %273
  ]

272:                                              ; preds = %270
  br label %79, !llvm.loop !24

273:                                              ; preds = %270, %79
  %274 = load ptr, ptr %18, align 8, !tbaa !5
  call void @free(ptr noundef %274) #6
  %275 = load i64, ptr %10, align 8, !tbaa !9
  store i64 %275, ptr %5, align 8
  store i32 1, ptr %17, align 4
  call void @llvm.lifetime.end.p0(i64 8, ptr %22) #6
  call void @llvm.lifetime.end.p0(i64 8, ptr %21) #6
  call void @llvm.lifetime.end.p0(i64 8, ptr %20) #6
  call void @llvm.lifetime.end.p0(i64 8, ptr %19) #6
  br label %276

276:                                              ; preds = %273, %71
  call void @llvm.lifetime.end.p0(i64 8, ptr %18) #6
  br label %277

277:                                              ; preds = %276, %64
  call void @llvm.lifetime.end.p0(i64 8, ptr %16) #6
  call void @llvm.lifetime.end.p0(i64 1, ptr %15) #6
  call void @llvm.lifetime.end.p0(i64 1, ptr %14) #6
  call void @llvm.lifetime.end.p0(i64 1, ptr %13) #6
  call void @llvm.lifetime.end.p0(i64 8, ptr %12) #6
  call void @llvm.lifetime.end.p0(i64 8, ptr %11) #6
  call void @llvm.lifetime.end.p0(i64 8, ptr %10) #6
  br label %278

278:                                              ; preds = %277, %32
  %279 = load i64, ptr %5, align 8
  ret i64 %279

280:                                              ; preds = %270
  unreachable
}

; Function Attrs: nounwind uwtable
declare hidden void @compute_lps_array(ptr noundef, i64 noundef, ptr noundef, i1 noundef zeroext) #5

attributes #0 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #1 = { nounwind allocsize(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 = { "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 #3 = { nounwind "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 #4 = { inlinehint 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 #5 = { 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 #6 = { nounwind }
attributes #7 = { nounwind allocsize(0) }

!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 = !{!"any pointer", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C/C++ TBAA"}
!9 = !{!10, !10, i64 0}
!10 = !{!"long", !7, i64 0}
!11 = !{!12, !10, i64 64}
!12 = !{!"search_params", !6, i64 0, !10, i64 8, !6, i64 16, !6, i64 24, !10, i64 32, !13, i64 40, !13, i64 41, !13, i64 42, !13, i64 43, !13, i64 44, !13, i64 45, !6, i64 48, !6, i64 56, !10, i64 64}
!13 = !{!"_Bool", !7, i64 0}
!14 = !{!12, !6, i64 0}
!15 = !{!12, !10, i64 8}
!16 = !{!12, !13, i64 40}
!17 = !{i8 0, i8 2}
!18 = !{}
!19 = !{!13, !13, i64 0}
!20 = !{!12, !13, i64 42}
!21 = !{!12, !13, i64 44}
!22 = !{!7, !7, i64 0}
!23 = !{!12, !13, i64 45}
!24 = distinct !{!24, !25}
!25 = !{!"llvm.loop.mustprogress"}
!26 = !{!27, !27, i64 0}
!27 = !{!"int", !7, i64 0}


; 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"

@lower_table = external dso_local local_unnamed_addr global [256 x i8], align 16
@stderr = external local_unnamed_addr global ptr, align 8
@.str.73 = external hidden unnamed_addr constant [32 x i8], align 1
@.str.74 = external hidden unnamed_addr constant [46 x i8], align 1

; Function Attrs: mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @malloc(i64 noundef) local_unnamed_addr #0

; Function Attrs: nofree nounwind
declare void @perror(ptr nocapture noundef readonly) local_unnamed_addr #1

; Function Attrs: nofree nounwind
declare noundef i32 @fprintf(ptr nocapture noundef, ptr nocapture noundef readonly, ...) local_unnamed_addr #1

; Function Attrs: mustprogress nounwind willreturn allockind("free") memory(argmem: readwrite, inaccessiblemem: readwrite)
declare void @free(ptr allocptr nocapture noundef) local_unnamed_addr #2

; Function Attrs: inlinehint nounwind uwtable
declare dso_local zeroext i1 @match_result_add(ptr noundef, i64 noundef, i64 noundef) local_unnamed_addr #3

; Function Attrs: nounwind uwtable
declare dso_local i64 @find_line_start(ptr noundef, i64 noundef, i64 noundef) local_unnamed_addr #4

; Function Attrs: nounwind uwtable
declare dso_local i64 @find_line_end(ptr noundef, i64 noundef, i64 noundef) local_unnamed_addr #4

; Function Attrs: inlinehint nounwind uwtable
declare hidden zeroext i1 @is_whole_word_match(ptr noundef, i64 noundef, i64 noundef, i64 noundef) local_unnamed_addr #3

; Function Attrs: nounwind uwtable
define dso_local i64 @kmp_search(ptr nocapture noundef readonly %0, ptr noundef %1, i64 noundef %2, ptr noundef %3) local_unnamed_addr #4 {
  %5 = getelementptr inbounds i8, ptr %0, i64 64
  %6 = load i64, ptr %5, align 8, !tbaa !5
  %7 = icmp eq i64 %6, 0
  br i1 %7, label %109, label %8

8:                                                ; preds = %4
  %9 = load ptr, ptr %0, align 8, !tbaa !12
  %10 = getelementptr inbounds i8, ptr %0, i64 8
  %11 = load i64, ptr %10, align 8, !tbaa !13
  %12 = getelementptr inbounds i8, ptr %0, i64 40
  %13 = load i8, ptr %12, align 8, !tbaa !14, !range !15, !noundef !16
  %14 = trunc nuw i8 %13 to i1
  %15 = getelementptr inbounds i8, ptr %0, i64 42
  %16 = load i8, ptr %15, align 2, !tbaa !17, !range !15, !noundef !16
  %17 = trunc nuw i8 %16 to i1
  %18 = getelementptr inbounds i8, ptr %0, i64 44
  %19 = load i8, ptr %18, align 4, !tbaa !18, !range !15, !noundef !16
  %20 = trunc nuw i8 %19 to i1
  %21 = add i64 %11, -1
  %or.cond139.not = icmp ult i64 %21, %2
  br i1 %or.cond139.not, label %22, label %109

22:                                               ; preds = %8
  %23 = shl i64 %11, 2
  %24 = tail call noalias ptr @malloc(i64 noundef %23) #5
  %.not = icmp eq ptr %24, null
  br i1 %.not, label %25, label %26

25:                                               ; preds = %22
  tail call void @perror(ptr noundef nonnull @.str.73) #6
  br label %109

26:                                               ; preds = %22
  tail call void @compute_lps_array(ptr noundef %9, i64 noundef %11, ptr noundef nonnull %24, i1 noundef zeroext %14)
  %invariant.gep = getelementptr i8, ptr %24, i64 -4
  %27 = getelementptr inbounds i8, ptr %0, i64 45
  %.not134 = icmp eq i64 %6, -1
  %28 = icmp ne ptr %3, null
  %or.cond = and i1 %28, %20
  br i1 %17, label %.split.us.preheader, label %.split.preheader

.split.us.preheader:                              ; preds = %26, %.split.us
  %.096.us172 = phi i64 [ %.5.us, %.split.us ], [ 0, %26 ]
  %.0102.us171 = phi i64 [ %.6108.us, %.split.us ], [ 0, %26 ]
  %.0109.us170 = phi i64 [ %.6115.us, %.split.us ], [ 0, %26 ]
  %.0116.us169 = phi i64 [ %.5121.us, %.split.us ], [ -1, %26 ]
  %29 = getelementptr inbounds i8, ptr %1, i64 %.0102.us171
  br i1 %14, label %38, label %30

30:                                               ; preds = %.split.us.preheader
  %31 = load i8, ptr %29, align 1, !tbaa !19
  %32 = zext i8 %31 to i64
  %33 = getelementptr inbounds [256 x i8], ptr @lower_table, i64 0, i64 %32
  %34 = getelementptr inbounds i8, ptr %9, i64 %.0109.us170
  %35 = load i8, ptr %34, align 1, !tbaa !19
  %36 = zext i8 %35 to i64
  %37 = getelementptr inbounds [256 x i8], ptr @lower_table, i64 0, i64 %36
  br label %40

38:                                               ; preds = %.split.us.preheader
  %39 = getelementptr inbounds i8, ptr %9, i64 %.0109.us170
  br label %40

40:                                               ; preds = %38, %30
  %.in129146.in.us = phi ptr [ %29, %38 ], [ %33, %30 ]
  %.in.in130.us = phi ptr [ %39, %38 ], [ %37, %30 ]
  %.in129146.us = load i8, ptr %.in129146.in.us, align 1, !tbaa !19
  %.in131.us = load i8, ptr %.in.in130.us, align 1, !tbaa !19
  %41 = icmp eq i8 %.in131.us, %.in129146.us
  %42 = zext i1 %41 to i64
  %.1110.us = add i64 %.0109.us170, %42
  %.1103.us = add nuw i64 %.0102.us171, %42
  %43 = icmp eq i64 %.1110.us, %11
  br i1 %43, label %52, label %44

44:                                               ; preds = %40
  %45 = icmp uge i64 %.1103.us, %2
  %or.cond142.us = or i1 %41, %45
  br i1 %or.cond142.us, label %.split.us, label %46

46:                                               ; preds = %44
  %.not133.us = icmp eq i64 %.1110.us, 0
  br i1 %.not133.us, label %50, label %47

47:                                               ; preds = %46
  %gep.us = getelementptr i32, ptr %invariant.gep, i64 %.1110.us
  %48 = load i32, ptr %gep.us, align 4, !tbaa !20
  %49 = sext i32 %48 to i64
  br label %.split.us

50:                                               ; preds = %46
  %51 = add nuw i64 %.1103.us, 1
  br label %.split.us

52:                                               ; preds = %40
  %53 = sub i64 %.1103.us, %11
  %54 = load i8, ptr %27, align 1, !tbaa !22, !range !15, !noundef !16
  %55 = trunc nuw i8 %54 to i1
  br i1 %55, label %56, label %58

56:                                               ; preds = %52
  %57 = tail call zeroext i1 @is_whole_word_match(ptr noundef nonnull %1, i64 noundef %2, i64 noundef %53, i64 noundef %.1103.us)
  br i1 %57, label %58, label %.split.us, !llvm.loop !23

58:                                               ; preds = %56, %52
  %59 = tail call i64 @find_line_start(ptr noundef %1, i64 noundef %2, i64 noundef %53)
  %.not136.us = icmp eq i64 %59, %.0116.us169
  br i1 %.not136.us, label %.split.us, label %60

60:                                               ; preds = %58
  %.not138.us = icmp ult i64 %.096.us172, %6
  %or.cond140.us = select i1 %.not134, i1 true, i1 %.not138.us
  br i1 %or.cond140.us, label %61, label %.split149.us

61:                                               ; preds = %60
  %62 = add i64 %.096.us172, 1
  %63 = tail call i64 @find_line_end(ptr noundef %1, i64 noundef %2, i64 noundef %59)
  %64 = icmp ult i64 %63, %2
  %65 = add i64 %63, 1
  %66 = select i1 %64, i64 %65, i64 %2
  br label %.split.us

.split.us:                                        ; preds = %61, %58, %56, %50, %47, %44
  %.5121.us = phi i64 [ %.0116.us169, %47 ], [ %.0116.us169, %50 ], [ %.0116.us169, %44 ], [ %.0116.us169, %56 ], [ %59, %61 ], [ %.0116.us169, %58 ]
  %.6115.us = phi i64 [ %49, %47 ], [ 0, %50 ], [ %.1110.us, %44 ], [ 0, %56 ], [ 0, %61 ], [ 0, %58 ]
  %.6108.us = phi i64 [ %.1103.us, %47 ], [ %51, %50 ], [ %.1103.us, %44 ], [ %.1103.us, %56 ], [ %66, %61 ], [ %.1103.us, %58 ]
  %.5.us = phi i64 [ %.096.us172, %47 ], [ %.096.us172, %50 ], [ %.096.us172, %44 ], [ %.096.us172, %56 ], [ %62, %61 ], [ %.096.us172, %58 ]
  %67 = icmp ult i64 %.6108.us, %2
  br i1 %67, label %.split.us.preheader, label %.split149.us

.split.preheader:                                 ; preds = %26, %.split
  %.096168 = phi i64 [ %.5, %.split ], [ 0, %26 ]
  %.0102167 = phi i64 [ %.6108, %.split ], [ 0, %26 ]
  %.0109166 = phi i64 [ %.6115, %.split ], [ 0, %26 ]
  %68 = getelementptr inbounds i8, ptr %1, i64 %.0102167
  br i1 %14, label %69, label %71

69:                                               ; preds = %.split.preheader
  %70 = getelementptr inbounds i8, ptr %9, i64 %.0109166
  br label %79

71:                                               ; preds = %.split.preheader
  %72 = load i8, ptr %68, align 1, !tbaa !19
  %73 = zext i8 %72 to i64
  %74 = getelementptr inbounds [256 x i8], ptr @lower_table, i64 0, i64 %73
  %75 = getelementptr inbounds i8, ptr %9, i64 %.0109166
  %76 = load i8, ptr %75, align 1, !tbaa !19
  %77 = zext i8 %76 to i64
  %78 = getelementptr inbounds [256 x i8], ptr @lower_table, i64 0, i64 %77
  br label %79

79:                                               ; preds = %71, %69
  %.in129146.in = phi ptr [ %68, %69 ], [ %74, %71 ]
  %.in.in130 = phi ptr [ %70, %69 ], [ %78, %71 ]
  %.in129146 = load i8, ptr %.in129146.in, align 1, !tbaa !19
  %.in131 = load i8, ptr %.in.in130, align 1, !tbaa !19
  %80 = icmp eq i8 %.in131, %.in129146
  %81 = zext i1 %80 to i64
  %.1110 = add i64 %.0109166, %81
  %.1103 = add nuw i64 %.0102167, %81
  %82 = icmp eq i64 %.1110, %11
  br i1 %82, label %83, label %100

83:                                               ; preds = %79
  %84 = sub i64 %.1103, %11
  %85 = load i8, ptr %27, align 1, !tbaa !22, !range !15, !noundef !16
  %86 = trunc nuw i8 %85 to i1
  br i1 %86, label %87, label %89

87:                                               ; preds = %83
  %88 = tail call zeroext i1 @is_whole_word_match(ptr noundef nonnull %1, i64 noundef %2, i64 noundef %84, i64 noundef %.1103)
  br i1 %88, label %89, label %.split, !llvm.loop !23

89:                                               ; preds = %87, %83
  %.not135 = icmp ult i64 %.096168, %6
  %or.cond141 = select i1 %.not134, i1 true, i1 %.not135
  br i1 %or.cond141, label %93, label %90

90:                                               ; preds = %89
  br i1 %or.cond, label %91, label %.split149.us

91:                                               ; preds = %90
  %92 = tail call zeroext i1 @match_result_add(ptr noundef nonnull %3, i64 noundef %84, i64 noundef %.1103)
  br label %.split149.us

93:                                               ; preds = %89
  %94 = add i64 %.096168, 1
  br i1 %or.cond, label %95, label %.split

95:                                               ; preds = %93
  %96 = tail call zeroext i1 @match_result_add(ptr noundef nonnull %3, i64 noundef %84, i64 noundef %.1103)
  br i1 %96, label %.split, label %97

97:                                               ; preds = %95
  %98 = load ptr, ptr @stderr, align 8, !tbaa !25
  %99 = tail call i32 (ptr, ptr, ...) @fprintf(ptr noundef %98, ptr noundef nonnull @.str.74) #7
  br label %.split

100:                                              ; preds = %79
  %101 = icmp uge i64 %.1103, %2
  %or.cond142 = or i1 %80, %101
  br i1 %or.cond142, label %.split, label %102

102:                                              ; preds = %100
  %.not133 = icmp eq i64 %.1110, 0
  br i1 %.not133, label %106, label %103

103:                                              ; preds = %102
  %gep = getelementptr i32, ptr %invariant.gep, i64 %.1110
  %104 = load i32, ptr %gep, align 4, !tbaa !20
  %105 = sext i32 %104 to i64
  br label %.split

106:                                              ; preds = %102
  %107 = add nuw i64 %.1103, 1
  br label %.split

.split:                                           ; preds = %93, %97, %95, %87, %103, %106, %100
  %.6115 = phi i64 [ %105, %103 ], [ 0, %106 ], [ %.1110, %100 ], [ 0, %87 ], [ 0, %95 ], [ 0, %97 ], [ 0, %93 ]
  %.6108 = phi i64 [ %.1103, %103 ], [ %107, %106 ], [ %.1103, %100 ], [ %.1103, %87 ], [ %.1103, %95 ], [ %.1103, %97 ], [ %.1103, %93 ]
  %.5 = phi i64 [ %.096168, %103 ], [ %.096168, %106 ], [ %.096168, %100 ], [ %.096168, %87 ], [ %94, %95 ], [ %94, %97 ], [ %94, %93 ]
  %108 = icmp ult i64 %.6108, %2
  br i1 %108, label %.split.preheader, label %.split149.us

.split149.us:                                     ; preds = %.split, %60, %.split.us, %90, %91
  %.us-phi = phi i64 [ %.096168, %91 ], [ %.096168, %90 ], [ %.096.us172, %60 ], [ %.5.us, %.split.us ], [ %.5, %.split ]
  tail call void @free(ptr noundef %24) #8
  br label %109

109:                                              ; preds = %8, %.split149.us, %25, %4
  %.2 = phi i64 [ 0, %4 ], [ 0, %8 ], [ %.us-phi, %.split149.us ], [ 0, %25 ]
  ret i64 %.2
}

; Function Attrs: nounwind uwtable
declare hidden void @compute_lps_array(ptr noundef, i64 noundef, ptr noundef, i1 noundef zeroext) local_unnamed_addr #4

attributes #0 = { mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" "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 = { nofree nounwind "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 = { mustprogress nounwind willreturn allockind("free") memory(argmem: readwrite, inaccessiblemem: readwrite) "alloc-family"="malloc" "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 #3 = { inlinehint 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 #4 = { 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 #5 = { nounwind allocsize(0) }
attributes #6 = { cold }
attributes #7 = { cold nounwind }
attributes #8 = { 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, !10, i64 64}
!6 = !{!"search_params", !7, i64 0, !10, i64 8, !7, i64 16, !7, i64 24, !10, i64 32, !11, i64 40, !11, i64 41, !11, i64 42, !11, i64 43, !11, i64 44, !11, i64 45, !7, i64 48, !7, i64 56, !10, i64 64}
!7 = !{!"any pointer", !8, i64 0}
!8 = !{!"omnipotent char", !9, i64 0}
!9 = !{!"Simple C/C++ TBAA"}
!10 = !{!"long", !8, i64 0}
!11 = !{!"_Bool", !8, i64 0}
!12 = !{!6, !7, i64 0}
!13 = !{!6, !10, i64 8}
!14 = !{!6, !11, i64 40}
!15 = !{i8 0, i8 2}
!16 = !{}
!17 = !{!6, !11, i64 42}
!18 = !{!6, !11, i64 44}
!19 = !{!8, !8, i64 0}
!20 = !{!21, !21, i64 0}
!21 = !{!"int", !8, i64 0}
!22 = !{!6, !11, i64 45}
!23 = distinct !{!23, !24}
!24 = !{!"llvm.loop.mustprogress"}
!25 = !{!7, !7, i64 0}


; Effective O3 passes: CorrelatedValuePropagationPass,EarlyCSEPass,GVNPass,GlobalOptPass,IPSCCPPass,InferFunctionAttrsPass,InstCombinePass,InstSimplifyPass,JumpThreadingPass,LCSSAPass,LICMPass,LoopInstSimplifyPass,LoopRotatePass,LoopSimplifyCFGPass,LoopSimplifyPass,LoopUnrollPass,PostOrderFunctionAttrsPass,ReassociatePass,SROAPass,SimplifyCFGPass,TailCallElimPass