diff options
| author | Gabor Greif <ggreif@gmail.com> | 2008-06-16 21:06:12 +0000 |
|---|---|---|
| committer | Gabor Greif <ggreif@gmail.com> | 2008-06-16 21:06:12 +0000 |
| commit | 92e8776a5244172205550bcdeca8b116ba2195a3 (patch) | |
| tree | 48335f43fe07cd94c2a02c2e0af82b2c6976df70 | |
| parent | 0b228bf4315ee36f591046c309cb213f7c1197c0 (diff) | |
| download | external_llvm-92e8776a5244172205550bcdeca8b116ba2195a3.zip external_llvm-92e8776a5244172205550bcdeca8b116ba2195a3.tar.gz external_llvm-92e8776a5244172205550bcdeca8b116ba2195a3.tar.bz2 | |
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
| -rw-r--r-- | docs/ProgrammersManual.html | 187 | ||||
| -rw-r--r-- | include/llvm/User.h | 165 |
2 files changed, 183 insertions, 169 deletions
diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html index 716d364..f0f941f 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> diff --git a/include/llvm/User.h b/include/llvm/User.h index f1f4110..570f381 100644 --- a/include/llvm/User.h +++ b/include/llvm/User.h @@ -23,171 +23,6 @@ namespace llvm { -/*============================================================================== - - - ----------------------------------------------------------------- - --- 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. - -==============================================================================*/ - /// OperandTraits - Compile-time customization of /// operand-related allocators and accessors /// for use of the User class |