blob: bd41c8882c3d7dd83a8644eb2dc0ff201f22e5f4 [file] [log] [blame]
Ruchira Sasankaf5788aa2001-09-08 14:22:50 +00001/* Title: PhyRegAlloc.h
2 Author: Ruchira Sasanka
3 Date: Aug 20, 01
4 Purpose: This is the main entry point for register allocation.
5
6 Notes:
7
8 * RegisterClasses: Each RegClass accepts a
9 MachineRegClass which contains machine specific info about that register
10 class. The code in the RegClass is machine independent and they use
11 access functions in the MachineRegClass object passed into it to get
12 machine specific info.
13
14 * Machine dependent work: All parts of the register coloring algorithm
15 except coloring of an individual node are machine independent.
16
17 Register allocation must be done as:
18
19 static const MachineRegInfo MRI = MachineRegInfo(); // machine reg info
20
21 MethodLiveVarInfo LVI(*MethodI ); // compute LV info
22 LVI.analyze();
23
24 PhyRegAlloc PRA(*MethodI, &MRI, &LVI); // allocate regs
25 PRA.allocateRegisters();
26
27 Assumptions:
28 All values in a live range will be of the same physical reg class.
29
30*/
31
32
33
34#ifndef PHY_REG_ALLOC_H
35#define PHY_REG_ALLOC_H
36
37#include "llvm/CodeGen/MachineInstr.h"
Ruchira Sasankaf5788aa2001-09-08 14:22:50 +000038#include "llvm/CodeGen/RegClass.h"
39#include "llvm/CodeGen/LiveRangeInfo.h"
40#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
41
Ruchira Sasanka33535772001-10-15 16:22:44 +000042#include <deque>
Ruchira Sasankaf5788aa2001-09-08 14:22:50 +000043
44class AddedInstrns
45{
46 public:
Ruchira Sasanka33535772001-10-15 16:22:44 +000047 deque<MachineInstr *> InstrnsBefore;
48 deque<MachineInstr *> InstrnsAfter;
Ruchira Sasankaf5788aa2001-09-08 14:22:50 +000049
50 AddedInstrns() : InstrnsBefore(), InstrnsAfter() { }
51};
52
53typedef hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
54
55
56
57class PhyRegAlloc
58{
59
60 vector<RegClass *> RegClassList ; // vector of register classes
61 const Method *const Meth; // name of the method we work on
62 const TargetMachine &TM; // target machine
63 MethodLiveVarInfo *const LVI; // LV information for this method
64 // (already computed for BBs)
65 LiveRangeInfo LRI; // LR info (will be computed)
66 const MachineRegInfo &MRI; // Machine Register information
67 const unsigned NumOfRegClasses; // recorded here for efficiency
68
Ruchira Sasanka560b0ad2001-09-30 23:19:57 +000069 //vector<const Instruction *> CallInstrList; // a list of all call instrs
70 //vector<const Instruction *> RetInstrList; // a list of all return instrs
Ruchira Sasankaf5788aa2001-09-08 14:22:50 +000071
72 AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
73
74
Ruchira Sasankaf60342a2001-09-15 00:33:26 +000075
Ruchira Sasankaf5788aa2001-09-08 14:22:50 +000076 //------- private methods ---------------------------------------------------
77
78 void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
79 const bool isCallInst);
80
81 void addInterferencesForArgs();
82 void createIGNodeListsAndIGs();
83 void buildInterferenceGraphs();
Ruchira Sasanka5b8971f2001-10-16 01:23:19 +000084 void insertCallerSavingCode(const MachineInstr *MInst,
85 const BasicBlock *BB );
86
Ruchira Sasanka6275a042001-10-19 17:21:59 +000087 void setCallInterferences(const MachineInstr *MInst,
88 const LiveVarSet *const LVSetAft );
Ruchira Sasankaf5788aa2001-09-08 14:22:50 +000089
90 inline void constructLiveRanges()
91 { LRI.constructLiveRanges(); }
92
93 void colorIncomingArgs();
Ruchira Sasanka560b0ad2001-09-30 23:19:57 +000094 void colorCallRetArgs();
Ruchira Sasankaf5788aa2001-09-08 14:22:50 +000095 void updateMachineCode();
Ruchira Sasanka560b0ad2001-09-30 23:19:57 +000096
Ruchira Sasanka86b2ad42001-09-15 19:08:41 +000097 void printLabel(const Value *const Val);
98 void printMachineCode();
Ruchira Sasankaf5788aa2001-09-08 14:22:50 +000099
100 public:
101 PhyRegAlloc(const Method *const M, const TargetMachine& TM,
102 MethodLiveVarInfo *const Lvi);
103
104 void allocateRegisters(); // main method called for allocatin
105
106};
107
108
109
110
111
112
113
114
115#endif
116