Change the IR-generation of VLAs so that we capture bounds,

not sizes;  so that we use well-typed allocas;  and so that we
properly recurse through the full set of variably-modified types.



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@133827 91177308-0d34-0410-b5e6-96231b3b80d8

8 files changed, 187 insertions, 106 deletions

diff --git a/lib/CodeGen/CGDecl.cpp b/lib/CodeGen/CGDecl.cpp
index a12365e8e4..b6ad130a40 100644
--- a/lib/CodeGen/CGDecl.cpp
+++ b/lib/CodeGen/CGDecl.cpp
@@ -98,7 +98,7 @@ void CodeGenFunction::EmitDecl(const Decl &D) {
     QualType Ty = TD.getUnderlyingType();
 
     if (Ty->isVariablyModifiedType())
-      EmitVLASize(Ty);
+      EmitVariablyModifiedType(Ty);
   }
   }
 }
@@ -258,7 +258,7 @@ void CodeGenFunction::EmitStaticVarDecl(const VarDecl &D,
   // even though that doesn't really make any sense.
   // Make sure to evaluate VLA bounds now so that we have them for later.
   if (D.getType()->isVariablyModifiedType())
-    EmitVLASize(D.getType());
+    EmitVariablyModifiedType(D.getType());
   
   // Local static block variables must be treated as globals as they may be
   // referenced in their RHS initializer block-literal expresion.
@@ -699,6 +699,10 @@ CodeGenFunction::EmitAutoVarAlloca(const VarDecl &D) {
   CharUnits alignment = getContext().getDeclAlign(&D);
   emission.Alignment = alignment;
 
+  // If the type is variably-modified, emit all the VLA sizes for it.
+  if (Ty->isVariablyModifiedType())
+    EmitVariablyModifiedType(Ty);
+
   llvm::Value *DeclPtr;
   if (Ty->isConstantSizeType()) {
     if (!Target.useGlobalsForAutomaticVariables()) {
@@ -778,10 +782,6 @@ CodeGenFunction::EmitAutoVarAlloca(const VarDecl &D) {
       DeclPtr = CreateStaticVarDecl(D, Class,
                                     llvm::GlobalValue::InternalLinkage);
     }
-
-    // FIXME: Can this happen?
-    if (Ty->isVariablyModifiedType())
-      EmitVLASize(Ty);
   } else {
     EnsureInsertPoint();
 
@@ -801,19 +801,17 @@ CodeGenFunction::EmitAutoVarAlloca(const VarDecl &D) {
       EHStack.pushCleanup<CallStackRestore>(NormalCleanup, Stack);
     }
 
-    // Get the element type.
-    const llvm::Type *LElemTy = ConvertTypeForMem(Ty);
-    const llvm::Type *LElemPtrTy =
-      LElemTy->getPointerTo(CGM.getContext().getTargetAddressSpace(Ty));
+    llvm::Value *elementCount;
+    QualType elementType;
+    llvm::tie(elementCount, elementType) = getVLASize(Ty);
 
-    llvm::Value *VLASize = EmitVLASize(Ty);
+    const llvm::Type *llvmTy = ConvertTypeForMem(elementType);
 
     // Allocate memory for the array.
-    llvm::AllocaInst *VLA = 
-      Builder.CreateAlloca(llvm::Type::getInt8Ty(getLLVMContext()), VLASize, "vla");
-    VLA->setAlignment(alignment.getQuantity());
+    llvm::AllocaInst *vla = Builder.CreateAlloca(llvmTy, elementCount, "vla");
+    vla->setAlignment(alignment.getQuantity());
 
-    DeclPtr = Builder.CreateBitCast(VLA, LElemPtrTy, "tmp");
+    DeclPtr = vla;
   }
 
   llvm::Value *&DMEntry = LocalDeclMap[&D];
diff --git a/lib/CodeGen/CGExpr.cpp b/lib/CodeGen/CGExpr.cpp
index af0af7fbef..e8d156ea64 100644
--- a/lib/CodeGen/CGExpr.cpp
+++ b/lib/CodeGen/CGExpr.cpp
@@ -1579,21 +1579,22 @@ LValue CodeGenFunction::EmitArraySubscriptExpr(const ArraySubscriptExpr *E) {
   // size is a VLA or Objective-C interface.
   llvm::Value *Address = 0;
   unsigned ArrayAlignment = 0;
-  if (const VariableArrayType *VAT =
+  if (const VariableArrayType *vla =
         getContext().getAsVariableArrayType(E->getType())) {
-    llvm::Value *VLASize = GetVLASize(VAT);
+    // The base must be a pointer, which is not an aggregate.  Emit
+    // it.  It needs to be emitted first in case it's what captures
+    // the VLA bounds.
+    Address = EmitScalarExpr(E->getBase());
 
-    Idx = Builder.CreateMul(Idx, VLASize);
+    // The element count here is the total number of non-VLA elements.
+    llvm::Value *numElements = getVLASize(vla).first;
 
-    // The base must be a pointer, which is not an aggregate.  Emit it.
-    llvm::Value *Base = EmitScalarExpr(E->getBase());
+    Idx = Builder.CreateMul(Idx, numElements);
 
-    Address = EmitCastToVoidPtr(Base);
     if (getContext().getLangOptions().isSignedOverflowDefined())
       Address = Builder.CreateGEP(Address, Idx, "arrayidx");
     else
       Address = Builder.CreateInBoundsGEP(Address, Idx, "arrayidx");
-    Address = Builder.CreateBitCast(Address, Base->getType());
   } else if (const ObjCObjectType *OIT = E->getType()->getAs<ObjCObjectType>()){
     // Indexing over an interface, as in "NSString *P; P[4];"
     llvm::Value *InterfaceSize =
diff --git a/lib/CodeGen/CGExprScalar.cpp b/lib/CodeGen/CGExprScalar.cpp
index 6e42da8e01..7b4aecceb9 100644
--- a/lib/CodeGen/CGExprScalar.cpp
+++ b/lib/CodeGen/CGExprScalar.cpp
@@ -269,14 +269,12 @@ public:
   Value *VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E) {
     return CGF.CGM.EmitNullConstant(E->getType());
   }
-  Value *VisitCastExpr(CastExpr *E) {
-    // Make sure to evaluate VLA bounds now so that we have them for later.
+  Value *VisitExplicitCastExpr(ExplicitCastExpr *E) {
     if (E->getType()->isVariablyModifiedType())
-      CGF.EmitVLASize(E->getType());
-
-    return EmitCastExpr(E);
+      CGF.EmitVariablyModifiedType(E->getType());
+    return VisitCastExpr(E);
   }
-  Value *EmitCastExpr(CastExpr *E);
+  Value *VisitCastExpr(CastExpr *E);
 
   Value *VisitCallExpr(const CallExpr *E) {
     if (E->getCallReturnType()->isReferenceType())
@@ -1001,7 +999,7 @@ static bool ShouldNullCheckClassCastValue(const CastExpr *CE) {
 // VisitCastExpr - Emit code for an explicit or implicit cast.  Implicit casts
 // have to handle a more broad range of conversions than explicit casts, as they
 // handle things like function to ptr-to-function decay etc.
-Value *ScalarExprEmitter::EmitCastExpr(CastExpr *CE) {
+Value *ScalarExprEmitter::VisitCastExpr(CastExpr *CE) {
   Expr *E = CE->getSubExpr();
   QualType DestTy = CE->getType();
   CastKind Kind = CE->getCastKind();
@@ -1298,15 +1296,12 @@ ScalarExprEmitter::EmitScalarPrePostIncDec(const UnaryOperator *E, LValue LV,
 
     // VLA types don't have constant size.
     if (type->isVariableArrayType()) {
-      llvm::Value *vlaSize =
-        CGF.GetVLASize(CGF.getContext().getAsVariableArrayType(type));
-      value = CGF.EmitCastToVoidPtr(value);
-      if (!isInc) vlaSize = Builder.CreateNSWNeg(vlaSize, "vla.negsize");
+      llvm::Value *numElts = CGF.getVLASize(type).first;
+      if (!isInc) numElts = Builder.CreateNSWNeg(numElts, "vla.negsize");
       if (CGF.getContext().getLangOptions().isSignedOverflowDefined())
-        value = Builder.CreateGEP(value, vlaSize, "vla.inc");
+        value = Builder.CreateGEP(value, numElts, "vla.inc");
       else
-        value = Builder.CreateInBoundsGEP(value, vlaSize, "vla.inc");
-      value = Builder.CreateBitCast(value, input->getType());
+        value = Builder.CreateInBoundsGEP(value, numElts, "vla.inc");
     
     // Arithmetic on function pointers (!) is just +-1.
     } else if (type->isFunctionType()) {
@@ -1526,14 +1521,25 @@ ScalarExprEmitter::VisitUnaryExprOrTypeTraitExpr(
           CGF.getContext().getAsVariableArrayType(TypeToSize)) {
       if (E->isArgumentType()) {
         // sizeof(type) - make sure to emit the VLA size.
-        CGF.EmitVLASize(TypeToSize);
+        CGF.EmitVariablyModifiedType(TypeToSize);
       } else {
         // C99 6.5.3.4p2: If the argument is an expression of type
         // VLA, it is evaluated.
         CGF.EmitIgnoredExpr(E->getArgumentExpr());
       }
 
-      return CGF.GetVLASize(VAT);
+      QualType eltType;
+      llvm::Value *numElts;
+      llvm::tie(numElts, eltType) = CGF.getVLASize(VAT);
+
+      llvm::Value *size = numElts;
+
+      // Scale the number of non-VLA elements by the non-VLA element size.
+      CharUnits eltSize = CGF.getContext().getTypeSizeInChars(eltType);
+      if (!eltSize.isOne())
+        size = CGF.Builder.CreateNUWMul(CGF.CGM.getSize(eltSize), numElts);
+
+      return size;
     }
   }
 
diff --git a/lib/CodeGen/CGObjC.cpp b/lib/CodeGen/CGObjC.cpp
index 50e8d320dd..9107e9859e 100644
--- a/lib/CodeGen/CGObjC.cpp
+++ b/lib/CodeGen/CGObjC.cpp
@@ -1894,9 +1894,10 @@ namespace {
 
       // If it's a VLA, we have to load the stored size.  Note that
       // this is the size of the VLA in bytes, not its size in elements.
-      llvm::Value *vlaSizeInBytes = 0;
+      llvm::Value *numVLAElements = 0;
       if (isa<VariableArrayType>(arrayType)) {
-        vlaSizeInBytes = CGF.GetVLASize(cast<VariableArrayType>(arrayType));
+        numVLAElements =
+          CGF.getVLASize(cast<VariableArrayType>(arrayType)).first;
 
         // Walk into all VLAs.  This doesn't require changes to addr,
         // which has type T* where T is the first non-VLA element type.
@@ -1907,7 +1908,7 @@ namespace {
           // If we only have VLA components, 'addr' requires no adjustment.
           if (!arrayType) {
             baseType = elementType;
-            return divideVLASizeByBaseType(CGF, vlaSizeInBytes, baseType);
+            return numVLAElements;
           }
         } while (isa<VariableArrayType>(arrayType));
 
@@ -1947,22 +1948,20 @@ namespace {
         assert(arrayType && "LLVM and Clang types are out-of-synch");
       }
 
+      baseType = arrayType->getElementType();
+
       // Create the actual GEP.
       addr = CGF.Builder.CreateInBoundsGEP(addr, gepIndices.begin(),
                                            gepIndices.end(), "array.begin");
 
-      baseType = arrayType->getElementType();
-
-      // If we had an VLA dimensions, we need to use the captured size.
-      if (vlaSizeInBytes)
-        return divideVLASizeByBaseType(CGF, vlaSizeInBytes, baseType);
+      llvm::Value *numElements
+        = llvm::ConstantInt::get(CGF.IntPtrTy, countFromCLAs);
 
-      // Otherwise, use countFromCLAs.
-      assert(countFromCLAs == (uint64_t)
-               (Ctx.getTypeSizeInChars(origArrayType).getQuantity() /
-                Ctx.getTypeSizeInChars(baseType).getQuantity()));
+      // If we had any VLA dimensions, factor them in.
+      if (numVLAElements)
+        numElements = CGF.Builder.CreateNUWMul(numVLAElements, numElements);
 
-      return llvm::ConstantInt::get(CGF.IntPtrTy, countFromCLAs);
+      return numElements;
     }
 
     static llvm::Value *divideVLASizeByBaseType(CodeGenFunction &CGF,
diff --git a/lib/CodeGen/CodeGenFunction.cpp b/lib/CodeGen/CodeGenFunction.cpp
index 6ab4b76e75..43e07e24fc 100644
--- a/lib/CodeGen/CodeGenFunction.cpp
+++ b/lib/CodeGen/CodeGenFunction.cpp
@@ -343,7 +343,7 @@ void CodeGenFunction::StartFunction(GlobalDecl GD, QualType RetTy,
     QualType Ty = (*i)->getType();
 
     if (Ty->isVariablyModifiedType())
-      EmitVLASize(Ty);
+      EmitVariablyModifiedType(Ty);
   }
 }
 
@@ -709,13 +709,20 @@ CodeGenFunction::EmitNullInitialization(llvm::Value *DestPtr, QualType Ty) {
     if (const VariableArrayType *vlaType =
           dyn_cast_or_null<VariableArrayType>(
                                           getContext().getAsArrayType(Ty))) {
-      SizeVal = GetVLASize(vlaType);
+      QualType eltType;
+      llvm::Value *numElts;
+      llvm::tie(numElts, eltType) = getVLASize(vlaType);
+
+      SizeVal = numElts;
+      CharUnits eltSize = getContext().getTypeSizeInChars(eltType);
+      if (!eltSize.isOne())
+        SizeVal = Builder.CreateNUWMul(SizeVal, CGM.getSize(eltSize));
       vla = vlaType;
     } else {
       return;
     }
   } else {
-    SizeVal = llvm::ConstantInt::get(IntPtrTy, Size.getQuantity());
+    SizeVal = CGM.getSize(Size);
     vla = 0;
   }
 
@@ -778,60 +785,120 @@ llvm::BasicBlock *CodeGenFunction::GetIndirectGotoBlock() {
   return IndirectBranch->getParent();
 }
 
-llvm::Value *CodeGenFunction::GetVLASize(const VariableArrayType *VAT) {
-  llvm::Value *&SizeEntry = VLASizeMap[VAT->getSizeExpr()];
-
-  assert(SizeEntry && "Did not emit size for type");
-  return SizeEntry;
+std::pair<llvm::Value*, QualType>
+CodeGenFunction::getVLASize(QualType type) {
+  const VariableArrayType *vla = getContext().getAsVariableArrayType(type);
+  assert(vla && "type was not a variable array type!");
+  return getVLASize(vla);
 }
 
-llvm::Value *CodeGenFunction::EmitVLASize(QualType Ty) {
-  assert(Ty->isVariablyModifiedType() &&
-         "Must pass variably modified type to EmitVLASizes!");
+std::pair<llvm::Value*, QualType>
+CodeGenFunction::getVLASize(const VariableArrayType *type) {
+  // The number of elements so far; always size_t.
+  llvm::Value *numElements = 0;
 
-  EnsureInsertPoint();
+  QualType elementType;
+  do {
+    elementType = type->getElementType();
+    llvm::Value *vlaSize = VLASizeMap[type->getSizeExpr()];
+    assert(vlaSize && "no size for VLA!");
+    assert(vlaSize->getType() == SizeTy);
 
-  if (const VariableArrayType *VAT = getContext().getAsVariableArrayType(Ty)) {
-    // unknown size indication requires no size computation.
-    if (!VAT->getSizeExpr())
-      return 0;
-    llvm::Value *&SizeEntry = VLASizeMap[VAT->getSizeExpr()];
+    if (!numElements) {
+      numElements = vlaSize;
+    } else {
+      // It's undefined behavior if this wraps around, so mark it that way.
+      numElements = Builder.CreateNUWMul(numElements, vlaSize);
+    }
+  } while ((type = getContext().getAsVariableArrayType(elementType)));
 
-    if (!SizeEntry) {
-      const llvm::Type *SizeTy = ConvertType(getContext().getSizeType());
+  return std::pair<llvm::Value*,QualType>(numElements, elementType);
+}
 
-      // Get the element size;
-      QualType ElemTy = VAT->getElementType();
-      llvm::Value *ElemSize;
-      if (ElemTy->isVariableArrayType())
-        ElemSize = EmitVLASize(ElemTy);
-      else
-        ElemSize = llvm::ConstantInt::get(SizeTy,
-            getContext().getTypeSizeInChars(ElemTy).getQuantity());
+void CodeGenFunction::EmitVariablyModifiedType(QualType type) {
+  assert(type->isVariablyModifiedType() &&
+         "Must pass variably modified type to EmitVLASizes!");
 
-      llvm::Value *NumElements = EmitScalarExpr(VAT->getSizeExpr());
-      NumElements = Builder.CreateIntCast(NumElements, SizeTy, false, "tmp");
+  EnsureInsertPoint();
 
-      SizeEntry = Builder.CreateMul(ElemSize, NumElements);
+  // We're going to walk down into the type and look for VLA
+  // expressions.
+  type = type.getCanonicalType();
+  do {
+    assert(type->isVariablyModifiedType());
+
+    const Type *ty = type.getTypePtr();
+    switch (ty->getTypeClass()) {
+#define TYPE(Class, Base)
+#define ABSTRACT_TYPE(Class, Base)
+#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
+#define DEPENDENT_TYPE(Class, Base) case Type::Class:
+#define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class, Base) case Type::Class:
+#include "clang/AST/TypeNodes.def"
+      llvm_unreachable("unexpected dependent or non-canonical type!");
+
+    // These types are never variably-modified.
+    case Type::Builtin:
+    case Type::Complex:
+    case Type::Vector:
+    case Type::ExtVector:
+    case Type::Record:
+    case Type::Enum:
+    case Type::ObjCObject:
+    case Type::ObjCInterface:
+    case Type::ObjCObjectPointer:
+      llvm_unreachable("type class is never variably-modified!");
+
+    case Type::Pointer:
+      type = cast<PointerType>(ty)->getPointeeType();
+      break;
+
+    case Type::BlockPointer:
+      type = cast<BlockPointerType>(ty)->getPointeeType();
+      break;
+
+    case Type::LValueReference:
+    case Type::RValueReference:
+      type = cast<ReferenceType>(ty)->getPointeeType();
+      break;
+
+    case Type::MemberPointer:
+      type = cast<MemberPointerType>(ty)->getPointeeType();
+      break;
+
+    case Type::ConstantArray:
+    case Type::IncompleteArray:
+      // Losing element qualification here is fine.
+      type = cast<ArrayType>(ty)->getElementType();
+      break;
+
+    case Type::VariableArray: {
+      // Losing element qualification here is fine.
+      const VariableArrayType *vat = cast<VariableArrayType>(ty);
+
+      // Unknown size indication requires no size computation.
+      // Otherwise, evaluate and record it.
+      if (const Expr *size = vat->getSizeExpr()) {
+        // It's possible that we might have emitted this already,
+        // e.g. with a typedef and a pointer to it.
+        llvm::Value *&entry = VLASizeMap[size];
+        if (!entry) {
+          // Always zexting here would be wrong if it weren't
+          // undefined behavior to have a negative bound.
+          entry = Builder.CreateIntCast(EmitScalarExpr(size), SizeTy,
+                                        /*signed*/ false);
+        }
+      }
+      type = vat->getElementType();
+      break;
     }
 
-    return SizeEntry;
-  }
-
-  if (const ArrayType *AT = dyn_cast<ArrayType>(Ty)) {
-    EmitVLASize(AT->getElementType());
-    return 0;
-  }
-
-  if (const ParenType *PT = dyn_cast<ParenType>(Ty)) {
-    EmitVLASize(PT->getInnerType());
-    return 0;
-  }
-
-  const PointerType *PT = Ty->getAs<PointerType>();
-  assert(PT && "unknown VM type!");
-  EmitVLASize(PT->getPointeeType());
-  return 0;
+    case Type::FunctionProto: 
+    case Type::FunctionNoProto:
+      type = cast<FunctionType>(ty)->getResultType();
+      break;
+    }
+  } while (type->isVariablyModifiedType());
 }
 
 llvm::Value* CodeGenFunction::EmitVAListRef(const Expr* E) {
diff --git a/lib/CodeGen/CodeGenFunction.h b/lib/CodeGen/CodeGenFunction.h
index 0b24525029..fea2e6111a 100644
--- a/lib/CodeGen/CodeGenFunction.h
+++ b/lib/CodeGen/CodeGenFunction.h
@@ -1526,16 +1526,18 @@ public:
   // instruction in LLVM instead once it works well enough.
   llvm::Value *EmitVAArg(llvm::Value *VAListAddr, QualType Ty);
 
-  /// EmitVLASize - Generate code for any VLA size expressions that might occur
-  /// in a variably modified type. If Ty is a VLA, will return the value that
-  /// corresponds to the size in bytes of the VLA type. Will return 0 otherwise.
+  /// EmitVLASize - Capture all the sizes for the VLA expressions in
+  /// the given variably-modified type and store them in the VLASizeMap.
   ///
   /// This function can be called with a null (unreachable) insert point.
-  llvm::Value *EmitVLASize(QualType Ty);
-
-  // GetVLASize - Returns an LLVM value that corresponds to the size in bytes
-  // of a variable length array type.
-  llvm::Value *GetVLASize(const VariableArrayType *);
+  void EmitVariablyModifiedType(QualType Ty);
+
+  /// getVLASize - Returns an LLVM value that corresponds to the size,
+  /// in non-variably-sized elements, of a variable length array type,
+  /// plus that largest non-variably-sized element type.  Assumes that
+  /// the type has already been emitted with EmitVariablyModifiedType.
+  std::pair<llvm::Value*,QualType> getVLASize(const VariableArrayType *vla);
+  std::pair<llvm::Value*,QualType> getVLASize(QualType vla);
 
   /// LoadCXXThis - Load the value of 'this'. This function is only valid while
   /// generating code for an C++ member function.
diff --git a/lib/CodeGen/CodeGenModule.cpp b/lib/CodeGen/CodeGenModule.cpp
index af29990da6..ddef39726f 100644
--- a/lib/CodeGen/CodeGenModule.cpp
+++ b/lib/CodeGen/CodeGenModule.cpp
@@ -196,6 +196,10 @@ void CodeGenModule::ErrorUnsupported(const Decl *D, const char *Type,
   getDiags().Report(Context.getFullLoc(D->getLocation()), DiagID) << Msg;
 }
 
+llvm::ConstantInt *CodeGenModule::getSize(CharUnits size) {
+  return llvm::ConstantInt::get(SizeTy, size.getQuantity());
+}
+
 void CodeGenModule::setGlobalVisibility(llvm::GlobalValue *GV,
                                         const NamedDecl *D) const {
   // Internal definitions always have default visibility.
diff --git a/lib/CodeGen/CodeGenModule.h b/lib/CodeGen/CodeGenModule.h
index 7321ac45f4..3cca76a171 100644
--- a/lib/CodeGen/CodeGenModule.h
+++ b/lib/CodeGen/CodeGenModule.h
@@ -33,6 +33,7 @@
 namespace llvm {
   class Module;
   class Constant;
+  class ConstantInt;
   class Function;
   class GlobalValue;
   class TargetData;
@@ -382,6 +383,9 @@ public:
   static void DecorateInstruction(llvm::Instruction *Inst,
                                   llvm::MDNode *TBAAInfo);
 
+  /// getSize - Emit the given number of characters as a value of type size_t.
+  llvm::ConstantInt *getSize(CharUnits numChars);
+
   /// setGlobalVisibility - Set the visibility for the given LLVM
   /// GlobalValue.
   void setGlobalVisibility(llvm::GlobalValue *GV, const NamedDecl *D) const;