diff options
| author | Stephen Hines <srhines@google.com> | 2015-03-23 12:10:34 -0700 |
|---|---|---|
| committer | Stephen Hines <srhines@google.com> | 2015-03-23 12:10:34 -0700 |
| commit | ebe69fe11e48d322045d5949c83283927a0d790b (patch) | |
| tree | c92f1907a6b8006628a4b01615f38264d29834ea /docs/Passes.rst | |
| parent | b7d2e72b02a4cb8034f32f8247a2558d2434e121 (diff) | |
| download | external_llvm-ebe69fe11e48d322045d5949c83283927a0d790b.zip external_llvm-ebe69fe11e48d322045d5949c83283927a0d790b.tar.gz external_llvm-ebe69fe11e48d322045d5949c83283927a0d790b.tar.bz2 | |
Update aosp/master LLVM for rebase to r230699.
Change-Id: I2b5be30509658cb8266be782de0ab24f9099f9b9
Diffstat (limited to 'docs/Passes.rst')
| -rw-r--r-- | docs/Passes.rst | 32 |
1 files changed, 16 insertions, 16 deletions
diff --git a/docs/Passes.rst b/docs/Passes.rst index 9f40092..cc0a853 100644 --- a/docs/Passes.rst +++ b/docs/Passes.rst @@ -891,17 +891,24 @@ calls, or transforming sets of stores into ``memset``\ s. This pass looks for equivalent functions that are mergable and folds them. -A hash is computed from the function, based on its type and number of basic -blocks. +Total-ordering is introduced among the functions set: we define comparison +that answers for every two functions which of them is greater. It allows to +arrange functions into the binary tree. -Once all hashes are computed, we perform an expensive equality comparison on -each function pair. This takes n^2/2 comparisons per bucket, so it's important -that the hash function be high quality. The equality comparison iterates -through each instruction in each basic block. +For every new function we check for equivalent in tree. -When a match is found the functions are folded. If both functions are -overridable, we move the functionality into a new internal function and leave -two overridable thunks to it. +If equivalent exists we fold such functions. If both functions are overridable, +we move the functionality into a new internal function and leave two +overridable thunks to it. + +If there is no equivalent, then we add this function to tree. + +Lookup routine has O(log(n)) complexity, while whole merging process has +complexity of O(n*log(n)). + +Read +:doc:`this <MergeFunctions>` +article for more details. ``-mergereturn``: Unify function exit nodes ------------------------------------------- @@ -1112,13 +1119,6 @@ useful when diffing the effect of an optimization because deleting an unnamed instruction can change all other instruction numbering, making the diff very noisy. -``-preverify``: Preliminary module verification ------------------------------------------------ - -Ensures that the module is in the form required by the :ref:`Module Verifier -<passes-verify>` pass. Running the verifier runs this pass automatically, so -there should be no need to use it directly. - .. _passes-verify: ``-verify``: Module Verifier |