llvm / llvm/llvm-project

Recongnize `strcmp == 0` and `memcmp == 0` as commutative

Open
#211,058 2 comments 0 reactions 1 assignee Claimed by @iamaayushrivastava View on GitHub
llvm:transforms missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

`strcmp(x, y) == 0`, `memcmp(x, y, n) == 0`, and `strncmp(x, y, n) == 0` are commutative (`strcmp(x, y) == 0` is equivalent to calling `strcmp(y, x) == 0` and etc). There are two ways to benefit from this:
1. Calling `strcmp(y, x) == 0` if it is cheaper than `strcmp(x, y) == 0`
2. Re-using the result from `strcmp(x, y) == 0` for `strcmp(y, x) == 0`

https://godbolt.org/z/c9hb31fGq

***

For the first case, there is slightly more overhead from calling `strcmp(y, x)` than `strcmp(x, y)` (since `x` and `y` need to be swapped before calling `strcmp(y, x)` on x86-64).
```c
bool test1(const char* x, const char* y) {
return (strcmp(x, y) == 0);
}

bool test2(const char* x, const char* y) {
return (strcmp(y, x) == 0);
}
```

***

For the second case, Clang/LLVM will emit 2 calls/comparisons:
```c
bool test3(const char* x, const char* y) {
// strcmp is emitted twice in this function
return (strcmp(x, y) == 0) && (strcmp(y, x) == 0);
}
```

It will only reduce to a single comparison when calling `memcmp` or `strncmp` with 1 byte:
```c
bool memcmp3_1(const char* x, const char* y) {
// only one cmp is emitted in LLVM IR
return (memcmp(x, y, 1) == 0) && (memcmp(y, x, 1) == 0);
}
```

LLVM can already eliminate repeated calls to `strcmp(x, y)` when its existing memory-dependence analysis proves that the compared data has not changed. The result of `strcmp(x, y) == 0` should likewise be reusable for `strcmp(y, x) == 0` under the same conditions.

***

This could also be extended to assuming that `strcmp(x, y) < 0` is equivalent to `strcmp(y, x) > 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.