llvm dev - Mar 2018 - [RFC] jump threading on std::pair<int, bool>

Hi,

While comparing the code by LLVM and GCC for some major libraries, I found
that LLVM fails to apply jump threading with a method whose return type is
std::pair<int, bool> (actually, any pair of 32-bit values like
std::pair<bool, int> and std::pair<int, int>).
For example, jump threading does not work for the if statement in func.

std::pair<int, bool> callee(int v) {
  int a = dummy(v);
  if (a) return std::make_pair(dummy(v), true);
  else return std::make_pair(v, v < 0);
}

int func(int v) {
  std::pair<int, bool> rc = callee(v);
  if (rc.second) {
    // do something
  }
  ...

SROA executed before the method inlining replaces std::pair by i64 without
splitting in both `callee` and `func` since at this point no access to the
individual fields is seen to SROA.
After inlining, jump threading fails to identify that the incoming value is
a constant due to additional instructions (like or, and, trunc).

I would appreciate it if I could have any suggestions on how we can
optimization such cases.
I am planning to enhance InstCombine pass to eliminate these additional
instructions before jump threading rather than enhancing SROA or jump
threading.


Here is LLVM IR generated for above C code.

define signext i32 @_Z4funci(i32 signext %v) local_unnamed_addr #0 {
entry:
  %call.i = tail call signext i32 @_Z5dummyi(i32 signext %v)
  %tobool.i = icmp eq i32 %call.i, 0
  br i1 %tobool.i, label %if.else.i, label %if.then.i

if.then.i:                                        ; preds = %entry
  %call1.i = tail call signext i32 @_Z5dummyi(i32 signext %v)
  %retval.sroa.0.0.insert.ext.i.i = zext i32 %call1.i to i64
  br label %_ZL6calleei.exit

if.else.i:                                        ; preds = %entry
  %.lobit.i = lshr i32 %v, 31
  %0 = zext i32 %.lobit.i to i64
  %retval.sroa.2.0.insert.shift.i8.i = shl nuw nsw i64 %0, 32
  %retval.sroa.0.0.insert.ext.i9.i = zext i32 %v to i64
  br label %_ZL6calleei.exit

_ZL6calleei.exit:                                 ; preds = %if.then.i,
%if.else.i
  %.sink = phi i64 [ 4294967296, %if.then.i ],
[ %retval.sroa.0.0.insert.ext.i9.i, %if.else.i ]
  %retval.sroa.0.0.insert.ext.i.i.sink = phi i64
[ %retval.sroa.0.0.insert.ext.i.i, %if.then.i ],
[ %retval.sroa.2.0.insert.shift.i8.i, %if.else.i ]
  %retval.sroa.0.0.insert.insert.i.i = or i64
%retval.sroa.0.0.insert.ext.i.i.sink, %.sink
  %rc.sroa.0.0.extract.trunc = trunc i64 %retval.sroa.0.0.insert.insert.i.i
to i32
  %1 = and i64 %retval.sroa.0.0.insert.insert.i.i, 4294967296
  %tobool = icmp eq i64 %1, 0
  br i1 %tobool, label %if.end, label %if.then ; <<- not jump threaded


-----
Hiroshi Inoue <inouehrs at jp.ibm.com>
IBM Research - Tokyo
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180308/57ba6464/attachment.html>

On 3/8/2018 6:29 AM, Hiroshi 7 Inoue via llvm-dev wrote:
>
> Hi,
>
> While comparing the code by LLVM and GCC for some major libraries, I 
> found that LLVM fails to apply jump threading with a method whose 
> return type is std::pair<int, bool> (actually, any pair of 32-bit 
> values like std::pair<bool, int> and std::pair<int, int>).
> For example, jump threading does not work for the if statement in func.
>
> std::pair<int, bool> callee(int v) {
> int a = dummy(v);
> if (a) return std::make_pair(dummy(v), true);
> else return std::make_pair(v, v < 0);
> }
>
> int func(int v) {
> std::pair<int, bool> rc = callee(v);
> if (rc.second) {
> // do something
> }
> ...
>
> SROA executed before the method inlining replaces std::pair by i64 
> without splitting in both `callee` and `func` since at this point no 
> access to the individual fields is seen to SROA.
> After inlining, jump threading fails to identify that the incoming 
> value is a constant due to additional instructions (like or, and, trunc).
>
> I would appreciate it if I could have any suggestions on how we can 
> optimization such cases.
> I am planning to enhance InstCombine pass to eliminate these 
> additional instructions before jump threading rather than enhancing 
> SROA or jump threading.
>
InstCombiner::SliceUpIllegalIntegerPHI already sort of does what you 
want... but it's currently disabled for legal integer types. Not sure 
what the performance implications would be if we run that more aggressively.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180308/3ed74064/attachment.html>