LLVM  13.0.0git
Classes | Public Member Functions | Protected Types | Protected Member Functions | List of all members
WidenIV Class Reference

Classes

struct  NarrowIVDefUse
 Record a link in the Narrow IV def-use chain along with the WideIV that computes the same value as the Narrow IV def. More...
 

Public Member Functions

 WidenIV (const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv, DominatorTree *DTree, SmallVectorImpl< WeakTrackingVH > &DI, bool HasGuards, bool UsePostIncrementRanges=true)
 
PHINodecreateWideIV (SCEVExpander &Rewriter)
 Process a single induction variable. More...
 
unsigned getNumElimExt ()
 
unsigned getNumWidened ()
 

Protected Types

using WidenedRecTy = std::pair< const SCEVAddRecExpr *, ExtendKind >
 

Protected Member Functions

ValuecreateExtendInst (Value *NarrowOper, Type *WideType, bool IsSigned, Instruction *Use)
 
InstructioncloneIVUser (NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR)
 Instantiate a wide operation to replace a narrow operation. More...
 
InstructioncloneArithmeticIVUser (NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR)
 
InstructioncloneBitwiseIVUser (NarrowIVDefUse DU)
 
ExtendKind getExtendKind (Instruction *I)
 
WidenedRecTy getWideRecurrence (NarrowIVDefUse DU)
 Is this instruction potentially interesting for further simplification after widening it's type? In other words, can the extend be safely hoisted out of the loop with SCEV reducing the value to a recurrence on the same loop. More...
 
WidenedRecTy getExtendedOperandRecurrence (NarrowIVDefUse DU)
 No-wrap operations can transfer sign extension of their result to their operands. More...
 
const SCEVgetSCEVByOpCode (const SCEV *LHS, const SCEV *RHS, unsigned OpCode) const
 
InstructionwidenIVUse (NarrowIVDefUse DU, SCEVExpander &Rewriter)
 Determine whether an individual user of the narrow IV can be widened. More...
 
bool widenLoopCompare (NarrowIVDefUse DU)
 If the narrow use is a compare instruction, then widen the compare. More...
 
bool widenWithVariantUse (NarrowIVDefUse DU)
 
void pushNarrowIVUsers (Instruction *NarrowDef, Instruction *WideDef)
 Add eligible users of NarrowDef to NarrowIVUsers. More...
 

Detailed Description

Definition at line 950 of file SimplifyIndVar.cpp.

Member Typedef Documentation

◆ WidenedRecTy

using WidenIV::WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>
protected

Definition at line 1056 of file SimplifyIndVar.cpp.

Constructor & Destructor Documentation

◆ WidenIV()

WidenIV::WidenIV ( const WideIVInfo WI,
LoopInfo LInfo,
ScalarEvolution SEv,
DominatorTree DTree,
SmallVectorImpl< WeakTrackingVH > &  DI,
bool  HasGuards,
bool  UsePostIncrementRanges = true 
)

Member Function Documentation

◆ cloneArithmeticIVUser()

Instruction * WidenIV::cloneArithmeticIVUser ( WidenIV::NarrowIVDefUse  DU,
const SCEVAddRecExpr WideAR 
)
protected

◆ cloneBitwiseIVUser()

Instruction * WidenIV::cloneBitwiseIVUser ( WidenIV::NarrowIVDefUse  DU)
protected

◆ cloneIVUser()

Instruction * WidenIV::cloneIVUser ( WidenIV::NarrowIVDefUse  DU,
const SCEVAddRecExpr WideAR 
)
protected

Instantiate a wide operation to replace a narrow operation.

This only needs to handle operations that can evaluation to SCEVAddRec. It can safely return 0 for any operation we decide not to clone.

Definition at line 1156 of file SimplifyIndVar.cpp.

References llvm::MCID::Add, cloneArithmeticIVUser(), cloneBitwiseIVUser(), llvm::Instruction::getOpcode(), and WidenIV::NarrowIVDefUse::NarrowUse.

Referenced by widenIVUse().

◆ createExtendInst()

Value * WidenIV::createExtendInst ( Value NarrowOper,
Type WideType,
bool  IsSigned,
Instruction Use 
)
protected

◆ createWideIV()

PHINode * WidenIV::createWideIV ( SCEVExpander Rewriter)

Process a single induction variable.

First use the SCEVExpander to create a wide induction variable that evaluates to the same recurrence as the original narrow IV. Then use a worklist to forward traverse the narrow IV's def-use chain. After widenIVUse has processed all interesting IV users, the narrow IV will be isolated for removal by DeleteDeadPHIs.

It would be simpler to delete uses as they are processed, but we must avoid invalidating SCEV expressions.

Definition at line 1830 of file SimplifyIndVar.cpp.

References assert(), llvm::dbgs(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallPtrSetImplBase::empty(), llvm::ScalarEvolution::getEffectiveSCEVType(), getExtendKind(), llvm::BasicBlock::getFirstInsertionPt(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm::Value::hasNUses(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, WidenIV::NarrowIVDefUse::NarrowDef, WidenIV::NarrowIVDefUse::NarrowUse, llvm::ScalarEvolution::properlyDominates(), pushNarrowIVUsers(), llvm::replaceAllDbgUsesWith(), Rewriter, llvm::Instruction::setDebugLoc(), llvm::Value::use_empty(), and widenIVUse().

Referenced by llvm::createWideIV().

◆ getExtendedOperandRecurrence()

WidenIV::WidenedRecTy WidenIV::getExtendedOperandRecurrence ( WidenIV::NarrowIVDefUse  DU)
protected

No-wrap operations can transfer sign extension of their result to their operands.

Generate the SCEV value for the widened operation without actually modifying the IR yet. If the expression after extending the operands is an AddRec for this loop, return the AddRec and the kind of extension used.

Definition at line 1308 of file SimplifyIndVar.cpp.

References llvm::MCID::Add, assert(), getExtendKind(), llvm::SCEVAddRecExpr::getLoop(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::ScalarEvolution::getSCEV(), getSCEVByOpCode(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm::OverflowingBinaryOperator::hasNoSignedWrap(), llvm::OverflowingBinaryOperator::hasNoUnsignedWrap(), WidenIV::NarrowIVDefUse::NarrowDef, WidenIV::NarrowIVDefUse::NarrowUse, std::swap(), and WidenIV::NarrowIVDefUse::WideDef.

Referenced by widenIVUse().

◆ getExtendKind()

WidenIV::ExtendKind WidenIV::getExtendKind ( Instruction I)
protected

◆ getNumElimExt()

unsigned WidenIV::getNumElimExt ( )
inline

Definition at line 1042 of file SimplifyIndVar.cpp.

Referenced by llvm::createWideIV().

◆ getNumWidened()

unsigned WidenIV::getNumWidened ( )
inline

Definition at line 1043 of file SimplifyIndVar.cpp.

Referenced by llvm::createWideIV().

◆ getSCEVByOpCode()

const SCEV * WidenIV::getSCEVByOpCode ( const SCEV LHS,
const SCEV RHS,
unsigned  OpCode 
) const
protected

◆ getWideRecurrence()

WidenIV::WidenedRecTy WidenIV::getWideRecurrence ( WidenIV::NarrowIVDefUse  DU)
protected

Is this instruction potentially interesting for further simplification after widening it's type? In other words, can the extend be safely hoisted out of the loop with SCEV reducing the value to a recurrence on the same loop.

If so, return the extended recurrence and the kind of extension used. Otherwise return {nullptr, Unknown}.

Definition at line 1361 of file SimplifyIndVar.cpp.

References getExtendKind(), llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm::Type::isIntegerTy(), WidenIV::NarrowIVDefUse::NarrowDef, WidenIV::NarrowIVDefUse::NarrowUse, and WidenIV::NarrowIVDefUse::NeverNegative.

Referenced by widenIVUse().

◆ pushNarrowIVUsers()

void WidenIV::pushNarrowIVUsers ( Instruction NarrowDef,
Instruction WideDef 
)
protected

◆ widenIVUse()

Instruction * WidenIV::widenIVUse ( WidenIV::NarrowIVDefUse  DU,
SCEVExpander Rewriter 
)
protected

◆ widenLoopCompare()

bool WidenIV::widenLoopCompare ( WidenIV::NarrowIVDefUse  DU)
protected

◆ widenWithVariantUse()

bool WidenIV::widenWithVariantUse ( WidenIV::NarrowIVDefUse  DU)
protected

The documentation for this class was generated from the following file: