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 in the GNU coreutils package. When generating bitcode, I find that sometimes the CFG produced can have basic blocks that have no successors or predecessors; using "-view-cfg-only" they just float 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, James -- View this message in context: http://www.nabble.com/Irreducibility-and-the--simplifycfg-flag-tp24270165p24270165.html Sent from the LLVM - Dev mailing list archive at Nabble.com.
On Tue, Jun 30, 2009 at 4:22 AM, James Stanier<j.stanier at sussex.ac.uk> wrote:> My question is this: would the simplify pass ever make a reducible CFG > become irreducible?If it does, it's a bug; transforming a reducible CFG into an irreducible CFG significantly pessimizes the loop analysis passes. That said, I'm pretty sure it can in some unusual cases. If you care, a patch to split out the RemoveUnreachableBlocksFromFn helper from SimplifyCFGPass into a helper available from llvm/Transforms/Utils/Local.h would be welcome, I think. That said, it's pretty easy to dodge the issue in your pass by iterating over the tree of BBs with df_begin/df_end rather than the list of BBs for the function; see llvm/ADT/DepthFirstIterator.h. -Eli
Hi,>... > As a test for the algorithm I've been producing LLVM bitcode for C files in > the GNU coreutils package. When generating bitcode, I find that sometimes > the CFG produced can have basic blocks that have no successors or > predecessors; using "-view-cfg-only" they just float 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?you can always write your own mini-pass that just dumps unreachable basic blocks. Ciao, Duncan.