Lecture 3 COMPILER DESIGN

Lecture 3COMPILER DESIGNZhendong Su Compiler Design1

Announcements HW1: Hellocaml– Due Thursday, 1 Oct. at 23:59 HW2: X86lite– Will be available next week on our course Moodle– Simulator / Loader for x86 assembly subsetZhendong Su Compiler Design2

(Simplified) Compiler StructureSource Code(Character stream)if (b 0) a 0;Lexical AnalysisToken StreamParsingFront End(machine independent)Abstract Syntax TreeIntermediate CodeGenerationMiddle End(compiler dependent)Intermediate CodeCode GenerationAssembly CodeBack End(machine dependent)CMP ECX, 0SETBZ EAXZhendong Su Compiler Design3

Back EndCompilerIntermediateRepresentationZhendong Su Compiler DesignAssembly Code4

Multiple Back EndsX86 (IA-32)X86 64Code inIntermediateRepresentationARMv7ISAsARMv8 Zhendong Su Compiler Design5

Instruction Set ong Su Compiler DesignHardwareInstruction Semantics?Datatypes?Addressing Modes? ?6

The target architectureX86LITEZhendong Su Compiler Design7

x861978time20198086 (1978)80186, 802868038680486 (100MHz, 1µm)PentiumPentium ProPentium II/IIIPentium 4Intel Core 2Intel Core ake/KabyLakeCannonlake/IceLakex86-16x86-32 Binary Compatibility (old code runs on newhardware) Complex ISA (1500 instructions) Multiple extensionsx86-64 Non-Intel implementations (e.g., AMD, Via)Visualization adapted from an Advanced Systems Lab lectureZhendong Su Compiler Design8

X86 vs. X86liteX86 assembly is very complicated!X86lite is a very simple subset of X86 8-, 16-, 32-, 64-bit values floating point, etc. Intel 64 and IA 32 architectures have a hugenumber of functions“CISC” complex instructions Only 64-bit signed integers (nofloating point, no 16-bit, no ) Machine code: instructions range in size from1 byte to 17 bytes Lots of hold-over design decisions forbackward compatibility Hard to understand, there is a large bookabout optimizations at just the instructionselection level1 Only about 20 instructions Sufficient as a target language forgeneral-purpose computingZhendong Su Compiler Design 1Intel 64 and IA-32 Architectures Software Developer’s Manual9

X86 SchematicProcessorMemoryRIP0x00000000Code &DataHeapOFSFControlALUZFLarger RpbRsbr08r09r10r11r12r13r14r15RegistersZhendong Su Compiler DesignStack0xffffffff10

Simplest instruction: movInitialState movq SRC, DEST Here, DEST and SRC are operandsrax rbx00movq 42, %rax– A location can be a register or a memoryaddressrax rbx420movq %rax, %rbxrax rbx42Zhendong Su Compiler Design DEST is treated as a location42 SRC is treated as a value– A value is the contents of a register ormemory address– A value can also be an immediate(constant) or a label11

A Note About Instruction SyntaxAT&T notation: source beforedestinationIntel notation: destination beforesource Prevalent in the Unix ecosystems Used in the Intel specification / manuals Immediate values prefixed with ‘ ’ Registers prefixed with ‘%’PrevalentNote: X86lite uses the AT&Tnotation in the Windows ecosystemand the 64-bit only version of theinstructions and registers Mnemonic suffixes: movq vs. mov– q quadword (4 words)– l long (2 words)movq 5, %rax– w word (16-bit)– b byte (8-bit)movl 5, %eaxZhendong Su Compiler Design Instruction variant determined by registernamemov rax, 5mov eax, 512

X86 OperandsTypeDescriptionExampleImm64-bit literal signed integer “immediate”movq 4, %raxLbla “label” representing a machine address, theassembler/linker/loader resolves labelscallq FOORegOne of the 16 registers, the value of a register is its contents movq %rbx, %raxIndmachine address:[base:Reg][index:Reg][disp:int32] (base index*8 disp)Zhendong Su Compiler Designmovq 12(%rax, %rcx), %rbx13

Arithmetic instructionsInstructionDescriptionExamplenegq DEST2’s complement negationnegq %raxaddq SRC, DESTDEST DEST SRCaddq %rbx, %raxsubq SRC, DESTDEST DEST – SRCsubq 4, %rspimulq SRC, RegReg Reg * SRC(truncated 128-bit mult.)imulq 2, %raxNotesReg must be a register, nota memory addressmovq 2, %raxmovq 3, %rbximulq %rbx, %rax// rax 6, rbx 3Zhendong Su Compiler Design14

Logic/Bit Manipulation instructionsInstructionExplanationExampleNotesnotq DESTlogical negationnotq %raxbitwise notandq SRC, DESTDEST DEST & SRCandq %rbx, %raxbitwise andorq SRC, DESTDEST DEST SRCorq 4, %rspbitwise orxorq SRC, DESTDEST DEST xor SRCxorq 2, %raxbitwise xorInstructionExplanationExampleNotessarq Amt, DESTDEST DEST Amtsarq 4, %raxarithmetic shift rightshlq Amt, DESTDEST DEST Amtshlq %rbx, %raxlogical shift leftshrq Amt, DESTDEST DEST Amtshrq 1, %rsplogical shift rightZhendong Su Compiler Design15

X86lite State: Condition Flags & CodesSome X86 instructions set flags asside effects OF: “overflow” set when the resultis too big/small to fit in 64-bit reg. SF: “sign” set to the sign of theresult (0 positive, 1 negative) ZF: “zero” set when the result is 0CodeConditione (equality)ZF is setne (inequality)(not ZF)g (greater than)(not ZF) and (SF OF)l (less than)SF OFge (greater or equal)(SF OF)le (less than or equal) SF OF or ZFFrom these flags, we can defineCondition CodesTo compare SRC1 and SRC2,compute SRC1 – SRC2 to set theflagsZhendong Su Compiler DesignExamplesmovq INTMAX, %raxsubq 1,%rax//rax INTMAX-1//OF 0, SF 0, ZF 0movq INTMIN, %raxsubq -1,%rax//rax INTMIN 1//OF 0, SF 1, ZF 0movq INTMAX, %raxsubq -1,%rax//rax INTMIN (neg)//OF 1, SF 1, ZF 0movq INTMIN, %raxsubq 1,%rax//rax INTMAX//OF 1, SF 0, ZF 016

Conditional Instructionsif (a b){//something} else ncmpq SRC2, SRC1Compute SRC1 – SRC2,set condition flagssetbCC DESTDEST’s lower byte if CC then 1 else 0jCC SRCrip if CC then SRCelse fallthroughZhendong Su Compiler Designcmpq %rax, %rbxjesomethingsomethingElse: instruction jmp commonCodesomething: instruction commonCode: instruction 17

Code Blocks & Labels X86 assembly code is organized intolabeled blockscmpq %rax, %rbxjesomething Labels indicate code locations that canbe jump targets (either throughconditional branch instructions orfunction calls).somethingElse: instruction jmp commonCode Labels are translated away by thelinker and loader – instructions live inthe heap in the “code segment”.something: instruction An X86 program begins executing at adesignated code label(usually “main”).commonCode: instruction Zhendong Su Compiler Design18

Jumps, Call and ReturnInstructionDescriptionNotesjmp SRCrip SRCJump to location in SRCPush rip;rip SRC(Call aprocedure)Push the program counter to thestack (decrementing rsp), and thenjump to the machine instruction atthe address given by SRCcall SRCretPop into rip Pop the current top of the stack(Return from into rip (incrementing rsp). Thisa procedure) instruction effectively jumps to theaddress at the top of the stackZhendong Su Compiler Designbar: instruction instruction retfoo: instruction instruction call bar 19

X86Lite Addressing In general, there are three components of anindirect address– Base: a machine address stored in a register– Index : a variable offset from the base– Disp: a constant offset (displacement) from thebase addr(ind) Base [Index * 8] Disp– When used as a location, ind denotes the addressaddr(ind)– When used as a value, ind denotes Mem[addr(ind)],the contentsof the memory address Examples:ExpressionAddress-8(%rsp)rsp – 8(%rax, %rcx)rax 8*rcx8(%rax, %rcx)rax 8*rcx 8// Array [0,42,2020]// Array address OxBEEFmovq %0xBEEF, %raxmovq %rax,%rbx//rbx 0xBEEFmovq (%rax), %rbx//rbx 0movq 16(%rax), %rbx //rbx 2020movq 1, %rcxmovq (%rax, %rcx), %rbxmovq 8(%rax, %rcx), %rbx//rbx 42//rbx 2020Note: Index cannot be rspZhendong Su Compiler Design20

X86lite Memory Model The X86lite memory consists of 264 bytes numbered 0x00000000 through 0xffffffff. Therefore: legal X86lite memory addresses consist of 64-bit,quadword-aligned pointers.MemoryCode &Data– All memory addresses are evenly divisible by 8 leaq Ind, DESTDEST addr(Ind)loads a pointer into DESTHeap By convention, the stack grows from high addresses to low addresses The register rsp points to the top of the stack– pushq SRCrsp rsp - 8; Mem[rsp] SRC– popq DESTDEST Mem[rsp]; rsp rsp 8Zhendong Su Compiler Design0x00000000Larger Addresses X86lite treats the memory as consisting of 64-bit (8-byte) quadwords.Stack0xffffffff21

DEMO: HANDCODING X86LITEZhendong Su Compiler Design22

See file: x86.mlIMPLEMENTING X86LITEZhendong Su Compiler Design23

Zhendong Su Compiler Design 14 Instruction Description Example Notes negqDEST 2’s complement negation negq %rax addqSRC, DEST DEST DEST SRC addq %rbx, %rax subqSRC, DEST DEST DEST –SRC 4, %rsp imulqSRC, Reg Reg Reg * SRC (truncated 128-bit mult.) 2, %rax Reg must be a r