lib/Bitcode/Reader/Deserialize.cpp

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