LLVM  7.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/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Transforms/Utils/Local.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 <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 (NumOverflows, "Number of overflow checks removed")
 
 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 *C, 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 *SI, LazyValueInfo *LVI, DominatorTree *DT)
 Simplify a switch instruction by removing cases which can never fire. More...
 
static bool willNotOverflow (IntrinsicInst *II, LazyValueInfo *LVI)
 
static void processOverflowIntrinsic (IntrinsicInst *II)
 
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 processAdd (BinaryOperator *AddOp, 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< boolDontProcessAdds ("cvp-dont-process-adds", cl::init(true))
 
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   
)

◆ processAdd()

static bool processAdd ( BinaryOperator AddOp,
LazyValueInfo LVI 
)
static

◆ processAShr()

static bool processAShr ( BinaryOperator SDI,
LazyValueInfo LVI 
)
static

◆ processCallSite()

static bool processCallSite ( CallSite  CS,
LazyValueInfo LVI 
)
static

◆ processCmp()

static bool processCmp ( CmpInst C,
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 275 of file CorrelatedValuePropagation.cpp.

References C, llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::Value::getContext(), llvm::ConstantInt::getFalse(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::CmpInst::getPredicate(), llvm::LazyValueInfo::getPredicateAt(), llvm::ConstantInt::getTrue(), I, llvm::Value::replaceAllUsesWith(), Result, llvm::LazyValueInfo::True, and llvm::LazyValueInfo::Unknown.

Referenced by runImpl().

◆ processMemAccess()

static bool processMemAccess ( Instruction I,
LazyValueInfo LVI 
)
static

◆ processOverflowIntrinsic()

static void processOverflowIntrinsic ( IntrinsicInst II)
static

◆ processPHI()

static bool processPHI ( PHINode P,
LazyValueInfo LVI,
DominatorTree DT,
const SimplifyQuery SQ 
)
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 571 of file CorrelatedValuePropagation.cpp.

References llvm::Instruction::eraseFromParent(), 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

◆ processSRem()

static bool processSRem ( BinaryOperator SDI,
LazyValueInfo LVI 
)
static

◆ processSwitch()

static bool processSwitch ( SwitchInst SI,
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 310 of file CorrelatedValuePropagation.cpp.

References llvm::SwitchInst::case_begin(), llvm::SwitchInst::case_end(), llvm::ConstantFoldTerminator(), llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge(), llvm::LazyValueInfo::False, llvm::DeferredDominance::flush(), llvm::SwitchInst::getCondition(), llvm::SwitchInst::getNumCases(), llvm::Instruction::getParent(), getParent(), llvm::LazyValueInfo::getPredicateOnEdge(), llvm::CmpInst::ICMP_EQ, llvm::pred_begin(), llvm::pred_end(), llvm::SwitchInst::removeCase(), llvm::BasicBlock::removePredecessor(), llvm::SwitchInst::setCondition(), llvm::successors(), llvm::LazyValueInfo::True, and llvm::LazyValueInfo::Unknown.

Referenced by llvm::collectCmpOps(), and runImpl().

◆ processUDivOrURem()

static bool processUDivOrURem ( BinaryOperator Instr,
LazyValueInfo LVI 
)
static

◆ runImpl()

static bool runImpl ( Function F,
LazyValueInfo LVI,
DominatorTree DT,
const SimplifyQuery SQ 
)
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 139 of file CorrelatedValuePropagation.cpp.

References C, llvm::DominatorTree::dominates(), llvm::SmallVectorBase::empty(), llvm::Instruction::eraseFromParent(), llvm::LazyValueInfo::getConstantOnEdge(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and llvm::Value::replaceAllUsesWith().

Referenced by processPHI().

◆ STATISTIC() [1/12]

STATISTIC ( NumPhis  ,
"Number of phis propagated"   
)

◆ STATISTIC() [2/12]

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

◆ STATISTIC() [3/12]

STATISTIC ( NumSelects  ,
"Number of selects propagated"   
)

◆ STATISTIC() [4/12]

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

◆ STATISTIC() [5/12]

STATISTIC ( NumCmps  ,
"Number of comparisons propagated"   
)

◆ STATISTIC() [6/12]

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

◆ STATISTIC() [7/12]

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

◆ STATISTIC() [8/12]

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

◆ STATISTIC() [9/12]

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

◆ STATISTIC() [10/12]

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

◆ STATISTIC() [11/12]

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

◆ STATISTIC() [12/12]

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

◆ willNotOverflow()

static bool willNotOverflow ( IntrinsicInst II,
LazyValueInfo LVI 
)
static

Variable Documentation

◆ DontProcessAdds

cl::opt<bool> DontProcessAdds("cvp-dont-process-adds", cl::init(true))
static

Referenced by processAdd().

◆ false

correlated Value false

Definition at line 97 of file CorrelatedValuePropagation.cpp.

◆ propagation

correlated propagation

Definition at line 97 of file CorrelatedValuePropagation.cpp.

◆ Propagation

correlated Value Propagation

Definition at line 97 of file CorrelatedValuePropagation.cpp.