Index: lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- lib/Transforms/Scalar/LoopDeletion.cpp +++ lib/Transforms/Scalar/LoopDeletion.cpp @@ -29,6 +29,24 @@ STATISTIC(NumDeleted, "Number of loops deleted"); +/// This function deletes dead loops. The caller of this function needs to +/// guarantee that the loop is infact dead. +/// Here we handle two kinds of dead loop. The first kind is where no backedges exist, and +/// the loop variant statements are made invariant by moving to the preheader. +/// The second kind is where the loop is no longer a loop in LLVM notion, since +/// the loop is semantically unreachable (see `IsLoopSemanticallyUnreachable`). +/// We can be more aggressive in removing the semantically unreachable loops +/// since they will not cause any difference to program behaviour (observable or +/// unobservable). +/// +/// This also updates the relevant analysis information in \p DT, \p SE, and \p +/// LI. It also updates the loop PM if an updater struct is provided. +// TODO: This function will be used by loop-simplifyCFG as well. So, move this +// to LoopUtils.cpp +static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE, + LoopInfo &LI, + bool LoopIsSemanticallyUnreachable, + LPMUpdater *Updater = nullptr); /// Determines if a loop is dead. /// /// This assumes that we've already checked for unique exit and exiting blocks, @@ -84,12 +102,56 @@ return true; } +/// In LLVM, a loop can never be unreachable i.e. it's header would +/// always have atleast one predecessor. However, in cases where the loop +/// header would never be executed at runtime, we consider such loops as +/// semantically unreachable. This function returns true when loop `L` is +/// semantically unreachable. For example, loop L2 is unreachable in +/// the following IR: +/// L1: ... +/// br i1 true, label L1, label L2 +/// L2: ... ; predecessors: L1, B3 +/// br label B3 +/// B3: ... ; predecessors: L2 +/// br label L2 +static bool isLoopSemanticallyUnreachable(Loop *L) { + + auto *Preheader = L->getLoopPreheader(); + + // Get a block `HeaderPred` that is the single predecessor of the loop header/preheader. + // `HeaderPred` can have more than one successor (but will have exactly one + // successor at runtime, i.e. its terminator is a constant conditional + // branch). We do not stop at Preheader for precisely this reason, it will + // unconditionally branch to the header of the loop. + auto *HeaderPred = + Preheader ? Preheader->getSinglePredecessor() : L->getLoopPredecessor(); + auto *FirstLoopBlock = Preheader ? Preheader : L->getHeader(); + if (!HeaderPred) + return false; + // Note: We could keep iterating backwards over the singlePredecessors + // (straight line code) until we reach a block that satisfies the constraint + // of constant conditional branch. We avoid doing this now, because + // Loop-SimplifyCFG will be enhanced to change branches in loop from constant + // conditional to unconditional, thereby iterating forward across the straight + // line code. + TerminatorInst *T = HeaderPred->getTerminator(); + auto *BI = dyn_cast(T); + if (!BI || BI->isUnconditional()) + return false; + ConstantInt *Cond = dyn_cast(BI->getCondition()); + if (!Cond) + return false; + BasicBlock *NotTaken = + Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0); + return (NotTaken == FirstLoopBlock); +} + /// Remove a loop if it is dead. /// /// A loop is considered dead if it does not impact the observable behavior of /// the program other than finite running time. This never removes a loop that -/// might be infinite, as doing so could change the halting/non-halting nature -/// of a program. +/// might be infinite (unless it is semantically unreachable), as doing so +/// could change the halting/non-halting nature of a program. /// /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in /// order to make various safety checks work. @@ -97,28 +159,43 @@ /// \returns true if any changes were made. This may mutate the loop even if it /// is unable to delete it due to hoisting trivially loop invariant /// instructions out of the loop. -/// -/// This also updates the relevant analysis information in \p DT, \p SE, and \p -/// LI. It also updates the loop PM if an updater struct is provided. static bool deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, LPMUpdater *Updater = nullptr) { assert(L->isLCSSAForm(DT) && "Expected LCSSA!"); - // We can only remove the loop if there is a preheader that we can - // branch from after removing it. - BasicBlock *Preheader = L->getLoopPreheader(); - if (!Preheader) + + // We can't remove loops that contain subloops. If the subloops were dead, + // they would already have been removed in earlier executions of this pass. + if (L->begin() != L->end()) return false; // If LoopSimplify form is not available, stay out of trouble. if (!L->hasDedicatedExits()) return false; - // We can't remove loops that contain subloops. If the subloops were dead, - // they would already have been removed in earlier executions of this pass. - if (L->begin() != L->end()) + BasicBlock *ExitBlock = L->getUniqueExitBlock(); + + // When the loop is semantically unreachable, we do not care if it is an + // infinite loop, has multiple exits, or subloops (entirely contained in this + // loop). For now, we handle possibly infinite loops and loops with single exit. + if (ExitBlock && isLoopSemanticallyUnreachable(L)) { + deleteDeadLoop(L, DT, SE, LI, + /*LoopIsSemanticallyUnreachable*/ true, Updater); + ++NumDeleted; + return true; + } + + // The loop is not semantically unreachable. Check for the second case of a + // dead loop, i.e. where the loop has no backedge, and all statements in the + // loop are invariant. This is a non-loop if we can move all statements within + // the loop to the preheader. + // We can only remove the loop if there is a preheader that we can + // branch from after removing it. + BasicBlock *Preheader = L->getLoopPreheader(); + if (!Preheader) return false; + SmallVector ExitingBlocks; L->getExitingBlocks(ExitingBlocks); @@ -126,7 +203,6 @@ // be in the situation of needing to be able to solve statically which exit // block will be branched to, or trying to preserve the branching logic in // a loop invariant manner. - BasicBlock *ExitBlock = L->getUniqueExitBlock(); if (!ExitBlock) return false; @@ -141,6 +217,28 @@ if (isa(S)) return Changed; + deleteDeadLoop(L, DT, SE, LI, false /*LoopIsSemanticallyUnreachable*/, Updater); + ++NumDeleted; + + return true; +} + +static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE, + LoopInfo &LI, bool LoopIsSemanticallyUnreachable, + LPMUpdater *Updater) { + assert(L->isLCSSAForm(DT) && "Expected LCSSA!"); + auto *Preheader = L->getLoopPreheader(); + assert((Preheader || LoopIsSemanticallyUnreachable) && + "Preheader should exist if loop is reachable!"); + BasicBlock *BlockCausingLoopUnreachable = nullptr; + // We already proved that the loop is unreachable. Get the block that makes + // the loop unreachable. If the preheader does not exist, this will be the + // source block which will be directly connected to the exit block of the + // loop. + if (LoopIsSemanticallyUnreachable) + BlockCausingLoopUnreachable = + Preheader ? Preheader->getSinglePredecessor() : L->getLoopPredecessor(); + // Now that we know the removal is safe, remove the loop by changing the // branch from the preheader to go to the single exit block. // @@ -156,18 +254,33 @@ // to determine what it needs to clean up. SE.forgetLoop(L); - // Connect the preheader directly to the exit block. - TerminatorInst *TI = Preheader->getTerminator(); - TI->replaceUsesOfWith(L->getHeader(), ExitBlock); + auto *ExitBlock = L->getUniqueExitBlock(); + assert(ExitBlock && "Should have a unique exit block!"); + // All the branch changes, phi node updates at the exit block and dom tree + // updates should be done with this node as the source. + auto *SourceBB = Preheader ? Preheader : BlockCausingLoopUnreachable; + assert(SourceBB && "the source basic block into the loop should exist!"); + + // Connect the source block that exists outside the loop, directly to + // the exit block. + SourceBB->getTerminator()->replaceUsesOfWith(L->getHeader(), ExitBlock); - // Rewrite phis in the exit block to get their inputs from - // the preheader instead of the exiting block. + SmallVector ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + // When the loop is dead because the backedge is removed, rewrite phis in the + // exit block to get their inputs from the SourceBB instead of the exiting + // block. BasicBlock *ExitingBlock = ExitingBlocks[0]; BasicBlock::iterator BI = ExitBlock->begin(); while (PHINode *P = dyn_cast(BI)) { int j = P->getBasicBlockIndex(ExitingBlock); assert(j >= 0 && "Can't find exiting block in exit block's phi node!"); - P->setIncomingBlock(j, Preheader); + // We set it to the undef value instead of removing the incoming value to + // avoid dealing with dead phi's, which may make the corresponding block + // dead. + if (LoopIsSemanticallyUnreachable) + P->setIncomingValue(j, UndefValue::get(P->getType())); + P->setIncomingBlock(j, SourceBB); for (unsigned i = 1; i < ExitingBlocks.size(); ++i) P->removeIncomingValue(ExitingBlocks[i]); ++BI; @@ -178,11 +291,11 @@ SmallVector ChildNodes; for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); LI != LE; ++LI) { - // Move all of the block's children to be children of the Preheader, which + // Move all of the block's children to be children of the SourceBB, which // allows us to remove the domtree entry for the block. ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end()); for (DomTreeNode *ChildNode : ChildNodes) { - DT.changeImmediateDominator(ChildNode, DT[Preheader]); + DT.changeImmediateDominator(ChildNode, DT[SourceBB]); } ChildNodes.clear(); @@ -211,11 +324,7 @@ // The last step is to update LoopInfo now that we've eliminated this loop. LI.markAsRemoved(L); - ++NumDeleted; - - return true; } - PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { Index: test/Transforms/LoopDeletion/unreachable-loops.ll =================================================================== --- /dev/null +++ test/Transforms/LoopDeletion/unreachable-loops.ll @@ -0,0 +1,143 @@ +; RUN: opt < %s -loop-deletion -S | FileCheck %s +; RUN: opt < %s -loop-deletion -verify-dom-info -S + +; Checking that we can delete loops that are deemed semantically unreachable. +; We do not change the constant conditional branch statement (where the not-taken target +; is the loop) to an unconditional one. This will be done as an enhancement to +; loop-simplfycfg. + +; delete the infinite loop because it is semantically unreachable. +define void @test1(i64 %n, i64 %m) nounwind { +; CHECK-LABEL: test1 +; CHECK-LABEL: entry: +; CHECK-NEXT: br i1 true, label %return, label %bb.preheader +; CHECK-NOT: bb: +entry: + br i1 true, label %return, label %bb + +bb: + %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ] + %t0 = add i64 %x.0, 1 + %t1 = icmp slt i64 %x.0, %n + %t3 = icmp sgt i64 %x.0, %m + %t4 = and i1 %t1, %t3 + br i1 true, label %bb, label %return + +return: + ret void +} + +; FIXME: We can delete this infinite loop. Currently we do not, +; because the infinite loop has no exit block. +define void @test2(i64 %n, i64 %m) nounwind { +; CHECK-LABEL: test2 +; CHECK-LABEL: entry: +; CHECK-NEXT: br i1 true, label %return, label %bb.preheader +; CHECK-LABEL: bb: +; CHECK: br label %bb +entry: + br i1 true, label %return, label %bb + +bb: + %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ] + %t0 = add i64 %x.0, 1 + %t1 = icmp slt i64 %x.0, %n + %t3 = icmp sgt i64 %x.0, %m + %t4 = and i1 %t1, %t3 + br label %bb + +return: + ret void +} + +; There are multiple exiting blocks and a single exit block. +; Since it is a semantically unreachable loop, we do not care about the values +; from different exiting paths and we can +; delete the loop. +define i64 @test3(i64 %n, i64 %m, i64 %maybe_zero) nounwind { + +; CHECK-NOT: bb: +; CHECK-NOT: bb2: +; CHECK-NOT: bb3: +; CHECK-LABEL: return.loopexit: +; CHECK-NEXT: %x.lcssa.ph = phi i64 [ undef, %bb.preheader ] +; CHECK-NEXT: br label %return +; CHECK-LABEL: return: +; CHECK-NEXT: %x.lcssa = phi i64 [ 20, %entry ], [ %x.lcssa.ph, %return.loopexit ] +; CHECK-NEXT: ret i64 %x.lcssa +entry: + br i1 false, label %bb, label %return + +bb: + %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb3 ] + %t0 = add i64 %x.0, 1 + %t1 = icmp slt i64 %x.0, %n + br i1 %t1, label %bb2, label %return + +bb2: + %t2 = icmp slt i64 %x.0, %m + %unused1 = udiv i64 42, %maybe_zero + br i1 %t2, label %bb3, label %return + +bb3: + %t3 = icmp slt i64 %x.0, %m + %unused2 = sdiv i64 42, %maybe_zero + br i1 %t3, label %bb, label %return + +return: +; the only valid value fo x.lcssa is 20. + %x.lcssa = phi i64 [ 12, %bb ], [ 14, %bb2 ], [ 16, %bb3 ], [20, %entry ] + ret i64 %x.lcssa +} + +; Cannot delete the loop, since it may be executed at runtime. +define void @test4(i64 %n, i64 %m, i1 %cond) { +; CHECK-LABEL: test4 +; CHECK-LABEL: bb: +entry: + br i1 %cond, label %looppred1, label %looppred2 + +looppred1: + br i1 true, label %return, label %bb + +looppred2: + br i1 false, label %return, label %bb + +bb: + %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ] + %t0 = add i64 %x.0, 1 + %t1 = icmp slt i64 %x.0, %n + %t3 = icmp sgt i64 %x.0, %m + %t4 = and i1 %t1, %t3 + br i1 true, label %bb, label %return + +return: + ret void +} + +; FIXME: multiple constant conditional branches with loop not-taken in test1. +; Currently, we do not delete the loop. This will be handled as an enhancement +; when loop-simplifyCFG and loop-deletion is merged. +define void @test5(i64 %n, i64 %m, i1 %cond) nounwind { +; CHECK-LABEL: test5 +; CHECK-LABEL: bb: +entry: + br i1 %cond, label %looppred1, label %looppred2 + +looppred1: + br i1 true, label %return, label %bb + +looppred2: + br i1 true, label %return, label %bb + +bb: + %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ] + %t0 = add i64 %x.0, 1 + %t1 = icmp slt i64 %x.0, %n + %t3 = icmp sgt i64 %x.0, %m + %t4 = and i1 %t1, %t3 + br i1 true, label %bb, label %return + +return: + ret void +}