Bug Summary

File:llvm/lib/CodeGen/BranchFolding.cpp
Warning:line 1489, column 11
Forming reference to null pointer

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name BranchFolding.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-09-17-195756-12974-1 -x c++ /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp

/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp

1//===- BranchFolding.cpp - Fold machine code branch instructions ----------===//
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// This pass forwards branches to unconditional branches to make them branch
10// directly to the target block. This pass often results in dead MBB's, which
11// it then removes.
12//
13// Note that this pass must be run after register allocation, it cannot handle
14// SSA form. It also must handle virtual registers for targets that emit virtual
15// ISA (e.g. NVPTX).
16//
17//===----------------------------------------------------------------------===//
18
19#include "BranchFolding.h"
20#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/SmallSet.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/Analysis/ProfileSummaryInfo.h"
26#include "llvm/CodeGen/Analysis.h"
27#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
28#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
29#include "llvm/CodeGen/MachineFunction.h"
30#include "llvm/CodeGen/MachineFunctionPass.h"
31#include "llvm/CodeGen/MachineInstr.h"
32#include "llvm/CodeGen/MachineInstrBuilder.h"
33#include "llvm/CodeGen/MachineJumpTableInfo.h"
34#include "llvm/CodeGen/MachineLoopInfo.h"
35#include "llvm/CodeGen/MachineModuleInfo.h"
36#include "llvm/CodeGen/MachineOperand.h"
37#include "llvm/CodeGen/MachineRegisterInfo.h"
38#include "llvm/CodeGen/MachineSizeOpts.h"
39#include "llvm/CodeGen/MBFIWrapper.h"
40#include "llvm/CodeGen/TargetInstrInfo.h"
41#include "llvm/CodeGen/TargetOpcodes.h"
42#include "llvm/CodeGen/TargetPassConfig.h"
43#include "llvm/CodeGen/TargetRegisterInfo.h"
44#include "llvm/CodeGen/TargetSubtargetInfo.h"
45#include "llvm/IR/DebugInfoMetadata.h"
46#include "llvm/IR/DebugLoc.h"
47#include "llvm/IR/Function.h"
48#include "llvm/InitializePasses.h"
49#include "llvm/MC/LaneBitmask.h"
50#include "llvm/MC/MCRegisterInfo.h"
51#include "llvm/Pass.h"
52#include "llvm/Support/BlockFrequency.h"
53#include "llvm/Support/BranchProbability.h"
54#include "llvm/Support/CommandLine.h"
55#include "llvm/Support/Debug.h"
56#include "llvm/Support/ErrorHandling.h"
57#include "llvm/Support/raw_ostream.h"
58#include "llvm/Target/TargetMachine.h"
59#include <cassert>
60#include <cstddef>
61#include <iterator>
62#include <numeric>
63
64using namespace llvm;
65
66#define DEBUG_TYPE"branch-folder" "branch-folder"
67
68STATISTIC(NumDeadBlocks, "Number of dead blocks removed")static llvm::Statistic NumDeadBlocks = {"branch-folder", "NumDeadBlocks"
, "Number of dead blocks removed"}
;
69STATISTIC(NumBranchOpts, "Number of branches optimized")static llvm::Statistic NumBranchOpts = {"branch-folder", "NumBranchOpts"
, "Number of branches optimized"}
;
70STATISTIC(NumTailMerge , "Number of block tails merged")static llvm::Statistic NumTailMerge = {"branch-folder", "NumTailMerge"
, "Number of block tails merged"}
;
71STATISTIC(NumHoist , "Number of times common instructions are hoisted")static llvm::Statistic NumHoist = {"branch-folder", "NumHoist"
, "Number of times common instructions are hoisted"}
;
72STATISTIC(NumTailCalls, "Number of tail calls optimized")static llvm::Statistic NumTailCalls = {"branch-folder", "NumTailCalls"
, "Number of tail calls optimized"}
;
73
74static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge",
75 cl::init(cl::BOU_UNSET), cl::Hidden);
76
77// Throttle for huge numbers of predecessors (compile speed problems)
78static cl::opt<unsigned>
79TailMergeThreshold("tail-merge-threshold",
80 cl::desc("Max number of predecessors to consider tail merging"),
81 cl::init(150), cl::Hidden);
82
83// Heuristic for tail merging (and, inversely, tail duplication).
84// TODO: This should be replaced with a target query.
85static cl::opt<unsigned>
86TailMergeSize("tail-merge-size",
87 cl::desc("Min number of instructions to consider tail merging"),
88 cl::init(3), cl::Hidden);
89
90namespace {
91
92 /// BranchFolderPass - Wrap branch folder in a machine function pass.
93 class BranchFolderPass : public MachineFunctionPass {
94 public:
95 static char ID;
96
97 explicit BranchFolderPass(): MachineFunctionPass(ID) {}
98
99 bool runOnMachineFunction(MachineFunction &MF) override;
100
101 void getAnalysisUsage(AnalysisUsage &AU) const override {
102 AU.addRequired<MachineBlockFrequencyInfo>();
103 AU.addRequired<MachineBranchProbabilityInfo>();
104 AU.addRequired<ProfileSummaryInfoWrapperPass>();
105 AU.addRequired<TargetPassConfig>();
106 MachineFunctionPass::getAnalysisUsage(AU);
107 }
108 };
109
110} // end anonymous namespace
111
112char BranchFolderPass::ID = 0;
113
114char &llvm::BranchFolderPassID = BranchFolderPass::ID;
115
116INITIALIZE_PASS(BranchFolderPass, DEBUG_TYPE,static void *initializeBranchFolderPassPassOnce(PassRegistry &
Registry) { PassInfo *PI = new PassInfo( "Control Flow Optimizer"
, "branch-folder", &BranchFolderPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<BranchFolderPass>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeBranchFolderPassPassFlag; void llvm::initializeBranchFolderPassPass
(PassRegistry &Registry) { llvm::call_once(InitializeBranchFolderPassPassFlag
, initializeBranchFolderPassPassOnce, std::ref(Registry)); }
117 "Control Flow Optimizer", false, false)static void *initializeBranchFolderPassPassOnce(PassRegistry &
Registry) { PassInfo *PI = new PassInfo( "Control Flow Optimizer"
, "branch-folder", &BranchFolderPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<BranchFolderPass>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeBranchFolderPassPassFlag; void llvm::initializeBranchFolderPassPass
(PassRegistry &Registry) { llvm::call_once(InitializeBranchFolderPassPassFlag
, initializeBranchFolderPassPassOnce, std::ref(Registry)); }
118
119bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
120 if (skipFunction(MF.getFunction()))
121 return false;
122
123 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
124 // TailMerge can create jump into if branches that make CFG irreducible for
125 // HW that requires structurized CFG.
126 bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
127 PassConfig->getEnableTailMerge();
128 MBFIWrapper MBBFreqInfo(
129 getAnalysis<MachineBlockFrequencyInfo>());
130 BranchFolder Folder(EnableTailMerge, /*CommonHoist=*/true, MBBFreqInfo,
131 getAnalysis<MachineBranchProbabilityInfo>(),
132 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
133 return Folder.OptimizeFunction(MF, MF.getSubtarget().getInstrInfo(),
134 MF.getSubtarget().getRegisterInfo());
135}
136
137BranchFolder::BranchFolder(bool defaultEnableTailMerge, bool CommonHoist,
138 MBFIWrapper &FreqInfo,
139 const MachineBranchProbabilityInfo &ProbInfo,
140 ProfileSummaryInfo *PSI,
141 unsigned MinTailLength)
142 : EnableHoistCommonCode(CommonHoist), MinCommonTailLength(MinTailLength),
143 MBBFreqInfo(FreqInfo), MBPI(ProbInfo), PSI(PSI) {
144 if (MinCommonTailLength == 0)
145 MinCommonTailLength = TailMergeSize;
146 switch (FlagEnableTailMerge) {
147 case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break;
148 case cl::BOU_TRUE: EnableTailMerge = true; break;
149 case cl::BOU_FALSE: EnableTailMerge = false; break;
150 }
151}
152
153void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
154 assert(MBB->pred_empty() && "MBB must be dead!")((MBB->pred_empty() && "MBB must be dead!") ? static_cast
<void> (0) : __assert_fail ("MBB->pred_empty() && \"MBB must be dead!\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 154, __PRETTY_FUNCTION__))
;
155 LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nRemoving MBB: " <<
*MBB; } } while (false)
;
156
157 MachineFunction *MF = MBB->getParent();
158 // drop all successors.
159 while (!MBB->succ_empty())
160 MBB->removeSuccessor(MBB->succ_end()-1);
161
162 // Avoid matching if this pointer gets reused.
163 TriedMerging.erase(MBB);
164
165 // Update call site info.
166 std::for_each(MBB->begin(), MBB->end(), [MF](const MachineInstr &MI) {
167 if (MI.shouldUpdateCallSiteInfo())
168 MF->eraseCallSiteInfo(&MI);
169 });
170 // Remove the block.
171 MF->erase(MBB);
172 EHScopeMembership.erase(MBB);
173 if (MLI)
174 MLI->removeBlock(MBB);
175}
176
177bool BranchFolder::OptimizeFunction(MachineFunction &MF,
178 const TargetInstrInfo *tii,
179 const TargetRegisterInfo *tri,
180 MachineLoopInfo *mli, bool AfterPlacement) {
181 if (!tii) return false;
182
183 TriedMerging.clear();
184
185 MachineRegisterInfo &MRI = MF.getRegInfo();
186 AfterBlockPlacement = AfterPlacement;
187 TII = tii;
188 TRI = tri;
189 MLI = mli;
190 this->MRI = &MRI;
191
192 UpdateLiveIns = MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF);
193 if (!UpdateLiveIns)
194 MRI.invalidateLiveness();
195
196 bool MadeChange = false;
197
198 // Recalculate EH scope membership.
199 EHScopeMembership = getEHScopeMembership(MF);
200
201 bool MadeChangeThisIteration = true;
202 while (MadeChangeThisIteration) {
203 MadeChangeThisIteration = TailMergeBlocks(MF);
204 // No need to clean up if tail merging does not change anything after the
205 // block placement.
206 if (!AfterBlockPlacement || MadeChangeThisIteration)
207 MadeChangeThisIteration |= OptimizeBranches(MF);
208 if (EnableHoistCommonCode)
209 MadeChangeThisIteration |= HoistCommonCode(MF);
210 MadeChange |= MadeChangeThisIteration;
211 }
212
213 // See if any jump tables have become dead as the code generator
214 // did its thing.
215 MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
216 if (!JTI)
217 return MadeChange;
218
219 // Walk the function to find jump tables that are live.
220 BitVector JTIsLive(JTI->getJumpTables().size());
221 for (const MachineBasicBlock &BB : MF) {
222 for (const MachineInstr &I : BB)
223 for (const MachineOperand &Op : I.operands()) {
224 if (!Op.isJTI()) continue;
225
226 // Remember that this JT is live.
227 JTIsLive.set(Op.getIndex());
228 }
229 }
230
231 // Finally, remove dead jump tables. This happens when the
232 // indirect jump was unreachable (and thus deleted).
233 for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
234 if (!JTIsLive.test(i)) {
235 JTI->RemoveJumpTable(i);
236 MadeChange = true;
237 }
238
239 return MadeChange;
240}
241
242//===----------------------------------------------------------------------===//
243// Tail Merging of Blocks
244//===----------------------------------------------------------------------===//
245
246/// HashMachineInstr - Compute a hash value for MI and its operands.
247static unsigned HashMachineInstr(const MachineInstr &MI) {
248 unsigned Hash = MI.getOpcode();
249 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
250 const MachineOperand &Op = MI.getOperand(i);
251
252 // Merge in bits from the operand if easy. We can't use MachineOperand's
253 // hash_code here because it's not deterministic and we sort by hash value
254 // later.
255 unsigned OperandHash = 0;
256 switch (Op.getType()) {
257 case MachineOperand::MO_Register:
258 OperandHash = Op.getReg();
259 break;
260 case MachineOperand::MO_Immediate:
261 OperandHash = Op.getImm();
262 break;
263 case MachineOperand::MO_MachineBasicBlock:
264 OperandHash = Op.getMBB()->getNumber();
265 break;
266 case MachineOperand::MO_FrameIndex:
267 case MachineOperand::MO_ConstantPoolIndex:
268 case MachineOperand::MO_JumpTableIndex:
269 OperandHash = Op.getIndex();
270 break;
271 case MachineOperand::MO_GlobalAddress:
272 case MachineOperand::MO_ExternalSymbol:
273 // Global address / external symbol are too hard, don't bother, but do
274 // pull in the offset.
275 OperandHash = Op.getOffset();
276 break;
277 default:
278 break;
279 }
280
281 Hash += ((OperandHash << 3) | Op.getType()) << (i & 31);
282 }
283 return Hash;
284}
285
286/// HashEndOfMBB - Hash the last instruction in the MBB.
287static unsigned HashEndOfMBB(const MachineBasicBlock &MBB) {
288 MachineBasicBlock::const_iterator I = MBB.getLastNonDebugInstr();
289 if (I == MBB.end())
290 return 0;
291
292 return HashMachineInstr(*I);
293}
294
295/// Whether MI should be counted as an instruction when calculating common tail.
296static bool countsAsInstruction(const MachineInstr &MI) {
297 return !(MI.isDebugInstr() || MI.isCFIInstruction());
298}
299
300/// Iterate backwards from the given iterator \p I, towards the beginning of the
301/// block. If a MI satisfying 'countsAsInstruction' is found, return an iterator
302/// pointing to that MI. If no such MI is found, return the end iterator.
303static MachineBasicBlock::iterator
304skipBackwardPastNonInstructions(MachineBasicBlock::iterator I,
305 MachineBasicBlock *MBB) {
306 while (I != MBB->begin()) {
307 --I;
308 if (countsAsInstruction(*I))
309 return I;
310 }
311 return MBB->end();
312}
313
314/// Given two machine basic blocks, return the number of instructions they
315/// actually have in common together at their end. If a common tail is found (at
316/// least by one instruction), then iterators for the first shared instruction
317/// in each block are returned as well.
318///
319/// Non-instructions according to countsAsInstruction are ignored.
320static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
321 MachineBasicBlock *MBB2,
322 MachineBasicBlock::iterator &I1,
323 MachineBasicBlock::iterator &I2) {
324 MachineBasicBlock::iterator MBBI1 = MBB1->end();
325 MachineBasicBlock::iterator MBBI2 = MBB2->end();
326
327 unsigned TailLen = 0;
328 while (true) {
329 MBBI1 = skipBackwardPastNonInstructions(MBBI1, MBB1);
330 MBBI2 = skipBackwardPastNonInstructions(MBBI2, MBB2);
331 if (MBBI1 == MBB1->end() || MBBI2 == MBB2->end())
332 break;
333 if (!MBBI1->isIdenticalTo(*MBBI2) ||
334 // FIXME: This check is dubious. It's used to get around a problem where
335 // people incorrectly expect inline asm directives to remain in the same
336 // relative order. This is untenable because normal compiler
337 // optimizations (like this one) may reorder and/or merge these
338 // directives.
339 MBBI1->isInlineAsm()) {
340 break;
341 }
342 if (MBBI1->getFlag(MachineInstr::NoMerge) ||
343 MBBI2->getFlag(MachineInstr::NoMerge))
344 break;
345 ++TailLen;
346 I1 = MBBI1;
347 I2 = MBBI2;
348 }
349
350 return TailLen;
351}
352
353void BranchFolder::replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
354 MachineBasicBlock &NewDest) {
355 if (UpdateLiveIns) {
356 // OldInst should always point to an instruction.
357 MachineBasicBlock &OldMBB = *OldInst->getParent();
358 LiveRegs.clear();
359 LiveRegs.addLiveOuts(OldMBB);
360 // Move backward to the place where will insert the jump.
361 MachineBasicBlock::iterator I = OldMBB.end();
362 do {
363 --I;
364 LiveRegs.stepBackward(*I);
365 } while (I != OldInst);
366
367 // Merging the tails may have switched some undef operand to non-undef ones.
368 // Add IMPLICIT_DEFS into OldMBB as necessary to have a definition of the
369 // register.
370 for (MachineBasicBlock::RegisterMaskPair P : NewDest.liveins()) {
371 // We computed the liveins with computeLiveIn earlier and should only see
372 // full registers:
373 assert(P.LaneMask == LaneBitmask::getAll() &&((P.LaneMask == LaneBitmask::getAll() && "Can only handle full register."
) ? static_cast<void> (0) : __assert_fail ("P.LaneMask == LaneBitmask::getAll() && \"Can only handle full register.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 374, __PRETTY_FUNCTION__))
374 "Can only handle full register.")((P.LaneMask == LaneBitmask::getAll() && "Can only handle full register."
) ? static_cast<void> (0) : __assert_fail ("P.LaneMask == LaneBitmask::getAll() && \"Can only handle full register.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 374, __PRETTY_FUNCTION__))
;
375 MCPhysReg Reg = P.PhysReg;
376 if (!LiveRegs.available(*MRI, Reg))
377 continue;
378 DebugLoc DL;
379 BuildMI(OldMBB, OldInst, DL, TII->get(TargetOpcode::IMPLICIT_DEF), Reg);
380 }
381 }
382
383 TII->ReplaceTailWithBranchTo(OldInst, &NewDest);
384 ++NumTailMerge;
385}
386
387MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
388 MachineBasicBlock::iterator BBI1,
389 const BasicBlock *BB) {
390 if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))
391 return nullptr;
392
393 MachineFunction &MF = *CurMBB.getParent();
394
395 // Create the fall-through block.
396 MachineFunction::iterator MBBI = CurMBB.getIterator();
397 MachineBasicBlock *NewMBB = MF.CreateMachineBasicBlock(BB);
398 CurMBB.getParent()->insert(++MBBI, NewMBB);
399
400 // Move all the successors of this block to the specified block.
401 NewMBB->transferSuccessors(&CurMBB);
402
403 // Add an edge from CurMBB to NewMBB for the fall-through.
404 CurMBB.addSuccessor(NewMBB);
405
406 // Splice the code over.
407 NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
408
409 // NewMBB belongs to the same loop as CurMBB.
410 if (MLI)
411 if (MachineLoop *ML = MLI->getLoopFor(&CurMBB))
412 ML->addBasicBlockToLoop(NewMBB, MLI->getBase());
413
414 // NewMBB inherits CurMBB's block frequency.
415 MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB));
416
417 if (UpdateLiveIns)
418 computeAndAddLiveIns(LiveRegs, *NewMBB);
419
420 // Add the new block to the EH scope.
421 const auto &EHScopeI = EHScopeMembership.find(&CurMBB);
422 if (EHScopeI != EHScopeMembership.end()) {
423 auto n = EHScopeI->second;
424 EHScopeMembership[NewMBB] = n;
425 }
426
427 return NewMBB;
428}
429
430/// EstimateRuntime - Make a rough estimate for how long it will take to run
431/// the specified code.
432static unsigned EstimateRuntime(MachineBasicBlock::iterator I,
433 MachineBasicBlock::iterator E) {
434 unsigned Time = 0;
435 for (; I != E; ++I) {
436 if (!countsAsInstruction(*I))
437 continue;
438 if (I->isCall())
439 Time += 10;
440 else if (I->mayLoadOrStore())
441 Time += 2;
442 else
443 ++Time;
444 }
445 return Time;
446}
447
448// CurMBB needs to add an unconditional branch to SuccMBB (we removed these
449// branches temporarily for tail merging). In the case where CurMBB ends
450// with a conditional branch to the next block, optimize by reversing the
451// test and conditionally branching to SuccMBB instead.
452static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
453 const TargetInstrInfo *TII) {
454 MachineFunction *MF = CurMBB->getParent();
455 MachineFunction::iterator I = std::next(MachineFunction::iterator(CurMBB));
456 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
457 SmallVector<MachineOperand, 4> Cond;
458 DebugLoc dl = CurMBB->findBranchDebugLoc();
459 if (I != MF->end() && !TII->analyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {
460 MachineBasicBlock *NextBB = &*I;
461 if (TBB == NextBB && !Cond.empty() && !FBB) {
462 if (!TII->reverseBranchCondition(Cond)) {
463 TII->removeBranch(*CurMBB);
464 TII->insertBranch(*CurMBB, SuccBB, nullptr, Cond, dl);
465 return;
466 }
467 }
468 }
469 TII->insertBranch(*CurMBB, SuccBB, nullptr,
470 SmallVector<MachineOperand, 0>(), dl);
471}
472
473bool
474BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const {
475 if (getHash() < o.getHash())
476 return true;
477 if (getHash() > o.getHash())
478 return false;
479 if (getBlock()->getNumber() < o.getBlock()->getNumber())
480 return true;
481 if (getBlock()->getNumber() > o.getBlock()->getNumber())
482 return false;
483 // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
484 // an object with itself.
485#ifndef _GLIBCXX_DEBUG
486 llvm_unreachable("Predecessor appears twice")::llvm::llvm_unreachable_internal("Predecessor appears twice"
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 486)
;
487#else
488 return false;
489#endif
490}
491
492/// CountTerminators - Count the number of terminators in the given
493/// block and set I to the position of the first non-terminator, if there
494/// is one, or MBB->end() otherwise.
495static unsigned CountTerminators(MachineBasicBlock *MBB,
496 MachineBasicBlock::iterator &I) {
497 I = MBB->end();
498 unsigned NumTerms = 0;
499 while (true) {
500 if (I == MBB->begin()) {
501 I = MBB->end();
502 break;
503 }
504 --I;
505 if (!I->isTerminator()) break;
506 ++NumTerms;
507 }
508 return NumTerms;
509}
510
511/// A no successor, non-return block probably ends in unreachable and is cold.
512/// Also consider a block that ends in an indirect branch to be a return block,
513/// since many targets use plain indirect branches to return.
514static bool blockEndsInUnreachable(const MachineBasicBlock *MBB) {
515 if (!MBB->succ_empty())
516 return false;
517 if (MBB->empty())
518 return true;
519 return !(MBB->back().isReturn() || MBB->back().isIndirectBranch());
520}
521
522/// ProfitableToMerge - Check if two machine basic blocks have a common tail
523/// and decide if it would be profitable to merge those tails. Return the
524/// length of the common tail and iterators to the first common instruction
525/// in each block.
526/// MBB1, MBB2 The blocks to check
527/// MinCommonTailLength Minimum size of tail block to be merged.
528/// CommonTailLen Out parameter to record the size of the shared tail between
529/// MBB1 and MBB2
530/// I1, I2 Iterator references that will be changed to point to the first
531/// instruction in the common tail shared by MBB1,MBB2
532/// SuccBB A common successor of MBB1, MBB2 which are in a canonical form
533/// relative to SuccBB
534/// PredBB The layout predecessor of SuccBB, if any.
535/// EHScopeMembership map from block to EH scope #.
536/// AfterPlacement True if we are merging blocks after layout. Stricter
537/// thresholds apply to prevent undoing tail-duplication.
538static bool
539ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2,
540 unsigned MinCommonTailLength, unsigned &CommonTailLen,
541 MachineBasicBlock::iterator &I1,
542 MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB,
543 MachineBasicBlock *PredBB,
544 DenseMap<const MachineBasicBlock *, int> &EHScopeMembership,
545 bool AfterPlacement,
546 MBFIWrapper &MBBFreqInfo,
547 ProfileSummaryInfo *PSI) {
548 // It is never profitable to tail-merge blocks from two different EH scopes.
549 if (!EHScopeMembership.empty()) {
550 auto EHScope1 = EHScopeMembership.find(MBB1);
551 assert(EHScope1 != EHScopeMembership.end())((EHScope1 != EHScopeMembership.end()) ? static_cast<void>
(0) : __assert_fail ("EHScope1 != EHScopeMembership.end()", "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 551, __PRETTY_FUNCTION__))
;
552 auto EHScope2 = EHScopeMembership.find(MBB2);
553 assert(EHScope2 != EHScopeMembership.end())((EHScope2 != EHScopeMembership.end()) ? static_cast<void>
(0) : __assert_fail ("EHScope2 != EHScopeMembership.end()", "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 553, __PRETTY_FUNCTION__))
;
554 if (EHScope1->second != EHScope2->second)
555 return false;
556 }
557
558 CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
559 if (CommonTailLen == 0)
560 return false;
561 LLVM_DEBUG(dbgs() << "Common tail length of " << printMBBReference(*MBB1)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "Common tail length of "
<< printMBBReference(*MBB1) << " and " << printMBBReference
(*MBB2) << " is " << CommonTailLen << '\n';
} } while (false)
562 << " and " << printMBBReference(*MBB2) << " is "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "Common tail length of "
<< printMBBReference(*MBB1) << " and " << printMBBReference
(*MBB2) << " is " << CommonTailLen << '\n';
} } while (false)
563 << CommonTailLen << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "Common tail length of "
<< printMBBReference(*MBB1) << " and " << printMBBReference
(*MBB2) << " is " << CommonTailLen << '\n';
} } while (false)
;
564
565 // Move the iterators to the beginning of the MBB if we only got debug
566 // instructions before the tail. This is to avoid splitting a block when we
567 // only got debug instructions before the tail (to be invariant on -g).
568 if (skipDebugInstructionsForward(MBB1->begin(), MBB1->end()) == I1)
569 I1 = MBB1->begin();
570 if (skipDebugInstructionsForward(MBB2->begin(), MBB2->end()) == I2)
571 I2 = MBB2->begin();
572
573 bool FullBlockTail1 = I1 == MBB1->begin();
574 bool FullBlockTail2 = I2 == MBB2->begin();
575
576 // It's almost always profitable to merge any number of non-terminator
577 // instructions with the block that falls through into the common successor.
578 // This is true only for a single successor. For multiple successors, we are
579 // trading a conditional branch for an unconditional one.
580 // TODO: Re-visit successor size for non-layout tail merging.
581 if ((MBB1 == PredBB || MBB2 == PredBB) &&
582 (!AfterPlacement || MBB1->succ_size() == 1)) {
583 MachineBasicBlock::iterator I;
584 unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);
585 if (CommonTailLen > NumTerms)
586 return true;
587 }
588
589 // If these are identical non-return blocks with no successors, merge them.
590 // Such blocks are typically cold calls to noreturn functions like abort, and
591 // are unlikely to become a fallthrough target after machine block placement.
592 // Tail merging these blocks is unlikely to create additional unconditional
593 // branches, and will reduce the size of this cold code.
594 if (FullBlockTail1 && FullBlockTail2 &&
595 blockEndsInUnreachable(MBB1) && blockEndsInUnreachable(MBB2))
596 return true;
597
598 // If one of the blocks can be completely merged and happens to be in
599 // a position where the other could fall through into it, merge any number
600 // of instructions, because it can be done without a branch.
601 // TODO: If the blocks are not adjacent, move one of them so that they are?
602 if (MBB1->isLayoutSuccessor(MBB2) && FullBlockTail2)
603 return true;
604 if (MBB2->isLayoutSuccessor(MBB1) && FullBlockTail1)
605 return true;
606
607 // If both blocks are identical and end in a branch, merge them unless they
608 // both have a fallthrough predecessor and successor.
609 // We can only do this after block placement because it depends on whether
610 // there are fallthroughs, and we don't know until after layout.
611 if (AfterPlacement && FullBlockTail1 && FullBlockTail2) {
612 auto BothFallThrough = [](MachineBasicBlock *MBB) {
613 if (MBB->succ_size() != 0 && !MBB->canFallThrough())
614 return false;
615 MachineFunction::iterator I(MBB);
616 MachineFunction *MF = MBB->getParent();
617 return (MBB != &*MF->begin()) && std::prev(I)->canFallThrough();
618 };
619 if (!BothFallThrough(MBB1) || !BothFallThrough(MBB2))
620 return true;
621 }
622
623 // If both blocks have an unconditional branch temporarily stripped out,
624 // count that as an additional common instruction for the following
625 // heuristics. This heuristic is only accurate for single-succ blocks, so to
626 // make sure that during layout merging and duplicating don't crash, we check
627 // for that when merging during layout.
628 unsigned EffectiveTailLen = CommonTailLen;
629 if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
630 (MBB1->succ_size() == 1 || !AfterPlacement) &&
631 !MBB1->back().isBarrier() &&
632 !MBB2->back().isBarrier())
633 ++EffectiveTailLen;
634
635 // Check if the common tail is long enough to be worthwhile.
636 if (EffectiveTailLen >= MinCommonTailLength)
637 return true;
638
639 // If we are optimizing for code size, 2 instructions in common is enough if
640 // we don't have to split a block. At worst we will be introducing 1 new
641 // branch instruction, which is likely to be smaller than the 2
642 // instructions that would be deleted in the merge.
643 MachineFunction *MF = MBB1->getParent();
644 bool OptForSize =
645 MF->getFunction().hasOptSize() ||
646 (llvm::shouldOptimizeForSize(MBB1, PSI, &MBBFreqInfo) &&
647 llvm::shouldOptimizeForSize(MBB2, PSI, &MBBFreqInfo));
648 return EffectiveTailLen >= 2 && OptForSize &&
649 (FullBlockTail1 || FullBlockTail2);
650}
651
652unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
653 unsigned MinCommonTailLength,
654 MachineBasicBlock *SuccBB,
655 MachineBasicBlock *PredBB) {
656 unsigned maxCommonTailLength = 0U;
657 SameTails.clear();
658 MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
659 MPIterator HighestMPIter = std::prev(MergePotentials.end());
660 for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
661 B = MergePotentials.begin();
662 CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {
663 for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {
664 unsigned CommonTailLen;
665 if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
666 MinCommonTailLength,
667 CommonTailLen, TrialBBI1, TrialBBI2,
668 SuccBB, PredBB,
669 EHScopeMembership,
670 AfterBlockPlacement, MBBFreqInfo, PSI)) {
671 if (CommonTailLen > maxCommonTailLength) {
672 SameTails.clear();
673 maxCommonTailLength = CommonTailLen;
674 HighestMPIter = CurMPIter;
675 SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
676 }
677 if (HighestMPIter == CurMPIter &&
678 CommonTailLen == maxCommonTailLength)
679 SameTails.push_back(SameTailElt(I, TrialBBI2));
680 }
681 if (I == B)
682 break;
683 }
684 }
685 return maxCommonTailLength;
686}
687
688void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
689 MachineBasicBlock *SuccBB,
690 MachineBasicBlock *PredBB) {
691 MPIterator CurMPIter, B;
692 for (CurMPIter = std::prev(MergePotentials.end()),
693 B = MergePotentials.begin();
694 CurMPIter->getHash() == CurHash; --CurMPIter) {
695 // Put the unconditional branch back, if we need one.
696 MachineBasicBlock *CurMBB = CurMPIter->getBlock();
697 if (SuccBB && CurMBB != PredBB)
698 FixTail(CurMBB, SuccBB, TII);
699 if (CurMPIter == B)
700 break;
701 }
702 if (CurMPIter->getHash() != CurHash)
703 CurMPIter++;
704 MergePotentials.erase(CurMPIter, MergePotentials.end());
705}
706
707bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
708 MachineBasicBlock *SuccBB,
709 unsigned maxCommonTailLength,
710 unsigned &commonTailIndex) {
711 commonTailIndex = 0;
712 unsigned TimeEstimate = ~0U;
713 for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
714 // Use PredBB if possible; that doesn't require a new branch.
715 if (SameTails[i].getBlock() == PredBB) {
716 commonTailIndex = i;
717 break;
718 }
719 // Otherwise, make a (fairly bogus) choice based on estimate of
720 // how long it will take the various blocks to execute.
721 unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(),
722 SameTails[i].getTailStartPos());
723 if (t <= TimeEstimate) {
724 TimeEstimate = t;
725 commonTailIndex = i;
726 }
727 }
728
729 MachineBasicBlock::iterator BBI =
730 SameTails[commonTailIndex].getTailStartPos();
731 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
732
733 LLVM_DEBUG(dbgs() << "\nSplitting " << printMBBReference(*MBB) << ", size "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nSplitting " << printMBBReference
(*MBB) << ", size " << maxCommonTailLength; } } while
(false)
734 << maxCommonTailLength)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nSplitting " << printMBBReference
(*MBB) << ", size " << maxCommonTailLength; } } while
(false)
;
735
736 // If the split block unconditionally falls-thru to SuccBB, it will be
737 // merged. In control flow terms it should then take SuccBB's name. e.g. If
738 // SuccBB is an inner loop, the common tail is still part of the inner loop.
739 const BasicBlock *BB = (SuccBB && MBB->succ_size() == 1) ?
740 SuccBB->getBasicBlock() : MBB->getBasicBlock();
741 MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI, BB);
742 if (!newMBB) {
743 LLVM_DEBUG(dbgs() << "... failed!")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "... failed!"; } } while
(false)
;
744 return false;
745 }
746
747 SameTails[commonTailIndex].setBlock(newMBB);
748 SameTails[commonTailIndex].setTailStartPos(newMBB->begin());
749
750 // If we split PredBB, newMBB is the new predecessor.
751 if (PredBB == MBB)
752 PredBB = newMBB;
753
754 return true;
755}
756
757static void
758mergeOperations(MachineBasicBlock::iterator MBBIStartPos,
759 MachineBasicBlock &MBBCommon) {
760 MachineBasicBlock *MBB = MBBIStartPos->getParent();
761 // Note CommonTailLen does not necessarily matches the size of
762 // the common BB nor all its instructions because of debug
763 // instructions differences.
764 unsigned CommonTailLen = 0;
765 for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos)
766 ++CommonTailLen;
767
768 MachineBasicBlock::reverse_iterator MBBI = MBB->rbegin();
769 MachineBasicBlock::reverse_iterator MBBIE = MBB->rend();
770 MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin();
771 MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend();
772
773 while (CommonTailLen--) {
774 assert(MBBI != MBBIE && "Reached BB end within common tail length!")((MBBI != MBBIE && "Reached BB end within common tail length!"
) ? static_cast<void> (0) : __assert_fail ("MBBI != MBBIE && \"Reached BB end within common tail length!\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 774, __PRETTY_FUNCTION__))
;
775 (void)MBBIE;
776
777 if (!countsAsInstruction(*MBBI)) {
778 ++MBBI;
779 continue;
780 }
781
782 while ((MBBICommon != MBBIECommon) && !countsAsInstruction(*MBBICommon))
783 ++MBBICommon;
784
785 assert(MBBICommon != MBBIECommon &&((MBBICommon != MBBIECommon && "Reached BB end within common tail length!"
) ? static_cast<void> (0) : __assert_fail ("MBBICommon != MBBIECommon && \"Reached BB end within common tail length!\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 786, __PRETTY_FUNCTION__))
786 "Reached BB end within common tail length!")((MBBICommon != MBBIECommon && "Reached BB end within common tail length!"
) ? static_cast<void> (0) : __assert_fail ("MBBICommon != MBBIECommon && \"Reached BB end within common tail length!\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 786, __PRETTY_FUNCTION__))
;
787 assert(MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!")((MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!"
) ? static_cast<void> (0) : __assert_fail ("MBBICommon->isIdenticalTo(*MBBI) && \"Expected matching MIIs!\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 787, __PRETTY_FUNCTION__))
;
788
789 // Merge MMOs from memory operations in the common block.
790 if (MBBICommon->mayLoadOrStore())
791 MBBICommon->cloneMergedMemRefs(*MBB->getParent(), {&*MBBICommon, &*MBBI});
792 // Drop undef flags if they aren't present in all merged instructions.
793 for (unsigned I = 0, E = MBBICommon->getNumOperands(); I != E; ++I) {
794 MachineOperand &MO = MBBICommon->getOperand(I);
795 if (MO.isReg() && MO.isUndef()) {
796 const MachineOperand &OtherMO = MBBI->getOperand(I);
797 if (!OtherMO.isUndef())
798 MO.setIsUndef(false);
799 }
800 }
801
802 ++MBBI;
803 ++MBBICommon;
804 }
805}
806
807void BranchFolder::mergeCommonTails(unsigned commonTailIndex) {
808 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
809
810 std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
811 for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {
812 if (i != commonTailIndex) {
813 NextCommonInsts[i] = SameTails[i].getTailStartPos();
814 mergeOperations(SameTails[i].getTailStartPos(), *MBB);
815 } else {
816 assert(SameTails[i].getTailStartPos() == MBB->begin() &&((SameTails[i].getTailStartPos() == MBB->begin() &&
"MBB is not a common tail only block") ? static_cast<void
> (0) : __assert_fail ("SameTails[i].getTailStartPos() == MBB->begin() && \"MBB is not a common tail only block\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 817, __PRETTY_FUNCTION__))
817 "MBB is not a common tail only block")((SameTails[i].getTailStartPos() == MBB->begin() &&
"MBB is not a common tail only block") ? static_cast<void
> (0) : __assert_fail ("SameTails[i].getTailStartPos() == MBB->begin() && \"MBB is not a common tail only block\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 817, __PRETTY_FUNCTION__))
;
818 }
819 }
820
821 for (auto &MI : *MBB) {
822 if (!countsAsInstruction(MI))
823 continue;
824 DebugLoc DL = MI.getDebugLoc();
825 for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
826 if (i == commonTailIndex)
827 continue;
828
829 auto &Pos = NextCommonInsts[i];
830 assert(Pos != SameTails[i].getBlock()->end() &&((Pos != SameTails[i].getBlock()->end() && "Reached BB end within common tail"
) ? static_cast<void> (0) : __assert_fail ("Pos != SameTails[i].getBlock()->end() && \"Reached BB end within common tail\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 831, __PRETTY_FUNCTION__))
831 "Reached BB end within common tail")((Pos != SameTails[i].getBlock()->end() && "Reached BB end within common tail"
) ? static_cast<void> (0) : __assert_fail ("Pos != SameTails[i].getBlock()->end() && \"Reached BB end within common tail\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 831, __PRETTY_FUNCTION__))
;
832 while (!countsAsInstruction(*Pos)) {
833 ++Pos;
834 assert(Pos != SameTails[i].getBlock()->end() &&((Pos != SameTails[i].getBlock()->end() && "Reached BB end within common tail"
) ? static_cast<void> (0) : __assert_fail ("Pos != SameTails[i].getBlock()->end() && \"Reached BB end within common tail\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 835, __PRETTY_FUNCTION__))
835 "Reached BB end within common tail")((Pos != SameTails[i].getBlock()->end() && "Reached BB end within common tail"
) ? static_cast<void> (0) : __assert_fail ("Pos != SameTails[i].getBlock()->end() && \"Reached BB end within common tail\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 835, __PRETTY_FUNCTION__))
;
836 }
837 assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!")((MI.isIdenticalTo(*Pos) && "Expected matching MIIs!"
) ? static_cast<void> (0) : __assert_fail ("MI.isIdenticalTo(*Pos) && \"Expected matching MIIs!\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 837, __PRETTY_FUNCTION__))
;
838 DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
839 NextCommonInsts[i] = ++Pos;
840 }
841 MI.setDebugLoc(DL);
842 }
843
844 if (UpdateLiveIns) {
845 LivePhysRegs NewLiveIns(*TRI);
846 computeLiveIns(NewLiveIns, *MBB);
847 LiveRegs.init(*TRI);
848
849 // The flag merging may lead to some register uses no longer using the
850 // <undef> flag, add IMPLICIT_DEFs in the predecessors as necessary.
851 for (MachineBasicBlock *Pred : MBB->predecessors()) {
852 LiveRegs.clear();
853 LiveRegs.addLiveOuts(*Pred);
854 MachineBasicBlock::iterator InsertBefore = Pred->getFirstTerminator();
855 for (Register Reg : NewLiveIns) {
856 if (!LiveRegs.available(*MRI, Reg))
857 continue;
858 DebugLoc DL;
859 BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),
860 Reg);
861 }
862 }
863
864 MBB->clearLiveIns();
865 addLiveIns(*MBB, NewLiveIns);
866 }
867}
868
869// See if any of the blocks in MergePotentials (which all have SuccBB as a
870// successor, or all have no successor if it is null) can be tail-merged.
871// If there is a successor, any blocks in MergePotentials that are not
872// tail-merged and are not immediately before Succ must have an unconditional
873// branch to Succ added (but the predecessor/successor lists need no
874// adjustment). The lone predecessor of Succ that falls through into Succ,
875// if any, is given in PredBB.
876// MinCommonTailLength - Except for the special cases below, tail-merge if
877// there are at least this many instructions in common.
878bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
879 MachineBasicBlock *PredBB,
880 unsigned MinCommonTailLength) {
881 bool MadeChange = false;
882
883 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
884 dbgs() << "\nTryTailMergeBlocks: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
885 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
886 << printMBBReference(*MergePotentials[i].getBlock())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
887 << (i == e - 1 ? "" : ", ");do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
888 dbgs() << "\n"; if (SuccBB) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
889 dbgs() << " with successor " << printMBBReference(*SuccBB) << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
890 if (PredBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
891 dbgs() << " which has fall-through from "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
892 << printMBBReference(*PredBB) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
893 } dbgs() << "Looking for common tails of at least "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
894 << MinCommonTailLength << " instruction"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
895 << (MinCommonTailLength == 1 ? "" : "s") << '\n';)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nTryTailMergeBlocks: "
; for (unsigned i = 0, e = MergePotentials.size(); i != e; ++
i) dbgs() << printMBBReference(*MergePotentials[i].getBlock
()) << (i == e - 1 ? "" : ", "); dbgs() << "\n"; if
(SuccBB) { dbgs() << " with successor " << printMBBReference
(*SuccBB) << '\n'; if (PredBB) dbgs() << " which has fall-through from "
<< printMBBReference(*PredBB) << "\n"; } dbgs() <<
"Looking for common tails of at least " << MinCommonTailLength
<< " instruction" << (MinCommonTailLength == 1 ?
"" : "s") << '\n';; } } while (false)
;
896
897 // Sort by hash value so that blocks with identical end sequences sort
898 // together.
899 array_pod_sort(MergePotentials.begin(), MergePotentials.end());
900
901 // Walk through equivalence sets looking for actual exact matches.
902 while (MergePotentials.size() > 1) {
903 unsigned CurHash = MergePotentials.back().getHash();
904
905 // Build SameTails, identifying the set of blocks with this hash code
906 // and with the maximum number of instructions in common.
907 unsigned maxCommonTailLength = ComputeSameTails(CurHash,
908 MinCommonTailLength,
909 SuccBB, PredBB);
910
911 // If we didn't find any pair that has at least MinCommonTailLength
912 // instructions in common, remove all blocks with this hash code and retry.
913 if (SameTails.empty()) {
914 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
915 continue;
916 }
917
918 // If one of the blocks is the entire common tail (and is not the entry
919 // block/an EH pad, which we can't jump to), we can treat all blocks with
920 // this same tail at once. Use PredBB if that is one of the possibilities,
921 // as that will not introduce any extra branches.
922 MachineBasicBlock *EntryBB =
923 &MergePotentials.front().getBlock()->getParent()->front();
924 unsigned commonTailIndex = SameTails.size();
925 // If there are two blocks, check to see if one can be made to fall through
926 // into the other.
927 if (SameTails.size() == 2 &&
928 SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
929 SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())
930 commonTailIndex = 1;
931 else if (SameTails.size() == 2 &&
932 SameTails[1].getBlock()->isLayoutSuccessor(
933 SameTails[0].getBlock()) &&
934 SameTails[0].tailIsWholeBlock() &&
935 !SameTails[0].getBlock()->isEHPad())
936 commonTailIndex = 0;
937 else {
938 // Otherwise just pick one, favoring the fall-through predecessor if
939 // there is one.
940 for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
941 MachineBasicBlock *MBB = SameTails[i].getBlock();
942 if ((MBB == EntryBB || MBB->isEHPad()) &&
943 SameTails[i].tailIsWholeBlock())
944 continue;
945 if (MBB == PredBB) {
946 commonTailIndex = i;
947 break;
948 }
949 if (SameTails[i].tailIsWholeBlock())
950 commonTailIndex = i;
951 }
952 }
953
954 if (commonTailIndex == SameTails.size() ||
955 (SameTails[commonTailIndex].getBlock() == PredBB &&
956 !SameTails[commonTailIndex].tailIsWholeBlock())) {
957 // None of the blocks consist entirely of the common tail.
958 // Split a block so that one does.
959 if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,
960 maxCommonTailLength, commonTailIndex)) {
961 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
962 continue;
963 }
964 }
965
966 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
967
968 // Recompute common tail MBB's edge weights and block frequency.
969 setCommonTailEdgeWeights(*MBB);
970
971 // Merge debug locations, MMOs and undef flags across identical instructions
972 // for common tail.
973 mergeCommonTails(commonTailIndex);
974
975 // MBB is common tail. Adjust all other BB's to jump to this one.
976 // Traversal must be forwards so erases work.
977 LLVM_DEBUG(dbgs() << "\nUsing common tail in " << printMBBReference(*MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nUsing common tail in "
<< printMBBReference(*MBB) << " for "; } } while
(false)
978 << " for ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nUsing common tail in "
<< printMBBReference(*MBB) << " for "; } } while
(false)
;
979 for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
980 if (commonTailIndex == i)
981 continue;
982 LLVM_DEBUG(dbgs() << printMBBReference(*SameTails[i].getBlock())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << printMBBReference(*SameTails
[i].getBlock()) << (i == e - 1 ? "" : ", "); } } while (
false)
983 << (i == e - 1 ? "" : ", "))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << printMBBReference(*SameTails
[i].getBlock()) << (i == e - 1 ? "" : ", "); } } while (
false)
;
984 // Hack the end off BB i, making it jump to BB commonTailIndex instead.
985 replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);
986 // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
987 MergePotentials.erase(SameTails[i].getMPIter());
988 }
989 LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\n"; } } while (false)
;
990 // We leave commonTailIndex in the worklist in case there are other blocks
991 // that match it with a smaller number of instructions.
992 MadeChange = true;
993 }
994 return MadeChange;
995}
996
997bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
998 bool MadeChange = false;
999 if (!EnableTailMerge)
1000 return MadeChange;
1001
1002 // First find blocks with no successors.
1003 // Block placement may create new tail merging opportunities for these blocks.
1004 MergePotentials.clear();
1005 for (MachineBasicBlock &MBB : MF) {
1006 if (MergePotentials.size() == TailMergeThreshold)
1007 break;
1008 if (!TriedMerging.count(&MBB) && MBB.succ_empty())
1009 MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB));
1010 }
1011
1012 // If this is a large problem, avoid visiting the same basic blocks
1013 // multiple times.
1014 if (MergePotentials.size() == TailMergeThreshold)
1015 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
1016 TriedMerging.insert(MergePotentials[i].getBlock());
1017
1018 // See if we can do any tail merging on those.
1019 if (MergePotentials.size() >= 2)
1020 MadeChange |= TryTailMergeBlocks(nullptr, nullptr, MinCommonTailLength);
1021
1022 // Look at blocks (IBB) with multiple predecessors (PBB).
1023 // We change each predecessor to a canonical form, by
1024 // (1) temporarily removing any unconditional branch from the predecessor
1025 // to IBB, and
1026 // (2) alter conditional branches so they branch to the other block
1027 // not IBB; this may require adding back an unconditional branch to IBB
1028 // later, where there wasn't one coming in. E.g.
1029 // Bcc IBB
1030 // fallthrough to QBB
1031 // here becomes
1032 // Bncc QBB
1033 // with a conceptual B to IBB after that, which never actually exists.
1034 // With those changes, we see whether the predecessors' tails match,
1035 // and merge them if so. We change things out of canonical form and
1036 // back to the way they were later in the process. (OptimizeBranches
1037 // would undo some of this, but we can't use it, because we'd get into
1038 // a compile-time infinite loop repeatedly doing and undoing the same
1039 // transformations.)
1040
1041 for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
1042 I != E; ++I) {
1043 if (I->pred_size() < 2) continue;
1044 SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;
1045 MachineBasicBlock *IBB = &*I;
1046 MachineBasicBlock *PredBB = &*std::prev(I);
1047 MergePotentials.clear();
1048 MachineLoop *ML;
1049
1050 // Bail if merging after placement and IBB is the loop header because
1051 // -- If merging predecessors that belong to the same loop as IBB, the
1052 // common tail of merged predecessors may become the loop top if block
1053 // placement is called again and the predecessors may branch to this common
1054 // tail and require more branches. This can be relaxed if
1055 // MachineBlockPlacement::findBestLoopTop is more flexible.
1056 // --If merging predecessors that do not belong to the same loop as IBB, the
1057 // loop info of IBB's loop and the other loops may be affected. Calling the
1058 // block placement again may make big change to the layout and eliminate the
1059 // reason to do tail merging here.
1060 if (AfterBlockPlacement && MLI) {
1061 ML = MLI->getLoopFor(IBB);
1062 if (ML && IBB == ML->getHeader())
1063 continue;
1064 }
1065
1066 for (MachineBasicBlock *PBB : I->predecessors()) {
1067 if (MergePotentials.size() == TailMergeThreshold)
1068 break;
1069
1070 if (TriedMerging.count(PBB))
1071 continue;
1072
1073 // Skip blocks that loop to themselves, can't tail merge these.
1074 if (PBB == IBB)
1075 continue;
1076
1077 // Visit each predecessor only once.
1078 if (!UniquePreds.insert(PBB).second)
1079 continue;
1080
1081 // Skip blocks which may jump to a landing pad or jump from an asm blob.
1082 // Can't tail merge these.
1083 if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())
1084 continue;
1085
1086 // After block placement, only consider predecessors that belong to the
1087 // same loop as IBB. The reason is the same as above when skipping loop
1088 // header.
1089 if (AfterBlockPlacement && MLI)
1090 if (ML != MLI->getLoopFor(PBB))
1091 continue;
1092
1093 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1094 SmallVector<MachineOperand, 4> Cond;
1095 if (!TII->analyzeBranch(*PBB, TBB, FBB, Cond, true)) {
1096 // Failing case: IBB is the target of a cbr, and we cannot reverse the
1097 // branch.
1098 SmallVector<MachineOperand, 4> NewCond(Cond);
1099 if (!Cond.empty() && TBB == IBB) {
1100 if (TII->reverseBranchCondition(NewCond))
1101 continue;
1102 // This is the QBB case described above
1103 if (!FBB) {
1104 auto Next = ++PBB->getIterator();
1105 if (Next != MF.end())
1106 FBB = &*Next;
1107 }
1108 }
1109
1110 // Remove the unconditional branch at the end, if any.
1111 if (TBB && (Cond.empty() || FBB)) {
1112 DebugLoc dl = PBB->findBranchDebugLoc();
1113 TII->removeBranch(*PBB);
1114 if (!Cond.empty())
1115 // reinsert conditional branch only, for now
1116 TII->insertBranch(*PBB, (TBB == IBB) ? FBB : TBB, nullptr,
1117 NewCond, dl);
1118 }
1119
1120 MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(*PBB), PBB));
1121 }
1122 }
1123
1124 // If this is a large problem, avoid visiting the same basic blocks multiple
1125 // times.
1126 if (MergePotentials.size() == TailMergeThreshold)
1127 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
1128 TriedMerging.insert(MergePotentials[i].getBlock());
1129
1130 if (MergePotentials.size() >= 2)
1131 MadeChange |= TryTailMergeBlocks(IBB, PredBB, MinCommonTailLength);
1132
1133 // Reinsert an unconditional branch if needed. The 1 below can occur as a
1134 // result of removing blocks in TryTailMergeBlocks.
1135 PredBB = &*std::prev(I); // this may have been changed in TryTailMergeBlocks
1136 if (MergePotentials.size() == 1 &&
1137 MergePotentials.begin()->getBlock() != PredBB)
1138 FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
1139 }
1140
1141 return MadeChange;
1142}
1143
1144void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) {
1145 SmallVector<BlockFrequency, 2> EdgeFreqLs(TailMBB.succ_size());
1146 BlockFrequency AccumulatedMBBFreq;
1147
1148 // Aggregate edge frequency of successor edge j:
1149 // edgeFreq(j) = sum (freq(bb) * edgeProb(bb, j)),
1150 // where bb is a basic block that is in SameTails.
1151 for (const auto &Src : SameTails) {
1152 const MachineBasicBlock *SrcMBB = Src.getBlock();
1153 BlockFrequency BlockFreq = MBBFreqInfo.getBlockFreq(SrcMBB);
1154 AccumulatedMBBFreq += BlockFreq;
1155
1156 // It is not necessary to recompute edge weights if TailBB has less than two
1157 // successors.
1158 if (TailMBB.succ_size() <= 1)
1159 continue;
1160
1161 auto EdgeFreq = EdgeFreqLs.begin();
1162
1163 for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1164 SuccI != SuccE; ++SuccI, ++EdgeFreq)
1165 *EdgeFreq += BlockFreq * MBPI.getEdgeProbability(SrcMBB, *SuccI);
1166 }
1167
1168 MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq);
1169
1170 if (TailMBB.succ_size() <= 1)
1171 return;
1172
1173 auto SumEdgeFreq =
1174 std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0))
1175 .getFrequency();
1176 auto EdgeFreq = EdgeFreqLs.begin();
1177
1178 if (SumEdgeFreq > 0) {
1179 for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1180 SuccI != SuccE; ++SuccI, ++EdgeFreq) {
1181 auto Prob = BranchProbability::getBranchProbability(
1182 EdgeFreq->getFrequency(), SumEdgeFreq);
1183 TailMBB.setSuccProbability(SuccI, Prob);
1184 }
1185 }
1186}
1187
1188//===----------------------------------------------------------------------===//
1189// Branch Optimization
1190//===----------------------------------------------------------------------===//
1191
1192bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
1193 bool MadeChange = false;
1194
1195 // Make sure blocks are numbered in order
1196 MF.RenumberBlocks();
1197 // Renumbering blocks alters EH scope membership, recalculate it.
1198 EHScopeMembership = getEHScopeMembership(MF);
1199
1200 for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
1201 I != E; ) {
1202 MachineBasicBlock *MBB = &*I++;
1203 MadeChange |= OptimizeBlock(MBB);
1204
1205 // If it is dead, remove it.
1206 if (MBB->pred_empty()) {
1207 RemoveDeadBlock(MBB);
1208 MadeChange = true;
1209 ++NumDeadBlocks;
1210 }
1211 }
1212
1213 return MadeChange;
1214}
1215
1216// Blocks should be considered empty if they contain only debug info;
1217// else the debug info would affect codegen.
1218static bool IsEmptyBlock(MachineBasicBlock *MBB) {
1219 return MBB->getFirstNonDebugInstr() == MBB->end();
4
Calling 'operator=='
10
Returning from 'operator=='
11
Returning zero, which participates in a condition later
1220}
1221
1222// Blocks with only debug info and branches should be considered the same
1223// as blocks with only branches.
1224static bool IsBranchOnlyBlock(MachineBasicBlock *MBB) {
1225 MachineBasicBlock::iterator I = MBB->getFirstNonDebugInstr();
1226 assert(I != MBB->end() && "empty block!")((I != MBB->end() && "empty block!") ? static_cast
<void> (0) : __assert_fail ("I != MBB->end() && \"empty block!\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 1226, __PRETTY_FUNCTION__))
;
1227 return I->isBranch();
1228}
1229
1230/// IsBetterFallthrough - Return true if it would be clearly better to
1231/// fall-through to MBB1 than to fall through into MBB2. This has to return
1232/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
1233/// result in infinite loops.
1234static bool IsBetterFallthrough(MachineBasicBlock *MBB1,
1235 MachineBasicBlock *MBB2) {
1236 assert(MBB1 && MBB2 && "Unknown MachineBasicBlock")((MBB1 && MBB2 && "Unknown MachineBasicBlock"
) ? static_cast<void> (0) : __assert_fail ("MBB1 && MBB2 && \"Unknown MachineBasicBlock\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 1236, __PRETTY_FUNCTION__))
;
1237
1238 // Right now, we use a simple heuristic. If MBB2 ends with a call, and
1239 // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to
1240 // optimize branches that branch to either a return block or an assert block
1241 // into a fallthrough to the return.
1242 MachineBasicBlock::iterator MBB1I = MBB1->getLastNonDebugInstr();
1243 MachineBasicBlock::iterator MBB2I = MBB2->getLastNonDebugInstr();
1244 if (MBB1I == MBB1->end() || MBB2I == MBB2->end())
1245 return false;
1246
1247 // If there is a clear successor ordering we make sure that one block
1248 // will fall through to the next
1249 if (MBB1->isSuccessor(MBB2)) return true;
1250 if (MBB2->isSuccessor(MBB1)) return false;
1251
1252 return MBB2I->isCall() && !MBB1I->isCall();
1253}
1254
1255/// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
1256/// instructions on the block.
1257static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB) {
1258 MachineBasicBlock::iterator I = MBB.getLastNonDebugInstr();
1259 if (I != MBB.end() && I->isBranch())
1260 return I->getDebugLoc();
1261 return DebugLoc();
1262}
1263
1264static void copyDebugInfoToPredecessor(const TargetInstrInfo *TII,
1265 MachineBasicBlock &MBB,
1266 MachineBasicBlock &PredMBB) {
1267 auto InsertBefore = PredMBB.getFirstTerminator();
1268 for (MachineInstr &MI : MBB.instrs())
1269 if (MI.isDebugInstr()) {
1270 TII->duplicate(PredMBB, InsertBefore, MI);
1271 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to pred: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "Copied debug entity from empty block to pred: "
<< MI; } } while (false)
1272 << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "Copied debug entity from empty block to pred: "
<< MI; } } while (false)
;
1273 }
1274}
1275
1276static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII,
1277 MachineBasicBlock &MBB,
1278 MachineBasicBlock &SuccMBB) {
1279 auto InsertBefore = SuccMBB.SkipPHIsAndLabels(SuccMBB.begin());
1280 for (MachineInstr &MI : MBB.instrs())
1281 if (MI.isDebugInstr()) {
1282 TII->duplicate(SuccMBB, InsertBefore, MI);
1283 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to succ: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "Copied debug entity from empty block to succ: "
<< MI; } } while (false)
1284 << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "Copied debug entity from empty block to succ: "
<< MI; } } while (false)
;
1285 }
1286}
1287
1288// Try to salvage DBG_VALUE instructions from an otherwise empty block. If such
1289// a basic block is removed we would lose the debug information unless we have
1290// copied the information to a predecessor/successor.
1291//
1292// TODO: This function only handles some simple cases. An alternative would be
1293// to run a heavier analysis, such as the LiveDebugValues pass, before we do
1294// branch folding.
1295static void salvageDebugInfoFromEmptyBlock(const TargetInstrInfo *TII,
1296 MachineBasicBlock &MBB) {
1297 assert(IsEmptyBlock(&MBB) && "Expected an empty block (except debug info).")((IsEmptyBlock(&MBB) && "Expected an empty block (except debug info)."
) ? static_cast<void> (0) : __assert_fail ("IsEmptyBlock(&MBB) && \"Expected an empty block (except debug info).\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 1297, __PRETTY_FUNCTION__))
;
1298 // If this MBB is the only predecessor of a successor it is legal to copy
1299 // DBG_VALUE instructions to the beginning of the successor.
1300 for (MachineBasicBlock *SuccBB : MBB.successors())
1301 if (SuccBB->pred_size() == 1)
1302 copyDebugInfoToSuccessor(TII, MBB, *SuccBB);
1303 // If this MBB is the only successor of a predecessor it is legal to copy the
1304 // DBG_VALUE instructions to the end of the predecessor (just before the
1305 // terminators, assuming that the terminator isn't affecting the DBG_VALUE).
1306 for (MachineBasicBlock *PredBB : MBB.predecessors())
1307 if (PredBB->succ_size() == 1)
1308 copyDebugInfoToPredecessor(TII, MBB, *PredBB);
1309}
1310
1311bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
1312 bool MadeChange = false;
1313 MachineFunction &MF = *MBB->getParent();
1314ReoptimizeBlock:
1315
1316 MachineFunction::iterator FallThrough = MBB->getIterator();
1317 ++FallThrough;
1318
1319 // Make sure MBB and FallThrough belong to the same EH scope.
1320 bool SameEHScope = true;
1321 if (!EHScopeMembership.empty() && FallThrough != MF.end()) {
1
Assuming the condition is false
2
Taking false branch
1322 auto MBBEHScope = EHScopeMembership.find(MBB);
1323 assert(MBBEHScope != EHScopeMembership.end())((MBBEHScope != EHScopeMembership.end()) ? static_cast<void
> (0) : __assert_fail ("MBBEHScope != EHScopeMembership.end()"
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 1323, __PRETTY_FUNCTION__))
;
1324 auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);
1325 assert(FallThroughEHScope != EHScopeMembership.end())((FallThroughEHScope != EHScopeMembership.end()) ? static_cast
<void> (0) : __assert_fail ("FallThroughEHScope != EHScopeMembership.end()"
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 1325, __PRETTY_FUNCTION__))
;
1326 SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
1327 }
1328
1329 // Analyze the branch in the current block. As a side-effect, this may cause
1330 // the block to become empty.
1331 MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
1332 SmallVector<MachineOperand, 4> CurCond;
1333 bool CurUnAnalyzable =
1334 TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
1335
1336 // If this block is empty, make everyone use its fall-through, not the block
1337 // explicitly. Landing pads should not do this since the landing-pad table
1338 // points to this block. Blocks with their addresses taken shouldn't be
1339 // optimized away.
1340 if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&
3
Calling 'IsEmptyBlock'
12
Returning from 'IsEmptyBlock'
1341 SameEHScope) {
1342 salvageDebugInfoFromEmptyBlock(TII, *MBB);
1343 // Dead block? Leave for cleanup later.
1344 if (MBB->pred_empty()) return MadeChange;
1345
1346 if (FallThrough == MF.end()) {
1347 // TODO: Simplify preds to not branch here if possible!
1348 } else if (FallThrough->isEHPad()) {
1349 // Don't rewrite to a landing pad fallthough. That could lead to the case
1350 // where a BB jumps to more than one landing pad.
1351 // TODO: Is it ever worth rewriting predecessors which don't already
1352 // jump to a landing pad, and so can safely jump to the fallthrough?
1353 } else if (MBB->isSuccessor(&*FallThrough)) {
1354 // Rewrite all predecessors of the old block to go to the fallthrough
1355 // instead.
1356 while (!MBB->pred_empty()) {
1357 MachineBasicBlock *Pred = *(MBB->pred_end()-1);
1358 Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);
1359 }
1360 // If MBB was the target of a jump table, update jump tables to go to the
1361 // fallthrough instead.
1362 if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1363 MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);
1364 MadeChange = true;
1365 }
1366 return MadeChange;
1367 }
1368
1369 // Check to see if we can simplify the terminator of the block before this
1370 // one.
1371 MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
1372
1373 MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
1374 SmallVector<MachineOperand, 4> PriorCond;
1375 bool PriorUnAnalyzable =
1376 TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
13
Value assigned to 'PriorTBB'
1377 if (!PriorUnAnalyzable) {
14
Assuming 'PriorUnAnalyzable' is false
15
Taking true branch
1378 // If the previous branch is conditional and both conditions go to the same
1379 // destination, remove the branch, replacing it with an unconditional one or
1380 // a fall-through.
1381 if (PriorTBB && PriorTBB == PriorFBB) {
16
Assuming 'PriorTBB' is null
1382 DebugLoc dl = getBranchDebugLoc(PrevBB);
1383 TII->removeBranch(PrevBB);
1384 PriorCond.clear();
1385 if (PriorTBB != MBB)
1386 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1387 MadeChange = true;
1388 ++NumBranchOpts;
1389 goto ReoptimizeBlock;
1390 }
1391
1392 // If the previous block unconditionally falls through to this block and
1393 // this block has no other predecessors, move the contents of this block
1394 // into the prior block. This doesn't usually happen when SimplifyCFG
1395 // has been used, but it can happen if tail merging splits a fall-through
1396 // predecessor of a block.
1397 // This has to check PrevBB->succ_size() because EH edges are ignored by
1398 // analyzeBranch.
1399 if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
17
Calling 'SmallVectorBase::empty'
20
Returning from 'SmallVectorBase::empty'
1400 PrevBB.succ_size() == 1 &&
1401 !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1402 LLVM_DEBUG(dbgs() << "\nMerging into block: " << PrevBBdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nMerging into block: "
<< PrevBB << "From MBB: " << *MBB; } } while
(false)
1403 << "From MBB: " << *MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nMerging into block: "
<< PrevBB << "From MBB: " << *MBB; } } while
(false)
;
1404 // Remove redundant DBG_VALUEs first.
1405 if (PrevBB.begin() != PrevBB.end()) {
1406 MachineBasicBlock::iterator PrevBBIter = PrevBB.end();
1407 --PrevBBIter;
1408 MachineBasicBlock::iterator MBBIter = MBB->begin();
1409 // Check if DBG_VALUE at the end of PrevBB is identical to the
1410 // DBG_VALUE at the beginning of MBB.
1411 while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()
1412 && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {
1413 if (!MBBIter->isIdenticalTo(*PrevBBIter))
1414 break;
1415 MachineInstr &DuplicateDbg = *MBBIter;
1416 ++MBBIter; -- PrevBBIter;
1417 DuplicateDbg.eraseFromParent();
1418 }
1419 }
1420 PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
1421 PrevBB.removeSuccessor(PrevBB.succ_begin());
1422 assert(PrevBB.succ_empty())((PrevBB.succ_empty()) ? static_cast<void> (0) : __assert_fail
("PrevBB.succ_empty()", "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 1422, __PRETTY_FUNCTION__))
;
1423 PrevBB.transferSuccessors(MBB);
1424 MadeChange = true;
1425 return MadeChange;
1426 }
1427
1428 // If the previous branch *only* branches to *this* block (conditional or
1429 // not) remove the branch.
1430 if (PriorTBB
20.1
'PriorTBB' is not equal to 'MBB'
20.1
'PriorTBB' is not equal to 'MBB'
20.1
'PriorTBB' is not equal to 'MBB'
20.1
'PriorTBB' is not equal to 'MBB'
== MBB && !PriorFBB) {
1431 TII->removeBranch(PrevBB);
1432 MadeChange = true;
1433 ++NumBranchOpts;
1434 goto ReoptimizeBlock;
1435 }
1436
1437 // If the prior block branches somewhere else on the condition and here if
1438 // the condition is false, remove the uncond second branch.
1439 if (PriorFBB == MBB) {
21
Assuming 'PriorFBB' is not equal to 'MBB'
22
Taking false branch
1440 DebugLoc dl = getBranchDebugLoc(PrevBB);
1441 TII->removeBranch(PrevBB);
1442 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1443 MadeChange = true;
1444 ++NumBranchOpts;
1445 goto ReoptimizeBlock;
1446 }
1447
1448 // If the prior block branches here on true and somewhere else on false, and
1449 // if the branch condition is reversible, reverse the branch to create a
1450 // fall-through.
1451 if (PriorTBB
22.1
'PriorTBB' is not equal to 'MBB'
22.1
'PriorTBB' is not equal to 'MBB'
22.1
'PriorTBB' is not equal to 'MBB'
22.1
'PriorTBB' is not equal to 'MBB'
== MBB) {
23
Taking false branch
1452 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1453 if (!TII->reverseBranchCondition(NewPriorCond)) {
1454 DebugLoc dl = getBranchDebugLoc(PrevBB);
1455 TII->removeBranch(PrevBB);
1456 TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);
1457 MadeChange = true;
1458 ++NumBranchOpts;
1459 goto ReoptimizeBlock;
1460 }
1461 }
1462
1463 // If this block has no successors (e.g. it is a return block or ends with
1464 // a call to a no-return function like abort or __cxa_throw) and if the pred
1465 // falls through into this block, and if it would otherwise fall through
1466 // into the block after this, move this block to the end of the function.
1467 //
1468 // We consider it more likely that execution will stay in the function (e.g.
1469 // due to loops) than it is to exit it. This asserts in loops etc, moving
1470 // the assert condition out of the loop body.
1471 if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&
24
Assuming the condition is true
25
Assuming 'PriorFBB' is null
27
Taking true branch
1472 MachineFunction::iterator(PriorTBB) == FallThrough &&
1473 !MBB->canFallThrough()) {
26
Assuming the condition is true
1474 bool DoTransform = true;
1475
1476 // We have to be careful that the succs of PredBB aren't both no-successor
1477 // blocks. If neither have successors and if PredBB is the second from
1478 // last block in the function, we'd just keep swapping the two blocks for
1479 // last. Only do the swap if one is clearly better to fall through than
1480 // the other.
1481 if (FallThrough == --MF.end() &&
28
Taking false branch
1482 !IsBetterFallthrough(PriorTBB, MBB))
1483 DoTransform = false;
1484
1485 if (DoTransform
28.1
'DoTransform' is true
28.1
'DoTransform' is true
28.1
'DoTransform' is true
28.1
'DoTransform' is true
) {
29
Taking true branch
1486 // Reverse the branch so we will fall through on the previous true cond.
1487 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1488 if (!TII->reverseBranchCondition(NewPriorCond)) {
30
Assuming the condition is true
31
Taking true branch
1489 LLVM_DEBUG(dbgs() << "\nMoving MBB: " << *MBBdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nMoving MBB: " <<
*MBB << "To make fallthrough to: " << *PriorTBB <<
"\n"; } } while (false)
32
Assuming 'DebugFlag' is true
33
Assuming the condition is true
34
Taking true branch
35
Forming reference to null pointer
1490 << "To make fallthrough to: " << *PriorTBB << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("branch-folder")) { dbgs() << "\nMoving MBB: " <<
*MBB << "To make fallthrough to: " << *PriorTBB <<
"\n"; } } while (false)
;
1491
1492 DebugLoc dl = getBranchDebugLoc(PrevBB);
1493 TII->removeBranch(PrevBB);
1494 TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);
1495
1496 // Move this block to the end of the function.
1497 MBB->moveAfter(&MF.back());
1498 MadeChange = true;
1499 ++NumBranchOpts;
1500 return MadeChange;
1501 }
1502 }
1503 }
1504 }
1505
1506 bool OptForSize =
1507 MF.getFunction().hasOptSize() ||
1508 llvm::shouldOptimizeForSize(MBB, PSI, &MBBFreqInfo);
1509 if (!IsEmptyBlock(MBB) && MBB->pred_size() == 1 && OptForSize) {
1510 // Changing "Jcc foo; foo: jmp bar;" into "Jcc bar;" might change the branch
1511 // direction, thereby defeating careful block placement and regressing
1512 // performance. Therefore, only consider this for optsize functions.
1513 MachineInstr &TailCall = *MBB->getFirstNonDebugInstr();
1514 if (TII->isUnconditionalTailCall(TailCall)) {
1515 MachineBasicBlock *Pred = *MBB->pred_begin();
1516 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1517 SmallVector<MachineOperand, 4> PredCond;
1518 bool PredAnalyzable =
1519 !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);
1520
1521 if (PredAnalyzable && !PredCond.empty() && PredTBB == MBB &&
1522 PredTBB != PredFBB) {
1523 // The predecessor has a conditional branch to this block which consists
1524 // of only a tail call. Try to fold the tail call into the conditional
1525 // branch.
1526 if (TII->canMakeTailCallConditional(PredCond, TailCall)) {
1527 // TODO: It would be nice if analyzeBranch() could provide a pointer
1528 // to the branch instruction so replaceBranchWithTailCall() doesn't
1529 // have to search for it.
1530 TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);
1531 ++NumTailCalls;
1532 Pred->removeSuccessor(MBB);
1533 MadeChange = true;
1534 return MadeChange;
1535 }
1536 }
1537 // If the predecessor is falling through to this block, we could reverse
1538 // the branch condition and fold the tail call into that. However, after
1539 // that we might have to re-arrange the CFG to fall through to the other
1540 // block and there is a high risk of regressing code size rather than
1541 // improving it.
1542 }
1543 }
1544
1545 if (!CurUnAnalyzable) {
1546 // If this is a two-way branch, and the FBB branches to this block, reverse
1547 // the condition so the single-basic-block loop is faster. Instead of:
1548 // Loop: xxx; jcc Out; jmp Loop
1549 // we want:
1550 // Loop: xxx; jncc Loop; jmp Out
1551 if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
1552 SmallVector<MachineOperand, 4> NewCond(CurCond);
1553 if (!TII->reverseBranchCondition(NewCond)) {
1554 DebugLoc dl = getBranchDebugLoc(*MBB);
1555 TII->removeBranch(*MBB);
1556 TII->insertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);
1557 MadeChange = true;
1558 ++NumBranchOpts;
1559 goto ReoptimizeBlock;
1560 }
1561 }
1562
1563 // If this branch is the only thing in its block, see if we can forward
1564 // other blocks across it.
1565 if (CurTBB && CurCond.empty() && !CurFBB &&
1566 IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
1567 !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1568 DebugLoc dl = getBranchDebugLoc(*MBB);
1569 // This block may contain just an unconditional branch. Because there can
1570 // be 'non-branch terminators' in the block, try removing the branch and
1571 // then seeing if the block is empty.
1572 TII->removeBranch(*MBB);
1573 // If the only things remaining in the block are debug info, remove these
1574 // as well, so this will behave the same as an empty block in non-debug
1575 // mode.
1576 if (IsEmptyBlock(MBB)) {
1577 // Make the block empty, losing the debug info (we could probably
1578 // improve this in some cases.)
1579 MBB->erase(MBB->begin(), MBB->end());
1580 }
1581 // If this block is just an unconditional branch to CurTBB, we can
1582 // usually completely eliminate the block. The only case we cannot
1583 // completely eliminate the block is when the block before this one
1584 // falls through into MBB and we can't understand the prior block's branch
1585 // condition.
1586 if (MBB->empty()) {
1587 bool PredHasNoFallThrough = !PrevBB.canFallThrough();
1588 if (PredHasNoFallThrough || !PriorUnAnalyzable ||
1589 !PrevBB.isSuccessor(MBB)) {
1590 // If the prior block falls through into us, turn it into an
1591 // explicit branch to us to make updates simpler.
1592 if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
1593 PriorTBB != MBB && PriorFBB != MBB) {
1594 if (!PriorTBB) {
1595 assert(PriorCond.empty() && !PriorFBB &&((PriorCond.empty() && !PriorFBB && "Bad branch analysis"
) ? static_cast<void> (0) : __assert_fail ("PriorCond.empty() && !PriorFBB && \"Bad branch analysis\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 1596, __PRETTY_FUNCTION__))
1596 "Bad branch analysis")((PriorCond.empty() && !PriorFBB && "Bad branch analysis"
) ? static_cast<void> (0) : __assert_fail ("PriorCond.empty() && !PriorFBB && \"Bad branch analysis\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 1596, __PRETTY_FUNCTION__))
;
1597 PriorTBB = MBB;
1598 } else {
1599 assert(!PriorFBB && "Machine CFG out of date!")((!PriorFBB && "Machine CFG out of date!") ? static_cast
<void> (0) : __assert_fail ("!PriorFBB && \"Machine CFG out of date!\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/CodeGen/BranchFolding.cpp"
, 1599, __PRETTY_FUNCTION__))
;
1600 PriorFBB = MBB;
1601 }
1602 DebugLoc pdl = getBranchDebugLoc(PrevBB);
1603 TII->removeBranch(PrevBB);
1604 TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
1605 }
1606
1607 // Iterate through all the predecessors, revectoring each in-turn.
1608 size_t PI = 0;
1609 bool DidChange = false;
1610 bool HasBranchToSelf = false;
1611 while(PI != MBB->pred_size()) {
1612 MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
1613 if (PMBB == MBB) {
1614 // If this block has an uncond branch to itself, leave it.
1615 ++PI;
1616 HasBranchToSelf = true;
1617 } else {
1618 DidChange = true;
1619 PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
1620 // If this change resulted in PMBB ending in a conditional
1621 // branch where both conditions go to the same destination,
1622 // change this to an unconditional branch.
1623 MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;
1624 SmallVector<MachineOperand, 4> NewCurCond;
1625 bool NewCurUnAnalyzable = TII->analyzeBranch(
1626 *PMBB, NewCurTBB, NewCurFBB, NewCurCond, true);
1627 if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
1628 DebugLoc pdl = getBranchDebugLoc(*PMBB);
1629 TII->removeBranch(*PMBB);
1630 NewCurCond.clear();
1631 TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);
1632 MadeChange = true;
1633 ++NumBranchOpts;
1634 }
1635 }
1636 }
1637
1638 // Change any jumptables to go to the new MBB.
1639 if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1640 MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
1641 if (DidChange) {
1642 ++NumBranchOpts;
1643 MadeChange = true;
1644 if (!HasBranchToSelf) return MadeChange;
1645 }
1646 }
1647 }
1648
1649 // Add the branch back if the block is more than just an uncond branch.
1650 TII->insertBranch(*MBB, CurTBB, nullptr, CurCond, dl);
1651 }
1652 }
1653
1654 // If the prior block doesn't fall through into this block, and if this
1655 // block doesn't fall through into some other block, see if we can find a
1656 // place to move this block where a fall-through will happen.
1657 if (!PrevBB.canFallThrough()) {
1658 // Now we know that there was no fall-through into this block, check to
1659 // see if it has a fall-through into its successor.
1660 bool CurFallsThru = MBB->canFallThrough();
1661
1662 if (!MBB->isEHPad()) {
1663 // Check all the predecessors of this block. If one of them has no fall
1664 // throughs, and analyzeBranch thinks it _could_ fallthrough to this
1665 // block, move this block right after it.
1666 for (MachineBasicBlock *PredBB : MBB->predecessors()) {
1667 // Analyze the branch at the end of the pred.
1668 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1669 SmallVector<MachineOperand, 4> PredCond;
1670 if (PredBB != MBB && !PredBB->canFallThrough() &&
1671 !TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) &&
1672 (PredTBB == MBB || PredFBB == MBB) &&
1673 (!CurFallsThru || !CurTBB || !CurFBB) &&
1674 (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
1675 // If the current block doesn't fall through, just move it.
1676 // If the current block can fall through and does not end with a
1677 // conditional branch, we need to append an unconditional jump to
1678 // the (current) next block. To avoid a possible compile-time
1679 // infinite loop, move blocks only backward in this case.
1680 // Also, if there are already 2 branches here, we cannot add a third;
1681 // this means we have the case
1682 // Bcc next
1683 // B elsewhere
1684 // next:
1685 if (CurFallsThru) {
1686 MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());
1687 CurCond.clear();
1688 TII->insertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());
1689 }
1690 MBB->moveAfter(PredBB);
1691 MadeChange = true;
1692 goto ReoptimizeBlock;
1693 }
1694 }
1695 }
1696
1697 if (!CurFallsThru) {
1698 // Check analyzable branch-successors to see if we can move this block
1699 // before one.
1700 if (!CurUnAnalyzable) {
1701 for (MachineBasicBlock *SuccBB : {CurFBB, CurTBB}) {
1702 if (!SuccBB)
1703 continue;
1704 // Analyze the branch at the end of the block before the succ.
1705 MachineFunction::iterator SuccPrev = --SuccBB->getIterator();
1706
1707 // If this block doesn't already fall-through to that successor, and
1708 // if the succ doesn't already have a block that can fall through into
1709 // it, we can arrange for the fallthrough to happen.
1710 if (SuccBB != MBB && &*SuccPrev != MBB &&
1711 !SuccPrev->canFallThrough()) {
1712 MBB->moveBefore(SuccBB);
1713 MadeChange = true;
1714 goto ReoptimizeBlock;
1715 }
1716 }
1717 }
1718
1719 // Okay, there is no really great place to put this block. If, however,
1720 // the block before this one would be a fall-through if this block were
1721 // removed, move this block to the end of the function. There is no real
1722 // advantage in "falling through" to an EH block, so we don't want to
1723 // perform this transformation for that case.
1724 //
1725 // Also, Windows EH introduced the possibility of an arbitrary number of
1726 // successors to a given block. The analyzeBranch call does not consider
1727 // exception handling and so we can get in a state where a block
1728 // containing a call is followed by multiple EH blocks that would be
1729 // rotated infinitely at the end of the function if the transformation
1730 // below were performed for EH "FallThrough" blocks. Therefore, even if
1731 // that appears not to be happening anymore, we should assume that it is
1732 // possible and not remove the "!FallThrough()->isEHPad" condition below.
1733 MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
1734 SmallVector<MachineOperand, 4> PrevCond;
1735 if (FallThrough != MF.end() &&
1736 !FallThrough->isEHPad() &&
1737 !TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
1738 PrevBB.isSuccessor(&*FallThrough)) {
1739 MBB->moveAfter(&MF.back());
1740 MadeChange = true;
1741 return MadeChange;
1742 }
1743 }
1744 }
1745
1746 return MadeChange;
1747}
1748
1749//===----------------------------------------------------------------------===//
1750// Hoist Common Code
1751//===----------------------------------------------------------------------===//
1752
1753bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
1754 bool MadeChange = false;
1755 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ) {
1756 MachineBasicBlock *MBB = &*I++;
1757 MadeChange |= HoistCommonCodeInSuccs(MBB);
1758 }
1759
1760 return MadeChange;
1761}
1762
1763/// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
1764/// its 'true' successor.
1765static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
1766 MachineBasicBlock *TrueBB) {
1767 for (MachineBasicBlock *SuccBB : BB->successors())
1768 if (SuccBB != TrueBB)
1769 return SuccBB;
1770 return nullptr;
1771}
1772
1773template <class Container>
1774static void addRegAndItsAliases(Register Reg, const TargetRegisterInfo *TRI,
1775 Container &Set) {
1776 if (Reg.isPhysical()) {
1777 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
1778 Set.insert(*AI);
1779 } else {
1780 Set.insert(Reg);
1781 }
1782}
1783
1784/// findHoistingInsertPosAndDeps - Find the location to move common instructions
1785/// in successors to. The location is usually just before the terminator,
1786/// however if the terminator is a conditional branch and its previous
1787/// instruction is the flag setting instruction, the previous instruction is
1788/// the preferred location. This function also gathers uses and defs of the
1789/// instructions from the insertion point to the end of the block. The data is
1790/// used by HoistCommonCodeInSuccs to ensure safety.
1791static
1792MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
1793 const TargetInstrInfo *TII,
1794 const TargetRegisterInfo *TRI,
1795 SmallSet<Register, 4> &Uses,
1796 SmallSet<Register, 4> &Defs) {
1797 MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();
1798 if (!TII->isUnpredicatedTerminator(*Loc))
1799 return MBB->end();
1800
1801 for (const MachineOperand &MO : Loc->operands()) {
1802 if (!MO.isReg())
1803 continue;
1804 Register Reg = MO.getReg();
1805 if (!Reg)
1806 continue;
1807 if (MO.isUse()) {
1808 addRegAndItsAliases(Reg, TRI, Uses);
1809 } else {
1810 if (!MO.isDead())
1811 // Don't try to hoist code in the rare case the terminator defines a
1812 // register that is later used.
1813 return MBB->end();
1814
1815 // If the terminator defines a register, make sure we don't hoist
1816 // the instruction whose def might be clobbered by the terminator.
1817 addRegAndItsAliases(Reg, TRI, Defs);
1818 }
1819 }
1820
1821 if (Uses.empty())
1822 return Loc;
1823 // If the terminator is the only instruction in the block and Uses is not
1824 // empty (or we would have returned above), we can still safely hoist
1825 // instructions just before the terminator as long as the Defs/Uses are not
1826 // violated (which is checked in HoistCommonCodeInSuccs).
1827 if (Loc == MBB->begin())
1828 return Loc;
1829
1830 // The terminator is probably a conditional branch, try not to separate the
1831 // branch from condition setting instruction.
1832 MachineBasicBlock::iterator PI = prev_nodbg(Loc, MBB->begin());
1833
1834 bool IsDef = false;
1835 for (const MachineOperand &MO : PI->operands()) {
1836 // If PI has a regmask operand, it is probably a call. Separate away.
1837 if (MO.isRegMask())
1838 return Loc;
1839 if (!MO.isReg() || MO.isUse())
1840 continue;
1841 Register Reg = MO.getReg();
1842 if (!Reg)
1843 continue;
1844 if (Uses.count(Reg)) {
1845 IsDef = true;
1846 break;
1847 }
1848 }
1849 if (!IsDef)
1850 // The condition setting instruction is not just before the conditional
1851 // branch.
1852 return Loc;
1853
1854 // Be conservative, don't insert instruction above something that may have
1855 // side-effects. And since it's potentially bad to separate flag setting
1856 // instruction from the conditional branch, just abort the optimization
1857 // completely.
1858 // Also avoid moving code above predicated instruction since it's hard to
1859 // reason about register liveness with predicated instruction.
1860 bool DontMoveAcrossStore = true;
1861 if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(*PI))
1862 return MBB->end();
1863
1864 // Find out what registers are live. Note this routine is ignoring other live
1865 // registers which are only used by instructions in successor blocks.
1866 for (const MachineOperand &MO : PI->operands()) {
1867 if (!MO.isReg())
1868 continue;
1869 Register Reg = MO.getReg();
1870 if (!Reg)
1871 continue;
1872 if (MO.isUse()) {
1873 addRegAndItsAliases(Reg, TRI, Uses);
1874 } else {
1875 if (Uses.erase(Reg)) {
1876 if (Register::isPhysicalRegister(Reg)) {
1877 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
1878 Uses.erase(*SubRegs); // Use sub-registers to be conservative
1879 }
1880 }
1881 addRegAndItsAliases(Reg, TRI, Defs);
1882 }
1883 }
1884
1885 return PI;
1886}
1887
1888bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
1889 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1890 SmallVector<MachineOperand, 4> Cond;
1891 if (TII->analyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
1892 return false;
1893
1894 if (!FBB) FBB = findFalseBlock(MBB, TBB);
1895 if (!FBB)
1896 // Malformed bcc? True and false blocks are the same?
1897 return false;
1898
1899 // Restrict the optimization to cases where MBB is the only predecessor,
1900 // it is an obvious win.
1901 if (TBB->pred_size() > 1 || FBB->pred_size() > 1)
1902 return false;
1903
1904 // Find a suitable position to hoist the common instructions to. Also figure
1905 // out which registers are used or defined by instructions from the insertion
1906 // point to the end of the block.
1907 SmallSet<Register, 4> Uses, Defs;
1908 MachineBasicBlock::iterator Loc =
1909 findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
1910 if (Loc == MBB->end())
1911 return false;
1912
1913 bool HasDups = false;
1914 SmallSet<Register, 4> ActiveDefsSet, AllDefsSet;
1915 MachineBasicBlock::iterator TIB = TBB->begin();
1916 MachineBasicBlock::iterator FIB = FBB->begin();
1917 MachineBasicBlock::iterator TIE = TBB->end();
1918 MachineBasicBlock::iterator FIE = FBB->end();
1919 while (TIB != TIE && FIB != FIE) {
1920 // Skip dbg_value instructions. These do not count.
1921 TIB = skipDebugInstructionsForward(TIB, TIE);
1922 FIB = skipDebugInstructionsForward(FIB, FIE);
1923 if (TIB == TIE || FIB == FIE)
1924 break;
1925
1926 if (!TIB->isIdenticalTo(*FIB, MachineInstr::CheckKillDead))
1927 break;
1928
1929 if (TII->isPredicated(*TIB))
1930 // Hard to reason about register liveness with predicated instruction.
1931 break;
1932
1933 bool IsSafe = true;
1934 for (MachineOperand &MO : TIB->operands()) {
1935 // Don't attempt to hoist instructions with register masks.
1936 if (MO.isRegMask()) {
1937 IsSafe = false;
1938 break;
1939 }
1940 if (!MO.isReg())
1941 continue;
1942 Register Reg = MO.getReg();
1943 if (!Reg)
1944 continue;
1945 if (MO.isDef()) {
1946 if (Uses.count(Reg)) {
1947 // Avoid clobbering a register that's used by the instruction at
1948 // the point of insertion.
1949 IsSafe = false;
1950 break;
1951 }
1952
1953 if (Defs.count(Reg) && !MO.isDead()) {
1954 // Don't hoist the instruction if the def would be clobber by the
1955 // instruction at the point insertion. FIXME: This is overly
1956 // conservative. It should be possible to hoist the instructions
1957 // in BB2 in the following example:
1958 // BB1:
1959 // r1, eflag = op1 r2, r3
1960 // brcc eflag
1961 //
1962 // BB2:
1963 // r1 = op2, ...
1964 // = op3, killed r1
1965 IsSafe = false;
1966 break;
1967 }
1968 } else if (!ActiveDefsSet.count(Reg)) {
1969 if (Defs.count(Reg)) {
1970 // Use is defined by the instruction at the point of insertion.
1971 IsSafe = false;
1972 break;
1973 }
1974
1975 if (MO.isKill() && Uses.count(Reg))
1976 // Kills a register that's read by the instruction at the point of
1977 // insertion. Remove the kill marker.
1978 MO.setIsKill(false);
1979 }
1980 }
1981 if (!IsSafe)
1982 break;
1983
1984 bool DontMoveAcrossStore = true;
1985 if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore))
1986 break;
1987
1988 // Remove kills from ActiveDefsSet, these registers had short live ranges.
1989 for (const MachineOperand &MO : TIB->operands()) {
1990 if (!MO.isReg() || !MO.isUse() || !MO.isKill())
1991 continue;
1992 Register Reg = MO.getReg();
1993 if (!Reg)
1994 continue;
1995 if (!AllDefsSet.count(Reg)) {
1996 continue;
1997 }
1998 if (Reg.isPhysical()) {
1999 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
2000 ActiveDefsSet.erase(*AI);
2001 } else {
2002 ActiveDefsSet.erase(Reg);
2003 }
2004 }
2005
2006 // Track local defs so we can update liveins.
2007 for (const MachineOperand &MO : TIB->operands()) {
2008 if (!MO.isReg() || !MO.isDef() || MO.isDead())
2009 continue;
2010 Register Reg = MO.getReg();
2011 if (!Reg || Reg.isVirtual())
2012 continue;
2013 addRegAndItsAliases(Reg, TRI, ActiveDefsSet);
2014 addRegAndItsAliases(Reg, TRI, AllDefsSet);
2015 }
2016
2017 HasDups = true;
2018 ++TIB;
2019 ++FIB;
2020 }
2021
2022 if (!HasDups)
2023 return false;
2024
2025 MBB->splice(Loc, TBB, TBB->begin(), TIB);
2026 FBB->erase(FBB->begin(), FIB);
2027
2028 if (UpdateLiveIns) {
2029 recomputeLiveIns(*TBB);
2030 recomputeLiveIns(*FBB);
2031 }
2032
2033 ++NumHoist;
2034 return true;
2035}

/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h

1//===- llvm/CodeGen/MachineInstrBundleIterator.h ----------------*- C++ -*-===//
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// Defines an iterator class that bundles MachineInstr.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H
14#define LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H
15
16#include "llvm/ADT/ilist.h"
17#include "llvm/ADT/simple_ilist.h"
18#include <cassert>
19#include <iterator>
20#include <type_traits>
21
22namespace llvm {
23
24template <class T, bool IsReverse> struct MachineInstrBundleIteratorTraits;
25template <class T> struct MachineInstrBundleIteratorTraits<T, false> {
26 using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>;
27 using instr_iterator = typename list_type::iterator;
28 using nonconst_instr_iterator = typename list_type::iterator;
29 using const_instr_iterator = typename list_type::const_iterator;
30};
31template <class T> struct MachineInstrBundleIteratorTraits<T, true> {
32 using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>;
33 using instr_iterator = typename list_type::reverse_iterator;
34 using nonconst_instr_iterator = typename list_type::reverse_iterator;
35 using const_instr_iterator = typename list_type::const_reverse_iterator;
36};
37template <class T> struct MachineInstrBundleIteratorTraits<const T, false> {
38 using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>;
39 using instr_iterator = typename list_type::const_iterator;
40 using nonconst_instr_iterator = typename list_type::iterator;
41 using const_instr_iterator = typename list_type::const_iterator;
42};
43template <class T> struct MachineInstrBundleIteratorTraits<const T, true> {
44 using list_type = simple_ilist<T, ilist_sentinel_tracking<true>>;
45 using instr_iterator = typename list_type::const_reverse_iterator;
46 using nonconst_instr_iterator = typename list_type::reverse_iterator;
47 using const_instr_iterator = typename list_type::const_reverse_iterator;
48};
49
50template <bool IsReverse> struct MachineInstrBundleIteratorHelper;
51template <> struct MachineInstrBundleIteratorHelper<false> {
52 /// Get the beginning of the current bundle.
53 template <class Iterator> static Iterator getBundleBegin(Iterator I) {
54 if (!I.isEnd())
55 while (I->isBundledWithPred())
56 --I;
57 return I;
58 }
59
60 /// Get the final node of the current bundle.
61 template <class Iterator> static Iterator getBundleFinal(Iterator I) {
62 if (!I.isEnd())
63 while (I->isBundledWithSucc())
64 ++I;
65 return I;
66 }
67
68 /// Increment forward ilist iterator.
69 template <class Iterator> static void increment(Iterator &I) {
70 I = std::next(getBundleFinal(I));
71 }
72
73 /// Decrement forward ilist iterator.
74 template <class Iterator> static void decrement(Iterator &I) {
75 I = getBundleBegin(std::prev(I));
76 }
77};
78
79template <> struct MachineInstrBundleIteratorHelper<true> {
80 /// Get the beginning of the current bundle.
81 template <class Iterator> static Iterator getBundleBegin(Iterator I) {
82 return MachineInstrBundleIteratorHelper<false>::getBundleBegin(
83 I.getReverse())
84 .getReverse();
85 }
86
87 /// Get the final node of the current bundle.
88 template <class Iterator> static Iterator getBundleFinal(Iterator I) {
89 return MachineInstrBundleIteratorHelper<false>::getBundleFinal(
90 I.getReverse())
91 .getReverse();
92 }
93
94 /// Increment reverse ilist iterator.
95 template <class Iterator> static void increment(Iterator &I) {
96 I = getBundleBegin(std::next(I));
97 }
98
99 /// Decrement reverse ilist iterator.
100 template <class Iterator> static void decrement(Iterator &I) {
101 I = std::prev(getBundleFinal(I));
102 }
103};
104
105/// MachineBasicBlock iterator that automatically skips over MIs that are
106/// inside bundles (i.e. walk top level MIs only).
107template <typename Ty, bool IsReverse = false>
108class MachineInstrBundleIterator : MachineInstrBundleIteratorHelper<IsReverse> {
109 using Traits = MachineInstrBundleIteratorTraits<Ty, IsReverse>;
110 using instr_iterator = typename Traits::instr_iterator;
111
112 instr_iterator MII;
113
114public:
115 using value_type = typename instr_iterator::value_type;
116 using difference_type = typename instr_iterator::difference_type;
117 using pointer = typename instr_iterator::pointer;
118 using reference = typename instr_iterator::reference;
119 using const_pointer = typename instr_iterator::const_pointer;
120 using const_reference = typename instr_iterator::const_reference;
121 using iterator_category = std::bidirectional_iterator_tag;
122
123private:
124 using nonconst_instr_iterator = typename Traits::nonconst_instr_iterator;
125 using const_instr_iterator = typename Traits::const_instr_iterator;
126 using nonconst_iterator =
127 MachineInstrBundleIterator<typename nonconst_instr_iterator::value_type,
128 IsReverse>;
129 using reverse_iterator = MachineInstrBundleIterator<Ty, !IsReverse>;
130
131public:
132 MachineInstrBundleIterator(instr_iterator MI) : MII(MI) {
133 assert((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) &&(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred
()) && "It's not legal to initialize MachineInstrBundleIterator with a "
"bundled MI") ? static_cast<void> (0) : __assert_fail (
"(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 135, __PRETTY_FUNCTION__))
134 "It's not legal to initialize MachineInstrBundleIterator with a "(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred
()) && "It's not legal to initialize MachineInstrBundleIterator with a "
"bundled MI") ? static_cast<void> (0) : __assert_fail (
"(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 135, __PRETTY_FUNCTION__))
135 "bundled MI")(((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred
()) && "It's not legal to initialize MachineInstrBundleIterator with a "
"bundled MI") ? static_cast<void> (0) : __assert_fail (
"(!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) && \"It's not legal to initialize MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 135, __PRETTY_FUNCTION__))
;
136 }
137
138 MachineInstrBundleIterator(reference MI) : MII(MI) {
139 assert(!MI.isBundledWithPred() && "It's not legal to initialize "((!MI.isBundledWithPred() && "It's not legal to initialize "
"MachineInstrBundleIterator with a " "bundled MI") ? static_cast
<void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 141, __PRETTY_FUNCTION__))
140 "MachineInstrBundleIterator with a "((!MI.isBundledWithPred() && "It's not legal to initialize "
"MachineInstrBundleIterator with a " "bundled MI") ? static_cast
<void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 141, __PRETTY_FUNCTION__))
141 "bundled MI")((!MI.isBundledWithPred() && "It's not legal to initialize "
"MachineInstrBundleIterator with a " "bundled MI") ? static_cast
<void> (0) : __assert_fail ("!MI.isBundledWithPred() && \"It's not legal to initialize \" \"MachineInstrBundleIterator with a \" \"bundled MI\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 141, __PRETTY_FUNCTION__))
;
142 }
143
144 MachineInstrBundleIterator(pointer MI) : MII(MI) {
145 // FIXME: This conversion should be explicit.
146 assert((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "
"MachineInstrBundleIterator " "with a bundled MI") ? static_cast
<void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 148, __PRETTY_FUNCTION__))
147 "MachineInstrBundleIterator "(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "
"MachineInstrBundleIterator " "with a bundled MI") ? static_cast
<void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 148, __PRETTY_FUNCTION__))
148 "with a bundled MI")(((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "
"MachineInstrBundleIterator " "with a bundled MI") ? static_cast
<void> (0) : __assert_fail ("(!MI || !MI->isBundledWithPred()) && \"It's not legal to initialize \" \"MachineInstrBundleIterator \" \"with a bundled MI\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h"
, 148, __PRETTY_FUNCTION__))
;
149 }
150
151 // Template allows conversion from const to nonconst.
152 template <class OtherTy>
153 MachineInstrBundleIterator(
154 const MachineInstrBundleIterator<OtherTy, IsReverse> &I,
155 std::enable_if_t<std::is_convertible<OtherTy *, Ty *>::value, void *> =
156 nullptr)
157 : MII(I.getInstrIterator()) {}
158
159 MachineInstrBundleIterator() : MII(nullptr) {}
160
161 /// Explicit conversion between forward/reverse iterators.
162 ///
163 /// Translate between forward and reverse iterators without changing range
164 /// boundaries. The resulting iterator will dereference (and have a handle)
165 /// to the previous node, which is somewhat unexpected; but converting the
166 /// two endpoints in a range will give the same range in reverse.
167 ///
168 /// This matches std::reverse_iterator conversions.
169 explicit MachineInstrBundleIterator(
170 const MachineInstrBundleIterator<Ty, !IsReverse> &I)
171 : MachineInstrBundleIterator(++I.getReverse()) {}
172
173 /// Get the bundle iterator for the given instruction's bundle.
174 static MachineInstrBundleIterator getAtBundleBegin(instr_iterator MI) {
175 return MachineInstrBundleIteratorHelper<IsReverse>::getBundleBegin(MI);
176 }
177
178 reference operator*() const { return *MII; }
179 pointer operator->() const { return &operator*(); }
180
181 /// Check for null.
182 bool isValid() const { return MII.getNodePtr(); }
183
184 friend bool operator==(const MachineInstrBundleIterator &L,
185 const MachineInstrBundleIterator &R) {
186 return L.MII == R.MII;
5
Calling 'operator=='
8
Returning from 'operator=='
9
Returning zero, which participates in a condition later
187 }
188 friend bool operator==(const MachineInstrBundleIterator &L,
189 const const_instr_iterator &R) {
190 return L.MII == R; // Avoid assertion about validity of R.
191 }
192 friend bool operator==(const const_instr_iterator &L,
193 const MachineInstrBundleIterator &R) {
194 return L == R.MII; // Avoid assertion about validity of L.
195 }
196 friend bool operator==(const MachineInstrBundleIterator &L,
197 const nonconst_instr_iterator &R) {
198 return L.MII == R; // Avoid assertion about validity of R.
199 }
200 friend bool operator==(const nonconst_instr_iterator &L,
201 const MachineInstrBundleIterator &R) {
202 return L == R.MII; // Avoid assertion about validity of L.
203 }
204 friend bool operator==(const MachineInstrBundleIterator &L, const_pointer R) {
205 return L == const_instr_iterator(R); // Avoid assertion about validity of R.
206 }
207 friend bool operator==(const_pointer L, const MachineInstrBundleIterator &R) {
208 return const_instr_iterator(L) == R; // Avoid assertion about validity of L.
209 }
210 friend bool operator==(const MachineInstrBundleIterator &L,
211 const_reference R) {
212 return L == &R; // Avoid assertion about validity of R.
213 }
214 friend bool operator==(const_reference L,
215 const MachineInstrBundleIterator &R) {
216 return &L == R; // Avoid assertion about validity of L.
217 }
218
219 friend bool operator!=(const MachineInstrBundleIterator &L,
220 const MachineInstrBundleIterator &R) {
221 return !(L == R);
222 }
223 friend bool operator!=(const MachineInstrBundleIterator &L,
224 const const_instr_iterator &R) {
225 return !(L == R);
226 }
227 friend bool operator!=(const const_instr_iterator &L,
228 const MachineInstrBundleIterator &R) {
229 return !(L == R);
230 }
231 friend bool operator!=(const MachineInstrBundleIterator &L,
232 const nonconst_instr_iterator &R) {
233 return !(L == R);
234 }
235 friend bool operator!=(const nonconst_instr_iterator &L,
236 const MachineInstrBundleIterator &R) {
237 return !(L == R);
238 }
239 friend bool operator!=(const MachineInstrBundleIterator &L, const_pointer R) {
240 return !(L == R);
241 }
242 friend bool operator!=(const_pointer L, const MachineInstrBundleIterator &R) {
243 return !(L == R);
244 }
245 friend bool operator!=(const MachineInstrBundleIterator &L,
246 const_reference R) {
247 return !(L == R);
248 }
249 friend bool operator!=(const_reference L,
250 const MachineInstrBundleIterator &R) {
251 return !(L == R);
252 }
253
254 // Increment and decrement operators...
255 MachineInstrBundleIterator &operator--() {
256 this->decrement(MII);
257 return *this;
258 }
259 MachineInstrBundleIterator &operator++() {
260 this->increment(MII);
261 return *this;
262 }
263 MachineInstrBundleIterator operator--(int) {
264 MachineInstrBundleIterator Temp = *this;
265 --*this;
266 return Temp;
267 }
268 MachineInstrBundleIterator operator++(int) {
269 MachineInstrBundleIterator Temp = *this;
270 ++*this;
271 return Temp;
272 }
273
274 instr_iterator getInstrIterator() const { return MII; }
275
276 nonconst_iterator getNonConstIterator() const { return MII.getNonConst(); }
277
278 /// Get a reverse iterator to the same node.
279 ///
280 /// Gives a reverse iterator that will dereference (and have a handle) to the
281 /// same node. Converting the endpoint iterators in a range will give a
282 /// different range; for range operations, use the explicit conversions.
283 reverse_iterator getReverse() const { return MII.getReverse(); }
284};
285
286} // end namespace llvm
287
288#endif // LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H

/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/ilist_iterator.h

1//===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===//
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#ifndef LLVM_ADT_ILIST_ITERATOR_H
10#define LLVM_ADT_ILIST_ITERATOR_H
11
12#include "llvm/ADT/ilist_node.h"
13#include <cassert>
14#include <cstddef>
15#include <iterator>
16#include <type_traits>
17
18namespace llvm {
19
20namespace ilist_detail {
21
22/// Find const-correct node types.
23template <class OptionsT, bool IsConst> struct IteratorTraits;
24template <class OptionsT> struct IteratorTraits<OptionsT, false> {
25 using value_type = typename OptionsT::value_type;
26 using pointer = typename OptionsT::pointer;
27 using reference = typename OptionsT::reference;
28 using node_pointer = ilist_node_impl<OptionsT> *;
29 using node_reference = ilist_node_impl<OptionsT> &;
30};
31template <class OptionsT> struct IteratorTraits<OptionsT, true> {
32 using value_type = const typename OptionsT::value_type;
33 using pointer = typename OptionsT::const_pointer;
34 using reference = typename OptionsT::const_reference;
35 using node_pointer = const ilist_node_impl<OptionsT> *;
36 using node_reference = const ilist_node_impl<OptionsT> &;
37};
38
39template <bool IsReverse> struct IteratorHelper;
40template <> struct IteratorHelper<false> : ilist_detail::NodeAccess {
41 using Access = ilist_detail::NodeAccess;
42
43 template <class T> static void increment(T *&I) { I = Access::getNext(*I); }
44 template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); }
45};
46template <> struct IteratorHelper<true> : ilist_detail::NodeAccess {
47 using Access = ilist_detail::NodeAccess;
48
49 template <class T> static void increment(T *&I) { I = Access::getPrev(*I); }
50 template <class T> static void decrement(T *&I) { I = Access::getNext(*I); }
51};
52
53} // end namespace ilist_detail
54
55/// Iterator for intrusive lists based on ilist_node.
56template <class OptionsT, bool IsReverse, bool IsConst>
57class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> {
58 friend ilist_iterator<OptionsT, IsReverse, !IsConst>;
59 friend ilist_iterator<OptionsT, !IsReverse, IsConst>;
60 friend ilist_iterator<OptionsT, !IsReverse, !IsConst>;
61
62 using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
63 using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
64
65public:
66 using value_type = typename Traits::value_type;
67 using pointer = typename Traits::pointer;
68 using reference = typename Traits::reference;
69 using difference_type = ptrdiff_t;
70 using iterator_category = std::bidirectional_iterator_tag;
71 using const_pointer = typename OptionsT::const_pointer;
72 using const_reference = typename OptionsT::const_reference;
73
74private:
75 using node_pointer = typename Traits::node_pointer;
76 using node_reference = typename Traits::node_reference;
77
78 node_pointer NodePtr = nullptr;
79
80public:
81 /// Create from an ilist_node.
82 explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
83
84 explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {}
85 explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {}
86 ilist_iterator() = default;
87
88 // This is templated so that we can allow constructing a const iterator from
89 // a nonconst iterator...
90 template <bool RHSIsConst>
91 ilist_iterator(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS,
92 std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr)
93 : NodePtr(RHS.NodePtr) {}
94
95 // This is templated so that we can allow assigning to a const iterator from
96 // a nonconst iterator...
97 template <bool RHSIsConst>
98 std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator &>
99 operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) {
100 NodePtr = RHS.NodePtr;
101 return *this;
102 }
103
104 /// Explicit conversion between forward/reverse iterators.
105 ///
106 /// Translate between forward and reverse iterators without changing range
107 /// boundaries. The resulting iterator will dereference (and have a handle)
108 /// to the previous node, which is somewhat unexpected; but converting the
109 /// two endpoints in a range will give the same range in reverse.
110 ///
111 /// This matches std::reverse_iterator conversions.
112 explicit ilist_iterator(
113 const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS)
114 : ilist_iterator(++RHS.getReverse()) {}
115
116 /// Get a reverse iterator to the same node.
117 ///
118 /// Gives a reverse iterator that will dereference (and have a handle) to the
119 /// same node. Converting the endpoint iterators in a range will give a
120 /// different range; for range operations, use the explicit conversions.
121 ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const {
122 if (NodePtr)
123 return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr);
124 return ilist_iterator<OptionsT, !IsReverse, IsConst>();
125 }
126
127 /// Const-cast.
128 ilist_iterator<OptionsT, IsReverse, false> getNonConst() const {
129 if (NodePtr)
130 return ilist_iterator<OptionsT, IsReverse, false>(
131 const_cast<typename ilist_iterator<OptionsT, IsReverse,
132 false>::node_reference>(*NodePtr));
133 return ilist_iterator<OptionsT, IsReverse, false>();
134 }
135
136 // Accessors...
137 reference operator*() const {
138 assert(!NodePtr->isKnownSentinel())((!NodePtr->isKnownSentinel()) ? static_cast<void> (
0) : __assert_fail ("!NodePtr->isKnownSentinel()", "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/ilist_iterator.h"
, 138, __PRETTY_FUNCTION__))
;
139 return *Access::getValuePtr(NodePtr);
140 }
141 pointer operator->() const { return &operator*(); }
142
143 // Comparison operators
144 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
145 return LHS.NodePtr == RHS.NodePtr;
6
Assuming 'LHS.NodePtr' is not equal to 'RHS.NodePtr'
7
Returning zero, which participates in a condition later
146 }
147 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
148 return LHS.NodePtr != RHS.NodePtr;
149 }
150
151 // Increment and decrement operators...
152 ilist_iterator &operator--() {
153 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
154 return *this;
155 }
156 ilist_iterator &operator++() {
157 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
158 return *this;
159 }
160 ilist_iterator operator--(int) {
161 ilist_iterator tmp = *this;
162 --*this;
163 return tmp;
164 }
165 ilist_iterator operator++(int) {
166 ilist_iterator tmp = *this;
167 ++*this;
168 return tmp;
169 }
170
171 /// Get the underlying ilist_node.
172 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
173
174 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
175 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
176};
177
178template <typename From> struct simplify_type;
179
180/// Allow ilist_iterators to convert into pointers to a node automatically when
181/// used by the dyn_cast, cast, isa mechanisms...
182///
183/// FIXME: remove this, since there is no implicit conversion to NodeTy.
184template <class OptionsT, bool IsConst>
185struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
186 using iterator = ilist_iterator<OptionsT, false, IsConst>;
187 using SimpleType = typename iterator::pointer;
188
189 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
190};
191template <class OptionsT, bool IsConst>
192struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
193 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
194
195} // end namespace llvm
196
197#endif // LLVM_ADT_ILIST_ITERATOR_H

/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h

1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
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// This file defines the SmallVector class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_SMALLVECTOR_H
14#define LLVM_ADT_SMALLVECTOR_H
15
16#include "llvm/ADT/iterator_range.h"
17#include "llvm/Support/AlignOf.h"
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/ErrorHandling.h"
20#include "llvm/Support/MathExtras.h"
21#include "llvm/Support/MemAlloc.h"
22#include "llvm/Support/type_traits.h"
23#include <algorithm>
24#include <cassert>
25#include <cstddef>
26#include <cstdlib>
27#include <cstring>
28#include <initializer_list>
29#include <iterator>
30#include <limits>
31#include <memory>
32#include <new>
33#include <type_traits>
34#include <utility>
35
36namespace llvm {
37
38/// This is all the stuff common to all SmallVectors.
39///
40/// The template parameter specifies the type which should be used to hold the
41/// Size and Capacity of the SmallVector, so it can be adjusted.
42/// Using 32 bit size is desirable to shrink the size of the SmallVector.
43/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
44/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
45/// buffering bitcode output - which can exceed 4GB.
46template <class Size_T> class SmallVectorBase {
47protected:
48 void *BeginX;
49 Size_T Size = 0, Capacity;
50
51 /// The maximum value of the Size_T used.
52 static constexpr size_t SizeTypeMax() {
53 return std::numeric_limits<Size_T>::max();
54 }
55
56 SmallVectorBase() = delete;
57 SmallVectorBase(void *FirstEl, size_t TotalCapacity)
58 : BeginX(FirstEl), Capacity(TotalCapacity) {}
59
60 /// This is an implementation of the grow() method which only works
61 /// on POD-like data types and is out of line to reduce code duplication.
62 /// This function will report a fatal error if it cannot increase capacity.
63 void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
64
65 /// Report that MinSize doesn't fit into this vector's size type. Throws
66 /// std::length_error or calls report_fatal_error.
67 LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) static void report_size_overflow(size_t MinSize);
68 /// Report that this vector is already at maximum capacity. Throws
69 /// std::length_error or calls report_fatal_error.
70 LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) static void report_at_maximum_capacity();
71
72public:
73 size_t size() const { return Size; }
74 size_t capacity() const { return Capacity; }
75
76 LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; }
18
Assuming field 'Size' is not equal to 0, which participates in a condition later
19
Returning zero, which participates in a condition later
77
78 /// Set the array size to \p N, which the current array must have enough
79 /// capacity for.
80 ///
81 /// This does not construct or destroy any elements in the vector.
82 ///
83 /// Clients can use this in conjunction with capacity() to write past the end
84 /// of the buffer when they know that more elements are available, and only
85 /// update the size later. This avoids the cost of value initializing elements
86 /// which will only be overwritten.
87 void set_size(size_t N) {
88 assert(N <= capacity())((N <= capacity()) ? static_cast<void> (0) : __assert_fail
("N <= capacity()", "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 88, __PRETTY_FUNCTION__))
;
89 Size = N;
90 }
91};
92
93template <class T>
94using SmallVectorSizeType =
95 typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
96 uint32_t>::type;
97
98/// Figure out the offset of the first element.
99template <class T, typename = void> struct SmallVectorAlignmentAndSize {
100 AlignedCharArrayUnion<SmallVectorBase<SmallVectorSizeType<T>>> Base;
101 AlignedCharArrayUnion<T> FirstEl;
102};
103
104/// This is the part of SmallVectorTemplateBase which does not depend on whether
105/// the type T is a POD. The extra dummy template argument is used by ArrayRef
106/// to avoid unnecessarily requiring T to be complete.
107template <typename T, typename = void>
108class SmallVectorTemplateCommon
109 : public SmallVectorBase<SmallVectorSizeType<T>> {
110 using Base = SmallVectorBase<SmallVectorSizeType<T>>;
111
112 /// Find the address of the first element. For this pointer math to be valid
113 /// with small-size of 0 for T with lots of alignment, it's important that
114 /// SmallVectorStorage is properly-aligned even for small-size of 0.
115 void *getFirstEl() const {
116 return const_cast<void *>(reinterpret_cast<const void *>(
117 reinterpret_cast<const char *>(this) +
118 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl
)
));
119 }
120 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
121
122protected:
123 SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
124
125 void grow_pod(size_t MinSize, size_t TSize) {
126 Base::grow_pod(getFirstEl(), MinSize, TSize);
127 }
128
129 /// Return true if this is a smallvector which has not had dynamic
130 /// memory allocated for it.
131 bool isSmall() const { return this->BeginX == getFirstEl(); }
132
133 /// Put this vector in a state of being small.
134 void resetToSmall() {
135 this->BeginX = getFirstEl();
136 this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
137 }
138
139public:
140 using size_type = size_t;
141 using difference_type = ptrdiff_t;
142 using value_type = T;
143 using iterator = T *;
144 using const_iterator = const T *;
145
146 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
147 using reverse_iterator = std::reverse_iterator<iterator>;
148
149 using reference = T &;
150 using const_reference = const T &;
151 using pointer = T *;
152 using const_pointer = const T *;
153
154 using Base::capacity;
155 using Base::empty;
156 using Base::size;
157
158 // forward iterator creation methods.
159 iterator begin() { return (iterator)this->BeginX; }
160 const_iterator begin() const { return (const_iterator)this->BeginX; }
161 iterator end() { return begin() + size(); }
162 const_iterator end() const { return begin() + size(); }
163
164 // reverse iterator creation methods.
165 reverse_iterator rbegin() { return reverse_iterator(end()); }
166 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
167 reverse_iterator rend() { return reverse_iterator(begin()); }
168 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
169
170 size_type size_in_bytes() const { return size() * sizeof(T); }
171 size_type max_size() const {
172 return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
173 }
174
175 size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
176
177 /// Return a pointer to the vector's buffer, even if empty().
178 pointer data() { return pointer(begin()); }
179 /// Return a pointer to the vector's buffer, even if empty().
180 const_pointer data() const { return const_pointer(begin()); }
181
182 reference operator[](size_type idx) {
183 assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 183, __PRETTY_FUNCTION__))
;
184 return begin()[idx];
185 }
186 const_reference operator[](size_type idx) const {
187 assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 187, __PRETTY_FUNCTION__))
;
188 return begin()[idx];
189 }
190
191 reference front() {
192 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 192, __PRETTY_FUNCTION__))
;
193 return begin()[0];
194 }
195 const_reference front() const {
196 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 196, __PRETTY_FUNCTION__))
;
197 return begin()[0];
198 }
199
200 reference back() {
201 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 201, __PRETTY_FUNCTION__))
;
202 return end()[-1];
203 }
204 const_reference back() const {
205 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 205, __PRETTY_FUNCTION__))
;
206 return end()[-1];
207 }
208};
209
210/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
211/// method implementations that are designed to work with non-trivial T's.
212///
213/// We approximate is_trivially_copyable with trivial move/copy construction and
214/// trivial destruction. While the standard doesn't specify that you're allowed
215/// copy these types with memcpy, there is no way for the type to observe this.
216/// This catches the important case of std::pair<POD, POD>, which is not
217/// trivially assignable.
218template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
219 (is_trivially_move_constructible<T>::value) &&
220 std::is_trivially_destructible<T>::value>
221class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
222protected:
223 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
224
225 static void destroy_range(T *S, T *E) {
226 while (S != E) {
227 --E;
228 E->~T();
229 }
230 }
231
232 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
233 /// constructing elements as needed.
234 template<typename It1, typename It2>
235 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
236 std::uninitialized_copy(std::make_move_iterator(I),
237 std::make_move_iterator(E), Dest);
238 }
239
240 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
241 /// constructing elements as needed.
242 template<typename It1, typename It2>
243 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
244 std::uninitialized_copy(I, E, Dest);
245 }
246
247 /// Grow the allocated memory (without initializing new elements), doubling
248 /// the size of the allocated memory. Guarantees space for at least one more
249 /// element, or MinSize more elements if specified.
250 void grow(size_t MinSize = 0);
251
252public:
253 void push_back(const T &Elt) {
254 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
255 this->grow();
256 ::new ((void*) this->end()) T(Elt);
257 this->set_size(this->size() + 1);
258 }
259
260 void push_back(T &&Elt) {
261 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
262 this->grow();
263 ::new ((void*) this->end()) T(::std::move(Elt));
264 this->set_size(this->size() + 1);
265 }
266
267 void pop_back() {
268 this->set_size(this->size() - 1);
269 this->end()->~T();
270 }
271};
272
273// Define this out-of-line to dissuade the C++ compiler from inlining it.
274template <typename T, bool TriviallyCopyable>
275void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
276 // Ensure we can fit the new capacity.
277 // This is only going to be applicable when the capacity is 32 bit.
278 if (MinSize > this->SizeTypeMax())
279 this->report_size_overflow(MinSize);
280
281 // Ensure we can meet the guarantee of space for at least one more element.
282 // The above check alone will not catch the case where grow is called with a
283 // default MinSize of 0, but the current capacity cannot be increased.
284 // This is only going to be applicable when the capacity is 32 bit.
285 if (this->capacity() == this->SizeTypeMax())
286 this->report_at_maximum_capacity();
287
288 // Always grow, even from zero.
289 size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
290 NewCapacity = std::min(std::max(NewCapacity, MinSize), this->SizeTypeMax());
291 T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
292
293 // Move the elements over.
294 this->uninitialized_move(this->begin(), this->end(), NewElts);
295
296 // Destroy the original elements.
297 destroy_range(this->begin(), this->end());
298
299 // If this wasn't grown from the inline copy, deallocate the old space.
300 if (!this->isSmall())
301 free(this->begin());
302
303 this->BeginX = NewElts;
304 this->Capacity = NewCapacity;
305}
306
307/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
308/// method implementations that are designed to work with trivially copyable
309/// T's. This allows using memcpy in place of copy/move construction and
310/// skipping destruction.
311template <typename T>
312class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
313protected:
314 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
315
316 // No need to do a destroy loop for POD's.
317 static void destroy_range(T *, T *) {}
318
319 /// Move the range [I, E) onto the uninitialized memory
320 /// starting with "Dest", constructing elements into it as needed.
321 template<typename It1, typename It2>
322 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
323 // Just do a copy.
324 uninitialized_copy(I, E, Dest);
325 }
326
327 /// Copy the range [I, E) onto the uninitialized memory
328 /// starting with "Dest", constructing elements into it as needed.
329 template<typename It1, typename It2>
330 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
331 // Arbitrary iterator types; just use the basic implementation.
332 std::uninitialized_copy(I, E, Dest);
333 }
334
335 /// Copy the range [I, E) onto the uninitialized memory
336 /// starting with "Dest", constructing elements into it as needed.
337 template <typename T1, typename T2>
338 static void uninitialized_copy(
339 T1 *I, T1 *E, T2 *Dest,
340 std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
341 T2>::value> * = nullptr) {
342 // Use memcpy for PODs iterated by pointers (which includes SmallVector
343 // iterators): std::uninitialized_copy optimizes to memmove, but we can
344 // use memcpy here. Note that I and E are iterators and thus might be
345 // invalid for memcpy if they are equal.
346 if (I != E)
347 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
348 }
349
350 /// Double the size of the allocated memory, guaranteeing space for at
351 /// least one more element or MinSize if specified.
352 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
353
354public:
355 void push_back(const T &Elt) {
356 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
357 this->grow();
358 memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
359 this->set_size(this->size() + 1);
360 }
361
362 void pop_back() { this->set_size(this->size() - 1); }
363};
364
365/// This class consists of common code factored out of the SmallVector class to
366/// reduce code duplication based on the SmallVector 'N' template parameter.
367template <typename T>
368class SmallVectorImpl : public SmallVectorTemplateBase<T> {
369 using SuperClass = SmallVectorTemplateBase<T>;
370
371public:
372 using iterator = typename SuperClass::iterator;
373 using const_iterator = typename SuperClass::const_iterator;
374 using reference = typename SuperClass::reference;
375 using size_type = typename SuperClass::size_type;
376
377protected:
378 // Default ctor - Initialize to empty.
379 explicit SmallVectorImpl(unsigned N)
380 : SmallVectorTemplateBase<T>(N) {}
381
382public:
383 SmallVectorImpl(const SmallVectorImpl &) = delete;
384
385 ~SmallVectorImpl() {
386 // Subclass has already destructed this vector's elements.
387 // If this wasn't grown from the inline copy, deallocate the old space.
388 if (!this->isSmall())
389 free(this->begin());
390 }
391
392 void clear() {
393 this->destroy_range(this->begin(), this->end());
394 this->Size = 0;
395 }
396
397 void resize(size_type N) {
398 if (N < this->size()) {
399 this->destroy_range(this->begin()+N, this->end());
400 this->set_size(N);
401 } else if (N > this->size()) {
402 if (this->capacity() < N)
403 this->grow(N);
404 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
405 new (&*I) T();
406 this->set_size(N);
407 }
408 }
409
410 void resize(size_type N, const T &NV) {
411 if (N < this->size()) {
412 this->destroy_range(this->begin()+N, this->end());
413 this->set_size(N);
414 } else if (N > this->size()) {
415 if (this->capacity() < N)
416 this->grow(N);
417 std::uninitialized_fill(this->end(), this->begin()+N, NV);
418 this->set_size(N);
419 }
420 }
421
422 void reserve(size_type N) {
423 if (this->capacity() < N)
424 this->grow(N);
425 }
426
427 LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
428 T Result = ::std::move(this->back());
429 this->pop_back();
430 return Result;
431 }
432
433 void swap(SmallVectorImpl &RHS);
434
435 /// Add the specified range to the end of the SmallVector.
436 template <typename in_iter,
437 typename = std::enable_if_t<std::is_convertible<
438 typename std::iterator_traits<in_iter>::iterator_category,
439 std::input_iterator_tag>::value>>
440 void append(in_iter in_start, in_iter in_end) {
441 size_type NumInputs = std::distance(in_start, in_end);
442 if (NumInputs > this->capacity() - this->size())
443 this->grow(this->size()+NumInputs);
444
445 this->uninitialized_copy(in_start, in_end, this->end());
446 this->set_size(this->size() + NumInputs);
447 }
448
449 /// Append \p NumInputs copies of \p Elt to the end.
450 void append(size_type NumInputs, const T &Elt) {
451 if (NumInputs > this->capacity() - this->size())
452 this->grow(this->size()+NumInputs);
453
454 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
455 this->set_size(this->size() + NumInputs);
456 }
457
458 void append(std::initializer_list<T> IL) {
459 append(IL.begin(), IL.end());
460 }
461
462 // FIXME: Consider assigning over existing elements, rather than clearing &
463 // re-initializing them - for all assign(...) variants.
464
465 void assign(size_type NumElts, const T &Elt) {
466 clear();
467 if (this->capacity() < NumElts)
468 this->grow(NumElts);
469 this->set_size(NumElts);
470 std::uninitialized_fill(this->begin(), this->end(), Elt);
471 }
472
473 template <typename in_iter,
474 typename = std::enable_if_t<std::is_convertible<
475 typename std::iterator_traits<in_iter>::iterator_category,
476 std::input_iterator_tag>::value>>
477 void assign(in_iter in_start, in_iter in_end) {
478 clear();
479 append(in_start, in_end);
480 }
481
482 void assign(std::initializer_list<T> IL) {
483 clear();
484 append(IL);
485 }
486
487 iterator erase(const_iterator CI) {
488 // Just cast away constness because this is a non-const member function.
489 iterator I = const_cast<iterator>(CI);
490
491 assert(I >= this->begin() && "Iterator to erase is out of bounds.")((I >= this->begin() && "Iterator to erase is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Iterator to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 491, __PRETTY_FUNCTION__))
;
492 assert(I < this->end() && "Erasing at past-the-end iterator.")((I < this->end() && "Erasing at past-the-end iterator."
) ? static_cast<void> (0) : __assert_fail ("I < this->end() && \"Erasing at past-the-end iterator.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 492, __PRETTY_FUNCTION__))
;
493
494 iterator N = I;
495 // Shift all elts down one.
496 std::move(I+1, this->end(), I);
497 // Drop the last elt.
498 this->pop_back();
499 return(N);
500 }
501
502 iterator erase(const_iterator CS, const_iterator CE) {
503 // Just cast away constness because this is a non-const member function.
504 iterator S = const_cast<iterator>(CS);
505 iterator E = const_cast<iterator>(CE);
506
507 assert(S >= this->begin() && "Range to erase is out of bounds.")((S >= this->begin() && "Range to erase is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("S >= this->begin() && \"Range to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 507, __PRETTY_FUNCTION__))
;
508 assert(S <= E && "Trying to erase invalid range.")((S <= E && "Trying to erase invalid range.") ? static_cast
<void> (0) : __assert_fail ("S <= E && \"Trying to erase invalid range.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 508, __PRETTY_FUNCTION__))
;
509 assert(E <= this->end() && "Trying to erase past the end.")((E <= this->end() && "Trying to erase past the end."
) ? static_cast<void> (0) : __assert_fail ("E <= this->end() && \"Trying to erase past the end.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 509, __PRETTY_FUNCTION__))
;
510
511 iterator N = S;
512 // Shift all elts down.
513 iterator I = std::move(E, this->end(), S);
514 // Drop the last elts.
515 this->destroy_range(I, this->end());
516 this->set_size(I - this->begin());
517 return(N);
518 }
519
520 iterator insert(iterator I, T &&Elt) {
521 if (I == this->end()) { // Important special case for empty vector.
522 this->push_back(::std::move(Elt));
523 return this->end()-1;
524 }
525
526 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 526, __PRETTY_FUNCTION__))
;
527 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 527, __PRETTY_FUNCTION__))
;
528
529 if (this->size() >= this->capacity()) {
530 size_t EltNo = I-this->begin();
531 this->grow();
532 I = this->begin()+EltNo;
533 }
534
535 ::new ((void*) this->end()) T(::std::move(this->back()));
536 // Push everything else over.
537 std::move_backward(I, this->end()-1, this->end());
538 this->set_size(this->size() + 1);
539
540 // If we just moved the element we're inserting, be sure to update
541 // the reference.
542 T *EltPtr = &Elt;
543 if (I <= EltPtr && EltPtr < this->end())
544 ++EltPtr;
545
546 *I = ::std::move(*EltPtr);
547 return I;
548 }
549
550 iterator insert(iterator I, const T &Elt) {
551 if (I == this->end()) { // Important special case for empty vector.
552 this->push_back(Elt);
553 return this->end()-1;
554 }
555
556 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 556, __PRETTY_FUNCTION__))
;
557 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 557, __PRETTY_FUNCTION__))
;
558
559 if (this->size() >= this->capacity()) {
560 size_t EltNo = I-this->begin();
561 this->grow();
562 I = this->begin()+EltNo;
563 }
564 ::new ((void*) this->end()) T(std::move(this->back()));
565 // Push everything else over.
566 std::move_backward(I, this->end()-1, this->end());
567 this->set_size(this->size() + 1);
568
569 // If we just moved the element we're inserting, be sure to update
570 // the reference.
571 const T *EltPtr = &Elt;
572 if (I <= EltPtr && EltPtr < this->end())
573 ++EltPtr;
574
575 *I = *EltPtr;
576 return I;
577 }
578
579 iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
580 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
581 size_t InsertElt = I - this->begin();
582
583 if (I == this->end()) { // Important special case for empty vector.
584 append(NumToInsert, Elt);
585 return this->begin()+InsertElt;
586 }
587
588 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 588, __PRETTY_FUNCTION__))
;
589 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 589, __PRETTY_FUNCTION__))
;
590
591 // Ensure there is enough space.
592 reserve(this->size() + NumToInsert);
593
594 // Uninvalidate the iterator.
595 I = this->begin()+InsertElt;
596
597 // If there are more elements between the insertion point and the end of the
598 // range than there are being inserted, we can use a simple approach to
599 // insertion. Since we already reserved space, we know that this won't
600 // reallocate the vector.
601 if (size_t(this->end()-I) >= NumToInsert) {
602 T *OldEnd = this->end();
603 append(std::move_iterator<iterator>(this->end() - NumToInsert),
604 std::move_iterator<iterator>(this->end()));
605
606 // Copy the existing elements that get replaced.
607 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
608
609 std::fill_n(I, NumToInsert, Elt);
610 return I;
611 }
612
613 // Otherwise, we're inserting more elements than exist already, and we're
614 // not inserting at the end.
615
616 // Move over the elements that we're about to overwrite.
617 T *OldEnd = this->end();
618 this->set_size(this->size() + NumToInsert);
619 size_t NumOverwritten = OldEnd-I;
620 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
621
622 // Replace the overwritten part.
623 std::fill_n(I, NumOverwritten, Elt);
624
625 // Insert the non-overwritten middle part.
626 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
627 return I;
628 }
629
630 template <typename ItTy,
631 typename = std::enable_if_t<std::is_convertible<
632 typename std::iterator_traits<ItTy>::iterator_category,
633 std::input_iterator_tag>::value>>
634 iterator insert(iterator I, ItTy From, ItTy To) {
635 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
636 size_t InsertElt = I - this->begin();
637
638 if (I == this->end()) { // Important special case for empty vector.
639 append(From, To);
640 return this->begin()+InsertElt;
641 }
642
643 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 643, __PRETTY_FUNCTION__))
;
644 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include/llvm/ADT/SmallVector.h"
, 644, __PRETTY_FUNCTION__))
;
645
646 size_t NumToInsert = std::distance(From, To);
647
648 // Ensure there is enough space.
649 reserve(this->size() + NumToInsert);
650
651 // Uninvalidate the iterator.
652 I = this->begin()+InsertElt;
653
654 // If there are more elements between the insertion point and the end of the
655 // range than there are being inserted, we can use a simple approach to
656 // insertion. Since we already reserved space, we know that this won't
657 // reallocate the vector.
658 if (size_t(this->end()-I) >= NumToInsert) {
659 T *OldEnd = this->end();
660 append(std::move_iterator<iterator>(this->end() - NumToInsert),
661 std::move_iterator<iterator>(this->end()));
662
663 // Copy the existing elements that get replaced.
664 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
665
666 std::copy(From, To, I);
667 return I;
668 }
669
670 // Otherwise, we're inserting more elements than exist already, and we're
671 // not inserting at the end.
672
673 // Move over the elements that we're about to overwrite.
674 T *OldEnd = this->end();
675 this->set_size(this->size() + NumToInsert);
676 size_t NumOverwritten = OldEnd-I;
677 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
678
679 // Replace the overwritten part.
680 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
681 *J = *From;
682 ++J; ++From;
683 }
684
685 // Insert the non-overwritten middle part.
686 this->uninitialized_copy(From, To, OldEnd);
687 return I;
688 }
689
690 void insert(iterator I, std::initializer_list<T> IL) {
691 insert(I, IL.begin(), IL.end());
692 }
693
694 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
695 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
696 this->grow();
697 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
698 this->set_size(this->size() + 1);
699 return this->back();
700 }
701
702 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
703
704 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
705
706 bool operator==(const SmallVectorImpl &RHS) const {
707 if (this->size() != RHS.size()) return false;
708 return std::equal(this->begin(), this->end(), RHS.begin());
709 }
710 bool operator!=(const SmallVectorImpl &RHS) const {
711 return !(*this == RHS);
712 }
713
714 bool operator<(const SmallVectorImpl &RHS) const {
715 return std::lexicographical_compare(this->begin(), this->end(),
716 RHS.begin(), RHS.end());
717 }
718};
719
720template <typename T>
721void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
722 if (this == &RHS) return;
723
724 // We can only avoid copying elements if neither vector is small.
725 if (!this->isSmall() && !RHS.isSmall()) {
726 std::swap(this->BeginX, RHS.BeginX);
727 std::swap(this->Size, RHS.Size);
728 std::swap(this->Capacity, RHS.Capacity);
729 return;
730 }
731 if (RHS.size() > this->capacity())
732 this->grow(RHS.size());
733 if (this->size() > RHS.capacity())
734 RHS.grow(this->size());
735
736 // Swap the shared elements.
737 size_t NumShared = this->size();
738 if (NumShared > RHS.size()) NumShared = RHS.size();
739 for (size_type i = 0; i != NumShared; ++i)
740 std::swap((*this)[i], RHS[i]);
741
742 // Copy over the extra elts.
743 if (this->size() > RHS.size()) {
744 size_t EltDiff = this->size() - RHS.size();
745 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
746 RHS.set_size(RHS.size() + EltDiff);
747 this->destroy_range(this->begin()+NumShared, this->end());
748 this->set_size(NumShared);
749 } else if (RHS.size() > this->size()) {
750 size_t EltDiff = RHS.size() - this->size();
751 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
752 this->set_size(this->size() + EltDiff);
753 this->destroy_range(RHS.begin()+NumShared, RHS.end());
754 RHS.set_size(NumShared);
755 }
756}
757
758template <typename T>
759SmallVectorImpl<T> &SmallVectorImpl<T>::
760 operator=(const SmallVectorImpl<T> &RHS) {
761 // Avoid self-assignment.
762 if (this == &RHS) return *this;
763
764 // If we already have sufficient space, assign the common elements, then
765 // destroy any excess.
766 size_t RHSSize = RHS.size();
767 size_t CurSize = this->size();
768 if (CurSize >= RHSSize) {
769 // Assign common elements.
770 iterator NewEnd;
771 if (RHSSize)
772 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
773 else
774 NewEnd = this->begin();
775
776 // Destroy excess elements.
777 this->destroy_range(NewEnd, this->end());
778
779 // Trim.
780 this->set_size(RHSSize);
781 return *this;
782 }
783
784 // If we have to grow to have enough elements, destroy the current elements.
785 // This allows us to avoid copying them during the grow.
786 // FIXME: don't do this if they're efficiently moveable.
787 if (this->capacity() < RHSSize) {
788 // Destroy current elements.
789 this->destroy_range(this->begin(), this->end());
790 this->set_size(0);
791 CurSize = 0;
792 this->grow(RHSSize);
793 } else if (CurSize) {
794 // Otherwise, use assignment for the already-constructed elements.
795 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
796 }
797
798 // Copy construct the new elements in place.
799 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
800 this->begin()+CurSize);
801
802 // Set end.
803 this->set_size(RHSSize);
804 return *this;
805}
806
807template <typename T>
808SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
809 // Avoid self-assignment.
810 if (this == &RHS) return *this;
811
812 // If the RHS isn't small, clear this vector and then steal its buffer.
813 if (!RHS.isSmall()) {
814 this->destroy_range(this->begin(), this->end());
815 if (!this->isSmall()) free(this->begin());
816 this->BeginX = RHS.BeginX;
817 this->Size = RHS.Size;
818 this->Capacity = RHS.Capacity;
819 RHS.resetToSmall();
820 return *this;
821 }
822
823 // If we already have sufficient space, assign the common elements, then
824 // destroy any excess.
825 size_t RHSSize = RHS.size();
826 size_t CurSize = this->size();
827 if (CurSize >= RHSSize) {
828 // Assign common elements.
829 iterator NewEnd = this->begin();
830 if (RHSSize)
831 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
832
833 // Destroy excess elements and trim the bounds.
834 this->destroy_range(NewEnd, this->end());
835 this->set_size(RHSSize);
836
837 // Clear the RHS.
838 RHS.clear();
839
840 return *this;
841 }
842
843 // If we have to grow to have enough elements, destroy the current elements.
844 // This allows us to avoid copying them during the grow.
845 // FIXME: this may not actually make any sense if we can efficiently move
846 // elements.
847 if (this->capacity() < RHSSize) {
848 // Destroy current elements.
849 this->destroy_range(this->begin(), this->end());
850 this->set_size(0);
851 CurSize = 0;
852 this->grow(RHSSize);
853 } else if (CurSize) {
854 // Otherwise, use assignment for the already-constructed elements.
855 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
856 }
857
858 // Move-construct the new elements in place.
859 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
860 this->begin()+CurSize);
861
862 // Set end.
863 this->set_size(RHSSize);
864
865 RHS.clear();
866 return *this;
867}
868
869/// Storage for the SmallVector elements. This is specialized for the N=0 case
870/// to avoid allocating unnecessary storage.
871template <typename T, unsigned N>
872struct SmallVectorStorage {
873 AlignedCharArrayUnion<T> InlineElts[N];
874};
875
876/// We need the storage to be properly aligned even for small-size of 0 so that
877/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
878/// well-defined.
879template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
880
881/// This is a 'vector' (really, a variable-sized array), optimized
882/// for the case when the array is small. It contains some number of elements
883/// in-place, which allows it to avoid heap allocation when the actual number of
884/// elements is below that threshold. This allows normal "small" cases to be
885/// fast without losing generality for large inputs.
886///
887/// Note that this does not attempt to be exception safe.
888///
889template <typename T, unsigned N>
890class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
891 SmallVectorStorage<T, N> {
892public:
893 SmallVector() : SmallVectorImpl<T>(N) {}
894
895 ~SmallVector() {
896 // Destroy the constructed elements in the vector.
897 this->destroy_range(this->begin(), this->end());
898 }
899
900 explicit SmallVector(size_t Size, const T &Value = T())
901 : SmallVectorImpl<T>(N) {
902 this->assign(Size, Value);
903 }
904
905 template <typename ItTy,
906 typename = std::enable_if_t<std::is_convertible<
907 typename std::iterator_traits<ItTy>::iterator_category,
908 std::input_iterator_tag>::value>>
909 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
910 this->append(S, E);
911 }
912
913 template <typename RangeTy>
914 explicit SmallVector(const iterator_range<RangeTy> &R)
915 : SmallVectorImpl<T>(N) {
916 this->append(R.begin(), R.end());
917 }
918
919 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
920 this->assign(IL);
921 }
922
923 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
924 if (!RHS.empty())
925 SmallVectorImpl<T>::operator=(RHS);
926 }
927
928 const SmallVector &operator=(const SmallVector &RHS) {
929 SmallVectorImpl<T>::operator=(RHS);
930 return *this;
931 }
932
933 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
934 if (!RHS.empty())
935 SmallVectorImpl<T>::operator=(::std::move(RHS));
936 }
937
938 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
939 if (!RHS.empty())
940 SmallVectorImpl<T>::operator=(::std::move(RHS));
941 }
942
943 const SmallVector &operator=(SmallVector &&RHS) {
944 SmallVectorImpl<T>::operator=(::std::move(RHS));
945 return *this;
946 }
947
948 const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
949 SmallVectorImpl<T>::operator=(::std::move(RHS));
950 return *this;
951 }
952
953 const SmallVector &operator=(std::initializer_list<T> IL) {
954 this->assign(IL);
955 return *this;
956 }
957};
958
959template <typename T, unsigned N>
960inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
961 return X.capacity_in_bytes();
962}
963
964/// Given a range of type R, iterate the entire range and return a
965/// SmallVector with elements of the vector. This is useful, for example,
966/// when you want to iterate a range and then sort the results.
967template <unsigned Size, typename R>
968SmallVector<typename std::remove_const<typename std::remove_reference<
969 decltype(*std::begin(std::declval<R &>()))>::type>::type,
970 Size>
971to_vector(R &&Range) {
972 return {std::begin(Range), std::end(Range)};
973}
974
975} // end namespace llvm
976
977namespace std {
978
979 /// Implement std::swap in terms of SmallVector swap.
980 template<typename T>
981 inline void
982 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
983 LHS.swap(RHS);
984 }
985
986 /// Implement std::swap in terms of SmallVector swap.
987 template<typename T, unsigned N>
988 inline void
989 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
990 LHS.swap(RHS);
991 }
992
993} // end namespace std
994
995#endif // LLVM_ADT_SMALLVECTOR_H