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 = (LLVMTypeRef*) malloc(ParamCount * sizeof(LLVMTypeRef));
94           LLVMGetParamTypes(Src, Params);
95           for (unsigned i = 0; i < ParamCount; i++)
96             Params[i] = Clone(Params[i]);
97         }
98 
99         LLVMTypeRef FunTy = LLVMFunctionType(Clone(LLVMGetReturnType(Src)),
100                                              Params, ParamCount,
101                                              LLVMIsFunctionVarArg(Src));
102         if (ParamCount > 0)
103           free(Params);
104         return FunTy;
105       }
106       case LLVMStructTypeKind: {
107         LLVMTypeRef S = nullptr;
108         const char *Name = LLVMGetStructName(Src);
109         if (Name) {
110           S = LLVMGetTypeByName(M, Name);
111           if (S)
112             return S;
113           S = LLVMStructCreateNamed(Ctx, Name);
114           if (LLVMIsOpaqueStruct(Src))
115             return S;
116         }
117 
118         unsigned EltCount = LLVMCountStructElementTypes(Src);
119         SmallVector<LLVMTypeRef, 8> Elts;
120         for (unsigned i = 0; i < EltCount; i++)
121           Elts.push_back(Clone(LLVMStructGetTypeAtIndex(Src, i)));
122         if (Name)
123           LLVMStructSetBody(S, Elts.data(), EltCount, LLVMIsPackedStruct(Src));
124         else
125           S = LLVMStructTypeInContext(Ctx, Elts.data(), EltCount,
126                                       LLVMIsPackedStruct(Src));
127         return S;
128       }
129       case LLVMArrayTypeKind:
130         return LLVMArrayType(
131           Clone(LLVMGetElementType(Src)),
132           LLVMGetArrayLength(Src)
133         );
134       case LLVMPointerTypeKind:
135         return LLVMPointerType(
136           Clone(LLVMGetElementType(Src)),
137           LLVMGetPointerAddressSpace(Src)
138         );
139       case LLVMVectorTypeKind:
140         return LLVMVectorType(
141           Clone(LLVMGetElementType(Src)),
142           LLVMGetVectorSize(Src)
143         );
144       case LLVMMetadataTypeKind:
145         break;
146       case LLVMX86_MMXTypeKind:
147         return LLVMX86MMXTypeInContext(Ctx);
148       default:
149         break;
150     }
151 
152     fprintf(stderr, "%d is not a supported typekind\n", Kind);
153     exit(-1);
154   }
155 };
156 
157 static ValueMap clone_params(LLVMValueRef Src, LLVMValueRef Dst) {
158   unsigned Count = LLVMCountParams(Src);
159   if (Count != LLVMCountParams(Dst))
160     report_fatal_error("Parameter count mismatch");
161 
162   ValueMap VMap;
163   if (Count == 0)
164     return VMap;
165 
166   LLVMValueRef SrcFirst = LLVMGetFirstParam(Src);
167   LLVMValueRef DstFirst = LLVMGetFirstParam(Dst);
168   LLVMValueRef SrcLast = LLVMGetLastParam(Src);
169   LLVMValueRef DstLast = LLVMGetLastParam(Dst);
170 
171   LLVMValueRef SrcCur = SrcFirst;
172   LLVMValueRef DstCur = DstFirst;
173   LLVMValueRef SrcNext = nullptr;
174   LLVMValueRef DstNext = nullptr;
175   while (true) {
176     const char *Name = LLVMGetValueName(SrcCur);
177     LLVMSetValueName(DstCur, Name);
178 
179     VMap[SrcCur] = DstCur;
180 
181     Count--;
182     SrcNext = LLVMGetNextParam(SrcCur);
183     DstNext = LLVMGetNextParam(DstCur);
184     if (SrcNext == nullptr && DstNext == nullptr) {
185       if (SrcCur != SrcLast)
186         report_fatal_error("SrcLast param does not match End");
187       if (DstCur != DstLast)
188         report_fatal_error("DstLast param does not match End");
189       break;
190     }
191 
192     if (SrcNext == nullptr)
193       report_fatal_error("SrcNext was unexpectedly null");
194     if (DstNext == nullptr)
195       report_fatal_error("DstNext was unexpectedly null");
196 
197     LLVMValueRef SrcPrev = LLVMGetPreviousParam(SrcNext);
198     if (SrcPrev != SrcCur)
199       report_fatal_error("SrcNext.Previous param is not Current");
200 
201     LLVMValueRef DstPrev = LLVMGetPreviousParam(DstNext);
202     if (DstPrev != DstCur)
203       report_fatal_error("DstNext.Previous param is not Current");
204 
205     SrcCur = SrcNext;
206     DstCur = DstNext;
207   }
208 
209   if (Count != 0)
210     report_fatal_error("Parameter count does not match iteration");
211 
212   return VMap;
213 }
214 
215 static void check_value_kind(LLVMValueRef V, LLVMValueKind K) {
216   if (LLVMGetValueKind(V) != K)
217     report_fatal_error("LLVMGetValueKind returned incorrect type");
218 }
219 
220 static LLVMValueRef clone_constant_impl(LLVMValueRef Cst, LLVMModuleRef M);
221 
222 static LLVMValueRef clone_constant(LLVMValueRef Cst, LLVMModuleRef M) {
223   LLVMValueRef Ret = clone_constant_impl(Cst, M);
224   check_value_kind(Ret, LLVMGetValueKind(Cst));
225   return Ret;
226 }
227 
228 static LLVMValueRef clone_constant_impl(LLVMValueRef Cst, LLVMModuleRef M) {
229   if (!LLVMIsAConstant(Cst))
230     report_fatal_error("Expected a constant");
231 
232   // Maybe it is a symbol
233   if (LLVMIsAGlobalValue(Cst)) {
234     const char *Name = LLVMGetValueName(Cst);
235 
236     // Try function
237     if (LLVMIsAFunction(Cst)) {
238       check_value_kind(Cst, LLVMFunctionValueKind);
239       LLVMValueRef Dst = LLVMGetNamedFunction(M, Name);
240       if (Dst)
241         return Dst;
242       report_fatal_error("Could not find function");
243     }
244 
245     // Try global variable
246     if (LLVMIsAGlobalVariable(Cst)) {
247       check_value_kind(Cst, LLVMGlobalVariableValueKind);
248       LLVMValueRef Dst  = LLVMGetNamedGlobal(M, Name);
249       if (Dst)
250         return Dst;
251       report_fatal_error("Could not find function");
252     }
253 
254     fprintf(stderr, "Could not find @%s\n", Name);
255     exit(-1);
256   }
257 
258   // Try integer literal
259   if (LLVMIsAConstantInt(Cst)) {
260     check_value_kind(Cst, LLVMConstantIntValueKind);
261     return LLVMConstInt(TypeCloner(M).Clone(Cst),
262                         LLVMConstIntGetZExtValue(Cst), false);
263   }
264 
265   // Try zeroinitializer
266   if (LLVMIsAConstantAggregateZero(Cst)) {
267     check_value_kind(Cst, LLVMConstantAggregateZeroValueKind);
268     return LLVMConstNull(TypeCloner(M).Clone(Cst));
269   }
270 
271   // Try constant array
272   if (LLVMIsAConstantArray(Cst)) {
273     check_value_kind(Cst, LLVMConstantArrayValueKind);
274     LLVMTypeRef Ty = TypeCloner(M).Clone(Cst);
275     unsigned EltCount = LLVMGetArrayLength(Ty);
276     SmallVector<LLVMValueRef, 8> Elts;
277     for (unsigned i = 0; i < EltCount; i++)
278       Elts.push_back(clone_constant(LLVMGetOperand(Cst, i), M));
279     return LLVMConstArray(LLVMGetElementType(Ty), Elts.data(), EltCount);
280   }
281 
282   // Try contant data array
283   if (LLVMIsAConstantDataArray(Cst)) {
284     check_value_kind(Cst, LLVMConstantDataArrayValueKind);
285     LLVMTypeRef Ty = TypeCloner(M).Clone(Cst);
286     unsigned EltCount = LLVMGetArrayLength(Ty);
287     SmallVector<LLVMValueRef, 8> Elts;
288     for (unsigned i = 0; i < EltCount; i++)
289       Elts.push_back(clone_constant(LLVMGetElementAsConstant(Cst, i), M));
290     return LLVMConstArray(LLVMGetElementType(Ty), Elts.data(), EltCount);
291   }
292 
293   // Try constant struct
294   if (LLVMIsAConstantStruct(Cst)) {
295     check_value_kind(Cst, LLVMConstantStructValueKind);
296     LLVMTypeRef Ty = TypeCloner(M).Clone(Cst);
297     unsigned EltCount = LLVMCountStructElementTypes(Ty);
298     SmallVector<LLVMValueRef, 8> Elts;
299     for (unsigned i = 0; i < EltCount; i++)
300       Elts.push_back(clone_constant(LLVMGetOperand(Cst, i), M));
301     if (LLVMGetStructName(Ty))
302       return LLVMConstNamedStruct(Ty, Elts.data(), EltCount);
303     return LLVMConstStructInContext(LLVMGetModuleContext(M), Elts.data(),
304                                     EltCount, LLVMIsPackedStruct(Ty));
305   }
306 
307   // Try undef
308   if (LLVMIsUndef(Cst)) {
309     check_value_kind(Cst, LLVMUndefValueValueKind);
310     return LLVMGetUndef(TypeCloner(M).Clone(Cst));
311   }
312 
313   // Try float literal
314   if (LLVMIsAConstantFP(Cst)) {
315     check_value_kind(Cst, LLVMConstantFPValueKind);
316     report_fatal_error("ConstantFP is not supported");
317   }
318 
319   // This kind of constant is not supported
320   if (!LLVMIsAConstantExpr(Cst))
321     report_fatal_error("Expected a constant expression");
322 
323   // At this point, it must be a constant expression
324   check_value_kind(Cst, LLVMConstantExprValueKind);
325 
326   LLVMOpcode Op = LLVMGetConstOpcode(Cst);
327   switch(Op) {
328     case LLVMBitCast:
329       return LLVMConstBitCast(clone_constant(LLVMGetOperand(Cst, 0), M),
330                               TypeCloner(M).Clone(Cst));
331     default:
332       fprintf(stderr, "%d is not a supported opcode\n", Op);
333       exit(-1);
334   }
335 }
336 
337 struct FunCloner {
338   LLVMValueRef Fun;
339   LLVMModuleRef M;
340 
341   ValueMap VMap;
342   BasicBlockMap BBMap;
343 
344   FunCloner(LLVMValueRef Src, LLVMValueRef Dst): Fun(Dst),
345     M(LLVMGetGlobalParent(Fun)), VMap(clone_params(Src, Dst)) {}
346 
347   LLVMTypeRef CloneType(LLVMTypeRef Src) {
348     return TypeCloner(M).Clone(Src);
349   }
350 
351   LLVMTypeRef CloneType(LLVMValueRef Src) {
352     return TypeCloner(M).Clone(Src);
353   }
354 
355   // Try to clone everything in the llvm::Value hierarchy.
356   LLVMValueRef CloneValue(LLVMValueRef Src) {
357     // First, the value may be constant.
358     if (LLVMIsAConstant(Src))
359       return clone_constant(Src, M);
360 
361     // Function argument should always be in the map already.
362     auto i = VMap.find(Src);
363     if (i != VMap.end())
364       return i->second;
365 
366     if (!LLVMIsAInstruction(Src))
367       report_fatal_error("Expected an instruction");
368 
369     auto Ctx = LLVMGetModuleContext(M);
370     auto Builder = LLVMCreateBuilderInContext(Ctx);
371     auto BB = DeclareBB(LLVMGetInstructionParent(Src));
372     LLVMPositionBuilderAtEnd(Builder, BB);
373     auto Dst = CloneInstruction(Src, Builder);
374     LLVMDisposeBuilder(Builder);
375     return Dst;
376   }
377 
378   LLVMValueRef CloneInstruction(LLVMValueRef Src, LLVMBuilderRef Builder) {
379     check_value_kind(Src, LLVMInstructionValueKind);
380     if (!LLVMIsAInstruction(Src))
381       report_fatal_error("Expected an instruction");
382 
383     const char *Name = LLVMGetValueName(Src);
384 
385     // Check if this is something we already computed.
386     {
387       auto i = VMap.find(Src);
388       if (i != VMap.end()) {
389         // If we have a hit, it means we already generated the instruction
390         // as a dependancy to somethign else. We need to make sure
391         // it is ordered properly.
392         auto I = i->second;
393         LLVMInstructionRemoveFromParent(I);
394         LLVMInsertIntoBuilderWithName(Builder, I, Name);
395         return I;
396       }
397     }
398 
399     // We tried everything, it must be an instruction
400     // that hasn't been generated already.
401     LLVMValueRef Dst = nullptr;
402 
403     LLVMOpcode Op = LLVMGetInstructionOpcode(Src);
404     switch(Op) {
405       case LLVMRet: {
406         int OpCount = LLVMGetNumOperands(Src);
407         if (OpCount == 0)
408           Dst = LLVMBuildRetVoid(Builder);
409         else
410           Dst = LLVMBuildRet(Builder, CloneValue(LLVMGetOperand(Src, 0)));
411         break;
412       }
413       case LLVMBr: {
414         if (!LLVMIsConditional(Src)) {
415           LLVMValueRef SrcOp = LLVMGetOperand(Src, 0);
416           LLVMBasicBlockRef SrcBB = LLVMValueAsBasicBlock(SrcOp);
417           Dst = LLVMBuildBr(Builder, DeclareBB(SrcBB));
418           break;
419         }
420 
421         LLVMValueRef Cond = LLVMGetCondition(Src);
422         LLVMValueRef Else = LLVMGetOperand(Src, 1);
423         LLVMBasicBlockRef ElseBB = DeclareBB(LLVMValueAsBasicBlock(Else));
424         LLVMValueRef Then = LLVMGetOperand(Src, 2);
425         LLVMBasicBlockRef ThenBB = DeclareBB(LLVMValueAsBasicBlock(Then));
426         Dst = LLVMBuildCondBr(Builder, Cond, ThenBB, ElseBB);
427         break;
428       }
429       case LLVMSwitch:
430       case LLVMIndirectBr:
431         break;
432       case LLVMInvoke: {
433         SmallVector<LLVMValueRef, 8> Args;
434         int ArgCount = LLVMGetNumArgOperands(Src);
435         for (int i = 0; i < ArgCount; i++)
436           Args.push_back(CloneValue(LLVMGetOperand(Src, i)));
437         LLVMValueRef Fn = CloneValue(LLVMGetCalledValue(Src));
438         LLVMBasicBlockRef Then = DeclareBB(LLVMGetNormalDest(Src));
439         LLVMBasicBlockRef Unwind = DeclareBB(LLVMGetUnwindDest(Src));
440         Dst = LLVMBuildInvoke(Builder, Fn, Args.data(), ArgCount,
441                               Then, Unwind, Name);
442         break;
443       }
444       case LLVMUnreachable:
445         Dst = LLVMBuildUnreachable(Builder);
446         break;
447       case LLVMAdd: {
448         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
449         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
450         Dst = LLVMBuildAdd(Builder, LHS, RHS, Name);
451         break;
452       }
453       case LLVMSub: {
454         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
455         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
456         Dst = LLVMBuildSub(Builder, LHS, RHS, Name);
457         break;
458       }
459       case LLVMMul: {
460         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
461         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
462         Dst = LLVMBuildMul(Builder, LHS, RHS, Name);
463         break;
464       }
465       case LLVMUDiv: {
466         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
467         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
468         Dst = LLVMBuildUDiv(Builder, LHS, RHS, Name);
469         break;
470       }
471       case LLVMSDiv: {
472         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
473         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
474         Dst = LLVMBuildSDiv(Builder, LHS, RHS, Name);
475         break;
476       }
477       case LLVMURem: {
478         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
479         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
480         Dst = LLVMBuildURem(Builder, LHS, RHS, Name);
481         break;
482       }
483       case LLVMSRem: {
484         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
485         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
486         Dst = LLVMBuildSRem(Builder, LHS, RHS, Name);
487         break;
488       }
489       case LLVMShl: {
490         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
491         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
492         Dst = LLVMBuildShl(Builder, LHS, RHS, Name);
493         break;
494       }
495       case LLVMLShr: {
496         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
497         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
498         Dst = LLVMBuildLShr(Builder, LHS, RHS, Name);
499         break;
500       }
501       case LLVMAShr: {
502         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
503         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
504         Dst = LLVMBuildAShr(Builder, LHS, RHS, Name);
505         break;
506       }
507       case LLVMAnd: {
508         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
509         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
510         Dst = LLVMBuildAnd(Builder, LHS, RHS, Name);
511         break;
512       }
513       case LLVMOr: {
514         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
515         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
516         Dst = LLVMBuildOr(Builder, LHS, RHS, Name);
517         break;
518       }
519       case LLVMXor: {
520         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
521         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
522         Dst = LLVMBuildXor(Builder, LHS, RHS, Name);
523         break;
524       }
525       case LLVMAlloca: {
526         LLVMTypeRef Ty = CloneType(LLVMGetAllocatedType(Src));
527         Dst = LLVMBuildAlloca(Builder, Ty, Name);
528         break;
529       }
530       case LLVMLoad: {
531         LLVMValueRef Ptr = CloneValue(LLVMGetOperand(Src, 0));
532         Dst = LLVMBuildLoad(Builder, Ptr, Name);
533         LLVMSetAlignment(Dst, LLVMGetAlignment(Src));
534         break;
535       }
536       case LLVMStore: {
537         LLVMValueRef Val = CloneValue(LLVMGetOperand(Src, 0));
538         LLVMValueRef Ptr = CloneValue(LLVMGetOperand(Src, 1));
539         Dst = LLVMBuildStore(Builder, Val, Ptr);
540         LLVMSetAlignment(Dst, LLVMGetAlignment(Src));
541         break;
542       }
543       case LLVMGetElementPtr: {
544         LLVMValueRef Ptr = CloneValue(LLVMGetOperand(Src, 0));
545         SmallVector<LLVMValueRef, 8> Idx;
546         int NumIdx = LLVMGetNumIndices(Src);
547         for (int i = 1; i <= NumIdx; i++)
548           Idx.push_back(CloneValue(LLVMGetOperand(Src, i)));
549         if (LLVMIsInBounds(Src))
550           Dst = LLVMBuildInBoundsGEP(Builder, Ptr, Idx.data(), NumIdx, Name);
551         else
552           Dst = LLVMBuildGEP(Builder, Ptr, Idx.data(), NumIdx, Name);
553         break;
554       }
555       case LLVMAtomicCmpXchg: {
556         LLVMValueRef Ptr = CloneValue(LLVMGetOperand(Src, 0));
557         LLVMValueRef Cmp = CloneValue(LLVMGetOperand(Src, 1));
558         LLVMValueRef New = CloneValue(LLVMGetOperand(Src, 2));
559         LLVMAtomicOrdering Succ = LLVMGetCmpXchgSuccessOrdering(Src);
560         LLVMAtomicOrdering Fail = LLVMGetCmpXchgFailureOrdering(Src);
561         LLVMBool SingleThread = LLVMIsAtomicSingleThread(Src);
562 
563         Dst = LLVMBuildAtomicCmpXchg(Builder, Ptr, Cmp, New, Succ, Fail,
564                                      SingleThread);
565       } break;
566       case LLVMBitCast: {
567         LLVMValueRef V = CloneValue(LLVMGetOperand(Src, 0));
568         Dst = LLVMBuildBitCast(Builder, V, CloneType(Src), Name);
569         break;
570       }
571       case LLVMICmp: {
572         LLVMIntPredicate Pred = LLVMGetICmpPredicate(Src);
573         LLVMValueRef LHS = CloneValue(LLVMGetOperand(Src, 0));
574         LLVMValueRef RHS = CloneValue(LLVMGetOperand(Src, 1));
575         Dst = LLVMBuildICmp(Builder, Pred, LHS, RHS, Name);
576         break;
577       }
578       case LLVMPHI: {
579         // We need to agressively set things here because of loops.
580         VMap[Src] = Dst = LLVMBuildPhi(Builder, CloneType(Src), Name);
581 
582         SmallVector<LLVMValueRef, 8> Values;
583         SmallVector<LLVMBasicBlockRef, 8> Blocks;
584 
585         unsigned IncomingCount = LLVMCountIncoming(Src);
586         for (unsigned i = 0; i < IncomingCount; ++i) {
587           Blocks.push_back(DeclareBB(LLVMGetIncomingBlock(Src, i)));
588           Values.push_back(CloneValue(LLVMGetIncomingValue(Src, i)));
589         }
590 
591         LLVMAddIncoming(Dst, Values.data(), Blocks.data(), IncomingCount);
592         return Dst;
593       }
594       case LLVMCall: {
595         SmallVector<LLVMValueRef, 8> Args;
596         int ArgCount = LLVMGetNumArgOperands(Src);
597         for (int i = 0; i < ArgCount; i++)
598           Args.push_back(CloneValue(LLVMGetOperand(Src, i)));
599         LLVMValueRef Fn = CloneValue(LLVMGetCalledValue(Src));
600         Dst = LLVMBuildCall(Builder, Fn, Args.data(), ArgCount, Name);
601         LLVMSetTailCall(Dst, LLVMIsTailCall(Src));
602         break;
603       }
604       case LLVMResume: {
605         Dst = LLVMBuildResume(Builder, CloneValue(LLVMGetOperand(Src, 0)));
606         break;
607       }
608       case LLVMLandingPad: {
609         // The landing pad API is a bit screwed up for historical reasons.
610         Dst = LLVMBuildLandingPad(Builder, CloneType(Src), nullptr, 0, Name);
611         unsigned NumClauses = LLVMGetNumClauses(Src);
612         for (unsigned i = 0; i < NumClauses; ++i)
613           LLVMAddClause(Dst, CloneValue(LLVMGetClause(Src, i)));
614         LLVMSetCleanup(Dst, LLVMIsCleanup(Src));
615         break;
616       }
617       case LLVMExtractValue: {
618         LLVMValueRef Agg = CloneValue(LLVMGetOperand(Src, 0));
619         if (LLVMGetNumIndices(Src) != 1)
620           report_fatal_error("Expected only one indice");
621         auto I = LLVMGetIndices(Src)[0];
622         Dst = LLVMBuildExtractValue(Builder, Agg, I, Name);
623         break;
624       }
625       case LLVMInsertValue: {
626         LLVMValueRef Agg = CloneValue(LLVMGetOperand(Src, 0));
627         LLVMValueRef V = CloneValue(LLVMGetOperand(Src, 1));
628         if (LLVMGetNumIndices(Src) != 1)
629           report_fatal_error("Expected only one indice");
630         auto I = LLVMGetIndices(Src)[0];
631         Dst = LLVMBuildInsertValue(Builder, Agg, V, I, Name);
632         break;
633       }
634       default:
635         break;
636     }
637 
638     if (Dst == nullptr) {
639       fprintf(stderr, "%d is not a supported opcode\n", Op);
640       exit(-1);
641     }
642 
643     check_value_kind(Dst, LLVMInstructionValueKind);
644     return VMap[Src] = Dst;
645   }
646 
647   LLVMBasicBlockRef DeclareBB(LLVMBasicBlockRef Src) {
648     // Check if this is something we already computed.
649     {
650       auto i = BBMap.find(Src);
651       if (i != BBMap.end()) {
652         return i->second;
653       }
654     }
655 
656     LLVMValueRef V = LLVMBasicBlockAsValue(Src);
657     if (!LLVMValueIsBasicBlock(V) || LLVMValueAsBasicBlock(V) != Src)
658       report_fatal_error("Basic block is not a basic block");
659 
660     const char *Name = LLVMGetBasicBlockName(Src);
661     const char *VName = LLVMGetValueName(V);
662     if (Name != VName)
663       report_fatal_error("Basic block name mismatch");
664 
665     LLVMBasicBlockRef BB = LLVMAppendBasicBlock(Fun, Name);
666     return BBMap[Src] = BB;
667   }
668 
669   LLVMBasicBlockRef CloneBB(LLVMBasicBlockRef Src) {
670     LLVMBasicBlockRef BB = DeclareBB(Src);
671 
672     // Make sure ordering is correct.
673     LLVMBasicBlockRef Prev = LLVMGetPreviousBasicBlock(Src);
674     if (Prev)
675       LLVMMoveBasicBlockAfter(BB, DeclareBB(Prev));
676 
677     LLVMValueRef First = LLVMGetFirstInstruction(Src);
678     LLVMValueRef Last = LLVMGetLastInstruction(Src);
679 
680     if (First == nullptr) {
681       if (Last != nullptr)
682         report_fatal_error("Has no first instruction, but last one");
683       return BB;
684     }
685 
686     auto Ctx = LLVMGetModuleContext(M);
687     LLVMBuilderRef Builder = LLVMCreateBuilderInContext(Ctx);
688     LLVMPositionBuilderAtEnd(Builder, BB);
689 
690     LLVMValueRef Cur = First;
691     LLVMValueRef Next = nullptr;
692     while(true) {
693       CloneInstruction(Cur, Builder);
694       Next = LLVMGetNextInstruction(Cur);
695       if (Next == nullptr) {
696         if (Cur != Last)
697           report_fatal_error("Final instruction does not match Last");
698         break;
699       }
700 
701       LLVMValueRef Prev = LLVMGetPreviousInstruction(Next);
702       if (Prev != Cur)
703         report_fatal_error("Next.Previous instruction is not Current");
704 
705       Cur = Next;
706     }
707 
708     LLVMDisposeBuilder(Builder);
709     return BB;
710   }
711 
712   void CloneBBs(LLVMValueRef Src) {
713     unsigned Count = LLVMCountBasicBlocks(Src);
714     if (Count == 0)
715       return;
716 
717     LLVMBasicBlockRef First = LLVMGetFirstBasicBlock(Src);
718     LLVMBasicBlockRef Last = LLVMGetLastBasicBlock(Src);
719 
720     LLVMBasicBlockRef Cur = First;
721     LLVMBasicBlockRef Next = nullptr;
722     while(true) {
723       CloneBB(Cur);
724       Count--;
725       Next = LLVMGetNextBasicBlock(Cur);
726       if (Next == nullptr) {
727         if (Cur != Last)
728           report_fatal_error("Final basic block does not match Last");
729         break;
730       }
731 
732       LLVMBasicBlockRef Prev = LLVMGetPreviousBasicBlock(Next);
733       if (Prev != Cur)
734         report_fatal_error("Next.Previous basic bloc is not Current");
735 
736       Cur = Next;
737     }
738 
739     if (Count != 0)
740       report_fatal_error("Basic block count does not match iterration");
741   }
742 };
743 
744 static void declare_symbols(LLVMModuleRef Src, LLVMModuleRef M) {
745   LLVMValueRef Begin = LLVMGetFirstGlobal(Src);
746   LLVMValueRef End = LLVMGetLastGlobal(Src);
747 
748   LLVMValueRef Cur = Begin;
749   LLVMValueRef Next = nullptr;
750   if (!Begin) {
751     if (End != nullptr)
752       report_fatal_error("Range has an end but no begining");
753     goto FunDecl;
754   }
755 
756   while (true) {
757     const char *Name = LLVMGetValueName(Cur);
758     if (LLVMGetNamedGlobal(M, Name))
759       report_fatal_error("GlobalVariable already cloned");
760     LLVMAddGlobal(M, LLVMGetElementType(TypeCloner(M).Clone(Cur)), Name);
761 
762     Next = LLVMGetNextGlobal(Cur);
763     if (Next == nullptr) {
764       if (Cur != End)
765         report_fatal_error("");
766       break;
767     }
768 
769     LLVMValueRef Prev = LLVMGetPreviousGlobal(Next);
770     if (Prev != Cur)
771       report_fatal_error("Next.Previous global is not Current");
772 
773     Cur = Next;
774   }
775 
776 FunDecl:
777   Begin = LLVMGetFirstFunction(Src);
778   End = LLVMGetLastFunction(Src);
779   if (!Begin) {
780     if (End != nullptr)
781       report_fatal_error("Range has an end but no begining");
782     return;
783   }
784 
785   Cur = Begin;
786   Next = nullptr;
787   while (true) {
788     const char *Name = LLVMGetValueName(Cur);
789     if (LLVMGetNamedFunction(M, Name))
790       report_fatal_error("Function already cloned");
791     LLVMAddFunction(M, Name, LLVMGetElementType(TypeCloner(M).Clone(Cur)));
792 
793     Next = LLVMGetNextFunction(Cur);
794     if (Next == nullptr) {
795       if (Cur != End)
796         report_fatal_error("Last function does not match End");
797       break;
798     }
799 
800     LLVMValueRef Prev = LLVMGetPreviousFunction(Next);
801     if (Prev != Cur)
802       report_fatal_error("Next.Previous function is not Current");
803 
804     Cur = Next;
805   }
806 }
807 
808 static void clone_symbols(LLVMModuleRef Src, LLVMModuleRef M) {
809   LLVMValueRef Begin = LLVMGetFirstGlobal(Src);
810   LLVMValueRef End = LLVMGetLastGlobal(Src);
811 
812   LLVMValueRef Cur = Begin;
813   LLVMValueRef Next = nullptr;
814   if (!Begin) {
815     if (End != nullptr)
816       report_fatal_error("Range has an end but no begining");
817     goto FunClone;
818   }
819 
820   while (true) {
821     const char *Name = LLVMGetValueName(Cur);
822     LLVMValueRef G = LLVMGetNamedGlobal(M, Name);
823     if (!G)
824       report_fatal_error("GlobalVariable must have been declared already");
825 
826     if (auto I = LLVMGetInitializer(Cur))
827       LLVMSetInitializer(G, clone_constant(I, M));
828 
829     LLVMSetGlobalConstant(G, LLVMIsGlobalConstant(Cur));
830     LLVMSetThreadLocal(G, LLVMIsThreadLocal(Cur));
831     LLVMSetExternallyInitialized(G, LLVMIsExternallyInitialized(Cur));
832     LLVMSetLinkage(G, LLVMGetLinkage(Cur));
833     LLVMSetSection(G, LLVMGetSection(Cur));
834     LLVMSetVisibility(G, LLVMGetVisibility(Cur));
835     LLVMSetUnnamedAddr(G, LLVMHasUnnamedAddr(Cur));
836     LLVMSetAlignment(G, LLVMGetAlignment(Cur));
837 
838     Next = LLVMGetNextGlobal(Cur);
839     if (Next == nullptr) {
840       if (Cur != End)
841         report_fatal_error("");
842       break;
843     }
844 
845     LLVMValueRef Prev = LLVMGetPreviousGlobal(Next);
846     if (Prev != Cur)
847       report_fatal_error("Next.Previous global is not Current");
848 
849     Cur = Next;
850   }
851 
852 FunClone:
853   Begin = LLVMGetFirstFunction(Src);
854   End = LLVMGetLastFunction(Src);
855   if (!Begin) {
856     if (End != nullptr)
857       report_fatal_error("Range has an end but no begining");
858     return;
859   }
860 
861   Cur = Begin;
862   Next = nullptr;
863   while (true) {
864     const char *Name = LLVMGetValueName(Cur);
865     LLVMValueRef Fun = LLVMGetNamedFunction(M, Name);
866     if (!Fun)
867       report_fatal_error("Function must have been declared already");
868 
869     if (LLVMHasPersonalityFn(Cur)) {
870       const char *FName = LLVMGetValueName(LLVMGetPersonalityFn(Cur));
871       LLVMValueRef P = LLVMGetNamedFunction(M, FName);
872       if (!P)
873         report_fatal_error("Could not find personality function");
874       LLVMSetPersonalityFn(Fun, P);
875     }
876 
877     FunCloner FC(Cur, Fun);
878     FC.CloneBBs(Cur);
879 
880     Next = LLVMGetNextFunction(Cur);
881     if (Next == nullptr) {
882       if (Cur != End)
883         report_fatal_error("Last function does not match End");
884       break;
885     }
886 
887     LLVMValueRef Prev = LLVMGetPreviousFunction(Next);
888     if (Prev != Cur)
889       report_fatal_error("Next.Previous function is not Current");
890 
891     Cur = Next;
892   }
893 }
894 
895 int llvm_echo(void) {
896   LLVMEnablePrettyStackTrace();
897 
898   LLVMModuleRef Src = llvm_load_module(false, true);
899   size_t Len;
900   const char *ModuleName = LLVMGetModuleIdentifier(Src, &Len);
901   LLVMContextRef Ctx = LLVMContextCreate();
902   LLVMModuleRef M = LLVMModuleCreateWithNameInContext(ModuleName, Ctx);
903 
904   // This whole switcharound is done because the C API has no way to
905   // set the source_filename
906   LLVMSetModuleIdentifier(M, "", 0);
907   LLVMGetModuleIdentifier(M, &Len);
908   if (Len != 0)
909       report_fatal_error("LLVM{Set,Get}ModuleIdentifier failed");
910   LLVMSetModuleIdentifier(M, ModuleName, strlen(ModuleName));
911 
912   LLVMSetTarget(M, LLVMGetTarget(Src));
913   LLVMSetModuleDataLayout(M, LLVMGetModuleDataLayout(Src));
914   if (strcmp(LLVMGetDataLayoutStr(M), LLVMGetDataLayoutStr(Src)))
915     report_fatal_error("Inconsistent DataLayout string representation");
916 
917   declare_symbols(Src, M);
918   clone_symbols(Src, M);
919   char *Str = LLVMPrintModuleToString(M);
920   fputs(Str, stdout);
921 
922   LLVMDisposeMessage(Str);
923   LLVMDisposeModule(M);
924   LLVMContextDispose(Ctx);
925 
926   return 0;
927 }
928