1 module d.ir.instruction;
2 
3 import source.context;
4 import source.location;
5 import source.name;
6 
7 import d.ir.expression;
8 import d.ir.symbol;
9 
10 struct Body {
11 private:
12 	BasicBlock[] basicBlocks;
13 
14 public:
15 	ref inout(BasicBlock) opIndex(BasicBlockRef i) inout in {
16 		assert(i, "null block ref");
17 		assert(i.index <= basicBlocks.length, "Out of bounds block ref");
18 	} do {
19 		return basicBlocks.ptr[i.index - 1];
20 	}
21 
22 	bool opCast(T : bool)() const {
23 		return basicBlocks.length > 0;
24 	}
25 
26 	@property
27 	auto length() const {
28 		return basicBlocks.length;
29 	}
30 
31 	// XXX: Required due to conversion rules.
32 	BasicBlockRef newBasicBlock(Name name) {
33 		BasicBlockRef landingpad;
34 		return newBasicBlock(name, landingpad);
35 	}
36 
37 	BasicBlockRef newBasicBlock(Name name, BasicBlockRef landingpad) {
38 		auto i = cast(uint) basicBlocks.length;
39 		auto bbref = BasicBlockRef(i);
40 		// XXX: We can't happend because it is non copyable (DMD bug, IMO).
41 		// basicBlocks ~= BasicBlock(bbref);
42 		basicBlocks.length += 1;
43 		basicBlocks[i] = BasicBlock(name, landingpad);
44 		return bbref;
45 	}
46 
47 	void dump(const Context c) const {
48 		foreach (ref b; basicBlocks) {
49 			dump(c, b);
50 		}
51 	}
52 
53 	void dump(const Context c, const ref BasicBlock b) const {
54 		import std.stdio;
55 		writeln();
56 		dumpBasicBlockName(c, b);
57 		write(':');
58 
59 		if (b.landingpad) {
60 			import std.stdio;
61 			write("\t\t\t\tunwind to ");
62 			dumpBasicBlockName(c, this[b.landingpad]);
63 		}
64 
65 		writeln();
66 
67 		foreach (ref i; b.instructions) {
68 			dump(c, b, i);
69 		}
70 
71 		final switch (b.terminator) with (Terminator) {
72 			case None:
73 				writeln("unterminated...");
74 				break;
75 
76 			case Branch:
77 				write("\tbranch ");
78 				if (b.value is null) {
79 					dumpBasicBlockName(c, this[b.successors[0]]);
80 				} else {
81 					write(b.value.toString(c), ", ");
82 					dumpBasicBlockName(c, this[b.successors[0]]);
83 					write(", ");
84 					dumpBasicBlockName(c, this[b.successors[1]]);
85 				}
86 
87 				writeln();
88 				break;
89 
90 			case Switch:
91 				writeln("\tswitch ", b.value.toString(c));
92 				write("\t\tdefault: ");
93 				dumpBasicBlockName(c, this[b.switchTable.defaultBlock]);
94 				foreach (ce; b.switchTable.cases) {
95 					write("\n\t\tcase ", ce.value, ": ");
96 					dumpBasicBlockName(c, this[ce.block]);
97 				}
98 
99 				writeln();
100 				break;
101 
102 			case Return:
103 				writeln("\treturn ", b.value ? b.value.toString(c) : "void");
104 				break;
105 
106 			case Throw:
107 				if (b.value) {
108 					writeln("\tthrow ", b.value.toString(c));
109 				} else if (b.catchTable) {
110 					write("\tcatch");
111 					foreach (ca; b.catchTable.catches) {
112 						write("\n\t\t", ca.type.name.toString(c), ": ");
113 						dumpBasicBlockName(c, this[ca.block]);
114 					}
115 
116 					writeln();
117 				} else {
118 					writeln("\trethrow");
119 				}
120 
121 				break;
122 
123 			case Halt:
124 				writeln("\thalt ", b.value ? b.value.toString(c) : "");
125 				break;
126 		}
127 	}
128 
129 	void dumpBasicBlockName(const Context c, const ref BasicBlock b) const {
130 		size_t index = (cast(size_t) &b - cast(size_t) basicBlocks.ptr)
131 			/ BasicBlock.sizeof;
132 
133 		import std.stdio;
134 		write(b.name.toString(c), index);
135 	}
136 
137 	void dump(const Context c, const ref BasicBlock b,
138 	          const ref Instruction i) const {
139 		import std.stdio;
140 		final switch (i.op) with (OpCode) {
141 			case Alloca:
142 				writeln("\t", i.var.toString(c));
143 				break;
144 
145 			case Destroy:
146 				writeln("\tdestroy\t", i.var.name.toString(c));
147 				break;
148 
149 			case Evaluate:
150 				writeln("\t", i.expr.toString(c));
151 				break;
152 
153 			case Declare:
154 				writeln("\t", i.sym.toString(c));
155 				break;
156 		}
157 	}
158 }
159 
160 auto range(const Body fbody) {
161 	import std.algorithm, std.range;
162 	return iota(0, cast(uint) fbody.basicBlocks.length)
163 		.map!(i => BasicBlockRef(i));
164 }
165 
166 struct BasicBlockRef {
167 private:
168 	uint index;
169 
170 	this(uint index) {
171 		this.index = index + 1;
172 	}
173 
174 public:
175 	bool opCast(T : bool)() const {
176 		return index != 0;
177 	}
178 
179 	BasicBlockRef opAssign(typeof(null)) {
180 		index = 0;
181 		return this;
182 	}
183 }
184 
185 auto range(inout Body fbody, BasicBlockRef b) {
186 	return fbody[b].instructions;
187 }
188 
189 enum Terminator {
190 	None,
191 	Branch,
192 	Switch,
193 	Return,
194 	Throw,
195 	Halt,
196 }
197 
198 struct BasicBlock {
199 private:
200 	Instruction[] instructions;
201 
202 	import source.name;
203 	Name _name;
204 
205 	Terminator _terminator;
206 	union {
207 		public BasicBlockRef[2] successors;
208 		public SwitchTable* switchTable;
209 		public CatchTable* catchTable;
210 	}
211 
212 	// We need to win a uint in there so that this is 4 pointers sized.
213 	// We probably won't need more than 4G instructions, so we can win
214 	// int he instruction array length.
215 	BasicBlockRef _landingpad;
216 
217 	// XXX: Let's say I'm not happy with that layout.
218 	public Location location;
219 	public Expression value;
220 
221 	this(Name name, BasicBlockRef landingpad) {
222 		_name = name;
223 		_landingpad = landingpad;
224 	}
225 
226 	@disable
227 	this(this);
228 
229 	void add(Instruction i) in {
230 		assert(!terminate, "block does terminate already");
231 	} do {
232 		instructions ~= i;
233 	}
234 
235 public:
236 	@property
237 	Name name() const {
238 		return _name;
239 	}
240 
241 	@property
242 	Terminator terminator() const {
243 		return _terminator;
244 	}
245 
246 	@property
247 	bool terminate() const {
248 		return terminator != Terminator.None;
249 	}
250 
251 	@property
252 	bool empty() const {
253 		return !terminate && instructions.length == 0;
254 	}
255 
256 	@property
257 	BasicBlockRef landingpad() const {
258 		return _landingpad;
259 	}
260 
261 	@property
262 	BasicBlockRef landingpad(BasicBlockRef landingpad) {
263 		return _landingpad = landingpad;
264 	}
265 
266 	void alloca(Location location, Variable v) {
267 		add(Instruction(location, v));
268 	}
269 
270 	void destroy(Location location, Variable v) {
271 		add(Instruction.destroy(location, v));
272 	}
273 
274 	void eval(Location location, Expression e) {
275 		add(Instruction(location, e));
276 	}
277 
278 	void declare(Location location, Symbol s) {
279 		add(Instruction(location, s));
280 	}
281 
282 	void branch(Location location, BasicBlockRef dst) {
283 		_terminator = Terminator.Branch;
284 		successors[0] = dst;
285 	}
286 
287 	void branch(Location location, Expression cond, BasicBlockRef ifTrue,
288 	            BasicBlockRef ifFalse) {
289 		_terminator = Terminator.Branch;
290 
291 		// XXX: ALARM! ALARM!
292 		value = cond;
293 		successors[0] = ifTrue;
294 		successors[1] = ifFalse;
295 	}
296 
297 	void doSwitch(Location location, Expression e, SwitchTable* switchTable) {
298 		_terminator = Terminator.Switch;
299 		this.location = location;
300 		this.value = e;
301 		this.switchTable = switchTable;
302 	}
303 
304 	void ret(Location location, Expression e = null) {
305 		_terminator = Terminator.Return;
306 		this.location = location;
307 		value = e;
308 	}
309 
310 	void doThrow(Location location, Expression e = null) {
311 		_terminator = Terminator.Throw;
312 		this.location = location;
313 		value = e;
314 	}
315 
316 	void doCatch(Location location, CatchTable* catchTable) {
317 		_terminator = Terminator.Throw;
318 		this.location = location;
319 		this.catchTable = catchTable;
320 	}
321 
322 	void halt(Location location, Expression msg = null) {
323 		_terminator = Terminator.Halt;
324 		this.location = location;
325 		value = msg;
326 	}
327 }
328 
329 enum OpCode {
330 	Alloca,
331 	Destroy,
332 	Evaluate,
333 
334 	// FIXME: This is unecessary, but will makes things easier for now.
335 	Declare,
336 }
337 
338 struct Instruction {
339 	Location location;
340 
341 	OpCode op;
342 
343 	union {
344 		Expression expr;
345 		Variable var;
346 		Symbol sym;
347 	}
348 
349 private:
350 	this(Location location, Expression e) {
351 		this.location = location;
352 		op = OpCode.Evaluate;
353 		expr = e;
354 	}
355 
356 	this(Location location, Variable v) in {
357 		assert(v.step == Step.Processed, "Variable is not processed");
358 	} do {
359 		this.location = location;
360 		op = OpCode.Alloca;
361 		var = v;
362 	}
363 
364 	static destroy(Location location, Variable v) {
365 		auto i = Instruction(location, v);
366 		i.op = OpCode.Destroy;
367 		return i;
368 	}
369 
370 	this(Location location, Symbol s) in {
371 		assert(s.step == Step.Processed, "Symbol is not processed");
372 		assert(!cast(Variable) s, "Use alloca for variables");
373 	} do {
374 		this.location = location;
375 		op = OpCode.Declare;
376 		sym = s;
377 	}
378 }
379 
380 struct SwitchTable {
381 	BasicBlockRef defaultBlock;
382 	uint entryCount;
383 
384 	@property
385 	inout(CaseEntry)[] cases() inout {
386 		return (cast(inout(CaseEntry)*) &(&this)[1])[0 .. entryCount];
387 	}
388 }
389 
390 struct CaseEntry {
391 	BasicBlockRef block;
392 	uint value;
393 }
394 
395 struct CatchTable {
396 	size_t catchCount;
397 	BasicBlockRef catchAll;
398 
399 	@property
400 	inout(CatchPad)[] catches() inout {
401 		return (cast(inout(CatchPad)*) &(&this)[1])[0 .. catchCount];
402 	}
403 }
404 
405 struct CatchPad {
406 	Class type;
407 	BasicBlockRef block;
408 }