[AggressiveInstCombine] Fold strcmp for short string literals

[kitaisreal]

Summary

Fold strcmp for short string literals
https://github.com/llvm/llvm-project/issues/58003
Depends D155053.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

576 ↗

(On Diff #538168)

This will return an incorrect result if the first character of Str1 and Str2 is the same, but Str1 has length greater than one.

581 ↗

(On Diff #538168)

This may perform an out of bounds access for zero-length strings.

612 ↗

(On Diff #538168)

This is the transform that implements what you're trying to do, but taking dereferenceability into account.

[efriedma]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

612 ↗

(On Diff #538168)

https://github.com/llvm/llvm-project/issues/58003 is requesting that we generate control flow for small strings. For example, transforming strcmp(c, "x") == 0 to c[0] == 'x' && c[1] == '\0'. This is distinct from transforming it to a memcmp. (Of course, the current version of this patch doesn't implement that.)

[kitaisreal]

Added propert implementation with branches.

[kitaisreal]

For such program.

#include <cstring>

bool testFunction1_1(const char* c)
{
    return strcmp(c, "0") == 0;
}

GCC emits:

	.type	_Z15testFunction1_1PKc, @function
_Z15testFunction1_1PKc:
.LFB27:
	.cfi_startproc
	endbr64
	movzbl	(%rdi), %eax
	subl	$48, %eax
	jne	.L2
	movzbl	1(%rdi), %eax
.L2:
	testl	%eax, %eax
	sete	%al
	ret
	.cfi_endproc
.LFE27:
	.size	_Z15testFunction1_1PKc, .-_Z15testFunction1_1PKc
	.p2align 4
	.globl	_Z15testFunction1_2PKc
	.type	_Z15testFunction1_2PKc, @function

After changes clang emits:

	.type	_Z15testFunction1_1PKc,@function
_Z15testFunction1_1PKc:                 # @_Z15testFunction1_1PKc
	.cfi_startproc
# %bb.0:                                # %entry
	movsbl	(%rdi), %eax
	addl	$-48, %eax
	je	.LBB0_1
# %bb.2:                                # %strcmp_fold_sub_join
	testl	%eax, %eax
	sete	%al
	retq
.LBB0_1:                                # %strcmp_fold_sub_is_zero
	movsbl	1(%rdi), %eax
	testl	%eax, %eax
	sete	%al
	retq
.Lfunc_end0:
	.size	_Z15testFunction1_1PKc, .Lfunc_end0-_Z15testFunction1_1PKc
	.cfi_endproc

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

612 ↗

(On Diff #538168)

I updated implementation for single character str2 constant. If current approach is valid I will implement it for two characters str2 constant as well.
I am not sure if current approach with changing control flow inside this optimization is valid and safe, because it seems that other SimplifyLibCalls optimizations does not change control flow.

[kitaisreal]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

576 ↗

(On Diff #538168)

Updated implementation.

581 ↗

(On Diff #538168)

Updated implementation.

[xbolva00]

efriedma:

(instcombine specifically won't work; for the sake of compile-time performance, we've forbidden instcombine from changing the cfg.)

Your patch changes it, indeed. (SLC is part of InstCombine).

[nikic]

Right, InstCombine is control-flow preserving transform. We don't really have a great place to put such a transform right now, so SimplifyCFG is probably your best bet.

[kitaisreal]

This comment was removed by kitaisreal.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

567 ↗

(On Diff #538379)

You need to guard this behind isOnlyUsedInComparisonWithZero(), as the exact return value of strcmp() is unspecified (only its relation to zero is).

[kitaisreal]

Thanks. I will try to implement it in SimplifyCFG.

[kitaisreal]

In D154725#4483022, @nikic wrote:

Right, InstCombine is control-flow preserving transform. We don't really have a great place to put such a transform right now, so SimplifyCFG is probably your best bet.

I checked SimplifyCFG and if I decide to put transform into this pass, it seems that implementation will look complex and unexpected. It will require to get TargetLibraryInfo in SimplifyCFGPass and pass it to simplifyCFG function in Local.h, but this function is called from a lot of places, and it will be unexpected if this function can optimize library calls.
There is PartiallyInlineLibCallsPass that currently optimizes sqrt function and changes CFG, but it is registered in CodeGenPassBuilder and applied during codegen, but I expect that our optimization need to be registered in PassBuilderPipelines and applied during common IR optimizations.
Can we move this PartiallyInlineLibCallsPass to common IR optimizations, so we can extend it ? Or maybe it is better to create separate pass ?

[efriedma]

Maybe AggressiveInstCombine? It currently doesn't contain any CFG modifications, I think, but I don't see any reason they can't be added.

[kitaisreal]

Moved transformation into AggressiveInstCombine

[xbolva00]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

908

more like expand?

[xbolva00]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

920

GCC I think “inlines “ strcmp up to some length, but not strictly 1, no?

Also it can inline (expand) strcmp calls if we know that src/dst are dereferenceable with known size.

[kitaisreal]

Rename fold into expand.

[kitaisreal]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

920

It expands strcmp if size is 1 or 2 https://godbolt.org/z/jhbToh5Kb.
I plan to add case for string with size 2 in separate patch, because control flow becomes more complicated and it will make patch harder to review.

[xbolva00]

It would be great to have reusable general algo with N as parameter.

Then it can be used also some memcmp calls…

[nikic]

Generally on board with the direction of doing this in AggressiveInstCombine.

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

884

Aren't these conditions already checked by the caller now?

920

// instead of ///.

928

We should also handle constant string on the LHS.

942

As mentioned on the previous review, I believe you need to require that the strcmp result is only used in a comparison with zero. The exact return value of strcmp is unspecified, and we should not optimize to a result that deviates from the used libc implementation.

949

Why the use of sign extension? The C standard says the comparison is performed on unsigned char, not signed char:

The sign of a nonzero value returned by the comparison functions memcmp, strcmp, and strncmp

is determined by the sign of the difference between the values of the first pair of characters (both
interpreted as unsigned char) that differ in the objects being compared.

992

Why is this relevant?

1003

Why is this relevant?

1008

This is only used by expandStrcmp(), I would sink it into there.

llvm/test/Transforms/AggressiveInstCombine/strcmp.ll

3

TODO (If you write an extra comment, put it below RUN, not above.)

52

Should also test:

• Comparison with empty string (not folded, because left to SLC).
• Comparison with two known strings (not folded, because left to SLC).
• Comparison with two-char string (not folded for now).
• Comparison with known string on the LHS rather than RHS.

[kitaisreal]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

949

I cast this char to int32 so I can later sub them as signed integers. This looks simillar to standard glibc implementation https://github.com/zerovm/glibc/blob/master/string/strcmp.c#L45C15-L45C15. If we take this standard implementation and look and the IR it will be similar to mine https://godbolt.org/z/Pd9xKcnE8.

992

I take it from SimplifyLibCalls.cpp. Not sure if this is safe to ignore it for our transformation.

// Then check for known library functions.
if (TLI->getLibFunc(*Callee, Func) && isLibFuncEmittable(M, TLI, Func)) {
  // We never change the calling convention.
  if (!ignoreCallingConv(Func) && !IsCallingConvC)
    return nullptr;
  if (Value *V = optimizeStringMemoryLibCall(CI, Builder))
    return V;

1003

I take it from InstCombineCalls.cpp. Not sure if this is safe to ignore it for our transformation.

// Skip optimizing notail and musttail calls so
// LibCallSimplifier::optimizeCall doesn't have to preserve those invariants.
// LibCallSimplifier::optimizeCall should try to preseve tail calls though.
if (CI->isMustTailCall() || CI->isNoTailCall())
  return nullptr;

[kitaisreal]

Updated implementation.

[nikic]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

949

You can do the subtraction as you do now, but the characters need to be zero-extended. Otherwise you will claim that '\x7f' is larger than '\x80', which is not correct according to strcmp semantics.

959

Rather than hardcoding B.getInt32Ty(), it is better to use the original type (CI->getType()). There are platforms where int is not 32-bit.

992

We're removing the call entirely, so calling convention doesn't matter.

1003

Same here. This doesn't matter as the call is removed entirely.

llvm/test/Transforms/AggressiveInstCombine/strcmp.ll

25

@expand_strcmp_eq_s1

47

@expand_strcmp_eq_s1_commuted

69

@expand_strcmp_ne_s1

And so on, to get at least a slightly meaningful test name, rather than just a counter.

108

It's okay to have just one test with the constant on the left-hand-side. No need to test LHS and RHS for all predicates.

[kitaisreal]

Updated implementation.

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

269 ↗

(On Diff #541567)

This should probably have a max iteration cnt?

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

907

should the sqrt patch be split into a preliminary NFC?

[nikic]

LGTM

[kitaisreal]

llvm/lib/Analysis/ValueTracking.cpp

269 ↗

(On Diff #541567)

I am not sure about the requested change. You suggest to add max_iteration_count argument to isOnlyUsedInZeroComparison function, and relace all_of I->users() iteration with loop, so we can limit iteration count ? Can you please provide more information about the requested change.

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

907

Do you propose to extract most of the changes from AggressiveInstCombine, that are not related to expandStrcmp in separate patch ?

[goldstein.w.n]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

907

Yeah, but this has already been approved, so no need to make it a blocker.

[kitaisreal]

I do not have commit access. Can you please land this one for me Maksim Kita <[e-mail]> ?

[nikic]

Done! Please follow https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access for requesting commit access.

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

907

Yeah, this would have been a bit nicer, to make it clear that this doesn't really change anything about the sqrt fold, just moves code around.

[asmok-g]

This is causing a mis-compilation. Repro:

#include <string.h>

#define TOKMAXLEN 10

typedef struct {
  char token[TOKMAXLEN + 1]; /* always NUL-terminated */
} datetkn;

constexpr datetkn TimezoneAbbrevTable[] = {{"z"}};

static const int TimezoneAbbrevTableSize =
    sizeof TimezoneAbbrevTable / sizeof TimezoneAbbrevTable[0];

int main() {
  const char* token = "";
  for (int i = 0; i < TimezoneAbbrevTableSize; ++i) {
    const datetkn& timezone_abbrev = TimezoneAbbrevTable[i];
    if (strcmp("z", token) <= 0) {
      return 10;
    }
    token = timezone_abbrev.token;
  }

  return 0;
}

cmd: clang -O2 ./prog.cc -o ./prog.o

[nikic]

I believe the problem is that if the constant string is on the LHS, we also need to invert the greater/smaller results. The current code would be correct for equality comparisons, but not for relational comparisons.

[xbolva00]

This is serious, please fix or revert from release branches.

[alexfh]

In D154725#4568911, @xbolva00 wrote:

This is serious, please fix or revert from release branches.

I'll prepare a revert in case @kitaisreal doesn't respond soon.

Here a slightly more convenient reproducer (dumped IR right before the AggressiveInstCombine pass): https://gcc.godbolt.org/z/bGn3EnWG6

[alexfh]

In D154725#4570358, @alexfh wrote:

In D154725#4568911, @xbolva00 wrote:

This is serious, please fix or revert from release branches.

I'll prepare a revert in case @kitaisreal doesn't respond soon.

Here a slightly more convenient reproducer (dumped IR right before the AggressiveInstCombine pass): https://gcc.godbolt.org/z/bGn3EnWG6

The commit can't be reverted cleanly, I'll have to also revert dependent commits: cbfcf90152de5392a36d0a0241eef25f5e159eef and 5dde755188e34c0ba5304365612904476c8adfda.

[alexfh]

In D154725#4570452, @alexfh wrote:

In D154725#4570358, @alexfh wrote:

In D154725#4568911, @xbolva00 wrote:

This is serious, please fix or revert from release branches.

I'll prepare a revert in case @kitaisreal doesn't respond soon.

Here a slightly more convenient reproducer (dumped IR right before the AggressiveInstCombine pass): https://gcc.godbolt.org/z/bGn3EnWG6

The commit can't be reverted cleanly, I'll have to also revert dependent commits: cbfcf90152de5392a36d0a0241eef25f5e159eef and 5dde755188e34c0ba5304365612904476c8adfda.

Prepared a revert of the three commits here: https://reviews.llvm.org/D157430. I'm running tests now and will land the revert once they finish, unless I hear any objections.

llvm/include/llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h

 //===- AggressiveInstCombine.h - AggressiveInstCombine pass -----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// AggressiveInstCombiner - Combine expression patterns to form expressions
-/// with fewer, simple instructions. This pass does not modify the CFG.
+/// with fewer, simple instructions.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_AGGRESSIVEINSTCOMBINE_AGGRESSIVEINSTCOMBINE_H
 #define LLVM_TRANSFORMS_AGGRESSIVEINSTCOMBINE_AGGRESSIVEINSTCOMBINE_H
 
 #include "llvm/IR/PassManager.h"
 

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

 
 #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
 #include "AggressiveInstCombineInternal.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/PatternMatch.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/BuildLibCalls.h"
 #include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "aggressive-instcombine"
 
static bool tryToFPToSat(Instruction &I, TargetTransformInfo &TTI) {
   IRBuilder<> Builder(&I);
   Function *Fn = Intrinsic::getDeclaration(I.getModule(), Intrinsic::fptosi_sat,
                                            {SatTy, FpTy});
   Value *Sat = Builder.CreateCall(Fn, In);
   I.replaceAllUsesWith(Builder.CreateSExt(Sat, IntTy));
   return true;
 }
 
-/// Try to replace a mathlib call to sqrt with the LLVM intrinsic. This avoids
-/// pessimistic codegen that has to account for setting errno and can enable
-/// vectorization.
-static bool foldSqrt(Instruction &I, TargetTransformInfo &TTI,
-                     TargetLibraryInfo &TLI) {
-  // Match a call to sqrt mathlib function.
-  auto *Call = dyn_cast<CallInst>(&I);
-  if (!Call)
-    return false;
-
-  Module *M = Call->getModule();
-  LibFunc Func;
-  if (!TLI.getLibFunc(*Call, Func) || !isLibFuncEmittable(M, &TLI, Func))
-    return false;
-
-  if (Func != LibFunc_sqrt && Func != LibFunc_sqrtf && Func != LibFunc_sqrtl)
-    return false;
-
-  // If (1) this is a sqrt libcall, (2) we can assume that NAN is not created
-  // (because NNAN or the operand arg must not be less than -0.0) and (2) we
-  // would not end up lowering to a libcall anyway (which could change the value
-  // of errno), then:
-  // (1) errno won't be set.
-  // (2) it is safe to convert this to an intrinsic call.
-  Type *Ty = Call->getType();
-  Value *Arg = Call->getArgOperand(0);
-  if (TTI.haveFastSqrt(Ty) &&
-      (Call->hasNoNaNs() ||
-       CannotBeOrderedLessThanZero(Arg, M->getDataLayout(), &TLI))) {
-    IRBuilder<> Builder(&I);
-    IRBuilderBase::FastMathFlagGuard Guard(Builder);
-    Builder.setFastMathFlags(Call->getFastMathFlags());
-
-    Function *Sqrt = Intrinsic::getDeclaration(M, Intrinsic::sqrt, Ty);
-    Value *NewSqrt = Builder.CreateCall(Sqrt, Arg, "sqrt");
-    I.replaceAllUsesWith(NewSqrt);
-
-    // Explicitly erase the old call because a call with side effects is not
-    // trivially dead.
-    I.eraseFromParent();
-    return true;
-  }
-
-  return false;
-}
-
 // Check if this array of constants represents a cttz table.
 // Iterate over the elements from \p Table by trying to find/match all
 // the numbers from 0 to \p InputBits that should represent cttz results.
 static bool isCTTZTable(const ConstantDataArray &Table, uint64_t Mul,
                         uint64_t Shift, uint64_t InputBits) {
   unsigned Length = Table.getNumElements();
   if (Length < InputBits || Length > InputBits * 2)
     return false;
for (; ConstOffset.getZExtValue() <= E; ConstOffset += Stride)
     if (Ca != ConstantFoldLoadFromConst(C, LoadTy, ConstOffset, DL))
       return false;
 
   I.replaceAllUsesWith(Ca);
 
   return true;
 }
 
+/// Try to replace a mathlib call to sqrt with the LLVM intrinsic. This avoids
+/// pessimistic codegen that has to account for setting errno and can enable
+/// vectorization.
+static bool foldSqrt(CallInst *Call, TargetTransformInfo &TTI,
+                     TargetLibraryInfo &TLI) {
+  Module *M = Call->getModule();
+
+  // If (1) this is a sqrt libcall, (2) we can assume that NAN is not created
+  // (because NNAN or the operand arg must not be less than -0.0) and (2) we
+  // would not end up lowering to a libcall anyway (which could change the value
+  // of errno), then:
+  // (1) errno won't be set.
+  // (2) it is safe to convert this to an intrinsic call.
+  Type *Ty = Call->getType();
+  Value *Arg = Call->getArgOperand(0);
+  if (TTI.haveFastSqrt(Ty) &&
+      (Call->hasNoNaNs() ||
+       CannotBeOrderedLessThanZero(Arg, M->getDataLayout(), &TLI))) {
+    IRBuilder<> Builder(Call);
+    IRBuilderBase::FastMathFlagGuard Guard(Builder);
+    Builder.setFastMathFlags(Call->getFastMathFlags());
+
+    Function *Sqrt = Intrinsic::getDeclaration(M, Intrinsic::sqrt, Ty);
+    Value *NewSqrt = Builder.CreateCall(Sqrt, Arg, "sqrt");
+    Call->replaceAllUsesWith(NewSqrt);
+
+    // Explicitly erase the old call because a call with side effects is not
+    // trivially dead.
+    Call->eraseFromParent();
+    return true;
+  }
+
+  return false;
+}
+
+/// Try to fold strcmp(P, "x") calls.
+static bool foldStcmp(CallInst *CI, IRBuilderBase &B, DominatorTree &DT,
+                      bool &MadeCFGChange) {
+  Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
+
+  /// Trivial cases are optimized during inst combine
+  if (Str1P == Str2P)
+    return false;
+
+  StringRef Str1, Str2;
+  bool HasStr1 = getConstantStringInfo(Str1P, Str1);
+  bool HasStr2 = getConstantStringInfo(Str2P, Str2);
+
+  bool Match = !HasStr1 && HasStr2 && Str2.size() == 1;
+  if (!Match)
+    return false;
+
+  // For strcmp(P, "x") do the following transformation:
+  //
+  // (before)
+  // dst = strcmp(P, "x")
+  //
+  // (after)
+  // v0 = P[0] - 'x'
+  // [if v0 == 0]
+  //   v1 = P[1]
+  // dst = phi(v0, v1)
+  //
+
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+
+  B.SetInsertPoint(CI);
+  BasicBlock *InitialBB = B.GetInsertBlock();
+  Value *Str1FirstCharacterValue =
+      B.CreateIntCast(B.CreateLoad(B.getInt8Ty(), Str1P), B.getInt32Ty(), true);
+  Value *Str2FirstCharacterValue = ConstantInt::get(
+      B.getInt32Ty(), static_cast<unsigned char>(Str2[0]), true);
+  Value *FirstCharacterSub =
+      B.CreateNSWSub(Str1FirstCharacterValue, Str2FirstCharacterValue);
+  Value *IsFirstCharacterSubZero = B.CreateICmpEQ(
+      FirstCharacterSub, ConstantInt::get(B.getInt32Ty(), 0, true));
+  Instruction *IsFirstCharacterSubZeroBBTerminator = SplitBlockAndInsertIfThen(
+      IsFirstCharacterSubZero, CI, /*Unreachable*/ false,
+      /*BranchWeights*/ nullptr, &DTU);
+
+  B.SetInsertPoint(IsFirstCharacterSubZeroBBTerminator);
+  B.GetInsertBlock()->setName("strcmp_fold_sub_is_zero");
+  BasicBlock *IsFirstCharacterSubZeroBB = B.GetInsertBlock();
+  Value *Str1SecondCharacterValue = B.CreateIntCast(
+      B.CreateLoad(B.getInt8Ty(),
+                   B.CreateConstInBoundsGEP1_64(B.getInt8Ty(), Str1P, 1)),
+      B.getInt32Ty(), true);
+
+  B.SetInsertPoint(CI);
+  B.GetInsertBlock()->setName("strcmp_fold_sub_join");
+
+  PHINode *Result = B.CreatePHI(B.getInt32Ty(), 2);
+  Result->addIncoming(FirstCharacterSub, InitialBB);
+  Result->addIncoming(Str1SecondCharacterValue, IsFirstCharacterSubZeroBB);
+
+  CI->replaceAllUsesWith(Result);
+  CI->eraseFromParent();
+
+  MadeCFGChange = true;
+
+  return true;
+}
+
+static bool foldLibraryCalls(Instruction &I, TargetTransformInfo &TTI,
+                             TargetLibraryInfo &TLI, DominatorTree &DT,
+                             bool &MadeCFGChange) {
+  CallInst *CI = dyn_cast<CallInst>(&I);
+  if (!CI)
+    return false;
+
+  bool IsCallingConvC = TargetLibraryInfoImpl::isCallingConvCCompatible(CI);
+  if (!IsCallingConvC)
+    return false;
+
+  Module *M = I.getModule();
+
+  LibFunc Func;
+  Function *Callee = CI->getCalledFunction();
+  if (!TLI.getLibFunc(*Callee, Func) || !isLibFuncEmittable(M, &TLI, Func))
+    return false;
+
+  IRBuilder<> Builder(I.getParent());
+
+  switch (Func) {
+  case LibFunc_sqrt:
+  case LibFunc_sqrtf:
+  case LibFunc_sqrtl:
+    return foldSqrt(CI, TTI, TLI);
+  case LibFunc_strcmp:
+    return foldStcmp(CI, Builder, DT, MadeCFGChange);
+  default:
+    break;
+  }
+
+  return false;
+}
+
 /// This is the entry point for folds that could be implemented in regular
 /// InstCombine, but they are separated because they are not expected to
 /// occur frequently and/or have more than a constant-length pattern match.
 static bool foldUnusualPatterns(Function &F, DominatorTree &DT,
                                 TargetTransformInfo &TTI,
-                                TargetLibraryInfo &TLI, AliasAnalysis &AA) {
+                                TargetLibraryInfo &TLI, AliasAnalysis &AA,
+                                bool &MadeCFGChange) {
   bool MadeChange = false;
   for (BasicBlock &BB : F) {
     // Ignore unreachable basic blocks.
     if (!DT.isReachableFromEntry(&BB))
       continue;
 
     const DataLayout &DL = F.getParent()->getDataLayout();
 
     // Walk the block backwards for efficiency. We're matching a chain of
     // use->defs, so we're more likely to succeed by starting from the bottom.
     // Also, we want to avoid matching partial patterns.
     // TODO: It would be more efficient if we removed dead instructions
     // iteratively in this loop rather than waiting until the end.
     for (Instruction &I : make_early_inc_range(llvm::reverse(BB))) {
       MadeChange |= foldAnyOrAllBitsSet(I);
       MadeChange |= foldGuardedFunnelShift(I, DT);
       MadeChange |= tryToRecognizePopCount(I);
       MadeChange |= tryToFPToSat(I, TTI);
       MadeChange |= tryToRecognizeTableBasedCttz(I);
       MadeChange |= foldConsecutiveLoads(I, DL, TTI, AA, DT);
       MadeChange |= foldPatternedLoads(I, DL);
       // NOTE: This function introduces erasing of the instruction `I`, so it
       // needs to be called at the end of this sequence, otherwise we may make
       // bugs.
-      MadeChange |= foldSqrt(I, TTI, TLI);
+      MadeChange |= foldLibraryCalls(I, TTI, TLI, DT, MadeCFGChange);
     }
   }
 
   // We're done with transforms, so remove dead instructions.
   if (MadeChange)
     for (BasicBlock &BB : F)
       SimplifyInstructionsInBlock(&BB);
 
   return MadeChange;
 }
 
 /// This is the entry point for all transforms. Pass manager differences are
 /// handled in the callers of this function.
 static bool runImpl(Function &F, AssumptionCache &AC, TargetTransformInfo &TTI,
                     TargetLibraryInfo &TLI, DominatorTree &DT,
-                    AliasAnalysis &AA) {
+                    AliasAnalysis &AA, bool &ChangedCFG) {
   bool MadeChange = false;
   const DataLayout &DL = F.getParent()->getDataLayout();
   TruncInstCombine TIC(AC, TLI, DL, DT);
   MadeChange |= TIC.run(F);
-  MadeChange |= foldUnusualPatterns(F, DT, TTI, TLI, AA);
+  MadeChange |= foldUnusualPatterns(F, DT, TTI, TLI, AA, ChangedCFG);
   return MadeChange;
 }
 
 PreservedAnalyses AggressiveInstCombinePass::run(Function &F,
                                                  FunctionAnalysisManager &AM) {
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
-  if (!runImpl(F, AC, TTI, TLI, DT, AA)) {
+
+  bool MadeCFGChange = false;
+
+  if (!runImpl(F, AC, TTI, TLI, DT, AA, MadeCFGChange)) {
     // No changes, all analyses are preserved.
     return PreservedAnalyses::all();
   }
+
   // Mark all the analyses that instcombine updates as preserved.
   PreservedAnalyses PA;
+
+  if (MadeCFGChange)
+    PA.preserve<DominatorTreeAnalysis>();
+  else
     PA.preserveSet<CFGAnalyses>();
+
   return PA;
 }

llvm/test/Transforms/AggressiveInstCombine/strcmp.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; TODO: Test that ...
+; RUN: opt < %s -passes=aggressive-instcombine -S | FileCheck %s
+
+declare i32 @strcmp(ptr, ptr)
+
+@s1 = constant [2 x i8] c"0\00"
+
+; Fold strcmp(C, "x").
+
+define i1 @fold_strcmp_s1_1(ptr %C) {
+; CHECK-LABEL: @fold_strcmp_s1_1(
+; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr %C, align 1
+; CHECK-NEXT:    [[SEXT1:%.*]] = sext i8 [[TMP1]] to i32
+; CHECK-NEXT:    [[ADD:%.*]] = sub nsw i32 [[SEXT1]], 48
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[ADD]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label %strcmp_fold_sub_is_zero, label %strcmp_fold_sub_join
+; CHECK-LABEL: strcmp_fold_sub_is_zero:
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i8, ptr %C, i64 1
+; CHECK-NEXT:    [[TMP3:%.*]] = load i8, ptr [[TMP2]], align 1
+; CHECK-NEXT:    [[SEXT2:%.*]] = sext i8 [[TMP3]] to i32
+; CHECK-NEXT:    br label %strcmp_fold_sub_join
+; CHECK-LABEL: strcmp_fold_sub_join:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[ADD]], %0 ], [ [[SEXT2]], %strcmp_fold_sub_is_zero ]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[PHI]], 0
+; CHECK-NEXT:    ret i1 [[CMP2]]
+;
+  %call = call i32 @strcmp(ptr %C, ptr noundef @s1)
+  %cmp = icmp eq i32 %call, 0
+  ret i1 %cmp
+}
+
+define i32 @fold_strcmp_s1_2(ptr %C) {
+; CHECK-LABEL: @fold_strcmp_s1_2(
+; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr %C, align 1
+; CHECK-NEXT:    [[SEXT1:%.*]] = sext i8 [[TMP1]] to i32
+; CHECK-NEXT:    [[ADD:%.*]] = sub nsw i32 [[SEXT1]], 48
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[ADD]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label %strcmp_fold_sub_is_zero, label %strcmp_fold_sub_join
+; CHECK-LABEL: strcmp_fold_sub_is_zero:
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i8, ptr %C, i64 1
+; CHECK-NEXT:    [[TMP3:%.*]] = load i8, ptr [[TMP2]], align 1
+; CHECK-NEXT:    [[SEXT2:%.*]] = sext i8 [[TMP3]] to i32
+; CHECK-NEXT:    br label %strcmp_fold_sub_join
+; CHECK-LABEL: strcmp_fold_sub_join:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[ADD]], %0 ], [ [[SEXT2]], %strcmp_fold_sub_is_zero ]
+; CHECK-NEXT:    ret i32 [[PHI]]
+;
+  %call = call i32 @strcmp(ptr %C, ptr noundef @s1)
+  ret i32 %call
+}