diff --git a/llvm/include/llvm/Transforms/Utils/CodeLayout.h b/llvm/include/llvm/Transforms/Utils/CodeLayout.h
new file mode 100644
--- /dev/null
+++ b/llvm/include/llvm/Transforms/Utils/CodeLayout.h
@@ -0,0 +1,59 @@
+//===- CodeLayout.h - Code layout/placement algorithms ---------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// Declares methods and data structures for code layout algorithms.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_CODELAYOUT_H
+#define LLVM_TRANSFORMS_UTILS_CODELAYOUT_H
+
+#include "llvm/ADT/DenseMap.h"
+
+#include <vector>
+
+namespace llvm {
+
+class MachineBasicBlock;
+
+/// Find a layout of nodes (basic blocks) of a given CFG optimizing jump
+/// locality and thus processor I-cache utilization. This is achieved via
+/// increasing the number of fall-through jumps and co-locating frequently
+/// executed nodes together.
+/// The nodes are assumed to be indexed by integers from [0, |V|) so that the
+/// current order is the identity permutation.
+/// \p NodeSizes: The sizes of the nodes (in bytes).
+/// \p NodeCounts: The execution counts of the nodes in the profile.
+/// \p EdgeCounts: The execution counts of every edge (jump) in the profile. The
+/// map also defines the edges in CFG and should include 0-count edges.
+/// \returns The best block order found.
+std::vector<uint64_t> applyExtTspLayout(
+ const DenseMap<uint64_t, uint64_t> &NodeSizes,
+ const DenseMap<uint64_t, uint64_t> &NodeCounts,
+ const DenseMap<std::pair<uint64_t, uint64_t>, uint64_t> &EdgeCounts);
+
+/// Estimate the "quality" of a given node order in CFG. The higher the score,
+/// the better the order is. The score is designed to reflect the locality of
+/// the given order, which is anti-correlated with the number of I-cache misses
+/// in a typical execution of the function.
+uint64_t calcExtTspScore(
+ const std::vector<uint64_t> &Order,
+ const DenseMap<uint64_t, uint64_t> &NodeSizes,
+ const DenseMap<uint64_t, uint64_t> &NodeCounts,
+ const DenseMap<std::pair<uint64_t, uint64_t>, uint64_t> &EdgeCounts);
+
+/// Estimate the "quality" of the current node order in CFG.
+uint64_t calcExtTspScore(
+ const DenseMap<uint64_t, uint64_t> &NodeSizes,
+ const DenseMap<uint64_t, uint64_t> &NodeCounts,
+ const DenseMap<std::pair<uint64_t, uint64_t>, uint64_t> &EdgeCounts);
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CODELAYOUT_H
diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -61,6 +61,7 @@
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
+#include "llvm/Transforms/Utils/CodeLayout.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
@@ -71,6 +72,8 @@
#include <utility>
#include <vector>
+#include <sstream>
+
using namespace llvm;
#define DEBUG_TYPE "block-placement"
@@ -193,6 +196,11 @@
cl::init(2),
cl::Hidden);
+static cl::opt<bool> EnableExtTspBlockPlacement(
+ "enable-ext-tsp-block-placement", cl::Hidden, cl::init(false),
+ cl::desc("Enable machine block placement based on the ext-tsp model, "
+ "optimizing I-cache utilization."));
+
namespace llvm {
extern cl::opt<unsigned> StaticLikelyProb;
extern cl::opt<unsigned> ProfileLikelyProb;
@@ -557,6 +565,15 @@
/// but a local analysis would not find them.
void precomputeTriangleChains();
+ /// Apply a post-processing step optimizing block placement.
+ void applyExtTsp();
+
+ /// Modify the existing block placement in the function and adjust all jumps.
+ void assignBlockOrder(const std::vector<const MachineBasicBlock *> &NewOrder);
+
+ /// Create a single CFG chain from the current block order.
+ void createCFGChain();
+
public:
static char ID; // Pass identification, replacement for typeid
@@ -3387,6 +3404,15 @@
}
}
+ // Apply a post-processing optimizing block placement.
+ if (MF.size() >= 3 && EnableExtTspBlockPlacement) {
+ // Find a new placement and modify the layout of the blocks in the function.
+ applyExtTsp();
+
+ // Re-create CFG chain so that we can optimizeBranches and alignBlocks.
+ createCFGChain();
+ }
+
optimizeBranches();
alignBlocks();
@@ -3413,12 +3439,138 @@
MBFI->view("MBP." + MF.getName(), false);
}
-
// We always return true as we have no way to track whether the final order
// differs from the original order.
return true;
}
+void MachineBlockPlacement::applyExtTsp() {
+ // Prepare data; blocks are indexed by their index in the current ordering.
+ DenseMap<const MachineBasicBlock *, uint64_t> BlockIndex;
+ BlockIndex.reserve(F->size());
+ std::vector<const MachineBasicBlock *> CurrentBlockOrder;
+ CurrentBlockOrder.reserve(F->size());
+ size_t NumBlocks = 0;
+ for (const MachineBasicBlock &MBB : *F) {
+ BlockIndex[&MBB] = NumBlocks++;
+ CurrentBlockOrder.push_back(&MBB);
+ }
+
+ DenseMap<uint64_t, uint64_t> BlockSizes;
+ BlockSizes.reserve(F->size());
+ DenseMap<uint64_t, uint64_t> BlockCounts;
+ BlockCounts.reserve(F->size());
+ DenseMap<std::pair<uint64_t, uint64_t>, uint64_t> JumpCounts;
+ for (MachineBasicBlock &MBB : *F) {
+ BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB);
+ BlockSizes[BlockIndex[&MBB]] = MBB.size();
+ BlockCounts[BlockIndex[&MBB]] = BlockFreq.getFrequency();
+ for (MachineBasicBlock *Succ : MBB.successors()) {
+ auto EP = MBPI->getEdgeProbability(&MBB, Succ);
+ BlockFrequency EdgeFreq = BlockFreq * EP;
+ auto Edge = std::make_pair(BlockIndex[&MBB], BlockIndex[Succ]);
+ JumpCounts[Edge] += EdgeFreq.getFrequency();
+ }
+ }
+
+ LLVM_DEBUG(dbgs() << "Applying ext-tsp layout for |V| = " << F->size()
+ << " with profile = " << F->getFunction().hasProfileData()
+ << " (" << F->getName().str() << ")"
+ << "\n");
+ LLVM_DEBUG(dbgs() << " original layout score: "
+ << calcExtTspScore(BlockSizes, BlockCounts, JumpCounts)
+ << "\n");
+
+ // Run the layout algorithm.
+ auto NewOrder = applyExtTspLayout(BlockSizes, BlockCounts, JumpCounts);
+ std::vector<const MachineBasicBlock *> NewBlockOrder;
+ NewBlockOrder.reserve(F->size());
+ for (uint64_t Node : NewOrder) {
+ NewBlockOrder.push_back(CurrentBlockOrder[Node]);
+ }
+ LLVM_DEBUG(
+ dbgs() << " optimized layout score: "
+ << calcExtTspScore(NewOrder, BlockSizes, BlockCounts, JumpCounts)
+ << "\n");
+
+ // Assign new block order.
+ assignBlockOrder(NewBlockOrder);
+}
+
+void MachineBlockPlacement::assignBlockOrder(
+ const std::vector<const MachineBasicBlock *> &NewBlockOrder) {
+ assert(F->size() == NewBlockOrder.size() && "Incorrect size of block order");
+ F->RenumberBlocks();
+
+ bool HasChanges = false;
+ for (size_t I = 0; I < NewBlockOrder.size(); I++) {
+ if (NewBlockOrder[I] != F->getBlockNumbered(I)) {
+ HasChanges = true;
+ break;
+ }
+ }
+ // Stop early if the new block order is identical to the existing one.
+ if (!HasChanges)
+ return;
+
+ SmallVector<MachineBasicBlock *, 4> PrevFallThroughs(F->getNumBlockIDs());
+ for (auto &MBB : *F) {
+ PrevFallThroughs[MBB.getNumber()] = MBB.getFallThrough();
+ }
+
+ // Sort basic blocks in the function according to the computed order.
+ DenseMap<const MachineBasicBlock *, size_t> NewIndex;
+ for (const MachineBasicBlock *MBB : NewBlockOrder) {
+ NewIndex[MBB] = NewIndex.size();
+ }
+ F->sort([&](MachineBasicBlock &L, MachineBasicBlock &R) {
+ return NewIndex[&L] < NewIndex[&R];
+ });
+
+ // Update basic block branches by inserting explicit fallthrough branches
+ // when required and re-optimize branches when possible.
+ const TargetInstrInfo *TII = F->getSubtarget().getInstrInfo();
+ SmallVector<MachineOperand, 4> Cond;
+ for (auto &MBB : *F) {
+ MachineFunction::iterator NextMBB = std::next(MBB.getIterator());
+ MachineFunction::iterator EndIt = MBB.getParent()->end();
+ auto *FTMBB = PrevFallThroughs[MBB.getNumber()];
+ // If this block had a fallthrough before we need an explicit unconditional
+ // branch to that block if the fallthrough block is not adjacent to the
+ // block in the new order.
+ if (FTMBB && NextMBB != EndIt && &*NextMBB != FTMBB)
+ TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc());
+
+ // It might be possible to optimize branches by flipping the condition.
+ Cond.clear();
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+ if (TII->analyzeBranch(MBB, TBB, FBB, Cond))
+ continue;
+ MBB.updateTerminator(FTMBB);
+ }
+
+#ifndef NDEBUG
+ // Make sure we correctly constructed all branches.
+ F->verify(this, "After optimized block reordering");
+#endif
+}
+
+void MachineBlockPlacement::createCFGChain() {
+ BlockToChain.clear();
+ ComputedEdges.clear();
+ ChainAllocator.DestroyAll();
+
+ MachineBasicBlock *HeadBB = &F->front();
+ BlockChain *FunctionChain =
+ new (ChainAllocator.Allocate()) BlockChain(BlockToChain, HeadBB);
+
+ for (MachineBasicBlock &MBB : *F) {
+ if (HeadBB == &MBB)
+ continue; // Ignore head of the chain
+ FunctionChain->merge(&MBB, nullptr);
+ }
+}
+
namespace {
/// A pass to compute block placement statistics.
diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt
--- a/llvm/lib/Transforms/Utils/CMakeLists.txt
+++ b/llvm/lib/Transforms/Utils/CMakeLists.txt
@@ -14,6 +14,7 @@
CloneFunction.cpp
CloneModule.cpp
CodeExtractor.cpp
+ CodeLayout.cpp
CodeMoverUtils.cpp
CtorUtils.cpp
Debugify.cpp
diff --git a/llvm/lib/Transforms/Utils/CodeLayout.cpp b/llvm/lib/Transforms/Utils/CodeLayout.cpp
new file mode 100644
--- /dev/null
+++ b/llvm/lib/Transforms/Utils/CodeLayout.cpp
@@ -0,0 +1,905 @@
+//===- CodeLayout.cpp - Implementation of code layout algorithms ----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// ExtTSP - layout of basic blocks with i-cache optimization.
+//
+// The algorithm tries to find a layout of nodes (basic blocks) of a given CFG
+// optimizing jump locality and thus processor I-cache utilization. This is
+// achieved via increasing the number of fall-through jumps and co-locating
+// frequently executed nodes together. The name follows the underlying
+// optimization problem, Extended-TSP, which is a generalization of classical
+// (maximum) Traveling Salesmen Problem.
+//
+// The algorithm is a greedy heuristic that works with chains (ordered lists)
+// of basic blocks. Initially all chains are isolated basic blocks. On every
+// iteration, we pick a pair of chains whose merging yields the biggest increase
+// in the ExtTSP score, which models how i-cache "friendly" a specific chain is.
+// A pair of chains giving the maximum gain is merged into a new chain. The
+// procedure stops when there is only one chain left, or when merging does not
+// increase ExtTSP. In the latter case, the remaining chains are sorted by
+// density in the decreasing order.
+//
+// An important aspect is the way two chains are merged. Unlike earlier
+// algorithms (e.g., based on the approach of Pettis-Hansen), two
+// chains, X and Y, are first split into three, X1, X2, and Y. Then we
+// consider all possible ways of gluing the three chains (e.g., X1YX2, X1X2Y,
+// X2X1Y, X2YX1, YX1X2, YX2X1) and choose the one producing the largest score.
+// This improves the quality of the final result (the search space is larger)
+// while keeping the implementation sufficiently fast.
+//
+// Reference:
+// * A. Newell and S. Pupyrev, Improved Basic Block Reordering,
+// IEEE Transactions on Computers, 2020
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/CodeLayout.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+#define DEBUG_TYPE "code-layout"
+
+namespace {
+
+// Algorithm-specific constants. The values are tuned for the best performance
+// of large-scale front-end bound binaries.
+const double ForwardWeight = 0.1;
+const double BackwardWeight = 0.1;
+const size_t ForwardDistance = 1024;
+const size_t BackwardDistance = 640;
+// The maximum size of a chain for splitting. Larger values of the threshold
+// may yield better quality at the cost of worsen run-time.
+const size_t ChainSplitThreshold = 128;
+// Epsilon for comparison of doubles.
+constexpr double EPS = 1e-8;
+
+class Block;
+class Chain;
+class Edge;
+
+// Calculate the Ext-TSP score, which quantifies the expected number of i-cache
+// misses for a given ordering of basic blocks
+double extTSPScore(uint64_t SrcAddr, uint64_t SrcSize, uint64_t DstAddr,
+ uint64_t Count) {
+ // Fallthrough
+ if (SrcAddr + SrcSize == DstAddr) {
+ // Assume that FallthroughWeight = 1.0 after normalization
+ return static_cast<double>(Count);
+ }
+ // Forward
+ if (SrcAddr + SrcSize < DstAddr) {
+ const auto Dist = DstAddr - (SrcAddr + SrcSize);
+ if (Dist <= ForwardDistance) {
+ double Prob = 1.0 - static_cast<double>(Dist) / ForwardDistance;
+ return ForwardWeight * Prob * Count;
+ }
+ return 0;
+ }
+ // Backward
+ const auto Dist = SrcAddr + SrcSize - DstAddr;
+ if (Dist <= BackwardDistance) {
+ double Prob = 1.0 - static_cast<double>(Dist) / BackwardDistance;
+ return BackwardWeight * Prob * Count;
+ }
+ return 0;
+}
+
+using BlockPair = std::pair<Block *, Block *>;
+using JumpList = std::vector<std::pair<BlockPair, uint64_t>>;
+using BlockIter = std::vector<Block *>::const_iterator;
+
+enum MergeTypeTy {
+ X_Y = 0,
+ X1_Y_X2 = 1,
+ Y_X2_X1 = 2,
+ X2_X1_Y = 3,
+};
+
+class MergeGainTy {
+public:
+ explicit MergeGainTy() {}
+ explicit MergeGainTy(double Score, size_t MergeOffset, MergeTypeTy MergeType)
+ : Score(Score), MergeOffset(MergeOffset), MergeType(MergeType) {}
+
+ double score() const { return Score; }
+
+ size_t mergeOffset() const { return MergeOffset; }
+
+ MergeTypeTy mergeType() const { return MergeType; }
+
+ // returns 'true' iff Other is preferred other this
+ bool operator<(const MergeGainTy &Other) const {
+ return (Other.Score > EPS && Other.Score > Score + EPS);
+ }
+
+private:
+ double Score{-1.0};
+ size_t MergeOffset{0};
+ MergeTypeTy MergeType{MergeTypeTy::X_Y};
+};
+
+/// A node in CFG corresponding to a basic block.
+/// The class wraps several mutable fields utilized in the ExtTSP algorithm.
+class Block {
+public:
+ Block(const Block &) = delete;
+ Block(Block &&) = default;
+ Block &operator=(const Block &) = delete;
+ Block &operator=(Block &&) = default;
+
+ // The original index of the node in CFG.
+ size_t Index{0};
+ // The index of the block in the current chain.
+ size_t CurIndex{0};
+ // Size of the block in the binary.
+ uint64_t Size{0};
+ // Execution count of the block in the binary.
+ uint64_t ExecutionCount{0};
+ // Current chain of the basic block.
+ Chain *CurChain{nullptr};
+ // An offset of the block in the current chain.
+ mutable uint64_t EstimatedAddr{0};
+ // Fallthrough successor of the node in CFG.
+ Block *FallthroughSucc{nullptr};
+ // Fallthrough predecessor of the node in CFG.
+ Block *FallthroughPred{nullptr};
+ // Outgoing jumps from the block.
+ std::vector<std::pair<Block *, uint64_t>> OutJumps;
+ // Incoming jumps to the block.
+ std::vector<std::pair<Block *, uint64_t>> InJumps;
+
+public:
+ explicit Block(size_t Index, uint64_t Size_, uint64_t EC)
+ : Index(Index), Size(Size_), ExecutionCount(EC) {}
+};
+
+/// A chain (ordered sequence) of CFG nodes.
+class Chain {
+public:
+ Chain(const Chain &) = delete;
+ Chain(Chain &&) = default;
+ Chain &operator=(const Chain &) = delete;
+ Chain &operator=(Chain &&) = default;
+
+ explicit Chain(size_t Id, Block *Block)
+ : Id(Id), IsEntry(Block->Index == 0), Score(0), Blocks(1, Block) {}
+
+ size_t id() const { return Id; }
+
+ bool isEntryPoint() const { return IsEntry; }
+
+ double score() const { return Score; }
+
+ void setScore(double NewScore) { Score = NewScore; }
+
+ const std::vector<Block *> &blocks() const { return Blocks; }
+
+ const std::vector<std::pair<Chain *, Edge *>> &edges() const { return Edges; }
+
+ Edge *getEdge(Chain *Other) const {
+ for (auto It : Edges) {
+ if (It.first == Other)
+ return It.second;
+ }
+ return nullptr;
+ }
+
+ void removeEdge(Chain *Other) {
+ auto It = Edges.begin();
+ while (It != Edges.end()) {
+ if (It->first == Other) {
+ Edges.erase(It);
+ return;
+ }
+ It++;
+ }
+ }
+
+ void addEdge(Chain *Other, Edge *Edge) {
+ Edges.push_back(std::make_pair(Other, Edge));
+ }
+
+ void merge(Chain *Other, const std::vector<Block *> &MergedBlocks) {
+ Blocks = MergedBlocks;
+ IsEntry |= Other->IsEntry;
+ // Update the block's chains
+ for (size_t Idx = 0; Idx < Blocks.size(); Idx++) {
+ Blocks[Idx]->CurChain = this;
+ Blocks[Idx]->CurIndex = Idx;
+ }
+ }
+
+ void mergeEdges(Chain *Other);
+
+ void clear() {
+ Blocks.clear();
+ Edges.clear();
+ }
+
+private:
+ // Unique chain identifier.
+ size_t Id;
+ // Whether the chain starts with the entry basic block.
+ bool IsEntry;
+ // Cached ext-tsp score for the chain.
+ double Score;
+ // Blocks of the chain.
+ std::vector<Block *> Blocks;
+ // Adjacent chains and corresponding edges (lists of jumps).
+ std::vector<std::pair<Chain *, Edge *>> Edges;
+};
+
+/// An edge in CFG reprsenting jumps between two chains.
+/// When blocks are merged into chains, the edges are combined too so that
+/// there is always at most one edge between a pair of chains
+class Edge {
+public:
+ Edge(const Edge &) = delete;
+ Edge(Edge &&) = default;
+ Edge &operator=(const Edge &) = delete;
+ Edge &operator=(Edge &&) = default;
+
+ explicit Edge(Block *SrcBlock, Block *DstBlock, uint64_t EC)
+ : SrcChain(SrcBlock->CurChain), DstChain(DstBlock->CurChain),
+ Jumps(1, std::make_pair(std::make_pair(SrcBlock, DstBlock), EC)) {}
+
+ const JumpList &jumps() const { return Jumps; }
+
+ void changeEndpoint(Chain *From, Chain *To) {
+ if (From == SrcChain)
+ SrcChain = To;
+ if (From == DstChain)
+ DstChain = To;
+ }
+
+ void appendJump(Block *SrcBlock, Block *DstBlock, uint64_t EC) {
+ Jumps.push_back(std::make_pair(std::make_pair(SrcBlock, DstBlock), EC));
+ }
+
+ void moveJumps(Edge *Other) {
+ Jumps.insert(Jumps.end(), Other->Jumps.begin(), Other->Jumps.end());
+ Other->Jumps.clear();
+ }
+
+ bool hasCachedMergeGain(Chain *Src, Chain *Dst) const {
+ return Src == SrcChain ? CacheValidForward : CacheValidBackward;
+ }
+
+ MergeGainTy getCachedMergeGain(Chain *Src, Chain *Dst) const {
+ return Src == SrcChain ? CachedGainForward : CachedGainBackward;
+ }
+
+ void setCachedMergeGain(Chain *Src, Chain *Dst, MergeGainTy MergeGain) {
+ if (Src == SrcChain) {
+ CachedGainForward = MergeGain;
+ CacheValidForward = true;
+ } else {
+ CachedGainBackward = MergeGain;
+ CacheValidBackward = true;
+ }
+ }
+
+ void invalidateCache() {
+ CacheValidForward = false;
+ CacheValidBackward = false;
+ }
+
+private:
+ // Source chain.
+ Chain *SrcChain{nullptr};
+ // Destination chain.
+ Chain *DstChain{nullptr};
+ // Original jumps in the binary with correspinding execution counts.
+ JumpList Jumps;
+ // Cached ext-tsp value for merging the pair of chains.
+ // Since the gain of merging (Src, Dst) and (Dst, Src) might be different,
+ // we store both values here.
+ MergeGainTy CachedGainForward;
+ MergeGainTy CachedGainBackward;
+ // Whether the cached value must be recomputed.
+ bool CacheValidForward{false};
+ bool CacheValidBackward{false};
+};
+
+void Chain::mergeEdges(Chain *Other) {
+ assert(this != Other && "cannot merge a chain with itself");
+
+ // Update edges adjacent to chain Other
+ for (auto EdgeIt : Other->Edges) {
+ const auto DstChain = EdgeIt.first;
+ const auto DstEdge = EdgeIt.second;
+ const auto TargetChain = DstChain == Other ? this : DstChain;
+ auto CurEdge = getEdge(TargetChain);
+ if (CurEdge == nullptr) {
+ DstEdge->changeEndpoint(Other, this);
+ this->addEdge(TargetChain, DstEdge);
+ if (DstChain != this && DstChain != Other) {
+ DstChain->addEdge(this, DstEdge);
+ }
+ } else {
+ CurEdge->moveJumps(DstEdge);
+ }
+ // Cleanup leftover edge
+ if (DstChain != Other) {
+ DstChain->removeEdge(Other);
+ }
+ }
+}
+
+/// A wrapper around three chains of basic blocks; it is used to avoid extra
+/// instantiation of the vectors.
+class MergedChain {
+public:
+ MergedChain(BlockIter Begin1, BlockIter End1, BlockIter Begin2 = BlockIter(),
+ BlockIter End2 = BlockIter(), BlockIter Begin3 = BlockIter(),
+ BlockIter End3 = BlockIter())
+ : Begin1(Begin1), End1(End1), Begin2(Begin2), End2(End2), Begin3(Begin3),
+ End3(End3) {}
+
+ template <typename F> void forEach(const F &Func) const {
+ for (auto It = Begin1; It != End1; It++)
+ Func(*It);
+ for (auto It = Begin2; It != End2; It++)
+ Func(*It);
+ for (auto It = Begin3; It != End3; It++)
+ Func(*It);
+ }
+
+ std::vector<Block *> getBlocks() const {
+ std::vector<Block *> Result;
+ Result.reserve(std::distance(Begin1, End1) + std::distance(Begin2, End2) +
+ std::distance(Begin3, End3));
+ Result.insert(Result.end(), Begin1, End1);
+ Result.insert(Result.end(), Begin2, End2);
+ Result.insert(Result.end(), Begin3, End3);
+ return Result;
+ }
+
+ const Block *getFirstBlock() const { return *Begin1; }
+
+private:
+ BlockIter Begin1;
+ BlockIter End1;
+ BlockIter Begin2;
+ BlockIter End2;
+ BlockIter Begin3;
+ BlockIter End3;
+};
+
+/// The implementation of the ExtTSP algorithm.
+class ExtTSPImpl {
+ using NodeOrder = std::vector<uint64_t>;
+ using NodeSizeMap = DenseMap<uint64_t, uint64_t>;
+ using NodeCountMap = DenseMap<uint64_t, uint64_t>;
+ using EdgeT = std::pair<uint64_t, uint64_t>;
+ using EdgeCountMap = DenseMap<EdgeT, uint64_t>;
+
+public:
+ ExtTSPImpl(size_t NumNodes, const NodeSizeMap &NodeSizes,
+ const NodeCountMap &NodeCounts, const EdgeCountMap &EdgeCounts)
+ : NumNodes(NumNodes) {
+ initialize(NodeSizes, NodeCounts, EdgeCounts);
+ }
+
+ /// Run the algorithm and return an ordering of basic block.
+ void run(std::vector<uint64_t> &Result) {
+ // Pass 1: Merge blocks with their fallthrough successors
+ mergeFallthroughs();
+
+ // Pass 2: Merge pairs of chains while improving the ExtTSP objective
+ mergeChainPairs();
+
+ // Pass 3: Merge cold blocks to reduce code size
+ mergeColdChains();
+
+ // Collect blocks from all chains
+ concatChains(Result);
+ }
+
+private:
+ /// Initialize algorithm's data structures.
+ void initialize(const NodeSizeMap &NodeSizes, const NodeCountMap &NodeCounts,
+ const EdgeCountMap &EdgeCounts) {
+ // Initialize blocks
+ AllBlocks.reserve(NumNodes);
+ for (uint64_t Node = 0; Node < NumNodes; Node++) {
+ uint64_t Size = std::max<uint64_t>(NodeSizes.find(Node)->second, 1ULL);
+ uint64_t ExecutionCount = NodeCounts.find(Node)->second;
+ // The execution count of the entry block is set to at least 1
+ if (Node == 0 && ExecutionCount == 0)
+ ExecutionCount = 1;
+ AllBlocks.emplace_back(Node, Size, ExecutionCount);
+ }
+
+ // Initialize edges for the blocks and compute their total in/out weights
+ SuccNodes = std::vector<std::vector<uint64_t>>(NumNodes);
+ PredNodes = std::vector<std::vector<uint64_t>>(NumNodes);
+ size_t NumEdges = 0;
+ for (auto It : EdgeCounts) {
+ auto Pred = It.first.first;
+ auto Succ = It.first.second;
+ // Ignore self-edges
+ if (Pred == Succ)
+ continue;
+
+ SuccNodes[Pred].push_back(Succ);
+ PredNodes[Succ].push_back(Pred);
+ auto Count = It.second;
+ if (Count > 0) {
+ auto &Block = AllBlocks[Pred];
+ auto &SuccBlock = AllBlocks[Succ];
+ SuccBlock.InJumps.push_back(std::make_pair(&Block, Count));
+ Block.OutJumps.push_back(std::make_pair(&SuccBlock, Count));
+ NumEdges++;
+ }
+ }
+
+ // Initialize chains
+ AllChains.reserve(NumNodes);
+ HotChains.reserve(NumNodes);
+ for (auto &Block : AllBlocks) {
+ AllChains.emplace_back(Block.Index, &Block);
+ Block.CurChain = &AllChains.back();
+ if (Block.ExecutionCount > 0) {
+ HotChains.push_back(&AllChains.back());
+ }
+ }
+
+ // Initialize edges
+ AllEdges.reserve(NumEdges);
+ for (auto &Block : AllBlocks) {
+ for (auto &Jump : Block.OutJumps) {
+ const auto SuccBlock = Jump.first;
+ auto CurEdge = Block.CurChain->getEdge(SuccBlock->CurChain);
+ // this edge is already present in the graph
+ if (CurEdge != nullptr) {
+ assert(SuccBlock->CurChain->getEdge(Block.CurChain) != nullptr);
+ CurEdge->appendJump(&Block, SuccBlock, Jump.second);
+ continue;
+ }
+ // this is a new edge
+ AllEdges.emplace_back(&Block, SuccBlock, Jump.second);
+ Block.CurChain->addEdge(SuccBlock->CurChain, &AllEdges.back());
+ SuccBlock->CurChain->addEdge(Block.CurChain, &AllEdges.back());
+ }
+ }
+ assert(AllEdges.size() <= NumEdges && "Incorrect number of created edges");
+ }
+
+ /// For a pair of blocks, A and B, block B is the fallthrough successor of A,
+ /// if (i) all jumps (based on profile) from A goes to B and (ii) all jumps
+ /// to B are from A. Such blocks should be adjacent in the optimal ordering;
+ /// the method finds and merges such pairs of blocks.
+ void mergeFallthroughs() {
+ // Find fallthroughs based on edge weights
+ for (auto &Block : AllBlocks) {
+ if (SuccNodes[Block.Index].size() == 1 &&
+ PredNodes[SuccNodes[Block.Index][0]].size() == 1 &&
+ SuccNodes[Block.Index][0] != 0) {
+ size_t SuccIndex = SuccNodes[Block.Index][0];
+ Block.FallthroughSucc = &AllBlocks[SuccIndex];
+ AllBlocks[SuccIndex].FallthroughPred = &Block;
+ }
+ }
+
+ // There might be 'cycles' in the fallthrough dependencies (since profile
+ // data isn't 100% accurate).
+ // Break the cycles by choosing the block with smallest index as the tail
+ for (auto &Block : AllBlocks) {
+ if (Block.FallthroughSucc == nullptr || Block.FallthroughPred == nullptr)
+ continue;
+
+ auto SuccBlock = Block.FallthroughSucc;
+ while (SuccBlock != nullptr && SuccBlock != &Block) {
+ SuccBlock = SuccBlock->FallthroughSucc;
+ }
+ if (SuccBlock == nullptr)
+ continue;
+ // Break the cycle
+ AllBlocks[Block.FallthroughPred->Index].FallthroughSucc = nullptr;
+ Block.FallthroughPred = nullptr;
+ }
+
+ // Merge blocks with their fallthrough successors
+ for (auto &Block : AllBlocks) {
+ if (Block.FallthroughPred == nullptr &&
+ Block.FallthroughSucc != nullptr) {
+ auto CurBlock = &Block;
+ while (CurBlock->FallthroughSucc != nullptr) {
+ const auto NextBlock = CurBlock->FallthroughSucc;
+ mergeChains(Block.CurChain, NextBlock->CurChain, 0, MergeTypeTy::X_Y);
+ CurBlock = NextBlock;
+ }
+ }
+ }
+ }
+
+ /// Merge pairs of chains while improving the ExtTSP objective.
+ void mergeChainPairs() {
+ /// Deterministically compare pairs of chains
+ auto compareChainPairs = [](const Chain *A1, const Chain *B1,
+ const Chain *A2, const Chain *B2) {
+ if (A1 != A2)
+ return A1->id() < A2->id();
+ return B1->id() < B2->id();
+ };
+
+ while (HotChains.size() > 1) {
+ Chain *BestChainPred = nullptr;
+ Chain *BestChainSucc = nullptr;
+ auto BestGain = MergeGainTy();
+ // Iterate over all pairs of chains
+ for (auto ChainPred : HotChains) {
+ // Get candidates for merging with the current chain
+ for (auto EdgeIter : ChainPred->edges()) {
+ auto ChainSucc = EdgeIter.first;
+ auto ChainEdge = EdgeIter.second;
+ // Ignore loop edges
+ if (ChainPred == ChainSucc)
+ continue;
+
+ // Compute the gain of merging the two chains
+ auto CurGain = mergeGain(ChainPred, ChainSucc, ChainEdge);
+ if (CurGain.score() <= EPS)
+ continue;
+
+ if (BestGain < CurGain ||
+ (std::abs(CurGain.score() - BestGain.score()) < EPS &&
+ compareChainPairs(ChainPred, ChainSucc, BestChainPred,
+ BestChainSucc))) {
+ BestGain = CurGain;
+ BestChainPred = ChainPred;
+ BestChainSucc = ChainSucc;
+ }
+ }
+ }
+
+ // Stop merging when there is no improvement
+ if (BestGain.score() <= EPS)
+ break;
+
+ // Merge the best pair of chains
+ mergeChains(BestChainPred, BestChainSucc, BestGain.mergeOffset(),
+ BestGain.mergeType());
+ }
+ }
+
+ /// Merge cold blocks to reduce code size.
+ void mergeColdChains() {
+ for (size_t SrcBB = 0; SrcBB < NumNodes; SrcBB++) {
+ // Iterating over neighbors in the reverse order to make sure original
+ // fallthrough jumps are merged first
+ size_t NumSuccs = SuccNodes[SrcBB].size();
+ for (size_t Idx = 0; Idx < NumSuccs; Idx++) {
+ auto DstBB = SuccNodes[SrcBB][NumSuccs - Idx - 1];
+ auto SrcChain = AllBlocks[SrcBB].CurChain;
+ auto DstChain = AllBlocks[DstBB].CurChain;
+ if (SrcChain != DstChain && !DstChain->isEntryPoint() &&
+ SrcChain->blocks().back()->Index == SrcBB &&
+ DstChain->blocks().front()->Index == DstBB) {
+ mergeChains(SrcChain, DstChain, 0, MergeTypeTy::X_Y);
+ }
+ }
+ }
+ }
+
+ /// Compute ExtTSP score for a given order of basic blocks.
+ double score(const MergedChain &MergedBlocks, const JumpList &Jumps) const {
+ if (Jumps.empty())
+ return 0.0;
+ uint64_t CurAddr = 0;
+ MergedBlocks.forEach([&](const Block *BB) {
+ BB->EstimatedAddr = CurAddr;
+ CurAddr += BB->Size;
+ });
+
+ double Score = 0;
+ for (auto &Jump : Jumps) {
+ const auto SrcBlock = Jump.first.first;
+ const auto DstBlock = Jump.first.second;
+ Score += extTSPScore(SrcBlock->EstimatedAddr, SrcBlock->Size,
+ DstBlock->EstimatedAddr, Jump.second);
+ }
+ return Score;
+ }
+
+ /// Compute the gain of merging two chains.
+ ///
+ /// The function considers all possible ways of merging two chains and
+ /// computes the one having the largest increase in ExtTSP objective. The
+ /// result is a pair with the first element being the gain and the second
+ /// element being the corresponding merging type.
+ MergeGainTy mergeGain(Chain *ChainPred, Chain *ChainSucc, Edge *Edge) const {
+ if (Edge->hasCachedMergeGain(ChainPred, ChainSucc)) {
+ return Edge->getCachedMergeGain(ChainPred, ChainSucc);
+ }
+
+ // Precompute jumps between ChainPred and ChainSucc
+ auto Jumps = Edge->jumps();
+ auto EdgePP = ChainPred->getEdge(ChainPred);
+ if (EdgePP != nullptr)
+ Jumps.insert(Jumps.end(), EdgePP->jumps().begin(), EdgePP->jumps().end());
+ assert(Jumps.size() > 0 && "trying to merge chains w/o jumps");
+
+ MergeGainTy Gain = MergeGainTy();
+ // Try to concatenate two chains w/o splitting
+ Gain = computeMergeGain(Gain, ChainPred, ChainSucc, Jumps, 0,
+ MergeTypeTy::X_Y);
+
+ // Attach (a part of) ChainPred before the first block of ChainSucc
+ for (auto &Jump : ChainSucc->blocks().front()->InJumps) {
+ const auto SrcBlock = Jump.first;
+ if (SrcBlock->CurChain != ChainPred)
+ continue;
+ if (SrcBlock->FallthroughSucc != nullptr)
+ continue;
+ size_t Offset = SrcBlock->CurIndex + 1;
+ if (Offset == ChainPred->blocks().size())
+ continue;
+
+ Gain = computeMergeGain(Gain, ChainPred, ChainSucc, Jumps, Offset,
+ MergeTypeTy::X1_Y_X2);
+ Gain = computeMergeGain(Gain, ChainPred, ChainSucc, Jumps, Offset,
+ MergeTypeTy::X2_X1_Y);
+ }
+
+ // Attach (a part of) ChainPred after the last block of ChainSucc
+ for (auto &Jump : ChainSucc->blocks().back()->OutJumps) {
+ const auto DstBlock = Jump.first;
+ if (DstBlock->CurChain != ChainPred)
+ continue;
+ if (DstBlock->FallthroughPred != nullptr)
+ continue;
+ size_t Offset = DstBlock->CurIndex;
+ if (Offset == 0)
+ continue;
+
+ Gain = computeMergeGain(Gain, ChainPred, ChainSucc, Jumps, Offset,
+ MergeTypeTy::X1_Y_X2);
+ Gain = computeMergeGain(Gain, ChainPred, ChainSucc, Jumps, Offset,
+ MergeTypeTy::Y_X2_X1);
+ }
+
+ // Try to break ChainPred in various ways and concatenate with ChainSucc
+ if (ChainPred->blocks().size() <= ChainSplitThreshold) {
+ for (size_t Offset = 1; Offset < ChainPred->blocks().size(); Offset++) {
+ auto BB1 = ChainPred->blocks()[Offset - 1];
+
+ // Skip the splitting if it breaks FT successors
+ if (BB1->FallthroughSucc != nullptr) {
+#ifndef NDEBUG
+ auto BB2 = ChainPred->blocks()[Offset];
+ assert(BB1->FallthroughSucc == BB2 && "Fallthrough not preserved");
+#endif
+ continue;
+ }
+
+ // Try to split the chain in different ways
+ Gain = computeMergeGain(Gain, ChainPred, ChainSucc, Jumps, Offset,
+ MergeTypeTy::X1_Y_X2);
+ Gain = computeMergeGain(Gain, ChainPred, ChainSucc, Jumps, Offset,
+ MergeTypeTy::Y_X2_X1);
+ Gain = computeMergeGain(Gain, ChainPred, ChainSucc, Jumps, Offset,
+ MergeTypeTy::X2_X1_Y);
+ }
+ }
+ Edge->setCachedMergeGain(ChainPred, ChainSucc, Gain);
+ return Gain;
+ }
+
+ /// Merge two chains and update the best gain.
+ MergeGainTy computeMergeGain(const MergeGainTy &CurGain,
+ const Chain *ChainPred, const Chain *ChainSucc,
+ const JumpList &Jumps, size_t MergeOffset,
+ MergeTypeTy MergeType) const {
+ auto MergedBlocks = mergeBlocks(ChainPred->blocks(), ChainSucc->blocks(),
+ MergeOffset, MergeType);
+
+ // Do not allow a merge that does not preserve the original entry block
+ if ((ChainPred->isEntryPoint() || ChainSucc->isEntryPoint()) &&
+ MergedBlocks.getFirstBlock()->Index != 0)
+ return CurGain;
+
+ // The gain for the new chain
+ const auto NewScore = score(MergedBlocks, Jumps) - ChainPred->score();
+ auto NewGain = MergeGainTy(NewScore, MergeOffset, MergeType);
+ return CurGain < NewGain ? NewGain : CurGain;
+ }
+
+ /// Merge two chains of blocks respecting a given merge 'type' and 'offset'.
+ ///
+ /// If MergeType == 0, then the result is a concatentation of two chains.
+ /// Otherwise, the first chain is cut into two sub-chains at the offset,
+ /// and merged using all possible ways of concatenating three chains.
+ MergedChain mergeBlocks(const std::vector<Block *> &X,
+ const std::vector<Block *> &Y, size_t MergeOffset,
+ MergeTypeTy MergeType) const {
+ // Split the first chain, X, into X1 and X2
+ BlockIter BeginX1 = X.begin();
+ BlockIter EndX1 = X.begin() + MergeOffset;
+ BlockIter BeginX2 = X.begin() + MergeOffset;
+ BlockIter EndX2 = X.end();
+ BlockIter BeginY = Y.begin();
+ BlockIter EndY = Y.end();
+
+ // Construct a new chain from the three existing ones
+ switch (MergeType) {
+ case MergeTypeTy::X_Y:
+ return MergedChain(BeginX1, EndX2, BeginY, EndY);
+ case MergeTypeTy::X1_Y_X2:
+ return MergedChain(BeginX1, EndX1, BeginY, EndY, BeginX2, EndX2);
+ case MergeTypeTy::Y_X2_X1:
+ return MergedChain(BeginY, EndY, BeginX2, EndX2, BeginX1, EndX1);
+ case MergeTypeTy::X2_X1_Y:
+ return MergedChain(BeginX2, EndX2, BeginX1, EndX1, BeginY, EndY);
+ }
+ llvm_unreachable("unexpected chain merge type");
+ }
+
+ /// Merge chain From into chain Into, update the list of active chains,
+ /// adjacency information, and the corresponding cached values.
+ void mergeChains(Chain *Into, Chain *From, size_t MergeOffset,
+ MergeTypeTy MergeType) {
+ assert(Into != From && "a chain cannot be merged with itself");
+
+ // Merge the blocks
+ auto MergedBlocks =
+ mergeBlocks(Into->blocks(), From->blocks(), MergeOffset, MergeType);
+ Into->merge(From, MergedBlocks.getBlocks());
+ Into->mergeEdges(From);
+ From->clear();
+
+ // Update cached ext-tsp score for the new chain
+ auto SelfEdge = Into->getEdge(Into);
+ if (SelfEdge != nullptr) {
+ MergedBlocks = MergedChain(Into->blocks().begin(), Into->blocks().end());
+ Into->setScore(score(MergedBlocks, SelfEdge->jumps()));
+ }
+
+ // Remove chain From from the list of active chains
+ auto Iter = std::remove(HotChains.begin(), HotChains.end(), From);
+ HotChains.erase(Iter, HotChains.end());
+
+ // Invalidate caches
+ for (auto EdgeIter : Into->edges()) {
+ EdgeIter.second->invalidateCache();
+ }
+ }
+
+ /// Concatenate all chains into a final order of blocks.
+ void concatChains(std::vector<uint64_t> &Order) {
+ // Collect chains and calculate basic stats (for their ordering)
+ std::vector<Chain *> SortedChains;
+ DenseMap<const Chain *, double> ChainDensity;
+ for (auto &Chain : AllChains) {
+ if (!Chain.blocks().empty()) {
+ SortedChains.push_back(&Chain);
+ // using doubles to avoid overflow of ExecutionCount
+ double Size = 0;
+ double ExecutionCount = 0;
+ for (auto Block : Chain.blocks()) {
+ Size += static_cast<double>(Block->Size);
+ ExecutionCount += static_cast<double>(Block->ExecutionCount);
+ }
+ assert(Size > 0 && "a chain of zero size");
+ ChainDensity[&Chain] = ExecutionCount / Size;
+ }
+ }
+
+ // Sorting chains by density in the decreasing order
+ std::stable_sort(SortedChains.begin(), SortedChains.end(),
+ [&](const Chain *C1, const Chain *C2) {
+ // Original entry point to the front
+ if (C1->isEntryPoint() != C2->isEntryPoint()) {
+ if (C1->isEntryPoint())
+ return true;
+ if (C2->isEntryPoint())
+ return false;
+ }
+
+ const double D1 = ChainDensity[C1];
+ const double D2 = ChainDensity[C2];
+ if (D1 != D2)
+ return D1 > D2;
+
+ // Making the order deterministic
+ return C1->id() < C2->id();
+ });
+
+ // Collect the basic blocks in the order specified by their chains
+ Order.reserve(NumNodes);
+ for (auto Chain : SortedChains) {
+ for (auto Block : Chain->blocks()) {
+ Order.push_back(Block->Index);
+ }
+ }
+ }
+
+private:
+ /// The number of nodes in the graph.
+ const size_t NumNodes;
+
+ /// Successors of each node.
+ std::vector<std::vector<uint64_t>> SuccNodes;
+
+ /// Predecessors of each node.
+ std::vector<std::vector<uint64_t>> PredNodes;
+
+ /// All basic blocks.
+ std::vector<Block> AllBlocks;
+
+ /// All chains of basic blocks.
+ std::vector<Chain> AllChains;
+
+ /// Active chains. The vector gets updated at runtime when chains are merged.
+ std::vector<Chain *> HotChains;
+
+ /// All edges between chains.
+ std::vector<Edge> AllEdges;
+};
+
+} // end of anonymous namespace
+
+std::vector<uint64_t> llvm::applyExtTspLayout(
+ const DenseMap<uint64_t, uint64_t> &NodeSizes,
+ const DenseMap<uint64_t, uint64_t> &NodeCounts,
+ const DenseMap<std::pair<uint64_t, uint64_t>, uint64_t> &EdgeCounts) {
+ size_t NumNodes = NodeSizes.size();
+ // Verify correctness of the input data.
+ assert(NodeCounts.size() == NodeSizes.size() && "Incorrect input");
+ assert(NumNodes > 2 && "Incorrect input");
+ for (size_t Node = 0; Node < NumNodes; Node++) {
+ assert(NodeSizes.count(Node) > 0 && "Missing node size");
+ assert(NodeCounts.count(Node) > 0 && "Missing node count");
+ }
+
+ // Apply the reordering algorithm.
+ auto Alg = ExtTSPImpl(NumNodes, NodeSizes, NodeCounts, EdgeCounts);
+ std::vector<uint64_t> Result;
+ Alg.run(Result);
+
+ // Verify correctness of the output.
+ assert(Result.front() == 0 && "Original entry point is not preserved");
+ assert(Result.size() == NumNodes && "Incorrect size of reordered layout");
+ return Result;
+}
+
+uint64_t llvm::calcExtTspScore(
+ const std::vector<uint64_t> &Order,
+ const DenseMap<uint64_t, uint64_t> &NodeSizes,
+ const DenseMap<uint64_t, uint64_t> &NodeCounts,
+ const DenseMap<std::pair<uint64_t, uint64_t>, uint64_t> &EdgeCounts) {
+ DenseMap<uint64_t, uint64_t> BlockIndex;
+ for (size_t Idx = 0; Idx < Order.size(); Idx++) {
+ BlockIndex[Order[Idx]] = Idx;
+ }
+
+ uint64_t Score = 0;
+ for (auto It : EdgeCounts) {
+ auto Pred = It.first.first;
+ assert(BlockIndex.find(Pred) != BlockIndex.end() && "Block not found");
+ auto Succ = It.first.second;
+ assert(BlockIndex.find(Succ) != BlockIndex.end() && "Block not found");
+ // Incresing the score if the two nodes are adjacent in the order.
+ if (BlockIndex[Pred] + 1 == BlockIndex[Succ])
+ Score += It.second;
+ }
+ return Score;
+}
+
+uint64_t llvm::calcExtTspScore(
+ const DenseMap<uint64_t, uint64_t> &NodeSizes,
+ const DenseMap<uint64_t, uint64_t> &NodeCounts,
+ const DenseMap<std::pair<uint64_t, uint64_t>, uint64_t> &EdgeCounts) {
+ std::vector<uint64_t> Order;
+ Order.reserve(NodeSizes.size());
+ for (size_t Idx = 0; Idx < NodeSizes.size(); Idx++) {
+ Order.push_back(Idx);
+ }
+ return calcExtTspScore(Order, NodeSizes, NodeCounts, EdgeCounts);
+}
diff --git a/llvm/test/CodeGen/X86/code_placement_ext_tsp.ll b/llvm/test/CodeGen/X86/code_placement_ext_tsp.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/X86/code_placement_ext_tsp.ll
@@ -0,0 +1,222 @@
+; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux -enable-ext-tsp-block-placement=1 < %s | FileCheck %s
+
+define void @func1() {
+; Test that the placement positions the most likely sucessor first
+;
+; CHECK-LABEL: func1:
+; CHECK: b0
+; CHECK: b2
+; CHECK: b1
+
+b0:
+ %call = call zeroext i1 @a()
+ br i1 %call, label %b1, label %b2, !prof !1
+
+b1:
+ call void @d()
+ call void @d()
+ call void @d()
+ br label %b2
+
+b2:
+ call void @e()
+ ret void
+}
+
+
+define void @func2() !prof !2 {
+; Test that the placement positions the hot chain is placed continuosly
+;
+; +----+ [7] +-------+
+; | b1 | <----- | b0 |
+; +----+ +-------+
+; | |
+; | | [15]
+; | v
+; | +-------+
+; | | b3 |
+; | +-------+
+; | |
+; | | [15]
+; | v
+; | +-------+ [31]
+; | | | -------+
+; | | b4 | |
+; | | | <------+
+; | +-------+
+; | |
+; | | [15]
+; | v
+; | [7] +-------+
+; +---------> | b2 |
+; +-------+
+;
+; CHECK-LABEL: func2:
+; CHECK: b0
+; CHECK: b3
+; CHECK: b4
+; CHECK: b2
+; CHECK: b1
+
+b0:
+ call void @d()
+ call void @d()
+ call void @d()
+ %call = call zeroext i1 @a()
+ br i1 %call, label %b1, label %b3, !prof !3
+
+b1:
+ call void @d()
+ br label %b2
+
+b2:
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ ret void
+
+b3:
+ call void @d()
+ br label %b4
+
+b4:
+ call void @d()
+ %call2 = call zeroext i1 @a()
+ br i1 %call2, label %b2, label %b4, !prof !4
+}
+
+
+define void @func3() !prof !5 {
+; A larger test where it is beneficial for locality to break the loop
+;
+; +--------+
+; | b0 |
+; +--------+
+; |
+; | [177]
+; v
+; +----+ [177] +---------------------------+
+; | b5 | <------- | b1 |
+; +----+ +---------------------------+
+; | ^ ^
+; | [196] | [124] | [70]
+; v | |
+; +----+ [70] +--------+ | |
+; | b4 | <------- | b2 | | |
+; +----+ +--------+ | |
+; | | | |
+; | | [124] | |
+; | v | |
+; | +--------+ | |
+; | | b3 | -+ |
+; | +--------+ |
+; | |
+; +-----------------------------------+
+;
+; CHECK-LABEL: func3:
+; CHECK: b0
+; CHECK: b1
+; CHECK: b2
+; CHECK: b3
+; CHECK: b5
+; CHECK: b4
+
+b0:
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ call void @f()
+ br label %b1
+
+b1:
+ %call = call zeroext i1 @a()
+ br i1 %call, label %b5, label %b2, !prof !6
+
+b2:
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ %call2 = call zeroext i1 @a()
+ br i1 %call2, label %b3, label %b4, !prof !7
+
+b3:
+ call void @d()
+ call void @f()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ call void @d()
+ br label %b1
+
+b4:
+ call void @d()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ call void @e()
+ br label %b1
+
+b5:
+ ret void
+}
+
+declare zeroext i1 @a()
+declare void @d()
+declare void @e()
+declare void @g()
+declare void @f()
+
+!1 = !{!"branch_weights", i32 40, i32 100}
+!2 = !{!"function_entry_count", i64 2200}
+!3 = !{!"branch_weights", i32 700, i32 1500}
+!4 = !{!"branch_weights", i32 1500, i32 3100}
+!5 = !{!"function_entry_count", i64 177}
+!6 = !{!"branch_weights", i32 177, i32 196}
+!7 = !{!"branch_weights", i32 125, i32 70}