Multiple successors, single dynamic successor

Suppose I have a bb with N predecessors and N successors. What is, in your opinion, the best way to express that the bb has (dynamically) only one successor (i.e. if coming from the i-th predecessor we will always jump to the i-th successor)?
b.r.,

I'm assuming that you're talking about a situation where this can't be
determined statically in the existing LLVM IR, but you know it's true
and want to put it in (e.g. you're the one generating LLVM IR). If
that's not the case, then see if JumpThreading will do it for you.

I'm not familiar with a way to express exactly what you want to say,
but are you opposed to just duplicating the block? That is, you could
duplicate the block, and have the ith predecessor go to the duplicate
which goes to the ith successor. You can use JumpThreading::ThreadEdge
in lib/Transforms/Scalar/JumpThreading.cpp as a guide.

Nella citazione martedì 2 agosto 2011 20:02:08, Michael Ilseman ha scritto:

I'm assuming that you're talking about a situation where this can't be
determined statically in the existing LLVM IR, but you know it's true
and want to put it in (e.g. you're the one generating LLVM IR).

Correct. Or, more precisely, I'd like to investigate macro compression, i.e. finding duplicate sequences of instructions and merging them together.
Suppose you have two fragments in the cfg like this: a -> b -> c and d -> e -> f. Suppose that basic blocks b and e are identical: macro compression would discard e and have the second fragment transformed like this: d -> b -> f.
b has now two predecessor (a and d) and two successors (c and f), but we know that when control comes from a we will always have to jump to c and when coming from d we will always jump to f (basically we could say that macro compression is the inverse of jump threading). My question is: what is the best way to
express such relationships in LLVM IR ("best" in the sense of allowing other optimizations to run effectively)? Bear in mind that in this example N=2, but it may be way bigger than that.

Nella citazione martedì 2 agosto 2011 22:01:13, Carlo Alberto Ferraris ha scritto:

My question is: what is the best way to
express such relationships in LLVM IR ("best" in the sense of allowing other optimizations to run effectively)? Bear in mind that in this example N=2, but it may be way bigger than that.

Just to clarify: I already figured out two ways to do it, i.e.:

%0 = phi i8* [blockaddr(%succ0), %pred0], [blockaddr(%succ1), %pred1], ...
...
indirectbr %0, [%succ0, %succ1, ...]

or

%0 = phi i8 [0, %pred0], [1, %pred1], ...
...
switch %0, undef, [0, %succ0], [1, %succ1], ...

what I'd like to know is which one do you think is better (and why) or if there are better ways I didn't think of.

I see, you want to combine identical sequences of instructions by
making a BasicBlock for them, while preserving the semantics of the
original program, correct? Could you just add a PHINode to the top of
the new BB denoting what path it took to get there, and have the new
BB's terminator be a switch on that PHI? That's the only way I know of
for representing that sort of thing, but someone else here might know
more. If you choose to implement it that way,
include/llvm/Transforms/Utils/BasicBlockUtils.h would be helpful to
you, particularly the SplitBlock function.

I think we sent our emails at the exact same time. I've never used
indirectbr, but my guess would be that the best solution doesn't
involve taking the address of a block (i.e.
BasicBlock::hasAddressTaken() returns false). Some LoopUnrolling and
BasicBlockUtils/Local utility functions don't do anything if a BB's
address has been taken, but it may not matter if SimplifyCFG
simplifies these away (it does turn indirectbr in br when it can,
don't know about switch).

Hopefully someone more knowledgeable can give you a better idea, but I
think that switch is preferable or otherwise equivalent to indirectbr.
This may not be the case if you happen to tell LLVM to run the
LowerSwitch pass (which may undo your work), but I don't think
anything runs that by default. When the IR reaches the SelectionDAG,
the SelectionDAG is capable of converting switches to jump tables (I
don't know about indirectbr).