lib/Bitcode/Reader/ValueList.cpp

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