llvm / llvm/llvm-project

[missed-optimization] `a != b` implies that a or b is also non-zero

Open
#199,532 0 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

From this [GCC bug](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=117760),
[Clang trunk Godbolt](https://godbolt.org/z/xKhK67r1x) does not optimized like this [gcc/match.pd patch](https://gcc.gnu.org/cgit/gcc/commit/?id=c65691bc5a2873e0e2ffbfcaa80eb9bdc6e1f7b8) with -O3

C code
```
/* Given two integers a and b:
(a != b) & ((a|b) != 0) -> (a != b)
(a == b) | ((a|b) == 0) -> (a == b)

(a == b) & ((a|b) == 0) -> ((a|b) == 0)
(a != b) | ((a|b) != 0) -> ((a|b) != 0)

(a != b) & ((a|b) == 0) -> false
(a == b) | ((a|b) != 0) -> true */

_Bool src (unsigned long a, unsigned long b, unsigned long c)
{
switch (c) {
case 0:
return (a != b) & ((a|b) != 0);
case 1:
return (a == b) | ((a|b) == 0);
case 2:
return (a == b) & ((a|b) == 0);
case 3:
return (a != b) | ((a|b) != 0);
case 4:
return (a != b) & ((a|b) == 0);
default:
return (a == b) | ((a|b) != 0);
}
}

_Bool tgt (unsigned long a, unsigned long b, unsigned long c)
{
_Bool or_ab = a|b;
switch (c) {
case 0:
return a != b;
case 1:
return a == b;
case 2:
return (or_ab) == 0;
case 3:
return (or_ab);
case 4:
return false;
default:
return true;
}
}
```

LLVM IR:
```
define dso_local noundef zeroext i1 @src(i64 noundef %a, i64 noundef %b, i64 noundef %c) local_unnamed_addr {
entry:
%or37 = or i64 %b, %a
switch i64 %c, label %sw.default [
i64 0, label %sw.bb
i64 1, label %sw.bb3
i64 2, label %sw.bb11
i64 3, label %sw.bb19
i64 4, label %sw.bb27
]

sw.bb:
%cmp = icmp ne i64 %a, %b
%cmp1 = icmp ne i64 %or37, 0
%and68 = and i1 %cmp, %cmp1
br label %return

sw.bb3:
%cmp4 = icmp eq i64 %a, %b
%cmp7 = icmp eq i64 %or37, 0
%or967 = or i1 %cmp4, %cmp7
br label %return

sw.bb11:
%cmp12 = icmp eq i64 %a, %b
%cmp15 = icmp eq i64 %or37, 0
%and1766 = and i1 %cmp12, %cmp15
br label %return

sw.bb19:
%cmp20 = icmp ne i64 %a, %b
%cmp23 = icmp ne i64 %or37, 0
%or2565 = or i1 %cmp20, %cmp23
br label %return

sw.bb27:
%cmp28 = icmp ne i64 %a, %b
%cmp31 = icmp eq i64 %or37, 0
%and3364 = and i1 %cmp28, %cmp31
br label %return

sw.default:
%cmp35 = icmp eq i64 %a, %b
%cmp38 = icmp ne i64 %or37, 0
%or4069 = or i1 %cmp35, %cmp38
br label %return

return:
%retval.0 = phi i1 [ %or4069, %sw.default ], [ %and68, %sw.bb ], [ %or967, %sw.bb3 ], [ %and1766, %sw.bb11 ], [ %or2565, %sw.bb19 ], [ %and3364, %sw.bb27 ]
ret i1 %retval.0
}

define dso_local noundef zeroext i1 @tgt(i64 noundef %a, i64 noundef %b, i64 noundef %c) local_unnamed_addr {
entry:
%or = or i64 %b, %a
%tobool = icmp ne i64 %or, 0
switch i64 %c, label %sw.default [
i64 0, label %sw.bb
i64 1, label %sw.bb1
i64 2, label %sw.bb3
i64 3, label %cleanup
i64 4, label %sw.bb8
]

sw.bb:
%cmp = icmp ne i64 %a, %b
br label %cleanup

sw.bb1:
%cmp2 = icmp eq i64 %a, %b
br label %cleanup

sw.bb3:
%cmp4 = xor i1 %tobool, true
br label %cleanup

sw.bb8:
br label %cleanup

sw.default:
br label %cleanup

cleanup:
%retval.0 = phi i1 [ true, %sw.default ], [ %cmp, %sw.bb ], [ %cmp2, %sw.bb1 ], [ %cmp4, %sw.bb3 ], [ false, %sw.bb8 ], [ %tobool, %entry ]
ret i1 %retval.0
}
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.