X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=docs%2FPasses.rst;h=cc0a853bc4deb6a8839a8e1925d35add00e65a0f;hb=daaec40323619188f16f744af624de4b30755f56;hp=9f4009297acaef7680a32e05b4ee7aed7a99f1f7;hpb=e5d8481310415d60ec64d6283aeaa4ee1ed7089b;p=oota-llvm.git diff --git a/docs/Passes.rst b/docs/Passes.rst index 9f4009297ac..cc0a853bc4d 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 ` +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 -` pass. Running the verifier runs this pass automatically, so -there should be no need to use it directly. - .. _passes-verify: ``-verify``: Module Verifier