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 }