LLVM  6.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/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/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/IRBuilder.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 (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 (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 processPHI (PHINode *P, LazyValueInfo *LVI, 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)
 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 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, 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 211 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(), 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,
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 451 of file CorrelatedValuePropagation.cpp.

References llvm::Instruction::eraseFromParent(), llvm::Value::getName(), llvm::User::getOperand(), llvm::Value::getType(), hasPositiveOperands(), llvm::Instruction::isExact(), llvm::Type::isVectorTy(), 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 
)
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 246 of file CorrelatedValuePropagation.cpp.

References llvm::SwitchInst::case_begin(), llvm::SwitchInst::case_end(), llvm::ConstantFoldTerminator(), llvm::LazyValueInfo::False, 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::SwitchInst::setCondition(), llvm::LazyValueInfo::True, and llvm::LazyValueInfo::Unknown.

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

◆ runImpl()

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

◆ STATISTIC() [1/10]

STATISTIC ( NumPhis  ,
"Number of phis propagated"   
)

◆ STATISTIC() [2/10]

STATISTIC ( NumSelects  ,
"Number of selects propagated"   
)

◆ STATISTIC() [3/10]

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

◆ STATISTIC() [4/10]

STATISTIC ( NumCmps  ,
"Number of comparisons propagated"   
)

◆ STATISTIC() [5/10]

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

◆ STATISTIC() [6/10]

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

◆ STATISTIC() [7/10]

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

◆ STATISTIC() [8/10]

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

◆ STATISTIC() [9/10]

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

◆ STATISTIC() [10/10]

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

◆ propagation

correlated propagation

Definition at line 92 of file CorrelatedValuePropagation.cpp.

◆ Propagation

Interprocedural Sparse Conditional Constant Propagation

Definition at line 92 of file CorrelatedValuePropagation.cpp.