Index: llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
+++ llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
@@ -1650,26 +1650,10 @@
   PHINode *LCSSAPhi = dyn_cast<PHINode>(LoopExitBB->begin());
   if (!LCSSAPhi || LCSSAPhi->getNumIncomingValues() != 1)
     return false;
-  const SCEVAddRecExpr *LCSSAEv = 
+  const SCEVAddRecExpr *LCSSAEv =
       dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LCSSAPhi->getIncomingValue(0)));
-  if (!LCSSAEv || !LCSSAEv->isAffine())
-    return false;
 
-  auto *CleanupBB =
-      (PreCondBI->getSuccessor(0) == PH ? PreCondBI->getSuccessor(1)
-                                        : PreCondBI->getSuccessor(0));
-
-  // 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.
-  Value *ResInst = nullptr;
-  for (auto &Phi : CleanupBB->phis()) {
-    if (Phi.getBasicBlockIndex(LoopExitBB) != 1) {
-      ResInst = Phi.getIncomingValueForBlock(LoopExitBB);
-      break;
-    }
-  }
-  if (!ResInst)
+  if (!LCSSAEv || !LCSSAEv->isAffine())
     return false;
 
   // We can now expand the base of the str and transform the loop
@@ -1683,13 +1667,22 @@
       PH->getTerminator());
   EVC.add(Expanded);
   EVC.commit();
-				  
-  Value *LibCall = emitStrLen(Expanded, Builder, *DL, TLI);
-  Value *Strlen = Builder.CreateZExtOrTrunc(LibCall, ResInst->getType());
-  ResInst->replaceAllUsesWith(Strlen);
+
+  auto *Base = dyn_cast<SCEVUnknown>(SE->getPointerBase(LCSSAEv));
+  if (!Base)
+    return false;
+
+  // Insert the call to strlen
+  Value *Strlen = emitStrLen(Expanded, Builder, *DL, TLI);
+
+  // Rewrite LCSSAPhi as GEP that point to (%Str + %strlen)
+  Builder.SetInsertPoint(&*LCSSAPhi->getParent()->getFirstInsertionPt());
+  auto *GEP = Builder.CreateGEP(Base->getValue(), Strlen, "strlen-term");
+
+  LCSSAPhi->replaceAllUsesWith(GEP);
 
   // Remove the loop-exit branch and delete dead instructions
-  RecursivelyDeleteTriviallyDeadInstructions(ResInst, TLI);
+  RecursivelyDeleteTriviallyDeadInstructions(LCSSAPhi, TLI);
   ConstantInt *NewLoopCond = LoopTerm->getSuccessor(0) == LoopBody
                                  ? Builder.getFalse()
                                  : Builder.getTrue();
Index: llvm/test/Transforms/LoopIdiom/recognize-strlen.ll
===================================================================
--- llvm/test/Transforms/LoopIdiom/recognize-strlen.ll
+++ llvm/test/Transforms/LoopIdiom/recognize-strlen.ll
@@ -21,9 +21,13 @@
 ; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i8 undef, 0
 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_INC]]
 ; CHECK:       for.end:
+; CHECK-NEXT:    [[STRLEN_TERM:%.*]] = getelementptr i8, i8* [[STR]], i64 [[STRLEN]]
+; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint i8* [[STRLEN_TERM]] to i64
+; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint i8* [[STR]] to i64
+; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]]
 ; CHECK-NEXT:    br label [[CLEANUP]]
 ; CHECK:       cleanup:
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[STRLEN]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[LOR_LHS_FALSE]] ]
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[SUB_PTR_SUB]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[LOR_LHS_FALSE]] ]
 ; CHECK-NEXT:    ret i64 [[RETVAL_0]]
 ;
 entry:
@@ -67,9 +71,13 @@
 ; 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:    [[STRLEN_TERM:%.*]] = getelementptr i8, i8* [[STR]], i64 [[STRLEN]]
+; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint i8* [[STRLEN_TERM]] to i64
+; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint i8* [[STR]] to i64
+; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]]
 ; CHECK-NEXT:    br label [[CLEANUP]]
 ; CHECK:       cleanup:
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[STRLEN]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[SUB_PTR_SUB]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i64 [[RETVAL_0]]
 ;
 entry: