LLVM  9.0.0svn
Macros | Functions | Variables
InstructionCombining.cpp File Reference
#include "InstCombineInternal.h"
#include "llvm-c/Initialization.h"
#include "llvm-c/Transforms/InstCombine.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/TinyPtrVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/EHPersonalities.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/TargetFolder.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GetElementPtrTypeIterator.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/Intrinsics.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/CBindingWrapping.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/InstCombine/InstCombine.h"
#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <memory>
#include <string>
#include <utility>

Go to the source code of this file.


#define DEBUG_TYPE   "instcombine"


 STATISTIC (NumCombined, "Number of insts combined")
 STATISTIC (NumConstProp, "Number of constant folds")
 STATISTIC (NumDeadInst, "Number of dead inst eliminated")
 STATISTIC (NumSunkInst, "Number of instructions sunk")
 STATISTIC (NumExpand, "Number of expansions")
 STATISTIC (NumFactor, "Number of factorizations")
 STATISTIC (NumReassoc, "Number of reassociations")
 DEBUG_COUNTER (VisitCounter, "instcombine-visit", "Controls which instructions are visited")
static bool MaintainNoSignedWrap (BinaryOperator &I, Value *B, Value *C)
static void ClearSubclassDataAfterReassociation (BinaryOperator &I)
 Conservatively clears subclassOptionalData after a reassociation or commutation. More...
static bool simplifyAssocCastAssoc (BinaryOperator *BinOp1)
 Combine constant operands of associative operations either before or after a cast to eliminate one of the associative operations: (op (cast (op X, C2)), C1) –> (cast (op X, op (C1, C2))) (op (cast (op X, C2)), C1) –> (op (cast X), op (C1, C2)) More...
static bool leftDistributesOverRight (Instruction::BinaryOps LOp, Instruction::BinaryOps ROp)
 Return whether "X LOp (Y ROp Z)" is always equal to "(X LOp Y) ROp (X LOp Z)". More...
static bool rightDistributesOverLeft (Instruction::BinaryOps LOp, Instruction::BinaryOps ROp)
 Return whether "(X LOp Y) ROp Z" is always equal to "(X ROp Z) LOp (Y ROp Z)". More...
static ValuegetIdentityValue (Instruction::BinaryOps Opcode, Value *V)
 This function returns identity value for given opcode, which can be used to factor patterns like (X * 2) + X ==> (X * 2) + (X * 1) ==> X * (2 + 1). More...
static Instruction::BinaryOps getBinOpsForFactorization (Instruction::BinaryOps TopOpcode, BinaryOperator *Op, Value *&LHS, Value *&RHS)
 This function predicates factorization using distributive laws. More...
static ValuefoldOperationIntoSelectOperand (Instruction &I, Value *SO, InstCombiner::BuilderTy &Builder)
static ValuefoldOperationIntoPhiValue (BinaryOperator *I, Value *InV, InstCombiner::BuilderTy &Builder)
static bool shouldMergeGEPs (GEPOperator &GEP, GEPOperator &Src)
static bool isNeverEqualToUnescapedAlloc (Value *V, const TargetLibraryInfo *TLI, Instruction *AI)
static bool isAllocSiteRemovable (Instruction *AI, SmallVectorImpl< WeakTrackingVH > &Users, const TargetLibraryInfo *TLI)
static InstructiontryToMoveFreeBeforeNullTest (CallInst &FI, const DataLayout &DL)
 Move the call to free before a NULL test. More...
static bool isCatchAll (EHPersonality Personality, Constant *TypeInfo)
 Return 'true' if the given typeinfo will match anything. More...
static bool shorter_filter (const Value *LHS, const Value *RHS)
static bool TryToSinkInstruction (Instruction *I, BasicBlock *DestBlock)
 Try to move the specified instruction from its current block into the beginning of DestBlock, which can only happen if it's safe to move the instruction past all of the instructions between it and the end of its block. More...
static bool AddReachableCodeToWorklist (BasicBlock *BB, const DataLayout &DL, SmallPtrSetImpl< BasicBlock *> &Visited, InstCombineWorklist &ICWorklist, const TargetLibraryInfo *TLI)
 Walk the function in depth-first order, adding all reachable code to the worklist. More...
static bool prepareICWorklistFromFunction (Function &F, const DataLayout &DL, TargetLibraryInfo *TLI, InstCombineWorklist &ICWorklist)
 Populate the IC worklist from a function, and prune any dead basic blocks discovered in the process. More...
static bool combineInstructionsOverFunction (Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, bool ExpensiveCombines=true, LoopInfo *LI=nullptr)
 INITIALIZE_PASS_BEGIN (InstructionCombiningPass, "instcombine", "Combine redundant instructions", false, false) INITIALIZE_PASS_END(InstructionCombiningPass
void LLVMInitializeInstCombine (LLVMPassRegistryRef R)
void LLVMAddInstructionCombiningPass (LLVMPassManagerRef PM)
 See llvm::createInstructionCombiningPass function. More...


static cl::opt< boolEnableCodeSinking ("instcombine-code-sinking", cl::desc("Enable code sinking"), cl::init(true))
static cl::opt< boolEnableExpensiveCombines ("expensive-combines", cl::desc("Enable expensive instruction combines"))
static cl::opt< unsignedMaxArraySize ("instcombine-maxarray-size", cl::init(1024), cl::desc("Maximum array size considered when doing a combine"))
static cl::opt< unsignedShouldLowerDbgDeclare ("instcombine-lower-dbg-declare", cl::Hidden, cl::init(true))
Combine redundant instructions
Combine redundant false

Macro Definition Documentation


#define DEBUG_TYPE   "instcombine"

Definition at line 109 of file InstructionCombining.cpp.

Function Documentation

◆ AddReachableCodeToWorklist()

static bool AddReachableCodeToWorklist ( BasicBlock BB,
const DataLayout DL,
SmallPtrSetImpl< BasicBlock *> &  Visited,
InstCombineWorklist ICWorklist,
const TargetLibraryInfo TLI 

Walk the function in depth-first order, adding all reachable code to the worklist.

This has a couple of tricks to make the code faster and more powerful. In particular, we constant fold and DCE instructions as we go, to avoid adding them to the worklist (this significantly speeds up instcombine on code where many instructions are dead or constant). Additionally, if we find a branch whose condition is a known constant, we only visit the reachable successors.

Definition at line 3301 of file InstructionCombining.cpp.

References llvm::InstCombineWorklist::AddInitialGroup(), llvm::BasicBlock::begin(), C, llvm::ConstantFoldConstant(), llvm::ConstantFoldInstruction(), llvm::dbgs(), E, llvm::SmallVectorBase::empty(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::SelectInst::getCondition(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::BasicBlock::getTerminator(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isInstructionTriviallyDead(), LLVM_DEBUG, llvm::User::operands(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::salvageDebugInfo(), llvm::successors(), and llvm::Value::use_empty().

Referenced by prepareICWorklistFromFunction().

◆ ClearSubclassDataAfterReassociation()

static void ClearSubclassDataAfterReassociation ( BinaryOperator I)

Conservatively clears subclassOptionalData after a reassociation or commutation.

We preserve fast-math flags when applicable as they can be preserved.

Definition at line 226 of file InstructionCombining.cpp.

References llvm::Value::clearSubclassOptionalData(), llvm::dyn_cast(), llvm::Instruction::getFastMathFlags(), I, and llvm::Instruction::setFastMathFlags().

Referenced by simplifyAssocCastAssoc().

◆ combineInstructionsOverFunction()

static bool combineInstructionsOverFunction ( Function F,
InstCombineWorklist Worklist,
AliasAnalysis AA,
AssumptionCache AC,
TargetLibraryInfo TLI,
DominatorTree DT,
OptimizationRemarkEmitter ORE,
bool  ExpensiveCombines = true,
LoopInfo LI = nullptr 


DEBUG_COUNTER ( VisitCounter  ,
"instcombine-visit"  ,
"Controls which instructions are visited"   

◆ foldOperationIntoPhiValue()

static Value* foldOperationIntoPhiValue ( BinaryOperator I,
Value InV,
InstCombiner::BuilderTy Builder 

◆ foldOperationIntoSelectOperand()

static Value* foldOperationIntoSelectOperand ( Instruction I,
Value SO,
InstCombiner::BuilderTy Builder 

◆ getBinOpsForFactorization()

static Instruction::BinaryOps getBinOpsForFactorization ( Instruction::BinaryOps  TopOpcode,
BinaryOperator Op,
Value *&  LHS,
Value *&  RHS 

◆ getIdentityValue()

static Value* getIdentityValue ( Instruction::BinaryOps  Opcode,
Value V 

This function returns identity value for given opcode, which can be used to factor patterns like (X * 2) + X ==> (X * 2) + (X * 1) ==> X * (2 + 1).

Definition at line 484 of file InstructionCombining.cpp.

References llvm::ConstantExpr::getBinOpIdentity(), and llvm::Value::getType().

Referenced by getBinOpsForFactorization().


INITIALIZE_PASS_BEGIN ( InstructionCombiningPass  ,
"instcombine"  ,
"Combine redundant instructions ,
false  ,

◆ isAllocSiteRemovable()

static bool isAllocSiteRemovable ( Instruction AI,
SmallVectorImpl< WeakTrackingVH > &  Users,
const TargetLibraryInfo TLI 

◆ isCatchAll()

static bool isCatchAll ( EHPersonality  Personality,
Constant TypeInfo 

◆ isNeverEqualToUnescapedAlloc()

static bool isNeverEqualToUnescapedAlloc ( Value V,
const TargetLibraryInfo TLI,
Instruction AI 

Definition at line 2176 of file InstructionCombining.cpp.

References llvm::isAllocLikeFn().

Referenced by isAllocSiteRemovable().

◆ leftDistributesOverRight()

static bool leftDistributesOverRight ( Instruction::BinaryOps  LOp,
Instruction::BinaryOps  ROp 

Return whether "X LOp (Y ROp Z)" is always equal to "(X LOp Y) ROp (X LOp Z)".

Definition at line 448 of file InstructionCombining.cpp.

References llvm::MCID::Add.

Referenced by getBinOpsForFactorization(), and rightDistributesOverLeft().

◆ MaintainNoSignedWrap()

static bool MaintainNoSignedWrap ( BinaryOperator I,
Value B,
Value C 

◆ prepareICWorklistFromFunction()

static bool prepareICWorklistFromFunction ( Function F,
const DataLayout DL,
TargetLibraryInfo TLI,
InstCombineWorklist ICWorklist 

Populate the IC worklist from a function, and prune any dead basic blocks discovered in the process.

This also does basic constant propagation and other forward fixing to make the combiner itself run much faster.

Definition at line 3409 of file InstructionCombining.cpp.

References AddReachableCodeToWorklist(), llvm::Function::front(), and llvm::removeAllNonTerminatorAndEHPadInstructions().

Referenced by combineInstructionsOverFunction().

◆ rightDistributesOverLeft()

static bool rightDistributesOverLeft ( Instruction::BinaryOps  LOp,
Instruction::BinaryOps  ROp 

Return whether "(X LOp Y) ROp Z" is always equal to "(X ROp Z) LOp (Y ROp Z)".

Definition at line 469 of file InstructionCombining.cpp.

References llvm::Instruction::isBitwiseLogicOp(), llvm::Instruction::isCommutative(), llvm::Instruction::isShift(), and leftDistributesOverRight().

Referenced by getBinOpsForFactorization().

◆ shorter_filter()

static bool shorter_filter ( const Value LHS,
const Value RHS 

◆ shouldMergeGEPs()

static bool shouldMergeGEPs ( GEPOperator GEP,
GEPOperator Src 

Definition at line 1109 of file InstructionCombining.cpp.

References assert(), C, llvm::CastInst::Create(), llvm::APInt::exactLogBase2(), llvm::ConstantInt::get(), llvm::ConstantVector::get(), llvm::ConstantExpr::get(), llvm::UndefValue::get(), llvm::Constant::getAggregateElement(), getBitWidth(), llvm::APInt::getBitWidth(), llvm::ConstantExpr::getCast(), llvm::Instruction::getOpcode(), getOpcode(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::getSafeVectorConstantForBinop(), llvm::Type::getScalarType(), llvm::ShuffleVectorInst::getShuffleMask(), llvm::ConstantExpr::getTrunc(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), llvm::GEPOperator::hasAllZeroIndices(), llvm::Instruction::hasNoSignedWrap(), hasOneUse(), llvm::Value::hasOneUse(), I, llvm::Instruction::isIntDivRem(), llvm::APInt::isMinValue(), llvm::isSafeToSpeculativelyExecute(), llvm::Instruction::isShift(), llvm::Type::isVectorTy(), llvm::PatternMatch::m_c_BinOp(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_SExt(), llvm::PatternMatch::m_ShuffleVector(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Undef(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::m_ZExtOrSExt(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), llvm::APInt::sdivrem(), llvm::APInt::sext(), std::swap(), llvm::APInt::trunc(), llvm::Instruction::user_back(), llvm::NVPTX::PTXLdStInstCode::V2, willNotOverflow(), X, and Y.

Referenced by llvm::InstCombiner::visitGetElementPtrInst().

◆ simplifyAssocCastAssoc()

static bool simplifyAssocCastAssoc ( BinaryOperator BinOp1)

◆ STATISTIC() [1/7]

STATISTIC ( NumCombined  ,
"Number of insts combined"   

◆ STATISTIC() [2/7]

STATISTIC ( NumConstProp  ,
"Number of constant folds"   

◆ STATISTIC() [3/7]

STATISTIC ( NumDeadInst  ,
"Number of dead inst eliminated"   

◆ STATISTIC() [4/7]

STATISTIC ( NumSunkInst  ,
"Number of instructions sunk"   

◆ STATISTIC() [5/7]

STATISTIC ( NumExpand  ,
"Number of expansions"   

◆ STATISTIC() [6/7]

STATISTIC ( NumFactor  ,
"Number of factorizations"   

◆ STATISTIC() [7/7]

STATISTIC ( NumReassoc  ,
"Number of reassociations"   

◆ tryToMoveFreeBeforeNullTest()

static Instruction* tryToMoveFreeBeforeNullTest ( CallInst FI,
const DataLayout DL 

Move the call to free before a NULL test.

Check if this free is accessed after its argument has been test against NULL (property 0). If yes, it is legal to move this call in its predecessor block.

The move is performed only if the block containing the call to free will be removed, i.e.:

  1. it has only one predecessor P, and P has two successors
  2. it contains the call, noops, and an unconditional branch
  3. its successor is the same as its predecessor's successor

The profitability is out-of concern here and this function should be called only if the caller knows this transformation would be profitable (e.g., for code size).

Definition at line 2363 of file InstructionCombining.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::dyn_cast(), llvm::CallBase::getArgOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_UnconditionalBr(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), llvm::BasicBlock::size(), and llvm::Value::stripPointerCasts().

Referenced by llvm::InstCombiner::visitFree().

◆ TryToSinkInstruction()

static bool TryToSinkInstruction ( Instruction I,
BasicBlock DestBlock 

Variable Documentation

◆ EnableCodeSinking

cl::opt<bool> EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"), cl::init(true))

Referenced by llvm::InstCombiner::run().

◆ EnableExpensiveCombines

cl::opt<bool> EnableExpensiveCombines("expensive-combines", cl::desc("Enable expensive instruction combines"))

◆ false

Combine redundant false

Definition at line 3546 of file InstructionCombining.cpp.

◆ instcombine


Definition at line 3546 of file InstructionCombining.cpp.

◆ instructions

Combine redundant instructions

Definition at line 3546 of file InstructionCombining.cpp.

◆ MaxArraySize

cl::opt<unsigned> MaxArraySize("instcombine-maxarray-size", cl::init(1024), cl::desc("Maximum array size considered when doing a combine"))

◆ ShouldLowerDbgDeclare

cl::opt<unsigned> ShouldLowerDbgDeclare("instcombine-lower-dbg-declare", cl::Hidden, cl::init(true))