Line data Source code
1 : //===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===//
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 : // This utility class duplicates basic blocks ending in unconditional branches
11 : // into the tails of their predecessors.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "llvm/CodeGen/TailDuplicator.h"
16 : #include "llvm/ADT/DenseMap.h"
17 : #include "llvm/ADT/DenseSet.h"
18 : #include "llvm/ADT/STLExtras.h"
19 : #include "llvm/ADT/SetVector.h"
20 : #include "llvm/ADT/SmallPtrSet.h"
21 : #include "llvm/ADT/SmallVector.h"
22 : #include "llvm/ADT/Statistic.h"
23 : #include "llvm/CodeGen/MachineBasicBlock.h"
24 : #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
25 : #include "llvm/CodeGen/MachineFunction.h"
26 : #include "llvm/CodeGen/MachineInstr.h"
27 : #include "llvm/CodeGen/MachineInstrBuilder.h"
28 : #include "llvm/CodeGen/MachineOperand.h"
29 : #include "llvm/CodeGen/MachineRegisterInfo.h"
30 : #include "llvm/CodeGen/MachineSSAUpdater.h"
31 : #include "llvm/CodeGen/TargetInstrInfo.h"
32 : #include "llvm/CodeGen/TargetRegisterInfo.h"
33 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
34 : #include "llvm/IR/DebugLoc.h"
35 : #include "llvm/IR/Function.h"
36 : #include "llvm/Support/CommandLine.h"
37 : #include "llvm/Support/Debug.h"
38 : #include "llvm/Support/ErrorHandling.h"
39 : #include "llvm/Support/raw_ostream.h"
40 : #include "llvm/Target/TargetMachine.h"
41 : #include <algorithm>
42 : #include <cassert>
43 : #include <iterator>
44 : #include <utility>
45 :
46 : using namespace llvm;
47 :
48 : #define DEBUG_TYPE "tailduplication"
49 :
50 : STATISTIC(NumTails, "Number of tails duplicated");
51 : STATISTIC(NumTailDups, "Number of tail duplicated blocks");
52 : STATISTIC(NumTailDupAdded,
53 : "Number of instructions added due to tail duplication");
54 : STATISTIC(NumTailDupRemoved,
55 : "Number of instructions removed due to tail duplication");
56 : STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
57 : STATISTIC(NumAddedPHIs, "Number of phis added");
58 :
59 : // Heuristic for tail duplication.
60 : static cl::opt<unsigned> TailDuplicateSize(
61 : "tail-dup-size",
62 : cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2),
63 : cl::Hidden);
64 :
65 : static cl::opt<unsigned> TailDupIndirectBranchSize(
66 : "tail-dup-indirect-size",
67 : cl::desc("Maximum instructions to consider tail duplicating blocks that "
68 : "end with indirect branches."), cl::init(20),
69 : cl::Hidden);
70 :
71 : static cl::opt<bool>
72 : TailDupVerify("tail-dup-verify",
73 : cl::desc("Verify sanity of PHI instructions during taildup"),
74 : cl::init(false), cl::Hidden);
75 :
76 : static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U),
77 : cl::Hidden);
78 :
79 408961 : void TailDuplicator::initMF(MachineFunction &MFin, bool PreRegAlloc,
80 : const MachineBranchProbabilityInfo *MBPIin,
81 : bool LayoutModeIn, unsigned TailDupSizeIn) {
82 408961 : MF = &MFin;
83 408961 : TII = MF->getSubtarget().getInstrInfo();
84 408962 : TRI = MF->getSubtarget().getRegisterInfo();
85 408962 : MRI = &MF->getRegInfo();
86 408962 : MMI = &MF->getMMI();
87 408962 : MBPI = MBPIin;
88 408962 : TailDupSize = TailDupSizeIn;
89 :
90 : assert(MBPI != nullptr && "Machine Branch Probability Info required");
91 :
92 408962 : LayoutMode = LayoutModeIn;
93 408962 : this->PreRegAlloc = PreRegAlloc;
94 408962 : }
95 :
96 0 : static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {
97 0 : for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) {
98 : MachineBasicBlock *MBB = &*I;
99 : SmallSetVector<MachineBasicBlock *, 8> Preds(MBB->pred_begin(),
100 0 : MBB->pred_end());
101 : MachineBasicBlock::iterator MI = MBB->begin();
102 0 : while (MI != MBB->end()) {
103 : if (!MI->isPHI())
104 : break;
105 0 : for (MachineBasicBlock *PredBB : Preds) {
106 : bool Found = false;
107 0 : for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
108 0 : MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();
109 0 : if (PHIBB == PredBB) {
110 : Found = true;
111 : break;
112 : }
113 : }
114 0 : if (!Found) {
115 0 : dbgs() << "Malformed PHI in " << printMBBReference(*MBB) << ": "
116 0 : << *MI;
117 0 : dbgs() << " missing input from predecessor "
118 0 : << printMBBReference(*PredBB) << '\n';
119 0 : llvm_unreachable(nullptr);
120 : }
121 : }
122 :
123 0 : for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
124 0 : MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();
125 0 : if (CheckExtra && !Preds.count(PHIBB)) {
126 0 : dbgs() << "Warning: malformed PHI in " << printMBBReference(*MBB)
127 0 : << ": " << *MI;
128 0 : dbgs() << " extra input from predecessor "
129 0 : << printMBBReference(*PHIBB) << '\n';
130 0 : llvm_unreachable(nullptr);
131 : }
132 0 : if (PHIBB->getNumber() < 0) {
133 0 : dbgs() << "Malformed PHI in " << printMBBReference(*MBB) << ": "
134 0 : << *MI;
135 0 : dbgs() << " non-existing " << printMBBReference(*PHIBB) << '\n';
136 0 : llvm_unreachable(nullptr);
137 : }
138 : }
139 : ++MI;
140 : }
141 : }
142 0 : }
143 :
144 : /// Tail duplicate the block and cleanup.
145 : /// \p IsSimple - return value of isSimpleBB
146 : /// \p MBB - block to be duplicated
147 : /// \p ForcedLayoutPred - If non-null, treat this block as the layout
148 : /// predecessor, instead of using the ordering in MF
149 : /// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of
150 : /// all Preds that received a copy of \p MBB.
151 : /// \p RemovalCallback - if non-null, called just before MBB is deleted.
152 65512 : bool TailDuplicator::tailDuplicateAndUpdate(
153 : bool IsSimple, MachineBasicBlock *MBB,
154 : MachineBasicBlock *ForcedLayoutPred,
155 : SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds,
156 : function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
157 : // Save the successors list.
158 : SmallSetVector<MachineBasicBlock *, 8> Succs(MBB->succ_begin(),
159 65512 : MBB->succ_end());
160 :
161 : SmallVector<MachineBasicBlock *, 8> TDBBs;
162 : SmallVector<MachineInstr *, 16> Copies;
163 65512 : if (!tailDuplicate(IsSimple, MBB, ForcedLayoutPred, TDBBs, Copies))
164 : return false;
165 :
166 : ++NumTails;
167 :
168 : SmallVector<MachineInstr *, 8> NewPHIs;
169 6830 : MachineSSAUpdater SSAUpdate(*MF, &NewPHIs);
170 :
171 : // TailBB's immediate successors are now successors of those predecessors
172 : // which duplicated TailBB. Add the predecessors as sources to the PHI
173 : // instructions.
174 3415 : bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken();
175 3415 : if (PreRegAlloc)
176 531 : updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs);
177 :
178 : // If it is dead, remove it.
179 3415 : if (isDead) {
180 : NumTailDupRemoved += MBB->size();
181 1909 : removeDeadBlock(MBB, RemovalCallback);
182 : ++NumDeadBlocks;
183 : }
184 :
185 : // Update SSA form.
186 3415 : if (!SSAUpdateVRs.empty()) {
187 307 : for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) {
188 178 : unsigned VReg = SSAUpdateVRs[i];
189 178 : SSAUpdate.Initialize(VReg);
190 :
191 : // If the original definition is still around, add it as an available
192 : // value.
193 178 : MachineInstr *DefMI = MRI->getVRegDef(VReg);
194 : MachineBasicBlock *DefBB = nullptr;
195 178 : if (DefMI) {
196 2 : DefBB = DefMI->getParent();
197 2 : SSAUpdate.AddAvailableValue(DefBB, VReg);
198 : }
199 :
200 : // Add the new vregs as available values.
201 : DenseMap<unsigned, AvailableValsTy>::iterator LI =
202 178 : SSAUpdateVals.find(VReg);
203 793 : for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
204 437 : MachineBasicBlock *SrcBB = LI->second[j].first;
205 437 : unsigned SrcReg = LI->second[j].second;
206 437 : SSAUpdate.AddAvailableValue(SrcBB, SrcReg);
207 : }
208 :
209 : // Rewrite uses that are outside of the original def's block.
210 178 : MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg);
211 242 : while (UI != MRI->use_end()) {
212 : MachineOperand &UseMO = *UI;
213 64 : MachineInstr *UseMI = UseMO.getParent();
214 : ++UI;
215 64 : if (UseMI->isDebugValue()) {
216 : // SSAUpdate can replace the use with an undef. That creates
217 : // a debug instruction that is a kill.
218 : // FIXME: Should it SSAUpdate job to delete debug instructions
219 : // instead of replacing the use with undef?
220 0 : UseMI->eraseFromParent();
221 0 : continue;
222 : }
223 64 : if (UseMI->getParent() == DefBB && !UseMI->isPHI())
224 : continue;
225 64 : SSAUpdate.RewriteUse(UseMO);
226 : }
227 : }
228 :
229 : SSAUpdateVRs.clear();
230 129 : SSAUpdateVals.clear();
231 : }
232 :
233 : // Eliminate some of the copies inserted by tail duplication to maintain
234 : // SSA form.
235 3874 : for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
236 918 : MachineInstr *Copy = Copies[i];
237 459 : if (!Copy->isCopy())
238 : continue;
239 459 : unsigned Dst = Copy->getOperand(0).getReg();
240 459 : unsigned Src = Copy->getOperand(1).getReg();
241 796 : if (MRI->hasOneNonDBGUse(Src) &&
242 674 : MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) {
243 : // Copy is the only use. Do trivial copy propagation here.
244 337 : MRI->replaceRegWith(Dst, Src);
245 337 : Copy->eraseFromParent();
246 : }
247 : }
248 :
249 : if (NewPHIs.size())
250 : NumAddedPHIs += NewPHIs.size();
251 :
252 3415 : if (DuplicatedPreds)
253 1991 : *DuplicatedPreds = std::move(TDBBs);
254 :
255 : return true;
256 : }
257 :
258 : /// Look for small blocks that are unconditionally branched to and do not fall
259 : /// through. Tail-duplicate their instructions into their predecessors to
260 : /// eliminate (dynamic) branches.
261 393185 : bool TailDuplicator::tailDuplicateBlocks() {
262 : bool MadeChange = false;
263 :
264 393185 : if (PreRegAlloc && TailDupVerify) {
265 : LLVM_DEBUG(dbgs() << "\n*** Before tail-duplicating\n");
266 0 : VerifyPHIs(*MF, true);
267 : }
268 :
269 916060 : for (MachineFunction::iterator I = ++MF->begin(), E = MF->end(); I != E;) {
270 : MachineBasicBlock *MBB = &*I++;
271 :
272 522876 : if (NumTails == TailDupLimit)
273 : break;
274 :
275 522876 : bool IsSimple = isSimpleBB(MBB);
276 :
277 522875 : if (!shouldTailDuplicate(IsSimple, *MBB))
278 : continue;
279 :
280 43061 : MadeChange |= tailDuplicateAndUpdate(IsSimple, MBB, nullptr);
281 : }
282 :
283 393184 : if (PreRegAlloc && TailDupVerify)
284 0 : VerifyPHIs(*MF, false);
285 :
286 393184 : return MadeChange;
287 : }
288 :
289 745 : static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB,
290 : const MachineRegisterInfo *MRI) {
291 1022 : for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
292 709 : if (UseMI.isDebugValue())
293 : continue;
294 699 : if (UseMI.getParent() != BB)
295 432 : return true;
296 : }
297 313 : return false;
298 : }
299 :
300 : static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) {
301 11844 : for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2)
302 23688 : if (MI->getOperand(i + 1).getMBB() == SrcBB)
303 : return i;
304 : return 0;
305 : }
306 :
307 : // Remember which registers are used by phis in this block. This is
308 : // used to determine which registers are liveout while modifying the
309 : // block (which is why we need to copy the information).
310 65512 : static void getRegsUsedByPHIs(const MachineBasicBlock &BB,
311 : DenseSet<unsigned> *UsedByPhi) {
312 65716 : for (const auto &MI : BB) {
313 : if (!MI.isPHI())
314 : break;
315 687 : for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
316 966 : unsigned SrcReg = MI.getOperand(i).getReg();
317 : UsedByPhi->insert(SrcReg);
318 : }
319 : }
320 65512 : }
321 :
322 : /// Add a definition and source virtual registers pair for SSA update.
323 437 : void TailDuplicator::addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
324 : MachineBasicBlock *BB) {
325 : DenseMap<unsigned, AvailableValsTy>::iterator LI =
326 437 : SSAUpdateVals.find(OrigReg);
327 437 : if (LI != SSAUpdateVals.end())
328 259 : LI->second.push_back(std::make_pair(BB, NewReg));
329 : else {
330 : AvailableValsTy Vals;
331 178 : Vals.push_back(std::make_pair(BB, NewReg));
332 356 : SSAUpdateVals.insert(std::make_pair(OrigReg, Vals));
333 178 : SSAUpdateVRs.push_back(OrigReg);
334 : }
335 437 : }
336 :
337 : /// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the
338 : /// source register that's contributed by PredBB and update SSA update map.
339 459 : void TailDuplicator::processPHI(
340 : MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,
341 : DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
342 : SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies,
343 : const DenseSet<unsigned> &RegsUsedByPhi, bool Remove) {
344 459 : unsigned DefReg = MI->getOperand(0).getReg();
345 : unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB);
346 : assert(SrcOpIdx && "Unable to find matching PHI source?");
347 459 : unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg();
348 : unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg();
349 459 : const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
350 459 : LocalVRMap.insert(std::make_pair(DefReg, RegSubRegPair(SrcReg, SrcSubReg)));
351 :
352 : // Insert a copy from source to the end of the block. The def register is the
353 : // available value liveout of the block.
354 918 : unsigned NewDef = MRI->createVirtualRegister(RC);
355 459 : Copies.push_back(std::make_pair(NewDef, RegSubRegPair(SrcReg, SrcSubReg)));
356 459 : if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg))
357 278 : addSSAUpdateEntry(DefReg, NewDef, PredBB);
358 :
359 459 : if (!Remove)
360 0 : return;
361 :
362 : // Remove PredBB from the PHI node.
363 459 : MI->RemoveOperand(SrcOpIdx + 1);
364 459 : MI->RemoveOperand(SrcOpIdx);
365 459 : if (MI->getNumOperands() == 1)
366 179 : MI->eraseFromParent();
367 : }
368 :
369 : /// Duplicate a TailBB instruction to PredBB and update
370 : /// the source operands due to earlier PHI translation.
371 9429 : void TailDuplicator::duplicateInstruction(
372 : MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,
373 : DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
374 : const DenseSet<unsigned> &UsedByPhi) {
375 : // Allow duplication of CFI instructions.
376 9429 : if (MI->isCFIInstruction()) {
377 116 : BuildMI(*PredBB, PredBB->end(), PredBB->findDebugLoc(PredBB->begin()),
378 116 : TII->get(TargetOpcode::CFI_INSTRUCTION)).addCFIIndex(
379 116 : MI->getOperand(0).getCFIIndex());
380 116 : return;
381 : }
382 18626 : MachineInstr &NewMI = TII->duplicate(*PredBB, PredBB->end(), *MI);
383 9313 : if (PreRegAlloc) {
384 3092 : for (unsigned i = 0, e = NewMI.getNumOperands(); i != e; ++i) {
385 2124 : MachineOperand &MO = NewMI.getOperand(i);
386 2124 : if (!MO.isReg())
387 1424 : continue;
388 1089 : unsigned Reg = MO.getReg();
389 1089 : if (!TargetRegisterInfo::isVirtualRegister(Reg))
390 : continue;
391 700 : if (MO.isDef()) {
392 286 : const TargetRegisterClass *RC = MRI->getRegClass(Reg);
393 286 : unsigned NewReg = MRI->createVirtualRegister(RC);
394 286 : MO.setReg(NewReg);
395 286 : LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
396 286 : if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg))
397 159 : addSSAUpdateEntry(Reg, NewReg, PredBB);
398 : } else {
399 414 : auto VI = LocalVRMap.find(Reg);
400 414 : if (VI != LocalVRMap.end()) {
401 : // Need to make sure that the register class of the mapped register
402 : // will satisfy the constraints of the class of the register being
403 : // replaced.
404 257 : auto *OrigRC = MRI->getRegClass(Reg);
405 257 : auto *MappedRC = MRI->getRegClass(VI->second.Reg);
406 : const TargetRegisterClass *ConstrRC;
407 257 : if (VI->second.SubReg != 0) {
408 0 : ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC,
409 0 : VI->second.SubReg);
410 0 : if (ConstrRC) {
411 : // The actual constraining (as in "find appropriate new class")
412 : // is done by getMatchingSuperRegClass, so now we only need to
413 : // change the class of the mapped register.
414 0 : MRI->setRegClass(VI->second.Reg, ConstrRC);
415 : }
416 : } else {
417 : // For mapped registers that do not have sub-registers, simply
418 : // restrict their class to match the original one.
419 257 : ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC);
420 : }
421 :
422 257 : if (ConstrRC) {
423 : // If the class constraining succeeded, we can simply replace
424 : // the old register with the mapped one.
425 257 : MO.setReg(VI->second.Reg);
426 : // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a
427 : // sub-register, we need to compose the sub-register indices.
428 257 : MO.setSubReg(TRI->composeSubRegIndices(MO.getSubReg(),
429 : VI->second.SubReg));
430 : } else {
431 : // The direct replacement is not possible, due to failing register
432 : // class constraints. An explicit COPY is necessary. Create one
433 : // that can be reused
434 0 : auto *NewRC = MI->getRegClassConstraint(i, TII, TRI);
435 0 : if (NewRC == nullptr)
436 : NewRC = OrigRC;
437 0 : unsigned NewReg = MRI->createVirtualRegister(NewRC);
438 0 : BuildMI(*PredBB, MI, MI->getDebugLoc(),
439 0 : TII->get(TargetOpcode::COPY), NewReg)
440 0 : .addReg(VI->second.Reg, 0, VI->second.SubReg);
441 : LocalVRMap.erase(VI);
442 0 : LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
443 0 : MO.setReg(NewReg);
444 : // The composed VI.Reg:VI.SubReg is replaced with NewReg, which
445 : // is equivalent to the whole register Reg. Hence, Reg:subreg
446 : // is same as NewReg:subreg, so keep the sub-register index
447 : // unchanged.
448 : }
449 : // Clear any kill flags from this operand. The new register could
450 : // have uses after this one, so kills are not valid here.
451 : MO.setIsKill(false);
452 : }
453 : }
454 : }
455 : }
456 : }
457 :
458 : /// After FromBB is tail duplicated into its predecessor blocks, the successors
459 : /// have gained new predecessors. Update the PHI instructions in them
460 : /// accordingly.
461 531 : void TailDuplicator::updateSuccessorsPHIs(
462 : MachineBasicBlock *FromBB, bool isDead,
463 : SmallVectorImpl<MachineBasicBlock *> &TDBBs,
464 : SmallSetVector<MachineBasicBlock *, 8> &Succs) {
465 1151 : for (MachineBasicBlock *SuccBB : Succs) {
466 1033 : for (MachineInstr &MI : *SuccBB) {
467 : if (!MI.isPHI())
468 : break;
469 413 : MachineInstrBuilder MIB(*FromBB->getParent(), MI);
470 : unsigned Idx = 0;
471 674 : for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
472 674 : MachineOperand &MO = MI.getOperand(i + 1);
473 674 : if (MO.getMBB() == FromBB) {
474 : Idx = i;
475 : break;
476 : }
477 : }
478 :
479 : assert(Idx != 0);
480 413 : MachineOperand &MO0 = MI.getOperand(Idx);
481 413 : unsigned Reg = MO0.getReg();
482 413 : if (isDead) {
483 : // Folded into the previous BB.
484 : // There could be duplicate phi source entries. FIXME: Should sdisel
485 : // or earlier pass fixed this?
486 783 : for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) {
487 376 : MachineOperand &MO = MI.getOperand(i + 1);
488 376 : if (MO.getMBB() == FromBB) {
489 0 : MI.RemoveOperand(i + 1);
490 0 : MI.RemoveOperand(i);
491 : }
492 : }
493 : } else
494 : Idx = 0;
495 :
496 : // If Idx is set, the operands at Idx and Idx+1 must be removed.
497 : // We reuse the location to avoid expensive RemoveOperand calls.
498 :
499 : DenseMap<unsigned, AvailableValsTy>::iterator LI =
500 413 : SSAUpdateVals.find(Reg);
501 413 : if (LI != SSAUpdateVals.end()) {
502 : // This register is defined in the tail block.
503 759 : for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
504 415 : MachineBasicBlock *SrcBB = LI->second[j].first;
505 : // If we didn't duplicate a bb into a particular predecessor, we
506 : // might still have added an entry to SSAUpdateVals to correcly
507 : // recompute SSA. If that case, avoid adding a dummy extra argument
508 : // this PHI.
509 415 : if (!SrcBB->isSuccessor(SuccBB))
510 : continue;
511 :
512 415 : unsigned SrcReg = LI->second[j].second;
513 415 : if (Idx != 0) {
514 344 : MI.getOperand(Idx).setReg(SrcReg);
515 172 : MI.getOperand(Idx + 1).setMBB(SrcBB);
516 : Idx = 0;
517 : } else {
518 243 : MIB.addReg(SrcReg).addMBB(SrcBB);
519 : }
520 : }
521 : } else {
522 : // Live in tail block, must also be live in predecessors.
523 504 : for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) {
524 263 : MachineBasicBlock *SrcBB = TDBBs[j];
525 263 : if (Idx != 0) {
526 470 : MI.getOperand(Idx).setReg(Reg);
527 235 : MI.getOperand(Idx + 1).setMBB(SrcBB);
528 : Idx = 0;
529 : } else {
530 28 : MIB.addReg(Reg).addMBB(SrcBB);
531 : }
532 : }
533 : }
534 413 : if (Idx != 0) {
535 0 : MI.RemoveOperand(Idx + 1);
536 0 : MI.RemoveOperand(Idx);
537 : }
538 : }
539 : }
540 531 : }
541 :
542 : /// Determine if it is profitable to duplicate this block.
543 760471 : bool TailDuplicator::shouldTailDuplicate(bool IsSimple,
544 : MachineBasicBlock &TailBB) {
545 : // When doing tail-duplication during layout, the block ordering is in flux,
546 : // so canFallThrough returns a result based on incorrect information and
547 : // should just be ignored.
548 760471 : if (!LayoutMode && TailBB.canFallThrough())
549 : return false;
550 :
551 : // Don't try to tail-duplicate single-block loops.
552 458272 : if (TailBB.isSuccessor(&TailBB))
553 : return false;
554 :
555 : // Set the limit on the cost to duplicate. When optimizing for size,
556 : // duplicate only one, because one branch instruction can be eliminated to
557 : // compensate for the duplication.
558 : unsigned MaxDuplicateCount;
559 668428 : if (TailDupSize == 0 &&
560 668408 : TailDuplicateSize.getNumOccurrences() == 0 &&
561 219310 : MF->getFunction().optForSize())
562 : MaxDuplicateCount = 1;
563 448009 : else if (TailDupSize == 0)
564 : MaxDuplicateCount = TailDuplicateSize;
565 : else
566 : MaxDuplicateCount = TailDupSize;
567 :
568 : // If the block to be duplicated ends in an unanalyzable fallthrough, don't
569 : // duplicate it.
570 : // A similar check is necessary in MachineBlockPlacement to make sure pairs of
571 : // blocks with unanalyzable fallthrough get layed out contiguously.
572 449098 : MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
573 : SmallVector<MachineOperand, 4> PredCond;
574 532137 : if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) &&
575 83039 : TailBB.canFallThrough())
576 : return false;
577 :
578 : // If the target has hardware branch prediction that can handle indirect
579 : // branches, duplicating them can often make them predictable when there
580 : // are common paths through the code. The limit needs to be high enough
581 : // to allow undoing the effects of tail merging and other optimizations
582 : // that rearrange the predecessors of the indirect branch.
583 :
584 : bool HasIndirectbr = false;
585 449057 : if (!TailBB.empty())
586 : HasIndirectbr = TailBB.back().isIndirectBranch();
587 :
588 443860 : if (HasIndirectbr && PreRegAlloc)
589 : MaxDuplicateCount = TailDupIndirectBranchSize;
590 :
591 : // Check the instructions in the block to determine whether tail-duplication
592 : // is invalid or unlikely to be profitable.
593 : unsigned InstrCount = 0;
594 1323240 : for (MachineInstr &MI : TailBB) {
595 : // Non-duplicable things shouldn't be tail-duplicated.
596 : // CFI instructions are marked as non-duplicable, because Darwin compact
597 : // unwind info emission can't handle multiple prologue setups. In case of
598 : // DWARF, allow them be duplicated, so that their existence doesn't prevent
599 : // tail duplication of some basic blocks, that would be duplicated otherwise.
600 1216287 : if (MI.isNotDuplicable() &&
601 198671 : (TailBB.getParent()->getTarget().getTargetTriple().isOSDarwin() ||
602 : !MI.isCFIInstruction()))
603 : return false;
604 :
605 : // Convergent instructions can be duplicated only if doing so doesn't add
606 : // new control dependencies, which is what we're going to do here.
607 1131836 : if (MI.isConvergent())
608 : return false;
609 :
610 : // Do not duplicate 'return' instructions if this is a pre-regalloc run.
611 : // A return may expand into a lot more instructions (e.g. reload of callee
612 : // saved registers) after PEI.
613 1399661 : if (PreRegAlloc && MI.isReturn())
614 : return false;
615 :
616 : // Avoid duplicating calls before register allocation. Calls presents a
617 : // barrier to register allocation so duplicating them may end up increasing
618 : // spills.
619 1373561 : if (PreRegAlloc && MI.isCall())
620 : return false;
621 :
622 : if (!MI.isPHI() && !MI.isMetaInstruction())
623 956431 : InstrCount += 1;
624 :
625 1114403 : if (InstrCount > MaxDuplicateCount)
626 : return false;
627 : }
628 :
629 : // Check if any of the successors of TailBB has a PHI node in which the
630 : // value corresponding to TailBB uses a subregister.
631 : // If a phi node uses a register paired with a subregister, the actual
632 : // "value type" of the phi may differ from the type of the register without
633 : // any subregisters. Due to a bug, tail duplication may add a new operand
634 : // without a necessary subregister, producing an invalid code. This is
635 : // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll.
636 : // Disable tail duplication for this case for now, until the problem is
637 : // fixed.
638 215927 : for (auto SB : TailBB.successors()) {
639 113059 : for (auto &I : *SB) {
640 : if (!I.isPHI())
641 : break;
642 : unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
643 : assert(Idx != 0);
644 4085 : MachineOperand &PU = I.getOperand(Idx);
645 4085 : if (PU.getSubReg() != 0)
646 : return false;
647 : }
648 : }
649 :
650 106953 : if (HasIndirectbr && PreRegAlloc)
651 : return true;
652 :
653 106617 : if (IsSimple)
654 : return true;
655 :
656 106164 : if (!PreRegAlloc)
657 : return true;
658 :
659 5160 : return canCompletelyDuplicateBB(TailBB);
660 : }
661 :
662 : /// True if this BB has only one unconditional jump.
663 910617 : bool TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) {
664 910617 : if (TailBB->succ_size() != 1)
665 : return false;
666 348194 : if (TailBB->pred_empty())
667 : return false;
668 348191 : MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr();
669 348191 : if (I == TailBB->end())
670 : return true;
671 344305 : return I->isUnconditionalBranch();
672 : }
673 :
674 494 : static bool bothUsedInPHI(const MachineBasicBlock &A,
675 : const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) {
676 1745 : for (MachineBasicBlock *BB : A.successors())
677 1304 : if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI())
678 : return true;
679 :
680 : return false;
681 : }
682 :
683 5160 : bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) {
684 5654 : for (MachineBasicBlock *PredBB : BB.predecessors()) {
685 5330 : if (PredBB->succ_size() > 1)
686 4836 : return false;
687 :
688 516 : MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
689 : SmallVector<MachineOperand, 4> PredCond;
690 516 : if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
691 : return false;
692 :
693 495 : if (!PredCond.empty())
694 : return false;
695 : }
696 : return true;
697 : }
698 :
699 453 : bool TailDuplicator::duplicateSimpleBB(
700 : MachineBasicBlock *TailBB, SmallVectorImpl<MachineBasicBlock *> &TDBBs,
701 : const DenseSet<unsigned> &UsedByPhi,
702 : SmallVectorImpl<MachineInstr *> &Copies) {
703 : SmallPtrSet<MachineBasicBlock *, 8> Succs(TailBB->succ_begin(),
704 453 : TailBB->succ_end());
705 : SmallVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(),
706 453 : TailBB->pred_end());
707 : bool Changed = false;
708 959 : for (MachineBasicBlock *PredBB : Preds) {
709 506 : if (PredBB->hasEHPadSuccessor())
710 127 : continue;
711 :
712 494 : if (bothUsedInPHI(*PredBB, Succs))
713 : continue;
714 :
715 441 : MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
716 : SmallVector<MachineOperand, 4> PredCond;
717 441 : if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
718 : continue;
719 :
720 : Changed = true;
721 : LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
722 : << "From simple Succ: " << *TailBB);
723 :
724 379 : MachineBasicBlock *NewTarget = *TailBB->succ_begin();
725 379 : MachineBasicBlock *NextBB = PredBB->getNextNode();
726 :
727 : // Make PredFBB explicit.
728 379 : if (PredCond.empty())
729 26 : PredFBB = PredTBB;
730 :
731 : // Make fall through explicit.
732 379 : if (!PredTBB)
733 14 : PredTBB = NextBB;
734 379 : if (!PredFBB)
735 25 : PredFBB = NextBB;
736 :
737 : // Redirect
738 379 : if (PredFBB == TailBB)
739 306 : PredFBB = NewTarget;
740 379 : if (PredTBB == TailBB)
741 99 : PredTBB = NewTarget;
742 :
743 : // Make the branch unconditional if possible
744 379 : if (PredTBB == PredFBB) {
745 : PredCond.clear();
746 69 : PredFBB = nullptr;
747 : }
748 :
749 : // Avoid adding fall through branches.
750 379 : if (PredFBB == NextBB)
751 49 : PredFBB = nullptr;
752 379 : if (PredTBB == NextBB && PredFBB == nullptr)
753 10 : PredTBB = nullptr;
754 :
755 379 : auto DL = PredBB->findBranchDebugLoc();
756 379 : TII->removeBranch(*PredBB);
757 :
758 379 : if (!PredBB->isSuccessor(NewTarget))
759 336 : PredBB->replaceSuccessor(TailBB, NewTarget);
760 : else {
761 43 : PredBB->removeSuccessor(TailBB, true);
762 : assert(PredBB->succ_size() <= 1);
763 : }
764 :
765 379 : if (PredTBB)
766 738 : TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL);
767 :
768 379 : TDBBs.push_back(PredBB);
769 : }
770 453 : return Changed;
771 : }
772 :
773 88828 : bool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB,
774 : MachineBasicBlock *PredBB) {
775 : // EH edges are ignored by analyzeBranch.
776 88828 : if (PredBB->succ_size() > 1)
777 : return false;
778 :
779 18005 : MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
780 : SmallVector<MachineOperand, 4> PredCond;
781 18005 : if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
782 : return false;
783 17768 : if (!PredCond.empty())
784 20 : return false;
785 : return true;
786 : }
787 :
788 : /// If it is profitable, duplicate TailBB's contents in each
789 : /// of its predecessors.
790 : /// \p IsSimple result of isSimpleBB
791 : /// \p TailBB Block to be duplicated.
792 : /// \p ForcedLayoutPred When non-null, use this block as the layout predecessor
793 : /// instead of the previous block in MF's order.
794 : /// \p TDBBs A vector to keep track of all blocks tail-duplicated
795 : /// into.
796 : /// \p Copies A vector of copy instructions inserted. Used later to
797 : /// walk all the inserted copies and remove redundant ones.
798 65512 : bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,
799 : MachineBasicBlock *ForcedLayoutPred,
800 : SmallVectorImpl<MachineBasicBlock *> &TDBBs,
801 : SmallVectorImpl<MachineInstr *> &Copies) {
802 : LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB)
803 : << '\n');
804 :
805 : DenseSet<unsigned> UsedByPhi;
806 65512 : getRegsUsedByPHIs(*TailBB, &UsedByPhi);
807 :
808 65512 : if (IsSimple)
809 453 : return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies);
810 :
811 : // Iterate through all the unique predecessors and tail-duplicate this
812 : // block into them, if possible. Copying the list ahead of time also
813 : // avoids trouble with the predecessor list reallocating.
814 : bool Changed = false;
815 : SmallSetVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(),
816 65059 : TailBB->pred_end());
817 145379 : for (MachineBasicBlock *PredBB : Preds) {
818 : assert(TailBB != PredBB &&
819 : "Single-block loop should have been rejected earlier!");
820 :
821 80320 : if (!canTailDuplicate(TailBB, PredBB))
822 76554 : continue;
823 :
824 : // Don't duplicate into a fall-through predecessor (at least for now).
825 : bool IsLayoutSuccessor = false;
826 11569 : if (ForcedLayoutPred)
827 5974 : IsLayoutSuccessor = (ForcedLayoutPred == PredBB);
828 5595 : else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
829 : IsLayoutSuccessor = true;
830 5974 : if (IsLayoutSuccessor)
831 7803 : continue;
832 :
833 : LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
834 : << "From Succ: " << *TailBB);
835 :
836 3766 : TDBBs.push_back(PredBB);
837 :
838 : // Remove PredBB's unconditional branch.
839 3766 : TII->removeBranch(*PredBB);
840 :
841 : // Clone the contents of TailBB into PredBB.
842 : DenseMap<unsigned, RegSubRegPair> LocalVRMap;
843 : SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos;
844 : for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end();
845 13094 : I != E; /* empty */) {
846 : MachineInstr *MI = &*I;
847 : ++I;
848 : if (MI->isPHI()) {
849 : // Replace the uses of the def of the PHI with the register coming
850 : // from PredBB.
851 290 : processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true);
852 : } else {
853 : // Replace def of virtual registers with new registers, and update
854 : // uses with PHI source register or the new registers.
855 9038 : duplicateInstruction(MI, TailBB, PredBB, LocalVRMap, UsedByPhi);
856 : }
857 : }
858 3766 : appendCopies(PredBB, CopyInfos, Copies);
859 :
860 : // Simplify
861 3766 : MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
862 : SmallVector<MachineOperand, 4> PredCond;
863 3766 : TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond);
864 :
865 : NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch
866 :
867 : // Update the CFG.
868 7532 : PredBB->removeSuccessor(PredBB->succ_begin());
869 : assert(PredBB->succ_empty() &&
870 : "TailDuplicate called on block with multiple successors!");
871 8341 : for (MachineBasicBlock *Succ : TailBB->successors())
872 4575 : PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ));
873 :
874 : Changed = true;
875 : ++NumTailDups;
876 : }
877 :
878 : // If TailBB was duplicated into all its predecessors except for the prior
879 : // block, which falls through unconditionally, move the contents of this
880 : // block into the prior block.
881 65059 : MachineBasicBlock *PrevBB = ForcedLayoutPred;
882 65059 : if (!PrevBB)
883 85216 : PrevBB = &*std::prev(TailBB->getIterator());
884 65059 : MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
885 : SmallVector<MachineOperand, 4> PriorCond;
886 : // This has to check PrevBB->succ_size() because EH edges are ignored by
887 : // analyzeBranch.
888 65059 : if (PrevBB->succ_size() == 1 &&
889 : // Layout preds are not always CFG preds. Check.
890 17004 : *PrevBB->succ_begin() == TailBB &&
891 8013 : !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) &&
892 7819 : PriorCond.empty() &&
893 7803 : (!PriorTBB || PriorTBB == TailBB) &&
894 65059 : TailBB->pred_size() == 1 &&
895 1625 : !TailBB->hasAddressTaken()) {
896 : LLVM_DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
897 : << "From MBB: " << *TailBB);
898 : // There may be a branch to the layout successor. This is unlikely but it
899 : // happens. The correct thing to do is to remove the branch before
900 : // duplicating the instructions in all cases.
901 1571 : TII->removeBranch(*PrevBB);
902 1571 : if (PreRegAlloc) {
903 : DenseMap<unsigned, RegSubRegPair> LocalVRMap;
904 : SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos;
905 : MachineBasicBlock::iterator I = TailBB->begin();
906 : // Process PHI instructions first.
907 347 : while (I != TailBB->end() && I->isPHI()) {
908 : // Replace the uses of the def of the PHI with the register coming
909 : // from PredBB.
910 : MachineInstr *MI = &*I++;
911 169 : processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true);
912 : }
913 :
914 : // Now copy the non-PHI instructions.
915 569 : while (I != TailBB->end()) {
916 : // Replace def of virtual registers with new registers, and update
917 : // uses with PHI source register or the new registers.
918 : MachineInstr *MI = &*I++;
919 : assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
920 391 : duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
921 391 : MI->eraseFromParent();
922 : }
923 178 : appendCopies(PrevBB, CopyInfos, Copies);
924 : } else {
925 1393 : TII->removeBranch(*PrevBB);
926 : // No PHIs to worry about, just splice the instructions over.
927 1393 : PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
928 : }
929 3142 : PrevBB->removeSuccessor(PrevBB->succ_begin());
930 : assert(PrevBB->succ_empty());
931 1571 : PrevBB->transferSuccessors(TailBB);
932 1571 : TDBBs.push_back(PrevBB);
933 : Changed = true;
934 : }
935 :
936 : // If this is after register allocation, there are no phis to fix.
937 65059 : if (!PreRegAlloc)
938 : return Changed;
939 :
940 : // If we made no changes so far, we are safe.
941 660 : if (!Changed)
942 : return Changed;
943 :
944 : // Handle the nasty case in that we duplicated a block that is part of a loop
945 : // into some but not all of its predecessors. For example:
946 : // 1 -> 2 <-> 3 |
947 : // \ |
948 : // \---> rest |
949 : // if we duplicate 2 into 1 but not into 3, we end up with
950 : // 12 -> 3 <-> 2 -> rest |
951 : // \ / |
952 : // \----->-----/ |
953 : // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced
954 : // with a phi in 3 (which now dominates 2).
955 : // What we do here is introduce a copy in 3 of the register defined by the
956 : // phi, just like when we are duplicating 2 into 3, but we don't copy any
957 : // real instructions or remove the 3 -> 2 edge from the phi in 2.
958 645 : for (MachineBasicBlock *PredBB : Preds) {
959 448 : if (is_contained(TDBBs, PredBB))
960 448 : continue;
961 :
962 : // EH edges
963 10 : if (PredBB->succ_size() != 1)
964 : continue;
965 :
966 : DenseMap<unsigned, RegSubRegPair> LocalVRMap;
967 : SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos;
968 : MachineBasicBlock::iterator I = TailBB->begin();
969 : // Process PHI instructions first.
970 0 : while (I != TailBB->end() && I->isPHI()) {
971 : // Replace the uses of the def of the PHI with the register coming
972 : // from PredBB.
973 : MachineInstr *MI = &*I++;
974 0 : processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);
975 : }
976 0 : appendCopies(PredBB, CopyInfos, Copies);
977 : }
978 :
979 197 : return Changed;
980 : }
981 :
982 : /// At the end of the block \p MBB generate COPY instructions between registers
983 : /// described by \p CopyInfos. Append resulting instructions to \p Copies.
984 3944 : void TailDuplicator::appendCopies(MachineBasicBlock *MBB,
985 : SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
986 : SmallVectorImpl<MachineInstr*> &Copies) {
987 3944 : MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();
988 3944 : const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY);
989 4403 : for (auto &CI : CopyInfos) {
990 459 : auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)
991 459 : .addReg(CI.second.Reg, 0, CI.second.SubReg);
992 459 : Copies.push_back(C);
993 : }
994 3944 : }
995 :
996 : /// Remove the specified dead machine basic block from the function, updating
997 : /// the CFG.
998 1909 : void TailDuplicator::removeDeadBlock(
999 : MachineBasicBlock *MBB,
1000 : function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
1001 : assert(MBB->pred_empty() && "MBB must be dead!");
1002 : LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
1003 :
1004 1909 : if (RemovalCallback)
1005 712 : (*RemovalCallback)(MBB);
1006 :
1007 : // Remove all successors.
1008 2247 : while (!MBB->succ_empty())
1009 338 : MBB->removeSuccessor(MBB->succ_end() - 1);
1010 :
1011 : // Remove the block.
1012 1909 : MBB->eraseFromParent();
1013 1909 : }
|
