html/suif1_4.html

   1 <HTML>
   2 <HEAD>
   3 <!-- This HTML file has been created by texi2html 1.54
   4      from suif1.texi on 28 April 1999 -->
   5
   6 <TITLE>The SUIF Version 1 Library - Instruction Level</TITLE>
   7 <link href="suif1_5.html" rel=Next>
   8 <link href="suif1_3.html" rel=Previous>
   9 <link href="suif1_toc.html" rel=ToC>
  10
  11 </HEAD>
  12 <BODY>
  13 <p>Go to the <A HREF="suif1_1.html">first</A>, <A HREF="suif1_3.html">previous</A>, <A HREF="suif1_5.html">next</A>, <A HREF="suif1_113.html">last</A> section, <A HREF="suif1_toc.html">table of contents</A>.
  14 <P><HR><P>
  15
  16
  17 <H2><A NAME="SEC4" HREF="suif1_toc.html#TOC4">The Instruction Level</A></H2>
  18
  19 <P>
  20 Each instruction node in an abstract syntax tree holds a SUIF
  21 instruction.  See section <A HREF="suif1_22.html#SEC22">Instructions and Expression Trees</A>.  Most SUIF instructions perform
  22 simple operations; the opcodes resemble those for a typical RISC
  23 processor.  However, more complex instructions are used in places where
  24 it is important to retain high-level information.
  25
  26 </P>
  27 <P>
  28 SUIF supports both expression trees and flat lists of instructions.  In
  29 an expression tree, the instructions for an expression are all grouped
  30 together.  This works well for high-level passes.  Because expression
  31 trees do not totally order the evaluation of the instructions, they do
  32 not work so well for back-end optimization and scheduling passes.  Thus
  33 SUIF also provides the flat list representation where each instruction
  34 node contains a single instruction.
  35
  36 </P>
  37 <P>
  38 Most SUIF instructions use a "quadruple" format with a destination
  39 operand and two source operands; however, some instructions require more
  40 specialized formats.  For example, <CODE>ldc</CODE> (load constant)
  41 instructions have an immediate value field in place of the source
  42 operands.  While most SUIF instructions are very simple, it is important
  43 to retain sufficient high-level information to support detailed
  44 analysis.  Thus SUIF includes several instructions with more complex
  45 behavior:
  46
  47 </P>
  48
  49 <UL>
  50 <LI>
  51
  52 The <CODE>cal</CODE> (call) instruction implements a machine-independent
  53 procedure call with a list of parameters.  This hides the details of
  54 various linkage conventions.
  55
  56 <LI>
  57
  58 The <CODE>mbr</CODE> (multi-way branch) instruction transfers control to one
  59 of the given labels depending on the value of its source operand.  This
  60 represents computed <CODE>goto</CODE> and <CODE>switch</CODE> statements.
  61
  62 <LI>
  63
  64 The <CODE>array</CODE> instruction computes the address of an element in an
  65 array given a list of index values.  These instructions are eventually
  66 expanded to additions and multiplications to perform the necessary
  67 pointer arithmetic.
  68 </UL>
  69
  70 <P>
  71 These instructions are much easier to analyze than the equivalent series
  72 of low-level instructions.
  73
  74 </P>
  75 <P>
  76 The following example shows the low-SUIF instructions corresponding to a
  77 simple fragment of C code:
  78
  79 </P>
  80
  81 <PRE>
  82 x = 0;
  83 y = *ptr;
  84 if (y &#60; x + z) {
  85     *ptr = x;
  86 }
  87 </PRE>
  88
  89
  90 <PRE>
  91 1: ldc (i.32) x = 0           // load integer constant 0
  92 2: lod (i.32) y = ptr         // load from address in ptr
  93 3: add (i.32) nd#3 = x, z     // add x and z
  94 4: sl  (i.32) nd#4 = y, nd#3  // set if y &#60; x + z
  95 5: bfalse     nd#4, L:L1      // branch if false to label L1
  96 6: str        ptr = x         // store x to address in ptr
  97 7: lab        L:L1            // label L1
  98 </PRE>
  99
 100 <P>
 101 Most of the operands in this example are variables; however, the results
 102 of the <CODE>add</CODE> and <CODE>sl</CODE> instructions are temporary values and
 103 are not stored in variables.  Such temporary values occur frequently,
 104 and rather than requiring that new variables be created to hold them,
 105 SUIF allows them to be used directly.  Each temporary must have a single
 106 definition and a single use within the same basic block.  In the printed
 107 code above, the temporary values are indicated by "node" numbers,
 108 using the ID numbers of the instructions that produce the values.
 109 Internally, however, the operands contain pointers between the
 110 instructions.  For example, the <CODE>bfalse</CODE> source operand contains a
 111 pointer to the <CODE>sl</CODE> comparison instruction, and the <CODE>sl</CODE>
 112 destination operand contains a pointer to the branch instruction.  Thus
 113 the definition and use of a temporary value are directly connected,
 114 making it easy to find one from the other.
 115
 116 </P>
 117 <P>
 118 Flat lists of instructions work well for many back-end compiler passes,
 119 but for high-level transformations expression trees are often a better
 120 representation.  Thus the SUIF system supports expression trees as well
 121 as flat lists.  See section <A HREF="suif1_31.html#SEC31">Expression Trees</A>.  The difference between the two
 122 representations is actually quite small.  The temporary value pointers
 123 described above naturally create trees, except that with flat lists the
 124 nodes of the trees are listed in bottom-up order.  When using the
 125 expression tree representation, the instructions are rearranged so that
 126 only the roots of the expression trees are included in the AST
 127 instruction nodes.  The other instructions are reached through the
 128 pointers in the operands.  For example, by labeling each subtree (e.g.
 129 <CODE>e1</CODE> and <CODE>e2</CODE>), the expression tree in the example could be
 130 printed as:
 131
 132 </P>
 133
 134 <PRE>
 135 5: bfalse e1, L:L1
 136 4:   e1: sl (i.32) y, e2
 137 3:     e2: add (i.32) x, z
 138 </PRE>
 139
 140 <P>
 141 In this case, only the branch instruction is directly contained in an
 142 instruction node.  The <CODE>sl</CODE> instruction is reached through the
 143 branch's source operand, and the <CODE>add</CODE> instruction is contained in
 144 the second source operand of the <CODE>sl</CODE> instruction.
 145
 146 </P>
 147
 148 <P><HR><P>
 149 <p>Go to the <A HREF="suif1_1.html">first</A>, <A HREF="suif1_3.html">previous</A>, <A HREF="suif1_5.html">next</A>, <A HREF="suif1_113.html">last</A> section, <A HREF="suif1_toc.html">table of contents</A>.
 150 </BODY>
 151 </HTML>