LLVM: lib/Transforms/Utils/LoopUnrollRuntime.cpp File Reference (original) (raw)

Go to the source code of this file.

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-unroll"

◆ canProfitablyRuntimeUnrollMultiExitLoop()

◆ CloneLoopBlocks()

Create a clone of the blocks in a loop and connect them together.

A new loop will be created including all cloned blocks, and the iterator of the new loop switched to count NewIter down to 0. The cloned blocks should be inserted between InsertTop and InsertBot. InsertTop should be new preheader, InsertBot new loop exit. Returns the new cloned loop that is created.

Definition at line 405 of file LoopUnrollRuntime.cpp.

References llvm::addClonedBlockToLoopInfo(), llvm::PHINode::addIncoming(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), assert(), llvm::cast(), llvm::CloneBasicBlock(), llvm::Count, llvm::PHINode::Create(), llvm::MDBuilder::createBranchWeights(), llvm::ValueMap< KeyT, ValueT, Config >::erase(), llvm::Instruction::eraseFromParent(), F, llvm::PHINode::getBasicBlockIndex(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::BranchProbability::getBranchProbability(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::PHINode::getIncomingValue(), llvm::Value::getName(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::BranchProbability::getOne(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::hasBranchWeightMD(), I, llvm::Instruction::insertBefore(), llvm::isa(), llvm::BranchProbability::isUnknown(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), N, probOfNextInRemainder(), llvm::setBranchProbability(), llvm::PHINode::setIncomingBlock(), llvm::PHINode::setIncomingValue(), llvm::Loop::setLoopAlreadyUnrolled(), llvm::setLoopEstimatedTripCount(), llvm::Instruction::setSuccessor(), and llvm::BranchProbability::toDouble().

Referenced by llvm::UnrollRuntimeLoopRemainder().

◆ ConnectEpilog()

Connect the unrolling epilog code to the original loop.

The unrolling epilog code contains code to execute the 'extra' iterations if the run-time trip count modulo the unroll count is non-zero.

This function performs the following:

• Update PHI nodes at the epilog loop exit
• Create PHI nodes at the unrolling loop exit and epilog preheader to combine values that exit the unrolling loop code and jump around it.
• Update PHI operands in the epilog loop by the new PHI nodes
• At the unrolling loop exit, branch around the epilog loop if extra iters
• At the epilog preheader, add an llvm.assume call that extra iters is non-zero. If the unrolling loop exit is the predecessor, the above new branch guarantees that assumption. If the unrolling loop preheader is the predecessor, then the required first iteration from the original loop has yet to be executed, so it must be executed in the epilog loop. If we later unroll the epilog loop, that llvm.assume call somehow enables ScalarEvolution to compute a epilog loop maximum trip count, which enables eliminating the branch at the end of the final unrolled epilog iteration.

Definition at line 256 of file LoopUnrollRuntime.cpp.

References llvm::PHINode::addIncoming(), assert(), B(), llvm::cast(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::Count, llvm::PHINode::Create(), llvm::IRBuilderBase::CreateAssumption(), llvm::MDBuilder::createBranchWeights(), llvm::IRBuilderBase::CreateIsNotNull(), llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::DominatorTree::findNearestCommonDominator(), llvm::PHINode::getBasicBlockIndex(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), llvm::hasBranchWeightMD(), I, llvm::Instruction::insertBefore(), llvm::BranchProbability::isUnknown(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::BasicBlock::phis(), llvm::predecessors(), probOfNextInRemainder(), llvm::AssumptionCache::registerAssumption(), llvm::setBranchProbability(), llvm::PHINode::setIncomingBlock(), llvm::PHINode::setIncomingValueForBlock(), llvm::SplitBlockPredecessors(), and llvm::successors().

Referenced by llvm::UnrollRuntimeLoopRemainder().

◆ ConnectProlog()

Connect the unrolling prolog code to the original loop.

The unrolling prolog code contains code to execute the 'extra' iterations if the run-time trip count modulo the unroll count is non-zero.

This function performs the following:

• Create PHI nodes at prolog end block to combine values that exit the prolog code and jump around the prolog.
• Add a PHI operand to a PHI node at the loop exit block for values that exit the prolog and go around the loop.
• Branch around the original loop if the trip count is less than the unroll factor.

Definition at line 83 of file LoopUnrollRuntime.cpp.

References llvm::PHINode::addIncoming(), assert(), B(), llvm::cast(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::Count, llvm::PHINode::Create(), llvm::MDBuilder::createBranchWeights(), llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::DominatorTree::findNearestCommonDominator(), llvm::ScalarEvolution::forgetLcssaPhiWithNewPredecessor(), llvm::PoisonValue::get(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::hasBranchWeightMD(), I, llvm::Instruction::insertBefore(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SplitBlockPredecessors(), llvm::successors(), and UnrolledLoopHeaderWeights.

Referenced by llvm::UnrollRuntimeLoopRemainder().

◆ CreateTripRemainder()

◆ probOfNextInRemainder()

◆ STATISTIC()

◆ EpilogHeaderWeights

◆ UnrolledLoopHeaderWeights

◆ UnrollRuntimeMultiExit

◆ UnrollRuntimeOtherExitPredictable