Refactor string encoding checks in BitcodeWriter (NFC)

[oota-llvm.git] / docs / Passes.rst

diff --git a/docs/Passes.rst b/docs/Passes.rst
index 9f4009297acaef7680a32e05b4ee7aed7a99f1f7..cc0a853bc4deb6a8839a8e1925d35add00e65a0f 100644 (file)
--- 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.
 
 
 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
 -------------------------------------------
 
 ``-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.
 
 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
 .. _passes-verify:
 
 ``-verify``: Module Verifier