aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/Analysis
AgeCommit message (Collapse)Author
2012-03-22Cleanup IVUsers::addUsersIfInteresting.Andrew Trick
Keep the public interface clean, even though LLVM proper does not currently use it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153263 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-16Start removing the use of an ad-hoc 'never inline' set and insteadChandler Carruth
directly query the function information which this set was representing. This simplifies the interface of the inline cost analysis, and makes the always-inline pass significantly more efficient. Previously, always-inline would first make a single set of every function in the module *except* those marked with the always-inline attribute. It would then query this set at every call site to see if the function was a member of the set, and if so, refuse to inline it. This is quite wasteful. Instead, simply check the function attribute directly when looking at the callsite. The normal inliner also had similar redundancy. It added every function in the module with the noinline attribute to its set to ignore, even though inside the cost analysis function we *already tested* the noinline attribute and produced the same result. The only tricky part of removing this is that we have to be able to correctly remove only the functions inlined by the always-inline pass when finalizing, which requires a bit of a hack. Still, much less of a hack than the set of all non-always-inline functions was. While I was touching this function, I switched a heavy-weight set to a vector with sort+unique. The algorithm already had a two-phase insert and removal pattern, we were just needlessly paying the uniquing cost on every insert. This probably speeds up some compiles by a small amount (-O0 compiles with lots of always-inline, so potentially heavy libc++ users), but I've not tried to measure it. I believe there is no functional change here, but yell if you spot one. None are intended. Finally, the direction this is going in is to greatly simplify the inline cost query interface so that we can replace its implementation with a much more clever one. Along the way, all the APIs get simplified, so it seems incrementally good. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152903 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-16Pull the implementation of the code metrics out of the inline costChandler Carruth
analysis implementation. The header was already separated. Also cleanup all the comments in the header to follow a nice modern doxygen form. There is still plenty of cruft here, but some of that will fall out in subsequent refactorings and this was an easy step in the right direction. No functionality changed here. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152898 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-16LSR fix: Add isSimplifiedLoopNest to IVUsers analysis.Andrew Trick
Only record IVUsers that are dominated by simplified loop headers. Otherwise SCEVExpander will crash while looking for a preheader. I previously tried to work around this in LSR itself, but that was insufficient. This way, LSR can continue to run if some uses are not in simple loops, as long as we don't attempt to analyze those users. Fixes <rdar://problem/11049788> Segmentation fault: 11 in LoopStrengthReduce git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152892 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-15Remove all remnants of partial specialization in the cost computationChandler Carruth
side of things. This is all dead code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152759 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-14Extend the inline cost calculation to account for bonuses due toChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152752 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-13enhance jump threading to preserve TBAA information when PRE'ing loads,Chris Lattner
fixing rdar://11039258, an issue that came up when inspecting clang's bootstrapped codegen. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152635 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-13Generalize the "trunc(ptrtoint(x)) - trunc(ptrtoint(y)) ->Duncan Sands
trunc(ptrtoint(x-y))" optimization introduced by Chandler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152626 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-13Uniformize the InstructionSimplify interface by ensuring that all routinesDuncan Sands
take a TargetLibraryInfo parameter. Internally, rather than passing TD, TLI and DT parameters around all over the place, introduce a struct for holding them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152623 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-08Taken into account Duncan's comments for r149481 dated by 2nd Feb 2012:Stepan Dyatkovskiy
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152297 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-08Rotate two of the functions used to count bonuses for the inline costChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152283 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-26Change the implementation of dominates(inst, inst) to one based on what theRafael Espindola
verifier does. This correctly handles invoke. Thanks to Duncan, Andrew and Chris for the comments. Thanks to Joerg for the early testing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151469 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-26Don't call dominates on unreachable instructions.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151466 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-25Move isKnownNonNull from private implementation detail of BasicAA to a publicNick Lewycky
function that others can use, next to llvm::isIdentifiedObject. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151446 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-20Add support for runtime languages on our forward declarations.Eric Christopher
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150973 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-19Remove dead code. Improve llvm_unreachable text. Simplify some control flow.Ahmed Charles
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150918 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-10Make aliasesPointer and aliasesUnknownInst public members of AliasSet.Hal Finkel
These query functions are safe for external use and, furthermore, are the only way to make queries against the "unknown instructions" array. BBVectorize will use these functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150248 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-08Add support for a temporary forward decl type. We want this so weEric Christopher
can rauw forward declarations if we decide to emit the full type. Part of rdar://10809898 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150024 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-08Remove tabs.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150022 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-06DebugInfo: Provide a new hook to encode relationship between a property and ↵Devang Patel
an ivar. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149874 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-05Convert assert(0) to llvm_unreachableCraig Topper
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149849 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-05reapply the patches reverted in r149470 that reenable ConstantDataArray,Chris Lattner
but with a critical fix to the SelectionDAG code that optimizes copies from strings into immediate stores: the previous code was stopping reading string data at the first nul. Address this by adding a new argument to llvm::getConstantStringInfo, preserving the behavior before the patch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149800 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-04Update llvm debug version to support new structure and tag for Objective-C ↵Devang Patel
property's debug info. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149736 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-04Introduce DIObjCProperty. This will be used to encode objective-c property.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149732 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-01SwitchInst refactoring.Stepan Dyatkovskiy
The purpose of refactoring is to hide operand roles from SwitchInst user (programmer). If you want to play with operands directly, probably you will need lower level methods than SwitchInst ones (TerminatorInst or may be User). After this patch we can reorganize SwitchInst operands and successors as we want. What was done: 1. Changed semantics of index inside the getCaseValue method: getCaseValue(0) means "get first case", not a condition. Use getCondition() if you want to resolve the condition. I propose don't mix SwitchInst case indexing with low level indexing (TI successors indexing, User's operands indexing), since it may be dangerous. 2. By the same reason findCaseValue(ConstantInt*) returns actual number of case value. 0 means first case, not default. If there is no case with given value, ErrorIndex will returned. 3. Added getCaseSuccessor method. I propose to avoid usage of TerminatorInst::getSuccessor if you want to resolve case successor BB. Use getCaseSuccessor instead, since internal SwitchInst organization of operands/successors is hidden and may be changed in any moment. 4. Added resolveSuccessorIndex and resolveCaseIndex. The main purpose of these methods is to see how case successors are really mapped in TerminatorInst. 4.1 "resolveSuccessorIndex" was created if you need to level down from SwitchInst to TerminatorInst. It returns TerminatorInst's successor index for given case successor. 4.2 "resolveCaseIndex" converts low level successors index to case index that curresponds to the given successor. Note: There are also related compatability fix patches for dragonegg, klee, llvm-gcc-4.0, llvm-gcc-4.2, safecode, clang. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149481 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-01Revert Chris' commits up to r149348 that started causing VMCoreTests unit ↵Argyrios Kyrtzidis
test to fail. These are: r149348 r149351 r149352 r149354 r149356 r149357 r149361 r149362 r149364 r149365 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149470 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-31remove commented-out code.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149364 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-31remove the last vestiges of llvm::GetConstantStringInfo, in CodeGen.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149356 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-31Change ConstantArray::get to form a ConstantDataArray when possible,Chris Lattner
kicking in the big win of ConstantDataArray. As part of this, change the implementation of GetConstantStringInfo in ValueTracking to work with ConstantDataArray (and not ConstantArray) making it dramatically, amazingly, more efficient in the process and renaming it to getConstantStringInfo. This keeps around a GetConstantStringInfo entrypoint that (grossly) forwards to getConstantStringInfo and constructs the std::string required, but existing clients should move over to getConstantStringInfo instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149351 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-24Split the interesting bits of ConstantFoldLoadThroughGEPConstantExprChris Lattner
out into a new ConstantFoldLoadThroughGEPIndices (more useful) function and rewrite it to be simpler, more efficient, and to handle the new ConstantDataSequential type. Enhance ConstantFoldLoadFromConstPtr to handle ConstantDataSequential. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148786 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-20SCEVExpander fixes. Affects LSR and indvars.Andrew Trick
LSR has gradually been improved to more aggressively reuse existing code, particularly existing phi cycles. This exposed problems with the SCEVExpander's sloppy treatment of its insertion point. I applied some rigor to the insertion point problem that will hopefully avoid an endless bug cycle in this area. Changes: - Always used properlyDominates to check safe code hoisting. - The insertion point provided to SCEV is now considered a lower bound. This is usually a block terminator or the use itself. Under no cirumstance may SCEVExpander insert below this point. - LSR is reponsible for finding a "canonical" insertion point across expansion of different expressions. - Robust logic to determine whether IV increments are in "expanded" form and/or can be safely hoisted above some insertion point. Fixes PR11783: SCEVExpander assert. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148535 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-17Move includes to the .cpp file.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148342 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-11Clarified the SCEV getSmallConstantTripCount interface with in-your-face ↵Andrew Trick
comments. This interface is misleading and dangerous, but it is actually what we need for unrolling. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147926 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-10Enable LSR IV Chains with sufficient heuristics.Andrew Trick
These heuristics are sufficient for enabling IV chains by default. Performance analysis has been done for i386, x86_64, and thumbv7. The optimization is rarely important, but can significantly speed up certain cases by eliminating spill code within the loop. Unrolled loops are prime candidates for IV chains. In many cases, the final code could still be improved with more target specific optimization following LSR. The goal of this feature is for LSR to make the best choice of induction variables. Instruction selection may not completely take advantage of this feature yet. As a result, there could be cases of slight code size increase. Code size can be worse on x86 because it doesn't support postincrement addressing. In fact, when chains are formed, you may see redundant address plus stride addition in the addressing mode. GenerateIVChains tries to compensate for the common cases. On ARM, code size increase can be mitigated by using postincrement addressing, but downstream codegen currently misses some opportunities. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147826 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-07Extended replaceCongruentPhis to handle mixed phi types.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147707 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-07Expose isNonConstantNegative to users of ScalarEvolution.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147700 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-06Put all IVUsers in the processed set. Allow querying IVUsers with ↵Andrew Trick
isIVUserOrOperand. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147686 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-04Generalize isSafeToSpeculativelyExecute to work on arbitraryDan Gohman
Values, rather than just Instructions, since it's interesting for ConstantExprs too. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147560 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-04Simplify more DenseMap.find users.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147550 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-04Simplify code. No functionality change.Benjamin Kramer
Using DenseMap iterators isn't free as they have to check for empty buckets. Dominator queries are common so this gives a minor speedup. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147544 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-29Fix grammar error noticed by Duncan.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147333 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-28Change CaptureTracking to pass a Use* instead of a Value* when a value isNick Lewycky
captured. This allows the tracker to look at the specific use, which may be especially interesting for function calls. Use this to fix 'nocapture' deduction in FunctionAttrs. The existing one does not iterate until a fixpoint and does not guarantee that it produces the same result regardless of iteration order. The new implementation builds up a graph of how arguments are passed from function to function, and uses a bottom-up walk on the argument-SCCs to assign nocapture. This gets us nocapture more often, and does so rather efficiently and independent of iteration order. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147327 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-20Add some constantness to BranchProbabilityInfo and BlockFrequnencyInfo.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146986 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-20Unweaken vtables as per ↵David Blaikie
http://llvm.org/docs/CodingStandards.html#ll_virtual_anch git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146960 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-18Allow inlining of functions with returns_twice calls, if they have theJoerg Sonnenberger
attribute themselve. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146851 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-14Move Instruction::isSafeToSpeculativelyExecute out of VMCore andDan Gohman
into Analysis as a standalone function, since there's no need for it to be in VMCore. Also, update it to use isKnownNonZero and other goodies available in Analysis, making it more precise, enabling more aggressive optimization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146610 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-05Change the Dominators recalculate() function to only rely on GraphTraitsAnna Zaks
This is a patch by Guoping Long! As part of utilizing LLVM Dominator computation in Clang, made two changes to LLVM dominators tree implementation: - (1) Change the recalculate() template function to only rely on GraphTraits. - (2) Add a size() method to GraphTraits template class to query the number of nodes in the graph. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145837 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-02Fix a few more places where TargetData/TargetLibraryInfo is not being passed.Chad Rosier
Add FIXMEs to places that are non-trivial to fix. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145661 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-01Propagate TargetLibraryInfo throughout ConstantFolding.cpp and Chad Rosier
InstructionSimplify.cpp. Other fixups as needed. Part of rdar://10500969 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145559 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-30LSR: handle the expansion of phi operands that use postinc forms of the IV.Andrew Trick
Fixes PR11431: SCEVExpander::expandAddRecExprLiterally(const llvm::SCEVAddRecExpr*): Assertion `(!isa<Instruction>(Result) || SE.DT->dominates(cast<Instruction>(Result), Builder.GetInsertPoint())) && "postinc expansion does not dominate use"' failed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145482 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-04 20:31:49 +0000