Missed optimization: Imperfect optimization of straightforward std::find

[Alcaro]

static bool any_of_impl(int* first, int* last, int num)
{
    for (; first != last; ++first) {
        if (*first == num)
            return true;
    }
    return false;
}
bool square(int num) {
    int x[] = {1,2,3};
    return any_of_impl(x, x+3, num);
}

bool cube(int num) {
    return num==1 || num==2 || num==3;
}

-O2 or -O3

Expected: Same asm for both

Actual:

square(int):
        cmp     edi, 1
        sete    cl
        add     edi, -2
        test    edi, -2
        sete    al
        or      al, cl
        ret

cube(int):
        dec     edi
        cmp     edi, 3
        setb    al
        ret

The expected result shows up on pretty much any simplification of the input, including moving the +3 to the callee, or changing both functions' return type to int. Feels like some optimizer passes are running in wrong order and confusing each other.

https://godbolt.org/z/88938fP3d

Originally found via a std::ranges::any_of call, hence the function name. It turned into std::find when I reduced it. https://godbolt.org/z/GjsE3vEK4

[dtcxzyw]

Should be fixed in trunk: https://godbolt.org/z/o5Mzzadcj

[dtcxzyw]

Originally found via a std::ranges::any_of call, hence the function name. It turned into std::find when I reduced it.

Oops, codegen for this case is still suboptimal: https://godbolt.org/z/5nh1fWvva

[dtcxzyw]

This seems to be a phase-ordering problem. We need another InstCombine run to cleanup after late SimplifyCFG pass converts the icmp chain into a range check + select. Or just handle this case in SimplifyCFG.

[Alcaro]

Yep, as I said, it's fragile. Re-reducing it reveals that it reproduces in trunk only if the outer function returns int, not bool.

static bool any_of_impl(int* first, int* last, int num)
{
    for (; first != last; ++first) {
        if (*first == num)
            return true;
    }
    return false;
}
int square(int num) {
    int x[] = {1,2,3};
    return any_of_impl(x, x+3, num);
}

int cube(int num) {
    return num==1 || num==2 || num==3;
}

https://godbolt.org/z/hnzvhcb8r

Which is a pretty goofy code pattern. Feel free to wontfix it if you feel it's too rare to care about.

[dtcxzyw]

We need another InstCombine run to cleanup after late SimplifyCFG pass converts the icmp chain into a range check + select. Or just handle this case in SimplifyCFG.

Another solution is to avoid folding zext i1 into phi because it is likely to break logical and/or patterns. But the following fix is fragile:

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
index 6c2554ea73b7..3802e3aa3744 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
@@ -199,8 +199,9 @@ Instruction *InstCombinerImpl::commonCastTransforms(CastInst &CI) {
   if (auto *PN = dyn_cast<PHINode>(Src)) {
     // Don't do this if it would create a PHI node with an illegal type from a
     // legal type.
-    if (!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() ||
+    if ((!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() ||
         shouldChangeType(CI.getSrcTy(), CI.getType()))
+        && !(CI.getOpcode() == Instruction::ZExt && Src->getType()->isIntOrIntVectorTy(1)))
       if (Instruction *NV = foldOpIntoPhi(CI, PN))
         return NV;
   }

cc @nikic @goldsteinn Any thoughts?

[goldsteinn]

Might that we just need to improve logic for pulling casts through phi: https://godbolt.org/z/9MEW7Ke4z

We pull zext through the phi if its a common op, but we don't have the logic to truncate constants even if they fit.