summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* Type sizes and fields offsets inside structs are unsigned. This is a highlyDuncan Sands2012-03-151-4/+2
| | | | | | | theoretical fix since it only matters for types with >= 2^63 bits (!) and also only matters if pointers have more than 64 bits, which is not supported anyway. llvm-svn: 152831
* Make the swap code here a bit more obvious what its doing... We'reChandler Carruth2012-03-151-1/+1
| | | | | | | essentially sorting the pair's arguments. I'd love to actually call sort here, but I'm just not that crazy. ;] llvm-svn: 152764
* Don't assume that the arguments are processed in some particular order.Chandler Carruth2012-03-151-2/+4
| | | | | | | This appears to not be the case with dragonegg at least in some contexts. Hopefully will fix the bootstrap assert failure there. llvm-svn: 152763
* Remove all remnants of partial specialization in the cost computationChandler Carruth2012-03-151-69/+0
| | | | | | side of things. This is all dead code. llvm-svn: 152759
* Extend the inline cost calculation to account for bonuses due toChandler Carruth2012-03-141-3/+86
| | | | | | | | | | | | | | | | | | | | | | | | | | | correlated pairs of pointer arguments at the callsite. This is designed to recognize the common C++ idiom of begin/end pointer pairs when the end pointer is a constant offset from the begin pointer. With the C-based idiom of a pointer and size, the inline cost saw the constant size calculation, and this provides the same level of information for begin/end pairs. In order to propagate this information we have to search for candidate operations on a pair of pointer function arguments (or derived from them) which would be simplified if the pointers had a known constant offset. Then the callsite analysis looks for such pointer pairs in the argument list, and applies the appropriate bonus. This helps LLVM detect that half of bounds-checked STL algorithms (such as hash_combine_range, and some hybrid sort implementations) disappear when inlined with a constant size input. However, it's not a complete fix due the inaccuracy of our cost metric for constants in general. I'm looking into that next. Benchmarks showed no significant code size change, and very minor performance changes. However, specific code such as hashing is showing significantly cleaner inlining decisions. llvm-svn: 152752
* Refactor the inline cost bonus calculation for constants to useChandler Carruth2012-03-141-20/+26
| | | | | | | | a worklist rather than a recursive call. No functionality changed. llvm-svn: 152706
* enhance jump threading to preserve TBAA information when PRE'ing loads,Chris Lattner2012-03-131-3/+13
| | | | | | | fixing rdar://11039258, an issue that came up when inspecting clang's bootstrapped codegen. llvm-svn: 152635
* Generalize the "trunc(ptrtoint(x)) - trunc(ptrtoint(y)) ->Duncan Sands2012-03-131-14/+34
| | | | | | trunc(ptrtoint(x-y))" optimization introduced by Chandler. llvm-svn: 152626
* Uniformize the InstructionSimplify interface by ensuring that all routinesDuncan Sands2012-03-132-337/+278
| | | | | | | | take a TargetLibraryInfo parameter. Internally, rather than passing TD, TLI and DT parameters around all over the place, introduce a struct for holding them. llvm-svn: 152623
* Fix regression from r151466: an we can't replace uses of an instruction ↵Eli Friedman2012-03-131-3/+7
| | | | | | reachable from the entry block with uses of an instruction not reachable from the entry block. PR12231. llvm-svn: 152595
* Address some review comments from Duncan. This moves the iterativeChandler Carruth2012-03-131-32/+23
| | | | | | | | | | | | | | | | | | | offset accumulation to use a boring APInt instead of ConstantExprs. I didn't go all the way to an 'int64_t' because I wanted APInt to handle any magic required to properly wrap the arithmetic when the pointer width is <64 bits. If there is a significant penalty from using APInt here, first off WTF, and secondly let me know and I'll do the math by hand. I've left one layer still operating w/ ConstantExpr because it makes the interface quite a bit simpler, and that one isn't iterative so has much lower cost. I suppose this may potentially speed up some strang compilation situations, but I don't really expect much. It should have no functional impact either way. llvm-svn: 152590
* Teach instsimplify how to constant fold pointer differences.Chandler Carruth2012-03-121-0/+122
| | | | | | | | | | | | | | | | | | | Typically instcombine has handled this, but pointer differences show up in several contexts where we would like to get constant folding, and cannot afford to run instcombine. Specifically, I'm working on improving the constant folding of arguments used in inline cost analysis with instsimplify. Doing this in instsimplify implies some algorithm changes. We have to handle multiple layers of all-constant GEPs because instsimplify cannot fold them into a single GEP the way instcombine can. Also, we're only interested in all-constant GEPs. The result is that this doesn't really replace the instcombine logic, it's just complimentary and focused on constant folding. Reviewed on IRC by Benjamin Kramer. llvm-svn: 152555
* llvm::SwitchInstStepan Dyatkovskiy2012-03-111-1/+1
| | | | | | | Renamed methods caseBegin, caseEnd and caseDefault with case_begin, case_end, and case_default. Added some notes relative to case iterators. llvm-svn: 152532
* Make helper static, so it can be inlined into its sole caller.Benjamin Kramer2012-03-101-3/+3
| | | | llvm-svn: 152515
* As Duncan pointed out, pointers tend not to be in floating point ↵Bill Wendling2012-03-101-6/+6
| | | | | | format...for now. llvm-svn: 152499
* Make this transformation slightly less agressive and more correct.Bill Wendling2012-03-101-8/+18
| | | | | | | | | | | The 'CmpInst::isFalseWhenEqual' function returns 'false' for values other than simply equality. For instance, it returns 'false' for <= or >=. This isn't the correct behavior for this transformation, which is checking for strict equality and non-equality. It was causing the gcc.c-torture/execute/frame-address.c test to fail because it would completely (and incorrectly) optimize a whole function into a 'ret i32 0'. llvm-svn: 152497
* Refactor some methods to look through bitcasts and GEPs on pointers intoChandler Carruth2012-03-101-25/+3
| | | | | | | | | | a common collection of methods on Value, and share their implementation. We had two variations in two different places already, and I need the third variation for inline cost estimation. Reviewed by Duncan Sands on IRC, but further comments here welcome. llvm-svn: 152490
* Factor out the analysis of addition and subtraction in ComputeMaskedBits. ReuseNick Lewycky2012-03-091-83/+123
| | | | | | it to analyze extractvalue(llvm.[us](add|sub).with.overflow.*) intrinsics! llvm-svn: 152398
* Undo a previous restriction on the inline cost calculation which NickChandler Carruth2012-03-091-107/+146
| | | | | | | | | | | | | | | | | | | | | | introduced. Specifically, there are cost reductions for all constant-operand icmp instructions against an alloca, regardless of whether the alloca will in fact be elligible for SROA. That means we don't want to abort the icmp reduction computation when we abort the SROA reduction computation. That in turn frees us from the need to keep a separate worklist and defer the ICmp calculations. Use this new-found freedom and some judicious function boundaries to factor the innards of computing the cost factor of any given instruction out of the loop over the instructions and into static helper functions. This greatly simplifies the code, and hopefully makes it more clear what is happening here. Reviewed by Eric Christopher. There is some concern that we'd like to ensure this doesn't get out of hand, and I plan to benchmark the effects of this change over the next few days along with some further fixes to the inline cost. llvm-svn: 152368
* Taken into account Duncan's comments for r149481 dated by 2nd Feb 2012:Stepan Dyatkovskiy2012-03-082-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120130/136146.html Implemented CaseIterator and it solves almost all described issues: we don't need to mix operand/case/successor indexing anymore. Base iterator class is implemented as a template since it may be initialized either from "const SwitchInst*" or from "SwitchInst*". ConstCaseIt is just a read-only iterator. CaseIt is read-write iterator; it allows to change case successor and case value. Usage of iterator allows totally remove resolveXXXX methods. All indexing convertions done automatically inside the iterator's getters. Main way of iterator usage looks like this: SwitchInst *SI = ... // intialize it somehow for (SwitchInst::CaseIt i = SI->caseBegin(), e = SI->caseEnd(); i != e; ++i) { BasicBlock *BB = i.getCaseSuccessor(); ConstantInt *V = i.getCaseValue(); // Do something. } If you want to convert case number to TerminatorInst successor index, just use getSuccessorIndex iterator's method. If you want initialize iterator from TerminatorInst successor index, use CaseIt::fromSuccessorIndex(...) method. There are also related changes in llvm-clients: klee and clang. llvm-svn: 152297
* Rotate two of the functions used to count bonuses for the inline costChandler Carruth2012-03-081-14/+10
| | | | | | | | | | | | | analysis to be methods on the cost analysis's function info object instead of the code metrics object. These really are just users of the code metrics, they're building the information for the function's analysis. This is the first step of growing the amount of information we collect about a function in order to cope with pair-wise simplifications due to allocas. llvm-svn: 152283
* No functionality change. Type::isSized() can be expensive, so avoid calling itNick Lewycky2012-03-071-8/+10
| | | | | | until after other inexpensive tests. llvm-svn: 152195
* A few more cases of missing masking in ComputeMaskedBits; found by inspection.Eli Friedman2012-03-051-3/+3
| | | | llvm-svn: 152070
* Make sure we don't return bits outside the mask in ComputeMaskedBits. PR12189.Eli Friedman2012-03-051-2/+2
| | | | llvm-svn: 152066
* LVI: Recognize the form instcombine canonicalizes range checks into when ↵Benjamin Kramer2012-03-021-4/+16
| | | | | | | | | | forming constant ranges. This could probably be made a lot smarter, but this is a common case and doesn't require LVI to scan a lot of code. With this change CVP can optimize away the "shift == 0" case in Hashing.h that only gets hit when "shift" is in a range not containing 0. llvm-svn: 151919
* Duncan pointed out that if the alignment isn't explicitly specified, it ↵Eli Friedman2012-02-271-4/+4
| | | | | | defaults to the ABI alignment. Given that, make this code a bit more aggressive in such cases. llvm-svn: 151584
* Teach BasicAA about the LLVM IR rules that allow reading past the end of an ↵Eli Friedman2012-02-271-9/+26
| | | | | | object given sufficient alignment. Fixes PR12098. llvm-svn: 151553
* Fix this assert. IP can point to an instruction with strange dominanceRafael Espindola2012-02-271-15/+20
| | | | | | | properties (invoke). Just assert that the instruction we return dominates the insertion point. llvm-svn: 151511
* Don't call dominates on unreachable instructions. Should fix the dragoneggRafael Espindola2012-02-261-2/+6
| | | | | | build. Testcase is still reducing. llvm-svn: 151474
* And update the comment...Rafael Espindola2012-02-261-1/+0
| | | | llvm-svn: 151472
* Enable the assert that got all this dominator work started.Rafael Espindola2012-02-261-1/+1
| | | | llvm-svn: 151471
* Change the implementation of dominates(inst, inst) to one based on what theRafael Espindola2012-02-261-6/+5
| | | | | | | | verifier does. This correctly handles invoke. Thanks to Duncan, Andrew and Chris for the comments. Thanks to Joerg for the early testing. llvm-svn: 151469
* Reinstate the optimization from r151449 with a fix to not turn 'gep %x' intoNick Lewycky2012-02-261-11/+51
| | | | | | 'gep null' when the icmp predicate is unsigned (or is signed without inbounds). llvm-svn: 151467
* Don't call dominates on unreachable instructions.Rafael Espindola2012-02-261-1/+2
| | | | llvm-svn: 151466
* Roll these back to r151448 until I figure out how they're breakingNick Lewycky2012-02-251-42/+10
| | | | | | MultiSource/Applications/lua. llvm-svn: 151463
* An argument and a local identified object (eg. a noalias call) could turn outNick Lewycky2012-02-251-12/+13
| | | | | | | equal if both are null. In the test, scope type %t and global @y by adding a 'gep' prefix to them. llvm-svn: 151452
* Fix five-letter typo in comment.Nick Lewycky2012-02-251-1/+1
| | | | llvm-svn: 151450
* Teach instsimplify to be more aggressive when analyzing comparisons of pointersNick Lewycky2012-02-251-10/+41
| | | | | | | by using llvm::isIdentifiedObject. Also teach it to handle GEPs that have the same base pointer and constant operands. Fixes PR11238! llvm-svn: 151449
* Move isKnownNonNull from private implementation detail of BasicAA to a publicNick Lewycky2012-02-252-16/+16
| | | | | | function that others can use, next to llvm::isIdentifiedObject. llvm-svn: 151446
* fix PR12075, a regression in a recent transform I added. In unreachable ↵Chris Lattner2012-02-241-4/+18
| | | | | | code, gep chains can be infinite. Just like "stripPointerCasts", use a set to keep track of visited instructions so we don't recurse infinitely. llvm-svn: 151383
* Fix typo.Rafael Espindola2012-02-231-1/+1
| | | | llvm-svn: 151238
* Remove extra semi-colons.Chad Rosier2012-02-221-1/+1
| | | | llvm-svn: 151169
* Improve comment. Thanks for Andrew for the suggestion.Rafael Espindola2012-02-221-2/+3
| | | | llvm-svn: 151127
* Semantically revert 151015. Add a comment on why we should be able to assertRafael Espindola2012-02-221-7/+17
| | | | | | | | the dominance once the dominates method is fixed and why we can use the builder's insertion point. Fixes pr12048. llvm-svn: 151125
* s/the the/the/Rafael Espindola2012-02-211-1/+1
| | | | llvm-svn: 151079
* Use more idiomatic assert.Rafael Espindola2012-02-211-2/+2
| | | | llvm-svn: 151026
* Avoid warning on non assert builds.Rafael Espindola2012-02-211-2/+3
| | | | llvm-svn: 151025
* It turns out that with the current scev organization ReuseOrCreateCast cannotRafael Espindola2012-02-211-9/+9
| | | | | | | | | | | | | | know where users will be added. Because of this, it cannot use Builder.GetInsertPoint at all. This patch * removes the FIXME about adding the assert. * adds a comment explaining hy we don't have one. * removes a broken logic that only works for some callers and is not needed since r150884. * adds an assert to caller that would have caught the bug fixed by r150884. llvm-svn: 151015
* Make this a bit prettier and more obvious when a derived type isn'tEric Christopher2012-02-201-1/+3
| | | | | | derived from anything. llvm-svn: 150975
* If a derived type is also a composite type, print that informationEric Christopher2012-02-201-2/+7
| | | | | | too. llvm-svn: 150974
OpenPOWER on IntegriCloud