diff options
| author | Stephen Hines <srhines@google.com> | 2015-04-01 18:49:24 +0000 |
|---|---|---|
| committer | Gerrit Code Review <noreply-gerritcodereview@google.com> | 2015-04-01 18:49:26 +0000 |
| commit | 3fa16bd6062e23bcdb82ed4dd965674792e6b761 (patch) | |
| tree | 9348fc507292f7e8715d22d64ce5a32131b4f875 /docs/Passes.rst | |
| parent | beed47390a60f6f0c77532b3d3f76bb47ef49423 (diff) | |
| parent | ebe69fe11e48d322045d5949c83283927a0d790b (diff) | |
| download | external_llvm-3fa16bd6062e23bcdb82ed4dd965674792e6b761.zip external_llvm-3fa16bd6062e23bcdb82ed4dd965674792e6b761.tar.gz external_llvm-3fa16bd6062e23bcdb82ed4dd965674792e6b761.tar.bz2 | |
Merge "Update aosp/master LLVM for rebase to r230699."
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 |