aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/Analysis
AgeCommit message (Collapse)Author
2011-01-23Remove friend declaration for removed function.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124057 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23Convert a std::vector to a SmallVector.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124055 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23Simplify some code now that we've removed the more optimal (but slower) versionCameron Zwarich
of the link-eval data structure from dominator computation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124053 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-18There is no point in verifying an analysis that is never updated.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123743 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-18Remove some now-unused DominanceFrontier methods.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123726 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-16remove the partial specialization pass. It is unmaintained and has bugs.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123554 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-14Move some shift transforms out of instcombine and into InstructionSimplify.Duncan Sands
While there, I noticed that the transform "undef >>a X -> undef" was wrong. For example if X is 2 then the top two bits must be equal, so the result can not be anything. I fixed this in the constant folder as well. Also, I made the transform for "X << undef" stronger: it now folds to undef always, even though X might be zero. This is in accordance with the LangRef, but I must admit that it is fairly aggressive. Also, I added "i32 X << 32 -> undef" following the LangRef and the constant folder, likewise fairly aggressive. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123417 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-13Add single entry / single exit accessors.Tobias Grosser
Add methods for accessing the (single) entry / exit edge of a region. If no such edge exists, null is returned. Both accessors return the start block of the corresponding edge. The edge can finally be formed by utilizing Region::getEntry() or Region::getExit(); Contributed by: Andreas Simbuerger <simbuerg@fim.uni-passau.de> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123410 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11Put the Dominator improvements back in. They were not the cause of bootstrap ↵Jakob Stoklund Olesen
miscomparisons. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123273 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11Speculatively revert the recent improvements to Dominators.h in an attempt ↵Jakob Stoklund Olesen
to track down the gcc bootstrap miscompare. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123254 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11some comment improvements.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123243 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-09Step #2 to improve trip count analysis for loops like this:Chris Lattner
void f(int* begin, int* end) { std::fill(begin, end, 0); } which turns into a != exit expression where one pointer is strided and (thanks to step #1) known to not overflow, and the other is loop invariant. The observation here is that, though the IV is strided by 4 in this case, that the IV *has* to become equal to the end value. It cannot "miss" the end value by stepping over it, because if it did, the strided IV expression would eventually wrap around. Handle this by turning A != B into "A-B != 0" where the A-B part is known to be NUW. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123131 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-09DominatorTree->print() now prints the status of the DFSNumbers correctlyTobias Grosser
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123120 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-08fit in 80 colsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123085 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-08make this file properly self contained.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123059 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-03Stub out a new updating interface to AliasAnalysis, allowing stateful ↵Owen Anderson
analyses to be informed when a pointer value has potentially become escaping. Implementations can choose to either fall back to conservative responses for that value, or may recompute their analysis to accomodate the change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122777 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-03Add spliceFunction to the CallGraph interface. This allows users to efficientlyNick Lewycky
update a callGraph when performing the common operation of splicing the body to a new function and updating all callers (such as via RAUW). No users yet, though this is intended for DeadArgumentElimination as part of PR8887. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122728 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner
so that Dominators.h is *just* domtree. Also prune #includes a bit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122714 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Remove an unused member function.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122693 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Fix a typo in a variable name.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122691 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Move a load into the only branch where it is used and eliminate a temporary.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122690 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Add the explanatory comment from r122680's commit message to the code itself.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122689 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Tidy up indentation.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122688 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Fix a typo, which should also fix the failure on llvm-x86_64-linux-checks.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122687 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Remove the #ifdef'd code for balancing the eval-link data structure. It doesn'tCameron Zwarich
compile, and everyone's tests have shown it to be slower in practice, even for quite large graphs. I also hope to do an optimization that is only correct with the simpler data structure, which would break this even further. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122684 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Speed up dominator computation some more by optimizing bucket processing. WhenCameron Zwarich
naively implemented, the Lengauer-Tarjan algorithm requires a separate bucket for each vertex. However, this is unnecessary, because each vertex is only placed into a single bucket (that of its semidominator), and each vertex's bucket is processed before it is added to any bucket itself. Instead of using a bucket per vertex, we use a single array Buckets that has two purposes. Before the vertex V with DFS number i is processed, Buckets[i] stores the index of the first element in V's bucket. After V's bucket is processed, Buckets[i] stores the index of the next element in the bucket to which V now belongs, if any. Reading from the buckets can also be optimized. Instead of processing the bucket of V's parent at the end of processing V, we process the bucket of V itself at the beginning of processing V. This means that the case of the root vertex can be simplified somewhat. It also means that we don't need to look up the DFS number of the semidominator of every node in the bucket we are processing, since we know it is the current index being processed. This is a 6.5% speedup running -domtree on test-suite + SPEC2000/2006, with larger speedups of around 12% on the larger benchmarks like GCC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122680 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-28Clarify that InstructionSimplify only returns values that dominate theDuncan Sands
original instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122601 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-28Small optimization to speed up replacementPreservesLCSSAForm.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122600 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-26implement enough of the memset inference algorithm to recognize and insert Chris Lattner
memsets. This is still missing one important validity check, but this is enough to compile stuff like this: void test0(std::vector<char> &X) { for (std::vector<char>::iterator I = X.begin(), E = X.end(); I != E; ++I) *I = 0; } void test1(std::vector<int> &X) { for (long i = 0, e = X.size(); i != e; ++i) X[i] = 0x01010101; } With: $ clang t.cpp -S -o - -O2 -emit-llvm | opt -loop-idiom | opt -O3 | llc to: __Z5test0RSt6vectorIcSaIcEE: ## @_Z5test0RSt6vectorIcSaIcEE ## BB#0: ## %entry subq $8, %rsp movq (%rdi), %rax movq 8(%rdi), %rsi cmpq %rsi, %rax je LBB0_2 ## BB#1: ## %bb.nph subq %rax, %rsi movq %rax, %rdi callq ___bzero LBB0_2: ## %for.end addq $8, %rsp ret ... __Z5test1RSt6vectorIiSaIiEE: ## @_Z5test1RSt6vectorIiSaIiEE ## BB#0: ## %entry subq $8, %rsp movq (%rdi), %rax movq 8(%rdi), %rdx subq %rax, %rdx cmpq $4, %rdx jb LBB1_2 ## BB#1: ## %for.body.preheader andq $-4, %rdx movl $1, %esi movq %rax, %rdi callq _memset LBB1_2: ## %for.end addq $8, %rsp ret git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122573 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-26move isBytewiseValue out to ValueTracking.h/cppChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122565 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-22Constify.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122447 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-21Pull a few more simplifications out of instcombine (there are stillDuncan Sands
plenty left though!), in particular for multiplication. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122330 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-15Move Value::getUnderlyingObject to be a standaloneDan Gohman
function so that it can live in Analysis instead of VMCore. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121885 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-15Move Sub simplifications and additional Add simplifications out ofDuncan Sands
instcombine and into InstructionSimplify. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121861 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-10Introduce a new PartialAlias response for AliasAnalysis. For mostDan Gohman
AliasAnalysis consumers, PartialAlias will be treated as MayAlias. For AliasAnalysis chaining, MayAlias says "procede to the next analysis". PartialAlias will be used to indicate that the query should terminate, even though it didn't reach MustAlias or NoAlias. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121507 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-08Add support to create debug info for functions and methods.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121281 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-08Add support to create class type.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121279 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-08Add support to create vector, array, enums etc...Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121224 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-08Global variable does not need linkage name.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121212 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-07Add support to create local variable's debug info.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121211 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-07Add support to create variables, structs etc.. using DIBuilder.Devang Patel
This is still work in progress. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121205 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-06Fix PR8728, a miscompilation I recently introduced. When optimizingChris Lattner
memcpy's like: memcpy(A, B) memcpy(A, C) we cannot delete the first memcpy as dead if A and C might be aliases. If so, we actually get: memcpy(A, B) memcpy(A, A) which is not correct to transform into: memcpy(A, A) This patch was heavily influenced by Jakub Staszak's patch in PR8728, thanks Jakub! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120974 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-06add a helper method.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120973 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-30teach DSE to use GetPointerBaseWithConstantOffset to analyzeChris Lattner
may-aliasing stores that partially overlap with different base pointers. This implements PR6043 and the non-variable part of PR8657 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120485 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-30move GetPointerBaseWithConstantOffset out of GVN into ValueTracking.hChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120476 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-30Change the basic block map in LoopInfo from a std::map to a DenseMap. This ↵Cameron Zwarich
is a 16% speedup running loops on test-suite + SPEC2000. Reviewed by Eric Christopher. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120440 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-30Rewrite the main DSE loop to be written in terms of reasoningChris Lattner
about pairs of AA::Location's instead of looking for MemDep's "Def" predicate. This is more powerful and general, handling memset/memcpy/store all uniformly, and implementing PR8701 and probably obsoleting parts of memcpyoptimizer. This also fixes an obscure bug with init.trampoline and i8 stores, but I'm not surprised it hasn't been hit yet. Enhancing init.trampoline to carry the size that it stores would allow DSE to be much more aggressive about optimizing them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120406 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-30death to extraneous \n's.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120405 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-30getLocationForDest should work for memset as well.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120380 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-30clean up handling of 'free', detangling it from everything else.Chris Lattner
It can be seriously improved, but at least now it isn't intertwined with the other logic. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120377 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-09 16:45:50 +0000