LLVM  9.0.0svn
Macros | Functions
SpeculateAroundPHIs.cpp File Reference
#include "llvm/Transforms/Scalar/SpeculateAroundPHIs.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Include dependency graph for SpeculateAroundPHIs.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "spec-phis"
 

Functions

 STATISTIC (NumPHIsSpeculated, "Number of PHI nodes we speculated around")
 
 STATISTIC (NumEdgesSplit, "Number of critical edges which were split for speculation")
 
 STATISTIC (NumSpeculatedInstructions, "Number of instructions we speculated around the PHI nodes")
 
 STATISTIC (NumNewRedundantInstructions, "Number of new, redundant instructions inserted")
 
static bool isSafeToSpeculatePHIUsers (PHINode &PN, DominatorTree &DT, SmallPtrSetImpl< Instruction *> &PotentialSpecSet, SmallPtrSetImpl< Instruction *> &UnsafeSet)
 Check whether speculating the users of a PHI node around the PHI will be safe. More...
 
static bool isSafeAndProfitableToSpeculateAroundPHI (PHINode &PN, SmallDenseMap< PHINode *, int, 16 > &CostSavingsMap, SmallPtrSetImpl< Instruction *> &PotentialSpecSet, SmallPtrSetImpl< Instruction *> &UnsafeSet, DominatorTree &DT, TargetTransformInfo &TTI)
 Check whether, in isolation, a given PHI node is both safe and profitable to speculate users around. More...
 
template<typename IsVisitedT , typename VisitT >
static void visitPHIUsersAndDepsInPostOrder (ArrayRef< PHINode *> PNs, IsVisitedT IsVisited, VisitT Visit)
 Simple helper to walk all the users of a list of phis depth first, and call a visit function on each one in post-order. More...
 
static SmallVector< PHINode *, 16 > findProfitablePHIs (ArrayRef< PHINode *> PNs, const SmallDenseMap< PHINode *, int, 16 > &CostSavingsMap, const SmallPtrSetImpl< Instruction *> &PotentialSpecSet, int NumPreds, DominatorTree &DT, TargetTransformInfo &TTI)
 Find profitable PHIs to speculate. More...
 
static void speculatePHIs (ArrayRef< PHINode *> SpecPNs, SmallPtrSetImpl< Instruction *> &PotentialSpecSet, SmallSetVector< BasicBlock *, 16 > &PredSet, DominatorTree &DT)
 Speculate users around a set of PHI nodes. More...
 
static bool tryToSpeculatePHIs (SmallVectorImpl< PHINode *> &PNs, DominatorTree &DT, TargetTransformInfo &TTI)
 Try to speculate around a series of PHIs from a single basic block. More...
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "spec-phis"

Definition at line 25 of file SpeculateAroundPHIs.cpp.

Function Documentation

◆ findProfitablePHIs()

static SmallVector<PHINode *, 16> findProfitablePHIs ( ArrayRef< PHINode *>  PNs,
const SmallDenseMap< PHINode *, int, 16 > &  CostSavingsMap,
const SmallPtrSetImpl< Instruction *> &  PotentialSpecSet,
int  NumPreds,
DominatorTree DT,
TargetTransformInfo TTI 
)
static

Find profitable PHIs to speculate.

For a PHI node to be profitable, we need the cost of speculating its users (and their dependencies) to not exceed the savings of folding the PHI's constant operands into the speculated users.

Computing this is surprisingly challenging. Because users of two different PHI nodes can depend on each other or on common other instructions, it may be profitable to speculate two PHI nodes together even though neither one in isolation is profitable. The straightforward way to find all the profitable PHIs would be to check each combination of PHIs' cost, but this is exponential in complexity.

Even if we assume that we only care about cases where we can consider each PHI node in isolation (rather than considering cases where none are profitable in isolation but some subset are profitable as a set), we still have a challenge. The obvious way to find all individually profitable PHIs is to iterate until reaching a fixed point, but this will be quadratic in complexity. =/

This code currently uses a linear-to-compute order for a greedy approach. It won't find cases where a set of PHIs must be considered together, but it handles most cases of order dependence without quadratic iteration. The specific order used is the post-order across the operand DAG. When the last user of a PHI is visited in this postorder walk, we check it for profitability.

There is an orthogonal extra complexity to all of this: computing the cost itself can easily become a linear computation making everything again (at best) quadratic. Using a postorder over the operand graph makes it particularly easy to avoid this through dynamic programming. As we do the postorder walk, we build the transitive cost of that subgraph. It is also straightforward to then update these costs when we mark a PHI for speculation so that subsequent PHIs don't re-pay the cost of already speculated instructions.

Definition at line 413 of file SpeculateAroundPHIs.cpp.

References assert(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::dyn_cast(), llvm::SmallPtrSetImplBase::empty(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), first, llvm::TargetTransformInfo::getUserCost(), I, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, llvm::make_range(), llvm::User::operand_values(), llvm::SmallVectorTemplateBase< T >::push_back(), second, llvm::SmallPtrSetImplBase::size(), llvm::TargetTransformInfo::TCC_Free, llvm::Value::uses(), and visitPHIUsersAndDepsInPostOrder().

Referenced by tryToSpeculatePHIs().

◆ isSafeAndProfitableToSpeculateAroundPHI()

static bool isSafeAndProfitableToSpeculateAroundPHI ( PHINode PN,
SmallDenseMap< PHINode *, int, 16 > &  CostSavingsMap,
SmallPtrSetImpl< Instruction *> &  PotentialSpecSet,
SmallPtrSetImpl< Instruction *> &  UnsafeSet,
DominatorTree DT,
TargetTransformInfo TTI 
)
static

Check whether, in isolation, a given PHI node is both safe and profitable to speculate users around.

This handles checking whether there are any constant operands to a PHI which could represent a useful speculation candidate, whether the users of the PHI are safe to speculate including all their transitive dependencies, and whether after speculation there will be some cost savings (profit) to folding the operands into the users of the PHI node. Returns true if both safe and profitable with relevant cost savings updated in the map and with an update to the PotentialSpecSet. Returns false if either safety or profitability are absent. Some new entries may be made to the PotentialSpecSet even when this routine returns false, but they remain conservatively correct.

The profitability check here is a local one, but it checks this in an interesting way. Beyond checking that the total cost of materializing the constants will be less than the cost of folding them into their users, it also checks that no one incoming constant will have a higher cost when folded into its users rather than materialized. This higher cost could result in a dynamic path that is more expensive even when the total cost is lower. Currently, all of the interesting cases where this optimization should fire are ones where it is a no-loss operation in this sense. If we ever want to be more aggressive here, we would need to balance the different incoming edges' cost by looking at their respective probabilities.

Definition at line 194 of file SpeculateAroundPHIs.cpp.

References assert(), llvm::dbgs(), llvm::dyn_cast(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::TargetTransformInfo::getIntImmCost(), llvm::PHINode::getNumIncomingValues(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), isSafeToSpeculatePHIUsers(), LLVM_DEBUG, llvm::Intrinsic::not_intrinsic, second, llvm::TargetTransformInfo::TCC_Free, and llvm::Value::uses().

Referenced by tryToSpeculatePHIs().

◆ isSafeToSpeculatePHIUsers()

static bool isSafeToSpeculatePHIUsers ( PHINode PN,
DominatorTree DT,
SmallPtrSetImpl< Instruction *> &  PotentialSpecSet,
SmallPtrSetImpl< Instruction *> &  UnsafeSet 
)
static

Check whether speculating the users of a PHI node around the PHI will be safe.

This checks both that all of the users are safe and also that all of their operands are either recursively safe or already available along an incoming edge to the PHI.

This routine caches both all the safe nodes explored in PotentialSpecSet and the chain of nodes that definitively reach any unsafe node in UnsafeSet. By preserving these between repeated calls to this routine for PHIs in the same basic block, the exploration here can be reused. However, these caches must no be reused for PHIs in a different basic block as they reflect what is available along incoming edges.

Definition at line 49 of file SpeculateAroundPHIs.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::Instruction::getParent(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, llvm::mayBeMemoryDependent(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::Value::uses().

Referenced by isSafeAndProfitableToSpeculateAroundPHI().

◆ speculatePHIs()

static void speculatePHIs ( ArrayRef< PHINode *>  SpecPNs,
SmallPtrSetImpl< Instruction *> &  PotentialSpecSet,
SmallSetVector< BasicBlock *, 16 > &  PredSet,
DominatorTree DT 
)
static

◆ STATISTIC() [1/4]

STATISTIC ( NumPHIsSpeculated  ,
"Number of PHI nodes we speculated around"   
)

◆ STATISTIC() [2/4]

STATISTIC ( NumEdgesSplit  ,
"Number of critical edges which were split for speculation"   
)

◆ STATISTIC() [3/4]

STATISTIC ( NumSpeculatedInstructions  ,
"Number of instructions we speculated around the PHI nodes  
)

◆ STATISTIC() [4/4]

STATISTIC ( NumNewRedundantInstructions  ,
"Number of  new,
redundant instructions inserted"   
)

◆ tryToSpeculatePHIs()

static bool tryToSpeculatePHIs ( SmallVectorImpl< PHINode *> &  PNs,
DominatorTree DT,
TargetTransformInfo TTI 
)
static

Try to speculate around a series of PHIs from a single basic block.

This routine checks whether any of these PHIs are profitable to speculate users around. If safe and profitable, it does the speculation. It returns true when at least some speculation occurs.

Definition at line 725 of file SpeculateAroundPHIs.cpp.

References llvm::dbgs(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallVectorImpl< T >::erase(), findProfitablePHIs(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert(), isSafeAndProfitableToSpeculateAroundPHI(), LLVM_DEBUG, llvm::remove_if(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size(), and speculatePHIs().

Referenced by llvm::SpeculateAroundPHIsPass::run().

◆ visitPHIUsersAndDepsInPostOrder()

template<typename IsVisitedT , typename VisitT >
static void visitPHIUsersAndDepsInPostOrder ( ArrayRef< PHINode *>  PNs,
IsVisitedT  IsVisited,
VisitT  Visit 
)
static

Simple helper to walk all the users of a list of phis depth first, and call a visit function on each one in post-order.

All of the PHIs should be in the same basic block, and this is primarily used to make a single depth-first walk across their collective users without revisiting any subgraphs. Callers should provide a fast, idempotent callable to test whether a node has been visited and the more important callable to actually visit a particular node.

Depth-first and postorder here refer to the operand graph – we start from a collection of users of PHI nodes and walk "up" the operands depth-first.

Definition at line 335 of file SpeculateAroundPHIs.cpp.

References assert(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::Value::uses().

Referenced by findProfitablePHIs(), and speculatePHIs().