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