aboutsummaryrefslogtreecommitdiffstats
path: root/docs/Passes.rst
diff options
context:
space:
mode:
Diffstat (limited to 'docs/Passes.rst')
-rw-r--r--docs/Passes.rst32
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