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