InstructionCombining.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "InstCombine.h"
#include "llvm-c/Initialization.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <climits>

Include dependency graph for InstructionCombining.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "instcombine"

Enumerations
enum	Personality_Type { Unknown_Personality, GNU_Ada_Personality, GNU_CXX_Personality, GNU_ObjC_Personality }

Functions
	STATISTIC (NumCombined,"Number of insts combined")
	STATISTIC (NumConstProp,"Number of constant folds")
	STATISTIC (NumDeadInst,"Number of dead inst eliminated")
	STATISTIC (NumSunkInst,"Number of instructions sunk")
	STATISTIC (NumExpand,"Number of expansions")
	STATISTIC (NumFactor,"Number of factorizations")
	STATISTIC (NumReassoc,"Number of reassociations")
void	LLVMInitializeInstCombine (LLVMPassRegistryRef R)
	INITIALIZE_PASS_BEGIN (InstCombiner,"instcombine","Combine redundant instructions", false, false) INITIALIZE_PASS_END(InstCombiner
static bool	MaintainNoSignedWrap (BinaryOperator &I, Value *B, Value *C)
static void	ClearSubclassDataAfterReassociation (BinaryOperator &I)
static bool	LeftDistributesOverRight (Instruction::BinaryOps LOp, Instruction::BinaryOps ROp)
static bool	RightDistributesOverLeft (Instruction::BinaryOps LOp, Instruction::BinaryOps ROp)
static Value *	FoldOperationIntoSelectOperand (Instruction &I, Value *SO, InstCombiner *IC)
static bool	shouldMergeGEPs (GEPOperator &GEP, GEPOperator &Src)
static bool	isAllocSiteRemovable (Instruction *AI, SmallVectorImpl< WeakVH > &Users, const TargetLibraryInfo *TLI)
static Instruction *	tryToMoveFreeBeforeNullTest (CallInst &FI)
	Move the call to free before a NULL test. More...
static Personality_Type	RecognizePersonality (Value *Pers)
static bool	isCatchAll (Personality_Type Personality, Constant *TypeInfo)
	isCatchAll - Return 'true' if the given typeinfo will match anything. More...
static bool	shorter_filter (const Value *LHS, const Value *RHS)
static bool	TryToSinkInstruction (Instruction *I, BasicBlock *DestBlock)
static bool	AddReachableCodeToWorklist (BasicBlock *BB, SmallPtrSet< BasicBlock *, 64 > &Visited, InstCombiner &IC, const DataLayout *TD, const TargetLibraryInfo *TLI)

Variables
static cl::opt< bool >	UnsafeFPShrink ("enable-double-float-shrink", cl::Hidden, cl::init(false), cl::desc("Enable unsafe double to float ""shrinking for math lib calls"))
	instcombine
Combine redundant	instructions
Combine redundant	false

Macro Definition Documentation

#define DEBUG_TYPE   "instcombine"

Definition at line 36 of file InstructionCombining.cpp.

Enumeration Type Documentation

enum Personality_Type

Enumerator
Unknown_Personality
GNU_Ada_Personality
GNU_CXX_Personality
GNU_ObjC_Personality

Definition at line 1827 of file InstructionCombining.cpp.

Function Documentation

static bool AddReachableCodeToWorklist ( BasicBlock *  BB, SmallPtrSet< BasicBlock *, 64 > &  Visited, InstCombiner &  IC, const DataLayout *  TD, const TargetLibraryInfo *  TLI  )

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

References llvm::InstCombineWorklist::AddInitialGroup(), llvm::BasicBlock::begin(), llvm::ConstantFoldConstantExpression(), llvm::ConstantFoldInstruction(), llvm::dbgs(), DEBUG, llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::SelectInst::getCondition(), llvm::BranchInst::getCondition(), llvm::TerminatorInst::getNumSuccessors(), llvm::User::getOperand(), llvm::TerminatorInst::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::BranchInst::isConditional(), llvm::isInstructionTriviallyDead(), llvm::User::op_begin(), llvm::User::op_end(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::Value::use_empty(), and llvm::InstCombiner::Worklist.

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

static void ClearSubclassDataAfterReassociation ( BinaryOperator &  I )

static

Conservatively clears subclassOptionalData after a reassociation or commutation. We preserve fast-math flags when applicable as they can be preserved.

Definition at line 168 of file InstructionCombining.cpp.

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

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

static

Definition at line 549 of file InstructionCombining.cpp.

References llvm::InstCombiner::Builder, llvm::IRBuilder< preserveNames, T, Inserter >::CreateBinOp(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateCast(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateICmp(), llvm::ConstantExpr::get(), llvm::Value::getName(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm_unreachable, and std::swap().

INITIALIZE_PASS_BEGIN	(	InstCombiner	,
		"instcombine"	,
		"Combine redundant instructions"	,
		false	,
		false
	)

static bool isAllocSiteRemovable ( Instruction *  AI, SmallVectorImpl< WeakVH > &  Users, const TargetLibraryInfo *  TLI  )

static

Definition at line 1401 of file InstructionCombining.cpp.

References llvm::Call, llvm::Intrinsic::dbg_declare, llvm::Intrinsic::dbg_value, llvm::SmallVectorBase::empty(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::StoreInst::getPointerOperand(), llvm::MemIntrinsic::getRawDest(), I, llvm::Intrinsic::invariant_end, llvm::Intrinsic::invariant_start, llvm::ICmpInst::isEquality(), llvm::isFreeCall(), llvm::MemIntrinsic::isVolatile(), llvm::StoreInst::isVolatile(), llvm::Intrinsic::lifetime_end, llvm::Intrinsic::lifetime_start, llvm_unreachable, llvm::Intrinsic::memcpy, llvm::Intrinsic::memmove, llvm::Intrinsic::memset, llvm::A64CC::MI, llvm::Intrinsic::objectsize, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SPII::Store, llvm::Value::use_begin(), and llvm::Value::use_end().

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

static bool isCatchAll ( Personality_Type  Personality, Constant *  TypeInfo  )

static

isCatchAll - Return 'true' if the given typeinfo will match anything.

Definition at line 1849 of file InstructionCombining.cpp.

References GNU_Ada_Personality, GNU_CXX_Personality, GNU_ObjC_Personality, llvm::Constant::isNullValue(), llvm_unreachable, and Unknown_Personality.

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

static bool LeftDistributesOverRight ( Instruction::BinaryOps  LOp, Instruction::BinaryOps  ROp  )

static

LeftDistributesOverRight - Whether "X LOp (Y ROp Z)" is always equal to "(X LOp Y) ROp (X LOp Z)".

Definition at line 342 of file InstructionCombining.cpp.

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

Referenced by RightDistributesOverLeft().

static bool MaintainNoSignedWrap ( BinaryOperator &  I, Value *  B, Value *  C  )

static

Definition at line 132 of file InstructionCombining.cpp.

References llvm::CallingConv::C, llvm::dyn_cast(), llvm::BinaryOperator::getOpcode(), llvm::ConstantInt::getValue(), llvm::OverflowingBinaryOperator::hasNoSignedWrap(), I, llvm::APInt::sadd_ov(), and llvm::APInt::ssub_ov().

static Personality_Type RecognizePersonality ( Value *  Pers )

static

RecognizePersonality - See if the given exception handling personality function is one that we understand. If so, return a description of it; otherwise return Unknown_Personality.

Definition at line 1837 of file InstructionCombining.cpp.

References llvm::StringSwitch< T, R >::Case(), llvm::StringSwitch< T, R >::Default(), llvm::dyn_cast(), F(), llvm::Value::getName(), GNU_Ada_Personality, GNU_CXX_Personality, GNU_ObjC_Personality, llvm::Value::stripPointerCasts(), and Unknown_Personality.

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

static bool RightDistributesOverLeft ( Instruction::BinaryOps  LOp, Instruction::BinaryOps  ROp  )

static

RightDistributesOverLeft - Whether "(X LOp Y) ROp Z" is always equal to "(X ROp Z) LOp (Y ROp Z)".

Definition at line 381 of file InstructionCombining.cpp.

References llvm::Instruction::isCommutative(), and LeftDistributesOverRight().

static bool shorter_filter ( const Value *  LHS, const Value *  RHS  )

static

Definition at line 1864 of file InstructionCombining.cpp.

References llvm::Value::getType().

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

static bool shouldMergeGEPs ( GEPOperator &  GEP, GEPOperator &  Src  )

static

Definition at line 825 of file InstructionCombining.cpp.

References llvm::GEPOperator::hasAllZeroIndices(), and llvm::Value::hasOneUse().

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

STATISTIC	(	NumCombined	,
		"Number of insts combined"
	)

STATISTIC	(	NumConstProp	,
		"Number of constant folds"
	)

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

STATISTIC	(	NumSunkInst	,
		"Number of instructions sunk"
	)

STATISTIC	(	NumExpand	,
		"Number of expansions"
	)

STATISTIC	(	NumFactor	,
		"Number of factorizations"
	)

STATISTIC	(	NumReassoc	,
		"Number of reassociations"
	)

static Instruction* tryToMoveFreeBeforeNullTest ( CallInst &  FI )

static

Move the call to free before a NULL test.

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

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

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

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

Definition at line 1532 of file InstructionCombining.cpp.

References llvm::CallInst::getArgOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_UnconditionalBr(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), llvm::Instruction::moveBefore(), and llvm::BasicBlock::size().

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

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

References llvm::BasicBlock::end(), llvm::Function::getEntryBlock(), llvm::BasicBlock::getFirstInsertionPt(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::Value::hasOneUse(), I, llvm::Instruction::mayHaveSideEffects(), llvm::Instruction::mayReadFromMemory(), and llvm::Instruction::moveBefore().

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

Variable Documentation

Combine redundant false

Definition at line 87 of file InstructionCombining.cpp.

instcombine

Definition at line 87 of file InstructionCombining.cpp.

Combine redundant instructions

Definition at line 87 of file InstructionCombining.cpp.

cl::opt<bool> UnsafeFPShrink("enable-double-float-shrink", cl::Hidden, cl::init(false), cl::desc("Enable unsafe double to float ""shrinking for math lib calls"))

static