summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/MachineBlockPlacement.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/MachineBlockPlacement.cpp')
-rw-r--r--llvm/lib/CodeGen/MachineBlockPlacement.cpp94
1 files changed, 64 insertions, 30 deletions
diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
index c30f306a169..f135cf71593 100644
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -1,4 +1,4 @@
-//===-- MachineBlockPlacement.cpp - Basic Block Code Layout optimization --===//
+//===- MachineBlockPlacement.cpp - Basic Block Code Layout optimization ---===//
//
// The LLVM Compiler Infrastructure
//
@@ -26,7 +26,10 @@
//===----------------------------------------------------------------------===//
#include "BranchFolding.h"
+#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.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"
@@ -39,19 +42,33 @@
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachinePostDominators.h"
-#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/TailDuplicator.h"
#include "llvm/CodeGen/TargetPassConfig.h"
+#include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
+#include "llvm/Support/BlockFrequency.h"
+#include "llvm/Support/BranchProbability.h"
+#include "llvm/Support/CodeGen.h"
#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <algorithm>
-#include <functional>
+#include <cassert>
+#include <cstdint>
+#include <iterator>
+#include <memory>
+#include <string>
+#include <tuple>
#include <utility>
+#include <vector>
+
using namespace llvm;
#define DEBUG_TYPE "block-placement"
@@ -101,6 +118,7 @@ static cl::opt<bool>
cl::desc("Model the cost of loop rotation more "
"precisely by using profile data."),
cl::init(false), cl::Hidden);
+
static cl::opt<bool>
ForcePreciseRotationCost("force-precise-rotation-cost",
cl::desc("Force the use of precise cost "
@@ -177,12 +195,12 @@ extern cl::opt<GVDAGType> ViewBlockLayoutWithBFI;
extern cl::opt<std::string> ViewBlockFreqFuncName;
namespace {
+
class BlockChain;
+
/// \brief Type for our function-wide basic block -> block chain mapping.
-typedef DenseMap<const MachineBasicBlock *, BlockChain *> BlockToChainMapType;
-}
+using BlockToChainMapType = DenseMap<const MachineBasicBlock *, BlockChain *>;
-namespace {
/// \brief A chain of blocks which will be laid out contiguously.
///
/// This is the datastructure representing a chain of consecutive blocks that
@@ -216,14 +234,14 @@ public:
/// function. It also registers itself as the chain that block participates
/// in with the BlockToChain mapping.
BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB)
- : Blocks(1, BB), BlockToChain(BlockToChain), UnscheduledPredecessors(0) {
+ : Blocks(1, BB), BlockToChain(BlockToChain) {
assert(BB && "Cannot create a chain with a null basic block");
BlockToChain[BB] = this;
}
/// \brief Iterator over blocks within the chain.
- typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator;
- typedef SmallVectorImpl<MachineBasicBlock *>::const_iterator const_iterator;
+ using iterator = SmallVectorImpl<MachineBasicBlock *>::iterator;
+ using const_iterator = SmallVectorImpl<MachineBasicBlock *>::const_iterator;
/// \brief Beginning of blocks within the chain.
iterator begin() { return Blocks.begin(); }
@@ -291,14 +309,12 @@ public:
///
/// Note: This field is reinitialized multiple times - once for each loop,
/// and then once for the function as a whole.
- unsigned UnscheduledPredecessors;
+ unsigned UnscheduledPredecessors = 0;
};
-}
-namespace {
class MachineBlockPlacement : public MachineFunctionPass {
- /// \brief A typedef for a block filter set.
- typedef SmallSetVector<const MachineBasicBlock *, 16> BlockFilterSet;
+ /// \brief A type for a block filter set.
+ using BlockFilterSet = SmallSetVector<const MachineBasicBlock *, 16>;
/// Pair struct containing basic block and taildup profitiability
struct BlockAndTailDupResult {
@@ -433,6 +449,7 @@ class MachineBlockPlacement : public MachineFunctionPass {
void fillWorkLists(const MachineBasicBlock *MBB,
SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
const BlockFilterSet *BlockFilter);
+
void buildChain(const MachineBasicBlock *BB, BlockChain &Chain,
BlockFilterSet *BlockFilter = nullptr);
MachineBasicBlock *findBestLoopTop(
@@ -459,31 +476,37 @@ class MachineBlockPlacement : public MachineFunctionPass {
const MachineBasicBlock *BB, const MachineBasicBlock *Succ,
BranchProbability AdjustedSumProb,
const BlockChain &Chain, const BlockFilterSet *BlockFilter);
+
/// Check for a trellis layout.
bool isTrellis(const MachineBasicBlock *BB,
const SmallVectorImpl<MachineBasicBlock *> &ViableSuccs,
const BlockChain &Chain, const BlockFilterSet *BlockFilter);
+
/// Get the best successor given a trellis layout.
BlockAndTailDupResult getBestTrellisSuccessor(
const MachineBasicBlock *BB,
const SmallVectorImpl<MachineBasicBlock *> &ViableSuccs,
BranchProbability AdjustedSumProb, const BlockChain &Chain,
const BlockFilterSet *BlockFilter);
+
/// Get the best pair of non-conflicting edges.
static std::pair<WeightedEdge, WeightedEdge> getBestNonConflictingEdges(
const MachineBasicBlock *BB,
MutableArrayRef<SmallVector<WeightedEdge, 8>> Edges);
+
/// Returns true if a block can tail duplicate into all unplaced
/// predecessors. Filters based on loop.
bool canTailDuplicateUnplacedPreds(
const MachineBasicBlock *BB, MachineBasicBlock *Succ,
const BlockChain &Chain, const BlockFilterSet *BlockFilter);
+
/// Find chains of triangles to tail-duplicate where a global analysis works,
/// but a local analysis would not find them.
void precomputeTriangleChains();
public:
static char ID; // Pass identification, replacement for typeid
+
MachineBlockPlacement() : MachineFunctionPass(ID) {
initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
}
@@ -500,10 +523,13 @@ public:
MachineFunctionPass::getAnalysisUsage(AU);
}
};
-}
+
+} // end anonymous namespace
char MachineBlockPlacement::ID = 0;
+
char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID;
+
INITIALIZE_PASS_BEGIN(MachineBlockPlacement, DEBUG_TYPE,
"Branch Probability Basic Block Placement", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
@@ -1099,6 +1125,7 @@ bool MachineBlockPlacement::canTailDuplicateUnplacedPreds(
void MachineBlockPlacement::precomputeTriangleChains() {
struct TriangleChain {
std::vector<MachineBasicBlock *> Edges;
+
TriangleChain(MachineBasicBlock *src, MachineBasicBlock *dst)
: Edges({src, dst}) {}
@@ -1539,10 +1566,10 @@ MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock(
// worklist of already placed entries.
// FIXME: If this shows up on profiles, it could be folded (at the cost of
// some code complexity) into the loop below.
- WorkList.erase(remove_if(WorkList,
- [&](MachineBasicBlock *BB) {
- return BlockToChain.lookup(BB) == &Chain;
- }),
+ WorkList.erase(llvm::remove_if(WorkList,
+ [&](MachineBasicBlock *BB) {
+ return BlockToChain.lookup(BB) == &Chain;
+ }),
WorkList.end());
if (WorkList.empty())
@@ -1664,7 +1691,7 @@ void MachineBlockPlacement::buildChain(
const MachineBasicBlock *LoopHeaderBB = HeadBB;
markChainSuccessors(Chain, LoopHeaderBB, BlockFilter);
MachineBasicBlock *BB = *std::prev(Chain.end());
- for (;;) {
+ while (true) {
assert(BB && "null block found at end of chain in loop.");
assert(BlockToChain[BB] == &Chain && "BlockToChainMap mis-match in loop.");
assert(*std::prev(Chain.end()) == BB && "BB Not found at end of chain.");
@@ -1950,7 +1977,7 @@ void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain,
}
}
- BlockChain::iterator ExitIt = find(LoopChain, ExitingBB);
+ BlockChain::iterator ExitIt = llvm::find(LoopChain, ExitingBB);
if (ExitIt == LoopChain.end())
return;
@@ -2004,7 +2031,7 @@ void MachineBlockPlacement::rotateLoopWithProfile(
BlockChain &LoopChain, const MachineLoop &L,
const BlockFilterSet &LoopBlockSet) {
auto HeaderBB = L.getHeader();
- auto HeaderIter = find(LoopChain, HeaderBB);
+ auto HeaderIter = llvm::find(LoopChain, HeaderBB);
auto RotationPos = LoopChain.end();
BlockFrequency SmallestRotationCost = BlockFrequency::getMaxFrequency();
@@ -2277,7 +2304,7 @@ void MachineBlockPlacement::buildCFGChains() {
new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB);
// Also, merge any blocks which we cannot reason about and must preserve
// the exact fallthrough behavior for.
- for (;;) {
+ while (true) {
Cond.clear();
MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
if (!TII->analyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough())
@@ -2318,7 +2345,7 @@ void MachineBlockPlacement::buildCFGChains() {
buildChain(&F->front(), FunctionChain);
#ifndef NDEBUG
- typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType;
+ using FunctionBlockSetType = SmallPtrSet<MachineBasicBlock *, 16>;
#endif
DEBUG({
// Crash at the end so we get all of the debugging output first.
@@ -2550,8 +2577,8 @@ bool MachineBlockPlacement::repeatedlyTailDuplicateBlock(
// duplicated from here on are already scheduled.
// Note that DuplicatedToLPred always implies Removed.
while (DuplicatedToLPred) {
- assert (Removed && "Block must have been removed to be duplicated into its "
- "layout predecessor.");
+ assert(Removed && "Block must have been removed to be duplicated into its "
+ "layout predecessor.");
MachineBasicBlock *DupBB, *DupPred;
// The removal callback causes Chain.end() to be updated when a block is
// removed. On the first pass through the loop, the chain end should be the
@@ -2634,8 +2661,10 @@ bool MachineBlockPlacement::maybeTailDuplicateBlock(
if (RemBB->isEHPad())
RemoveList = EHPadWorkList;
RemoveList.erase(
- remove_if(RemoveList,
- [RemBB](MachineBasicBlock *BB) {return BB == RemBB;}),
+ llvm::remove_if(RemoveList,
+ [RemBB](MachineBasicBlock *BB) {
+ return BB == RemBB;
+ }),
RemoveList.end());
}
@@ -2653,7 +2682,7 @@ bool MachineBlockPlacement::maybeTailDuplicateBlock(
<< getBlockName(RemBB) << "\n");
};
auto RemovalCallbackRef =
- llvm::function_ref<void(MachineBasicBlock*)>(RemovalCallback);
+ function_ref<void(MachineBasicBlock*)>(RemovalCallback);
SmallVector<MachineBasicBlock *, 8> DuplicatedPreds;
bool IsSimple = TailDup.isSimpleBB(BB);
@@ -2795,6 +2824,7 @@ bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
}
namespace {
+
/// \brief A pass to compute block placement statistics.
///
/// A separate pass to compute interesting statistics for evaluating block
@@ -2810,6 +2840,7 @@ class MachineBlockPlacementStats : public MachineFunctionPass {
public:
static char ID; // Pass identification, replacement for typeid
+
MachineBlockPlacementStats() : MachineFunctionPass(ID) {
initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry());
}
@@ -2823,10 +2854,13 @@ public:
MachineFunctionPass::getAnalysisUsage(AU);
}
};
-}
+
+} // end anonymous namespace
char MachineBlockPlacementStats::ID = 0;
+
char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID;
+
INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats",
"Basic Block Placement Stats", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
OpenPOWER on IntegriCloud