1 /**
2 Copyright: Copyright (c) 2017-2019 Andrey Penechko.
3 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
4 Authors: Andrey Penechko.
5 */
6 /// IR instruction format and metadata
7 module vox.ir.ir_instructions;
8 
9 import std.traits : getUDAs;
10 import std.bitmanip : bitfields;
11 
12 import vox.all;
13 import vox.ir.ir_index;
14 
15 enum IrInstructionSet : ubyte
16 {
17 	ir,
18 	lir_amd64
19 }
20 immutable string[] instr_set_names = ["IR", "LIR Amd64"];
21 static assert(instr_set_names.length == IrInstructionSet.max+1);
22 
23 immutable InstrInfo[][] allInstrInfos = [
24 	irInstrInfos,
25 	amd64InstrInfos
26 ];
27 
28 struct InstrInfo
29 {
30 	this(byte _numArgs, uint _flags = 0, ubyte _numHiddenArgs = 0) {
31 		numArgs = _numArgs;
32 		flags = _flags;
33 		numHiddenArgs = _numHiddenArgs;
34 	}
35 
36 	/// If hasVariadicArgs is set, then determines the minimum required number of arguments
37 	/// Otherwise specifies exact number of arguments
38 	/// Is copied to IrInstrHeader.numArgs
39 	ubyte numArgs;
40 
41 	/// those are allocated after results and arguments
42 	/// Doesn't affect IrInstrHeader.numArgs
43 	/// If contains non IrIndex data, then must be of type IrValueKind.none. (Only lowest 28 bits can be used)
44 	ubyte numHiddenArgs;
45 
46 	/// Set of IrInstrFlags
47 	uint flags;
48 
49 	static assert(IrInstrFlags.max <= uint.max, "Not enough bits for flags");
50 
51 	bool isMov() const { return (flags & IFLG.isMov) != 0; }
52 	bool isJump() const { return (flags & IFLG.isJump) != 0; }
53 	bool isBranch() const { return (flags & IFLG.isBranch) != 0; }
54 	bool isBlockExit() const { return (flags & IFLG.isBlockExit) != 0; }
55 	bool isLoad() const { return (flags & IFLG.isLoad) != 0; }
56 	bool isStore() const { return (flags & IFLG.isStore) != 0; }
57 	bool modifiesMemory() const { return (flags & IFLG.modifiesMemory) != 0; }
58 	bool hasResult() const { return (flags & IFLG.hasResult) != 0; }
59 	bool hasVariadicArgs() const { return (flags & IFLG.hasVariadicArgs) != 0; }
60 	bool hasVariadicResult() const { return (flags & IFLG.hasVariadicResult) != 0; }
61 	bool hasCondition() const { return (flags & IFLG.hasCondition) != 0; }
62 	bool isResultInDst() const { return (flags & IFLG.isResultInDst) != 0; }
63 	bool isCommutative() const { return (flags & IFLG.isCommutative) != 0; }
64 	bool isCall() const { return (flags & IFLG.isCall) != 0; }
65 	bool isGeneric() const { return (flags & IFLG.isGeneric) != 0; }
66 	bool hasSideEffects() const { return (flags & IFLG.hasSideEffects) != 0; }
67 
68 	bool mayHaveResult() { return hasResult || hasVariadicResult; }
69 }
70 
71 InstrInfo[] gatherInstrInfos(alias instrsEnum)()
72 {
73 	InstrInfo[] res = new InstrInfo[__traits(allMembers, instrsEnum).length];
74 	foreach (i, m; __traits(allMembers, instrsEnum))
75 	{
76 		res[i] = __traits(getAttributes, __traits(getMember, instrsEnum, m))[0];
77 	}
78 	return res;
79 }
80 
81 enum IrInstrFlags : uint {
82 	none = 0,
83 	hasResult = 1 << 0,
84 	isMov = 1 << 1,
85 	isBranch = 1 << 2,
86 	isJump = 1 << 3,
87 	isBlockExit = 1 << 4,
88 	isLoad = 1 << 5,
89 	isStore = 1 << 6,
90 	modifiesMemory = 1 << 7,
91 	/// If set, InstrInfo.numArgs defines minimaly required number of args
92 	/// and IrInstrHeader.numArgs is set at runtime
93 	/// IrBuilder automatically allocates nesessary amount of argument slots after the result slot
94 	hasVariadicArgs = 1 << 8,
95 	/// If set IFLG.hasResult flag must not be set
96 	/// and IrInstrHeader.hasResult is set at runtime
97 	hasVariadicResult = 1 << 9,
98 	/// If set IrInstrHeader.cond is used
99 	hasCondition = 1 << 10,
100 	/// If set machine instruction requires a = a op b, or a = op a form
101 	/// while IR instruction has a = b op c, or a = op b form
102 	isResultInDst = 1 << 11,
103 	/// If order of arguments doesn't change the result
104 	isCommutative = 1 << 12,
105 	isCall = 1 << 13,
106 	/// For reg allocator
107 	/// For instructions with single arg no restrictions
108 	/// For binary instructions - only one of two args or one of result or arg may be memory
109 	/// If not set, then no args/results can be memory
110 	/// If only one of non-fixed arguments can be memory operand
111 	singleMemArg = 1 << 14,
112 	/// If all non-fixed arguments can be memory operands
113 	allMemArg = 1 << 15,
114 	/// If set, then opcode of instruction is set from ExtraInstrArgs.opcode
115 	isGeneric = 1 << 16,
116 	/// Not safe to delete or reorder. Instruction is not a candidate for simple user-based instruction DCE
117 	hasSideEffects = 1 << 17,
118 }
119 
120 // shortcut
121 alias IFLG = IrInstrFlags;
122 
123 enum getInstrInfo(alias T) = getUDAs!(T, InstrInfo)[0];
124 enum getIrValueKind(T) = getUDAs!(T, IrValueKind)[0];
125 
126 // InstrInfo array gathered from IrOpcode enum
127 immutable InstrInfo[] irInstrInfos = gatherInstrInfos!IrOpcode;
128 
129 // shortcut
130 private alias _ii = InstrInfo;
131 
132 /// List of machine-independent opcodes
133 enum IrOpcode : ushort
134 {
135 	// used as placeholder inside generic instructions. Must not remain in IR.
136 	@_ii() invalid,
137 
138 	@_ii(0, IFLG.isBlockExit | IFLG.hasSideEffects) jump,
139 	/// Uses IrUnaryCondition inside IrInstrHeader.cond
140 	@_ii(1, IFLG.hasCondition | IFLG.isBlockExit | IFLG.hasSideEffects) branch_unary,
141 	/// Uses IrBinaryCondition inside IrInstrHeader.cond
142 	@_ii(2, IFLG.hasCondition | IFLG.isBlockExit | IFLG.hasSideEffects) branch_binary,
143 	/// Args:
144 	///   iNN value to be switched on
145 	///   _k_ >= 0 integer constants (no duplicated constants allowed)
146 	/// Basic block successors are in the following order
147 	///   default basic block
148 	///   0 or more case blocks
149 	@_ii(1, IFLG.hasVariadicArgs | IFLG.isBlockExit | IFLG.hasSideEffects) branch_switch,
150 	@_ii(0, IFLG.isBlockExit | IFLG.hasSideEffects) ret,
151 	/// Only for ABI handling
152 	@_ii(1, IFLG.isBlockExit | IFLG.hasSideEffects) ret_val,
153 	@_ii(0, IFLG.isBlockExit | IFLG.hasSideEffects) unreachable,
154 
155 	/// Emitted by frontend and replaced in lowering pass
156 	/// Extra argument represents parameter index and stored as plain uint of type IrValueKind.none.
157 	@_ii(0, IFLG.hasResult | IFLG.hasSideEffects, 1) parameter,
158 	// first argument is function or function pointer
159 	@_ii(1, IFLG.hasVariadicArgs | IFLG.hasVariadicResult | IFLG.hasSideEffects) call,
160 	// first argument is syscall number
161 	@_ii(1, IFLG.hasVariadicArgs | IFLG.hasVariadicResult | IFLG.hasSideEffects) syscall,
162 	// Special instruction used during inlining. Should not occur in other places.
163 	@_ii(0) inline_marker,
164 
165 	/// Args: iNN a, iNN b
166 	/// Returns boolean result of binary comparison: a cond b
167 	@_ii(2, IFLG.hasResult | IFLG.hasCondition) set_binary_cond,
168 	/// Args: iNN a
169 	/// Returns boolean result of unary comparison: cond a
170 	@_ii(1, IFLG.hasResult | IFLG.hasCondition) set_unary_cond,
171 
172 	/// Only for ABI handling
173 	/// Args: T
174 	/// Returns: T
175 	@_ii(1, IFLG.hasResult) move,
176 	/// Lowered into load+store sequence
177 	/// Args: T* dst, T* src
178 	@_ii(2, IFLG.hasSideEffects) copy,
179 	/// Only for ABI handling
180 	/// Args: int that is added to stack pointer
181 	@_ii(1, IFLG.hasSideEffects) shrink_stack,
182 	/// Only for ABI handling
183 	/// Args: int that is substracted from stack pointer
184 	@_ii(1, IFLG.hasSideEffects) grow_stack,
185 	/// Only for ABI handling
186 	/// Args: iNN
187 	@_ii(1, IFLG.hasSideEffects) push,
188 
189 	/// Args: T*, T
190 	@_ii(2, IFLG.hasSideEffects) store,
191 	/// Args: T*
192 	/// Returns: T
193 	@_ii(1, IFLG.hasResult) load,
194 	/// Args: aggregate pointer
195 	/// Returns: member pointer
196 	@_ii(1, IFLG.hasResult) load_aggregate, // TODO: remove. Use load instead
197 	@_ii(2, IFLG.hasVariadicArgs | IFLG.hasResult) get_element_ptr,
198 	/// Args: aggregate pointer, 1 or more index
199 	/// Returns: member pointer
200 	/// Same as get_element_ptr, but first index is hardcoded to be 0.
201 	/// 0 indixies do not make sense, because then instuction is no op and can replaced with first arg
202 	/// Indices are compatible with ones from get_element and insert_element
203 	@_ii(2, IFLG.hasVariadicArgs | IFLG.hasResult) get_element_ptr_0,
204 	/// Args: aggregate members
205 	@_ii(1, IFLG.hasVariadicArgs | IFLG.hasResult) create_aggregate,
206 	/// Args: aggregate, byte offset
207 	/// Returns: member of aggregate at given offset
208 	/// For now offset must be a constant
209 	@_ii(2, IFLG.hasVariadicArgs | IFLG.hasResult) get_element,
210 	/// Gets a register sized slice of aggregate
211 	/// Args: aggregate, 1 index of 8byte chunk
212 	@_ii(2, IFLG.hasResult) get_aggregate_slice,
213 	/// Args: aggregate, byte offset, new element value
214 	/// Returns: aggregate with replaced element
215 	/// Restriction: original aggregate's member that is being replaced here, must not
216 	/// be read from in postdominating instructions. But it can be read on other control flow paths.
217 	/// In other words, after this instruction got executed, original aggregate can not be read. All reads
218 	/// must go through result of this instruction.
219 	@_ii(3, IFLG.hasVariadicArgs | IFLG.hasResult) insert_element,
220 
221 	/// One's complement negation
222 	/// Args: iNN a
223 	/// Returns ~a
224 	@_ii(1, IFLG.hasResult) not,
225 	/// Two's complement negation
226 	/// Args: iNN a
227 	/// Returns -a
228 	@_ii(1, IFLG.hasResult) neg,
229 	/// Float negation
230 	/// Args: fNN a
231 	/// Returns -a
232 	@_ii(1, IFLG.hasResult) fneg,
233 
234 	/// Args: source value, target size is represented with argSize field
235 	/// Currently is used as bitcast. Need clearer semantics
236 	@_ii(1, IFLG.hasResult) conv,
237 	/// Args: iNN a, argSize sets MM. MM must be > NN
238 	/// Returns iMM
239 	@_ii(1, IFLG.hasResult) zext,
240 	/// Args: iNN a, argSize sets MM. MM must be > NN
241 	/// Returns iMM
242 	@_ii(1, IFLG.hasResult) sext,
243 	/// Args: iNN a, argSize sets MM. MM must be < NN
244 	/// Returns iMM
245 	@_ii(1, IFLG.hasResult) trunc,
246 
247 	/// Args: fNN a, argSize sets MM. MM must be < NN
248 	/// Returns fMM
249 	@_ii(1, IFLG.hasResult) fptrunc,
250 	/// Args: fNN a, argSize sets MM. MM must be > NN
251 	/// Returns fMM
252 	@_ii(1, IFLG.hasResult) fpext,
253 	/// Args: fNN a, argSize sets MM
254 	/// Returns iMM
255 	@_ii(1, IFLG.hasResult) fptoui,
256 	/// Args: fNN a, argSize sets MM
257 	/// Returns iMM
258 	@_ii(1, IFLG.hasResult) fptosi,
259 	/// Args: iNN a, argSize sets MM
260 	/// Returns fMM
261 	@_ii(1, IFLG.hasResult) uitofp,
262 	/// Args: iNN a, argSize sets MM
263 	/// Returns fMM
264 	@_ii(1, IFLG.hasResult) sitofp,
265 
266 	/// Used when generating any of binary instructions.
267 	/// Actual opcode is passed via ExtraInstrArgs.opcode
268 	@_ii(2, IFLG.hasResult | IFLG.isGeneric) generic_binary,
269 	@_ii(2, IFLG.hasResult) add,
270 	@_ii(2, IFLG.hasResult) sub,
271 	@_ii(2, IFLG.hasResult) and,
272 	@_ii(2, IFLG.hasResult) or,
273 	@_ii(2, IFLG.hasResult) xor,
274 
275 	/// Unsigned multiply
276 	@_ii(2, IFLG.hasResult) umul,
277 	/// Signed multiply
278 	@_ii(2, IFLG.hasResult) smul,
279 	/// Unsigned division
280 	@_ii(2, IFLG.hasResult) udiv,
281 	/// Signed division
282 	@_ii(2, IFLG.hasResult) sdiv,
283 	/// Unsigned remainder
284 	@_ii(2, IFLG.hasResult) urem,
285 	/// Signed remainder
286 	@_ii(2, IFLG.hasResult) srem,
287 
288 	@_ii(2, IFLG.hasResult) shl,
289 	@_ii(2, IFLG.hasResult) lshr,
290 	@_ii(2, IFLG.hasResult) ashr,
291 
292 	@_ii(2, IFLG.hasResult) fadd,
293 	@_ii(2, IFLG.hasResult) fsub,
294 	@_ii(2, IFLG.hasResult) fmul,
295 	@_ii(2, IFLG.hasResult) fdiv,
296 
297 	@_ii(0) noop,
298 }
299 
300 enum IrArgSize : ubyte {
301 	size8,
302 	size16,
303 	size32,
304 	size64,
305 	size128,
306 	size256,
307 	size512,
308 }
309 
310 IrArgSize sizeToIrArgSize(uint typeSize, CompilationContext* context) {
311 	switch (typeSize) {
312 		case 1: return IrArgSize.size8;
313 		case 2: return IrArgSize.size16;
314 		case 4: return IrArgSize.size32;
315 		case 8: return IrArgSize.size64;
316 		case 16: return IrArgSize.size128;
317 		case 32: return IrArgSize.size256;
318 		case 64: return IrArgSize.size512;
319 		default:
320 			context.internal_error("Type of size %s cannot be stored in a register", typeSize);
321 	}
322 }
323 
324 IrIndex sizeToIntType(uint typeSize, CompilationContext* context) {
325 	switch (typeSize) {
326 		case 1: return makeIrType(IrBasicType.i8);
327 		case 2: return makeIrType(IrBasicType.i16);
328 		case 4: return makeIrType(IrBasicType.i32);
329 		case 8: return makeIrType(IrBasicType.i64);
330 		default: context.internal_error("Unhandled size %s", typeSize);
331 	}
332 }
333 
334 IrArgSize typeToIrArgSize(IrIndex type, CompilationContext* context) {
335 	uint typeSize = context.types.typeSize(type);
336 	return sizeToIrArgSize(typeSize, context);
337 }
338 
339 /// Common prefix of all IR instruction structs
340 @(IrValueKind.instruction)
341 struct IrInstrHeader
342 {
343 	ushort op;
344 	ubyte numArgs;
345 
346 	enum MAX_ARGS = 255;
347 
348 	union {
349 		mixin(bitfields!(
350 			// Always used
351 			bool,       "hasResult", 1,
352 			// Only used when IrInstrFlags.hasCondition is set
353 			ubyte,      "cond",      4,
354 			// Not always possible to infer arg size from arguments (like in store ptr, imm)
355 			IrArgSize,  "argSize",   3,
356 		));
357 
358 		// for calls
359 		mixin(bitfields!(
360 			uint, "",                       1, // hasResult
361 			// marks instruction that has non-mov instruction between argument movs and itself
362 			bool, "extendFixedArgRange",    1,
363 			// marks instruction that has non-mov instruction between result movs and itself
364 			bool, "extendFixedResultRange", 1,
365 			// Used on call instruction
366 			bool, "alwaysInline",           1,
367 			uint, "",                       4,
368 		));
369 
370 		// for loads
371 		mixin(bitfields!(
372 			uint, "",                       1, // hasResult
373 			// Only used for loads to mark source pointer as uniqely owned by load
374 			bool, "isUniqueLoad",           1,
375 			uint, "",                       6,
376 		));
377 	}
378 
379 	static assert(IrBinaryCondition.max <= 0b1111, "4 bits are reserved");
380 	static assert(IrUnaryCondition.max <= 0b1111, "4 bits are reserved");
381 
382 	// points to first argument (result is immediately before first arg)
383 	uint _payloadOffset;
384 
385 	// points to basic block if first instruction of basic block
386 	IrIndex prevInstr(IrFunction* ir, IrIndex instrIndex) {
387 		return ir.instrPrevPtr[instrIndex.storageUintIndex];
388 	}
389 	// points to basic block if last instruction of basic block
390 	IrIndex nextInstr(IrFunction* ir, IrIndex instrIndex) {
391 		return ir.instrNextPtr[instrIndex.storageUintIndex];
392 	}
393 
394 	ref IrIndex result(IrFunction* ir) {
395 		assert(hasResult, "No result");
396 		return ir.instrPayloadPtr[_payloadOffset-1];
397 	}
398 
399 	// returns result or undefined
400 	IrIndex tryGetResult(IrFunction* ir) {
401 		if (hasResult) return ir.instrPayloadPtr[_payloadOffset-1];
402 		return IrIndex();
403 	}
404 
405 	IrIndex[] args(IrFunction* ir) {
406 		return ir.instrPayloadPtr[_payloadOffset.._payloadOffset + numArgs];
407 	}
408 
409 	ref IrIndex arg(IrFunction* ir, uint index) {
410 		assert(index < numArgs, "arg index out of bounds");
411 		return ir.instrPayloadPtr[_payloadOffset + index];
412 	}
413 
414 	IrIndex[] extraPayload(IrFunction* ir, uint numSlots) {
415 		uint start = _payloadOffset + numArgs;
416 		return ir.instrPayloadPtr[start..start+numSlots];
417 	}
418 }
419 
420 
421 enum IrBinaryCondition : ubyte {
422 	eq,
423 	ne,
424 
425 	ugt,
426 	uge,
427 	ult,
428 	ule,
429 
430 	sgt,
431 	sge,
432 	slt,
433 	sle,
434 
435 	fgt,
436 	fge,
437 	flt,
438 	fle,
439 }
440 
441 string[] binaryCondStrings = cast(string[IrBinaryCondition.max+1])["==", "!=", "u>", "u>=", "u<", "u<=", "s>", "s>=", "s<", "s<=", "f>", "f>=", "f<", "f<="];
442 string[] binaryCondStringsEscapedForDot = cast(string[IrBinaryCondition.max+1])[`==`, `!=`, `u\>`, `u\>=`, `u\<`, `u\<=`, `s\>`, `s\>=`, `s\<`, `s\<=`, `f\>`, `f\>=`, `f\<`, `f\<=`];
443 
444 bool evalBinCondition(ref CompilationContext context, IrBinaryCondition cond, IrIndex conLeft, IrIndex conRight)
445 {
446 	IrConstant left = context.constants.get(conLeft);
447 	IrConstant right = context.constants.get(conRight);
448 	final switch(cond) with(IrBinaryCondition)
449 	{
450 		case eq: return left.i64 == right.i64;
451 		case ne: return left.i64 != right.i64;
452 
453 		case ugt: return left.u64 >  right.u64;
454 		case uge: return left.u64 >= right.u64;
455 		case ult: return left.u64 <  right.u64;
456 		case ule: return left.u64 <= right.u64;
457 
458 		case sgt: return left.i64 >  right.i64;
459 		case sge: return left.i64 >= right.i64;
460 		case slt: return left.i64 <  right.i64;
461 		case sle: return left.i64 <= right.i64;
462 
463 		case fgt: if (left.type == makeIrType(IrBasicType.f64)) return left.f64 >  right.f64; return left.f32 >  right.f32;
464 		case fge: if (left.type == makeIrType(IrBasicType.f64)) return left.f64 >= right.f64; return left.f32 >= right.f32;
465 		case flt: if (left.type == makeIrType(IrBasicType.f64)) return left.f64 <  right.f64; return left.f32 <  right.f32;
466 		case fle: if (left.type == makeIrType(IrBasicType.f64)) return left.f64 <= right.f64; return left.f32 <= right.f32;
467 	}
468 }
469 
470 IrBinaryCondition invertBinaryCond(IrBinaryCondition cond)
471 {
472 	final switch(cond) with(IrBinaryCondition)
473 	{
474 		case eq: return ne;
475 		case ne: return eq;
476 
477 		case ugt: return ule;
478 		case uge: return ult;
479 		case ult: return uge;
480 		case ule: return ugt;
481 
482 		case sgt: return sle;
483 		case sge: return slt;
484 		case slt: return sge;
485 		case sle: return sgt;
486 
487 		case fgt: return fle;
488 		case fge: return flt;
489 		case flt: return fge;
490 		case fle: return fgt;
491 	}
492 }
493 
494 enum IrUnaryCondition : ubyte {
495 	zero,
496 	not_zero
497 }
498 string[] unaryCondStrings = cast(string[IrUnaryCondition.max+1])[" not", ""];
499 
500 IrUnaryCondition invertUnaryCond(IrUnaryCondition cond)
501 {
502 	final switch(cond) with(IrUnaryCondition)
503 	{
504 		case zero: return not_zero;
505 		case not_zero: return zero;
506 	}
507 }
508 
509 @(IrValueKind.instruction)
510 struct IrInstr_parameter
511 {
512 	IrInstrHeader header;
513 	ref uint index(IrFunction* ir) {
514 		return header.extraPayload(ir, 1)[0].asUint;
515 	}
516 }