Tuple-Based Intermediate Representations

What are Tuples?

Tuples are instruction-like entities consisting of an operator and zero to three arguments. Arguments are literals, variables, temporaries, subroutines, or labels.

Typical tuples are:

Different authors of tuple systems will make different design choices. For example, what happens if an assertion fails? That depends on the source language; therefore, a given translator will fill in these details. How big is an integer, or a float? How are characters encoded? Also left up to the implementation.

Tuple Arguments

Tuple arguments are generally low-level entities, such as:

• labels
• subroutine references
• simple, non-structured, values (literals, variables, and temporaries)

By non-structured we mean items that fit into a single fixed-size machine unit. Strings, arrays, and structs are always referenced through a pointer.

It is not necessary to specify the kinds or sizes of the value data types. Integers and floating-point values are generally assumed, but a system will generally allow for a several different types of various sizes of these. A specific translation would define these types, and a back end would arrange for type conversions. For example:

    (ADD, x, i, y)

where x and y are floating point and i is an integer, is an allowable tuple, and would be turned into backend code that explicitly or implicitly converts i to a floating-point value (of the right size) before doing a floating-point addition.

Similarly, a particular translation may include unsigned integer types (as one would in C). A backend has to take care of these cases. For example, with an x86 backend, a JGE tuple would become a jge instruction with signed arguments, but a jae with unsigned arguments.

In practice, tuple arguments can sometimes take arguments that represent sizes in bytes. It is up to a specific translation to compute these values.

Literals

In tuple-base representations, source language features like enumeration, character, and boolean literals should be turned into simple integer literals by a compiler front-end. Ditto for arrays and structs: tuples generally maniuplate individual word-like entities; large structures are flattened into smaller things.

Variables

Variables represent run-time storage locations. It’s not important, really. if these locations are in static memory, in a stack frame, or the heap, but it’s good to keep track of the static nesting level for a variable, as this is useful for languages with arbitrarily nested subroutines. In languages without subroutine nesting, such as C, global variables would have level 0 and all others would have level 1.

You might often see two types of variables, integer variables and floating point variables, since most hardware makes the same distinction.

Temporaries

Temporaries differ from variables in that variables come from source language variables that are actually declared, while temporaries are the result of evaluating expressions. For example, if a source language featured the expression

    x + y * z

the corresponding tuple sequence would be:

   (MUL, y, z, r0)
   (ADD, x, r0, r1)

where r0 and r1 are temporaries. Temporaries come in two flavors: value temporaries and address temporaries. An address temporary would arise from evaluating an expression like:

   a[i].x

since the address of the corresponding storage location has to be computed at run-time (assuming the value of i is not known at compile-time).

Value temporaries can be either integer or floating-point, while address temporaries are always themselves integer-valued, since their value is an address, but internally they track whether they are referencing an integer or floating-point object.

Subroutines

It might be helpful to distinguish between subroutines defined in the current translation unit (user subroutines) and those defined elsewhere (external subroutines).

User Subroutines

A user subroutine denotes a function in the current translation unit. It contains the following properties:

• level: the static nesting level
• parent: the subroutine in which this subroutine is nested within
• locals: the set of local variables
• parameters: the list of parameters
• tuples: the list of tuples for the body

External Subroutines

External subroutines represent top-level functions callable by the current translation unit but defined elsewhere. They are known only by name. Example:

print(x+4);

    add i0, 4, r3
    param r3
    param s0
    call __print

Labels

Labels are used to hold the structured control graph in a linearized list of tuples.

while (x < 3) {
    y = 10;
    x = x * 5;
}

L1:
    if i0 >= 3 goto L2
    i1 := 10
    r3 := i0 * 5
    i0 := r3
    goto L1
L2:

Comprehensive Examples

A simple example:

string f(real i) {
    return "dog" unless i >= 3.3;
}
string test = f(cos(2.2));

p0:
  ; level=0 parent=null params=[] locals=[i0]
  f0 := cos 2.2
  startcall p1
  f1 := cos 2.2
  param f1
  r1 := call p1
  i0 := r1
  exit
p1:
  ; level=1 parent=p0 params=[x1] locals=[]
  r0 := x1 >= 3.3
  if r0 != 0 goto L0
  ret s0
L0:
  call __terminate_thread
s0:
  [100, 111, 103]

An example with heap-allocated arrays and structures:

int[] a;
a[6] = 20;
real x = a[80];
a = new int[]{4, 2, 1};
struct Point {
  int x; int y;
}
Point[] polygon;
print(polygon[5].y);

p0:
  ; level=0 parent=null params=[] locals=[i0, x1, i1]
  assert i0 != 0
  r0 := *(i0+-4)
  assert 0 <= 6 < r0
  r1 := 6 * 4
  r2 := i0 + r1
  *r2 := 20
  assert i0 != 0
  r3 := *(i0+-4)
  assert 0 <= 80 < r3
  r4 := 80 * 4
  r5 := i0 + r4
  r6 := *r5
  x1 := r6
  r7 := alloc 16
  *r7 := 3
  r7 := r7 + 4
  *(r7+0) := 4
  *(r7+4) := 2
  *(r7+8) := 1
  i0 := r7
  assert i1 != 0
  r8 := *(i1+-4)
  assert 0 <= 5 < r8
  r9 := 5 * 4
  r10 := i1 + r9
  r11 := *r10
  assert r11 != 0
  r12 := r11 + 4
  r14 := *r12
  r13 := int_to_str r14
  param r13
  call __print
  exit

An example with threads:

void f() {
    for (int i = 0; i < 20000; i++) {
        print (i + " ");
    }
}
thread t1 = start f();
thread t2 = start f();
join(t1);
join(t2);

p0:
  ; level=0 parent=null params=[] locals=[i1, i2]
  param 0
  param p1
  r3 := call __create_thread
  i1 := r3
  param 0
  param p1
  r4 := call __create_thread
  i2 := r4
  param i1
  call __join
  param i2
  call __join
  exit
p1:
  ; level=1 parent=p0 params=[] locals=[i0]
  i0 := 0
L0:
  if i0 >= 20000 goto L1
  r1 := int_to_str i0
  param s0
  param r1
  r2 := call __concat_string
  param r2
  call __print
  inc i0
  goto L0
L1:
  ret
s0:
  [32]