summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Make SimplifyCFG simply depend upon TargetTransformInfo and pass itChandler Carruth2013-01-071-37/+37
| | | | | | | | | | | | | through as a reference rather than a pointer. There is always *some* implementation of this available, so this simplifies code by not having to test for whether it is available or not. Further, it turns out there were piles of places where SimplifyCFG was recursing and not passing down either TD or TTI. These are fixed to be more pedantically consistent even though I don't have any particular cases where it would matter. llvm-svn: 171691
* Move TargetTransformInfo to live under the Analysis library. This noChandler Carruth2013-01-071-1/+1
| | | | | | | longer would violate any dependency layering and it is in fact an analysis. =] llvm-svn: 171686
* Switch SimplifyCFG over to the TargetTransformInfo interface rather thanChandler Carruth2013-01-051-4/+2
| | | | | | the ScalarTargetTransformInfo interface. llvm-svn: 171617
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-13/+13
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-10/+10
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Fix non-determinism introduced in r168970 and pointed out by Duncan.Chandler Carruth2012-11-301-5/+13
| | | | | | | | | | | | | We're iterating over a non-deterministically ordered container looking for two saturating flags. To do this correctly, we have to saturate both, and only stop looping if both saturate to their final value. Otherwise, which flag we see first changes the result. This is also a micro-optimization of the previous version as now we don't go into the (possibly expensive) test logic once the first violation of either constraint is detected. llvm-svn: 168989
* Rearrange the comments, control flow, and variable names; noChandler Carruth2012-11-301-7/+14
| | | | | | | | | | | | | | functionality changed. Evan's commit r168970 moved the code that the primary comment in this function referred to to the other end of the function without moving the comment, and there has been a steady creep of "boolean" logic in it that is simpler if handled via early exit. That way each special case can have its own comments. I've also made the variable name a bit more explanatory than "AllFit". This is in preparation to fix the non-deterministic output of this function. llvm-svn: 168988
* Fix logic to determine whether to turn a switch into a lookup table. WhenEvan Cheng2012-11-301-6/+13
| | | | | | | | | the tables cannot fit in registers (i.e. bitmap), do not emit the table if it's using an illegal type. rdar://12779436 llvm-svn: 168970
* 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
OpenPOWER on IntegriCloud