/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/MachineBasicBlock.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // Collect the sequence of machine instructions for a basic block. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
15 | | #include "llvm/ADT/SmallPtrSet.h" |
16 | | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
17 | | #include "llvm/CodeGen/LiveVariables.h" |
18 | | #include "llvm/CodeGen/MachineDominators.h" |
19 | | #include "llvm/CodeGen/MachineFunction.h" |
20 | | #include "llvm/CodeGen/MachineInstrBuilder.h" |
21 | | #include "llvm/CodeGen/MachineLoopInfo.h" |
22 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
23 | | #include "llvm/CodeGen/SlotIndexes.h" |
24 | | #include "llvm/IR/BasicBlock.h" |
25 | | #include "llvm/IR/DataLayout.h" |
26 | | #include "llvm/IR/DebugInfoMetadata.h" |
27 | | #include "llvm/IR/ModuleSlotTracker.h" |
28 | | #include "llvm/MC/MCAsmInfo.h" |
29 | | #include "llvm/MC/MCContext.h" |
30 | | #include "llvm/Support/DataTypes.h" |
31 | | #include "llvm/Support/Debug.h" |
32 | | #include "llvm/Support/raw_ostream.h" |
33 | | #include "llvm/Target/TargetInstrInfo.h" |
34 | | #include "llvm/Target/TargetMachine.h" |
35 | | #include "llvm/Target/TargetRegisterInfo.h" |
36 | | #include "llvm/Target/TargetSubtargetInfo.h" |
37 | | #include <algorithm> |
38 | | using namespace llvm; |
39 | | |
40 | | #define DEBUG_TYPE "codegen" |
41 | | |
42 | | MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B) |
43 | 5.99M | : BB(B), Number(-1), xParent(&MF) { |
44 | 5.99M | Insts.Parent = this; |
45 | 5.99M | } |
46 | | |
47 | 5.99M | MachineBasicBlock::~MachineBasicBlock() { |
48 | 5.99M | } |
49 | | |
50 | | /// Return the MCSymbol for this basic block. |
51 | 4.35M | MCSymbol *MachineBasicBlock::getSymbol() const { |
52 | 4.35M | if (!CachedMCSymbol4.35M ) { |
53 | 1.81M | const MachineFunction *MF = getParent(); |
54 | 1.81M | MCContext &Ctx = MF->getContext(); |
55 | 1.81M | auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix(); |
56 | 1.81M | assert(getNumber() >= 0 && "cannot get label for unreachable MBB"); |
57 | 1.81M | CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" + |
58 | 1.81M | Twine(MF->getFunctionNumber()) + |
59 | 1.81M | "_" + Twine(getNumber())); |
60 | 1.81M | } |
61 | 4.35M | |
62 | 4.35M | return CachedMCSymbol; |
63 | 4.35M | } |
64 | | |
65 | | |
66 | 0 | raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { |
67 | 0 | MBB.print(OS); |
68 | 0 | return OS; |
69 | 0 | } |
70 | | |
71 | | /// When an MBB is added to an MF, we need to update the parent pointer of the |
72 | | /// MBB, the MBB numbering, and any instructions in the MBB to be on the right |
73 | | /// operand list for registers. |
74 | | /// |
75 | | /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it |
76 | | /// gets the next available unique MBB number. If it is removed from a |
77 | | /// MachineFunction, it goes back to being #-1. |
78 | | void ilist_callback_traits<MachineBasicBlock>::addNodeToList( |
79 | 5.99M | MachineBasicBlock *N) { |
80 | 5.99M | MachineFunction &MF = *N->getParent(); |
81 | 5.99M | N->Number = MF.addToMBBNumbering(N); |
82 | 5.99M | |
83 | 5.99M | // Make sure the instructions have their operands in the reginfo lists. |
84 | 5.99M | MachineRegisterInfo &RegInfo = MF.getRegInfo(); |
85 | 5.99M | for (MachineBasicBlock::instr_iterator |
86 | 5.99M | I = N->instr_begin(), E = N->instr_end(); I != E5.99M ; ++I91 ) |
87 | 91 | I->AddRegOperandsToUseLists(RegInfo); |
88 | 5.99M | } |
89 | | |
90 | | void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList( |
91 | 5.99M | MachineBasicBlock *N) { |
92 | 5.99M | N->getParent()->removeFromMBBNumbering(N->Number); |
93 | 5.99M | N->Number = -1; |
94 | 5.99M | } |
95 | | |
96 | | /// When we add an instruction to a basic block list, we update its parent |
97 | | /// pointer and add its operands from reg use/def lists if appropriate. |
98 | 91.2M | void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) { |
99 | 91.2M | assert(!N->getParent() && "machine instruction already in a basic block"); |
100 | 91.2M | N->setParent(Parent); |
101 | 91.2M | |
102 | 91.2M | // Add the instruction's register operands to their corresponding |
103 | 91.2M | // use/def lists. |
104 | 91.2M | MachineFunction *MF = Parent->getParent(); |
105 | 91.2M | N->AddRegOperandsToUseLists(MF->getRegInfo()); |
106 | 91.2M | } |
107 | | |
108 | | /// When we remove an instruction from a basic block list, we update its parent |
109 | | /// pointer and remove its operands from reg use/def lists if appropriate. |
110 | 51.9M | void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) { |
111 | 51.9M | assert(N->getParent() && "machine instruction not in a basic block"); |
112 | 51.9M | |
113 | 51.9M | // Remove from the use/def lists. |
114 | 51.9M | if (MachineFunction *MF = N->getParent()->getParent()) |
115 | 51.9M | N->RemoveRegOperandsFromUseLists(MF->getRegInfo()); |
116 | 51.9M | |
117 | 51.9M | N->setParent(nullptr); |
118 | 51.9M | } |
119 | | |
120 | | /// When moving a range of instructions from one MBB list to another, we need to |
121 | | /// update the parent pointers and the use/def lists. |
122 | | void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList, |
123 | | instr_iterator First, |
124 | 3.98M | instr_iterator Last) { |
125 | 3.98M | assert(Parent->getParent() == FromList.Parent->getParent() && |
126 | 3.98M | "MachineInstr parent mismatch!"); |
127 | 3.98M | assert(this != &FromList && "Called without a real transfer..."); |
128 | 3.98M | assert(Parent != FromList.Parent && "Two lists have the same parent?"); |
129 | 3.98M | |
130 | 3.98M | // If splicing between two blocks within the same function, just update the |
131 | 3.98M | // parent pointers. |
132 | 11.6M | for (; First != Last11.6M ; ++First7.63M ) |
133 | 7.63M | First->setParent(Parent); |
134 | 3.98M | } |
135 | | |
136 | 51.0M | void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) { |
137 | 51.0M | assert(!MI->getParent() && "MI is still in a block!"); |
138 | 51.0M | Parent->getParent()->DeleteMachineInstr(MI); |
139 | 51.0M | } |
140 | | |
141 | 30.2k | MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() { |
142 | 30.2k | instr_iterator I = instr_begin(), E = instr_end(); |
143 | 55.3k | while (I != E && 55.3k I->isPHI()47.1k ) |
144 | 25.0k | ++I; |
145 | 30.2k | assert((I == E || !I->isInsideBundle()) && |
146 | 30.2k | "First non-phi MI cannot be inside a bundle!"); |
147 | 30.2k | return I; |
148 | 30.2k | } |
149 | | |
150 | | MachineBasicBlock::iterator |
151 | 649k | MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) { |
152 | 649k | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
153 | 649k | |
154 | 649k | iterator E = end(); |
155 | 1.61M | while (I != E && 1.61M (I->isPHI() || 1.59M I->isPosition()658k || |
156 | 1.61M | TII->isBasicBlockPrologue(*I))) |
157 | 964k | ++I; |
158 | 649k | // FIXME: This needs to change if we wish to bundle labels |
159 | 649k | // inside the bundle. |
160 | 649k | assert((I == E || !I->isInsideBundle()) && |
161 | 649k | "First non-phi / non-label instruction is inside a bundle!"); |
162 | 649k | return I; |
163 | 649k | } |
164 | | |
165 | | MachineBasicBlock::iterator |
166 | 122k | MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) { |
167 | 122k | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
168 | 122k | |
169 | 122k | iterator E = end(); |
170 | 123k | while (I != E && 123k (I->isPHI() || 120k I->isPosition()120k || I->isDebugValue()119k || |
171 | 123k | TII->isBasicBlockPrologue(*I))) |
172 | 1.06k | ++I; |
173 | 122k | // FIXME: This needs to change if we wish to bundle labels / dbg_values |
174 | 122k | // inside the bundle. |
175 | 122k | assert((I == E || !I->isInsideBundle()) && |
176 | 122k | "First non-phi / non-label / non-debug " |
177 | 122k | "instruction is inside a bundle!"); |
178 | 122k | return I; |
179 | 122k | } |
180 | | |
181 | 38.3M | MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { |
182 | 38.3M | iterator B = begin(), E = end(), I = E; |
183 | 78.2M | while (I != B && 78.2M ((--I)->isTerminator() || 75.1M I->isDebugValue()35.2M )) |
184 | 39.8M | ; /*noop */ |
185 | 73.6M | while (I != E && 73.6M !I->isTerminator()67.2M ) |
186 | 35.2M | ++I; |
187 | 38.3M | return I; |
188 | 38.3M | } |
189 | | |
190 | 175k | MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() { |
191 | 175k | instr_iterator B = instr_begin(), E = instr_end(), I = E; |
192 | 499k | while (I != B && 499k ((--I)->isTerminator() || 486k I->isDebugValue()162k )) |
193 | 324k | ; /*noop */ |
194 | 337k | while (I != E && 337k !I->isTerminator()335k ) |
195 | 162k | ++I; |
196 | 175k | return I; |
197 | 175k | } |
198 | | |
199 | 27.9M | MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() { |
200 | 27.9M | // Skip over begin-of-block dbg_value instructions. |
201 | 27.9M | return skipDebugInstructionsForward(begin(), end()); |
202 | 27.9M | } |
203 | | |
204 | 133M | MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() { |
205 | 133M | // Skip over end-of-block dbg_value instructions. |
206 | 133M | instr_iterator B = instr_begin(), I = instr_end(); |
207 | 133M | while (I != B133M ) { |
208 | 132M | --I; |
209 | 132M | // Return instruction that starts a bundle. |
210 | 132M | if (I->isDebugValue() || 132M I->isInsideBundle()132M ) |
211 | 2.18k | continue; |
212 | 132M | return I; |
213 | 132M | } |
214 | 133M | // The block is all debug values. |
215 | 900k | return end(); |
216 | 133M | } |
217 | | |
218 | 10.2M | bool MachineBasicBlock::hasEHPadSuccessor() const { |
219 | 26.1M | for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E26.1M ; ++I15.8M ) |
220 | 15.9M | if (15.9M (*I)->isEHPad()15.9M ) |
221 | 59.6k | return true; |
222 | 10.2M | return false; |
223 | 10.2M | } |
224 | | |
225 | | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
226 | | LLVM_DUMP_METHOD void MachineBasicBlock::dump() const { |
227 | | print(dbgs()); |
228 | | } |
229 | | #endif |
230 | | |
231 | 541k | bool MachineBasicBlock::isLegalToHoistInto() const { |
232 | 541k | if (isReturnBlock() || 541k hasEHPadSuccessor()541k ) |
233 | 0 | return false; |
234 | 541k | return true; |
235 | 541k | } |
236 | | |
237 | 1.77k | StringRef MachineBasicBlock::getName() const { |
238 | 1.77k | if (const BasicBlock *LBB = getBasicBlock()) |
239 | 1.76k | return LBB->getName(); |
240 | 1.77k | else |
241 | 3 | return StringRef("", 0); |
242 | 0 | } |
243 | | |
244 | | /// Return a hopefully unique identifier for this block. |
245 | 0 | std::string MachineBasicBlock::getFullName() const { |
246 | 0 | std::string Name; |
247 | 0 | if (getParent()) |
248 | 0 | Name = (getParent()->getName() + ":").str(); |
249 | 0 | if (getBasicBlock()) |
250 | 0 | Name += getBasicBlock()->getName(); |
251 | 0 | else |
252 | 0 | Name += ("BB" + Twine(getNumber())).str(); |
253 | 0 | return Name; |
254 | 0 | } |
255 | | |
256 | | void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes) |
257 | 0 | const { |
258 | 0 | const MachineFunction *MF = getParent(); |
259 | 0 | if (!MF0 ) { |
260 | 0 | OS << "Can't print out MachineBasicBlock because parent MachineFunction" |
261 | 0 | << " is null\n"; |
262 | 0 | return; |
263 | 0 | } |
264 | 0 | const Function *F = MF->getFunction(); |
265 | 0 | const Module *M = F ? F->getParent()0 : nullptr0 ; |
266 | 0 | ModuleSlotTracker MST(M); |
267 | 0 | print(OS, MST, Indexes); |
268 | 0 | } |
269 | | |
270 | | void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST, |
271 | 12.2k | const SlotIndexes *Indexes) const { |
272 | 12.2k | const MachineFunction *MF = getParent(); |
273 | 12.2k | if (!MF12.2k ) { |
274 | 0 | OS << "Can't print out MachineBasicBlock because parent MachineFunction" |
275 | 0 | << " is null\n"; |
276 | 0 | return; |
277 | 0 | } |
278 | 12.2k | |
279 | 12.2k | if (12.2k Indexes12.2k ) |
280 | 1.14k | OS << Indexes->getMBBStartIdx(this) << '\t'; |
281 | 12.2k | |
282 | 12.2k | OS << "BB#" << getNumber() << ": "; |
283 | 12.2k | |
284 | 12.2k | const char *Comma = ""; |
285 | 12.2k | if (const BasicBlock *LBB12.2k = getBasicBlock()) { |
286 | 12.1k | OS << Comma << "derived from LLVM BB "; |
287 | 12.1k | LBB->printAsOperand(OS, /*PrintType=*/false, MST); |
288 | 12.1k | Comma = ", "; |
289 | 12.1k | } |
290 | 12.2k | if (isEHPad()12.2k ) { OS << Comma << "EH LANDING PAD"; Comma = ", "; }4 |
291 | 12.2k | if (hasAddressTaken()12.2k ) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; }2 |
292 | 12.2k | if (Alignment) |
293 | 0 | OS << Comma << "Align " << Alignment << " (" << (1u << Alignment) |
294 | 0 | << " bytes)"; |
295 | 12.2k | |
296 | 12.2k | OS << '\n'; |
297 | 12.2k | |
298 | 12.2k | const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); |
299 | 12.2k | if (!livein_empty()12.2k ) { |
300 | 5.30k | if (Indexes5.30k ) OS << '\t'272 ; |
301 | 5.30k | OS << " Live Ins:"; |
302 | 7.74k | for (const auto &LI : LiveIns) { |
303 | 7.74k | OS << ' ' << PrintReg(LI.PhysReg, TRI); |
304 | 7.74k | if (!LI.LaneMask.all()) |
305 | 0 | OS << ':' << PrintLaneMask(LI.LaneMask); |
306 | 7.74k | } |
307 | 5.30k | OS << '\n'; |
308 | 5.30k | } |
309 | 12.2k | // Print the preds of this block according to the CFG. |
310 | 12.2k | if (!pred_empty()12.2k ) { |
311 | 10.7k | if (Indexes10.7k ) OS << '\t'979 ; |
312 | 10.7k | OS << " Predecessors according to CFG:"; |
313 | 27.7k | for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E27.7k ; ++PI17.0k ) |
314 | 17.0k | OS << " BB#" << (*PI)->getNumber(); |
315 | 10.7k | OS << '\n'; |
316 | 10.7k | } |
317 | 12.2k | |
318 | 46.1k | for (auto &I : instrs()) { |
319 | 46.1k | if (Indexes46.1k ) { |
320 | 4.36k | if (Indexes->hasIndex(I)) |
321 | 4.36k | OS << Indexes->getInstructionIndex(I); |
322 | 4.36k | OS << '\t'; |
323 | 4.36k | } |
324 | 46.1k | OS << '\t'; |
325 | 46.1k | if (I.isInsideBundle()) |
326 | 8 | OS << " * "; |
327 | 46.1k | I.print(OS, MST); |
328 | 46.1k | } |
329 | 12.2k | |
330 | 12.2k | // Print the successors of this block according to the CFG. |
331 | 12.2k | if (!succ_empty()12.2k ) { |
332 | 9.44k | if (Indexes9.44k ) OS << '\t'859 ; |
333 | 9.44k | OS << " Successors according to CFG:"; |
334 | 26.4k | for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E26.4k ; ++SI17.0k ) { |
335 | 17.0k | OS << " BB#" << (*SI)->getNumber(); |
336 | 17.0k | if (!Probs.empty()) |
337 | 17.0k | OS << '(' << *getProbabilityIterator(SI) << ')'; |
338 | 17.0k | } |
339 | 9.44k | OS << '\n'; |
340 | 9.44k | } |
341 | 12.2k | } |
342 | | |
343 | | void MachineBasicBlock::printAsOperand(raw_ostream &OS, |
344 | 0 | bool /*PrintType*/) const { |
345 | 0 | OS << "BB#" << getNumber(); |
346 | 0 | } |
347 | | |
348 | 7.40k | void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) { |
349 | 7.40k | LiveInVector::iterator I = find_if( |
350 | 13.4k | LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); |
351 | 7.40k | if (I == LiveIns.end()) |
352 | 0 | return; |
353 | 7.40k | |
354 | 7.40k | I->LaneMask &= ~LaneMask; |
355 | 7.40k | if (I->LaneMask.none()) |
356 | 7.40k | LiveIns.erase(I); |
357 | 7.40k | } |
358 | | |
359 | | MachineBasicBlock::livein_iterator |
360 | 4.64k | MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) { |
361 | 4.64k | // Get non-const version of iterator. |
362 | 4.64k | LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin()); |
363 | 4.64k | return LiveIns.erase(LI); |
364 | 4.64k | } |
365 | | |
366 | 3.36M | bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const { |
367 | 3.36M | livein_iterator I = find_if( |
368 | 12.8M | LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); |
369 | 1.67M | return I != livein_end() && (I->LaneMask & LaneMask).any(); |
370 | 3.36M | } |
371 | | |
372 | 4.50M | void MachineBasicBlock::sortUniqueLiveIns() { |
373 | 4.50M | std::sort(LiveIns.begin(), LiveIns.end(), |
374 | 48.5M | [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) { |
375 | 48.5M | return LI0.PhysReg < LI1.PhysReg; |
376 | 48.5M | }); |
377 | 4.50M | // Liveins are sorted by physreg now we can merge their lanemasks. |
378 | 4.50M | LiveInVector::const_iterator I = LiveIns.begin(); |
379 | 4.50M | LiveInVector::const_iterator J; |
380 | 4.50M | LiveInVector::iterator Out = LiveIns.begin(); |
381 | 26.1M | for (; I != LiveIns.end()26.1M ; ++Out, I = J21.6M ) { |
382 | 21.6M | unsigned PhysReg = I->PhysReg; |
383 | 21.6M | LaneBitmask LaneMask = I->LaneMask; |
384 | 21.6M | for (J = std::next(I); J != LiveIns.end() && 21.6M J->PhysReg == PhysReg17.6M ; ++J200 ) |
385 | 200 | LaneMask |= J->LaneMask; |
386 | 21.6M | Out->PhysReg = PhysReg; |
387 | 21.6M | Out->LaneMask = LaneMask; |
388 | 21.6M | } |
389 | 4.50M | LiveIns.erase(Out, LiveIns.end()); |
390 | 4.50M | } |
391 | | |
392 | | unsigned |
393 | 25.4k | MachineBasicBlock::addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC) { |
394 | 25.4k | assert(getParent() && "MBB must be inserted in function"); |
395 | 25.4k | assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg"); |
396 | 25.4k | assert(RC && "Register class is required"); |
397 | 25.4k | assert((isEHPad() || this == &getParent()->front()) && |
398 | 25.4k | "Only the entry block and landing pads can have physreg live ins"); |
399 | 25.4k | |
400 | 25.4k | bool LiveIn = isLiveIn(PhysReg); |
401 | 25.4k | iterator I = SkipPHIsAndLabels(begin()), E = end(); |
402 | 25.4k | MachineRegisterInfo &MRI = getParent()->getRegInfo(); |
403 | 25.4k | const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo(); |
404 | 25.4k | |
405 | 25.4k | // Look for an existing copy. |
406 | 25.4k | if (LiveIn) |
407 | 0 | for (;0 I != E && 0 I->isCopy()0 ; ++I0 ) |
408 | 0 | if (0 I->getOperand(1).getReg() == PhysReg0 ) { |
409 | 0 | unsigned VirtReg = I->getOperand(0).getReg(); |
410 | 0 | if (!MRI.constrainRegClass(VirtReg, RC)) |
411 | 0 | llvm_unreachable("Incompatible live-in register class."); |
412 | 0 | return VirtReg; |
413 | 0 | } |
414 | 25.4k | |
415 | 25.4k | // No luck, create a virtual register. |
416 | 25.4k | unsigned VirtReg = MRI.createVirtualRegister(RC); |
417 | 25.4k | BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg) |
418 | 25.4k | .addReg(PhysReg, RegState::Kill); |
419 | 25.4k | if (!LiveIn) |
420 | 25.4k | addLiveIn(PhysReg); |
421 | 25.4k | return VirtReg; |
422 | 25.4k | } |
423 | | |
424 | 27.6k | void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { |
425 | 27.6k | getParent()->splice(NewAfter->getIterator(), getIterator()); |
426 | 27.6k | } |
427 | | |
428 | 439k | void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { |
429 | 439k | getParent()->splice(++NewBefore->getIterator(), getIterator()); |
430 | 439k | } |
431 | | |
432 | 4.05M | void MachineBasicBlock::updateTerminator() { |
433 | 4.05M | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
434 | 4.05M | // A block with no successors has no concerns with fall-through edges. |
435 | 4.05M | if (this->succ_empty()) |
436 | 26.1k | return; |
437 | 4.02M | |
438 | 4.02M | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
439 | 4.02M | SmallVector<MachineOperand, 4> Cond; |
440 | 4.02M | DebugLoc DL = findBranchDebugLoc(); |
441 | 4.02M | bool B = TII->analyzeBranch(*this, TBB, FBB, Cond); |
442 | 4.02M | (void) B; |
443 | 4.02M | assert(!B && "UpdateTerminators requires analyzable predecessors!"); |
444 | 4.02M | if (Cond.empty()4.02M ) { |
445 | 1.11M | if (TBB1.11M ) { |
446 | 292k | // The block has an unconditional branch. If its successor is now its |
447 | 292k | // layout successor, delete the branch. |
448 | 292k | if (isLayoutSuccessor(TBB)) |
449 | 93.4k | TII->removeBranch(*this); |
450 | 1.11M | } else { |
451 | 822k | // The block has an unconditional fallthrough. If its successor is not its |
452 | 822k | // layout successor, insert a branch. First we have to locate the only |
453 | 822k | // non-landing-pad successor, as that is the fallthrough block. |
454 | 1.66M | for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE1.66M ; ++SI845k ) { |
455 | 845k | if ((*SI)->isEHPad()) |
456 | 22.7k | continue; |
457 | 845k | assert(!TBB && "Found more than one non-landing-pad successor!"); |
458 | 822k | TBB = *SI; |
459 | 822k | } |
460 | 822k | |
461 | 822k | // If there is no non-landing-pad successor, the block has no fall-through |
462 | 822k | // edges to be concerned with. |
463 | 822k | if (!TBB) |
464 | 0 | return; |
465 | 822k | |
466 | 822k | // Finally update the unconditional successor to be reached via a branch |
467 | 822k | // if it would not be reached by fallthrough. |
468 | 822k | if (822k !isLayoutSuccessor(TBB)822k ) |
469 | 97.1k | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
470 | 822k | } |
471 | 1.11M | return; |
472 | 2.91M | } |
473 | 2.91M | |
474 | 2.91M | if (2.91M FBB2.91M ) { |
475 | 589k | // The block has a non-fallthrough conditional branch. If one of its |
476 | 589k | // successors is its layout successor, rewrite it to a fallthrough |
477 | 589k | // conditional branch. |
478 | 589k | if (isLayoutSuccessor(TBB)589k ) { |
479 | 380k | if (TII->reverseBranchCondition(Cond)) |
480 | 16 | return; |
481 | 380k | TII->removeBranch(*this); |
482 | 380k | TII->insertBranch(*this, FBB, nullptr, Cond, DL); |
483 | 589k | } else if (208k isLayoutSuccessor(FBB)208k ) { |
484 | 113k | TII->removeBranch(*this); |
485 | 113k | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
486 | 113k | } |
487 | 589k | return; |
488 | 2.32M | } |
489 | 2.32M | |
490 | 2.32M | // Walk through the successors and find the successor which is not a landing |
491 | 2.32M | // pad and is not the conditional branch destination (in TBB) as the |
492 | 2.32M | // fallthrough successor. |
493 | 2.32M | MachineBasicBlock *FallthroughBB = nullptr; |
494 | 6.97M | for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE6.97M ; ++SI4.65M ) { |
495 | 4.65M | if ((*SI)->isEHPad() || 4.65M *SI == TBB4.65M ) |
496 | 2.32M | continue; |
497 | 4.65M | assert(!FallthroughBB && "Found more than one fallthrough successor."); |
498 | 2.32M | FallthroughBB = *SI; |
499 | 2.32M | } |
500 | 2.32M | |
501 | 2.32M | if (!FallthroughBB2.32M ) { |
502 | 17 | if (canFallThrough()17 ) { |
503 | 16 | // We fallthrough to the same basic block as the conditional jump targets. |
504 | 16 | // Remove the conditional jump, leaving unconditional fallthrough. |
505 | 16 | // FIXME: This does not seem like a reasonable pattern to support, but it |
506 | 16 | // has been seen in the wild coming out of degenerate ARM test cases. |
507 | 16 | TII->removeBranch(*this); |
508 | 16 | |
509 | 16 | // Finally update the unconditional successor to be reached via a branch if |
510 | 16 | // it would not be reached by fallthrough. |
511 | 16 | if (!isLayoutSuccessor(TBB)) |
512 | 0 | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
513 | 16 | return; |
514 | 16 | } |
515 | 1 | |
516 | 1 | // We enter here iff exactly one successor is TBB which cannot fallthrough |
517 | 1 | // and the rest successors if any are EHPads. In this case, we need to |
518 | 1 | // change the conditional branch into unconditional branch. |
519 | 1 | TII->removeBranch(*this); |
520 | 1 | Cond.clear(); |
521 | 1 | TII->insertBranch(*this, TBB, nullptr, Cond, DL); |
522 | 1 | return; |
523 | 1 | } |
524 | 2.32M | |
525 | 2.32M | // The block has a fallthrough conditional branch. |
526 | 2.32M | if (2.32M isLayoutSuccessor(TBB)2.32M ) { |
527 | 408k | if (TII->reverseBranchCondition(Cond)408k ) { |
528 | 15 | // We can't reverse the condition, add an unconditional branch. |
529 | 15 | Cond.clear(); |
530 | 15 | TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL); |
531 | 15 | return; |
532 | 15 | } |
533 | 408k | TII->removeBranch(*this); |
534 | 408k | TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL); |
535 | 2.32M | } else if (1.91M !isLayoutSuccessor(FallthroughBB)1.91M ) { |
536 | 191k | TII->removeBranch(*this); |
537 | 191k | TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL); |
538 | 191k | } |
539 | 4.05M | } |
540 | | |
541 | 0 | void MachineBasicBlock::validateSuccProbs() const { |
542 | | #ifndef NDEBUG |
543 | | int64_t Sum = 0; |
544 | | for (auto Prob : Probs) |
545 | | Sum += Prob.getNumerator(); |
546 | | // Due to precision issue, we assume that the sum of probabilities is one if |
547 | | // the difference between the sum of their numerators and the denominator is |
548 | | // no greater than the number of successors. |
549 | | assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <= |
550 | | Probs.size() && |
551 | | "The sum of successors's probabilities exceeds one."); |
552 | | #endif // NDEBUG |
553 | | } |
554 | | |
555 | | void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, |
556 | 8.63M | BranchProbability Prob) { |
557 | 8.63M | // Probability list is either empty (if successor list isn't empty, this means |
558 | 8.63M | // disabled optimization) or has the same size as successor list. |
559 | 8.63M | if (!(Probs.empty() && 8.63M !Successors.empty()5.61M )) |
560 | 8.63M | Probs.push_back(Prob); |
561 | 8.63M | Successors.push_back(Succ); |
562 | 8.63M | Succ->addPredecessor(this); |
563 | 8.63M | } |
564 | | |
565 | 3.10k | void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) { |
566 | 3.10k | // We need to make sure probability list is either empty or has the same size |
567 | 3.10k | // of successor list. When this function is called, we can safely delete all |
568 | 3.10k | // probability in the list. |
569 | 3.10k | Probs.clear(); |
570 | 3.10k | Successors.push_back(Succ); |
571 | 3.10k | Succ->addPredecessor(this); |
572 | 3.10k | } |
573 | | |
574 | | void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ, |
575 | 540k | bool NormalizeSuccProbs) { |
576 | 540k | succ_iterator I = find(Successors, Succ); |
577 | 540k | removeSuccessor(I, NormalizeSuccProbs); |
578 | 540k | } |
579 | | |
580 | | MachineBasicBlock::succ_iterator |
581 | 1.56M | MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) { |
582 | 1.56M | assert(I != Successors.end() && "Not a current successor!"); |
583 | 1.56M | |
584 | 1.56M | // If probability list is empty it means we don't use it (disabled |
585 | 1.56M | // optimization). |
586 | 1.56M | if (!Probs.empty()1.56M ) { |
587 | 1.56M | probability_iterator WI = getProbabilityIterator(I); |
588 | 1.56M | Probs.erase(WI); |
589 | 1.56M | if (NormalizeSuccProbs) |
590 | 26.2k | normalizeSuccProbs(); |
591 | 1.56M | } |
592 | 1.56M | |
593 | 1.56M | (*I)->removePredecessor(this); |
594 | 1.56M | return Successors.erase(I); |
595 | 1.56M | } |
596 | | |
597 | | void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, |
598 | 870k | MachineBasicBlock *New) { |
599 | 870k | if (Old == New) |
600 | 0 | return; |
601 | 870k | |
602 | 870k | succ_iterator E = succ_end(); |
603 | 870k | succ_iterator NewI = E; |
604 | 870k | succ_iterator OldI = E; |
605 | 2.60M | for (succ_iterator I = succ_begin(); I != E2.60M ; ++I1.73M ) { |
606 | 1.73M | if (*I == Old1.73M ) { |
607 | 870k | OldI = I; |
608 | 870k | if (NewI != E) |
609 | 743 | break; |
610 | 1.73M | } |
611 | 1.73M | if (1.73M *I == New1.73M ) { |
612 | 1.78k | NewI = I; |
613 | 1.78k | if (OldI != E) |
614 | 1.04k | break; |
615 | 1.78k | } |
616 | 1.73M | } |
617 | 870k | assert(OldI != E && "Old is not a successor of this block"); |
618 | 870k | |
619 | 870k | // If New isn't already a successor, let it take Old's place. |
620 | 870k | if (NewI == E870k ) { |
621 | 868k | Old->removePredecessor(this); |
622 | 868k | New->addPredecessor(this); |
623 | 868k | *OldI = New; |
624 | 868k | return; |
625 | 868k | } |
626 | 1.78k | |
627 | 1.78k | // New is already a successor. |
628 | 1.78k | // Update its probability instead of adding a duplicate edge. |
629 | 1.78k | if (1.78k !Probs.empty()1.78k ) { |
630 | 1.78k | auto ProbIter = getProbabilityIterator(NewI); |
631 | 1.78k | if (!ProbIter->isUnknown()) |
632 | 1.76k | *ProbIter += *getProbabilityIterator(OldI); |
633 | 1.78k | } |
634 | 870k | removeSuccessor(OldI); |
635 | 870k | } |
636 | | |
637 | 9.50M | void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) { |
638 | 9.50M | Predecessors.push_back(Pred); |
639 | 9.50M | } |
640 | | |
641 | 2.42M | void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) { |
642 | 2.42M | pred_iterator I = find(Predecessors, Pred); |
643 | 2.42M | assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); |
644 | 2.42M | Predecessors.erase(I); |
645 | 2.42M | } |
646 | | |
647 | 193k | void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) { |
648 | 193k | if (this == FromMBB) |
649 | 0 | return; |
650 | 193k | |
651 | 395k | while (193k !FromMBB->succ_empty()395k ) { |
652 | 202k | MachineBasicBlock *Succ = *FromMBB->succ_begin(); |
653 | 202k | |
654 | 202k | // If probability list is empty it means we don't use it (disabled optimization). |
655 | 202k | if (!FromMBB->Probs.empty()202k ) { |
656 | 202k | auto Prob = *FromMBB->Probs.begin(); |
657 | 202k | addSuccessor(Succ, Prob); |
658 | 202k | } else |
659 | 24 | addSuccessorWithoutProb(Succ); |
660 | 202k | |
661 | 202k | FromMBB->removeSuccessor(Succ); |
662 | 202k | } |
663 | 193k | } |
664 | | |
665 | | void |
666 | 32.8k | MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) { |
667 | 32.8k | if (this == FromMBB) |
668 | 0 | return; |
669 | 32.8k | |
670 | 63.5k | while (32.8k !FromMBB->succ_empty()63.5k ) { |
671 | 30.7k | MachineBasicBlock *Succ = *FromMBB->succ_begin(); |
672 | 30.7k | if (!FromMBB->Probs.empty()30.7k ) { |
673 | 30.7k | auto Prob = *FromMBB->Probs.begin(); |
674 | 30.7k | addSuccessor(Succ, Prob); |
675 | 30.7k | } else |
676 | 24 | addSuccessorWithoutProb(Succ); |
677 | 30.7k | FromMBB->removeSuccessor(Succ); |
678 | 30.7k | |
679 | 30.7k | // Fix up any PHI nodes in the successor. |
680 | 30.7k | for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(), |
681 | 54.7k | ME = Succ->instr_end(); MI != ME && 54.7k MI->isPHI()51.4k ; ++MI23.9k ) |
682 | 96.7k | for (unsigned i = 2, e = MI->getNumOperands()+1; 23.9k i != e96.7k ; i += 272.8k ) { |
683 | 72.8k | MachineOperand &MO = MI->getOperand(i); |
684 | 72.8k | if (MO.getMBB() == FromMBB) |
685 | 23.9k | MO.setMBB(this); |
686 | 23.9k | } |
687 | 30.7k | } |
688 | 32.8k | normalizeSuccProbs(); |
689 | 32.8k | } |
690 | | |
691 | 710 | bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const { |
692 | 710 | return is_contained(predecessors(), MBB); |
693 | 710 | } |
694 | | |
695 | 52.6M | bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { |
696 | 52.6M | return is_contained(successors(), MBB); |
697 | 52.6M | } |
698 | | |
699 | 23.2M | bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { |
700 | 23.2M | MachineFunction::const_iterator I(this); |
701 | 23.2M | return std::next(I) == MachineFunction::const_iterator(MBB); |
702 | 23.2M | } |
703 | | |
704 | 26.9M | MachineBasicBlock *MachineBasicBlock::getFallThrough() { |
705 | 26.9M | MachineFunction::iterator Fallthrough = getIterator(); |
706 | 26.9M | ++Fallthrough; |
707 | 26.9M | // If FallthroughBlock is off the end of the function, it can't fall through. |
708 | 26.9M | if (Fallthrough == getParent()->end()) |
709 | 1.93M | return nullptr; |
710 | 25.0M | |
711 | 25.0M | // If FallthroughBlock isn't a successor, no fallthrough is possible. |
712 | 25.0M | if (25.0M !isSuccessor(&*Fallthrough)25.0M ) |
713 | 6.93M | return nullptr; |
714 | 18.1M | |
715 | 18.1M | // Analyze the branches, if any, at the end of the block. |
716 | 18.1M | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
717 | 18.1M | SmallVector<MachineOperand, 4> Cond; |
718 | 18.1M | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
719 | 18.1M | if (TII->analyzeBranch(*this, TBB, FBB, Cond)18.1M ) { |
720 | 106k | // If we couldn't analyze the branch, examine the last instruction. |
721 | 106k | // If the block doesn't end in a known control barrier, assume fallthrough |
722 | 106k | // is possible. The isPredicated check is needed because this code can be |
723 | 106k | // called during IfConversion, where an instruction which is normally a |
724 | 106k | // Barrier is predicated and thus no longer an actual control barrier. |
725 | 106k | return (empty() || !back().isBarrier()106k || TII->isPredicated(back())102k ) |
726 | 3.51k | ? &*Fallthrough |
727 | 102k | : nullptr; |
728 | 106k | } |
729 | 18.0M | |
730 | 18.0M | // If there is no branch, control always falls through. |
731 | 18.0M | if (18.0M !TBB18.0M ) return &*Fallthrough4.85M ; |
732 | 13.1M | |
733 | 13.1M | // If there is some explicit branch to the fallthrough block, it can obviously |
734 | 13.1M | // reach, even though the branch should get folded to fall through implicitly. |
735 | 13.1M | if (13.1M MachineFunction::iterator(TBB) == Fallthrough || |
736 | 12.9M | MachineFunction::iterator(FBB) == Fallthrough) |
737 | 2.28M | return &*Fallthrough; |
738 | 10.8M | |
739 | 10.8M | // If it's an unconditional branch to some block not the fall through, it |
740 | 10.8M | // doesn't fall through. |
741 | 10.8M | if (10.8M Cond.empty()10.8M ) return nullptr13.5k ; |
742 | 10.8M | |
743 | 10.8M | // Otherwise, if it is conditional and has no explicit false block, it falls |
744 | 10.8M | // through. |
745 | 10.8M | return (FBB == nullptr) ? 10.8M &*Fallthrough10.8M : nullptr0 ; |
746 | 26.9M | } |
747 | | |
748 | 26.9M | bool MachineBasicBlock::canFallThrough() { |
749 | 26.9M | return getFallThrough() != nullptr; |
750 | 26.9M | } |
751 | | |
752 | | MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, |
753 | 470k | Pass &P) { |
754 | 470k | if (!canSplitCriticalEdge(Succ)) |
755 | 2.63k | return nullptr; |
756 | 467k | |
757 | 467k | MachineFunction *MF = getParent(); |
758 | 467k | DebugLoc DL; // FIXME: this is nowhere |
759 | 467k | |
760 | 467k | MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); |
761 | 467k | MF->insert(std::next(MachineFunction::iterator(this)), NMBB); |
762 | 467k | DEBUG(dbgs() << "Splitting critical edge:" |
763 | 467k | " BB#" << getNumber() |
764 | 467k | << " -- BB#" << NMBB->getNumber() |
765 | 467k | << " -- BB#" << Succ->getNumber() << '\n'); |
766 | 467k | |
767 | 467k | LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>(); |
768 | 467k | SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>(); |
769 | 467k | if (LIS) |
770 | 0 | LIS->insertMBBInMaps(NMBB); |
771 | 467k | else if (467k Indexes467k ) |
772 | 0 | Indexes->insertMBBInMaps(NMBB); |
773 | 467k | |
774 | 467k | // On some targets like Mips, branches may kill virtual registers. Make sure |
775 | 467k | // that LiveVariables is properly updated after updateTerminator replaces the |
776 | 467k | // terminators. |
777 | 467k | LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>(); |
778 | 467k | |
779 | 467k | // Collect a list of virtual registers killed by the terminators. |
780 | 467k | SmallVector<unsigned, 4> KilledRegs; |
781 | 467k | if (LV) |
782 | 161k | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
783 | 472k | I != E472k ; ++I311k ) { |
784 | 311k | MachineInstr *MI = &*I; |
785 | 311k | for (MachineInstr::mop_iterator OI = MI->operands_begin(), |
786 | 911k | OE = MI->operands_end(); OI != OE911k ; ++OI600k ) { |
787 | 600k | if (!OI->isReg() || 600k OI->getReg() == 0163k || |
788 | 600k | !OI->isUse()161k || !OI->isKill()161k || OI->isUndef()145k ) |
789 | 455k | continue; |
790 | 145k | unsigned Reg = OI->getReg(); |
791 | 145k | if (TargetRegisterInfo::isPhysicalRegister(Reg) || |
792 | 145k | LV->getVarInfo(Reg).removeKill(*MI)26.8k ) { |
793 | 145k | KilledRegs.push_back(Reg); |
794 | 145k | DEBUG(dbgs() << "Removing terminator kill: " << *MI); |
795 | 145k | OI->setIsKill(false); |
796 | 145k | } |
797 | 600k | } |
798 | 161k | } |
799 | 467k | |
800 | 467k | SmallVector<unsigned, 4> UsedRegs; |
801 | 467k | if (LIS467k ) { |
802 | 0 | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
803 | 0 | I != E0 ; ++I0 ) { |
804 | 0 | MachineInstr *MI = &*I; |
805 | 0 |
|
806 | 0 | for (MachineInstr::mop_iterator OI = MI->operands_begin(), |
807 | 0 | OE = MI->operands_end(); OI != OE0 ; ++OI0 ) { |
808 | 0 | if (!OI->isReg() || 0 OI->getReg() == 00 ) |
809 | 0 | continue; |
810 | 0 |
|
811 | 0 | unsigned Reg = OI->getReg(); |
812 | 0 | if (!is_contained(UsedRegs, Reg)) |
813 | 0 | UsedRegs.push_back(Reg); |
814 | 0 | } |
815 | 0 | } |
816 | 0 | } |
817 | 467k | |
818 | 467k | ReplaceUsesOfBlockWith(Succ, NMBB); |
819 | 467k | |
820 | 467k | // If updateTerminator() removes instructions, we need to remove them from |
821 | 467k | // SlotIndexes. |
822 | 467k | SmallVector<MachineInstr*, 4> Terminators; |
823 | 467k | if (Indexes467k ) { |
824 | 0 | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
825 | 0 | I != E0 ; ++I0 ) |
826 | 0 | Terminators.push_back(&*I); |
827 | 0 | } |
828 | 467k | |
829 | 467k | updateTerminator(); |
830 | 467k | |
831 | 467k | if (Indexes467k ) { |
832 | 0 | SmallVector<MachineInstr*, 4> NewTerminators; |
833 | 0 | for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); |
834 | 0 | I != E0 ; ++I0 ) |
835 | 0 | NewTerminators.push_back(&*I); |
836 | 0 |
|
837 | 0 | for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(), |
838 | 0 | E = Terminators.end(); I != E0 ; ++I0 ) { |
839 | 0 | if (!is_contained(NewTerminators, *I)) |
840 | 0 | Indexes->removeMachineInstrFromMaps(**I); |
841 | 0 | } |
842 | 0 | } |
843 | 467k | |
844 | 467k | // Insert unconditional "jump Succ" instruction in NMBB if necessary. |
845 | 467k | NMBB->addSuccessor(Succ); |
846 | 467k | if (!NMBB->isLayoutSuccessor(Succ)467k ) { |
847 | 428k | SmallVector<MachineOperand, 4> Cond; |
848 | 428k | const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); |
849 | 428k | TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL); |
850 | 428k | |
851 | 428k | if (Indexes428k ) { |
852 | 0 | for (MachineInstr &MI : NMBB->instrs()) { |
853 | 0 | // Some instructions may have been moved to NMBB by updateTerminator(), |
854 | 0 | // so we first remove any instruction that already has an index. |
855 | 0 | if (Indexes->hasIndex(MI)) |
856 | 0 | Indexes->removeMachineInstrFromMaps(MI); |
857 | 0 | Indexes->insertMachineInstrInMaps(MI); |
858 | 0 | } |
859 | 0 | } |
860 | 428k | } |
861 | 467k | |
862 | 467k | // Fix PHI nodes in Succ so they refer to NMBB instead of this |
863 | 467k | for (MachineBasicBlock::instr_iterator |
864 | 467k | i = Succ->instr_begin(),e = Succ->instr_end(); |
865 | 1.04M | i != e && 1.04M i->isPHI()1.04M ; ++i575k ) |
866 | 7.01M | for (unsigned ni = 1, ne = i->getNumOperands(); 575k ni != ne7.01M ; ni += 26.44M ) |
867 | 6.44M | if (6.44M i->getOperand(ni+1).getMBB() == this6.44M ) |
868 | 579k | i->getOperand(ni+1).setMBB(NMBB); |
869 | 467k | |
870 | 467k | // Inherit live-ins from the successor |
871 | 467k | for (const auto &LI : Succ->liveins()) |
872 | 268 | NMBB->addLiveIn(LI); |
873 | 467k | |
874 | 467k | // Update LiveVariables. |
875 | 467k | const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); |
876 | 467k | if (LV467k ) { |
877 | 161k | // Restore kills of virtual registers that were killed by the terminators. |
878 | 306k | while (!KilledRegs.empty()306k ) { |
879 | 145k | unsigned Reg = KilledRegs.pop_back_val(); |
880 | 145k | for (instr_iterator I = instr_end(), E = instr_begin(); I != E145k ;) { |
881 | 145k | if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false)) |
882 | 11 | continue; |
883 | 145k | if (145k TargetRegisterInfo::isVirtualRegister(Reg)145k ) |
884 | 26.8k | LV->getVarInfo(Reg).Kills.push_back(&*I); |
885 | 145k | DEBUG(dbgs() << "Restored terminator kill: " << *I); |
886 | 145k | break; |
887 | 145k | } |
888 | 145k | } |
889 | 161k | // Update relevant live-through information. |
890 | 161k | LV->addNewBlock(NMBB, this, Succ); |
891 | 161k | } |
892 | 467k | |
893 | 467k | if (LIS467k ) { |
894 | 0 | // After splitting the edge and updating SlotIndexes, live intervals may be |
895 | 0 | // in one of two situations, depending on whether this block was the last in |
896 | 0 | // the function. If the original block was the last in the function, all |
897 | 0 | // live intervals will end prior to the beginning of the new split block. If |
898 | 0 | // the original block was not at the end of the function, all live intervals |
899 | 0 | // will extend to the end of the new split block. |
900 | 0 |
|
901 | 0 | bool isLastMBB = |
902 | 0 | std::next(MachineFunction::iterator(NMBB)) == getParent()->end(); |
903 | 0 |
|
904 | 0 | SlotIndex StartIndex = Indexes->getMBBEndIdx(this); |
905 | 0 | SlotIndex PrevIndex = StartIndex.getPrevSlot(); |
906 | 0 | SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB); |
907 | 0 |
|
908 | 0 | // Find the registers used from NMBB in PHIs in Succ. |
909 | 0 | SmallSet<unsigned, 8> PHISrcRegs; |
910 | 0 | for (MachineBasicBlock::instr_iterator |
911 | 0 | I = Succ->instr_begin(), E = Succ->instr_end(); |
912 | 0 | I != E && 0 I->isPHI()0 ; ++I0 ) { |
913 | 0 | for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne0 ; ni += 20 ) { |
914 | 0 | if (I->getOperand(ni+1).getMBB() == NMBB0 ) { |
915 | 0 | MachineOperand &MO = I->getOperand(ni); |
916 | 0 | unsigned Reg = MO.getReg(); |
917 | 0 | PHISrcRegs.insert(Reg); |
918 | 0 | if (MO.isUndef()) |
919 | 0 | continue; |
920 | 0 |
|
921 | 0 | LiveInterval &LI = LIS->getInterval(Reg); |
922 | 0 | VNInfo *VNI = LI.getVNInfoAt(PrevIndex); |
923 | 0 | assert(VNI && |
924 | 0 | "PHI sources should be live out of their predecessors."); |
925 | 0 | LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); |
926 | 0 | } |
927 | 0 | } |
928 | 0 | } |
929 | 0 |
|
930 | 0 | MachineRegisterInfo *MRI = &getParent()->getRegInfo(); |
931 | 0 | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e0 ; ++i0 ) { |
932 | 0 | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
933 | 0 | if (PHISrcRegs.count(Reg) || 0 !LIS->hasInterval(Reg)0 ) |
934 | 0 | continue; |
935 | 0 |
|
936 | 0 | LiveInterval &LI = LIS->getInterval(Reg); |
937 | 0 | if (!LI.liveAt(PrevIndex)) |
938 | 0 | continue; |
939 | 0 |
|
940 | 0 | bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ)); |
941 | 0 | if (isLiveOut && 0 isLastMBB0 ) { |
942 | 0 | VNInfo *VNI = LI.getVNInfoAt(PrevIndex); |
943 | 0 | assert(VNI && "LiveInterval should have VNInfo where it is live."); |
944 | 0 | LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); |
945 | 0 | } else if (0 !isLiveOut && 0 !isLastMBB0 ) { |
946 | 0 | LI.removeSegment(StartIndex, EndIndex); |
947 | 0 | } |
948 | 0 | } |
949 | 0 |
|
950 | 0 | // Update all intervals for registers whose uses may have been modified by |
951 | 0 | // updateTerminator(). |
952 | 0 | LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs); |
953 | 0 | } |
954 | 467k | |
955 | 467k | if (MachineDominatorTree *MDT = |
956 | 467k | P.getAnalysisIfAvailable<MachineDominatorTree>()) |
957 | 467k | MDT->recordSplitCriticalEdge(this, Succ, NMBB); |
958 | 467k | |
959 | 467k | if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>()) |
960 | 467k | if (MachineLoop *467k TIL467k = MLI->getLoopFor(this)) { |
961 | 141k | // If one or the other blocks were not in a loop, the new block is not |
962 | 141k | // either, and thus LI doesn't need to be updated. |
963 | 141k | if (MachineLoop *DestLoop141k = MLI->getLoopFor(Succ)) { |
964 | 96.1k | if (TIL == DestLoop96.1k ) { |
965 | 84.9k | // Both in the same loop, the NMBB joins loop. |
966 | 84.9k | DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); |
967 | 96.1k | } else if (11.2k TIL->contains(DestLoop)11.2k ) { |
968 | 365 | // Edge from an outer loop to an inner loop. Add to the outer loop. |
969 | 365 | TIL->addBasicBlockToLoop(NMBB, MLI->getBase()); |
970 | 11.2k | } else if (10.8k DestLoop->contains(TIL)10.8k ) { |
971 | 10.7k | // Edge from an inner loop to an outer loop. Add to the outer loop. |
972 | 10.7k | DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); |
973 | 10.8k | } else { |
974 | 70 | // Edge from two loops with no containment relation. Because these |
975 | 70 | // are natural loops, we know that the destination block must be the |
976 | 70 | // header of its loop (adding a branch into a loop elsewhere would |
977 | 70 | // create an irreducible loop). |
978 | 70 | assert(DestLoop->getHeader() == Succ && |
979 | 70 | "Should not create irreducible loops!"); |
980 | 70 | if (MachineLoop *P = DestLoop->getParentLoop()) |
981 | 32 | P->addBasicBlockToLoop(NMBB, MLI->getBase()); |
982 | 11.2k | } |
983 | 96.1k | } |
984 | 467k | } |
985 | 470k | |
986 | 470k | return NMBB; |
987 | 470k | } |
988 | | |
989 | | bool MachineBasicBlock::canSplitCriticalEdge( |
990 | 470k | const MachineBasicBlock *Succ) const { |
991 | 470k | // Splitting the critical edge to a landing pad block is non-trivial. Don't do |
992 | 470k | // it in this generic function. |
993 | 470k | if (Succ->isEHPad()) |
994 | 0 | return false; |
995 | 470k | |
996 | 470k | const MachineFunction *MF = getParent(); |
997 | 470k | |
998 | 470k | // Performance might be harmed on HW that implements branching using exec mask |
999 | 470k | // where both sides of the branches are always executed. |
1000 | 470k | if (MF->getTarget().requiresStructuredCFG()) |
1001 | 45 | return false; |
1002 | 470k | |
1003 | 470k | // We may need to update this's terminator, but we can't do that if |
1004 | 470k | // AnalyzeBranch fails. If this uses a jump table, we won't touch it. |
1005 | 470k | const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); |
1006 | 470k | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
1007 | 470k | SmallVector<MachineOperand, 4> Cond; |
1008 | 470k | // AnalyzeBanch should modify this, since we did not allow modification. |
1009 | 470k | if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond, |
1010 | 470k | /*AllowModify*/ false)) |
1011 | 2.58k | return false; |
1012 | 467k | |
1013 | 467k | // Avoid bugpoint weirdness: A block may end with a conditional branch but |
1014 | 467k | // jumps to the same MBB is either case. We have duplicate CFG edges in that |
1015 | 467k | // case that we can't handle. Since this never happens in properly optimized |
1016 | 467k | // code, just skip those edges. |
1017 | 467k | if (467k TBB && 467k TBB == FBB467k ) { |
1018 | 0 | DEBUG(dbgs() << "Won't split critical edge after degenerate BB#" |
1019 | 0 | << getNumber() << '\n'); |
1020 | 0 | return false; |
1021 | 0 | } |
1022 | 467k | return true; |
1023 | 467k | } |
1024 | | |
1025 | | /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's |
1026 | | /// neighboring instructions so the bundle won't be broken by removing MI. |
1027 | 3.91M | static void unbundleSingleMI(MachineInstr *MI) { |
1028 | 3.91M | // Removing the first instruction in a bundle. |
1029 | 3.91M | if (MI->isBundledWithSucc() && 3.91M !MI->isBundledWithPred()1.23k ) |
1030 | 6 | MI->unbundleFromSucc(); |
1031 | 3.91M | // Removing the last instruction in a bundle. |
1032 | 3.91M | if (MI->isBundledWithPred() && 3.91M !MI->isBundledWithSucc()5.03k ) |
1033 | 3.80k | MI->unbundleFromPred(); |
1034 | 3.91M | // If MI is not bundled, or if it is internal to a bundle, the neighbor flags |
1035 | 3.91M | // are already fine. |
1036 | 3.91M | } |
1037 | | |
1038 | | MachineBasicBlock::instr_iterator |
1039 | 3.91M | MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) { |
1040 | 3.91M | unbundleSingleMI(&*I); |
1041 | 3.91M | return Insts.erase(I); |
1042 | 3.91M | } |
1043 | | |
1044 | 7 | MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) { |
1045 | 7 | unbundleSingleMI(MI); |
1046 | 7 | MI->clearFlag(MachineInstr::BundledPred); |
1047 | 7 | MI->clearFlag(MachineInstr::BundledSucc); |
1048 | 7 | return Insts.remove(MI); |
1049 | 7 | } |
1050 | | |
1051 | | MachineBasicBlock::instr_iterator |
1052 | 48.2k | MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) { |
1053 | 48.2k | assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && |
1054 | 48.2k | "Cannot insert instruction with bundle flags"); |
1055 | 48.2k | // Set the bundle flags when inserting inside a bundle. |
1056 | 48.2k | if (I != instr_end() && 48.2k I->isBundledWithPred()48.1k ) { |
1057 | 5.03k | MI->setFlag(MachineInstr::BundledPred); |
1058 | 5.03k | MI->setFlag(MachineInstr::BundledSucc); |
1059 | 5.03k | } |
1060 | 48.2k | return Insts.insert(I, MI); |
1061 | 48.2k | } |
1062 | | |
1063 | | /// This method unlinks 'this' from the containing function, and returns it, but |
1064 | | /// does not delete it. |
1065 | 0 | MachineBasicBlock *MachineBasicBlock::removeFromParent() { |
1066 | 0 | assert(getParent() && "Not embedded in a function!"); |
1067 | 0 | getParent()->remove(this); |
1068 | 0 | return this; |
1069 | 0 | } |
1070 | | |
1071 | | /// This method unlinks 'this' from the containing function, and deletes it. |
1072 | 168k | void MachineBasicBlock::eraseFromParent() { |
1073 | 168k | assert(getParent() && "Not embedded in a function!"); |
1074 | 168k | getParent()->erase(this); |
1075 | 168k | } |
1076 | | |
1077 | | /// Given a machine basic block that branched to 'Old', change the code and CFG |
1078 | | /// so that it branches to 'New' instead. |
1079 | | void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, |
1080 | 832k | MachineBasicBlock *New) { |
1081 | 832k | assert(Old != New && "Cannot replace self with self!"); |
1082 | 832k | |
1083 | 832k | MachineBasicBlock::instr_iterator I = instr_end(); |
1084 | 2.35M | while (I != instr_begin()2.35M ) { |
1085 | 2.31M | --I; |
1086 | 2.31M | if (!I->isTerminator()2.31M ) break793k ; |
1087 | 1.51M | |
1088 | 1.51M | // Scan the operands of this machine instruction, replacing any uses of Old |
1089 | 1.51M | // with New. |
1090 | 4.30M | for (unsigned i = 0, e = I->getNumOperands(); 1.51M i != e4.30M ; ++i2.78M ) |
1091 | 2.78M | if (2.78M I->getOperand(i).isMBB() && |
1092 | 1.51M | I->getOperand(i).getMBB() == Old) |
1093 | 775k | I->getOperand(i).setMBB(New); |
1094 | 2.31M | } |
1095 | 832k | |
1096 | 832k | // Update the successor information. |
1097 | 832k | replaceSuccessor(Old, New); |
1098 | 832k | } |
1099 | | |
1100 | | /// Various pieces of code can cause excess edges in the CFG to be inserted. If |
1101 | | /// we have proven that MBB can only branch to DestA and DestB, remove any other |
1102 | | /// MBB successors from the CFG. DestA and DestB can be null. |
1103 | | /// |
1104 | | /// Besides DestA and DestB, retain other edges leading to LandingPads |
1105 | | /// (currently there can be only one; we don't check or require that here). |
1106 | | /// Note it is possible that DestA and/or DestB are LandingPads. |
1107 | | bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, |
1108 | | MachineBasicBlock *DestB, |
1109 | 26.2M | bool IsCond) { |
1110 | 26.2M | // The values of DestA and DestB frequently come from a call to the |
1111 | 26.2M | // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial |
1112 | 26.2M | // values from there. |
1113 | 26.2M | // |
1114 | 26.2M | // 1. If both DestA and DestB are null, then the block ends with no branches |
1115 | 26.2M | // (it falls through to its successor). |
1116 | 26.2M | // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends |
1117 | 26.2M | // with only an unconditional branch. |
1118 | 26.2M | // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends |
1119 | 26.2M | // with a conditional branch that falls through to a successor (DestB). |
1120 | 26.2M | // 4. If DestA and DestB is set and IsCond is true, then the block ends with a |
1121 | 26.2M | // conditional branch followed by an unconditional branch. DestA is the |
1122 | 26.2M | // 'true' destination and DestB is the 'false' destination. |
1123 | 26.2M | |
1124 | 26.2M | bool Changed = false; |
1125 | 26.2M | |
1126 | 26.2M | MachineBasicBlock *FallThru = getNextNode(); |
1127 | 26.2M | |
1128 | 26.2M | if (!DestA && 26.2M !DestB5.91M ) { |
1129 | 5.91M | // Block falls through to successor. |
1130 | 5.91M | DestA = FallThru; |
1131 | 5.91M | DestB = FallThru; |
1132 | 26.2M | } else if (20.3M DestA && 20.3M !DestB20.3M ) { |
1133 | 16.7M | if (IsCond) |
1134 | 16.7M | // Block ends in conditional jump that falls through to successor. |
1135 | 11.9M | DestB = FallThru; |
1136 | 20.3M | } else { |
1137 | 3.61M | assert(DestA && DestB && IsCond && |
1138 | 3.61M | "CFG in a bad state. Cannot correct CFG edges"); |
1139 | 3.61M | } |
1140 | 26.2M | |
1141 | 26.2M | // Remove superfluous edges. I.e., those which aren't destinations of this |
1142 | 26.2M | // basic block, duplicate edges, or landing pads. |
1143 | 26.2M | SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs; |
1144 | 26.2M | MachineBasicBlock::succ_iterator SI = succ_begin(); |
1145 | 68.1M | while (SI != succ_end()68.1M ) { |
1146 | 41.8M | const MachineBasicBlock *MBB = *SI; |
1147 | 41.8M | if (!SeenMBBs.insert(MBB).second || |
1148 | 41.8M | (MBB != DestA && 41.8M MBB != DestB15.7M && !MBB->isEHPad()192k )) { |
1149 | 1.33k | // This is a superfluous edge, remove it. |
1150 | 1.33k | SI = removeSuccessor(SI); |
1151 | 1.33k | Changed = true; |
1152 | 41.8M | } else { |
1153 | 41.8M | ++SI; |
1154 | 41.8M | } |
1155 | 41.8M | } |
1156 | 26.2M | |
1157 | 26.2M | if (Changed) |
1158 | 1.33k | normalizeSuccProbs(); |
1159 | 26.2M | return Changed; |
1160 | 26.2M | } |
1161 | | |
1162 | | /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE |
1163 | | /// instructions. Return UnknownLoc if there is none. |
1164 | | DebugLoc |
1165 | 403k | MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { |
1166 | 403k | // Skip debug declarations, we don't want a DebugLoc from them. |
1167 | 403k | MBBI = skipDebugInstructionsForward(MBBI, instr_end()); |
1168 | 403k | if (MBBI != instr_end()) |
1169 | 403k | return MBBI->getDebugLoc(); |
1170 | 507 | return {}; |
1171 | 507 | } |
1172 | | |
1173 | | /// Find and return the merged DebugLoc of the branch instructions of the block. |
1174 | | /// Return UnknownLoc if there is none. |
1175 | | DebugLoc |
1176 | 16.0M | MachineBasicBlock::findBranchDebugLoc() { |
1177 | 16.0M | DebugLoc DL; |
1178 | 16.0M | auto TI = getFirstTerminator(); |
1179 | 16.0M | while (TI != end() && 16.0M !TI->isBranch()13.3M ) |
1180 | 146 | ++TI; |
1181 | 16.0M | |
1182 | 16.0M | if (TI != end()16.0M ) { |
1183 | 13.3M | DL = TI->getDebugLoc(); |
1184 | 15.3M | for (++TI ; TI != end()15.3M ; ++TI2.01M ) |
1185 | 2.01M | if (2.01M TI->isBranch()2.01M ) |
1186 | 2.01M | DL = DILocation::getMergedLocation(DL, TI->getDebugLoc()); |
1187 | 13.3M | } |
1188 | 16.0M | return DL; |
1189 | 16.0M | } |
1190 | | |
1191 | | /// Return probability of the edge from this block to MBB. |
1192 | | BranchProbability |
1193 | 35.1M | MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const { |
1194 | 35.1M | if (Probs.empty()) |
1195 | 213 | return BranchProbability(1, succ_size()); |
1196 | 35.1M | |
1197 | 35.1M | const auto &Prob = *getProbabilityIterator(Succ); |
1198 | 35.1M | if (Prob.isUnknown()35.1M ) { |
1199 | 9.75M | // For unknown probabilities, collect the sum of all known ones, and evenly |
1200 | 9.75M | // ditribute the complemental of the sum to each unknown probability. |
1201 | 9.75M | unsigned KnownProbNum = 0; |
1202 | 9.75M | auto Sum = BranchProbability::getZero(); |
1203 | 11.5M | for (auto &P : Probs) { |
1204 | 11.5M | if (!P.isUnknown()11.5M ) { |
1205 | 11 | Sum += P; |
1206 | 11 | KnownProbNum++; |
1207 | 11 | } |
1208 | 11.5M | } |
1209 | 9.75M | return Sum.getCompl() / (Probs.size() - KnownProbNum); |
1210 | 9.75M | } else |
1211 | 25.3M | return Prob; |
1212 | 0 | } |
1213 | | |
1214 | | /// Set successor probability of a given iterator. |
1215 | | void MachineBasicBlock::setSuccProbability(succ_iterator I, |
1216 | 83.3k | BranchProbability Prob) { |
1217 | 83.3k | assert(!Prob.isUnknown()); |
1218 | 83.3k | if (Probs.empty()) |
1219 | 3 | return; |
1220 | 83.3k | *getProbabilityIterator(I) = Prob; |
1221 | 83.3k | } |
1222 | | |
1223 | | /// Return probability iterator corresonding to the I successor iterator |
1224 | | MachineBasicBlock::const_probability_iterator |
1225 | | MachineBasicBlock::getProbabilityIterator( |
1226 | 35.1M | MachineBasicBlock::const_succ_iterator I) const { |
1227 | 35.1M | assert(Probs.size() == Successors.size() && "Async probability list!"); |
1228 | 35.1M | const size_t index = std::distance(Successors.begin(), I); |
1229 | 35.1M | assert(index < Probs.size() && "Not a current successor!"); |
1230 | 35.1M | return Probs.begin() + index; |
1231 | 35.1M | } |
1232 | | |
1233 | | /// Return probability iterator corresonding to the I successor iterator. |
1234 | | MachineBasicBlock::probability_iterator |
1235 | 1.64M | MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) { |
1236 | 1.64M | assert(Probs.size() == Successors.size() && "Async probability list!"); |
1237 | 1.64M | const size_t index = std::distance(Successors.begin(), I); |
1238 | 1.64M | assert(index < Probs.size() && "Not a current successor!"); |
1239 | 1.64M | return Probs.begin() + index; |
1240 | 1.64M | } |
1241 | | |
1242 | | /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed |
1243 | | /// as of just before "MI". |
1244 | | /// |
1245 | | /// Search is localised to a neighborhood of |
1246 | | /// Neighborhood instructions before (searching for defs or kills) and N |
1247 | | /// instructions after (searching just for defs) MI. |
1248 | | MachineBasicBlock::LivenessQueryResult |
1249 | | MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, |
1250 | | unsigned Reg, const_iterator Before, |
1251 | 862 | unsigned Neighborhood) const { |
1252 | 862 | unsigned N = Neighborhood; |
1253 | 862 | |
1254 | 862 | // Start by searching backwards from Before, looking for kills, reads or defs. |
1255 | 862 | const_iterator I(Before); |
1256 | 862 | // If this is the first insn in the block, don't search backwards. |
1257 | 862 | if (I != begin()862 ) { |
1258 | 2.61k | do { |
1259 | 2.61k | --I; |
1260 | 2.61k | |
1261 | 2.61k | MachineOperandIteratorBase::PhysRegInfo Info = |
1262 | 2.61k | ConstMIOperands(*I).analyzePhysReg(Reg, TRI); |
1263 | 2.61k | |
1264 | 2.61k | // Defs happen after uses so they take precedence if both are present. |
1265 | 2.61k | |
1266 | 2.61k | // Register is dead after a dead def of the full register. |
1267 | 2.61k | if (Info.DeadDef) |
1268 | 338 | return LQR_Dead; |
1269 | 2.27k | // Register is (at least partially) live after a def. |
1270 | 2.27k | if (2.27k Info.Defined2.27k ) { |
1271 | 58 | if (!Info.PartialDeadDef) |
1272 | 55 | return LQR_Live; |
1273 | 3 | // As soon as we saw a partial definition (dead or not), |
1274 | 3 | // we cannot tell if the value is partial live without |
1275 | 3 | // tracking the lanemasks. We are not going to do this, |
1276 | 3 | // so fall back on the remaining of the analysis. |
1277 | 3 | break; |
1278 | 3 | } |
1279 | 2.21k | // Register is dead after a full kill or clobber and no def. |
1280 | 2.21k | if (2.21k Info.Killed || 2.21k Info.Clobbered2.18k ) |
1281 | 29 | return LQR_Dead; |
1282 | 2.18k | // Register must be live if we read it. |
1283 | 2.18k | if (2.18k Info.Read2.18k ) |
1284 | 2 | return LQR_Live; |
1285 | 2.18k | } while (I != begin() && 2.18k --N > 01.86k ); |
1286 | 763 | } |
1287 | 862 | |
1288 | 862 | // Did we get to the start of the block? |
1289 | 438 | if (438 I == begin()438 ) { |
1290 | 418 | // If so, the register's state is definitely defined by the live-in state. |
1291 | 2.68k | for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid(); |
1292 | 2.26k | ++RAI) |
1293 | 2.27k | if (2.27k isLiveIn(*RAI)2.27k ) |
1294 | 13 | return LQR_Live; |
1295 | 418 | |
1296 | 405 | return LQR_Dead; |
1297 | 20 | } |
1298 | 20 | |
1299 | 20 | N = Neighborhood; |
1300 | 20 | |
1301 | 20 | // Try searching forwards from Before, looking for reads or defs. |
1302 | 20 | I = const_iterator(Before); |
1303 | 20 | // If this is the last insn in the block, don't search forwards. |
1304 | 20 | if (I != end()20 ) { |
1305 | 82 | for (++I; I != end() && 82 N > 081 ; ++I, --N62 ) { |
1306 | 80 | MachineOperandIteratorBase::PhysRegInfo Info = |
1307 | 80 | ConstMIOperands(*I).analyzePhysReg(Reg, TRI); |
1308 | 80 | |
1309 | 80 | // Register is live when we read it here. |
1310 | 80 | if (Info.Read) |
1311 | 1 | return LQR_Live; |
1312 | 79 | // Register is dead if we can fully overwrite or clobber it here. |
1313 | 79 | if (79 Info.FullyDefined || 79 Info.Clobbered70 ) |
1314 | 17 | return LQR_Dead; |
1315 | 80 | } |
1316 | 20 | } |
1317 | 20 | |
1318 | 20 | // At this point we have no idea of the liveness of the register. |
1319 | 2 | return LQR_Unknown; |
1320 | 862 | } |
1321 | | |
1322 | | const uint32_t * |
1323 | 4.27M | MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const { |
1324 | 4.27M | // EH funclet entry does not preserve any registers. |
1325 | 4.27M | return isEHFuncletEntry() ? TRI->getNoPreservedMask()114 : nullptr4.27M ; |
1326 | 4.27M | } |
1327 | | |
1328 | | const uint32_t * |
1329 | 4.27M | MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const { |
1330 | 4.27M | // If we see a return block with successors, this must be a funclet return, |
1331 | 4.27M | // which does not preserve any registers. If there are no successors, we don't |
1332 | 4.27M | // care what kind of return it is, putting a mask after it is a no-op. |
1333 | 4.27M | return isReturnBlock() && !succ_empty()824k ? TRI->getNoPreservedMask()71 : nullptr4.27M ; |
1334 | 4.27M | } |
1335 | | |
1336 | 131k | void MachineBasicBlock::clearLiveIns() { |
1337 | 131k | LiveIns.clear(); |
1338 | 131k | } |
1339 | | |
1340 | 33.1M | MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const { |
1341 | 33.1M | assert(getParent()->getProperties().hasProperty( |
1342 | 33.1M | MachineFunctionProperties::Property::TracksLiveness) && |
1343 | 33.1M | "Liveness information is accurate"); |
1344 | 33.1M | return LiveIns.begin(); |
1345 | 33.1M | } |