1 using System;
2 using System.IO;
3 using System.Collections;
4 using CodeFormatter = System.Text.CodeFormatter;
5
6 namespace cmsx.intermediate
7 {
8 public class RegisterDescriptor
9 {
10 public nothrow RegisterDescriptor(Register* reg_) : reg(reg_), loaded(false)
11 {
12 }
13 public void DebugPrint(CodeFormatter& formatter)
14 {
15 reg->DebugPrint(formatter);
16 formatter << "(";
17 bool first = true;
18 for (Value* value : values)
19 {
20 if (first)
21 {
22 first = false;
23 }
24 else
25 {
26 formatter << ", ";
27 }
28 formatter << value->Name();
29 }
30 formatter << ")";
31 }
32 public nothrow void SetValue(Value* value)
33 {
34 values.Clear();
35 values.Add(value);
36 loaded = false;
37 }
38 public nothrow void AddValue(Value* value)
39 {
40 for (Value* v : values)
41 {
42 if (v == value) return;
43 }
44 values.Add(value);
45 }
46 public inline nothrow bool HasValue(Value* value)
47 {
48 return Find(values.CBegin(), values.CEnd(), value) != values.CEnd();
49 }
50 public inline nothrow bool IsEmpty() const
51 {
52 return values.IsEmpty();
53 }
54 public Register* reg;
55 public List<Value*> values;
56 public bool loaded;
57 }
58
59 public class RegisterDescriptors
60 {
61 public nothrow RegisterDescriptors(Registers& regs_) : regs(regs_), numUsedLocalRegs(0u)
62 {
63 byte np = regs.GetNumParamRegisters();
64 for (byte i = 0u; i < np; ++i;)
65 {
66 registerDescriptors.Add(RegisterDescriptor(regs.GetParamRegister(i)));
67 }
68 byte nl = regs.GetNumLocalRegisters();
69 for (byte i = 0u; i < nl; ++i;)
70 {
71 registerDescriptors.Add(RegisterDescriptor(regs.GetLocalRegister(i)));
72 }
73 for (RegisterDescriptor& descriptor : registerDescriptors)
74 {
75 registerDescriptorMap[descriptor.reg] = &descriptor;
76 }
77 }
78 public nothrow RegisterDescriptor* GetRegisterDescriptor(Register* reg) const
79 {
80 HashMap<Register*, RegisterDescriptor*>.ConstIterator it = registerDescriptorMap.CFind(reg);
81 if (it != registerDescriptorMap.CEnd())
82 {
83 return it->second;
84 }
85 else
86 {
87 #assert(false);
88 return null;
89 }
90 }
91 public RegisterDescriptor* GetLocalRegDescriptor(const List<Register*>& dontUse, AddressDescriptors& addressDescriptors, MachineCode& machineCode, int line, Instruction* inst)
92 {
93 byte n = regs.GetNumLocalRegisters();
94 for (byte i = 0u; i < n; ++i;)
95 {
96 LocalRegister* localReg = regs.GetLocalRegister(i);
97 if (Find(dontUse.CBegin(), dontUse.CEnd(), localReg) != dontUse.CEnd()) continue;
98 RegisterDescriptor* registerDescriptor = GetRegisterDescriptor(localReg);
99 if (registerDescriptor->IsEmpty())
100 {
101 numUsedLocalRegs = Max(numUsedLocalRegs, i + 1u);
102 return registerDescriptor;
103 }
104 }
105 List<Pair<RegisterDescriptor*, int>> descriptorScores;
106 for (byte i = 0u; i < n; ++i;)
107 {
108 LocalRegister* localReg = regs.GetLocalRegister(i);
109 if (Find(dontUse.CBegin(), dontUse.CEnd(), localReg) != dontUse.CEnd()) continue;
110 RegisterDescriptor* registerDescriptor = GetRegisterDescriptor(localReg);
111 if (registerDescriptor->loaded) continue;
112 int score = 0;
113 for (Value* value : registerDescriptor->values)
114 {
115 if (!(value is LiteralValue*) && value->HomeLocation() != null)
116 {
117 AddressDescriptor* addressDescriptor = addressDescriptors.GetAddressDescriptor(value);
118 bool foundSomewhereElse = true;
119 for (Location* loc : addressDescriptor->locations)
120 {
121 if ((loc is MemoryLocation*))
122 {
123 foundSomewhereElse = true;
124 break;
125 }
126 }
127 if (!foundSomewhereElse)
128 {
129 ++score;
130 }
131 }
132 }
133 descriptorScores.Add(MakePair(registerDescriptor, score));
134 }
135 Pair<RegisterDescriptor*, int> descriptorScore = GetMinScoreDescriptor(descriptorScores);
136 RegisterDescriptor* registerDescriptor = descriptorScore.first;
137 int score = descriptorScore.second;
138 MakeRegisterDescriptorEmpty(*registerDescriptor, addressDescriptors, machineCode, line, inst);
139 numUsedLocalRegs = Max(numUsedLocalRegs, cast<LocalRegister*>(registerDescriptor->reg)->number + 1u);
140 return registerDescriptor;
141 }
142 public void DebugPrint(CodeFormatter& formatter)
143 {
144 formatter << "register descriptors: { " << endl();
145 formatter.IncIndent();
146 for (const RegisterDescriptor& descriptor : registerDescriptors)
147 {
148 if (descriptor.IsEmpty()) continue;
149 descriptor.DebugPrint(formatter);
150 formatter << endl();
151 }
152 formatter.DecIndent();
153 formatter << "}" << endl();
154 }
155 public inline nothrow byte GetNumUsedLocalRegs()
156 {
157 return numUsedLocalRegs;
158 }
159 public inline nothrow void SetNumUsedLocalRegs(byte numUsedLocalRegs_)
160 {
161 numUsedLocalRegs = numUsedLocalRegs_;
162 }
163 private Registers& regs;
164 private List<RegisterDescriptor> registerDescriptors;
165 private HashMap<Register*, RegisterDescriptor*> registerDescriptorMap;
166 private byte numUsedLocalRegs;
167 }
168
169 internal class ScoreLess : Rel<Pair<RegisterDescriptor*, int>>
170 {
171 public inline nothrow bool operator()(const Pair<RegisterDescriptor*, int>& left, const Pair<RegisterDescriptor*, int>& right) const
172 {
173 return left.second < right.second;
174 }
175 }
176
177 internal Pair<RegisterDescriptor*, int> GetMinScoreDescriptor(const List<Pair<RegisterDescriptor*, int>>& descriptorScores)
178 {
179 #assert(!descriptorScores.IsEmpty());
180 List<Pair<RegisterDescriptor*, int>>.ConstIterator it = MinElement(descriptorScores.CBegin(), descriptorScores.CEnd(), ScoreLess());
181 #assert(it != descriptorScores.CEnd());
182 return *it;
183 }
184
185 public void MakeRegisterDescriptorEmpty(RegisterDescriptor& registerDescriptor, AddressDescriptors& addressDescriptors, MachineCode& machineCode, int line, Instruction* inst)
186 {
187 for (Value* value : registerDescriptor.values)
188 {
189 if (value is LiteralValue*) continue;
190 Type* type = value->type;
191 if (type == null)
192 {
193 continue;
194 }
195 #assert(type is ScalarType*);
196 int storeOpCode = type->GetStoreOp(line);
197 AddressDescriptor* addressDescriptor = addressDescriptors.GetAddressDescriptor(value);
198 bool saved = false;
199 if (addressDescriptor != null)
200 {
201 for (Location* loc : addressDescriptor->locations)
202 {
203 if (loc is MemoryLocation*)
204 {
205 loc->GenerateStore(storeOpCode, registerDescriptor.reg, machineCode, inst);
206 saved = true;
207 break;
208 }
209 }
210 }
211 if (!saved)
212 {
213 Location* homeLocation = value->HomeLocation();
214 if (homeLocation != null)
215 {
216 homeLocation->GenerateStore(storeOpCode, registerDescriptor.reg, machineCode, inst);
217 }
218 }
219 }
220 addressDescriptors.RemoveRegister(registerDescriptor.reg);
221 registerDescriptor.values.Clear();
222 }
223
224 public RegisterDescriptor* GetOperandReg(Value* operand, Register* reservedReg, RegisterDescriptors& registerDescriptors, AddressDescriptors& addressDescriptors,
225 MachineCode& machineCode, int line, Instruction* inst)
226 {
227 AddressDescriptor* addressDescriptor = addressDescriptors.GetAddressDescriptor(operand);
228 if (addressDescriptor != null)
229 {
230 Location* loc = addressDescriptor->GetLocation();
231 if (loc != null)
232 {
233 if (loc is Register*)
234 {
235 Register* reg = cast<Register*>(loc);
236 return registerDescriptors.GetRegisterDescriptor(reg);
237 }
238 }
239 }
240 List<Register*> dontUse;
241 if (reservedReg != null)
242 {
243 dontUse.Add(reservedReg);
244 }
245 return registerDescriptors.GetLocalRegDescriptor(dontUse, addressDescriptors, machineCode, line, inst);
246 }
247
248 public void GetReg(Value* x, Value* y, Value* z, bool useRegYForX, RegisterDescriptors& registerDescriptors, AddressDescriptors& addressDescriptors, MachineCode& machineCode, int line,
249 RegisterDescriptor*& rx, RegisterDescriptor*& ry, RegisterDescriptor*& rz, Instruction* inst)
250 {
251 ry = GetOperandReg(y, null, registerDescriptors, addressDescriptors, machineCode, line, inst);
252 if (z != null)
253 {
254 rz = GetOperandReg(z, ry->reg, registerDescriptors, addressDescriptors, machineCode, line, inst);
255 }
256 if (useRegYForX)
257 {
258 rx = ry;
259 }
260 else
261 {
262 List<Register*> dontUse;
263 dontUse.Add(ry->reg);
264 if (rz != null)
265 {
266 dontUse.Add(rz->reg);
267 }
268 rx = registerDescriptors.GetLocalRegDescriptor(dontUse, addressDescriptors, machineCode, line, inst);
269 }
270 }
271
272 public void LoadOperandValue(Value* operand, RegisterDescriptor* targetRegisterDescriptor, AddressDescriptors& addressDescriptors, MachineCode& machineCode, int line, Instruction* inst)
273 {
274 if (targetRegisterDescriptor->HasValue(operand)) return;
275 AddressDescriptor* addressDescriptor = addressDescriptors.GetAddressDescriptor(operand);
276 Location* loc = addressDescriptor->GetLocation();
277 if (loc == null)
278 {
279 loc = operand->HomeLocation();
280 }
281 if (loc != null)
282 {
283 Type* type = operand->type;
284 int loadOpCode = type->GetLoadOp(line);
285 loc->GenerateLoad(loadOpCode, targetRegisterDescriptor->reg, machineCode, inst);
286 targetRegisterDescriptor->SetValue(operand);
287 addressDescriptor->AddLocation(targetRegisterDescriptor->reg);
288 }
289 else
290 {
291 throw Exception("error: could not load operand value, location for operand '" + operand->Name() + "' not found (line " + ToString(line) + ")");
292 }
293 }
294
295 public void LoadOperandAddress(Value* operand, RegisterDescriptor* targetRegisterDescriptor, AddressDescriptors& addressDescriptors, MachineCode& machineCode, int line, Instruction* inst)
296 {
297 if (targetRegisterDescriptor->HasValue(operand)) return;
298 AddressDescriptor* addressDescriptor = addressDescriptors.GetAddressDescriptor(operand);
299 Location* loc = addressDescriptor->GetLocation();
300 if (loc == null)
301 {
302 loc = operand->HomeLocation();
303 }
304 if (loc != null)
305 {
306 loc->GenerateLoadAddress(targetRegisterDescriptor->reg, machineCode, inst);
307 }
308 else
309 {
310 throw Exception("error: could not load operand address, location for operand '" + operand->Name() + "' not found (line " + ToString(line) + ")");
311 }
312 }
313
314 public bool CanUseRegYForX(Value* y, RegisterDescriptors& registerDescriptors, AddressDescriptors& addressDescriptors)
315 {
316 if (y is LoadInstruction*)
317 {
318 AddressDescriptor* adY = addressDescriptors.GetAddressDescriptor(y);
319 Location* locY = adY->GetLocation();
320 if (locY == null) return true;
321 if (locY is LocalRegister*)
322 {
323 LoadInstruction* loadY = cast<LoadInstruction*>(y);
324 if (loadY->numUses <= 1)
325 {
326 return true;
327 }
328 }
329 }
330 return false;
331 }
332 }