Move some documentation from the header file into ProgrammersManual. About to improve.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52360 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 183 insertions, 4 deletions

diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html
index 716d364ed5..f0f941f584 100644
--- a/docs/ProgrammersManual.html
+++ b/docs/ProgrammersManual.html
@@ -138,7 +138,8 @@ with another <tt>Value</tt></a> </li>
     <li><a href="#AbstractTypeUser">The AbstractTypeUser Class</a></li>
   </ul></li>
 
-  <li><a href="#SymbolTable">The <tt>ValueSymbolTable</tt> and <tt>TypeSymbolTable</tt> classes </a></li>
+  <li><a href="#SymbolTable">The <tt>ValueSymbolTable</tt> and <tt>TypeSymbolTable</tt> classes</a></li>
+  <li><a href="#UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a></li>
   </ul></li>
 
   <li><a href="#coreclasses">The Core LLVM Class Hierarchy Reference</a>
@@ -173,7 +174,8 @@ with another <tt>Value</tt></a> </li>
 <div class="doc_author">    
   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>, 
                 <a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a>, 
-                <a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a>, and
+                <a href="mailto:ggreif@gmail.com">Gabor Greif</a>, 
+                <a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a> and
                 <a href="mailto:rspencer@x10sys.com">Reid Spencer</a></p>
 </div>
 
@@ -2207,7 +2209,7 @@ names for types.</p>
 by most clients.  It should only be used when iteration over the symbol table 
 names themselves are required, which is very special purpose.  Note that not 
 all LLVM
-<a href="#Value">Value</a>s have names, and those without names (i.e. they have
+<tt><a href="#Value">Value</a></tt>s have names, and those without names (i.e. they have
 an empty name) do not exist in the symbol table.
 </p>
 
@@ -2223,7 +2225,184 @@ insert entries into the symbol table.</p>
 
 
 
-<!-- *********************************************************************** -->
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+  <a name="UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a>
+</div>
+
+<div class="doc_text">
+<p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1User.html">
+User</a></tt> class provides a base for expressing the ownership of <tt>User</tt>
+towards other <tt><a href="http://llvm.org/doxygen/classllvm_1_1Value.html">
+Value</a></tt>s. The <tt><a href="http://llvm.org/doxygen/classllvm_1_1Use.html">
+Use</a></tt> helper class is employed to do the bookkeeping and facilitate O(1)
+addition and removal.</p>
+
+<pre>
+   -----------------------------------------------------------------
+   --- Interaction and relationship between User and Use objects ---
+   -----------------------------------------------------------------
+
+
+A subclass of User can choose between incorporating its Use objects
+or refer to them out-of-line by means of a pointer. A mixed variant
+(some Uses inline others hung off) is impractical and breaks the invariant
+that the Use objects belonging to the same User form a contiguous array.
+
+We have 2 different layouts in the User (sub)classes:
+
+Layout a)
+The Use object(s) are inside (resp. at fixed offset) of the User
+object and there are a fixed number of them.
+
+Layout b)
+The Use object(s) are referenced by a pointer to an
+array from the User object and there may be a variable
+number of them.
+
+Initially each layout will possess a direct pointer to the
+start of the array of Uses. Though not mandatory for layout a),
+we stick to this redundancy for the sake of simplicity.
+The User object will also store the number of Use objects it
+has. (Theoretically this information can also be calculated
+given the scheme presented below.)
+
+Special forms of allocation operators (operator new)
+will enforce the following memory layouts:
+
+
+#  Layout a) will be modelled by prepending the User object
+#  by the Use[] array.
+#      
+#      ...---.---.---.---.-------...
+#        | P | P | P | P | User
+#      '''---'---'---'---'-------'''
+
+
+#  Layout b) will be modelled by pointing at the Use[] array.
+#      
+#      .-------...
+#      | User
+#      '-------'''
+#          |
+#          v
+#          .---.---.---.---...
+#          | P | P | P | P |
+#          '---'---'---'---'''
+
+   (In the above figures 'P' stands for the Use** that
+    is stored in each Use object in the member Use::Prev)
+
+
+Since the Use objects will be deprived of the direct pointer to
+their User objects, there must be a fast and exact method to
+recover it. This is accomplished by the following scheme:
+
+A bit-encoding in the 2 LSBits of the Use::Prev will allow to find the
+start of the User object:
+
+00 --> binary digit 0
+01 --> binary digit 1
+10 --> stop and calc (s)
+11 --> full stop (S)
+
+Given a Use*, all we have to do is to walk till we get
+a stop and we either have a User immediately behind or
+we have to walk to the next stop picking up digits
+and calculating the offset:
+
+.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
+| 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*)
+'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
+    |+15                |+10            |+6         |+3     |+1
+    |                   |               |           |       |__>
+    |                   |               |           |__________>
+    |                   |               |______________________>
+    |                   |______________________________________>
+    |__________________________________________________________>
+
+
+Only the significant number of bits need to be stored between the
+stops, so that the worst case is 20 memory accesses when there are
+1000 Use objects.
+
+The following literate Haskell fragment demonstrates the concept:
+
+> import Test.QuickCheck
+> 
+> digits :: Int -> [Char] -> [Char]
+> digits 0 acc = '0' : acc
+> digits 1 acc = '1' : acc
+> digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc
+> 
+> dist :: Int -> [Char] -> [Char]
+> dist 0 [] = ['S']
+> dist 0 acc = acc
+> dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r
+> dist n acc = dist (n - 1) $ dist 1 acc
+> 
+> takeLast n ss = reverse $ take n $ reverse ss
+> 
+> test = takeLast 40 $ dist 20 []
+> 
+
+Printing <test> gives: "1s100000s11010s10100s1111s1010s110s11s1S"
+
+The reverse algorithm computes the
+length of the string just by examining
+a certain prefix:
+
+> pref :: [Char] -> Int
+> pref "S" = 1
+> pref ('s':'1':rest) = decode 2 1 rest
+> pref (_:rest) = 1 + pref rest
+> 
+> decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest
+> decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
+> decode walk acc _ = walk + acc
+> 
+
+Now, as expected, printing <pref test> gives 40.
+
+We can quickCheck this with following property:
+
+> testcase = dist 2000 []
+> testcaseLength = length testcase
+> 
+> identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr
+>     where arr = takeLast n testcase
+
+As expected <quickCheck identityProp> gives:
+
+*Main> quickCheck identityProp
+OK, passed 100 tests.
+
+Let's be a bit more exhaustive:
+
+> 
+> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
+> 
+
+And here is the result of <deepCheck identityProp>:
+
+*Main> deepCheck identityProp
+OK, passed 500 tests.
+
+
+To maintain the invariant that the 2 LSBits of each Use** in Use
+never change after being set up, setters of Use::Prev must re-tag the
+new Use** on every modification. Accordingly getters must strip the
+tag bits.
+
+For layout b) instead of the User we will find a pointer (User* with LSBit set).
+Following this pointer brings us to the User. A portable trick will ensure
+that the first bytes of User (if interpreted as a pointer) will never have
+the LSBit set.
+</pre>
+
+</div>
+
+  <!-- *********************************************************************** -->
 <div class="doc_section">
   <a name="coreclasses">The Core LLVM Class Hierarchy Reference </a>
 </div>