Bug Summary

File:lib/CodeGen/BranchFolding.cpp
Warning:line 1314, column 39
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~svn373517/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-10~svn373517/lib/CodeGen -I /build/llvm-toolchain-snapshot-10~svn373517/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn373517/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-10/lib/clang/10.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-10~svn373517/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn373517=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-10-02-234743-9763-1 -x c++ /build/llvm-toolchain-snapshot-10~svn373517/lib/CodeGen/BranchFolding.cpp

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

/build/llvm-toolchain-snapshot-10~svn373517/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-10~svn373517/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-10~svn373517/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-10~svn373517/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-10~svn373517/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-10~svn373517/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-10~svn373517/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-10~svn373517/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-10~svn373517/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-10~svn373517/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 typename std::enable_if<std::is_convertible<OtherTy *, Ty *>::value,
156 void *>::type = 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-10~svn373517/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(
92 const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS,
93 typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr)
94 : NodePtr(RHS.NodePtr) {}
95
96 // This is templated so that we can allow assigning to a const iterator from
97 // a nonconst iterator...
98 template <bool RHSIsConst>
99 typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type
100 operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) {
101 NodePtr = RHS.NodePtr;
102 return *this;
103 }
104
105 /// Explicit conversion between forward/reverse iterators.
106 ///
107 /// Translate between forward and reverse iterators without changing range
108 /// boundaries. The resulting iterator will dereference (and have a handle)
109 /// to the previous node, which is somewhat unexpected; but converting the
110 /// two endpoints in a range will give the same range in reverse.
111 ///
112 /// This matches std::reverse_iterator conversions.
113 explicit ilist_iterator(
114 const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS)
115 : ilist_iterator(++RHS.getReverse()) {}
116
117 /// Get a reverse iterator to the same node.
118 ///
119 /// Gives a reverse iterator that will dereference (and have a handle) to the
120 /// same node. Converting the endpoint iterators in a range will give a
121 /// different range; for range operations, use the explicit conversions.
122 ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const {
123 if (NodePtr)
124 return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr);
125 return ilist_iterator<OptionsT, !IsReverse, IsConst>();
126 }
127
128 /// Const-cast.
129 ilist_iterator<OptionsT, IsReverse, false> getNonConst() const {
130 if (NodePtr)
131 return ilist_iterator<OptionsT, IsReverse, false>(
132 const_cast<typename ilist_iterator<OptionsT, IsReverse,
133 false>::node_reference>(*NodePtr));
134 return ilist_iterator<OptionsT, IsReverse, false>();
135 }
136
137 // Accessors...
138 reference operator*() const {
139 assert(!NodePtr->isKnownSentinel())((!NodePtr->isKnownSentinel()) ? static_cast<void> (
0) : __assert_fail ("!NodePtr->isKnownSentinel()", "/build/llvm-toolchain-snapshot-10~svn373517/include/llvm/ADT/ilist_iterator.h"
, 139, __PRETTY_FUNCTION__))
;
140 return *Access::getValuePtr(NodePtr);
141 }
142 pointer operator->() const { return &operator*(); }
143
144 // Comparison operators
145 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
146 return LHS.NodePtr == RHS.NodePtr;
6
Assuming 'LHS.NodePtr' is not equal to 'RHS.NodePtr'
7
Returning zero, which participates in a condition later
31
Assuming 'LHS.NodePtr' is equal to 'RHS.NodePtr'
32
Returning the value 1, which participates in a condition later
147 }
148 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
149 return LHS.NodePtr != RHS.NodePtr;
150 }
151
152 // Increment and decrement operators...
153 ilist_iterator &operator--() {
154 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
155 return *this;
156 }
157 ilist_iterator &operator++() {
158 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
159 return *this;
160 }
161 ilist_iterator operator--(int) {
162 ilist_iterator tmp = *this;
163 --*this;
164 return tmp;
165 }
166 ilist_iterator operator++(int) {
167 ilist_iterator tmp = *this;
168 ++*this;
169 return tmp;
170 }
171
172 /// Get the underlying ilist_node.
173 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
174
175 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
176 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
177};
178
179template <typename From> struct simplify_type;
180
181/// Allow ilist_iterators to convert into pointers to a node automatically when
182/// used by the dyn_cast, cast, isa mechanisms...
183///
184/// FIXME: remove this, since there is no implicit conversion to NodeTy.
185template <class OptionsT, bool IsConst>
186struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
187 using iterator = ilist_iterator<OptionsT, false, IsConst>;
188 using SimpleType = typename iterator::pointer;
189
190 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
191};
192template <class OptionsT, bool IsConst>
193struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
194 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
195
196} // end namespace llvm
197
198#endif // LLVM_ADT_ILIST_ITERATOR_H

/build/llvm-toolchain-snapshot-10~svn373517/include/llvm/ADT/SmallVector.h

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