LLVM  8.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/MemorySSAUpdater.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/DomTreeUpdater.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 "llvm/Transforms/Utils/ValueMapper.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 * >
 
using DbgValReplacement = Optional< DIExpression * >
 A replacement for a dbg.value expression. More...
 

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 valueCoversEntireFragment (Type *ValTy, DbgVariableIntrinsic *DII)
 Check if the alloc size of ValTy is large enough to cover the variable (or fragment of the variable) described by DII. More...
 
static bool isArray (AllocaInst *AI)
 Determine whether this alloca is either a VLA or an array. More...
 
static void replaceOneDbgValueForAlloca (DbgValueInst *DVI, Value *NewAddress, DIBuilder &Builder, int Offset)
 
static MetadataAsValuewrapValueInMetadata (LLVMContext &C, Value *V)
 Wrap V in a ValueAsMetadata instance. More...
 
static bool rewriteDebugUsers (Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT, function_ref< DbgValReplacement(DbgVariableIntrinsic &DII)> RewriteExpr)
 Point debug users of From to To using exprs given by RewriteExpr, possibly moving/deleting users to prevent use-before-def. More...
 
static bool isBitCastSemanticsPreserving (const DataLayout &DL, Type *FromTy, Type *ToTy)
 Check if a bitcast between a value of type FromTy to type ToTy would losslessly preserve the bits and semantics of the value. More...
 
static void changeToCall (InvokeInst *II, DomTreeUpdater *DTU=nullptr)
 changeToCall - Convert the specified invoke into a normal call. More...
 
static bool markAliveBlocks (Function &F, SmallPtrSetImpl< BasicBlock *> &Reachable, DomTreeUpdater *DTU=nullptr)
 
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 90 of file Local.cpp.

Typedef Documentation

◆ DbgValReplacement

A replacement for a dbg.value expression.

Definition at line 1732 of file Local.cpp.

◆ IncomingValueMap

Definition at line 813 of file Local.cpp.

◆ PredBlockVector

Definition at line 812 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 483 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 2706 of file Local.cpp.

Referenced by llvm::recognizeBSwapOrBitReverseIdiom().

◆ bitTransformIsCorrectForBSwap()

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

Definition at line 2695 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 747 of file Local.cpp.

Referenced by CanPropagatePredecessorsForPHIs().

◆ CanPropagatePredecessorsForPHIs()

static bool CanPropagatePredecessorsForPHIs ( BasicBlock BB,
BasicBlock Succ 
)
static

◆ changeToCall()

static void changeToCall ( InvokeInst II,
DomTreeUpdater DTU = nullptr 
)
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 2577 of file Local.cpp.

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

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 1129 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().

◆ 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 852 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 1384 of file Local.cpp.

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

Referenced by llvm::LowerDbgDeclare().

◆ isBitCastSemanticsPreserving()

static bool isBitCastSemanticsPreserving ( const DataLayout DL,
Type FromTy,
Type ToTy 
)
static

Check if a bitcast between a value of type FromTy to type ToTy would losslessly preserve the bits and semantics of the value.

This predicate is symmetric, i.e swapping FromTy and ToTy should give the same result.

Note that Type::canLosslesslyBitCastTo is not suitable here because it allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>, and also does not allow lossless pointer <-> integer conversions.

Definition at line 1808 of file Local.cpp.

References llvm::DataLayout::getTypeSizeInBits(), llvm::Type::isIntOrPtrTy(), and llvm::DataLayout::isNonIntegralPointerType().

Referenced by llvm::replaceAllDbgUsesWith().

◆ 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 1207 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,
DomTreeUpdater DTU = nullptr 
)
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 1225 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 890 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::SmallVectorBase::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 868 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().

◆ rewriteDebugUsers()

static bool rewriteDebugUsers ( Instruction From,
Value To,
Instruction DomPoint,
DominatorTree DT,
function_ref< DbgValReplacement(DbgVariableIntrinsic &DII)>  RewriteExpr 
)
static

◆ 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 827 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"   
)

◆ valueCoversEntireFragment()

static bool valueCoversEntireFragment ( Type ValTy,
DbgVariableIntrinsic DII 
)
static

Check if the alloc size of ValTy is large enough to cover the variable (or fragment of the variable) described by DII.

This is primarily intended as a helper for the different ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is converted describes an alloca'd variable, so we need to use the alloc size of the value when doing the comparison. E.g. an i1 value will be identified as covering an n-bit fragment, if the store size of i1 is at least n bits.

Definition at line 1250 of file Local.cpp.

References llvm::Module::getDataLayout(), llvm::DbgVariableIntrinsic::getFragmentSizeInBits(), llvm::Instruction::getModule(), llvm::DataLayout::getTypeAllocSizeInBits(), llvm::DbgVariableIntrinsic::getVariableLocation(), and llvm::DbgVariableIntrinsic::isAddressOfVariable().

Referenced by llvm::ConvertDebugDeclareToDebugValue().

◆ wrapValueInMetadata()

static MetadataAsValue* wrapValueInMetadata ( LLVMContext C,
Value V 
)
static

Wrap V in a ValueAsMetadata instance.

Definition at line 1605 of file Local.cpp.

References llvm::MetadataAsValue::get(), and llvm::ValueAsMetadata::get().

Referenced by rewriteDebugUsers(), and llvm::salvageDebugInfo().