Index: include/llvm-c/Core.h
===================================================================
--- include/llvm-c/Core.h
+++ include/llvm-c/Core.h
@@ -2332,6 +2332,16 @@
  * Remove and delete an instruction.
  *
  * The instruction specified is removed from its containing building
+ * block but is kept alive.
+ *
+ * @see llvm::Instruction::removeFromParent()
+ */
+void LLVMInstructionRemoveFromParent(LLVMValueRef Inst);
+
+/**
+ * Remove and delete an instruction.
+ *
+ * The instruction specified is removed from its containing building
  * block and then deleted.
  *
  * @see llvm::Instruction::eraseFromParent()
Index: lib/IR/Core.cpp
===================================================================
--- lib/IR/Core.cpp
+++ lib/IR/Core.cpp
@@ -2005,6 +2005,10 @@
   return wrap(&*--I);
 }
 
+void LLVMInstructionRemoveFromParent(LLVMValueRef Inst) {
+  unwrap<Instruction>(Inst)->removeFromParent();
+}
+
 void LLVMInstructionEraseFromParent(LLVMValueRef Inst) {
   unwrap<Instruction>(Inst)->eraseFromParent();
 }
Index: test/Bindings/llvm-c/echo.ll
===================================================================
--- test/Bindings/llvm-c/echo.ll
+++ test/Bindings/llvm-c/echo.ll
@@ -80,3 +80,19 @@
 next9:
   ret i32 0
 }
+
+define i32 @loop(i32 %i) {
+  br label %cond
+cond:
+  %c = phi i32 [ %i, %0 ], [ %j, %do ]
+  %p = phi i32 [ %r, %do ], [ 789, %0 ]
+  %1 = icmp eq i32 %c, 0
+  br i1 %1, label %do, label %done
+do:
+  %2 = sub i32 %p, 23
+  %j = sub i32 %i, 1
+  %r = mul i32 %2, 3
+  br label %cond
+done:
+  ret i32 %p
+}
Index: tools/llvm-c-test/echo.cpp
===================================================================
--- tools/llvm-c-test/echo.cpp
+++ tools/llvm-c-test/echo.cpp
@@ -176,7 +176,7 @@
     }
 
     // Function argument should always be in the map already.
-    if (LLVMIsAArgument(Src)) {
+    if (LLVMIsAArgument(Src) || LLVMIsAInstruction(Src)) {
       auto i = VMap.find(Src);
       if (i != VMap.end())
         return i->second;
@@ -203,8 +203,15 @@
     // Check if this is something we already computed.
     {
       auto i = VMap.find(Src);
-      if (i != VMap.end())
-        return i->second;
+      if (i != VMap.end()) {
+        // If we have a hit, it means we already generated the instruction
+        // as a dependancy to somethign else. We need to make sure
+        // it is ordered properly.
+        auto I = i->second;
+        LLVMInstructionRemoveFromParent(I);
+        LLVMInsertIntoBuilderWithName(Builder, I, Name);
+        return I;
+      }
     }
 
     // We tried everything, it must be an instruction
@@ -334,6 +341,24 @@
         Dst = LLVMBuildICmp(Builder, Pred, LHS, RHS, Name);
         break;
       }
+      case LLVMPHI: {
+        LLVMTypeRef Ty = clone_type(LLVMTypeOf(Src), Ctx);
+
+        // We need to agressively set things here because of loops.
+        VMap[Src] = Dst = LLVMBuildPhi(Builder, Ty, Name);
+
+        SmallVector<LLVMValueRef, 8> Values;
+        SmallVector<LLVMBasicBlockRef, 8> Blocks;
+
+        unsigned IncomingCount = LLVMCountIncoming(Src);
+        for (unsigned i = 0; i < IncomingCount; ++i) {
+          Blocks.push_back(DeclareBB(LLVMGetIncomingBlock(Src, i)));
+          Values.push_back(CloneValue(LLVMGetIncomingValue(Src, i)));
+        }
+
+        LLVMAddIncoming(Dst, Values.data(), Blocks.data(), IncomingCount);
+        return Dst;
+      }
       case LLVMCall: {
         SmallVector<LLVMValueRef, 8> Args;
         int ArgCount = LLVMGetNumArgOperands(Src);