Bug Summary

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

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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-11/lib/clang/11.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-11~++20200309111110+2c36c23f347/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c++ /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/BranchFolding.cpp

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/BranchFolding.cpp

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

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h

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

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/ilist_iterator.h

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

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/SmallVector.h

1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the SmallVector class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_SMALLVECTOR_H
14#define LLVM_ADT_SMALLVECTOR_H
15
16#include "llvm/ADT/iterator_range.h"
17#include "llvm/Support/AlignOf.h"
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/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, which participates in a condition later
20.1
Field 'Size' is not equal to 0, which participates in a condition later
20.1
Field 'Size' is not equal to 0, which participates in a condition later
20.1
Field 'Size' is not equal to 0, which participates in a condition later
; }
17
Assuming field 'Size' is not equal to 0, which participates in a condition later
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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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 std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
288 T2>::value> * = 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 = std::enable_if_t<std::is_convertible<
385 typename std::iterator_traits<in_iter>::iterator_category,
386 std::input_iterator_tag>::value>>
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 = std::enable_if_t<std::is_convertible<
422 typename std::iterator_traits<in_iter>::iterator_category,
423 std::input_iterator_tag>::value>>
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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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 = std::enable_if_t<std::is_convertible<
579 typename std::iterator_traits<ItTy>::iterator_category,
580 std::input_iterator_tag>::value>>
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-11~++20200309111110+2c36c23f347/llvm/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-11~++20200309111110+2c36c23f347/llvm/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 = std::enable_if_t<std::is_convertible<
853 typename std::iterator_traits<ItTy>::iterator_category,
854 std::input_iterator_tag>::value>>
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/// Given a range of type R, iterate the entire range and return a
911/// SmallVector with elements of the vector. This is useful, for example,
912/// when you want to iterate a range and then sort the results.
913template <unsigned Size, typename R>
914SmallVector<typename std::remove_const<typename std::remove_reference<
915 decltype(*std::begin(std::declval<R &>()))>::type>::type,
916 Size>
917to_vector(R &&Range) {
918 return {std::begin(Range), std::end(Range)};
919}
920
921} // end namespace llvm
922
923namespace std {
924
925 /// Implement std::swap in terms of SmallVector swap.
926 template<typename T>
927 inline void
928 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
929 LHS.swap(RHS);
930 }
931
932 /// Implement std::swap in terms of SmallVector swap.
933 template<typename T, unsigned N>
934 inline void
935 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
936 LHS.swap(RHS);
937 }
938
939} // end namespace std
940
941#endif // LLVM_ADT_SMALLVECTOR_H