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/Support/Compiler.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/ADT/SmallPtrSet.h"
43 #include "llvm/ADT/Statistic.h"
44 #include "llvm/ADT/STLExtras.h"
47 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
48 STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
49 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
50 STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk");
53 class VISIBILITY_HIDDEN TwoAddressInstructionPass
54 : public MachineFunctionPass {
55 const TargetInstrInfo *TII;
56 const TargetRegisterInfo *TRI;
57 MachineRegisterInfo *MRI;
60 bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
62 MachineBasicBlock::iterator OldPos);
64 static char ID; // Pass identification, replacement for typeid
65 TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {}
67 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
68 AU.addRequired<LiveVariables>();
69 AU.addPreserved<LiveVariables>();
70 AU.addPreservedID(MachineLoopInfoID);
71 AU.addPreservedID(MachineDominatorsID);
72 AU.addPreservedID(PHIEliminationID);
73 MachineFunctionPass::getAnalysisUsage(AU);
76 /// runOnMachineFunction - Pass entry point.
77 bool runOnMachineFunction(MachineFunction&);
81 char TwoAddressInstructionPass::ID = 0;
82 static RegisterPass<TwoAddressInstructionPass>
83 X("twoaddressinstruction", "Two-Address instruction pass");
85 const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
87 /// Sink3AddrInstruction - A two-address instruction has been converted to a
88 /// three-address instruction to avoid clobbering a register. Try to sink it
89 /// past the instruction that would kill the above mentioned register to reduce
90 /// register pressure.
92 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
93 MachineInstr *MI, unsigned SavedReg,
94 MachineBasicBlock::iterator OldPos) {
95 // Check if it's safe to move this instruction.
96 bool SeenStore = true; // Be conservative.
97 if (!MI->isSafeToMove(TII, SeenStore))
101 SmallSet<unsigned, 4> UseRegs;
103 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
104 const MachineOperand &MO = MI->getOperand(i);
105 if (!MO.isRegister())
107 unsigned MOReg = MO.getReg();
110 if (MO.isUse() && MOReg != SavedReg)
111 UseRegs.insert(MO.getReg());
115 // Don't try to move it if it implicitly defines a register.
118 // For now, don't move any instructions that define multiple registers.
120 DefReg = MO.getReg();
123 // Find the instruction that kills SavedReg.
124 MachineInstr *KillMI = NULL;
126 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
127 UE = MRI->use_end(); UI != UE; ++UI) {
128 MachineOperand &UseMO = UI.getOperand();
131 KillMI = UseMO.getParent();
135 if (!KillMI || KillMI->getParent() != MBB)
138 // If any of the definitions are used by another instruction between the
139 // position and the kill use, then it's not safe to sink it.
141 // FIXME: This can be sped up if there is an easy way to query whether an
142 // instruction if before or after another instruction. Then we can use
143 // MachineRegisterInfo def / use instead.
144 MachineOperand *KillMO = NULL;
145 MachineBasicBlock::iterator KillPos = KillMI;
148 for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
149 MachineInstr *OtherMI = I;
151 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
152 MachineOperand &MO = OtherMI->getOperand(i);
153 if (!MO.isRegister())
155 unsigned MOReg = MO.getReg();
162 if (OtherMI == KillMI && MOReg == SavedReg)
163 // Save the operand that kills the register. We want unset the kill
164 // marker is we can sink MI past it.
166 else if (UseRegs.count(MOReg))
167 // One of the uses is killed before the destination.
173 // Update kill and LV information.
174 KillMO->setIsKill(false);
175 KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
176 KillMO->setIsKill(true);
177 LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg);
178 VarInfo.removeKill(KillMI);
179 VarInfo.Kills.push_back(MI);
181 // Move instruction to its destination.
183 MBB->insert(KillPos, MI);
189 /// runOnMachineFunction - Reduce two-address instructions to two operands.
191 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
192 DOUT << "Machine Function\n";
193 const TargetMachine &TM = MF.getTarget();
194 MRI = &MF.getRegInfo();
195 TII = TM.getInstrInfo();
196 TRI = TM.getRegisterInfo();
197 LV = &getAnalysis<LiveVariables>();
199 bool MadeChange = false;
201 DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
202 DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
204 SmallPtrSet<MachineInstr*, 8> ReMattedInstrs;
206 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
207 mbbi != mbbe; ++mbbi) {
208 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
210 MachineBasicBlock::iterator nmi = next(mi);
211 const TargetInstrDesc &TID = mi->getDesc();
212 bool FirstTied = true;
214 for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
215 int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
220 ++NumTwoAddressInstrs;
221 DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
226 assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() &&
227 mi->getOperand(si).isUse() && "two address instruction invalid");
229 // If the two operands are the same we just remove the use
230 // and mark the def as def&use, otherwise we have to insert a copy.
231 if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
237 unsigned regA = mi->getOperand(ti).getReg();
238 unsigned regB = mi->getOperand(si).getReg();
240 assert(TargetRegisterInfo::isVirtualRegister(regA) &&
241 TargetRegisterInfo::isVirtualRegister(regB) &&
242 "cannot update physical register live information");
245 // First, verify that we don't have a use of a in the instruction (a =
246 // b + a for example) because our transformation will not work. This
247 // should never occur because we are in SSA form.
248 for (unsigned i = 0; i != mi->getNumOperands(); ++i)
249 assert((int)i == ti ||
250 !mi->getOperand(i).isRegister() ||
251 mi->getOperand(i).getReg() != regA);
254 // If this instruction is not the killing user of B, see if we can
255 // rearrange the code to make it so. Making it the killing user will
256 // allow us to coalesce A and B together, eliminating the copy we are
258 if (!mi->killsRegister(regB)) {
259 // If this instruction is commutative, check to see if C dies. If
260 // so, swap the B and C operands. This makes the live ranges of A
262 // FIXME: This code also works for A := B op C instructions.
263 if (TID.isCommutable() && mi->getNumOperands() >= 3) {
264 assert(mi->getOperand(3-si).isRegister() &&
265 "Not a proper commutative instruction!");
266 unsigned regC = mi->getOperand(3-si).getReg();
268 if (mi->killsRegister(regC)) {
269 DOUT << "2addr: COMMUTING : " << *mi;
270 MachineInstr *NewMI = TII->commuteInstruction(mi);
273 DOUT << "2addr: COMMUTING FAILED!\n";
275 DOUT << "2addr: COMMUTED TO: " << *NewMI;
276 // If the instruction changed to commute it, update livevar.
278 LV->instructionChanged(mi, NewMI); // Update live variables
279 mbbi->insert(mi, NewMI); // Insert the new inst
280 mbbi->erase(mi); // Nuke the old inst.
286 goto InstructionRearranged;
291 // If this instruction is potentially convertible to a true
292 // three-address instruction,
293 if (TID.isConvertibleTo3Addr()) {
294 // FIXME: This assumes there are no more operands which are tied
295 // to another register.
297 for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i)
298 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
301 if (MachineInstr *New=TII->convertToThreeAddress(mbbi, mi, *LV)) {
302 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
303 DOUT << "2addr: TO 3-ADDR: " << *New;
306 if (New->findRegisterUseOperand(regB, false, TRI))
307 // FIXME: Temporary workaround. If the new instruction doesn't
308 // uses regB, convertToThreeAddress must have created more
309 // then one instruction.
310 Sunk = Sink3AddrInstruction(mbbi, New, regB, mi);
312 mbbi->erase(mi); // Nuke the old inst.
319 ++NumConvertedTo3Addr;
320 break; // Done with this instruction.
325 InstructionRearranged:
326 const TargetRegisterClass* rc = MF.getRegInfo().getRegClass(regA);
327 MachineInstr *Orig = MRI->getVRegDef(regB);
329 if (Orig && TII->isTriviallyReMaterializable(Orig)) {
330 TII->reMaterialize(*mbbi, mi, regA, Orig);
331 ReMattedInstrs.insert(Orig);
333 TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
336 MachineBasicBlock::iterator prevMi = prior(mi);
337 DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
339 // Update live variables for regB.
340 LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
342 // regB is used in this BB.
343 varInfoB.UsedBlocks[mbbi->getNumber()] = true;
345 if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
346 LV->addVirtualRegisterKilled(regB, prevMi);
348 if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
349 LV->addVirtualRegisterDead(regB, prevMi);
351 // Replace all occurences of regB with regA.
352 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
353 if (mi->getOperand(i).isRegister() &&
354 mi->getOperand(i).getReg() == regB)
355 mi->getOperand(i).setReg(regA);
359 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
360 mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
363 DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
370 SmallPtrSet<MachineInstr*, 8>::iterator I = ReMattedInstrs.begin();
371 SmallPtrSet<MachineInstr*, 8>::iterator E = ReMattedInstrs.end();
373 for (; I != E; ++I) {
374 MachineInstr *MI = *I;
375 bool InstrDead = true;
377 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
378 const MachineOperand &MO = MI->getOperand(i);
379 if (!MO.isRegister())
381 unsigned MOReg = MO.getReg();
388 if (MRI->use_begin(MOReg) != MRI->use_end()) {
395 if (InstrDead && MI->getNumOperands() > 0)
396 MI->eraseFromParent();