blob: a81edda858cf1aa3bc91d121b9adac93f124fe04 [file] [log] [blame]
Chris Lattner1d62cea2002-12-16 14:37:00 +00001//===-- RegAllocSimple.cpp - A simple generic register allocator ----------===//
John Criswellb576c942003-10-20 19:43:21 +00002//
3// The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
Misha Brukman07218672002-11-22 22:44:32 +00009//
Chris Lattner600dee42002-12-28 20:42:14 +000010// This file implements a simple register allocator. *Very* simple: It immediate
11// spills every value right after it is computed, and it reloads all used
12// operands from the spill area to temporary registers before each instruction.
13// It does not keep values in registers across instructions.
Misha Brukman07218672002-11-22 22:44:32 +000014//
15//===----------------------------------------------------------------------===//
16
Chris Lattner4cc662b2003-08-03 21:47:31 +000017#define DEBUG_TYPE "regalloc"
Chris Lattner80a04782003-01-13 00:26:08 +000018#include "llvm/CodeGen/Passes.h"
Chris Lattner600dee42002-12-28 20:42:14 +000019#include "llvm/CodeGen/MachineFunctionPass.h"
Chris Lattnerabe8dd52002-12-15 18:19:24 +000020#include "llvm/CodeGen/MachineInstr.h"
Chris Lattner5124aec2002-12-25 05:04:20 +000021#include "llvm/CodeGen/SSARegMap.h"
Chris Lattnereb24db92002-12-28 21:08:26 +000022#include "llvm/CodeGen/MachineFrameInfo.h"
Chris Lattner3501fea2003-01-14 22:00:31 +000023#include "llvm/Target/TargetInstrInfo.h"
Misha Brukman07218672002-11-22 22:44:32 +000024#include "llvm/Target/TargetMachine.h"
Chris Lattnera11136b2003-08-01 22:21:34 +000025#include "Support/Debug.h"
Misha Brukman07218672002-11-22 22:44:32 +000026#include "Support/Statistic.h"
Chris Lattnerabe8dd52002-12-15 18:19:24 +000027#include <iostream>
Misha Brukman07218672002-11-22 22:44:32 +000028
Brian Gaeked0fde302003-11-11 22:41:34 +000029namespace llvm {
30
Misha Brukman59b3eed2002-12-13 10:42:31 +000031namespace {
Chris Lattnerda7e4532002-12-15 20:36:09 +000032 Statistic<> NumSpilled ("ra-simple", "Number of registers spilled");
33 Statistic<> NumReloaded("ra-simple", "Number of registers reloaded");
34
Chris Lattner600dee42002-12-28 20:42:14 +000035 class RegAllocSimple : public MachineFunctionPass {
Misha Brukman07218672002-11-22 22:44:32 +000036 MachineFunction *MF;
Chris Lattner600dee42002-12-28 20:42:14 +000037 const TargetMachine *TM;
Misha Brukman07218672002-11-22 22:44:32 +000038 const MRegisterInfo *RegInfo;
Misha Brukman07218672002-11-22 22:44:32 +000039
Chris Lattner600dee42002-12-28 20:42:14 +000040 // StackSlotForVirtReg - Maps SSA Regs => frame index on the stack where
41 // these values are spilled
42 std::map<unsigned, int> StackSlotForVirtReg;
Misha Brukman07218672002-11-22 22:44:32 +000043
Chris Lattner600dee42002-12-28 20:42:14 +000044 // RegsUsed - Keep track of what registers are currently in use. This is a
45 // bitset.
46 std::vector<bool> RegsUsed;
Chris Lattnerda7e4532002-12-15 20:36:09 +000047
48 // RegClassIdx - Maps RegClass => which index we can take a register
49 // from. Since this is a simple register allocator, when we need a register
50 // of a certain class, we just take the next available one.
Misha Brukman07218672002-11-22 22:44:32 +000051 std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
52
Chris Lattnerda7e4532002-12-15 20:36:09 +000053 public:
Chris Lattner8233e2f2002-12-15 21:13:12 +000054 virtual const char *getPassName() const {
55 return "Simple Register Allocator";
56 }
57
Chris Lattnerda7e4532002-12-15 20:36:09 +000058 /// runOnMachineFunction - Register allocate the whole function
59 bool runOnMachineFunction(MachineFunction &Fn);
60
Chris Lattner80a04782003-01-13 00:26:08 +000061 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
62 AU.addRequiredID(PHIEliminationID); // Eliminate PHI nodes
63 MachineFunctionPass::getAnalysisUsage(AU);
64 }
Chris Lattner600dee42002-12-28 20:42:14 +000065 private:
Chris Lattnerda7e4532002-12-15 20:36:09 +000066 /// AllocateBasicBlock - Register allocate the specified basic block.
67 void AllocateBasicBlock(MachineBasicBlock &MBB);
68
Chris Lattner9f366d72002-12-15 22:19:19 +000069 /// getStackSpaceFor - This returns the offset of the specified virtual
Misha Brukman5560c9d2003-08-18 14:43:39 +000070 /// register on the stack, allocating space if necessary.
Chris Lattner600dee42002-12-28 20:42:14 +000071 int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
Misha Brukman07218672002-11-22 22:44:32 +000072
Chris Lattner9f366d72002-12-15 22:19:19 +000073 /// Given a virtual register, return a compatible physical register that is
74 /// currently unused.
Chris Lattnerda7e4532002-12-15 20:36:09 +000075 ///
Misha Brukman07218672002-11-22 22:44:32 +000076 /// Side effect: marks that register as being used until manually cleared
Chris Lattnerda7e4532002-12-15 20:36:09 +000077 ///
Misha Brukman07218672002-11-22 22:44:32 +000078 unsigned getFreeReg(unsigned virtualReg);
79
Misha Brukman07218672002-11-22 22:44:32 +000080 /// Moves value from memory into that register
Chris Lattnerb167c042002-12-15 23:01:26 +000081 unsigned reloadVirtReg(MachineBasicBlock &MBB,
82 MachineBasicBlock::iterator &I, unsigned VirtReg);
Misha Brukman07218672002-11-22 22:44:32 +000083
84 /// Saves reg value on the stack (maps virtual register to stack value)
Chris Lattnerb167c042002-12-15 23:01:26 +000085 void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
86 unsigned VirtReg, unsigned PhysReg);
Misha Brukman07218672002-11-22 22:44:32 +000087 };
88
Misha Brukman59b3eed2002-12-13 10:42:31 +000089}
Misha Brukman07218672002-11-22 22:44:32 +000090
Chris Lattner9f366d72002-12-15 22:19:19 +000091/// getStackSpaceFor - This allocates space for the specified virtual
Chris Lattnerc2db1a92002-12-15 19:51:14 +000092/// register to be held on the stack.
Chris Lattner600dee42002-12-28 20:42:14 +000093int RegAllocSimple::getStackSpaceFor(unsigned VirtReg,
94 const TargetRegisterClass *RC) {
Chris Lattner9f366d72002-12-15 22:19:19 +000095 // Find the location VirtReg would belong...
Chris Lattner600dee42002-12-28 20:42:14 +000096 std::map<unsigned, int>::iterator I =
97 StackSlotForVirtReg.lower_bound(VirtReg);
Chris Lattner9593fb12002-12-15 19:07:34 +000098
Chris Lattner600dee42002-12-28 20:42:14 +000099 if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
Chris Lattner9f366d72002-12-15 22:19:19 +0000100 return I->second; // Already has space allocated?
Chris Lattner9593fb12002-12-15 19:07:34 +0000101
Chris Lattner600dee42002-12-28 20:42:14 +0000102 // Allocate a new stack object for this spill location...
Chris Lattner80a04782003-01-13 00:26:08 +0000103 int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC);
Chris Lattner9f366d72002-12-15 22:19:19 +0000104
105 // Assign the slot...
Chris Lattner600dee42002-12-28 20:42:14 +0000106 StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
107
108 return FrameIdx;
Misha Brukmanf514d512002-12-02 21:11:58 +0000109}
110
Misha Brukman07218672002-11-22 22:44:32 +0000111unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
Chris Lattner5124aec2002-12-25 05:04:20 +0000112 const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(virtualReg);
Chris Lattner600dee42002-12-28 20:42:14 +0000113 TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
114 TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
Misha Brukman07218672002-11-22 22:44:32 +0000115
Chris Lattner600dee42002-12-28 20:42:14 +0000116 while (1) {
117 unsigned regIdx = RegClassIdx[RC]++;
118 assert(RI+regIdx != RE && "Not enough registers!");
119 unsigned PhysReg = *(RI+regIdx);
120
121 if (!RegsUsed[PhysReg])
122 return PhysReg;
123 }
Misha Brukman07218672002-11-22 22:44:32 +0000124}
125
Chris Lattnerb167c042002-12-15 23:01:26 +0000126unsigned RegAllocSimple::reloadVirtReg(MachineBasicBlock &MBB,
127 MachineBasicBlock::iterator &I,
128 unsigned VirtReg) {
Chris Lattner5124aec2002-12-25 05:04:20 +0000129 const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
Chris Lattner600dee42002-12-28 20:42:14 +0000130 int FrameIdx = getStackSpaceFor(VirtReg, RC);
Chris Lattnerb167c042002-12-15 23:01:26 +0000131 unsigned PhysReg = getFreeReg(VirtReg);
Misha Brukman07218672002-11-22 22:44:32 +0000132
Misha Brukmanf514d512002-12-02 21:11:58 +0000133 // Add move instruction(s)
Chris Lattnerda7e4532002-12-15 20:36:09 +0000134 ++NumReloaded;
Chris Lattner600dee42002-12-28 20:42:14 +0000135 RegInfo->loadRegFromStackSlot(MBB, I, PhysReg, FrameIdx, RC);
Chris Lattnerb167c042002-12-15 23:01:26 +0000136 return PhysReg;
Misha Brukman07218672002-11-22 22:44:32 +0000137}
138
Chris Lattnerb167c042002-12-15 23:01:26 +0000139void RegAllocSimple::spillVirtReg(MachineBasicBlock &MBB,
140 MachineBasicBlock::iterator &I,
Chris Lattner600dee42002-12-28 20:42:14 +0000141 unsigned VirtReg, unsigned PhysReg) {
Chris Lattner5124aec2002-12-25 05:04:20 +0000142 const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
Chris Lattner600dee42002-12-28 20:42:14 +0000143 int FrameIdx = getStackSpaceFor(VirtReg, RC);
Misha Brukmanf514d512002-12-02 21:11:58 +0000144
Misha Brukman07218672002-11-22 22:44:32 +0000145 // Add move instruction(s)
Chris Lattnerda7e4532002-12-15 20:36:09 +0000146 ++NumSpilled;
Chris Lattner600dee42002-12-28 20:42:14 +0000147 RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIdx, RC);
Misha Brukman07218672002-11-22 22:44:32 +0000148}
149
Misha Brukmandc2ec002002-12-03 23:15:19 +0000150
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000151void RegAllocSimple::AllocateBasicBlock(MachineBasicBlock &MBB) {
Chris Lattnerf6050552002-12-15 21:33:51 +0000152 // loop over each instruction
Alkis Evlogimenosc0b9dc52004-02-12 02:27:10 +0000153 for (MachineBasicBlock::iterator MI = MBB.begin(); MI != MBB.end(); ++MI) {
Chris Lattner01b08c52002-12-15 21:24:30 +0000154 // Made to combat the incorrect allocation of r2 = add r1, r1
Chris Lattner9f366d72002-12-15 22:19:19 +0000155 std::map<unsigned, unsigned> Virt2PhysRegMap;
Chris Lattner01b08c52002-12-15 21:24:30 +0000156
Alkis Evlogimenos859a18b2004-02-15 21:37:17 +0000157 RegsUsed.resize(RegInfo->getNumRegs());
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000158
159 // a preliminary pass that will invalidate any registers that
160 // are used by the instruction (including implicit uses)
Chris Lattner600dee42002-12-28 20:42:14 +0000161 unsigned Opcode = MI->getOpcode();
Chris Lattner3501fea2003-01-14 22:00:31 +0000162 const TargetInstrDescriptor &Desc = TM->getInstrInfo().get(Opcode);
Alkis Evlogimenos73ff5122003-10-08 05:20:08 +0000163 const unsigned *Regs = Desc.ImplicitUses;
164 while (*Regs)
165 RegsUsed[*Regs++] = true;
Chris Lattner600dee42002-12-28 20:42:14 +0000166
Alkis Evlogimenos73ff5122003-10-08 05:20:08 +0000167 Regs = Desc.ImplicitDefs;
168 while (*Regs)
169 RegsUsed[*Regs++] = true;
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000170
171 // Loop over uses, move from memory into registers
172 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
173 MachineOperand &op = MI->getOperand(i);
174
Chris Lattner1cbe4d02004-02-10 21:12:22 +0000175 if (op.isRegister() && MRegisterInfo::isVirtualRegister(op.getReg())) {
Alkis Evlogimenosbe766c72004-02-13 21:01:20 +0000176 unsigned virtualReg = (unsigned) op.getReg();
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000177 DEBUG(std::cerr << "op: " << op << "\n");
178 DEBUG(std::cerr << "\t inst[" << i << "]: ";
Chris Lattner600dee42002-12-28 20:42:14 +0000179 MI->print(std::cerr, *TM));
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000180
181 // make sure the same virtual register maps to the same physical
182 // register in any given instruction
Chris Lattner9f366d72002-12-15 22:19:19 +0000183 unsigned physReg = Virt2PhysRegMap[virtualReg];
184 if (physReg == 0) {
Alkis Evlogimenos4d7af652003-12-14 13:24:17 +0000185 if (op.isDef()) {
Chris Lattner600dee42002-12-28 20:42:14 +0000186 if (TM->getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000187 // must be same register number as the first operand
188 // This maps a = b + c into b += c, and saves b into a's spot
Chris Lattner15f96db2002-12-15 21:02:20 +0000189 assert(MI->getOperand(1).isRegister() &&
Alkis Evlogimenosbe766c72004-02-13 21:01:20 +0000190 MI->getOperand(1).getReg() &&
Alkis Evlogimenos4d7af652003-12-14 13:24:17 +0000191 MI->getOperand(1).isUse() &&
Chris Lattner15f96db2002-12-15 21:02:20 +0000192 "Two address instruction invalid!");
193
Alkis Evlogimenosbe766c72004-02-13 21:01:20 +0000194 physReg = MI->getOperand(1).getReg();
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000195 } else {
196 physReg = getFreeReg(virtualReg);
197 }
Alkis Evlogimenosc0b9dc52004-02-12 02:27:10 +0000198 ++MI;
199 spillVirtReg(MBB, MI, virtualReg, physReg);
200 --MI;
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000201 } else {
Alkis Evlogimenosc0b9dc52004-02-12 02:27:10 +0000202 physReg = reloadVirtReg(MBB, MI, virtualReg);
Chris Lattnerb167c042002-12-15 23:01:26 +0000203 Virt2PhysRegMap[virtualReg] = physReg;
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000204 }
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000205 }
206 MI->SetMachineOperandReg(i, physReg);
207 DEBUG(std::cerr << "virt: " << virtualReg <<
Alkis Evlogimenosbe766c72004-02-13 21:01:20 +0000208 ", phys: " << op.getReg() << "\n");
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000209 }
210 }
Chris Lattner600dee42002-12-28 20:42:14 +0000211 RegClassIdx.clear();
212 RegsUsed.clear();
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000213 }
214}
215
Chris Lattnere7d361d2002-12-17 04:19:40 +0000216
Chris Lattnerda7e4532002-12-15 20:36:09 +0000217/// runOnMachineFunction - Register allocate the whole function
218///
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000219bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
Misha Brukman07218672002-11-22 22:44:32 +0000220 DEBUG(std::cerr << "Machine Function " << "\n");
221 MF = &Fn;
Chris Lattner600dee42002-12-28 20:42:14 +0000222 TM = &MF->getTarget();
223 RegInfo = TM->getRegisterInfo();
Misha Brukmandc2ec002002-12-03 23:15:19 +0000224
Chris Lattner9f366d72002-12-15 22:19:19 +0000225 // Loop over all of the basic blocks, eliminating virtual register references
Misha Brukman07218672002-11-22 22:44:32 +0000226 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
227 MBB != MBBe; ++MBB)
Chris Lattnerc2db1a92002-12-15 19:51:14 +0000228 AllocateBasicBlock(*MBB);
Misha Brukman07218672002-11-22 22:44:32 +0000229
Chris Lattner600dee42002-12-28 20:42:14 +0000230 StackSlotForVirtReg.clear();
Chris Lattner9f366d72002-12-15 22:19:19 +0000231 return true;
Misha Brukman07218672002-11-22 22:44:32 +0000232}
233
Brian Gaeke19df3872003-08-13 18:18:15 +0000234FunctionPass *createSimpleRegisterAllocator() {
Chris Lattner600dee42002-12-28 20:42:14 +0000235 return new RegAllocSimple();
Misha Brukman07218672002-11-22 22:44:32 +0000236}
Brian Gaeked0fde302003-11-11 22:41:34 +0000237
238} // End llvm namespace