summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/IPO/MergeFunctions.cpp
Commit message (Collapse)AuthorAgeFilesLines
* MergeFunc: Quick fix for r245140, Ignore second, aka Function*, in sorting.NAKAMURA Takumi2015-08-161-1/+6
| | | | | | Don't assume second would be ordered in the module. llvm-svn: 245168
* Accelerate MergeFunctions with hashingJF Bastien2015-08-151-4/+99
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch makes the Merge Functions pass faster by calculating and comparing a hash value which captures the essential structure of a function before performing a full function comparison. The hash is calculated by hashing the function signature, then walking the basic blocks of the function in the same order as the main comparison function. The opcode of each instruction is hashed in sequence, which means that different functions according to the existing total order cannot have the same hash, as the comparison requires the opcodes of the two functions to be the same order. The hash function is a static member of the FunctionComparator class because it is tightly coupled to the exact comparison function used. For example, functions which are equivalent modulo a single variant callsite might be merged by a more aggressive MergeFunctions, and the hash function would need to be insensitive to these differences in order to exploit this. The hashing function uses a utility class which accumulates the values into an internal state using a standard bit-mixing function. Note that this is a different interface than a regular hashing routine, because the values to be hashed are scattered amongst the properties of a llvm::Function, not linear in memory. This scheme is fast because only one word of state needs to be kept, and the mixing function is a few instructions. The main runOnModule function first computes the hash of each function, and only further processes functions which do not have a unique function hash. The hash is also used to order the sorted function set. If the hashes differ, their values are used to order the functions, otherwise the full comparison is done. Both of these are helpful in speeding up MergeFunctions. Together they result in speedups of 9% for mysqld (a mostly C application with little redundancy), 46% for libxul in Firefox, and 117% for Chromium. (These are all LTO builds.) In all three cases, the new speed of MergeFunctions is about half that of the module verifier, making it relatively inexpensive even for large LTO builds with hundreds of thousands of functions. The same functions are merged, so this change is free performance. Author: jrkoenig Reviewers: nlewycky, dschuff, jfb Subscribers: llvm-commits, aemerson Differential revision: http://reviews.llvm.org/D11923 llvm-svn: 245140
* [IR] Add token typesDavid Majnemer2015-08-141-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This introduces the basic functionality to support "token types". The motivation stems from the need to perform operations on a Value whose provenance cannot be obscured. There are several applications for such a type but my immediate motivation stems from WinEH. Our personality routine enforces a single-entry - single-exit regime for cleanups. After several rounds of optimizations, we may be left with a terminator whose "cleanup-entry block" is not entirely clear because control flow has merged two cleanups together. We have experimented with using labels as operands inside of instructions which are not terminators to indicate where we came from but found that LLVM does not expect such exotic uses of BasicBlocks. Instead, we can use this new type to clearly associate the "entry point" and "exit point" of our cleanup. This is done by having the cleanuppad yield a Token and consuming it at the cleanupret. The token type makes it impossible to obscure or otherwise hide the Value, making it trivial to track the relationship between the two points. What is the burden to the optimizer? Well, it turns out we have already paid down this cost by accepting that there are certain calls that we are not permitted to duplicate, optimizations have to watch out for such instructions anyway. There are additional places in the optimizer that we will probably have to update but early examination has given me the impression that this will not be heroic. Differential Revision: http://reviews.llvm.org/D11861 llvm-svn: 245029
* De-constify pointers to Type since they can't be modified. NFCCraig Topper2015-08-011-2/+2
| | | | | | This was already done in most places a while ago. This just fixes the ones that crept in over time. llvm-svn: 243842
* MergeFunc: Transfer the callee's attributes when replacing a direct callerArnold Schwaighofer2015-07-211-0/+19
| | | | | | | | | | We insert a bitcast which obfuscates the getCalledFunction for the utility function which looks up attributes from the called function. Loosing ABI changing parameter attributes is a bad thing. rdar://21516488 llvm-svn: 242807
* Revert "MergeFuncs: Transfer the function parameter attributes to the call site"Arnold Schwaighofer2015-07-191-1/+0
| | | | | | | | It is okay to not transfer parameter attributes. This reverts commit r242558. llvm-svn: 242646
* MergeFuncs: Transfer the function parameter attributes to the call siteArnold Schwaighofer2015-07-171-0/+1
| | | | | | rdar://21516488 llvm-svn: 242558
* Fix mergefunc infinite loopJF Bastien2015-07-151-2/+6
| | | | | | | | | | | | | | | Self-referential constants containing references to a merged function no longer cause the MergeFunctions pass to infinite loop. Also adds a reproduction IR which would otherwise fail, which was isolated from a similar issue in Chromium. Author: jrkoenig Reviewers: nlewycky, jfb Subscribers: llvm-commits, nlewycky, jfb Differential Revision: http://reviews.llvm.org/D11208 llvm-svn: 242337
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* MergeFunctions: Don't replace a weak function use by another equivalent weak ↵Arnold Schwaighofer2015-06-091-15/+13
| | | | | | | | | | function We don't know whether the weak functions definition is the definitive definition. rdar://21303727 llvm-svn: 239422
* MergeFunctions: Fix gcc warning in conditionDenis Protivensky2015-06-091-2/+2
| | | | llvm-svn: 239391
* Fix unused variable warningArnold Schwaighofer2015-06-091-0/+1
| | | | llvm-svn: 239369
* MergeFunctions: Impose a total order on the replacement of functionsArnold Schwaighofer2015-06-091-1/+44
| | | | | | | | | | | | | We don't want to replace function A by Function B in one module and Function B by Function A in another module. If these functions are marked with linkonce_odr we would end up with a function stub calling B in one module and a function stub calling A in another module. If the linker decides to pick these two we will have two stubs calling each other. rdar://21265586 llvm-svn: 239367
* Replace push_back(Constructor(foo)) with emplace_back(foo) for non-trivial typesBenjamin Kramer2015-05-291-1/+1
| | | | | | | | | | | | | | | | | | | | If the type isn't trivially moveable emplace can skip a potentially expensive move. It also saves a couple of characters. Call sites were found with the ASTMatcher + some semi-automated cleanup. memberCallExpr( argumentCountIs(1), callee(methodDecl(hasName("push_back"))), on(hasType(recordDecl(has(namedDecl(hasName("emplace_back")))))), hasArgument(0, bindTemporaryExpr( hasType(recordDecl(hasNonTrivialDestructor())), has(constructExpr()))), unless(isInTemplateInstantiation())) No functional change intended. llvm-svn: 238602
* MergeFunctions: Two different sized allocas are *not* the sameArnold Schwaighofer2015-05-121-0/+9
| | | | llvm-svn: 237193
* [opaque pointer type] Pass GlobalAlias the actual pointer type rather than ↵David Blaikie2015-04-291-2/+1
| | | | | | | | | | | | | decomposing it into pointee type + address space Many of the callers already have the pointer type anyway, and for the couple of callers that don't it's pretty easy to call PointerType::get on the pointee type and address space. This avoids LLParser from using PointerType::getElementType when parsing GlobalAliases from IR. llvm-svn: 236160
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-31/+22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* Make DataLayout Non-Optional in the ModuleMehdi Amini2015-03-041-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: DataLayout keeps the string used for its creation. As a side effect it is no longer needed in the Module. This is "almost" NFC, the string is no longer canonicalized, you can't rely on two "equals" DataLayout having the same string returned by getStringRepresentation(). Get rid of DataLayoutPass: the DataLayout is in the Module The DataLayout is "per-module", let's enforce this by not duplicating it more than necessary. One more step toward non-optionality of the DataLayout in the module. Make DataLayout Non-Optional in the Module Module->getDataLayout() will never returns nullptr anymore. Reviewers: echristo Subscribers: resistor, llvm-commits, jholewinski Differential Revision: http://reviews.llvm.org/D7992 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231270
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-191-1/+1
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* MergeFunctions: FunctionPtr has been renamed to FunctionNode.Stepan Dyatkovskiy2014-09-101-7/+7
| | | | | | | It's supposed to store additional pass information for current function here. That was the reason for name change. llvm-svn: 217483
* Simplify creation of a bunch of ArrayRefs by using None, makeArrayRef or ↵Craig Topper2014-08-271-2/+2
| | | | | | just letting them be implicitly created. llvm-svn: 216525
* MergeFunctions, tiny refactoring:Stepan Dyatkovskiy2014-08-251-3/+3
| | | | | | cmpAPFloat has been renamed to cmpAPFloats (multiple form). llvm-svn: 216376
* MergeFunctions, tiny refactoring:Stepan Dyatkovskiy2014-08-251-5/+5
| | | | | | cmpAPInt has been renamed to cmpAPInts (multiple form). llvm-svn: 216375
* MergeFunctions, tiny refactoring:Stepan Dyatkovskiy2014-08-251-12/+11
| | | | | | cmpType has been renamed to cmpTypes (multiple form). llvm-svn: 216374
* MergeFunctions, tiny refactoring:Stepan Dyatkovskiy2014-08-251-5/+5
| | | | | | cmpGEP has been renamed to cmpGEPs (multiple form). llvm-svn: 216373
* MergeFunctions, tiny refactoring:Stepan Dyatkovskiy2014-07-311-4/+4
| | | | | | cmpOperation has been renamed to cmpOperations (multiple form). llvm-svn: 214392
* MergeFunc patch from Björn Steinbrink.Stepan Dyatkovskiy2014-07-151-2/+12
| | | | | | | Phabricator ticket: D4246, Don't merge functions with different range metadata on call/invoke. Thanks! llvm-svn: 213060
* MergeFunctions Pass, removed DenseMap helpers.Stepan Dyatkovskiy2014-06-221-104/+0
| | | | | | | | | | | Patch removes rest part of code related to old implementation. This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). This one was the final patch. llvm-svn: 211457
* MergeFunctions Pass, updated header comments.Stepan Dyatkovskiy2014-06-221-9/+47
| | | | | | | | | | Added short description for new comparison algorithm, that introduces total ordering among functions set. This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). llvm-svn: 211456
* MergeFunctions Pass, FnSet has been replaced with FnTree.Stepan Dyatkovskiy2014-06-211-37/+49
| | | | | | | | | | | | | | | | Patch activates new implementation. So from now, merging process should take time O(N*log(N)). Where N size of module (we are free to measure it in functions or in instructions). Internally FnTree represents binary tree. So every lookup operation takes O(log(N)) time. It is still not the last patch in series, we also have to clean-up pass from old code, and update pass comments. This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). llvm-svn: 211445
* MergeFunctions Pass, removed unused methods from old implementation.Stepan Dyatkovskiy2014-06-211-21/+0
| | | | | | | | | | | | | Patch removed next old FunctionComparator methods: * enumerate * isEquivalentOperation * isEquivalentGEP * isEquivalentType This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). llvm-svn: 211444
* MergeFunctions, doSanityCheck: fixed body comments.Stepan Dyatkovskiy2014-06-211-7/+5
| | | | llvm-svn: 211443
* MergeFunctions Pass, introduced sanity check, that checks order relation,Stepan Dyatkovskiy2014-06-211-0/+88
| | | | | | | | | introduced among functions set. This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). llvm-svn: 211442
* MergeFunctions Pass, introduced total ordering among top-level comparisonStepan Dyatkovskiy2014-06-211-79/+94
| | | | | | | | | | | | | methods. Patch changes return type of FunctionComparator::compare() and FunctionComparator::compare(const BasicBlock*, const BasicBlock*) methods from bool (equal or not) to {-1, 0, 1} (less, equal, great). This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). llvm-svn: 211437
* Commited patch from Björn Steinbrink:Stepan Dyatkovskiy2014-06-201-1/+6
| | | | | | | | | | | | Summary: Different range metadata can lead to different optimizations in later passes, possibly breaking the semantics of the merged function. So range metadata must be taken into consideration when comparing Load instructions. Thanks! llvm-svn: 211391
* IR: add "cmpxchg weak" variant to support permitted failure.Tim Northover2014-06-131-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit adds a weak variant of the cmpxchg operation, as described in C++11. A cmpxchg instruction with this modifier is permitted to fail to store, even if the comparison indicated it should. As a result, cmpxchg instructions must return a flag indicating success in addition to their original iN value loaded. Thus, for uniformity *all* cmpxchg instructions now return "{ iN, i1 }". The second flag is 1 when the store succeeded. At the DAG level, a new ATOMIC_CMP_SWAP_WITH_SUCCESS node has been added as the natural representation for the new cmpxchg instructions. It is a strong cmpxchg. By default this gets Expanded to the existing ATOMIC_CMP_SWAP during Legalization, so existing backends should see no change in behaviour. If they wish to deal with the enhanced node instead, they can call setOperationAction on it. Beware: as a node with 2 results, it cannot be selected from TableGen. Currently, no use is made of the extra information provided in this patch. Test updates are almost entirely adapting the input IR to the new scheme. Summary for out of tree users: ------------------------------ + Legacy Bitcode files are upgraded during read. + Legacy assembly IR files will be invalid. + Front-ends must adapt to different type for "cmpxchg". + Backends should be unaffected by default. llvm-svn: 210903
* Use create methods since msvc doesn't handle delegating constructors.Rafael Espindola2014-05-171-2/+2
| | | | llvm-svn: 209076
* Reduce abuse of default values in the GlobalAlias constructor.Rafael Espindola2014-05-171-2/+2
| | | | | | This is in preparation for adding an optional offset. llvm-svn: 209073
* Fix most of PR10367.Rafael Espindola2014-05-161-4/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch changes the design of GlobalAlias so that it doesn't take a ConstantExpr anymore. It now points directly to a GlobalObject, but its type is independent of the aliasee type. To avoid changing all alias related tests in this patches, I kept the common syntax @foo = alias i32* @bar to mean the same as now. The cases that used to use cast now use the more general syntax @foo = alias i16, i32* @bar. Note that GlobalAlias now behaves a bit more like GlobalVariable. We know that its type is always a pointer, so we omit the '*'. For the bitcode, a nice surprise is that we were writing both identical types already, so the format change is minimal. Auto upgrade is handled by looking through the casts and no new fields are needed for now. New bitcode will simply have different types for Alias and Aliasee. One last interesting point in the patch is that replaceAllUsesWith becomes smart enough to avoid putting a ConstantExpr in the aliasee. This seems better than checking and updating every caller. A followup patch will delete getAliasedGlobal now that it is redundant. Another patch will add support for an explicit offset. llvm-svn: 209007
* Change the GlobalAlias constructor to look a bit more like GlobalVariable.Rafael Espindola2014-05-161-2/+4
| | | | | | | This is part of the fix for pr10367. A GlobalAlias always has a pointer type, so just have the constructor build the type. llvm-svn: 208983
* MergeFunctions Pass, introduced total ordering among GEP operations.Stepan Dyatkovskiy2014-05-161-23/+41
| | | | | | | | | | Patch replaces old isEquivalentGEP implementation, and changes type of comparison result from bool (equal or not) to {-1, 0, 1} (less, equal, greater). This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). llvm-svn: 208976
* MergeFunctions Pass, introduced total ordering among operations.Stepan Dyatkovskiy2014-05-161-50/+135
| | | | | | | | | | Patch replaces old isEquivalentOperation implementation, and changes type of comparison result from bool (equal or not) to {-1, 0, 1} (less, equal, greater). This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). llvm-svn: 208973
* MergeFunctions Pass, introduced total ordering among function attributes.Stepan Dyatkovskiy2014-05-161-0/+36
| | | | | | | This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). llvm-svn: 208953
* MergeFunctions Pass, introduced total ordering among values.Stepan Dyatkovskiy2014-05-071-41/+96
| | | | | | | | | | | | | | | | | | | This is a third patch of patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). This patch description: Being comparing functions we need to compare values we meet at left and right sides. Its easy to sort things out for external values. It just should be the same value at left and right. But for local values (those were introduced inside function body) we have to ensure they were introduced at exactly the same place, and plays the same role. In short, patch introduces values serial numbering and comparison routine. The last one compares two values by their serial numbers. llvm-svn: 208189
* Second patch of patch series that improves MergeFunctions performance time ↵Stepan Dyatkovskiy2014-05-071-4/+278
| | | | | | | | | | | | | | | | | from O(N*N) to O(N*log(N)). The idea is to introduce total ordering among functions set. It allows to build binary tree and perform function look-up procedure in O(log(N)) time. This patch description: Introduced total ordering among constants implemented in cmpConstants method. Method performs lexicographical comparison between constants represented as hypothetical numbers of next format: <bitcastability-trait><raw-bit-contents> Please, read cmpConstants declaration comments for more details. llvm-svn: 208173
* [IPO/MergeFunctions] changes so it doesn't try to bitcast a struct return ↵Carlo Kok2014-04-301-1/+16
| | | | | | type but instead recreates it with insert/extract value. llvm-svn: 207679
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-3/+3
| | | | llvm-svn: 207196
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. llvm-svn: 206844
* MergeFunctions, cmpType: fixed variable names from XXTy1 and XXTy2 to XXTyL ↵Stepan Dyatkovskiy2014-03-141-29/+29
| | | | | | and XXTyR. llvm-svn: 203907
OpenPOWER on IntegriCloud