html/suif1_63.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 - Array Types</TITLE>
   7 <link href="suif1_64.html" rel=Next>
   8 <link href="suif1_62.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_62.html">previous</A>, <A HREF="suif1_64.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="SEC63" HREF="suif1_toc.html#TOC63">Array Types</A></H2>
  18 <P>
  19 <A NAME="IDX438"></A>
  20 <A NAME="IDX439"></A>
  21
  22 </P>
  23 <P>
  24 A SUIF array type defines a new type that is a one-dimensional vector
  25 with elements of another type.  Multi-dimensional arrays are handled as
  26 nested arrays (i.e. arrays of arrays) as in C.  The size of an array is
  27 specified by the upper and lower bounds.  Each bound is either an
  28 integer expression or unknown.  If the bound is an integer expression,
  29 it can either be an integer known at compile time, or a SUIF variable
  30 symbol representing an integer value to be computed at run time.
  31
  32 </P>
  33 <P>
  34 <A NAME="IDX440"></A>
  35 <A NAME="IDX441"></A>
  36 <A NAME="IDX442"></A>
  37 <A NAME="IDX443"></A>
  38 <A NAME="IDX444"></A>
  39 <A NAME="IDX445"></A>
  40 <A NAME="IDX446"></A>
  41 <A NAME="IDX447"></A>
  42 The upper and lower bounds of an array type are stored in objects of the
  43 <CODE>array_bound</CODE> class.  An array bound can be one of three things,
  44 an integer constant, a SUIF variable symbol, or entirely unknown.  The
  45 <CODE>is_constant</CODE>, <CODE>is_variable</CODE>, and <CODE>is_unknown</CODE> methods
  46 check for these three conditions.  If the bound is a constant, the
  47 <CODE>constant</CODE> method returns the integer value of the bound.
  48 Likewise, if it is a variable, the <CODE>variable</CODE> method returns a
  49 pointer to the variable symbol.  The <CODE>print</CODE> method is also
  50 available to print out the value of an array bound.  The global
  51 variable <CODE>unknown_bound</CODE> is a predefined array bound that can be
  52 used when a bound is unknown.
  53
  54 </P>
  55 <P>
  56 <A NAME="IDX448"></A>
  57 <A NAME="IDX449"></A>
  58 <A NAME="IDX450"></A>
  59 <A NAME="IDX451"></A>
  60 <A NAME="IDX452"></A>
  61 <A NAME="IDX453"></A>
  62 <A NAME="IDX454"></A>
  63 A type node with a <CODE>TYPE_ARRAY</CODE> operator is stored in an
  64 <CODE>array_type</CODE> object.  The <CODE>array_type</CODE> class contains three
  65 fields: the lower and upper bounds and the element type.  The
  66 <CODE>lower_bound</CODE>, <CODE>upper_bound</CODE>, and <CODE>elem_type</CODE> methods
  67 retrieve the contents of these fields, and the <CODE>set_lower_bound</CODE>,
  68 <CODE>set_upper_bound</CODE>, and <CODE>set_elem_type</CODE> methods change their
  69 values.  The SUIF definition of arrays says that the elements will be
  70 stored adjacently.  If this would violate alignment restrictions, the
  71 element types must be padded with extra space.  For example, if some
  72 machine has 24 bit integers with a 32 bit alignment requirement, the
  73 24 bit integers may not be used directly as array elements; instead,
  74 one would have to create a structure of size 32 bits that contains a
  75 24 bit integer at offset zero and no other fields, and then use arrays
  76 of this structure type.
  77
  78 </P>
  79 <P>
  80 The bounds of an array type tell two things: the number of elements
  81 and the how the index of an array access instruction will be
  82 interpreted.  The number of elements determines the size of the array
  83 -- the size will be the number of elements times the size of each
  84 element.  Any array type with an upper or lower bound that is anything
  85 but an integer constant will not have a size that is known at compile
  86 time, so such a type cannot be used anywhere a known size is required,
  87 such as for a variable type, an expression type, or the type of an
  88 object copied by a <CODE>memcpy</CODE> instruction.
  89
  90 </P>
  91 <P>
  92 <A NAME="IDX455"></A>
  93 The other time when array bounds are meaningful is in an array access
  94 (a SUIF <CODE>in_array</CODE> instruction).  There each index is required to
  95 be between the given bounds or the result is undefined.  The location
  96 referred to is determined by subtracting the lower bound from the index
  97 and then multiplying by the size of the next lower dimension, or
  98 element size if there are no more dimensions in the array access
  99 instruction.  The size in this case is not necessarily known at
 100 compile time and is considered to be the difference between the upper
 101 and lower bounds plus one (the number of elements) times the size of
 102 the next lower dimension, or the element size if this is the smallest
 103 dimension.  The bounds are evaluated after all sub-expressions of the
 104 array access instruction have been evaluated and before the result of
 105 the array access instruction itself.  Any bounds needed in this
 106 calculation must evaluate to integers when this array access
 107 instruction is executed, so they must be integer constants or variable
 108 symbols, and if variable symbols they must have defined values at this
 109 point.  Note that this implies that the array type for an array access
 110 may not have unknown lower bounds and may have only one unknown upper
 111 bound, that of the outermost dimension.  The <CODE>are_bounds_unknown</CODE>
 112 method checks if the upper bound of an array type is unknown.
 113
 114 </P>
 115 <P>
 116 Note also that all of this information from the array type is also
 117 available in a different form from the <CODE>in_array</CODE> class, between
 118 the <CODE>bound</CODE> expressions and <CODE>offset_op</CODE> expression.  The
 119 results are required to be the same at run time whether the array type
 120 bound information is used or whether the <CODE>bound</CODE> and
 121 <CODE>offset_op</CODE> expressions are used, or else the resulting behavior
 122 is undefined.  This redundancy allows more flexibility in analyzing
 123 array access patterns.  Code transformation passes can treat the
 124 <CODE>in_array</CODE> sub-expressions like any other expressions and
 125 propagate additional information in, and dependence analysis on
 126 individual accesses can look at these general expressions.  Code
 127 dealing with objects and types only has to deal with the symbolic
 128 placeholders.
 129
 130 </P>
 131 <P>
 132 Array bounds are subject to certain constraints.  The upper bound may
 133 never be less than the lower bound.  If both are constants, this
 134 constraint applies to those constants.  If one or both are symbolic
 135 bounds, this constraint must hold for every array access for which
 136 this is the array type.  Symbolic bounds are typically local variables
 137 that are assigned once each at the very beginning of a procedure and
 138 used only as bounds, so their values have the same scope as the types
 139 they are used in.  This corresponds directly to the declarations in
 140 Fortran code of array types with non-constant bounds, but this
 141 particular form is not required by SUIF, and heavily transformed code
 142 may be somewhat different.  What is required is that symbolic bounds
 143 not be sub-variables or call-by-reference parameters, since these are
 144 really just short-hand for other expressions (see section <A HREF="suif1_89.html#SEC89">Features for Compiling Fortran</A>).
 145
 146 </P>
 147
 148 <P><HR><P>
 149 <p>Go to the <A HREF="suif1_1.html">first</A>, <A HREF="suif1_62.html">previous</A>, <A HREF="suif1_64.html">next</A>, <A HREF="suif1_113.html">last</A> section, <A HREF="suif1_toc.html">table of contents</A>.
 150 </BODY>
 151 </HTML>