summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* PR2621: Improvements to the SCEV AddRec binomial expansion. This Eli Friedman2008-08-041-84/+111
| | | | | | | | | | | | | | | | | | | | | | | | | version uses a new algorithm for evaluating the binomial coefficients which is significantly more efficient for AddRecs of more than 2 terms (see the comments in the code for details on how the algorithm works). It also fixes some bugs: it removes the arbitrary length restriction for AddRecs, it fixes the silent generation of incorrect code for AddRecs which require a wide calculation width, and it fixes an issue where we were incorrectly truncating the iteration count too far when evaluating an AddRec expression narrower than the induction variable. There are still a few related issues I know of: I think there's still an issue with the SCEVExpander expansion of AddRec in terms of the width of the induction variable used. The hack to avoid generating too-wide integers shouldn't be necessary; instead, the callers should be considering the cost of the expansion before expanding it (in addition to not expanding too-wide integers, we might not want to expand expressions that are really expensive, especially when optimizing for size; calculating an length-17 32-bit AddRec currently generates about 250 instructions of straight-line code on X86). Also, for long 32-bit AddRecs on X86, CodeGen really sucks at scheduling the code. I'm planning on filing follow-up PRs for these issues. llvm-svn: 54332
* Another SCEV issue from PR2607; essentially the same issue, but this Eli Friedman2008-07-301-4/+4
| | | | | | | | | | | time applying to the implicit comparison in smin expressions. The correct way to transform an inequality into the opposite inequality, either signed or unsigned, is with a not expression. I looked through the SCEV code, and I don't think there are any more occurrences of this issue. llvm-svn: 54194
* Fix for PR2607: SCEV miscomputing the loop count for loops with an Eli Friedman2008-07-301-3/+7
| | | | | | | | | | | | SGT exit condition. Essentially, the correct way to flip an inequality in 2's complement is the not operator, not the negation operator. That said, the difference only affects cases involving INT_MIN. Also, enhance the pre-test search logic to be a bit smarter about inequalities flipped with a not operator, so it can eliminate the smax from the iteration count for simple loops. llvm-svn: 54184
* Fix a subtle bug when removing instructions from memdep. In very specific Owen Anderson2008-07-281-0/+4
| | | | | | | | circumstances we could end up remapping a dependee to the same instruction that we're trying to remove. Handle this properly by just falling back to a conservative solution. llvm-svn: 54132
* Fix minor issues with VICmp/VFCmp constant expressionsNate Begeman2008-07-251-1/+3
| | | | llvm-svn: 54030
* Revert r53812 -- premature. LegalizeTypes isn't actually on yet!Nick Lewycky2008-07-211-8/+22
| | | | llvm-svn: 53816
* Switch on the use of arbitrary precision integers in scalar evolution. This willNick Lewycky2008-07-211-22/+8
| | | | | | | | | | bail after 256-bits to avoid producing code that the backends can't handle. Previously, we capped it at 64-bits, preferring to miscompile in those cases. This change also reverts much of r52248 because the invariants the code was expecting are now being met. llvm-svn: 53812
* This header isn't necessary now.Wojciech Matyjewicz2008-07-201-2/+0
| | | | llvm-svn: 53811
* Fix PR2088. Use modulo linear equation solver to compute loop iterationWojciech Matyjewicz2008-07-201-22/+71
| | | | | | count. llvm-svn: 53810
* Don't use ++idx_begin when I actually mean idx_begin + 1, especially since weMatthijs Kooijman2008-07-161-1/+1
| | | | | | | | also use *idx_begin in the same expression, giving unpredictable results. This fixes this bug: http://lists.cs.uiuc.edu/pipermail/llvmdev/2008-July/015877.html llvm-svn: 53670
* Correct this inversion!Nick Lewycky2008-07-151-1/+1
| | | | | | I swear that didn't show up in svn diff... llvm-svn: 53587
* Fix up comments.Nick Lewycky2008-07-151-5/+7
| | | | llvm-svn: 53586
* Stop creating extraneous smax/umax in SCEV. This removes a regression where weNick Lewycky2008-07-121-6/+79
| | | | | | started complicating many loops ('for' loops, in fact). llvm-svn: 53508
* Fix spelling of "hierarchy" in comments.Dan Gohman2008-07-111-1/+1
| | | | llvm-svn: 53489
* Use find instead of lower_bound.Dan Gohman2008-07-111-2/+2
| | | | llvm-svn: 53474
* Remove getValueRange from SCEV. It wasn't doing anything there anyways, and aNick Lewycky2008-07-091-31/+0
| | | | | | more complete version is now available from the LoopVR pass. llvm-svn: 53269
* Expand SCEVUDiv of power of 2 to a lshr instruction.Nick Lewycky2008-07-081-0/+14
| | | | llvm-svn: 53217
* Handle 'lshr' instruction with SCEVUDiv object.Nick Lewycky2008-07-071-2/+14
| | | | | | Comment the xor %x, -1 case. llvm-svn: 53167
* Keep track of inherited analysis (e.g. dominator tree).Devang Patel2008-07-031-0/+3
| | | | llvm-svn: 53088
* A better fix for PR2503 that doesn't pessimize GVN in the presence of ↵Owen Anderson2008-07-021-13/+0
| | | | | | unreachable blocks. llvm-svn: 53032
* Fix typos in comments. Devang Patel2008-07-011-1/+1
| | | | | | Thanks for the feedback! llvm-svn: 52978
* Add dom info verifier.Devang Patel2008-07-011-0/+3
| | | | llvm-svn: 52967
* Properly handle cases where a predecessor of the block being queried on is ↵Owen Anderson2008-07-011-0/+13
| | | | | | | | unreachable. This fixes PR2503, though we should also fix other passes not to emit this kind of code. llvm-svn: 52946
* - Re-apply 52748 and friends with fix. GetConstantStringInfo() returns an ↵Evan Cheng2008-06-301-0/+100
| | | | | | | | empty string for ConstantAggregateZero case which surprises selectiondag. - Correctly handle memcpy from constant string which is zero-initialized. llvm-svn: 52891
* Add a value range analysis that lazily computes ranges using ScalarEvolutions.Nick Lewycky2008-06-301-0/+289
| | | | llvm-svn: 52885
* Revert (52748 and friends):Anton Korobeynikov2008-06-291-100/+0
| | | | | | | | | | | | Move GetConstantStringInfo to lib/Analysis. Remove string output routine from Constant. Update all callers. Change debug intrinsic api slightly to accomodate move of routine, these now return values instead of strings. This unbreaks llvm-gcc bootstrap. llvm-svn: 52884
* Add back the capability to include nul characters in strings with Chris Lattner2008-06-281-5/+7
| | | | | | | GetConstantStringInfo. This will hopefully restore llvm-gcc to happy bootstrap land. llvm-svn: 52851
* Tighten up checking.Chris Lattner2008-06-281-4/+10
| | | | llvm-svn: 52850
* fix the regressions from Eric's patch by making GetConstantStringInfoChris Lattner2008-06-271-29/+34
| | | | | | | tolerate a non-nul-terminated string, and handling a direct global reference. llvm-svn: 52813
* Reserve the size we'll need in advance.Owen Anderson2008-06-261-0/+1
| | | | llvm-svn: 52763
* Move GetConstantStringInfo to lib/Analysis. RemoveEric Christopher2008-06-261-0/+86
| | | | | | | | | string output routine from Constant. Update all callers. Change debug intrinsic api slightly to accomodate move of routine, these now return values instead of strings. llvm-svn: 52748
* Generalize createSCEV to be able to form SCEV expressions fromDan Gohman2008-06-221-110/+117
| | | | | | ConstantExprs. llvm-svn: 52615
* Use SCEVAddRecExpr::isAffine.Dan Gohman2008-06-221-2/+2
| | | | llvm-svn: 52614
* Move a few more SCEVExpander methods out-of-line.Dan Gohman2008-06-221-0/+21
| | | | llvm-svn: 52612
* fix warning when assertions disabled.Chris Lattner2008-06-211-2/+1
| | | | llvm-svn: 52589
* Fix some warnings reported by gcc-4.3. HopefullyDuncan Sands2008-06-191-1/+2
| | | | | | this still compiles on windows - I can't test! llvm-svn: 52488
* Move SCEVExpander::visitAddExpr out-of-line.Dan Gohman2008-06-181-0/+10
| | | | llvm-svn: 52464
* Move LSR's private isZero function to a public SCEV memberDan Gohman2008-06-182-10/+13
| | | | | | function, and make use of it in several places. llvm-svn: 52463
* Use a SmallVector instead of an array, since auto_ptr doesn't handle arraysMatthijs Kooijman2008-06-171-11/+8
| | | | | | properly. llvm-svn: 52390
* Make BuildSubAggregate use FindInsertedElement again to prevent it fromMatthijs Kooijman2008-06-161-20/+48
| | | | | | | | inserting extractvalues. In particular, this prevents the insertion of extractvalues that can't be folded away later. Also add an example of when this stuff is needed. llvm-svn: 52328
* Make the InsertBefore argument to FindInsertedValue optional, so you can ↵Matthijs Kooijman2008-06-161-3/+8
| | | | | | find an inserted value without modifying the code. llvm-svn: 52319
* Pass around Instruction* instead of Instruction& in FindInsertedValue and ↵Matthijs Kooijman2008-06-161-5/+5
| | | | | | friends. llvm-svn: 52318
* 80 column fixes.Matthijs Kooijman2008-06-161-15/+31
| | | | llvm-svn: 52316
* Move FindScalarValue from InstructionCombining.cpp to ValueTracking.cpp. WhileMatthijs Kooijman2008-06-161-0/+128
| | | | | | | | | | I'm at it, rename it to FindInsertedValue. The only functional change is that newly created instructions are no longer added to instcombine's worklist, but that is not really necessary anyway (and I'll commit some improvements next that will completely remove the need). llvm-svn: 52315
* simplify some code by using a helper function. This really reallyChris Lattner2008-06-161-22/+16
| | | | | | wants a 'nocapture' predicate. llvm-svn: 52304
* move a bunch of predicates up into their own sectionChris Lattner2008-06-161-157/+171
| | | | | | in this file, no other changes. llvm-svn: 52303
* Other parts of this code treat noalias arguments as objects forChris Lattner2008-06-161-4/+8
| | | | | | the purposes of escape analysis. llvm-svn: 52302
* If we are checking to see if the result of a call aliases aChris Lattner2008-06-161-1/+21
| | | | | | | pointer derived from a local allocation, if the local allocation never escapes, the pointers can't alias. This implements PR2436 llvm-svn: 52301
* Refactor basicaa's main alias function somethin' fierce. Chris Lattner2008-06-161-104/+94
| | | | | | | | This fixes several minor bugs (such as returning noalias for comparisons between external weak functions an null) but is mostly a cleanup. llvm-svn: 52299
* Fix PR2434. When scanning for exising binary operator to reuse don't Wojciech Matyjewicz2008-06-151-15/+15
| | | | | | | | | | | take into account the instrucion pointed by InsertPt. Thanks to it, returning the new value of InsertPt to the InsertBinop() caller can be avoided. The bug was, actually, in visitAddRecExpr() method which wasn't correctly handling changes of InsertPt. There shouldn't be any performance regression, as -gvn pass (run after -indvars) removes any redundant binops. llvm-svn: 52291
OpenPOWER on IntegriCloud