22b15924d263113f1e93eb2bd50f8c148910f1a1
[oota-llvm.git] / lib / Bytecode / Reader / Reader.cpp
1 //===- Reader.cpp - Code to read bytecode files ---------------------------===//
2 //
3 // This library implements the functionality defined in llvm/Bytecode/Reader.h
4 //
5 // Note that this library should be as fast as possible, reentrant, and 
6 // threadsafe!!
7 //
8 // TODO: Return error messages to caller instead of printing them out directly.
9 // TODO: Allow passing in an option to ignore the symbol table
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "ReaderInternals.h"
14 #include "llvm/Bytecode/Reader.h"
15 #include "llvm/Bytecode/Format.h"
16 #include "llvm/Module.h"
17 #include "llvm/Constants.h"
18 #include "llvm/iPHINode.h"
19 #include "llvm/iOther.h"
20 #include <sys/types.h>
21 #include <sys/stat.h>
22 #include <sys/mman.h>
23 #include <fcntl.h>
24 #include <unistd.h>
25 #include <algorithm>
26 using std::cerr;
27 using std::pair;
28 using std::make_pair;
29
30 bool BytecodeParser::getTypeSlot(const Type *Ty, unsigned &Slot) {
31   if (Ty->isPrimitiveType()) {
32     Slot = Ty->getPrimitiveID();
33   } else {
34     // Check the method level types first...
35     TypeValuesListTy::iterator I = find(MethodTypeValues.begin(),
36                                         MethodTypeValues.end(), Ty);
37     if (I != MethodTypeValues.end()) {
38       Slot = FirstDerivedTyID+ModuleTypeValues.size()+
39              (&*I - &MethodTypeValues[0]);
40     } else {
41       I = find(ModuleTypeValues.begin(), ModuleTypeValues.end(), Ty);
42       if (I == ModuleTypeValues.end()) return true;   // Didn't find type!
43       Slot = FirstDerivedTyID + (&*I - &ModuleTypeValues[0]);
44     }
45   }
46   //cerr << "getTypeSlot '" << Ty->getName() << "' = " << Slot << "\n";
47   return false;
48 }
49
50 const Type *BytecodeParser::getType(unsigned ID) {
51   const Type *T = Type::getPrimitiveType((Type::PrimitiveID)ID);
52   if (T) return T;
53   
54   //cerr << "Looking up Type ID: " << ID << "\n";
55
56   const Value *D = getValue(Type::TypeTy, ID, false);
57   if (D == 0) return 0;
58
59   return cast<Type>(D);
60 }
61
62 int BytecodeParser::insertValue(Value *Val, std::vector<ValueList> &ValueTab) {
63   unsigned type;
64   if (getTypeSlot(Val->getType(), type)) return -1;
65   assert(type != Type::TypeTyID && "Types should never be insertValue'd!");
66  
67   if (ValueTab.size() <= type)
68     ValueTab.resize(type+1, ValueList());
69
70   //cerr << "insertValue Values[" << type << "][" << ValueTab[type].size() 
71   //     << "] = " << Val << "\n";
72   ValueTab[type].push_back(Val);
73
74   return ValueTab[type].size()-1;
75 }
76
77 Value *BytecodeParser::getValue(const Type *Ty, unsigned oNum, bool Create) {
78   unsigned Num = oNum;
79   unsigned type;   // The type plane it lives in...
80
81   if (getTypeSlot(Ty, type)) return 0;
82
83   if (type == Type::TypeTyID) {  // The 'type' plane has implicit values
84     assert(Create == false);
85     const Type *T = Type::getPrimitiveType((Type::PrimitiveID)Num);
86     if (T) return (Value*)T;   // Asked for a primitive type...
87
88     // Otherwise, derived types need offset...
89     Num -= FirstDerivedTyID;
90
91     // Is it a module level type?
92     if (Num < ModuleTypeValues.size())
93       return (Value*)ModuleTypeValues[Num].get();
94
95     // Nope, is it a method level type?
96     Num -= ModuleTypeValues.size();
97     if (Num < MethodTypeValues.size())
98       return (Value*)MethodTypeValues[Num].get();
99
100     return 0;
101   }
102
103   if (type < ModuleValues.size()) {
104     if (Num < ModuleValues[type].size())
105       return ModuleValues[type][Num];
106     Num -= ModuleValues[type].size();
107   }
108
109   if (Values.size() > type && Values[type].size() > Num)
110     return Values[type][Num];
111
112   if (!Create) return 0;  // Do not create a placeholder?
113
114   Value *d = 0;
115   switch (Ty->getPrimitiveID()) {
116   case Type::FunctionTyID:
117     cerr << "Creating method pholder! : " << type << ":" << oNum << " " 
118          << Ty->getName() << "\n";
119     d = new FunctionPHolder(Ty, oNum);
120     if (insertValue(d, LateResolveModuleValues) == -1) return 0;
121     return d;
122   case Type::LabelTyID:
123     d = new BBPHolder(Ty, oNum);
124     break;
125   default:
126     d = new ValPHolder(Ty, oNum);
127     break;
128   }
129
130   assert(d != 0 && "How did we not make something?");
131   if (insertValue(d, LateResolveValues) == -1) return 0;
132   return d;
133 }
134
135 bool BytecodeParser::postResolveValues(ValueTable &ValTab) {
136   bool Error = false;
137   for (unsigned ty = 0; ty < ValTab.size(); ++ty) {
138     ValueList &DL = ValTab[ty];
139     unsigned Size;
140     while ((Size = DL.size())) {
141       unsigned IDNumber = getValueIDNumberFromPlaceHolder(DL[Size-1]);
142
143       Value *D = DL[Size-1];
144       DL.pop_back();
145
146       Value *NewDef = getValue(D->getType(), IDNumber, false);
147       if (NewDef == 0) {
148         Error = true;  // Unresolved thinger
149         cerr << "Unresolvable reference found: <"
150               << D->getType()->getDescription() << ">:" << IDNumber << "!\n";
151       } else {
152         // Fixup all of the uses of this placeholder def...
153         D->replaceAllUsesWith(NewDef);
154
155         // Now that all the uses are gone, delete the placeholder...
156         // If we couldn't find a def (error case), then leak a little
157         delete D;  // memory, 'cause otherwise we can't remove all uses!
158       }
159     }
160   }
161
162   return Error;
163 }
164
165 bool BytecodeParser::ParseBasicBlock(const uchar *&Buf, const uchar *EndBuf, 
166                                      BasicBlock *&BB) {
167   BB = new BasicBlock();
168
169   while (Buf < EndBuf) {
170     Instruction *Inst;
171     if (ParseInstruction(Buf, EndBuf, Inst,
172                          /*HACK*/BB)) {
173       delete BB;
174       return true;
175     }
176
177     if (Inst == 0) { delete BB; return true; }
178     if (insertValue(Inst, Values) == -1) { delete BB; return true; }
179
180     BB->getInstList().push_back(Inst);
181
182     BCR_TRACE(4, Inst);
183   }
184
185   return false;
186 }
187
188 bool BytecodeParser::ParseSymbolTable(const uchar *&Buf, const uchar *EndBuf,
189                                       SymbolTable *ST) {
190   while (Buf < EndBuf) {
191     // Symtab block header: [num entries][type id number]
192     unsigned NumEntries, Typ;
193     if (read_vbr(Buf, EndBuf, NumEntries) ||
194         read_vbr(Buf, EndBuf, Typ)) return true;
195     const Type *Ty = getType(Typ);
196     if (Ty == 0) return true;
197
198     BCR_TRACE(3, "Plane Type: '" << Ty << "' with " << NumEntries <<
199               " entries\n");
200
201     for (unsigned i = 0; i < NumEntries; ++i) {
202       // Symtab entry: [def slot #][name]
203       unsigned slot;
204       if (read_vbr(Buf, EndBuf, slot)) return true;
205       std::string Name;
206       if (read(Buf, EndBuf, Name, false))  // Not aligned...
207         return true;
208
209       Value *D = getValue(Ty, slot, false); // Find mapping...
210       if (D == 0) {
211         BCR_TRACE(3, "FAILED LOOKUP: Slot #" << slot << "\n");
212         return true;
213       }
214       BCR_TRACE(4, "Map: '" << Name << "' to #" << slot << ":" << D;
215                 if (!isa<Instruction>(D)) cerr << "\n");
216
217       D->setName(Name, ST);
218     }
219   }
220
221   if (Buf > EndBuf) return true;
222   return false;
223 }
224
225 void BytecodeParser::ResolveReferencesToValue(Value *NewV, unsigned Slot) {
226   GlobalRefsType::iterator I = GlobalRefs.find(make_pair(NewV->getType(),Slot));
227   if (I == GlobalRefs.end()) return;   // Never forward referenced?
228
229   BCR_TRACE(3, "Mutating forward refs!\n");
230   Value *VPH = I->second;   // Get the placeholder...
231
232   // Loop over all of the uses of the Value.  What they are depends
233   // on what NewV is.  Replacing a use of the old reference takes the
234   // use off the use list, so loop with !use_empty(), not the use_iterator.
235   while (!VPH->use_empty()) {
236     Constant *C = cast<Constant>(VPH->use_back());
237     unsigned numReplaced = C->mutateReferences(VPH, NewV);
238     assert(numReplaced > 0 && "Supposed user wasn't really a user?");
239       
240     if (GlobalValue* GVal = dyn_cast<GlobalValue>(NewV)) {
241       // Remove the placeholder GlobalValue from the module...
242       GVal->getParent()->getGlobalList().remove(cast<GlobalVariable>(VPH));
243     }
244   }
245
246   delete VPH;                         // Delete the old placeholder
247   GlobalRefs.erase(I);                // Remove the map entry for it
248 }
249
250 bool BytecodeParser::ParseMethod(const uchar *&Buf, const uchar *EndBuf, 
251                                  Module *C) {
252   // Clear out the local values table...
253   Values.clear();
254   if (FunctionSignatureList.empty()) {
255     Error = "Function found, but FunctionSignatureList empty!";
256     return true;  // Unexpected method!
257   }
258
259   const PointerType *PMTy = FunctionSignatureList.back().first; // PtrMeth
260   const FunctionType *MTy  = dyn_cast<FunctionType>(PMTy->getElementType());
261   if (MTy == 0) return true;  // Not ptr to method!
262
263   unsigned isInternal;
264   if (read_vbr(Buf, EndBuf, isInternal)) return true;
265
266   unsigned MethSlot = FunctionSignatureList.back().second;
267   FunctionSignatureList.pop_back();
268   Function *M = new Function(MTy, isInternal != 0);
269
270   BCR_TRACE(2, "METHOD TYPE: " << MTy << "\n");
271
272   const FunctionType::ParamTypes &Params = MTy->getParamTypes();
273   for (FunctionType::ParamTypes::const_iterator It = Params.begin();
274        It != Params.end(); ++It) {
275     Argument *FA = new Argument(*It);
276     if (insertValue(FA, Values) == -1) {
277       Error = "Error reading method arguments!\n";
278       delete M; return true; 
279     }
280     M->getArgumentList().push_back(FA);
281   }
282
283   while (Buf < EndBuf) {
284     unsigned Type, Size;
285     const uchar *OldBuf = Buf;
286     if (readBlock(Buf, EndBuf, Type, Size)) {
287       Error = "Error reading Function level block!";
288       delete M; return true; 
289     }
290
291     switch (Type) {
292     case BytecodeFormat::ConstantPool:
293       BCR_TRACE(2, "BLOCK BytecodeFormat::ConstantPool: {\n");
294       if (ParseConstantPool(Buf, Buf+Size, Values, MethodTypeValues)) {
295         delete M; return true;
296       }
297       break;
298
299     case BytecodeFormat::BasicBlock: {
300       BCR_TRACE(2, "BLOCK BytecodeFormat::BasicBlock: {\n");
301       BasicBlock *BB;
302       if (ParseBasicBlock(Buf, Buf+Size, BB) ||
303           insertValue(BB, Values) == -1) {
304         delete M; return true;                // Parse error... :(
305       }
306
307       M->getBasicBlockList().push_back(BB);
308       break;
309     }
310
311     case BytecodeFormat::SymbolTable:
312       BCR_TRACE(2, "BLOCK BytecodeFormat::SymbolTable: {\n");
313       if (ParseSymbolTable(Buf, Buf+Size, M->getSymbolTableSure())) {
314         delete M; return true;
315       }
316       break;
317
318     default:
319       BCR_TRACE(2, "BLOCK <unknown>:ignored! {\n");
320       Buf += Size;
321       if (OldBuf > Buf) return true; // Wrap around!
322       break;
323     }
324     BCR_TRACE(2, "} end block\n");
325
326     if (align32(Buf, EndBuf)) {
327       Error = "Error aligning Function level block!";
328       delete M;    // Malformed bc file, read past end of block.
329       return true;
330     }
331   }
332
333   if (postResolveValues(LateResolveValues) ||
334       postResolveValues(LateResolveModuleValues)) {
335     Error = "Error resolving method values!";
336     delete M; return true;     // Unresolvable references!
337   }
338
339   Value *FunctionPHolder = getValue(PMTy, MethSlot, false);
340   assert(FunctionPHolder && "Something is broken no placeholder found!");
341   assert(isa<Function>(FunctionPHolder) && "Not a function?");
342
343   unsigned type;  // Type slot
344   assert(!getTypeSlot(MTy, type) && "How can meth type not exist?");
345   getTypeSlot(PMTy, type);
346
347   C->getFunctionList().push_back(M);
348
349   // Replace placeholder with the real method pointer...
350   ModuleValues[type][MethSlot] = M;
351
352   // Clear out method level types...
353   MethodTypeValues.clear();
354
355   // If anyone is using the placeholder make them use the real method instead
356   FunctionPHolder->replaceAllUsesWith(M);
357
358   // We don't need the placeholder anymore!
359   delete FunctionPHolder;
360
361   // If the method is empty, we don't need the method argument entries...
362   if (M->isExternal())
363     M->getArgumentList().clear();
364
365   ResolveReferencesToValue(M, MethSlot);
366
367   return false;
368 }
369
370 bool BytecodeParser::ParseModuleGlobalInfo(const uchar *&Buf, const uchar *End,
371                                            Module *Mod) {
372   if (!FunctionSignatureList.empty()) {
373     Error = "Two ModuleGlobalInfo packets found!";
374     return true;  // Two ModuleGlobal blocks?
375   }
376
377   // Read global variables...
378   unsigned VarType;
379   if (read_vbr(Buf, End, VarType)) return true;
380   while (VarType != Type::VoidTyID) { // List is terminated by Void
381     // VarType Fields: bit0 = isConstant, bit1 = hasInitializer,
382     // bit2 = isInternal, bit3+ = slot#
383     const Type *Ty = getType(VarType >> 3);
384     if (!Ty || !isa<PointerType>(Ty)) { 
385       Error = "Global not pointer type!  Ty = " + Ty->getDescription();
386       return true; 
387     }
388
389     const PointerType *PTy = cast<const PointerType>(Ty);
390     const Type *ElTy = PTy->getElementType();
391
392     Constant *Initializer = 0;
393     if (VarType & 2) { // Does it have an initalizer?
394       // Do not improvise... values must have been stored in the constant pool,
395       // which should have been read before now.
396       //
397       unsigned InitSlot;
398       if (read_vbr(Buf, End, InitSlot)) return true;
399       
400       Value *V = getValue(ElTy, InitSlot, false);
401       if (V == 0) return true;
402       Initializer = cast<Constant>(V);
403     }
404
405     // Create the global variable...
406     GlobalVariable *GV = new GlobalVariable(ElTy, VarType & 1, VarType & 4,
407                                             Initializer);
408     int DestSlot = insertValue(GV, ModuleValues);
409     if (DestSlot == -1) return true;
410
411     Mod->getGlobalList().push_back(GV);
412
413     ResolveReferencesToValue(GV, (unsigned)DestSlot);
414
415     BCR_TRACE(2, "Global Variable of type: " << PTy->getDescription() 
416               << " into slot #" << DestSlot << "\n");
417
418     if (read_vbr(Buf, End, VarType)) return true;
419   }
420
421   // Read the method signatures for all of the methods that are coming, and 
422   // create fillers in the Value tables.
423   unsigned FnSignature;
424   if (read_vbr(Buf, End, FnSignature)) return true;
425   while (FnSignature != Type::VoidTyID) { // List is terminated by Void
426     const Type *Ty = getType(FnSignature);
427     if (!Ty || !isa<PointerType>(Ty) ||
428         !isa<FunctionType>(cast<PointerType>(Ty)->getElementType())) { 
429       Error = "Function not ptr to func type!  Ty = " + Ty->getDescription();
430       return true; 
431     }
432     
433     // We create methods by passing the underlying FunctionType to create...
434     Ty = cast<PointerType>(Ty)->getElementType();
435
436     // When the ModuleGlobalInfo section is read, we load the type of each 
437     // method and the 'ModuleValues' slot that it lands in.  We then load a 
438     // placeholder into its slot to reserve it.  When the method is loaded, this
439     // placeholder is replaced.
440
441     // Insert the placeholder...
442     Value *Val = new FunctionPHolder(Ty, 0);
443     if (insertValue(Val, ModuleValues) == -1) return true;
444
445     // Figure out which entry of its typeslot it went into...
446     unsigned TypeSlot;
447     if (getTypeSlot(Val->getType(), TypeSlot)) return true;
448
449     unsigned SlotNo = ModuleValues[TypeSlot].size()-1;
450     
451     // Keep track of this information in a linked list that is emptied as 
452     // methods are loaded...
453     //
454     FunctionSignatureList.push_back(
455            make_pair(cast<const PointerType>(Val->getType()), SlotNo));
456     if (read_vbr(Buf, End, FnSignature)) return true;
457     BCR_TRACE(2, "Function of type: " << Ty << "\n");
458   }
459
460   if (align32(Buf, End)) return true;
461
462   // Now that the function signature list is set up, reverse it so that we can 
463   // remove elements efficiently from the back of the vector.
464   std::reverse(FunctionSignatureList.begin(), FunctionSignatureList.end());
465
466   // This is for future proofing... in the future extra fields may be added that
467   // we don't understand, so we transparently ignore them.
468   //
469   Buf = End;
470   return false;
471 }
472
473 bool BytecodeParser::ParseModule(const uchar *Buf, const uchar *EndBuf, 
474                                 Module *&Mod) {
475
476   unsigned Type, Size;
477   if (readBlock(Buf, EndBuf, Type, Size)) return true;
478   if (Type != BytecodeFormat::Module || Buf+Size != EndBuf) {
479     Error = "Expected Module packet!";
480     return true;                      // Hrm, not a class?
481   }
482
483   BCR_TRACE(0, "BLOCK BytecodeFormat::Module: {\n");
484   FunctionSignatureList.clear();                 // Just in case...
485
486   // Read into instance variables...
487   if (read_vbr(Buf, EndBuf, FirstDerivedTyID)) return true;
488   if (align32(Buf, EndBuf)) return true;
489   BCR_TRACE(1, "FirstDerivedTyID = " << FirstDerivedTyID << "\n");
490
491   TheModule = Mod = new Module();
492
493   while (Buf < EndBuf) {
494     const uchar *OldBuf = Buf;
495     if (readBlock(Buf, EndBuf, Type, Size)) { delete Mod; return true;}
496     switch (Type) {
497     case BytecodeFormat::ConstantPool:
498       BCR_TRACE(1, "BLOCK BytecodeFormat::ConstantPool: {\n");
499       if (ParseConstantPool(Buf, Buf+Size, ModuleValues, ModuleTypeValues)) {
500         delete Mod; return true;
501       }
502       break;
503
504     case BytecodeFormat::ModuleGlobalInfo:
505       BCR_TRACE(1, "BLOCK BytecodeFormat::ModuleGlobalInfo: {\n");
506
507       if (ParseModuleGlobalInfo(Buf, Buf+Size, Mod)) {
508         delete Mod; return true;
509       }
510       break;
511
512     case BytecodeFormat::Function: {
513       BCR_TRACE(1, "BLOCK BytecodeFormat::Function: {\n");
514       if (ParseMethod(Buf, Buf+Size, Mod)) {
515         delete Mod; return true;              // Error parsing function
516       }
517       break;
518     }
519
520     case BytecodeFormat::SymbolTable:
521       BCR_TRACE(1, "BLOCK BytecodeFormat::SymbolTable: {\n");
522       if (ParseSymbolTable(Buf, Buf+Size, Mod->getSymbolTableSure())) {
523         delete Mod; return true;
524       }
525       break;
526
527     default:
528       Error = "Expected Module Block!";
529       Buf += Size;
530       if (OldBuf > Buf) return true; // Wrap around!
531       break;
532     }
533     BCR_TRACE(1, "} end block\n");
534     if (align32(Buf, EndBuf)) { delete Mod; return true; }
535   }
536
537   if (!FunctionSignatureList.empty()) {     // Expected more methods!
538     Error = "Function expected, but bytecode stream at end!";
539     return true;
540   }
541
542   BCR_TRACE(0, "} end block\n\n");
543   return false;
544 }
545
546 Module *BytecodeParser::ParseBytecode(const uchar *Buf, const uchar *EndBuf) {
547   LateResolveValues.clear();
548   unsigned Sig;
549   // Read and check signature...
550   if (read(Buf, EndBuf, Sig) ||
551       Sig != ('l' | ('l' << 8) | ('v' << 16) | 'm' << 24)) {
552     Error = "Invalid bytecode signature!";
553     return 0;                          // Invalid signature!
554   }
555
556   Module *Result;
557   if (ParseModule(Buf, EndBuf, Result)) return 0;
558   return Result;
559 }
560
561
562 Module *ParseBytecodeBuffer(const unsigned char *Buffer, unsigned Length) {
563   BytecodeParser Parser;
564   return Parser.ParseBytecode(Buffer, Buffer+Length);
565 }
566
567 // Parse and return a class file...
568 //
569 Module *ParseBytecodeFile(const std::string &Filename, std::string *ErrorStr) {
570   struct stat StatBuf;
571   Module *Result = 0;
572
573   if (Filename != std::string("-")) {        // Read from a file...
574     int FD = open(Filename.c_str(), O_RDONLY);
575     if (FD == -1) {
576       if (ErrorStr) *ErrorStr = "Error opening file!";
577       return 0;
578     }
579
580     if (fstat(FD, &StatBuf) == -1) { close(FD); return 0; }
581
582     int Length = StatBuf.st_size;
583     if (Length == 0) { 
584       if (ErrorStr) *ErrorStr = "Error stat'ing file!";
585       close(FD); return 0; 
586     }
587     uchar *Buffer = (uchar*)mmap(0, Length, PROT_READ, 
588                                 MAP_PRIVATE, FD, 0);
589     if (Buffer == (uchar*)-1) {
590       if (ErrorStr) *ErrorStr = "Error mmapping file!";
591       close(FD); return 0;
592     }
593
594     BytecodeParser Parser;
595     Result  = Parser.ParseBytecode(Buffer, Buffer+Length);
596
597     munmap((char*)Buffer, Length);
598     close(FD);
599     if (ErrorStr) *ErrorStr = Parser.getError();
600   } else {                              // Read from stdin
601     size_t FileSize = 0;
602     int BlockSize;
603     uchar Buffer[4096], *FileData = 0;
604     while ((BlockSize = read(0, Buffer, 4))) {
605       if (BlockSize == -1) { free(FileData); return 0; }
606
607       FileData = (uchar*)realloc(FileData, FileSize+BlockSize);
608       memcpy(FileData+FileSize, Buffer, BlockSize);
609       FileSize += BlockSize;
610     }
611
612     if (FileSize == 0) {
613       if (ErrorStr) *ErrorStr = "Standard Input empty!";
614       free(FileData); return 0;
615     }
616
617 #define ALIGN_PTRS 0
618 #if ALIGN_PTRS
619     uchar *Buf = (uchar*)mmap(0, FileSize, PROT_READ|PROT_WRITE, 
620                               MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
621     assert((Buf != (uchar*)-1) && "mmap returned error!");
622     memcpy(Buf, FileData, FileSize);
623     free(FileData);
624 #else
625     uchar *Buf = FileData;
626 #endif
627
628     BytecodeParser Parser;
629     Result = Parser.ParseBytecode(Buf, Buf+FileSize);
630
631 #if ALIGN_PTRS
632     munmap((char*)Buf, FileSize);   // Free mmap'd data area
633 #else
634     free(FileData);          // Free realloc'd block of memory
635 #endif
636
637     if (ErrorStr) *ErrorStr = Parser.getError();
638   }
639
640   return Result;
641 }