Page MenuHomePhabricator

[InstCombine] Optimize strchr(cststr, C)
Needs ReviewPublic

Authored by xbolva00 on Jan 19 2020, 6:54 AM.

Details

Summary

Motivation: https://godbolt.org/z/yAkD8B - Both functions should produce same codegen.

Solution: Build chain of OR comparisons and rely on InstSimplify/InstCombine to clean up the chain.

memchr("abcd", C, 4) != NULL -> (C == 'a' | C == 'b' | C == 'c' | C == 'd') != 0

Event Timeline

xbolva00 created this revision.Jan 19 2020, 6:54 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 19 2020, 6:54 AM
Harbormaster completed remote builds in B44358: Diff 238987.
xbolva00 edited the summary of this revision. (Show Details)Jan 19 2020, 7:01 AM
joerg added inline comments.Jan 20 2020, 10:49 AM
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
935

We are planning on doing exactly that, so the above comment needs adjustment?

948

The switch table logic is fine with lowering it to a multiple tests, isn't it?

xbolva00 marked 2 inline comments as done.Jan 20 2020, 11:15 AM
xbolva00 added a subscriber: hans.
xbolva00 added inline comments.
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
935

True.

948

Hmm.. building switch directly is for some cases* better choice** than ORs, but I am wondering if this is best solution here - Maybe @hans could give us some recommendations here?

Ideas?

hans added inline comments.Jan 21 2020, 9:47 AM
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
948

I think we (SimplifyCFG) does turn a chain of ORs into a switch, but only logical or, not bitwise. Maybe emitting a chain of logical or would be good here?

jdoerfert added inline comments.Jan 21 2020, 12:21 PM
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
932

Unrelated: Even if it is not only checked against null we can do this and add a nonnull result to the string pointer, right?

948

We should add a test with instcombing and simplifyCFG to make sure this works.

Nitpick: regardless of any further potential folds, is this particular fold always a win?
Is there some potential pattern where this will not/can not get as nicely folded as it does in the newly added tests?

Nitpick: regardless of any further potential folds, is this particular fold always a win?
Is there some potential pattern where this will not/can not get as nicely folded as it does in the newly added tests?

Maybe if the string is made up of far apart chars: "ahpzDKOTZ"
Though if we can verify it becomes a switch it might still be better.