similar to: [LLVMdev] Making Flow graphs reducible

Hi Raj, > Is there any pass in LLVM 2.6/2.7/2.8 that makes an irreducible flow graph > reducible? can you please give an example of what you have in mind. Ciao, Duncan.

Duncan Sands wrote: > > Is there any pass in LLVM 2.6/2.7/2.8 that makes an irreducible flow > graph > reducible? > Do you mean something like this? http://portal.acm.org/citation.cfm?id=977393 -- View this message in context: http://old.nabble.com/Making-Flow-graphs-reducible-tp30110882p30134979.html Sent from the LLVM - Dev mailing list archive at Nabble.com.

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 >

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

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

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

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

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 producing LLVM bitcode for C files

Thanks Eli. It's not introducing loops, just unstructured conditionals (e.g. X's in the control-flow graph, rather than diamonds). You can see it using "opt -view-cfg" 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

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

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

Hi, I like Eli approach here. Phases like SimplifyCFG and various loop transformations are just to useful to cleanup code and generate much high quality output. If we look at the passes, I hope we might be able to quantify what changes they make. My hope is that since the incoming graph is reducible that it doesn't cost that much after running these phases to make them reducible

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"

On Thu, Aug 14, 2008 at 2:55 PM, Benedict Gaster <benedict.gaster at amd.com> wrote: > 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

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

Hi Ben, On Aug 12, 2008, at 11:36 AM, Benedict Gaster wrote: > Hi Owen, > > On 12/08/2008 16:52, "Owen Anderson" <resistor at mac.com> wrote: > >> >> SNIP >> >> >> I'm still not seeing how these two are any different. You just >> replace the text of "if" with "br", and add the explicit target >>

Hi all, This is a request for comment on a series of patches which introduce a new way of writing algorithms that are generic over different types of CFG. What is this? ============= This series of patches introduces a set of classes and templates for: 1. Working on basic blocks and values generically, in particular with the same algorithm implementation on both LLVM IR and MachineIR (in SSA

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

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.

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.