blob: 8f0c473d48da3efc32467a7e69959a3cf463294f [file] [log] [blame]
Alkis Evlogimenos71499de2003-12-18 13:06:04 +00001//===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Alkis Evlogimenos71499de2003-12-18 13:06:04 +00007//
8//===----------------------------------------------------------------------===//
9//
Alkis Evlogimenos50c047d2004-01-04 23:09:24 +000010// This file implements the TwoAddress instruction pass which is used
11// by most register allocators. Two-Address instructions are rewritten
12// from:
13//
14// A = B op C
15//
16// to:
17//
18// A = B
Alkis Evlogimenos14be6402004-02-04 22:17:40 +000019// A op= C
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000020//
Alkis Evlogimenos14be6402004-02-04 22:17:40 +000021// Note that if a register allocator chooses to use this pass, that it
22// has to be capable of handling the non-SSA nature of these rewritten
23// virtual registers.
24//
25// It is also worth noting that the duplicate operand of the two
26// address instruction is removed.
Chris Lattnerbd91c1c2004-01-31 21:07:15 +000027//
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000028//===----------------------------------------------------------------------===//
29
30#define DEBUG_TYPE "twoaddrinstr"
Chris Lattnerbd91c1c2004-01-31 21:07:15 +000031#include "llvm/CodeGen/Passes.h"
Chris Lattner1e313632004-07-21 23:17:57 +000032#include "llvm/Function.h"
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000033#include "llvm/CodeGen/LiveVariables.h"
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000034#include "llvm/CodeGen/MachineFunctionPass.h"
35#include "llvm/CodeGen/MachineInstr.h"
Chris Lattner84bc5422007-12-31 04:13:23 +000036#include "llvm/CodeGen/MachineRegisterInfo.h"
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000037#include "llvm/Target/MRegisterInfo.h"
38#include "llvm/Target/TargetInstrInfo.h"
39#include "llvm/Target/TargetMachine.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000040#include "llvm/Support/Debug.h"
Chris Lattnera4f0b3a2006-08-27 12:54:02 +000041#include "llvm/Support/Compiler.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000042#include "llvm/ADT/Statistic.h"
43#include "llvm/ADT/STLExtras.h"
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000044using namespace llvm;
45
Chris Lattnercd3245a2006-12-19 22:41:21 +000046STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
47STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
48STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
Chris Lattnerbd91c1c2004-01-31 21:07:15 +000049
Chris Lattnercd3245a2006-12-19 22:41:21 +000050namespace {
Chris Lattnerf8c68f62006-06-28 22:17:39 +000051 struct VISIBILITY_HIDDEN TwoAddressInstructionPass
52 : public MachineFunctionPass {
Nick Lewyckyecd94c82007-05-06 13:37:16 +000053 static char ID; // Pass identification, replacement for typeid
Devang Patel794fd752007-05-01 21:15:47 +000054 TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {}
55
Misha Brukman75fa4e42004-07-22 15:26:23 +000056 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
Alkis Evlogimenos4c080862003-12-18 22:40:24 +000057
Misha Brukman75fa4e42004-07-22 15:26:23 +000058 /// runOnMachineFunction - pass entry point
59 bool runOnMachineFunction(MachineFunction&);
60 };
Alkis Evlogimenos4c080862003-12-18 22:40:24 +000061
Devang Patel19974732007-05-03 01:11:54 +000062 char TwoAddressInstructionPass::ID = 0;
Misha Brukmanedf128a2005-04-21 22:36:52 +000063 RegisterPass<TwoAddressInstructionPass>
Misha Brukman75fa4e42004-07-22 15:26:23 +000064 X("twoaddressinstruction", "Two-Address instruction pass");
Chris Lattnerd74ea2b2006-05-24 17:04:05 +000065}
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000066
Alkis Evlogimenos4c080862003-12-18 22:40:24 +000067const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo();
68
Misha Brukman75fa4e42004-07-22 15:26:23 +000069void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const {
Chris Lattnercfa0f2e2005-01-02 02:34:12 +000070 AU.addRequired<LiveVariables>();
Misha Brukman75fa4e42004-07-22 15:26:23 +000071 AU.addPreserved<LiveVariables>();
Bill Wendling67d65bb2008-01-04 20:54:55 +000072 AU.addPreservedID(MachineLoopInfoID);
73 AU.addPreservedID(MachineDominatorsID);
Misha Brukman75fa4e42004-07-22 15:26:23 +000074 AU.addPreservedID(PHIEliminationID);
75 MachineFunctionPass::getAnalysisUsage(AU);
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000076}
77
78/// runOnMachineFunction - Reduce two-address instructions to two
Chris Lattner163c1e72004-01-31 21:14:04 +000079/// operands.
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000080///
Chris Lattner163c1e72004-01-31 21:14:04 +000081bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
Bill Wendlinga09362e2006-11-28 22:48:48 +000082 DOUT << "Machine Function\n";
Misha Brukman75fa4e42004-07-22 15:26:23 +000083 const TargetMachine &TM = MF.getTarget();
Misha Brukman75fa4e42004-07-22 15:26:23 +000084 const TargetInstrInfo &TII = *TM.getInstrInfo();
Chris Lattnercfa0f2e2005-01-02 02:34:12 +000085 LiveVariables &LV = getAnalysis<LiveVariables>();
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000086
Misha Brukman75fa4e42004-07-22 15:26:23 +000087 bool MadeChange = false;
Alkis Evlogimenos71499de2003-12-18 13:06:04 +000088
Bill Wendlinga09362e2006-11-28 22:48:48 +000089 DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
90 DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
Alkis Evlogimenos3a9986f2004-02-18 00:35:06 +000091
Misha Brukman75fa4e42004-07-22 15:26:23 +000092 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
93 mbbi != mbbe; ++mbbi) {
94 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
95 mi != me; ++mi) {
Evan Chengba59a1e2006-12-01 21:52:58 +000096 const TargetInstrDescriptor *TID = mi->getInstrDescriptor();
Chris Lattner163c1e72004-01-31 21:14:04 +000097
Evan Cheng360c2dd2006-11-01 23:06:55 +000098 bool FirstTied = true;
Evan Chengba59a1e2006-12-01 21:52:58 +000099 for (unsigned si = 1, e = TID->numOperands; si < e; ++si) {
100 int ti = TID->getOperandConstraint(si, TOI::TIED_TO);
Evan Cheng360c2dd2006-11-01 23:06:55 +0000101 if (ti == -1)
102 continue;
Alkis Evlogimenos71499de2003-12-18 13:06:04 +0000103
Evan Cheng360c2dd2006-11-01 23:06:55 +0000104 if (FirstTied) {
105 ++NumTwoAddressInstrs;
Bill Wendlingbcd24982006-12-07 20:28:15 +0000106 DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
Evan Cheng360c2dd2006-11-01 23:06:55 +0000107 }
108 FirstTied = false;
Alkis Evlogimenos71499de2003-12-18 13:06:04 +0000109
Evan Cheng360c2dd2006-11-01 23:06:55 +0000110 assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() &&
111 mi->getOperand(si).isUse() && "two address instruction invalid");
Alkis Evlogimenos71499de2003-12-18 13:06:04 +0000112
Evan Cheng360c2dd2006-11-01 23:06:55 +0000113 // if the two operands are the same we just remove the use
114 // and mark the def as def&use, otherwise we have to insert a copy.
115 if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
116 // rewrite:
117 // a = b op c
118 // to:
119 // a = b
120 // a = a op c
121 unsigned regA = mi->getOperand(ti).getReg();
122 unsigned regB = mi->getOperand(si).getReg();
123
124 assert(MRegisterInfo::isVirtualRegister(regA) &&
125 MRegisterInfo::isVirtualRegister(regB) &&
126 "cannot update physical register live information");
Chris Lattner6b507672004-01-31 21:21:43 +0000127
Chris Lattner1e313632004-07-21 23:17:57 +0000128#ifndef NDEBUG
Evan Cheng360c2dd2006-11-01 23:06:55 +0000129 // First, verify that we don't have a use of a in the instruction (a =
130 // b + a for example) because our transformation will not work. This
131 // should never occur because we are in SSA form.
132 for (unsigned i = 0; i != mi->getNumOperands(); ++i)
133 assert((int)i == ti ||
134 !mi->getOperand(i).isRegister() ||
135 mi->getOperand(i).getReg() != regA);
Chris Lattner1e313632004-07-21 23:17:57 +0000136#endif
Alkis Evlogimenos14be6402004-02-04 22:17:40 +0000137
Evan Cheng360c2dd2006-11-01 23:06:55 +0000138 // If this instruction is not the killing user of B, see if we can
139 // rearrange the code to make it so. Making it the killing user will
140 // allow us to coalesce A and B together, eliminating the copy we are
141 // about to insert.
142 if (!LV.KillsRegister(mi, regB)) {
Evan Cheng360c2dd2006-11-01 23:06:55 +0000143 // If this instruction is commutative, check to see if C dies. If
144 // so, swap the B and C operands. This makes the live ranges of A
145 // and C joinable.
146 // FIXME: This code also works for A := B op C instructions.
Evan Cheng7bb175b2007-10-23 20:14:40 +0000147 if ((TID->Flags & M_COMMUTABLE) && mi->getNumOperands() >= 3) {
Evan Cheng360c2dd2006-11-01 23:06:55 +0000148 assert(mi->getOperand(3-si).isRegister() &&
149 "Not a proper commutative instruction!");
150 unsigned regC = mi->getOperand(3-si).getReg();
151 if (LV.KillsRegister(mi, regC)) {
Bill Wendlinga09362e2006-11-28 22:48:48 +0000152 DOUT << "2addr: COMMUTING : " << *mi;
Evan Cheng360c2dd2006-11-01 23:06:55 +0000153 MachineInstr *NewMI = TII.commuteInstruction(mi);
154 if (NewMI == 0) {
Bill Wendlinga09362e2006-11-28 22:48:48 +0000155 DOUT << "2addr: COMMUTING FAILED!\n";
Evan Cheng360c2dd2006-11-01 23:06:55 +0000156 } else {
Bill Wendlinga09362e2006-11-28 22:48:48 +0000157 DOUT << "2addr: COMMUTED TO: " << *NewMI;
Evan Cheng360c2dd2006-11-01 23:06:55 +0000158 // If the instruction changed to commute it, update livevar.
159 if (NewMI != mi) {
160 LV.instructionChanged(mi, NewMI); // Update live variables
161 mbbi->insert(mi, NewMI); // Insert the new inst
162 mbbi->erase(mi); // Nuke the old inst.
163 mi = NewMI;
164 }
165
166 ++NumCommuted;
167 regB = regC;
168 goto InstructionRearranged;
Misha Brukmanedf128a2005-04-21 22:36:52 +0000169 }
Chris Lattnerc71d6942005-01-19 07:08:42 +0000170 }
Chris Lattnercfa0f2e2005-01-02 02:34:12 +0000171 }
Evan Cheng360c2dd2006-11-01 23:06:55 +0000172
173 // If this instruction is potentially convertible to a true
174 // three-address instruction,
Evan Chengb9d5e7c2007-10-20 04:01:47 +0000175 if (TID->Flags & M_CONVERTIBLE_TO_3_ADDR) {
Evan Cheng360c2dd2006-11-01 23:06:55 +0000176 // FIXME: This assumes there are no more operands which are tied
177 // to another register.
178#ifndef NDEBUG
Evan Chengba59a1e2006-12-01 21:52:58 +0000179 for (unsigned i = si+1, e = TID->numOperands; i < e; ++i)
180 assert(TID->getOperandConstraint(i, TOI::TIED_TO) == -1);
Evan Cheng360c2dd2006-11-01 23:06:55 +0000181#endif
182
Evan Chengba59a1e2006-12-01 21:52:58 +0000183 if (MachineInstr *New = TII.convertToThreeAddress(mbbi, mi, LV)) {
Bill Wendlinga09362e2006-11-28 22:48:48 +0000184 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
185 DOUT << "2addr: TO 3-ADDR: " << *New;
Evan Cheng360c2dd2006-11-01 23:06:55 +0000186 mbbi->erase(mi); // Nuke the old inst.
187 mi = New;
188 ++NumConvertedTo3Addr;
Evan Cheng360c2dd2006-11-01 23:06:55 +0000189 // Done with this instruction.
190 break;
191 }
Evan Chengb9d5e7c2007-10-20 04:01:47 +0000192 }
Chris Lattnercfa0f2e2005-01-02 02:34:12 +0000193 }
Evan Cheng360c2dd2006-11-01 23:06:55 +0000194
195 InstructionRearranged:
Chris Lattner84bc5422007-12-31 04:13:23 +0000196 const TargetRegisterClass* rc = MF.getRegInfo().getRegClass(regA);
Owen Andersond10fd972007-12-31 06:32:00 +0000197 TII.copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
Evan Cheng360c2dd2006-11-01 23:06:55 +0000198
199 MachineBasicBlock::iterator prevMi = prior(mi);
Bill Wendlingbcd24982006-12-07 20:28:15 +0000200 DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
Evan Cheng360c2dd2006-11-01 23:06:55 +0000201
202 // Update live variables for regA
203 LiveVariables::VarInfo& varInfo = LV.getVarInfo(regA);
204 varInfo.DefInst = prevMi;
205
Owen Andersona0185402007-11-08 01:20:48 +0000206 // update live variables for regB
207 LiveVariables::VarInfo& varInfoB = LV.getVarInfo(regB);
208 // regB is used in this BB.
209 varInfoB.UsedBlocks[mbbi->getNumber()] = true;
Evan Cheng360c2dd2006-11-01 23:06:55 +0000210 if (LV.removeVirtualRegisterKilled(regB, mbbi, mi))
211 LV.addVirtualRegisterKilled(regB, prevMi);
212
213 if (LV.removeVirtualRegisterDead(regB, mbbi, mi))
214 LV.addVirtualRegisterDead(regB, prevMi);
215
216 // replace all occurences of regB with regA
217 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
218 if (mi->getOperand(i).isRegister() &&
219 mi->getOperand(i).getReg() == regB)
220 mi->getOperand(i).setReg(regA);
221 }
Chris Lattnercfa0f2e2005-01-02 02:34:12 +0000222 }
Alkis Evlogimenos14be6402004-02-04 22:17:40 +0000223
Evan Cheng360c2dd2006-11-01 23:06:55 +0000224 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
225 mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
226 MadeChange = true;
Alkis Evlogimenos14be6402004-02-04 22:17:40 +0000227
Bill Wendlingbcd24982006-12-07 20:28:15 +0000228 DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
Misha Brukman75fa4e42004-07-22 15:26:23 +0000229 }
Misha Brukman75fa4e42004-07-22 15:26:23 +0000230 }
231 }
232
233 return MadeChange;
Alkis Evlogimenos71499de2003-12-18 13:06:04 +0000234}