diff --git a/llvm/lib/IR/ReplaceConstant.cpp b/llvm/lib/IR/ReplaceConstant.cpp
--- a/llvm/lib/IR/ReplaceConstant.cpp
+++ b/llvm/lib/IR/ReplaceConstant.cpp
@@ -15,6 +15,7 @@
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/NoFolder.h"
+#include "llvm/IR/ValueMap.h"
 
 namespace llvm {
 // Replace a constant expression by instructions with equivalent operations at
@@ -40,7 +41,8 @@
     Instruction *I,
     std::map<Use *, std::vector<std::vector<ConstantExpr *>>> &CEPaths,
     SmallPtrSetImpl<Instruction *> *Insts) {
-  SmallPtrSet<ConstantExpr *, 8> Visited;
+  ValueMap<ConstantExpr *, Instruction *> Visited;
+
   for (Use &U : I->operands()) {
     // The operand U is either not a constant expression operand or the
     // constant expression paths do not belong to U, ignore U.
@@ -55,24 +57,48 @@
       BI = &(*(BB->getFirstInsertionPt()));
     }
 
-    // Go through the paths associated with operand U, and convert all the
-    // constant expressions along all paths to corresponding instructions.
+    // Go through all the paths associated with operand U, and convert all the
+    // constant expressions along all the paths to corresponding instructions.
     auto *II = I;
     auto &Paths = CEPaths[&U];
     for (auto &Path : Paths) {
       for (auto *CE : Path) {
-        if (!Visited.insert(CE).second)
-          continue;
-        auto *NI = CE->getAsInstruction();
-        NI->insertBefore(BI);
+        // Instruction which is equivalent to CE.
+        Instruction *NI = nullptr;
+
+        if (!Visited.count(CE)) {
+          // CE is encountered first time, convert it into a corresponding
+          // instruction NI, and appropriately insert NI before the parent
+          // instruction.
+          NI = CE->getAsInstruction();
+          NI->insertBefore(BI);
+
+          // Mark CE as visited by mapping CE to NI.
+          Visited[CE] = NI;
+
+          // If required collect NI.
+          if (Insts)
+            Insts->insert(NI);
+        } else {
+          // We had already encountered CE, the correponding instruction already
+          // exist, use it to replace CE.
+          NI = Visited[CE];
+        }
+
+        assert(NI && "Expected an instruction corresponding to constant "
+                     "expression.");
+
+        // Replace all uses of constant expression CE by the corresponding
+        // instruction NI within the current parent instruction.
         II->replaceUsesOfWith(CE, NI);
-        CE->removeDeadConstantUsers();
         BI = II = NI;
-        if (Insts)
-          Insts->insert(NI);
       }
     }
   }
+
+  // Remove all converted constant expressions which are dead by now.
+  for (auto Item : Visited)
+    Item.first->removeDeadConstantUsers();
 }
 
 void collectConstantExprPaths(
diff --git a/llvm/test/CodeGen/AMDGPU/lower-kernel-lds-constexpr.ll b/llvm/test/CodeGen/AMDGPU/lower-kernel-lds-constexpr.ll
--- a/llvm/test/CodeGen/AMDGPU/lower-kernel-lds-constexpr.ll
+++ b/llvm/test/CodeGen/AMDGPU/lower-kernel-lds-constexpr.ll
@@ -107,8 +107,10 @@
 ; CHECK-LABEL: @k5(
 ; CHECK-NEXT: %1 = addrspacecast [505 x i32] addrspace(3)* getelementptr inbounds (%llvm.amdgcn.kernel.k5.lds.t, %llvm.amdgcn.kernel.k5.lds.t addrspace(3)* @llvm.amdgcn.kernel.k5.lds, i32 0, i32 0) to [505 x i32]*
 ; CHECK-NEXT: %2 = getelementptr inbounds [505 x i32], [505 x i32]* %1, i64 0, i64 0
-; CHECK-NEXT: call void undef(i32* %2, i32* %2)
+; CHECK-NEXT: %3 = addrspacecast i32* %2 to i32 addrspace(4)*
+; CHECK-NEXT: %4 = addrspacecast i32* %2 to i32 addrspace(5)*
+; CHECK-NEXT: call void undef(i32 addrspace(4)* %3, i32 addrspace(5)* %4)
 ;
-  call void undef(i32* getelementptr inbounds ([505 x i32], [505 x i32]* addrspacecast ([505 x i32] addrspace(3)* @lds.4 to [505 x i32]*), i64 0, i64 0), i32* getelementptr inbounds ([505 x i32], [505 x i32]* addrspacecast ([505 x i32] addrspace(3)* @lds.4 to [505 x i32]*), i64 0, i64 0))
+  call void undef(i32 addrspace(4)* addrspacecast (i32* getelementptr inbounds ([505 x i32], [505 x i32]* addrspacecast ([505 x i32] addrspace(3)* @lds.4 to [505 x i32]*), i64 0, i64 0) to i32 addrspace(4)*),                  i32 addrspace(5)* addrspacecast (i32* getelementptr inbounds ([505 x i32], [505 x i32]* addrspacecast ([505 x i32] addrspace(3)* @lds.4 to [505 x i32]*), i64 0, i64 0) to i32 addrspace(5)*))
   ret void
 }