Bug Summary

File:build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Transforms/Utils/CodeLayout.cpp
Warning:line 629, column 27
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name CodeLayout.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Transforms/Utils -I include -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-10-03-140002-15933-1 -x c++ /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Transforms/Utils/CodeLayout.cpp
1//===- CodeLayout.cpp - Implementation of code layout algorithms ----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// ExtTSP - layout of basic blocks with i-cache optimization.
10//
11// The algorithm tries to find a layout of nodes (basic blocks) of a given CFG
12// optimizing jump locality and thus processor I-cache utilization. This is
13// achieved via increasing the number of fall-through jumps and co-locating
14// frequently executed nodes together. The name follows the underlying
15// optimization problem, Extended-TSP, which is a generalization of classical
16// (maximum) Traveling Salesmen Problem.
17//
18// The algorithm is a greedy heuristic that works with chains (ordered lists)
19// of basic blocks. Initially all chains are isolated basic blocks. On every
20// iteration, we pick a pair of chains whose merging yields the biggest increase
21// in the ExtTSP score, which models how i-cache "friendly" a specific chain is.
22// A pair of chains giving the maximum gain is merged into a new chain. The
23// procedure stops when there is only one chain left, or when merging does not
24// increase ExtTSP. In the latter case, the remaining chains are sorted by
25// density in the decreasing order.
26//
27// An important aspect is the way two chains are merged. Unlike earlier
28// algorithms (e.g., based on the approach of Pettis-Hansen), two
29// chains, X and Y, are first split into three, X1, X2, and Y. Then we
30// consider all possible ways of gluing the three chains (e.g., X1YX2, X1X2Y,
31// X2X1Y, X2YX1, YX1X2, YX2X1) and choose the one producing the largest score.
32// This improves the quality of the final result (the search space is larger)
33// while keeping the implementation sufficiently fast.
34//
35// Reference:
36// * A. Newell and S. Pupyrev, Improved Basic Block Reordering,
37// IEEE Transactions on Computers, 2020
38// https://arxiv.org/abs/1809.04676
39//
40//===----------------------------------------------------------------------===//
41
42#include "llvm/Transforms/Utils/CodeLayout.h"
43#include "llvm/Support/CommandLine.h"
44
45using namespace llvm;
46#define DEBUG_TYPE"code-layout" "code-layout"
47
48cl::opt<bool> EnableExtTspBlockPlacement(
49 "enable-ext-tsp-block-placement", cl::Hidden, cl::init(false),
50 cl::desc("Enable machine block placement based on the ext-tsp model, "
51 "optimizing I-cache utilization."));
52
53cl::opt<bool> ApplyExtTspWithoutProfile(
54 "ext-tsp-apply-without-profile",
55 cl::desc("Whether to apply ext-tsp placement for instances w/o profile"),
56 cl::init(true), cl::Hidden);
57
58// Algorithm-specific params. The values are tuned for the best performance
59// of large-scale front-end bound binaries.
60static cl::opt<double> ForwardWeightCond(
61 "ext-tsp-forward-weight-cond", cl::ReallyHidden, cl::init(0.1),
62 cl::desc("The weight of conditional forward jumps for ExtTSP value"));
63
64static cl::opt<double> ForwardWeightUncond(
65 "ext-tsp-forward-weight-uncond", cl::ReallyHidden, cl::init(0.1),
66 cl::desc("The weight of unconditional forward jumps for ExtTSP value"));
67
68static cl::opt<double> BackwardWeightCond(
69 "ext-tsp-backward-weight-cond", cl::ReallyHidden, cl::init(0.1),
70 cl::desc("The weight of conditonal backward jumps for ExtTSP value"));
71
72static cl::opt<double> BackwardWeightUncond(
73 "ext-tsp-backward-weight-uncond", cl::ReallyHidden, cl::init(0.1),
74 cl::desc("The weight of unconditonal backward jumps for ExtTSP value"));
75
76static cl::opt<double> FallthroughWeightCond(
77 "ext-tsp-fallthrough-weight-cond", cl::ReallyHidden, cl::init(1.0),
78 cl::desc("The weight of conditional fallthrough jumps for ExtTSP value"));
79
80static cl::opt<double> FallthroughWeightUncond(
81 "ext-tsp-fallthrough-weight-uncond", cl::ReallyHidden, cl::init(1.05),
82 cl::desc("The weight of unconditional fallthrough jumps for ExtTSP value"));
83
84static cl::opt<unsigned> ForwardDistance(
85 "ext-tsp-forward-distance", cl::ReallyHidden, cl::init(1024),
86 cl::desc("The maximum distance (in bytes) of a forward jump for ExtTSP"));
87
88static cl::opt<unsigned> BackwardDistance(
89 "ext-tsp-backward-distance", cl::ReallyHidden, cl::init(640),
90 cl::desc("The maximum distance (in bytes) of a backward jump for ExtTSP"));
91
92// The maximum size of a chain created by the algorithm. The size is bounded
93// so that the algorithm can efficiently process extremely large instance.
94static cl::opt<unsigned>
95 MaxChainSize("ext-tsp-max-chain-size", cl::ReallyHidden, cl::init(4096),
96 cl::desc("The maximum size of a chain to create."));
97
98// The maximum size of a chain for splitting. Larger values of the threshold
99// may yield better quality at the cost of worsen run-time.
100static cl::opt<unsigned> ChainSplitThreshold(
101 "ext-tsp-chain-split-threshold", cl::ReallyHidden, cl::init(128),
102 cl::desc("The maximum size of a chain to apply splitting"));
103
104// The option enables splitting (large) chains along in-coming and out-going
105// jumps. This typically results in a better quality.
106static cl::opt<bool> EnableChainSplitAlongJumps(
107 "ext-tsp-enable-chain-split-along-jumps", cl::ReallyHidden, cl::init(true),
108 cl::desc("The maximum size of a chain to apply splitting"));
109
110namespace {
111
112// Epsilon for comparison of doubles.
113constexpr double EPS = 1e-8;
114
115// Compute the Ext-TSP score for a given jump.
116double jumpExtTSPScore(uint64_t JumpDist, uint64_t JumpMaxDist, uint64_t Count,
117 double Weight) {
118 if (JumpDist > JumpMaxDist)
119 return 0;
120 double Prob = 1.0 - static_cast<double>(JumpDist) / JumpMaxDist;
121 return Weight * Prob * Count;
122}
123
124// Compute the Ext-TSP score for a jump between a given pair of blocks,
125// using their sizes, (estimated) addresses and the jump execution count.
126double extTSPScore(uint64_t SrcAddr, uint64_t SrcSize, uint64_t DstAddr,
127 uint64_t Count, bool IsConditional) {
128 // Fallthrough
129 if (SrcAddr + SrcSize == DstAddr) {
130 return jumpExtTSPScore(0, 1, Count,
131 IsConditional ? FallthroughWeightCond
132 : FallthroughWeightUncond);
133 }
134 // Forward
135 if (SrcAddr + SrcSize < DstAddr) {
136 const uint64_t Dist = DstAddr - (SrcAddr + SrcSize);
137 return jumpExtTSPScore(Dist, ForwardDistance, Count,
138 IsConditional ? ForwardWeightCond
139 : ForwardWeightUncond);
140 }
141 // Backward
142 const uint64_t Dist = SrcAddr + SrcSize - DstAddr;
143 return jumpExtTSPScore(Dist, BackwardDistance, Count,
144 IsConditional ? BackwardWeightCond
145 : BackwardWeightUncond);
146}
147
148/// A type of merging two chains, X and Y. The former chain is split into
149/// X1 and X2 and then concatenated with Y in the order specified by the type.
150enum class MergeTypeTy : int { X_Y, X1_Y_X2, Y_X2_X1, X2_X1_Y };
151
152/// The gain of merging two chains, that is, the Ext-TSP score of the merge
153/// together with the corresponfiding merge 'type' and 'offset'.
154class MergeGainTy {
155public:
156 explicit MergeGainTy() = default;
157 explicit MergeGainTy(double Score, size_t MergeOffset, MergeTypeTy MergeType)
158 : Score(Score), MergeOffset(MergeOffset), MergeType(MergeType) {}
159
160 double score() const { return Score; }
161
162 size_t mergeOffset() const { return MergeOffset; }
163
164 MergeTypeTy mergeType() const { return MergeType; }
165
166 // Returns 'true' iff Other is preferred over this.
167 bool operator<(const MergeGainTy &Other) const {
168 return (Other.Score > EPS && Other.Score > Score + EPS);
169 }
170
171 // Update the current gain if Other is preferred over this.
172 void updateIfLessThan(const MergeGainTy &Other) {
173 if (*this < Other)
174 *this = Other;
175 }
176
177private:
178 double Score{-1.0};
179 size_t MergeOffset{0};
180 MergeTypeTy MergeType{MergeTypeTy::X_Y};
181};
182
183class Jump;
184class Chain;
185class ChainEdge;
186
187/// A node in the graph, typically corresponding to a basic block in CFG.
188class Block {
189public:
190 Block(const Block &) = delete;
191 Block(Block &&) = default;
192 Block &operator=(const Block &) = delete;
193 Block &operator=(Block &&) = default;
194
195 // The original index of the block in CFG.
196 size_t Index{0};
197 // The index of the block in the current chain.
198 size_t CurIndex{0};
199 // Size of the block in the binary.
200 uint64_t Size{0};
201 // Execution count of the block in the profile data.
202 uint64_t ExecutionCount{0};
203 // Current chain of the node.
204 Chain *CurChain{nullptr};
205 // An offset of the block in the current chain.
206 mutable uint64_t EstimatedAddr{0};
207 // Forced successor of the block in CFG.
208 Block *ForcedSucc{nullptr};
209 // Forced predecessor of the block in CFG.
210 Block *ForcedPred{nullptr};
211 // Outgoing jumps from the block.
212 std::vector<Jump *> OutJumps;
213 // Incoming jumps to the block.
214 std::vector<Jump *> InJumps;
215
216public:
217 explicit Block(size_t Index, uint64_t Size, uint64_t EC)
218 : Index(Index), Size(Size), ExecutionCount(EC) {}
219 bool isEntry() const { return Index == 0; }
220};
221
222/// An arc in the graph, typically corresponding to a jump between two blocks.
223class Jump {
224public:
225 Jump(const Jump &) = delete;
226 Jump(Jump &&) = default;
227 Jump &operator=(const Jump &) = delete;
228 Jump &operator=(Jump &&) = default;
229
230 // Source block of the jump.
231 Block *Source;
232 // Target block of the jump.
233 Block *Target;
234 // Execution count of the arc in the profile data.
235 uint64_t ExecutionCount{0};
236 // Whether the jump corresponds to a conditional branch.
237 bool IsConditional{false};
238
239public:
240 explicit Jump(Block *Source, Block *Target, uint64_t ExecutionCount)
241 : Source(Source), Target(Target), ExecutionCount(ExecutionCount) {}
242};
243
244/// A chain (ordered sequence) of blocks.
245class Chain {
246public:
247 Chain(const Chain &) = delete;
248 Chain(Chain &&) = default;
249 Chain &operator=(const Chain &) = delete;
250 Chain &operator=(Chain &&) = default;
251
252 explicit Chain(uint64_t Id, Block *Block)
253 : Id(Id), Score(0), Blocks(1, Block) {}
254
255 uint64_t id() const { return Id; }
256
257 bool isEntry() const { return Blocks[0]->Index == 0; }
258
259 bool isCold() const {
260 for (auto *Block : Blocks) {
261 if (Block->ExecutionCount > 0)
262 return false;
263 }
264 return true;
265 }
266
267 double score() const { return Score; }
268
269 void setScore(double NewScore) { Score = NewScore; }
270
271 const std::vector<Block *> &blocks() const { return Blocks; }
272
273 size_t numBlocks() const { return Blocks.size(); }
274
275 const std::vector<std::pair<Chain *, ChainEdge *>> &edges() const {
276 return Edges;
277 }
278
279 ChainEdge *getEdge(Chain *Other) const {
280 for (auto It : Edges) {
281 if (It.first == Other)
282 return It.second;
283 }
284 return nullptr;
285 }
286
287 void removeEdge(Chain *Other) {
288 auto It = Edges.begin();
289 while (It != Edges.end()) {
290 if (It->first == Other) {
291 Edges.erase(It);
292 return;
293 }
294 It++;
295 }
296 }
297
298 void addEdge(Chain *Other, ChainEdge *Edge) {
299 Edges.push_back(std::make_pair(Other, Edge));
300 }
301
302 void merge(Chain *Other, const std::vector<Block *> &MergedBlocks) {
303 Blocks = MergedBlocks;
304 // Update the block's chains
305 for (size_t Idx = 0; Idx < Blocks.size(); Idx++) {
306 Blocks[Idx]->CurChain = this;
307 Blocks[Idx]->CurIndex = Idx;
308 }
309 }
310
311 void mergeEdges(Chain *Other);
312
313 void clear() {
314 Blocks.clear();
315 Blocks.shrink_to_fit();
316 Edges.clear();
317 Edges.shrink_to_fit();
318 }
319
320private:
321 // Unique chain identifier.
322 uint64_t Id;
323 // Cached ext-tsp score for the chain.
324 double Score;
325 // Blocks of the chain.
326 std::vector<Block *> Blocks;
327 // Adjacent chains and corresponding edges (lists of jumps).
328 std::vector<std::pair<Chain *, ChainEdge *>> Edges;
329};
330
331/// An edge in CFG representing jumps between two chains.
332/// When blocks are merged into chains, the edges are combined too so that
333/// there is always at most one edge between a pair of chains
334class ChainEdge {
335public:
336 ChainEdge(const ChainEdge &) = delete;
337 ChainEdge(ChainEdge &&) = default;
338 ChainEdge &operator=(const ChainEdge &) = delete;
339 ChainEdge &operator=(ChainEdge &&) = default;
340
341 explicit ChainEdge(Jump *Jump)
342 : SrcChain(Jump->Source->CurChain), DstChain(Jump->Target->CurChain),
343 Jumps(1, Jump) {}
344
345 const std::vector<Jump *> &jumps() const { return Jumps; }
346
347 void changeEndpoint(Chain *From, Chain *To) {
348 if (From == SrcChain)
349 SrcChain = To;
350 if (From == DstChain)
351 DstChain = To;
352 }
353
354 void appendJump(Jump *Jump) { Jumps.push_back(Jump); }
355
356 void moveJumps(ChainEdge *Other) {
357 Jumps.insert(Jumps.end(), Other->Jumps.begin(), Other->Jumps.end());
358 Other->Jumps.clear();
359 Other->Jumps.shrink_to_fit();
360 }
361
362 bool hasCachedMergeGain(Chain *Src, Chain *Dst) const {
363 return Src == SrcChain ? CacheValidForward : CacheValidBackward;
364 }
365
366 MergeGainTy getCachedMergeGain(Chain *Src, Chain *Dst) const {
367 return Src == SrcChain ? CachedGainForward : CachedGainBackward;
368 }
369
370 void setCachedMergeGain(Chain *Src, Chain *Dst, MergeGainTy MergeGain) {
371 if (Src == SrcChain) {
372 CachedGainForward = MergeGain;
373 CacheValidForward = true;
374 } else {
375 CachedGainBackward = MergeGain;
376 CacheValidBackward = true;
377 }
378 }
379
380 void invalidateCache() {
381 CacheValidForward = false;
382 CacheValidBackward = false;
383 }
384
385private:
386 // Source chain.
387 Chain *SrcChain{nullptr};
388 // Destination chain.
389 Chain *DstChain{nullptr};
390 // Original jumps in the binary with correspinding execution counts.
391 std::vector<Jump *> Jumps;
392 // Cached ext-tsp value for merging the pair of chains.
393 // Since the gain of merging (Src, Dst) and (Dst, Src) might be different,
394 // we store both values here.
395 MergeGainTy CachedGainForward;
396 MergeGainTy CachedGainBackward;
397 // Whether the cached value must be recomputed.
398 bool CacheValidForward{false};
399 bool CacheValidBackward{false};
400};
401
402void Chain::mergeEdges(Chain *Other) {
403 assert(this != Other && "cannot merge a chain with itself")(static_cast <bool> (this != Other && "cannot merge a chain with itself"
) ? void (0) : __assert_fail ("this != Other && \"cannot merge a chain with itself\""
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 403, __extension__
__PRETTY_FUNCTION__))
;
404
405 // Update edges adjacent to chain Other
406 for (auto EdgeIt : Other->Edges) {
407 Chain *DstChain = EdgeIt.first;
408 ChainEdge *DstEdge = EdgeIt.second;
409 Chain *TargetChain = DstChain == Other ? this : DstChain;
410 ChainEdge *CurEdge = getEdge(TargetChain);
411 if (CurEdge == nullptr) {
412 DstEdge->changeEndpoint(Other, this);
413 this->addEdge(TargetChain, DstEdge);
414 if (DstChain != this && DstChain != Other) {
415 DstChain->addEdge(this, DstEdge);
416 }
417 } else {
418 CurEdge->moveJumps(DstEdge);
419 }
420 // Cleanup leftover edge
421 if (DstChain != Other) {
422 DstChain->removeEdge(Other);
423 }
424 }
425}
426
427using BlockIter = std::vector<Block *>::const_iterator;
428
429/// A wrapper around three chains of blocks; it is used to avoid extra
430/// instantiation of the vectors.
431class MergedChain {
432public:
433 MergedChain(BlockIter Begin1, BlockIter End1, BlockIter Begin2 = BlockIter(),
434 BlockIter End2 = BlockIter(), BlockIter Begin3 = BlockIter(),
435 BlockIter End3 = BlockIter())
436 : Begin1(Begin1), End1(End1), Begin2(Begin2), End2(End2), Begin3(Begin3),
437 End3(End3) {}
438
439 template <typename F> void forEach(const F &Func) const {
440 for (auto It = Begin1; It != End1; It++)
441 Func(*It);
442 for (auto It = Begin2; It != End2; It++)
443 Func(*It);
444 for (auto It = Begin3; It != End3; It++)
445 Func(*It);
446 }
447
448 std::vector<Block *> getBlocks() const {
449 std::vector<Block *> Result;
450 Result.reserve(std::distance(Begin1, End1) + std::distance(Begin2, End2) +
451 std::distance(Begin3, End3));
452 Result.insert(Result.end(), Begin1, End1);
453 Result.insert(Result.end(), Begin2, End2);
454 Result.insert(Result.end(), Begin3, End3);
455 return Result;
456 }
457
458 const Block *getFirstBlock() const { return *Begin1; }
459
460private:
461 BlockIter Begin1;
462 BlockIter End1;
463 BlockIter Begin2;
464 BlockIter End2;
465 BlockIter Begin3;
466 BlockIter End3;
467};
468
469/// The implementation of the ExtTSP algorithm.
470class ExtTSPImpl {
471 using EdgeT = std::pair<uint64_t, uint64_t>;
472 using EdgeCountMap = std::vector<std::pair<EdgeT, uint64_t>>;
473
474public:
475 ExtTSPImpl(size_t NumNodes, const std::vector<uint64_t> &NodeSizes,
476 const std::vector<uint64_t> &NodeCounts,
477 const EdgeCountMap &EdgeCounts)
478 : NumNodes(NumNodes) {
479 initialize(NodeSizes, NodeCounts, EdgeCounts);
480 }
481
482 /// Run the algorithm and return an optimized ordering of blocks.
483 void run(std::vector<uint64_t> &Result) {
484 // Pass 1: Merge blocks with their mutually forced successors
485 mergeForcedPairs();
486
487 // Pass 2: Merge pairs of chains while improving the ExtTSP objective
488 mergeChainPairs();
6
Calling 'ExtTSPImpl::mergeChainPairs'
489
490 // Pass 3: Merge cold blocks to reduce code size
491 mergeColdChains();
492
493 // Collect blocks from all chains
494 concatChains(Result);
495 }
496
497private:
498 /// Initialize the algorithm's data structures.
499 void initialize(const std::vector<uint64_t> &NodeSizes,
500 const std::vector<uint64_t> &NodeCounts,
501 const EdgeCountMap &EdgeCounts) {
502 // Initialize blocks
503 AllBlocks.reserve(NumNodes);
504 for (uint64_t Node = 0; Node < NumNodes; Node++) {
505 uint64_t Size = std::max<uint64_t>(NodeSizes[Node], 1ULL);
506 uint64_t ExecutionCount = NodeCounts[Node];
507 // The execution count of the entry block is set to at least 1
508 if (Node == 0 && ExecutionCount == 0)
509 ExecutionCount = 1;
510 AllBlocks.emplace_back(Node, Size, ExecutionCount);
511 }
512
513 // Initialize jumps between blocks
514 SuccNodes.resize(NumNodes);
515 PredNodes.resize(NumNodes);
516 std::vector<uint64_t> OutDegree(NumNodes, 0);
517 AllJumps.reserve(EdgeCounts.size());
518 for (auto It : EdgeCounts) {
519 auto Pred = It.first.first;
520 auto Succ = It.first.second;
521 OutDegree[Pred]++;
522 // Ignore self-edges
523 if (Pred == Succ)
524 continue;
525
526 SuccNodes[Pred].push_back(Succ);
527 PredNodes[Succ].push_back(Pred);
528 auto ExecutionCount = It.second;
529 if (ExecutionCount > 0) {
530 auto &Block = AllBlocks[Pred];
531 auto &SuccBlock = AllBlocks[Succ];
532 AllJumps.emplace_back(&Block, &SuccBlock, ExecutionCount);
533 SuccBlock.InJumps.push_back(&AllJumps.back());
534 Block.OutJumps.push_back(&AllJumps.back());
535 }
536 }
537 for (auto &Jump : AllJumps) {
538 assert(OutDegree[Jump.Source->Index] > 0)(static_cast <bool> (OutDegree[Jump.Source->Index] >
0) ? void (0) : __assert_fail ("OutDegree[Jump.Source->Index] > 0"
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 538, __extension__
__PRETTY_FUNCTION__))
;
539 Jump.IsConditional = OutDegree[Jump.Source->Index] > 1;
540 }
541
542 // Initialize chains
543 AllChains.reserve(NumNodes);
544 HotChains.reserve(NumNodes);
545 for (Block &Block : AllBlocks) {
546 AllChains.emplace_back(Block.Index, &Block);
547 Block.CurChain = &AllChains.back();
548 if (Block.ExecutionCount > 0) {
549 HotChains.push_back(&AllChains.back());
550 }
551 }
552
553 // Initialize chain edges
554 AllEdges.reserve(AllJumps.size());
555 for (Block &Block : AllBlocks) {
556 for (auto &Jump : Block.OutJumps) {
557 auto SuccBlock = Jump->Target;
558 ChainEdge *CurEdge = Block.CurChain->getEdge(SuccBlock->CurChain);
559 // this edge is already present in the graph
560 if (CurEdge != nullptr) {
561 assert(SuccBlock->CurChain->getEdge(Block.CurChain) != nullptr)(static_cast <bool> (SuccBlock->CurChain->getEdge
(Block.CurChain) != nullptr) ? void (0) : __assert_fail ("SuccBlock->CurChain->getEdge(Block.CurChain) != nullptr"
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 561, __extension__
__PRETTY_FUNCTION__))
;
562 CurEdge->appendJump(Jump);
563 continue;
564 }
565 // this is a new edge
566 AllEdges.emplace_back(Jump);
567 Block.CurChain->addEdge(SuccBlock->CurChain, &AllEdges.back());
568 SuccBlock->CurChain->addEdge(Block.CurChain, &AllEdges.back());
569 }
570 }
571 }
572
573 /// For a pair of blocks, A and B, block B is the forced successor of A,
574 /// if (i) all jumps (based on profile) from A goes to B and (ii) all jumps
575 /// to B are from A. Such blocks should be adjacent in the optimal ordering;
576 /// the method finds and merges such pairs of blocks.
577 void mergeForcedPairs() {
578 // Find fallthroughs based on edge weights
579 for (auto &Block : AllBlocks) {
580 if (SuccNodes[Block.Index].size() == 1 &&
581 PredNodes[SuccNodes[Block.Index][0]].size() == 1 &&
582 SuccNodes[Block.Index][0] != 0) {
583 size_t SuccIndex = SuccNodes[Block.Index][0];
584 Block.ForcedSucc = &AllBlocks[SuccIndex];
585 AllBlocks[SuccIndex].ForcedPred = &Block;
586 }
587 }
588
589 // There might be 'cycles' in the forced dependencies, since profile
590 // data isn't 100% accurate. Typically this is observed in loops, when the
591 // loop edges are the hottest successors for the basic blocks of the loop.
592 // Break the cycles by choosing the block with the smallest index as the
593 // head. This helps to keep the original order of the loops, which likely
594 // have already been rotated in the optimized manner.
595 for (auto &Block : AllBlocks) {
596 if (Block.ForcedSucc == nullptr || Block.ForcedPred == nullptr)
597 continue;
598
599 auto SuccBlock = Block.ForcedSucc;
600 while (SuccBlock != nullptr && SuccBlock != &Block) {
601 SuccBlock = SuccBlock->ForcedSucc;
602 }
603 if (SuccBlock == nullptr)
604 continue;
605 // Break the cycle
606 AllBlocks[Block.ForcedPred->Index].ForcedSucc = nullptr;
607 Block.ForcedPred = nullptr;
608 }
609
610 // Merge blocks with their fallthrough successors
611 for (auto &Block : AllBlocks) {
612 if (Block.ForcedPred == nullptr && Block.ForcedSucc != nullptr) {
613 auto CurBlock = &Block;
614 while (CurBlock->ForcedSucc != nullptr) {
615 const auto NextBlock = CurBlock->ForcedSucc;
616 mergeChains(Block.CurChain, NextBlock->CurChain, 0, MergeTypeTy::X_Y);
617 CurBlock = NextBlock;
618 }
619 }
620 }
621 }
622
623 /// Merge pairs of chains while improving the ExtTSP objective.
624 void mergeChainPairs() {
625 /// Deterministically compare pairs of chains
626 auto compareChainPairs = [](const Chain *A1, const Chain *B1,
627 const Chain *A2, const Chain *B2) {
628 if (A1
17.1
'A1' is not equal to 'A2'
!= A2)
18
Taking true branch
629 return A1->id() < A2->id();
19
Called C++ object pointer is null
630 return B1->id() < B2->id();
631 };
632
633 while (HotChains.size() > 1) {
7
Assuming the condition is true
8
Loop condition is true. Entering loop body
634 Chain *BestChainPred = nullptr;
9
'BestChainPred' initialized to a null pointer value
635 Chain *BestChainSucc = nullptr;
636 auto BestGain = MergeGainTy();
637 // Iterate over all pairs of chains
638 for (Chain *ChainPred : HotChains) {
639 // Get candidates for merging with the current chain
640 for (auto EdgeIter : ChainPred->edges()) {
641 Chain *ChainSucc = EdgeIter.first;
642 class ChainEdge *ChainEdge = EdgeIter.second;
643 // Ignore loop edges
644 if (ChainPred == ChainSucc)
10
Assuming 'ChainPred' is not equal to 'ChainSucc'
11
Taking false branch
645 continue;
646
647 // Stop early if the combined chain violates the maximum allowed size
648 if (ChainPred->numBlocks() + ChainSucc->numBlocks() >= MaxChainSize)
12
Assuming the condition is false
13
Taking false branch
649 continue;
650
651 // Compute the gain of merging the two chains
652 MergeGainTy CurGain =
653 getBestMergeGain(ChainPred, ChainSucc, ChainEdge);
654 if (CurGain.score() <= EPS)
14
Assuming the condition is false
655 continue;
656
657 if (BestGain < CurGain ||
658 (std::abs(CurGain.score() - BestGain.score()) < EPS &&
15
Assuming the condition is true
659 compareChainPairs(ChainPred, ChainSucc, BestChainPred,
16
Passing null pointer value via 3rd parameter 'A2'
17
Calling 'operator()'
660 BestChainSucc))) {
661 BestGain = CurGain;
662 BestChainPred = ChainPred;
663 BestChainSucc = ChainSucc;
664 }
665 }
666 }
667
668 // Stop merging when there is no improvement
669 if (BestGain.score() <= EPS)
670 break;
671
672 // Merge the best pair of chains
673 mergeChains(BestChainPred, BestChainSucc, BestGain.mergeOffset(),
674 BestGain.mergeType());
675 }
676 }
677
678 /// Merge remaining blocks into chains w/o taking jump counts into
679 /// consideration. This allows to maintain the original block order in the
680 /// absense of profile data
681 void mergeColdChains() {
682 for (size_t SrcBB = 0; SrcBB < NumNodes; SrcBB++) {
683 // Iterating in reverse order to make sure original fallthrough jumps are
684 // merged first; this might be beneficial for code size.
685 size_t NumSuccs = SuccNodes[SrcBB].size();
686 for (size_t Idx = 0; Idx < NumSuccs; Idx++) {
687 auto DstBB = SuccNodes[SrcBB][NumSuccs - Idx - 1];
688 auto SrcChain = AllBlocks[SrcBB].CurChain;
689 auto DstChain = AllBlocks[DstBB].CurChain;
690 if (SrcChain != DstChain && !DstChain->isEntry() &&
691 SrcChain->blocks().back()->Index == SrcBB &&
692 DstChain->blocks().front()->Index == DstBB &&
693 SrcChain->isCold() == DstChain->isCold()) {
694 mergeChains(SrcChain, DstChain, 0, MergeTypeTy::X_Y);
695 }
696 }
697 }
698 }
699
700 /// Compute the Ext-TSP score for a given block order and a list of jumps.
701 double extTSPScore(const MergedChain &MergedBlocks,
702 const std::vector<Jump *> &Jumps) const {
703 if (Jumps.empty())
704 return 0.0;
705 uint64_t CurAddr = 0;
706 MergedBlocks.forEach([&](const Block *BB) {
707 BB->EstimatedAddr = CurAddr;
708 CurAddr += BB->Size;
709 });
710
711 double Score = 0;
712 for (auto &Jump : Jumps) {
713 const Block *SrcBlock = Jump->Source;
714 const Block *DstBlock = Jump->Target;
715 Score += ::extTSPScore(SrcBlock->EstimatedAddr, SrcBlock->Size,
716 DstBlock->EstimatedAddr, Jump->ExecutionCount,
717 Jump->IsConditional);
718 }
719 return Score;
720 }
721
722 /// Compute the gain of merging two chains.
723 ///
724 /// The function considers all possible ways of merging two chains and
725 /// computes the one having the largest increase in ExtTSP objective. The
726 /// result is a pair with the first element being the gain and the second
727 /// element being the corresponding merging type.
728 MergeGainTy getBestMergeGain(Chain *ChainPred, Chain *ChainSucc,
729 ChainEdge *Edge) const {
730 if (Edge->hasCachedMergeGain(ChainPred, ChainSucc)) {
731 return Edge->getCachedMergeGain(ChainPred, ChainSucc);
732 }
733
734 // Precompute jumps between ChainPred and ChainSucc
735 auto Jumps = Edge->jumps();
736 ChainEdge *EdgePP = ChainPred->getEdge(ChainPred);
737 if (EdgePP != nullptr) {
738 Jumps.insert(Jumps.end(), EdgePP->jumps().begin(), EdgePP->jumps().end());
739 }
740 assert(!Jumps.empty() && "trying to merge chains w/o jumps")(static_cast <bool> (!Jumps.empty() && "trying to merge chains w/o jumps"
) ? void (0) : __assert_fail ("!Jumps.empty() && \"trying to merge chains w/o jumps\""
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 740, __extension__
__PRETTY_FUNCTION__))
;
741
742 // The object holds the best currently chosen gain of merging the two chains
743 MergeGainTy Gain = MergeGainTy();
744
745 /// Given a merge offset and a list of merge types, try to merge two chains
746 /// and update Gain with a better alternative
747 auto tryChainMerging = [&](size_t Offset,
748 const std::vector<MergeTypeTy> &MergeTypes) {
749 // Skip merging corresponding to concatenation w/o splitting
750 if (Offset == 0 || Offset == ChainPred->blocks().size())
751 return;
752 // Skip merging if it breaks Forced successors
753 auto BB = ChainPred->blocks()[Offset - 1];
754 if (BB->ForcedSucc != nullptr)
755 return;
756 // Apply the merge, compute the corresponding gain, and update the best
757 // value, if the merge is beneficial
758 for (const auto &MergeType : MergeTypes) {
759 Gain.updateIfLessThan(
760 computeMergeGain(ChainPred, ChainSucc, Jumps, Offset, MergeType));
761 }
762 };
763
764 // Try to concatenate two chains w/o splitting
765 Gain.updateIfLessThan(
766 computeMergeGain(ChainPred, ChainSucc, Jumps, 0, MergeTypeTy::X_Y));
767
768 if (EnableChainSplitAlongJumps) {
769 // Attach (a part of) ChainPred before the first block of ChainSucc
770 for (auto &Jump : ChainSucc->blocks().front()->InJumps) {
771 const auto SrcBlock = Jump->Source;
772 if (SrcBlock->CurChain != ChainPred)
773 continue;
774 size_t Offset = SrcBlock->CurIndex + 1;
775 tryChainMerging(Offset, {MergeTypeTy::X1_Y_X2, MergeTypeTy::X2_X1_Y});
776 }
777
778 // Attach (a part of) ChainPred after the last block of ChainSucc
779 for (auto &Jump : ChainSucc->blocks().back()->OutJumps) {
780 const auto DstBlock = Jump->Source;
781 if (DstBlock->CurChain != ChainPred)
782 continue;
783 size_t Offset = DstBlock->CurIndex;
784 tryChainMerging(Offset, {MergeTypeTy::X1_Y_X2, MergeTypeTy::Y_X2_X1});
785 }
786 }
787
788 // Try to break ChainPred in various ways and concatenate with ChainSucc
789 if (ChainPred->blocks().size() <= ChainSplitThreshold) {
790 for (size_t Offset = 1; Offset < ChainPred->blocks().size(); Offset++) {
791 // Try to split the chain in different ways. In practice, applying
792 // X2_Y_X1 merging is almost never provides benefits; thus, we exclude
793 // it from consideration to reduce the search space
794 tryChainMerging(Offset, {MergeTypeTy::X1_Y_X2, MergeTypeTy::Y_X2_X1,
795 MergeTypeTy::X2_X1_Y});
796 }
797 }
798 Edge->setCachedMergeGain(ChainPred, ChainSucc, Gain);
799 return Gain;
800 }
801
802 /// Compute the score gain of merging two chains, respecting a given
803 /// merge 'type' and 'offset'.
804 ///
805 /// The two chains are not modified in the method.
806 MergeGainTy computeMergeGain(const Chain *ChainPred, const Chain *ChainSucc,
807 const std::vector<Jump *> &Jumps,
808 size_t MergeOffset,
809 MergeTypeTy MergeType) const {
810 auto MergedBlocks = mergeBlocks(ChainPred->blocks(), ChainSucc->blocks(),
811 MergeOffset, MergeType);
812
813 // Do not allow a merge that does not preserve the original entry block
814 if ((ChainPred->isEntry() || ChainSucc->isEntry()) &&
815 !MergedBlocks.getFirstBlock()->isEntry())
816 return MergeGainTy();
817
818 // The gain for the new chain
819 auto NewGainScore = extTSPScore(MergedBlocks, Jumps) - ChainPred->score();
820 return MergeGainTy(NewGainScore, MergeOffset, MergeType);
821 }
822
823 /// Merge two chains of blocks respecting a given merge 'type' and 'offset'.
824 ///
825 /// If MergeType == 0, then the result is a concatenation of two chains.
826 /// Otherwise, the first chain is cut into two sub-chains at the offset,
827 /// and merged using all possible ways of concatenating three chains.
828 MergedChain mergeBlocks(const std::vector<Block *> &X,
829 const std::vector<Block *> &Y, size_t MergeOffset,
830 MergeTypeTy MergeType) const {
831 // Split the first chain, X, into X1 and X2
832 BlockIter BeginX1 = X.begin();
833 BlockIter EndX1 = X.begin() + MergeOffset;
834 BlockIter BeginX2 = X.begin() + MergeOffset;
835 BlockIter EndX2 = X.end();
836 BlockIter BeginY = Y.begin();
837 BlockIter EndY = Y.end();
838
839 // Construct a new chain from the three existing ones
840 switch (MergeType) {
841 case MergeTypeTy::X_Y:
842 return MergedChain(BeginX1, EndX2, BeginY, EndY);
843 case MergeTypeTy::X1_Y_X2:
844 return MergedChain(BeginX1, EndX1, BeginY, EndY, BeginX2, EndX2);
845 case MergeTypeTy::Y_X2_X1:
846 return MergedChain(BeginY, EndY, BeginX2, EndX2, BeginX1, EndX1);
847 case MergeTypeTy::X2_X1_Y:
848 return MergedChain(BeginX2, EndX2, BeginX1, EndX1, BeginY, EndY);
849 }
850 llvm_unreachable("unexpected chain merge type")::llvm::llvm_unreachable_internal("unexpected chain merge type"
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 850)
;
851 }
852
853 /// Merge chain From into chain Into, update the list of active chains,
854 /// adjacency information, and the corresponding cached values.
855 void mergeChains(Chain *Into, Chain *From, size_t MergeOffset,
856 MergeTypeTy MergeType) {
857 assert(Into != From && "a chain cannot be merged with itself")(static_cast <bool> (Into != From && "a chain cannot be merged with itself"
) ? void (0) : __assert_fail ("Into != From && \"a chain cannot be merged with itself\""
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 857, __extension__
__PRETTY_FUNCTION__))
;
858
859 // Merge the blocks
860 MergedChain MergedBlocks =
861 mergeBlocks(Into->blocks(), From->blocks(), MergeOffset, MergeType);
862 Into->merge(From, MergedBlocks.getBlocks());
863 Into->mergeEdges(From);
864 From->clear();
865
866 // Update cached ext-tsp score for the new chain
867 ChainEdge *SelfEdge = Into->getEdge(Into);
868 if (SelfEdge != nullptr) {
869 MergedBlocks = MergedChain(Into->blocks().begin(), Into->blocks().end());
870 Into->setScore(extTSPScore(MergedBlocks, SelfEdge->jumps()));
871 }
872
873 // Remove chain From from the list of active chains
874 llvm::erase_value(HotChains, From);
875
876 // Invalidate caches
877 for (auto EdgeIter : Into->edges()) {
878 EdgeIter.second->invalidateCache();
879 }
880 }
881
882 /// Concatenate all chains into a final order of blocks.
883 void concatChains(std::vector<uint64_t> &Order) {
884 // Collect chains and calculate some stats for their sorting
885 std::vector<Chain *> SortedChains;
886 DenseMap<const Chain *, double> ChainDensity;
887 for (auto &Chain : AllChains) {
888 if (!Chain.blocks().empty()) {
889 SortedChains.push_back(&Chain);
890 // Using doubles to avoid overflow of ExecutionCount
891 double Size = 0;
892 double ExecutionCount = 0;
893 for (auto *Block : Chain.blocks()) {
894 Size += static_cast<double>(Block->Size);
895 ExecutionCount += static_cast<double>(Block->ExecutionCount);
896 }
897 assert(Size > 0 && "a chain of zero size")(static_cast <bool> (Size > 0 && "a chain of zero size"
) ? void (0) : __assert_fail ("Size > 0 && \"a chain of zero size\""
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 897, __extension__
__PRETTY_FUNCTION__))
;
898 ChainDensity[&Chain] = ExecutionCount / Size;
899 }
900 }
901
902 // Sorting chains by density in the decreasing order
903 std::stable_sort(SortedChains.begin(), SortedChains.end(),
904 [&](const Chain *C1, const Chain *C2) {
905 // Make sure the original entry block is at the
906 // beginning of the order
907 if (C1->isEntry() != C2->isEntry()) {
908 return C1->isEntry();
909 }
910
911 const double D1 = ChainDensity[C1];
912 const double D2 = ChainDensity[C2];
913 // Compare by density and break ties by chain identifiers
914 return (D1 != D2) ? (D1 > D2) : (C1->id() < C2->id());
915 });
916
917 // Collect the blocks in the order specified by their chains
918 Order.reserve(NumNodes);
919 for (Chain *Chain : SortedChains) {
920 for (Block *Block : Chain->blocks()) {
921 Order.push_back(Block->Index);
922 }
923 }
924 }
925
926private:
927 /// The number of nodes in the graph.
928 const size_t NumNodes;
929
930 /// Successors of each node.
931 std::vector<std::vector<uint64_t>> SuccNodes;
932
933 /// Predecessors of each node.
934 std::vector<std::vector<uint64_t>> PredNodes;
935
936 /// All basic blocks.
937 std::vector<Block> AllBlocks;
938
939 /// All jumps between blocks.
940 std::vector<Jump> AllJumps;
941
942 /// All chains of basic blocks.
943 std::vector<Chain> AllChains;
944
945 /// All edges between chains.
946 std::vector<ChainEdge> AllEdges;
947
948 /// Active chains. The vector gets updated at runtime when chains are merged.
949 std::vector<Chain *> HotChains;
950};
951
952} // end of anonymous namespace
953
954std::vector<uint64_t> llvm::applyExtTspLayout(
955 const std::vector<uint64_t> &NodeSizes,
956 const std::vector<uint64_t> &NodeCounts,
957 const std::vector<std::pair<EdgeT, uint64_t>> &EdgeCounts) {
958 size_t NumNodes = NodeSizes.size();
959
960 // Verify correctness of the input data.
961 assert(NodeCounts.size() == NodeSizes.size() && "Incorrect input")(static_cast <bool> (NodeCounts.size() == NodeSizes.size
() && "Incorrect input") ? void (0) : __assert_fail (
"NodeCounts.size() == NodeSizes.size() && \"Incorrect input\""
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 961, __extension__
__PRETTY_FUNCTION__))
;
1
Assuming the condition is true
2
'?' condition is true
962 assert(NumNodes > 2 && "Incorrect input")(static_cast <bool> (NumNodes > 2 && "Incorrect input"
) ? void (0) : __assert_fail ("NumNodes > 2 && \"Incorrect input\""
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 962, __extension__
__PRETTY_FUNCTION__))
;
3
Assuming 'NumNodes' is > 2
4
'?' condition is true
963
964 // Apply the reordering algorithm.
965 auto Alg = ExtTSPImpl(NumNodes, NodeSizes, NodeCounts, EdgeCounts);
966 std::vector<uint64_t> Result;
967 Alg.run(Result);
5
Calling 'ExtTSPImpl::run'
968
969 // Verify correctness of the output.
970 assert(Result.front() == 0 && "Original entry point is not preserved")(static_cast <bool> (Result.front() == 0 && "Original entry point is not preserved"
) ? void (0) : __assert_fail ("Result.front() == 0 && \"Original entry point is not preserved\""
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 970, __extension__
__PRETTY_FUNCTION__))
;
971 assert(Result.size() == NumNodes && "Incorrect size of reordered layout")(static_cast <bool> (Result.size() == NumNodes &&
"Incorrect size of reordered layout") ? void (0) : __assert_fail
("Result.size() == NumNodes && \"Incorrect size of reordered layout\""
, "llvm/lib/Transforms/Utils/CodeLayout.cpp", 971, __extension__
__PRETTY_FUNCTION__))
;
972 return Result;
973}
974
975double llvm::calcExtTspScore(
976 const std::vector<uint64_t> &Order, const std::vector<uint64_t> &NodeSizes,
977 const std::vector<uint64_t> &NodeCounts,
978 const std::vector<std::pair<EdgeT, uint64_t>> &EdgeCounts) {
979 // Estimate addresses of the blocks in memory
980 std::vector<uint64_t> Addr(NodeSizes.size(), 0);
981 for (size_t Idx = 1; Idx < Order.size(); Idx++) {
982 Addr[Order[Idx]] = Addr[Order[Idx - 1]] + NodeSizes[Order[Idx - 1]];
983 }
984 std::vector<uint64_t> OutDegree(NodeSizes.size(), 0);
985 for (auto It : EdgeCounts) {
986 auto Pred = It.first.first;
987 OutDegree[Pred]++;
988 }
989
990 // Increase the score for each jump
991 double Score = 0;
992 for (auto It : EdgeCounts) {
993 auto Pred = It.first.first;
994 auto Succ = It.first.second;
995 uint64_t Count = It.second;
996 bool IsConditional = OutDegree[Pred] > 1;
997 Score += ::extTSPScore(Addr[Pred], NodeSizes[Pred], Addr[Succ], Count,
998 IsConditional);
999 }
1000 return Score;
1001}
1002
1003double llvm::calcExtTspScore(
1004 const std::vector<uint64_t> &NodeSizes,
1005 const std::vector<uint64_t> &NodeCounts,
1006 const std::vector<std::pair<EdgeT, uint64_t>> &EdgeCounts) {
1007 std::vector<uint64_t> Order(NodeSizes.size());
1008 for (size_t Idx = 0; Idx < NodeSizes.size(); Idx++) {
1009 Order[Idx] = Idx;
1010 }
1011 return calcExtTspScore(Order, NodeSizes, NodeCounts, EdgeCounts);
1012}