LLVM API Documentation
#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 Type * | getPromotedType (const Type *Ty) |
static Value * | isCast (Value *V) |
static Value * | dyn_castNegVal (Value *V) |
static Value * | dyn_castNotVal (Value *V) |
static Value * | dyn_castFoldableMul (Value *V, ConstantInt *&CST) |
static User * | dyn_castGetElementPtr (Value *V) |
static ConstantInt * | AddOne (ConstantInt *C) |
static ConstantInt * | SubOne (ConstantInt *C) |
static ConstantIntegral * | GetConstantInType (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> | |
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 | isSignBit (ConstantInt *CI) |
static Value * | RemoveNoopCast (Value *V) |
static bool | isSignBitCheck (unsigned Opcode, Value *LHS, ConstantInt *RHS) |
static Constant * | GetFactor (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 Value * | getSetCCValue (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 Value * | EmitGEPOffset (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 Value * | DecomposeSimpleLinearExpr (Value *Val, unsigned &Scale, unsigned &Offset) |
static unsigned | GetSelectFoldableOperands (Instruction *I) |
static Constant * | GetSelectFoldableConstant (Instruction *I) |
static unsigned | GetKnownAlignment (Value *V, TargetData *TD) |
static bool | DeadPHICycle (PHINode *PN, std::set< PHINode * > &PotentiallyDeadPHIs) |
static Value * | InsertSignExtendToPtrTy (Value *V, const Type *DTy, Instruction *InsertPoint, InstCombiner *IC) |
static Instruction * | InstCombineLoadCast (InstCombiner &IC, LoadInst &LI) |
InstCombineLoadCast - Fold 'load (cast P)' -> cast (load P)' when possible. | |
static bool | isSafeToLoadUnconditionally (Value *V, Instruction *ScanFrom) |
static Instruction * | InstCombineStoreToCast (InstCombiner &IC, StoreInst &SI) |
static bool | CheapToScalarize (Value *V, bool isConstant) |
static Value * | FindScalarElement (Value *V, unsigned EltNo) |
static bool | TryToSinkInstruction (Instruction *I, BasicBlock *DestBlock) |
FunctionPass * | llvm::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 |
TargetData * | TD |
RegisterOpt< InstCombiner > | X ("instcombine","Combine redundant instructions") |
#define DEBUG_TYPE "instcombine" |
Definition at line 36 of file InstructionCombining.cpp.
enum CastType |
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().
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.
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.
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* 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.
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.
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] |
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().
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.
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().
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.
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().
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] |
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().
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] |
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.
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().
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] |