Displaying 17 results from an estimated 17 matches for "lengauer".
2012 Jan 07
0
[LLVMdev] dominance frontiers
...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...
2012 Jan 07
2
[LLVMdev] dominance frontiers
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.
>>>
2012 Jan 07
1
[LLVMdev] dominance frontiers
...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...
2006 Dec 20
1
[LLVMdev] Books, papers and information
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...
2017 Jun 13
9
RFC: Dynamic dominators
...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...
2017 Jul 17
2
An update on the DominatorTree and incremental dominators
...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...
2017 Jun 13
2
RFC: Dynamic dominators
...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...
2005 Feb 28
0
New package: ROCR (Visualizing classifier performance)
...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...
2005 Feb 28
0
New package: ROCR (Visualizing classifier performance)
...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...
2006 Apr 20
0
[LLVMdev] First draft of release notes done
...* 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...
2005 Dec 24
4
[LLVMdev] Weird memory bug
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
2007 Apr 20
2
[LLVMdev] post dominance frontier fix
...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...
2006 Apr 19
4
[LLVMdev] First draft of release notes done
Please take a look:
http://llvm.org/docs/ReleaseNotes.html
-Chris
--
http://nondot.org/sabre/
http://llvm.org/
2003 Dec 18
0
LLVM 1.1 Release & Status Update
...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...
2006 Apr 14
2
[LLVMdev] [DRAFT] LLVM 1.7 release announcement notes [DRAFT]
...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...
2006 Apr 20
0
[LLVMdev] [DRAFT] LLVM 1.7 release announcement notes [DRAFT]
...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...
2006 Apr 20
0
LLVM 1.7 Release!
...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...