Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -1452,18 +1452,67 @@ assert(BI1->isUnconditional()); BasicBlock *BBEnd = BI1->getSuccessor(0); - // We currently only support branch targets with two predecessors. - // FIXME: this is an arbitrary restriction and should be lifted. - SmallVector Blocks; - for (auto *BB : predecessors(BBEnd)) - Blocks.push_back(BB); - if (Blocks.size() != 2 || - !all_of(Blocks, [](const BasicBlock *BB) { - auto *BI = dyn_cast(BB->getTerminator()); - return BI && BI->isUnconditional(); - })) + // We support two situations: + // (1) all incoming arcs are unconditional + // (2) one incoming arc is conditional + // + // (2) is very common in switch defaults and + // else-if patterns; + // + // if (a) x(1); + // else if (b) x(2); + // + // produces: + // + // [if] + // / \ + // [x(1)] [if] + // | | \ + // | | \ + // | [x(2)]| + // \ | / + // [ end ] + // + // [end] has two unconditional predecessor arcs and one conditional. The + // conditional refers to the implicit empty 'else' arc. This conditional + // arc can also be caused by an empty default block in a switch. + // + // In this case, we attempt to sink code from all *unconditional* arcs. + // If we can sink instructions from these arcs (determined during the scan + // phase below) we insert a common successor for all unconditional arcs and + // connect that to [end], to enable sinking: + // + // [if] + // / \ + // [x(1)] [if] + // | | \ + // | | \ + // | [x(2)] | + // \ / | + // [sink.split] | + // \ / + // [ end ] + // + SmallVector Blocks, AllBlocks; + Instruction *Cond = nullptr; + for (auto *B : predecessors(BBEnd)) { + AllBlocks.push_back(B); + auto *T = B->getTerminator(); + if (isa(T) && cast(T)->isUnconditional()) { + Blocks.push_back(B); + continue; + } + if (isa(T) || isa(T)) { + if (Cond) + return false; + Cond = T; + continue; + } return false; - + } + if (Blocks.size() < 2) + return false; + bool Changed = false; SmallVector Insts; @@ -1495,11 +1544,23 @@ SmallVector ThisValuesNeedingPHIs; while (PopulateInsts(ScanIdx) && canSinkInstruction(Insts, ThisValuesNeedingPHIs)) { + DEBUG(dbgs() << "SINK: instruction can be sunk: " << *Insts[0] << " - " + << ThisValuesNeedingPHIs.size() << " phis needed\n"); ValuesNeedingPHIs.push_back(ThisValuesNeedingPHIs); ValuesToSink.insert(Insts.begin(), Insts.end()); ++ScanIdx; } + if (ScanIdx > 0 && Cond) { + DEBUG(dbgs() << "SINK: Splitting edge\n"); + // We have a conditional edge and we're going to sink some instructions. + // Insert a new block postdominating all blocks we're going to sink from. + if (!SplitBlockPredecessors(BI1->getSuccessor(0), Blocks, ".sink.split")) + // Edges couldn't be split. + return false; + Changed = true; + } + // Now that we've analyzed all potential sinking candidates, perform the // actual sink. We iteratively sink the last non-terminator of the source // blocks into their common successor unless doing so would require too @@ -1513,22 +1574,26 @@ // and never actually sink it which means we produce more PHIs than intended. // This is unlikely in practice though. for (unsigned SinkIdx = 0; SinkIdx != ScanIdx; ++SinkIdx) { + DEBUG(dbgs() << "SINK: Sink: " << *Blocks[0]->getTerminator()->getPrevNode() + << "\n"); unsigned NumPHIdValues = 0; for (auto *V : ValuesNeedingPHIs[SinkIdx]) if (ValuesToSink.count(V) == 0) ++NumPHIdValues; + DEBUG(dbgs() << "SINK: #phid values: " << NumPHIdValues << "\n"); assert((NumPHIdValues % Blocks.size() == 0) && "Every operand must either be PHId or not PHId!"); - if (NumPHIdValues / Blocks.size() > 1) + if (NumPHIdValues / Blocks.size() > 1) { // Too many PHIs would be created. + DEBUG(dbgs() << "SINK: stopping here, too many PHIs would be created!\n"); break; + } sinkLastInstruction(Blocks); NumSinkCommons++; Changed = true; } - return Changed; } Index: test/Transforms/SimplifyCFG/sink-common-code.ll =================================================================== --- test/Transforms/SimplifyCFG/sink-common-code.ll +++ test/Transforms/SimplifyCFG/sink-common-code.ll @@ -393,3 +393,113 @@ ; CHECK: getelementptr ; CHECK: load ; CHECK-NOT: load + +define zeroext i1 @test16(i1 zeroext %flag, i1 zeroext %flag2, i32 %blksA, i32 %blksB, i32 %nblks) { +entry: + br i1 %flag, label %if.then, label %if.else + +if.then: + %cmp = icmp uge i32 %blksA, %nblks + %frombool1 = zext i1 %cmp to i8 + br label %if.end + +if.else: + br i1 %flag2, label %if.then2, label %if.end + +if.then2: + %add = add i32 %nblks, %blksB + %cmp2 = icmp ule i32 %add, %blksA + %frombool3 = zext i1 %cmp2 to i8 + br label %if.end + +if.end: + %obeys.0 = phi i8 [ %frombool1, %if.then ], [ %frombool3, %if.then2 ], [ 0, %if.else ] + %tobool4 = icmp ne i8 %obeys.0, 0 + ret i1 %tobool4 +} + +; CHECK-LABEL: test16 +; CHECK: zext +; CHECK-NOT: zext + +define zeroext i1 @test17(i32 %flag, i32 %blksA, i32 %blksB, i32 %nblks) { +entry: + switch i32 %flag, label %if.end [ + i32 0, label %if.then + i32 1, label %if.then2 + ] + +if.then: + %cmp = icmp uge i32 %blksA, %nblks + %frombool1 = zext i1 %cmp to i8 + br label %if.end + +if.then2: + %add = add i32 %nblks, %blksB + %cmp2 = icmp ule i32 %add, %blksA + %frombool3 = zext i1 %cmp2 to i8 + br label %if.end + +if.end: + %obeys.0 = phi i8 [ %frombool1, %if.then ], [ %frombool3, %if.then2 ], [ 0, %entry ] + %tobool4 = icmp ne i8 %obeys.0, 0 + ret i1 %tobool4 +} + +; CHECK-LABEL: test17 +; CHECK: if.then: +; CHECK-NEXT: icmp uge +; CHECK-NEXT: br label %[[x:.*]] + +; CHECK: if.then2: +; CHECK-NEXT: add +; CHECK-NEXT: icmp ule +; CHECK-NEXT: br label %[[x]] + +; CHECK: [[x]]: +; CHECK-NEXT: %[[y:.*]] = phi i1 [ %cmp +; CHECK-NEXT: %[[z:.*]] = zext i1 %[[y]] +; CHECK-NEXT: br label %if.end + +; CHECK: if.end: +; CHECK-NEXT: phi i8 +; CHECK-DAG: [ %[[z]], %[[x]] ] +; CHECK-DAG: [ 0, %entry ] + +define zeroext i1 @test18(i32 %flag, i32 %blksA, i32 %blksB, i32 %nblks) { +entry: + switch i32 %flag, label %if.then3 [ + i32 0, label %if.then + i32 1, label %if.then2 + ] + +if.then: + %cmp = icmp uge i32 %blksA, %nblks + %frombool1 = zext i1 %cmp to i8 + br label %if.end + +if.then2: + %add = add i32 %nblks, %blksB + %cmp2 = icmp ule i32 %add, %blksA + %frombool3 = zext i1 %cmp2 to i8 + br label %if.end + +if.then3: + %add2 = add i32 %nblks, %blksA + %cmp3 = icmp ule i32 %add2, %blksA + %frombool4 = zext i1 %cmp3 to i8 + br label %if.end + +if.end: + %obeys.0 = phi i8 [ %frombool1, %if.then ], [ %frombool3, %if.then2 ], [ %frombool4, %if.then3 ] + %tobool4 = icmp ne i8 %obeys.0, 0 + ret i1 %tobool4 +} + +; CHECK-LABEL: test18 +; CHECK: if.end: +; CHECK-NEXT: %[[x:.*]] = phi i1 +; CHECK-DAG: [ %cmp, %if.then ] +; CHECK-DAG: [ %cmp2, %if.then2 ] +; CHECK-DAG: [ %cmp3, %if.then3 ] +; CHECK-NEXT: zext i1 %[[x]] to i8