html/suif1_17.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 - For Nodes</TITLE>
   7 <link href="suif1_18.html" rel=Next>
   8 <link href="suif1_16.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_16.html">previous</A>, <A HREF="suif1_18.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 <H3><A NAME="SEC17" HREF="suif1_toc.html#TOC17">For Nodes</A></H3>
  18 <P>
  19 <A NAME="IDX77"></A>
  20 <A NAME="IDX78"></A>
  21
  22 </P>
  23 <P>
  24 <A NAME="IDX79"></A>
  25 Many of our compiler passes are designed to work with Fortran <CODE>DO</CODE>
  26 loops because they are relatively easy to analyze.  A <CODE>DO</CODE> loop has
  27 a single index variable that is incremented or decremented on every
  28 iteration and varies from an initial to a final value.  SUIF uses
  29 <CODE>tree_for</CODE> nodes to represent well-structured <CODE>DO</CODE> loops.  The
  30 exact conditions that a loop must meet to be represented as a
  31 <CODE>tree_for</CODE> in SUIF are described below.  The expander's cleanup
  32 pass, which is run immediately after the front-end, converts
  33 <CODE>tree_for</CODE> nodes that violate any of these conditions into
  34 <CODE>tree_loop</CODE> nodes (see section <A HREF="suif1_16.html#SEC16">Loop Nodes</A>).  Even though they are
  35 primarily intended for Fortran code, <CODE>tree_for</CODE> nodes may also be
  36 used for C loops that meet the same conditions.
  37
  38 </P>
  39 <P>
  40 <A NAME="IDX80"></A>
  41 <A NAME="IDX81"></A>
  42 The index variable of a <CODE>tree_for</CODE> can be accessed using the
  43 <CODE>index</CODE> method and set using the <CODE>set_index</CODE> method.  The
  44 index variable must be a scalar variable that is defined in the scope of
  45 the <CODE>tree_for</CODE> node.  It may not be modified anywhere within the
  46 loop body.  This applies across procedures as well.  If the loop body
  47 contains a call to another procedure that modifies the index variable,
  48 then the loop cannot be represented by a <CODE>tree_for</CODE> node.
  49 Moreover, if you are using Fortran form, the index variable may not be a
  50 call-by-reference parameter.
  51 See section <A HREF="suif1_89.html#SEC89">Features for Compiling Fortran</A>.
  52
  53 </P>
  54 <P>
  55 <A NAME="IDX82"></A>
  56 <A NAME="IDX83"></A>
  57 <A NAME="IDX84"></A>
  58 <A NAME="IDX85"></A>
  59 <A NAME="IDX86"></A>
  60 <A NAME="IDX87"></A>
  61 The range of values for the index variable is specified by three
  62 <CODE>operand</CODE> fields.  See section <A HREF="suif1_30.html#SEC30">Operands</A>.  The lower and upper bounds and
  63 the step value can be accessed by the <CODE>lb_op</CODE>, <CODE>ub_op</CODE>, and
  64 <CODE>step_op</CODE> methods.  The <CODE>set_lb_op</CODE>, <CODE>set_ub_op</CODE>, and
  65 <CODE>set_step_op</CODE> methods are provided to change them.  These operands
  66 are expressions that are evaluated once at the beginning of the loop.
  67 The index variable is initially assigned the lower bound value and then
  68 incremented by the step value on every iteration until it reaches the
  69 upper bound value; the code to do this is automatically created when the
  70 <CODE>tree_for</CODE> is expanded to low-SUIF code.
  71
  72 </P>
  73 <P>
  74 <A NAME="IDX88"></A>
  75 <A NAME="IDX89"></A>
  76 <A NAME="IDX90"></A>
  77 <A NAME="IDX91"></A>
  78 <A NAME="IDX92"></A>
  79 <A NAME="IDX93"></A>
  80 Most users will always use <CODE>tree_for</CODE> nodes in conjunction with
  81 expression trees.  Flat lists of instructions are typically used only in
  82 the library and with back-end passes where the <CODE>tree_for</CODE> nodes
  83 have been dismantled.  It is possible to use <CODE>tree_for</CODE> nodes
  84 without expression trees, but the bounds and step values cannot be
  85 treated as operands.  In fact, even with expression trees those operands
  86 are actually stored on tree node lists.  If necessary, these lists can
  87 be accessed directly using the <CODE>lb_list</CODE>, <CODE>ub_list</CODE>, and
  88 <CODE>step_list</CODE> methods.  Each list is required to contain a single
  89 expression with a dummy copy instruction at the root.  The destination
  90 of the dummy copy must be a null operand.  Methods are provided in the
  91 tree node list class to extract the operands from the tree node lists
  92 (see section <A HREF="suif1_20.html#SEC20">Tree Node Lists</A>).
  93
  94 </P>
  95 <P>
  96 <A NAME="IDX94"></A>
  97 <A NAME="IDX95"></A>
  98 <A NAME="IDX96"></A>
  99 The <CODE>tree_for</CODE> must also specify the comparison operator used to
 100 determine when the index variable has reached the upper bound value.
 101 The possible comparison operators are members of the
 102 <CODE>tree_for_test</CODE> enumerated type.  The <CODE>test</CODE> and
 103 <CODE>set_test</CODE> methods are used to access and modify the comparison
 104 operator for a <CODE>tree_for</CODE> node.  The <CODE>tree_for_test</CODE>
 105 enumeration includes quite a few comparison operators, but some of them
 106 are only used by the front-end.  Both signed and unsigned versions are
 107 available for most of the comparison operators, as indicated by the
 108 letters "<CODE>S</CODE>" and "<CODE>U</CODE>" in their names.
 109
 110 </P>
 111 <DL COMPACT>
 112
 113 <DT><CODE>FOR_SLT</CODE>
 114 <DD>
 115 <DT><CODE>FOR_ULT</CODE>
 116 <DD>
 117 Less than.  Repeat as long as the index is strictly less than the upper
 118 bound.
 119
 120 <DT><CODE>FOR_SLTE</CODE>
 121 <DD>
 122 <DT><CODE>FOR_ULTE</CODE>
 123 <DD>
 124 Less than or equal.  Repeat as long as the index is less than or equal
 125 to the upper bound.
 126
 127 <DT><CODE>FOR_SGT</CODE>
 128 <DD>
 129 <DT><CODE>FOR_UGT</CODE>
 130 <DD>
 131 Greater than.  Repeat as long as the index is strictly greater than the
 132 upper bound.  Sometimes <CODE>DO</CODE> loops go backwards, using a negative
 133 step value.  For those loops, the comparison operator must also be
 134 reversed.
 135
 136 <DT><CODE>FOR_SGTE</CODE>
 137 <DD>
 138 <DT><CODE>FOR_UGTE</CODE>
 139 <DD>
 140 Greater than or equal.  Repeat as long as the index is greater than or
 141 equal to the upper bound.  Again, this may be used when the step value
 142 is negative.
 143
 144 <DT><CODE>FOR_SGELE</CODE>
 145 <DD>
 146 <DT><CODE>FOR_UGELE</CODE>
 147 <DD>
 148 These comparisons are only used by the front-end.  In FORTRAN, it may
 149 not be possible to determine the direction of a loop at compile time.
 150 For example, if the step value is not a constant, it could be either
 151 positive or negative.  These comparison operators indicate that the loop
 152 test may be either "greater than or equal" or "less than or equal",
 153 depending on the sign of the step value.  The expander's cleanup pass
 154 converts any <CODE>tree_for</CODE> nodes with these tests to two
 155 <CODE>tree_for</CODE> nodes and a <CODE>tree_if</CODE> node to decide between them.
 156 Thus, these comparison operators should never be encountered in most
 157 SUIF code.
 158
 159 <DT><CODE>FOR_EQ</CODE>
 160 <DD>
 161 <DT><CODE>FOR_NEQ</CODE>
 162 <DD>
 163 Equal and not equal.  These comparisons are only used by the front-end.
 164 The expander's cleanup pass dismantles <CODE>tree_for</CODE> nodes that use
 165 these comparisons.
 166 </DL>
 167
 168 <P>
 169 <A NAME="IDX97"></A>
 170 <A NAME="IDX98"></A>
 171 The body of a <CODE>tree_for</CODE> loop is stored in a tree node list.  The
 172 methods to get and set the loop body are <CODE>body</CODE> and
 173 <CODE>set_body</CODE>, respectively.  The <CODE>body</CODE> list contains only the
 174 instructions corresponding to the body of the loop in the source
 175 program.  The instructions to compare the index variable with the upper
 176 bound, increment it, and branch back to the beginning of the body are
 177 not included as part of the body; they are created when the
 178 <CODE>tree_for</CODE> is expanded to low-SUIF code.
 179
 180 </P>
 181 <P>
 182 <A NAME="IDX99"></A>
 183 <A NAME="IDX100"></A>
 184 <A NAME="IDX101"></A>
 185 Besides the loop body, a <CODE>tree_for</CODE> node has an additional tree
 186 node list called the <CODE>landing_pad</CODE>.  The code in the landing pad
 187 is executed if and only if the loop body is executed at least one
 188 time, but the <CODE>landing_pad</CODE> is executed only once, unlike the
 189 body which is usually executed many times.  The <CODE>landing_pad</CODE> is
 190 executed immediately before the first time through the loop body.  The
 191 landing pad thus provides a place to move loop-invariant code.
 192
 193 </P>
 194 <P>
 195 <A NAME="IDX102"></A>
 196 <A NAME="IDX103"></A>
 197 <A NAME="IDX104"></A>
 198 <A NAME="IDX105"></A>
 199 Two labels are associated with a <CODE>tree_for</CODE>: <CODE>contlab</CODE> and
 200 <CODE>brklab</CODE>.  A "continue" statement in the loop body requires a
 201 jump over the rest of the body to the code that increments the index and
 202 continues with the next iteration.  This can be implemented with a jump
 203 to the <CODE>contlab</CODE> label, which is implicitly located at the end of
 204 the <CODE>body</CODE> list.  Similarly, a "break" statement in the loop is
 205 translated to a jump to the <CODE>brklab</CODE> label which is located
 206 immediately after the loop.  These two labels must be defined in the
 207 scope of the <CODE>tree_for</CODE> node, but the label instructions that mark
 208 their locations are not inserted into the tree node lists until the
 209 <CODE>tree_for</CODE> node is expanded into low-SUIF form.
 210
 211 </P>
 212 <P>
 213 In summary, the semantics of a <CODE>tree_for</CODE> node are as follows.  The
 214 lower bound, upper bound, and step operands are evaluated once at the
 215 beginning of the loop <A NAME="DOCF2" HREF="suif1_foot.html#FOOT2">(2)</A>.  The lower bound is compared to the upper bound.  If
 216 the test fails, the loop does not execute.  Otherwise, the lower bound
 217 is assigned to the index variable, and any code in the landing pad list
 218 is executed.  After that, the body is executed repeatedly and the index
 219 variable is incremented by the step value on every iteration, until the
 220 index variable fails the test with the upper bound value.
 221
 222 </P>
 223 <P>
 224 As an example, the following C code could be translated into the SUIF
 225 code shown in a simplified form below:
 226
 227 </P>
 228
 229 <PRE>
 230 for (i = 100; i &#62;= 0; i--) {
 231     A[i] = i;
 232 }
 233 </PRE>
 234
 235
 236 <PRE>
 237 FOR (Index=i Test=SGTE Cont=L:__L1 Brk=L:__L2)
 238 FOR LB
 239     ldc 100
 240 FOR UB
 241     ldc 0
 242 FOR STEP
 243     ldc -1
 244 FOR LANDING PAD
 245 FOR BODY
 246     str e1 = i
 247       e1: array e2+0, size(32), index(i), bound(e3)
 248         e2: ldc &#60;A,0&#62;
 249           e3: ldc 101
 250 FOR END
 251 </PRE>
 252
 253 <P><HR><P>
 254 <p>Go to the <A HREF="suif1_1.html">first</A>, <A HREF="suif1_16.html">previous</A>, <A HREF="suif1_18.html">next</A>, <A HREF="suif1_113.html">last</A> section, <A HREF="suif1_toc.html">table of contents</A>.
 255 </BODY>
 256 </HTML>