search for: lengauer

...h/Embed/dom.pdf, > Figure 5, it was ~30% faster (AFAIK, Jeanne Ferrante is somewhat > responsible for both algorithms :P). It is also a lot simpler to > explain, IMHO. There is a followup paper from other authors (including Tarjan himself) that discusses some implementation tricks for the Lengauer-Tarjan algorithm: http://www.cs.princeton.edu/~rwerneck/docs/GWTTA04.pdf They cite personal communication from Keith Cooper that a later more careful implementation of Lengauer-Tarjan led to different benchmark results than what they published. I added those tricks and some others to LLVM's i...

On Fri, Jan 6, 2012 at 8:17 PM, Chris Lattner <clattner at apple.com> wrote: > > On Jan 6, 2012, at 5:08 PM, Chris Lattner wrote: > >>>> >>>> It's very like SSA construction, but must make provision >>>> testing anti dependences.  I had planned to use dominance frontiers to >>>> guide placement of phi nodes, as usual. >>>

...t; Figure 5, it was ~30% faster (AFAIK, Jeanne Ferrante is somewhat > responsible for both algorithms :P). It is also a lot simpler to > explain, IMHO. > > > There is a followup paper from other authors (including Tarjan himself) that > discusses some implementation tricks for the Lengauer-Tarjan algorithm: Ah, i was referring to the *dominance frontier* computation, not the dominator computation. If you look, you'll see there is an algorithm in the paper that computes dominance frontiers touching only the nodes that are *actually in* the dominance frontier :) The algorithm in...

I found the chapters in Engineering a Compiler (Cooper and Torczon) perfectly match the code generator of LLVM. And this paper: Lengauer and Tarjan, A Fast Algorithm for Finding Dominators in a Flowgraph, ACM TOPLAS, Vol 1 , No.1, July 1979 I also would like to know more papers/books whose algorithms are implemented in LLVM. 在 星期二 19 十二月 2006 22:13，Fredrik Svensson 写道： > Hi, > > As Christmas approaches rapidly I would lik...

...as a Google Doc <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing> if you prefer so. Please let us know what you think. ~Kuba ======================================================================= *1. Context* Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the (post)dominator tree. The only way to update it is by manually setting IDoms which is not obvious in many cases and can be extremely error-prone. And because updating it manually is so difficult, programmers tend to just recompute it after changing the CFG (by not AU.a...

...on improving the DominatorTree and PostDominatorTree in LLVM. The RFC that explains the motivations and plans can be found here: http://lists.llvm.org/pipermail/llvm-dev/2017-June/114045.html . Here’s a short summary of what changed upstream since posting it: - We switched from the Simple Lengauer-Tarjan algorithm for computing dominators to Semi-NCA, which is a bit faster in most cases. Although it is possible to construct a CFG that triggers the pathological quadratic complexity of Semi-NCA, we weren’t able to observe it in practice. - DomTreeNodes now automatically store t...

...F65OTfhSMaNHQ/edit?usp=sharing> > > if you prefer so. Please let us know what you think. > > > > ~Kuba > > > > ======================================================================= > > > > *1. Context* > > > > Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the > > (post)dominator tree. The only way to update it is by manually setting > > IDoms which is not obvious in many cases and can be extremely > > error-prone. > > And because updating it manually is so difficult, programmers tend to > > jus...

...ption below, or the ROCR website: http://rocr.bioinf.mpi-sb.mpg.de. You can get a short overview by typing 'demo(ROCR)'. Any kind of feedback (questions, comments, suggestions, bug reports) is very welcome. Best regards, the ROCRs (Tobias Sing, Oliver Sander, Niko Beerenwinkel, Thomas Lengauer) Package description: ------------------------- ROC graphs, sensitivity/specificity curves, lift charts, and precision/recall plots are popular examples of trade-off visualizations for specific pairs of performance measures. ROCR is a flexible tool for creating cutoff-parametrized 2D performanc...

...ption below, or the ROCR website: http://rocr.bioinf.mpi-sb.mpg.de. You can get a short overview by typing 'demo(ROCR)'. Any kind of feedback (questions, comments, suggestions, bug reports) is very welcome. Best regards, the ROCRs (Tobias Sing, Oliver Sander, Niko Beerenwinkel, Thomas Lengauer) Package description: ------------------------- ROC graphs, sensitivity/specificity curves, lift charts, and precision/recall plots are popular examples of trade-off visualizations for specific pairs of performance measures. ROCR is a flexible tool for creating cutoff-parametrized 2D performanc...

...* Andrew added support for a new LLVM "readcyclecounter" intrinsic, for accessing low-level target timing interfaces. * LLVM now supports llvm.stacksave/llvm.stackrestore intrinsics, for proper C99 Variable Length Array support. * Nate reimplemented post-dominator analysis using the Lengauer and Tarjan algorithm, replacing the old iterative implementation. On one extreme example his implementation is 40x faster than the old one (PR681) and uses far less memory. * Daniel Berlin contributed an ET-Forest implementation, which replaces the old LLVM DominatorSet with a far more eff...

After running through bugpoint, I get this reduced function You can reproduce the problem with: opt bugpoint-reduced-function.bc -break-crit-edges -adce -verify Bugpoint is currently trying to narrow down which block breaks this, but is so far failing. It seems to be running out of memory rather than failing on a particular block. This is on freebsd 5.4, X86, llvm is compiled with gcc 3.4.2

...arvey, and K. Kennedy (http://www.hipersoft.rice.edu/grads/publications/dom14.pdf). It is not the most algorithmically-efficient algorithm for computing dominance frontiers, but the authors claim that it runs faster in practice than other more algorithmically -efficient algorithms such as the Lengauer-Tarjan algorithm. The algorithm by Cooper, Harvey, and Kennedy also has the added benefit that it is easier to implement, and consequently easier to get correct. I would like to contribute the code back to LLVM if you want it. However, there are a few points I should bring up. 1) I'm sure...

Please take a look: http://llvm.org/docs/ReleaseNotes.html -Chris -- http://nondot.org/sabre/ http://llvm.org/

...adds --load options to the program script for a compiled program. This means that many programs that require native libraries (such as X11 libraries) will now work with LLVM and the JIT without tweaking the script. 10. The LLVM dominator analyses were completely rewritten to use the Lengauer & Tarjan algorithm, which speeds up gccas quite a bit in some large testcases. 10. The LLVM C++ front-end in particular has had a number of important bugfixes and improvements. We can now compile and run a large number of C++ programs "off the shelf", including LLVM itse...

...that support them (e.g. X86). * The -instcombine pass has a framework and implementation for simplifying code based on whether computed bits are demanded or not, based on Nate's design and implementation in the code generator. * Nate reimplemented post-dominator analysis using the Lengauer and Tarjan algorithm, replacing the old iterative implementation. On one extreme example his implementation is 40x faster than the old one (PR681) and uses far less memory. * Daniel Berlin contributed an ET-Forest implementation, which replaces the old LLVM DominatorSet with a far...

...mework and implementation for simplifying > code based on whether computed bits are demanded or not, based on > Nate's design and implementation in the code generator. Try to reword and get rid of one "based on". > * Nate reimplemented post-dominator analysis using the Lengauer and > Tarjan algorithm, replacing the old iterative implementation. On one > extreme example his implementation is 40x faster than the old one > (PR681) and uses far less memory. > * Daniel Berlin contributed an ET-Forest implementation, which > replaces the old LLVM Domina...

...e a parameterized target interface and to take advantage of strided loads on targets that support them (e.g. X86). 13. The -instcombine pass now uses information about whether individual bits are actually used to simplify code. 14. Nate reimplemented post-dominator analysis using the Lengauer and Tarjan algorithm, replacing the old iterative implementation. On one extreme example (PR681) his implementation is 40x faster than the old one and uses 19x less memory. 15. Daniel Berlin contributed an ET-Forest implementation, which replaces the old LLVM DominatorSet with...