[Bitcode] Support expanding constant expressions into instructions

This implements an autoupgrade from constant expressions to
instructions, which is needed for
https://discourse.llvm.org/t/rfc-remove-most-constant-expressions/63179.

The basic approach is that constant expressions (CST_CODE_CE_*
records) now initially only create a BitcodeConstant value that
holds opcode, flags and operands IDs. Then, when the value actually
gets used, it can be converted either into a constant expression
(if that expression type is still supported) or into a sequence of
instructions. As currently all expressions are still supported,
-expand-constant-exprs is added for testing purposes, to force
expansion.

PHI nodes require special handling, because the constant expression
needs to be evaluated on the incoming edge. We do this by putting
it into a temporary block and then wiring it up appropriately
afterwards (for non-critical edges, we could also move the
instructions into the predecessor).

This also removes the need for the forward referenced constants
machinery, as the BitcodeConstants only hold value IDs. At the
point where the value is actually materialized, no forward
references are needed anymore.

Differential Revision: https://reviews.llvm.org/D127729

1 files changed, 19 insertions, 157 deletions

diff --git a/llvm/lib/Bitcode/Reader/ValueList.cpp b/llvm/lib/Bitcode/Reader/ValueList.cpp
index 010108b06bcc..b9dbf904c89e 100644
--- a/llvm/lib/Bitcode/Reader/ValueList.cpp
+++ b/llvm/lib/Bitcode/Reader/ValueList.cpp
@@ -23,44 +23,6 @@
 
 using namespace llvm;
 
-namespace llvm {
-
-namespace {
-
-/// A class for maintaining the slot number definition
-/// as a placeholder for the actual definition for forward constants defs.
-class ConstantPlaceHolder : public ConstantExpr {
-public:
-  explicit ConstantPlaceHolder(Type *Ty, LLVMContext &Context)
-      : ConstantExpr(Ty, Instruction::UserOp1, &Op<0>(), 1) {
-    Op<0>() = UndefValue::get(Type::getInt32Ty(Context));
-  }
-
-  ConstantPlaceHolder &operator=(const ConstantPlaceHolder &) = delete;
-
-  // allocate space for exactly one operand
-  void *operator new(size_t s) { return User::operator new(s, 1); }
-
-  /// Methods to support type inquiry through isa, cast, and dyn_cast.
-  static bool classof(const Value *V) {
-    return isa<ConstantExpr>(V) &&
-           cast<ConstantExpr>(V)->getOpcode() == Instruction::UserOp1;
-  }
-
-  /// Provide fast operand accessors
-  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
-};
-
-} // end anonymous namespace
-
-// FIXME: can we inherit this from ConstantExpr?
-template <>
-struct OperandTraits<ConstantPlaceHolder>
-    : public FixedNumOperandTraits<ConstantPlaceHolder, 1> {};
-DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantPlaceHolder, Value)
-
-} // end namespace llvm
-
 Error BitcodeReaderValueList::assignValue(unsigned Idx, Value *V,
                                           unsigned TypeID) {
   if (Idx == size()) {
@@ -78,48 +40,21 @@ Error BitcodeReaderValueList::assignValue(unsigned Idx, Value *V,
     return Error::success();
   }
 
-  // Handle constants and non-constants (e.g. instrs) differently for
-  // efficiency.
-  if (Constant *PHC = dyn_cast<Constant>(&*Old.first)) {
-    ResolveConstants.push_back(std::make_pair(PHC, Idx));
-    Old.first = V;
-    Old.second = TypeID;
-  } else {
-    // If there was a forward reference to this value, replace it.
-    Value *PrevVal = Old.first;
-    if (PrevVal->getType() != V->getType())
-      return createStringError(
-          std::errc::illegal_byte_sequence,
-          "Assigned value does not match type of forward declaration");
-    Old.first->replaceAllUsesWith(V);
-    PrevVal->deleteValue();
-  }
+  assert(!isa<Constant>(&*Old.first) && "Shouldn't update constant");
+  // If there was a forward reference to this value, replace it.
+  Value *PrevVal = Old.first;
+  if (PrevVal->getType() != V->getType())
+    return createStringError(
+        std::errc::illegal_byte_sequence,
+        "Assigned value does not match type of forward declaration");
+  Old.first->replaceAllUsesWith(V);
+  PrevVal->deleteValue();
   return Error::success();
 }
 
-Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx, Type *Ty,
-                                                    unsigned TyID) {
-  // Bail out for a clearly invalid value.
-  if (Idx >= RefsUpperBound)
-    return nullptr;
-
-  if (Idx >= size())
-    resize(Idx + 1);
-
-  if (Value *V = ValuePtrs[Idx].first) {
-    if (Ty != V->getType())
-      report_fatal_error("Type mismatch in constant table!");
-    return cast<Constant>(V);
-  }
-
-  // Create and return a placeholder, which will later be RAUW'd.
-  Constant *C = new ConstantPlaceHolder(Ty, Context);
-  ValuePtrs[Idx] = {C, TyID};
-  return C;
-}
-
 Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty,
-                                              unsigned TyID) {
+                                              unsigned TyID,
+                                              BasicBlock *ConstExprInsertBB) {
   // Bail out for a clearly invalid value.
   if (Idx >= RefsUpperBound)
     return nullptr;
@@ -131,7 +66,14 @@ Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty,
     // If the types don't match, it's invalid.
     if (Ty && Ty != V->getType())
       return nullptr;
-    return V;
+
+    Expected<Value *> MaybeV = MaterializeValueFn(Idx, ConstExprInsertBB);
+    if (!MaybeV) {
+      // TODO: We might want to propagate the precise error message here.
+      consumeError(MaybeV.takeError());
+      return nullptr;
+    }
+    return MaybeV.get();
   }
 
   // No type specified, must be invalid reference.
@@ -143,83 +85,3 @@ Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty,
   ValuePtrs[Idx] = {V, TyID};
   return V;
 }
-
-/// Once all constants are read, this method bulk resolves any forward
-/// references.  The idea behind this is that we sometimes get constants (such
-/// as large arrays) which reference *many* forward ref constants.  Replacing
-/// each of these causes a lot of thrashing when building/reuniquing the
-/// constant.  Instead of doing this, we look at all the uses and rewrite all
-/// the place holders at once for any constant that uses a placeholder.
-void BitcodeReaderValueList::resolveConstantForwardRefs() {
-  // Sort the values by-pointer so that they are efficient to look up with a
-  // binary search.
-  llvm::sort(ResolveConstants);
-
-  SmallVector<Constant *, 64> NewOps;
-
-  while (!ResolveConstants.empty()) {
-    Value *RealVal = operator[](ResolveConstants.back().second);
-    Constant *Placeholder = ResolveConstants.back().first;
-    ResolveConstants.pop_back();
-
-    // Loop over all users of the placeholder, updating them to reference the
-    // new value.  If they reference more than one placeholder, update them all
-    // at once.
-    while (!Placeholder->use_empty()) {
-      auto UI = Placeholder->user_begin();
-      User *U = *UI;
-
-      // If the using object isn't uniqued, just update the operands.  This
-      // handles instructions and initializers for global variables.
-      if (!isa<Constant>(U) || isa<GlobalValue>(U)) {
-        UI.getUse().set(RealVal);
-        continue;
-      }
-
-      // Otherwise, we have a constant that uses the placeholder.  Replace that
-      // constant with a new constant that has *all* placeholder uses updated.
-      Constant *UserC = cast<Constant>(U);
-      for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end(); I != E;
-           ++I) {
-        Value *NewOp;
-        if (!isa<ConstantPlaceHolder>(*I)) {
-          // Not a placeholder reference.
-          NewOp = *I;
-        } else if (*I == Placeholder) {
-          // Common case is that it just references this one placeholder.
-          NewOp = RealVal;
-        } else {
-          // Otherwise, look up the placeholder in ResolveConstants.
-          ResolveConstantsTy::iterator It = llvm::lower_bound(
-              ResolveConstants,
-              std::pair<Constant *, unsigned>(cast<Constant>(*I), 0));
-          assert(It != ResolveConstants.end() && It->first == *I);
-          NewOp = operator[](It->second);
-        }
-
-        NewOps.push_back(cast<Constant>(NewOp));
-      }
-
-      // Make the new constant.
-      Constant *NewC;
-      if (ConstantArray *UserCA = dyn_cast<ConstantArray>(UserC)) {
-        NewC = ConstantArray::get(UserCA->getType(), NewOps);
-      } else if (ConstantStruct *UserCS = dyn_cast<ConstantStruct>(UserC)) {
-        NewC = ConstantStruct::get(UserCS->getType(), NewOps);
-      } else if (isa<ConstantVector>(UserC)) {
-        NewC = ConstantVector::get(NewOps);
-      } else {
-        assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr.");
-        NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps);
-      }
-
-      UserC->replaceAllUsesWith(NewC);
-      UserC->destroyConstant();
-      NewOps.clear();
-    }
-
-    // Update all ValueHandles, they should be the only users at this point.
-    Placeholder->replaceAllUsesWith(RealVal);
-    delete cast<ConstantPlaceHolder>(Placeholder);
-  }
-}