LLVM 17.0.0git
Macros | Functions | Variables
LoopFlatten.cpp File Reference
#include "llvm/Transforms/Scalar/LoopFlatten.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include <optional>
Include dependency graph for LoopFlatten.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "loop-flatten"
 

Functions

 STATISTIC (NumFlattened, "Number of loops flattened")
 
static bool setLoopComponents (Value *&TC, Value *&TripCount, BinaryOperator *&Increment, SmallPtrSetImpl< Instruction * > &IterationInstructions)
 
static bool verifyTripCount (Value *RHS, Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)
 
static bool findLoopComponents (Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)
 
static bool checkPHIs (FlattenInfo &FI, const TargetTransformInfo *TTI)
 
static bool checkOuterLoopInsts (FlattenInfo &FI, SmallPtrSetImpl< Instruction * > &IterationInstructions, const TargetTransformInfo *TTI)
 
static bool checkIVUsers (FlattenInfo &FI)
 
static OverflowResult checkOverflow (FlattenInfo &FI, DominatorTree *DT, AssumptionCache *AC)
 
static bool CanFlattenLoopPair (FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
 
static bool DoFlattenLoopPair (FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)
 
static bool CanWidenIV (FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
 
static bool FlattenLoopPair (FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)
 

Variables

static cl::opt< unsigned > RepeatedInstructionThreshold ("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening"))
 
static cl::opt< bool > AssumeNoOverflow ("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "trip counts will never overflow"))
 
static cl::opt< bool > WidenIV ("loop-flatten-widen-iv", cl::Hidden, cl::init(true), cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening"))
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-flatten"

Definition at line 83 of file LoopFlatten.cpp.

Function Documentation

◆ CanFlattenLoopPair()

static bool CanFlattenLoopPair ( FlattenInfo &  FI,
DominatorTree *  DT,
LoopInfo *  LI,
ScalarEvolution *  SE,
AssumptionCache *  AC,
const TargetTransformInfo *  TTI 
)
static

Definition at line 683 of file LoopFlatten.cpp.

References checkIVUsers(), checkOuterLoopInsts(), checkPHIs(), llvm::dbgs(), findLoopComponents(), and LLVM_DEBUG.

Referenced by CanWidenIV(), and FlattenLoopPair().

◆ CanWidenIV()

static bool CanWidenIV ( FlattenInfo &  FI,
DominatorTree *  DT,
LoopInfo *  LI,
ScalarEvolution *  SE,
AssumptionCache *  AC,
const TargetTransformInfo *  TTI 
)
static

Definition at line 802 of file LoopFlatten.cpp.

References assert(), CanFlattenLoopPair(), llvm::createWideIV(), llvm::dbgs(), Deleted, DL, llvm::Value::dump(), LLVM_DEBUG, llvm::WideIVInfo::NarrowIV, llvm::RecursivelyDeleteDeadPHINode(), Rewriter, and WidenIV.

Referenced by FlattenLoopPair().

◆ checkIVUsers()

static bool checkIVUsers ( FlattenInfo &  FI)
static

Definition at line 610 of file LoopFlatten.cpp.

References llvm::dbgs(), and LLVM_DEBUG.

Referenced by CanFlattenLoopPair().

◆ checkOuterLoopInsts()

static bool checkOuterLoopInsts ( FlattenInfo &  FI,
SmallPtrSetImpl< Instruction * > &  IterationInstructions,
const TargetTransformInfo *  TTI 
)
static

Definition at line 543 of file LoopFlatten.cpp.

References B, Cost, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::TargetTransformInfo::getInstructionCost(), llvm::BranchInst::getSuccessor(), I, llvm::isSafeToSpeculativelyExecute(), llvm::BranchInst::isUnconditional(), LLVM_DEBUG, llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::match(), RepeatedInstructionThreshold, and llvm::TargetTransformInfo::TCK_SizeAndLatency.

Referenced by CanFlattenLoopPair().

◆ checkOverflow()

static OverflowResult checkOverflow ( FlattenInfo &  FI,
DominatorTree *  DT,
AssumptionCache *  AC 
)
static

Definition at line 634 of file LoopFlatten.cpp.

References AssumeNoOverflow, llvm::computeOverflowForUnsignedMul(), llvm::dbgs(), DL, F, GEP, llvm::isGuaranteedToExecuteForEveryIteration(), and LLVM_DEBUG.

Referenced by FlattenLoopPair().

◆ checkPHIs()

static bool checkPHIs ( FlattenInfo &  FI,
const TargetTransformInfo *  TTI 
)
static

Definition at line 458 of file LoopFlatten.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::Value::dump(), llvm::PHINode::getIncomingValueForBlock(), llvm::Instruction::getParent(), llvm::PHINode::hasConstantValue(), llvm::SmallPtrSetImpl< PtrType >::insert(), and LLVM_DEBUG.

Referenced by CanFlattenLoopPair().

◆ DoFlattenLoopPair()

static bool DoFlattenLoopPair ( FlattenInfo &  FI,
DominatorTree *  DT,
LoopInfo *  LI,
ScalarEvolution *  SE,
AssumptionCache *  AC,
const TargetTransformInfo *  TTI,
LPMUpdater *  U,
MemorySSAUpdater *  MSSAU 
)
static

Definition at line 729 of file LoopFlatten.cpp.

References Builder, llvm::BranchInst::Create(), llvm::dbgs(), DEBUG_TYPE, llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge(), llvm::Value::dump(), llvm::OptimizationRemarkEmitter::emit(), llvm::LoopInfo::erase(), llvm::Instruction::eraseFromParent(), F, llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::ScalarEvolution::forgetLoop(), llvm::BasicBlock::getTerminator(), LLVM_DEBUG, PHI, llvm::Remark, and llvm::MemorySSAUpdater::removeEdge().

Referenced by FlattenLoopPair().

◆ findLoopComponents()

static bool findLoopComponents ( Loop *  L,
SmallPtrSetImpl< Instruction * > &  IterationInstructions,
PHINode *&  InductionPHI,
Value *&  TripCount,
BinaryOperator *&  Increment,
BranchInst *&  BackBranch,
ScalarEvolution *  SE,
bool  IsWidened 
)
static

Definition at line 378 of file LoopFlatten.cpp.

References llvm::dbgs(), llvm::Value::dump(), llvm::PHINode::getIncomingValueForBlock(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_ULT, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, RHS, and verifyTripCount().

Referenced by CanFlattenLoopPair().

◆ FlattenLoopPair()

static bool FlattenLoopPair ( FlattenInfo &  FI,
DominatorTree *  DT,
LoopInfo *  LI,
ScalarEvolution *  SE,
AssumptionCache *  AC,
const TargetTransformInfo *  TTI,
LPMUpdater *  U,
MemorySSAUpdater *  MSSAU 
)
static

Definition at line 868 of file LoopFlatten.cpp.

References CanFlattenLoopPair(), CanWidenIV(), checkOverflow(), llvm::dbgs(), DoFlattenLoopPair(), and LLVM_DEBUG.

Referenced by llvm::LoopFlattenPass::run().

◆ setLoopComponents()

static bool setLoopComponents ( Value *&  TC,
Value *&  TripCount,
BinaryOperator *&  Increment,
SmallPtrSetImpl< Instruction * > &  IterationInstructions 
)
static

Definition at line 295 of file LoopFlatten.cpp.

References llvm::dbgs(), llvm::Value::dump(), llvm::SmallPtrSetImpl< PtrType >::insert(), and LLVM_DEBUG.

Referenced by verifyTripCount().

◆ STATISTIC()

STATISTIC ( NumFlattened  ,
"Number of loops flattened"   
)

◆ verifyTripCount()

static bool verifyTripCount ( Value *  RHS,
Loop *  L,
SmallPtrSetImpl< Instruction * > &  IterationInstructions,
PHINode *&  InductionPHI,
Value *&  TripCount,
BinaryOperator *&  Increment,
BranchInst *&  BackBranch,
ScalarEvolution *  SE,
bool  IsWidened 
)
static

Definition at line 311 of file LoopFlatten.cpp.

References llvm::dbgs(), llvm::ConstantInt::get(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::Value::getContext(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::ScalarEvolution::getZeroExtendExpr(), LLVM_DEBUG, RHS, and setLoopComponents().

Referenced by findLoopComponents().

Variable Documentation

◆ AssumeNoOverflow

cl::opt< bool > AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "trip counts will never overflow")) ( "loop-flatten-assume-no-overflow"  ,
cl::Hidden  ,
cl::init(false)  ,
cl::desc("Assume that the product of the two iteration " "trip counts will never overflow")   
)
static

Referenced by checkOverflow().

◆ RepeatedInstructionThreshold

cl::opt< unsigned > RepeatedInstructionThreshold("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening")) ( "loop-flatten-cost-threshold"  ,
cl::Hidden  ,
cl::init(2)  ,
cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening")   
)
static

Referenced by checkOuterLoopInsts().

◆ WidenIV

WidenIV::WidenIV ( "loop-flatten-widen-iv"  ,
cl::Hidden  ,
cl::init(true)  ,
cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening")   
)
static

Definition at line 1172 of file SimplifyIndVar.cpp.

Referenced by CanWidenIV(), and llvm::createWideIV().

Generated on Fri Mar 24 2023 02:17:58 for LLVM by doxygen 1.9.6