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