#include "llvm/Analysis/MustExecute.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/raw_ostream.h"

Macros
#define	DEBUG_TYPE "must-execute"

Functions
static bool	CanProveNotTakenFirstIteration (const BasicBlock ExitBlock, const DominatorTree DT, const Loop *CurLoop)
	Return true if we can prove that the given ExitBlock is not reached on the first iteration of the given loop.

static void	collectTransitivePredecessors (const Loop CurLoop, const BasicBlock BB, SmallPtrSetImpl< const BasicBlock * > &Predecessors)
	Collect all blocks from `CurLoop` which lie on all possible paths from the header of `CurLoop` (inclusive) to BB (exclusive) into the set `Predecessors`.

static bool	isMustExecuteIn (const Instruction &I, Loop L, DominatorTree DT)

static bool	maybeEndlessLoop (const Loop &L)
	Return true if `L` might be an endless loop.

template<typename K , typename V , typename FnTy , typename... ArgsTy>
static V	getOrCreateCachedOptional (K Key, DenseMap< K, std::optional< V > > &Map, FnTy &&Fn, ArgsTy &&...args)
	Lookup `Key` in `Map` and return the result, potentially after initializing the optional through `Fn`(`args`).

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "must-execute"

Definition at line 27 of file MustExecute.cpp.

Function Documentation

◆ CanProveNotTakenFirstIteration()

static bool CanProveNotTakenFirstIteration	(	const BasicBlock *	ExitBlock,
		const DominatorTree *	DT,
		const Loop *	CurLoop
	)

static

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.

Definition at line 115 of file MustExecute.cpp.

References assert(), Cond, llvm::LoopBase< BlockT, LoopT >::contains(), DL, llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BasicBlock::getModule(), llvm::BasicBlock::getSinglePredecessor(), LHS, RHS, and llvm::simplifyCmpInst().

Referenced by llvm::LoopSafetyInfo::allLoopPathsLeadToBlock().

◆ collectTransitivePredecessors()

static void collectTransitivePredecessors	(	const Loop *	CurLoop,
		const BasicBlock *	BB,
		SmallPtrSetImpl< const BasicBlock * > &	Predecessors
	)

static

Collect all blocks from CurLoop which lie on all possible paths from the header of CurLoop (inclusive) to BB (exclusive) into the set Predecessors.

If BB is the header, Predecessors will be empty. Note: It's possible that we encounter Irreducible control flow, due to which, we may find that a few predecessors of BB are not a part of the CurLoop. We only return Predecessors that are a part of CurLoop.

Definition at line 166 of file MustExecute.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::LoopSafetyInfo::allLoopPathsLeadToBlock(), and llvm::ICFLoopSafetyInfo::doesNotWriteMemoryBefore().