1 using System;
2 using System.Collections;
3 using CodeFormatter = System.Text.CodeFormatter;
4
5 namespace cmsx.intermediate
6 {
7 public class BasicBlock
8 {
9 public nothrow BasicBlock(Function& function_, uint id_) : function(function_), id(id_), registerDescriptors(function.context.regs), empty(true)
10 {
11 }
12 public nothrow void AddInstruction(Instruction* instruction, MDStructRef* metadata)
13 {
14 instruction->parent = this;
15 instruction->metadata = metadata;
16 instructions.Add(UniquePtr<Instruction>(instruction));
17 empty = false;
18 }
19 public nothrow Instruction* GetLeader() const
20 {
21 return instructions.Front().Get();
22 }
23 public nothrow Instruction* GetLastInstruction() const
24 {
25 if (!instructions.IsEmpty())
26 {
27 return instructions.Back().Get();
28 }
29 else
30 {
31 return null;
32 }
33 }
34 public nothrow List<UniquePtr<Instruction>>& Instructions()
35 {
36 return instructions;
37 }
38 public void MapInstructions(uint& nextIdNumber)
39 {
40 for (const UniquePtr<Instruction>& instruction : instructions)
41 {
42 ValueInstruction* valueInst = instruction.Get() as ValueInstruction*;
43 if (valueInst != null)
44 {
45 IdValue* idValue = valueInst->Result() as IdValue*;
46 if (idValue != null)
47 {
48 if (idValue->id != nextIdNumber)
49 {
50 throw Exception("error: value number " + ToString(nextIdNumber) + " expected for " + instruction->OperationName() + " instruction at line " + ToString(instruction->line));
51 }
52 function.MapInstruction(idValue->id, instruction.Get());
53 nextIdNumber = nextIdNumber + 1u;
54 }
55 else
56 {
57 throw Exception("internal error: value instruction '" + instruction->OperationName() + "' at line " + ToString(instruction->line) + " has no id value");
58 }
59 }
60 }
61 }
62 public void Validate()
63 {
64 function.ResetNextArgIndex();
65 long n = instructions.Count();
66 int numParams = 0;
67 int numArgs = 0;
68 List<ArgInstruction*> args;
69 for (long i = 0; i < n; ++i;)
70 {
71 Instruction* instruction = instructions[i].Get();
72 if (i < n - 1 && (instruction is TerminatorInstruction*))
73 {
74 throw Exception("error: terminator instruction " + instruction->OperationName() + " at line " + ToString(instruction->line) + " found in the middle of a basic block");
75 }
76 else if (i == n - 1 && !(instruction is TerminatorInstruction*) && !(instruction is NoOperationInstruction*))
77 {
78 throw Exception("error: the last instruction of a basic block, the " + instruction->OperationName() + " instruction at line " + ToString(instruction->line) + " must be a terminator instruction");
79 }
80 bool resetArgs = true;
81 if (instruction is ArgInstruction*)
82 {
83 ++numArgs;
84 resetArgs = false;
85 args.Add(cast<ArgInstruction*>(instruction));
86 }
87 else if (instruction is ParamInstruction*)
88 {
89 if (id == 0u)
90 {
91 ++numParams;
92 }
93 else
94 {
95 throw Exception("error: a non-entry block contains a param instruction (line " + ToString(instruction->line) + ")");
96 }
97 }
98 else if ((instruction is FunctionCallInstruction*) || (instruction is ProcedureCallInstruction*) || (instruction is TrapInstruction*))
99 {
100 for (ArgInstruction* arg : args)
101 {
102 arg->numArgs = numArgs;
103 if (instruction is TrapInstruction*)
104 {
105 arg->trap = true;
106 }
107 }
108 }
109 instruction->Validate(function, numArgs);
110 if (resetArgs)
111 {
112 numArgs = 0;
113 args.Clear();
114 }
115 }
116 if (id == 0u && numParams != function.type->ParamTypes().Count())
117 {
118 throw Exception("error: wrong number of param instructions for function " + function.name);
119 }
120 }
121 public void Print(CodeFormatter& formatter, int stage)
122 {
123 if (instructions.IsEmpty())
124 {
125 return;
126 }
127 int indentSize = formatter.IndentSize();
128 formatter.DecIndent();
129 formatter << Format(Name(), indentSize, FormatWidth.min);
130 bool first = true;
131 for (const UniquePtr<Instruction>& instruction : instructions)
132 {
133 instruction->Print(formatter);
134 if (livenessAndNextUseComputed)
135 {
136 instruction->PrintLivenessAndNextUse(60, formatter);
137 }
138 if (first)
139 {
140 first = false;
141 int fieldPos = 60;
142 if (livenessAndNextUseComputed)
143 {
144 fieldPos = 100;
145 }
146 formatter << string(' ', Max(cast<long>(1), fieldPos - formatter.Pos()));
147 if (predecessors.IsEmpty())
148 {
149 if (id != 0u)
150 {
151 formatter << "no predecessors!";
152 }
153 else
154 {
155 formatter << "predecessors: -";
156 }
157 }
158 else
159 {
160 formatter << "predecessors: ";
161 bool f = true;
162 for (BasicBlock* predecessor : predecessors)
163 {
164 if (f)
165 {
166 f = false;
167 }
168 else
169 {
170 formatter << ", ";
171 }
172 formatter << predecessor->Name();
173 }
174 }
175 formatter.IncIndent();
176 }
177 bool machineCodePrinted = false;
178 if (stage == printMachineCodeStage)
179 {
180 instruction->PrintMachineCode(formatter, machineCodePrinted);
181 }
182 if (!machineCodePrinted)
183 {
184 formatter.WriteLine();
185 }
186 }
187 }
188 public nothrow string Name() const
189 {
190 if (id == prologId)
191 {
192 return "";
193 }
194 return "@" + ToString(id);
195 }
196 public nothrow void AddPredecessor(BasicBlock* predecessor)
197 {
198 for (BasicBlock* bb : predecessors)
199 {
200 if (bb == predecessor) return;
201 }
202 predecessors.Add(predecessor);
203 }
204 public nothrow void ComputeLivenessAndNextUse()
205 {
206 livenessAndNextUseComputed = true;
207 long n = instructions.Count();
208 for (long i = 0; i < n; ++i;)
209 {
210 Instruction* instruction = instructions[i].Get();
211 if (instruction is LocalInstruction* || instruction is ParamInstruction*)
212 {
213 livenessAndNextUseMap[instruction] = MakePair(Liveness.live, cast<Value*>(null));
214 }
215 }
216 for (long i = n - 1; i >= 0; --i;)
217 {
218 Instruction* instruction = instructions[i].Get();
219 instruction->ComputeLivenessAndNextUse();
220 }
221 }
222 public nothrow const Pair<Liveness, Value*>* GetCurrentLivenessAndNextUse(Value* value)
223 {
224 HashMap<Value*, Pair<Liveness, Value*>>.ConstIterator it = livenessAndNextUseMap.CFind(value);
225 if (it != livenessAndNextUseMap.CEnd())
226 {
227 return &it->second;
228 }
229 else
230 {
231 return null;
232 }
233 }
234 public nothrow void SetValueLivenessAndNextUse(Value* value, Liveness liveness, Value* nextUse)
235 {
236 HashMap<Value*, Pair<Liveness, Value*>>.ConstIterator it = livenessAndNextUseMap.CFind(value);
237 if (it != livenessAndNextUseMap.CEnd())
238 {
239 livenessAndNextUseMap[value] = MakePair(liveness, nextUse);
240 }
241 }
242 public void GenerateCode(MachineCode& machineCode, CodeFormatter& formatter)
243 {
244 function.addressDescriptors.RemoveRegisterLocations();
245 long n = instructions.Count();
246 for (long i = 0; i < n; ++i;)
247 {
248 Instruction* instruction = instructions[i].Get();
249 if (i == 200)
250 {
251 int x = 0;
252 }
253 instruction->GenerateCode(machineCode, formatter);
254 }
255 }
256 public inline nothrow bool IsEmpty() const
257 {
258 return empty;
259 }
260 public inline nothrow void SetEmpty(bool empty_)
261 {
262 empty = empty_;
263 }
264 public inline nothrow List<BasicBlock*>& Predecessors()
265 {
266 return predecessors;
267 }
268 public inline nothrow void SetId(uint id_)
269 {
270 id = id_;
271 }
272 public inline nothrow uint Id() const
273 {
274 return id;
275 }
276 public Function& function;
277 public RegisterDescriptors registerDescriptors;
278 private uint id;
279 private bool empty;
280 private List<UniquePtr<Instruction>> instructions;
281 private List<BasicBlock*> predecessors;
282 private HashMap<Value*, Pair<Liveness, Value*>> livenessAndNextUseMap;
283 private bool livenessAndNextUseComputed;
284 }
285 }