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/LiveVariables.h"
34 #include "llvm/CodeGen/MachineFunctionPass.h"
35 #include "llvm/CodeGen/MachineInstr.h"
36 #include "llvm/CodeGen/MachineRegisterInfo.h"
37 #include "llvm/Target/TargetRegisterInfo.h"
38 #include "llvm/Target/TargetInstrInfo.h"
39 #include "llvm/Target/TargetMachine.h"
40 #include "llvm/Target/TargetOptions.h"
41 #include "llvm/Support/Compiler.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/ADT/BitVector.h"
44 #include "llvm/ADT/DenseMap.h"
45 #include "llvm/ADT/SmallSet.h"
46 #include "llvm/ADT/Statistic.h"
47 #include "llvm/ADT/STLExtras.h"
50 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
51 STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
52 STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted");
53 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
54 STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk");
55 STATISTIC(NumReMats, "Number of instructions re-materialized");
56 STATISTIC(NumDeletes, "Number of dead instructions deleted");
59 class VISIBILITY_HIDDEN TwoAddressInstructionPass
60 : public MachineFunctionPass {
61 const TargetInstrInfo *TII;
62 const TargetRegisterInfo *TRI;
63 MachineRegisterInfo *MRI;
66 bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
68 MachineBasicBlock::iterator OldPos);
70 bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
71 MachineInstr *MI, MachineInstr *DefMI,
72 MachineBasicBlock *MBB, unsigned Loc,
73 DenseMap<MachineInstr*, unsigned> &DistanceMap);
75 bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist,
76 DenseMap<MachineInstr*, unsigned> &DistanceMap,
79 bool isProfitableToCommute(unsigned regB, unsigned regC,
80 MachineInstr *MI, MachineBasicBlock *MBB,
82 DenseMap<MachineInstr*, unsigned> &DistanceMap);
84 bool CommuteInstruction(MachineBasicBlock::iterator &mi,
85 MachineFunction::iterator &mbbi,
86 unsigned RegC, unsigned Dist,
87 DenseMap<MachineInstr*, unsigned> &DistanceMap);
89 static char ID; // Pass identification, replacement for typeid
90 TwoAddressInstructionPass() : MachineFunctionPass(&ID) {}
92 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
93 AU.addPreserved<LiveVariables>();
94 AU.addPreservedID(MachineLoopInfoID);
95 AU.addPreservedID(MachineDominatorsID);
97 AU.addPreservedID(StrongPHIEliminationID);
99 AU.addPreservedID(PHIEliminationID);
100 MachineFunctionPass::getAnalysisUsage(AU);
103 /// runOnMachineFunction - Pass entry point.
104 bool runOnMachineFunction(MachineFunction&);
108 char TwoAddressInstructionPass::ID = 0;
109 static RegisterPass<TwoAddressInstructionPass>
110 X("twoaddressinstruction", "Two-Address instruction pass");
112 const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
114 /// Sink3AddrInstruction - A two-address instruction has been converted to a
115 /// three-address instruction to avoid clobbering a register. Try to sink it
116 /// past the instruction that would kill the above mentioned register to reduce
117 /// register pressure.
118 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
119 MachineInstr *MI, unsigned SavedReg,
120 MachineBasicBlock::iterator OldPos) {
121 // Check if it's safe to move this instruction.
122 bool SeenStore = true; // Be conservative.
123 if (!MI->isSafeToMove(TII, SeenStore))
127 SmallSet<unsigned, 4> UseRegs;
129 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
130 const MachineOperand &MO = MI->getOperand(i);
133 unsigned MOReg = MO.getReg();
136 if (MO.isUse() && MOReg != SavedReg)
137 UseRegs.insert(MO.getReg());
141 // Don't try to move it if it implicitly defines a register.
144 // For now, don't move any instructions that define multiple registers.
146 DefReg = MO.getReg();
149 // Find the instruction that kills SavedReg.
150 MachineInstr *KillMI = NULL;
151 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
152 UE = MRI->use_end(); UI != UE; ++UI) {
153 MachineOperand &UseMO = UI.getOperand();
156 KillMI = UseMO.getParent();
160 if (!KillMI || KillMI->getParent() != MBB)
163 // If any of the definitions are used by another instruction between the
164 // position and the kill use, then it's not safe to sink it.
166 // FIXME: This can be sped up if there is an easy way to query whether an
167 // instruction is before or after another instruction. Then we can use
168 // MachineRegisterInfo def / use instead.
169 MachineOperand *KillMO = NULL;
170 MachineBasicBlock::iterator KillPos = KillMI;
173 unsigned NumVisited = 0;
174 for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
175 MachineInstr *OtherMI = I;
176 if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost.
179 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
180 MachineOperand &MO = OtherMI->getOperand(i);
183 unsigned MOReg = MO.getReg();
190 if (OtherMI == KillMI && MOReg == SavedReg)
191 // Save the operand that kills the register. We want to unset the kill
192 // marker if we can sink MI past it.
194 else if (UseRegs.count(MOReg))
195 // One of the uses is killed before the destination.
201 // Update kill and LV information.
202 KillMO->setIsKill(false);
203 KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
204 KillMO->setIsKill(true);
207 LV->replaceKillInstruction(SavedReg, KillMI, MI);
209 // Move instruction to its destination.
211 MBB->insert(KillPos, MI);
217 /// isTwoAddrUse - Return true if the specified MI is using the specified
218 /// register as a two-address operand.
219 static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
220 const TargetInstrDesc &TID = UseMI->getDesc();
221 for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
222 MachineOperand &MO = UseMI->getOperand(i);
223 if (MO.isReg() && MO.getReg() == Reg &&
224 (MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1))
225 // Earlier use is a two-address one.
231 /// isProfitableToReMat - Return true if the heuristics determines it is likely
232 /// to be profitable to re-materialize the definition of Reg rather than copy
235 TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
236 const TargetRegisterClass *RC,
237 MachineInstr *MI, MachineInstr *DefMI,
238 MachineBasicBlock *MBB, unsigned Loc,
239 DenseMap<MachineInstr*, unsigned> &DistanceMap){
240 bool OtherUse = false;
241 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
242 UE = MRI->use_end(); UI != UE; ++UI) {
243 MachineOperand &UseMO = UI.getOperand();
244 MachineInstr *UseMI = UseMO.getParent();
245 MachineBasicBlock *UseMBB = UseMI->getParent();
247 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
248 if (DI != DistanceMap.end() && DI->second == Loc)
249 continue; // Current use.
251 // There is at least one other use in the MBB that will clobber the
253 if (isTwoAddrUse(UseMI, Reg))
258 // If other uses in MBB are not two-address uses, then don't remat.
262 // No other uses in the same block, remat if it's defined in the same
263 // block so it does not unnecessarily extend the live range.
264 return MBB == DefMI->getParent();
267 /// NoUseAfterLastDef - Return true if there are no intervening uses between the
268 /// last instruction in the MBB that defines the specified register and the
269 /// two-address instruction which is being processed. It also returns the last
270 /// def location by reference
271 bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg,
272 MachineBasicBlock *MBB, unsigned Dist,
273 DenseMap<MachineInstr*, unsigned> &DistanceMap,
276 unsigned LastUse = Dist;
277 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
278 E = MRI->reg_end(); I != E; ++I) {
279 MachineOperand &MO = I.getOperand();
280 MachineInstr *MI = MO.getParent();
281 if (MI->getParent() != MBB)
283 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
284 if (DI == DistanceMap.end())
286 if (MO.isUse() && DI->second < LastUse)
287 LastUse = DI->second;
288 if (MO.isDef() && DI->second > LastDef)
289 LastDef = DI->second;
292 return !(LastUse > LastDef && LastUse < Dist);
295 /// isProfitableToReMat - Return true if it's potentially profitable to commute
296 /// the two-address instruction that's being processed.
298 TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC,
299 MachineInstr *MI, MachineBasicBlock *MBB,
300 unsigned Dist, DenseMap<MachineInstr*, unsigned> &DistanceMap) {
301 // Determine if it's profitable to commute this two address instruction. In
302 // general, we want no uses between this instruction and the definition of
303 // the two-address register.
305 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
306 // %reg1029<def> = MOV8rr %reg1028
307 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
308 // insert => %reg1030<def> = MOV8rr %reg1028
309 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
310 // In this case, it might not be possible to coalesce the second MOV8rr
311 // instruction if the first one is coalesced. So it would be profitable to
313 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
314 // %reg1029<def> = MOV8rr %reg1028
315 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
316 // insert => %reg1030<def> = MOV8rr %reg1029
317 // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead>
319 if (!MI->killsRegister(regC))
322 // Ok, we have something like:
323 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
324 // let's see if it's worth commuting it.
326 // If there is a use of regC between its last def (could be livein) and this
327 // instruction, then bail.
328 unsigned LastDefC = 0;
329 if (!NoUseAfterLastDef(regC, MBB, Dist, DistanceMap, LastDefC))
332 // If there is a use of regB between its last def (could be livein) and this
333 // instruction, then go ahead and make this transformation.
334 unsigned LastDefB = 0;
335 if (!NoUseAfterLastDef(regB, MBB, Dist, DistanceMap, LastDefB))
338 // Since there are no intervening uses for both registers, then commute
339 // if the def of regC is closer. Its live interval is shorter.
340 return LastDefB && LastDefC && LastDefC > LastDefB;
343 /// CommuteInstruction - Commute a two-address instruction and update the basic
344 /// block, distance map, and live variables if needed. Return true if it is
347 TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi,
348 MachineFunction::iterator &mbbi,
349 unsigned RegC, unsigned Dist,
350 DenseMap<MachineInstr*, unsigned> &DistanceMap) {
351 MachineInstr *MI = mi;
352 DOUT << "2addr: COMMUTING : " << *MI;
353 MachineInstr *NewMI = TII->commuteInstruction(MI);
356 DOUT << "2addr: COMMUTING FAILED!\n";
360 DOUT << "2addr: COMMUTED TO: " << *NewMI;
361 // If the instruction changed to commute it, update livevar.
364 // Update live variables
365 LV->replaceKillInstruction(RegC, MI, NewMI);
367 mbbi->insert(mi, NewMI); // Insert the new inst
368 mbbi->erase(mi); // Nuke the old inst.
370 DistanceMap.insert(std::make_pair(NewMI, Dist));
375 /// isSafeToDelete - If the specified instruction does not produce any side
376 /// effects and all of its defs are dead, then it's safe to delete.
377 static bool isSafeToDelete(MachineInstr *MI, const TargetInstrInfo *TII) {
378 const TargetInstrDesc &TID = MI->getDesc();
379 if (TID.mayStore() || TID.isCall())
381 if (TID.isTerminator() || TID.hasUnmodeledSideEffects())
384 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
385 MachineOperand &MO = MI->getOperand(i);
386 if (!MO.isReg() || !MO.isDef())
395 /// runOnMachineFunction - Reduce two-address instructions to two operands.
397 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
398 DOUT << "Machine Function\n";
399 const TargetMachine &TM = MF.getTarget();
400 MRI = &MF.getRegInfo();
401 TII = TM.getInstrInfo();
402 TRI = TM.getRegisterInfo();
403 LV = getAnalysisIfAvailable<LiveVariables>();
405 bool MadeChange = false;
407 DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
408 DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
410 // ReMatRegs - Keep track of the registers whose def's are remat'ed.
412 ReMatRegs.resize(MRI->getLastVirtReg()+1);
414 // DistanceMap - Keep track the distance of a MI from the start of the
415 // current basic block.
416 DenseMap<MachineInstr*, unsigned> DistanceMap;
418 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
419 mbbi != mbbe; ++mbbi) {
422 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
424 MachineBasicBlock::iterator nmi = next(mi);
425 const TargetInstrDesc &TID = mi->getDesc();
426 bool FirstTied = true;
428 DistanceMap.insert(std::make_pair(mi, ++Dist));
429 for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
430 int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
435 ++NumTwoAddressInstrs;
436 DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
441 assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() &&
442 mi->getOperand(si).isUse() && "two address instruction invalid");
444 // If the two operands are the same we just remove the use
445 // and mark the def as def&use, otherwise we have to insert a copy.
446 if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
452 unsigned regA = mi->getOperand(ti).getReg();
453 unsigned regB = mi->getOperand(si).getReg();
455 assert(TargetRegisterInfo::isVirtualRegister(regA) &&
456 TargetRegisterInfo::isVirtualRegister(regB) &&
457 "cannot update physical register live information");
460 // First, verify that we don't have a use of a in the instruction (a =
461 // b + a for example) because our transformation will not work. This
462 // should never occur because we are in SSA form.
463 for (unsigned i = 0; i != mi->getNumOperands(); ++i)
464 assert((int)i == ti ||
465 !mi->getOperand(i).isReg() ||
466 mi->getOperand(i).getReg() != regA);
469 // If this instruction is not the killing user of B, see if we can
470 // rearrange the code to make it so. Making it the killing user will
471 // allow us to coalesce A and B together, eliminating the copy we are
473 if (!mi->killsRegister(regB)) {
474 // If regA is dead and the instruction can be deleted, just delete
475 // it so it doesn't clobber regB.
476 if (mi->getOperand(ti).isDead() && isSafeToDelete(mi, TII)) {
477 mbbi->erase(mi); // Nuke the old inst.
480 break; // Done with this instruction.
483 // If this instruction is commutative, check to see if C dies. If
484 // so, swap the B and C operands. This makes the live ranges of A
486 // FIXME: This code also works for A := B op C instructions.
487 if (TID.isCommutable() && mi->getNumOperands() >= 3) {
488 assert(mi->getOperand(3-si).isReg() &&
489 "Not a proper commutative instruction!");
490 unsigned regC = mi->getOperand(3-si).getReg();
491 if (mi->killsRegister(regC)) {
492 if (CommuteInstruction(mi, mbbi, regC, Dist, DistanceMap)) {
495 goto InstructionRearranged;
500 // If this instruction is potentially convertible to a true
501 // three-address instruction,
502 if (TID.isConvertibleTo3Addr()) {
503 // FIXME: This assumes there are no more operands which are tied
504 // to another register.
506 for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i)
507 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
510 MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV);
512 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
513 DOUT << "2addr: TO 3-ADDR: " << *NewMI;
516 if (NewMI->findRegisterUseOperand(regB, false, TRI))
517 // FIXME: Temporary workaround. If the new instruction doesn't
518 // uses regB, convertToThreeAddress must have created more
519 // then one instruction.
520 Sunk = Sink3AddrInstruction(mbbi, NewMI, regB, mi);
522 mbbi->erase(mi); // Nuke the old inst.
525 DistanceMap.insert(std::make_pair(NewMI, Dist));
530 ++NumConvertedTo3Addr;
531 break; // Done with this instruction.
536 // If it's profitable to commute the instruction, do so.
537 if (TID.isCommutable() && mi->getNumOperands() >= 3) {
538 unsigned regC = mi->getOperand(3-si).getReg();
539 if (isProfitableToCommute(regB, regC, mi, mbbi, Dist, DistanceMap))
540 if (CommuteInstruction(mi, mbbi, regC, Dist, DistanceMap)) {
547 InstructionRearranged:
548 const TargetRegisterClass* rc = MRI->getRegClass(regA);
549 MachineInstr *DefMI = MRI->getVRegDef(regB);
550 // If it's safe and profitable, remat the definition instead of
553 DefMI->getDesc().isAsCheapAsAMove() &&
554 DefMI->isSafeToReMat(TII, regB) &&
555 isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist,DistanceMap)){
556 DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n");
557 TII->reMaterialize(*mbbi, mi, regA, DefMI);
561 TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
564 MachineBasicBlock::iterator prevMI = prior(mi);
565 // Update DistanceMap.
566 DistanceMap.insert(std::make_pair(prevMI, Dist));
567 DistanceMap[mi] = ++Dist;
569 // Update live variables for regB.
571 LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
573 // regB is used in this BB.
574 varInfoB.UsedBlocks[mbbi->getNumber()] = true;
576 if (LV->removeVirtualRegisterKilled(regB, mi))
577 LV->addVirtualRegisterKilled(regB, prevMI);
579 if (LV->removeVirtualRegisterDead(regB, mi))
580 LV->addVirtualRegisterDead(regB, prevMI);
583 DOUT << "\t\tprepend:\t"; DEBUG(prevMI->print(*cerr.stream(), &TM));
585 // Replace all occurences of regB with regA.
586 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
587 if (mi->getOperand(i).isReg() &&
588 mi->getOperand(i).getReg() == regB)
589 mi->getOperand(i).setReg(regA);
593 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
594 mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
597 DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
604 // Some remat'ed instructions are dead.
605 int VReg = ReMatRegs.find_first();
607 if (MRI->use_empty(VReg)) {
608 MachineInstr *DefMI = MRI->getVRegDef(VReg);
609 DefMI->eraseFromParent();
611 VReg = ReMatRegs.find_next(VReg);