LLVM
12.0.0git
|
#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/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/InitializePasses.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>
Go to the source code of this file.
Macros | |
#define | DEBUG_TYPE "correlated-value-propagation" |
Enumerations | |
enum | Domain { Domain::NonNegative, Domain::NonPositive, Domain::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 (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 (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 (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 (CallBase &CB, LazyValueInfo *LVI) |
Infer nonnull attributes for the arguments at the specified callsite. More... | |
static bool | isNonNegative (Value *V, LazyValueInfo *LVI, Instruction *CxtI) |
static bool | isNonPositive (Value *V, LazyValueInfo *LVI, Instruction *CxtI) |
Domain | getDomain (Value *V, LazyValueInfo *LVI, Instruction *CxtI) |
static bool | narrowSDivOrSRem (BinaryOperator *Instr, LazyValueInfo *LVI) |
Try to shrink a sdiv/srem's width down to the smallest power of two that's sufficient to contain its operands. More... | |
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 signs of both operands of this SDiv. More... | |
static bool | processSDivOrSRem (BinaryOperator *Instr, LazyValueInfo *LVI) |
static bool | processAShr (BinaryOperator *SDI, LazyValueInfo *LVI) |
static bool | processSExt (SExtInst *SDI, LazyValueInfo *LVI) |
static bool | processAnd (BinaryOperator *BinOp, LazyValueInfo *LVI) |
static Constant * | getConstantAt (Value *V, Instruction *At, LazyValueInfo *LVI) |
static bool | runImpl (Function &F, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ) |
Variables | |
static cl::opt< bool > | DontAddNoWrapFlags ("cvp-dont-add-nowrap-flags", cl::init(false)) |
correlated | propagation |
correlated Value | Propagation |
correlated Value | false |
#define DEBUG_TYPE "correlated-value-propagation" |
Definition at line 52 of file CorrelatedValuePropagation.cpp.
|
strong |
Enumerator | |
---|---|
NonNegative | |
NonPositive | |
Unknown |
Definition at line 573 of file CorrelatedValuePropagation.cpp.
|
static |
Definition at line 909 of file CorrelatedValuePropagation.cpp.
References C, llvm::LazyValueInfo::getConstant(), llvm::Value::getContext(), llvm::ConstantInt::getFalse(), llvm::User::getOperand(), llvm::LazyValueInfo::getPredicateAt(), llvm::ConstantInt::getTrue(), llvm::LazyValueInfo::True, and llvm::LazyValueInfo::Unknown.
Referenced by runImpl().
Domain getDomain | ( | Value * | V, |
LazyValueInfo * | LVI, | ||
Instruction * | CxtI | ||
) |
Definition at line 575 of file CorrelatedValuePropagation.cpp.
References isNonNegative(), isNonPositive(), NonNegative, NonPositive, and Unknown.
Referenced by processSDiv(), and processSRem().
INITIALIZE_PASS_BEGIN | ( | CorrelatedValuePropagation | , |
"correlated-propagation" | , | ||
"Value Propagation" | , | ||
false | , | ||
false | |||
) |
|
static |
Definition at line 561 of file CorrelatedValuePropagation.cpp.
References llvm::ConstantInt::get(), llvm::LazyValueInfo::getPredicateAt(), llvm::Value::getType(), llvm::CmpInst::ICMP_SGE, and llvm::LazyValueInfo::True.
Referenced by getDomain(), llvm::APSInt::isStrictlyPositive(), llvm::APInt::isStrictlyPositive(), processAShr(), and processSExt().
|
static |
Definition at line 567 of file CorrelatedValuePropagation.cpp.
References llvm::ConstantInt::get(), llvm::LazyValueInfo::getPredicateAt(), llvm::Value::getType(), llvm::CmpInst::ICMP_SLE, and llvm::LazyValueInfo::True.
Referenced by getDomain().
|
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 585 of file CorrelatedValuePropagation.cpp.
References assert(), B, contains(), llvm::Instruction::eraseFromParent(), llvm::APInt::getAllOnesValue(), llvm::LazyValueInfo::getConstantRange(), llvm::Value::getContext(), llvm::Type::getIntegerBitWidth(), llvm::Type::getIntNTy(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::APInt::getSignedMinValue(), llvm::Value::getType(), I, llvm::Instruction::isExact(), llvm::Type::isVectorTy(), llvm::max(), llvm::User::operands(), llvm::PowerOf2Ceil(), llvm::Value::replaceAllUsesWith(), and llvm::zip().
Referenced by processSDivOrSRem().
|
static |
Definition at line 884 of file CorrelatedValuePropagation.cpp.
References llvm::Instruction::eraseFromParent(), llvm::LazyValueInfo::getConstantRange(), llvm::User::getOperand(), llvm::Value::getType(), llvm::ConstantRange::getUnsignedMax(), llvm::ConstantInt::getValue(), llvm::APInt::isMask(), llvm::Type::isVectorTy(), llvm::Value::replaceAllUsesWith(), and llvm::APInt::ule().
Referenced by runImpl().
|
static |
Definition at line 806 of file CorrelatedValuePropagation.cpp.
References llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), llvm::Value::getName(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Instruction::isExact(), isNonNegative(), llvm::Type::isVectorTy(), and llvm::Value::replaceAllUsesWith().
Referenced by runImpl().
|
static |
Definition at line 843 of file CorrelatedValuePropagation.cpp.
References llvm::ConstantRange::contains(), DontAddNoWrapFlags, llvm::LazyValueInfo::getConstantRange(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Instruction::hasNoSignedWrap(), llvm::Instruction::hasNoUnsignedWrap(), llvm::Type::isVectorTy(), llvm::ConstantRange::makeGuaranteedNoWrapRegion(), and setDeducedOverflowingFlags().
Referenced by processOverflowIntrinsic(), processSaturatingInst(), and runImpl().
|
static |
Infer nonnull attributes for the arguments at the specified callsite.
Definition at line 491 of file CorrelatedValuePropagation.cpp.
References llvm::AttributeList::addParamAttribute(), llvm::CallBase::arg_size(), llvm::CallBase::args(), assert(), C, llvm::SmallVectorBase< Size_T >::empty(), llvm::LazyValueInfo::False, llvm::Use::get(), llvm::Attribute::get(), llvm::ConstantPointerNull::get(), llvm::CallBase::getAttributes(), llvm::LazyValueInfo::getConstant(), llvm::Value::getContext(), llvm::CallBase::getOperandBundle(), llvm::LazyValueInfo::getPredicateAt(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::Type::isVectorTy(), llvm::LLVMContext::OB_deopt, llvm::CallBase::paramHasAttr(), processOverflowIntrinsic(), processSaturatingInst(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Use::set(), llvm::CallBase::setAttributes(), SI, and willNotOverflow().
Referenced by runImpl().
|
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 301 of file CorrelatedValuePropagation.cpp.
References C, llvm::ConstantInt::get(), llvm::Type::getInt1Ty(), llvm::LazyValueInfo::getPredicateAt(), and llvm::LazyValueInfo::Unknown.
Referenced by runImpl().
|
static |
Definition at line 280 of file CorrelatedValuePropagation.cpp.
References C, llvm::LazyValueInfo::getConstant(), and I.
Referenced by runImpl().
|
static |
Definition at line 448 of file CorrelatedValuePropagation.cpp.
References B, llvm::Instruction::eraseFromParent(), llvm::ConstantStruct::get(), llvm::UndefValue::get(), llvm::BinaryOpIntrinsic::getBinaryOp(), llvm::ConstantInt::getFalse(), llvm::BinaryOpIntrinsic::getLHS(), llvm::Value::getName(), llvm::BinaryOpIntrinsic::getRHS(), llvm::Value::getType(), llvm::BinaryOpIntrinsic::isSigned(), processBinOp(), llvm::Value::replaceAllUsesWith(), setDeducedOverflowingFlags(), and llvm::ARM_MB::ST.
Referenced by processCallSite().
|
static |
Definition at line 210 of file CorrelatedValuePropagation.cpp.
References C, llvm::dbgs(), llvm::numbers::e, llvm::LazyValueInfo::False, llvm::LazyValueInfo::getConstantOnEdge(), llvm::LazyValueInfo::getPredicateOnEdge(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::Type::isVectorTy(), LLVM_DEBUG, P, SI, simplifyCommonValuePhi(), and llvm::SimplifyInstruction().
Referenced by runImpl().
|
static |
Definition at line 472 of file CorrelatedValuePropagation.cpp.
References llvm::BinaryOperator::Create(), processBinOp(), llvm::Instruction::setDebugLoc(), setDeducedOverflowingFlags(), and SI.
Referenced by processCallSite().
|
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 737 of file CorrelatedValuePropagation.cpp.
References assert(), llvm::BinaryOperator::CreateNeg(), D, llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), getDomain(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::Value::getType(), I, llvm::Instruction::isExact(), llvm::Type::isVectorTy(), NonNegative, llvm::User::operands(), processUDivOrURem(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), Unknown, and llvm::zip().
Referenced by processSDivOrSRem().
|
static |
Definition at line 789 of file CorrelatedValuePropagation.cpp.
References assert(), llvm::BinaryOperator::getOpcode(), llvm::Value::getType(), llvm::Type::isVectorTy(), narrowSDivOrSRem(), processSDiv(), and processSRem().
Referenced by runImpl().
|
static |
Definition at line 128 of file CorrelatedValuePropagation.cpp.
References C, llvm::Instruction::eraseFromParent(), llvm::SelectInst::getCondition(), llvm::LazyValueInfo::getConstant(), llvm::SelectInst::getFalseValue(), llvm::SelectInst::getTrueValue(), llvm::Value::getType(), llvm::ConstantInt::isOne(), llvm::Type::isVectorTy(), and llvm::Value::replaceAllUsesWith().
Referenced by runImpl().
|
static |
Definition at line 824 of file CorrelatedValuePropagation.cpp.
References llvm::CastInst::CreateZExtOrBitCast(), llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), llvm::Value::getName(), llvm::User::getOperand(), llvm::Value::getType(), isNonNegative(), llvm::Type::isVectorTy(), llvm::Value::replaceAllUsesWith(), and llvm::Instruction::setDebugLoc().
Referenced by runImpl().
|
static |
Definition at line 681 of file CorrelatedValuePropagation.cpp.
References assert(), llvm::BinaryOperator::CreateNeg(), D, llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), getDomain(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::Value::getType(), I, llvm::Type::isVectorTy(), NonNegative, NonPositive, llvm::User::operands(), processUDivOrURem(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), Unknown, and llvm::zip().
Referenced by processSDivOrSRem().
|
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 327 of file CorrelatedValuePropagation.cpp.
References llvm::DomTreeUpdater::applyUpdatesPermissive(), Cond, llvm::ConstantFoldTerminator(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::LazyValueInfo::False, llvm::LazyValueInfo::getPredicateAt(), I, llvm::CmpInst::ICMP_EQ, llvm::DomTreeUpdater::Lazy, llvm::BasicBlock::removePredecessor(), SI, llvm::successors(), and llvm::LazyValueInfo::True.
Referenced by llvm::PredicateInfoBuilder::buildPredicateInfo(), and runImpl().
|
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 639 of file CorrelatedValuePropagation.cpp.
References assert(), B, llvm::Instruction::eraseFromParent(), llvm::ConstantRange::getActiveBits(), llvm::LazyValueInfo::getConstantRange(), llvm::Value::getContext(), llvm::Type::getIntegerBitWidth(), llvm::Type::getIntNTy(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Instruction::isExact(), llvm::Type::isVectorTy(), llvm::max(), llvm::User::operands(), llvm::PowerOf2Ceil(), and llvm::Value::replaceAllUsesWith().
Referenced by processSDiv(), processSRem(), and runImpl().
|
static |
Definition at line 932 of file CorrelatedValuePropagation.cpp.
References llvm::Add, llvm::And, C, llvm::MCID::Call, llvm::depth_first(), F(), getConstantAt(), llvm::Instruction::getOpcode(), llvm::SPII::Load, llvm::Mul, processAnd(), processAShr(), processBinOp(), processCallSite(), processCmp(), processMemAccess(), processPHI(), processSDivOrSRem(), processSelect(), processSExt(), processSwitch(), processUDivOrURem(), llvm::MipsISD::Ret, llvm::MCID::Select, and llvm::SPII::Store.
Referenced by llvm::CorrelatedValuePropagationPass::run().
|
static |
Definition at line 398 of file CorrelatedValuePropagation.cpp.
References llvm::Add, llvm_unreachable, and llvm::Mul.
Referenced by processBinOp(), processOverflowIntrinsic(), and processSaturatingInst().
|
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 158 of file CorrelatedValuePropagation.cpp.
References C, llvm::DominatorTree::dominates(), llvm::numbers::e, llvm::SmallVectorBase< SmallVectorSizeType< T > >::empty(), llvm::LazyValueInfo::getConstantOnEdge(), P, and llvm::SmallVectorTemplateBase< T >::push_back().
Referenced by processPHI().
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 | ( | 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 | ( | 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 | ( | NumOverflows | , |
"Number of overflow checks removed" | |||
) |
STATISTIC | ( | NumSaturating | , |
"Number of saturating arithmetics converted to normal arithmetics" | |||
) |
|
static |
Definition at line 390 of file CorrelatedValuePropagation.cpp.
References llvm::ConstantRange::contains(), llvm::BinaryOpIntrinsic::getBinaryOp(), llvm::LazyValueInfo::getConstantRange(), llvm::BinaryOpIntrinsic::getLHS(), llvm::BinaryOpIntrinsic::getNoWrapKind(), llvm::BinaryOpIntrinsic::getRHS(), and llvm::ConstantRange::makeGuaranteedNoWrapRegion().
Referenced by processCallSite().
Referenced by processBinOp().
correlated Value false |
Definition at line 120 of file CorrelatedValuePropagation.cpp.
correlated propagation |
Definition at line 120 of file CorrelatedValuePropagation.cpp.
correlated Value Propagation |
Definition at line 120 of file CorrelatedValuePropagation.cpp.