Improve the C API echo test tool to emit basic block is the right order.

[deadalnix]

Summary

As per title. Also add a facility method to get the name of a basic block from the C API.

[deadalnix]

Formating changes + reduce diff size by keeping clone_params at the same place.

[deadalnix]

Remove TODO.

[mehdi_amini]

tools/llvm-c-test/echo.cpp

349

report_fatal_error(..) ?

355

(same)

369

This is not clear to me that CloneBB will enforce ordering in the absolute: if "Prev" hasn't been encountered yet it may be seen later and will be moved.

On the opposite if you're relying here on the order in which CloneBB is called, what is the ordering actually doing?

[deadalnix]

tools/llvm-c-test/echo.cpp

220

DeclareBB is called here for instance.

369

CloneBB will be called in order, but DeclareBB will be called whenever the basic block is needed (for instance, because it is the destination of a branch).

[mehdi_amini]

LGTM.

[deadalnix]

Use report_fatal_error and remove braces around one line if

include/llvm-c/Core.h

 LLVMBool LLVMValueIsBasicBlock(LLVMValueRef Val);
 
 /**
  * Convert an LLVMValueRef to an LLVMBasicBlockRef instance.
  */
 LLVMBasicBlockRef LLVMValueAsBasicBlock(LLVMValueRef Val);
 
 /**
+ * Obtain the string name of a basic block.
+ */
+const char *LLVMGetBasicBlockName(LLVMBasicBlockRef BB);
+
+/**
  * Obtain the function to which a basic block belongs.
  *
  * @see llvm::BasicBlock::getParent()
  */
 LLVMValueRef LLVMGetBasicBlockParent(LLVMBasicBlockRef BB);
 
 /**
  * Obtain the terminator instruction for a basic block.

lib/IR/Core.cpp

 LLVMBool LLVMValueIsBasicBlock(LLVMValueRef Val) {
   return isa<BasicBlock>(unwrap(Val));
 }
 
 LLVMBasicBlockRef LLVMValueAsBasicBlock(LLVMValueRef Val) {
   return wrap(unwrap<BasicBlock>(Val));
 }
 
+const char *LLVMGetBasicBlockName(LLVMBasicBlockRef BB) {
+  return unwrap(BB)->getName().data();
+}
+
 LLVMValueRef LLVMGetBasicBlockParent(LLVMBasicBlockRef BB) {
   return wrap(unwrap(BB)->getParent());
 }
 
 LLVMValueRef LLVMGetBasicBlockTerminator(LLVMBasicBlockRef BB) {
   return wrap(unwrap(BB)->getTerminator());
 }
 

test/Bindings/llvm-c/echo.ll

define i32 @iops(i32 %a, i32 %b) {
   %13 = xor i32 %12, %4
   ret i32 %13
 }
 
 define i32 @call() {
   %1 = call i32 @iops(i32 23, i32 19)
   ret i32 %1
 }
+
+define i32 @bborder(i32 %a, i32 %b) {
+  br label %br
+unreachable:
+  unreachable
+br:
+  br label %unreachable
+}

tools/llvm-c-test/echo.cpp

struct CAPIDenseMapInfo {
     }
     static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
   };
 
   typedef DenseMap<T*, T*, CAPIDenseMapInfo> Map;
 };
 
 typedef CAPIDenseMap<LLVMValueRef>::Map ValueMap;
+typedef CAPIDenseMap<LLVMBasicBlockRef>::Map BasicBlockMap;
 
 static LLVMTypeRef clone_type(LLVMTypeRef Src, LLVMContextRef Ctx) {
   LLVMTypeKind Kind = LLVMGetTypeKind(Src);
   switch (Kind) {
     case LLVMVoidTypeKind:
       return LLVMVoidTypeInContext(Ctx);
     case LLVMHalfTypeKind:
       return LLVMHalfTypeInContext(Ctx);

 }
 
 static LLVMModuleRef get_module(LLVMBuilderRef Builder) {
   LLVMBasicBlockRef BB = LLVMGetInsertBlock(Builder);
   LLVMValueRef Fn = LLVMGetBasicBlockParent(BB);
   return LLVMGetGlobalParent(Fn);
 }
 
+static ValueMap clone_params(LLVMValueRef Src, LLVMValueRef Dst);
+
+struct FunCloner {
+  LLVMValueRef Fun;
+
+  ValueMap VMap;
+  BasicBlockMap BBMap;
+
+  FunCloner(LLVMValueRef Src, LLVMValueRef Dst)
+    : Fun(Dst), VMap(clone_params(Src, Dst)) {}
+
   // Try to clone everything in the llvm::Value hierarchy.
-static LLVMValueRef clone_value(LLVMValueRef Src, LLVMBuilderRef Builder, ValueMap &VMap) {
+  LLVMValueRef CloneValue(LLVMValueRef Src, LLVMBuilderRef Builder) {
     const char *Name = LLVMGetValueName(Src);
 
     // First, the value may be constant.
     if (LLVMIsAConstant(Src)) {
       LLVMModuleRef M = get_module(Builder);
 
       // Maybe it is a symbol
       if (LLVMIsAGlobalValue(Src)) {
         // Try function
         LLVMValueRef Dst = LLVMGetNamedFunction(M, Name);
         if (Dst != nullptr)
           return Dst;
 
         // Try global variable
         Dst = LLVMGetNamedGlobal(M, Name);
         if (Dst != nullptr)
           return Dst;
 
         fprintf(stderr, "Could not find @%s\n", Name);
         exit(-1);
       }
 
       // Try literal
       LLVMContextRef Ctx = LLVMGetModuleContext(M);
       return clone_literal(Src, Ctx);
     }
 
     // Try undef
     if (LLVMIsUndef(Src)) {
       LLVMContextRef Ctx = LLVMGetModuleContext(get_module(Builder));
       LLVMTypeRef Ty = clone_type(LLVMTypeOf(Src), Ctx);
       return LLVMGetUndef(Ty);
     }
 
     // Check if this is something we already computed.
     {
       auto i = VMap.find(Src);
       if (i != VMap.end())
         return i->second;
     }
 
     // We tried everything, it must be an instruction
     // that hasn't been generated already.
     LLVMValueRef Dst = nullptr;
 
     LLVMOpcode Op = LLVMGetInstructionOpcode(Src);
     switch(Op) {
       case LLVMRet: {
         int OpCount = LLVMGetNumOperands(Src);
         if (OpCount == 0)
           Dst = LLVMBuildRetVoid(Builder);
         else
-        Dst = LLVMBuildRet(Builder, clone_value(LLVMGetOperand(Src, 0),
-                                                Builder, VMap));
+          Dst = LLVMBuildRet(Builder, CloneValue(LLVMGetOperand(Src, 0),
+                                                 Builder));
+        break;
+      }
+      case LLVMBr: {
+        LLVMBasicBlockRef SrcBB = LLVMValueAsBasicBlock(LLVMGetOperand(Src, 0));
+        Dst = LLVMBuildBr(Builder, DeclareBB(SrcBB));
         break;
       }
-    case LLVMBr:
       case LLVMSwitch:
       case LLVMIndirectBr:
       case LLVMInvoke:
+        break;
       case LLVMUnreachable:
+        Dst = LLVMBuildUnreachable(Builder);
         break;
       case LLVMAdd: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildAdd(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMSub: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildSub(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMMul: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildMul(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMUDiv: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildUDiv(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMSDiv: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildSDiv(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMURem: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildURem(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMSRem: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildSRem(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMShl: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildShl(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMLShr: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildLShr(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMAShr: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildAShr(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMAnd: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildAnd(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMOr: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildOr(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMXor: {
-      LLVMValueRef LHS = clone_value(LLVMGetOperand(Src, 0), Builder, VMap);
-      LLVMValueRef RHS = clone_value(LLVMGetOperand(Src, 1), Builder, VMap);
+        LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0), Builder);
+        LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1), Builder);
         Dst = LLVMBuildXor(Builder, LHS, RHS, Name);
         break;
       }
       case LLVMAlloca: {
+        // TODO: Add a binding for AllocaInst::getAllocatedType
         LLVMTypeRef Ty = LLVMGetElementType(LLVMTypeOf(Src));
         Dst = LLVMBuildAlloca(Builder, Ty, Name);
         break;
       }
       case LLVMCall: {
         int ArgCount = LLVMGetNumOperands(Src) - 1;
         SmallVector<LLVMValueRef, 8> Args;
         for (int i = 0; i < ArgCount; i++)
-        Args.push_back(clone_value(LLVMGetOperand(Src, i), Builder, VMap));
-      LLVMValueRef Fn = clone_value(LLVMGetOperand(Src, ArgCount), Builder, VMap);
+          Args.push_back(CloneValue(LLVMGetOperand(Src, i), Builder));
+        LLVMValueRef Fn = CloneValue(LLVMGetOperand(Src, ArgCount), Builder);
         Dst = LLVMBuildCall(Builder, Fn, Args.data(), ArgCount, Name);
         break;
       }
       default:
         break;
     }
 
     if (Dst == nullptr) {
       fprintf(stderr, "%d is not a supported opcode\n", Op);
       exit(-1);
     }
 
     return VMap[Src] = Dst;
   }
 
-static LLVMBasicBlockRef clone_bb(LLVMBasicBlockRef Src, LLVMValueRef Dst, ValueMap &VMap) {
-  LLVMBasicBlockRef BB = LLVMAppendBasicBlock(Dst, "");
+  LLVMBasicBlockRef DeclareBB(LLVMBasicBlockRef Src) {
+    // Check if this is something we already computed.
+    {
+      auto i = BBMap.find(Src);
+      if (i != BBMap.end()) {
+        return i->second;
+      }
+    }
+
+    const char *Name = LLVMGetBasicBlockName(Src);
+
+    LLVMValueRef V = LLVMBasicBlockAsValue(Src);
+    if (!LLVMValueIsBasicBlock(V) || LLVMValueAsBasicBlock(V) != Src) {
+      fprintf(stderr, "Basic block is not a basic block...\n");
+      exit(-1);
+    }
+
+    const char *VName = LLVMGetValueName(V);
+    if (Name != VName) {
+      fprintf(stderr, "Basic block name do not match: %s and %s\n", Name, VName);
+      exit(-1);
+    }
+
+    LLVMBasicBlockRef BB = LLVMAppendBasicBlock(Fun, Name);
+    return BBMap[Src] = BB;
+  }
+
+  LLVMBasicBlockRef CloneBB(LLVMBasicBlockRef Src) {
+    LLVMBasicBlockRef BB = DeclareBB(Src);
+
+    // Make sure ordering is correct.
+    LLVMBasicBlockRef Prev = LLVMGetPreviousBasicBlock(Src);
+    if (Prev) {
+      LLVMMoveBasicBlockAfter(BB, DeclareBB(Prev));
+    }
 
     LLVMValueRef First = LLVMGetFirstInstruction(Src);
     LLVMValueRef Last = LLVMGetLastInstruction(Src);
 
     if (First == nullptr) {
       if (Last != nullptr) {
         fprintf(stderr, "Has no first instruction, but last one\n");
         exit(-1);
       }
 
       return BB;
     }
 
-  LLVMContextRef Ctx = LLVMGetModuleContext(LLVMGetGlobalParent(Dst));
+    LLVMContextRef Ctx = LLVMGetModuleContext(LLVMGetGlobalParent(Fun));
     LLVMBuilderRef Builder = LLVMCreateBuilderInContext(Ctx);
     LLVMPositionBuilderAtEnd(Builder, BB);
 
     LLVMValueRef Cur = First;
     LLVMValueRef Next = nullptr;
     while(true) {
-    clone_value(Cur, Builder, VMap);
+      CloneValue(Cur, Builder);
       Next = LLVMGetNextInstruction(Cur);
       if (Next == nullptr) {
         if (Cur != Last) {
           fprintf(stderr, "Final instruction does not match Last\n");
           exit(-1);
         }
 
         break;
       }
 
       LLVMValueRef Prev = LLVMGetPreviousInstruction(Next);
       if (Prev != Cur) {
         fprintf(stderr, "Next.Previous instruction is not Current\n");
         exit(-1);
       }
 
       Cur = Next;
     }
 
     LLVMDisposeBuilder(Builder);
     return BB;
   }
 
-static void clone_bbs(LLVMValueRef Src, LLVMValueRef Dst, ValueMap &VMap) {
+  void CloneBBs(LLVMValueRef Src) {
     unsigned Count = LLVMCountBasicBlocks(Src);
     if (Count == 0)
       return;
 
     LLVMBasicBlockRef First = LLVMGetFirstBasicBlock(Src);
     LLVMBasicBlockRef Last = LLVMGetLastBasicBlock(Src);
 
     LLVMBasicBlockRef Cur = First;
     LLVMBasicBlockRef Next = nullptr;
     while(true) {
-    clone_bb(Cur, Dst, VMap);
+      CloneBB(Cur);
       Count--;
       Next = LLVMGetNextBasicBlock(Cur);
       if (Next == nullptr) {
         if (Cur != Last) {
           fprintf(stderr, "Final basic block does not match Last\n");
           exit(-1);
         }
 
         break;
       }
 
       LLVMBasicBlockRef Prev = LLVMGetPreviousBasicBlock(Next);
       if (Prev != Cur) {
         fprintf(stderr, "Next.Previous basic bloc is not Current\n");
         exit(-1);
       }
 
       Cur = Next;
     }
 
     if (Count != 0) {
       fprintf(stderr, "Basic block count does not match iterration\n");
       exit(-1);
     }
   }
+};
 
 static ValueMap clone_params(LLVMValueRef Src, LLVMValueRef Dst) {
   unsigned Count = LLVMCountParams(Src);
   if (Count != LLVMCountParams(Dst)) {
     fprintf(stderr, "Parameter count mismatch\n");
     exit(-1);
   }
 
static LLVMValueRef clone_function(LLVMValueRef Src, LLVMModuleRef Dst) {
   if (Fun != nullptr)
     return Fun;
 
   LLVMTypeRef SrcTy = LLVMTypeOf(Src);
   LLVMTypeRef DstTy = clone_type(SrcTy, LLVMGetModuleContext(Dst));
   LLVMTypeRef FunTy = LLVMGetElementType(DstTy);
 
   Fun = LLVMAddFunction(Dst, Name, FunTy);
-
-  ValueMap VMap = clone_params(Src, Fun);
-  clone_bbs(Src, Fun, VMap);
+  FunCloner FC(Src, Fun);
+  FC.CloneBBs(Src);
 
   return Fun;
 }
 
 static void clone_functions(LLVMModuleRef Src, LLVMModuleRef Dst) {
   LLVMValueRef Begin = LLVMGetFirstFunction(Src);
   LLVMValueRef End = LLVMGetLastFunction(Src);