From ebe69fe11e48d322045d5949c83283927a0d790b Mon Sep 17 00:00:00 2001 From: Stephen Hines Date: Mon, 23 Mar 2015 12:10:34 -0700 Subject: Update aosp/master LLVM for rebase to r230699. Change-Id: I2b5be30509658cb8266be782de0ab24f9099f9b9 --- docs/Passes.rst | 32 ++++++++++++++++---------------- 1 file changed, 16 insertions(+), 16 deletions(-) (limited to 'docs/Passes.rst') 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 ` +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 -- cgit v1.1