1 //===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the TwoAddress instruction pass which is used
11 // by most register allocators. Two-Address instructions are rewritten
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
25 // It is also worth noting that the duplicate operand of the two
26 // address instruction is removed.
28 //===----------------------------------------------------------------------===//
30 #define DEBUG_TYPE "twoaddrinstr"
31 #include "llvm/CodeGen/Passes.h"
32 #include "llvm/Function.h"
33 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
34 #include "llvm/CodeGen/LiveVariables.h"
35 #include "llvm/CodeGen/MachineFunctionPass.h"
36 #include "llvm/CodeGen/MachineInstr.h"
37 #include "llvm/CodeGen/MachineInstrBuilder.h"
38 #include "llvm/CodeGen/MachineRegisterInfo.h"
39 #include "llvm/Analysis/AliasAnalysis.h"
40 #include "llvm/MC/MCInstrItineraries.h"
41 #include "llvm/Target/TargetRegisterInfo.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetMachine.h"
44 #include "llvm/Target/TargetOptions.h"
45 #include "llvm/Support/Debug.h"
46 #include "llvm/Support/ErrorHandling.h"
47 #include "llvm/ADT/BitVector.h"
48 #include "llvm/ADT/DenseMap.h"
49 #include "llvm/ADT/SmallSet.h"
50 #include "llvm/ADT/Statistic.h"
51 #include "llvm/ADT/STLExtras.h"
54 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
55 STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
56 STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted");
57 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
58 STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk");
59 STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up");
60 STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down");
63 class TwoAddressInstructionPass : public MachineFunctionPass {
64 const TargetInstrInfo *TII;
65 const TargetRegisterInfo *TRI;
66 const InstrItineraryData *InstrItins;
67 MachineRegisterInfo *MRI;
72 CodeGenOpt::Level OptLevel;
74 // DistanceMap - Keep track the distance of a MI from the start of the
75 // current basic block.
76 DenseMap<MachineInstr*, unsigned> DistanceMap;
78 // SrcRegMap - A map from virtual registers to physical registers which
79 // are likely targets to be coalesced to due to copies from physical
80 // registers to virtual registers. e.g. v1024 = move r0.
81 DenseMap<unsigned, unsigned> SrcRegMap;
83 // DstRegMap - A map from virtual registers to physical registers which
84 // are likely targets to be coalesced to due to copies to physical
85 // registers from virtual registers. e.g. r1 = move v1024.
86 DenseMap<unsigned, unsigned> DstRegMap;
88 /// RegSequences - Keep track the list of REG_SEQUENCE instructions seen
89 /// during the initial walk of the machine function.
90 SmallVector<MachineInstr*, 16> RegSequences;
92 bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
94 MachineBasicBlock::iterator OldPos);
96 bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist,
99 bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
100 MachineInstr *MI, MachineBasicBlock *MBB,
103 bool CommuteInstruction(MachineBasicBlock::iterator &mi,
104 MachineFunction::iterator &mbbi,
105 unsigned RegB, unsigned RegC, unsigned Dist);
107 bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB);
109 bool ConvertInstTo3Addr(MachineBasicBlock::iterator &mi,
110 MachineBasicBlock::iterator &nmi,
111 MachineFunction::iterator &mbbi,
112 unsigned RegA, unsigned RegB, unsigned Dist);
114 bool isDefTooClose(unsigned Reg, unsigned Dist,
115 MachineInstr *MI, MachineBasicBlock *MBB);
117 bool RescheduleMIBelowKill(MachineBasicBlock *MBB,
118 MachineBasicBlock::iterator &mi,
119 MachineBasicBlock::iterator &nmi,
121 bool RescheduleKillAboveMI(MachineBasicBlock *MBB,
122 MachineBasicBlock::iterator &mi,
123 MachineBasicBlock::iterator &nmi,
126 bool TryInstructionTransform(MachineBasicBlock::iterator &mi,
127 MachineBasicBlock::iterator &nmi,
128 MachineFunction::iterator &mbbi,
129 unsigned SrcIdx, unsigned DstIdx,
131 SmallPtrSet<MachineInstr*, 8> &Processed);
133 void ScanUses(unsigned DstReg, MachineBasicBlock *MBB,
134 SmallPtrSet<MachineInstr*, 8> &Processed);
136 void ProcessCopy(MachineInstr *MI, MachineBasicBlock *MBB,
137 SmallPtrSet<MachineInstr*, 8> &Processed);
139 void CoalesceExtSubRegs(SmallVector<unsigned,4> &Srcs, unsigned DstReg);
141 /// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as part
142 /// of the de-ssa process. This replaces sources of REG_SEQUENCE as
143 /// sub-register references of the register defined by REG_SEQUENCE.
144 bool EliminateRegSequences();
147 static char ID; // Pass identification, replacement for typeid
148 TwoAddressInstructionPass() : MachineFunctionPass(ID) {
149 initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry());
152 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
153 AU.setPreservesCFG();
154 AU.addRequired<AliasAnalysis>();
155 AU.addPreserved<LiveVariables>();
156 AU.addPreserved<SlotIndexes>();
157 AU.addPreserved<LiveIntervals>();
158 AU.addPreservedID(MachineLoopInfoID);
159 AU.addPreservedID(MachineDominatorsID);
160 MachineFunctionPass::getAnalysisUsage(AU);
163 /// runOnMachineFunction - Pass entry point.
164 bool runOnMachineFunction(MachineFunction&);
168 char TwoAddressInstructionPass::ID = 0;
169 INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, "twoaddressinstruction",
170 "Two-Address instruction pass", false, false)
171 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
172 INITIALIZE_PASS_END(TwoAddressInstructionPass, "twoaddressinstruction",
173 "Two-Address instruction pass", false, false)
175 char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID;
177 /// Sink3AddrInstruction - A two-address instruction has been converted to a
178 /// three-address instruction to avoid clobbering a register. Try to sink it
179 /// past the instruction that would kill the above mentioned register to reduce
180 /// register pressure.
181 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
182 MachineInstr *MI, unsigned SavedReg,
183 MachineBasicBlock::iterator OldPos) {
184 // FIXME: Shouldn't we be trying to do this before we three-addressify the
185 // instruction? After this transformation is done, we no longer need
186 // the instruction to be in three-address form.
188 // Check if it's safe to move this instruction.
189 bool SeenStore = true; // Be conservative.
190 if (!MI->isSafeToMove(TII, AA, SeenStore))
194 SmallSet<unsigned, 4> UseRegs;
196 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
197 const MachineOperand &MO = MI->getOperand(i);
200 unsigned MOReg = MO.getReg();
203 if (MO.isUse() && MOReg != SavedReg)
204 UseRegs.insert(MO.getReg());
208 // Don't try to move it if it implicitly defines a register.
211 // For now, don't move any instructions that define multiple registers.
213 DefReg = MO.getReg();
216 // Find the instruction that kills SavedReg.
217 MachineInstr *KillMI = NULL;
218 for (MachineRegisterInfo::use_nodbg_iterator
219 UI = MRI->use_nodbg_begin(SavedReg),
220 UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
221 MachineOperand &UseMO = UI.getOperand();
224 KillMI = UseMO.getParent();
228 // If we find the instruction that kills SavedReg, and it is in an
229 // appropriate location, we can try to sink the current instruction
231 if (!KillMI || KillMI->getParent() != MBB || KillMI == MI ||
232 KillMI->isTerminator())
235 // If any of the definitions are used by another instruction between the
236 // position and the kill use, then it's not safe to sink it.
238 // FIXME: This can be sped up if there is an easy way to query whether an
239 // instruction is before or after another instruction. Then we can use
240 // MachineRegisterInfo def / use instead.
241 MachineOperand *KillMO = NULL;
242 MachineBasicBlock::iterator KillPos = KillMI;
245 unsigned NumVisited = 0;
246 for (MachineBasicBlock::iterator I = llvm::next(OldPos); I != KillPos; ++I) {
247 MachineInstr *OtherMI = I;
248 // DBG_VALUE cannot be counted against the limit.
249 if (OtherMI->isDebugValue())
251 if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost.
254 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
255 MachineOperand &MO = OtherMI->getOperand(i);
258 unsigned MOReg = MO.getReg();
265 if (OtherMI == KillMI && MOReg == SavedReg)
266 // Save the operand that kills the register. We want to unset the kill
267 // marker if we can sink MI past it.
269 else if (UseRegs.count(MOReg))
270 // One of the uses is killed before the destination.
276 // Update kill and LV information.
277 KillMO->setIsKill(false);
278 KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
279 KillMO->setIsKill(true);
282 LV->replaceKillInstruction(SavedReg, KillMI, MI);
284 // Move instruction to its destination.
286 MBB->insert(KillPos, MI);
295 /// NoUseAfterLastDef - Return true if there are no intervening uses between the
296 /// last instruction in the MBB that defines the specified register and the
297 /// two-address instruction which is being processed. It also returns the last
298 /// def location by reference
299 bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg,
300 MachineBasicBlock *MBB, unsigned Dist,
303 unsigned LastUse = Dist;
304 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
305 E = MRI->reg_end(); I != E; ++I) {
306 MachineOperand &MO = I.getOperand();
307 MachineInstr *MI = MO.getParent();
308 if (MI->getParent() != MBB || MI->isDebugValue())
310 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
311 if (DI == DistanceMap.end())
313 if (MO.isUse() && DI->second < LastUse)
314 LastUse = DI->second;
315 if (MO.isDef() && DI->second > LastDef)
316 LastDef = DI->second;
319 return !(LastUse > LastDef && LastUse < Dist);
322 /// isCopyToReg - Return true if the specified MI is a copy instruction or
323 /// a extract_subreg instruction. It also returns the source and destination
324 /// registers and whether they are physical registers by reference.
325 static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII,
326 unsigned &SrcReg, unsigned &DstReg,
327 bool &IsSrcPhys, bool &IsDstPhys) {
331 DstReg = MI.getOperand(0).getReg();
332 SrcReg = MI.getOperand(1).getReg();
333 } else if (MI.isInsertSubreg() || MI.isSubregToReg()) {
334 DstReg = MI.getOperand(0).getReg();
335 SrcReg = MI.getOperand(2).getReg();
339 IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
340 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
344 /// isKilled - Test if the given register value, which is used by the given
345 /// instruction, is killed by the given instruction. This looks through
346 /// coalescable copies to see if the original value is potentially not killed.
348 /// For example, in this code:
350 /// %reg1034 = copy %reg1024
351 /// %reg1035 = copy %reg1025<kill>
352 /// %reg1036 = add %reg1034<kill>, %reg1035<kill>
354 /// %reg1034 is not considered to be killed, since it is copied from a
355 /// register which is not killed. Treating it as not killed lets the
356 /// normal heuristics commute the (two-address) add, which lets
357 /// coalescing eliminate the extra copy.
359 static bool isKilled(MachineInstr &MI, unsigned Reg,
360 const MachineRegisterInfo *MRI,
361 const TargetInstrInfo *TII) {
362 MachineInstr *DefMI = &MI;
364 if (!DefMI->killsRegister(Reg))
366 if (TargetRegisterInfo::isPhysicalRegister(Reg))
368 MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg);
369 // If there are multiple defs, we can't do a simple analysis, so just
370 // go with what the kill flag says.
371 if (llvm::next(Begin) != MRI->def_end())
374 bool IsSrcPhys, IsDstPhys;
375 unsigned SrcReg, DstReg;
376 // If the def is something other than a copy, then it isn't going to
377 // be coalesced, so follow the kill flag.
378 if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
384 /// isTwoAddrUse - Return true if the specified MI uses the specified register
385 /// as a two-address use. If so, return the destination register by reference.
386 static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) {
387 const MCInstrDesc &MCID = MI.getDesc();
388 unsigned NumOps = MI.isInlineAsm()
389 ? MI.getNumOperands() : MCID.getNumOperands();
390 for (unsigned i = 0; i != NumOps; ++i) {
391 const MachineOperand &MO = MI.getOperand(i);
392 if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
395 if (MI.isRegTiedToDefOperand(i, &ti)) {
396 DstReg = MI.getOperand(ti).getReg();
403 /// findOnlyInterestingUse - Given a register, if has a single in-basic block
404 /// use, return the use instruction if it's a copy or a two-address use.
406 MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB,
407 MachineRegisterInfo *MRI,
408 const TargetInstrInfo *TII,
410 unsigned &DstReg, bool &IsDstPhys) {
411 if (!MRI->hasOneNonDBGUse(Reg))
412 // None or more than one use.
414 MachineInstr &UseMI = *MRI->use_nodbg_begin(Reg);
415 if (UseMI.getParent() != MBB)
419 if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
424 if (isTwoAddrUse(UseMI, Reg, DstReg)) {
425 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
431 /// getMappedReg - Return the physical register the specified virtual register
432 /// might be mapped to.
434 getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) {
435 while (TargetRegisterInfo::isVirtualRegister(Reg)) {
436 DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg);
437 if (SI == RegMap.end())
441 if (TargetRegisterInfo::isPhysicalRegister(Reg))
446 /// regsAreCompatible - Return true if the two registers are equal or aliased.
449 regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) {
454 return TRI->regsOverlap(RegA, RegB);
458 /// isProfitableToCommute - Return true if it's potentially profitable to commute
459 /// the two-address instruction that's being processed.
461 TwoAddressInstructionPass::isProfitableToCommute(unsigned regA, unsigned regB,
463 MachineInstr *MI, MachineBasicBlock *MBB,
465 if (OptLevel == CodeGenOpt::None)
468 // Determine if it's profitable to commute this two address instruction. In
469 // general, we want no uses between this instruction and the definition of
470 // the two-address register.
472 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
473 // %reg1029<def> = MOV8rr %reg1028
474 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
475 // insert => %reg1030<def> = MOV8rr %reg1028
476 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
477 // In this case, it might not be possible to coalesce the second MOV8rr
478 // instruction if the first one is coalesced. So it would be profitable to
480 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
481 // %reg1029<def> = MOV8rr %reg1028
482 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
483 // insert => %reg1030<def> = MOV8rr %reg1029
484 // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead>
486 if (!MI->killsRegister(regC))
489 // Ok, we have something like:
490 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
491 // let's see if it's worth commuting it.
493 // Look for situations like this:
494 // %reg1024<def> = MOV r1
495 // %reg1025<def> = MOV r0
496 // %reg1026<def> = ADD %reg1024, %reg1025
498 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
499 unsigned ToRegA = getMappedReg(regA, DstRegMap);
501 unsigned FromRegB = getMappedReg(regB, SrcRegMap);
502 unsigned FromRegC = getMappedReg(regC, SrcRegMap);
503 bool BComp = !FromRegB || regsAreCompatible(FromRegB, ToRegA, TRI);
504 bool CComp = !FromRegC || regsAreCompatible(FromRegC, ToRegA, TRI);
506 return !BComp && CComp;
509 // If there is a use of regC between its last def (could be livein) and this
510 // instruction, then bail.
511 unsigned LastDefC = 0;
512 if (!NoUseAfterLastDef(regC, MBB, Dist, LastDefC))
515 // If there is a use of regB between its last def (could be livein) and this
516 // instruction, then go ahead and make this transformation.
517 unsigned LastDefB = 0;
518 if (!NoUseAfterLastDef(regB, MBB, Dist, LastDefB))
521 // Since there are no intervening uses for both registers, then commute
522 // if the def of regC is closer. Its live interval is shorter.
523 return LastDefB && LastDefC && LastDefC > LastDefB;
526 /// CommuteInstruction - Commute a two-address instruction and update the basic
527 /// block, distance map, and live variables if needed. Return true if it is
530 TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi,
531 MachineFunction::iterator &mbbi,
532 unsigned RegB, unsigned RegC, unsigned Dist) {
533 MachineInstr *MI = mi;
534 DEBUG(dbgs() << "2addr: COMMUTING : " << *MI);
535 MachineInstr *NewMI = TII->commuteInstruction(MI);
538 DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
542 DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI);
543 // If the instruction changed to commute it, update livevar.
546 // Update live variables
547 LV->replaceKillInstruction(RegC, MI, NewMI);
549 Indexes->replaceMachineInstrInMaps(MI, NewMI);
551 mbbi->insert(mi, NewMI); // Insert the new inst
552 mbbi->erase(mi); // Nuke the old inst.
554 DistanceMap.insert(std::make_pair(NewMI, Dist));
557 // Update source register map.
558 unsigned FromRegC = getMappedReg(RegC, SrcRegMap);
560 unsigned RegA = MI->getOperand(0).getReg();
561 SrcRegMap[RegA] = FromRegC;
567 /// isProfitableToConv3Addr - Return true if it is profitable to convert the
568 /// given 2-address instruction to a 3-address one.
570 TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){
571 // Look for situations like this:
572 // %reg1024<def> = MOV r1
573 // %reg1025<def> = MOV r0
574 // %reg1026<def> = ADD %reg1024, %reg1025
576 // Turn ADD into a 3-address instruction to avoid a copy.
577 unsigned FromRegB = getMappedReg(RegB, SrcRegMap);
580 unsigned ToRegA = getMappedReg(RegA, DstRegMap);
581 return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI));
584 /// ConvertInstTo3Addr - Convert the specified two-address instruction into a
585 /// three address one. Return true if this transformation was successful.
587 TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi,
588 MachineBasicBlock::iterator &nmi,
589 MachineFunction::iterator &mbbi,
590 unsigned RegA, unsigned RegB,
592 MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV);
594 DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
595 DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI);
599 Indexes->replaceMachineInstrInMaps(mi, NewMI);
601 if (NewMI->findRegisterUseOperand(RegB, false, TRI))
602 // FIXME: Temporary workaround. If the new instruction doesn't
603 // uses RegB, convertToThreeAddress must have created more
604 // then one instruction.
605 Sunk = Sink3AddrInstruction(mbbi, NewMI, RegB, mi);
607 mbbi->erase(mi); // Nuke the old inst.
610 DistanceMap.insert(std::make_pair(NewMI, Dist));
612 nmi = llvm::next(mi);
615 // Update source and destination register maps.
616 SrcRegMap.erase(RegA);
617 DstRegMap.erase(RegB);
624 /// ScanUses - Scan forward recursively for only uses, update maps if the use
625 /// is a copy or a two-address instruction.
627 TwoAddressInstructionPass::ScanUses(unsigned DstReg, MachineBasicBlock *MBB,
628 SmallPtrSet<MachineInstr*, 8> &Processed) {
629 SmallVector<unsigned, 4> VirtRegPairs;
633 unsigned Reg = DstReg;
634 while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy,
635 NewReg, IsDstPhys)) {
636 if (IsCopy && !Processed.insert(UseMI))
639 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
640 if (DI != DistanceMap.end())
641 // Earlier in the same MBB.Reached via a back edge.
645 VirtRegPairs.push_back(NewReg);
648 bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second;
650 assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!");
651 VirtRegPairs.push_back(NewReg);
655 if (!VirtRegPairs.empty()) {
656 unsigned ToReg = VirtRegPairs.back();
657 VirtRegPairs.pop_back();
658 while (!VirtRegPairs.empty()) {
659 unsigned FromReg = VirtRegPairs.back();
660 VirtRegPairs.pop_back();
661 bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
663 assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!");
666 bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second;
668 assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!");
672 /// ProcessCopy - If the specified instruction is not yet processed, process it
673 /// if it's a copy. For a copy instruction, we find the physical registers the
674 /// source and destination registers might be mapped to. These are kept in
675 /// point-to maps used to determine future optimizations. e.g.
678 /// v1026 = add v1024, v1025
680 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially
681 /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
682 /// potentially joined with r1 on the output side. It's worthwhile to commute
683 /// 'add' to eliminate a copy.
684 void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI,
685 MachineBasicBlock *MBB,
686 SmallPtrSet<MachineInstr*, 8> &Processed) {
687 if (Processed.count(MI))
690 bool IsSrcPhys, IsDstPhys;
691 unsigned SrcReg, DstReg;
692 if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
695 if (IsDstPhys && !IsSrcPhys)
696 DstRegMap.insert(std::make_pair(SrcReg, DstReg));
697 else if (!IsDstPhys && IsSrcPhys) {
698 bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
700 assert(SrcRegMap[DstReg] == SrcReg &&
701 "Can't map to two src physical registers!");
703 ScanUses(DstReg, MBB, Processed);
706 Processed.insert(MI);
710 /// RescheduleMIBelowKill - If there is one more local instruction that reads
711 /// 'Reg' and it kills 'Reg, consider moving the instruction below the kill
712 /// instruction in order to eliminate the need for the copy.
714 TwoAddressInstructionPass::RescheduleMIBelowKill(MachineBasicBlock *MBB,
715 MachineBasicBlock::iterator &mi,
716 MachineBasicBlock::iterator &nmi,
718 // Bail immediately if we don't have LV available. We use it to find kills
723 MachineInstr *MI = &*mi;
724 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
725 if (DI == DistanceMap.end())
726 // Must be created from unfolded load. Don't waste time trying this.
729 MachineInstr *KillMI = LV->getVarInfo(Reg).findKill(MBB);
730 if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
731 // Don't mess with copies, they may be coalesced later.
734 if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() ||
735 KillMI->isBranch() || KillMI->isTerminator())
736 // Don't move pass calls, etc.
740 if (isTwoAddrUse(*KillMI, Reg, DstReg))
743 bool SeenStore = true;
744 if (!MI->isSafeToMove(TII, AA, SeenStore))
747 if (TII->getInstrLatency(InstrItins, MI) > 1)
748 // FIXME: Needs more sophisticated heuristics.
751 SmallSet<unsigned, 2> Uses;
752 SmallSet<unsigned, 2> Kills;
753 SmallSet<unsigned, 2> Defs;
754 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
755 const MachineOperand &MO = MI->getOperand(i);
758 unsigned MOReg = MO.getReg();
765 if (MO.isKill() && MOReg != Reg)
770 // Move the copies connected to MI down as well.
771 MachineBasicBlock::iterator From = MI;
772 MachineBasicBlock::iterator To = llvm::next(From);
773 while (To->isCopy() && Defs.count(To->getOperand(1).getReg())) {
774 Defs.insert(To->getOperand(0).getReg());
778 // Check if the reschedule will not break depedencies.
779 unsigned NumVisited = 0;
780 MachineBasicBlock::iterator KillPos = KillMI;
782 for (MachineBasicBlock::iterator I = To; I != KillPos; ++I) {
783 MachineInstr *OtherMI = I;
784 // DBG_VALUE cannot be counted against the limit.
785 if (OtherMI->isDebugValue())
787 if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
790 if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() ||
791 OtherMI->isBranch() || OtherMI->isTerminator())
792 // Don't move pass calls, etc.
794 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
795 const MachineOperand &MO = OtherMI->getOperand(i);
798 unsigned MOReg = MO.getReg();
802 if (Uses.count(MOReg))
803 // Physical register use would be clobbered.
805 if (!MO.isDead() && Defs.count(MOReg))
806 // May clobber a physical register def.
807 // FIXME: This may be too conservative. It's ok if the instruction
808 // is sunken completely below the use.
811 if (Defs.count(MOReg))
814 ((MO.isKill() && Uses.count(MOReg)) || Kills.count(MOReg)))
815 // Don't want to extend other live ranges and update kills.
817 if (MOReg == Reg && !MO.isKill())
818 // We can't schedule across a use of the register in question.
820 // Ensure that if this is register in question, its the kill we expect.
821 assert((MOReg != Reg || OtherMI == KillMI) &&
822 "Found multiple kills of a register in a basic block");
827 // Move debug info as well.
828 while (From != MBB->begin() && llvm::prior(From)->isDebugValue())
831 // Copies following MI may have been moved as well.
833 MBB->splice(KillPos, MBB, From, To);
834 DistanceMap.erase(DI);
836 // Update live variables
837 LV->removeVirtualRegisterKilled(Reg, KillMI);
838 LV->addVirtualRegisterKilled(Reg, MI);
842 DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI);
846 /// isDefTooClose - Return true if the re-scheduling will put the given
847 /// instruction too close to the defs of its register dependencies.
848 bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist,
850 MachineBasicBlock *MBB) {
851 for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(Reg),
852 DE = MRI->def_end(); DI != DE; ++DI) {
853 MachineInstr *DefMI = &*DI;
854 if (DefMI->getParent() != MBB || DefMI->isCopy() || DefMI->isCopyLike())
857 return true; // MI is defining something KillMI uses
858 DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(DefMI);
859 if (DDI == DistanceMap.end())
860 return true; // Below MI
861 unsigned DefDist = DDI->second;
862 assert(Dist > DefDist && "Visited def already?");
863 if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist))
869 /// RescheduleKillAboveMI - If there is one more local instruction that reads
870 /// 'Reg' and it kills 'Reg, consider moving the kill instruction above the
871 /// current two-address instruction in order to eliminate the need for the
874 TwoAddressInstructionPass::RescheduleKillAboveMI(MachineBasicBlock *MBB,
875 MachineBasicBlock::iterator &mi,
876 MachineBasicBlock::iterator &nmi,
878 // Bail immediately if we don't have LV available. We use it to find kills
883 MachineInstr *MI = &*mi;
884 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
885 if (DI == DistanceMap.end())
886 // Must be created from unfolded load. Don't waste time trying this.
889 MachineInstr *KillMI = LV->getVarInfo(Reg).findKill(MBB);
890 if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
891 // Don't mess with copies, they may be coalesced later.
895 if (isTwoAddrUse(*KillMI, Reg, DstReg))
898 bool SeenStore = true;
899 if (!KillMI->isSafeToMove(TII, AA, SeenStore))
902 SmallSet<unsigned, 2> Uses;
903 SmallSet<unsigned, 2> Kills;
904 SmallSet<unsigned, 2> Defs;
905 SmallSet<unsigned, 2> LiveDefs;
906 for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) {
907 const MachineOperand &MO = KillMI->getOperand(i);
910 unsigned MOReg = MO.getReg();
914 if (isDefTooClose(MOReg, DI->second, MI, MBB))
916 if (MOReg == Reg && !MO.isKill())
919 if (MO.isKill() && MOReg != Reg)
921 } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
924 LiveDefs.insert(MOReg);
928 // Check if the reschedule will not break depedencies.
929 unsigned NumVisited = 0;
930 MachineBasicBlock::iterator KillPos = KillMI;
931 for (MachineBasicBlock::iterator I = mi; I != KillPos; ++I) {
932 MachineInstr *OtherMI = I;
933 // DBG_VALUE cannot be counted against the limit.
934 if (OtherMI->isDebugValue())
936 if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
939 if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() ||
940 OtherMI->isBranch() || OtherMI->isTerminator())
941 // Don't move pass calls, etc.
943 SmallVector<unsigned, 2> OtherDefs;
944 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
945 const MachineOperand &MO = OtherMI->getOperand(i);
948 unsigned MOReg = MO.getReg();
952 if (Defs.count(MOReg))
953 // Moving KillMI can clobber the physical register if the def has
956 if (Kills.count(MOReg))
957 // Don't want to extend other live ranges and update kills.
959 if (OtherMI != MI && MOReg == Reg && !MO.isKill())
960 // We can't schedule across a use of the register in question.
963 OtherDefs.push_back(MOReg);
967 for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) {
968 unsigned MOReg = OtherDefs[i];
969 if (Uses.count(MOReg))
971 if (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
972 LiveDefs.count(MOReg))
974 // Physical register def is seen.
979 // Move the old kill above MI, don't forget to move debug info as well.
980 MachineBasicBlock::iterator InsertPos = mi;
981 while (InsertPos != MBB->begin() && llvm::prior(InsertPos)->isDebugValue())
983 MachineBasicBlock::iterator From = KillMI;
984 MachineBasicBlock::iterator To = llvm::next(From);
985 while (llvm::prior(From)->isDebugValue())
987 MBB->splice(InsertPos, MBB, From, To);
989 nmi = llvm::prior(InsertPos); // Backtrack so we process the moved instr.
990 DistanceMap.erase(DI);
992 // Update live variables
993 LV->removeVirtualRegisterKilled(Reg, KillMI);
994 LV->addVirtualRegisterKilled(Reg, MI);
996 LIS->handleMove(KillMI);
998 DEBUG(dbgs() << "\trescheduled kill: " << *KillMI);
1002 /// TryInstructionTransform - For the case where an instruction has a single
1003 /// pair of tied register operands, attempt some transformations that may
1004 /// either eliminate the tied operands or improve the opportunities for
1005 /// coalescing away the register copy. Returns true if no copy needs to be
1006 /// inserted to untie mi's operands (either because they were untied, or
1007 /// because mi was rescheduled, and will be visited again later).
1008 bool TwoAddressInstructionPass::
1009 TryInstructionTransform(MachineBasicBlock::iterator &mi,
1010 MachineBasicBlock::iterator &nmi,
1011 MachineFunction::iterator &mbbi,
1012 unsigned SrcIdx, unsigned DstIdx, unsigned Dist,
1013 SmallPtrSet<MachineInstr*, 8> &Processed) {
1014 if (OptLevel == CodeGenOpt::None)
1017 MachineInstr &MI = *mi;
1018 unsigned regA = MI.getOperand(DstIdx).getReg();
1019 unsigned regB = MI.getOperand(SrcIdx).getReg();
1021 assert(TargetRegisterInfo::isVirtualRegister(regB) &&
1022 "cannot make instruction into two-address form");
1023 bool regBKilled = isKilled(MI, regB, MRI, TII);
1025 if (TargetRegisterInfo::isVirtualRegister(regA))
1026 ScanUses(regA, &*mbbi, Processed);
1028 // Check if it is profitable to commute the operands.
1029 unsigned SrcOp1, SrcOp2;
1031 unsigned regCIdx = ~0U;
1032 bool TryCommute = false;
1033 bool AggressiveCommute = false;
1034 if (MI.isCommutable() && MI.getNumOperands() >= 3 &&
1035 TII->findCommutedOpIndices(&MI, SrcOp1, SrcOp2)) {
1036 if (SrcIdx == SrcOp1)
1038 else if (SrcIdx == SrcOp2)
1041 if (regCIdx != ~0U) {
1042 regC = MI.getOperand(regCIdx).getReg();
1043 if (!regBKilled && isKilled(MI, regC, MRI, TII))
1044 // If C dies but B does not, swap the B and C operands.
1045 // This makes the live ranges of A and C joinable.
1047 else if (isProfitableToCommute(regA, regB, regC, &MI, mbbi, Dist)) {
1049 AggressiveCommute = true;
1054 // If it's profitable to commute, try to do so.
1055 if (TryCommute && CommuteInstruction(mi, mbbi, regB, regC, Dist)) {
1057 if (AggressiveCommute)
1062 // If there is one more use of regB later in the same MBB, consider
1063 // re-schedule this MI below it.
1064 if (RescheduleMIBelowKill(mbbi, mi, nmi, regB)) {
1069 if (MI.isConvertibleTo3Addr()) {
1070 // This instruction is potentially convertible to a true
1071 // three-address instruction. Check if it is profitable.
1072 if (!regBKilled || isProfitableToConv3Addr(regA, regB)) {
1073 // Try to convert it.
1074 if (ConvertInstTo3Addr(mi, nmi, mbbi, regA, regB, Dist)) {
1075 ++NumConvertedTo3Addr;
1076 return true; // Done with this instruction.
1081 // If there is one more use of regB later in the same MBB, consider
1082 // re-schedule it before this MI if it's legal.
1083 if (RescheduleKillAboveMI(mbbi, mi, nmi, regB)) {
1088 // If this is an instruction with a load folded into it, try unfolding
1089 // the load, e.g. avoid this:
1091 // addq (%rax), %rcx
1092 // in favor of this:
1093 // movq (%rax), %rcx
1095 // because it's preferable to schedule a load than a register copy.
1096 if (MI.mayLoad() && !regBKilled) {
1097 // Determine if a load can be unfolded.
1098 unsigned LoadRegIndex;
1100 TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
1101 /*UnfoldLoad=*/true,
1102 /*UnfoldStore=*/false,
1105 const MCInstrDesc &UnfoldMCID = TII->get(NewOpc);
1106 if (UnfoldMCID.getNumDefs() == 1) {
1107 MachineFunction &MF = *mbbi->getParent();
1110 DEBUG(dbgs() << "2addr: UNFOLDING: " << MI);
1111 const TargetRegisterClass *RC =
1112 TRI->getAllocatableClass(
1113 TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, MF));
1114 unsigned Reg = MRI->createVirtualRegister(RC);
1115 SmallVector<MachineInstr *, 2> NewMIs;
1116 if (!TII->unfoldMemoryOperand(MF, &MI, Reg,
1117 /*UnfoldLoad=*/true,/*UnfoldStore=*/false,
1119 DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1122 assert(NewMIs.size() == 2 &&
1123 "Unfolded a load into multiple instructions!");
1124 // The load was previously folded, so this is the only use.
1125 NewMIs[1]->addRegisterKilled(Reg, TRI);
1127 // Tentatively insert the instructions into the block so that they
1128 // look "normal" to the transformation logic.
1129 mbbi->insert(mi, NewMIs[0]);
1130 mbbi->insert(mi, NewMIs[1]);
1132 DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0]
1133 << "2addr: NEW INST: " << *NewMIs[1]);
1135 // Transform the instruction, now that it no longer has a load.
1136 unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA);
1137 unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB);
1138 MachineBasicBlock::iterator NewMI = NewMIs[1];
1139 bool TransformSuccess =
1140 TryInstructionTransform(NewMI, mi, mbbi,
1141 NewSrcIdx, NewDstIdx, Dist, Processed);
1142 if (TransformSuccess ||
1143 NewMIs[1]->getOperand(NewSrcIdx).isKill()) {
1144 // Success, or at least we made an improvement. Keep the unfolded
1145 // instructions and discard the original.
1147 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1148 MachineOperand &MO = MI.getOperand(i);
1150 TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
1153 if (NewMIs[0]->killsRegister(MO.getReg()))
1154 LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[0]);
1156 assert(NewMIs[1]->killsRegister(MO.getReg()) &&
1157 "Kill missing after load unfold!");
1158 LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[1]);
1161 } else if (LV->removeVirtualRegisterDead(MO.getReg(), &MI)) {
1162 if (NewMIs[1]->registerDefIsDead(MO.getReg()))
1163 LV->addVirtualRegisterDead(MO.getReg(), NewMIs[1]);
1165 assert(NewMIs[0]->registerDefIsDead(MO.getReg()) &&
1166 "Dead flag missing after load unfold!");
1167 LV->addVirtualRegisterDead(MO.getReg(), NewMIs[0]);
1172 LV->addVirtualRegisterKilled(Reg, NewMIs[1]);
1174 MI.eraseFromParent();
1176 if (TransformSuccess)
1179 // Transforming didn't eliminate the tie and didn't lead to an
1180 // improvement. Clean up the unfolded instructions and keep the
1182 DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1183 NewMIs[0]->eraseFromParent();
1184 NewMIs[1]->eraseFromParent();
1193 /// runOnMachineFunction - Reduce two-address instructions to two operands.
1195 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
1196 const TargetMachine &TM = MF.getTarget();
1197 MRI = &MF.getRegInfo();
1198 TII = TM.getInstrInfo();
1199 TRI = TM.getRegisterInfo();
1200 InstrItins = TM.getInstrItineraryData();
1201 Indexes = getAnalysisIfAvailable<SlotIndexes>();
1202 LV = getAnalysisIfAvailable<LiveVariables>();
1203 LIS = getAnalysisIfAvailable<LiveIntervals>();
1204 AA = &getAnalysis<AliasAnalysis>();
1205 OptLevel = TM.getOptLevel();
1207 bool MadeChange = false;
1209 DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1210 DEBUG(dbgs() << "********** Function: "
1211 << MF.getFunction()->getName() << '\n');
1213 // This pass takes the function out of SSA form.
1216 // ReMatRegs - Keep track of the registers whose def's are remat'ed.
1217 BitVector ReMatRegs(MRI->getNumVirtRegs());
1219 typedef DenseMap<unsigned, SmallVector<std::pair<unsigned, unsigned>, 4> >
1221 TiedOperandMap TiedOperands(4);
1223 SmallPtrSet<MachineInstr*, 8> Processed;
1224 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
1225 mbbi != mbbe; ++mbbi) {
1227 DistanceMap.clear();
1231 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
1233 MachineBasicBlock::iterator nmi = llvm::next(mi);
1234 if (mi->isDebugValue()) {
1239 // Remember REG_SEQUENCE instructions, we'll deal with them later.
1240 if (mi->isRegSequence())
1241 RegSequences.push_back(&*mi);
1243 const MCInstrDesc &MCID = mi->getDesc();
1244 bool FirstTied = true;
1246 DistanceMap.insert(std::make_pair(mi, ++Dist));
1248 ProcessCopy(&*mi, &*mbbi, Processed);
1250 // First scan through all the tied register uses in this instruction
1251 // and record a list of pairs of tied operands for each register.
1252 unsigned NumOps = mi->isInlineAsm()
1253 ? mi->getNumOperands() : MCID.getNumOperands();
1254 for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
1255 unsigned DstIdx = 0;
1256 if (!mi->isRegTiedToDefOperand(SrcIdx, &DstIdx))
1261 ++NumTwoAddressInstrs;
1262 DEBUG(dbgs() << '\t' << *mi);
1265 assert(mi->getOperand(SrcIdx).isReg() &&
1266 mi->getOperand(SrcIdx).getReg() &&
1267 mi->getOperand(SrcIdx).isUse() &&
1268 "two address instruction invalid");
1270 unsigned regB = mi->getOperand(SrcIdx).getReg();
1272 // Deal with <undef> uses immediately - simply rewrite the src operand.
1273 if (mi->getOperand(SrcIdx).isUndef()) {
1274 unsigned DstReg = mi->getOperand(DstIdx).getReg();
1275 // Constrain the DstReg register class if required.
1276 if (TargetRegisterInfo::isVirtualRegister(DstReg))
1277 if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx,
1279 MRI->constrainRegClass(DstReg, RC);
1280 mi->getOperand(SrcIdx).setReg(DstReg);
1281 DEBUG(dbgs() << "\t\trewrite undef:\t" << *mi);
1284 TiedOperands[regB].push_back(std::make_pair(SrcIdx, DstIdx));
1287 // If the instruction has a single pair of tied operands, try some
1288 // transformations that may either eliminate the tied operands or
1289 // improve the opportunities for coalescing away the register copy.
1290 if (TiedOperands.size() == 1) {
1291 SmallVector<std::pair<unsigned, unsigned>, 4> &TiedPairs
1292 = TiedOperands.begin()->second;
1293 if (TiedPairs.size() == 1) {
1294 unsigned SrcIdx = TiedPairs[0].first;
1295 unsigned DstIdx = TiedPairs[0].second;
1296 unsigned SrcReg = mi->getOperand(SrcIdx).getReg();
1297 unsigned DstReg = mi->getOperand(DstIdx).getReg();
1298 if (SrcReg != DstReg &&
1299 TryInstructionTransform(mi, nmi, mbbi, SrcIdx, DstIdx, Dist,
1301 // The tied operands have been eliminated or shifted further down the
1302 // block to ease elimination. Continue processing with 'nmi'.
1303 TiedOperands.clear();
1310 // Now iterate over the information collected above.
1311 for (TiedOperandMap::iterator OI = TiedOperands.begin(),
1312 OE = TiedOperands.end(); OI != OE; ++OI) {
1313 SmallVector<std::pair<unsigned, unsigned>, 4> &TiedPairs = OI->second;
1315 bool IsEarlyClobber = false;
1316 bool RemovedKillFlag = false;
1317 bool AllUsesCopied = true;
1318 unsigned LastCopiedReg = 0;
1319 unsigned regB = OI->first;
1320 for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1321 unsigned SrcIdx = TiedPairs[tpi].first;
1322 unsigned DstIdx = TiedPairs[tpi].second;
1324 const MachineOperand &DstMO = mi->getOperand(DstIdx);
1325 unsigned regA = DstMO.getReg();
1326 IsEarlyClobber |= DstMO.isEarlyClobber();
1328 // Grab regB from the instruction because it may have changed if the
1329 // instruction was commuted.
1330 regB = mi->getOperand(SrcIdx).getReg();
1333 // The register is tied to multiple destinations (or else we would
1334 // not have continued this far), but this use of the register
1335 // already matches the tied destination. Leave it.
1336 AllUsesCopied = false;
1339 LastCopiedReg = regA;
1341 assert(TargetRegisterInfo::isVirtualRegister(regB) &&
1342 "cannot make instruction into two-address form");
1345 // First, verify that we don't have a use of "a" in the instruction
1346 // (a = b + a for example) because our transformation will not
1347 // work. This should never occur because we are in SSA form.
1348 for (unsigned i = 0; i != mi->getNumOperands(); ++i)
1349 assert(i == DstIdx ||
1350 !mi->getOperand(i).isReg() ||
1351 mi->getOperand(i).getReg() != regA);
1355 BuildMI(*mbbi, mi, mi->getDebugLoc(), TII->get(TargetOpcode::COPY),
1358 // Update DistanceMap.
1359 MachineBasicBlock::iterator prevMI = prior(mi);
1360 DistanceMap.insert(std::make_pair(prevMI, Dist));
1361 DistanceMap[mi] = ++Dist;
1365 CopyIdx = Indexes->insertMachineInstrInMaps(prevMI).getRegSlot();
1367 DEBUG(dbgs() << "\t\tprepend:\t" << *prevMI);
1369 MachineOperand &MO = mi->getOperand(SrcIdx);
1370 assert(MO.isReg() && MO.getReg() == regB && MO.isUse() &&
1371 "inconsistent operand info for 2-reg pass");
1373 MO.setIsKill(false);
1374 RemovedKillFlag = true;
1377 // Make sure regA is a legal regclass for the SrcIdx operand.
1378 if (TargetRegisterInfo::isVirtualRegister(regA) &&
1379 TargetRegisterInfo::isVirtualRegister(regB))
1380 MRI->constrainRegClass(regA, MRI->getRegClass(regB));
1384 // Propagate SrcRegMap.
1385 SrcRegMap[regA] = regB;
1388 if (AllUsesCopied) {
1389 if (!IsEarlyClobber) {
1390 // Replace other (un-tied) uses of regB with LastCopiedReg.
1391 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
1392 MachineOperand &MO = mi->getOperand(i);
1393 if (MO.isReg() && MO.getReg() == regB && MO.isUse()) {
1395 MO.setIsKill(false);
1396 RemovedKillFlag = true;
1398 MO.setReg(LastCopiedReg);
1403 // Update live variables for regB.
1404 if (RemovedKillFlag && LV && LV->getVarInfo(regB).removeKill(mi))
1405 LV->addVirtualRegisterKilled(regB, prior(mi));
1407 } else if (RemovedKillFlag) {
1408 // Some tied uses of regB matched their destination registers, so
1409 // regB is still used in this instruction, but a kill flag was
1410 // removed from a different tied use of regB, so now we need to add
1411 // a kill flag to one of the remaining uses of regB.
1412 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
1413 MachineOperand &MO = mi->getOperand(i);
1414 if (MO.isReg() && MO.getReg() == regB && MO.isUse()) {
1421 // We didn't change anything if there was a single tied pair, and that
1422 // pair didn't require copies.
1423 if (AllUsesCopied || TiedPairs.size() > 1) {
1426 // Schedule the source copy / remat inserted to form two-address
1427 // instruction. FIXME: Does it matter the distance map may not be
1428 // accurate after it's scheduled?
1429 TII->scheduleTwoAddrSource(prior(mi), mi, *TRI);
1432 DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1435 // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
1436 if (mi->isInsertSubreg()) {
1437 // From %reg = INSERT_SUBREG %reg, %subreg, subidx
1438 // To %reg:subidx = COPY %subreg
1439 unsigned SubIdx = mi->getOperand(3).getImm();
1440 mi->RemoveOperand(3);
1441 assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
1442 mi->getOperand(0).setSubReg(SubIdx);
1443 mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef());
1444 mi->RemoveOperand(1);
1445 mi->setDesc(TII->get(TargetOpcode::COPY));
1446 DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
1449 // Clear TiedOperands here instead of at the top of the loop
1450 // since most instructions do not have tied operands.
1451 TiedOperands.clear();
1456 // Some remat'ed instructions are dead.
1457 for (int i = ReMatRegs.find_first(); i != -1; i = ReMatRegs.find_next(i)) {
1458 unsigned VReg = TargetRegisterInfo::index2VirtReg(i);
1459 if (MRI->use_nodbg_empty(VReg)) {
1460 MachineInstr *DefMI = MRI->getVRegDef(VReg);
1461 DefMI->eraseFromParent();
1465 // Eliminate REG_SEQUENCE instructions. Their whole purpose was to preseve
1466 // SSA form. It's now safe to de-SSA.
1467 MadeChange |= EliminateRegSequences();
1472 static void UpdateRegSequenceSrcs(unsigned SrcReg,
1473 unsigned DstReg, unsigned SubIdx,
1474 MachineRegisterInfo *MRI,
1475 const TargetRegisterInfo &TRI) {
1476 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
1477 RE = MRI->reg_end(); RI != RE; ) {
1478 MachineOperand &MO = RI.getOperand();
1480 MO.substVirtReg(DstReg, SubIdx, TRI);
1484 // Find the first def of Reg, assuming they are all in the same basic block.
1485 static MachineInstr *findFirstDef(unsigned Reg, MachineRegisterInfo *MRI) {
1486 SmallPtrSet<MachineInstr*, 8> Defs;
1487 MachineInstr *First = 0;
1488 for (MachineRegisterInfo::def_iterator RI = MRI->def_begin(Reg);
1489 MachineInstr *MI = RI.skipInstruction(); Defs.insert(MI))
1494 MachineBasicBlock *MBB = First->getParent();
1495 MachineBasicBlock::iterator A = First, B = First;
1499 if (A != MBB->begin()) {
1502 if (Defs.erase(A)) First = A;
1504 if (B != MBB->end()) {
1509 } while (Moving && !Defs.empty());
1510 assert(Defs.empty() && "Instructions outside basic block!");
1514 /// CoalesceExtSubRegs - If a number of sources of the REG_SEQUENCE are
1515 /// EXTRACT_SUBREG from the same register and to the same virtual register
1516 /// with different sub-register indices, attempt to combine the
1517 /// EXTRACT_SUBREGs and pre-coalesce them. e.g.
1518 /// %reg1026<def> = VLDMQ %reg1025<kill>, 260, pred:14, pred:%reg0
1519 /// %reg1029:6<def> = EXTRACT_SUBREG %reg1026, 6
1520 /// %reg1029:5<def> = EXTRACT_SUBREG %reg1026<kill>, 5
1521 /// Since D subregs 5, 6 can combine to a Q register, we can coalesce
1522 /// reg1026 to reg1029.
1524 TwoAddressInstructionPass::CoalesceExtSubRegs(SmallVector<unsigned,4> &Srcs,
1526 SmallSet<unsigned, 4> Seen;
1527 for (unsigned i = 0, e = Srcs.size(); i != e; ++i) {
1528 unsigned SrcReg = Srcs[i];
1529 if (!Seen.insert(SrcReg))
1532 // Check that the instructions are all in the same basic block.
1533 MachineInstr *SrcDefMI = MRI->getUniqueVRegDef(SrcReg);
1534 MachineInstr *DstDefMI = MRI->getUniqueVRegDef(DstReg);
1535 if (!SrcDefMI || !DstDefMI ||
1536 SrcDefMI->getParent() != DstDefMI->getParent())
1539 // If there are no other uses than copies which feed into
1540 // the reg_sequence, then we might be able to coalesce them.
1541 bool CanCoalesce = true;
1542 SmallVector<unsigned, 4> SrcSubIndices, DstSubIndices;
1543 for (MachineRegisterInfo::use_nodbg_iterator
1544 UI = MRI->use_nodbg_begin(SrcReg),
1545 UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
1546 MachineInstr *UseMI = &*UI;
1547 if (!UseMI->isCopy() || UseMI->getOperand(0).getReg() != DstReg) {
1548 CanCoalesce = false;
1551 SrcSubIndices.push_back(UseMI->getOperand(1).getSubReg());
1552 DstSubIndices.push_back(UseMI->getOperand(0).getSubReg());
1555 if (!CanCoalesce || SrcSubIndices.size() < 2)
1558 // Check that the source subregisters can be combined.
1559 std::sort(SrcSubIndices.begin(), SrcSubIndices.end());
1560 unsigned NewSrcSubIdx = 0;
1561 if (!TRI->canCombineSubRegIndices(MRI->getRegClass(SrcReg), SrcSubIndices,
1565 // Check that the destination subregisters can also be combined.
1566 std::sort(DstSubIndices.begin(), DstSubIndices.end());
1567 unsigned NewDstSubIdx = 0;
1568 if (!TRI->canCombineSubRegIndices(MRI->getRegClass(DstReg), DstSubIndices,
1572 // If neither source nor destination can be combined to the full register,
1573 // just give up. This could be improved if it ever matters.
1574 if (NewSrcSubIdx != 0 && NewDstSubIdx != 0)
1577 // Now that we know that all the uses are extract_subregs and that those
1578 // subregs can somehow be combined, scan all the extract_subregs again to
1579 // make sure the subregs are in the right order and can be composed.
1580 MachineInstr *SomeMI = 0;
1582 for (MachineRegisterInfo::use_nodbg_iterator
1583 UI = MRI->use_nodbg_begin(SrcReg),
1584 UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
1585 MachineInstr *UseMI = &*UI;
1586 assert(UseMI->isCopy());
1587 unsigned DstSubIdx = UseMI->getOperand(0).getSubReg();
1588 unsigned SrcSubIdx = UseMI->getOperand(1).getSubReg();
1589 assert(DstSubIdx != 0 && "missing subreg from RegSequence elimination");
1590 if ((NewDstSubIdx == 0 &&
1591 TRI->composeSubRegIndices(NewSrcSubIdx, DstSubIdx) != SrcSubIdx) ||
1592 (NewSrcSubIdx == 0 &&
1593 TRI->composeSubRegIndices(NewDstSubIdx, SrcSubIdx) != DstSubIdx)) {
1594 CanCoalesce = false;
1597 // Keep track of one of the uses. Preferably the first one which has a
1598 // <def,undef> flag.
1599 if (!SomeMI || UseMI->getOperand(0).isUndef())
1605 // Insert a copy to replace the original.
1606 MachineInstr *CopyMI = BuildMI(*SomeMI->getParent(), SomeMI,
1607 SomeMI->getDebugLoc(),
1608 TII->get(TargetOpcode::COPY))
1609 .addReg(DstReg, RegState::Define |
1610 getUndefRegState(SomeMI->getOperand(0).isUndef()),
1612 .addReg(SrcReg, 0, NewSrcSubIdx);
1614 // Remove all the old extract instructions.
1615 for (MachineRegisterInfo::use_nodbg_iterator
1616 UI = MRI->use_nodbg_begin(SrcReg),
1617 UE = MRI->use_nodbg_end(); UI != UE; ) {
1618 MachineInstr *UseMI = &*UI;
1620 if (UseMI == CopyMI)
1622 assert(UseMI->isCopy());
1623 // Move any kills to the new copy or extract instruction.
1624 if (UseMI->getOperand(1).isKill()) {
1625 CopyMI->getOperand(1).setIsKill();
1627 // Update live variables
1628 LV->replaceKillInstruction(SrcReg, UseMI, &*CopyMI);
1630 UseMI->eraseFromParent();
1635 static bool HasOtherRegSequenceUses(unsigned Reg, MachineInstr *RegSeq,
1636 MachineRegisterInfo *MRI) {
1637 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
1638 UE = MRI->use_end(); UI != UE; ++UI) {
1639 MachineInstr *UseMI = &*UI;
1640 if (UseMI != RegSeq && UseMI->isRegSequence())
1646 /// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as part
1647 /// of the de-ssa process. This replaces sources of REG_SEQUENCE as
1648 /// sub-register references of the register defined by REG_SEQUENCE. e.g.
1650 /// %reg1029<def>, %reg1030<def> = VLD1q16 %reg1024<kill>, ...
1651 /// %reg1031<def> = REG_SEQUENCE %reg1029<kill>, 5, %reg1030<kill>, 6
1653 /// %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
1654 bool TwoAddressInstructionPass::EliminateRegSequences() {
1655 if (RegSequences.empty())
1658 for (unsigned i = 0, e = RegSequences.size(); i != e; ++i) {
1659 MachineInstr *MI = RegSequences[i];
1660 unsigned DstReg = MI->getOperand(0).getReg();
1661 if (MI->getOperand(0).getSubReg() ||
1662 TargetRegisterInfo::isPhysicalRegister(DstReg) ||
1663 !(MI->getNumOperands() & 1)) {
1664 DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
1665 llvm_unreachable(0);
1668 bool IsImpDef = true;
1669 SmallVector<unsigned, 4> RealSrcs;
1670 SmallSet<unsigned, 4> Seen;
1671 for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) {
1672 // Nothing needs to be inserted for <undef> operands.
1673 if (MI->getOperand(i).isUndef()) {
1674 MI->getOperand(i).setReg(0);
1677 unsigned SrcReg = MI->getOperand(i).getReg();
1678 unsigned SrcSubIdx = MI->getOperand(i).getSubReg();
1679 unsigned SubIdx = MI->getOperand(i+1).getImm();
1680 // DefMI of NULL means the value does not have a vreg in this block
1681 // i.e., its a physical register or a subreg.
1682 // In either case we force a copy to be generated.
1683 MachineInstr *DefMI = NULL;
1684 if (!MI->getOperand(i).getSubReg() &&
1685 !TargetRegisterInfo::isPhysicalRegister(SrcReg)) {
1686 DefMI = MRI->getUniqueVRegDef(SrcReg);
1689 if (DefMI && DefMI->isImplicitDef()) {
1690 DefMI->eraseFromParent();
1695 // Remember COPY sources. These might be candidate for coalescing.
1696 if (DefMI && DefMI->isCopy() && DefMI->getOperand(1).getSubReg())
1697 RealSrcs.push_back(DefMI->getOperand(1).getReg());
1699 bool isKill = MI->getOperand(i).isKill();
1700 if (!DefMI || !Seen.insert(SrcReg) ||
1701 MI->getParent() != DefMI->getParent() ||
1702 !isKill || HasOtherRegSequenceUses(SrcReg, MI, MRI) ||
1703 !TRI->getMatchingSuperRegClass(MRI->getRegClass(DstReg),
1704 MRI->getRegClass(SrcReg), SubIdx)) {
1705 // REG_SEQUENCE cannot have duplicated operands, add a copy.
1706 // Also add an copy if the source is live-in the block. We don't want
1707 // to end up with a partial-redef of a livein, e.g.
1709 // reg1051:10<def> =
1715 // LiveIntervalAnalysis won't like it.
1717 // If the REG_SEQUENCE doesn't kill its source, keeping live variables
1718 // correctly up to date becomes very difficult. Insert a copy.
1720 // Defer any kill flag to the last operand using SrcReg. Otherwise, we
1721 // might insert a COPY that uses SrcReg after is was killed.
1723 for (unsigned j = i + 2; j < e; j += 2)
1724 if (MI->getOperand(j).getReg() == SrcReg) {
1725 MI->getOperand(j).setIsKill();
1730 MachineBasicBlock::iterator InsertLoc = MI;
1731 MachineInstr *CopyMI = BuildMI(*MI->getParent(), InsertLoc,
1732 MI->getDebugLoc(), TII->get(TargetOpcode::COPY))
1733 .addReg(DstReg, RegState::Define, SubIdx)
1734 .addReg(SrcReg, getKillRegState(isKill), SrcSubIdx);
1735 MI->getOperand(i).setReg(0);
1736 if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg))
1737 LV->replaceKillInstruction(SrcReg, MI, CopyMI);
1738 DEBUG(dbgs() << "Inserted: " << *CopyMI);
1742 for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) {
1743 unsigned SrcReg = MI->getOperand(i).getReg();
1744 if (!SrcReg) continue;
1745 unsigned SubIdx = MI->getOperand(i+1).getImm();
1746 UpdateRegSequenceSrcs(SrcReg, DstReg, SubIdx, MRI, *TRI);
1749 // Set <def,undef> flags on the first DstReg def in the basic block.
1750 // It marks the beginning of the live range. All the other defs are
1751 // read-modify-write.
1752 if (MachineInstr *Def = findFirstDef(DstReg, MRI)) {
1753 for (unsigned i = 0, e = Def->getNumOperands(); i != e; ++i) {
1754 MachineOperand &MO = Def->getOperand(i);
1755 if (MO.isReg() && MO.isDef() && MO.getReg() == DstReg)
1758 // Make sure there is a full non-subreg imp-def operand on the
1759 // instruction. This shouldn't be necessary, but it seems that at least
1760 // RAFast requires it.
1761 Def->addRegisterDefined(DstReg, TRI);
1762 DEBUG(dbgs() << "First def: " << *Def);
1766 DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF");
1767 MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1768 for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
1769 MI->RemoveOperand(j);
1771 DEBUG(dbgs() << "Eliminated: " << *MI);
1772 MI->eraseFromParent();
1775 // Try coalescing some EXTRACT_SUBREG instructions. This can create
1776 // INSERT_SUBREG instructions that must have <undef> flags added by
1777 // LiveIntervalAnalysis, so only run it when LiveVariables is available.
1779 CoalesceExtSubRegs(RealSrcs, DstReg);
1782 RegSequences.clear();