summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru2012-09-272-2/+2
| | | | | | See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 llvm-svn: 164768
* Fix a typo 'iff' => 'if'Sylvestre Ledru2012-09-272-2/+2
| | | | llvm-svn: 164767
* 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
* Rename virtual table anchors from Anchor() to anchor() for consistency with ↵Craig Topper2012-09-261-1/+1
| | | | | | the rest of the tree. llvm-svn: 164666
* Expansions for u/srem, using the udiv expansion. More unit tests for udiv ↵Michael Ilseman2012-09-261-7/+115
| | | | | | | | and u/srem. Fixed issue with Release build. llvm-svn: 164654
* Revert r164614 to appease the buildbots.Chad Rosier2012-09-251-115/+7
| | | | llvm-svn: 164627
* Expansions for u/srem, using the udiv expansion. More unit tests for udiv ↵Michael Ilseman2012-09-251-7/+115
| | | | | | and u/srem. llvm-svn: 164614
* 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
* Renaming functions to match coding style guidelinesMichael Ilseman2012-09-191-4/+4
| | | | llvm-svn: 164238
* Doxygen-ify commentsMichael Ilseman2012-09-191-8/+16
| | | | llvm-svn: 164235
* Put the * and & next to the variable, rather than the type.Michael Ilseman2012-09-191-73/+73
| | | | llvm-svn: 164232
* 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
* IntegerDivision: Style cleanups, avoid warning about mixing || and && ↵Benjamin Kramer2012-09-191-7/+5
| | | | | | without parens. llvm-svn: 164216
* New utility for expanding integer division for targets that don't support it.Michael Ilseman2012-09-182-0/+307
| | | | | | Implementation derived from compiler-rt's implementation of signed and unsigned integer division. llvm-svn: 164173
* 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-142-2/+33
| | | | | | case to a conditional branch and when removing dead cases. llvm-svn: 163942
* Stylistic and 80-col fixesEvan Cheng2012-09-141-1/+1
| | | | llvm-svn: 163940
* Review feedback from Duncan Sands. Alphabetize includes and simplifyAlex Rosenberg2012-09-141-3/+3
| | | | | | lit config. llvm-svn: 163928
* 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
* PGO: preserve branch-weight metadata when removing a case which jumpsManman Ren2012-09-121-0/+22
| | | | | | to the default target. llvm-svn: 163724
* Release build: guard dump functions withManman Ren2012-09-121-1/+1
| | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163344. llvm-svn: 163679
* 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
* llvm/lib/Transforms/Utils/CMakeLists.txt: Update.NAKAMURA Takumi2012-09-111-0/+1
| | | | llvm-svn: 163593
* Add a pass that renames everything with metasyntatic names. This works well ↵Alex Rosenberg2012-09-112-0/+133
| | | | | | after using bugpoint to reduce the confusion presented by the original names, which no longer mean what they used to. llvm-svn: 163592
* Move bypassSlowDivision into the llvm namespace.Benjamin Kramer2012-09-101-4/+6
| | | | llvm-svn: 163503
* 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
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-061-0/+2
| | | | | | No functional change. llvm-svn: 163344
* 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
* BypassSlowDivision: Assign to reference, don't copy the object.Jakub Staszak2012-09-041-2/+2
| | | | llvm-svn: 163179
* Fix my previous patch (r163164). It does now what it is supposed to do:Jakub Staszak2012-09-041-1/+0
| | | | | | Doesn't set MadeChange to TRUE if BypassSlowDivision doesn't change anything. llvm-svn: 163165
* Return false if BypassSlowDivision doesn't change anything.Jakub Staszak2012-09-041-33/+34
| | | | | | | | | | Also a few minor changes: - use pre-inc instead of post-inc - use isa instead of dyn_cast - 80 col - trailing spaces llvm-svn: 163164
* Generic Bypass Slow DivPreston Gurd2012-09-042-0/+252
| | | | | | | | | | | | | | | | | | | | | | | - CodeGenPrepare pass for identifying div/rem ops - Backend specifies the type mapping using addBypassSlowDivType - Enabled only for Intel Atom with O2 32-bit -> 8-bit - Replace IDIV with instructions which test its value and use DIVB if the value is positive and less than 256. - In the case when the quotient and remainder of a divide are used a DIV and a REM instruction will be present in the IR. In the non-Atom case they are both lowered to IDIVs and CSE removes the redundant IDIV instruction, using the quotient and remainder from the first IDIV. However, due to this optimization CSE is not able to eliminate redundant IDIV instructions because they are located in different basic blocks. This is overcome by calculating both the quotient (DIV) and remainder (REM) in each basic block that is inserted by the optimization and reusing the result values when a subsequent DIV or REM instruction uses the same operands. - Test cases check for the presents of the optimization when calculating either the quotient, remainder, or both. Patch by Tyler Nowicki! llvm-svn: 163150
* 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
OpenPOWER on IntegriCloud