summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms
Commit message (Collapse)AuthorAgeFilesLines
...
* [RewriteStatepointsForGC] Further style/naming fixup [NFCI]Philip Reames2015-09-101-26/+26
| | | | llvm-svn: 247217
* Fix Clang-tidy misc-use-override warnings, other minor fixesHans Wennborg2015-09-101-4/+3
| | | | | | | | Patch by Eugene Zelenko! Differential Revision: http://reviews.llvm.org/D12740 llvm-svn: 247216
* [RewriteStatepointsForGC] More naming cleanup [NFCI]Philip Reames2015-09-101-6/+6
| | | | llvm-svn: 247213
* [RewriteStatepointsForGC] Code cleanup [NFC]Philip Reames2015-09-091-25/+26
| | | | | | Factor out common code related to naming values, fix a small style issue. More to follow in separate changes. llvm-svn: 247211
* [RewriteStatepointsForGC] Extend base pointer inference to handle insertelementPhilip Reames2015-09-091-58/+61
| | | | | | | | | | | | This change is simply enhancing the existing inference algorithm to handle insertelement instructions by conservatively inserting a new instruction to propagate the vector of associated base pointers. In the process, I'm ripping out the peephole optimizations which mostly helped cover the fact this hadn't been done. Note that most of the newly inserted nodes will be nearly immediately removed by the post insertion optimization pass introduced in 246718. Arguably, we should be trying harder to avoid the malloc traffic here, but I'd rather get the code correct, then worry about compile time. Unlike previous extensions of the algorithm to handle more case, I discovered the existing code was causing miscompiles in some cases. In particular, we had an implicit assumption that the peephole covered *all* insert element instructions, so if we had a value directly based on a insert element the peephole didn't cover, we proceeded as if it were a base anyways. Not good. I believe we had the same issue with shufflevector which is why I adjusted the predicate for them as well. Differential Revision: http://reviews.llvm.org/D12583 llvm-svn: 247210
* [RewriteStatepointsForGC] Make base pointer inference deterministicPhilip Reames2015-09-091-44/+35
| | | | | | | | | | | | | | Previously, the base pointer algorithm wasn't deterministic. The core fixed point was (of course), but we were inserting new nodes and optimizing them in an order which was unspecified and variable. We'd somewhat hacked around this for testing by sorting by value name, but that doesn't solve the general determinism problem. Instead, we can use the order of traversal over the def/use graph to give us a single consistent ordering. Today, this is a DFS order, but the exact order doesn't mater provided it's deterministic for a given input. (Q: It is safe to rely on a deterministic order of operands right?) Note that this only fixes the determinism within a single inference step. The inference step is currently invoked many times in a non-deterministic order. That's a future change in the sequence. :) Differential Revision: http://reviews.llvm.org/D12640 llvm-svn: 247208
* LowerBitSets: Fix non-determinism bug.Peter Collingbourne2015-09-091-4/+22
| | | | | | | | Visit disjoint sets in a deterministic order based on the maximum BitSetNM index, otherwise the order in which we visit them will depend on pointer comparisons. This was being exposed by MSan. llvm-svn: 247201
* Revert trunc(lshr (sext A), Cst) to ashr A, CstDavid Majnemer2015-09-091-20/+0
| | | | | | This reverts commit r246997, it introduced a regression (PR24763). llvm-svn: 247180
* [PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatibleChandler Carruth2015-09-0934-131/+230
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | with the new pass manager, and no longer relying on analysis groups. This builds essentially a ground-up new AA infrastructure stack for LLVM. The core ideas are the same that are used throughout the new pass manager: type erased polymorphism and direct composition. The design is as follows: - FunctionAAResults is a type-erasing alias analysis results aggregation interface to walk a single query across a range of results from different alias analyses. Currently this is function-specific as we always assume that aliasing queries are *within* a function. - AAResultBase is a CRTP utility providing stub implementations of various parts of the alias analysis result concept, notably in several cases in terms of other more general parts of the interface. This can be used to implement only a narrow part of the interface rather than the entire interface. This isn't really ideal, this logic should be hoisted into FunctionAAResults as currently it will cause a significant amount of redundant work, but it faithfully models the behavior of the prior infrastructure. - All the alias analysis passes are ported to be wrapper passes for the legacy PM and new-style analysis passes for the new PM with a shared result object. In some cases (most notably CFL), this is an extremely naive approach that we should revisit when we can specialize for the new pass manager. - BasicAA has been restructured to reflect that it is much more fundamentally a function analysis because it uses dominator trees and loop info that need to be constructed for each function. All of the references to getting alias analysis results have been updated to use the new aggregation interface. All the preservation and other pass management code has been updated accordingly. The way the FunctionAAResultsWrapperPass works is to detect the available alias analyses when run, and add them to the results object. This means that we should be able to continue to respect when various passes are added to the pipeline, for example adding CFL or adding TBAA passes should just cause their results to be available and to get folded into this. The exception to this rule is BasicAA which really needs to be a function pass due to using dominator trees and loop info. As a consequence, the FunctionAAResultsWrapperPass directly depends on BasicAA and always includes it in the aggregation. This has significant implications for preserving analyses. Generally, most passes shouldn't bother preserving FunctionAAResultsWrapperPass because rebuilding the results just updates the set of known AA passes. The exception to this rule are LoopPass instances which need to preserve all the function analyses that the loop pass manager will end up needing. This means preserving both BasicAAWrapperPass and the aggregating FunctionAAResultsWrapperPass. Now, when preserving an alias analysis, you do so by directly preserving that analysis. This is only necessary for non-immutable-pass-provided alias analyses though, and there are only three of interest: BasicAA, GlobalsAA (formerly GlobalsModRef), and SCEVAA. Usually BasicAA is preserved when needed because it (like DominatorTree and LoopInfo) is marked as a CFG-only pass. I've expanded GlobalsAA into the preserved set everywhere we previously were preserving all of AliasAnalysis, and I've added SCEVAA in the intersection of that with where we preserve SCEV itself. One significant challenge to all of this is that the CGSCC passes were actually using the alias analysis implementations by taking advantage of a pretty amazing set of loop holes in the old pass manager's analysis management code which allowed analysis groups to slide through in many cases. Moving away from analysis groups makes this problem much more obvious. To fix it, I've leveraged the flexibility the design of the new PM components provides to just directly construct the relevant alias analyses for the relevant functions in the IPO passes that need them. This is a bit hacky, but should go away with the new pass manager, and is already in many ways cleaner than the prior state. Another significant challenge is that various facilities of the old alias analysis infrastructure just don't fit any more. The most significant of these is the alias analysis 'counter' pass. That pass relied on the ability to snoop on AA queries at different points in the analysis group chain. Instead, I'm planning to build printing functionality directly into the aggregation layer. I've not included that in this patch merely to keep it smaller. Note that all of this needs a nearly complete rewrite of the AA documentation. I'm planning to do that, but I'd like to make sure the new design settles, and to flesh out a bit more of what it looks like in the new pass manager first. Differential Revision: http://reviews.llvm.org/D12080 llvm-svn: 247167
* don't repeat function names in comments; NFCSanjay Patel2015-09-094-33/+27
| | | | llvm-svn: 247154
* function names start with a lower case letter; NFCSanjay Patel2015-09-091-54/+54
| | | | llvm-svn: 247150
* don't repeat function names in comments; NFCSanjay Patel2015-09-091-35/+32
| | | | llvm-svn: 247148
* Rename ExitCount to BackedgeTakenCount, because that's what it is.James Molloy2015-09-091-8/+9
| | | | | | We called a variable ExitCount, stored the backedge count in it, then redefined it to be the exit count again. llvm-svn: 247140
* Delay predication of stores until near the end of vector code generationJames Molloy2015-09-091-56/+28
| | | | | | | | Predicating stores requires creating extra blocks. It's much cleaner if we do this in one pass instead of mutating the CFG while writing vector instructions. Besides which we can make use of helper functions to update domtree for us, reducing the work we need to do. llvm-svn: 247139
* Fix a typo I spotted when hacking on SROA. Somewhat alarming thatChandler Carruth2015-09-091-1/+1
| | | | | | nothing broke. llvm-svn: 247127
* [IRCE] Add INITIALIZE_PASS_DEPENDENCY invocations.Sanjoy Das2015-09-091-2/+9
| | | | | | IRCE was just using INITIALIZE_PASS(), which is incorrect. llvm-svn: 247122
* Re-apply r247080 with order of evaluation fix.Peter Collingbourne2015-09-081-127/+406
| | | | llvm-svn: 247095
* Revert r247080, "LowerBitSets: Extend pass to support functions as bitsetPeter Collingbourne2015-09-081-406/+127
| | | | | | members." as it causes test failures on a number of bots. llvm-svn: 247088
* LowerBitSets: Extend pass to support functions as bitset members.Peter Collingbourne2015-09-081-127/+406
| | | | | | | | | | | | | | This change extends the bitset lowering pass to support bitsets that may contain either functions or global variables. A function bitset is lowered to a jump table that is laid out before one of the functions in the bitset. Also add support for non-string bitset identifier names. This allows for distinct metadata nodes to stand in for names with internal linkage, as done in D11857. Differential Revision: http://reviews.llvm.org/D11856 llvm-svn: 247080
* refactor matches for De Morgan's Laws; NFCISanjay Patel2015-09-081-17/+32
| | | | llvm-svn: 247061
* remove function names from comments; NFCSanjay Patel2015-09-081-49/+45
| | | | llvm-svn: 247043
* There is a trunc(lshr (zext A), Cst) optimization in InstCombineCasts thatJakub Kuderski2015-09-081-0/+20
| | | | | | | | | | | removes cast by performing the lshr on smaller types. However, currently there is no trunc(lshr (sext A), Cst) variant. This patch add such optimization by transforming trunc(lshr (sext A), Cst) to ashr A, Cst. Differential Revision: http://reviews.llvm.org/D12520 llvm-svn: 246997
* Prune utf8 chars in comments.NAKAMURA Takumi2015-09-071-1/+1
| | | | llvm-svn: 246953
* [InstCombine] Don't divide by zero when evaluating a potential transformDavid Majnemer2015-09-061-0/+8
| | | | | | | | | | Trivial multiplication by zero may survive the worklist. We tried to reassociate the multiplication with a division instruction, causing us to divide by zero; bail out instead. This fixes PR24726. llvm-svn: 246939
* [InstCombine] Don't assume m_Mul gives back an InstructionDavid Majnemer2015-09-051-1/+3
| | | | | | This fixes PR24713. llvm-svn: 246933
* Fix build warning.Craig Topper2015-09-051-1/+1
| | | | llvm-svn: 246908
* Fix build warningAndrew Kaylor2015-09-051-2/+2
| | | | llvm-svn: 246903
* Fix build warningAndrew Kaylor2015-09-041-4/+0
| | | | llvm-svn: 246899
* [WinEH] Teach SimplfyCFG to eliminate empty cleanup pads.Andrew Kaylor2015-09-041-20/+201
| | | | | | Differential Revision: http://reviews.llvm.org/D12434 llvm-svn: 246896
* Remove two unused includes and C++11 rangify for loops.Yaron Keren2015-09-041-15/+12
| | | | llvm-svn: 246865
* [RewriteStatepointsForGC] Extract common code, comment, and fix a build ↵Philip Reames2015-09-031-55/+48
| | | | | | warning [NFC] llvm-svn: 246810
* [RewriteStatepointsForGC] Strengthen invariants around BDVsPhilip Reames2015-09-031-29/+65
| | | | | | | | | | As a first step towards a new implementation of the base pointer inference algorithm, introduce an abstraction for BDVs, strengthen the assertions around them, and rewrite the BDV relation code in terms of the abstraction which includes an explicit notion of whether the BDV is also a base. The later is motivated by the fact we had a bug where insertelement was always assumed to be a base pointer even though the BDV code knew it wasn't. The strengthened assertions in this patch would have caught that bug. The next step will be to separate the DefiningValueMap into a BDV use list cache (entirely within findBasePointers) and a base pointer cache. Having the former will allow me to use a deterministic visit order when visiting BDVs in the inference algorithm and remove a bunch of ordering related hacks. Before actually doing the last step, I'm likely going to extend the lattice with a 'BaseN' (seen only base inputs) state so that I can kill the post process optimization step. Phabricator Revision: http://reviews.llvm.org/D12608 llvm-svn: 246809
* [RewriteStatepointsForGC] Workaround a lack of determinism in visit orderPhilip Reames2015-09-031-4/+9
| | | | | | | | The visit order being used in the base pointer inference algorithm is currently non-deterministic. When working on http://reviews.llvm.org/D12583, I discovered that we were relying on a peephole optimization to get deterministic ordering in one of the test cases. This change is intented to let me test and land http://reviews.llvm.org/D12583. The current code will not be long lived. I'm starting to investigate a rewrite of the algorithm which will combine the post-process step into the initial algorithm and make the visit order determistic. Before doing that, I wanted to make sure the existing code was complete and the test were stable. Hopefully, patches should be up for review for the new algorithm this week or early next. llvm-svn: 246801
* [sancov] Disable sanitizer coverage on functions using SEHReid Kleckner2015-09-031-0/+7
| | | | | | | Splitting basic blocks really messes up WinEHPrepare. We can remove this change when SEH uses the new EH IR. llvm-svn: 246799
* [WinEH] Add cleanupendpad instructionJoseph Tremoulet2015-09-032-0/+11
| | | | | | | | | | | | | | | | | | | | | | | Summary: Add a `cleanupendpad` instruction, used to mark exceptional exits out of cleanups (for languages/targets that can abort a cleanup with another exception). The `cleanupendpad` instruction is similar to the `catchendpad` instruction in that it is an EH pad which is the target of unwind edges in the handler and which itself has an unwind edge to the next EH action. The `cleanupendpad` instruction, similar to `cleanupret` has a `cleanuppad` argument indicating which cleanup it exits. The unwind successors of a `cleanuppad`'s `cleanupendpad`s must agree with each other and with its `cleanupret`s. Update WinEHPrepare (and docs/tests) to accomodate `cleanupendpad`. Reviewers: rnk, andrew.w.kaylor, majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12433 llvm-svn: 246751
* [MergeFuncs] Efficiently defer functions on mergeJF Bastien2015-09-021-28/+34
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch introduces a side table in Merge Functions to efficiently remove functions from the function set when functions they refer to are merged. Previously these functions would need to be compared lg(N) times to find the appropriate FunctionNode in the tree to defer. With the recent determinism changes, this comparison is more expensive. In addition, the removal function would not always actually remove the function from the set (i.e. after remove(F), there would sometimes still be a node in the tree which contains F). With these changes, these functions are properly deferred, and so more functions can be merged. In addition, when there are many merged functions (and thus more deferred functions), there is a speedup: chromium: 48678 merged -> 49380 merged; 6.58s -> 5.49s libxul.so: 41004 merged -> 41030 merged; 8.02s -> 6.94s mysqld: 1607 merged -> 1607 merged (same); 0.215s -> 0.212s (probably noise) Author: jrkoenig Reviewers: jfb, dschuff Subscribers: llvm-commits, nlewycky Differential revision: http://reviews.llvm.org/D12537 llvm-svn: 246735
* [RewriteStatepointsForGC] Delete stale comment [NFC]Philip Reames2015-09-021-3/+0
| | | | llvm-svn: 246722
* [RewriteStatepointsForGC] Pull a function out of anon namespace [NFC]Philip Reames2015-09-021-1/+5
| | | | | | Thanks to David Blaikie for noticing in previous commit. llvm-svn: 246721
* [RewriteStatepointsForGC] Bugfix for change 246133Philip Reames2015-09-021-16/+16
| | | | | | | | Fix a bug in change 246133. I didn't handle the case where we had a cycle in the use graph and could add an instruction we were about to erase back on to the worklist. Oddly, I have not been able to write a small test case for this, even with the AssertingVH added. I have confirmed the basic theory for the fix on a large failing example, but all attempts to reduce that to something appropriate for a test case have failed. Differential Revision: http://reviews.llvm.org/D12575 llvm-svn: 246718
* Fix release build warning for unused functionPhilip Reames2015-09-021-1/+2
| | | | llvm-svn: 246717
* [RewriteStatepointsForGC] Improve debug output [NFC]Philip Reames2015-09-021-30/+36
| | | | llvm-svn: 246713
* assuem(X) handling in GVN bugfixPiotr Padlewski2015-09-021-1/+20
| | | | | | | | | | There was infinite loop because it was trying to change assume(true) into assume(true) Also added handling when assume(false) appear http://reviews.llvm.org/D12516 llvm-svn: 246697
* Constant propagation after hitting assume(cmp) bugfixPiotr Padlewski2015-09-022-9/+46
| | | | | | | | | Last time code run into assertion `BBE.isSingleEdge()` in lib/IR/Dominators.cpp:200. http://reviews.llvm.org/D12170 llvm-svn: 246696
* Constant propagation after hiting llvm.assumePiotr Padlewski2015-09-021-3/+68
| | | | | | | | | | | After hitting @llvm.assume(X) we can: - propagate equality that X == true - if X is icmp/fcmp (with eq operation), and one of operand is constant we can change all variables with constants in the same BasicBlock http://reviews.llvm.org/D11918 llvm-svn: 246695
* [RemoveDuplicatePHINodes] Start over after removing a PHI.Benjamin Kramer2015-09-021-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This makes RemoveDuplicatePHINodes more effective and fixes an assertion failure. Triggering the assertions requires a DenseSet reallocation so this change only contains a constructive test. I'll explain the issue with a small example. In the following function there's a duplicate PHI, %4 and %5 are identical. When this is found the DenseSet in RemoveDuplicatePHINodes contains %2, %3 and %4. define void @F() { br label %1 ; <label>:1 ; preds = %1, %0 %2 = phi i32 [ 42, %0 ], [ %4, %1 ] %3 = phi i32 [ 42, %0 ], [ %5, %1 ] %4 = phi i32 [ 42, %0 ], [ 23, %1 ] %5 = phi i32 [ 42, %0 ], [ 23, %1 ] br label %1 } after RemoveDuplicatePHINodes runs the function looks like this. %3 has changed and is now identical to %2, but RemoveDuplicatePHINodes never saw this. define void @F() { br label %1 ; <label>:1 ; preds = %1, %0 %2 = phi i32 [ 42, %0 ], [ %4, %1 ] %3 = phi i32 [ 42, %0 ], [ %4, %1 ] %4 = phi i32 [ 42, %0 ], [ 23, %1 ] br label %1 } If the DenseSet does a reallocation now it will reinsert all keys and stumble over %3 now having a different hash value than it had when inserted into the map for the first time. This change clears the set whenever a PHI is deleted and starts the progress from the beginning, allowing %3 to be deleted and avoiding inconsistent DenseSet state. This potentially has a negative performance impact because it rescans all PHIs, but I don't think that this ever makes a difference in practice. llvm-svn: 246694
* [LV] Don't bail to MiddleBlock if a runtime check fails, bail to ScalarPH ↵James Molloy2015-09-021-60/+27
| | | | | | | | | | instead We were bailing to two places if our runtime checks failed. If the initial overflow check failed, we'd go to ScalarPH. If any other check failed, we'd go to MiddleBlock. This caused us to have to have an extra PHI per induction and reduction as the vector loop's exit block was not dominated by its latch. There's no need to have this behavior - if we just always go to ScalarPH we can get rid of a bunch of complexity. llvm-svn: 246637
* [LV] Move some code around slightly to make the intent of the function more ↵James Molloy2015-09-021-3/+1
| | | | | | | | clear. NFC. llvm-svn: 246636
* [LV] Cleanup: Sink an IRBuilder closer to its uses.James Molloy2015-09-021-10/+5
| | | | | | NFC. llvm-svn: 246635
* [LV] Refactor all runtime check emissions into helper functions.James Molloy2015-09-021-100/+126
| | | | | | | | This reduces the complexity of createEmptyBlock() and will open the door to further refactoring. The test change is simply because we're now constant folding a trivial test. llvm-svn: 246634
* [LV] Pull creation of trip counts into a helper function.James Molloy2015-09-021-63/+101
| | | | | | ... and do a tad of tidyup while we're at it. Because StartIdx must now be zero, there's no difference between Count and EndIdx. llvm-svn: 246633
OpenPOWER on IntegriCloud