blob b3be08e8 (17212B) - Raw
1 //! Machine Intermediate Representation. 2 //! This data is produced by x86_64 Codegen and consumed by x86_64 Isel. 3 //! These instructions have a 1:1 correspondence with machine code instructions 4 //! for the target. MIR can be lowered to source-annotated textual assembly code 5 //! instructions, or it can be lowered to machine code. 6 //! The main purpose of MIR is to postpone the assignment of offsets until Isel, 7 //! so that, for example, the smaller encodings of jump instructions can be used. 8 9 const Mir = @This(); 10 const std = @import("std"); 11 const builtin = @import("builtin"); 12 const assert = std.debug.assert; 13 14 const bits = @import("bits.zig"); 15 const Air = @import("../../Air.zig"); 16 const CodeGen = @import("CodeGen.zig"); 17 const IntegerBitSet = std.bit_set.IntegerBitSet; 18 const Register = bits.Register; 19 20 instructions: std.MultiArrayList(Inst).Slice, 21 /// The meaning of this data is determined by `Inst.Tag` value. 22 extra: []const u32, 23 24 pub const Inst = struct { 25 tag: Tag, 26 ops: Ops, 27 /// The meaning of this depends on `tag` and `ops`. 28 data: Data, 29 30 pub const Tag = enum(u16) { 31 /// ops flags: form: 32 /// 0b00 reg1, reg2 33 /// 0b00 reg1, imm32 34 /// 0b01 reg1, [reg2 + imm32] 35 /// 0b01 reg1, [ds:imm32] 36 /// 0b10 [reg1 + imm32], reg2 37 /// Notes: 38 /// * If reg2 is `none` then it means Data field `imm` is used as the immediate. 39 /// * When two imm32 values are required, Data field `payload` points at `ImmPair`. 40 adc, 41 42 /// ops flags: form: 43 /// 0b00 byte ptr [reg1 + imm32], imm8 44 /// 0b01 word ptr [reg1 + imm32], imm16 45 /// 0b10 dword ptr [reg1 + imm32], imm32 46 /// 0b11 qword ptr [reg1 + imm32], imm32 (sign-extended to imm64) 47 /// Notes: 48 /// * Uses `ImmPair` as payload 49 adc_mem_imm, 50 51 /// form: reg1, [reg2 + scale*index + imm32] 52 /// ops flags scale 53 /// 0b00 1 54 /// 0b01 2 55 /// 0b10 4 56 /// 0b11 8 57 /// Notes: 58 /// * Uses `IndexRegisterDisp` as payload 59 adc_scale_src, 60 61 /// form: [reg1 + scale*index + imm32], reg2 62 /// ops flags scale 63 /// 0b00 1 64 /// 0b01 2 65 /// 0b10 4 66 /// 0b11 8 67 /// Notes: 68 /// * Uses `IndexRegisterDisp` payload. 69 adc_scale_dst, 70 71 /// form: [reg1 + scale*rax + imm32], imm32 72 /// ops flags scale 73 /// 0b00 1 74 /// 0b01 2 75 /// 0b10 4 76 /// 0b11 8 77 /// Notes: 78 /// * Uses `IndexRegisterDispImm` payload. 79 adc_scale_imm, 80 81 /// ops flags: form: 82 /// 0b00 byte ptr [reg1 + index + imm32], imm8 83 /// 0b01 word ptr [reg1 + index + imm32], imm16 84 /// 0b10 dword ptr [reg1 + index + imm32], imm32 85 /// 0b11 qword ptr [reg1 + index + imm32], imm32 (sign-extended to imm64) 86 /// Notes: 87 /// * Uses `IndexRegisterDispImm` payload. 88 adc_mem_index_imm, 89 90 // The following instructions all have the same encoding as `adc`. 91 92 add, 93 add_mem_imm, 94 add_scale_src, 95 add_scale_dst, 96 add_scale_imm, 97 add_mem_index_imm, 98 sub, 99 sub_mem_imm, 100 sub_scale_src, 101 sub_scale_dst, 102 sub_scale_imm, 103 sub_mem_index_imm, 104 xor, 105 xor_mem_imm, 106 xor_scale_src, 107 xor_scale_dst, 108 xor_scale_imm, 109 xor_mem_index_imm, 110 @"and", 111 and_mem_imm, 112 and_scale_src, 113 and_scale_dst, 114 and_scale_imm, 115 and_mem_index_imm, 116 @"or", 117 or_mem_imm, 118 or_scale_src, 119 or_scale_dst, 120 or_scale_imm, 121 or_mem_index_imm, 122 rol, 123 rol_mem_imm, 124 rol_scale_src, 125 rol_scale_dst, 126 rol_scale_imm, 127 rol_mem_index_imm, 128 ror, 129 ror_mem_imm, 130 ror_scale_src, 131 ror_scale_dst, 132 ror_scale_imm, 133 ror_mem_index_imm, 134 rcl, 135 rcl_mem_imm, 136 rcl_scale_src, 137 rcl_scale_dst, 138 rcl_scale_imm, 139 rcl_mem_index_imm, 140 rcr, 141 rcr_mem_imm, 142 rcr_scale_src, 143 rcr_scale_dst, 144 rcr_scale_imm, 145 rcr_mem_index_imm, 146 sbb, 147 sbb_mem_imm, 148 sbb_scale_src, 149 sbb_scale_dst, 150 sbb_scale_imm, 151 sbb_mem_index_imm, 152 cmp, 153 cmp_mem_imm, 154 cmp_scale_src, 155 cmp_scale_dst, 156 cmp_scale_imm, 157 cmp_mem_index_imm, 158 mov, 159 mov_mem_imm, 160 mov_scale_src, 161 mov_scale_dst, 162 mov_scale_imm, 163 mov_mem_index_imm, 164 165 /// ops flags: form: 166 /// 0b00 reg1, reg2, 167 /// 0b01 reg1, byte ptr [reg2 + imm32] 168 /// 0b10 reg1, word ptr [reg2 + imm32] 169 /// 0b11 reg1, dword ptr [reg2 + imm32] 170 mov_sign_extend, 171 172 /// ops flags: form: 173 /// 0b00 reg1, reg2 174 /// 0b01 reg1, byte ptr [reg2 + imm32] 175 /// 0b10 reg1, word ptr [reg2 + imm32] 176 mov_zero_extend, 177 178 /// ops flags: form: 179 /// 0b00 reg1, [reg2 + imm32] 180 /// 0b00 reg1, [ds:imm32] 181 /// 0b01 reg1, [rip + imm32] 182 /// 0b10 reg1, [reg2 + index + imm32] 183 /// Notes: 184 /// * 0b10 uses `IndexRegisterDisp` payload 185 lea, 186 187 /// ops flags: form: 188 /// 0b00 reg1, [rip + reloc] // via GOT PIC 189 /// 0b01 reg1, [rip + reloc] // direct load PIC 190 /// 0b10 reg1, [rip + reloc] // via imports table PIC 191 /// Notes: 192 /// * `Data` contains `relocation` 193 lea_pic, 194 195 /// ops flags: form: 196 /// 0b00 reg1, 1 197 /// 0b01 reg1, .cl 198 /// 0b10 reg1, imm8 199 /// Notes: 200 /// * If flags == 0b10, uses `imm`. 201 shl, 202 shl_mem_imm, 203 shl_scale_src, 204 shl_scale_dst, 205 shl_scale_imm, 206 shl_mem_index_imm, 207 sal, 208 sal_mem_imm, 209 sal_scale_src, 210 sal_scale_dst, 211 sal_scale_imm, 212 sal_mem_index_imm, 213 shr, 214 shr_mem_imm, 215 shr_scale_src, 216 shr_scale_dst, 217 shr_scale_imm, 218 shr_mem_index_imm, 219 sar, 220 sar_mem_imm, 221 sar_scale_src, 222 sar_scale_dst, 223 sar_scale_imm, 224 sar_mem_index_imm, 225 226 /// ops flags: form: 227 /// 0b00 reg1 228 /// 0b00 byte ptr [reg2 + imm32] 229 /// 0b01 word ptr [reg2 + imm32] 230 /// 0b10 dword ptr [reg2 + imm32] 231 /// 0b11 qword ptr [reg2 + imm32] 232 imul, 233 idiv, 234 mul, 235 div, 236 237 /// ops flags: form: 238 /// 0b00 AX <- AL 239 /// 0b01 DX:AX <- AX 240 /// 0b10 EDX:EAX <- EAX 241 /// 0b11 RDX:RAX <- RAX 242 cwd, 243 244 /// ops flags: form: 245 /// 0b00 reg1, reg2 246 /// 0b01 reg1, [reg2 + imm32] 247 /// 0b01 reg1, [imm32] if reg2 is none 248 /// 0b10 reg1, reg2, imm32 249 /// 0b11 reg1, [reg2 + imm32], imm32 250 imul_complex, 251 252 /// ops flags: form: 253 /// 0b00 reg1, imm64 254 /// 0b01 rax, moffs64 255 /// Notes: 256 /// * If reg1 is 64-bit, the immediate is 64-bit and stored 257 /// within extra data `Imm64`. 258 /// * For 0b01, reg1 (or reg2) need to be 259 /// a version of rax. If reg1 == .none, then reg2 == .rax, 260 /// or vice versa. 261 movabs, 262 263 /// ops flags: form: 264 /// 0b00 word ptr [reg1 + imm32] 265 /// 0b01 dword ptr [reg1 + imm32] 266 /// 0b10 qword ptr [reg1 + imm32] 267 /// Notes: 268 /// * source is always ST(0) 269 /// * only supports memory operands as destination 270 fisttp, 271 272 /// ops flags: form: 273 /// 0b01 dword ptr [reg1 + imm32] 274 /// 0b10 qword ptr [reg1 + imm32] 275 fld, 276 277 /// ops flags: form: 278 /// 0b00 inst 279 /// 0b01 reg1 280 /// 0b01 [imm32] if reg1 is none 281 /// 0b10 [reg1 + imm32] 282 jmp, 283 call, 284 285 /// ops flags: 286 /// unused 287 /// Notes: 288 /// * uses `inst_cc` in Data. 289 cond_jmp, 290 291 /// ops flags: 292 /// 0b00 reg1 293 /// Notes: 294 /// * uses condition code (CC) stored as part of data 295 cond_set_byte, 296 297 /// ops flags: 298 /// 0b00 reg1, reg2, 299 /// 0b01 reg1, word ptr [reg2 + imm] 300 /// 0b10 reg1, dword ptr [reg2 + imm] 301 /// 0b11 reg1, qword ptr [reg2 + imm] 302 /// Notes: 303 /// * uses condition code (CC) stored as part of data 304 cond_mov, 305 306 /// ops flags: form: 307 /// 0b00 reg1 308 /// 0b01 [reg1 + imm32] 309 /// 0b10 imm32 310 /// Notes: 311 /// * If 0b10 is specified and the tag is push, pushes immediate onto the stack 312 /// using the mnemonic PUSH imm32. 313 push, 314 pop, 315 316 /// ops flags: form: 317 /// 0b00 retf imm16 318 /// 0b01 retf 319 /// 0b10 retn imm16 320 /// 0b11 retn 321 ret, 322 323 /// Fast system call 324 syscall, 325 326 /// ops flags: form: 327 /// 0b00 reg1, imm32 if reg2 == .none 328 /// 0b00 reg1, reg2 329 /// TODO handle more cases 330 @"test", 331 332 /// Undefined Instruction 333 ud, 334 335 /// Breakpoint form: 336 /// 0b00 int3 337 interrupt, 338 339 /// Nop 340 nop, 341 342 /// SSE/AVX instructions 343 /// ops flags: form: 344 /// 0b00 reg1, qword ptr [reg2 + imm32] 345 /// 0b01 qword ptr [reg1 + imm32], reg2 346 /// 0b10 reg1, reg2 347 mov_f64, 348 mov_f32, 349 350 /// ops flags: form: 351 /// 0b00 reg1, reg2 352 add_f64, 353 add_f32, 354 355 /// ops flags: form: 356 /// 0b00 reg1, reg2 357 cmp_f64, 358 cmp_f32, 359 360 /// Pseudo-instructions 361 /// call extern function 362 /// Notes: 363 /// * target of the call is stored as `relocation` in `Data` union. 364 call_extern, 365 366 /// end of prologue 367 dbg_prologue_end, 368 369 /// start of epilogue 370 dbg_epilogue_begin, 371 372 /// update debug line 373 dbg_line, 374 375 /// push registers 376 /// Uses `payload` field with `SaveRegisterList` as payload. 377 push_regs, 378 379 /// pop registers 380 /// Uses `payload` field with `SaveRegisterList` as payload. 381 pop_regs, 382 }; 383 /// The position of an MIR instruction within the `Mir` instructions array. 384 pub const Index = u32; 385 386 pub const Ops = packed struct { 387 reg1: u7, 388 reg2: u7, 389 flags: u2, 390 391 pub fn encode(vals: struct { 392 reg1: Register = .none, 393 reg2: Register = .none, 394 flags: u2 = 0b00, 395 }) Ops { 396 return .{ 397 .reg1 = @enumToInt(vals.reg1), 398 .reg2 = @enumToInt(vals.reg2), 399 .flags = vals.flags, 400 }; 401 } 402 403 pub fn decode(ops: Ops) struct { 404 reg1: Register, 405 reg2: Register, 406 flags: u2, 407 } { 408 return .{ 409 .reg1 = @intToEnum(Register, ops.reg1), 410 .reg2 = @intToEnum(Register, ops.reg2), 411 .flags = ops.flags, 412 }; 413 } 414 }; 415 416 /// All instructions have a 4-byte payload, which is contained within 417 /// this union. `Tag` determines which union field is active, as well as 418 /// how to interpret the data within. 419 pub const Data = union { 420 /// Another instruction. 421 inst: Index, 422 /// A 32-bit immediate value. 423 imm: u32, 424 /// A 32-bit signed displacement value. 425 disp: i32, 426 /// A condition code for use with EFLAGS register. 427 cc: bits.Condition, 428 /// Another instruction with condition code. 429 /// Used by `cond_jmp`. 430 inst_cc: struct { 431 /// Another instruction. 432 inst: Index, 433 /// A condition code for use with EFLAGS register. 434 cc: bits.Condition, 435 }, 436 /// Relocation for the linker where: 437 /// * `atom_index` is the index of the source 438 /// * `sym_index` is the index of the target 439 relocation: struct { 440 /// Index of the containing atom. 441 atom_index: u32, 442 /// Index into the linker's symbol table. 443 sym_index: u32, 444 }, 445 /// Index into `extra`. Meaning of what can be found there is context-dependent. 446 payload: u32, 447 }; 448 449 // Make sure we don't accidentally make instructions bigger than expected. 450 // Note that in Debug builds, Zig is allowed to insert a secret field for safety checks. 451 comptime { 452 if (builtin.mode != .Debug and builtin.mode != .ReleaseSafe) { 453 assert(@sizeOf(Data) == 8); 454 } 455 } 456 }; 457 458 pub const IndexRegisterDisp = struct { 459 /// Index register to use with SIB-based encoding 460 index: u32, 461 462 /// Displacement value 463 disp: i32, 464 465 pub fn encode(index: Register, disp: i32) IndexRegisterDisp { 466 return .{ 467 .index = @enumToInt(index), 468 .disp = disp, 469 }; 470 } 471 472 pub fn decode(this: IndexRegisterDisp) struct { 473 index: Register, 474 disp: i32, 475 } { 476 return .{ 477 .index = @intToEnum(Register, this.index), 478 .disp = this.disp, 479 }; 480 } 481 }; 482 483 /// TODO: would it be worth making `IndexRegisterDisp` and `IndexRegisterDispImm` a variable length list 484 /// instead of having two structs, one a superset of the other one? 485 pub const IndexRegisterDispImm = struct { 486 /// Index register to use with SIB-based encoding 487 index: u32, 488 489 /// Displacement value 490 disp: i32, 491 492 /// Immediate 493 imm: u32, 494 495 pub fn encode(index: Register, disp: i32, imm: u32) IndexRegisterDispImm { 496 return .{ 497 .index = @enumToInt(index), 498 .disp = disp, 499 .imm = imm, 500 }; 501 } 502 503 pub fn decode(this: IndexRegisterDispImm) struct { 504 index: Register, 505 disp: i32, 506 imm: u32, 507 } { 508 return .{ 509 .index = @intToEnum(Register, this.index), 510 .disp = this.disp, 511 .imm = this.imm, 512 }; 513 } 514 }; 515 516 /// Used in conjunction with `SaveRegisterList` payload to transfer a list of used registers 517 /// in a compact manner. 518 pub const RegisterList = struct { 519 bitset: BitSet = BitSet.initEmpty(), 520 521 const BitSet = IntegerBitSet(@ctz(@as(u32, 0))); 522 const Self = @This(); 523 524 fn getIndexForReg(registers: []const Register, reg: Register) BitSet.MaskInt { 525 for (registers, 0..) |cpreg, i| { 526 if (reg.id() == cpreg.id()) return @intCast(u32, i); 527 } 528 unreachable; // register not in input register list! 529 } 530 531 pub fn push(self: *Self, registers: []const Register, reg: Register) void { 532 const index = getIndexForReg(registers, reg); 533 self.bitset.set(index); 534 } 535 536 pub fn isSet(self: Self, registers: []const Register, reg: Register) bool { 537 const index = getIndexForReg(registers, reg); 538 return self.bitset.isSet(index); 539 } 540 541 pub fn asInt(self: Self) u32 { 542 return self.bitset.mask; 543 } 544 545 pub fn fromInt(mask: u32) Self { 546 return .{ 547 .bitset = BitSet{ .mask = @intCast(BitSet.MaskInt, mask) }, 548 }; 549 } 550 551 pub fn count(self: Self) u32 { 552 return @intCast(u32, self.bitset.count()); 553 } 554 }; 555 556 pub const SaveRegisterList = struct { 557 /// Use `RegisterList` to populate. 558 register_list: u32, 559 stack_end: u32, 560 }; 561 562 pub const ImmPair = struct { 563 dest_off: i32, 564 operand: u32, 565 }; 566 567 pub const Imm64 = struct { 568 msb: u32, 569 lsb: u32, 570 571 pub fn encode(v: u64) Imm64 { 572 return .{ 573 .msb = @truncate(u32, v >> 32), 574 .lsb = @truncate(u32, v), 575 }; 576 } 577 578 pub fn decode(imm: Imm64) u64 { 579 var res: u64 = 0; 580 res |= (@intCast(u64, imm.msb) << 32); 581 res |= @intCast(u64, imm.lsb); 582 return res; 583 } 584 }; 585 586 pub const DbgLineColumn = struct { 587 line: u32, 588 column: u32, 589 }; 590 591 pub fn deinit(mir: *Mir, gpa: std.mem.Allocator) void { 592 mir.instructions.deinit(gpa); 593 gpa.free(mir.extra); 594 mir.* = undefined; 595 } 596 597 pub fn extraData(mir: Mir, comptime T: type, index: usize) struct { data: T, end: usize } { 598 const fields = std.meta.fields(T); 599 var i: usize = index; 600 var result: T = undefined; 601 inline for (fields) |field| { 602 @field(result, field.name) = switch (field.type) { 603 u32 => mir.extra[i], 604 i32 => @bitCast(i32, mir.extra[i]), 605 else => @compileError("bad field type"), 606 }; 607 i += 1; 608 } 609 return .{ 610 .data = result, 611 .end = i, 612 }; 613 }