| 55be644df6e8b8ba08ae789ee440c798f21974a0 |
|
23-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Convert a std::vector to a SmallVector for another 5.4% speedup on domtree.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124065 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 54cdad97eb77caf841ade5827a1d5da6b2d89df3 |
|
23-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
In the simpler version of the link-eval data structure that we use in dominator
computation, the Ancestor field is always set to the Parent, so we can remove
the explicit link entirely and merge the Parent and Ancestor fields. Instead of
checking for whether an ancestor exists for a node or not, we simply check
whether the node has already been processed. This is simpler if Compress is
inlined into Eval, so I did that as well.
This is about a 3% speedup running -domtree on test-suite + SPEC2000 & SPEC2006,
but it also opens up some opportunities for further improvement.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124061 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 11e222da1fe498a3c528d197ab57982e3bb5762d |
|
23-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Remove useless struct fields.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124058 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 907b56ce7ab26222fa128d5062f8dddf11c81603 |
|
23-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Convert a std::vector to a SmallVector.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124055 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 5c96c69161aa4480c432027e363d0ea1aa34acee |
|
23-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Simplify some code now that we've removed the more optimal (but slower) version
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
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 113328db1b6c71d6bb8f62ebef193efb1a44f1a4 |
|
11-Jan-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Put the Dominator improvements back in. They were not the cause of bootstrap miscomparisons.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123273 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| cbf39b58919497f711de24fa687b044805f58ae7 |
|
11-Jan-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Speculatively revert the recent improvements to Dominators.h in an attempt to track down the gcc bootstrap miscompare.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123254 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 94942cec11ba3dc2592d1195324d2315a58d7711 |
|
02-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Fix a typo in a variable name.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122691 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 63e07d72f8175cd2d74f0693edf1b0429580d64d |
|
02-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Move a load into the only branch where it is used and eliminate a temporary.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122690 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 2a8c22aa6824143fdf4c00d4486c65eca26f6c9f |
|
02-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Add the explanatory comment from r122680's commit message to the code itself.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122689 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 19feb4ca8a804aeda650cb1f700a89c2f2324b77 |
|
02-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Tidy up indentation.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122688 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| a4d93162cbb95423a9c8f35e38747c08aa8a3516 |
|
02-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Fix a typo, which should also fix the failure on llvm-x86_64-linux-checks.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122687 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| c9e152b778715afc5cdfdb98cb0e98757ed827d8 |
|
02-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Remove the #ifdef'd code for balancing the eval-link data structure. It doesn't
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
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 8252ad1351594039fa5d6633ff3eef1bafb7fdf9 |
|
02-Jan-2011 |
Cameron Zwarich <zwarich@apple.com> |
Speed up dominator computation some more by optimizing bucket processing. When
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
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 2974b6ffbcffcd7fb02958c7382edf45e4a30f14 |
|
23-Nov-2010 |
Cameron Zwarich <zwarich@apple.com> |
Optimize a common case in the Lengauer-Tarjan dominators algorithm. This gives a
9.7% speedup running domtree on test-suite.
Reviewed by Chris Lattner.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120003 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| a53fe6070cae7d2feccb542b8ba24b37d3fdd027 |
|
23-Oct-2010 |
Benjamin Kramer <benny.kra@googlemail.com> |
SmallVectorize.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117213 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 0764e39a921ae424e2ac8c7ba114b67040eba8f6 |
|
13-Jul-2010 |
Eric Christopher <echristo@apple.com> |
80-columns
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108228 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| da995609e6e963eaa77346d43b0a33b81e53a785 |
|
08-Jul-2010 |
Gabor Greif <ggreif@gmail.com> |
only dereference iterator once in the loop
(by caching the result we save a potentially expensive dereference)
also use typedefs to shorten type declarations
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107883 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 24dcbaf75618277b049ddf488a37ede3177613dc |
|
16-Jan-2010 |
Tobias Grosser <grosser@fim.uni-passau.de> |
Fix PR6047
Nodes that had children outside of the post dominator tree (infinite loops)
where removed from the post dominator tree. This seems to be wrong. Leave them
in the tree.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@93633 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 365ccd3a919b017f79140028dac15ef0c70641dd |
|
08-Jan-2010 |
Tobias Grosser <grosser@fim.uni-passau.de> |
Remove workaround in PostDominators
Remove a FIXME and unify code that was necessary to work around broken
updateDFSNumbers(). Before updateDFSNumbers() did not work correctly for post
dominators.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92968 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| d68a07650cdb2e18f18f362ba533459aa10e01b6 |
|
05-Jan-2009 |
Dan Gohman <gohman@apple.com> |
Tidy up #includes, deleting a bunch of unnecessary #includes.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61715 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 34cd4a484e532cc463fd5a4bf59b88d13c5467c1 |
|
05-May-2008 |
Evan Cheng <evan.cheng@apple.com> |
Fix more -Wshorten-64-to-32 warnings.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50659 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 46bb007014414c966586a983dbf24f38490e0f22 |
|
04-May-2008 |
Owen Anderson <resistor@mac.com> |
Fix PR1098 by correcting the postdominators analysis.
Patch by Florian Brandner.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50628 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 1f23e163190f85e46f2009bf43ee4fe8299044e4 |
|
16-Apr-2008 |
Owen Anderson <resistor@mac.com> |
Major repairs to the post-dominators implementation. Patch from Florian Brandner!
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49768 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 7ed47a13356daed2a34cd2209a31f92552e3bdd8 |
|
29-Dec-2007 |
Chris Lattner <sabre@nondot.org> |
Don't attribute in file headers anymore. See llvmdev for the
discussion of this change. Boy are my fingers tired. ;-)
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45411 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 5d32ec4cb002973cb12bc21a3fe12364794168c8 |
|
31-Oct-2007 |
Owen Anderson <resistor@mac.com> |
Some fixes to get MachineDomTree working better.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43541 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 4d6d5783d8f803a9ae1ad64b16643f7ddeacbc1b |
|
25-Oct-2007 |
Owen Anderson <resistor@mac.com> |
Make it possible for DomTreeBase to be constructed from MachineFunction's as well as just Function's.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43321 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 7b714321df4d286018d594c9c9f132f343dbabdc |
|
18-Oct-2007 |
Owen Anderson <resistor@mac.com> |
Move Split<...>() into DomTreeBase. This should make the #include's of DominatorInternals.h
in CodeExtractor and LoopSimplify unnecessary.
Hartmut, could you confirm that this fixes the issues you were seeing?
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43115 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 05d2318fbde7b603bd6de690f18d48e0ef44d81d |
|
17-Oct-2007 |
Owen Anderson <resistor@mac.com> |
Move splitBlock into DomTreeBase from DomTree.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43059 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 49b653aa6aaaed17be1c611c5722b5b9ff31a905 |
|
16-Oct-2007 |
Owen Anderson <resistor@mac.com> |
Template DominatorTreeBase by node type. This is the next major step towards
having dominator information on MBB's.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43036 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 9cb7f49ee9d8c77f5ae82e36befde2b3094fdd02 |
|
03-Oct-2007 |
Owen Anderson <resistor@mac.com> |
Completely merge the implementation details of DomTree and PostDomTree.
Also, add a FIXME for a bug in PostDomTree calculation I noticed while writing this,
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42593 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| ab528fe0fb7caa96ce789bf872d7058aec8ae7c8 |
|
30-Sep-2007 |
Owen Anderson <resistor@mac.com> |
Template-ize more of the DomTree internal implementation details. Only the calculate() methods for DomTree and PostDomTree remain to be merged/template-ized.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42476 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 3c5f0233e094ec5cea8e0f95af72fe29a7ce851d |
|
29-Sep-2007 |
Duncan Sands <baldrick@free.fr> |
Add newline at end of file.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42470 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 303f47b1dd3166a8abcd5425f863f7b4815a8e42 |
|
28-Sep-2007 |
Owen Anderson <resistor@mac.com> |
Have PostDomTree use the newly templated DFSPass.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42427 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|
| 58ec8825d46085841a1af55ee7f8117ad25ecf2f |
|
28-Sep-2007 |
Owen Anderson <resistor@mac.com> |
Convert DFSPass into a templated friend function, in preparation for making it common to DomTree and PostDomTree.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42420 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/Analysis/DominatorInternals.h
|