aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/Analysis
AgeCommit message (Collapse)Author
2012-11-02Add a cost model analysis that allows us to estimate the cost of IR-level ↵Nadav Rotem
instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167324 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-01Revert the series of commits starting with r166578 which introduced theChandler Carruth
getIntPtrType support for multiple address spaces via a pointer type, and also introduced a crasher bug in the constant folder reported in PR14233. These commits also contained several problems that should really be addressed before they are re-committed. I have avoided reverting various cleanups to the DataLayout APIs that are reasonable to have moving forward in order to reduce the amount of churn, and minimize the number of commits that were reverted. I've also manually updated merge conflicts and manually arranged for the getIntPtrType function to stay in DataLayout and to be defined in a plausible way after this revert. Thanks to Duncan for working through this exact strategy with me, and Nick Lewycky for tracking down the really annoying crasher this triggered. (Test case to follow in its own commit.) After discussing with Duncan extensively, and based on a note from Micah, I'm going to continue to back out some more of the more problematic patches in this series in order to ensure we go into the LLVM 3.2 branch with a reasonable story here. I'll send a note to llvmdev explaining what's going on and why. Summary of reverted revisions: r166634: Fix a compiler warning with an unused variable. r166607: Add some cleanup to the DataLayout changes requested by Chandler. r166596: Revert "Back out r166591, not sure why this made it through since I cancelled the command. Bleh, sorry about this! r166591: Delete a directory that wasn't supposed to be checked in yet. r166578: Add in support for getIntPtrType to get the pointer type based on the address space. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167221 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-31Fix a couple of comment typos.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167113 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-29Remove code to saturate profile counts.Bob Wilson
We may need to change the way profile counter values are stored, but saturation is the wrong thing to do. Just remove it for now. Patch by Alastair Murray! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166938 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-26Remove LoopDependenceAnalysis.Benjamin Kramer
It was unmaintained and not much more than a stub. The new DependenceAnalysis pass is both more general and complete. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166810 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-26Add a basic verifier for SCEV's backedge taken counts.Benjamin Kramer
Enabled with -verify-scev. This could be extended significantly but hopefully catches the common cases now. Note that it's not enabled by default in any configuration because the way it tries to distinguish SCEVs is still fragile and may produce false positives. Also the test-suite isn't clean yet, one example is that it fails if a pass drops an NSW bit but it's still present in SCEV's cached. Cleaning up all those cases will take some time. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166786 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-25DependenceAnalysis: Push #includes down into the implementation.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166688 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-24Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow
address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166578 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-19revert r166264 because the LTO build is still failingNadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166340 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-19recommit the patch that makes LSR and LowerInvoke use the TargetTransform ↵Nadav Rotem
interface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166264 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-18Temporarily revert the TargetTransform changes.Bob Wilson
The TargetTransform changes are breaking LTO bootstraps of clang. I am working with Nadav to figure out the problem, but I am reverting it for now to get our buildbots working. This reverts svn commits: 165665 165669 165670 165786 165787 165997 and I have also reverted clang svn 165741 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166168 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-11Remove unnecessary classof()'sSean Silva
isa<> et al. automatically infer when the cast is an upcast (including a self-cast), so these are no longer necessary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165767 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-11Remove extra semicolon.Chad Rosier
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165758 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-11llvm/Analysis/Passes.h: Fix copypasto in createDependenceAnalysisPass().NAKAMURA Takumi
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165709 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-11dependence analysisSebastian Pop
Patch from Preston Briggs <preston.briggs@gmail.com>. This is an updated version of the dependence-analysis patch, including an MIV test based on Banerjee's inequalities. It's a fairly complete implementation of the paper Practical Dependence Testing Gina Goff, Ken Kennedy, and Chau-Wen Tseng PLDI 1991 It cannot yet propagate constraints between coupled RDIV subscripts (discussed in Section 5.3.2 of the paper). It's organized as a FunctionPass with a single entry point that supports testing for dependence between two instructions in a function. If there's no dependence, it returns null. If there's a dependence, it returns a pointer to a Dependence which can be queried about details (what kind of dependence, is it loop independent, direction and distance vector entries, etc). I haven't included every imaginable feature, but there's a good selection that should be adequate for supporting many loop transformations. Of course, it can be extended as necessary. Included in the patch file are many test cases, commented with C code showing the loops and array references. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165708 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-10Add a new interface to allow IR-level passes to access codegen-specific ↵Nadav Rotem
information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165665 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-08Give CaptureTracker::shouldExplore a base implementation. Most users want to doNick Lewycky
the same thing. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165435 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-08Move TargetData to DataLayout.Micah Villmow
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165402 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-04Fix doxygen comment to match parameters' names.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165239 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-27Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru
See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164768 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-27Fix a typo 'iff' => 'if'Sylvestre Ledru
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164767 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-19Fix minor typo in IntervalPartition.hWill Dietz
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164222 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-19InlineCost: Make TotalAllocaSizeRecursiveCaller unsigned to avoid ↵Benjamin Kramer
sign-compare warnings. It's a size, not a cost. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164219 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-19Prevent inlining of callees which allocate lots of memory into a recursive ↵Nadav Rotem
caller. Example: void foo() { ... foo(); // I'm recursive! bar(); } bar() { int a[1000]; // large stack size } rdar://10853263 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164207 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-17Mark unimplemented copy constructors and copy assignment operators as ↵Craig Topper
LLVM_DELETED_FUNCTION. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164015 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-17Remove a couple unused fields. Not detected by Wunused-private-field because ↵Craig Topper
of unimplemented copy constructor and copy assignment operator that make the class look incomplete. Upcoming patch will mark them deleted. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164013 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-05Remove unused typedefs gcc4.8 warns about.Roman Divacky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163225 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-04Make provenance checking conservative in cases whenDan Gohman
pointers-to-strong-pointers may be in play. These can lead to retains and releases happening in unstructured ways, foiling the optimizer. This fixes rdar://12150909. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163180 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-31Clean up ProfileDataLoader a bit.Benjamin Kramer
- Overloading operator<< for raw_ostream and pointers is dangerous, it alters the behavior of code that includes the header. - Remove unused ID. - Use LLVM's byte swapping helpers instead of a hand-coded. - Make ReadProfilingData work directly on a pointer. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162992 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-31Cleanups due to feedback. No functionality change. Patch by Alistair.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162979 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-29fix C++ comment in C headerMichael Liao
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162856 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-29Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer
This disables malloc-specific optimization when -fno-builtin (or -ffreestanding) is specified. This has been a problem for a long time but became more severe with the recent memory builtin improvements. Since the memory builtin functions are used everywhere, this required passing TLI in many places. This means that functions that now have an optional TLI argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead mallocs anymore if the TLI argument is missing. I've updated most passes to do the right thing. Fixes PR13694 and probably others. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162841 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-28Profile: set branch weight metadata with data generated from profiling.Manman Ren
This patch implements ProfileDataLoader which loads profile data generated by -insert-edge-profiling and updates branch weight metadata accordingly. Patch by Alastair Murray. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162799 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-27Remove the the block_node_iterator of Region, replace it by the block_iterator.Hongbin Zheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162672 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-24Forgot to check in ProfileDataTypes.h in r162576Manman Ren
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162578 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-24Profile: move a single enum out of ProfileInfoTypes.h into a new Manman Ren
ProfileDataTypes.h header. With this patch the old and new profiling code can exist side-by-side. The new profiling code will be submitted soon and it only supports insert-edge-profiling for now and will not depend on ProfileInfo. Patch by Alastair Murray. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162576 91177308-0d34-0410-b5e6-96231b3b80d8
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-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-16Teach GVN to reason about edges dominating uses. This allows it to handle casesRafael Espindola
where some fact lake a=b dominates a use in a phi, but doesn't dominate the basic block itself. This feature could also be implemented by splitting critical edges, but at least with the current algorithm reasoning about the dominance directly is faster. The time for running "opt -O2" in the testcase in pr10584 is 1.003 times slower and on gcc as a single file it is 1.0007 times faster. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162023 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-13Fix a documentation typo.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161758 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-10Move BasicBlockEdge to the cpp file. No functionality change.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161663 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-07The dominance computation already has logic for computing if an edge dominatesRafael Espindola
a use or a BB, but it is inline in the handling of the invoke instruction. This patch refactors it so that it can be used in other cases. For example, in define i32 @f(i32 %x) { bb0: %cmp = icmp eq i32 %x, 0 br i1 %cmp, label %bb2, label %bb1 bb1: br label %bb2 bb2: %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] %foo = add i32 %cond, %x ret i32 %foo } GVN should be able to replace %x with 0 in any use that is dominated by the true edge out of bb0. In the above example the only such use is the one in the phi. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161429 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-02include/llvm/Analysis/RegionInfo.h: Appease msvc.NAKAMURA Takumi
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161179 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-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-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-18SCEVTraversal: Add a visited set.Andrew Trick
Expression trees may be DAGs. Make sure traversal has linear complexity. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160426 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-17Allow for customized graph edge pruning in PostOrderIterator.hJakob Stoklund Olesen
Make it possible to prune individual graph edges from a post-order traversal by specializing the po_iterator_storage template. Previously, it was only possible to prune full graph nodes. Edge pruning makes it possible to remove loop back-edges, for example. Also replace the existing DFSetTraits customization hook with a po_iterator_storage method for observing the post-order. DFSetTraits was only used by LoopIterator.h which now provides a po_iterator_storage specialization. Thanks to Sean and Chandler for reviewing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160366 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-29 13:57:26 +0000