html/suif1_85.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 - Cloning</TITLE>
   7 <link href="suif1_86.html" rel=Next>
   8 <link href="suif1_84.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_84.html">previous</A>, <A HREF="suif1_86.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 <H1><A NAME="SEC85" HREF="suif1_toc.html#TOC85">Replicating Trees and Instructions</A></H1>
  18 <P>
  19 <A NAME="IDX621"></A>
  20 <A NAME="IDX622"></A>
  21
  22 </P>
  23 <P>
  24 Many SUIF programs need to duplicate parts of abstract syntax trees or
  25 expression trees.  For example, loop transformations such as unrolling
  26 and peeling require copies of the loop bodies, and entire procedures
  27 must be copied to implement procedure inlining.  Because code
  28 replication can be quite complicated in SUIF, it is handled in the
  29 library by the <STRONG>cloning</STRONG> methods.
  30
  31 </P>
  32 <P>
  33 <A NAME="IDX623"></A>
  34 <A NAME="IDX624"></A>
  35 <A NAME="IDX625"></A>
  36 <A NAME="IDX626"></A>
  37 <A NAME="IDX627"></A>
  38 <A NAME="IDX628"></A>
  39 <A NAME="IDX629"></A>
  40 <A NAME="IDX630"></A>
  41 <A NAME="IDX631"></A>
  42 <A NAME="IDX632"></A>
  43 Several different kinds of SUIF objects can be cloned.  The
  44 <CODE>tree_node</CODE>, <CODE>tree_node_list</CODE>, <CODE>instruction</CODE>, and
  45 <CODE>operand</CODE> classes have <CODE>clone</CODE> methods.  The various derived
  46 <CODE>tree_node</CODE> classes also have wrapper methods to cast the result of
  47 the base class <CODE>clone</CODE> method to the appropriate pointer types.
  48 When an object is cloned, everything within it is recursively cloned.
  49 In addition to the child nodes and instructions, this includes symbol
  50 tables and the types and symbols within them.  All of the known
  51 references to cloned objects (including those in registered annotations)
  52 are updated.
  53
  54 </P>
  55 <P>
  56 The complexity of cloning is primarily due to SUIF's scope rules.  The
  57 code being copied may reference symbols and types that are not visible
  58 in the scope where the copy will be used.  Thus the cloning process is
  59 divided into three steps:
  60
  61 </P>
  62
  63 <OL>
  64 <LI>
  65
  66 The code to be copied is scanned for references to symbols and types
  67 that are not visible in the specified destination scope.  These are
  68 referred to as <STRONG>exposed references</STRONG>.
  69
  70 <LI>
  71
  72 The exposed references are resolved in the symbol table for the
  73 destination scope.  New variables are created to replace the exposed
  74 variables.  Types are usually moved up in the symbol table hierarchy so
  75 that they are visible in both the source and destination scopes.
  76
  77 <LI>
  78
  79 The code is actually copied.  Symbol tables nested within the code are
  80 copied and references to them and their contents are updated to use the
  81 copies.  Similarly, the exposed references are replaced with references
  82 to any new symbols or types that were created in the previous step.
  83 </OL>
  84
  85 <P>
  86 Each of these steps is described in more detail below.  The methods that
  87 perform the individual steps are available to users who need more
  88 control over the cloning process.  For example, you may want to insert
  89 code to initialize new variables that are created in the destination
  90 scope due to exposed references.  The cloning methods can also be used
  91 to replace references to particular symbols or types without actually
  92 copying anything.
  93
  94 </P>
  95 <P>
  96 <A NAME="IDX633"></A>
  97 The <CODE>replacements</CODE> structure is used throughout the cloning process
  98 to keep track of exposed references and objects that have been replaced.
  99 This structure includes lists of symbols, types, variable definitions,
 100 symbol tables, and instructions.  For each kind of object, there are two
 101 lists.  Except in intermediate steps, these lists should be the same
 102 length.  An entry on the first list refers to an object in the original
 103 code and the corresponding entry on the second list is a new object that
 104 has been created to replace the original.
 105
 106 </P>
 107
 108 <UL>
 109 <LI><A HREF="suif1_86.html#SEC86">Finding Exposed References</A>: Finding things not visible at the destination.
 110 <LI><A HREF="suif1_87.html#SEC87">Resolving Exposed References</A>: Creating replacement objects.
 111 <LI><A HREF="suif1_88.html#SEC88">Copying the Objects</A>: Copying the code and updating references.
 112 </UL>
 113
 114 <P><HR><P>
 115 <p>Go to the <A HREF="suif1_1.html">first</A>, <A HREF="suif1_84.html">previous</A>, <A HREF="suif1_86.html">next</A>, <A HREF="suif1_113.html">last</A> section, <A HREF="suif1_toc.html">table of contents</A>.
 116 </BODY>
 117 </HTML>