similar to: [LLVMdev] Irreducible CFG from tail duplication

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

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

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

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

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

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

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>

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

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

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.

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

Newbie question here: what's the best way to truncate a float to a signed int? The fptosi instruction rounds, and the fptrunc instruction simply truncates from a large float type to a smaller float type. Mark

Eli Friedman <eli.friedman at gmail.com> writes: >> Ah. So is the MachineFunction version expected to work correctly? > > It's part of the default set of CodeGen passes. It is? Was that true in 3.1? I can't see where it is initialized in llc. I probably missed something important. :) Thanks! -David

I'm reading up on LLVM's implementation of tail duplication and the description is confusing: http://llvm.org/docs/Passes.html -tailduplicate: Tail Duplication This pass performs a limited form of tail duplication, intended to simplify CFGs by removing some unconditional branches. This pass is necessary to straighten out loops created by the C front-end, but also is capable of

http://llvm.org/viewvc/llvm-project/llvm/tags/RELEASE_31/final/lib/CodeGen/Passes.cpp?revision=156747&view=markup void TargetPassConfig::addMachineSSAOptimization() { // Pre-ra tail duplication. if (addPass(EarlyTailDuplicateID) != &NoPassID) printAndVerify("After Pre-RegAlloc TailDuplicate"); /// Add passes that optimize machine instructions after register allocation.