LLVM  10.0.0svn
Macros | Functions | Variables
CorrelatedValuePropagation.cpp File Reference
#include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Optional.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/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/CallSite.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/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <utility>
Include dependency graph for CorrelatedValuePropagation.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "correlated-value-propagation"
 

Functions

 STATISTIC (NumPhis, "Number of phis propagated")
 
 STATISTIC (NumPhiCommon, "Number of phis deleted via common incoming value")
 
 STATISTIC (NumSelects, "Number of selects propagated")
 
 STATISTIC (NumMemAccess, "Number of memory access targets propagated")
 
 STATISTIC (NumCmps, "Number of comparisons propagated")
 
 STATISTIC (NumReturns, "Number of return values propagated")
 
 STATISTIC (NumDeadCases, "Number of switch cases removed")
 
 STATISTIC (NumSDivs, "Number of sdiv converted to udiv")
 
 STATISTIC (NumUDivs, "Number of udivs whose width was decreased")
 
 STATISTIC (NumAShrs, "Number of ashr converted to lshr")
 
 STATISTIC (NumSRems, "Number of srem converted to urem")
 
 STATISTIC (NumSExt, "Number of sext converted to zext")
 
 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 (NumOverflows, "Number of overflow checks removed")
 
 STATISTIC (NumSaturating, "Number of saturating arithmetics converted to normal arithmetics")
 
 INITIALIZE_PASS_BEGIN (CorrelatedValuePropagation, "correlated-propagation", "Value Propagation", false, false) INITIALIZE_PASS_END(CorrelatedValuePropagation
 
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. More...
 
static bool processPHI (PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
 
static bool processMemAccess (Instruction *I, LazyValueInfo *LVI)
 
static bool processCmp (CmpInst *Cmp, LazyValueInfo *LVI)
 See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove this comparison. More...
 
static bool processSwitch (SwitchInst *I, LazyValueInfo *LVI, DominatorTree *DT)
 Simplify a switch instruction by removing cases which can never fire. More...
 
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 void processOverflowIntrinsic (WithOverflowInst *WO, LazyValueInfo *LVI)
 
static void processSaturatingInst (SaturatingInst *SI, LazyValueInfo *LVI)
 
static bool processCallSite (CallSite CS, LazyValueInfo *LVI)
 Infer nonnull attributes for the arguments at the specified callsite. More...
 
static bool hasPositiveOperands (BinaryOperator *SDI, LazyValueInfo *LVI)
 
static bool processUDivOrURem (BinaryOperator *Instr, LazyValueInfo *LVI)
 Try to shrink a udiv/urem's width down to the smallest power of two that's sufficient to contain its operands. More...
 
static bool processSRem (BinaryOperator *SDI, LazyValueInfo *LVI)
 
static bool processSDiv (BinaryOperator *SDI, LazyValueInfo *LVI)
 See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove the both operands of this SDiv are positive. More...
 
static bool processAShr (BinaryOperator *SDI, LazyValueInfo *LVI)
 
static bool processSExt (SExtInst *SDI, LazyValueInfo *LVI)
 
static bool processAnd (BinaryOperator *BinOp, LazyValueInfo *LVI)
 
static ConstantgetConstantAt (Value *V, Instruction *At, LazyValueInfo *LVI)
 
static bool runImpl (Function &F, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
 

Variables

static cl::opt< boolDontAddNoWrapFlags ("cvp-dont-add-nowrap-flags", cl::init(false))
 
correlated propagation
 
correlated Value Propagation
 
correlated Value false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "correlated-value-propagation"

Definition at line 52 of file CorrelatedValuePropagation.cpp.

Function Documentation

◆ getConstantAt()

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

◆ hasPositiveOperands()

static bool hasPositiveOperands ( BinaryOperator SDI,
LazyValueInfo LVI 
)
static

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( CorrelatedValuePropagation  ,
"correlated-propagation ,
"Value Propagation ,
false  ,
false   
)

◆ 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 ( CallSite  CS,
LazyValueInfo LVI 
)
static

Infer nonnull attributes for the arguments at the specified callsite.

Definition at line 530 of file CorrelatedValuePropagation.cpp.

References llvm::AttributeList::addParamAttribute(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::arg_size(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::args(), assert(), C, llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::LazyValueInfo::False, llvm::Attribute::get(), llvm::Use::get(), llvm::ConstantPointerNull::get(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::getAttributes(), llvm::LazyValueInfo::getConstant(), llvm::Value::getContext(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::getInstruction(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::getOperandBundle(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::getParent(), llvm::LazyValueInfo::getPredicateAt(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::Type::isVectorTy(), llvm::LLVMContext::OB_deopt, llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::paramHasAttr(), processOverflowIntrinsic(), processSaturatingInst(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Use::set(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::setAttributes(), SI, and willNotOverflow().

Referenced by runImpl().

◆ processCmp()

static bool processCmp ( 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 295 of file CorrelatedValuePropagation.cpp.

References C, llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::ConstantInt::get(), llvm::Value::getContext(), llvm::Type::getInt1Ty(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::CmpInst::getPredicate(), llvm::LazyValueInfo::getPredicateAt(), I, llvm::Value::replaceAllUsesWith(), and llvm::LazyValueInfo::Unknown.

Referenced by runImpl().

◆ processMemAccess()

static bool processMemAccess ( Instruction I,
LazyValueInfo LVI 
)
static

◆ processOverflowIntrinsic()

static void processOverflowIntrinsic ( WithOverflowInst WO,
LazyValueInfo LVI 
)
static

◆ processPHI()

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

◆ processSaturatingInst()

static void processSaturatingInst ( SaturatingInst SI,
LazyValueInfo LVI 
)
static

◆ processSDiv()

static bool processSDiv ( BinaryOperator SDI,
LazyValueInfo LVI 
)
static

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

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 674 of file CorrelatedValuePropagation.cpp.

References llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), llvm::Value::getName(), llvm::User::getOperand(), llvm::Value::getType(), hasPositiveOperands(), llvm::Instruction::isExact(), llvm::Type::isVectorTy(), processUDivOrURem(), and llvm::Value::replaceAllUsesWith().

Referenced by runImpl().

◆ processSelect()

static bool processSelect ( SelectInst S,
LazyValueInfo LVI 
)
static

◆ processSExt()

static bool processSExt ( SExtInst SDI,
LazyValueInfo LVI 
)
static

◆ processSRem()

static bool processSRem ( BinaryOperator SDI,
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 329 of file CorrelatedValuePropagation.cpp.

References llvm::DomTreeUpdater::Lazy.

Referenced by runImpl().

◆ processUDivOrURem()

static bool processUDivOrURem ( BinaryOperator Instr,
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 C, llvm::DominatorTree::dominates(), llvm::numbers::e, llvm::SmallVectorBase::empty(), llvm::Instruction::eraseFromParent(), llvm::LazyValueInfo::getConstantOnEdge(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::Value::replaceAllUsesWith().

Referenced by processPHI().

◆ STATISTIC() [1/30]

STATISTIC ( NumPhis  ,
"Number of phis propagated"   
)

◆ STATISTIC() [2/30]

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

◆ STATISTIC() [3/30]

STATISTIC ( NumSelects  ,
"Number of selects propagated"   
)

◆ STATISTIC() [4/30]

STATISTIC ( NumMemAccess  ,
"Number of memory access targets propagated"   
)

◆ STATISTIC() [5/30]

STATISTIC ( NumCmps  ,
"Number of comparisons propagated"   
)

◆ STATISTIC() [6/30]

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

◆ STATISTIC() [7/30]

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

◆ STATISTIC() [8/30]

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

◆ STATISTIC() [9/30]

STATISTIC ( NumUDivs  ,
"Number of udivs whose width was decreased"   
)

◆ STATISTIC() [10/30]

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

◆ STATISTIC() [11/30]

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

◆ STATISTIC() [12/30]

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

◆ STATISTIC() [13/30]

STATISTIC ( NumAnd  ,
"Number of ands removed"   
)

◆ STATISTIC() [14/30]

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

◆ STATISTIC() [15/30]

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

◆ STATISTIC() [16/30]

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

◆ STATISTIC() [17/30]

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

◆ STATISTIC() [18/30]

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

◆ STATISTIC() [19/30]

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

◆ STATISTIC() [20/30]

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

◆ STATISTIC() [21/30]

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

◆ STATISTIC() [22/30]

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

◆ STATISTIC() [23/30]

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

◆ STATISTIC() [24/30]

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

◆ STATISTIC() [25/30]

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

◆ STATISTIC() [26/30]

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

◆ STATISTIC() [27/30]

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

◆ STATISTIC() [28/30]

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

◆ STATISTIC() [29/30]

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

◆ STATISTIC() [30/30]

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

◆ willNotOverflow()

static bool willNotOverflow ( BinaryOpIntrinsic BO,
LazyValueInfo LVI 
)
static

Variable Documentation

◆ DontAddNoWrapFlags

cl::opt<bool> DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(false))
static

Referenced by processBinOp().

◆ false

correlated Value false

Definition at line 117 of file CorrelatedValuePropagation.cpp.

◆ propagation

correlated propagation

Definition at line 117 of file CorrelatedValuePropagation.cpp.

◆ Propagation

correlated Value Propagation

Definition at line 117 of file CorrelatedValuePropagation.cpp.