LLVM API Documentation

InstructionCombining.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <iostream>

Include dependency graph for InstructionCombining.cpp:

Go to the source code of this file.

Classes

struct  AddRHS
struct  AddMaskingAnd
struct  FoldSetCCLogical
struct  XorSelf

Defines

#define DEBUG_TYPE   "instcombine"

Enumerations

enum  CastType { Noop = 0, Truncate = 1, Signext = 2, Zeroext = 3 }

Functions

static unsigned getComplexity (Value *V)
static bool isOnlyUse (Value *V)
static const TypegetPromotedType (const Type *Ty)
static ValueisCast (Value *V)
static Valuedyn_castNegVal (Value *V)
static Valuedyn_castNotVal (Value *V)
static Valuedyn_castFoldableMul (Value *V, ConstantInt *&CST)
static Userdyn_castGetElementPtr (Value *V)
static ConstantIntAddOne (ConstantInt *C)
static ConstantIntSubOne (ConstantInt *C)
static ConstantIntegralGetConstantInType (const Type *Ty, uint64_t Val)
static void ComputeMaskedBits (Value *V, uint64_t Mask, uint64_t &KnownZero, uint64_t &KnownOne, unsigned Depth=0)
static bool MaskedValueIsZero (Value *V, uint64_t Mask, unsigned Depth=0)
static bool ShrinkDemandedConstant (Instruction *I, unsigned OpNo, uint64_t Demanded)
static void ComputeSignedMinMaxValuesFromKnownBits (const Type *Ty, uint64_t KnownZero, uint64_t KnownOne, int64_t &Min, int64_t &Max)
static void ComputeUnsignedMinMaxValuesFromKnownBits (const Type *Ty, uint64_t KnownZero, uint64_t KnownOne, uint64_t &Min, uint64_t &Max)
static bool isTrueWhenEqual (Instruction &I)
template<typename Functor>
InstructionAssociativeOpt (BinaryOperator &Root, const Functor &F)
static ValueFoldOperationIntoSelectOperand (Instruction &I, Value *SO, InstCombiner *IC)
static InstructionFoldOpIntoSelect (Instruction &Op, SelectInst *SI, InstCombiner *IC)
static bool isSignBit (ConstantInt *CI)
static ValueRemoveNoopCast (Value *V)
static bool isSignBitCheck (unsigned Opcode, Value *LHS, ConstantInt *RHS)
static ConstantGetFactor (Value *V)
static bool isMaxValueMinusOne (const ConstantInt *C)
static bool isMinValuePlusOne (const ConstantInt *C)
static bool isOneBitSet (const ConstantInt *CI)
static bool isHighOnes (const ConstantInt *CI)
static unsigned getSetCondCode (const SetCondInst *SCI)
static ValuegetSetCCValue (unsigned Opcode, Value *LHS, Value *RHS)
static bool isRunOfOnes (ConstantIntegral *Val, unsigned &MB, unsigned &ME)
static bool MulWithOverflow (ConstantInt *&Result, ConstantInt *In1, ConstantInt *In2)
static bool isPositive (ConstantInt *C)
static bool AddWithOverflow (ConstantInt *&Result, ConstantInt *In1, ConstantInt *In2)
static ValueEmitGEPOffset (User *GEP, Instruction &I, InstCombiner &IC)
static CastType getCastType (const Type *Src, const Type *Dest)
static bool isEliminableCastOfCast (const Type *SrcTy, const Type *MidTy, const Type *DstTy, TargetData *TD)
static bool ValueRequiresCast (const Value *V, const Type *Ty, TargetData *TD)
static ValueDecomposeSimpleLinearExpr (Value *Val, unsigned &Scale, unsigned &Offset)
static unsigned GetSelectFoldableOperands (Instruction *I)
static ConstantGetSelectFoldableConstant (Instruction *I)
static unsigned GetKnownAlignment (Value *V, TargetData *TD)
static bool DeadPHICycle (PHINode *PN, std::set< PHINode * > &PotentiallyDeadPHIs)
static ValueInsertSignExtendToPtrTy (Value *V, const Type *DTy, Instruction *InsertPoint, InstCombiner *IC)
static InstructionInstCombineLoadCast (InstCombiner &IC, LoadInst &LI)
 InstCombineLoadCast - Fold 'load (cast P)' -> cast (load P)' when possible.
static bool isSafeToLoadUnconditionally (Value *V, Instruction *ScanFrom)
static InstructionInstCombineStoreToCast (InstCombiner &IC, StoreInst &SI)
static bool CheapToScalarize (Value *V, bool isConstant)
static ValueFindScalarElement (Value *V, unsigned EltNo)
static bool TryToSinkInstruction (Instruction *I, BasicBlock *DestBlock)
FunctionPassllvm::createInstructionCombiningPass ()

Variables

Statistic NumCombined ("instcombine","Number of insts combined")
Statistic NumConstProp ("instcombine","Number of constant folds")
Statistic NumDeadInst ("instcombine","Number of dead inst eliminated")
Statistic NumDeadStore ("instcombine","Number of dead stores eliminated")
Statistic NumSunkInst ("instcombine","Number of instructions sunk")
std::vector< Instruction * > WorkList
TargetDataTD
RegisterOpt< InstCombiner > X ("instcombine","Combine redundant instructions")


Define Documentation

#define DEBUG_TYPE   "instcombine"

Definition at line 36 of file InstructionCombining.cpp.


Enumeration Type Documentation

enum CastType

Enumerator:
Noop 
Truncate 
Signext 
Zeroext 

Definition at line 4455 of file InstructionCombining.cpp.


Function Documentation

static ConstantInt* AddOne ( ConstantInt C  )  [static]

Definition at line 408 of file InstructionCombining.cpp.

References llvm::CallingConv::C.

Referenced by llvm::SCEVAddExpr::get().

static bool AddWithOverflow ( ConstantInt *&  Result,
ConstantInt In1,
ConstantInt In2 
) [static]

AddWithOverflow - Compute Result = In1+In2, returning true if the result overflowed for this type.

Definition at line 3045 of file InstructionCombining.cpp.

References llvm::Value::getType(), isPositive(), and llvm::Type::isUnsigned().

template<typename Functor>
Instruction* AssociativeOpt ( BinaryOperator Root,
const Functor &  F 
)

AssociativeOpt - Perform an optimization on an associative operator. This function is designed to check a chain of associative operators for a potential to apply a certain optimization. Since the optimization may be applicable if the expression was reassociated, this checks the chain, then reassociates the expression as necessary to expose the optimization opportunity. This makes use of a special Functor, which must define 'shouldApply' and 'apply' methods.

Definition at line 1028 of file InstructionCombining.cpp.

References BB, llvm::BasicBlock::getInstList(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::Value::getType(), llvm::Value::hasOneUse(), llvm::Value::replaceAllUsesWith(), Root, and llvm::User::setOperand().

static bool CheapToScalarize ( Value V,
bool  isConstant 
) [static]

CheapToScalarize - Return true if the value is cheaper to scalarize than it is to leave as a vector operation.

Definition at line 6768 of file InstructionCombining.cpp.

References llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::hasOneUse(), llvm::InsertElement, Load, and V.

static void ComputeMaskedBits ( Value V,
uint64_t  Mask,
uint64_t &  KnownZero,
uint64_t &  KnownOne,
unsigned  Depth = 0 
) [static]

ComputeMaskedBits - Determine which of the bits specified in Mask are known to be either zero or one and return them in the KnownZero/KnownOne bitsets. This code only analyzes bits in Mask, in order to short-circuit processing.

Definition at line 435 of file InstructionCombining.cpp.

References llvm::Type::getIntegralTypeMask(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::Type::isIntegral(), llvm::Type::isSigned(), llvm::Type::isUnsigned(), llvm::Select, and V.

Referenced by MaskedValueIsZero().

static void ComputeSignedMinMaxValuesFromKnownBits ( const Type Ty,
uint64_t  KnownZero,
uint64_t  KnownOne,
int64_t &  Min,
int64_t &  Max 
) [static]

Definition at line 634 of file InstructionCombining.cpp.

References llvm::Type::getIntegralTypeMask(), llvm::Type::getPrimitiveSizeInBits(), and Ty.

static void ComputeUnsignedMinMaxValuesFromKnownBits ( const Type Ty,
uint64_t  KnownZero,
uint64_t  KnownOne,
uint64_t &  Min,
uint64_t &  Max 
) [static]

Definition at line 663 of file InstructionCombining.cpp.

References llvm::Type::getIntegralTypeMask(), and Ty.

static bool DeadPHICycle ( PHINode PN,
std::set< PHINode * > &  PotentiallyDeadPHIs 
) [static]

DeadPHICycle - Return true if this PHI node is only used by a PHI node cycle that is dead.

Definition at line 5862 of file InstructionCombining.cpp.

References llvm::Value::hasOneUse(), llvm::Value::use_back(), and llvm::Value::use_empty().

static Value* DecomposeSimpleLinearExpr ( Value Val,
unsigned &  Scale,
unsigned &  Offset 
) [static]

DecomposeSimpleLinearExpr - Analyze 'Val', seeing if it is a simple linear expression. If so, decompose it, returning some value X, such that Val is X*Scale+Offset.

Definition at line 4581 of file InstructionCombining.cpp.

References llvm::Value::getType(), llvm::ConstantUInt::getValue(), U, and Val.

static Value* dyn_castFoldableMul ( Value V,
ConstantInt *&  CST 
) [inline, static]

Definition at line 380 of file InstructionCombining.cpp.

References llvm::BinaryOperator::getOpcode(), llvm::BinaryOperator::getOperand(), and V.

static User* dyn_castGetElementPtr ( Value V  )  [static]

dyn_castGetElementPtr - If this is a getelementptr instruction or constant expression, return it.

Definition at line 399 of file InstructionCombining.cpp.

References V.

static Value* dyn_castNegVal ( Value V  )  [inline, static]

Definition at line 355 of file InstructionCombining.cpp.

References llvm::CallingConv::C, and V.

static Value* dyn_castNotVal ( Value V  )  [inline, static]

Definition at line 365 of file InstructionCombining.cpp.

References llvm::CallingConv::C, and V.

static Value* EmitGEPOffset ( User GEP,
Instruction I,
InstCombiner &  IC 
) [static]

EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from the base pointer (without adding in the base pointer). Return the result as a signed integer of intptr size.

Definition at line 3064 of file InstructionCombining.cpp.

References llvm::gep_type_begin(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::TargetData::getIntPtrType(), llvm::Value::getName(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::TargetData::getPointerSize(), llvm::Type::getSignedVersion(), llvm::TargetData::getTypeSize(), RC, Scale, TD, and UIntPtrTy.

static Value* FindScalarElement ( Value V,
unsigned  EltNo 
) [static]

FindScalarElement - Given a vector and an element number, see if the scalar value is already around as a register, for example if it were inserted then extracted from the vector.

Definition at line 6802 of file InstructionCombining.cpp.

References CP, llvm::SequentialType::getElementType(), llvm::PackedType::getNumElements(), llvm::Constant::getOperand(), and V.

static Value* FoldOperationIntoSelectOperand ( Instruction I,
Value SO,
InstCombiner *  IC 
) [static]

Definition at line 1126 of file InstructionCombining.cpp.

References abort().

Referenced by FoldOpIntoSelect().

static Instruction* FoldOpIntoSelect ( Instruction Op,
SelectInst SI,
InstCombiner *  IC 
) [static]

Definition at line 1165 of file InstructionCombining.cpp.

References FoldOperationIntoSelectOperand(), llvm::SelectInst::getCondition(), llvm::SelectInst::getOperand(), llvm::Value::getType(), llvm::Value::hasOneUse(), and Op.

static CastType getCastType ( const Type Src,
const Type Dest 
) [static]

getCastType - In the future, we will split the cast instruction into these various types. Until then, we have to do the analysis here.

Definition at line 4464 of file InstructionCombining.cpp.

References Dest, Noop, Signext, Src, Truncate, and Zeroext.

Referenced by isEliminableCastOfCast().

static unsigned getComplexity ( Value V  )  [static]

Definition at line 266 of file InstructionCombining.cpp.

References V.

static ConstantIntegral* GetConstantInType ( const Type Ty,
uint64_t  Val 
) [static]

GetConstantInType - Return a ConstantInt with the specified type and value.

Definition at line 419 of file InstructionCombining.cpp.

References llvm::Type::isUnsigned(), and Ty.

Referenced by ShrinkDemandedConstant().

static Constant* GetFactor ( Value V  )  [static]

GetFactor - If we can prove that the specified value is at least a multiple of some factor, return that factor.

Definition at line 1834 of file InstructionCombining.cpp.

References llvm::CountTrailingZeros_64(), llvm::Value::getType(), Op, and V.

static unsigned GetKnownAlignment ( Value V,
TargetData TD 
) [static]

GetKnownAlignment - If the specified pointer has an alignment that we can determine, return it, otherwise return 0.

Definition at line 5343 of file InstructionCombining.cpp.

References Align, llvm::GlobalValue::getAlignment(), llvm::SequentialType::getElementType(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Value::getType(), llvm::GlobalValue::getType(), llvm::TargetData::getTypeAlignment(), GV, TD, and V.

static const Type* getPromotedType ( const Type Ty  )  [static]

Definition at line 284 of file InstructionCombining.cpp.

References llvm::Type::getTypeID(), and Ty.

static Constant* GetSelectFoldableConstant ( Instruction I  )  [static]

GetSelectFoldableConstant - For the same transformation as the previous function, return the identity constant that goes into the select.

Definition at line 5007 of file InstructionCombining.cpp.

References abort(), llvm::Instruction::getOpcode(), and llvm::Value::getType().

static unsigned GetSelectFoldableOperands ( Instruction I  )  [static]

GetSelectFoldableOperands - We want to turn code that looks like this: C = or A, B D = select cond, C, A into: C = select cond, B, 0 D = or A, C

Assuming that the specified instruction is an operand to the select, return a bitmask indicating which operands of this instruction are foldable if they equal the other incoming value of the select.

Definition at line 4988 of file InstructionCombining.cpp.

References llvm::Instruction::getOpcode().

static Value* getSetCCValue ( unsigned  Opcode,
Value LHS,
Value RHS 
) [static]

getSetCCValue - This is the complement of getSetCondCode, which turns an opcode and two operands into either a constant true or false, or a brand new SetCC instruction.

Definition at line 2071 of file InstructionCombining.cpp.

References False, and True.

Referenced by FoldSetCCLogical::apply().

static unsigned getSetCondCode ( const SetCondInst SCI  )  [static]

getSetCondCode - Encode a setcc opcode into a three bit mask. These bits are carefully arranged to allow folding of expressions such as:

(A < B) | (A > B) --> (A != B)

Bit value '4' represents that the comparison is true if A > B, bit value '2' represents that the comparison is true if A == B, and bit value '1' is true if A < B.

Definition at line 2052 of file InstructionCombining.cpp.

References llvm::BinaryOperator::getOpcode().

Referenced by FoldSetCCLogical::apply().

static Value* InsertSignExtendToPtrTy ( Value V,
const Type DTy,
Instruction InsertPoint,
InstCombiner *  IC 
) [static]

Definition at line 5932 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSize(), llvm::Type::getSignedVersion(), llvm::Type::isSigned(), and V.

static Instruction* InstCombineLoadCast ( InstCombiner &  IC,
LoadInst LI 
) [static]

InstCombineLoadCast - Fold 'load (cast P)' -> cast (load P)' when possible.

Definition at line 6307 of file InstructionCombining.cpp.

References llvm::Value::getName(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::isInteger(), and LI.

static Instruction* InstCombineStoreToCast ( InstCombiner &  IC,
StoreInst SI 
) [static]

InstCombineStoreToCast - Fold 'store V, (cast P)' -> store (cast V), P' when possible.

Definition at line 6536 of file InstructionCombining.cpp.

References llvm::Value::getName(), llvm::User::getOperand(), llvm::StoreInst::getOperand(), llvm::Value::getType(), and llvm::Type::isInteger().

static Value* isCast ( Value V  )  [static]

isCast - If the specified operand is a CastInst or a constant expr cast, return the operand value, otherwise return null.

Definition at line 297 of file InstructionCombining.cpp.

References V.

static bool isEliminableCastOfCast ( const Type SrcTy,
const Type MidTy,
const Type DstTy,
TargetData TD 
) [static]

Definition at line 4480 of file InstructionCombining.cpp.

References getCastType(), llvm::TargetData::getIntPtrType(), llvm::Type::isLosslesslyConvertibleTo(), Noop, TD, and Truncate.

Referenced by ValueRequiresCast().

static bool isHighOnes ( const ConstantInt CI  )  [static]

Definition at line 2031 of file InstructionCombining.cpp.

References llvm::ConstantIntegral::getRawValue(), llvm::Value::getType(), and U.

static bool isMaxValueMinusOne ( const ConstantInt C  )  [static]

Definition at line 1982 of file InstructionCombining.cpp.

References llvm::CallingConv::C, llvm::ConstantSInt::getValue(), and INT64_MAX.

static bool isMinValuePlusOne ( const ConstantInt C  )  [static]

Definition at line 1996 of file InstructionCombining.cpp.

References llvm::CallingConv::C, and llvm::ConstantSInt::getValue().

static bool isOneBitSet ( const ConstantInt CI  )  [static]

Definition at line 2011 of file InstructionCombining.cpp.

References llvm::ConstantIntegral::getRawValue(), and V.

static bool isOnlyUse ( Value V  )  [static]

Definition at line 278 of file InstructionCombining.cpp.

References V.

static bool isPositive ( ConstantInt C  )  [static]

Definition at line 3039 of file InstructionCombining.cpp.

References llvm::CallingConv::C.

Referenced by AddWithOverflow().

static bool isRunOfOnes ( ConstantIntegral Val,
unsigned &  MB,
unsigned &  ME 
) [static]

Definition at line 2304 of file InstructionCombining.cpp.

References llvm::CountLeadingZeros_64(), llvm::isShiftedMask_64(), V, and Val.

static bool isSafeToLoadUnconditionally ( Value V,
Instruction ScanFrom 
) [static]

isSafeToLoadUnconditionally - Return true if we know that executing a load from this value cannot trap. If it is not obviously safe to load from the specified pointer, we do a quick local scan of the basic block containing ScanFrom, to determine if the address is already accessed.

Definition at line 6355 of file InstructionCombining.cpp.

References llvm::BasicBlock::begin(), E, llvm::Instruction::getParent(), LI, and V.

static bool isSignBit ( ConstantInt CI  )  [static]

Definition at line 1397 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSizeInBits(), llvm::ConstantIntegral::getRawValue(), and llvm::Value::getType().

static bool isSignBitCheck ( unsigned  Opcode,
Value LHS,
ConstantInt RHS 
) [static]

isSignBitCheck - Given an exploded setcc instruction, return true if it is really just returns true if the most significant (sign) bit is set.

Definition at line 1570 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::ConstantUInt::getValue(), llvm::ConstantIntegral::isAllOnesValue(), llvm::ConstantInt::isNullValue(), and llvm::Type::isSigned().

static bool isTrueWhenEqual ( Instruction I  )  [static]

Definition at line 1013 of file InstructionCombining.cpp.

References llvm::Instruction::getOpcode().

static bool MaskedValueIsZero ( Value V,
uint64_t  Mask,
unsigned  Depth = 0 
) [static]

MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use this predicate to simplify operations downstream. Mask is known to be zero for bits that V cannot have.

Definition at line 604 of file InstructionCombining.cpp.

References ComputeMaskedBits(), and V.

static bool MulWithOverflow ( ConstantInt *&  Result,
ConstantInt In1,
ConstantInt In2 
) [static]

MulWithOverflow - Compute Result = In1*In2, returning true if the result overflowed for this type.

Definition at line 3033 of file InstructionCombining.cpp.

References llvm::ConstantInt::isNullValue().

static Value* RemoveNoopCast ( Value V  )  [static]

RemoveNoopCast - Strip off nonconverting casts from the value.

Definition at line 1404 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::Type::isInteger(), and V.

static bool ShrinkDemandedConstant ( Instruction I,
unsigned  OpNo,
uint64_t  Demanded 
) [static]

ShrinkDemandedConstant - Check to see if the specified operand of the specified instruction is a constant integer. If so, check to see if there are any bits set in the constant that are not demanded. If so, shrink the constant and return true.

Definition at line 615 of file InstructionCombining.cpp.

References GetConstantInType(), llvm::User::getOperand(), llvm::Value::getType(), llvm::ConstantIntegral::getZExtValue(), llvm::User::setOperand(), and Val.

static ConstantInt* SubOne ( ConstantInt C  )  [static]

Definition at line 412 of file InstructionCombining.cpp.

References llvm::CallingConv::C.

static bool TryToSinkInstruction ( Instruction I,
BasicBlock DestBlock 
) [static]

TryToSinkInstruction - 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.

Definition at line 6990 of file InstructionCombining.cpp.

References llvm::BasicBlock::begin(), E, llvm::Function::front(), llvm::BasicBlock::getParent(), llvm::Value::hasOneUse(), InsertPos, and NumSunkInst.

static bool ValueRequiresCast ( const Value V,
const Type Ty,
TargetData TD 
) [static]

Definition at line 4553 of file InstructionCombining.cpp.

References isEliminableCastOfCast(), TD, Ty, and V.


Variable Documentation

Statistic NumCombined("instcombine","Number of insts combined") [static]

Statistic NumConstProp("instcombine","Number of constant folds") [static]

Statistic NumDeadInst("instcombine","Number of dead inst eliminated") [static]

Statistic NumDeadStore("instcombine","Number of dead stores eliminated") [static]

Statistic NumSunkInst("instcombine","Number of instructions sunk") [static]

Referenced by TryToSinkInstruction().

TargetData* TD

Definition at line 70 of file InstructionCombining.cpp.

std::vector<Instruction*> WorkList

Definition at line 69 of file InstructionCombining.cpp.

RegisterOpt<InstCombiner> X("instcombine","Combine redundant instructions") [static]