aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis
AgeCommit message (Collapse)Author
2012-08-24BranchProb: modify the definition of an edge in BranchProbabilityInfo to handleManman Ren
the case of multiple edges from one block to another. A simple example is a switch statement with multiple values to the same destination. The definition of an edge is modified from a pair of blocks to a pair of PredBlock and an index into the successors. Also set the weight correctly when building SelectionDAG from LLVM IR, especially when converting a Switch. IntegersSubsetMapping is updated to calculate the weight for each cluster. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162572 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-24Fix floating-point divide by zero, in a case where the value was not going ↵Richard Smith
to be used anyway. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162518 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-22Reduce duplicated hash map lookups.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162362 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-17MemoryBuiltins: Properly guard ObjectSizeOffsetVisitor against cycles in the IR.Benjamin Kramer
The previous fix only checked for simple cycles, use a set to catch longer cycles too. Drop the broken check from the ObjectSizeOffsetEvaluator. The BoundsChecking pass doesn't have to deal with invalid IR like InstCombine does. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162120 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-17Guard MemoryBuiltins against self-looping GEPs, which can occur in ↵Benjamin Kramer
unreachable code due to constant propagation. Fixes PR13621. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162098 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-15Set the branch probability of branching to the 'normal' destination of an invokeBill Wendling
instruction to something absurdly high, while setting the probability of branching to the 'unwind' destination to the bare minimum. This should set cause the normal destination's invoke blocks to be moved closer to the invoke. PR13612 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161944 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-13MemoryDependenceAnalysis attempts to find the first memory dependency for ↵Nadav Rotem
function calls. Currently, if GetLocation reports that it did not find a valid pointer (this is the case for volatile load/stores), we ignore the result. This patch adds code to handle the cases where we did not obtain a valid pointer. rdar://11872864 PR12899 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161802 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-07PR13095: Give an inline cost bonus to functions using byval arguments.Benjamin Kramer
We give a bonus for every argument because the argument setup is not needed anymore when the function is inlined. With this patch we interpret byval arguments as a compact representation of many arguments. The byval argument setup is implemented in the backend as an inline memcpy, so to model the cost as accurately as possible we take the number of pointer-sized elements in the byval argument and give a bonus of 2 instructions for every one of those. The bonus is capped at 8 elements, which is the number of stores at which the x86 backend switches from an expanded inline memcpy to a real memcpy. It would be better to use the real memcpy threshold from the backend, but it's not available via TargetData. This change brings the performance of c-ray in line with gcc 4.7. The included test case tries to reproduce the c-ray problem to catch regressions for this benchmark early, its performance is dominated by the inline decision of a specific call. This only has a small impact on most code, more on x86 and arm than on x86_64 due to the way the ABI works. When building LLVM for x86 it gives a small inline cost boost to virtually any function using StringRef or STL allocators, but only a 0.01% increase in overall binary size. The size of gcc compiled by clang actually shrunk by a couple bytes with this patch applied, but not significantly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161413 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-07Fix PR13412, a nasty miscompile due to the interleavedChandler Carruth
instsimplify+inline strategy. The crux of the problem is that instsimplify was reasonably relying on an invariant that is true within any single function, but is no longer true mid-inline the way we use it. This invariant is that an argument pointer != a local (alloca) pointer. The fix is really light weight though, and allows instsimplify to be resiliant to these situations: when checking the relation ships to function arguments, ensure that the argumets come from the same function. If they come from different functions, then none of these assumptions hold. All credit to Benjamin Kramer for coming up with this clever solution to the problem. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161410 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-02Implement the block_iterator of Region based on df_iterator.Hongbin Zheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161177 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-01Stay rational; don't assert trying to take the square root of a negative value.Nick Lewycky
If it's negative, the loop is already proven to be infinite. Fixes PR13489! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161107 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-30When constant folding GEP expressions, keep the address space information of ↵Nadav Rotem
pointers. Together with Ran Chachick <ran.chachick@intel.com> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160954 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-27fix PR13390: do not loop forever with self-referencing self instructionsNuno Lopes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160876 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-25revert r160742: it's breaking CMake buildNuno Lopes
original commit msg: MemoryBuiltins: add support to determine the size of strdup'ed non-constant strings git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160751 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-25MemoryBuiltins: add support to determine the size of strdup'ed non-constant ↵Nuno Lopes
strings git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160742 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-25When folding a load from a global constant, if the load started in the middleDuncan Sands
of an array element (rather than at the beginning of the element) and extended into the next element, then the load from the second element was being handled wrong due to incorrect updating of the notion of which byte to load next. This fixes PR13442. Thanks to Chris Smowton for reporting the problem, analyzing it and providing a fix. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160711 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-24teach objectsize about strdup() and strndup()Nuno Lopes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160676 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-23Fix a typo (the the => the)Sylvestre Ledru
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160621 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-20baby steps toward fixing some problems with inbound GEPs that overflow, as ↵Nuno Lopes
discussed 2 months ago or so. Make sure we do not emit index computations with NSW flags so that we dont get an undef value if the GEP overflows git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160589 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-20Remove unused private member variables uncovered by the recent changes to ↵Benjamin Kramer
clang's -Wunused-private-field. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160583 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-15Move llvm/Support/TypeBuilder.h -> llvm/TypeBuilder.h. This completesChandler Carruth
the move of *Builder classes into the Core library. No uses of this builder in Clang or DragonEgg I could find. If there is a desire to have an IR-building-support library that contains all of these builders, that can be easily added, but currently it seems likely that these add no real overhead to VMCore. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160243 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-13LSR Fix: check SCEV expression safety before expansion.Andrew Trick
All SCEV expressions used by LSR formulae must be safe to expand. i.e. they may not contain UDiv unless we can prove nonzero denominator. Fixes PR11356: LSR hoists UDiv. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160205 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-13IVUsers should only generate SCEV's for values that are safe to speculate.Andrew Trick
This allows SCEVExpander to run on the IV expressions. This codifies an assumption made by LSR to complete the fix for PR11356, but I haven't been able to generate a separate unit test for this part. I'm adding it as an extra safety check. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160204 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-13Factor SCEV traversal code so I can use it elsewhere. No functionality.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160203 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-09Delete code for folding undefs in ScalarEvolution. It's invalid inDan Gohman
obscure ways, and it isn't actually important in the real world. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159969 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-03PHINode::hasConstantValue(): return undef if the PHI is fully recursive.Nuno Lopes
Thanks Duncan for the idea git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159687 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-03fold PHI nodes in SizeOffsetEvaluator whenever possible.Nuno Lopes
Unfortunately this change requires the cache map to hold WeakVHs instead git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159667 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-30Reduce use list thrashing by using DenseMap's find_as for maps with ↵Benjamin Kramer
ValueHandle keys. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159497 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-29RefreshCallGraph: ignore 'invoke intrinsic'. IntrinsicInst doesnt not ↵Nuno Lopes
recognize invoke, and shouldnt at this point, since the rest of LLVM codebase doesnt expect invoke of intrinsics git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159441 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-29Update the CMake files.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159417 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-29The DIBuilder class is just a wrapper around debug info creationBill Wendling
(a.k.a. MDNodes). The module doesn't belong in Analysis. Move it to the VMCore instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159414 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-28If the step value is a constant zero, the loop isn't going to terminate. FixesNick Lewycky
the assert reported in PR13228! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159393 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-28MemoryBuiltins:Nuno Lopes
- recognize C++ new(std::nothrow) friends - ignore ExtractElement and ExtractValue instructions in size/offset analysis (all easy cases are probably folded away before we get here) - also recognize realloc as noalias git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159356 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-28make LazyValueInfo analyze the default case of switch statements (we know ↵Nuno Lopes
that in the default branch the value cannot be any of the switch cases) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159353 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-28make LVI::getEdgeValue() always intersect the constraints of the edge with ↵Nuno Lopes
the range of the block. Previously it was only performing the intersection for a few cases, thus losing precision git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159320 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-28Fix cmake failure from moving files around.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159314 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-28Move lib/Analysis/DebugInfo.cpp to lib/VMCore/DebugInfo.cpp andBill Wendling
include/llvm/Analysis/DebugInfo.h to include/llvm/DebugInfo.h. The reasoning is because the DebugInfo module is simply an interface to the debug info MDNodes and has nothing to do with analysis. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159312 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-26Reduce indentation in function. Rearrange some methods. No functionality change.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159239 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-26Revamp how debugging information is emitted for debug info objects.Bill Wendling
It's not necessary for each DI class to have its own copy of `print' and `dump'. Instead, just give DIDescriptor those methods and have it call the appropriate debugging printing routine based on the type of the debug information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159237 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-26Enable the new LoopInfo algorithm by default.Andrew Trick
The primary advantage is that loop optimizations will be applied in a stable order. This helps debugging and unit test creation. It is also a better overall implementation without pathologically bad performance on deep functions. On large functions (llvm-stress --size=200000 | opt -loops) Before: 0.1263s After: 0.0225s On deep functions (after tweaking llvm-stress, thanks Nadav): Before: 0.2281s After: 0.0227s See r158790 for more comments. The loop tree is now consistently generated in forward order, but loop passes are applied in reverse order over the program. If we have a loop optimization that prefers forward order, that can easily be achieved by adding a different type of LoopPassManager. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159183 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-26Remove unnecessary FIXMEAndrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159182 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-25check for the NoAlias attribute through CallSiteNuno Lopes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159145 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-24llvm/lib: [CMake] Add explicit dependency to intrinsics_gen.NAKAMURA Takumi
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159112 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-22simplify code from previous commits (Thanks Duncan)Nuno Lopes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158999 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-22remove extractMallocCallFromBitCast, since it was tailor maded for its sole ↵Nuno Lopes
user. Update GlobalOpt accordingly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158952 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-21Add support for invoke to the MemoryBuiltin analysid.Nuno Lopes
Update comments accordingly. Make instcombine remove useless invokes to C++'s 'new' allocation function (test attached). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158937 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-21fix build in C++11 mode.Nuno Lopes
Thanks to Chandler for pointing out the problem. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158928 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-21hopefully fix the buildbots: some tests have wrong definitions of malloc ↵Nuno Lopes
and were crashing this code on 64 bits machines git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158923 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-21refactor the MemoryBuiltin analysis:Nuno Lopes
- provide more extensive set of functions to detect library allocation functions (e.g., malloc, calloc, strdup, etc) - provide an API to compute the size and offset of an object pointed by Move a few clients (GVN, AA, instcombine, ...) to the new API. This implementation is a lot more aggressive than each of the custom implementations being replaced. Patch reviewed by Nick Lewycky and Chandler Carruth, thanks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158919 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-20A new algorithm for computing LoopInfo. Temporarily disabled.Andrew Trick
-stable-loops enables a new algorithm for generating the Loop forest. It differs from the original algorithm in a few respects: - Not determined by use-list order. - Initially guarantees RPO order of block and subloops. - Linear in the number of CFG edges. - Nonrecursive. I didn't want to change the LoopInfo API yet, so the block lists are still inclusive. This seems strange to me, and it means that building LoopInfo is not strictly linear, but it may not be a problem in practice. At least the block lists start out in RPO order now. In the future we may add an attribute or wrapper analysis that allows other passes to assume RPO order. The primary motivation of this work was not to optimize LoopInfo, but to allow reproducing performance issues by decomposing the compilation stages. I'm often unable to do this with the current LoopInfo, because the loop tree order determines Loop pass order. Serializing the IR tends to invert the order, which reverses the optimization order. This makes it nearly impossible to debug interdependent loop optimizations such as LSR. I also believe this will provide more stable performance results across time. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158790 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-02 09:24:41 +0000