[LLVMdev] Motivation for 'select' instruction

[Chris Lattner]

On Thu, 22 Apr 2004, Vladimir Prus wrote:

>
> I'm wondering what was the original motivaton for the 'select'
> instruction.  Was it for convenience, or for some deep reason. I'm
> asking because it's causing me some problems (see below) and I'd like to
> know I understand the situation before working those problems around.

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.  If
this is the case, we like to use the select when possible.  Once the
control flow is turned into data flow, the optimizers are also able to do
good things eliminating it.

> I have the following function:
>
>     int logsch(int ih,int nbh)
>     {
>          if(nbh < 0) { nbh = 0; ih = 10; }
>          if(nbh > 22528) { nbh = 22528; ih = 7; }
>          return(nbh + ih);
>     }
>
> >From the C language standpoint, there are 4 paths though this function: each
> "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?
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.  :)

Note that if you put more code (such as a function call) into the body of
the if statements that the selects will go away.  I don't know if this is
an option for you.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/