LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
#include <algorithm>

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 Valuedyn_castNegVal (Value *V)
static Valuedyn_castNotVal (Value *V)
static Valuedyn_castFoldableMul (Value *V, ConstantInt *&CST)
static unsigned Log2 (uint64_t Val)
static ConstantIntAddOne (ConstantInt *C)
static ConstantIntSubOne (ConstantInt *C)
static bool isTrueWhenEqual (Instruction &I)
template<typename Functor>
InstructionAssociativeOpt (BinaryOperator &Root, const Functor &F)
static ValueFoldOperationIntoSelectOperand (Instruction &BI, Value *SO, InstCombiner *IC)
static InstructionFoldBinOpIntoSelect (Instruction &BI, SelectInst *SI, InstCombiner *IC)
static bool isSignBit (ConstantInt *CI)
static unsigned getTypeSizeInBits (const Type *Ty)
static ValueRemoveNoopCast (Value *V)
static bool isSignBitCheck (unsigned Opcode, Value *LHS, ConstantInt *RHS)
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 MulWithOverflow (ConstantInt *&Result, ConstantInt *In1, ConstantInt *In2)
static bool isPositive (ConstantInt *C)
static bool AddWithOverflow (ConstantInt *&Result, ConstantInt *In1, ConstantInt *In2)
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 unsigned GetSelectFoldableOperands (Instruction *I)
static ConstantGetSelectFoldableConstant (Instruction *I)
static ValueInsertSignExtendToPtrTy (Value *V, const Type *DTy, Instruction *InsertPoint, InstCombiner *IC)
static ConstantGetGEPGlobalInitializer (Constant *C, ConstantExpr *CE)
static InstructionInstCombineLoadCast (InstCombiner &IC, LoadInst &LI)
static bool isSafeToLoadUnconditionally (Value *V, Instruction *ScanFrom)
FunctionPassllvm::createInstructionCombiningPass ()


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


Function Documentation

static ConstantInt* AddOne ConstantInt C  )  [static]
 

Definition at line 362 of file InstructionCombining.cpp.

References llvm::Value::getType().

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

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

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

Definition at line 331 of file InstructionCombining.cpp.

References llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Value::hasOneUse(), llvm::Type::isInteger(), and Mul().

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

Definition at line 306 of file InstructionCombining.cpp.

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

Definition at line 316 of file InstructionCombining.cpp.

static Instruction* FoldBinOpIntoSelect Instruction BI,
SelectInst SI,
InstCombiner *  IC
[static]
 

Definition at line 559 of file InstructionCombining.cpp.

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

static Value* FoldOperationIntoSelectOperand Instruction BI,
Value SO,
InstCombiner *  IC
[static]
 

Definition at line 487 of file InstructionCombining.cpp.

References abort(), llvm::Instruction::getOpcode(), and llvm::User::getOperand().

Referenced by FoldBinOpIntoSelect().

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

References llvm::Type::getPrimitiveSize(), llvm::Type::isIntegral(), llvm::Type::isSigned(), Noop, Signext, Truncate, and Zeroext.

Referenced by isEliminableCastOfCast().

static unsigned getComplexity Value V  )  [static]
 

Definition at line 228 of file InstructionCombining.cpp.

References llvm::BinaryOperator::isNeg(), and llvm::BinaryOperator::isNot().

static Constant* GetGEPGlobalInitializer Constant C,
ConstantExpr CE
[static]
 

GetGEPGlobalInitializer - Given a constant, and a getelementptr constantexpr, return the constant value being addressed by the constant expression, or null if something is funny.

Definition at line 3924 of file InstructionCombining.cpp.

References E, llvm::gep_type_begin(), llvm::gep_type_end(), llvm::SequentialType::getElementType(), llvm::ArrayType::getNumElements(), llvm::ConstantExpr::getOperand(), llvm::Value::getType(), and llvm::ConstantUInt::getValue().

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

Definition at line 246 of file InstructionCombining.cpp.

References llvm::Type::DoubleTy, llvm::Type::FloatTyID, llvm::Type::getTypeID(), llvm::Type::IntTy, llvm::Type::SByteTyID, llvm::Type::ShortTyID, llvm::Type::UByteTyID, llvm::Type::UIntTy, and llvm::Type::UShortTyID.

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

References abort(), Add(), llvm::ISD::And, llvm::Instruction::getOpcode(), llvm::Value::getType(), Mul(), llvm::ISD::Or, and llvm::ISD::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 3002 of file InstructionCombining.cpp.

References Add(), llvm::ISD::And, llvm::Instruction::getOpcode(), Mul(), llvm::ISD::Or, and llvm::ISD::Xor.

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

References False, llvm::ISD::SetEQ, llvm::ISD::SetGE, llvm::ISD::SetGT, llvm::ISD::SetLE, llvm::ISD::SetLT, llvm::ISD::SetNE, 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 1116 of file InstructionCombining.cpp.

References llvm::BinaryOperator::getOpcode(), llvm::ISD::SetEQ, llvm::ISD::SetGE, llvm::ISD::SetGT, llvm::ISD::SetLE, llvm::ISD::SetLT, and llvm::ISD::SetNE.

Referenced by FoldSetCCLogical::apply().

static unsigned getTypeSizeInBits const Type Ty  )  [static]
 

Definition at line 685 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSize().

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

Definition at line 3603 of file InstructionCombining.cpp.

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

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

Definition at line 3962 of file InstructionCombining.cpp.

References llvm::Value::getName(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::isInteger(), llvm::Type::isSized(), and llvm::LoadInst::isVolatile().

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

Definition at line 2762 of file InstructionCombining.cpp.

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

Referenced by ValueRequiresCast().

static bool isHighOnes const ConstantInt CI  )  [static]
 

Definition at line 1096 of file InstructionCombining.cpp.

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

static bool isMaxValueMinusOne const ConstantInt C  )  [static]
 

Definition at line 1042 of file InstructionCombining.cpp.

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

static bool isMinValuePlusOne const ConstantInt C  )  [static]
 

Definition at line 1061 of file InstructionCombining.cpp.

References llvm::ConstantSInt::getValue().

static bool isOneBitSet const ConstantInt CI  )  [static]
 

Definition at line 1076 of file InstructionCombining.cpp.

References llvm::ConstantIntegral::getRawValue().

static bool isOnlyUse Value V  )  [static]
 

Definition at line 240 of file InstructionCombining.cpp.

References llvm::Value::hasOneUse().

static bool isPositive ConstantInt C  )  [static]
 

Definition at line 1849 of file InstructionCombining.cpp.

Referenced by AddWithOverflow().

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

References llvm::BasicBlock::begin(), E, llvm::User::getOperand(), and llvm::Instruction::getParent().

static bool isSignBit ConstantInt CI  )  [static]
 

Definition at line 680 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSize(), 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 831 of file InstructionCombining.cpp.

References llvm::Type::getPrimitiveSize(), llvm::Value::getType(), llvm::ConstantUInt::getValue(), llvm::ConstantIntegral::isAllOnesValue(), llvm::ConstantInt::isNullValue(), llvm::Type::isSigned(), llvm::ISD::SetGE, llvm::ISD::SetGT, llvm::ISD::SetLE, and llvm::ISD::SetLT.

static bool isTrueWhenEqual Instruction I  )  [static]
 

Definition at line 374 of file InstructionCombining.cpp.

References llvm::Instruction::getOpcode(), llvm::ISD::SetEQ, llvm::ISD::SetGE, and llvm::ISD::SetLE.

static unsigned Log2 uint64_t  Val  )  [static]
 

Definition at line 350 of file InstructionCombining.cpp.

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

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

static ConstantInt* SubOne ConstantInt C  )  [static]
 

Definition at line 366 of file InstructionCombining.cpp.

References llvm::Value::getType().

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

Definition at line 2822 of file InstructionCombining.cpp.

References llvm::Constant::getOperand(), llvm::Value::getType(), and isEliminableCastOfCast().


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]
 

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