Strlen loop idiom recognition

[anjankgk]

Summary

(Original patch by musman under D83392. I am planning to commit this in his absence, with his consent.)
This patch adds strlen to LoopIdiomRecognize.cpp. It is the first part of 3 patches:

1. Strlen loop idiom recognition
2. Strlen16 recognition and creation of new strlen16 intrinsic
3. Folding of strlen/strlen16 call if they are only used for zero equality comparison (replace with load of first char)

Example that this recognizes:

unsigned strlen(char *Str) {

char *Src = Str;
if (!Src)
  return 0;
for (; *Src;)
  Src++;
return Src - Str;

}

[anjankgk]

Gentle ping..

[shawnl]

This pass should recognise the nonnull attribute, as it is analyzing against null.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1649

If the passed pointer has the "nonnull" attribute then this condition need not be present.

[shawnl]

It is possible DCE will handle the null check with "nonnull" attribute, so add the test first.

Otherwise I like how little code this took compared to earlier versions.

[efriedma]

(For future reference, Phabricator has an option "commandeer" a revision, to take control if the original author of a patch leaves a patch incomplete for whatever reason. Obviously use sparingly.)

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1649

The icmp isn't against a pointer; it's against an i8. Or, it should be; I guess the code is missing a check that it's i8, as opposed to some arbitrary integer type.

For comparison, it's undefined behavior to call strlen with a null pointer.

1701

I'm not sure how ResInst is connected to the rest of this transform; why are we transforming the operand of some random PHI node?

1718

"dead instructions", not "death instructions".

llvm/test/Transforms/LoopIdiom/recognize-strlen.ll

2

Can you generate the check lines use update_test_checks.py? It isn't obvious what the whole function looks like as a result of this transform.

[shawnl]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1649

My bad. I was really working from example code (and the tests also have a null check). This is why in my C code I always use '\x00' for NUL (the character) and not 0 or NULL.

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1701

I added a comment for clarity -

// Finally, we find the phi node that corresponds to the distance between the
// pointers and replace it's uses by the call to strlen in the transformed
// code.

[anjankgk]

Check for i8 type and use update_test_checks.py for testfile.

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1701

The patch doesn't appear to prove that anywhere.

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1701

I am getting the sub instruction saved in ResInst and replacing that in line# 1689. Is that something that you prefer to be done in a different way?

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1701

How do you know it's a sub instruction?

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1701

I agree. The current code is actually just looking for the phi node from the predecessor (LoopExitBB) block. I think, I should add a code to ensure that is actually a sub instruction. However, I am afraid that that could again lead to a pattern-matching kind of code which was initially posted.

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1701

What happens if we ignore ResInst, and rewrite LCSSAPhi instead? That still eliminates the inner loop; later passes should optimize the resulting arithmetic.

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1701

I tried a few things, but I am not sure how to do that.
This is the i/p BB:

for.end:                                          ; preds = %for.inc
  %incdec.ptr.lcssa = phi i8* [ %incdec.ptr, %for.inc ]
  %sub.ptr.lhs.cast = ptrtoint i8* %incdec.ptr.lcssa to i64
  %sub.ptr.rhs.cast = ptrtoint i8* %Str to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  br label %cleanup

return type of strlen is i64 (same as ResInt which is %sub.ptr.sub), as compared to the type of lcssa instrn (%incdec.ptr.lcssa) which is a i8*. I am not clear how I can rewrite lcssa with the strlen as suggested.

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1701

%incdec.ptr.lcssa is going to be equivalent to something like getelementptr i8, i8* %Str, i64 %strlen. Speaking in generic terms, replace %Str with the start value of LCSSAEv. Add the two values together with SCEV, and use SCEVExpander to materialize it.

[anjankgk]

Rewrite the LCSSAPhi instruction to reflect strlen idiom recognition.

[efriedma]

Phabricator doesn't track incremental patches the way you're uploading them; please upload the full diff against master.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1620–1777

LCSSAEv->getStart() is the value of the output of the loop; the input to strlen needs to be the input to the load (LoadEv->getStart()).

More tests would be helpful to catch this sort of issue.

1621

getPointerBase() isn't right; it strips all offsets from the pointer.

I'd like to see more regression test coverage of different variations on the values produced by the loop.

[hiraditya]

It'll be nice to know if this patch worked fine with a set of regression tests.
results on LLVM testsuite, or clang bootstrap will really help.

Thanks for working on this.

[anjankgk]

Changes from previous review comments:

• Replaced LCSSAEv->getStart() by LoadEv->getStart()
• Added another test function where multiple LCSSAPhi nodes were present and therefore shouldn't have replaced with strlen function.

[anjankgk]

In D88460#2342407, @efriedma wrote:

Phabricator doesn't track incremental patches the way you're uploading them; please upload the full diff against master.

Thanks @efriedma! I made the changes suggested and added another test as well. I have uploaded the right patch this time. Pls let me know in case it's still showing up wrongly.

[anjankgk]

In D88460#2342937, @hiraditya wrote:

It'll be nice to know if this patch worked fine with a set of regression tests.
results on LLVM testsuite, or clang bootstrap will really help.

Thanks for working on this.

Thank you for the feedback @hiraditya! I have tested the latest patch at various options (O2, O3, LTO and PGO) against the SPEC benchmarks as well as run the lnt tests and bootstrap tests successfully. If you were concerned about any other specific testsuite, pls let me know.

[hiraditya]

In D88460#2458205, @anjankgk wrote:

In D88460#2342937, @hiraditya wrote:

It'll be nice to know if this patch worked fine with a set of regression tests.
results on LLVM testsuite, or clang bootstrap will really help.

Thanks for working on this.

Thank you for the feedback @hiraditya! I have tested the latest patch at various options (O2, O3, LTO and PGO) against the SPEC benchmarks as well as run the lnt tests and bootstrap tests successfully. If you were concerned about any other specific testsuite, pls let me know.

Nice, if we have performance improvements on any of the benchmarks/workloads then do share.

[anjankgk]

In D88460#2462158, @hiraditya wrote:

In D88460#2458205, @anjankgk wrote:

In D88460#2342937, @hiraditya wrote:

It'll be nice to know if this patch worked fine with a set of regression tests.
results on LLVM testsuite, or clang bootstrap will really help.

Thanks for working on this.

Thank you for the feedback @hiraditya! I have tested the latest patch at various options (O2, O3, LTO and PGO) against the SPEC benchmarks as well as run the lnt tests and bootstrap tests successfully. If you were concerned about any other specific testsuite, pls let me know.

Nice, if we have performance improvements on any of the benchmarks/workloads then do share.

I did track performance measurements on a bunch of benchmarks but there was nothing noticeable since what this patch is doing is just recognizing the idiom and replacing with the lib call. However, going forward, if we could better the implementation of these library calls (which could be target platform specific) this should give us gains.

[anjankgk]

Gentle ping...

[anjankgk]

Another gentle reminder for the review.. Thanks!

[hiraditya]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1692

break when I != PN because PNs are in the beginning of a basic block.

if (!PN)
  break;

1754

Should we call forgetLoop before deleting the loop?

1756

Shouldn't be necessary as ORE is already there.

[anjankgk]

Updates from tests and fix to identifying the correct replace instruction from exit BB.

[anjankgk]

I have updated the code based on some more test results and based on the review comments.
Thanks!

[anjankgk]

Gentle ping..

[hiraditya]

Do we have an example of real world workload where this pattern was found?

[hiraditya]

This comment was removed by hiraditya.

[joerg]

Please make sure at the very least that it doesn't get matched if a function named strlen and also test for that.

[hiraditya]

In D88460#2816028, @joerg wrote:

Please make sure at the very least that it doesn't get matched if a function named strlen and also test for that.

yeah, transforming strlen itself will be a lot of trouble ;)

[hiraditya]

Can this patch also convert this one to strlen? gcc is able to recognize this idiom: https://godbolt.org/z/7ra1ErqKK

size_t strlen2(char *Str) {
    char *Src = Str;
    int i = 0;
    while (*Src) {
        ++i;
        ++Src;
    }
    return i;
}

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BuildLibCalls.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
+using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "loop-idiom"
 
 STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
 STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores");
+STATISTIC(NumStrLen, "Number of strlen's formed from loop loads");
 
 static cl::opt<bool> UseLIRCodeSizeHeurs(
     "use-lir-code-size-heurs",
     cl::desc("Use loop idiom recognition code size heuristics when compiling"
              "with -Os/-Oz"),
     cl::init(true), cl::Hidden);
 
+static cl::opt<bool> DisableStrLenIdiom(
+    "disable-strlen-idiom",
+    cl::desc("Disable strlen loop idiom recognize and transform"),
+    cl::init(false), cl::Hidden);
+
 namespace {
 
 class LoopIdiomRecognize {
   Loop *CurLoop = nullptr;
   AliasAnalysis *AA;
   DominatorTree *DT;
   LoopInfo *LI;
   ScalarEvolution *SE;
void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst,
                                PHINode *CntPhi, Value *Var);
   bool recognizeAndInsertFFS();  /// Find First Set: ctlz or cttz
   void transformLoopToCountable(Intrinsic::ID IntrinID, BasicBlock *PreCondBB,
                                 Instruction *CntInst, PHINode *CntPhi,
                                 Value *Var, Instruction *DefX,
                                 const DebugLoc &DL, bool ZeroCheck,
                                 bool IsCntPhiUsedOutsideLoop);
 
+  bool recognizeAndInsertStrLen();
   /// @}
 };
 
 class LoopIdiomRecognizeLegacyPass : public LoopPass {
 public:
   static char ID;
 
   explicit LoopIdiomRecognizeLegacyPass() : LoopPass(ID) {

 }
 
 bool LoopIdiomRecognize::runOnNoncountableLoop() {
   LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["
                     << CurLoop->getHeader()->getParent()->getName()
                     << "] Noncountable Loop %"
                     << CurLoop->getHeader()->getName() << "\n");
 
-  return recognizePopcount() || recognizeAndInsertFFS();
+  return recognizePopcount() || recognizeAndInsertFFS() ||
+         recognizeAndInsertStrLen();
+}
+
+/// getCandidateSubInstr - Return sub instruction if there is a pointer
+/// difference of \p EndAddress and \p StartAddress calculated that is also the
+/// only use of EndAddress, else return nullptr to the caller.
+static Instruction *getCandidateSubInstr(Instruction *EndAddress,
+                                         Value *StartAddress) {
+  // The pointer to the end address should only have one use which is a pointer
+  // to int instruction.
+  if (!EndAddress->hasOneUse())
+    return nullptr;
+
+  auto &U = *EndAddress->use_begin();
+  if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(U.getUser())) {
+    if (!PToI->hasOneUse())
+      return nullptr;
+    Use &PToIUse = *PToI->use_begin();
+
+    // The only user of the PtrToIntInst should be the sub instruction that
+    // calculates the difference b/w the two pointer operands.
+    Instruction *Inst = dyn_cast<Instruction>(PToIUse.getUser());
+    if (Inst->getOpcode() != Instruction::Sub || Inst->getOperand(0) != PToI)
+      return nullptr;
+    if (match(Inst->getOperand(1), m_PtrToInt(m_Value(StartAddress)))) {
+      // The candidate sub instruction is found, update the pointer to pass
+      // back to the caller.
+      return Inst;
+    }
+  }
+
+  return nullptr;
 }
 
 /// Check if the given conditional branch is based on the comparison between
-/// a variable and zero, and if the variable is non-zero or zero (JmpOnZero is
-/// true), the control yields to the loop entry. If the branch matches the
+/// a variable and zero/null, and if the variable is non-zero or zero (JmpOnZero
+/// is true), the control yields to the loop entry. If the branch matches the
 /// behavior, the variable involved in the comparison is returned. This function
 /// will be called to see if the precondition and postcondition of the loop are
 /// in desirable form.
 static Value *matchCondition(BranchInst *BI, BasicBlock *LoopEntry,
                              bool JmpOnZero = false) {
   if (!BI || !BI->isConditional())
     return nullptr;
 
   ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition());
   if (!Cond)
     return nullptr;
 
+  if (!isa<ConstantPointerNull>(Cond->getOperand(1))) {
     ConstantInt *CmpZero = dyn_cast<ConstantInt>(Cond->getOperand(1));
     if (!CmpZero || !CmpZero->isZero())
       return nullptr;
+  }
 
   BasicBlock *TrueSucc = BI->getSuccessor(0);
   BasicBlock *FalseSucc = BI->getSuccessor(1);
   if (JmpOnZero)
     std::swap(TrueSucc, FalseSucc);
 
   ICmpInst::Predicate Pred = Cond->getPredicate();
   if ((Pred == ICmpInst::ICMP_NE && TrueSucc == LoopEntry) ||
if (HeaderSize != IdiomCanonicalSize &&
       Cost > TargetTransformInfo::TCC_Basic)
     return false;
 
   transformLoopToCountable(IntrinID, PH, CntInst, CntPhi, InitX, DefX,
                            DefX->getDebugLoc(), ZeroCheck,
                            IsCntPhiUsedOutsideLoop);
   return true;
 }
 
+/// Recognizes a strlen idiom by checking for loops that increment
+/// a char pointer and then subtract with the base pointer.
+///
+/// If detected, transforms the relevant code to a strlen function
+/// call, and returns true; otherwise, returns false.
+///
+/// The core idiom we are trying to detect is:
+/// \code
+///     if (str == NULL)
+///       goto loop-exit // the precondition of the loop
+///     start = str;
+///     do {
+///       str++;
+///     } while(*str!='\0');
+///     return (str - start);
+/// loop-exit:
+/// \endcode
+///
+/// The transformed output is similar to below c-code:
+/// \code
+///     if (str == NULL)
+///       goto loop-exit // the precondition of the loop
+///     return strlen(str);
+/// \endcode
+bool LoopIdiomRecognize::recognizeAndInsertStrLen() {
+  if (DisableStrLenIdiom)
+    return false;
+
+  // Give up if the loop has multiple blocks or multiple backedges.
+  if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
+    return false;
+
+  // It should have a preheader containing nothing but an unconditional branch.
+  auto *Pre = CurLoop->getLoopPreheader();
+  if (!Pre || &Pre->front() != Pre->getTerminator())
+    return false;
+
+  auto *EntryBI = dyn_cast<BranchInst>(Pre->getTerminator());
+  if (!EntryBI || EntryBI->isConditional())
+    return false;
+
+  // It should have a precondition block
+  auto *PreCondBB = Pre->getSinglePredecessor();
+  if (!PreCondBB)
+    return false;
+
+  // The precondition terminator instruction should skip the loop body based on
+  // an icmp with zero/null.
+  if (!matchCondition(dyn_cast<BranchInst>(PreCondBB->getTerminator()), Pre))
+    return false;
+
+  // The loop exit must be conditioned on an icmp with 0.
+  // The icmp operand has to be a load on some SSA reg that increments
+  // by 1 in the loop.
+  auto *LoopBody = *(CurLoop->block_begin());
+  auto *LoopTerm = dyn_cast<BranchInst>(LoopBody->getTerminator());
+  auto *LoopCond = matchCondition(LoopTerm, LoopBody);
+
+  if (!LoopCond)
+    return false;
+
+  auto *LoopLoad = dyn_cast<LoadInst>(LoopCond);
+  if (!LoopLoad || !LoopLoad->getType()->isIntegerTy(8) ||
+      LoopLoad->getPointerAddressSpace() != 0)
+    return false;
+
+  // See if the pointer expression is an AddRec with step 1 ({n,+,1}) on
+  // the loop, indicating strlen calculation.
+  auto *IncPtr = LoopLoad->getPointerOperand();
+  const SCEVAddRecExpr *LoadEv = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IncPtr));
+  if (!LoadEv || LoadEv->getLoop() != CurLoop || !LoadEv->isAffine())
+    return false;
+  auto *StepRec = LoadEv->getStepRecurrence(*SE);
+  if (!StepRec || !StepRec->isOne())
+    return false;
+
+  // Scan every instruction in the loop to ensure there are no side effects.
+  for (auto &I : *LoopBody)
+    if (I.mayHaveSideEffects())
+      return false;
+
+  auto *LoopExitBB = CurLoop->getExitBlock();
+  if (!LoopExitBB)
+    return false;
+
+  // Check that the loop exit block is valid:
+  // It needs to have exactly one LCSSA Phi which is an AddRec.
+  PHINode *LCSSAPhi = nullptr;
+  for (PHINode &PN : LoopExitBB->phis()) {
+    if (!LCSSAPhi && PN.getNumIncomingValues() == 1)
+      LCSSAPhi = &PN;
+    else
+      return false;
+  }
+
+  if (!LCSSAPhi || !SE->isSCEVable(LCSSAPhi->getType()))
+    return false;
+
+  const SCEVAddRecExpr *LCSSAEv =
+      dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LCSSAPhi->getIncomingValue(0)));
+
+  if (!LCSSAEv || !dyn_cast<SCEVUnknown>(SE->getPointerBase(LCSSAEv)) ||
+      !LCSSAEv->isAffine())
+    return false;
+
+  // We can now expand the base of the str
+  SCEVExpander Expander(*SE, *DL, "loop-idiom");
+  ExpandedValuesCleaner EVC(Expander, TLI);
+  IRBuilder<> Builder(Pre->getTerminator());
+
+  Value *Expanded = Expander.expandCodeFor(
+      LoadEv->getStart(),
+      Builder.getInt8PtrTy(LoopLoad->getPointerAddressSpace()),
+      Pre->getTerminator());
+
+  if (!Expanded)
+    return false;
+
+  // Check that the LoopExitBB is calculating the string length
+  Instruction *ResInst = getCandidateSubInstr(LCSSAPhi, Expanded);
+  if (!ResInst)
+    return false;
+
+  Value *StrLen = emitStrLen(Expanded, Builder, *DL, TLI);
+  if (!StrLen)
+    return false;
+
+  EVC.add(Expanded);
+  EVC.commit();
+
+  // Replace the subtraction instruction by the result of strlen
+  ResInst->replaceAllUsesWith(StrLen);
+
+  // Remove the loop-exit branch and delete dead instructions
+  RecursivelyDeleteTriviallyDeadInstructions(ResInst, TLI);
+
+  ConstantInt *NewLoopCond = LoopTerm->getSuccessor(0) == LoopBody
+                                 ? Builder.getFalse()
+                                 : Builder.getTrue();
+  LoopTerm->setCondition(NewLoopCond);
+  deleteDeadInstruction(cast<Instruction>(LoopCond));
+  deleteDeadInstruction(cast<Instruction>(IncPtr));
+  SE->forgetLoop(CurLoop);
+
+  LLVM_DEBUG(dbgs() << "  Formed strlen: " << *StrLen << "\n");
+
+  ORE.emit([&]() {
+    return OptimizationRemark(DEBUG_TYPE, "recognizeAndInsertStrLen",
+                              CurLoop->getStartLoc(), Pre)
+           << "Transformed pointer difference into a call to strlen() function";
+  });
+
+  ++NumStrLen;
+  return true;
+}
+
 /// Recognizes a population count idiom in a non-countable loop.
 ///
 /// If detected, transforms the relevant code to issue the popcount intrinsic
 /// function call, and returns true; otherwise, returns false.
 bool LoopIdiomRecognize::recognizePopcount() {
   if (TTI->getPopcntSupport(32) != TargetTransformInfo::PSK_FastHardware)
     return false;
 
   // Counting population are usually conducted by few arithmetic instructions.

llvm/test/Transforms/LoopIdiom/recognize-strlen.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -loop-idiom < %s -S | FileCheck %s
+target datalayout = "e-m:e-i64:64-n32:64"
+target triple = "powerpc64le-unknown-linux-gnu"
+
+define i64 @valid_strlen1(i8* %Str) {
+; CHECK-LABEL: @valid_strlen1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[STR:%.*]], null
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[CLEANUP:%.*]], label [[LOR_LHS_FALSE:%.*]]
+; CHECK:       lor.lhs.false:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i8, i8* [[STR]], align 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[CLEANUP]], label [[FOR_INC_PREHEADER:%.*]]
+; CHECK:       for.inc.preheader:
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, i8* [[STR]], i64 1
+; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(i8* [[SCEVGEP]])
+; CHECK-NEXT:    br label [[FOR_INC:%.*]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[SRC_09:%.*]] = phi i8* [ undef, [[FOR_INC]] ], [ [[STR]], [[FOR_INC_PREHEADER]] ]
+; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i8 undef, 0
+; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_INC]]
+; CHECK:       for.end:
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[STRLEN]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[LOR_LHS_FALSE]] ]
+; CHECK-NEXT:    ret i64 [[RETVAL_0]]
+;
+entry:
+  %tobool = icmp eq i8* %Str, null
+  br i1 %tobool, label %cleanup, label %lor.lhs.false
+
+lor.lhs.false:                                    ; preds = %entry
+  %0 = load i8, i8* %Str, align 1
+  %cmp = icmp eq i8 %0, 0
+  br i1 %cmp, label %cleanup, label %for.inc
+
+for.inc:                                          ; preds = %lor.lhs.false, %for.inc
+  %Src.09 = phi i8* [ %incdec.ptr, %for.inc ], [ %Str, %lor.lhs.false ]
+  %incdec.ptr = getelementptr inbounds i8, i8* %Src.09, i64 1
+  %.pr = load i8, i8* %incdec.ptr, align 1
+  %tobool2 = icmp eq i8 %.pr, 0
+  br i1 %tobool2, label %for.end, label %for.inc
+
+for.end:                                          ; preds = %for.inc
+  %sub.ptr.lhs.cast = ptrtoint i8* %incdec.ptr to i64
+  %sub.ptr.rhs.cast = ptrtoint i8* %Str to i64
+  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
+  br label %cleanup
+
+cleanup:                                          ; preds = %lor.lhs.false, %entry, %for.end
+  %retval.0 = phi i64 [ %sub.ptr.sub, %for.end ], [ 0, %entry ], [ 0, %lor.lhs.false ]
+  ret i64 %retval.0
+}
+
+
+define i64 @valid_strlen2(i8* %Str) {
+; CHECK-LABEL: @valid_strlen2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[STR:%.*]], null
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[CLEANUP:%.*]], label [[FOR_COND_PREHEADER:%.*]]
+; CHECK:       for.cond.preheader:
+; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(i8* [[STR]])
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp eq i8 undef, 0
+; CHECK-NEXT:    [[INCDEC_PTR:%.*]] = getelementptr inbounds i8, i8* undef, i64 1
+; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[STRLEN]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i64 [[RETVAL_0]]
+;
+entry:
+  %tobool = icmp eq i8* %Str, null
+  br i1 %tobool, label %cleanup, label %for.cond
+
+for.cond:                                         ; preds = %entry, %for.cond
+  %Src.0 = phi i8* [ %incdec.ptr, %for.cond ], [ %Str, %entry ]
+  %0 = load i8, i8* %Src.0, align 1
+  %tobool1 = icmp eq i8 %0, 0
+  %incdec.ptr = getelementptr inbounds i8, i8* %Src.0, i64 1
+  br i1 %tobool1, label %for.end, label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %sub.ptr.lhs.cast = ptrtoint i8* %Src.0 to i64
+  %sub.ptr.rhs.cast = ptrtoint i8* %Str to i64
+  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
+  br label %cleanup
+
+  cleanup:                                          ; preds = %entry, %for.end
+  %retval.0 = phi i64 [ %sub.ptr.sub, %for.end ], [ 0, %entry ]
+  ret i64 %retval.0
+}
+
+
+define void @invalid_strlen3(i8* %s, i32 zeroext %i) {
+; CHECK-LABEL: @invalid_strlen3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i8* [ [[S:%.*]], [[ENTRY:%.*]] ], [ [[INCDEC_PTR1:%.*]], [[WHILE_COND]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i8, i8* [[S_ADDR_0]], align 1
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    [[INCDEC_PTR1]] = getelementptr inbounds i8, i8* [[S_ADDR_0]], i64 1
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[WHILE_END:%.*]], label [[WHILE_COND]]
+; CHECK:       while.end:
+; CHECK-NEXT:    [[S_ADDR_0_LCSSA:%.*]] = phi i8* [ [[S_ADDR_0]], [[WHILE_COND]] ]
+; CHECK-NEXT:    [[INCDEC_PTR1_LCSSA:%.*]] = phi i8* [ [[INCDEC_PTR1]], [[WHILE_COND]] ]
+; CHECK-NEXT:    store i8 45, i8* [[S_ADDR_0_LCSSA]], align 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[I:%.*]], 10
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    store i8 65, i8* [[INCDEC_PTR1_LCSSA]], align 1
+; CHECK-NEXT:    br label [[IF_END9:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store i8 66, i8* [[INCDEC_PTR1_LCSSA]], align 1
+; CHECK-NEXT:    br label [[IF_END9]]
+; CHECK:       if.end9:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.cond, %entry
+  %s.addr.0 = phi i8* [ %s, %entry ], [ %incdec.ptr1, %while.cond ]
+  %0 = load i8, i8* %s.addr.0, align 1
+  %tobool.not = icmp eq i8 %0, 0
+  %incdec.ptr1 = getelementptr inbounds i8, i8* %s.addr.0, i64 1
+  br i1 %tobool.not, label %while.end, label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  %s.addr.0.lcssa = phi i8* [ %s.addr.0, %while.cond ]
+  %incdec.ptr1.lcssa = phi i8* [ %incdec.ptr1, %while.cond ]
+  store i8 45, i8* %s.addr.0.lcssa, align 1
+  %cmp = icmp ult i32 %i, 10
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %while.end
+  store i8 65, i8* %incdec.ptr1.lcssa, align 1
+  br label %if.end9
+
+if.end:                                           ; preds = %while.end
+  store i8 66, i8* %incdec.ptr1.lcssa, align 1
+  br label %if.end9
+
+if.end9:                                          ; preds = %if.end, %if.then
+  ret void
+}