Carlo Alberto Ferraris
2011-Aug-02 20:01 UTC
[LLVMdev] Multiple successors, single dynamic successor
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. -- Carlo Alberto Ferraris <cafxx at strayorange.com <mailto:cafxx at strayorange.com>> website/blog <http://cafxx.strayorange.com> - +39 333 7643 235 -------------- next part -------------- A non-text attachment was scrubbed... Name: cafxx.vcf Type: text/x-vcard Size: 233 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110802/ce4698f5/attachment.vcf>
Carlo Alberto Ferraris
2011-Aug-02 20:16 UTC
[LLVMdev] Multiple successors, single dynamic successor
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. -- Carlo Alberto Ferraris <cafxx at strayorange.com <mailto:cafxx at strayorange.com>> website/blog <http://cafxx.strayorange.com> - +39 333 7643 235 -------------- next part -------------- A non-text attachment was scrubbed... Name: cafxx.vcf Type: text/x-vcard Size: 233 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110802/bf1eb783/attachment.vcf>
Michael Ilseman
2011-Aug-02 20:17 UTC
[LLVMdev] Multiple successors, single dynamic successor
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. On Tue, Aug 2, 2011 at 2:01 PM, Carlo Alberto Ferraris <cafxx at strayorange.com> wrote:> > > 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. > > -- > Carlo Alberto Ferraris <cafxx at strayorange.com > <mailto:cafxx at strayorange.com>> > website/blog <http://cafxx.strayorange.com> - +39 333 7643 235 > >
Michael Ilseman
2011-Aug-02 20:46 UTC
[LLVMdev] Multiple successors, single dynamic successor
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). On Tue, Aug 2, 2011 at 2:16 PM, Carlo Alberto Ferraris <cafxx at strayorange.com> wrote:> 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. > > -- > Carlo Alberto Ferraris <cafxx at strayorange.com > <mailto:cafxx at strayorange.com>> > website/blog <http://cafxx.strayorange.com> - +39 333 7643 235 > >
Apparently Analagous Threads
- [LLVMdev] Multiple successors, single dynamic successor
- [LLVMdev] RFC: Exception Handling Proposal II
- [LLVMdev] RFC: Exception Handling Proposal II
- [LLVMdev] Missed optimization with indirectbr terminator
- [LLVMdev] Multiple successors, single dynamic successor