LLVM  6.0.0svn
Macros | Typedefs | Functions
Local.cpp File Reference
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/TinyPtrVector.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/EHPersonalities.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalObject.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <iterator>
#include <map>
#include <utility>

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "local"
 

Typedefs

using PredBlockVector = SmallVector< BasicBlock *, 16 >
 
using IncomingValueMap = DenseMap< BasicBlock *, Value * >
 

Functions

 STATISTIC (NumRemoved, "Number of unreachable basic blocks removed")
 
static bool areAllUsesEqual (Instruction *I)
 areAllUsesEqual - Check whether the uses of a value are all the same. More...
 
static bool simplifyAndDCEInstruction (Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const DataLayout &DL, const TargetLibraryInfo *TLI)
 
static bool CanMergeValues (Value *First, Value *Second)
 CanMergeValues - Return true if we can choose one of these values to use in place of the other. More...
 
static bool CanPropagatePredecessorsForPHIs (BasicBlock *BB, BasicBlock *Succ)
 CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an almost-empty BB ending in an unconditional branch to Succ, into Succ. More...
 
static ValueselectIncomingValueForBlock (Value *OldVal, BasicBlock *BB, IncomingValueMap &IncomingValues)
 Determines the value to use as the phi node input for a block. More...
 
static void gatherIncomingValuesToPhi (PHINode *PN, IncomingValueMap &IncomingValues)
 Create a map from block to value for the operands of a given phi. More...
 
static void replaceUndefValuesInPhi (PHINode *PN, const IncomingValueMap &IncomingValues)
 Replace the incoming undef values to a phi with the values from a block-to-value map. More...
 
static void redirectValuesFromPredecessorsToPhi (BasicBlock *BB, const PredBlockVector &BBPreds, PHINode *PN)
 Replace a value flowing from a block to a phi with potentially multiple instances of that value flowing from the block's predecessors to the phi. More...
 
static unsigned enforceKnownAlignment (Value *V, unsigned Align, unsigned PrefAlign, const DataLayout &DL)
 enforceKnownAlignment - If the specified pointer points to an object that we control, modify the object's alignment to PrefAlign. More...
 
static bool LdStHasDebugValue (DILocalVariable *DIVar, DIExpression *DIExpr, Instruction *I)
 ===---------------------------------------------------------------——===// Dbg Intrinsic utilities More...
 
static bool PhiHasDebugValue (DILocalVariable *DIVar, DIExpression *DIExpr, PHINode *APN)
 See if there is a dbg.value intrinsic for DIVar for the PHI node. More...
 
static bool isArray (AllocaInst *AI)
 Determine whether this alloca is either a VLA or an array. More...
 
static void findDbgUsers (SmallVectorImpl< DbgInfoIntrinsic *> &DbgUsers, Value *V)
 
static void replaceOneDbgValueForAlloca (DbgValueInst *DVI, Value *NewAddress, DIBuilder &Builder, int Offset)
 
static void changeToCall (InvokeInst *II)
 changeToCall - Convert the specified invoke into a normal call. More...
 
static bool markAliveBlocks (Function &F, SmallPtrSetImpl< BasicBlock *> &Reachable)
 
template<typename RootType , typename DominatesFn >
static unsigned replaceDominatedUsesWith (Value *From, Value *To, const RootType &Root, const DominatesFn &Dominates)
 
static const Optional< BitPart > & collectBitParts (Value *V, bool MatchBSwaps, bool MatchBitReversals, std::map< Value *, Optional< BitPart >> &BPS)
 Analyze the specified subexpression and see if it is capable of providing pieces of a bswap or bitreverse. More...
 
static bool bitTransformIsCorrectForBSwap (unsigned From, unsigned To, unsigned BitWidth)
 
static bool bitTransformIsCorrectForBitReverse (unsigned From, unsigned To, unsigned BitWidth)
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "local"

Definition at line 87 of file Local.cpp.

Typedef Documentation

◆ IncomingValueMap

Definition at line 731 of file Local.cpp.

◆ PredBlockVector

Definition at line 730 of file Local.cpp.

Function Documentation

◆ areAllUsesEqual()

static bool areAllUsesEqual ( Instruction I)
static

areAllUsesEqual - Check whether the uses of a value are all the same.

This is similar to Instruction::hasOneUse() except this will also return true when there are no uses or multiple uses that all refer to the same value.

Definition at line 439 of file Local.cpp.

References llvm::Value::user_begin(), and llvm::Value::user_end().

Referenced by llvm::RecursivelyDeleteDeadPHINode().

◆ bitTransformIsCorrectForBitReverse()

static bool bitTransformIsCorrectForBitReverse ( unsigned  From,
unsigned  To,
unsigned  BitWidth 
)
static

Definition at line 2141 of file Local.cpp.

Referenced by llvm::recognizeBSwapOrBitReverseIdiom().

◆ bitTransformIsCorrectForBSwap()

static bool bitTransformIsCorrectForBSwap ( unsigned  From,
unsigned  To,
unsigned  BitWidth 
)
static

Definition at line 2130 of file Local.cpp.

Referenced by llvm::recognizeBSwapOrBitReverseIdiom().

◆ CanMergeValues()

static bool CanMergeValues ( Value First,
Value Second 
)
static

CanMergeValues - Return true if we can choose one of these values to use in place of the other.

Note that we will always choose the non-undef value to keep.

Definition at line 667 of file Local.cpp.

Referenced by CanPropagatePredecessorsForPHIs().

◆ CanPropagatePredecessorsForPHIs()

static bool CanPropagatePredecessorsForPHIs ( BasicBlock BB,
BasicBlock Succ 
)
static

◆ changeToCall()

static void changeToCall ( InvokeInst II)
static

◆ collectBitParts()

static const Optional<BitPart>& collectBitParts ( Value V,
bool  MatchBSwaps,
bool  MatchBitReversals,
std::map< Value *, Optional< BitPart >> &  BPS 
)
static

Analyze the specified subexpression and see if it is capable of providing pieces of a bswap or bitreverse.

The subexpression provides a potential piece of a bswap or bitreverse if it can be proven that each non-zero bit in the output of the expression came from a corresponding bit in some other value. This function is recursive, and the end result is a mapping of bitnumber to bitnumber. It is the caller's responsibility to validate that the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.

For example, if the current subexpression if "(shl i32 %X, 24)" then we know that the expression deposits the low byte of X into the high byte of the result and that all other bits are zero. This expression is accepted and a BitPart is returned with Provider set to X and Provenance[24-31] set to [0-7].

To avoid revisiting values, the BitPart results are memoized into the provided map. To avoid unnecessary copying of BitParts, BitParts are constructed in-place in the BPS map. Because of this BPS needs to store BitParts objects, not pointers. As we need the concept of a nullptr BitParts (Value has been analyzed and the analysis failed), we an Optional type instead to provide the same functionality.

Because we pass around references into BPS, we must use a container that does not invalidate internal references (std::map instead of DenseMap).

Definition at line 2012 of file Local.cpp.

References B, llvm::tgtok::Bit, for(), getBitWidth(), llvm::Value::getType(), I, llvm::None, and P.

Referenced by llvm::recognizeBSwapOrBitReverseIdiom().

◆ enforceKnownAlignment()

static unsigned enforceKnownAlignment ( Value V,
unsigned  Align,
unsigned  PrefAlign,
const DataLayout DL 
)
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 1020 of file Local.cpp.

References llvm::AMDGPU::HSAMD::Kernel::Arg::Key::Align, assert(), llvm::DataLayout::exceedsNaturalStackAlignment(), llvm::max(), and llvm::Value::stripPointerCasts().

Referenced by llvm::getOrEnforceKnownAlignment().

◆ findDbgUsers()

static void findDbgUsers ( SmallVectorImpl< DbgInfoIntrinsic *> &  DbgUsers,
Value V 
)
static

◆ gatherIncomingValuesToPhi()

static void gatherIncomingValuesToPhi ( PHINode PN,
IncomingValueMap IncomingValues 
)
static

Create a map from block to value for the operands of a given phi.

Create a map from block to value for each non-undef value flowing into PN.

Parameters
PNThe phi we are collecting the map for.
IncomingValues[out] The map from block to value for this phi.

Definition at line 770 of file Local.cpp.

References llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

Referenced by redirectValuesFromPredecessorsToPhi().

◆ isArray()

static bool isArray ( AllocaInst AI)
static

Determine whether this alloca is either a VLA or an array.

Definition at line 1217 of file Local.cpp.

References llvm::PointerType::getElementType(), llvm::AllocaInst::getType(), llvm::AllocaInst::isArrayAllocation(), and llvm::Type::isArrayTy().

Referenced by llvm::LowerDbgDeclare().

◆ LdStHasDebugValue()

static bool LdStHasDebugValue ( DILocalVariable DIVar,
DIExpression DIExpr,
Instruction I 
)
static

===---------------------------------------------------------------——===// Dbg Intrinsic utilities

See if there is a dbg.value intrinsic for DIVar before I.

Definition at line 1098 of file Local.cpp.

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

Referenced by llvm::ConvertDebugDeclareToDebugValue().

◆ markAliveBlocks()

static bool markAliveBlocks ( Function F,
SmallPtrSetImpl< BasicBlock *> &  Reachable 
)
static

◆ PhiHasDebugValue()

static bool PhiHasDebugValue ( DILocalVariable DIVar,
DIExpression DIExpr,
PHINode APN 
)
static

See if there is a dbg.value intrinsic for DIVar for the PHI node.

Definition at line 1116 of file Local.cpp.

References assert(), and llvm::findDbgValues().

Referenced by llvm::ConvertDebugDeclareToDebugValue().

◆ redirectValuesFromPredecessorsToPhi()

static void redirectValuesFromPredecessorsToPhi ( BasicBlock BB,
const PredBlockVector BBPreds,
PHINode PN 
)
static

Replace a value flowing from a block to a phi with potentially multiple instances of that value flowing from the block's predecessors to the phi.

Parameters
BBThe block with the value flowing into the phi.
BBPredsThe predecessors of BB.
PNThe phi that we are updating.

Definition at line 808 of file Local.cpp.

References llvm::PHINode::addIncoming(), assert(), gatherIncomingValuesToPhi(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), getParent(), llvm::PHINode::removeIncomingValue(), replaceUndefValuesInPhi(), selectIncomingValueForBlock(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

Referenced by llvm::TryToSimplifyUncondBranchFromEmptyBlock().

◆ replaceDominatedUsesWith()

template<typename RootType , typename DominatesFn >
static unsigned replaceDominatedUsesWith ( Value From,
Value To,
const RootType &  Root,
const DominatesFn &  Dominates 
)
static

◆ replaceOneDbgValueForAlloca()

static void replaceOneDbgValueForAlloca ( DbgValueInst DVI,
Value NewAddress,
DIBuilder Builder,
int  Offset 
)
static

◆ replaceUndefValuesInPhi()

static void replaceUndefValuesInPhi ( PHINode PN,
const IncomingValueMap IncomingValues 
)
static

Replace the incoming undef values to a phi with the values from a block-to-value map.

Parameters
PNThe phi we are replacing the undefs in.
IncomingValuesA map from block to value.

Definition at line 786 of file Local.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), and llvm::PHINode::setIncomingValue().

Referenced by redirectValuesFromPredecessorsToPhi().

◆ selectIncomingValueForBlock()

static Value* selectIncomingValueForBlock ( Value OldVal,
BasicBlock BB,
IncomingValueMap IncomingValues 
)
static

Determines the value to use as the phi node input for a block.

Select between OldVal any value that we know flows from BB to a particular phi on the basis of which one (if either) is not undef. Update IncomingValues based on the selected value.

Parameters
OldValThe value we are considering selecting.
BBThe block that the value flows in from.
IncomingValuesA map from block-to-value for other phi inputs that we have examined.
Returns
the selected value.

Definition at line 745 of file Local.cpp.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

Referenced by redirectValuesFromPredecessorsToPhi().

◆ simplifyAndDCEInstruction()

static bool simplifyAndDCEInstruction ( Instruction I,
SmallSetVector< Instruction *, 16 > &  WorkList,
const DataLayout DL,
const TargetLibraryInfo TLI 
)
static

◆ STATISTIC()

STATISTIC ( NumRemoved  ,
"Number of unreachable basic blocks removed"   
)