contrib/llvm/lib/Bitcode/Reader/ValueList.cpp

   1 //===----- ValueList.cpp - Internal BitcodeReader implementation ----------===//
   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 #include "ValueList.h"
  11 #include "llvm/IR/Constants.h"
  12 #include "llvm/IR/Instructions.h"
  13
  14 using namespace llvm;
  15
  16 namespace llvm {
  17 namespace {
  18
  19 /// \brief A class for maintaining the slot number definition
  20 /// as a placeholder for the actual definition for forward constants defs.
  21 class ConstantPlaceHolder : public ConstantExpr {
  22   void operator=(const ConstantPlaceHolder &) = delete;
  23
  24 public:
  25   // allocate space for exactly one operand
  26   void *operator new(size_t s) { return User::operator new(s, 1); }
  27   explicit ConstantPlaceHolder(Type *Ty, LLVMContext &Context)
  28       : ConstantExpr(Ty, Instruction::UserOp1, &Op<0>(), 1) {
  29     Op<0>() = UndefValue::get(Type::getInt32Ty(Context));
  30   }
  31
  32   /// \brief Methods to support type inquiry through isa, cast, and dyn_cast.
  33   static bool classof(const Value *V) {
  34     return isa<ConstantExpr>(V) &&
  35            cast<ConstantExpr>(V)->getOpcode() == Instruction::UserOp1;
  36   }
  37
  38   /// Provide fast operand accessors
  39   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
  40 };
  41
  42 } // end anonymous namespace
  43
  44 // FIXME: can we inherit this from ConstantExpr?
  45 template <>
  46 struct OperandTraits<ConstantPlaceHolder>
  47     : public FixedNumOperandTraits<ConstantPlaceHolder, 1> {};
  48 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantPlaceHolder, Value)
  49
  50 } // end namespace llvm
  51
  52 void BitcodeReaderValueList::assignValue(Value *V, unsigned Idx) {
  53   if (Idx == size()) {
  54     push_back(V);
  55     return;
  56   }
  57
  58   if (Idx >= size())
  59     resize(Idx + 1);
  60
  61   WeakVH &OldV = ValuePtrs[Idx];
  62   if (!OldV) {
  63     OldV = V;
  64     return;
  65   }
  66
  67   // Handle constants and non-constants (e.g. instrs) differently for
  68   // efficiency.
  69   if (Constant *PHC = dyn_cast<Constant>(&*OldV)) {
  70     ResolveConstants.push_back(std::make_pair(PHC, Idx));
  71     OldV = V;
  72   } else {
  73     // If there was a forward reference to this value, replace it.
  74     Value *PrevVal = OldV;
  75     OldV->replaceAllUsesWith(V);
  76     delete PrevVal;
  77   }
  78 }
  79
  80 Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx, Type *Ty) {
  81   if (Idx >= size())
  82     resize(Idx + 1);
  83
  84   if (Value *V = ValuePtrs[Idx]) {
  85     if (Ty != V->getType())
  86       report_fatal_error("Type mismatch in constant table!");
  87     return cast<Constant>(V);
  88   }
  89
  90   // Create and return a placeholder, which will later be RAUW'd.
  91   Constant *C = new ConstantPlaceHolder(Ty, Context);
  92   ValuePtrs[Idx] = C;
  93   return C;
  94 }
  95
  96 Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty) {
  97   // Bail out for a clearly invalid value. This would make us call resize(0)
  98   if (Idx == std::numeric_limits<unsigned>::max())
  99     return nullptr;
 100
 101   if (Idx >= size())
 102     resize(Idx + 1);
 103
 104   if (Value *V = ValuePtrs[Idx]) {
 105     // If the types don't match, it's invalid.
 106     if (Ty && Ty != V->getType())
 107       return nullptr;
 108     return V;
 109   }
 110
 111   // No type specified, must be invalid reference.
 112   if (!Ty)
 113     return nullptr;
 114
 115   // Create and return a placeholder, which will later be RAUW'd.
 116   Value *V = new Argument(Ty);
 117   ValuePtrs[Idx] = V;
 118   return V;
 119 }
 120
 121 /// Once all constants are read, this method bulk resolves any forward
 122 /// references.  The idea behind this is that we sometimes get constants (such
 123 /// as large arrays) which reference *many* forward ref constants.  Replacing
 124 /// each of these causes a lot of thrashing when building/reuniquing the
 125 /// constant.  Instead of doing this, we look at all the uses and rewrite all
 126 /// the place holders at once for any constant that uses a placeholder.
 127 void BitcodeReaderValueList::resolveConstantForwardRefs() {
 128   // Sort the values by-pointer so that they are efficient to look up with a
 129   // binary search.
 130   std::sort(ResolveConstants.begin(), ResolveConstants.end());
 131
 132   SmallVector<Constant *, 64> NewOps;
 133
 134   while (!ResolveConstants.empty()) {
 135     Value *RealVal = operator[](ResolveConstants.back().second);
 136     Constant *Placeholder = ResolveConstants.back().first;
 137     ResolveConstants.pop_back();
 138
 139     // Loop over all users of the placeholder, updating them to reference the
 140     // new value.  If they reference more than one placeholder, update them all
 141     // at once.
 142     while (!Placeholder->use_empty()) {
 143       auto UI = Placeholder->user_begin();
 144       User *U = *UI;
 145
 146       // If the using object isn't uniqued, just update the operands.  This
 147       // handles instructions and initializers for global variables.
 148       if (!isa<Constant>(U) || isa<GlobalValue>(U)) {
 149         UI.getUse().set(RealVal);
 150         continue;
 151       }
 152
 153       // Otherwise, we have a constant that uses the placeholder.  Replace that
 154       // constant with a new constant that has *all* placeholder uses updated.
 155       Constant *UserC = cast<Constant>(U);
 156       for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end(); I != E;
 157            ++I) {
 158         Value *NewOp;
 159         if (!isa<ConstantPlaceHolder>(*I)) {
 160           // Not a placeholder reference.
 161           NewOp = *I;
 162         } else if (*I == Placeholder) {
 163           // Common case is that it just references this one placeholder.
 164           NewOp = RealVal;
 165         } else {
 166           // Otherwise, look up the placeholder in ResolveConstants.
 167           ResolveConstantsTy::iterator It = std::lower_bound(
 168               ResolveConstants.begin(), ResolveConstants.end(),
 169               std::pair<Constant *, unsigned>(cast<Constant>(*I), 0));
 170           assert(It != ResolveConstants.end() && It->first == *I);
 171           NewOp = operator[](It->second);
 172         }
 173
 174         NewOps.push_back(cast<Constant>(NewOp));
 175       }
 176
 177       // Make the new constant.
 178       Constant *NewC;
 179       if (ConstantArray *UserCA = dyn_cast<ConstantArray>(UserC)) {
 180         NewC = ConstantArray::get(UserCA->getType(), NewOps);
 181       } else if (ConstantStruct *UserCS = dyn_cast<ConstantStruct>(UserC)) {
 182         NewC = ConstantStruct::get(UserCS->getType(), NewOps);
 183       } else if (isa<ConstantVector>(UserC)) {
 184         NewC = ConstantVector::get(NewOps);
 185       } else {
 186         assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr.");
 187         NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps);
 188       }
 189
 190       UserC->replaceAllUsesWith(NewC);
 191       UserC->destroyConstant();
 192       NewOps.clear();
 193     }
 194
 195     // Update all ValueHandles, they should be the only users at this point.
 196     Placeholder->replaceAllUsesWith(RealVal);
 197     delete Placeholder;
 198   }
 199 }