LLVM 19.0.0git
Macros | Enumerations | Functions
CorrelatedValuePropagation.cpp File Reference
#include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <optional>
#include <utility>

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "correlated-value-propagation"
 

Enumerations

enum class  Domain { NonNegative , NonPositive , Unknown }
 

Functions

 STATISTIC (NumPhis, "Number of phis propagated")
 
 STATISTIC (NumPhiCommon, "Number of phis deleted via common incoming value")
 
 STATISTIC (NumSelects, "Number of selects propagated")
 
 STATISTIC (NumCmps, "Number of comparisons propagated")
 
 STATISTIC (NumReturns, "Number of return values propagated")
 
 STATISTIC (NumDeadCases, "Number of switch cases removed")
 
 STATISTIC (NumSDivSRemsNarrowed, "Number of sdivs/srems whose width was decreased")
 
 STATISTIC (NumSDivs, "Number of sdiv converted to udiv")
 
 STATISTIC (NumUDivURemsNarrowed, "Number of udivs/urems whose width was decreased")
 
 STATISTIC (NumAShrsConverted, "Number of ashr converted to lshr")
 
 STATISTIC (NumAShrsRemoved, "Number of ashr removed")
 
 STATISTIC (NumSRems, "Number of srem converted to urem")
 
 STATISTIC (NumSExt, "Number of sext converted to zext")
 
 STATISTIC (NumSICmps, "Number of signed icmp preds simplified to unsigned")
 
 STATISTIC (NumAnd, "Number of ands removed")
 
 STATISTIC (NumNW, "Number of no-wrap deductions")
 
 STATISTIC (NumNSW, "Number of no-signed-wrap deductions")
 
 STATISTIC (NumNUW, "Number of no-unsigned-wrap deductions")
 
 STATISTIC (NumAddNW, "Number of no-wrap deductions for add")
 
 STATISTIC (NumAddNSW, "Number of no-signed-wrap deductions for add")
 
 STATISTIC (NumAddNUW, "Number of no-unsigned-wrap deductions for add")
 
 STATISTIC (NumSubNW, "Number of no-wrap deductions for sub")
 
 STATISTIC (NumSubNSW, "Number of no-signed-wrap deductions for sub")
 
 STATISTIC (NumSubNUW, "Number of no-unsigned-wrap deductions for sub")
 
 STATISTIC (NumMulNW, "Number of no-wrap deductions for mul")
 
 STATISTIC (NumMulNSW, "Number of no-signed-wrap deductions for mul")
 
 STATISTIC (NumMulNUW, "Number of no-unsigned-wrap deductions for mul")
 
 STATISTIC (NumShlNW, "Number of no-wrap deductions for shl")
 
 STATISTIC (NumShlNSW, "Number of no-signed-wrap deductions for shl")
 
 STATISTIC (NumShlNUW, "Number of no-unsigned-wrap deductions for shl")
 
 STATISTIC (NumAbs, "Number of llvm.abs intrinsics removed")
 
 STATISTIC (NumOverflows, "Number of overflow checks removed")
 
 STATISTIC (NumSaturating, "Number of saturating arithmetics converted to normal arithmetics")
 
 STATISTIC (NumNonNull, "Number of function pointer arguments marked non-null")
 
 STATISTIC (NumMinMax, "Number of llvm.[us]{min,max} intrinsics removed")
 
 STATISTIC (NumSMinMax, "Number of llvm.s{min,max} intrinsics simplified to unsigned")
 
 STATISTIC (NumUDivURemsNarrowedExpanded, "Number of bound udiv's/urem's expanded")
 
 STATISTIC (NumZExt, "Number of non-negative deductions")
 
static ConstantgetConstantAt (Value *V, Instruction *At, LazyValueInfo *LVI)
 
static bool processSelect (SelectInst *S, LazyValueInfo *LVI)
 
static bool simplifyCommonValuePhi (PHINode *P, LazyValueInfo *LVI, DominatorTree *DT)
 Try to simplify a phi with constant incoming values that match the edge values of a non-constant value on all other edges: bb0: isnull = icmp eq i8* x, null br i1 isnull, label bb2, label bb1 bb1: br label bb2 bb2: r = phi i8* [ x, bb1 ], [ null, bb0 ] --> r = x.
 
static ValuegetValueOnEdge (LazyValueInfo *LVI, Value *Incoming, BasicBlock *From, BasicBlock *To, Instruction *CxtI)
 
static bool processPHI (PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
 
static bool processICmp (ICmpInst *Cmp, LazyValueInfo *LVI)
 
static bool constantFoldCmp (CmpInst *Cmp, LazyValueInfo *LVI)
 See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove this comparison.
 
static bool processCmp (CmpInst *Cmp, LazyValueInfo *LVI)
 
static bool processSwitch (SwitchInst *I, LazyValueInfo *LVI, DominatorTree *DT)
 Simplify a switch instruction by removing cases which can never fire.
 
static bool willNotOverflow (BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
 
static void setDeducedOverflowingFlags (Value *V, Instruction::BinaryOps Opcode, bool NewNSW, bool NewNUW)
 
static bool processBinOp (BinaryOperator *BinOp, LazyValueInfo *LVI)
 
static bool processAbsIntrinsic (IntrinsicInst *II, LazyValueInfo *LVI)
 
static bool processMinMaxIntrinsic (MinMaxIntrinsic *MM, LazyValueInfo *LVI)
 
static bool processOverflowIntrinsic (WithOverflowInst *WO, LazyValueInfo *LVI)
 
static bool processSaturatingInst (SaturatingInst *SI, LazyValueInfo *LVI)
 
static bool processCallSite (CallBase &CB, LazyValueInfo *LVI)
 Infer nonnull attributes for the arguments at the specified callsite.
 
static Domain getDomain (const ConstantRange &CR)
 
static bool narrowSDivOrSRem (BinaryOperator *Instr, const ConstantRange &LCR, const ConstantRange &RCR)
 Try to shrink a sdiv/srem's width down to the smallest power of two that's sufficient to contain its operands.
 
static bool expandUDivOrURem (BinaryOperator *Instr, const ConstantRange &XCR, const ConstantRange &YCR)
 
static bool narrowUDivOrURem (BinaryOperator *Instr, const ConstantRange &XCR, const ConstantRange &YCR)
 Try to shrink a udiv/urem's width down to the smallest power of two that's sufficient to contain its operands.
 
static bool processUDivOrURem (BinaryOperator *Instr, LazyValueInfo *LVI)
 
static bool processSRem (BinaryOperator *SDI, const ConstantRange &LCR, const ConstantRange &RCR, LazyValueInfo *LVI)
 
static bool processSDiv (BinaryOperator *SDI, const ConstantRange &LCR, const ConstantRange &RCR, LazyValueInfo *LVI)
 See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove the signs of both operands of this SDiv.
 
static bool processSDivOrSRem (BinaryOperator *Instr, LazyValueInfo *LVI)
 
static bool processAShr (BinaryOperator *SDI, LazyValueInfo *LVI)
 
static bool processSExt (SExtInst *SDI, LazyValueInfo *LVI)
 
static bool processZExt (ZExtInst *ZExt, LazyValueInfo *LVI)
 
static bool processAnd (BinaryOperator *BinOp, LazyValueInfo *LVI)
 
static bool runImpl (Function &F, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "correlated-value-propagation"

Definition at line 48 of file CorrelatedValuePropagation.cpp.

Enumeration Type Documentation

◆ Domain

enum class Domain
strong
Enumerator
NonNegative 
NonPositive 
Unknown 

Definition at line 686 of file CorrelatedValuePropagation.cpp.

Function Documentation

◆ constantFoldCmp()

static bool constantFoldCmp ( CmpInst Cmp,
LazyValueInfo LVI 
)
static

See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove this comparison.

Even for local conditions, this can sometimes prove conditions instcombine can't by exploiting range information.

Definition at line 318 of file CorrelatedValuePropagation.cpp.

References llvm::LazyValueInfo::getPredicateAt(), llvm::Value::getType(), llvm::CmpInst::makeCmpResultType(), and llvm::LazyValueInfo::Unknown.

Referenced by processCmp().

◆ expandUDivOrURem()

static bool expandUDivOrURem ( BinaryOperator Instr,
const ConstantRange XCR,
const ConstantRange YCR 
)
static

◆ getConstantAt()

static Constant * getConstantAt ( Value V,
Instruction At,
LazyValueInfo LVI 
)
static

◆ getDomain()

static Domain getDomain ( const ConstantRange CR)
static

◆ getValueOnEdge()

static Value * getValueOnEdge ( LazyValueInfo LVI,
Value Incoming,
BasicBlock From,
BasicBlock To,
Instruction CxtI 
)
static

◆ narrowSDivOrSRem()

static bool narrowSDivOrSRem ( BinaryOperator Instr,
const ConstantRange LCR,
const ConstantRange RCR 
)
static

Try to shrink a sdiv/srem's width down to the smallest power of two that's sufficient to contain its operands.

Definition at line 698 of file CorrelatedValuePropagation.cpp.

References assert(), B, llvm::ConstantRange::contains(), llvm::APInt::getAllOnes(), llvm::Type::getIntNTy(), llvm::ConstantRange::getMinSignedBits(), llvm::APInt::getSignedMinValue(), LHS, llvm::PowerOf2Ceil(), RHS, and llvm::APInt::sext().

Referenced by processSDivOrSRem().

◆ narrowUDivOrURem()

static bool narrowUDivOrURem ( BinaryOperator Instr,
const ConstantRange XCR,
const ConstantRange YCR 
)
static

Try to shrink a udiv/urem's width down to the smallest power of two that's sufficient to contain its operands.

Definition at line 829 of file CorrelatedValuePropagation.cpp.

References assert(), B, llvm::ConstantRange::getActiveBits(), llvm::Type::getIntNTy(), LHS, llvm::PowerOf2Ceil(), and RHS.

Referenced by processUDivOrURem().

◆ processAbsIntrinsic()

static bool processAbsIntrinsic ( IntrinsicInst II,
LazyValueInfo LVI 
)
static

◆ processAnd()

static bool processAnd ( BinaryOperator BinOp,
LazyValueInfo LVI 
)
static

◆ processAShr()

static bool processAShr ( BinaryOperator SDI,
LazyValueInfo LVI 
)
static

◆ processBinOp()

static bool processBinOp ( BinaryOperator BinOp,
LazyValueInfo LVI 
)
static

◆ processCallSite()

static bool processCallSite ( CallBase CB,
LazyValueInfo LVI 
)
static

◆ processCmp()

static bool processCmp ( CmpInst Cmp,
LazyValueInfo LVI 
)
static

Definition at line 335 of file CorrelatedValuePropagation.cpp.

References constantFoldCmp(), and processICmp().

Referenced by runImpl().

◆ processICmp()

static bool processICmp ( ICmpInst Cmp,
LazyValueInfo LVI 
)
static

◆ processMinMaxIntrinsic()

static bool processMinMaxIntrinsic ( MinMaxIntrinsic MM,
LazyValueInfo LVI 
)
static

◆ processOverflowIntrinsic()

static bool processOverflowIntrinsic ( WithOverflowInst WO,
LazyValueInfo LVI 
)
static

◆ processPHI()

static bool processPHI ( PHINode P,
LazyValueInfo LVI,
DominatorTree DT,
const SimplifyQuery SQ 
)
static

◆ processSaturatingInst()

static bool processSaturatingInst ( SaturatingInst SI,
LazyValueInfo LVI 
)
static

◆ processSDiv()

static bool processSDiv ( BinaryOperator SDI,
const ConstantRange LCR,
const ConstantRange RCR,
LazyValueInfo LVI 
)
static

See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove the signs of both operands of this SDiv.

If this is the case, replace the SDiv with a UDiv. Even for local conditions, this can sometimes prove conditions instcombine can't by exploiting range information.

Definition at line 944 of file CorrelatedValuePropagation.cpp.

References assert(), llvm::BinaryOperator::CreateNeg(), D, llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), getDomain(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::ConstantRange::getSingleElement(), llvm::Value::getType(), llvm::Instruction::isExact(), llvm::Type::isVectorTy(), NonNegative, processUDivOrURem(), llvm::Value::replaceAllUsesWith(), llvm::ConstantRange::sdiv(), and Unknown.

Referenced by processSDivOrSRem().

◆ processSDivOrSRem()

static bool processSDivOrSRem ( BinaryOperator Instr,
LazyValueInfo LVI 
)
static

◆ processSelect()

static bool processSelect ( SelectInst S,
LazyValueInfo LVI 
)
static

◆ processSExt()

static bool processSExt ( SExtInst SDI,
LazyValueInfo LVI 
)
static

◆ processSRem()

static bool processSRem ( BinaryOperator SDI,
const ConstantRange LCR,
const ConstantRange RCR,
LazyValueInfo LVI 
)
static

◆ processSwitch()

static bool processSwitch ( SwitchInst I,
LazyValueInfo LVI,
DominatorTree DT 
)
static

Simplify a switch instruction by removing cases which can never fire.

If the uselessness of a case could be determined locally then constant propagation would already have figured it out. Instead, walk the predecessors and statically evaluate cases based on information available on that edge. Cases that cannot fire no matter what the incoming edge can safely be removed. If a case fires on every incoming edge then the entire switch can be removed and replaced with a branch to the case destination.

Definition at line 353 of file CorrelatedValuePropagation.cpp.

References llvm::DomTreeUpdater::applyUpdatesPermissive(), Cond, llvm::ConstantFoldTerminator(), llvm::LazyValueInfo::False, llvm::LazyValueInfo::getPredicateAt(), I, llvm::CmpInst::ICMP_EQ, llvm::BasicBlock::removePredecessor(), llvm::successors(), and llvm::LazyValueInfo::True.

Referenced by runImpl().

◆ processUDivOrURem()

static bool processUDivOrURem ( BinaryOperator Instr,
LazyValueInfo LVI 
)
static

◆ processZExt()

static bool processZExt ( ZExtInst ZExt,
LazyValueInfo LVI 
)
static

◆ runImpl()

static bool runImpl ( Function F,
LazyValueInfo LVI,
DominatorTree DT,
const SimplifyQuery SQ 
)
static

◆ setDeducedOverflowingFlags()

static void setDeducedOverflowingFlags ( Value V,
Instruction::BinaryOps  Opcode,
bool  NewNSW,
bool  NewNUW 
)
static

◆ simplifyCommonValuePhi()

static bool simplifyCommonValuePhi ( PHINode P,
LazyValueInfo LVI,
DominatorTree DT 
)
static

Try to simplify a phi with constant incoming values that match the edge values of a non-constant value on all other edges: bb0: isnull = icmp eq i8* x, null br i1 isnull, label bb2, label bb1 bb1: br label bb2 bb2: r = phi i8* [ x, bb1 ], [ null, bb0 ] --> r = x.

Definition at line 159 of file CorrelatedValuePropagation.cpp.

References llvm::CallingConv::C, llvm::DominatorTree::dominates(), llvm::SmallVectorBase< Size_T >::empty(), llvm::LazyValueInfo::getConstantOnEdge(), llvm::isGuaranteedNotToBePoison(), P, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by processPHI().

◆ STATISTIC() [1/38]

STATISTIC ( NumAbs  ,
"Number of llvm.abs intrinsics removed"   
)

◆ STATISTIC() [2/38]

STATISTIC ( NumAddNSW  ,
"Number of no-signed-wrap deductions for add"   
)

◆ STATISTIC() [3/38]

STATISTIC ( NumAddNUW  ,
"Number of no-unsigned-wrap deductions for add"   
)

◆ STATISTIC() [4/38]

STATISTIC ( NumAddNW  ,
"Number of no-wrap deductions for add"   
)

◆ STATISTIC() [5/38]

STATISTIC ( NumAnd  ,
"Number of ands removed"   
)

◆ STATISTIC() [6/38]

STATISTIC ( NumAShrsConverted  ,
"Number of ashr converted to lshr"   
)

◆ STATISTIC() [7/38]

STATISTIC ( NumAShrsRemoved  ,
"Number of ashr removed"   
)

◆ STATISTIC() [8/38]

STATISTIC ( NumCmps  ,
"Number of comparisons propagated"   
)

◆ STATISTIC() [9/38]

STATISTIC ( NumDeadCases  ,
"Number of switch cases removed"   
)

◆ STATISTIC() [10/38]

STATISTIC ( NumMinMax  ,
"Number of llvm.{min,max} intrinsics removed"  [us] 
)

◆ STATISTIC() [11/38]

STATISTIC ( NumMulNSW  ,
"Number of no-signed-wrap deductions for mul"   
)

◆ STATISTIC() [12/38]

STATISTIC ( NumMulNUW  ,
"Number of no-unsigned-wrap deductions for mul"   
)

◆ STATISTIC() [13/38]

STATISTIC ( NumMulNW  ,
"Number of no-wrap deductions for mul"   
)

◆ STATISTIC() [14/38]

STATISTIC ( NumNonNull  ,
"Number of function pointer arguments marked non-null"   
)

◆ STATISTIC() [15/38]

STATISTIC ( NumNSW  ,
"Number of no-signed-wrap deductions"   
)

◆ STATISTIC() [16/38]

STATISTIC ( NumNUW  ,
"Number of no-unsigned-wrap deductions"   
)

◆ STATISTIC() [17/38]

STATISTIC ( NumNW  ,
"Number of no-wrap deductions"   
)

◆ STATISTIC() [18/38]

STATISTIC ( NumOverflows  ,
"Number of overflow checks removed"   
)

◆ STATISTIC() [19/38]

STATISTIC ( NumPhiCommon  ,
"Number of phis deleted via common incoming value"   
)

◆ STATISTIC() [20/38]

STATISTIC ( NumPhis  ,
"Number of phis propagated"   
)

◆ STATISTIC() [21/38]

STATISTIC ( NumReturns  ,
"Number of return values propagated"   
)

◆ STATISTIC() [22/38]

STATISTIC ( NumSaturating  ,
"Number of saturating arithmetics converted to normal arithmetics"   
)

◆ STATISTIC() [23/38]

STATISTIC ( NumSDivs  ,
"Number of sdiv converted to udiv"   
)

◆ STATISTIC() [24/38]

STATISTIC ( NumSDivSRemsNarrowed  ,
"Number of sdivs/srems whose width was decreased"   
)

◆ STATISTIC() [25/38]

STATISTIC ( NumSelects  ,
"Number of selects propagated"   
)

◆ STATISTIC() [26/38]

STATISTIC ( NumSExt  ,
"Number of sext converted to zext"   
)

◆ STATISTIC() [27/38]

STATISTIC ( NumShlNSW  ,
"Number of no-signed-wrap deductions for shl"   
)

◆ STATISTIC() [28/38]

STATISTIC ( NumShlNUW  ,
"Number of no-unsigned-wrap deductions for shl"   
)

◆ STATISTIC() [29/38]

STATISTIC ( NumShlNW  ,
"Number of no-wrap deductions for shl"   
)

◆ STATISTIC() [30/38]

STATISTIC ( NumSICmps  ,
"Number of signed icmp preds simplified to unsigned"   
)

◆ STATISTIC() [31/38]

STATISTIC ( NumSMinMax  ,
"Number of llvm.s{min,max} intrinsics simplified to unsigned"   
)

◆ STATISTIC() [32/38]

STATISTIC ( NumSRems  ,
"Number of srem converted to urem"   
)

◆ STATISTIC() [33/38]

STATISTIC ( NumSubNSW  ,
"Number of no-signed-wrap deductions for sub"   
)

◆ STATISTIC() [34/38]

STATISTIC ( NumSubNUW  ,
"Number of no-unsigned-wrap deductions for sub"   
)

◆ STATISTIC() [35/38]

STATISTIC ( NumSubNW  ,
"Number of no-wrap deductions for sub"   
)

◆ STATISTIC() [36/38]

STATISTIC ( NumUDivURemsNarrowed  ,
"Number of udivs/urems whose width was decreased"   
)

◆ STATISTIC() [37/38]

STATISTIC ( NumUDivURemsNarrowedExpanded  ,
"Number of bound udiv's/urem's expanded"   
)

◆ STATISTIC() [38/38]

STATISTIC ( NumZExt  ,
"Number of non-negative deductions"   
)

◆ willNotOverflow()

static bool willNotOverflow ( BinaryOpIntrinsic BO,
LazyValueInfo LVI 
)
static