summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* SimplifyCFG: Don't assume non-null ScalarTargetTransformInfo.Hans Wennborg2012-11-161-1/+2
| | | | | | Patch by Pekka Jääskeläinen! llvm-svn: 168176
* misspellAndrew Trick2012-11-151-3/+3
| | | | llvm-svn: 168058
* whitespaceAndrew Trick2012-11-151-4/+4
| | | | llvm-svn: 168057
* Only do switch-to-lookup table transformation when TargetTransformInfoHans Wennborg2012-11-071-1/+2
| | | | | | is available. llvm-svn: 167552
* Revert the series of commits starting with r166578 which introduced theChandler Carruth2012-11-011-8/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | getIntPtrType support for multiple address spaces via a pointer type, and also introduced a crasher bug in the constant folder reported in PR14233. These commits also contained several problems that should really be addressed before they are re-committed. I have avoided reverting various cleanups to the DataLayout APIs that are reasonable to have moving forward in order to reduce the amount of churn, and minimize the number of commits that were reverted. I've also manually updated merge conflicts and manually arranged for the getIntPtrType function to stay in DataLayout and to be defined in a plausible way after this revert. Thanks to Duncan for working through this exact strategy with me, and Nick Lewycky for tracking down the really annoying crasher this triggered. (Test case to follow in its own commit.) After discussing with Duncan extensively, and based on a note from Micah, I'm going to continue to back out some more of the more problematic patches in this series in order to ensure we go into the LLVM 3.2 branch with a reasonable story here. I'll send a note to llvmdev explaining what's going on and why. Summary of reverted revisions: r166634: Fix a compiler warning with an unused variable. r166607: Add some cleanup to the DataLayout changes requested by Chandler. r166596: Revert "Back out r166591, not sure why this made it through since I cancelled the command. Bleh, sorry about this! r166591: Delete a directory that wasn't supposed to be checked in yet. r166578: Add in support for getIntPtrType to get the pointer type based on the address space. llvm-svn: 167221
* Remove fixme about unreachable cases from SwitchToLookupTableHans Wennborg2012-10-311-2/+0
| | | | | | SimplifyCFG will have removed those cases for us. llvm-svn: 167132
* Address Duncan's comments on r167121.Hans Wennborg2012-10-311-3/+4
| | | | llvm-svn: 167130
* Address Duncan's comments on r167115Hans Wennborg2012-10-311-48/+42
| | | | | | | - Use 0 instead of NULL - Helper function for "dyn_cast, else lookup in the constant pool". llvm-svn: 167121
* Fix false -> NULL conversion from r167115 spotted by Benjamin Kramer.Hans Wennborg2012-10-311-1/+1
| | | | llvm-svn: 167117
* Do simple constant propagation in lookup table formation for switchesHans Wennborg2012-10-311-15/+98
| | | | | | | | | | | | | | | | | | | By propagating the value for the switch condition, LLVM can now build lookup tables for code such as: switch (x) { case 1: return 5; case 2: return 42; case 3: case 4: case 5: return x - 123; default: return 123; } Given that x is known for each case, "x - 123" becomes a constant for cases 3, 4, and 5. llvm-svn: 167115
* Use TargetTransformInfo to control switch-to-lookup table transformationHans Wennborg2012-10-301-6/+15
| | | | | | | | | | | | | | When the switch-to-lookup tables transform landed in SimplifyCFG, it was pointed out that this could be inappropriate for some targets. Since there was no way at the time for the pass to know anything about the target, an awkward reverse-transform was added in CodeGenPrepare that turned lookup tables back into switches for some targets. This patch uses the new TargetTransformInfo to determine if a switch should be transformed, and removes CodeGenPrepare::ConvertLoadToSwitch. llvm-svn: 167011
* Remove a wrapper around getIntPtrType added to GVN by Hal in commit 166624 (theDuncan Sands2012-10-291-1/+1
| | | | | | | | | wrapper returns a vector of integers when passed a vector of pointers) by having getIntPtrType itself return a vector of integers in this case. Outside of this wrapper, I didn't find anywhere in the codebase that was relying on the old behaviour for vectors of pointers, so give this a whirl through the buildbots. llvm-svn: 166939
* Also optimize large switch statements.Jakob Stoklund Olesen2012-10-251-22/+20
| | | | | | | | | | The isValueEqualityComparison() guard at the top of SimplifySwitch() only applies to some of the possible transformations. The newer transformations work just fine on large switches, and the check on predecessor count is nonsensical. llvm-svn: 166710
* Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow2012-10-241-5/+9
| | | | | | | | | address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. llvm-svn: 166578
* Simplify code. No functionality change.Benjamin Kramer2012-10-141-5/+3
| | | | llvm-svn: 165904
* PGO: create metadata for switch only if it has more than one targets.Manman Ren2012-10-111-1/+1
| | | | | | | When all cases of a switch statement are dead, the weights vector only has one element, and we will get an ssertion failure when calling createBranchWeights. llvm-svn: 165759
* Move TargetData to DataLayout.Micah Villmow2012-10-081-18/+18
| | | | llvm-svn: 165402
* SimplifyCFG: Enhance the "remove CFG edge that leads to null pointer ↵Benjamin Kramer2012-10-041-2/+3
| | | | | | | | | | dereference" optimization to also handle instructions with multiple uses. We conservatively only check the first use to avoid walking long use chains. This catches the common case of having both a load and a store to a pointer supplied by a PHI node. llvm-svn: 165232
* SimplifyCFG: Don't crash when forming a switch bitmap with an undef default ↵Benjamin Kramer2012-10-011-2/+5
| | | | | | | | value. Fixes PR13985. llvm-svn: 164934
* SimplifyCFG: Enumerating all predecessors of a BB can be expensive ↵Benjamin Kramer2012-09-301-3/+7
| | | | | | | | (switches), avoid it if possible. No functionality change. llvm-svn: 164923
* Fix a integer overflow in SimplifyCFG's look up table formation logic.Benjamin Kramer2012-09-271-0/+4
| | | | | | | | If the width is very large it gets truncated from uint64_t to uint32_t when passed to TD->fitsInLegalInteger. The truncated value can fit in a register. This manifested in massive memory usage or crashes (PR13946). llvm-svn: 164784
* Address Duncan's comments on r164684:Hans Wennborg2012-09-261-9/+5
| | | | | | | | - Put statistics in alphabetical order - Don't use getZextValue when building TableInt, just use APInts - Introduce Create{Z,S}ExtOrTrunc in IRBuilder. llvm-svn: 164696
* Address Duncan's comments on r164682:Hans Wennborg2012-09-261-6/+4
| | | | | | | - Finish assert messages with exclamation mark - Move overflow checking into ShouldBuildLookupTable. llvm-svn: 164692
* SimplifyCFG: Make the switch-to-lookup table transformation store theHans Wennborg2012-09-261-12/+89
| | | | | | | | | | | | | | | | tables in bitmaps when they fit in a target-legal register. This saves some space, and it also allows for building tables that would otherwise be deemed too sparse. One interesting case that this hits is example 7 from http://blog.regehr.org/archives/320. We currently generate good code for this when lowering the switch to the selection DAG: we build a bitmask to decide whether to jump to one block or the other. My patch will result in the same bitmask, but it removes the need for the jump, as the return value can just be retrieved from the mask. llvm-svn: 164684
* SimplifyCFG: Refactor the switch-to-lookup table transformation byHans Wennborg2012-09-261-72/+115
| | | | | | breaking out the building of lookup tables into a separate class. llvm-svn: 164682
* SimplifyCFG: sink common codes from IF, ELSE blocks down to END block.Manman Ren2012-09-201-0/+173
| | | | | | | | | | | | We already have HoistThenElseCodeToIf, this patch implements SinkThenElseCodeToEnd. When END block has only two predecessors and each predecessor terminates with unconditional branches, we compare instructions in IF and ELSE blocks backwards and check whether we can sink the common instructions down. rdar://12191395 llvm-svn: 164325
* SimplifyCFG: Don't generate invalid code for switch used to initializeHans Wennborg2012-09-191-9/+8
| | | | | | | | | | | | | two variables where the first variable is returned and the second ignored. I don't think this occurs in practice (other passes should have cleaned up the unused phi node), but it should still be handled correctly. Also make the logic for determining if we should return early less sketchy. llvm-svn: 164225
* PGO: preserve branch-weight metadata when simplifying Switch to a sub, an icmpManman Ren2012-09-181-1/+38
| | | | | | and a conditional branch; also when removing dead cases from a switch. llvm-svn: 164084
* PGO: preserve branch-weight metadata when simplifying SwitchManman Ren2012-09-171-0/+15
| | | | | | | Hanlde the case when we split the default edge if the default target has "icmp" and unconditinal branch. llvm-svn: 164076
* PGO: preserve branch-weight metadata when simplifying SwitchOnSelect.Manman Ren2012-09-171-5/+28
| | | | llvm-svn: 164068
* PGO: preserve branch-weight metadata when simplifying two branches with a commonManman Ren2012-09-171-0/+27
| | | | | | destination in SimplifyCondBranchToCondBranch. llvm-svn: 164054
* Fix a few vars that can end up being used without initialization.Axel Naumann2012-09-171-1/+1
| | | | | | The cases where no initialization happens should still be checked for logic flaws. llvm-svn: 164032
* PGO: preserve branch-weight metadata when simplifying two branches with a commonManman Ren2012-09-151-111/+42
| | | | | | | | | | | | | | | | destination. Updated previous implementation to fix a case not covered: // PBI: br i1 %x, TrueDest, BB // BI: br i1 %y, TrueDest, FalseDest The other case was handled correctly. // PBI: br i1 %x, BB, FalseDest // BI: br i1 %y, TrueDest, FalseDest Also tried to use 64-bit arithmetic instead of APInt with scale to simplify the computation. Let me know if you have other opinions about this. llvm-svn: 163954
* PGO: preserve branch-weight metadata when simplifying a switch with a singleManman Ren2012-09-141-0/+19
| | | | | | case to a conditional branch and when removing dead cases. llvm-svn: 163942
* Try to fix the bots by detecting inconsistant branch-weight metadata.Manman Ren2012-09-141-4/+10
| | | | llvm-svn: 163926
* PGO: preserve branch-weight metadata when merging two switches whereManman Ren2012-09-141-5/+12
| | | | | | | the default target of the first switch is not the basic block the second switch is in (PredDefault != BB). llvm-svn: 163916
* SimplifyCFG: preserve branch-weight metadata when creating a new switch fromManman Ren2012-09-111-81/+45
| | | | | | | | | | | | | a pair of switch/branch where both depend on the value of the same variable and the default case of the first switch/branch goes to the second switch/branch. Code clean up and fixed a few issues: 1> handling the case where some cases of the 2nd switch are invalidated 2> correctly calculate the weight for the 2nd switch when it is a conditional eq Testing case is modified from Alastair's original patch. llvm-svn: 163635
* Fix style issues from r163302 pointed out by Evan.Hans Wennborg2012-09-101-18/+15
| | | | llvm-svn: 163491
* Remove an incorrect assert during branch weight propagation.Andrew Trick2012-09-081-1/+0
| | | | | | Patch and test case by Alastair Murray! llvm-svn: 163437
* SimplifyCFG: ValidLookupTableConstant should be staticHans Wennborg2012-09-071-1/+1
| | | | llvm-svn: 163378
* Fix switch_to_lookup_table.ll test from r163302.Hans Wennborg2012-09-061-5/+6
| | | | | | | | The lookup tables did not get built in a deterministic order. This makes them get built in the order that the corresponding phi nodes were found. llvm-svn: 163305
* Build lookup tables for switches (PR884)Hans Wennborg2012-09-061-0/+286
| | | | | | | | | | | | | | | | | | | | | | This adds a transformation to SimplifyCFG that attemps to turn switch instructions into loads from lookup tables. It works on switches that are only used to initialize one or more phi nodes in a common successor basic block, for example: int f(int x) { switch (x) { case 0: return 5; case 1: return 4; case 2: return -2; case 5: return 7; case 6: return 9; default: return 42; } This speeds up the code by removing the hard-to-predict jump, and reduces code size by removing the code for the jump targets. llvm-svn: 163302
* Stop casting away const qualifier needlessly.Roman Divacky2012-09-051-2/+2
| | | | llvm-svn: 163258
* testMichael Ilseman2012-08-301-2/+2
| | | | llvm-svn: 162914
* Preserve branch profile metadata during switch formation.Andrew Trick2012-08-291-0/+154
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Patch by Michael Ilseman! This fixes SimplifyCFGOpt::FoldValueComparisonIntoPredecessors to preserve metata when folding conditional branches into switches. void foo(int x) { if (x == 0) bar(1); else if (__builtin_expect(x == 10, 1)) bar(2); else if (x == 20) bar(3); } CFG: B0 | \ | X0 B10 | \ | X10 B20 | \ E X20 Merge B0-B10: w(B0-X0) = w(B0-X0)*sum-weights(B10) = w(B0-X0) * (w(B10-X10) + w(B10-B20)) w(B0-X10) = w(B0-B10) * w(B10-X10) w(B0-B20) = w(B0-B10) * w(B10-B20) B0 __ | \ \ | X10 X0 B20 | \ E X20 Merge B0-B20: w(B0-X0) = w(B0-X0) * sum-weights(B20) = w(B0-X0) * (w(B20-E) + w(B20-X20)) w(B0-X10) = w(B0-X10) * sum-weights(B20) = ... w(B0-X20) = w(B0-B20) * w(B20-X20) w(B0-E) = w(B0-B20) * w(B20-E) llvm-svn: 162868
* whitespaceAndrew Trick2012-08-291-168/+168
| | | | llvm-svn: 162867
* Fix a typo (the the => the)Sylvestre Ledru2012-07-231-1/+1
| | | | llvm-svn: 160621
* Move llvm/Support/MDBuilder.h to llvm/MDBuilder.h, to live withChandler Carruth2012-07-151-1/+1
| | | | | | | | | | | IRBuilder, DIBuilder, etc. This is the proper layering as MDBuilder can't be used (or implemented) without the Core Metadata representation. Patches to Clang and Dragonegg coming up. llvm-svn: 160237
* Make helper functions static.Benjamin Kramer2012-07-131-1/+1
| | | | llvm-svn: 160173
* Revert "IntRange:" as it appears to be breaking self hosting.Eric Christopher2012-07-021-85/+148
| | | | | | This reverts commit b2833d9dcba88c6f0520cad760619200adc0442c. llvm-svn: 159618
OpenPOWER on IntegriCloud