lib/Bitcode/Reader/Deserialize.cpp

   1 //==- Deserialize.cpp - Generic Object Serialization to Bitcode --*- C++ -*-==//
   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 defines the internal methods used for object serialization.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Bitcode/Deserialize.h"
  15
  16 #ifdef DEBUG_BACKPATCH
  17 #include "llvm/Support/Streams.h"
  18 #endif
  19
  20 using namespace llvm;
  21
  22 Deserializer::Deserializer(BitstreamReader& stream)
  23   : Stream(stream), RecIdx(0), FreeList(NULL), AbbrevNo(0), RecordCode(0) {
  24
  25     StreamStart = Stream.GetCurrentBitNo();
  26 }
  27
  28 Deserializer::~Deserializer() {
  29   assert (RecIdx >= Record.size() &&
  30           "Still scanning bitcode record when deserialization completed.");
  31
  32 #ifdef DEBUG_BACKPATCH
  33   for (MapTy::iterator I=BPatchMap.begin(), E=BPatchMap.end(); I!=E; ++I)
  34     assert (I->first.hasFinalPtr() &&
  35             "Some pointers were not backpatched.");
  36 #endif
  37 }
  38
  39
  40 bool Deserializer::inRecord() {
  41   if (Record.size() > 0) {
  42     if (RecIdx >= Record.size()) {
  43       RecIdx = 0;
  44       Record.clear();
  45       AbbrevNo = 0;
  46       return false;
  47     }
  48     else
  49       return true;
  50   }
  51
  52   return false;
  53 }
  54
  55 bool Deserializer::AdvanceStream() {
  56   assert (!inRecord() &&
  57           "Cannot advance stream.  Still processing a record.");
  58
  59   if (AbbrevNo == bitc::ENTER_SUBBLOCK ||
  60       AbbrevNo >= bitc::UNABBREV_RECORD)
  61     return true;
  62
  63   while (!Stream.AtEndOfStream()) {
  64
  65     uint64_t Pos = Stream.GetCurrentBitNo();
  66     AbbrevNo = Stream.ReadCode();
  67
  68     switch (AbbrevNo) {
  69       case bitc::ENTER_SUBBLOCK: {
  70         unsigned id = Stream.ReadSubBlockID();
  71
  72         // Determine the extent of the block.  This is useful for jumping around
  73         // the stream.  This is hack: we read the header of the block, save
  74         // the length, and then revert the bitstream to a location just before
  75         // the block is entered.
  76         uint64_t BPos = Stream.GetCurrentBitNo();
  77         Stream.ReadVBR(bitc::CodeLenWidth); // Skip the code size.
  78         Stream.SkipToWord();
  79         unsigned NumWords = Stream.Read(bitc::BlockSizeWidth);
  80         Stream.JumpToBit(BPos);
  81
  82         BlockStack.push_back(Location(Pos,id,NumWords));
  83         break;
  84       }
  85
  86       case bitc::END_BLOCK: {
  87         bool x = Stream.ReadBlockEnd();
  88         assert(!x && "Error at block end."); x=x;
  89         BlockStack.pop_back();
  90         continue;
  91       }
  92
  93       case bitc::DEFINE_ABBREV:
  94         Stream.ReadAbbrevRecord();
  95         continue;
  96
  97       default:
  98         break;
  99     }
 100
 101     return true;
 102   }
 103
 104   return false;
 105 }
 106
 107 void Deserializer::ReadRecord() {
 108
 109   while (AdvanceStream() && AbbrevNo == bitc::ENTER_SUBBLOCK) {
 110     assert (!BlockStack.empty());
 111     Stream.EnterSubBlock(BlockStack.back().BlockID);
 112     AbbrevNo = 0;
 113   }
 114
 115   if (Stream.AtEndOfStream())
 116     return;
 117
 118   assert (Record.empty());
 119   assert (AbbrevNo >= bitc::UNABBREV_RECORD);
 120   RecordCode = Stream.ReadRecord(AbbrevNo,Record);
 121   assert (Record.size() > 0);
 122 }
 123
 124 void Deserializer::SkipBlock() {
 125   assert (!inRecord());
 126
 127   if (AtEnd())
 128     return;
 129
 130   AdvanceStream();
 131
 132   assert (AbbrevNo == bitc::ENTER_SUBBLOCK);
 133   BlockStack.pop_back();
 134   Stream.SkipBlock();
 135
 136   AbbrevNo = 0;
 137   AdvanceStream();
 138 }
 139
 140 bool Deserializer::SkipToBlock(unsigned BlockID) {
 141   assert (!inRecord());
 142
 143   AdvanceStream();
 144   assert (AbbrevNo == bitc::ENTER_SUBBLOCK);
 145
 146   unsigned BlockLevel = BlockStack.size();
 147
 148   while (!AtEnd() &&
 149          BlockLevel == BlockStack.size() &&
 150          getCurrentBlockID() != BlockID)
 151     SkipBlock();
 152
 153   return !(AtEnd() || BlockLevel != BlockStack.size());
 154 }
 155
 156 Deserializer::Location Deserializer::getCurrentBlockLocation() {
 157   if (!inRecord())
 158     AdvanceStream();
 159
 160   return BlockStack.back();
 161 }
 162
 163 bool Deserializer::JumpTo(const Location& Loc) {
 164
 165   assert (!inRecord());
 166
 167   AdvanceStream();
 168
 169   assert (!BlockStack.empty() || AtEnd());
 170
 171   uint64_t LastBPos = StreamStart;
 172
 173   while (!BlockStack.empty()) {
 174
 175     LastBPos = BlockStack.back().BitNo;
 176
 177     // Determine of the current block contains the location of the block
 178     // we are looking for.
 179     if (BlockStack.back().contains(Loc)) {
 180       // We found the enclosing block.  We must first POP it off to
 181       // destroy any accumulated context within the block scope.  We then
 182       // jump to the position of the block and enter it.
 183       Stream.JumpToBit(LastBPos);
 184
 185       if (BlockStack.size() == Stream.BlockScope.size())
 186         Stream.PopBlockScope();
 187
 188       BlockStack.pop_back();
 189
 190       AbbrevNo = 0;
 191       AdvanceStream();
 192       assert (AbbrevNo == bitc::ENTER_SUBBLOCK);
 193
 194       Stream.EnterSubBlock(BlockStack.back().BlockID);
 195       break;
 196     }
 197
 198     // This block does not contain the block we are looking for.  Pop it.
 199     if (BlockStack.size() == Stream.BlockScope.size())
 200       Stream.PopBlockScope();
 201
 202     BlockStack.pop_back();
 203
 204   }
 205
 206   // Check if we have popped our way to the outermost scope.  If so,
 207   // we need to adjust our position.
 208   if (BlockStack.empty()) {
 209     assert (Stream.BlockScope.empty());
 210
 211     Stream.JumpToBit(Loc.BitNo < LastBPos ? StreamStart : LastBPos);
 212     AbbrevNo = 0;
 213     AdvanceStream();
 214   }
 215
 216   assert (AbbrevNo == bitc::ENTER_SUBBLOCK);
 217   assert (!BlockStack.empty());
 218
 219   while (!AtEnd() && BlockStack.back() != Loc) {
 220     if (BlockStack.back().contains(Loc)) {
 221       Stream.EnterSubBlock(BlockStack.back().BlockID);
 222       AbbrevNo = 0;
 223       AdvanceStream();
 224       continue;
 225     }
 226     else
 227       SkipBlock();
 228   }
 229
 230   if (AtEnd())
 231     return false;
 232
 233   assert (BlockStack.back() == Loc);
 234
 235   return true;
 236 }
 237
 238 void Deserializer::Rewind() {
 239   while (!Stream.BlockScope.empty())
 240     Stream.PopBlockScope();
 241
 242   while (!BlockStack.empty())
 243     BlockStack.pop_back();
 244
 245   Stream.JumpToBit(StreamStart);
 246   AbbrevNo = 0;
 247 }
 248
 249
 250 unsigned Deserializer::getCurrentBlockID() {
 251   if (!inRecord())
 252     AdvanceStream();
 253
 254   return BlockStack.back().BlockID;
 255 }
 256
 257 unsigned Deserializer::getRecordCode() {
 258   if (!inRecord()) {
 259     AdvanceStream();
 260     assert (AbbrevNo >= bitc::UNABBREV_RECORD);
 261     ReadRecord();
 262   }
 263
 264   return RecordCode;
 265 }
 266
 267 bool Deserializer::FinishedBlock(Location BlockLoc) {
 268   if (!inRecord())
 269     AdvanceStream();
 270
 271   for (llvm::SmallVector<Location,8>::reverse_iterator
 272         I=BlockStack.rbegin(), E=BlockStack.rend(); I!=E; ++I)
 273       if (*I == BlockLoc)
 274         return false;
 275
 276   return true;
 277 }
 278
 279 unsigned Deserializer::getAbbrevNo() {
 280   if (!inRecord())
 281     AdvanceStream();
 282
 283   return AbbrevNo;
 284 }
 285
 286 bool Deserializer::AtEnd() {
 287   if (inRecord())
 288     return false;
 289
 290   if (!AdvanceStream())
 291     return true;
 292
 293   return false;
 294 }
 295
 296 uint64_t Deserializer::ReadInt() {
 297   // FIXME: Any error recovery/handling with incomplete or bad files?
 298   if (!inRecord())
 299     ReadRecord();
 300
 301   return Record[RecIdx++];
 302 }
 303
 304 int64_t Deserializer::ReadSInt() {
 305   uint64_t x = ReadInt();
 306   int64_t magnitude = x >> 1;
 307   return x & 0x1 ? -magnitude : magnitude;
 308 }
 309
 310 char* Deserializer::ReadCStr(char* cstr, unsigned MaxLen, bool isNullTerm) {
 311   if (cstr == NULL)
 312     MaxLen = 0; // Zero this just in case someone does something funny.
 313
 314   unsigned len = ReadInt();
 315
 316   assert (MaxLen == 0 || (len + (isNullTerm ? 1 : 0)) <= MaxLen);
 317
 318   if (!cstr)
 319     cstr = new char[len + (isNullTerm ? 1 : 0)];
 320
 321   assert (cstr != NULL);
 322
 323   for (unsigned i = 0; i < len; ++i)
 324     cstr[i] = (char) ReadInt();
 325
 326   if (isNullTerm)
 327     cstr[len] = '\0';
 328
 329   return cstr;
 330 }
 331
 332 void Deserializer::ReadCStr(std::vector<char>& buff, bool isNullTerm,
 333                             unsigned Idx) {
 334
 335   unsigned len = ReadInt();
 336
 337   // If Idx is beyond the current before size, reduce Idx to refer to the
 338   // element after the last element.
 339   if (Idx > buff.size())
 340     Idx = buff.size();
 341
 342   buff.reserve(len+Idx);
 343   buff.resize(Idx);
 344
 345   for (unsigned i = 0; i < len; ++i)
 346     buff.push_back((char) ReadInt());
 347
 348   if (isNullTerm)
 349     buff.push_back('\0');
 350 }
 351
 352 void Deserializer::RegisterPtr(const SerializedPtrID& PtrId,
 353                                const void* Ptr) {
 354
 355   MapTy::value_type& E = BPatchMap.FindAndConstruct(BPKey(PtrId));
 356
 357   assert (!HasFinalPtr(E) && "Pointer already registered.");
 358
 359 #ifdef DEBUG_BACKPATCH
 360   llvm::cerr << "RegisterPtr: " << PtrId << " => " << Ptr << "\n";
 361 #endif
 362
 363   SetPtr(E,Ptr);
 364 }
 365
 366 void Deserializer::ReadUIntPtr(uintptr_t& PtrRef,
 367                                const SerializedPtrID& PtrId,
 368                                bool AllowBackpatch) {
 369   if (PtrId == 0) {
 370     PtrRef = 0;
 371     return;
 372   }
 373
 374   MapTy::value_type& E = BPatchMap.FindAndConstruct(BPKey(PtrId));
 375
 376   if (HasFinalPtr(E)) {
 377     PtrRef = GetFinalPtr(E);
 378
 379 #ifdef DEBUG_BACKPATCH
 380     llvm::cerr << "ReadUintPtr: " << PtrId
 381                << " <-- " <<  (void*) GetFinalPtr(E) << '\n';
 382 #endif
 383   }
 384   else {
 385     assert (AllowBackpatch &&
 386             "Client forbids backpatching for this pointer.");
 387
 388 #ifdef DEBUG_BACKPATCH
 389     llvm::cerr << "ReadUintPtr: " << PtrId << " (NO PTR YET)\n";
 390 #endif
 391
 392     // Register backpatch.  Check the freelist for a BPNode.
 393     BPNode* N;
 394
 395     if (FreeList) {
 396       N = FreeList;
 397       FreeList = FreeList->Next;
 398     }
 399     else // No available BPNode.  Allocate one.
 400       N = (BPNode*) Allocator.Allocate<BPNode>();
 401
 402     new (N) BPNode(GetBPNode(E),PtrRef);
 403     SetBPNode(E,N);
 404   }
 405 }
 406
 407 uintptr_t Deserializer::ReadInternalRefPtr() {
 408   SerializedPtrID PtrId = ReadPtrID();
 409
 410   assert (PtrId != 0 && "References cannot refer the NULL address.");
 411
 412   MapTy::value_type& E = BPatchMap.FindAndConstruct(BPKey(PtrId));
 413
 414   assert (HasFinalPtr(E) &&
 415           "Cannot backpatch references.  Object must be already deserialized.");
 416
 417   return GetFinalPtr(E);
 418 }
 419
 420 void Deserializer::BPEntry::SetPtr(BPNode*& FreeList, void* P) {
 421   BPNode* Last = NULL;
 422
 423   for (BPNode* N = Head; N != NULL; N=N->Next) {
 424     Last = N;
 425     N->PtrRef |= reinterpret_cast<uintptr_t>(P);
 426   }
 427
 428   if (Last) {
 429     Last->Next = FreeList;
 430     FreeList = Head;
 431   }
 432
 433   Ptr = const_cast<void*>(P);
 434 }
 435
 436
 437 #define INT_READ(TYPE)\
 438 void SerializeTrait<TYPE>::Read(Deserializer& D, TYPE& X) {\
 439   X = (TYPE) D.ReadInt(); }
 440
 441 INT_READ(bool)
 442 INT_READ(unsigned char)
 443 INT_READ(unsigned short)
 444 INT_READ(unsigned int)
 445 INT_READ(unsigned long)
 446
 447 #define SINT_READ(TYPE)\
 448 void SerializeTrait<TYPE>::Read(Deserializer& D, TYPE& X) {\
 449   X = (TYPE) D.ReadSInt(); }
 450
 451 INT_READ(signed char)
 452 INT_READ(signed short)
 453 INT_READ(signed int)
 454 INT_READ(signed long)