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 26 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 414 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 195 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 50 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

Speculate users around a set of PHI nodes.

This routine does the actual speculation around a set of PHI nodes where we have determined this to be both safe and profitable.

This routine handles any spliting of critical edges necessary to create a safe block to speculate into as well as cloning the instructions and rewriting all uses.

Definition at line 552 of file SpeculateAroundPHIs.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::IRBuilder< T, Inserter >::CreatePHI(), llvm::dbgs(), llvm::dyn_cast(), 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(), getType(), I, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::reverse(), llvm::SmallVectorBase::size(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size(), llvm::ArrayRef< T >::size(), llvm::SplitCriticalEdge(), and visitPHIUsersAndDepsInPostOrder().

Referenced by tryToSpeculatePHIs().

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 726 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 336 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().