Tapenade’s basic utility classes

TapIntList TapPair TapTriplet Int2ZoneInfo ToBool ToInt ToObject Chrono Tree FixedTree ListTree SAtomTree IAtomTree Operator Phylum  BoolVector BoolMatrix BlockStorage UnitStorage ILLang

Tapenade constantly uses the present classes to represent IL trees, chained lists, pairs and triplets of Objects, bit sets.

About IL trees

Class Tree is used to hold AST’s in the IL formalism.

Every Tree has an operator, which is a construct of IL.

A Tree can be an atomic tree, which means it has no child tree, and it contains a value. An atomic tree is indeed a SAtomTree (it value is a String) or a IAtomTree (its value is an int).

Otherwise a tree can have children trees. Depending on the operator, the arity (number of children) of the tree may be fixed (sometimes zero) or variable.

Every Tree can receive additional annotations. An annotation is basically the pair of a String keyword and an Object value.

Trees can be created in various ways:

  • ILUtils.build(int opCode, int value) builds a new atomic tree with value. opCode must be the code of an atomic IL operator that contains an int.

  • ILUtils.build(int opCode, String value) builds a new atomic tree with value. opCode must be the code of an atomic IL operator that contains a String.

  • ILUtils.build(int opCode, TapList<Tree> children) builds a new tree with the given children. opCode must be the code of a non-atomic operator. If this operator is of fixed arity and the length of the provided children list does not match, extra children are just discarded or missing children are filled with atomic trees of operator none

  • ILUtils.build(int opCode, Tree[] children) very similar to the above

  • ILUtils.build(int opCode, Tree tree1, Tree tree2, ...) very similar to the above

Trees can be modified with setChild(), cutChild(), addChild(), addChildren(), removeChild(), setValue().

One can navigate in Trees using up() and down().

NOTICE: the Tree’s that are contained in Instruction’s sometimes are (and must be) incomplete, i.e. some of their children may be of operator none. This happens for the control Instruction that may occur at the end of a Block: since the Flow Graph structure has indeed split the structured control statement, the control “header” is in the controlling Block’s last Instruction, and has an empty “body”, whereas the controlled “body” is in the Instruction’s of the following Blocks. For instance the Tree for a conditional statement such as

if (test>0) {
   x = 1 ;
} else {
   x = 2 ;
   y = 1.7 ;
}

which under normal circumstances corresponds to the IL Tree:

if
   gt
      ident:"test"
      intCst:0
   blockStatement
      assign
        ident:"x"
        intCst:1
   blockStatement[*]
      assign
        ident:"x"
        intCst:2
      assign
        ident:"y"
        realCst:"1.7"

is split in the Flow Graph as one Instruction containing Tree

if
   gt
      ident:"test"
      intCst:0
   none
   none

at the last Instruction of come “controlling” Block, plus another Instruction containing

assign
    ident:"x"
    intCst:1

inside some Block accessible through the “then” arrow leaving this “controlling” Block, and finally two other Instruction containing respectively

assign
   ident:"x"
   intCst:2

and

assign
   ident:"y"
   realCst:"1.7"

inside another Block accessible through the else arrow leaving the “controlling” Block. It is only at the Tree regeneration stage (package ir2tree) that a structured Tree like the “normal” Tree above will be reconstructed. The same applies to other structured Tree constructs such as switch, loop.

About chained lists

Tapenade provides the following utility classes, mostly independent from AD itself:

  • TapIntList: forward chained lists of integers (primitive type, not Integer). Direct access through int head and TapIntList tail.

  • TapPair TapTriplet: pairs and triplets of Objects (a dirty idea, should be used sparingly). Direct access through first, second, and third.

  • Int2ZoneInfo: essentially a TapPair whose first component is a plain Java int instead of an object and second component is a ZoneInfo. It is used only to hold couples (zone number . ZoneInfo). It would be nice to get rid of this class.

  • ToBool ToInt: emulation of pass-by-reference to return extra boolean or int results. Access through get() and set().

  • Chrono: run-time timer. Usage through reset() and elapsed().

  • Tree FixedTree ListTree SAtomTree IAtomTree Operator Phylum ILLang: Abstract Syntax Trees.

  • ILLang is generated automatically during the build chain from il.metal.

About bit sets

  • BoolVector BoolMatrix: bitset vectors and matrices.