blob: 8e85366b4618529d4dc366aea1d0351a433ef9d6 [file] [log] [blame]
//===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
// The LLVM Compiler Infrastructure
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
#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;
/// Computes loop safety information, checks loop body & header
/// for the possibility of may throw exception.
void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
assert(CurLoop != nullptr && "CurLoop can't be null");
BasicBlock *Header = CurLoop->getHeader();
// Setting default safety values.
SafetyInfo->MayThrow = false;
SafetyInfo->HeaderMayThrow = false;
// Iterate over header and compute safety info.
SafetyInfo->HeaderMayThrow =
SafetyInfo->MayThrow = SafetyInfo->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) && !SafetyInfo->MayThrow; ++BB)
SafetyInfo->MayThrow |=
// 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)))
SafetyInfo->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(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();
/// Returns true if the instruction in a loop is guaranteed to execute at least
/// once.
bool llvm::isGuaranteedToExecute(const Instruction &Inst,
const DominatorTree *DT, const Loop *CurLoop,
const LoopSafetyInfo *SafetyInfo) {
// We have to check to make sure that the instruction dominates all
// of the exit blocks. If it doesn't, then there is a path out of the loop
// which does not execute this instruction, so we can't hoist it.
// 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 !SafetyInfo->HeaderMayThrow ||
Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
// Somewhere in this loop there is an instruction which may throw and make us
// exit the loop.
if (SafetyInfo->MayThrow)
return false;
// Note: There are two styles of reasoning intermixed below for
// implementation efficiency reasons. They are:
// 1) If we can prove that the instruction dominates all exit blocks, then we
// know the instruction must have executed on *some* iteration before we
// exit. We do not prove *which* iteration the instruction must execute on.
// 2) If we can prove that the instruction dominates the latch and all exits
// which might be taken on the first iteration, we know the instruction must
// execute on the first iteration. This second style allows a conditional
// exit before the instruction of interest which is provably not taken on the
// first iteration. This is a quite common case for range check like
// patterns. TODO: support loops with multiple latches.
const bool InstDominatesLatch =
CurLoop->getLoopLatch() != nullptr &&
DT->dominates(Inst.getParent(), CurLoop->getLoopLatch());
// Get the exit blocks for the current loop.
SmallVector<BasicBlock *, 8> ExitBlocks;
// Verify that the block dominates each of the exit blocks of the loop.
for (BasicBlock *ExitBlock : ExitBlocks)
if (!DT->dominates(Inst.getParent(), ExitBlock))
if (!InstDominatesLatch ||
!CanProveNotTakenFirstIteration(ExitBlock, DT, CurLoop))
return false;
// As a degenerate case, if the loop is statically infinite then we haven't
// proven anything since there are no exit blocks.
if (ExitBlocks.empty())
return false;
// FIXME: In general, we have to prove that the loop isn't an infinite loop.
// See . (The "ExitBlocks.empty()" check above is
// just a special case of this.)
return true;
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.
LoopSafetyInfo LSI;
computeLoopSafetyInfo(&LSI, L);
return isGuaranteedToExecute(I, DT, L, &LSI) ||
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;