Line data Source code
1 : //===- TwoAddressInstructionPass.cpp - Two-Address instruction pass -------===//
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 file implements the TwoAddress instruction pass which is used
11 : // by most register allocators. Two-Address instructions are rewritten
12 : // from:
13 : //
14 : // A = B op C
15 : //
16 : // to:
17 : //
18 : // A = B
19 : // A op= C
20 : //
21 : // Note that if a register allocator chooses to use this pass, that it
22 : // has to be capable of handling the non-SSA nature of these rewritten
23 : // virtual registers.
24 : //
25 : // It is also worth noting that the duplicate operand of the two
26 : // address instruction is removed.
27 : //
28 : //===----------------------------------------------------------------------===//
29 :
30 : #include "llvm/ADT/DenseMap.h"
31 : #include "llvm/ADT/SmallPtrSet.h"
32 : #include "llvm/ADT/SmallSet.h"
33 : #include "llvm/ADT/SmallVector.h"
34 : #include "llvm/ADT/Statistic.h"
35 : #include "llvm/ADT/iterator_range.h"
36 : #include "llvm/Analysis/AliasAnalysis.h"
37 : #include "llvm/CodeGen/LiveInterval.h"
38 : #include "llvm/CodeGen/LiveIntervals.h"
39 : #include "llvm/CodeGen/LiveVariables.h"
40 : #include "llvm/CodeGen/MachineBasicBlock.h"
41 : #include "llvm/CodeGen/MachineFunction.h"
42 : #include "llvm/CodeGen/MachineFunctionPass.h"
43 : #include "llvm/CodeGen/MachineInstr.h"
44 : #include "llvm/CodeGen/MachineInstrBuilder.h"
45 : #include "llvm/CodeGen/MachineOperand.h"
46 : #include "llvm/CodeGen/MachineRegisterInfo.h"
47 : #include "llvm/CodeGen/Passes.h"
48 : #include "llvm/CodeGen/SlotIndexes.h"
49 : #include "llvm/CodeGen/TargetInstrInfo.h"
50 : #include "llvm/CodeGen/TargetOpcodes.h"
51 : #include "llvm/CodeGen/TargetRegisterInfo.h"
52 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
53 : #include "llvm/MC/MCInstrDesc.h"
54 : #include "llvm/MC/MCInstrItineraries.h"
55 : #include "llvm/Pass.h"
56 : #include "llvm/Support/CodeGen.h"
57 : #include "llvm/Support/CommandLine.h"
58 : #include "llvm/Support/Debug.h"
59 : #include "llvm/Support/ErrorHandling.h"
60 : #include "llvm/Support/raw_ostream.h"
61 : #include "llvm/Target/TargetMachine.h"
62 : #include <cassert>
63 : #include <iterator>
64 : #include <utility>
65 :
66 : using namespace llvm;
67 :
68 : #define DEBUG_TYPE "twoaddressinstruction"
69 :
70 : STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
71 : STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
72 : STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted");
73 : STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
74 : STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk");
75 : STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up");
76 : STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down");
77 :
78 : // Temporary flag to disable rescheduling.
79 : static cl::opt<bool>
80 : EnableRescheduling("twoaddr-reschedule",
81 : cl::desc("Coalesce copies by rescheduling (default=true)"),
82 : cl::init(true), cl::Hidden);
83 :
84 : // Limit the number of dataflow edges to traverse when evaluating the benefit
85 : // of commuting operands.
86 : static cl::opt<unsigned> MaxDataFlowEdge(
87 : "dataflow-edge-limit", cl::Hidden, cl::init(3),
88 : cl::desc("Maximum number of dataflow edges to traverse when evaluating "
89 : "the benefit of commuting operands"));
90 :
91 : namespace {
92 :
93 : class TwoAddressInstructionPass : public MachineFunctionPass {
94 : MachineFunction *MF;
95 : const TargetInstrInfo *TII;
96 : const TargetRegisterInfo *TRI;
97 : const InstrItineraryData *InstrItins;
98 : MachineRegisterInfo *MRI;
99 : LiveVariables *LV;
100 : LiveIntervals *LIS;
101 : AliasAnalysis *AA;
102 : CodeGenOpt::Level OptLevel;
103 :
104 : // The current basic block being processed.
105 : MachineBasicBlock *MBB;
106 :
107 : // Keep track the distance of a MI from the start of the current basic block.
108 : DenseMap<MachineInstr*, unsigned> DistanceMap;
109 :
110 : // Set of already processed instructions in the current block.
111 : SmallPtrSet<MachineInstr*, 8> Processed;
112 :
113 : // Set of instructions converted to three-address by target and then sunk
114 : // down current basic block.
115 : SmallPtrSet<MachineInstr*, 8> SunkInstrs;
116 :
117 : // A map from virtual registers to physical registers which are likely targets
118 : // to be coalesced to due to copies from physical registers to virtual
119 : // registers. e.g. v1024 = move r0.
120 : DenseMap<unsigned, unsigned> SrcRegMap;
121 :
122 : // A map from virtual registers to physical registers which are likely targets
123 : // to be coalesced to due to copies to physical registers from virtual
124 : // registers. e.g. r1 = move v1024.
125 : DenseMap<unsigned, unsigned> DstRegMap;
126 :
127 : bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg,
128 : MachineBasicBlock::iterator OldPos);
129 :
130 : bool isRevCopyChain(unsigned FromReg, unsigned ToReg, int Maxlen);
131 :
132 : bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef);
133 :
134 : bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
135 : MachineInstr *MI, unsigned Dist);
136 :
137 : bool commuteInstruction(MachineInstr *MI, unsigned DstIdx,
138 : unsigned RegBIdx, unsigned RegCIdx, unsigned Dist);
139 :
140 : bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB);
141 :
142 : bool convertInstTo3Addr(MachineBasicBlock::iterator &mi,
143 : MachineBasicBlock::iterator &nmi,
144 : unsigned RegA, unsigned RegB, unsigned Dist);
145 :
146 : bool isDefTooClose(unsigned Reg, unsigned Dist, MachineInstr *MI);
147 :
148 : bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
149 : MachineBasicBlock::iterator &nmi,
150 : unsigned Reg);
151 : bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
152 : MachineBasicBlock::iterator &nmi,
153 : unsigned Reg);
154 :
155 : bool tryInstructionTransform(MachineBasicBlock::iterator &mi,
156 : MachineBasicBlock::iterator &nmi,
157 : unsigned SrcIdx, unsigned DstIdx,
158 : unsigned Dist, bool shouldOnlyCommute);
159 :
160 : bool tryInstructionCommute(MachineInstr *MI,
161 : unsigned DstOpIdx,
162 : unsigned BaseOpIdx,
163 : bool BaseOpKilled,
164 : unsigned Dist);
165 : void scanUses(unsigned DstReg);
166 :
167 : void processCopy(MachineInstr *MI);
168 :
169 : using TiedPairList = SmallVector<std::pair<unsigned, unsigned>, 4>;
170 : using TiedOperandMap = SmallDenseMap<unsigned, TiedPairList>;
171 :
172 : bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&);
173 : void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist);
174 : void eliminateRegSequence(MachineBasicBlock::iterator&);
175 :
176 : public:
177 : static char ID; // Pass identification, replacement for typeid
178 :
179 27456 : TwoAddressInstructionPass() : MachineFunctionPass(ID) {
180 27456 : initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry());
181 27456 : }
182 :
183 27262 : void getAnalysisUsage(AnalysisUsage &AU) const override {
184 27262 : AU.setPreservesCFG();
185 : AU.addUsedIfAvailable<AAResultsWrapperPass>();
186 : AU.addUsedIfAvailable<LiveVariables>();
187 : AU.addPreserved<LiveVariables>();
188 : AU.addPreserved<SlotIndexes>();
189 : AU.addPreserved<LiveIntervals>();
190 27262 : AU.addPreservedID(MachineLoopInfoID);
191 27262 : AU.addPreservedID(MachineDominatorsID);
192 27262 : MachineFunctionPass::getAnalysisUsage(AU);
193 27262 : }
194 :
195 : /// Pass entry point.
196 : bool runOnMachineFunction(MachineFunction&) override;
197 : };
198 :
199 : } // end anonymous namespace
200 :
201 : char TwoAddressInstructionPass::ID = 0;
202 :
203 : char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID;
204 :
205 31780 : INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, DEBUG_TYPE,
206 : "Two-Address instruction pass", false, false)
207 31780 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
208 112603 : INITIALIZE_PASS_END(TwoAddressInstructionPass, DEBUG_TYPE,
209 : "Two-Address instruction pass", false, false)
210 :
211 : static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, LiveIntervals *LIS);
212 :
213 : /// A two-address instruction has been converted to a three-address instruction
214 : /// to avoid clobbering a register. Try to sink it past the instruction that
215 : /// would kill the above mentioned register to reduce register pressure.
216 8410 : bool TwoAddressInstructionPass::
217 : sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg,
218 : MachineBasicBlock::iterator OldPos) {
219 : // FIXME: Shouldn't we be trying to do this before we three-addressify the
220 : // instruction? After this transformation is done, we no longer need
221 : // the instruction to be in three-address form.
222 :
223 : // Check if it's safe to move this instruction.
224 8410 : bool SeenStore = true; // Be conservative.
225 8410 : if (!MI->isSafeToMove(AA, SeenStore))
226 : return false;
227 :
228 : unsigned DefReg = 0;
229 8367 : SmallSet<unsigned, 4> UseRegs;
230 :
231 58714 : for (const MachineOperand &MO : MI->operands()) {
232 50695 : if (!MO.isReg())
233 : continue;
234 33709 : unsigned MOReg = MO.getReg();
235 33709 : if (!MOReg)
236 : continue;
237 19869 : if (MO.isUse() && MOReg != SavedReg)
238 2648 : UseRegs.insert(MO.getReg());
239 19869 : if (!MO.isDef())
240 : continue;
241 8715 : if (MO.isImplicit())
242 : // Don't try to move it if it implicitly defines a register.
243 : return false;
244 8367 : if (DefReg)
245 : // For now, don't move any instructions that define multiple registers.
246 : return false;
247 8367 : DefReg = MO.getReg();
248 : }
249 :
250 : // Find the instruction that kills SavedReg.
251 : MachineInstr *KillMI = nullptr;
252 8019 : if (LIS) {
253 0 : LiveInterval &LI = LIS->getInterval(SavedReg);
254 : assert(LI.end() != LI.begin() &&
255 : "Reg should not have empty live interval.");
256 :
257 0 : SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
258 0 : LiveInterval::const_iterator I = LI.find(MBBEndIdx);
259 0 : if (I != LI.end() && I->start < MBBEndIdx)
260 : return false;
261 :
262 : --I;
263 : KillMI = LIS->getInstructionFromIndex(I->end);
264 : }
265 0 : if (!KillMI) {
266 57903 : for (MachineOperand &UseMO : MRI->use_nodbg_operands(SavedReg)) {
267 49447 : if (!UseMO.isKill())
268 : continue;
269 7582 : KillMI = UseMO.getParent();
270 7582 : break;
271 : }
272 : }
273 :
274 : // If we find the instruction that kills SavedReg, and it is in an
275 : // appropriate location, we can try to sink the current instruction
276 : // past it.
277 7582 : if (!KillMI || KillMI->getParent() != MBB || KillMI == MI ||
278 9935 : MachineBasicBlock::iterator(KillMI) == OldPos || KillMI->isTerminator())
279 6103 : return false;
280 :
281 : // If any of the definitions are used by another instruction between the
282 : // position and the kill use, then it's not safe to sink it.
283 : //
284 : // FIXME: This can be sped up if there is an easy way to query whether an
285 : // instruction is before or after another instruction. Then we can use
286 : // MachineRegisterInfo def / use instead.
287 : MachineOperand *KillMO = nullptr;
288 : MachineBasicBlock::iterator KillPos = KillMI;
289 : ++KillPos;
290 :
291 : unsigned NumVisited = 0;
292 5552 : for (MachineInstr &OtherMI : make_range(std::next(OldPos), KillPos)) {
293 : // Debug instructions cannot be counted against the limit.
294 : if (OtherMI.isDebugInstr())
295 : continue;
296 4593 : if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost.
297 : return false;
298 4588 : ++NumVisited;
299 24259 : for (unsigned i = 0, e = OtherMI.getNumOperands(); i != e; ++i) {
300 21227 : MachineOperand &MO = OtherMI.getOperand(i);
301 21227 : if (!MO.isReg())
302 9963 : continue;
303 15241 : unsigned MOReg = MO.getReg();
304 15241 : if (!MOReg)
305 : continue;
306 11264 : if (DefReg == MOReg)
307 1556 : return false;
308 :
309 9754 : if (MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS))) {
310 2073 : if (&OtherMI == KillMI && MOReg == SavedReg)
311 : // Save the operand that kills the register. We want to unset the kill
312 : // marker if we can sink MI past it.
313 : KillMO = &MO;
314 1577 : else if (UseRegs.count(MOReg))
315 : // One of the uses is killed before the destination.
316 : return false;
317 : }
318 : }
319 : }
320 : assert(KillMO && "Didn't find kill");
321 :
322 355 : if (!LIS) {
323 : // Update kill and LV information.
324 : KillMO->setIsKill(false);
325 355 : KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
326 : KillMO->setIsKill(true);
327 :
328 355 : if (LV)
329 355 : LV->replaceKillInstruction(SavedReg, *KillMI, *MI);
330 : }
331 :
332 : // Move instruction to its destination.
333 355 : MBB->remove(MI);
334 355 : MBB->insert(KillPos, MI);
335 :
336 355 : if (LIS)
337 0 : LIS->handleMove(*MI);
338 :
339 : ++Num3AddrSunk;
340 : return true;
341 : }
342 :
343 : /// Return the MachineInstr* if it is the single def of the Reg in current BB.
344 57645 : static MachineInstr *getSingleDef(unsigned Reg, MachineBasicBlock *BB,
345 : const MachineRegisterInfo *MRI) {
346 : MachineInstr *Ret = nullptr;
347 113748 : for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
348 81462 : if (DefMI.getParent() != BB || DefMI.isDebugValue())
349 : continue;
350 75186 : if (!Ret)
351 : Ret = &DefMI;
352 25359 : else if (Ret != &DefMI)
353 : return nullptr;
354 : }
355 : return Ret;
356 : }
357 :
358 : /// Check if there is a reversed copy chain from FromReg to ToReg:
359 : /// %Tmp1 = copy %Tmp2;
360 : /// %FromReg = copy %Tmp1;
361 : /// %ToReg = add %FromReg ...
362 : /// %Tmp2 = copy %ToReg;
363 : /// MaxLen specifies the maximum length of the copy chain the func
364 : /// can walk through.
365 0 : bool TwoAddressInstructionPass::isRevCopyChain(unsigned FromReg, unsigned ToReg,
366 : int Maxlen) {
367 : unsigned TmpReg = FromReg;
368 0 : for (int i = 0; i < Maxlen; i++) {
369 0 : MachineInstr *Def = getSingleDef(TmpReg, MBB, MRI);
370 0 : if (!Def || !Def->isCopy())
371 0 : return false;
372 :
373 0 : TmpReg = Def->getOperand(1).getReg();
374 :
375 0 : if (TmpReg == ToReg)
376 0 : return true;
377 : }
378 : return false;
379 : }
380 :
381 : /// Return true if there are no intervening uses between the last instruction
382 : /// in the MBB that defines the specified register and the two-address
383 : /// instruction which is being processed. It also returns the last def location
384 : /// by reference.
385 53437 : bool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist,
386 : unsigned &LastDef) {
387 53437 : LastDef = 0;
388 : unsigned LastUse = Dist;
389 290294 : for (MachineOperand &MO : MRI->reg_operands(Reg)) {
390 183420 : MachineInstr *MI = MO.getParent();
391 183420 : if (MI->getParent() != MBB || MI->isDebugValue())
392 13923 : continue;
393 169558 : DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
394 169558 : if (DI == DistanceMap.end())
395 : continue;
396 169497 : if (MO.isUse() && DI->second < LastUse)
397 : LastUse = DI->second;
398 169497 : if (MO.isDef() && DI->second > LastDef)
399 74078 : LastDef = DI->second;
400 : }
401 :
402 53437 : return !(LastUse > LastDef && LastUse < Dist);
403 : }
404 :
405 : /// Return true if the specified MI is a copy instruction or an extract_subreg
406 : /// instruction. It also returns the source and destination registers and
407 : /// whether they are physical registers by reference.
408 0 : static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII,
409 : unsigned &SrcReg, unsigned &DstReg,
410 : bool &IsSrcPhys, bool &IsDstPhys) {
411 0 : SrcReg = 0;
412 0 : DstReg = 0;
413 39842291 : if (MI.isCopy()) {
414 0 : DstReg = MI.getOperand(0).getReg();
415 7928161 : SrcReg = MI.getOperand(1).getReg();
416 31914130 : } else if (MI.isInsertSubreg() || MI.isSubregToReg()) {
417 0 : DstReg = MI.getOperand(0).getReg();
418 230179 : SrcReg = MI.getOperand(2).getReg();
419 : } else
420 0 : return false;
421 :
422 0 : IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
423 0 : IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
424 0 : return true;
425 : }
426 :
427 : /// Test if the given register value, which is used by the
428 : /// given instruction, is killed by the given instruction.
429 420624 : static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg,
430 : LiveIntervals *LIS) {
431 420624 : if (LIS && TargetRegisterInfo::isVirtualRegister(Reg) &&
432 0 : !LIS->isNotInMIMap(*MI)) {
433 : // FIXME: Sometimes tryInstructionTransform() will add instructions and
434 : // test whether they can be folded before keeping them. In this case it
435 : // sets a kill before recursively calling tryInstructionTransform() again.
436 : // If there is no interval available, we assume that this instruction is
437 : // one of those. A kill flag is manually inserted on the operand so the
438 : // check below will handle it.
439 0 : LiveInterval &LI = LIS->getInterval(Reg);
440 : // This is to match the kill flag version where undefs don't have kill
441 : // flags.
442 0 : if (!LI.hasAtLeastOneValue())
443 : return false;
444 :
445 0 : SlotIndex useIdx = LIS->getInstructionIndex(*MI);
446 0 : LiveInterval::const_iterator I = LI.find(useIdx);
447 : assert(I != LI.end() && "Reg must be live-in to use.");
448 0 : return !I->end.isBlock() && SlotIndex::isSameInstr(I->end, useIdx);
449 : }
450 :
451 420624 : return MI->killsRegister(Reg);
452 : }
453 :
454 : /// Test if the given register value, which is used by the given
455 : /// instruction, is killed by the given instruction. This looks through
456 : /// coalescable copies to see if the original value is potentially not killed.
457 : ///
458 : /// For example, in this code:
459 : ///
460 : /// %reg1034 = copy %reg1024
461 : /// %reg1035 = copy killed %reg1025
462 : /// %reg1036 = add killed %reg1034, killed %reg1035
463 : ///
464 : /// %reg1034 is not considered to be killed, since it is copied from a
465 : /// register which is not killed. Treating it as not killed lets the
466 : /// normal heuristics commute the (two-address) add, which lets
467 : /// coalescing eliminate the extra copy.
468 : ///
469 : /// If allowFalsePositives is true then likely kills are treated as kills even
470 : /// if it can't be proven that they are kills.
471 337694 : static bool isKilled(MachineInstr &MI, unsigned Reg,
472 : const MachineRegisterInfo *MRI,
473 : const TargetInstrInfo *TII,
474 : LiveIntervals *LIS,
475 : bool allowFalsePositives) {
476 : MachineInstr *DefMI = &MI;
477 : while (true) {
478 : // All uses of physical registers are likely to be kills.
479 418319 : if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
480 9733 : (allowFalsePositives || MRI->hasOneUse(Reg)))
481 48591 : return true;
482 369728 : if (!isPlainlyKilled(DefMI, Reg, LIS))
483 : return false;
484 314088 : if (TargetRegisterInfo::isPhysicalRegister(Reg))
485 : return true;
486 311090 : MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg);
487 : // If there are multiple defs, we can't do a simple analysis, so just
488 : // go with what the kill flag says.
489 311090 : if (std::next(Begin) != MRI->def_end())
490 : return true;
491 231269 : DefMI = Begin->getParent();
492 : bool IsSrcPhys, IsDstPhys;
493 : unsigned SrcReg, DstReg;
494 : // If the def is something other than a copy, then it isn't going to
495 : // be coalesced, so follow the kill flag.
496 231269 : if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
497 : return true;
498 : Reg = SrcReg;
499 80625 : }
500 : }
501 :
502 : /// Return true if the specified MI uses the specified register as a two-address
503 : /// use. If so, return the destination register by reference.
504 1755582 : static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) {
505 10732250 : for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) {
506 9180415 : const MachineOperand &MO = MI.getOperand(i);
507 9180415 : if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
508 7424198 : continue;
509 : unsigned ti;
510 1756217 : if (MI.isRegTiedToDefOperand(i, &ti)) {
511 203747 : DstReg = MI.getOperand(ti).getReg();
512 203747 : return true;
513 : }
514 : }
515 : return false;
516 : }
517 :
518 : /// Given a register, if has a single in-basic block use, return the use
519 : /// instruction if it's a copy or a two-address use.
520 : static
521 0 : MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB,
522 : MachineRegisterInfo *MRI,
523 : const TargetInstrInfo *TII,
524 : bool &IsCopy,
525 : unsigned &DstReg, bool &IsDstPhys) {
526 0 : if (!MRI->hasOneNonDBGUse(Reg))
527 : // None or more than one use.
528 0 : return nullptr;
529 0 : MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(Reg);
530 0 : if (UseMI.getParent() != MBB)
531 0 : return nullptr;
532 : unsigned SrcReg;
533 : bool IsSrcPhys;
534 : if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
535 0 : IsCopy = true;
536 0 : return &UseMI;
537 : }
538 0 : IsDstPhys = false;
539 0 : if (isTwoAddrUse(UseMI, Reg, DstReg)) {
540 0 : IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
541 0 : return &UseMI;
542 : }
543 : return nullptr;
544 : }
545 :
546 : /// Return the physical register the specified virtual register might be mapped
547 : /// to.
548 : static unsigned
549 123602 : getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) {
550 492910 : while (TargetRegisterInfo::isVirtualRegister(Reg)) {
551 200217 : DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg);
552 200217 : if (SI == RegMap.end())
553 77364 : return 0;
554 122853 : Reg = SI->second;
555 : }
556 46238 : if (TargetRegisterInfo::isPhysicalRegister(Reg))
557 46238 : return Reg;
558 : return 0;
559 : }
560 :
561 : /// Return true if the two registers are equal or aliased.
562 : static bool
563 : regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) {
564 20362 : if (RegA == RegB)
565 : return true;
566 : if (!RegA || !RegB)
567 : return false;
568 9975 : return TRI->regsOverlap(RegA, RegB);
569 : }
570 :
571 : // Returns true if Reg is equal or aliased to at least one register in Set.
572 48603 : static bool regOverlapsSet(const SmallVectorImpl<unsigned> &Set, unsigned Reg,
573 : const TargetRegisterInfo *TRI) {
574 106674 : for (unsigned R : Set)
575 63071 : if (TRI->regsOverlap(R, Reg))
576 : return true;
577 :
578 : return false;
579 : }
580 :
581 : /// Return true if it's potentially profitable to commute the two-address
582 : /// instruction that's being processed.
583 : bool
584 50896 : TwoAddressInstructionPass::
585 : isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
586 : MachineInstr *MI, unsigned Dist) {
587 50896 : if (OptLevel == CodeGenOpt::None)
588 : return false;
589 :
590 : // Determine if it's profitable to commute this two address instruction. In
591 : // general, we want no uses between this instruction and the definition of
592 : // the two-address register.
593 : // e.g.
594 : // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1
595 : // %reg1029 = COPY %reg1028
596 : // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags
597 : // insert => %reg1030 = COPY %reg1028
598 : // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags
599 : // In this case, it might not be possible to coalesce the second COPY
600 : // instruction if the first one is coalesced. So it would be profitable to
601 : // commute it:
602 : // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1
603 : // %reg1029 = COPY %reg1028
604 : // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags
605 : // insert => %reg1030 = COPY %reg1029
606 : // %reg1030 = ADD8rr killed %reg1029, killed %reg1028, implicit dead %eflags
607 :
608 50896 : if (!isPlainlyKilled(MI, regC, LIS))
609 : return false;
610 :
611 : // Ok, we have something like:
612 : // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags
613 : // let's see if it's worth commuting it.
614 :
615 : // Look for situations like this:
616 : // %reg1024 = MOV r1
617 : // %reg1025 = MOV r0
618 : // %reg1026 = ADD %reg1024, %reg1025
619 : // r0 = MOV %reg1026
620 : // Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
621 37102 : unsigned ToRegA = getMappedReg(regA, DstRegMap);
622 37102 : if (ToRegA) {
623 15013 : unsigned FromRegB = getMappedReg(regB, SrcRegMap);
624 15013 : unsigned FromRegC = getMappedReg(regC, SrcRegMap);
625 18076 : bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA, TRI);
626 20902 : bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA, TRI);
627 :
628 : // Compute if any of the following are true:
629 : // -RegB is not tied to a register and RegC is compatible with RegA.
630 : // -RegB is tied to the wrong physical register, but RegC is.
631 : // -RegB is tied to the wrong physical register, and RegC isn't tied.
632 15013 : if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC)))
633 : return true;
634 : // Don't compute if any of the following are true:
635 : // -RegC is not tied to a register and RegB is compatible with RegA.
636 : // -RegC is tied to the wrong physical register, but RegB is.
637 : // -RegC is tied to the wrong physical register, and RegB isn't tied.
638 12803 : if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB)))
639 : return false;
640 : }
641 :
642 : // If there is a use of regC between its last def (could be livein) and this
643 : // instruction, then bail.
644 28396 : unsigned LastDefC = 0;
645 28396 : if (!noUseAfterLastDef(regC, Dist, LastDefC))
646 : return false;
647 :
648 : // If there is a use of regB between its last def (could be livein) and this
649 : // instruction, then go ahead and make this transformation.
650 25041 : unsigned LastDefB = 0;
651 25041 : if (!noUseAfterLastDef(regB, Dist, LastDefB))
652 : return true;
653 :
654 : // Look for situation like this:
655 : // %reg101 = MOV %reg100
656 : // %reg102 = ...
657 : // %reg103 = ADD %reg102, %reg101
658 : // ... = %reg103 ...
659 : // %reg100 = MOV %reg103
660 : // If there is a reversed copy chain from reg101 to reg103, commute the ADD
661 : // to eliminate an otherwise unavoidable copy.
662 : // FIXME:
663 : // We can extend the logic further: If an pair of operands in an insn has
664 : // been merged, the insn could be regarded as a virtual copy, and the virtual
665 : // copy could also be used to construct a copy chain.
666 : // To more generally minimize register copies, ideally the logic of two addr
667 : // instruction pass should be integrated with register allocation pass where
668 : // interference graph is available.
669 23897 : if (isRevCopyChain(regC, regA, MaxDataFlowEdge))
670 : return true;
671 :
672 23863 : if (isRevCopyChain(regB, regA, MaxDataFlowEdge))
673 : return false;
674 :
675 : // Since there are no intervening uses for both registers, then commute
676 : // if the def of regC is closer. Its live interval is shorter.
677 23663 : return LastDefB && LastDefC && LastDefC > LastDefB;
678 : }
679 :
680 : /// Commute a two-address instruction and update the basic block, distance map,
681 : /// and live variables if needed. Return true if it is successful.
682 0 : bool TwoAddressInstructionPass::commuteInstruction(MachineInstr *MI,
683 : unsigned DstIdx,
684 : unsigned RegBIdx,
685 : unsigned RegCIdx,
686 : unsigned Dist) {
687 0 : unsigned RegC = MI->getOperand(RegCIdx).getReg();
688 : LLVM_DEBUG(dbgs() << "2addr: COMMUTING : " << *MI);
689 0 : MachineInstr *NewMI = TII->commuteInstruction(*MI, false, RegBIdx, RegCIdx);
690 :
691 0 : if (NewMI == nullptr) {
692 : LLVM_DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
693 0 : return false;
694 : }
695 :
696 : LLVM_DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI);
697 : assert(NewMI == MI &&
698 : "TargetInstrInfo::commuteInstruction() should not return a new "
699 : "instruction unless it was requested.");
700 :
701 : // Update source register map.
702 0 : unsigned FromRegC = getMappedReg(RegC, SrcRegMap);
703 0 : if (FromRegC) {
704 0 : unsigned RegA = MI->getOperand(DstIdx).getReg();
705 0 : SrcRegMap[RegA] = FromRegC;
706 : }
707 :
708 : return true;
709 : }
710 :
711 : /// Return true if it is profitable to convert the given 2-address instruction
712 : /// to a 3-address one.
713 : bool
714 30578 : TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){
715 : // Look for situations like this:
716 : // %reg1024 = MOV r1
717 : // %reg1025 = MOV r0
718 : // %reg1026 = ADD %reg1024, %reg1025
719 : // r2 = MOV %reg1026
720 : // Turn ADD into a 3-address instruction to avoid a copy.
721 30578 : unsigned FromRegB = getMappedReg(RegB, SrcRegMap);
722 30578 : if (!FromRegB)
723 : return false;
724 4951 : unsigned ToRegA = getMappedReg(RegA, DstRegMap);
725 5974 : return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI));
726 : }
727 :
728 : /// Convert the specified two-address instruction into a three address one.
729 : /// Return true if this transformation was successful.
730 : bool
731 11001 : TwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi,
732 : MachineBasicBlock::iterator &nmi,
733 : unsigned RegA, unsigned RegB,
734 : unsigned Dist) {
735 : // FIXME: Why does convertToThreeAddress() need an iterator reference?
736 11001 : MachineFunction::iterator MFI = MBB->getIterator();
737 22002 : MachineInstr *NewMI = TII->convertToThreeAddress(MFI, *mi, LV);
738 : assert(MBB->getIterator() == MFI &&
739 : "convertToThreeAddress changed iterator reference");
740 11001 : if (!NewMI)
741 : return false;
742 :
743 : LLVM_DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
744 : LLVM_DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI);
745 : bool Sunk = false;
746 :
747 9352 : if (LIS)
748 0 : LIS->ReplaceMachineInstrInMaps(*mi, *NewMI);
749 :
750 17762 : if (NewMI->findRegisterUseOperand(RegB, false, TRI))
751 : // FIXME: Temporary workaround. If the new instruction doesn't
752 : // uses RegB, convertToThreeAddress must have created more
753 : // then one instruction.
754 8410 : Sunk = sink3AddrInstruction(NewMI, RegB, mi);
755 :
756 9352 : MBB->erase(mi); // Nuke the old inst.
757 :
758 9352 : if (!Sunk) {
759 8997 : DistanceMap.insert(std::make_pair(NewMI, Dist));
760 8997 : mi = NewMI;
761 8997 : nmi = std::next(mi);
762 : }
763 : else
764 355 : SunkInstrs.insert(NewMI);
765 :
766 : // Update source and destination register maps.
767 9352 : SrcRegMap.erase(RegA);
768 9352 : DstRegMap.erase(RegB);
769 9352 : return true;
770 : }
771 :
772 : /// Scan forward recursively for only uses, update maps if the use is a copy or
773 : /// a two-address instruction.
774 : void
775 2426878 : TwoAddressInstructionPass::scanUses(unsigned DstReg) {
776 : SmallVector<unsigned, 4> VirtRegPairs;
777 : bool IsDstPhys;
778 2426878 : bool IsCopy = false;
779 2426878 : unsigned NewReg = 0;
780 : unsigned Reg = DstReg;
781 3806356 : while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy,
782 3806356 : NewReg, IsDstPhys)) {
783 1728077 : if (IsCopy && !Processed.insert(UseMI).second)
784 : break;
785 :
786 1689189 : DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
787 1689189 : if (DI != DistanceMap.end())
788 : // Earlier in the same MBB.Reached via a back edge.
789 : break;
790 :
791 1689189 : if (IsDstPhys) {
792 309711 : VirtRegPairs.push_back(NewReg);
793 309711 : break;
794 : }
795 1379478 : bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second;
796 : if (!isNew)
797 : assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!");
798 1379478 : VirtRegPairs.push_back(NewReg);
799 1379478 : Reg = NewReg;
800 : }
801 :
802 2426878 : if (!VirtRegPairs.empty()) {
803 1450712 : unsigned ToReg = VirtRegPairs.back();
804 : VirtRegPairs.pop_back();
805 1689189 : while (!VirtRegPairs.empty()) {
806 238477 : unsigned FromReg = VirtRegPairs.back();
807 : VirtRegPairs.pop_back();
808 238477 : bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
809 : if (!isNew)
810 : assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!");
811 : ToReg = FromReg;
812 : }
813 1450712 : bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second;
814 : if (!isNew)
815 : assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!");
816 : }
817 2426878 : }
818 :
819 : /// If the specified instruction is not yet processed, process it if it's a
820 : /// copy. For a copy instruction, we find the physical registers the
821 : /// source and destination registers might be mapped to. These are kept in
822 : /// point-to maps used to determine future optimizations. e.g.
823 : /// v1024 = mov r0
824 : /// v1025 = mov r1
825 : /// v1026 = add v1024, v1025
826 : /// r1 = mov r1026
827 : /// If 'add' is a two-address instruction, v1024, v1026 are both potentially
828 : /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
829 : /// potentially joined with r1 on the output side. It's worthwhile to commute
830 : /// 'add' to eliminate a copy.
831 41125861 : void TwoAddressInstructionPass::processCopy(MachineInstr *MI) {
832 41125861 : if (Processed.count(MI))
833 : return;
834 :
835 : bool IsSrcPhys, IsDstPhys;
836 : unsigned SrcReg, DstReg;
837 39611022 : if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
838 : return;
839 :
840 8077715 : if (IsDstPhys && !IsSrcPhys)
841 4008175 : DstRegMap.insert(std::make_pair(SrcReg, DstReg));
842 4069540 : else if (!IsDstPhys && IsSrcPhys) {
843 2149310 : bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
844 : if (!isNew)
845 : assert(SrcRegMap[DstReg] == SrcReg &&
846 : "Can't map to two src physical registers!");
847 :
848 2149310 : scanUses(DstReg);
849 : }
850 :
851 8077715 : Processed.insert(MI);
852 : }
853 :
854 : /// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
855 : /// consider moving the instruction below the kill instruction in order to
856 : /// eliminate the need for the copy.
857 256395 : bool TwoAddressInstructionPass::
858 : rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
859 : MachineBasicBlock::iterator &nmi,
860 : unsigned Reg) {
861 : // Bail immediately if we don't have LV or LIS available. We use them to find
862 : // kills efficiently.
863 256395 : if (!LV && !LIS)
864 : return false;
865 :
866 : MachineInstr *MI = &*mi;
867 256363 : DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
868 256363 : if (DI == DistanceMap.end())
869 : // Must be created from unfolded load. Don't waste time trying this.
870 : return false;
871 :
872 : MachineInstr *KillMI = nullptr;
873 256363 : if (LIS) {
874 0 : LiveInterval &LI = LIS->getInterval(Reg);
875 : assert(LI.end() != LI.begin() &&
876 : "Reg should not have empty live interval.");
877 :
878 0 : SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
879 0 : LiveInterval::const_iterator I = LI.find(MBBEndIdx);
880 0 : if (I != LI.end() && I->start < MBBEndIdx)
881 : return false;
882 :
883 : --I;
884 : KillMI = LIS->getInstructionFromIndex(I->end);
885 : } else {
886 256363 : KillMI = LV->getVarInfo(Reg).findKill(MBB);
887 : }
888 256363 : if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
889 : // Don't mess with copies, they may be coalesced later.
890 : return false;
891 :
892 55490 : if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() ||
893 36999 : KillMI->isBranch() || KillMI->isTerminator())
894 : // Don't move pass calls, etc.
895 17 : return false;
896 :
897 : unsigned DstReg;
898 18491 : if (isTwoAddrUse(*KillMI, Reg, DstReg))
899 : return false;
900 :
901 7552 : bool SeenStore = true;
902 7552 : if (!MI->isSafeToMove(AA, SeenStore))
903 : return false;
904 :
905 7007 : if (TII->getInstrLatency(InstrItins, *MI) > 1)
906 : // FIXME: Needs more sophisticated heuristics.
907 : return false;
908 :
909 : SmallVector<unsigned, 2> Uses;
910 : SmallVector<unsigned, 2> Kills;
911 : SmallVector<unsigned, 2> Defs;
912 31890 : for (const MachineOperand &MO : MI->operands()) {
913 25042 : if (!MO.isReg())
914 3638 : continue;
915 21440 : unsigned MOReg = MO.getReg();
916 21440 : if (!MOReg)
917 : continue;
918 21404 : if (MO.isDef())
919 10095 : Defs.push_back(MOReg);
920 : else {
921 11309 : Uses.push_back(MOReg);
922 11309 : if (MOReg != Reg && (MO.isKill() ||
923 2593 : (LIS && isPlainlyKilled(MI, MOReg, LIS))))
924 1425 : Kills.push_back(MOReg);
925 : }
926 : }
927 :
928 : // Move the copies connected to MI down as well.
929 : MachineBasicBlock::iterator Begin = MI;
930 6848 : MachineBasicBlock::iterator AfterMI = std::next(Begin);
931 : MachineBasicBlock::iterator End = AfterMI;
932 7747 : while (End->isCopy() &&
933 556 : regOverlapsSet(Defs, End->getOperand(1).getReg(), TRI)) {
934 343 : Defs.push_back(End->getOperand(0).getReg());
935 : ++End;
936 : }
937 :
938 : // Check if the reschedule will not break dependencies.
939 : unsigned NumVisited = 0;
940 : MachineBasicBlock::iterator KillPos = KillMI;
941 : ++KillPos;
942 13175 : for (MachineInstr &OtherMI : make_range(End, KillPos)) {
943 : // Debug instructions cannot be counted against the limit.
944 : if (OtherMI.isDebugInstr())
945 : continue;
946 10853 : if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
947 : return false;
948 10796 : ++NumVisited;
949 32378 : if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
950 21584 : OtherMI.isBranch() || OtherMI.isTerminator())
951 : // Don't move pass calls, etc.
952 8 : return false;
953 44094 : for (const MachineOperand &MO : OtherMI.operands()) {
954 38428 : if (!MO.isReg())
955 : continue;
956 30864 : unsigned MOReg = MO.getReg();
957 30864 : if (!MOReg)
958 : continue;
959 25771 : if (MO.isDef()) {
960 10052 : if (regOverlapsSet(Uses, MOReg, TRI))
961 : // Physical register use would be clobbered.
962 : return false;
963 9804 : if (!MO.isDead() && regOverlapsSet(Defs, MOReg, TRI))
964 : // May clobber a physical register def.
965 : // FIXME: This may be too conservative. It's ok if the instruction
966 : // is sunken completely below the use.
967 : return false;
968 : } else {
969 15719 : if (regOverlapsSet(Defs, MOReg, TRI))
970 : return false;
971 : bool isKill =
972 12039 : MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS));
973 21073 : if (MOReg != Reg && ((isKill && regOverlapsSet(Uses, MOReg, TRI)) ||
974 9034 : regOverlapsSet(Kills, MOReg, TRI)))
975 : // Don't want to extend other live ranges and update kills.
976 507 : return false;
977 11532 : if (MOReg == Reg && !isKill)
978 : // We can't schedule across a use of the register in question.
979 : return false;
980 : // Ensure that if this is register in question, its the kill we expect.
981 : assert((MOReg != Reg || &OtherMI == KillMI) &&
982 : "Found multiple kills of a register in a basic block");
983 : }
984 : }
985 : }
986 :
987 : // Move debug info as well.
988 6011 : while (Begin != MBB->begin() && std::prev(Begin)->isDebugInstr())
989 : --Begin;
990 :
991 1661 : nmi = End;
992 : MachineBasicBlock::iterator InsertPos = KillPos;
993 1661 : if (LIS) {
994 : // We have to move the copies first so that the MBB is still well-formed
995 : // when calling handleMove().
996 0 : for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) {
997 : auto CopyMI = MBBI++;
998 0 : MBB->splice(InsertPos, MBB, CopyMI);
999 0 : LIS->handleMove(*CopyMI);
1000 : InsertPos = CopyMI;
1001 : }
1002 0 : End = std::next(MachineBasicBlock::iterator(MI));
1003 : }
1004 :
1005 : // Copies following MI may have been moved as well.
1006 1661 : MBB->splice(InsertPos, MBB, Begin, End);
1007 : DistanceMap.erase(DI);
1008 :
1009 : // Update live variables
1010 1661 : if (LIS) {
1011 0 : LIS->handleMove(*MI);
1012 : } else {
1013 1661 : LV->removeVirtualRegisterKilled(Reg, *KillMI);
1014 1661 : LV->addVirtualRegisterKilled(Reg, *MI);
1015 : }
1016 :
1017 : LLVM_DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI);
1018 : return true;
1019 : }
1020 :
1021 : /// Return true if the re-scheduling will put the given instruction too close
1022 : /// to the defs of its register dependencies.
1023 6435 : bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist,
1024 : MachineInstr *MI) {
1025 20890 : for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
1026 10196 : if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike())
1027 6318 : continue;
1028 3878 : if (&DefMI == MI)
1029 2176 : return true; // MI is defining something KillMI uses
1030 3177 : DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(&DefMI);
1031 3177 : if (DDI == DistanceMap.end())
1032 : return true; // Below MI
1033 1867 : unsigned DefDist = DDI->second;
1034 : assert(Dist > DefDist && "Visited def already?");
1035 1867 : if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist))
1036 : return true;
1037 : }
1038 : return false;
1039 : }
1040 :
1041 : /// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
1042 : /// consider moving the kill instruction above the current two-address
1043 : /// instruction in order to eliminate the need for the copy.
1044 245505 : bool TwoAddressInstructionPass::
1045 : rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
1046 : MachineBasicBlock::iterator &nmi,
1047 : unsigned Reg) {
1048 : // Bail immediately if we don't have LV or LIS available. We use them to find
1049 : // kills efficiently.
1050 245505 : if (!LV && !LIS)
1051 : return false;
1052 :
1053 : MachineInstr *MI = &*mi;
1054 245482 : DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
1055 245482 : if (DI == DistanceMap.end())
1056 : // Must be created from unfolded load. Don't waste time trying this.
1057 : return false;
1058 :
1059 : MachineInstr *KillMI = nullptr;
1060 245482 : if (LIS) {
1061 0 : LiveInterval &LI = LIS->getInterval(Reg);
1062 : assert(LI.end() != LI.begin() &&
1063 : "Reg should not have empty live interval.");
1064 :
1065 0 : SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
1066 0 : LiveInterval::const_iterator I = LI.find(MBBEndIdx);
1067 0 : if (I != LI.end() && I->start < MBBEndIdx)
1068 : return false;
1069 :
1070 : --I;
1071 : KillMI = LIS->getInstructionFromIndex(I->end);
1072 : } else {
1073 245482 : KillMI = LV->getVarInfo(Reg).findKill(MBB);
1074 : }
1075 245482 : if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
1076 : // Don't mess with copies, they may be coalesced later.
1077 : return false;
1078 :
1079 : unsigned DstReg;
1080 14973 : if (isTwoAddrUse(*KillMI, Reg, DstReg))
1081 : return false;
1082 :
1083 4582 : bool SeenStore = true;
1084 4582 : if (!KillMI->isSafeToMove(AA, SeenStore))
1085 : return false;
1086 :
1087 4053 : SmallSet<unsigned, 2> Uses;
1088 4053 : SmallSet<unsigned, 2> Kills;
1089 4053 : SmallSet<unsigned, 2> Defs;
1090 4053 : SmallSet<unsigned, 2> LiveDefs;
1091 12715 : for (const MachineOperand &MO : KillMI->operands()) {
1092 11135 : if (!MO.isReg())
1093 664 : continue;
1094 10567 : unsigned MOReg = MO.getReg();
1095 10567 : if (MO.isUse()) {
1096 6531 : if (!MOReg)
1097 : continue;
1098 6435 : if (isDefTooClose(MOReg, DI->second, MI))
1099 2473 : return false;
1100 4259 : bool isKill = MO.isKill() || (LIS && isPlainlyKilled(KillMI, MOReg, LIS));
1101 4259 : if (MOReg == Reg && !isKill)
1102 : return false;
1103 3962 : Uses.insert(MOReg);
1104 3962 : if (isKill && MOReg != Reg)
1105 1461 : Kills.insert(MOReg);
1106 4036 : } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
1107 755 : Defs.insert(MOReg);
1108 755 : if (!MO.isDead())
1109 418 : LiveDefs.insert(MOReg);
1110 : }
1111 : }
1112 :
1113 : // Check if the reschedule will not break depedencies.
1114 : unsigned NumVisited = 0;
1115 : for (MachineInstr &OtherMI :
1116 5926 : make_range(mi, MachineBasicBlock::iterator(KillMI))) {
1117 : // Debug instructions cannot be counted against the limit.
1118 : if (OtherMI.isDebugInstr())
1119 68 : continue;
1120 5507 : if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
1121 1229 : return false;
1122 5415 : ++NumVisited;
1123 16220 : if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
1124 10815 : OtherMI.isBranch() || OtherMI.isTerminator())
1125 : // Don't move pass calls, etc.
1126 15 : return false;
1127 : SmallVector<unsigned, 2> OtherDefs;
1128 23004 : for (const MachineOperand &MO : OtherMI.operands()) {
1129 18312 : if (!MO.isReg())
1130 3910 : continue;
1131 15543 : unsigned MOReg = MO.getReg();
1132 15543 : if (!MOReg)
1133 : continue;
1134 14402 : if (MO.isUse()) {
1135 8497 : if (Defs.count(MOReg))
1136 : // Moving KillMI can clobber the physical register if the def has
1137 : // not been seen.
1138 708 : return false;
1139 8475 : if (Kills.count(MOReg))
1140 : // Don't want to extend other live ranges and update kills.
1141 : return false;
1142 8000 : if (&OtherMI != MI && MOReg == Reg &&
1143 211 : !(MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS))))
1144 : // We can't schedule across a use of the register in question.
1145 211 : return false;
1146 : } else {
1147 5905 : OtherDefs.push_back(MOReg);
1148 : }
1149 : }
1150 :
1151 9369 : for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) {
1152 5091 : unsigned MOReg = OtherDefs[i];
1153 5091 : if (Uses.count(MOReg))
1154 414 : return false;
1155 5555 : if (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
1156 641 : LiveDefs.count(MOReg))
1157 : return false;
1158 : // Physical register def is seen.
1159 4677 : Defs.erase(MOReg);
1160 : }
1161 : }
1162 :
1163 : // Move the old kill above MI, don't forget to move debug info as well.
1164 351 : MachineBasicBlock::iterator InsertPos = mi;
1165 1107 : while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugInstr())
1166 : --InsertPos;
1167 : MachineBasicBlock::iterator From = KillMI;
1168 351 : MachineBasicBlock::iterator To = std::next(From);
1169 397 : while (std::prev(From)->isDebugInstr())
1170 : --From;
1171 351 : MBB->splice(InsertPos, MBB, From, To);
1172 :
1173 351 : nmi = std::prev(InsertPos); // Backtrack so we process the moved instr.
1174 : DistanceMap.erase(DI);
1175 :
1176 : // Update live variables
1177 351 : if (LIS) {
1178 0 : LIS->handleMove(*KillMI);
1179 : } else {
1180 351 : LV->removeVirtualRegisterKilled(Reg, *KillMI);
1181 351 : LV->addVirtualRegisterKilled(Reg, *MI);
1182 : }
1183 :
1184 : LLVM_DEBUG(dbgs() << "\trescheduled kill: " << *KillMI);
1185 : return true;
1186 : }
1187 :
1188 : /// Tries to commute the operand 'BaseOpIdx' and some other operand in the
1189 : /// given machine instruction to improve opportunities for coalescing and
1190 : /// elimination of a register to register copy.
1191 : ///
1192 : /// 'DstOpIdx' specifies the index of MI def operand.
1193 : /// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx'
1194 : /// operand is killed by the given instruction.
1195 : /// The 'Dist' arguments provides the distance of MI from the start of the
1196 : /// current basic block and it is used to determine if it is profitable
1197 : /// to commute operands in the instruction.
1198 : ///
1199 : /// Returns true if the transformation happened. Otherwise, returns false.
1200 277600 : bool TwoAddressInstructionPass::tryInstructionCommute(MachineInstr *MI,
1201 : unsigned DstOpIdx,
1202 : unsigned BaseOpIdx,
1203 : bool BaseOpKilled,
1204 : unsigned Dist) {
1205 277600 : if (!MI->isCommutable())
1206 : return false;
1207 :
1208 : bool MadeChange = false;
1209 59307 : unsigned DstOpReg = MI->getOperand(DstOpIdx).getReg();
1210 59307 : unsigned BaseOpReg = MI->getOperand(BaseOpIdx).getReg();
1211 59307 : unsigned OpsNum = MI->getDesc().getNumOperands();
1212 118614 : unsigned OtherOpIdx = MI->getDesc().getNumDefs();
1213 186360 : for (; OtherOpIdx < OpsNum; OtherOpIdx++) {
1214 : // The call of findCommutedOpIndices below only checks if BaseOpIdx
1215 : // and OtherOpIdx are commutable, it does not really search for
1216 : // other commutable operands and does not change the values of passed
1217 : // variables.
1218 202103 : if (OtherOpIdx == BaseOpIdx || !MI->getOperand(OtherOpIdx).isReg() ||
1219 68806 : !TII->findCommutedOpIndices(*MI, BaseOpIdx, OtherOpIdx))
1220 76156 : continue;
1221 :
1222 57141 : unsigned OtherOpReg = MI->getOperand(OtherOpIdx).getReg();
1223 : bool AggressiveCommute = false;
1224 :
1225 : // If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp
1226 : // operands. This makes the live ranges of DstOp and OtherOp joinable.
1227 57141 : bool OtherOpKilled = isKilled(*MI, OtherOpReg, MRI, TII, LIS, false);
1228 57141 : bool DoCommute = !BaseOpKilled && OtherOpKilled;
1229 :
1230 108037 : if (!DoCommute &&
1231 50896 : isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg, MI, Dist)) {
1232 : DoCommute = true;
1233 : AggressiveCommute = true;
1234 : }
1235 :
1236 : // If it's profitable to commute, try to do so.
1237 57141 : if (DoCommute && commuteInstruction(MI, DstOpIdx, BaseOpIdx, OtherOpIdx,
1238 : Dist)) {
1239 : MadeChange = true;
1240 : ++NumCommuted;
1241 20945 : if (AggressiveCommute) {
1242 : ++NumAggrCommuted;
1243 : // There might be more than two commutable operands, update BaseOp and
1244 : // continue scanning.
1245 : BaseOpReg = OtherOpReg;
1246 : BaseOpKilled = OtherOpKilled;
1247 : continue;
1248 : }
1249 : // If this was a commute based on kill, we won't do better continuing.
1250 : return MadeChange;
1251 : }
1252 : }
1253 : return MadeChange;
1254 : }
1255 :
1256 : /// For the case where an instruction has a single pair of tied register
1257 : /// operands, attempt some transformations that may either eliminate the tied
1258 : /// operands or improve the opportunities for coalescing away the register copy.
1259 : /// Returns true if no copy needs to be inserted to untie mi's operands
1260 : /// (either because they were untied, or because mi was rescheduled, and will
1261 : /// be visited again later). If the shouldOnlyCommute flag is true, only
1262 : /// instruction commutation is attempted.
1263 1376686 : bool TwoAddressInstructionPass::
1264 : tryInstructionTransform(MachineBasicBlock::iterator &mi,
1265 : MachineBasicBlock::iterator &nmi,
1266 : unsigned SrcIdx, unsigned DstIdx,
1267 : unsigned Dist, bool shouldOnlyCommute) {
1268 1376686 : if (OptLevel == CodeGenOpt::None)
1269 : return false;
1270 :
1271 : MachineInstr &MI = *mi;
1272 555200 : unsigned regA = MI.getOperand(DstIdx).getReg();
1273 277600 : unsigned regB = MI.getOperand(SrcIdx).getReg();
1274 :
1275 : assert(TargetRegisterInfo::isVirtualRegister(regB) &&
1276 : "cannot make instruction into two-address form");
1277 277600 : bool regBKilled = isKilled(MI, regB, MRI, TII, LIS, true);
1278 :
1279 277600 : if (TargetRegisterInfo::isVirtualRegister(regA))
1280 277568 : scanUses(regA);
1281 :
1282 277600 : bool Commuted = tryInstructionCommute(&MI, DstIdx, SrcIdx, regBKilled, Dist);
1283 :
1284 : // If the instruction is convertible to 3 Addr, instead
1285 : // of returning try 3 Addr transformation aggresively and
1286 : // use this variable to check later. Because it might be better.
1287 : // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret`
1288 : // instead of the following code.
1289 : // addl %esi, %edi
1290 : // movl %edi, %eax
1291 : // ret
1292 298531 : if (Commuted && !MI.isConvertibleTo3Addr())
1293 : return false;
1294 :
1295 259815 : if (shouldOnlyCommute)
1296 : return false;
1297 :
1298 : // If there is one more use of regB later in the same MBB, consider
1299 : // re-schedule this MI below it.
1300 259348 : if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) {
1301 : ++NumReSchedDowns;
1302 : return true;
1303 : }
1304 :
1305 : // If we commuted, regB may have changed so we should re-sample it to avoid
1306 : // confusing the three address conversion below.
1307 257687 : if (Commuted) {
1308 2953 : regB = MI.getOperand(SrcIdx).getReg();
1309 2953 : regBKilled = isKilled(MI, regB, MRI, TII, LIS, true);
1310 : }
1311 :
1312 257687 : if (MI.isConvertibleTo3Addr()) {
1313 : // This instruction is potentially convertible to a true
1314 : // three-address instruction. Check if it is profitable.
1315 40561 : if (!regBKilled || isProfitableToConv3Addr(regA, regB)) {
1316 : // Try to convert it.
1317 11001 : if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) {
1318 : ++NumConvertedTo3Addr;
1319 : return true; // Done with this instruction.
1320 : }
1321 : }
1322 : }
1323 :
1324 : // Return if it is commuted but 3 addr conversion is failed.
1325 248335 : if (Commuted)
1326 : return false;
1327 :
1328 : // If there is one more use of regB later in the same MBB, consider
1329 : // re-schedule it before this MI if it's legal.
1330 245505 : if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) {
1331 : ++NumReSchedUps;
1332 : return true;
1333 : }
1334 :
1335 : // If this is an instruction with a load folded into it, try unfolding
1336 : // the load, e.g. avoid this:
1337 : // movq %rdx, %rcx
1338 : // addq (%rax), %rcx
1339 : // in favor of this:
1340 : // movq (%rax), %rcx
1341 : // addq %rdx, %rcx
1342 : // because it's preferable to schedule a load than a register copy.
1343 245154 : if (MI.mayLoad() && !regBKilled) {
1344 : // Determine if a load can be unfolded.
1345 : unsigned LoadRegIndex;
1346 : unsigned NewOpc =
1347 4427 : TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
1348 : /*UnfoldLoad=*/true,
1349 : /*UnfoldStore=*/false,
1350 4427 : &LoadRegIndex);
1351 4427 : if (NewOpc != 0) {
1352 3818 : const MCInstrDesc &UnfoldMCID = TII->get(NewOpc);
1353 3818 : if (UnfoldMCID.getNumDefs() == 1) {
1354 : // Unfold the load.
1355 : LLVM_DEBUG(dbgs() << "2addr: UNFOLDING: " << MI);
1356 : const TargetRegisterClass *RC =
1357 3818 : TRI->getAllocatableClass(
1358 3818 : TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF));
1359 7636 : unsigned Reg = MRI->createVirtualRegister(RC);
1360 : SmallVector<MachineInstr *, 2> NewMIs;
1361 3818 : if (!TII->unfoldMemoryOperand(*MF, MI, Reg,
1362 : /*UnfoldLoad=*/true,
1363 3818 : /*UnfoldStore=*/false, NewMIs)) {
1364 : LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1365 : return false;
1366 : }
1367 : assert(NewMIs.size() == 2 &&
1368 : "Unfolded a load into multiple instructions!");
1369 : // The load was previously folded, so this is the only use.
1370 3818 : NewMIs[1]->addRegisterKilled(Reg, TRI);
1371 :
1372 : // Tentatively insert the instructions into the block so that they
1373 : // look "normal" to the transformation logic.
1374 7636 : MBB->insert(mi, NewMIs[0]);
1375 7636 : MBB->insert(mi, NewMIs[1]);
1376 :
1377 : LLVM_DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0]
1378 : << "2addr: NEW INST: " << *NewMIs[1]);
1379 :
1380 : // Transform the instruction, now that it no longer has a load.
1381 3818 : unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA);
1382 3818 : unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB);
1383 3818 : MachineBasicBlock::iterator NewMI = NewMIs[1];
1384 : bool TransformResult =
1385 3818 : tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true);
1386 : (void)TransformResult;
1387 : assert(!TransformResult &&
1388 : "tryInstructionTransform() should return false.");
1389 7636 : if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) {
1390 : // Success, or at least we made an improvement. Keep the unfolded
1391 : // instructions and discard the original.
1392 3547 : if (LV) {
1393 29070 : for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1394 25528 : MachineOperand &MO = MI.getOperand(i);
1395 25528 : if (MO.isReg() &&
1396 18199 : TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
1397 9013 : if (MO.isUse()) {
1398 5471 : if (MO.isKill()) {
1399 227 : if (NewMIs[0]->killsRegister(MO.getReg()))
1400 254 : LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[0]);
1401 : else {
1402 : assert(NewMIs[1]->killsRegister(MO.getReg()) &&
1403 : "Kill missing after load unfold!");
1404 200 : LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[1]);
1405 : }
1406 : }
1407 3542 : } else if (LV->removeVirtualRegisterDead(MO.getReg(), MI)) {
1408 0 : if (NewMIs[1]->registerDefIsDead(MO.getReg()))
1409 0 : LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[1]);
1410 : else {
1411 : assert(NewMIs[0]->registerDefIsDead(MO.getReg()) &&
1412 : "Dead flag missing after load unfold!");
1413 0 : LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[0]);
1414 : }
1415 : }
1416 : }
1417 : }
1418 7084 : LV->addVirtualRegisterKilled(Reg, *NewMIs[1]);
1419 : }
1420 :
1421 : SmallVector<unsigned, 4> OrigRegs;
1422 3547 : if (LIS) {
1423 0 : for (const MachineOperand &MO : MI.operands()) {
1424 0 : if (MO.isReg())
1425 0 : OrigRegs.push_back(MO.getReg());
1426 : }
1427 : }
1428 :
1429 3547 : MI.eraseFromParent();
1430 :
1431 : // Update LiveIntervals.
1432 3547 : if (LIS) {
1433 0 : MachineBasicBlock::iterator Begin(NewMIs[0]);
1434 0 : MachineBasicBlock::iterator End(NewMIs[1]);
1435 0 : LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs);
1436 : }
1437 :
1438 3547 : mi = NewMIs[1];
1439 : } else {
1440 : // Transforming didn't eliminate the tie and didn't lead to an
1441 : // improvement. Clean up the unfolded instructions and keep the
1442 : // original.
1443 : LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1444 271 : NewMIs[0]->eraseFromParent();
1445 271 : NewMIs[1]->eraseFromParent();
1446 : }
1447 : }
1448 : }
1449 : }
1450 :
1451 : return false;
1452 : }
1453 :
1454 : // Collect tied operands of MI that need to be handled.
1455 : // Rewrite trivial cases immediately.
1456 : // Return true if any tied operands where found, including the trivial ones.
1457 41125861 : bool TwoAddressInstructionPass::
1458 : collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) {
1459 41125861 : const MCInstrDesc &MCID = MI->getDesc();
1460 : bool AnyOps = false;
1461 41125861 : unsigned NumOps = MI->getNumOperands();
1462 :
1463 229666214 : for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
1464 188540354 : unsigned DstIdx = 0;
1465 188540354 : if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx))
1466 187165316 : continue;
1467 : AnyOps = true;
1468 1402292 : MachineOperand &SrcMO = MI->getOperand(SrcIdx);
1469 1402292 : MachineOperand &DstMO = MI->getOperand(DstIdx);
1470 1402292 : unsigned SrcReg = SrcMO.getReg();
1471 1402292 : unsigned DstReg = DstMO.getReg();
1472 : // Tied constraint already satisfied?
1473 1402292 : if (SrcReg == DstReg)
1474 : continue;
1475 :
1476 : assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
1477 :
1478 : // Deal with undef uses immediately - simply rewrite the src operand.
1479 1402067 : if (SrcMO.isUndef() && !DstMO.getSubReg()) {
1480 : // Constrain the DstReg register class if required.
1481 27030 : if (TargetRegisterInfo::isVirtualRegister(DstReg))
1482 27030 : if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx,
1483 27030 : TRI, *MF))
1484 1465 : MRI->constrainRegClass(DstReg, RC);
1485 27030 : SrcMO.setReg(DstReg);
1486 : SrcMO.setSubReg(0);
1487 : LLVM_DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
1488 27030 : continue;
1489 : }
1490 1375037 : TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx));
1491 : }
1492 41125860 : return AnyOps;
1493 : }
1494 :
1495 : // Process a list of tied MI operands that all use the same source register.
1496 : // The tied pairs are of the form (SrcIdx, DstIdx).
1497 : void
1498 1363578 : TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
1499 : TiedPairList &TiedPairs,
1500 : unsigned &Dist) {
1501 : bool IsEarlyClobber = false;
1502 2727251 : for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1503 2727346 : const MachineOperand &DstMO = MI->getOperand(TiedPairs[tpi].second);
1504 1363673 : IsEarlyClobber |= DstMO.isEarlyClobber();
1505 : }
1506 :
1507 : bool RemovedKillFlag = false;
1508 : bool AllUsesCopied = true;
1509 : unsigned LastCopiedReg = 0;
1510 : SlotIndex LastCopyIdx;
1511 : unsigned RegB = 0;
1512 : unsigned SubRegB = 0;
1513 2727251 : for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1514 1363673 : unsigned SrcIdx = TiedPairs[tpi].first;
1515 1363673 : unsigned DstIdx = TiedPairs[tpi].second;
1516 :
1517 1363673 : const MachineOperand &DstMO = MI->getOperand(DstIdx);
1518 1363673 : unsigned RegA = DstMO.getReg();
1519 :
1520 : // Grab RegB from the instruction because it may have changed if the
1521 : // instruction was commuted.
1522 1363673 : RegB = MI->getOperand(SrcIdx).getReg();
1523 : SubRegB = MI->getOperand(SrcIdx).getSubReg();
1524 :
1525 1363673 : if (RegA == RegB) {
1526 : // The register is tied to multiple destinations (or else we would
1527 : // not have continued this far), but this use of the register
1528 : // already matches the tied destination. Leave it.
1529 : AllUsesCopied = false;
1530 0 : continue;
1531 : }
1532 : LastCopiedReg = RegA;
1533 :
1534 : assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
1535 : "cannot make instruction into two-address form");
1536 :
1537 : #ifndef NDEBUG
1538 : // First, verify that we don't have a use of "a" in the instruction
1539 : // (a = b + a for example) because our transformation will not
1540 : // work. This should never occur because we are in SSA form.
1541 : for (unsigned i = 0; i != MI->getNumOperands(); ++i)
1542 : assert(i == DstIdx ||
1543 : !MI->getOperand(i).isReg() ||
1544 : MI->getOperand(i).getReg() != RegA);
1545 : #endif
1546 :
1547 : // Emit a copy.
1548 1363673 : MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
1549 1363673 : TII->get(TargetOpcode::COPY), RegA);
1550 : // If this operand is folding a truncation, the truncation now moves to the
1551 : // copy so that the register classes remain valid for the operands.
1552 1363673 : MIB.addReg(RegB, 0, SubRegB);
1553 1363673 : const TargetRegisterClass *RC = MRI->getRegClass(RegB);
1554 1363673 : if (SubRegB) {
1555 6 : if (TargetRegisterInfo::isVirtualRegister(RegA)) {
1556 : assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA),
1557 : SubRegB) &&
1558 : "tied subregister must be a truncation");
1559 : // The superreg class will not be used to constrain the subreg class.
1560 : RC = nullptr;
1561 : }
1562 : else {
1563 : assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB))
1564 : && "tied subregister must be a truncation");
1565 : }
1566 : }
1567 :
1568 : // Update DistanceMap.
1569 1363673 : MachineBasicBlock::iterator PrevMI = MI;
1570 : --PrevMI;
1571 2727346 : DistanceMap.insert(std::make_pair(&*PrevMI, Dist));
1572 1363673 : DistanceMap[MI] = ++Dist;
1573 :
1574 1363673 : if (LIS) {
1575 0 : LastCopyIdx = LIS->InsertMachineInstrInMaps(*PrevMI).getRegSlot();
1576 :
1577 0 : if (TargetRegisterInfo::isVirtualRegister(RegA)) {
1578 0 : LiveInterval &LI = LIS->getInterval(RegA);
1579 0 : VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1580 : SlotIndex endIdx =
1581 0 : LIS->getInstructionIndex(*MI).getRegSlot(IsEarlyClobber);
1582 0 : LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI));
1583 : }
1584 : }
1585 :
1586 : LLVM_DEBUG(dbgs() << "\t\tprepend:\t" << *MIB);
1587 :
1588 1363673 : MachineOperand &MO = MI->getOperand(SrcIdx);
1589 : assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() &&
1590 : "inconsistent operand info for 2-reg pass");
1591 1363673 : if (MO.isKill()) {
1592 : MO.setIsKill(false);
1593 : RemovedKillFlag = true;
1594 : }
1595 :
1596 : // Make sure regA is a legal regclass for the SrcIdx operand.
1597 2727346 : if (TargetRegisterInfo::isVirtualRegister(RegA) &&
1598 : TargetRegisterInfo::isVirtualRegister(RegB))
1599 1363555 : MRI->constrainRegClass(RegA, RC);
1600 1363673 : MO.setReg(RegA);
1601 : // The getMatchingSuper asserts guarantee that the register class projected
1602 : // by SubRegB is compatible with RegA with no subregister. So regardless of
1603 : // whether the dest oper writes a subreg, the source oper should not.
1604 : MO.setSubReg(0);
1605 :
1606 : // Propagate SrcRegMap.
1607 1363673 : SrcRegMap[RegA] = RegB;
1608 : }
1609 :
1610 1363578 : if (AllUsesCopied) {
1611 : bool ReplacedAllUntiedUses = true;
1612 1363578 : if (!IsEarlyClobber) {
1613 : // Replace other (un-tied) uses of regB with LastCopiedReg.
1614 6959899 : for (MachineOperand &MO : MI->operands()) {
1615 5598976 : if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
1616 9702 : if (MO.getSubReg() == SubRegB) {
1617 9700 : if (MO.isKill()) {
1618 : MO.setIsKill(false);
1619 : RemovedKillFlag = true;
1620 : }
1621 9700 : MO.setReg(LastCopiedReg);
1622 : MO.setSubReg(0);
1623 : } else {
1624 : ReplacedAllUntiedUses = false;
1625 : }
1626 : }
1627 : }
1628 : }
1629 :
1630 : // Update live variables for regB.
1631 2199757 : if (RemovedKillFlag && ReplacedAllUntiedUses &&
1632 1363578 : LV && LV->getVarInfo(RegB).removeKill(*MI)) {
1633 244191 : MachineBasicBlock::iterator PrevMI = MI;
1634 : --PrevMI;
1635 488382 : LV->addVirtualRegisterKilled(RegB, *PrevMI);
1636 : }
1637 :
1638 : // Update LiveIntervals.
1639 1363578 : if (LIS) {
1640 0 : LiveInterval &LI = LIS->getInterval(RegB);
1641 0 : SlotIndex MIIdx = LIS->getInstructionIndex(*MI);
1642 0 : LiveInterval::const_iterator I = LI.find(MIIdx);
1643 : assert(I != LI.end() && "RegB must be live-in to use.");
1644 :
1645 : SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber);
1646 0 : if (I->end == UseIdx)
1647 0 : LI.removeSegment(LastCopyIdx, UseIdx);
1648 : }
1649 0 : } else if (RemovedKillFlag) {
1650 : // Some tied uses of regB matched their destination registers, so
1651 : // regB is still used in this instruction, but a kill flag was
1652 : // removed from a different tied use of regB, so now we need to add
1653 : // a kill flag to one of the remaining uses of regB.
1654 0 : for (MachineOperand &MO : MI->operands()) {
1655 0 : if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
1656 : MO.setIsKill(true);
1657 : break;
1658 : }
1659 : }
1660 : }
1661 1363578 : }
1662 :
1663 : /// Reduce two-address instructions to two operands.
1664 406008 : bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
1665 406008 : MF = &Func;
1666 406008 : const TargetMachine &TM = MF->getTarget();
1667 406008 : MRI = &MF->getRegInfo();
1668 406008 : TII = MF->getSubtarget().getInstrInfo();
1669 406008 : TRI = MF->getSubtarget().getRegisterInfo();
1670 406008 : InstrItins = MF->getSubtarget().getInstrItineraryData();
1671 406008 : LV = getAnalysisIfAvailable<LiveVariables>();
1672 406008 : LIS = getAnalysisIfAvailable<LiveIntervals>();
1673 406008 : if (auto *AAPass = getAnalysisIfAvailable<AAResultsWrapperPass>())
1674 198755 : AA = &AAPass->getAAResults();
1675 : else
1676 207253 : AA = nullptr;
1677 406008 : OptLevel = TM.getOptLevel();
1678 : // Disable optimizations if requested. We cannot skip the whole pass as some
1679 : // fixups are necessary for correctness.
1680 406008 : if (skipFunction(Func.getFunction()))
1681 192874 : OptLevel = CodeGenOpt::None;
1682 :
1683 : bool MadeChange = false;
1684 :
1685 : LLVM_DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1686 : LLVM_DEBUG(dbgs() << "********** Function: " << MF->getName() << '\n');
1687 :
1688 : // This pass takes the function out of SSA form.
1689 406008 : MRI->leaveSSA();
1690 :
1691 406008 : TiedOperandMap TiedOperands;
1692 406008 : for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
1693 3691585 : MBBI != MBBE; ++MBBI) {
1694 3285577 : MBB = &*MBBI;
1695 3285577 : unsigned Dist = 0;
1696 3285577 : DistanceMap.clear();
1697 3285577 : SrcRegMap.clear();
1698 3285576 : DstRegMap.clear();
1699 3285577 : Processed.clear();
1700 3285577 : SunkInstrs.clear();
1701 6571154 : for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
1702 44535309 : mi != me; ) {
1703 41249732 : MachineBasicBlock::iterator nmi = std::next(mi);
1704 : // Don't revisit an instruction previously converted by target. It may
1705 : // contain undef register operands (%noreg), which are not handled.
1706 41126216 : if (mi->isDebugInstr() || SunkInstrs.count(&*mi)) {
1707 123871 : mi = nmi;
1708 39860124 : continue;
1709 : }
1710 :
1711 : // Expand REG_SEQUENCE instructions. This will position mi at the first
1712 : // expanded instruction.
1713 41125861 : if (mi->isRegSequence())
1714 54997 : eliminateRegSequence(mi);
1715 :
1716 82251722 : DistanceMap.insert(std::make_pair(&*mi, ++Dist));
1717 :
1718 41125861 : processCopy(&*mi);
1719 :
1720 : // First scan through all the tied register uses in this instruction
1721 : // and record a list of pairs of tied operands for each register.
1722 41125861 : if (!collectTiedOperands(&*mi, TiedOperands)) {
1723 39724889 : mi = nmi;
1724 39724889 : continue;
1725 : }
1726 :
1727 : ++NumTwoAddressInstrs;
1728 : MadeChange = true;
1729 : LLVM_DEBUG(dbgs() << '\t' << *mi);
1730 :
1731 : // If the instruction has a single pair of tied operands, try some
1732 : // transformations that may either eliminate the tied operands or
1733 : // improve the opportunities for coalescing away the register copy.
1734 1400972 : if (TiedOperands.size() == 1) {
1735 : SmallVectorImpl<std::pair<unsigned, unsigned>> &TiedPairs
1736 1372881 : = TiedOperands.begin()->second;
1737 1372881 : if (TiedPairs.size() == 1) {
1738 1372868 : unsigned SrcIdx = TiedPairs[0].first;
1739 1372868 : unsigned DstIdx = TiedPairs[0].second;
1740 2745736 : unsigned SrcReg = mi->getOperand(SrcIdx).getReg();
1741 1372868 : unsigned DstReg = mi->getOperand(DstIdx).getReg();
1742 2745736 : if (SrcReg != DstReg &&
1743 1372868 : tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) {
1744 : // The tied operands have been eliminated or shifted further down
1745 : // the block to ease elimination. Continue processing with 'nmi'.
1746 11364 : TiedOperands.clear();
1747 11364 : mi = nmi;
1748 11364 : continue;
1749 : }
1750 : }
1751 : }
1752 :
1753 : // Now iterate over the information collected above.
1754 4142794 : for (auto &TO : TiedOperands) {
1755 2727156 : processTiedPairs(&*mi, TO.second, Dist);
1756 : LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1757 : }
1758 :
1759 : // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
1760 1389608 : if (mi->isInsertSubreg()) {
1761 : // From %reg = INSERT_SUBREG %reg, %subreg, subidx
1762 : // To %reg:subidx = COPY %subreg
1763 28838 : unsigned SubIdx = mi->getOperand(3).getImm();
1764 28838 : mi->RemoveOperand(3);
1765 : assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
1766 28838 : mi->getOperand(0).setSubReg(SubIdx);
1767 28838 : mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef());
1768 28838 : mi->RemoveOperand(1);
1769 28838 : mi->setDesc(TII->get(TargetOpcode::COPY));
1770 : LLVM_DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
1771 : }
1772 :
1773 : // Clear TiedOperands here instead of at the top of the loop
1774 : // since most instructions do not have tied operands.
1775 1389608 : TiedOperands.clear();
1776 1389608 : mi = nmi;
1777 : }
1778 : }
1779 :
1780 406008 : if (LIS)
1781 0 : MF->verify(this, "After two-address instruction pass");
1782 :
1783 406008 : return MadeChange;
1784 : }
1785 :
1786 : /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process.
1787 : ///
1788 : /// The instruction is turned into a sequence of sub-register copies:
1789 : ///
1790 : /// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
1791 : ///
1792 : /// Becomes:
1793 : ///
1794 : /// undef %dst:ssub0 = COPY %v1
1795 : /// %dst:ssub1 = COPY %v2
1796 54997 : void TwoAddressInstructionPass::
1797 : eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
1798 : MachineInstr &MI = *MBBI;
1799 54997 : unsigned DstReg = MI.getOperand(0).getReg();
1800 54997 : if (MI.getOperand(0).getSubReg() ||
1801 54997 : TargetRegisterInfo::isPhysicalRegister(DstReg) ||
1802 54997 : !(MI.getNumOperands() & 1)) {
1803 : LLVM_DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << MI);
1804 0 : llvm_unreachable(nullptr);
1805 : }
1806 :
1807 : SmallVector<unsigned, 4> OrigRegs;
1808 54997 : if (LIS) {
1809 0 : OrigRegs.push_back(MI.getOperand(0).getReg());
1810 0 : for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2)
1811 0 : OrigRegs.push_back(MI.getOperand(i).getReg());
1812 : }
1813 :
1814 : bool DefEmitted = false;
1815 213837 : for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) {
1816 158840 : MachineOperand &UseMO = MI.getOperand(i);
1817 158840 : unsigned SrcReg = UseMO.getReg();
1818 317680 : unsigned SubIdx = MI.getOperand(i+1).getImm();
1819 : // Nothing needs to be inserted for undef operands.
1820 158840 : if (UseMO.isUndef())
1821 : continue;
1822 :
1823 : // Defer any kill flag to the last operand using SrcReg. Otherwise, we
1824 : // might insert a COPY that uses SrcReg after is was killed.
1825 : bool isKill = UseMO.isKill();
1826 154260 : if (isKill)
1827 272677 : for (unsigned j = i + 2; j < e; j += 2)
1828 148230 : if (MI.getOperand(j).getReg() == SrcReg) {
1829 : MI.getOperand(j).setIsKill();
1830 : UseMO.setIsKill(false);
1831 : isKill = false;
1832 8719 : break;
1833 : }
1834 :
1835 : // Insert the sub-register copy.
1836 308520 : MachineInstr *CopyMI = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(),
1837 308520 : TII->get(TargetOpcode::COPY))
1838 154260 : .addReg(DstReg, RegState::Define, SubIdx)
1839 154260 : .add(UseMO);
1840 :
1841 : // The first def needs an undef flag because there is no live register
1842 : // before it.
1843 154260 : if (!DefEmitted) {
1844 54997 : CopyMI->getOperand(0).setIsUndef(true);
1845 : // Return an iterator pointing to the first inserted instr.
1846 54997 : MBBI = CopyMI;
1847 : }
1848 : DefEmitted = true;
1849 :
1850 : // Update LiveVariables' kill info.
1851 154260 : if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg))
1852 124380 : LV->replaceKillInstruction(SrcReg, MI, *CopyMI);
1853 :
1854 : LLVM_DEBUG(dbgs() << "Inserted: " << *CopyMI);
1855 : }
1856 :
1857 : MachineBasicBlock::iterator EndMBBI =
1858 54997 : std::next(MachineBasicBlock::iterator(MI));
1859 :
1860 54997 : if (!DefEmitted) {
1861 : LLVM_DEBUG(dbgs() << "Turned: " << MI << " into an IMPLICIT_DEF");
1862 0 : MI.setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1863 0 : for (int j = MI.getNumOperands() - 1, ee = 0; j > ee; --j)
1864 0 : MI.RemoveOperand(j);
1865 : } else {
1866 : LLVM_DEBUG(dbgs() << "Eliminated: " << MI);
1867 54997 : MI.eraseFromParent();
1868 : }
1869 :
1870 : // Udpate LiveIntervals.
1871 54997 : if (LIS)
1872 0 : LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs);
1873 54997 : }
|
