Successfully reported this slideshow.
We use your LinkedIn profile and activity data to personalize ads and to show you more relevant ads.
COMPILER DESIGN
UNIT-V
ANKUR SRIVASTAVA
ASSISTANT PROF.(CSE)
JETGI
31-Dec-16 1ANKUR SRIVASTAVA (CSE) JETGI
CONTENTS
Code Generation Issues
Target language Issues
Addresses in Target Code
Basic Blocks and Flow Graphs
Optimizations...
INTRODUCTION
The final phase of a compiler is code generator
It receives an intermediate representation (IR) with suppleme...
ISSUES IN THE DESIGN OF CODE GENERATOR
The most important criterion is that it produces correct code
Input to the code gen...
COMPLEXITY OF MAPPING
the level of the IR
the nature of the instruction-set architecture
the desired quality of the genera...
REGISTER ALLOCATION
Two sub-problems
Register allocation: selecting the set of variables that will reside in
registers at ...
A SIMPLE TARGET MACHINE MODEL
Load operations: LD r,x and LD r1, r2
Store operations: ST x,r
Computation operations: OP ds...
ADDRESSING MODES
variable name: x
indexed address: a(r) like LD R1, a(R2) means R1=contents(a+contents(R2))
integer indexe...
ADDRESSES IN THE TARGET CODE
A statically determined area Code
A statically determined data area Static
A dynamically mana...
THREE-ADDRESS STATEMENTS FOR PROCEDURE
CALLS AND RETURNS
call callee
Return
Halt
action
31-Dec-16 ANKUR SRIVASTAVA (CSE) J...
BASIC BLOCKS AND FLOW GRAPHS
Partition the intermediate code into basic blocks
The flow of control can only enter the basi...
RULES FOR FINDING LEADERS
The first three-address instruction in the intermediate code is a leader.
Any instruction that i...
DAG REPRESENTATION OF BASIC BLOCKS
There is a node in the DAG for each of the initial values of the variables
appearing in...
CODE IMPROVING TRANSFORMATIONS
We can eliminate local common subexpressions, that is, instructions that
compute a value th...
DAG FOR BASIC BLOCK
31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 15
DAG for basic block
31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 16
ARRAY ACCESSES IN A DAG
An assignment from an array, like x = a [i], is represented by creating a node
with operator =[] a...
RULES FOR RECONSTRUCTING THE BASIC BLOCK
FROM A DAG
The order of instructions must respect the order of nodes in the DAG. ...
PRINCIPAL USES OF REGISTERS
In most machine architectures, some or all of the operands of an operation
must be in register...
DESCRIPTORS FOR DATA STRUCTURE
For each available register, a register descriptor keeps track of the variable
names whose ...
MACHINE INSTRUCTIONS FOR OPERATIONS
• Use getReg(x = y + z) to select registers for x, y, and z. Call
these Rx, Ry and Rz....
Rules for updating the register and address descriptors
For the instruction LD R, x
Change the register descriptor for reg...
CHARACTERISTIC OF PEEPHOLE OPTIMIZATIONS
• Redundant-instruction elimination
• Flow-of-control optimizations
• Algebraic s...
REDUNDANT-INSTRUCTION ELIMINATION
• LD a, R0
ST R0, a
• if debug == 1 goto L1
goto L2
L I : print debugging information
L2...
FLOW-OF-CONTROL OPTIMIZATIONS
goto L1
...
Ll: goto L2
Can be replaced by:
goto L2
...
Ll: goto L2
if a<b goto L1
...
Ll: g...
ALGEBRAIC SIMPLIFICATIONS
• x=x+0
• x=x*1
31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 26
REGISTER ALLOCATION AND ASSIGNMENT
• Global Register Allocation
• Usage Counts
• Register Assignment for Outer Loops
• Reg...
GLOBAL REGISTER ALLOCATION
This resulted that all live variables be stored at the end of block
To save some of these store...
DYNAMIC PROGRAMMING ALGORITHM
Compute bottom-up for each node n of the expression tree T an array C of
costs, in which the...
Upcoming SlideShare
Loading in …5
×

Compiler unit 5

1,211 views

Published on

AKTU COMPILER DESIGN UNIT 5

Published in: Engineering
  • Be the first to comment

Compiler unit 5

  1. 1. COMPILER DESIGN UNIT-V ANKUR SRIVASTAVA ASSISTANT PROF.(CSE) JETGI 31-Dec-16 1ANKUR SRIVASTAVA (CSE) JETGI
  2. CONTENTS Code Generation Issues Target language Issues Addresses in Target Code Basic Blocks and Flow Graphs Optimizations of Basic Blocks A Simple Code Generator Peephole optimization Register allocation and assignment Instruction selection by tree rewriting 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 2
  3. INTRODUCTION The final phase of a compiler is code generator It receives an intermediate representation (IR) with supplementary information in symbol table Produces a semantically equivalent target program Code generator main tasks: Instruction selection Register allocation and assignment Instruction ordering Front end Code optimizer Code Generator 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 3
  4. ISSUES IN THE DESIGN OF CODE GENERATOR The most important criterion is that it produces correct code Input to the code generator IR + Symbol table We assume front end produces low-level IR, i.e. values of names in it can be directly manipulated by the machine instructions. Syntactic and semantic errors have been already detected The target program Common target architectures are: RISC, CISC and Stack based machines In this chapter we use a very simple RISC-like computer with addition of some CISC-like addressing modes 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 4
  5. COMPLEXITY OF MAPPING the level of the IR the nature of the instruction-set architecture the desired quality of the generated code. x=y+z LD R0, y ADD R0, R0, z ST x, R0 a=b+c d=a+e LD R0, b ADD R0, R0, c ST a, R0 LD R0, a ADD R0, R0, e ST d, R0 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 5
  6. REGISTER ALLOCATION Two sub-problems Register allocation: selecting the set of variables that will reside in registers at each point in the program Resister assignment: selecting specific register that a variable reside in Complications imposed by the hardware architecture Example: register pairs for multiplication and division t=a+b t=t*c T=t/d t=a+b t=t+c T=t/d L R1, a A R1, b M R0, c D R0, d ST R1, t L R0, a A R0, b M R0, c SRDA R0, 32 D R0, d ST R1, t 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 6
  7. A SIMPLE TARGET MACHINE MODEL Load operations: LD r,x and LD r1, r2 Store operations: ST x,r Computation operations: OP dst, src1, src2 Unconditional jumps: BR L Conditional jumps: Bcond r, L like BLTZ r, L 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 7
  8. ADDRESSING MODES variable name: x indexed address: a(r) like LD R1, a(R2) means R1=contents(a+contents(R2)) integer indexed by a register : like LD R1, 100(R2) Indirect addressing mode: *r and *100(r) immediate constant addressing mode: like LD R1, #100 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 8
  9. ADDRESSES IN THE TARGET CODE A statically determined area Code A statically determined data area Static A dynamically managed area Heap A dynamically managed area Stack 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 9
  10. THREE-ADDRESS STATEMENTS FOR PROCEDURE CALLS AND RETURNS call callee Return Halt action 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 10
  11. BASIC BLOCKS AND FLOW GRAPHS Partition the intermediate code into basic blocks The flow of control can only enter the basic block through the first instruction in the block. That is, there are no jumps into the middle of the block. Control will leave the block without halting or branching, except possibly at the last instruction in the block. The basic blocks become the nodes of a flow graph 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 11
  12. RULES FOR FINDING LEADERS The first three-address instruction in the intermediate code is a leader. Any instruction that is the target of a conditional or unconditional jump is a leader. Any instruction that immediately follows a conditional or unconditional jump is a leader. 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 12
  13. DAG REPRESENTATION OF BASIC BLOCKS There is a node in the DAG for each of the initial values of the variables appearing in the basic block. There is a node N associated with each statement s within the block. The children of N are those nodes corresponding to statements that are the last definitions, prior to s, of the operands used by s. Node N is labeled by the operator applied at s, and also attached to N is the list of variables for which it is the last definition within the block. Certain nodes are designated output nodes. These are the nodes whose variables are live on exit from the block. 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 13
  14. CODE IMPROVING TRANSFORMATIONS We can eliminate local common subexpressions, that is, instructions that compute a value that has already been computed. We can eliminate dead code, that is, instructions that compute a value that is never used. We can reorder statements that do not depend on one another; such reordering may reduce the time a temporary value needs to be preserved in a register. We can apply algebraic laws to reorder operands of three-address instructions, and sometimes t hereby simplify t he computation. 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 14
  15. DAG FOR BASIC BLOCK 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 15
  16. DAG for basic block 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 16
  17. ARRAY ACCESSES IN A DAG An assignment from an array, like x = a [i], is represented by creating a node with operator =[] and two children representing the initial value of the array, a0 in this case, and the index i. Variable x becomes a label of this new node. An assignment to an array, like a [j] = y, is represented by a new node with operator []= and three children representing a0, j and y. There is no variable labeling this node. What is different is that the creation of this node kills all currently constructed nodes whose value depends on a0. A node that has been killed cannot receive any more labels; that is, it cannot become a common subexpression. 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 17
  18. RULES FOR RECONSTRUCTING THE BASIC BLOCK FROM A DAG The order of instructions must respect the order of nodes in the DAG. That is, we cannot compute a node's value until we have computed a value for each of its children. Assignments to an array must follow all previous assignments to, or evaluations from, the same array, according to the order of these instructions in the original basic block. Evaluations of array elements must follow any previous (according to the original block) assignments to the same array. The only permutation allowed is that two evaluations from the same array may be done in either order, as long as neither crosses over an assignment to that array. Any use of a variable must follow all previous (according to the original block) procedure calls or indirect assignments through a pointer. Any procedure call or indirect assignment through a pointer must follow all previous (according to the original block) evaluations of any variable. 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 18
  19. PRINCIPAL USES OF REGISTERS In most machine architectures, some or all of the operands of an operation must be in registers in order to perform the operation. Registers make good temporaries - places to hold the result of a subexpression while a larger expression is being evaluated, or more generally, a place to hold a variable that is used only within a single basic block. Registers are often used to help with run-time storage management, for example, to manage the run-time stack, including the maintenance of stack pointers and possibly the top elements of the stack itself. 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 19
  20. DESCRIPTORS FOR DATA STRUCTURE For each available register, a register descriptor keeps track of the variable names whose current value is in that register. Since we shall use only those registers that are available for local use within a basic block, we assume that initially, all register descriptors are empty. As the code generation progresses, each register will hold the value of zero or more names. For each program variable, an address descriptor keeps track of the location or locations where the current value of that variable can be found. The location might be a register, a memory address, a stack location, or some set of more than one of these. The information can be stored in the symbol-table entry for that variable name. 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 20
  21. MACHINE INSTRUCTIONS FOR OPERATIONS • Use getReg(x = y + z) to select registers for x, y, and z. Call these Rx, Ry and Rz. • If y is not in Ry (according to the register descriptor for Ry), then issue an instruction LD Ry, y', where y' is one of the memory locations for y (according to the address descriptor for y). • Similarly, if z is not in Rz, issue and instruction LD Rz, z', where z' is a location for x . • Issue the instruction ADD Rx , Ry, Rz. 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 21
  22. Rules for updating the register and address descriptors For the instruction LD R, x Change the register descriptor for register R so it holds only x. Change the address descriptor for x by adding register R as an additional location. For the instruction ST x, R, change the address descriptor for x to include its own memory location. For an operation such as ADD Rx, Ry, Rz implementing a three-address instruction x = y + x Change the register descriptor for Rx so that it holds only x. Change the address descriptor for x so that its only location is Rx. Note that the memory location for x is not now in the address descriptor for x. Remove Rx from the address descriptor of any variable other than x. When we process a copy statement x = y, after generating the load for y into register Ry, if needed, and after managing descriptors as for all load statements (per rule I): Add x to the register descriptor for Ry. Change the address descriptor for x so that its only location is Ry . 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 22
  23. CHARACTERISTIC OF PEEPHOLE OPTIMIZATIONS • Redundant-instruction elimination • Flow-of-control optimizations • Algebraic simplifications • Use of machine idioms 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 23
  24. REDUNDANT-INSTRUCTION ELIMINATION • LD a, R0 ST R0, a • if debug == 1 goto L1 goto L2 L I : print debugging information L2: 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 24
  25. FLOW-OF-CONTROL OPTIMIZATIONS goto L1 ... Ll: goto L2 Can be replaced by: goto L2 ... Ll: goto L2 if a<b goto L1 ... Ll: goto L2 Can be replaced by: if a<b goto L2 ... Ll: goto L2 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 25
  26. ALGEBRAIC SIMPLIFICATIONS • x=x+0 • x=x*1 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 26
  27. REGISTER ALLOCATION AND ASSIGNMENT • Global Register Allocation • Usage Counts • Register Assignment for Outer Loops • Register Allocation by Graph Coloring 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 27
  28. GLOBAL REGISTER ALLOCATION This resulted that all live variables be stored at the end of block To save some of these stores and their corresponding loads, we might arrange to assign registers to frequently used variables and keep these registers consistent across block boundaries (globally) 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 28
  29. DYNAMIC PROGRAMMING ALGORITHM Compute bottom-up for each node n of the expression tree T an array C of costs, in which the ith component C[i] is the optimal cost of computing the subtree S rooted at n into a register, assuming i registers are available for the computation, for Traverse T, using the cost vectors to determine which subtrees of T must be computed into memory. Traverse each tree using the cost vectors and associated instructions to generate the final target code. The code for the subtrees computed into memory locations is generated first. 31-Dec-16 ANKUR SRIVASTAVA (CSE) JETGI 29
Услуги грузоперевозки киев грузоперевозки киев

×