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