//===- MustExecute.h - Is an instruction known to execute--------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file
/// Contains a collection of routines for determining if a given instruction is
/// guaranteed to execute if a given point in control flow is reached. The most
/// common example is an instruction within a loop being provably executed if we
/// branch to the header of it's containing loop.
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
#define LLVM_ANALYSIS_MUSTEXECUTE_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/Analysis/EHPersonalities.h"
#include "llvm/Analysis/InstructionPrecedenceTracking.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instruction.h"
namespace llvm {
class Instruction;
class DominatorTree;
class Loop;
/// Captures loop safety information.
/// It keep information for loop blocks may throw exception or otherwise
/// exit abnormaly on any iteration of the loop which might actually execute
/// at runtime. The primary way to consume this infromation is via
/// isGuaranteedToExecute below, but some callers bailout or fallback to
/// alternate reasoning if a loop contains any implicit control flow.
/// NOTE: LoopSafetyInfo contains cached information regarding loops and their
/// particular blocks. This information is only dropped on invocation of
/// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if
/// any thrower instructions have been added or removed from them, or if the
/// control flow has changed, or in case of other meaningful modifications, the
/// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
/// loop were made and the info wasn't recomputed properly, the behavior of all
/// methods except for computeLoopSafetyInfo is undefined.
class LoopSafetyInfo {
// Used to update funclet bundle operands.
DenseMap<BasicBlock *, ColorVector> BlockColors;
protected:
/// Computes block colors.
void computeBlockColors(const Loop *CurLoop);
public:
/// Returns block colors map that is used to update funclet operand bundles.
const DenseMap<BasicBlock *, ColorVector> &getBlockColors() const;
/// Copy colors of block \p Old into the block \p New.
void copyColors(BasicBlock *New, BasicBlock *Old);
/// Returns true iff the block \p BB potentially may throw exception. It can
/// be false-positive in cases when we want to avoid complex analysis.
virtual bool blockMayThrow(const BasicBlock *BB) const = 0;
/// Returns true iff any block of the loop for which this info is contains an
/// instruction that may throw or otherwise exit abnormally.
virtual bool anyBlockMayThrow() const = 0;
/// Return true if we must reach the block \p BB under assumption that the
/// loop \p CurLoop is entered.
bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
const DominatorTree *DT) const;
/// Computes safety information for a loop checks loop body & header for
/// the possibility of may throw exception, it takes LoopSafetyInfo and loop
/// as argument. Updates safety information in LoopSafetyInfo argument.
/// Note: This is defined to clear and reinitialize an already initialized
/// LoopSafetyInfo. Some callers rely on this fact.
virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0;
/// Returns true if the instruction in a loop is guaranteed to execute at
/// least once (under the assumption that the loop is entered).
virtual bool isGuaranteedToExecute(const Instruction &Inst,
const DominatorTree *DT,
const Loop *CurLoop) const = 0;
LoopSafetyInfo() = default;
virtual ~LoopSafetyInfo() = default;
};
/// Simple and conservative implementation of LoopSafetyInfo that can give
/// false-positive answers to its queries in order to avoid complicated
/// analysis.
class SimpleLoopSafetyInfo: public LoopSafetyInfo {
bool MayThrow = false; // The current loop contains an instruction which
// may throw.
bool HeaderMayThrow = false; // Same as previous, but specific to loop header
public:
virtual bool blockMayThrow(const BasicBlock *BB) const;
virtual bool anyBlockMayThrow() const;
virtual void computeLoopSafetyInfo(const Loop *CurLoop);
virtual bool isGuaranteedToExecute(const Instruction &Inst,
const DominatorTree *DT,
const Loop *CurLoop) const;
SimpleLoopSafetyInfo() : LoopSafetyInfo() {};
virtual ~SimpleLoopSafetyInfo() {};
};
/// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to
/// give precise answers on "may throw" queries. This implementation uses cache
/// that should be invalidated by calling the methods insertInstructionTo and
/// removeInstruction whenever we modify a basic block's contents by adding or
/// removing instructions.
class ICFLoopSafetyInfo: public LoopSafetyInfo {
bool MayThrow = false; // The current loop contains an instruction which
// may throw.
// Contains information about implicit control flow in this loop's blocks.
mutable ImplicitControlFlowTracking ICF;
// Contains information about instruction that may possibly write memory.
mutable MemoryWriteTracking MW;
public:
virtual bool blockMayThrow(const BasicBlock *BB) const;
virtual bool anyBlockMayThrow() const;
virtual void computeLoopSafetyInfo(const Loop *CurLoop);
virtual bool isGuaranteedToExecute(const Instruction &Inst,
const DominatorTree *DT,
const Loop *CurLoop) const;
/// Returns true if we could not execute a memory-modifying instruction before
/// we enter \p BB under assumption that \p CurLoop is entered.
bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop)
const;
/// Returns true if we could not execute a memory-modifying instruction before
/// we execute \p I under assumption that \p CurLoop is entered.
bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop)
const;
/// Inform the safety info that we are planning to insert a new instruction
/// into the basic block \p BB. It will make all cache updates to keep it
/// correct after this insertion.
void insertInstructionTo(const BasicBlock *BB);
/// Inform safety info that we are planning to remove the instruction \p Inst
/// from its block. It will make all cache updates to keep it correct after
/// this removal.
void removeInstruction(const Instruction *Inst);
ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
virtual ~ICFLoopSafetyInfo() {};
};
}
#endif