summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [SimplifyCFG] Fix for PR34219: Preserve alignment after merging conditional ↵Alexey Bataev2017-08-291-5/+30
| | | | | | | | | | | | | | | | | | stores. Summary: If SimplifyCFG pass is able to merge conditional stores into single one, it loses the alignment. This may lead to incorrect codegen. Patch sets the alignment of the new instruction if it is set in the original one. Reviewers: jmolloy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D36841 llvm-svn: 312030
* revert r310985 which breaks for the following case:Dehao Chen2017-08-271-2/+0
| | | | | | | | | | | | | | | | | | | | | struct string { ~string(); }; void f2(); void f1(int) { f2(); } void run(int c) { string body; while (true) { if (c) f1(c); else f1(c); } } Will recommit once the issue is fixed. llvm-svn: 311864
* Merge debug info when hoist then-else code to if.Dehao Chen2017-08-161-0/+2
| | | | | | | | | | | | | | Summary: When we move then-else code to if, we need to merge its debug info, otherwise the hoisted instruction may have inaccurate debug info attached. Reviewers: aprantl, probinson, dblaikie, echristo, loladiro Reviewed By: aprantl Subscribers: sanjoy, llvm-commits Differential Revision: https://reviews.llvm.org/D36778 llvm-svn: 310985
* [SimplifyCFG] Fix typo in comment. NFCCraig Topper2017-08-021-1/+1
| | | | llvm-svn: 309785
* [Value Tracking] Default argument to true and rename accordingly. NFC.Chad Rosier2017-08-011-2/+2
| | | | | | IMHO this is a bit more readable. llvm-svn: 309739
* [SimplifyCFG] Make the no-jump-tables attribute also disable switch lookup ↵Sumanth Gundapaneni2017-07-281-3/+6
| | | | | | | | tables Differential Revision: https://reviews.llvm.org/D35579 llvm-svn: 309444
* [SimplifyCFG] Defer folding unconditional branches to LateSimplifyCFG if it ↵Balaram Makam2017-07-191-7/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | can destroy canonical loop structure. Summary: When simplifying unconditional branches from empty blocks, we pre-test if the BB belongs to a set of loop headers and keep the block to prevent passes from destroying canonical loop structure. However, the current algorithm fails if the destination of the branch is a loop header. Especially when such a loop's latch block is folded into loop header it results in additional backedges and LoopSimplify turns it into a nested loop which prevent later optimizations from being applied (e.g., loop unrolling and loop interleaving). This patch augments the existing algorithm by further checking if the destination of the branch belongs to a set of loop headers and defer eliminating it if yes to LateSimplifyCFG. Fixes PR33605: https://bugs.llvm.org/show_bug.cgi?id=33605 Reviewers: efriedma, mcrosier, pacxx, hsung, davidxl Reviewed By: efriedma Subscribers: ashutosh.nema, gberry, javed.absar, llvm-commits Differential Revision: https://reviews.llvm.org/D35411 llvm-svn: 308422
* [SimplifyCFG] Move a portion of an if statement that should already be ↵Craig Topper2017-07-061-2/+2
| | | | | | | | | | | | | | | | implied to an assert Summary: In this code we got to Dom by following the predecessor link of BB. So it stands to reason that BB should also show up as a successor of Dom's terminator right? There isn't a way to have the CFG connect in only one direction is there? Reviewers: jmolloy, davide, mcrosier Reviewed By: mcrosier Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D35025 llvm-svn: 307276
* [SimplifyCFG] Update the name of switch generated lookup table.Sumanth Gundapaneni2017-06-301-4/+6
| | | | | | | | | | This patch appends the name of the function to the switch generated lookup table. This will ease the visual debugging in identifying the function the table is generated from. Differential Revision: https://reviews.llvm.org/D34817 llvm-svn: 306867
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-3/+2
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* [GVNSink] GVNSink passJames Molloy2017-05-251-47/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch provides an initial prototype for a pass that sinks instructions based on GVN information, similar to GVNHoist. It is not yet ready for commiting but I've uploaded it to gather some initial thoughts. This pass attempts to sink instructions into successors, reducing static instruction count and enabling if-conversion. We use a variant of global value numbering to decide what can be sunk. Consider: [ %a1 = add i32 %b, 1 ] [ %c1 = add i32 %d, 1 ] [ %a2 = xor i32 %a1, 1 ] [ %c2 = xor i32 %c1, 1 ] \ / [ %e = phi i32 %a2, %c2 ] [ add i32 %e, 4 ] GVN would number %a1 and %c1 differently because they compute different results - the VN of an instruction is a function of its opcode and the transitive closure of its operands. This is the key property for hoisting and CSE. What we want when sinking however is for a numbering that is a function of the *uses* of an instruction, which allows us to answer the question "if I replace %a1 with %c1, will it contribute in an equivalent way to all successive instructions?". The (new) PostValueTable class in GVN provides this mapping. This pass has some shown really impressive improvements especially for codesize already on internal benchmarks, so I have high hopes it can replace all the sinking logic in SimplifyCFG. Differential revision: https://reviews.llvm.org/D24805 llvm-svn: 303850
* [ValueTracking] Convert most of the calls to computeKnownBits to use the ↵Craig Topper2017-05-241-2/+1
| | | | | | | | | | version that returns the KnownBits object. This continues the changes started when computeSignBit was replaced with this new version of computeKnowBits. Differential Revision: https://reviews.llvm.org/D33431 llvm-svn: 303773
* [SimplifyCFG] Prevent a few APInt copies on method calls that return const ↵Craig Topper2017-05-221-2/+2
| | | | | | reference. NFCI llvm-svn: 303523
* [IR] De-virtualize ~Value to save a vptrReid Kleckner2017-05-181-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Implements PR889 Removing the virtual table pointer from Value saves 1% of RSS when doing LTO of llc on Linux. The impact on time was positive, but too noisy to conclusively say that performance improved. Here is a link to the spreadsheet with the original data: https://docs.google.com/spreadsheets/d/1F4FHir0qYnV0MEp2sYYp_BuvnJgWlWPhWOwZ6LbW7W4/edit?usp=sharing This change makes it invalid to directly delete a Value, User, or Instruction pointer. Instead, such code can be rewritten to a null check and a call Value::deleteValue(). Value objects tend to have their lifetimes managed through iplist, so for the most part, this isn't a big deal. However, there are some places where LLVM deletes values, and those places had to be migrated to deleteValue. I have also created llvm::unique_value, which has a custom deleter, so it can be used in place of std::unique_ptr<Value>. I had to add the "DerivedUser" Deleter escape hatch for MemorySSA, which derives from User outside of lib/IR. Code in IR cannot include MemorySSA headers or call the MemoryAccess object destructors without introducing a circular dependency, so we need some level of indirection. Unfortunately, no class derived from User may have any virtual methods, because adding a virtual method would break User::getHungOffOperands(), which assumes that it can find the use list immediately prior to the User object. I've added a static_assert to the appropriate OperandTraits templates to help people avoid this trap. Reviewers: chandlerc, mehdi_amini, pete, dberlin, george.burgess.iv Reviewed By: chandlerc Subscribers: krytarowski, eraman, george.burgess.iv, mzolotukhin, Prazek, nlewycky, hans, inglorion, pcc, tejohnson, dberlin, llvm-commits Differential Revision: https://reviews.llvm.org/D31261 llvm-svn: 303362
* [ConstantRange][SimplifyCFG] Add a helper method to allow SimplifyCFG to ↵Craig Topper2017-05-071-1/+1
| | | | | | | | | | determine if a ConstantRange has more than 8 elements without requiring an allocation if the ConstantRange is 64-bits wide. Previously SimplifyCFG used getSetSize which returns an APInt that is 1 bit wider than the ConstantRange's bit width. In the reasonably common case that the ConstantRange is 64-bits wide, this requires returning a 65-bit APInt. APInt's can only store 64-bits without a memory allocation so this is inefficient. The new method takes the 8 as an input and tells if the range contains more than that many elements without requiring any wider math. llvm-svn: 302385
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-281-3/+3
| | | | llvm-svn: 301673
* [ValueTracking] Introduce a KnownBits struct to wrap the two APInts for ↵Craig Topper2017-04-261-4/+5
| | | | | | | | | | | | | | | | computeKnownBits This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows us to treat them as more of a unit. Initially I've just altered the signatures of computeKnownBits and InstCombine's simplifyDemandedBits to pass a KnownBits reference instead of two separate APInt references. I'll do similar to the SelectionDAG version of computeKnownBits/simplifyDemandedBits as a separate patch. I've added a constructor that allows initializing both APInts to the same bit width with a starting value of 0. This reduces the repeated pattern of initializing both APInts. Once place default constructed the APInts so I added a default constructor for those cases. Going forward I would like to add more methods that will work on the pairs. For example trunc, zext, and sext occur on both APInts together in several places. We should probably add a clear method that can be used to clear both pieces. Maybe a method to check for conflicting information. A method to return (Zero|One) so we don't write it out everywhere. Maybe a method for (Zero|One).isAllOnesValue() to determine if all bits are known. I'm sure there are many other methods we can come up with. Differential Revision: https://reviews.llvm.org/D32376 llvm-svn: 301432
* [APInt] Use isSubsetOf, intersects, and bit counting methods to reduce ↵Craig Topper2017-04-251-1/+1
| | | | | | | | | | | | | | temporary APInts This patch uses various APInt methods to reduce temporary APInt creation. This should be all of the unrelated cleanups that got buried in D32376(creating a KnownBits struct) as well as some pointed out by Simon during the review of that. Plus a few improvements to use counting instead of masking. I've left out any places where we do something like (KnownZero & KnownOne) != 0 as I plan to add a helper method to KnownBits to ask that question and didn't want to thrash that code an additional time. Differential Revision: https://reviews.llvm.org/D32495 llvm-svn: 301338
* [SimplifyCFG] Fix for non-determinism in codegenMandeep Singh Grang2017-04-241-1/+1
| | | | | | | | | | | | | | Summary: This patch fixes issues in codegen uncovered due to https://reviews.llvm.org/D26718 Reviewers: majnemer, chenli, davide Reviewed By: davide Subscribers: davide, arsenm, llvm-commits Differential Revision: https://reviews.llvm.org/D26726 llvm-svn: 301222
* [SimplifyCFG] Fix the determination of PostBB in conditional store merging ↵Craig Topper2017-04-211-2/+10
| | | | | | | | | | to handle the targets on the second branch being commuted Currently we choose PostBB as the single successor of QFB, but its possible that QTB's single successor is QFB which would make QFB the correct choice. Differential Revision: https://reviews.llvm.org/D32323 llvm-svn: 300992
* [SimplifyCFG] Use hasNUses instead of comparing getNumUses to a constant."Craig Topper2017-04-171-1/+1
| | | | | | The use list is a linked list so getNumUses requires a linear scan through the whole list. hasNUses will stop scanning at N and see if that is the end. llvm-svn: 300505
* [IR] Redesign the case iterator in SwitchInst to actually be an iteratorChandler Carruth2017-04-121-33/+30
| | | | | | | | | | | | | | | | and to expose a handle to represent the actual case rather than having the iterator return a reference to itself. All of this allows the iterator to be used with common STL facilities, standard algorithms, etc. Doing this exposed some missing facilities in the iterator facade that I've fixed and required some work to the actual iterator to fully support the necessary API. Differential Revision: https://reviews.llvm.org/D31548 llvm-svn: 300032
* Split the SimplifyCFG pass into two variants.Joerg Sonnenberger2017-03-261-5/+14
| | | | | | | | | | | | | | | | | | | | | | | The first variant contains all current transformations except transforming switches into lookup tables. The second variant contains all current transformations. The switch-to-lookup-table conversion results in code that is more difficult to analyze and optimize by other passes. Most importantly, it can inhibit Dead Code Elimination. As such it is often beneficial to only apply this transformation very late. A common example is inlining, which can often result in range restrictions for the switch expression. Changes in execution time according to LNT: SingleSource/Benchmarks/Misc/fp-convert +3.03% MultiSource/Benchmarks/ASC_Sequoia/CrystalMk/CrystalMk -11.20% MultiSource/Benchmarks/Olden/perimeter/perimeter -10.43% and a couple of smaller changes. For perimeter it also results 2.6% a smaller binary. Differential Revision: https://reviews.llvm.org/D30333 llvm-svn: 298799
* [IR] Make SwitchInst::CaseIt almost a normal iterator.Chandler Carruth2017-03-261-8/+9
| | | | | | | | | | | | | | | | | | | | | | | | | This moves it to the iterator facade utilities giving it full random access semantics, etc. It can also now be used with standard algorithms like std::all_of and std::any_of and range adaptors like llvm::reverse. Also make the semantics of iterating match what every other iterator uses and forbid decrementing past the begin iterator. This was used as a hacky way to work around iterator invalidation. However, every instance trying to do this failed to actually avoid touching invalid iterators despite the clear documentation that the removed and all subsequent iterators become invalid including the end iterator. So I've added a return of the next iterator to removeCase and rewritten the loops that were doing this to correctly follow the iterator pattern of either incremneting or removing and assigning fresh values to the iterator and the end. In one case we were trying to go backwards to make this cleaner but it doesn't actually work. I've made that code match the code we use everywhere else to remove cases as we iterate. This changes the order of cases in one test output and I moved that test to CHECK-DAG so it wouldn't care -- the order isn't semantically meaningful anyways. llvm-svn: 298791
* Make GCC happy again.Benjamin Kramer2017-03-241-2/+1
| | | | llvm-svn: 298702
* Fix: Refactor SimplifyCFG:canSinkInstructions [NFC]Aditya Kumar2017-03-161-18/+17
| | | | | | Differential Revision: https://reviews.llvm.org/D30116 llvm-svn: 297955
* Revert "Refactor SimplifyCFG:canSinkInstructions [NFC]"Eric Liu2017-03-151-23/+23
| | | | | | This reverts commit r297839, which breaks Transforms/SimplifyCFG/sink-common-code.ll llvm-svn: 297845
* Refactor SimplifyCFG:canSinkInstructions [NFC]Aditya Kumar2017-03-151-23/+23
| | | | llvm-svn: 297839
* [SimplifyCFG] Use APInt::operator| instead of APInt::Or. NFCCraig Topper2017-03-051-1/+1
| | | | | | I'm looking to improve operator| to support rvalue references and may remove APInt::Or. llvm-svn: 296982
* SimplifyCFG: Register cloned assume intrinsics with assumption cache when ↵Peter Collingbourne2017-02-151-3/+10
| | | | | | | | creating critical edge. Differential Revision: https://reviews.llvm.org/D29976 llvm-svn: 295145
* [InstCombine] Merge DebugLoc when speculatively hoisting store instructionTaewook Oh2017-01-281-8/+11
| | | | | | | | | | | | | | Summary: Along with https://reviews.llvm.org/D27804, debug locations need to be merged when hoisting store instructions as well. Not sure if just dropping debug locations would make more sense for this case, but as the branch instruction will have at least different discriminator with the hoisted store instruction, I think there will be no difference in practice. Reviewers: aprantl, andreadb, danielcdh Reviewed By: aprantl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29062 llvm-svn: 293372
* [SimplifyCFG] Do not sink and merge inline-asm instructions.Akira Hatanaka2017-01-251-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Conservatively disable sinking and merging inline-asm instructions as doing so can potentially create arguments that cannot satisfy the inline-asm constraints. For example, SimplifyCFG used to do the following transformation: (before) if.then: %0 = call i32 asm "rorl $2, $0", "=&r,0,n"(i32 %r6, i32 8) br label %if.end if.else: %1 = call i32 asm "rorl $2, $0", "=&r,0,n"(i32 %r6, i32 6) br label %if.end (after) %.sink = select i1 %tobool, i32 6, i32 8 %0 = call i32 asm "rorl $2, $0", "=&r,0,n"(i32 %r6, i32 %.sink) This would result in a crash in the backend since only immediate integer operands are permitted for constraint "n". rdar://problem/30110806 Differential Revision: https://reviews.llvm.org/D29111 llvm-svn: 293025
* Tweak ASCII art in Simplify CFG. NFCAmaury Sechet2017-01-231-1/+1
| | | | llvm-svn: 292792
* [DebugInfo] Remove redundant check in SimplifyCFG; NFC.Robert Lougher2017-01-121-4/+3
| | | | llvm-svn: 291813
* [DebugInfo] DILocation variable declaration should be const; NFC.Robert Lougher2017-01-121-1/+1
| | | | llvm-svn: 291787
* Reapply "[SimplifyCFG] In sinkLastInstruction correctly set debugloc of ↵Robert Lougher2017-01-041-1/+9
| | | | | | | | | | | | | | | | | | | | common inst" This reapplies r289828 (reverted in r289833 as it broke the address sanitizer). The debugloc is now only set when the instruction is not a call, as this causes the verifier to assert (the inliner requires an inlinable callsite to have a debug loc if the caller and callee have debug info). Original commit message: Simplify CFG will try to sink the last instruction in a series of basic blocks, creating a "common" instruction in the successor block (sinkLastInstruction). When it does this, the debug location of the single instruction should be the merged debug locations of the commoned instructions. Original review: https://reviews.llvm.org/D27590 llvm-svn: 290973
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-36/+39
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Preserve loop metadata when folding branches to a common destination.Michael Kuperstein2016-12-161-0/+5
| | | | | | Differential Revision: https://reviews.llvm.org/D27830 llvm-svn: 289992
* [SimplifyCFG] Merge debug locations when hoisting an instruction from a ↵Andrea Di Biagio2016-12-151-4/+4
| | | | | | | | | | | | | | | | | then/else branch. NFC. Now that a new API to merge debug locations has been committed at r289661 (see review D26256 for more details), we can use it to "improve" the code added by revision r280995. Instead of nulling the debugloc of a commoned instruction, we use the 'merged' debug location. At the moment, this is just a no functional change since function `DILocation::getMergedLocation()` is just a stub and would always return a null location. Differential Revision: https://reviews.llvm.org/D27804 llvm-svn: 289862
* Revert "[SimplifyCFG] In sinkLastInstruction correctly set debugloc of ↵Robert Lougher2016-12-151-8/+1
| | | | | | | | common inst" Reverting as it is causing buildbot failures (address sanitizer). llvm-svn: 289833
* [SimplifyCFG] In sinkLastInstruction correctly set debugloc of "common" inst Robert Lougher2016-12-151-1/+9
| | | | | | | | | | | Simplify CFG will try to sink the last instruction in a series of basic blocks, creating a "common" instruction in the successor block (sinkLastInstruction). When it does this, the debug location of the single instruction should be the merged debug locations of the commoned instructions. Differential Revision: https://reviews.llvm.org/D27590 llvm-svn: 289828
* Remove the AssumptionCacheHal Finkel2016-12-151-39/+36
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* IR: Change the gep_type_iterator API to avoid always exposing the "current" ↵Peter Collingbourne2016-12-021-1/+1
| | | | | | | | | | | | | type. Instead, expose whether the current type is an array or a struct, if an array what the upper bound is, and if a struct the struct type itself. This is in preparation for a later change which will make PointerType derive from Type rather than SequentialType. Differential Revision: https://reviews.llvm.org/D26594 llvm-svn: 288458
* Fix some Clang-tidy and Include What You Use warnings; other minor fixes (NFC).Eugene Zelenko2016-11-301-11/+46
| | | | | | This preparation to remove SetVector.h dependency on SmallSet.h. llvm-svn: 288256
* Ignore debug info when making optimization decisions in SimplifyCFG.Dehao Chen2016-10-171-11/+18
| | | | | | | | | | | | Summary: Debug info should *not* affect code generation. This patch properly handles debug info to make sure the generated code are the same with or without debug info. Reviewers: davidxl, mzolotukhin, jmolloy Subscribers: aprantl, llvm-commits Differential Revision: https://reviews.llvm.org/D25286 llvm-svn: 284415
* [SimplifyCFG] Don't lower complex ConstantExprs to lookup tablesOliver Stannard2016-10-171-1/+4
| | | | | | | | | | Not all ConstantExprs can be represented by a global variable, for example most pointer arithmetic other than addition of a constant, so we can't convert these values from switch statements to lookup tables. Differential Revision: https://reviews.llvm.org/D25550 llvm-svn: 284379
* [SimplifyCFG] Use the error checking provided by getPrevNode.Benjamin Kramer2016-10-151-7/+11
| | | | | | | | | BasicBlock::size is O(insts), making this loop O(blocks*insts), which can be really slow on generated code. getPrevNode already checks if we're at the beginning of the block and returns nullptr if so, just use that instead. No functionality change intended. llvm-svn: 284303
* [SimplifyCFG] Don't create PHI nodes for constant bundle operandsSanjoy Das2016-10-121-1/+10
| | | | | | | | | | | | | | | | | | | | Summary: Constant bundle operands may need to retain their constant-ness for correctness. I'll admit that this is slightly odd, but it looks like SimplifyCFG already does this for things like @llvm.frameaddress and @llvm.stackmap, so I suppose adding one more case is not a big deal. It is possible to add a mechanism to denote bundle operands that need to remain constants, but that's probably too complicated for the time being. Reviewers: jmolloy Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D25502 llvm-svn: 284028
* [ARM] Don't convert switches to lookup tables of pointers with ROPI/RWPIOliver Stannard2016-10-071-17/+27
| | | | | | | | | | | | With the ROPI and RWPI relocation models we can't always have pointers to global data or functions in constant data, so don't try to convert switches into lookup tables if any value in the lookup table would require a relocation. We can still safely emit lookup tables of other values, such as simple constants. Differential Revision: https://reviews.llvm.org/D24462 llvm-svn: 283530
* [SimplifyCFG] Correctly test for unconditional branches in GetCaseResultsDavid Majnemer2016-10-071-1/+1
| | | | | | | | | | | GetCaseResults assumed that a terminator with one successor was an unconditional branch. This is not necessarily the case, it could be a cleanupret. Strengthen the check by querying whether or not the terminator is exceptional. llvm-svn: 283517
OpenPOWER on IntegriCloud