1 //===-- echo.cpp - tool for testing libLLVM and llvm-c API ----------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the --echo command in llvm-c-test.
11 //
12 // This command uses the C API to read a module and output an exact copy of it
13 // as output. It is used to check that the resulting module matches the input
14 // to validate that the C API can read and write modules properly.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm-c-test.h"
19 #include "llvm-c/Target.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/Support/ErrorHandling.h"
22 
23 #include <stdio.h>
24 #include <stdlib.h>
25 
26 using namespace llvm;
27 
28 // Provide DenseMapInfo for C API opaque types.
29 template<typename T>
30 struct CAPIDenseMap {};
31 
32 // The default DenseMapInfo require to know about pointer alignement.
33 // Because the C API uses opaques pointer types, their alignement is unknown.
34 // As a result, we need to roll out our own implementation.
35 template<typename T>
36 struct CAPIDenseMap<T*> {
37   struct CAPIDenseMapInfo {
38     static inline T* getEmptyKey() {
39       uintptr_t Val = static_cast<uintptr_t>(-1);
40       return reinterpret_cast<T*>(Val);
41     }
42     static inline T* getTombstoneKey() {
43       uintptr_t Val = static_cast<uintptr_t>(-2);
44       return reinterpret_cast<T*>(Val);
45     }
46     static unsigned getHashValue(const T *PtrVal) {
47       return hash_value(PtrVal);
48     }
49     static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
50   };
51 
52   typedef DenseMap<T*, T*, CAPIDenseMapInfo> Map;
53 };
54 
55 typedef CAPIDenseMap<LLVMValueRef>::Map ValueMap;
56 typedef CAPIDenseMap<LLVMBasicBlockRef>::Map BasicBlockMap;
57 
58 struct TypeCloner {
59   LLVMModuleRef M;
60   LLVMContextRef Ctx;
61 
62   TypeCloner(LLVMModuleRef M): M(M), Ctx(LLVMGetModuleContext(M)) {}
63 
64   LLVMTypeRef Clone(LLVMValueRef Src) {
65     return Clone(LLVMTypeOf(Src));
66   }
67 
68   LLVMTypeRef Clone(LLVMTypeRef Src) {
69     LLVMTypeKind Kind = LLVMGetTypeKind(Src);
70     switch (Kind) {
71       case LLVMVoidTypeKind:
72         return LLVMVoidTypeInContext(Ctx);
73       case LLVMHalfTypeKind:
74         return LLVMHalfTypeInContext(Ctx);
75       case LLVMFloatTypeKind:
76         return LLVMFloatTypeInContext(Ctx);
77       case LLVMDoubleTypeKind:
78         return LLVMDoubleTypeInContext(Ctx);
79       case LLVMX86_FP80TypeKind:
80         return LLVMX86FP80TypeInContext(Ctx);
81       case LLVMFP128TypeKind:
82         return LLVMFP128TypeInContext(Ctx);
83       case LLVMPPC_FP128TypeKind:
84         return LLVMPPCFP128TypeInContext(Ctx);
85       case LLVMLabelTypeKind:
86         return LLVMLabelTypeInContext(Ctx);
87       case LLVMIntegerTypeKind:
88         return LLVMIntTypeInContext(Ctx, LLVMGetIntTypeWidth(Src));
89       case LLVMFunctionTypeKind: {
90         unsigned ParamCount = LLVMCountParamTypes(Src);
91         LLVMTypeRef* Params = nullptr;
92         if (ParamCount > 0) {
93           Params = static_cast<LLVMTypeRef*>(
94               safe_malloc(ParamCount * sizeof(LLVMTypeRef)));
95           LLVMGetParamTypes(Src, Params);
96           for (unsigned i = 0; i < ParamCount; i++)
97             Params[i] = Clone(Params[i]);
98         }
99 
100         LLVMTypeRef FunTy = LLVMFunctionType(Clone(LLVMGetReturnType(Src)),
101                                              Params, ParamCount,
102                                              LLVMIsFunctionVarArg(Src));
103         if (ParamCount > 0)
104           free(Params);
105         return FunTy;
106       }
107       case LLVMStructTypeKind: {
108         LLVMTypeRef S = nullptr;
109         const char *Name = LLVMGetStructName(Src);
110         if (Name) {
111           S = LLVMGetTypeByName(M, Name);
112           if (S)
113             return S;
114           S = LLVMStructCreateNamed(Ctx, Name);
115           if (LLVMIsOpaqueStruct(Src))
116             return S;
117         }
118 
119         unsigned EltCount = LLVMCountStructElementTypes(Src);
120         SmallVector<LLVMTypeRef, 8> Elts;
121         for (unsigned i = 0; i < EltCount; i++)
122           Elts.push_back(Clone(LLVMStructGetTypeAtIndex(Src, i)));
123         if (Name)
124           LLVMStructSetBody(S, Elts.data(), EltCount, LLVMIsPackedStruct(Src));
125         else
126           S = LLVMStructTypeInContext(Ctx, Elts.data(), EltCount,
127                                       LLVMIsPackedStruct(Src));
128         return S;
129       }
130       case LLVMArrayTypeKind:
131         return LLVMArrayType(
132           Clone(LLVMGetElementType(Src)),
133           LLVMGetArrayLength(Src)
134         );
135       case LLVMPointerTypeKind:
136         return LLVMPointerType(
137           Clone(LLVMGetElementType(Src)),
138           LLVMGetPointerAddressSpace(Src)
139         );
140       case LLVMVectorTypeKind:
141         return LLVMVectorType(
142           Clone(LLVMGetElementType(Src)),
143           LLVMGetVectorSize(Src)
144         );
145       case LLVMMetadataTypeKind:
146         return LLVMMetadataTypeInContext(Ctx);
147       case LLVMX86_MMXTypeKind:
148         return LLVMX86MMXTypeInContext(Ctx);
149       case LLVMTokenTypeKind:
150         return LLVMTokenTypeInContext(Ctx);
151     }
152 
153     fprintf(stderr, "%d is not a supported typekind\n", Kind);
154     exit(-1);
155   }
156 };
157 
158 static ValueMap clone_params(LLVMValueRef Src, LLVMValueRef Dst) {
159   unsigned Count = LLVMCountParams(Src);
160   if (Count != LLVMCountParams(Dst))
161     report_fatal_error("Parameter count mismatch");
162 
163   ValueMap VMap;
164   if (Count == 0)
165     return VMap;
166 
167   LLVMValueRef SrcFirst = LLVMGetFirstParam(Src);
168   LLVMValueRef DstFirst = LLVMGetFirstParam(Dst);
169   LLVMValueRef SrcLast = LLVMGetLastParam(Src);
170   LLVMValueRef DstLast = LLVMGetLastParam(Dst);
171 
172   LLVMValueRef SrcCur = SrcFirst;
173   LLVMValueRef DstCur = DstFirst;
174   LLVMValueRef SrcNext = nullptr;
175   LLVMValueRef DstNext = nullptr;
176   while (true) {
177     size_t NameLen;
178     const char *Name = LLVMGetValueName2(SrcCur, &NameLen);
179     LLVMSetValueName2(DstCur, Name, NameLen);
180 
181     VMap[SrcCur] = DstCur;
182 
183     Count--;
184     SrcNext = LLVMGetNextParam(SrcCur);
185     DstNext = LLVMGetNextParam(DstCur);
186     if (SrcNext == nullptr && DstNext == nullptr) {
187       if (SrcCur != SrcLast)
188         report_fatal_error("SrcLast param does not match End");
189       if (DstCur != DstLast)
190         report_fatal_error("DstLast param does not match End");
191       break;
192     }
193 
194     if (SrcNext == nullptr)
195       report_fatal_error("SrcNext was unexpectedly null");
196     if (DstNext == nullptr)
197       report_fatal_error("DstNext was unexpectedly null");
198 
199     LLVMValueRef SrcPrev = LLVMGetPreviousParam(SrcNext);
200     if (SrcPrev != SrcCur)
201       report_fatal_error("SrcNext.Previous param is not Current");
202 
203     LLVMValueRef DstPrev = LLVMGetPreviousParam(DstNext);
204     if (DstPrev != DstCur)
205       report_fatal_error("DstNext.Previous param is not Current");
206 
207     SrcCur = SrcNext;
208     DstCur = DstNext;
209   }
210 
211   if (Count != 0)
212     report_fatal_error("Parameter count does not match iteration");
213 
214   return VMap;
215 }
216 
217 static void check_value_kind(LLVMValueRef V, LLVMValueKind K) {
218   if (LLVMGetValueKind(V) != K)
219     report_fatal_error("LLVMGetValueKind returned incorrect type");
220 }
221 
222 static LLVMValueRef clone_constant_impl(LLVMValueRef Cst, LLVMModuleRef M);
223 
224 static LLVMValueRef clone_constant(LLVMValueRef Cst, LLVMModuleRef M) {
225   LLVMValueRef Ret = clone_constant_impl(Cst, M);
226   check_value_kind(Ret, LLVMGetValueKind(Cst));
227   return Ret;
228 }
229 
230 static LLVMValueRef clone_constant_impl(LLVMValueRef Cst, LLVMModuleRef M) {
231   if (!LLVMIsAConstant(Cst))
232     report_fatal_error("Expected a constant");
233 
234   // Maybe it is a symbol
235   if (LLVMIsAGlobalValue(Cst)) {
236     size_t NameLen;
237     const char *Name = LLVMGetValueName2(Cst, &NameLen);
238 
239     // Try function
240     if (LLVMIsAFunction(Cst)) {
241       check_value_kind(Cst, LLVMFunctionValueKind);
242       LLVMValueRef Dst = LLVMGetNamedFunction(M, Name);
243       if (Dst)
244         return Dst;
245       report_fatal_error("Could not find function");
246     }
247 
248     // Try global variable
249     if (LLVMIsAGlobalVariable(Cst)) {
250       check_value_kind(Cst, LLVMGlobalVariableValueKind);
251       LLVMValueRef Dst = LLVMGetNamedGlobal(M, Name);
252       if (Dst)
253         return Dst;
254       report_fatal_error("Could not find variable");
255     }
256 
257     // Try global alias
258     if (LLVMIsAGlobalAlias(Cst)) {
259       check_value_kind(Cst, LLVMGlobalAliasValueKind);
260       LLVMValueRef Dst = LLVMGetNamedGlobalAlias(M, Name, NameLen);
261       if (Dst)
262         return Dst;
263       report_fatal_error("Could not find alias");
264     }
265 
266     fprintf(stderr, "Could not find @%s\n", Name);
267     exit(-1);
268   }
269 
270   // Try integer literal
271   if (LLVMIsAConstantInt(Cst)) {
272     check_value_kind(Cst, LLVMConstantIntValueKind);
273     return LLVMConstInt(TypeCloner(M).Clone(Cst),
274                         LLVMConstIntGetZExtValue(Cst), false);
275   }
276 
277   // Try zeroinitializer
278   if (LLVMIsAConstantAggregateZero(Cst)) {
279     check_value_kind(Cst, LLVMConstantAggregateZeroValueKind);
280     return LLVMConstNull(TypeCloner(M).Clone(Cst));
281   }
282 
283   // Try constant array
284   if (LLVMIsAConstantArray(Cst)) {
285     check_value_kind(Cst, LLVMConstantArrayValueKind);
286     LLVMTypeRef Ty = TypeCloner(M).Clone(Cst);
287     unsigned EltCount = LLVMGetArrayLength(Ty);
288     SmallVector<LLVMValueRef, 8> Elts;
289     for (unsigned i = 0; i < EltCount; i++)
290       Elts.push_back(clone_constant(LLVMGetOperand(Cst, i), M));
291     return LLVMConstArray(LLVMGetElementType(Ty), Elts.data(), EltCount);
292   }
293 
294   // Try contant data array
295   if (LLVMIsAConstantDataArray(Cst)) {
296     check_value_kind(Cst, LLVMConstantDataArrayValueKind);
297     LLVMTypeRef Ty = TypeCloner(M).Clone(Cst);
298     unsigned EltCount = LLVMGetArrayLength(Ty);
299     SmallVector<LLVMValueRef, 8> Elts;
300     for (unsigned i = 0; i < EltCount; i++)
301       Elts.push_back(clone_constant(LLVMGetElementAsConstant(Cst, i), M));
302     return LLVMConstArray(LLVMGetElementType(Ty), Elts.data(), EltCount);
303   }
304 
305   // Try constant struct
306   if (LLVMIsAConstantStruct(Cst)) {
307     check_value_kind(Cst, LLVMConstantStructValueKind);
308     LLVMTypeRef Ty = TypeCloner(M).Clone(Cst);
309     unsigned EltCount = LLVMCountStructElementTypes(Ty);
310     SmallVector<LLVMValueRef, 8> Elts;
311     for (unsigned i = 0; i < EltCount; i++)
312       Elts.push_back(clone_constant(LLVMGetOperand(Cst, i), M));
313     if (LLVMGetStructName(Ty))
314       return LLVMConstNamedStruct(Ty, Elts.data(), EltCount);
315     return LLVMConstStructInContext(LLVMGetModuleContext(M), Elts.data(),
316                                     EltCount, LLVMIsPackedStruct(Ty));
317   }
318 
319   // Try undef
320   if (LLVMIsUndef(Cst)) {
321     check_value_kind(Cst, LLVMUndefValueValueKind);
322     return LLVMGetUndef(TypeCloner(M).Clone(Cst));
323   }
324 
325   // Try null
326   if (LLVMIsNull(Cst)) {
327     check_value_kind(Cst, LLVMConstantTokenNoneValueKind);
328     LLVMTypeRef Ty = TypeCloner(M).Clone(Cst);
329     return LLVMConstNull(Ty);
330   }
331 
332   // Try float literal
333   if (LLVMIsAConstantFP(Cst)) {
334     check_value_kind(Cst, LLVMConstantFPValueKind);
335     report_fatal_error("ConstantFP is not supported");
336   }
337 
338   // This kind of constant is not supported
339   if (!LLVMIsAConstantExpr(Cst))
340     report_fatal_error("Expected a constant expression");
341 
342   // At this point, it must be a constant expression
343   check_value_kind(Cst, LLVMConstantExprValueKind);
344 
345   LLVMOpcode Op = LLVMGetConstOpcode(Cst);
346   switch(Op) {
347     case LLVMBitCast:
348       return LLVMConstBitCast(clone_constant(LLVMGetOperand(Cst, 0), M),
349                               TypeCloner(M).Clone(Cst));
350     default:
351       fprintf(stderr, "%d is not a supported opcode\n", Op);
352       exit(-1);
353   }
354 }
355 
356 struct FunCloner {
357   LLVMValueRef Fun;
358   LLVMModuleRef M;
359 
360   ValueMap VMap;
361   BasicBlockMap BBMap;
362 
363   FunCloner(LLVMValueRef Src, LLVMValueRef Dst): Fun(Dst),
364     M(LLVMGetGlobalParent(Fun)), VMap(clone_params(Src, Dst)) {}
365 
366   LLVMTypeRef CloneType(LLVMTypeRef Src) {
367     return TypeCloner(M).Clone(Src);
368   }
369 
370   LLVMTypeRef CloneType(LLVMValueRef Src) {
371     return TypeCloner(M).Clone(Src);
372   }
373 
374   // Try to clone everything in the llvm::Value hierarchy.
375   LLVMValueRef CloneValue(LLVMValueRef Src) {
376     // First, the value may be constant.
377     if (LLVMIsAConstant(Src))
378       return clone_constant(Src, M);
379 
380     // Function argument should always be in the map already.
381     auto i = VMap.find(Src);
382     if (i != VMap.end())
383       return i->second;
384 
385     if (!LLVMIsAInstruction(Src))
386       report_fatal_error("Expected an instruction");
387 
388     auto Ctx = LLVMGetModuleContext(M);
389     auto Builder = LLVMCreateBuilderInContext(Ctx);
390     auto BB = DeclareBB(LLVMGetInstructionParent(Src));
391     LLVMPositionBuilderAtEnd(Builder, BB);
392     auto Dst = CloneInstruction(Src, Builder);
393     LLVMDisposeBuilder(Builder);
394     return Dst;
395   }
396 
397   void CloneAttrs(LLVMValueRef Src, LLVMValueRef Dst) {
398     auto Ctx = LLVMGetModuleContext(M);
399     int ArgCount = LLVMGetNumArgOperands(Src);
400     for (int i = LLVMAttributeReturnIndex; i <= ArgCount; i++) {
401       for (unsigned k = 0, e = LLVMGetLastEnumAttributeKind(); k < e; ++k) {
402         if (auto SrcA = LLVMGetCallSiteEnumAttribute(Src, i, k)) {
403           auto Val = LLVMGetEnumAttributeValue(SrcA);
404           auto A = LLVMCreateEnumAttribute(Ctx, k, Val);
405           LLVMAddCallSiteAttribute(Dst, i, A);
406         }
407       }
408     }
409   }
410 
411   LLVMValueRef CloneInstruction(LLVMValueRef Src, LLVMBuilderRef Builder) {
412     check_value_kind(Src, LLVMInstructionValueKind);
413     if (!LLVMIsAInstruction(Src))
414       report_fatal_error("Expected an instruction");
415 
416     size_t NameLen;
417     const char *Name = LLVMGetValueName2(Src, &NameLen);
418 
419     // Check if this is something we already computed.
420     {
421       auto i = VMap.find(Src);
422       if (i != VMap.end()) {
423         // If we have a hit, it means we already generated the instruction
424         // as a dependancy to somethign else. We need to make sure
425         // it is ordered properly.
426         auto I = i->second;
427         LLVMInstructionRemoveFromParent(I);
428         LLVMInsertIntoBuilderWithName(Builder, I, Name);
429         return I;
430       }
431     }
432 
433     // We tried everything, it must be an instruction
434     // that hasn't been generated already.
435     LLVMValueRef Dst = nullptr;
436 
437     LLVMOpcode Op = LLVMGetInstructionOpcode(Src);
438     switch(Op) {
439       case LLVMRet: {
440         int OpCount = LLVMGetNumOperands(Src);
441         if (OpCount == 0)
442           Dst = LLVMBuildRetVoid(Builder);
443         else
444           Dst = LLVMBuildRet(Builder, CloneValue(LLVMGetOperand(Src, 0)));
445         break;
446       }
447       case LLVMBr: {
448         if (!LLVMIsConditional(Src)) {
449           LLVMValueRef SrcOp = LLVMGetOperand(Src, 0);
450           LLVMBasicBlockRef SrcBB = LLVMValueAsBasicBlock(SrcOp);
451           Dst = LLVMBuildBr(Builder, DeclareBB(SrcBB));
452           break;
453         }
454 
455         LLVMValueRef Cond = LLVMGetCondition(Src);
456         LLVMValueRef Else = LLVMGetOperand(Src, 1);
457         LLVMBasicBlockRef ElseBB = DeclareBB(LLVMValueAsBasicBlock(Else));
458         LLVMValueRef Then = LLVMGetOperand(Src, 2);
459         LLVMBasicBlockRef ThenBB = DeclareBB(LLVMValueAsBasicBlock(Then));
460         Dst = LLVMBuildCondBr(Builder, CloneValue(Cond), ThenBB, ElseBB);
461         break;
462       }
463       case LLVMSwitch:
464       case LLVMIndirectBr:
465         break;
466       case LLVMInvoke: {
467         SmallVector<LLVMValueRef, 8> Args;
468         int ArgCount = LLVMGetNumArgOperands(Src);
469         for (int i = 0; i < ArgCount; i++)
470           Args.push_back(CloneValue(LLVMGetOperand(Src, i)));
471         LLVMValueRef Fn = CloneValue(LLVMGetCalledValue(Src));
472         LLVMBasicBlockRef Then = DeclareBB(LLVMGetNormalDest(Src));
473         LLVMBasicBlockRef Unwind = DeclareBB(LLVMGetUnwindDest(Src));
474         Dst = LLVMBuildInvoke(Builder, Fn, Args.data(), ArgCount,
475                               Then, Unwind, Name);
476         CloneAttrs(Src, Dst);
477         break;
478       }
479       case LLVMUnreachable:
480         Dst = LLVMBuildUnreachable(Builder);
481         break;
482       case LLVMAdd: {
483         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
484         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
485         Dst = LLVMBuildAdd(Builder, LHS, RHS, Name);
486         break;
487       }
488       case LLVMSub: {
489         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
490         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
491         Dst = LLVMBuildSub(Builder, LHS, RHS, Name);
492         break;
493       }
494       case LLVMMul: {
495         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
496         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
497         Dst = LLVMBuildMul(Builder, LHS, RHS, Name);
498         break;
499       }
500       case LLVMUDiv: {
501         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
502         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
503         Dst = LLVMBuildUDiv(Builder, LHS, RHS, Name);
504         break;
505       }
506       case LLVMSDiv: {
507         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
508         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
509         Dst = LLVMBuildSDiv(Builder, LHS, RHS, Name);
510         break;
511       }
512       case LLVMURem: {
513         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
514         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
515         Dst = LLVMBuildURem(Builder, LHS, RHS, Name);
516         break;
517       }
518       case LLVMSRem: {
519         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
520         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
521         Dst = LLVMBuildSRem(Builder, LHS, RHS, Name);
522         break;
523       }
524       case LLVMShl: {
525         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
526         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
527         Dst = LLVMBuildShl(Builder, LHS, RHS, Name);
528         break;
529       }
530       case LLVMLShr: {
531         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
532         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
533         Dst = LLVMBuildLShr(Builder, LHS, RHS, Name);
534         break;
535       }
536       case LLVMAShr: {
537         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
538         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
539         Dst = LLVMBuildAShr(Builder, LHS, RHS, Name);
540         break;
541       }
542       case LLVMAnd: {
543         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
544         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
545         Dst = LLVMBuildAnd(Builder, LHS, RHS, Name);
546         break;
547       }
548       case LLVMOr: {
549         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
550         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
551         Dst = LLVMBuildOr(Builder, LHS, RHS, Name);
552         break;
553       }
554       case LLVMXor: {
555         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
556         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
557         Dst = LLVMBuildXor(Builder, LHS, RHS, Name);
558         break;
559       }
560       case LLVMAlloca: {
561         LLVMTypeRef Ty = CloneType(LLVMGetAllocatedType(Src));
562         Dst = LLVMBuildAlloca(Builder, Ty, Name);
563         break;
564       }
565       case LLVMLoad: {
566         LLVMValueRef Ptr = CloneValue(LLVMGetOperand(Src, 0));
567         Dst = LLVMBuildLoad(Builder, Ptr, Name);
568         LLVMSetAlignment(Dst, LLVMGetAlignment(Src));
569         break;
570       }
571       case LLVMStore: {
572         LLVMValueRef Val = CloneValue(LLVMGetOperand(Src, 0));
573         LLVMValueRef Ptr = CloneValue(LLVMGetOperand(Src, 1));
574         Dst = LLVMBuildStore(Builder, Val, Ptr);
575         LLVMSetAlignment(Dst, LLVMGetAlignment(Src));
576         break;
577       }
578       case LLVMGetElementPtr: {
579         LLVMValueRef Ptr = CloneValue(LLVMGetOperand(Src, 0));
580         SmallVector<LLVMValueRef, 8> Idx;
581         int NumIdx = LLVMGetNumIndices(Src);
582         for (int i = 1; i <= NumIdx; i++)
583           Idx.push_back(CloneValue(LLVMGetOperand(Src, i)));
584         if (LLVMIsInBounds(Src))
585           Dst = LLVMBuildInBoundsGEP(Builder, Ptr, Idx.data(), NumIdx, Name);
586         else
587           Dst = LLVMBuildGEP(Builder, Ptr, Idx.data(), NumIdx, Name);
588         break;
589       }
590       case LLVMAtomicCmpXchg: {
591         LLVMValueRef Ptr = CloneValue(LLVMGetOperand(Src, 0));
592         LLVMValueRef Cmp = CloneValue(LLVMGetOperand(Src, 1));
593         LLVMValueRef New = CloneValue(LLVMGetOperand(Src, 2));
594         LLVMAtomicOrdering Succ = LLVMGetCmpXchgSuccessOrdering(Src);
595         LLVMAtomicOrdering Fail = LLVMGetCmpXchgFailureOrdering(Src);
596         LLVMBool SingleThread = LLVMIsAtomicSingleThread(Src);
597 
598         Dst = LLVMBuildAtomicCmpXchg(Builder, Ptr, Cmp, New, Succ, Fail,
599                                      SingleThread);
600       } break;
601       case LLVMBitCast: {
602         LLVMValueRef V = CloneValue(LLVMGetOperand(Src, 0));
603         Dst = LLVMBuildBitCast(Builder, V, CloneType(Src), Name);
604         break;
605       }
606       case LLVMICmp: {
607         LLVMIntPredicate Pred = LLVMGetICmpPredicate(Src);
608         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
609         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
610         Dst = LLVMBuildICmp(Builder, Pred, LHS, RHS, Name);
611         break;
612       }
613       case LLVMPHI: {
614         // We need to aggressively set things here because of loops.
615         VMap[Src] = Dst = LLVMBuildPhi(Builder, CloneType(Src), Name);
616 
617         SmallVector<LLVMValueRef, 8> Values;
618         SmallVector<LLVMBasicBlockRef, 8> Blocks;
619 
620         unsigned IncomingCount = LLVMCountIncoming(Src);
621         for (unsigned i = 0; i < IncomingCount; ++i) {
622           Blocks.push_back(DeclareBB(LLVMGetIncomingBlock(Src, i)));
623           Values.push_back(CloneValue(LLVMGetIncomingValue(Src, i)));
624         }
625 
626         LLVMAddIncoming(Dst, Values.data(), Blocks.data(), IncomingCount);
627         return Dst;
628       }
629       case LLVMCall: {
630         SmallVector<LLVMValueRef, 8> Args;
631         int ArgCount = LLVMGetNumArgOperands(Src);
632         for (int i = 0; i < ArgCount; i++)
633           Args.push_back(CloneValue(LLVMGetOperand(Src, i)));
634         LLVMValueRef Fn = CloneValue(LLVMGetCalledValue(Src));
635         Dst = LLVMBuildCall(Builder, Fn, Args.data(), ArgCount, Name);
636         LLVMSetTailCall(Dst, LLVMIsTailCall(Src));
637         CloneAttrs(Src, Dst);
638         break;
639       }
640       case LLVMResume: {
641         Dst = LLVMBuildResume(Builder, CloneValue(LLVMGetOperand(Src, 0)));
642         break;
643       }
644       case LLVMLandingPad: {
645         // The landing pad API is a bit screwed up for historical reasons.
646         Dst = LLVMBuildLandingPad(Builder, CloneType(Src), nullptr, 0, Name);
647         unsigned NumClauses = LLVMGetNumClauses(Src);
648         for (unsigned i = 0; i < NumClauses; ++i)
649           LLVMAddClause(Dst, CloneValue(LLVMGetClause(Src, i)));
650         LLVMSetCleanup(Dst, LLVMIsCleanup(Src));
651         break;
652       }
653       case LLVMCleanupRet: {
654         LLVMValueRef CatchPad = CloneValue(LLVMGetOperand(Src, 0));
655         LLVMBasicBlockRef Unwind = nullptr;
656         if (LLVMBasicBlockRef UDest = LLVMGetUnwindDest(Src))
657           Unwind = DeclareBB(UDest);
658         Dst = LLVMBuildCleanupRet(Builder, CatchPad, Unwind);
659         break;
660       }
661       case LLVMCatchRet: {
662         LLVMValueRef CatchPad = CloneValue(LLVMGetOperand(Src, 0));
663         LLVMBasicBlockRef SuccBB = DeclareBB(LLVMGetSuccessor(Src, 0));
664         Dst = LLVMBuildCatchRet(Builder, CatchPad, SuccBB);
665         break;
666       }
667       case LLVMCatchPad: {
668         LLVMValueRef ParentPad = CloneValue(LLVMGetParentCatchSwitch(Src));
669         SmallVector<LLVMValueRef, 8> Args;
670         int ArgCount = LLVMGetNumArgOperands(Src);
671         for (int i = 0; i < ArgCount; i++)
672           Args.push_back(CloneValue(LLVMGetOperand(Src, i)));
673         Dst = LLVMBuildCatchPad(Builder, ParentPad,
674                                 Args.data(), ArgCount, Name);
675         break;
676       }
677       case LLVMCleanupPad: {
678         LLVMValueRef ParentPad = CloneValue(LLVMGetOperand(Src, 0));
679         SmallVector<LLVMValueRef, 8> Args;
680         int ArgCount = LLVMGetNumArgOperands(Src);
681         for (int i = 0; i < ArgCount; i++)
682           Args.push_back(CloneValue(LLVMGetArgOperand(Src, i)));
683         Dst = LLVMBuildCleanupPad(Builder, ParentPad,
684                                   Args.data(), ArgCount, Name);
685         break;
686       }
687       case LLVMCatchSwitch: {
688         LLVMValueRef ParentPad = CloneValue(LLVMGetOperand(Src, 0));
689         LLVMBasicBlockRef UnwindBB = nullptr;
690         if (LLVMBasicBlockRef UDest = LLVMGetUnwindDest(Src)) {
691           UnwindBB = DeclareBB(UDest);
692         }
693         unsigned NumHandlers = LLVMGetNumHandlers(Src);
694         Dst = LLVMBuildCatchSwitch(Builder, ParentPad, UnwindBB, NumHandlers, Name);
695         if (NumHandlers > 0) {
696           LLVMBasicBlockRef *Handlers = static_cast<LLVMBasicBlockRef*>(
697                        safe_malloc(NumHandlers * sizeof(LLVMBasicBlockRef)));
698           LLVMGetHandlers(Src, Handlers);
699           for (unsigned i = 0; i < NumHandlers; i++)
700             LLVMAddHandler(Dst, DeclareBB(Handlers[i]));
701           free(Handlers);
702         }
703         break;
704       }
705       case LLVMExtractValue: {
706         LLVMValueRef Agg = CloneValue(LLVMGetOperand(Src, 0));
707         if (LLVMGetNumIndices(Src) != 1)
708           report_fatal_error("Expected only one indice");
709         auto I = LLVMGetIndices(Src)[0];
710         Dst = LLVMBuildExtractValue(Builder, Agg, I, Name);
711         break;
712       }
713       case LLVMInsertValue: {
714         LLVMValueRef Agg = CloneValue(LLVMGetOperand(Src, 0));
715         LLVMValueRef V = CloneValue(LLVMGetOperand(Src, 1));
716         if (LLVMGetNumIndices(Src) != 1)
717           report_fatal_error("Expected only one indice");
718         auto I = LLVMGetIndices(Src)[0];
719         Dst = LLVMBuildInsertValue(Builder, Agg, V, I, Name);
720         break;
721       }
722       default:
723         break;
724     }
725 
726     if (Dst == nullptr) {
727       fprintf(stderr, "%d is not a supported opcode\n", Op);
728       exit(-1);
729     }
730 
731     check_value_kind(Dst, LLVMInstructionValueKind);
732     return VMap[Src] = Dst;
733   }
734 
735   LLVMBasicBlockRef DeclareBB(LLVMBasicBlockRef Src) {
736     // Check if this is something we already computed.
737     {
738       auto i = BBMap.find(Src);
739       if (i != BBMap.end()) {
740         return i->second;
741       }
742     }
743 
744     LLVMValueRef V = LLVMBasicBlockAsValue(Src);
745     if (!LLVMValueIsBasicBlock(V) || LLVMValueAsBasicBlock(V) != Src)
746       report_fatal_error("Basic block is not a basic block");
747 
748     const char *Name = LLVMGetBasicBlockName(Src);
749     size_t NameLen;
750     const char *VName = LLVMGetValueName2(V, &NameLen);
751     if (Name != VName)
752       report_fatal_error("Basic block name mismatch");
753 
754     LLVMBasicBlockRef BB = LLVMAppendBasicBlock(Fun, Name);
755     return BBMap[Src] = BB;
756   }
757 
758   LLVMBasicBlockRef CloneBB(LLVMBasicBlockRef Src) {
759     LLVMBasicBlockRef BB = DeclareBB(Src);
760 
761     // Make sure ordering is correct.
762     LLVMBasicBlockRef Prev = LLVMGetPreviousBasicBlock(Src);
763     if (Prev)
764       LLVMMoveBasicBlockAfter(BB, DeclareBB(Prev));
765 
766     LLVMValueRef First = LLVMGetFirstInstruction(Src);
767     LLVMValueRef Last = LLVMGetLastInstruction(Src);
768 
769     if (First == nullptr) {
770       if (Last != nullptr)
771         report_fatal_error("Has no first instruction, but last one");
772       return BB;
773     }
774 
775     auto Ctx = LLVMGetModuleContext(M);
776     LLVMBuilderRef Builder = LLVMCreateBuilderInContext(Ctx);
777     LLVMPositionBuilderAtEnd(Builder, BB);
778 
779     LLVMValueRef Cur = First;
780     LLVMValueRef Next = nullptr;
781     while(true) {
782       CloneInstruction(Cur, Builder);
783       Next = LLVMGetNextInstruction(Cur);
784       if (Next == nullptr) {
785         if (Cur != Last)
786           report_fatal_error("Final instruction does not match Last");
787         break;
788       }
789 
790       LLVMValueRef Prev = LLVMGetPreviousInstruction(Next);
791       if (Prev != Cur)
792         report_fatal_error("Next.Previous instruction is not Current");
793 
794       Cur = Next;
795     }
796 
797     LLVMDisposeBuilder(Builder);
798     return BB;
799   }
800 
801   void CloneBBs(LLVMValueRef Src) {
802     unsigned Count = LLVMCountBasicBlocks(Src);
803     if (Count == 0)
804       return;
805 
806     LLVMBasicBlockRef First = LLVMGetFirstBasicBlock(Src);
807     LLVMBasicBlockRef Last = LLVMGetLastBasicBlock(Src);
808 
809     LLVMBasicBlockRef Cur = First;
810     LLVMBasicBlockRef Next = nullptr;
811     while(true) {
812       CloneBB(Cur);
813       Count--;
814       Next = LLVMGetNextBasicBlock(Cur);
815       if (Next == nullptr) {
816         if (Cur != Last)
817           report_fatal_error("Final basic block does not match Last");
818         break;
819       }
820 
821       LLVMBasicBlockRef Prev = LLVMGetPreviousBasicBlock(Next);
822       if (Prev != Cur)
823         report_fatal_error("Next.Previous basic bloc is not Current");
824 
825       Cur = Next;
826     }
827 
828     if (Count != 0)
829       report_fatal_error("Basic block count does not match iterration");
830   }
831 };
832 
833 static void declare_symbols(LLVMModuleRef Src, LLVMModuleRef M) {
834   auto Ctx = LLVMGetModuleContext(M);
835 
836   LLVMValueRef Begin = LLVMGetFirstGlobal(Src);
837   LLVMValueRef End = LLVMGetLastGlobal(Src);
838 
839   LLVMValueRef Cur = Begin;
840   LLVMValueRef Next = nullptr;
841   if (!Begin) {
842     if (End != nullptr)
843       report_fatal_error("Range has an end but no beginning");
844     goto FunDecl;
845   }
846 
847   while (true) {
848     size_t NameLen;
849     const char *Name = LLVMGetValueName2(Cur, &NameLen);
850     if (LLVMGetNamedGlobal(M, Name))
851       report_fatal_error("GlobalVariable already cloned");
852     LLVMAddGlobal(M, LLVMGetElementType(TypeCloner(M).Clone(Cur)), Name);
853 
854     Next = LLVMGetNextGlobal(Cur);
855     if (Next == nullptr) {
856       if (Cur != End)
857         report_fatal_error("");
858       break;
859     }
860 
861     LLVMValueRef Prev = LLVMGetPreviousGlobal(Next);
862     if (Prev != Cur)
863       report_fatal_error("Next.Previous global is not Current");
864 
865     Cur = Next;
866   }
867 
868 FunDecl:
869   Begin = LLVMGetFirstFunction(Src);
870   End = LLVMGetLastFunction(Src);
871   if (!Begin) {
872     if (End != nullptr)
873       report_fatal_error("Range has an end but no beginning");
874     goto AliasDecl;
875   }
876 
877   Cur = Begin;
878   Next = nullptr;
879   while (true) {
880     size_t NameLen;
881     const char *Name = LLVMGetValueName2(Cur, &NameLen);
882     if (LLVMGetNamedFunction(M, Name))
883       report_fatal_error("Function already cloned");
884     auto Ty = LLVMGetElementType(TypeCloner(M).Clone(Cur));
885     auto F = LLVMAddFunction(M, Name, Ty);
886 
887     // Copy attributes
888     for (int i = LLVMAttributeFunctionIndex, c = LLVMCountParams(F);
889          i <= c; ++i) {
890       for (unsigned k = 0, e = LLVMGetLastEnumAttributeKind(); k < e; ++k) {
891         if (auto SrcA = LLVMGetEnumAttributeAtIndex(Cur, i, k)) {
892           auto Val = LLVMGetEnumAttributeValue(SrcA);
893           auto DstA = LLVMCreateEnumAttribute(Ctx, k, Val);
894           LLVMAddAttributeAtIndex(F, i, DstA);
895         }
896       }
897     }
898 
899     Next = LLVMGetNextFunction(Cur);
900     if (Next == nullptr) {
901       if (Cur != End)
902         report_fatal_error("Last function does not match End");
903       break;
904     }
905 
906     LLVMValueRef Prev = LLVMGetPreviousFunction(Next);
907     if (Prev != Cur)
908       report_fatal_error("Next.Previous function is not Current");
909 
910     Cur = Next;
911   }
912 
913 AliasDecl:
914   Begin = LLVMGetFirstGlobalAlias(Src);
915   End = LLVMGetLastGlobalAlias(Src);
916   if (!Begin) {
917     if (End != nullptr)
918       report_fatal_error("Range has an end but no beginning");
919     return;
920   }
921 
922   Cur = Begin;
923   Next = nullptr;
924   while (true) {
925     size_t NameLen;
926     const char *Name = LLVMGetValueName2(Cur, &NameLen);
927     if (LLVMGetNamedGlobalAlias(M, Name, NameLen))
928       report_fatal_error("Global alias already cloned");
929     LLVMTypeRef CurType = TypeCloner(M).Clone(Cur);
930     // FIXME: Allow NULL aliasee.
931     LLVMAddAlias(M, CurType, LLVMGetUndef(CurType), Name);
932 
933     Next = LLVMGetNextGlobalAlias(Cur);
934     if (Next == nullptr) {
935       if (Cur != End)
936         report_fatal_error("");
937       break;
938     }
939 
940     LLVMValueRef Prev = LLVMGetPreviousGlobalAlias(Next);
941     if (Prev != Cur)
942       report_fatal_error("Next.Previous global is not Current");
943 
944     Cur = Next;
945   }
946 }
947 
948 static void clone_symbols(LLVMModuleRef Src, LLVMModuleRef M) {
949   LLVMValueRef Begin = LLVMGetFirstGlobal(Src);
950   LLVMValueRef End = LLVMGetLastGlobal(Src);
951 
952   LLVMValueRef Cur = Begin;
953   LLVMValueRef Next = nullptr;
954   if (!Begin) {
955     if (End != nullptr)
956       report_fatal_error("Range has an end but no beginning");
957     goto FunClone;
958   }
959 
960   while (true) {
961     size_t NameLen;
962     const char *Name = LLVMGetValueName2(Cur, &NameLen);
963     LLVMValueRef G = LLVMGetNamedGlobal(M, Name);
964     if (!G)
965       report_fatal_error("GlobalVariable must have been declared already");
966 
967     if (auto I = LLVMGetInitializer(Cur))
968       LLVMSetInitializer(G, clone_constant(I, M));
969 
970     LLVMSetGlobalConstant(G, LLVMIsGlobalConstant(Cur));
971     LLVMSetThreadLocal(G, LLVMIsThreadLocal(Cur));
972     LLVMSetExternallyInitialized(G, LLVMIsExternallyInitialized(Cur));
973     LLVMSetLinkage(G, LLVMGetLinkage(Cur));
974     LLVMSetSection(G, LLVMGetSection(Cur));
975     LLVMSetVisibility(G, LLVMGetVisibility(Cur));
976     LLVMSetUnnamedAddress(G, LLVMGetUnnamedAddress(Cur));
977     LLVMSetAlignment(G, LLVMGetAlignment(Cur));
978 
979     Next = LLVMGetNextGlobal(Cur);
980     if (Next == nullptr) {
981       if (Cur != End)
982         report_fatal_error("");
983       break;
984     }
985 
986     LLVMValueRef Prev = LLVMGetPreviousGlobal(Next);
987     if (Prev != Cur)
988       report_fatal_error("Next.Previous global is not Current");
989 
990     Cur = Next;
991   }
992 
993 FunClone:
994   Begin = LLVMGetFirstFunction(Src);
995   End = LLVMGetLastFunction(Src);
996   if (!Begin) {
997     if (End != nullptr)
998       report_fatal_error("Range has an end but no beginning");
999     goto AliasClone;
1000   }
1001 
1002   Cur = Begin;
1003   Next = nullptr;
1004   while (true) {
1005     size_t NameLen;
1006     const char *Name = LLVMGetValueName2(Cur, &NameLen);
1007     LLVMValueRef Fun = LLVMGetNamedFunction(M, Name);
1008     if (!Fun)
1009       report_fatal_error("Function must have been declared already");
1010 
1011     if (LLVMHasPersonalityFn(Cur)) {
1012       size_t FNameLen;
1013       const char *FName = LLVMGetValueName2(LLVMGetPersonalityFn(Cur),
1014                                            &FNameLen);
1015       LLVMValueRef P = LLVMGetNamedFunction(M, FName);
1016       if (!P)
1017         report_fatal_error("Could not find personality function");
1018       LLVMSetPersonalityFn(Fun, P);
1019     }
1020 
1021     FunCloner FC(Cur, Fun);
1022     FC.CloneBBs(Cur);
1023 
1024     Next = LLVMGetNextFunction(Cur);
1025     if (Next == nullptr) {
1026       if (Cur != End)
1027         report_fatal_error("Last function does not match End");
1028       break;
1029     }
1030 
1031     LLVMValueRef Prev = LLVMGetPreviousFunction(Next);
1032     if (Prev != Cur)
1033       report_fatal_error("Next.Previous function is not Current");
1034 
1035     Cur = Next;
1036   }
1037 
1038 AliasClone:
1039   Begin = LLVMGetFirstGlobalAlias(Src);
1040   End = LLVMGetLastGlobalAlias(Src);
1041   if (!Begin) {
1042     if (End != nullptr)
1043       report_fatal_error("Range has an end but no beginning");
1044     return;
1045   }
1046 
1047   Cur = Begin;
1048   Next = nullptr;
1049   while (true) {
1050     size_t NameLen;
1051     const char *Name = LLVMGetValueName2(Cur, &NameLen);
1052     LLVMValueRef Alias = LLVMGetNamedGlobalAlias(M, Name, NameLen);
1053     if (!Alias)
1054       report_fatal_error("Global alias must have been declared already");
1055 
1056     if (LLVMValueRef Aliasee = LLVMAliasGetAliasee(Cur)) {
1057       LLVMAliasSetAliasee(Alias, clone_constant(Aliasee, M));
1058     }
1059 
1060     LLVMSetLinkage(Alias, LLVMGetLinkage(Cur));
1061     LLVMSetUnnamedAddress(Alias, LLVMGetUnnamedAddress(Cur));
1062 
1063     Next = LLVMGetNextGlobalAlias(Cur);
1064     if (Next == nullptr) {
1065       if (Cur != End)
1066         report_fatal_error("Last global alias does not match End");
1067       break;
1068     }
1069 
1070     LLVMValueRef Prev = LLVMGetPreviousGlobalAlias(Next);
1071     if (Prev != Cur)
1072       report_fatal_error("Next.Previous global alias is not Current");
1073 
1074     Cur = Next;
1075   }
1076 }
1077 
1078 int llvm_echo(void) {
1079   LLVMEnablePrettyStackTrace();
1080 
1081   LLVMModuleRef Src = llvm_load_module(false, true);
1082   size_t SourceFileLen;
1083   const char *SourceFileName = LLVMGetSourceFileName(Src, &SourceFileLen);
1084   size_t ModuleIdentLen;
1085   const char *ModuleName = LLVMGetModuleIdentifier(Src, &ModuleIdentLen);
1086   LLVMContextRef Ctx = LLVMContextCreate();
1087   LLVMModuleRef M = LLVMModuleCreateWithNameInContext(ModuleName, Ctx);
1088 
1089   LLVMSetSourceFileName(M, SourceFileName, SourceFileLen);
1090   LLVMSetModuleIdentifier(M, ModuleName, ModuleIdentLen);
1091 
1092   size_t SourceFlagsLen;
1093   LLVMModuleFlagEntry *ModuleFlags =
1094       LLVMCopyModuleFlagsMetadata(Src, &SourceFlagsLen);
1095   for (unsigned i = 0; i < SourceFlagsLen; ++i) {
1096     size_t EntryNameLen;
1097     const char *EntryName =
1098         LLVMModuleFlagEntriesGetKey(ModuleFlags, i, &EntryNameLen);
1099     LLVMAddModuleFlag(M, LLVMModuleFlagEntriesGetFlagBehavior(ModuleFlags, i),
1100                       EntryName, EntryNameLen,
1101                       LLVMModuleFlagEntriesGetMetadata(ModuleFlags, i));
1102   }
1103 
1104   LLVMSetTarget(M, LLVMGetTarget(Src));
1105   LLVMSetModuleDataLayout(M, LLVMGetModuleDataLayout(Src));
1106   if (strcmp(LLVMGetDataLayoutStr(M), LLVMGetDataLayoutStr(Src)))
1107     report_fatal_error("Inconsistent DataLayout string representation");
1108 
1109   size_t ModuleInlineAsmLen;
1110   const char *ModuleAsm = LLVMGetModuleInlineAsm(Src, &ModuleInlineAsmLen);
1111   LLVMSetModuleInlineAsm2(M, ModuleAsm, ModuleInlineAsmLen);
1112 
1113   declare_symbols(Src, M);
1114   clone_symbols(Src, M);
1115   char *Str = LLVMPrintModuleToString(M);
1116   fputs(Str, stdout);
1117 
1118   LLVMDisposeModuleFlagsMetadata(ModuleFlags);
1119   LLVMDisposeMessage(Str);
1120   LLVMDisposeModule(Src);
1121   LLVMDisposeModule(M);
1122   LLVMContextDispose(Ctx);
1123 
1124   return 0;
1125 }
1126