LLVM API Documentation

InstructionCombining.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#include "llvm/Pass.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Operator.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/ValueTracking.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/ConstantRange.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <climits>
#include <sstream>

Include dependency graph for InstructionCombining.cpp:

Go to the source code of this file.

Defines

#define DEBUG_TYPE   "instcombine"

Functions

 STATISTIC (NumCombined,"Number of insts combined")
 STATISTIC (NumConstProp,"Number of constant folds")
 STATISTIC (NumDeadInst,"Number of dead inst eliminated")
 STATISTIC (NumDeadStore,"Number of dead stores eliminated")
 STATISTIC (NumSunkInst,"Number of instructions sunk")
static unsigned getComplexity (LLVMContext *Context, Value *V)
static bool isOnlyUse (Value *V)
static const Type * getPromotedType (const Type *Ty)
static Value * getBitCastOperand (Value *V)
static Instruction::CastOps isEliminableCastPair (const CastInst *CI, unsigned opcode, const Type *DstTy, TargetData *TD)
static bool ValueRequiresCast (Instruction::CastOps opcode, const Value *V, const Type *Ty, TargetData *TD)
static Value * dyn_castNegVal (Value *V)
static Value * dyn_castFNegVal (Value *V)
static Value * dyn_castNotVal (Value *V)
static Value * dyn_castFoldableMul (Value *V, ConstantInt *&CST)
static Constant * AddOne (Constant *C)
 AddOne - Add one to a ConstantInt.
static Constant * SubOne (ConstantInt *C)
 SubOne - Subtract one from a ConstantInt.
static bool MultiplyOverflows (ConstantInt *C1, ConstantInt *C2, bool sign)
static bool ShrinkDemandedConstant (Instruction *I, unsigned OpNo, APInt Demanded)
static void ComputeSignedMinMaxValuesFromKnownBits (const APInt &KnownZero, const APInt &KnownOne, APInt &Min, APInt &Max)
static void ComputeUnsignedMinMaxValuesFromKnownBits (const APInt &KnownZero, const APInt &KnownOne, APInt &Min, APInt &Max)
template<typename Functor>
static Instruction * AssociativeOpt (BinaryOperator &Root, const Functor &F)
static Value * FoldOperationIntoSelectOperand (Instruction &I, Value *SO, InstCombiner *IC)
static Instruction * FoldOpIntoSelect (Instruction &Op, SelectInst *SI, InstCombiner *IC)
static bool isSignBitCheck (ICmpInst::Predicate pred, ConstantInt *RHS, bool &TrueIfSigned)
static bool isOneBitSet (const ConstantInt *CI)
static bool isHighOnes (const ConstantInt *CI)
static unsigned getICmpCode (const ICmpInst *ICI)
static unsigned getFCmpCode (FCmpInst::Predicate CC, bool &isOrdered)
static Value * getICmpValue (bool sign, unsigned code, Value *LHS, Value *RHS, LLVMContext *Context)
static Value * getFCmpValue (bool isordered, unsigned code, Value *LHS, Value *RHS, LLVMContext *Context)
static bool PredicatesFoldable (ICmpInst::Predicate p1, ICmpInst::Predicate p2)
static bool isRunOfOnes (ConstantInt *Val, uint32_t &MB, uint32_t &ME)
static bool CollectBSwapParts (Value *V, int OverallLeftShift, uint32_t ByteMask, SmallVector< Value *, 8 > &ByteValues)
static Instruction * MatchSelectFromAndOr (Value *A, Value *B, Value *C, Value *D, LLVMContext *Context)
static ConstantInt * ExtractElement (Constant *V, Constant *Idx, LLVMContext *Context)
static bool HasAddOverflow (ConstantInt *Result, ConstantInt *In1, ConstantInt *In2, bool IsSigned)
static bool AddWithOverflow (Constant *&Result, Constant *In1, Constant *In2, LLVMContext *Context, bool IsSigned=false)
static bool HasSubOverflow (ConstantInt *Result, ConstantInt *In1, ConstantInt *In2, bool IsSigned)
static bool SubWithOverflow (Constant *&Result, Constant *In1, Constant *In2, LLVMContext *Context, bool IsSigned=false)
static Value * EmitGEPOffset (User *GEP, Instruction &I, InstCombiner &IC)
static Value * EvaluateGEPOffsetExpression (User *GEP, Instruction &I, InstCombiner &IC)
static Value * DecomposeSimpleLinearExpr (Value *Val, unsigned &Scale, int &Offset, LLVMContext *Context)
static const Type * FindElementAtOffset (const Type *Ty, int64_t Offset, SmallVectorImpl< Value * > &NewIndices, const TargetData *TD, LLVMContext *Context)
static bool isSafeIntegerType (const Type *Ty)
static Constant * FitsInFPType (ConstantFP *CFP, const fltSemantics &Sem, LLVMContext *Context)
static Value * LookThroughFPExtensions (Value *V, LLVMContext *Context)
static unsigned GetSelectFoldableOperands (Instruction *I)
static Constant * GetSelectFoldableConstant (Instruction *I, LLVMContext *Context)
static bool isSelect01 (Constant *C1, Constant *C2)
static unsigned EnforceKnownAlignment (Value *V, unsigned Align, unsigned PrefAlign)
static bool isSafeToEliminateVarargsCast (const CallSite CS, const CastInst *const CI, const TargetData *const TD, const int ix)
static bool isSafeAndProfitableToSinkLoad (LoadInst *L)
static bool DeadPHICycle (PHINode *PN, SmallPtrSet< PHINode *, 16 > &PotentiallyDeadPHIs)
static bool PHIsEqualValue (PHINode *PN, Value *NonPhiInVal, SmallPtrSet< PHINode *, 16 > &ValueEqualPHIs)
static Value * InsertCastToIntPtrTy (Value *V, const Type *DTy, Instruction *InsertPoint, InstCombiner *IC)
static Instruction * InstCombineLoadCast (InstCombiner &IC, LoadInst &LI, const TargetData *TD)
 InstCombineLoadCast - Fold 'load (cast P)' -> cast (load P)' when possible.
static Instruction * InstCombineStoreToCast (InstCombiner &IC, StoreInst &SI)
static bool equivalentAddressValues (Value *A, Value *B)
static bool CheapToScalarize (Value *V, bool isConstant)
static std::vector< unsigned > getShuffleMask (const ShuffleVectorInst *SVI)
static Value * FindScalarElement (Value *V, unsigned EltNo, LLVMContext *Context)
static bool CollectSingleShuffleElements (Value *V, Value *LHS, Value *RHS, std::vector< Constant * > &Mask, LLVMContext *Context)
static Value * CollectShuffleElements (Value *V, std::vector< Constant * > &Mask, Value *&RHS, LLVMContext *Context)
static bool TryToSinkInstruction (Instruction *I, BasicBlock *DestBlock)
static void AddReachableCodeToWorklist (BasicBlock *BB, SmallPtrSet< BasicBlock *, 64 > &Visited, InstCombiner &IC, const TargetData *TD)
FunctionPass * llvm::createInstructionCombiningPass ()

Variables

static RegisterPass< InstCombiner > X ("instcombine","Combine redundant instructions")


Define Documentation

#define DEBUG_TYPE   "instcombine"

Definition at line 36 of file InstructionCombining.cpp.


Function Documentation

static Constant* AddOne ( Constant *  C  )  [static]

AddOne - Add one to a ConstantInt.

Definition at line 634 of file InstructionCombining.cpp.

References llvm::Value::getType().

Referenced by llvm::ScalarEvolution::getAddExpr().

static void AddReachableCodeToWorklist ( BasicBlock *  BB,
SmallPtrSet< BasicBlock *, 64 > &  Visited,
InstCombiner &  IC,
const TargetData *  TD 
) [static]

AddReachableCodeToWorklist - 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 12901 of file InstructionCombining.cpp.

References llvm::SmallVectorImpl< T >::back(), llvm::BasicBlock::begin(), llvm::ConstantFoldInstruction(), llvm::Intrinsic::dbg_stoppoint, DOUT, llvm::dyn_cast(), E, llvm::SmallVectorImpl< T >::empty(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::SwitchInst::getCaseValue(), llvm::BranchInst::getCondition(), llvm::SwitchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::IntrinsicInst::getIntrinsicID(), llvm::SwitchInst::getNumSuccessors(), llvm::TerminatorInst::getNumSuccessors(), llvm::SwitchInst::getSuccessor(), llvm::TerminatorInst::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::BranchInst::isConditional(), llvm::isInstructionTriviallyDead(), llvm::SmallVectorImpl< T >::pop_back(), llvm::SmallVectorImpl< T >::push_back(), llvm::Value::replaceAllUsesWith(), and Worklist.

static bool AddWithOverflow ( Constant *&  Result,
Constant *  In1,
Constant *  In2,
LLVMContext *  Context,
bool  IsSigned = false 
) [static]

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

Definition at line 5333 of file InstructionCombining.cpp.

References ExtractElement(), llvm::VectorType::getNumElements(), llvm::Value::getType(), and HasAddOverflow().

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

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 1774 of file InstructionCombining.cpp.

References llvm::dyn_cast(), llvm::Instruction::getOpcode(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Value::hasOneUse(), llvm::Instruction::moveBefore(), llvm::Value::replaceAllUsesWith(), 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 12289 of file InstructionCombining.cpp.

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

static bool CollectBSwapParts ( Value *  V,
int  OverallLeftShift,
uint32_t  ByteMask,
SmallVector< Value *, 8 > &  ByteValues 
) [static]

CollectBSwapParts - Analyze the specified subexpression and see if it is capable of providing pieces of a bswap. The subexpression provides pieces of a bswap if it is proven that each of the non-zero bytes in the output of the expression came from the corresponding "byte swapped" byte in some other value. For example, if the current subexpression is "(shl i32 %X, 24)" then we know that the expression deposits the low byte of X into the high byte of the bswap result and that all other bytes are zero. This expression is accepted, the high byte of ByteValues is set to X to indicate a correct match.

This function returns true if the match was unsuccessful and false if so. On entry to the function the "OverallLeftShift" is a signed integer value indicating the number of bytes that the subexpression is later shifted. For example, if the expression is later right shifted by 16 bits, the OverallLeftShift value would be -2 on entry. This is used to specify which byte of ByteValues is actually being set.

Similarly, ByteMask is a bitmask where a bit is clear if its corresponding byte is masked to zero by a user. For example, in (X & 255), X will be processed with a bytemask of 1. Because bytemask is 32-bits, this limits this function to working on up to 32-byte (256 bit) values. ByteMask is always in the local (OverallLeftShift) coordinate space.

Definition at line 4327 of file InstructionCombining.cpp.

References llvm::APIntOps::And(), llvm::CountTrailingZeros_32(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::Instruction::isLogicalShift(), llvm::isPowerOf2_32(), llvm::APIntOps::Or(), and llvm::SmallVectorImpl< T >::size().

static Value* CollectShuffleElements ( Value *  V,
std::vector< Constant * > &  Mask,
Value *&  RHS,
LLVMContext *  Context 
) [static]

CollectShuffleElements - We are building a shuffle of V, using RHS as the RHS of the shuffle instruction, if it is not null. Return a shuffle mask that computes V and the LHS value of the shuffle.

Definition at line 12600 of file InstructionCombining.cpp.

References CollectSingleShuffleElements(), llvm::User::getOperand(), and llvm::Value::getType().

static bool CollectSingleShuffleElements ( Value *  V,
Value *  LHS,
Value *  RHS,
std::vector< Constant * > &  Mask,
LLVMContext *  Context 
) [static]

CollectSingleShuffleElements - If V is a shuffle of values that ONLY returns elements from either LHS or RHS, return the shuffle mask and true. Otherwise, return false.

Definition at line 12529 of file InstructionCombining.cpp.

References llvm::User::getOperand(), and llvm::Value::getType().

Referenced by CollectShuffleElements().

static void ComputeSignedMinMaxValuesFromKnownBits ( const APInt &  KnownZero,
const APInt &  KnownOne,
APInt &  Min,
APInt &  Max 
) [static]

static void ComputeUnsignedMinMaxValuesFromKnownBits ( const APInt &  KnownZero,
const APInt &  KnownOne,
APInt &  Min,
APInt &  Max 
) [static]

Definition at line 719 of file InstructionCombining.cpp.

References llvm::APInt::getBitWidth().

static bool DeadPHICycle ( PHINode *  PN,
SmallPtrSet< PHINode *, 16 > &  PotentiallyDeadPHIs 
) [static]

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

Definition at line 10863 of file InstructionCombining.cpp.

References llvm::Value::hasOneUse(), llvm::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::SmallPtrSetImpl::size(), llvm::Instruction::use_back(), and llvm::Value::use_empty().

static Value* DecomposeSimpleLinearExpr ( Value *  Val,
unsigned &  Scale,
int &  Offset,
LLVMContext *  Context 
) [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 7778 of file InstructionCombining.cpp.

References llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), and llvm::ConstantInt::getZExtValue().

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

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

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

Definition at line 565 of file InstructionCombining.cpp.

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

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

Definition at line 599 of file InstructionCombining.cpp.

References llvm::Value::getType().

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 5394 of file InstructionCombining.cpp.

References Context, llvm::gep_type_begin(), llvm::Value::getContext(), llvm::StructLayout::getElementOffset(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::TargetData::getIntPtrType(), llvm::Value::getName(), llvm::TargetData::getPointerSizeInBits(), llvm::TargetData::getStructLayout(), llvm::Value::getType(), llvm::TargetData::getTypeAllocSize(), llvm::User::op_begin(), llvm::User::op_end(), Scale, and TD.

static unsigned EnforceKnownAlignment ( Value *  V,
unsigned  Align,
unsigned  PrefAlign 
) [static]

EnforceKnownAlignment - If the specified pointer points to an object that we control, modify the object's alignment to PrefAlign. This isn't often possible though. If alignment is important, a more reliable approach is to simply align all global variables and allocation instructions to their preferred alignment from the beginning.

Definition at line 9609 of file InstructionCombining.cpp.

References BitCast, llvm::dyn_cast(), llvm::AllocationInst::getAlignment(), llvm::GlobalValue::getAlignment(), llvm::User::getOperand(), GV, llvm::GlobalValue::isDeclaration(), llvm::User::op_begin(), llvm::User::op_end(), llvm::AllocationInst::setAlignment(), and llvm::GlobalValue::setAlignment().

static bool equivalentAddressValues ( Value *  A,
Value *  B 
) [static]

equivalentAddressValues - Test if A and B will obviously have the same value. This includes recognizing that t0 and t1 will have the same value in code like this: t0 = getelementptr @a, 0, 3 store i32 0, i32* t0 t1 = getelementptr @a, 0, 3 t2 = load i32* t1

Definition at line 11813 of file InstructionCombining.cpp.

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

EvaluateGEPOffsetExpression - Return a value that can be used to compare the *offset* implied by a GEP to zero. For example, if we have &A[i], we want to return 'i' for "icmp ne i, 0". Note that, in general, indices can be complex, and scales are involved. The above expression would also be legal to codegen as "icmp ne (i*4), 0" (assuming A is a pointer to i32). This later form is less amenable to optimization though, and we are allowed to generate the first by knowing that pointer arithmetic doesn't overflow.

If we can't emit an optimized form for this expression, this returns null.

Definition at line 5482 of file InstructionCombining.cpp.

References llvm::dyn_cast(), llvm::gep_type_begin(), llvm::Value::getContext(), llvm::StructLayout::getElementOffset(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::TargetData::getIntPtrType(), llvm::Value::getName(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::TargetData::getPointerSizeInBits(), llvm::Type::getPrimitiveSizeInBits(), llvm::ConstantInt::getSExtValue(), llvm::TargetData::getStructLayout(), llvm::Value::getType(), llvm::TargetData::getTypeAllocSize(), llvm::ConstantInt::getZExtValue(), llvm::ConstantInt::isZero(), Offset, and TD.

static ConstantInt* ExtractElement ( Constant *  V,
Constant *  Idx,
LLVMContext *  Context 
) [static]

static const Type* FindElementAtOffset ( const Type *  Ty,
int64_t  Offset,
SmallVectorImpl< Value * > &  NewIndices,
const TargetData *  TD,
LLVMContext *  Context 
) [static]

FindElementAtOffset - Given a type and a constant offset, determine whether or not there is a sequence of GEP indices into the type that will land us at the specified offset. If so, fill them into NewIndices and return the resultant element type, otherwise return null.

Definition at line 8169 of file InstructionCombining.cpp.

References llvm::StructLayout::getElementContainingOffset(), llvm::StructLayout::getElementOffset(), llvm::TargetData::getIntPtrType(), llvm::StructLayout::getSizeInBytes(), llvm::TargetData::getStructLayout(), llvm::TargetData::getTypeAllocSize(), llvm::TargetData::getTypeSizeInBits(), llvm::Type::isSized(), and llvm::SmallVectorImpl< T >::push_back().

static Value* FindScalarElement ( Value *  V,
unsigned  EltNo,
LLVMContext *  Context 
) [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 12349 of file InstructionCombining.cpp.

References CP, llvm::SequentialType::getElementType(), llvm::VectorType::getNumElements(), llvm::Constant::getOperand(), getShuffleMask(), and llvm::Value::getType().

static Constant* FitsInFPType ( ConstantFP *  CFP,
const fltSemantics &  Sem,
LLVMContext *  Context 
) [static]

FitsInFPType - Return a Constant* for the specified FP constant if it fits in the specified FP type without changing its value.

Definition at line 8781 of file InstructionCombining.cpp.

References llvm::APFloat::convert(), F, and llvm::ConstantFP::getValueAPF().

Referenced by LookThroughFPExtensions().

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

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

static Value* getBitCastOperand ( Value *  V  )  [static]

getBitCastOperand - If the specified operand is a CastInst, a constant expression bitcast, or a GetElementPtrInst with all zero indices, return the operand value, otherwise return null.

Definition at line 446 of file InstructionCombining.cpp.

References BitCast, and llvm::SystemZCC::O.

static unsigned getComplexity ( LLVMContext *  Context,
Value *  V 
) [static]

Definition at line 415 of file InstructionCombining.cpp.

static unsigned getFCmpCode ( FCmpInst::Predicate  CC,
bool &  isOrdered 
) [static]

getFCmpCode - Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into a three bit mask. It also returns whether it is an ordered predicate by reference.

Definition at line 3355 of file InstructionCombining.cpp.

References llvm_unreachable.

static Value* getFCmpValue ( bool  isordered,
unsigned  code,
Value *  LHS,
Value *  RHS,
LLVMContext *  Context 
) [static]

getFCmpValue - This is the complement of getFCmpCode, which turns an opcode and two operands into either a FCmp instruction. isordered is passed in to determine which kind of predicate to use in the new fcmp instruction.

Definition at line 3418 of file InstructionCombining.cpp.

References llvm_unreachable.

static unsigned getICmpCode ( const ICmpInst *  ICI  )  [static]

getICmpCode - Encode a icmp predicate into a three bit mask. These bits are carefully arranged to allow folding of expressions such as:

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

Note that this is only valid if the first and second predicates have the same sign. Is illegal to do: (A u< B) | (A s> B)

Three bits are used to represent the condition, as follows: 0 A > B 1 A == B 2 A < B

<=> Value Definition 000 0 Always false 001 1 A > B 010 2 A == B 011 3 A >= B 100 4 A < B 101 5 A != B 110 6 A <= B 111 7 Always true

Definition at line 3332 of file InstructionCombining.cpp.

References llvm::CmpInst::getPredicate(), and llvm_unreachable.

static Value* getICmpValue ( bool  sign,
unsigned  code,
Value *  LHS,
Value *  RHS,
LLVMContext *  Context 
) [static]

getICmpValue - This is the complement of getICmpCode, which turns an opcode and two operands into either a constant true or false, or a brand new ICmp instruction. The sign is passed in to determine which kind of predicate to use in the new icmp instruction.

Definition at line 3384 of file InstructionCombining.cpp.

References llvm_unreachable.

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

Definition at line 435 of file InstructionCombining.cpp.

References llvm::Type::getContext().

static Constant* GetSelectFoldableConstant ( Instruction *  I,
LLVMContext *  Context 
) [static]

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

Definition at line 9092 of file InstructionCombining.cpp.

References llvm::APIntOps::And(), llvm::Instruction::getOpcode(), llvm::Value::getType(), llvm_unreachable, LShr, llvm::APIntOps::Or(), and llvm::APIntOps::Xor().

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 9072 of file InstructionCombining.cpp.

References llvm::APIntOps::And(), llvm::Instruction::getOpcode(), LShr, llvm::APIntOps::Or(), and llvm::APIntOps::Xor().

static std::vector<unsigned> getShuffleMask ( const ShuffleVectorInst *  SVI  )  [static]

Read and decode a shufflevector mask.

It turns undef elements into values that are larger than the number of elements in the input.

Definition at line 12329 of file InstructionCombining.cpp.

References CP, llvm::VectorType::getNumElements(), llvm::User::getOperand(), llvm::ShuffleVectorInst::getType(), llvm::User::op_begin(), and llvm::User::op_end().

Referenced by FindScalarElement().

static bool HasAddOverflow ( ConstantInt *  Result,
ConstantInt *  In1,
ConstantInt *  In2,
bool  IsSigned 
) [static]

static bool HasSubOverflow ( ConstantInt *  Result,
ConstantInt *  In1,
ConstantInt *  In2,
bool  IsSigned 
) [static]

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

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

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

InstCombineStoreToCast - Fold store V, (cast P) -> store (cast V), P when possible. This makes it generally easy to do alias analysis and/or SROA/mem2reg of the memory object.

NewGEPIndices - If SrcPTy is an aggregate type, we can emit a "noop gep" to its first element. This allows us to handle things like: store i32 xxx, (bitcast {foo*, float}* P to i32*) on 32-bit hosts.

Definition at line 11711 of file InstructionCombining.cpp.

References llvm::SmallVectorImpl< T >::begin(), BitCast, llvm::dyn_cast(), llvm::SmallVectorImpl< T >::empty(), llvm::SmallVectorImpl< T >::end(), llvm::PointerType::getAddressSpace(), llvm::SequentialType::getElementType(), llvm::Value::getName(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::isInteger(), PtrToInt, llvm::SmallVectorImpl< T >::push_back(), and llvm::SmallVectorImpl< T >::size().

static Instruction::CastOps isEliminableCastPair ( const CastInst *  CI,
unsigned  opcode,
const Type *  DstTy,
TargetData *  TD 
) [static]

This function is a wrapper around CastInst::isEliminableCastPair. It simply extracts arguments and returns what that function returns.

Parameters:
CI  The first cast instruction
opcode  The opcode of the second cast instruction
DstTy  The target type for the second cast instruction
TD  The target data for pointer size

Definition at line 460 of file InstructionCombining.cpp.

References llvm::Value::getContext(), llvm::TargetData::getIntPtrType(), llvm::CastInst::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), and PtrToInt.

Referenced by foldConstantCastPair(), and ValueRequiresCast().

static bool isHighOnes ( const ConstantInt *  CI  )  [static]

Definition at line 3305 of file InstructionCombining.cpp.

References llvm::ConstantInt::getValue().

static bool isOneBitSet ( const ConstantInt *  CI  )  [static]

static bool isOnlyUse ( Value *  V  )  [static]

Definition at line 429 of file InstructionCombining.cpp.

References llvm::Value::hasOneUse().

static bool isRunOfOnes ( ConstantInt *  Val,
uint32_t &  MB,
uint32_t &  ME 
) [static]

static bool isSafeAndProfitableToSinkLoad ( LoadInst *  L  )  [static]

isSafeAndProfitableToSinkLoad - Return true if we know that it is safe to sink the load out of the block that defines it. This means that it must be obvious the value of the load is not changed from the point of the load to the end of the block it is in.

Finally, it is safe, but not profitable, to sink a load targetting a non-address-taken alloca. Doing so will cause us to not promote the alloca to a register.

Definition at line 10702 of file InstructionCombining.cpp.

References E, llvm::BasicBlock::end(), llvm::User::getOperand(), llvm::Instruction::getParent(), and llvm::GetElementPtrInst::hasAllConstantIndices().

static bool isSafeIntegerType ( const Type *  Ty  )  [static]

isSafeIntegerType - Return true if this is a basic integer type, not a crazy type like i42. We don't want to introduce operations on random non-legal integer types where they don't already exist in the code. In the future, we should consider making this based off target-data, so that 32-bit targets won't get i64 operations etc.

Definition at line 8288 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSizeInBits().

static bool isSafeToEliminateVarargsCast ( const CallSite  CS,
const CastInst *const   CI,
const TargetData *const   TD,
const int  ix 
) [static]

isSafeToEliminateVarargsCast - If this cast does not affect the value passed through the varargs area, we can eliminate the use of the cast.

Definition at line 10039 of file InstructionCombining.cpp.

References llvm::Attribute::ByVal, llvm::User::getOperand(), llvm::Value::getType(), llvm::TargetData::getTypeAllocSize(), llvm::CastInst::isLosslessCast(), llvm::Type::isSized(), and llvm::CallSite::paramHasAttr().

static bool isSelect01 ( Constant *  C1,
Constant *  C2 
) [static]

static bool isSignBitCheck ( ICmpInst::Predicate  pred,
ConstantInt *  RHS,
bool &  TrueIfSigned 
) [static]

isSignBitCheck - Given an exploded icmp instruction, return true if the comparison only checks the sign bit. If it only checks the sign bit, set TrueIfSigned if the result of the comparison is true when the input value is signed.

Definition at line 2588 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSizeInBits(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), llvm::ConstantInt::isAllOnesValue(), llvm::APInt::isSignBit(), and llvm::ConstantInt::isZero().

static Value* LookThroughFPExtensions ( Value *  V,
LLVMContext *  Context 
) [static]

LookThroughFPExtensions - If this is an fp extension instruction, look through it until we get the source value.

Definition at line 8793 of file InstructionCombining.cpp.

References FitsInFPType().

static Instruction* MatchSelectFromAndOr ( Value *  A,
Value *  B,
Value *  C,
Value *  D,
LLVMContext *  Context 
) [static]

MatchSelectFromAndOr - We have an expression of the form (A&C)|(B&D). Check If A is (cond?-1:0) and either B or D is ~(cond?-1,0) or (cond?0,-1), then we can simplify this expression to "cond ? C : D or B".

Definition at line 4467 of file InstructionCombining.cpp.

References llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

static bool MultiplyOverflows ( ConstantInt *  C1,
ConstantInt *  C2,
bool  sign 
) [static]

MultiplyOverflows - True if the multiply can not be expressed in an int this size.

Definition at line 645 of file InstructionCombining.cpp.

References llvm::ConstantInt::getBitWidth(), llvm::ConstantInt::getValue(), llvm::APInt::sext(), llvm::APInt::sgt(), llvm::APInt::slt(), llvm::APInt::ugt(), and llvm::APInt::zext().

static bool PHIsEqualValue ( PHINode *  PN,
Value *  NonPhiInVal,
SmallPtrSet< PHINode *, 16 > &  ValueEqualPHIs 
) [static]

PHIsEqualValue - Return true if this phi node is always equal to NonPhiInVal. This happens with mutually cyclic phi nodes like: z = some value; x = phi (y, z); y = phi (x, z)

Definition at line 10885 of file InstructionCombining.cpp.

References llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::SmallPtrSet< PtrType, SmallSize >::insert(), and llvm::SmallPtrSetImpl::size().

static bool PredicatesFoldable ( ICmpInst::Predicate  p1,
ICmpInst::Predicate  p2 
) [static]

PredicatesFoldable - Return true if both predicates match sign or if at least one of them is an equality comparison (which is signless).

Definition at line 3463 of file InstructionCombining.cpp.

static bool ShrinkDemandedConstant ( Instruction *  I,
unsigned  OpNo,
APInt  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 671 of file InstructionCombining.cpp.

References llvm::dyn_cast(), llvm::APInt::getBitWidth(), llvm::User::getOperand(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), llvm::User::setOperand(), and llvm::APInt::zextOrTrunc().

STATISTIC ( NumSunkInst  ,
"Number of instructions sunk"   
)

STATISTIC ( NumDeadStore  ,
"Number of dead stores eliminated"   
)

STATISTIC ( NumDeadInst  ,
"Number of dead inst eliminated"   
)

STATISTIC ( NumConstProp  ,
"Number of constant folds"   
)

STATISTIC ( NumCombined  ,
"Number of insts combined"   
)

static Constant* SubOne ( ConstantInt *  C  )  [static]

SubOne - Subtract one from a ConstantInt.

Definition at line 639 of file InstructionCombining.cpp.

References llvm::ConstantInt::getType().

static bool SubWithOverflow ( Constant *&  Result,
Constant *  In1,
Constant *  In2,
LLVMContext *  Context,
bool  IsSigned = false 
) [static]

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

Definition at line 5369 of file InstructionCombining.cpp.

References ExtractElement(), llvm::VectorType::getNumElements(), llvm::Value::getType(), and HasSubOverflow().

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 12862 of file InstructionCombining.cpp.

References llvm::CopyPrecedingStopPoint(), E, llvm::BasicBlock::end(), llvm::Function::getEntryBlock(), llvm::BasicBlock::getFirstNonPHI(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::Value::hasOneUse(), InsertPos, llvm::Instruction::mayHaveSideEffects(), llvm::Instruction::mayReadFromMemory(), and llvm::Instruction::moveBefore().

static bool ValueRequiresCast ( Instruction::CastOps  opcode,
const Value *  V,
const Type *  Ty,
TargetData *  TD 
) [static]

ValueRequiresCast - Return true if the cast from "V to Ty" actually results in any code being generated. It does not require codegen if V is simple enough or if the cast can be folded into other casts.

Definition at line 492 of file InstructionCombining.cpp.

References llvm::Value::getType(), and isEliminableCastPair().


Variable Documentation

InstCombiner& IC

char ID [static]

Definition at line 86 of file InstructionCombining.cpp.

Definition at line 84 of file InstructionCombining.cpp.

Definition at line 83 of file InstructionCombining.cpp.

Definition at line 82 of file InstructionCombining.cpp.

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