/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/MachineBasicBlock.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- 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 | | // Collect the sequence of machine instructions for a basic block. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
14 | | #include "llvm/ADT/SmallPtrSet.h" |
15 | | #include "llvm/CodeGen/LiveIntervals.h" |
16 | | #include "llvm/CodeGen/LiveVariables.h" |
17 | | #include "llvm/CodeGen/MachineDominators.h" |
18 | | #include "llvm/CodeGen/MachineFunction.h" |
19 | | #include "llvm/CodeGen/MachineInstrBuilder.h" |
20 | | #include "llvm/CodeGen/MachineLoopInfo.h" |
21 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
22 | | #include "llvm/CodeGen/SlotIndexes.h" |
23 | | #include "llvm/CodeGen/TargetInstrInfo.h" |
24 | | #include "llvm/CodeGen/TargetRegisterInfo.h" |
25 | | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
26 | | #include "llvm/Config/llvm-config.h" |
27 | | #include "llvm/IR/BasicBlock.h" |
28 | | #include "llvm/IR/DataLayout.h" |
29 | | #include "llvm/IR/DebugInfoMetadata.h" |
30 | | #include "llvm/IR/ModuleSlotTracker.h" |
31 | | #include "llvm/MC/MCAsmInfo.h" |
32 | | #include "llvm/MC/MCContext.h" |
33 | | #include "llvm/Support/DataTypes.h" |
34 | | #include "llvm/Support/Debug.h" |
35 | | #include "llvm/Support/raw_ostream.h" |
36 | | #include "llvm/Target/TargetMachine.h" |
37 | | #include <algorithm> |
38 | | using namespace llvm; |
39 | | |
40 | | #define DEBUG_TYPE "codegen" |
41 | | |
42 | | MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B) |
43 | 3.78M | : BB(B), Number(-1), xParent(&MF) { |
44 | 3.78M | Insts.Parent = this; |
45 | 3.78M | if (B) |
46 | 3.28M | IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight(); |
47 | 3.78M | } |
48 | | |
49 | 3.78M | MachineBasicBlock::~MachineBasicBlock() { |
50 | 3.78M | } |
51 | | |
52 | | /// Return the MCSymbol for this basic block. |
53 | 2.91M | MCSymbol *MachineBasicBlock::getSymbol() const { |
54 | 2.91M | if (!CachedMCSymbol) { |
55 | 1.19M | const MachineFunction *MF = getParent(); |
56 | 1.19M | MCContext &Ctx = MF->getContext(); |
57 | 1.19M | auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix(); |
58 | 1.19M | assert(getNumber() >= 0 && "cannot get label for unreachable MBB"); |
59 | 1.19M | CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" + |
60 | 1.19M | Twine(MF->getFunctionNumber()) + |
61 | 1.19M | "_" + Twine(getNumber())); |
62 | 1.19M | } |
63 | 2.91M | |
64 | 2.91M | return CachedMCSymbol; |
65 | 2.91M | } |
66 | | |
67 | | |
68 | 0 | raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { |
69 | 0 | MBB.print(OS); |
70 | 0 | return OS; |
71 | 0 | } |
72 | | |
73 | 170k | Printable llvm::printMBBReference(const MachineBasicBlock &MBB) { |
74 | 170k | return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); }); |
75 | 170k | } |
76 | | |
77 | | /// When an MBB is added to an MF, we need to update the parent pointer of the |
78 | | /// MBB, the MBB numbering, and any instructions in the MBB to be on the right |
79 | | /// operand list for registers. |
80 | | /// |
81 | | /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it |
82 | | /// gets the next available unique MBB number. If it is removed from a |
83 | | /// MachineFunction, it goes back to being #-1. |
84 | | void ilist_callback_traits<MachineBasicBlock>::addNodeToList( |
85 | 3.78M | MachineBasicBlock *N) { |
86 | 3.78M | MachineFunction &MF = *N->getParent(); |
87 | 3.78M | N->Number = MF.addToMBBNumbering(N); |
88 | 3.78M | |
89 | 3.78M | // Make sure the instructions have their operands in the reginfo lists. |
90 | 3.78M | MachineRegisterInfo &RegInfo = MF.getRegInfo(); |
91 | 3.78M | for (MachineBasicBlock::instr_iterator |
92 | 3.78M | I = N->instr_begin(), E = N->instr_end(); I != E; ++I94 ) |
93 | 94 | I->AddRegOperandsToUseLists(RegInfo); |
94 | 3.78M | } |
95 | | |
96 | | void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList( |
97 | 3.78M | MachineBasicBlock *N) { |
98 | 3.78M | N->getParent()->removeFromMBBNumbering(N->Number); |
99 | 3.78M | N->Number = -1; |
100 | 3.78M | } |
101 | | |
102 | | /// When we add an instruction to a basic block list, we update its parent |
103 | | /// pointer and add its operands from reg use/def lists if appropriate. |
104 | 66.5M | void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) { |
105 | 66.5M | assert(!N->getParent() && "machine instruction already in a basic block"); |
106 | 66.5M | N->setParent(Parent); |
107 | 66.5M | |
108 | 66.5M | // Add the instruction's register operands to their corresponding |
109 | 66.5M | // use/def lists. |
110 | 66.5M | MachineFunction *MF = Parent->getParent(); |
111 | 66.5M | N->AddRegOperandsToUseLists(MF->getRegInfo()); |
112 | 66.5M | MF->handleInsertion(*N); |
113 | 66.5M | } |
114 | | |
115 | | /// When we remove an instruction from a basic block list, we update its parent |
116 | | /// pointer and remove its operands from reg use/def lists if appropriate. |
117 | 41.6M | void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) { |
118 | 41.6M | assert(N->getParent() && "machine instruction not in a basic block"); |
119 | 41.6M | |
120 | 41.6M | // Remove from the use/def lists. |
121 | 41.6M | if (MachineFunction *MF = N->getMF()) { |
122 | 41.6M | MF->handleRemoval(*N); |
123 | 41.6M | N->RemoveRegOperandsFromUseLists(MF->getRegInfo()); |
124 | 41.6M | } |
125 | 41.6M | |
126 | 41.6M | N->setParent(nullptr); |
127 | 41.6M | } |
128 | | |
129 | | /// When moving a range of instructions from one MBB list to another, we need to |
130 | | /// update the parent pointers and the use/def lists. |
131 | | void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList, |
132 | | instr_iterator First, |
133 | 5.20M | instr_iterator Last) { |
134 | 5.20M | assert(Parent->getParent() == FromList.Parent->getParent() && |
135 | 5.20M | "cannot transfer MachineInstrs between MachineFunctions"); |
136 | 5.20M | |
137 | 5.20M | // If it's within the same BB, there's nothing to do. |
138 | 5.20M | if (this == &FromList) |
139 | 1.56M | return; |
140 | 3.63M | |
141 | 3.63M | assert(Parent != FromList.Parent && "Two lists have the same parent?"); |
142 | 3.63M | |
143 | 3.63M | // If splicing between two blocks within the same function, just update the |
144 | 3.63M | // parent pointers. |
145 | 10.3M | for (; First != Last; ++First6.72M ) |
146 | 6.72M | First->setParent(Parent); |
147 | 3.63M | } |
148 | | |
149 | 40.9M | void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) { |
150 | 40.9M | assert(!MI->getParent() && "MI is still in a block!"); |
151 | 40.9M | Parent->getParent()->DeleteMachineInstr(MI); |
152 | 40.9M | } |
153 | | |
154 | 219k | MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() { |
155 | 219k | instr_iterator I = instr_begin(), E = instr_end(); |
156 | 268k | while (I != E && I->isPHI()249k ) |
157 | 49.5k | ++I; |
158 | 219k | assert((I == E || !I->isInsideBundle()) && |
159 | 219k | "First non-phi MI cannot be inside a bundle!"); |
160 | 219k | return I; |
161 | 219k | } |
162 | | |
163 | | MachineBasicBlock::iterator |
164 | 416k | MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) { |
165 | 416k | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
166 | 416k | |
167 | 416k | iterator E = end(); |
168 | 1.05M | while (I != E && (1.04M I->isPHI()1.04M || I->isPosition()415k || |
169 | 1.04M | TII->isBasicBlockPrologue(*I)407k )) |
170 | 642k | ++I; |
171 | 416k | // FIXME: This needs to change if we wish to bundle labels |
172 | 416k | // inside the bundle. |
173 | 416k | assert((I == E || !I->isInsideBundle()) && |
174 | 416k | "First non-phi / non-label instruction is inside a bundle!"); |
175 | 416k | return I; |
176 | 416k | } |
177 | | |
178 | | MachineBasicBlock::iterator |
179 | 27.7M | MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) { |
180 | 27.7M | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
181 | 27.7M | |
182 | 27.7M | iterator E = end(); |
183 | 35.9M | while (I != E && (35.9M I->isPHI()35.9M || I->isPosition()35.9M || I->isDebugInstr()35.7M || |
184 | 35.9M | TII->isBasicBlockPrologue(*I)27.7M )) |
185 | 8.14M | ++I; |
186 | 27.7M | // FIXME: This needs to change if we wish to bundle labels / dbg_values |
187 | 27.7M | // inside the bundle. |
188 | 27.7M | assert((I == E || !I->isInsideBundle()) && |
189 | 27.7M | "First non-phi / non-label / non-debug " |
190 | 27.7M | "instruction is inside a bundle!"); |
191 | 27.7M | return I; |
192 | 27.7M | } |
193 | | |
194 | 27.1M | MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { |
195 | 27.1M | iterator B = begin(), E = end(), I = E; |
196 | 53.0M | while (I != B && (51.3M (--I)->isTerminator()51.3M || I->isDebugInstr()25.4M )) |
197 | 25.8M | ; /*noop */ |
198 | 52.5M | while (I != E && !I->isTerminator()48.3M ) |
199 | 25.4M | ++I; |
200 | 27.1M | return I; |
201 | 27.1M | } |
202 | | |
203 | 179k | MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() { |
204 | 179k | instr_iterator B = instr_begin(), E = instr_end(), I = E; |
205 | 412k | while (I != B && (405k (--I)->isTerminator()405k || I->isDebugInstr()172k )) |
206 | 232k | ; /*noop */ |
207 | 352k | while (I != E && !I->isTerminator()348k ) |
208 | 172k | ++I; |
209 | 179k | return I; |
210 | 179k | } |
211 | | |
212 | 17.5M | MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() { |
213 | 17.5M | // Skip over begin-of-block dbg_value instructions. |
214 | 17.5M | return skipDebugInstructionsForward(begin(), end()); |
215 | 17.5M | } |
216 | | |
217 | 75.5M | MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() { |
218 | 75.5M | // Skip over end-of-block dbg_value instructions. |
219 | 75.5M | instr_iterator B = instr_begin(), I = instr_end(); |
220 | 75.5M | while (I != B) { |
221 | 75.0M | --I; |
222 | 75.0M | // Return instruction that starts a bundle. |
223 | 75.0M | if (I->isDebugInstr() || I->isInsideBundle()75.0M ) |
224 | 3.50k | continue; |
225 | 75.0M | return I; |
226 | 75.0M | } |
227 | 75.5M | // The block is all debug values. |
228 | 75.5M | return end()531k ; |
229 | 75.5M | } |
230 | | |
231 | 6.95M | bool MachineBasicBlock::hasEHPadSuccessor() const { |
232 | 17.8M | for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I10.9M ) |
233 | 11.0M | if ((*I)->isEHPad()) |
234 | 96.1k | return true; |
235 | 6.95M | return false6.85M ; |
236 | 6.95M | } |
237 | | |
238 | | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
239 | | LLVM_DUMP_METHOD void MachineBasicBlock::dump() const { |
240 | | print(dbgs()); |
241 | | } |
242 | | #endif |
243 | | |
244 | 447k | bool MachineBasicBlock::isLegalToHoistInto() const { |
245 | 447k | if (isReturnBlock() || hasEHPadSuccessor()446k ) |
246 | 1.40k | return false; |
247 | 445k | return true; |
248 | 445k | } |
249 | | |
250 | 3.93k | StringRef MachineBasicBlock::getName() const { |
251 | 3.93k | if (const BasicBlock *LBB = getBasicBlock()) |
252 | 3.72k | return LBB->getName(); |
253 | 208 | else |
254 | 208 | return StringRef("", 0); |
255 | 3.93k | } |
256 | | |
257 | | /// Return a hopefully unique identifier for this block. |
258 | 0 | std::string MachineBasicBlock::getFullName() const { |
259 | 0 | std::string Name; |
260 | 0 | if (getParent()) |
261 | 0 | Name = (getParent()->getName() + ":").str(); |
262 | 0 | if (getBasicBlock()) |
263 | 0 | Name += getBasicBlock()->getName(); |
264 | 0 | else |
265 | 0 | Name += ("BB" + Twine(getNumber())).str(); |
266 | 0 | return Name; |
267 | 0 | } |
268 | | |
269 | | void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes, |
270 | 0 | bool IsStandalone) const { |
271 | 0 | const MachineFunction *MF = getParent(); |
272 | 0 | if (!MF) { |
273 | 0 | OS << "Can't print out MachineBasicBlock because parent MachineFunction" |
274 | 0 | << " is null\n"; |
275 | 0 | return; |
276 | 0 | } |
277 | 0 | const Function &F = MF->getFunction(); |
278 | 0 | const Module *M = F.getParent(); |
279 | 0 | ModuleSlotTracker MST(M); |
280 | 0 | MST.incorporateFunction(F); |
281 | 0 | print(OS, MST, Indexes, IsStandalone); |
282 | 0 | } |
283 | | |
284 | | void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST, |
285 | | const SlotIndexes *Indexes, |
286 | 31.7k | bool IsStandalone) const { |
287 | 31.7k | const MachineFunction *MF = getParent(); |
288 | 31.7k | if (!MF) { |
289 | 0 | OS << "Can't print out MachineBasicBlock because parent MachineFunction" |
290 | 0 | << " is null\n"; |
291 | 0 | return; |
292 | 0 | } |
293 | 31.7k | |
294 | 31.7k | if (Indexes) |
295 | 3.23k | OS << Indexes->getMBBStartIdx(this) << '\t'; |
296 | 31.7k | |
297 | 31.7k | OS << "bb." << getNumber(); |
298 | 31.7k | bool HasAttributes = false; |
299 | 31.7k | if (const auto *BB = getBasicBlock()) { |
300 | 31.6k | if (BB->hasName()) { |
301 | 31.0k | OS << "." << BB->getName(); |
302 | 31.0k | } else { |
303 | 549 | HasAttributes = true; |
304 | 549 | OS << " ("; |
305 | 549 | int Slot = MST.getLocalSlot(BB); |
306 | 549 | if (Slot == -1) |
307 | 0 | OS << "<ir-block badref>"; |
308 | 549 | else |
309 | 549 | OS << (Twine("%ir-block.") + Twine(Slot)).str(); |
310 | 549 | } |
311 | 31.6k | } |
312 | 31.7k | |
313 | 31.7k | if (hasAddressTaken()) { |
314 | 2 | OS << (HasAttributes ? ", "0 : " ("); |
315 | 2 | OS << "address-taken"; |
316 | 2 | HasAttributes = true; |
317 | 2 | } |
318 | 31.7k | if (isEHPad()) { |
319 | 4 | OS << (HasAttributes ? ", "0 : " ("); |
320 | 4 | OS << "landing-pad"; |
321 | 4 | HasAttributes = true; |
322 | 4 | } |
323 | 31.7k | if (getAlignment()) { |
324 | 0 | OS << (HasAttributes ? ", " : " ("); |
325 | 0 | OS << "align " << getAlignment(); |
326 | 0 | HasAttributes = true; |
327 | 0 | } |
328 | 31.7k | if (HasAttributes) |
329 | 555 | OS << ")"; |
330 | 31.7k | OS << ":\n"; |
331 | 31.7k | |
332 | 31.7k | const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); |
333 | 31.7k | const MachineRegisterInfo &MRI = MF->getRegInfo(); |
334 | 31.7k | const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo(); |
335 | 31.7k | bool HasLineAttributes = false; |
336 | 31.7k | |
337 | 31.7k | // Print the preds of this block according to the CFG. |
338 | 31.7k | if (!pred_empty() && IsStandalone28.7k ) { |
339 | 28.7k | if (Indexes) OS << '\t'2.90k ; |
340 | 28.7k | // Don't indent(2), align with previous line attributes. |
341 | 28.7k | OS << "; predecessors: "; |
342 | 68.8k | for (auto I = pred_begin(), E = pred_end(); I != E; ++I40.0k ) { |
343 | 40.0k | if (I != pred_begin()) |
344 | 11.2k | OS << ", "; |
345 | 40.0k | OS << printMBBReference(**I); |
346 | 40.0k | } |
347 | 28.7k | OS << '\n'; |
348 | 28.7k | HasLineAttributes = true; |
349 | 28.7k | } |
350 | 31.7k | |
351 | 31.7k | if (!succ_empty()) { |
352 | 18.1k | if (Indexes) OS << '\t'1.82k ; |
353 | 18.1k | // Print the successors |
354 | 18.1k | OS.indent(2) << "successors: "; |
355 | 58.2k | for (auto I = succ_begin(), E = succ_end(); I != E; ++I40.0k ) { |
356 | 40.0k | if (I != succ_begin()) |
357 | 21.8k | OS << ", "; |
358 | 40.0k | OS << printMBBReference(**I); |
359 | 40.0k | if (!Probs.empty()) |
360 | 40.0k | OS << '(' |
361 | 40.0k | << format("0x%08" PRIx32, getSuccProbability(I).getNumerator()) |
362 | 40.0k | << ')'; |
363 | 40.0k | } |
364 | 18.1k | if (!Probs.empty() && IsStandalone) { |
365 | 18.1k | // Print human readable probabilities as comments. |
366 | 18.1k | OS << "; "; |
367 | 58.2k | for (auto I = succ_begin(), E = succ_end(); I != E; ++I40.0k ) { |
368 | 40.0k | const BranchProbability &BP = getSuccProbability(I); |
369 | 40.0k | if (I != succ_begin()) |
370 | 21.8k | OS << ", "; |
371 | 40.0k | OS << printMBBReference(**I) << '(' |
372 | 40.0k | << format("%.2f%%", |
373 | 40.0k | rint(((double)BP.getNumerator() / BP.getDenominator()) * |
374 | 40.0k | 100.0 * 100.0) / |
375 | 40.0k | 100.0) |
376 | 40.0k | << ')'; |
377 | 40.0k | } |
378 | 18.1k | } |
379 | 18.1k | |
380 | 18.1k | OS << '\n'; |
381 | 18.1k | HasLineAttributes = true; |
382 | 18.1k | } |
383 | 31.7k | |
384 | 31.7k | if (!livein_empty() && MRI.tracksLiveness()11.2k ) { |
385 | 11.0k | if (Indexes) OS << '\t'815 ; |
386 | 11.0k | OS.indent(2) << "liveins: "; |
387 | 11.0k | |
388 | 11.0k | bool First = true; |
389 | 15.3k | for (const auto &LI : liveins()) { |
390 | 15.3k | if (!First) |
391 | 4.29k | OS << ", "; |
392 | 15.3k | First = false; |
393 | 15.3k | OS << printReg(LI.PhysReg, TRI); |
394 | 15.3k | if (!LI.LaneMask.all()) |
395 | 0 | OS << ":0x" << PrintLaneMask(LI.LaneMask); |
396 | 15.3k | } |
397 | 11.0k | HasLineAttributes = true; |
398 | 11.0k | } |
399 | 31.7k | |
400 | 31.7k | if (HasLineAttributes) |
401 | 31.3k | OS << '\n'; |
402 | 31.7k | |
403 | 31.7k | bool IsInBundle = false; |
404 | 134k | for (const MachineInstr &MI : instrs()) { |
405 | 134k | if (Indexes) { |
406 | 12.8k | if (Indexes->hasIndex(MI)) |
407 | 12.6k | OS << Indexes->getInstructionIndex(MI); |
408 | 12.8k | OS << '\t'; |
409 | 12.8k | } |
410 | 134k | |
411 | 134k | if (IsInBundle && !MI.isInsideBundle()10 ) { |
412 | 2 | OS.indent(2) << "}\n"; |
413 | 2 | IsInBundle = false; |
414 | 2 | } |
415 | 134k | |
416 | 134k | OS.indent(IsInBundle ? 48 : 2134k ); |
417 | 134k | MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false, |
418 | 134k | /*AddNewLine=*/false, &TII); |
419 | 134k | |
420 | 134k | if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)134k ) { |
421 | 2 | OS << " {"; |
422 | 2 | IsInBundle = true; |
423 | 2 | } |
424 | 134k | OS << '\n'; |
425 | 134k | } |
426 | 31.7k | |
427 | 31.7k | if (IsInBundle) |
428 | 0 | OS.indent(2) << "}\n"; |
429 | 31.7k | |
430 | 31.7k | if (IrrLoopHeaderWeight && IsStandalone0 ) { |
431 | 0 | if (Indexes) OS << '\t'; |
432 | 0 | OS.indent(2) << "; Irreducible loop header weight: " |
433 | 0 | << IrrLoopHeaderWeight.getValue() << '\n'; |
434 | 0 | } |
435 | 31.7k | } |
436 | | |
437 | | void MachineBasicBlock::printAsOperand(raw_ostream &OS, |
438 | 170k | bool /*PrintType*/) const { |
439 | 170k | OS << "%bb." << getNumber(); |
440 | 170k | } |
441 | | |
442 | 247k | void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) { |
443 | 247k | LiveInVector::iterator I = find_if( |
444 | 766k | LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); |
445 | 247k | if (I == LiveIns.end()) |
446 | 140k | return; |
447 | 106k | |
448 | 106k | I->LaneMask &= ~LaneMask; |
449 | 106k | if (I->LaneMask.none()) |
450 | 106k | LiveIns.erase(I); |
451 | 106k | } |
452 | | |
453 | | MachineBasicBlock::livein_iterator |
454 | 4.88k | MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) { |
455 | 4.88k | // Get non-const version of iterator. |
456 | 4.88k | LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin()); |
457 | 4.88k | return LiveIns.erase(LI); |
458 | 4.88k | } |
459 | | |
460 | 2.23M | bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const { |
461 | 2.23M | livein_iterator I = find_if( |
462 | 9.84M | LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); |
463 | 2.23M | return I != livein_end() && (I->LaneMask & LaneMask).any()1.16M ; |
464 | 2.23M | } |
465 | | |
466 | 3.06M | void MachineBasicBlock::sortUniqueLiveIns() { |
467 | 3.06M | llvm::sort(LiveIns, |
468 | 34.0M | [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) { |
469 | 34.0M | return LI0.PhysReg < LI1.PhysReg; |
470 | 34.0M | }); |
471 | 3.06M | // Liveins are sorted by physreg now we can merge their lanemasks. |
472 | 3.06M | LiveInVector::const_iterator I = LiveIns.begin(); |
473 | 3.06M | LiveInVector::const_iterator J; |
474 | 3.06M | LiveInVector::iterator Out = LiveIns.begin(); |
475 | 17.6M | for (; I != LiveIns.end(); ++Out, I = J14.6M ) { |
476 | 14.6M | unsigned PhysReg = I->PhysReg; |
477 | 14.6M | LaneBitmask LaneMask = I->LaneMask; |
478 | 14.6M | for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg11.8M ; ++J710 ) |
479 | 710 | LaneMask |= J->LaneMask; |
480 | 14.6M | Out->PhysReg = PhysReg; |
481 | 14.6M | Out->LaneMask = LaneMask; |
482 | 14.6M | } |
483 | 3.06M | LiveIns.erase(Out, LiveIns.end()); |
484 | 3.06M | } |
485 | | |
486 | | unsigned |
487 | 6.86k | MachineBasicBlock::addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC) { |
488 | 6.86k | assert(getParent() && "MBB must be inserted in function"); |
489 | 6.86k | assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg"); |
490 | 6.86k | assert(RC && "Register class is required"); |
491 | 6.86k | assert((isEHPad() || this == &getParent()->front()) && |
492 | 6.86k | "Only the entry block and landing pads can have physreg live ins"); |
493 | 6.86k | |
494 | 6.86k | bool LiveIn = isLiveIn(PhysReg); |
495 | 6.86k | iterator I = SkipPHIsAndLabels(begin()), E = end(); |
496 | 6.86k | MachineRegisterInfo &MRI = getParent()->getRegInfo(); |
497 | 6.86k | const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo(); |
498 | 6.86k | |
499 | 6.86k | // Look for an existing copy. |
500 | 6.86k | if (LiveIn) |
501 | 0 | for (;I != E && I->isCopy(); ++I) |
502 | 0 | if (I->getOperand(1).getReg() == PhysReg) { |
503 | 0 | unsigned VirtReg = I->getOperand(0).getReg(); |
504 | 0 | if (!MRI.constrainRegClass(VirtReg, RC)) |
505 | 0 | llvm_unreachable("Incompatible live-in register class."); |
506 | 0 | return VirtReg; |
507 | 0 | } |
508 | 6.86k | |
509 | 6.86k | // No luck, create a virtual register. |
510 | 6.86k | unsigned VirtReg = MRI.createVirtualRegister(RC); |
511 | 6.86k | BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg) |
512 | 6.86k | .addReg(PhysReg, RegState::Kill); |
513 | 6.86k | if (!LiveIn) |
514 | 6.86k | addLiveIn(PhysReg); |
515 | 6.86k | return VirtReg; |
516 | 6.86k | } |
517 | | |
518 | 15.3k | void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { |
519 | 15.3k | getParent()->splice(NewAfter->getIterator(), getIterator()); |
520 | 15.3k | } |
521 | | |
522 | 280k | void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { |
523 | 280k | getParent()->splice(++NewBefore->getIterator(), getIterator()); |
524 | 280k | } |
525 | | |
526 | 2.65M | void MachineBasicBlock::updateTerminator() { |
527 | 2.65M | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
528 | 2.65M | // A block with no successors has no concerns with fall-through edges. |
529 | 2.65M | if (this->succ_empty()) |
530 | 39.6k | return; |
531 | 2.61M | |
532 | 2.61M | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
533 | 2.61M | SmallVector<MachineOperand, 4> Cond; |
534 | 2.61M | DebugLoc DL = findBranchDebugLoc(); |
535 | 2.61M | bool B = TII->analyzeBranch(*this, TBB, FBB, Cond); |
536 | 2.61M | (void) B; |
537 | 2.61M | assert(!B && "UpdateTerminators requires analyzable predecessors!"); |
538 | 2.61M | if (Cond.empty()) { |
539 | 802k | if (TBB) { |
540 | 240k | // The block has an unconditional branch. If its successor is now its |
541 | 240k | // layout successor, delete the branch. |
542 | 240k | if (isLayoutSuccessor(TBB)) |
543 | 70.8k | TII->removeBranch(*this); |
544 | 561k | } else { |
545 | 561k | // The block has an unconditional fallthrough. If its successor is not its |
546 | 561k | // layout successor, insert a branch. First we have to locate the only |
547 | 561k | // non-landing-pad successor, as that is the fallthrough block. |
548 | 1.16M | for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI599k ) { |
549 | 599k | if ((*SI)->isEHPad()) |
550 | 37.7k | continue; |
551 | 561k | assert(!TBB && "Found more than one non-landing-pad successor!"); |
552 | 561k | TBB = *SI; |
553 | 561k | } |
554 | 561k | |
555 | 561k | // If there is no non-landing-pad successor, the block has no fall-through |
556 | 561k | // edges to be concerned with. |
557 | 561k | if (!TBB) |
558 | 0 | return; |
559 | 561k | |
560 | 561k | // Finally update the unconditional successor to be reached via a branch |
561 | 561k | // if it would not be reached by fallthrough. |
562 | 561k | if (!isLayoutSuccessor(TBB)) |
563 | 67.6k | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
564 | 561k | } |
565 | 802k | return; |
566 | 1.81M | } |
567 | 1.81M | |
568 | 1.81M | if (FBB) { |
569 | 230k | // The block has a non-fallthrough conditional branch. If one of its |
570 | 230k | // successors is its layout successor, rewrite it to a fallthrough |
571 | 230k | // conditional branch. |
572 | 230k | if (isLayoutSuccessor(TBB)) { |
573 | 128k | if (TII->reverseBranchCondition(Cond)) |
574 | 4 | return; |
575 | 128k | TII->removeBranch(*this); |
576 | 128k | TII->insertBranch(*this, FBB, nullptr, Cond, DL); |
577 | 128k | } else if (101k isLayoutSuccessor(FBB)101k ) { |
578 | 52.4k | TII->removeBranch(*this); |
579 | 52.4k | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
580 | 52.4k | } |
581 | 230k | return230k ; |
582 | 1.58M | } |
583 | 1.58M | |
584 | 1.58M | // Walk through the successors and find the successor which is not a landing |
585 | 1.58M | // pad and is not the conditional branch destination (in TBB) as the |
586 | 1.58M | // fallthrough successor. |
587 | 1.58M | MachineBasicBlock *FallthroughBB = nullptr; |
588 | 4.75M | for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI3.16M ) { |
589 | 3.16M | if ((*SI)->isEHPad() || *SI == TBB) |
590 | 1.58M | continue; |
591 | 1.58M | assert(!FallthroughBB && "Found more than one fallthrough successor."); |
592 | 1.58M | FallthroughBB = *SI; |
593 | 1.58M | } |
594 | 1.58M | |
595 | 1.58M | if (!FallthroughBB) { |
596 | 10 | if (canFallThrough()) { |
597 | 9 | // We fallthrough to the same basic block as the conditional jump targets. |
598 | 9 | // Remove the conditional jump, leaving unconditional fallthrough. |
599 | 9 | // FIXME: This does not seem like a reasonable pattern to support, but it |
600 | 9 | // has been seen in the wild coming out of degenerate ARM test cases. |
601 | 9 | TII->removeBranch(*this); |
602 | 9 | |
603 | 9 | // Finally update the unconditional successor to be reached via a branch if |
604 | 9 | // it would not be reached by fallthrough. |
605 | 9 | if (!isLayoutSuccessor(TBB)) |
606 | 0 | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
607 | 9 | return; |
608 | 9 | } |
609 | 1 | |
610 | 1 | // We enter here iff exactly one successor is TBB which cannot fallthrough |
611 | 1 | // and the rest successors if any are EHPads. In this case, we need to |
612 | 1 | // change the conditional branch into unconditional branch. |
613 | 1 | TII->removeBranch(*this); |
614 | 1 | Cond.clear(); |
615 | 1 | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
616 | 1 | return; |
617 | 1 | } |
618 | 1.58M | |
619 | 1.58M | // The block has a fallthrough conditional branch. |
620 | 1.58M | if (isLayoutSuccessor(TBB)) { |
621 | 344k | if (TII->reverseBranchCondition(Cond)) { |
622 | 22 | // We can't reverse the condition, add an unconditional branch. |
623 | 22 | Cond.clear(); |
624 | 22 | TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL); |
625 | 22 | return; |
626 | 22 | } |
627 | 344k | TII->removeBranch(*this); |
628 | 344k | TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL); |
629 | 1.23M | } else if (!isLayoutSuccessor(FallthroughBB)) { |
630 | 128k | TII->removeBranch(*this); |
631 | 128k | TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL); |
632 | 128k | } |
633 | 1.58M | } |
634 | | |
635 | 0 | void MachineBasicBlock::validateSuccProbs() const { |
636 | | #ifndef NDEBUG |
637 | | int64_t Sum = 0; |
638 | | for (auto Prob : Probs) |
639 | | Sum += Prob.getNumerator(); |
640 | | // Due to precision issue, we assume that the sum of probabilities is one if |
641 | | // the difference between the sum of their numerators and the denominator is |
642 | | // no greater than the number of successors. |
643 | | assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <= |
644 | | Probs.size() && |
645 | | "The sum of successors's probabilities exceeds one."); |
646 | | #endif // NDEBUG |
647 | | } |
648 | | |
649 | | void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, |
650 | 5.17M | BranchProbability Prob) { |
651 | 5.17M | // Probability list is either empty (if successor list isn't empty, this means |
652 | 5.17M | // disabled optimization) or has the same size as successor list. |
653 | 5.17M | if (!(Probs.empty() && !Successors.empty()3.44M )) |
654 | 5.17M | Probs.push_back(Prob); |
655 | 5.17M | Successors.push_back(Succ); |
656 | 5.17M | Succ->addPredecessor(this); |
657 | 5.17M | } |
658 | | |
659 | 82.2k | void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) { |
660 | 82.2k | // We need to make sure probability list is either empty or has the same size |
661 | 82.2k | // of successor list. When this function is called, we can safely delete all |
662 | 82.2k | // probability in the list. |
663 | 82.2k | Probs.clear(); |
664 | 82.2k | Successors.push_back(Succ); |
665 | 82.2k | Succ->addPredecessor(this); |
666 | 82.2k | } |
667 | | |
668 | | void MachineBasicBlock::splitSuccessor(MachineBasicBlock *Old, |
669 | | MachineBasicBlock *New, |
670 | 0 | bool NormalizeSuccProbs) { |
671 | 0 | succ_iterator OldI = llvm::find(successors(), Old); |
672 | 0 | assert(OldI != succ_end() && "Old is not a successor of this block!"); |
673 | 0 | assert(llvm::find(successors(), New) == succ_end() && |
674 | 0 | "New is already a successor of this block!"); |
675 | 0 |
|
676 | 0 | // Add a new successor with equal probability as the original one. Note |
677 | 0 | // that we directly copy the probability using the iterator rather than |
678 | 0 | // getting a potentially synthetic probability computed when unknown. This |
679 | 0 | // preserves the probabilities as-is and then we can renormalize them and |
680 | 0 | // query them effectively afterward. |
681 | 0 | addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown() |
682 | 0 | : *getProbabilityIterator(OldI)); |
683 | 0 | if (NormalizeSuccProbs) |
684 | 0 | normalizeSuccProbs(); |
685 | 0 | } |
686 | | |
687 | | void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ, |
688 | 407k | bool NormalizeSuccProbs) { |
689 | 407k | succ_iterator I = find(Successors, Succ); |
690 | 407k | removeSuccessor(I, NormalizeSuccProbs); |
691 | 407k | } |
692 | | |
693 | | MachineBasicBlock::succ_iterator |
694 | 1.04M | MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) { |
695 | 1.04M | assert(I != Successors.end() && "Not a current successor!"); |
696 | 1.04M | |
697 | 1.04M | // If probability list is empty it means we don't use it (disabled |
698 | 1.04M | // optimization). |
699 | 1.04M | if (!Probs.empty()) { |
700 | 1.04M | probability_iterator WI = getProbabilityIterator(I); |
701 | 1.04M | Probs.erase(WI); |
702 | 1.04M | if (NormalizeSuccProbs) |
703 | 17.5k | normalizeSuccProbs(); |
704 | 1.04M | } |
705 | 1.04M | |
706 | 1.04M | (*I)->removePredecessor(this); |
707 | 1.04M | return Successors.erase(I); |
708 | 1.04M | } |
709 | | |
710 | | void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, |
711 | 505k | MachineBasicBlock *New) { |
712 | 505k | if (Old == New) |
713 | 0 | return; |
714 | 505k | |
715 | 505k | succ_iterator E = succ_end(); |
716 | 505k | succ_iterator NewI = E; |
717 | 505k | succ_iterator OldI = E; |
718 | 1.52M | for (succ_iterator I = succ_begin(); I != E; ++I1.02M ) { |
719 | 1.02M | if (*I == Old) { |
720 | 505k | OldI = I; |
721 | 505k | if (NewI != E) |
722 | 617 | break; |
723 | 1.02M | } |
724 | 1.02M | if (*I == New) { |
725 | 1.25k | NewI = I; |
726 | 1.25k | if (OldI != E) |
727 | 636 | break; |
728 | 1.25k | } |
729 | 1.02M | } |
730 | 505k | assert(OldI != E && "Old is not a successor of this block"); |
731 | 505k | |
732 | 505k | // If New isn't already a successor, let it take Old's place. |
733 | 505k | if (NewI == E) { |
734 | 504k | Old->removePredecessor(this); |
735 | 504k | New->addPredecessor(this); |
736 | 504k | *OldI = New; |
737 | 504k | return; |
738 | 504k | } |
739 | 1.25k | |
740 | 1.25k | // New is already a successor. |
741 | 1.25k | // Update its probability instead of adding a duplicate edge. |
742 | 1.25k | if (!Probs.empty()) { |
743 | 905 | auto ProbIter = getProbabilityIterator(NewI); |
744 | 905 | if (!ProbIter->isUnknown()) |
745 | 888 | *ProbIter += *getProbabilityIterator(OldI); |
746 | 905 | } |
747 | 1.25k | removeSuccessor(OldI); |
748 | 1.25k | } |
749 | | |
750 | | void MachineBasicBlock::copySuccessor(MachineBasicBlock *Orig, |
751 | 10 | succ_iterator I) { |
752 | 10 | if (Orig->Probs.empty()) |
753 | 0 | addSuccessor(*I, Orig->getSuccProbability(I)); |
754 | 10 | else |
755 | 10 | addSuccessorWithoutProb(*I); |
756 | 10 | } |
757 | | |
758 | 5.76M | void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) { |
759 | 5.76M | Predecessors.push_back(Pred); |
760 | 5.76M | } |
761 | | |
762 | 1.54M | void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) { |
763 | 1.54M | pred_iterator I = find(Predecessors, Pred); |
764 | 1.54M | assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); |
765 | 1.54M | Predecessors.erase(I); |
766 | 1.54M | } |
767 | | |
768 | 133k | void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) { |
769 | 133k | if (this == FromMBB) |
770 | 0 | return; |
771 | 133k | |
772 | 260k | while (133k !FromMBB->succ_empty()) { |
773 | 127k | MachineBasicBlock *Succ = *FromMBB->succ_begin(); |
774 | 127k | |
775 | 127k | // If probability list is empty it means we don't use it (disabled optimization). |
776 | 127k | if (!FromMBB->Probs.empty()) { |
777 | 126k | auto Prob = *FromMBB->Probs.begin(); |
778 | 126k | addSuccessor(Succ, Prob); |
779 | 126k | } else |
780 | 1.22k | addSuccessorWithoutProb(Succ); |
781 | 127k | |
782 | 127k | FromMBB->removeSuccessor(Succ); |
783 | 127k | } |
784 | 133k | } |
785 | | |
786 | | void |
787 | 13.1k | MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) { |
788 | 13.1k | if (this == FromMBB) |
789 | 0 | return; |
790 | 13.1k | |
791 | 23.4k | while (13.1k !FromMBB->succ_empty()) { |
792 | 10.2k | MachineBasicBlock *Succ = *FromMBB->succ_begin(); |
793 | 10.2k | if (!FromMBB->Probs.empty()) { |
794 | 10.0k | auto Prob = *FromMBB->Probs.begin(); |
795 | 10.0k | addSuccessor(Succ, Prob); |
796 | 10.0k | } else |
797 | 226 | addSuccessorWithoutProb(Succ); |
798 | 10.2k | FromMBB->removeSuccessor(Succ); |
799 | 10.2k | |
800 | 10.2k | // Fix up any PHI nodes in the successor. |
801 | 10.2k | for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(), |
802 | 20.6k | ME = Succ->instr_end(); MI != ME && MI->isPHI()20.4k ; ++MI10.4k ) |
803 | 40.6k | for (unsigned i = 2, e = MI->getNumOperands()+1; 10.4k i != e; i += 230.1k ) { |
804 | 30.1k | MachineOperand &MO = MI->getOperand(i); |
805 | 30.1k | if (MO.getMBB() == FromMBB) |
806 | 10.4k | MO.setMBB(this); |
807 | 30.1k | } |
808 | 10.2k | } |
809 | 13.1k | normalizeSuccProbs(); |
810 | 13.1k | } |
811 | | |
812 | 1.28M | bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const { |
813 | 1.28M | return is_contained(predecessors(), MBB); |
814 | 1.28M | } |
815 | | |
816 | 31.5M | bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { |
817 | 31.5M | return is_contained(successors(), MBB); |
818 | 31.5M | } |
819 | | |
820 | 21.2M | bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { |
821 | 21.2M | MachineFunction::const_iterator I(this); |
822 | 21.2M | return std::next(I) == MachineFunction::const_iterator(MBB); |
823 | 21.2M | } |
824 | | |
825 | 16.9M | MachineBasicBlock *MachineBasicBlock::getFallThrough() { |
826 | 16.9M | MachineFunction::iterator Fallthrough = getIterator(); |
827 | 16.9M | ++Fallthrough; |
828 | 16.9M | // If FallthroughBlock is off the end of the function, it can't fall through. |
829 | 16.9M | if (Fallthrough == getParent()->end()) |
830 | 1.30M | return nullptr; |
831 | 15.6M | |
832 | 15.6M | // If FallthroughBlock isn't a successor, no fallthrough is possible. |
833 | 15.6M | if (!isSuccessor(&*Fallthrough)) |
834 | 4.20M | return nullptr; |
835 | 11.4M | |
836 | 11.4M | // Analyze the branches, if any, at the end of the block. |
837 | 11.4M | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
838 | 11.4M | SmallVector<MachineOperand, 4> Cond; |
839 | 11.4M | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
840 | 11.4M | if (TII->analyzeBranch(*this, TBB, FBB, Cond)) { |
841 | 83.9k | // If we couldn't analyze the branch, examine the last instruction. |
842 | 83.9k | // If the block doesn't end in a known control barrier, assume fallthrough |
843 | 83.9k | // is possible. The isPredicated check is needed because this code can be |
844 | 83.9k | // called during IfConversion, where an instruction which is normally a |
845 | 83.9k | // Barrier is predicated and thus no longer an actual control barrier. |
846 | 83.9k | return (empty() || !back().isBarrier() || TII->isPredicated(back())79.3k ) |
847 | 83.9k | ? &*Fallthrough4.98k |
848 | 83.9k | : nullptr78.9k ; |
849 | 83.9k | } |
850 | 11.3M | |
851 | 11.3M | // If there is no branch, control always falls through. |
852 | 11.3M | if (!TBB) return &*Fallthrough3.24M ; |
853 | 8.09M | |
854 | 8.09M | // If there is some explicit branch to the fallthrough block, it can obviously |
855 | 8.09M | // reach, even though the branch should get folded to fall through implicitly. |
856 | 8.09M | if (MachineFunction::iterator(TBB) == Fallthrough || |
857 | 8.09M | MachineFunction::iterator(FBB) == Fallthrough7.95M ) |
858 | 798k | return &*Fallthrough; |
859 | 7.29M | |
860 | 7.29M | // If it's an unconditional branch to some block not the fall through, it |
861 | 7.29M | // doesn't fall through. |
862 | 7.29M | if (Cond.empty()) return nullptr13.5k ; |
863 | 7.28M | |
864 | 7.28M | // Otherwise, if it is conditional and has no explicit false block, it falls |
865 | 7.28M | // through. |
866 | 7.28M | return (FBB == nullptr) ? &*Fallthrough : nullptr0 ; |
867 | 7.28M | } |
868 | | |
869 | 16.9M | bool MachineBasicBlock::canFallThrough() { |
870 | 16.9M | return getFallThrough() != nullptr; |
871 | 16.9M | } |
872 | | |
873 | | MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, |
874 | 254k | Pass &P) { |
875 | 254k | if (!canSplitCriticalEdge(Succ)) |
876 | 2.21k | return nullptr; |
877 | 252k | |
878 | 252k | MachineFunction *MF = getParent(); |
879 | 252k | DebugLoc DL; // FIXME: this is nowhere |
880 | 252k | |
881 | 252k | MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); |
882 | 252k | MF->insert(std::next(MachineFunction::iterator(this)), NMBB); |
883 | 252k | LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this) |
884 | 252k | << " -- " << printMBBReference(*NMBB) << " -- " |
885 | 252k | << printMBBReference(*Succ) << '\n'); |
886 | 252k | |
887 | 252k | LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>(); |
888 | 252k | SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>(); |
889 | 252k | if (LIS) |
890 | 0 | LIS->insertMBBInMaps(NMBB); |
891 | 252k | else if (Indexes) |
892 | 0 | Indexes->insertMBBInMaps(NMBB); |
893 | 252k | |
894 | 252k | // On some targets like Mips, branches may kill virtual registers. Make sure |
895 | 252k | // that LiveVariables is properly updated after updateTerminator replaces the |
896 | 252k | // terminators. |
897 | 252k | LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>(); |
898 | 252k | |
899 | 252k | // Collect a list of virtual registers killed by the terminators. |
900 | 252k | SmallVector<unsigned, 4> KilledRegs; |
901 | 252k | if (LV) |
902 | 142k | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
903 | 338k | I != E; ++I196k ) { |
904 | 196k | MachineInstr *MI = &*I; |
905 | 196k | for (MachineInstr::mop_iterator OI = MI->operands_begin(), |
906 | 642k | OE = MI->operands_end(); OI != OE; ++OI446k ) { |
907 | 446k | if (!OI->isReg() || OI->getReg() == 0145k || |
908 | 446k | !OI->isUse()142k || !OI->isKill()142k || OI->isUndef()120k ) |
909 | 326k | continue; |
910 | 120k | unsigned Reg = OI->getReg(); |
911 | 120k | if (TargetRegisterInfo::isPhysicalRegister(Reg) || |
912 | 120k | LV->getVarInfo(Reg).removeKill(*MI)31.8k ) { |
913 | 120k | KilledRegs.push_back(Reg); |
914 | 120k | LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI); |
915 | 120k | OI->setIsKill(false); |
916 | 120k | } |
917 | 120k | } |
918 | 196k | } |
919 | 252k | |
920 | 252k | SmallVector<unsigned, 4> UsedRegs; |
921 | 252k | if (LIS) { |
922 | 0 | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
923 | 0 | I != E; ++I) { |
924 | 0 | MachineInstr *MI = &*I; |
925 | 0 |
|
926 | 0 | for (MachineInstr::mop_iterator OI = MI->operands_begin(), |
927 | 0 | OE = MI->operands_end(); OI != OE; ++OI) { |
928 | 0 | if (!OI->isReg() || OI->getReg() == 0) |
929 | 0 | continue; |
930 | 0 | |
931 | 0 | unsigned Reg = OI->getReg(); |
932 | 0 | if (!is_contained(UsedRegs, Reg)) |
933 | 0 | UsedRegs.push_back(Reg); |
934 | 0 | } |
935 | 0 | } |
936 | 0 | } |
937 | 252k | |
938 | 252k | ReplaceUsesOfBlockWith(Succ, NMBB); |
939 | 252k | |
940 | 252k | // If updateTerminator() removes instructions, we need to remove them from |
941 | 252k | // SlotIndexes. |
942 | 252k | SmallVector<MachineInstr*, 4> Terminators; |
943 | 252k | if (Indexes) { |
944 | 0 | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
945 | 0 | I != E; ++I) |
946 | 0 | Terminators.push_back(&*I); |
947 | 0 | } |
948 | 252k | |
949 | 252k | updateTerminator(); |
950 | 252k | |
951 | 252k | if (Indexes) { |
952 | 0 | SmallVector<MachineInstr*, 4> NewTerminators; |
953 | 0 | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
954 | 0 | I != E; ++I) |
955 | 0 | NewTerminators.push_back(&*I); |
956 | 0 |
|
957 | 0 | for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(), |
958 | 0 | E = Terminators.end(); I != E; ++I) { |
959 | 0 | if (!is_contained(NewTerminators, *I)) |
960 | 0 | Indexes->removeMachineInstrFromMaps(**I); |
961 | 0 | } |
962 | 0 | } |
963 | 252k | |
964 | 252k | // Insert unconditional "jump Succ" instruction in NMBB if necessary. |
965 | 252k | NMBB->addSuccessor(Succ); |
966 | 252k | if (!NMBB->isLayoutSuccessor(Succ)) { |
967 | 238k | SmallVector<MachineOperand, 4> Cond; |
968 | 238k | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
969 | 238k | TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL); |
970 | 238k | |
971 | 238k | if (Indexes) { |
972 | 0 | for (MachineInstr &MI : NMBB->instrs()) { |
973 | 0 | // Some instructions may have been moved to NMBB by updateTerminator(), |
974 | 0 | // so we first remove any instruction that already has an index. |
975 | 0 | if (Indexes->hasIndex(MI)) |
976 | 0 | Indexes->removeMachineInstrFromMaps(MI); |
977 | 0 | Indexes->insertMachineInstrInMaps(MI); |
978 | 0 | } |
979 | 0 | } |
980 | 238k | } |
981 | 252k | |
982 | 252k | // Fix PHI nodes in Succ so they refer to NMBB instead of this |
983 | 252k | for (MachineBasicBlock::instr_iterator |
984 | 252k | i = Succ->instr_begin(),e = Succ->instr_end(); |
985 | 577k | i != e && i->isPHI()574k ; ++i325k ) |
986 | 3.48M | for (unsigned ni = 1, ne = i->getNumOperands(); 325k ni != ne; ni += 23.16M ) |
987 | 3.16M | if (i->getOperand(ni+1).getMBB() == this) |
988 | 327k | i->getOperand(ni+1).setMBB(NMBB); |
989 | 252k | |
990 | 252k | // Inherit live-ins from the successor |
991 | 252k | for (const auto &LI : Succ->liveins()) |
992 | 495 | NMBB->addLiveIn(LI); |
993 | 252k | |
994 | 252k | // Update LiveVariables. |
995 | 252k | const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); |
996 | 252k | if (LV) { |
997 | 142k | // Restore kills of virtual registers that were killed by the terminators. |
998 | 262k | while (!KilledRegs.empty()) { |
999 | 120k | unsigned Reg = KilledRegs.pop_back_val(); |
1000 | 120k | for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) { |
1001 | 120k | if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false)) |
1002 | 10 | continue; |
1003 | 120k | if (TargetRegisterInfo::isVirtualRegister(Reg)) |
1004 | 31.8k | LV->getVarInfo(Reg).Kills.push_back(&*I); |
1005 | 120k | LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I); |
1006 | 120k | break; |
1007 | 120k | } |
1008 | 120k | } |
1009 | 142k | // Update relevant live-through information. |
1010 | 142k | LV->addNewBlock(NMBB, this, Succ); |
1011 | 142k | } |
1012 | 252k | |
1013 | 252k | if (LIS) { |
1014 | 0 | // After splitting the edge and updating SlotIndexes, live intervals may be |
1015 | 0 | // in one of two situations, depending on whether this block was the last in |
1016 | 0 | // the function. If the original block was the last in the function, all |
1017 | 0 | // live intervals will end prior to the beginning of the new split block. If |
1018 | 0 | // the original block was not at the end of the function, all live intervals |
1019 | 0 | // will extend to the end of the new split block. |
1020 | 0 |
|
1021 | 0 | bool isLastMBB = |
1022 | 0 | std::next(MachineFunction::iterator(NMBB)) == getParent()->end(); |
1023 | 0 |
|
1024 | 0 | SlotIndex StartIndex = Indexes->getMBBEndIdx(this); |
1025 | 0 | SlotIndex PrevIndex = StartIndex.getPrevSlot(); |
1026 | 0 | SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB); |
1027 | 0 |
|
1028 | 0 | // Find the registers used from NMBB in PHIs in Succ. |
1029 | 0 | SmallSet<unsigned, 8> PHISrcRegs; |
1030 | 0 | for (MachineBasicBlock::instr_iterator |
1031 | 0 | I = Succ->instr_begin(), E = Succ->instr_end(); |
1032 | 0 | I != E && I->isPHI(); ++I) { |
1033 | 0 | for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) { |
1034 | 0 | if (I->getOperand(ni+1).getMBB() == NMBB) { |
1035 | 0 | MachineOperand &MO = I->getOperand(ni); |
1036 | 0 | unsigned Reg = MO.getReg(); |
1037 | 0 | PHISrcRegs.insert(Reg); |
1038 | 0 | if (MO.isUndef()) |
1039 | 0 | continue; |
1040 | 0 | |
1041 | 0 | LiveInterval &LI = LIS->getInterval(Reg); |
1042 | 0 | VNInfo *VNI = LI.getVNInfoAt(PrevIndex); |
1043 | 0 | assert(VNI && |
1044 | 0 | "PHI sources should be live out of their predecessors."); |
1045 | 0 | LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); |
1046 | 0 | } |
1047 | 0 | } |
1048 | 0 | } |
1049 | 0 |
|
1050 | 0 | MachineRegisterInfo *MRI = &getParent()->getRegInfo(); |
1051 | 0 | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { |
1052 | 0 | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
1053 | 0 | if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg)) |
1054 | 0 | continue; |
1055 | 0 | |
1056 | 0 | LiveInterval &LI = LIS->getInterval(Reg); |
1057 | 0 | if (!LI.liveAt(PrevIndex)) |
1058 | 0 | continue; |
1059 | 0 | |
1060 | 0 | bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ)); |
1061 | 0 | if (isLiveOut && isLastMBB) { |
1062 | 0 | VNInfo *VNI = LI.getVNInfoAt(PrevIndex); |
1063 | 0 | assert(VNI && "LiveInterval should have VNInfo where it is live."); |
1064 | 0 | LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); |
1065 | 0 | } else if (!isLiveOut && !isLastMBB) { |
1066 | 0 | LI.removeSegment(StartIndex, EndIndex); |
1067 | 0 | } |
1068 | 0 | } |
1069 | 0 |
|
1070 | 0 | // Update all intervals for registers whose uses may have been modified by |
1071 | 0 | // updateTerminator(). |
1072 | 0 | LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs); |
1073 | 0 | } |
1074 | 252k | |
1075 | 252k | if (MachineDominatorTree *MDT = |
1076 | 252k | P.getAnalysisIfAvailable<MachineDominatorTree>()) |
1077 | 252k | MDT->recordSplitCriticalEdge(this, Succ, NMBB); |
1078 | 252k | |
1079 | 252k | if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>()) |
1080 | 252k | if (MachineLoop *TIL = MLI->getLoopFor(this)) { |
1081 | 70.3k | // If one or the other blocks were not in a loop, the new block is not |
1082 | 70.3k | // either, and thus LI doesn't need to be updated. |
1083 | 70.3k | if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) { |
1084 | 44.9k | if (TIL == DestLoop) { |
1085 | 41.0k | // Both in the same loop, the NMBB joins loop. |
1086 | 41.0k | DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); |
1087 | 41.0k | } else if (3.94k TIL->contains(DestLoop)3.94k ) { |
1088 | 413 | // Edge from an outer loop to an inner loop. Add to the outer loop. |
1089 | 413 | TIL->addBasicBlockToLoop(NMBB, MLI->getBase()); |
1090 | 3.52k | } else if (DestLoop->contains(TIL)) { |
1091 | 3.37k | // Edge from an inner loop to an outer loop. Add to the outer loop. |
1092 | 3.37k | DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); |
1093 | 3.37k | } else { |
1094 | 157 | // Edge from two loops with no containment relation. Because these |
1095 | 157 | // are natural loops, we know that the destination block must be the |
1096 | 157 | // header of its loop (adding a branch into a loop elsewhere would |
1097 | 157 | // create an irreducible loop). |
1098 | 157 | assert(DestLoop->getHeader() == Succ && |
1099 | 157 | "Should not create irreducible loops!"); |
1100 | 157 | if (MachineLoop *P = DestLoop->getParentLoop()) |
1101 | 35 | P->addBasicBlockToLoop(NMBB, MLI->getBase()); |
1102 | 157 | } |
1103 | 44.9k | } |
1104 | 70.3k | } |
1105 | 252k | |
1106 | 252k | return NMBB; |
1107 | 252k | } |
1108 | | |
1109 | | bool MachineBasicBlock::canSplitCriticalEdge( |
1110 | 254k | const MachineBasicBlock *Succ) const { |
1111 | 254k | // Splitting the critical edge to a landing pad block is non-trivial. Don't do |
1112 | 254k | // it in this generic function. |
1113 | 254k | if (Succ->isEHPad()) |
1114 | 0 | return false; |
1115 | 254k | |
1116 | 254k | const MachineFunction *MF = getParent(); |
1117 | 254k | |
1118 | 254k | // Performance might be harmed on HW that implements branching using exec mask |
1119 | 254k | // where both sides of the branches are always executed. |
1120 | 254k | if (MF->getTarget().requiresStructuredCFG()) |
1121 | 87 | return false; |
1122 | 254k | |
1123 | 254k | // We may need to update this's terminator, but we can't do that if |
1124 | 254k | // AnalyzeBranch fails. If this uses a jump table, we won't touch it. |
1125 | 254k | const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); |
1126 | 254k | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
1127 | 254k | SmallVector<MachineOperand, 4> Cond; |
1128 | 254k | // AnalyzeBanch should modify this, since we did not allow modification. |
1129 | 254k | if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond, |
1130 | 254k | /*AllowModify*/ false)) |
1131 | 2.13k | return false; |
1132 | 252k | |
1133 | 252k | // Avoid bugpoint weirdness: A block may end with a conditional branch but |
1134 | 252k | // jumps to the same MBB is either case. We have duplicate CFG edges in that |
1135 | 252k | // case that we can't handle. Since this never happens in properly optimized |
1136 | 252k | // code, just skip those edges. |
1137 | 252k | if (TBB && TBB == FBB) { |
1138 | 0 | LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate " |
1139 | 0 | << printMBBReference(*this) << '\n'); |
1140 | 0 | return false; |
1141 | 0 | } |
1142 | 252k | return true; |
1143 | 252k | } |
1144 | | |
1145 | | /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's |
1146 | | /// neighboring instructions so the bundle won't be broken by removing MI. |
1147 | 2.85M | static void unbundleSingleMI(MachineInstr *MI) { |
1148 | 2.85M | // Removing the first instruction in a bundle. |
1149 | 2.85M | if (MI->isBundledWithSucc() && !MI->isBundledWithPred()2.19k ) |
1150 | 6 | MI->unbundleFromSucc(); |
1151 | 2.85M | // Removing the last instruction in a bundle. |
1152 | 2.85M | if (MI->isBundledWithPred() && !MI->isBundledWithSucc()8.86k ) |
1153 | 6.67k | MI->unbundleFromPred(); |
1154 | 2.85M | // If MI is not bundled, or if it is internal to a bundle, the neighbor flags |
1155 | 2.85M | // are already fine. |
1156 | 2.85M | } |
1157 | | |
1158 | | MachineBasicBlock::instr_iterator |
1159 | 2.85M | MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) { |
1160 | 2.85M | unbundleSingleMI(&*I); |
1161 | 2.85M | return Insts.erase(I); |
1162 | 2.85M | } |
1163 | | |
1164 | 98 | MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) { |
1165 | 98 | unbundleSingleMI(MI); |
1166 | 98 | MI->clearFlag(MachineInstr::BundledPred); |
1167 | 98 | MI->clearFlag(MachineInstr::BundledSucc); |
1168 | 98 | return Insts.remove(MI); |
1169 | 98 | } |
1170 | | |
1171 | | MachineBasicBlock::instr_iterator |
1172 | 122k | MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) { |
1173 | 122k | assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && |
1174 | 122k | "Cannot insert instruction with bundle flags"); |
1175 | 122k | // Set the bundle flags when inserting inside a bundle. |
1176 | 122k | if (I != instr_end() && I->isBundledWithPred()122k ) { |
1177 | 8.79k | MI->setFlag(MachineInstr::BundledPred); |
1178 | 8.79k | MI->setFlag(MachineInstr::BundledSucc); |
1179 | 8.79k | } |
1180 | 122k | return Insts.insert(I, MI); |
1181 | 122k | } |
1182 | | |
1183 | | /// This method unlinks 'this' from the containing function, and returns it, but |
1184 | | /// does not delete it. |
1185 | 0 | MachineBasicBlock *MachineBasicBlock::removeFromParent() { |
1186 | 0 | assert(getParent() && "Not embedded in a function!"); |
1187 | 0 | getParent()->remove(this); |
1188 | 0 | return this; |
1189 | 0 | } |
1190 | | |
1191 | | /// This method unlinks 'this' from the containing function, and deletes it. |
1192 | 102k | void MachineBasicBlock::eraseFromParent() { |
1193 | 102k | assert(getParent() && "Not embedded in a function!"); |
1194 | 102k | getParent()->erase(this); |
1195 | 102k | } |
1196 | | |
1197 | | /// Given a machine basic block that branched to 'Old', change the code and CFG |
1198 | | /// so that it branches to 'New' instead. |
1199 | | void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, |
1200 | 457k | MachineBasicBlock *New) { |
1201 | 457k | assert(Old != New && "Cannot replace self with self!"); |
1202 | 457k | |
1203 | 457k | MachineBasicBlock::instr_iterator I = instr_end(); |
1204 | 1.22M | while (I != instr_begin()) { |
1205 | 1.20M | --I; |
1206 | 1.20M | if (!I->isTerminator()) break441k ; |
1207 | 765k | |
1208 | 765k | // Scan the operands of this machine instruction, replacing any uses of Old |
1209 | 765k | // with New. |
1210 | 2.28M | for (unsigned i = 0, e = I->getNumOperands(); 765k i != e; ++i1.52M ) |
1211 | 1.52M | if (I->getOperand(i).isMBB() && |
1212 | 1.52M | I->getOperand(i).getMBB() == Old764k ) |
1213 | 425k | I->getOperand(i).setMBB(New); |
1214 | 765k | } |
1215 | 457k | |
1216 | 457k | // Update the successor information. |
1217 | 457k | replaceSuccessor(Old, New); |
1218 | 457k | } |
1219 | | |
1220 | | /// Various pieces of code can cause excess edges in the CFG to be inserted. If |
1221 | | /// we have proven that MBB can only branch to DestA and DestB, remove any other |
1222 | | /// MBB successors from the CFG. DestA and DestB can be null. |
1223 | | /// |
1224 | | /// Besides DestA and DestB, retain other edges leading to LandingPads |
1225 | | /// (currently there can be only one; we don't check or require that here). |
1226 | | /// Note it is possible that DestA and/or DestB are LandingPads. |
1227 | | bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, |
1228 | | MachineBasicBlock *DestB, |
1229 | 16.7M | bool IsCond) { |
1230 | 16.7M | // The values of DestA and DestB frequently come from a call to the |
1231 | 16.7M | // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial |
1232 | 16.7M | // values from there. |
1233 | 16.7M | // |
1234 | 16.7M | // 1. If both DestA and DestB are null, then the block ends with no branches |
1235 | 16.7M | // (it falls through to its successor). |
1236 | 16.7M | // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends |
1237 | 16.7M | // with only an unconditional branch. |
1238 | 16.7M | // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends |
1239 | 16.7M | // with a conditional branch that falls through to a successor (DestB). |
1240 | 16.7M | // 4. If DestA and DestB is set and IsCond is true, then the block ends with a |
1241 | 16.7M | // conditional branch followed by an unconditional branch. DestA is the |
1242 | 16.7M | // 'true' destination and DestB is the 'false' destination. |
1243 | 16.7M | |
1244 | 16.7M | bool Changed = false; |
1245 | 16.7M | |
1246 | 16.7M | MachineBasicBlock *FallThru = getNextNode(); |
1247 | 16.7M | |
1248 | 16.7M | if (!DestA && !DestB4.11M ) { |
1249 | 4.11M | // Block falls through to successor. |
1250 | 4.11M | DestA = FallThru; |
1251 | 4.11M | DestB = FallThru; |
1252 | 12.5M | } else if (DestA && !DestB) { |
1253 | 10.9M | if (IsCond) |
1254 | 7.96M | // Block ends in conditional jump that falls through to successor. |
1255 | 7.96M | DestB = FallThru; |
1256 | 10.9M | } else { |
1257 | 1.61M | assert(DestA && DestB && IsCond && |
1258 | 1.61M | "CFG in a bad state. Cannot correct CFG edges"); |
1259 | 1.61M | } |
1260 | 16.7M | |
1261 | 16.7M | // Remove superfluous edges. I.e., those which aren't destinations of this |
1262 | 16.7M | // basic block, duplicate edges, or landing pads. |
1263 | 16.7M | SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs; |
1264 | 16.7M | MachineBasicBlock::succ_iterator SI = succ_begin(); |
1265 | 43.0M | while (SI != succ_end()) { |
1266 | 26.3M | const MachineBasicBlock *MBB = *SI; |
1267 | 26.3M | if (!SeenMBBs.insert(MBB).second || |
1268 | 26.3M | (MBB != DestA && MBB != DestB9.88M && !MBB->isEHPad()299k )) { |
1269 | 2.92k | // This is a superfluous edge, remove it. |
1270 | 2.92k | SI = removeSuccessor(SI); |
1271 | 2.92k | Changed = true; |
1272 | 26.3M | } else { |
1273 | 26.3M | ++SI; |
1274 | 26.3M | } |
1275 | 26.3M | } |
1276 | 16.7M | |
1277 | 16.7M | if (Changed) |
1278 | 2.92k | normalizeSuccProbs(); |
1279 | 16.7M | return Changed; |
1280 | 16.7M | } |
1281 | | |
1282 | | /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE |
1283 | | /// instructions. Return UnknownLoc if there is none. |
1284 | | DebugLoc |
1285 | 528k | MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { |
1286 | 528k | // Skip debug declarations, we don't want a DebugLoc from them. |
1287 | 528k | MBBI = skipDebugInstructionsForward(MBBI, instr_end()); |
1288 | 528k | if (MBBI != instr_end()) |
1289 | 528k | return MBBI->getDebugLoc(); |
1290 | 250 | return {}; |
1291 | 250 | } |
1292 | | |
1293 | | /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE |
1294 | | /// instructions. Return UnknownLoc if there is none. |
1295 | 4.82k | DebugLoc MachineBasicBlock::findPrevDebugLoc(instr_iterator MBBI) { |
1296 | 4.82k | if (MBBI == instr_begin()) return {}286 ; |
1297 | 4.53k | // Skip debug declarations, we don't want a DebugLoc from them. |
1298 | 4.53k | MBBI = skipDebugInstructionsBackward(std::prev(MBBI), instr_begin()); |
1299 | 4.53k | if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc(); |
1300 | 0 | return {}; |
1301 | 0 | } |
1302 | | |
1303 | | /// Find and return the merged DebugLoc of the branch instructions of the block. |
1304 | | /// Return UnknownLoc if there is none. |
1305 | | DebugLoc |
1306 | 10.3M | MachineBasicBlock::findBranchDebugLoc() { |
1307 | 10.3M | DebugLoc DL; |
1308 | 10.3M | auto TI = getFirstTerminator(); |
1309 | 10.3M | while (TI != end() && !TI->isBranch()8.66M ) |
1310 | 171 | ++TI; |
1311 | 10.3M | |
1312 | 10.3M | if (TI != end()) { |
1313 | 8.66M | DL = TI->getDebugLoc(); |
1314 | 9.54M | for (++TI ; TI != end() ; ++TI871k ) |
1315 | 871k | if (TI->isBranch()) |
1316 | 871k | DL = DILocation::getMergedLocation(DL, TI->getDebugLoc()); |
1317 | 8.66M | } |
1318 | 10.3M | return DL; |
1319 | 10.3M | } |
1320 | | |
1321 | | /// Return probability of the edge from this block to MBB. |
1322 | | BranchProbability |
1323 | 23.7M | MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const { |
1324 | 23.7M | if (Probs.empty()) |
1325 | 349k | return BranchProbability(1, succ_size()); |
1326 | 23.4M | |
1327 | 23.4M | const auto &Prob = *getProbabilityIterator(Succ); |
1328 | 23.4M | if (Prob.isUnknown()) { |
1329 | 14.7M | // For unknown probabilities, collect the sum of all known ones, and evenly |
1330 | 14.7M | // ditribute the complemental of the sum to each unknown probability. |
1331 | 14.7M | unsigned KnownProbNum = 0; |
1332 | 14.7M | auto Sum = BranchProbability::getZero(); |
1333 | 23.7M | for (auto &P : Probs) { |
1334 | 23.7M | if (!P.isUnknown()) { |
1335 | 21 | Sum += P; |
1336 | 21 | KnownProbNum++; |
1337 | 21 | } |
1338 | 23.7M | } |
1339 | 14.7M | return Sum.getCompl() / (Probs.size() - KnownProbNum); |
1340 | 14.7M | } else |
1341 | 8.70M | return Prob; |
1342 | 23.4M | } |
1343 | | |
1344 | | /// Set successor probability of a given iterator. |
1345 | | void MachineBasicBlock::setSuccProbability(succ_iterator I, |
1346 | 29.7k | BranchProbability Prob) { |
1347 | 29.7k | assert(!Prob.isUnknown()); |
1348 | 29.7k | if (Probs.empty()) |
1349 | 578 | return; |
1350 | 29.1k | *getProbabilityIterator(I) = Prob; |
1351 | 29.1k | } |
1352 | | |
1353 | | /// Return probability iterator corresonding to the I successor iterator |
1354 | | MachineBasicBlock::const_probability_iterator |
1355 | | MachineBasicBlock::getProbabilityIterator( |
1356 | 23.4M | MachineBasicBlock::const_succ_iterator I) const { |
1357 | 23.4M | assert(Probs.size() == Successors.size() && "Async probability list!"); |
1358 | 23.4M | const size_t index = std::distance(Successors.begin(), I); |
1359 | 23.4M | assert(index < Probs.size() && "Not a current successor!"); |
1360 | 23.4M | return Probs.begin() + index; |
1361 | 23.4M | } |
1362 | | |
1363 | | /// Return probability iterator corresonding to the I successor iterator. |
1364 | | MachineBasicBlock::probability_iterator |
1365 | 1.07M | MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) { |
1366 | 1.07M | assert(Probs.size() == Successors.size() && "Async probability list!"); |
1367 | 1.07M | const size_t index = std::distance(Successors.begin(), I); |
1368 | 1.07M | assert(index < Probs.size() && "Not a current successor!"); |
1369 | 1.07M | return Probs.begin() + index; |
1370 | 1.07M | } |
1371 | | |
1372 | | /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed |
1373 | | /// as of just before "MI". |
1374 | | /// |
1375 | | /// Search is localised to a neighborhood of |
1376 | | /// Neighborhood instructions before (searching for defs or kills) and N |
1377 | | /// instructions after (searching just for defs) MI. |
1378 | | MachineBasicBlock::LivenessQueryResult |
1379 | | MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, |
1380 | | unsigned Reg, const_iterator Before, |
1381 | 95.6k | unsigned Neighborhood) const { |
1382 | 95.6k | unsigned N = Neighborhood; |
1383 | 95.6k | |
1384 | 95.6k | // Try searching forwards from Before, looking for reads or defs. |
1385 | 95.6k | const_iterator I(Before); |
1386 | 261k | for (; I != end() && N > 0251k ; ++I166k ) { |
1387 | 235k | if (I->isDebugInstr()) |
1388 | 37 | continue; |
1389 | 235k | |
1390 | 235k | --N; |
1391 | 235k | |
1392 | 235k | MachineOperandIteratorBase::PhysRegInfo Info = |
1393 | 235k | ConstMIOperands(*I).analyzePhysReg(Reg, TRI); |
1394 | 235k | |
1395 | 235k | // Register is live when we read it here. |
1396 | 235k | if (Info.Read) |
1397 | 2.05k | return LQR_Live; |
1398 | 233k | // Register is dead if we can fully overwrite or clobber it here. |
1399 | 233k | if (Info.FullyDefined || Info.Clobbered209k ) |
1400 | 67.3k | return LQR_Dead; |
1401 | 233k | } |
1402 | 95.6k | |
1403 | 95.6k | // If we reached the end, it is safe to clobber Reg at the end of a block of |
1404 | 95.6k | // no successor has it live in. |
1405 | 95.6k | if (26.1k I == end()26.1k ) { |
1406 | 10.4k | for (MachineBasicBlock *S : successors()) { |
1407 | 10.5k | for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) { |
1408 | 10.5k | if (TRI->regsOverlap(LI.PhysReg, Reg)) |
1409 | 28 | return LQR_Live; |
1410 | 10.5k | } |
1411 | 7.31k | } |
1412 | 10.4k | |
1413 | 10.4k | return LQR_Dead10.4k ; |
1414 | 15.7k | } |
1415 | 15.7k | |
1416 | 15.7k | |
1417 | 15.7k | N = Neighborhood; |
1418 | 15.7k | |
1419 | 15.7k | // Start by searching backwards from Before, looking for kills, reads or defs. |
1420 | 15.7k | I = const_iterator(Before); |
1421 | 15.7k | // If this is the first insn in the block, don't search backwards. |
1422 | 15.7k | if (I != begin()) { |
1423 | 30.1k | do { |
1424 | 30.1k | --I; |
1425 | 30.1k | |
1426 | 30.1k | if (I->isDebugInstr()) |
1427 | 8 | continue; |
1428 | 30.1k | |
1429 | 30.1k | --N; |
1430 | 30.1k | |
1431 | 30.1k | MachineOperandIteratorBase::PhysRegInfo Info = |
1432 | 30.1k | ConstMIOperands(*I).analyzePhysReg(Reg, TRI); |
1433 | 30.1k | |
1434 | 30.1k | // Defs happen after uses so they take precedence if both are present. |
1435 | 30.1k | |
1436 | 30.1k | // Register is dead after a dead def of the full register. |
1437 | 30.1k | if (Info.DeadDef) |
1438 | 7.16k | return LQR_Dead; |
1439 | 22.9k | // Register is (at least partially) live after a def. |
1440 | 22.9k | if (Info.Defined) { |
1441 | 63 | if (!Info.PartialDeadDef) |
1442 | 63 | return LQR_Live; |
1443 | 0 | // As soon as we saw a partial definition (dead or not), |
1444 | 0 | // we cannot tell if the value is partial live without |
1445 | 0 | // tracking the lanemasks. We are not going to do this, |
1446 | 0 | // so fall back on the remaining of the analysis. |
1447 | 0 | break; |
1448 | 0 | } |
1449 | 22.8k | // Register is dead after a full kill or clobber and no def. |
1450 | 22.8k | if (Info.Killed || Info.Clobbered22.8k ) |
1451 | 80 | return LQR_Dead; |
1452 | 22.8k | // Register must be live if we read it. |
1453 | 22.8k | if (Info.Read) |
1454 | 54 | return LQR_Live; |
1455 | 22.7k | |
1456 | 22.7k | } while (I != begin() && N > 021.4k ); |
1457 | 11.2k | } |
1458 | 15.7k | |
1459 | 15.7k | // Did we get to the start of the block? |
1460 | 15.7k | if (8.34k I == begin()8.34k ) { |
1461 | 5.73k | // If so, the register's state is definitely defined by the live-in state. |
1462 | 5.73k | for (const MachineBasicBlock::RegisterMaskPair &LI : liveins()) |
1463 | 18.5k | if (TRI->regsOverlap(LI.PhysReg, Reg)) |
1464 | 0 | return LQR_Live; |
1465 | 5.73k | |
1466 | 5.73k | return LQR_Dead; |
1467 | 2.60k | } |
1468 | 2.60k | |
1469 | 2.60k | // At this point we have no idea of the liveness of the register. |
1470 | 2.60k | return LQR_Unknown; |
1471 | 2.60k | } |
1472 | | |
1473 | | const uint32_t * |
1474 | 2.92M | MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const { |
1475 | 2.92M | // EH funclet entry does not preserve any registers. |
1476 | 2.92M | return isEHFuncletEntry() ? TRI->getNoPreservedMask()131 : nullptr2.92M ; |
1477 | 2.92M | } |
1478 | | |
1479 | | const uint32_t * |
1480 | 2.92M | MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const { |
1481 | 2.92M | // If we see a return block with successors, this must be a funclet return, |
1482 | 2.92M | // which does not preserve any registers. If there are no successors, we don't |
1483 | 2.92M | // care what kind of return it is, putting a mask after it is a no-op. |
1484 | 2.92M | return isReturnBlock() && !succ_empty()678k ? TRI->getNoPreservedMask()82 : nullptr2.92M ; |
1485 | 2.92M | } |
1486 | | |
1487 | 112k | void MachineBasicBlock::clearLiveIns() { |
1488 | 112k | LiveIns.clear(); |
1489 | 112k | } |
1490 | | |
1491 | 25.1M | MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const { |
1492 | 25.1M | assert(getParent()->getProperties().hasProperty( |
1493 | 25.1M | MachineFunctionProperties::Property::TracksLiveness) && |
1494 | 25.1M | "Liveness information is accurate"); |
1495 | 25.1M | return LiveIns.begin(); |
1496 | 25.1M | } |