search for: irreducible

Hello everybody, I just started implementing a part of my algorithm that deals with irreducible control-flow. Apparently, the LoopInfo analysis does not recognize loops with multiple incoming edges (as of LLVM 2.5). On the mailing list archives I found a few discussions related to irreducible control-flow, but it was never mentioned if it is planned to enhance LoopInfo to also represent such...

It seems that tail duplication can make a reducible CFG irreducible (example below). Is that intentional? Are there other optimizations that have that property? Is irreducibility a problem for existing LLVM passes? It looks like there was once an open project for a pass to make irreducible graphs reducible. Was that ever implemented? - Mark ; "opt -inl...

...e at gmail.com> wrote: > Is irreducibility a problem for existing LLVM passes? There aren't any LLVM passes that expect a reducible CFG at the moment; of course, some passes are more effective with reducible CFGs. > It looks like > there was once an open project for a pass to make irreducible graphs > reducible. Was that ever implemented? There isn't any such pass in trunk LLVM. One could potentially be added, but it would have to be a high-quality implementation, and we'd have to measure the costs and benefits carefully. > ; "opt -inline -tailduplicate" make...

Hey, Thank you for your replies, Chris and Dan. Chris Lattner wrote: >> I am considering writing a patch for LoopInfo instead of creating my own >> data structure for irreducible loops. >> Is such an enhancement desired or even already implemented by someone >> (e.g. in the 2.6 branch)? > I'm not sure that this is a good idea. LoopInfo is clearly defined to > represent "natural" loops (where the header dominates the body of the > loop). Na...

On Sep 28, 2009, at 2:28 AM, Ralf Karrenberg wrote: > Hello everybody, > > I just started implementing a part of my algorithm that deals with > irreducible control-flow. > Apparently, the LoopInfo analysis does not recognize loops with > multiple > incoming edges (as of LLVM 2.5). > On the mailing list archives I found a few discussions related to > irreducible control-flow, but it was never mentioned if it is > planned to > e...

...on the code below. Sounds like it's not a bug. Thanks for the info. - Mark ; Tail duplication yielded this code, which has non-structured control flow. ; Note that "then.i2" and "continue.i3" both have predecessors ; "then.i" and "foo.exit", making an irreducible "X" in the control-flow graph. @x = weak global float 0.000000e+00 define void @test() { entry: %x = load float* @x %b.i = fcmp ogt float %x, 0.000000e+00 %neg = sub float 0.000000e+00, %x %b.i1 = fcmp ogt float %neg, 0.000000e+00 br i1 %b.i, labe...

...around on their own, unconnected to anything in the dot file. This causes upset in the algorithm at the moment, so I was overcoming the problem by running "-simplify-cfg" before structural analysis takes place. My question is this: would the simplify pass ever make a reducible CFG become irreducible? My current inkling is towards no from what I can see in the source code and the documentation. However I was wondering if someone with more experience and understanding of the pass could share some wisdom! If it does, is there a simpler "clean-up" pass that I could run? Best wishes, Jam...

Hi, I've a short question: Does there exist any llvm pass that transforms an irreducible CFG into a reducible one? So far i didn't find any implementation on the internet, only an old feature request from 2003: https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_1/docs/OpenProjects.html (under "Miscellaneous Improvements") It would be exactly the thing that i need. Bes...

...g about cases like it, such as: https://godbolt.org/z/Fwq8mn I wonder what we can do about this in a general sense. As far as I can tell, the jump threading algorithm is *really* conservative, which is one reason this isn't working as well as I'd hope; however, we don't want to produce irreducible control flow that the other passes would work less effectively on. Thoughts? - Karl -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200130/579f396d/attachment.html>

Thank you, Nick. Yes, I have add getAnalysisUsage. As I know, some CFG is irreducible. At this time, Dominator Tree can not find some backedge. Is it means some MachineLoop is not be found? dominatorTree.jpg is a previous exmaple. best regards! renkun --- 10年3月9日，周二, Nick Lewycky <nicholas at mxc.ca> 写道： > 发件人: Nick Lewycky <nicholas at mxc.ca> > 主题: Re: [L...

...troducing “false” dependencies if necessary to > allow optimizations to be applied without changing the semantics. > Implement some structure of to the side that represents this high- > level flow. > > Thoughts? One downside of this is that it means eliminating all instances of irreducible control flow, which can lead to an exponential increase in code size. --Owen -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080811/4ccf9104/attachment.html>

We would like to develop a code generator using LLVM for a target language that does not support conditional branches and in fact only supports structured control flow, eg. If and while. As far as I can tell that the problem with doing this in LLVM today, is that it does not support these high-level constructs and instead all control flow is implemented as branches. It is ³fairly²

Hi, Dear Boissinot: 1. When I have irreducible CFG, I travel its nodes by DFS. search backedge for every node. After I finish one node, push it into a stack. [0, 1, 2, M] <---push. [0, 1, 2, M,...N] <---push. When resolving node M, find a edge from node N to node M, N is not in stack(M < N), It is a backedg...

Hi, Is there any pass in LLVM 2.6/2.7/2.8 that makes an irreducible flow graph reducible? Best Regards, Raj -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101101/d786d451/attachment.html>

Seung, On 8/25/07, Chris Lattner <sabre at nondot.org> wrote: > Ok. Note that LLVM can represent irreducible loops. You can handle > this through code duplication. > -Chris If you are willing to invest more effort into a more complicated analysis, in many cases you can even avoid code duplication. See this paper for details: @inproceedings{erosa94taming, author = {Ana M. Erosa and...

...aphs to decide if DS node > represented multiple objects or a single object. It's the basic query > to decide if a function is part of a recursive computation (a cycle in > the call graph). CFGs happen to have special code for natural loops > but you could use this query to handle irreducible loops as well. These typically don't use the scciterator though. -Chris

I am trying to implement node splitting to transform irreducible CFGS to reducible ones. This means making copies of some basic blocks, which in turn means making copies of individual instructions. I can use the "clone" function to make an exact copy, but then I need to change some operands. For example, when I copy %1 = ... %2 = add %1, 5 I...

...rg/z/Fwq8mn > > > > I wonder what we can do about this in a general sense. As far as I can > > tell, the jump threading algorithm is *really* conservative, which is one > > reason this isn't working as well as I'd hope; however, we don't want to > > produce irreducible control flow that the other passes would work less > > effectively on. Thoughts? > > I'm confused. In your godbold link you run it with O0 which disables > almost all transformations. If we take the IR, remove the optnone > attribute, run mem2reg and jump-threading we get what...

Hi Mon Ping, Discussing this with others in AMD it came up if it is possible for LLVM to take a program that has a reducible graph (any C code without goto/setjmp) and generate one that is irreducible? If it is the case that the code is actually structured coming in, a simple pattern matcher could turn everything into if/endif and so on. Ben On 14/08/2008 18:39, "Mon P Wang" <wangmp at apple.com> wrote: > Hi Ben, > > > On Aug 12, 2008, at 11:36 AM, Benedict Gaste...

...³false² dependencies if necessary to allow > optimizations to be applied without changing the semantics. > 3. Implement some structure of to the side that represents this high-level > flow. > 4. > > Thoughts? One downside of this is that it means eliminating all instances of irreducible control flow, which can lead to an exponential increase in code size. [bg] Actually this does not need to be the case. The paper that I sighted does not use code replication to resolve irreducible control flow but instead introduces a loop construct. For example, consider the following irreducible...