331 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 42; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s3 4define i32 @test1_factorial(i32 %x) {5; CHECK-LABEL: define i32 @test1_factorial(6; CHECK-SAME: i32 [[X:%.*]]) {7; CHECK-NEXT: entry:8; CHECK-NEXT: br label [[TAILRECURSE:%.*]]9; CHECK: tailrecurse:10; CHECK-NEXT: [[ACCUMULATOR_TR:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[THEN:%.*]] ]11; CHECK-NEXT: [[X_TR:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP_6:%.*]], [[THEN]] ]12; CHECK-NEXT: [[TMP_1:%.*]] = icmp sgt i32 [[X_TR]], 013; CHECK-NEXT: br i1 [[TMP_1]], label [[THEN]], label [[ELSE:%.*]]14; CHECK: then:15; CHECK-NEXT: [[TMP_6]] = add i32 [[X_TR]], -116; CHECK-NEXT: [[ACCUMULATE]] = mul i32 [[ACCUMULATOR_TR]], [[X_TR]]17; CHECK-NEXT: br label [[TAILRECURSE]]18; CHECK: else:19; CHECK-NEXT: [[ACCUMULATOR_RET_TR:%.*]] = mul i32 [[ACCUMULATOR_TR]], 120; CHECK-NEXT: ret i32 [[ACCUMULATOR_RET_TR]]21;22entry:23 %tmp.1 = icmp sgt i32 %x, 024 br i1 %tmp.1, label %then, label %else25then:26 %tmp.6 = add i32 %x, -127 %recurse = call i32 @test1_factorial( i32 %tmp.6 )28 %accumulate = mul i32 %recurse, %x29 ret i32 %accumulate30else:31 ret i32 132}33 34; This is a more aggressive form of accumulator recursion insertion, which35; requires noticing that X doesn't change as we perform the tailcall.36 37define i32 @test2_mul(i32 %x, i32 %y) {38; CHECK-LABEL: define i32 @test2_mul(39; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {40; CHECK-NEXT: entry:41; CHECK-NEXT: br label [[TAILRECURSE:%.*]]42; CHECK: tailrecurse:43; CHECK-NEXT: [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[ENDIF:%.*]] ]44; CHECK-NEXT: [[Y_TR:%.*]] = phi i32 [ [[Y]], [[ENTRY]] ], [ [[TMP_8:%.*]], [[ENDIF]] ]45; CHECK-NEXT: [[TMP_1:%.*]] = icmp eq i32 [[Y_TR]], 046; CHECK-NEXT: br i1 [[TMP_1]], label [[RETURN:%.*]], label [[ENDIF]]47; CHECK: endif:48; CHECK-NEXT: [[TMP_8]] = add i32 [[Y_TR]], -149; CHECK-NEXT: [[ACCUMULATE]] = add i32 [[ACCUMULATOR_TR]], [[X]]50; CHECK-NEXT: br label [[TAILRECURSE]]51; CHECK: return:52; CHECK-NEXT: [[ACCUMULATOR_RET_TR:%.*]] = add i32 [[ACCUMULATOR_TR]], [[X]]53; CHECK-NEXT: ret i32 [[ACCUMULATOR_RET_TR]]54;55entry:56 %tmp.1 = icmp eq i32 %y, 057 br i1 %tmp.1, label %return, label %endif58endif:59 %tmp.8 = add i32 %y, -160 %recurse = call i32 @test2_mul( i32 %x, i32 %tmp.8 )61 %accumulate = add i32 %recurse, %x62 ret i32 %accumulate63return:64 ret i32 %x65}66 67define i64 @test3_fib(i64 %n) nounwind readnone {68; CHECK-LABEL: define i64 @test3_fib(69; CHECK-SAME: i64 [[N:%.*]]) #[[ATTR0:[0-9]+]] {70; CHECK-NEXT: entry:71; CHECK-NEXT: br label [[TAILRECURSE:%.*]]72; CHECK: tailrecurse:73; CHECK-NEXT: [[ACCUMULATOR_TR:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[BB1:%.*]] ]74; CHECK-NEXT: [[N_TR:%.*]] = phi i64 [ [[N]], [[ENTRY]] ], [ [[TMP1:%.*]], [[BB1]] ]75; CHECK-NEXT: switch i64 [[N_TR]], label [[BB1]] [76; CHECK-NEXT: i64 0, label [[BB2:%.*]]77; CHECK-NEXT: i64 1, label [[BB2]]78; CHECK-NEXT: ]79; CHECK: bb1:80; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[N_TR]], -181; CHECK-NEXT: [[RECURSE1:%.*]] = tail call i64 @test3_fib(i64 [[TMP0]]) #[[ATTR2:[0-9]+]]82; CHECK-NEXT: [[TMP1]] = add i64 [[N_TR]], -283; CHECK-NEXT: [[ACCUMULATE]] = add nsw i64 [[ACCUMULATOR_TR]], [[RECURSE1]]84; CHECK-NEXT: br label [[TAILRECURSE]]85; CHECK: bb2:86; CHECK-NEXT: [[ACCUMULATOR_RET_TR:%.*]] = add nsw i64 [[ACCUMULATOR_TR]], [[N_TR]]87; CHECK-NEXT: ret i64 [[ACCUMULATOR_RET_TR]]88;89entry:90 switch i64 %n, label %bb1 [91 i64 0, label %bb292 i64 1, label %bb293 ]94 95bb1:96 %0 = add i64 %n, -197 %recurse1 = tail call i64 @test3_fib(i64 %0) nounwind98 %1 = add i64 %n, -299 %recurse2 = tail call i64 @test3_fib(i64 %1) nounwind100 %accumulate = add nsw i64 %recurse2, %recurse1101 ret i64 %accumulate102 103bb2:104 ret i64 %n105}106 107define i32 @test4_base_case_call() local_unnamed_addr {108; CHECK-LABEL: define i32 @test4_base_case_call() local_unnamed_addr {109; CHECK-NEXT: entry:110; CHECK-NEXT: br label [[TAILRECURSE:%.*]]111; CHECK: tailrecurse:112; CHECK-NEXT: [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[SW_DEFAULT:%.*]] ]113; CHECK-NEXT: [[BASE:%.*]] = tail call i32 @test4_helper()114; CHECK-NEXT: switch i32 [[BASE]], label [[SW_DEFAULT]] [115; CHECK-NEXT: i32 1, label [[CLEANUP:%.*]]116; CHECK-NEXT: i32 5, label [[CLEANUP]]117; CHECK-NEXT: i32 7, label [[CLEANUP]]118; CHECK-NEXT: ]119; CHECK: sw.default:120; CHECK-NEXT: [[ACCUMULATE]] = add nsw i32 [[ACCUMULATOR_TR]], 1121; CHECK-NEXT: br label [[TAILRECURSE]]122; CHECK: cleanup:123; CHECK-NEXT: [[ACCUMULATOR_RET_TR:%.*]] = add nsw i32 [[ACCUMULATOR_TR]], [[BASE]]124; CHECK-NEXT: ret i32 [[ACCUMULATOR_RET_TR]]125;126entry:127 %base = call i32 @test4_helper()128 switch i32 %base, label %sw.default [129 i32 1, label %cleanup130 i32 5, label %cleanup131 i32 7, label %cleanup132 ]133 134sw.default:135 %recurse = call i32 @test4_base_case_call()136 %accumulate = add nsw i32 %recurse, 1137 br label %cleanup138 139cleanup:140 %retval.0 = phi i32 [ %accumulate, %sw.default ], [ %base, %entry ], [ %base, %entry ], [ %base, %entry ]141 ret i32 %retval.0142}143 144declare i32 @test4_helper()145 146define i32 @test5_base_case_load(ptr nocapture %A, i32 %n) local_unnamed_addr {147; CHECK-LABEL: define i32 @test5_base_case_load(148; CHECK-SAME: ptr captures(none) [[A:%.*]], i32 [[N:%.*]]) local_unnamed_addr {149; CHECK-NEXT: entry:150; CHECK-NEXT: br label [[TAILRECURSE:%.*]]151; CHECK: tailrecurse:152; CHECK-NEXT: [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[IF_END:%.*]] ]153; CHECK-NEXT: [[N_TR:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SUB:%.*]], [[IF_END]] ]154; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[N_TR]], 0155; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END]]156; CHECK: if.then:157; CHECK-NEXT: [[BASE:%.*]] = load i32, ptr [[A]], align 4158; CHECK-NEXT: [[ACCUMULATOR_RET_TR:%.*]] = add i32 [[ACCUMULATOR_TR]], [[BASE]]159; CHECK-NEXT: ret i32 [[ACCUMULATOR_RET_TR]]160; CHECK: if.end:161; CHECK-NEXT: [[IDXPROM:%.*]] = zext i32 [[N_TR]] to i64162; CHECK-NEXT: [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IDXPROM]]163; CHECK-NEXT: [[LOAD:%.*]] = load i32, ptr [[ARRAYIDX1]], align 4164; CHECK-NEXT: [[SUB]] = add i32 [[N_TR]], -1165; CHECK-NEXT: [[ACCUMULATE]] = add i32 [[ACCUMULATOR_TR]], [[LOAD]]166; CHECK-NEXT: br label [[TAILRECURSE]]167;168entry:169 %cmp = icmp eq i32 %n, 0170 br i1 %cmp, label %if.then, label %if.end171 172if.then:173 %base = load i32, ptr %A, align 4174 ret i32 %base175 176if.end:177 %idxprom = zext i32 %n to i64178 %arrayidx1 = getelementptr inbounds i32, ptr %A, i64 %idxprom179 %load = load i32, ptr %arrayidx1, align 4180 %sub = add i32 %n, -1181 %recurse = tail call i32 @test5_base_case_load(ptr %A, i32 %sub)182 %accumulate = add i32 %recurse, %load183 ret i32 %accumulate184}185 186define i32 @test6_multiple_returns(i32 %x, i32 %y) local_unnamed_addr {187; CHECK-LABEL: define i32 @test6_multiple_returns(188; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) local_unnamed_addr {189; CHECK-NEXT: entry:190; CHECK-NEXT: br label [[TAILRECURSE:%.*]]191; CHECK: tailrecurse:192; CHECK-NEXT: [[ACCUMULATOR_TR:%.*]] = phi i32 [ [[ACCUMULATOR_TR]], [[CASE99:%.*]] ], [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[DEFAULT:%.*]] ]193; CHECK-NEXT: [[X_TR:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[SUB1:%.*]], [[CASE99]] ], [ [[SUB2:%.*]], [[DEFAULT]] ]194; CHECK-NEXT: [[RET_TR:%.*]] = phi i32 [ poison, [[ENTRY]] ], [ [[CURRENT_RET_TR:%.*]], [[CASE99]] ], [ [[RET_TR]], [[DEFAULT]] ]195; CHECK-NEXT: [[RET_KNOWN_TR:%.*]] = phi i1 [ false, [[ENTRY]] ], [ true, [[CASE99]] ], [ [[RET_KNOWN_TR]], [[DEFAULT]] ]196; CHECK-NEXT: switch i32 [[X_TR]], label [[DEFAULT]] [197; CHECK-NEXT: i32 0, label [[CASE0:%.*]]198; CHECK-NEXT: i32 99, label [[CASE99]]199; CHECK-NEXT: ]200; CHECK: case0:201; CHECK-NEXT: [[HELPER:%.*]] = tail call i32 @test6_helper()202; CHECK-NEXT: [[ACCUMULATOR_RET_TR2:%.*]] = add i32 [[ACCUMULATOR_TR]], [[HELPER]]203; CHECK-NEXT: [[CURRENT_RET_TR1:%.*]] = select i1 [[RET_KNOWN_TR]], i32 [[RET_TR]], i32 [[ACCUMULATOR_RET_TR2]]204; CHECK-NEXT: ret i32 [[CURRENT_RET_TR1]]205; CHECK: case99:206; CHECK-NEXT: [[SUB1]] = add i32 [[X_TR]], -1207; CHECK-NEXT: [[ACCUMULATOR_RET_TR:%.*]] = add i32 [[ACCUMULATOR_TR]], 18208; CHECK-NEXT: [[CURRENT_RET_TR]] = select i1 [[RET_KNOWN_TR]], i32 [[RET_TR]], i32 [[ACCUMULATOR_RET_TR]]209; CHECK-NEXT: br label [[TAILRECURSE]]210; CHECK: default:211; CHECK-NEXT: [[SUB2]] = add i32 [[X_TR]], -1212; CHECK-NEXT: [[ACCUMULATE]] = add i32 [[ACCUMULATOR_TR]], [[Y]]213; CHECK-NEXT: br label [[TAILRECURSE]]214;215entry:216 switch i32 %x, label %default [217 i32 0, label %case0218 i32 99, label %case99219 ]220 221case0:222 %helper = call i32 @test6_helper()223 ret i32 %helper224 225case99:226 %sub1 = add i32 %x, -1227 %recurse1 = call i32 @test6_multiple_returns(i32 %sub1, i32 %y)228 ret i32 18229 230default:231 %sub2 = add i32 %x, -1232 %recurse2 = call i32 @test6_multiple_returns(i32 %sub2, i32 %y)233 %accumulate = add i32 %recurse2, %y234 ret i32 %accumulate235}236 237declare i32 @test6_helper()238 239; It is only safe to transform one accumulator per function, make sure we don't240; try to remove more.241 242define i32 @test7_multiple_accumulators(i32 %a) local_unnamed_addr {243; CHECK-LABEL: define i32 @test7_multiple_accumulators(244; CHECK-SAME: i32 [[A:%.*]]) local_unnamed_addr {245; CHECK-NEXT: entry:246; CHECK-NEXT: br label [[TAILRECURSE:%.*]]247; CHECK: tailrecurse:248; CHECK-NEXT: [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE1:%.*]], [[IF_THEN2:%.*]] ]249; CHECK-NEXT: [[A_TR:%.*]] = phi i32 [ [[A]], [[ENTRY]] ], [ [[SUB:%.*]], [[IF_THEN2]] ]250; CHECK-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[A_TR]], 0251; CHECK-NEXT: br i1 [[TOBOOL]], label [[RETURN:%.*]], label [[IF_END:%.*]]252; CHECK: if.end:253; CHECK-NEXT: [[AND:%.*]] = and i32 [[A_TR]], 1254; CHECK-NEXT: [[TOBOOL1:%.*]] = icmp eq i32 [[AND]], 0255; CHECK-NEXT: [[SUB]] = add nsw i32 [[A_TR]], -1256; CHECK-NEXT: br i1 [[TOBOOL1]], label [[IF_END3:%.*]], label [[IF_THEN2]]257; CHECK: if.then2:258; CHECK-NEXT: [[ACCUMULATE1]] = add nsw i32 [[ACCUMULATOR_TR]], 1259; CHECK-NEXT: br label [[TAILRECURSE]]260; CHECK: if.end3:261; CHECK-NEXT: [[RECURSE2:%.*]] = tail call i32 @test7_multiple_accumulators(i32 [[SUB]])262; CHECK-NEXT: [[ACCUMULATE2:%.*]] = mul nsw i32 [[RECURSE2]], 2263; CHECK-NEXT: [[ACCUMULATOR_RET_TR:%.*]] = add nsw i32 [[ACCUMULATOR_TR]], [[ACCUMULATE2]]264; CHECK-NEXT: ret i32 [[ACCUMULATOR_RET_TR]]265; CHECK: return:266; CHECK-NEXT: [[ACCUMULATOR_RET_TR1:%.*]] = add nsw i32 [[ACCUMULATOR_TR]], 0267; CHECK-NEXT: ret i32 [[ACCUMULATOR_RET_TR1]]268;269entry:270 %tobool = icmp eq i32 %a, 0271 br i1 %tobool, label %return, label %if.end272 273if.end:274 %and = and i32 %a, 1275 %tobool1 = icmp eq i32 %and, 0276 %sub = add nsw i32 %a, -1277 br i1 %tobool1, label %if.end3, label %if.then2278 279if.then2:280 %recurse1 = tail call i32 @test7_multiple_accumulators(i32 %sub)281 %accumulate1 = add nsw i32 %recurse1, 1282 br label %return283 284if.end3:285 %recurse2 = tail call i32 @test7_multiple_accumulators(i32 %sub)286 %accumulate2 = mul nsw i32 %recurse2, 2287 br label %return288 289return:290 %retval.0 = phi i32 [ %accumulate1, %if.then2 ], [ %accumulate2, %if.end3 ], [ 0, %entry ]291 ret i32 %retval.0292}293 294%struct.ListNode = type { i32, ptr }295 296; We cannot TRE commutative, non-associative intrinsics297define i32 @test_non_associative_sadd_sat(ptr %a) local_unnamed_addr {298; CHECK-LABEL: define i32 @test_non_associative_sadd_sat(299; CHECK-SAME: ptr [[A:%.*]]) local_unnamed_addr {300; CHECK-NEXT: entry:301; CHECK-NEXT: [[TOBOOL_NOT:%.*]] = icmp eq ptr [[A]], null302; CHECK-NEXT: br i1 [[TOBOOL_NOT]], label [[COMMON_RET6:%.*]], label [[IF_END:%.*]]303; CHECK: common.ret6:304; CHECK-NEXT: ret i32 -1305; CHECK: if.end:306; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[A]], align 4307; CHECK-NEXT: [[NEXT:%.*]] = getelementptr inbounds [[STRUCT_LISTNODE:%.*]], ptr [[A]], i64 0, i32 1308; CHECK-NEXT: [[TMP1:%.*]] = load ptr, ptr [[NEXT]], align 8309; CHECK-NEXT: [[CALL:%.*]] = tail call i32 @test_non_associative_sadd_sat(ptr [[TMP1]])310; CHECK-NEXT: [[DOTSROA_SPECULATED:%.*]] = tail call i32 @llvm.sadd.sat.i32(i32 [[TMP0]], i32 [[CALL]])311; CHECK-NEXT: ret i32 [[DOTSROA_SPECULATED]]312;313entry:314 %tobool.not = icmp eq ptr %a, null315 br i1 %tobool.not, label %common.ret6, label %if.end316 317common.ret6: ; preds = %entry, %if.end318 %common.ret6.op = phi i32 [ %.sroa.speculated, %if.end ], [ -1, %entry ]319 ret i32 %common.ret6.op320 321if.end: ; preds = %entry322 %0 = load i32, ptr %a323 %next = getelementptr inbounds %struct.ListNode, ptr %a, i64 0, i32 1324 %1 = load ptr, ptr %next325 %call = tail call i32 @test_non_associative_sadd_sat(ptr %1)326 %.sroa.speculated = tail call i32 @llvm.sadd.sat.i32(i32 %0, i32 %call)327 br label %common.ret6328}329 330declare i32 @llvm.sadd.sat.i32(i32, i32)331