[LLVMdev] Motivation for 'select' instruction

[Vladimir Prus]

Chris Lattner wrote:

> The select instruction is basically an SSA-form "conditional move", or a
> very simple form of predication.  Integer codes often have very complex
> CFG's which are usually doing simple things.  For example, it's not
> uncommon to see something like this:
>
> if (blah)
>   X = 14;
>
> If the body of the if statement is simple enough, it's usually cheaper to
> unconditionally execute the body than it is to execute the branch.  

Yes, I understand that. Though I though such optimization is usually done 
somewhere in backend, that's why I was surprised that it's commonly used in 
LLVM.

> > "if" can be either take or not. In reality, both "if" can't be taked at
> > the same time -- and that's why I'm trying to automatically figure out
> > working on LLVM representation. However, the LLVM code:
> >
> >     int %logsch(int %ih, int %nbh) {
> >     entry:
> >              %tmp.1 = setlt int %nbh, 0
> >              %ih_addr.1 = select bool %tmp.1, int 10, int %ih
> >              %nbh_addr.1 = select bool %tmp.1, int 0, int %nbh
> >              %tmp.4 = setgt int %nbh_addr.1, 22528
> >              %ih_addr.0 = select bool %tmp.4, int 7, int %ih_addr.1
> >              %nbh_addr.0 = select bool %tmp.4, int 22528, int %nbh_addr.1
> >              %tmp.8 = add int %nbh_addr.0, %ih_addr.0
> >              ret int %tmp.8
> >     }
> >
> > Has 'select' instructions and a single path, which makes my task harder.
>
> What are you trying to do?  It looks like there is some correlation in the
> branches that could be optimized away, is that what you're going after?

No, not exactly. I need to find the path with the maximum execution time (in 
assembler for specific processor). Do to so, I must also find paths which 
cannot be executed no matter what input is (like one of the paths in the C 
example). I'm trying to do that using LLVM intermediate representation.

> In the very worst case, you can always use the SelectLowering pass to turn
> the select instructions into branches, but it would be preferable to find
> another way if possible.  :)

In fact, I think this might be enough for me, since for now I'm only going to 
evaluate the algorithms for detecting infeasible paths.

Thanks,
Volodya