../

intermediate-representation

Notes

Triples

Here the result column is eliminated. The place to store the result is derived from the position of the instruction. Pasted image 20231106095243

The main issue with this is that it is inflexible to rearrangement. For the sake of optimization, compiler usually switch the order in which instructions are executed. Since we are referring to the positions in the table, when we move an instruction all of its backlinks have to changed as well

Indirect triples

Instead of referring to instructions by their place in the triple table, we instead refer to them by a pointer. To facilitate this we need a separate array which holds the mapping from position -> instructions

Questions

Question 1: What are some IR properties

– Ease of generation

  • Ease of manipulation – Procedure size – Freedom of expression – Level of abstraction

Question 2: Explain the difference in the levels of abstraction using array reference as an example

Pasted image 20231228113155 This is an AST. Pasted image 20231228113210 This is three address code

Question 3: What are high level abstraction good for?

Memory Disambiguation

Question 4: What are low level abstractions good for?

Address Calculation

Question 5: What are the types of IR

  • Structural
  • Linear
  • Hybrid

Question 6: What is source to source translation?

Transpiling Converting between languages of similar levels of abstraction

Question 7: Which sort of IR is used in source to source translator?

Structural

Question 8: What is the usual hierarchy, in terms of abstraction, of the different types of IR?

Structural > Linear

Question 9: Is this hierarchy always true? If not give an example

No Pasted image 20231228114827 loadArray A,i,j is a high-level linear IR

Question 10: What is the difference between AST and DAG?

Unique node for each value

Question 11: Convert x-2*y to Stack Machine Code 

push x
push 2
push y
mult
sub

Question 12: What is the other name for Stack Machine Code

Single address code

Question 13: What are the instructions available in 3 address code

  • Assignment
    • a = b biop c where biop is any binary operation
    • a = uop b
    • a = b
  • Control Flow
    • goto L
    • if t goto L where t is a boolean
    • if (a relop b) goto L where relop is a relational operator
  • Function
    • func begin <name>
    • func end
    • param p
    • refparam p
    • return
    • return <value>
    • call f, n
  • Array
    • a = b[i]
    • b[i] = a
  • Pointers
    • a = &b
    • *a = b
    • a = *b

Question 14: What is the format of a quadruples

Question 15: What is the table size of Quadruples

Question 16: Advantages and disadvantages of quadruples

Question 17: Explain how triples work?

Question 18: How to represent an assignment to a variable in triples

Question 19: What are the disadvantages of triples

Question 20: What is the form of statement used in 2 address code

Question 21: What is SSA

Question 22: Convert the following to SSA 

x = 0
y = 1
while (x < k)
x = x + 1
y = y + x

Question 23: What do the nodes and edges in a Control Flow Graph represent?

Question 24: What is a basic block

Question 25: How to identify leaders?