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