Bug Summary

File:llvm/lib/CodeGen/BranchFolding.cpp
Warning:line 1490, 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~++20201129111111+e987fbdd85d/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-12~++20201129111111+e987fbdd85d/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-12~++20201129111111+e987fbdd85d/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20201129111111+e987fbdd85d/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~++20201129111111+e987fbdd85d/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20201129111111+e987fbdd85d=. -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-11-29-190409-37574-1 -x c++ /build/llvm-toolchain-snapshot-12~++20201129111111+e987fbdd85d/llvm/lib/CodeGen/BranchFolding.cpp

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

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