search for: irreducibility

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 -inline -tailduplicate" makes an irreducible CFG from this code @x = weak global float 0.0 define internal fast...

On Thu, Jul 24, 2008 at 2:00 PM, Mark Leone <markleone 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 eve...

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 >

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

...foo.exit, %then.i br label %foo.exit4 foo.exit4: ; preds = %continue.i3 ret void } On Thu, Jul 24, 2008 at 3:38 PM, Eli Friedman <eli.friedman at gmail.com> wrote: > On Thu, Jul 24, 2008 at 2:00 PM, Mark Leone <markleone 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 &gt...

Hi everyone, I'm currently trying to run a study on irreducibility of C programs, and I've implemented structural analysis (original paper by Sharir, algorithm in Muchnick's book) as an LLVM pass. When my implementation becomes a bit less buggy I'll certainly look into including it in the LLVM project. As a test for the algorithm I've been produc...

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. Best

Since the bug report here: https://bugs.llvm.org/show_bug.cgi?id=44679 I've been thinking 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

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: [LLVMdev] Find

On Aug 11, 2008, at 2:02 PM, Benedict Gaster wrote: > 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. What's the difference between an "if" and a conditional branch? > As far as I can tell that the problem with doing this in

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 backedge. N is in stack(M > N), It is NOT a backedge.

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.

On Aug 7, 2009, at 12:51 PM, Vikram S. Adve wrote: > Checking if a graph node is in a cycle or not must be a relatively > common query. E.g., we used this on DS graphs 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

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 get %3 = ... %4 = add %1, 5

Holy crap, I completely missed that. I'm sorry! That's my fault. On Sun, Feb 2, 2020 at 12:15 PM Johannes Doerfert <jdoerfert at anl.gov> wrote: > On 01/30, Karl Rehm via llvm-dev wrote: > > Since the bug report here: https://bugs.llvm.org/show_bug.cgi?id=44679 > I've > > been thinking about cases like it, such as: https://godbolt.org/z/Fwq8mn > > >

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"

Hi, Comments inline. Ben On 12/08/2008 03:14, "Owen Anderson" <resistor at mac.com> wrote: >> 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. What's the difference between an "if" and a conditional