blob: e22831cd6a9271eee52a43278e1f24a242b593c9 [file] [log] [blame]
//===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
const DenseMap<BasicBlock *, ColorVector> &
LoopSafetyInfo::getBlockColors() const {
return BlockColors;
void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
ColorVector &ColorsForNewBlock = BlockColors[New];
ColorVector &ColorsForOldBlock = BlockColors[Old];
ColorsForNewBlock = ColorsForOldBlock;
bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
return anyBlockMayThrow();
bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
return MayThrow;
void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
assert(CurLoop != nullptr && "CurLoop can't be null");
BasicBlock *Header = CurLoop->getHeader();
// Iterate over header and compute safety info.
HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
MayThrow = HeaderMayThrow;
// Iterate over loop instructions and compute safety info.
// Skip header as it has been computed and stored in HeaderMayThrow.
// The first block in loopinfo.Blocks is guaranteed to be the header.
assert(Header == *CurLoop->getBlocks().begin() &&
"First block must be header");
for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
BBE = CurLoop->block_end();
(BB != BBE) && !MayThrow; ++BB)
MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
return ICF.hasICF(BB);
bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
return MayThrow;
void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
assert(CurLoop != nullptr && "CurLoop can't be null");
MayThrow = false;
// Figure out the fact that at least one block may throw.
for (auto &BB : CurLoop->blocks())
if (ICF.hasICF(&*BB)) {
MayThrow = true;
void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
const BasicBlock *BB) {
ICF.insertInstructionTo(Inst, BB);
MW.insertInstructionTo(Inst, BB);
void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
// Compute funclet colors if we might sink/hoist in a function with a funclet
// personality routine.
Function *Fn = CurLoop->getHeader()->getParent();
if (Fn->hasPersonalityFn())
if (Constant *PersonalityFn = Fn->getPersonalityFn())
if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
BlockColors = colorEHFunclets(*Fn);
/// Return true if we can prove that the given ExitBlock is not reached on the
/// first iteration of the given loop. That is, the backedge of the loop must
/// be executed before the ExitBlock is executed in any dynamic execution trace.
static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
const DominatorTree *DT,
const Loop *CurLoop) {
auto *CondExitBlock = ExitBlock->getSinglePredecessor();
if (!CondExitBlock)
// expect unique exits
return false;
assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
if (!BI || !BI->isConditional())
return false;
// If condition is constant and false leads to ExitBlock then we always
// execute the true branch.
if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
if (!Cond)
return false;
// todo: this would be a lot more powerful if we used scev, but all the
// plumbing is currently missing to pass a pointer in from the pass
// Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
auto *RHS = Cond->getOperand(1);
if (!LHS || LHS->getParent() != CurLoop->getHeader())
return false;
auto DL = ExitBlock->getModule()->getDataLayout();
auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
IVStart, RHS,
{DL, /*TLI*/ nullptr,
DT, /*AC*/ nullptr, BI});
auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
if (!SimpleCst)
return false;
if (ExitBlock == BI->getSuccessor(0))
return SimpleCst->isZeroValue();
assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
return SimpleCst->isAllOnesValue();
/// Collect all blocks from \p CurLoop which lie on all possible paths from
/// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
/// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
static void collectTransitivePredecessors(
const Loop *CurLoop, const BasicBlock *BB,
SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
assert(Predecessors.empty() && "Garbage in predecessors set?");
assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
if (BB == CurLoop->getHeader())
SmallVector<const BasicBlock *, 4> WorkList;
for (auto *Pred : predecessors(BB)) {
while (!WorkList.empty()) {
auto *Pred = WorkList.pop_back_val();
assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
// We are not interested in backedges and we don't want to leave loop.
if (Pred == CurLoop->getHeader())
// TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
// blocks of this inner loop, even those that are always executed AFTER the
// BB. It may make our analysis more conservative than it could be, see test
// @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
// We can ignore backedge of all loops containing BB to get a sligtly more
// optimistic result.
for (auto *PredPred : predecessors(Pred))
if (Predecessors.insert(PredPred).second)
bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
const BasicBlock *BB,
const DominatorTree *DT) const {
assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
// Fast path: header is always reached once the loop is entered.
if (BB == CurLoop->getHeader())
return true;
// Collect all transitive predecessors of BB in the same loop. This set will
// be a subset of the blocks within the loop.
SmallPtrSet<const BasicBlock *, 4> Predecessors;
collectTransitivePredecessors(CurLoop, BB, Predecessors);
// Make sure that all successors of all predecessors of BB are either:
// 1) BB,
// 2) Also predecessors of BB,
// 3) Exit blocks which are not taken on 1st iteration.
// Memoize blocks we've already checked.
SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
for (auto *Pred : Predecessors) {
// Predecessor block may throw, so it has a side exit.
if (blockMayThrow(Pred))
return false;
for (auto *Succ : successors(Pred))
if (CheckedSuccessors.insert(Succ).second &&
Succ != BB && !Predecessors.count(Succ))
// By discharging conditions that are not executed on the 1st iteration,
// we guarantee that *at least* on the first iteration all paths from
// header that *may* execute will lead us to the block of interest. So
// that if we had virtually peeled one iteration away, in this peeled
// iteration the set of predecessors would contain only paths from
// header to BB without any exiting edges that may execute.
// TODO: We only do it for exiting edges currently. We could use the
// same function to skip some of the edges within the loop if we know
// that they will not be taken on the 1st iteration.
// TODO: If we somehow know the number of iterations in loop, the same
// check may be done for any arbitrary N-th iteration as long as N is
// not greater than minimum number of iterations in this loop.
if (CurLoop->contains(Succ) ||
!CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
return false;
// All predecessors can only lead us to BB.
return true;
/// Returns true if the instruction in a loop is guaranteed to execute at least
/// once.
bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
const DominatorTree *DT,
const Loop *CurLoop) const {
// If the instruction is in the header block for the loop (which is very
// common), it is always guaranteed to dominate the exit blocks. Since this
// is a common case, and can save some work, check it now.
if (Inst.getParent() == CurLoop->getHeader())
// If there's a throw in the header block, we can't guarantee we'll reach
// Inst unless we can prove that Inst comes before the potential implicit
// exit. At the moment, we use a (cheap) hack for the common case where
// the instruction of interest is the first one in the block.
return !HeaderMayThrow ||
Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
// If there is a path from header to exit or latch that doesn't lead to our
// instruction's block, return false.
return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
const DominatorTree *DT,
const Loop *CurLoop) const {
return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
const Loop *CurLoop) const {
assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
// Fast path: there are no instructions before header.
if (BB == CurLoop->getHeader())
return true;
// Collect all transitive predecessors of BB in the same loop. This set will
// be a subset of the blocks within the loop.
SmallPtrSet<const BasicBlock *, 4> Predecessors;
collectTransitivePredecessors(CurLoop, BB, Predecessors);
// Find if there any instruction in either predecessor that could write
// to memory.
for (auto *Pred : Predecessors)
if (MW.mayWriteToMemory(Pred))
return false;
return true;
bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
const Loop *CurLoop) const {
auto *BB = I.getParent();
assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
doesNotWriteMemoryBefore(BB, CurLoop);
namespace {
struct MustExecutePrinter : public FunctionPass {
static char ID; // Pass identification, replacement for typeid
MustExecutePrinter() : FunctionPass(ID) {
void getAnalysisUsage(AnalysisUsage &AU) const override {
bool runOnFunction(Function &F) override;
char MustExecutePrinter::ID = 0;
INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
"Instructions which execute on loop entry", false, true)
INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
"Instructions which execute on loop entry", false, true)
FunctionPass *llvm::createMustExecutePrinter() {
return new MustExecutePrinter();
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
// TODO: merge these two routines. For the moment, we display the best
// result obtained by *either* implementation. This is a bit unfair since no
// caller actually gets the full power at the moment.
SimpleLoopSafetyInfo LSI;
return LSI.isGuaranteedToExecute(I, DT, L) ||
isGuaranteedToExecuteForEveryIteration(&I, L);
namespace {
/// An assembly annotator class to print must execute information in
/// comments.
class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
MustExecuteAnnotatedWriter(const Function &F,
DominatorTree &DT, LoopInfo &LI) {
for (auto &I: instructions(F)) {
Loop *L = LI.getLoopFor(I.getParent());
while (L) {
if (isMustExecuteIn(I, L, &DT)) {
L = L->getParentLoop();
MustExecuteAnnotatedWriter(const Module &M,
DominatorTree &DT, LoopInfo &LI) {
for (auto &F : M)
for (auto &I: instructions(F)) {
Loop *L = LI.getLoopFor(I.getParent());
while (L) {
if (isMustExecuteIn(I, L, &DT)) {
L = L->getParentLoop();
void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
if (!MustExec.count(&V))
const auto &Loops = MustExec.lookup(&V);
const auto NumLoops = Loops.size();
if (NumLoops > 1)
OS << " ; (mustexec in " << NumLoops << " loops: ";
OS << " ; (mustexec in: ";
bool first = true;
for (const Loop *L : Loops) {
if (!first)
OS << ", ";
first = false;
OS << L->getHeader()->getName();
OS << ")";
} // namespace
bool MustExecutePrinter::runOnFunction(Function &F) {
auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
MustExecuteAnnotatedWriter Writer(F, DT, LI);
F.print(dbgs(), &Writer);
return false;