[Sema] Fix an assertion failure in constant expression evaluation of calls to functions with default arguments

[ahatanak]

Summary

The assertion fails when a function with a default argument that materializes a temporary is called more than once in an expression. The assertion fails in CallStackFrame::createTemporary when it searches map Temporaries using the default argument's expression (which is a MaterializeTemporaryExpr) as the key and it discovers that there is already an element with that key that has been initialized.

constexpr bool equals(const float& arg = 1.0f) {
  return arg == 1.0f;
}

constexpr bool test_default_arg() {
  return equals() && equals();
}

This patch removes the assertion and makes CallStackFrame::createTemporary reset the existing element and return it if the element is found in the map.

rdar://problem/36505742

[lebedev.ri]

test/SemaCXX/constexpr-default-arg.cpp

3

Down the line, it won't be obvious *what* this testcase is checking.
At the very least wrap it into namespace rdar_problem_36505742 {}

[erik.pilkington]

Hi Akira, thanks for working on this!

lib/AST/ExprConstant.cpp

1165–1173

I think that the problem is more subtle than this. This static assert errors (previously clang would assert) when it really it should be fine.

constexpr const int &x(const int &p = 0) { return p; }
static_assert(&x() != &x());

Because default arguments are allocated on the caller side, both the calls to x() call createTemporary for the same MaterializeTemporaryExpr in the same CallStackFrame, when really that MTE should correspond to two distinct values. This patch just hides that underlying problem by recycling the value created during the first call during the second call.

Maybe we could have a fancier key that incorporates a node on the caller side, such as the CXXDefaultArgExpr as well at the MTE, and store that fancy key in APValue::LValueBases? That would allow us generate distinct values for these MTEs, and also remember what expression originated it. What do you think about that?

There is small discussion about this problem here: https://bugs.llvm.org/show_bug.cgi?id=33140

[ahatanak]

Address Erik's and Roman's review comments.

lib/AST/ExprConstant.cpp

1165–1173

Thank you Erik for explaining the problem and pointing me to the PR.

I ended up using a version number that is updated every time VisitCXXDefaultArgExpr is called. I initially tried using CXXDefaultArgExpr and the void* pointer as the key, but discovered that that wouldn't fix the assertion failure when compiling the first test case in PR33140 since InitListExpr uses the same CXXConstructExpr (and hence the same CXXDefaultArgExpr) to initialize the array.

Let me know if there are other cases I haven't thought about.

test/SemaCXX/constexpr-default-arg.cpp

3

I added comments that explain what it's trying to check.

[rsmith]

lib/AST/APValue.cpp

27 ↗

(On Diff #133947)

Move this to the end so it can share space with IsNullPtr.

lib/AST/ExprConstant.cpp

587–596

This seems extremely similar to the purpose of the existing CallIndex parameter. Have you thought about ways the two might be unified?

If there's no reasonable path to unifying the two (which I suspect there may not be), it would make more sense to me to store a current version number on the CallStackFrame rather than globally in the EvalInfo, and to restart the numbering in each new call frame. That also emphasizes something else: this version number should be kept with the CallIndex. (We could achieve that by either moving the CallIndex into the LValueBase or moving the Version out of it.)

595

This is wrong: these scopes can nest, so you can't just reset the number to 0 when you're done. You should restore the prior number when you're done here, to divide up evaluation into CXXDefaultArgExpr scopes. (Technically, I think it would also be correct to leave the number alone when you leave one of these scopes, but only because a scope for a particular parameter's default argument can't nest within another scope for the same default argument expression -- and even that might not be true in the presence of template instantiation.)

4575

We need the same handling for CXXDefaultInitExpr, too.

[ahatanak]

lib/AST/ExprConstant.cpp

595

Do you mean VisitCXXDefaultArgExpr can be called the second time before the first call returns? Do you have an example code that would cause that to happen (which I can perhaps add as a test case)?

It seemed to me that that would happen only if you used a lambda expression for the default argument, but I thought the current standard doesn't allow using lambda expressions in constant expressions.

[ahatanak]

OK, I see. It's pretty easy to come up with an example.

constexpr int foo1(int a = 12) {
  return a * a;
}

constexpr int foo2(int a = foo1()) {
  return a - 12;
}

[ahatanak]

Address review comments.

lib/AST/ExprConstant.cpp

587–596

It couldn't come up with a way to unify CallIndex and Version. I think it's better to keep them separate because you need the CallIndex to get the frame that owns the temporary and you need Version to distinguish between two temporaries created by the same MTE.

I moved CallIndex into LValueBase as you suggested.

[ahatanak]

ping

[rsmith]

Thank you, this looks like a great direction.

As noted, there are a bunch of other cases that we should cover with this approach. I'm really happy about the number of related bugs we get to fix with this change.

lib/AST/ExprConstant.cpp

3177–3178

This should take the version into account.

5211

Hmm. We should be versioning local variables as well. Currently we'll accept invalid code such as:

constexpr int f() {
  int *p = nullptr;
  for (int k = 0; k != 2; ++k) {
    int local_var = 0;
    if (k == 0)
      p = &local_var;
    else
      return *p;
  }
}
static_assert(f() == 0);

5250–5253

Can you combine these, so we have a single function to create a temporary and produce both an LValue denoting it and an APValue* to hold its evaluated value?

5747

This should create a versioned temporary object.

6515

This should create a versioned temporary object.

8003

You already checked this above. It'd make sense to check the call index and version in the same place here, but we should only need one check for each :)

9945–9968

These temporaries should all be versioned.

[ahatanak]

Address review comments.

lib/AST/ExprConstant.cpp

5211

I made changes to the constructor and destructor of ScopeRAII so that a version is pushed at the start of a new iteration. This fixes the FIXME in test/SemaCXX/constant-expression-cxx1y.cpp.

[ahatanak]

Assign an uninitialized APValue to a temporary instead of removing it from the temporary map when the temporary's lifetime has ended.

[rsmith]

I think this can be cleaned up a bit further, but I'm fine with that happening after the patch lands. Thanks!

lib/AST/ExprConstant.cpp

442–443

Have you considered using a pair<const void*, unsigned> as the key rather than a map-of-maps? It'd be preferable to only allocate one heap node rather than two for the (hopefully common) case where there is only one version of an object.

452

If we're using this for variables in loops too, we should generalize the name and the description to not talk about temporaries.

[ahatanak]

Use pair<const void*, unsigned> as the key.

lib/AST/ExprConstant.cpp

struct CallStackFrame {
 
     /// Arguments - Parameter bindings for this function call, indexed by
     /// parameters' function scope indices.
     APValue *Arguments;
 
     // Note that we intentionally use std::map here so that references to
     // values are stable.
     typedef std::map<const void*, APValue> MapTy;
     typedef MapTy::const_iterator temp_iterator;
     /// Temporaries - Temporary lvalues materialized within this stack frame.
     MapTy Temporaries;
 
     /// CallLoc - The location of the call expression for this call.
     SourceLocation CallLoc;
 
     /// Index - The call index of this call.
     unsigned Index;
 
     // FIXME: Adding this to every 'CallStackFrame' may have a nontrivial impact
     // on the overall stack usage of deeply-recursing constexpr evaluataions.
     // (We should cache this map rather than recomputing it repeatedly.)
     // But let's try this and see how it goes; we can look into caching the map
     // as a later change.
 
     /// LambdaCaptureFields - Mapping from captured variables/this to
     /// corresponding data members in the closure class.
     llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
struct EvalInfo {
     /// to perform. This is essentially a limit for the number of statements
     /// we will evaluate.
     unsigned StepsLeft;
 
     /// BottomFrame - The frame in which evaluation started. This must be
     /// initialized after CurrentCall and CallStackDepth.
     CallStackFrame BottomFrame;
 
     /// A stack of values whose lifetimes end at the end of some surrounding
     /// evaluation frame.
     llvm::SmallVector<Cleanup, 16> CleanupStack;
 
     /// EvaluatingDecl - This is the declaration whose initializer is being
     /// evaluated, if any.
     APValue::LValueBase EvaluatingDecl;
 
     /// EvaluatingDeclValue - This is the value being constructed for the
     /// declaration whose initializer is being evaluated, if any.
     APValue *EvaluatingDeclValue;
 
     /// EvaluatingObject - Pair of the AST node that an lvalue represents and
     /// the call index that that lvalue was allocated in.
     typedef std::pair<APValue::LValueBase, unsigned> EvaluatingObject;
 
     /// EvaluatingConstructors - Set of objects that are currently being
     /// constructed.

 CallStackFrame::~CallStackFrame() {
   assert(Info.CurrentCall == this && "calls retired out of order");
   --Info.CallStackDepth;
   Info.CurrentCall = Caller;
 }
 
 APValue &CallStackFrame::createTemporary(const void *Key,
                                          bool IsLifetimeExtended) {
-  APValue &Result = Temporaries[Key];
-  assert(Result.isUninit() && "temporary created multiple times");
+  auto LB = Temporaries.lower_bound(Key);
+
+  // If an element with key Key is found, reset the value and return it. This
+  // can happen if Key is part of a default argument expression.
+  if (LB != Temporaries.end() && LB->first == Key)
+    return LB->second = APValue();
+
+  APValue &Result =
+      Temporaries.insert(LB, std::make_pair(Key, APValue()))->second;
   Info.CleanupStack.push_back(Cleanup(&Result, IsLifetimeExtended));
   return Result;
 }
 
 static void describeCall(CallStackFrame *Frame, raw_ostream &Out);
 
 void EvalInfo::addCallStack(unsigned Limit) {
   // Determine which calls to skip, if any.
if (BaseType.isVolatileQualified()) {
       }
       return CompleteObject();
     }
   }
 
   // During the construction of an object, it is not yet 'const'.
   // FIXME: This doesn't do quite the right thing for const subobjects of the
   // object under construction.
   if (Info.isEvaluatingConstructor(LVal.getLValueBase(), LVal.CallIndex)) {
     BaseType = Info.Ctx.getCanonicalType(BaseType);
     BaseType.removeLocalConst();
   }
 
   // In C++1y, we can't safely access any mutable state when we might be
   // evaluating after an unmodeled side effect.
   //
   // FIXME: Not all local state is mutable. Allow local constant subobjects
   // to be read here (but take care with 'mutable' fields).
public:
   bool VisitChooseExpr(const ChooseExpr *E)
     { return StmtVisitorTy::Visit(E->getChosenSubExpr()); }
   bool VisitGenericSelectionExpr(const GenericSelectionExpr *E)
     { return StmtVisitorTy::Visit(E->getResultExpr()); }
   bool VisitSubstNonTypeTemplateParmExpr(const SubstNonTypeTemplateParmExpr *E)
     { return StmtVisitorTy::Visit(E->getReplacement()); }
   bool VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *E)
     { return StmtVisitorTy::Visit(E->getExpr()); }
   bool VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *E) {
     // The initializer may not have been parsed yet, or might be erroneous.
     if (!E->getExpr())
       return Error(E);
     return StmtVisitorTy::Visit(E->getExpr());
   }
   // We cannot create any objects for which cleanups are required, so there is
   // nothing to do here; all cleanups must come from unevaluated subexpressions.
   bool VisitExprWithCleanups(const ExprWithCleanups *E)
if (VD->hasLocalStorage() && Info.CurrentCall->Index > 1) {
     if (Info.CurrentCall->Callee &&
         Info.CurrentCall->Callee->Equals(VD->getDeclContext())) {
       Frame = Info.CurrentCall;
     }
   }
 
   if (!VD->getType()->isReferenceType()) {
     if (Frame) {
       Result.set(VD, Frame->Index);
       return true;
     }
     return Success(VD);
   }
 
   APValue *V;
   if (!evaluateVarDeclInit(Info, E, VD, Frame, V))
     return false;
bool LValueExprEvaluator::VisitMaterializeTemporaryExpr(
   // result of a constant expression evaluation, so we need to preserve its
   // value for use outside this evaluation.
   APValue *Value;
   if (E->getStorageDuration() == SD_Static) {
     Value = Info.Ctx.getMaterializedTemporaryValue(E, true);
     *Value = APValue();
     Result.set(E);
   } else {
     Value = &Info.CurrentCall->
         createTemporary(E, E->getStorageDuration() == SD_Automatic);
     Result.set(E, Info.CurrentCall->Index);
   }
 
   QualType Type = Inner->getType();
 
   // Materialize the temporary itself.
   if (!EvaluateInPlace(*Value, Info, Result, Inner) ||
       (E->getStorageDuration() == SD_Static &&
        !CheckConstantExpression(Info, E->getExprLoc(), Type, *Value))) {
     *Value = APValue();
case CK_IntegralToPointer: {
     }
   }
 
   case CK_ArrayToPointerDecay: {
     if (SubExpr->isGLValue()) {
       if (!evaluateLValue(SubExpr, Result))
         return false;
     } else {
       Result.set(SubExpr, Info.CurrentCall->Index);
       if (!EvaluateInPlace(Info.CurrentCall->createTemporary(SubExpr, false),
                            Info, Result, SubExpr))
         return false;
     }
     // The result is a pointer to the first element of the array.
     auto *AT = Info.Ctx.getAsArrayType(SubExpr->getType());
     if (auto *CAT = dyn_cast<ConstantArrayType>(AT))
       Result.addArray(Info, E, CAT);

 class TemporaryExprEvaluator
   : public LValueExprEvaluatorBase<TemporaryExprEvaluator> {
 public:
   TemporaryExprEvaluator(EvalInfo &Info, LValue &Result) :
     LValueExprEvaluatorBaseTy(Info, Result, false) {}
 
   /// Visit an expression which constructs the value of this temporary.
   bool VisitConstructExpr(const Expr *E) {
     Result.set(E, Info.CurrentCall->Index);
     return EvaluateInPlace(Info.CurrentCall->createTemporary(E, false),
                            Info, Result, E);
   }
 
   bool VisitCastExpr(const CastExpr *E) {
     switch (E->getCastKind()) {
     default:
       return LValueExprEvaluatorBaseTy::VisitCastExpr(E);
if (!ADecl)
       return false;
     const Decl *BDecl = GetLValueBaseDecl(B);
     if (!BDecl || ADecl->getCanonicalDecl() != BDecl->getCanonicalDecl())
       return false;
   }
 
   return IsGlobalLValue(A.getLValueBase()) ||
          A.getLValueCallIndex() == B.getLValueCallIndex();
 }
 
 /// \brief Determine whether this is a pointer past the end of the complete
 /// object referred to by the lvalue.
 static bool isOnePastTheEndOfCompleteObject(const ASTContext &Ctx,
                                             const LValue &LV) {
   // A null pointer can be viewed as being "past the end" but we don't
   // choose to look at it that way here.
   if (!LV.getLValueBase())
static bool Evaluate(APValue &Result, EvalInfo &Info, const Expr *E) {
   } else if (T->isMemberPointerType()) {
     MemberPtr P;
     if (!EvaluateMemberPointer(E, P, Info))
       return false;
     P.moveInto(Result);
     return true;
   } else if (T->isArrayType()) {
     LValue LV;
     LV.set(E, Info.CurrentCall->Index);
     APValue &Value = Info.CurrentCall->createTemporary(E, false);
     if (!EvaluateArray(E, LV, Value, Info))
       return false;
     Result = Value;
   } else if (T->isRecordType()) {
     LValue LV;
     LV.set(E, Info.CurrentCall->Index);
     APValue &Value = Info.CurrentCall->createTemporary(E, false);
     if (!EvaluateRecord(E, LV, Value, Info))
       return false;
     Result = Value;
   } else if (T->isVoidType()) {
     if (!Info.getLangOpts().CPlusPlus11)
       Info.CCEDiag(E, diag::note_constexpr_nonliteral)
         << E->getType();
     if (!EvaluateVoid(E, Info))
       return false;
   } else if (T->isAtomicType()) {
     QualType Unqual = T.getAtomicUnqualifiedType();
     if (Unqual->isArrayType() || Unqual->isRecordType()) {
       LValue LV;
       LV.set(E, Info.CurrentCall->Index);
       APValue &Value = Info.CurrentCall->createTemporary(E, false);
       if (!EvaluateAtomic(E, &LV, Value, Info))
         return false;
     } else {
       if (!EvaluateAtomic(E, nullptr, Result, Info))
         return false;
     }
   } else if (Info.getLangOpts().CPlusPlus11) {
     Info.FFDiag(E, diag::note_constexpr_nonliteral) << E->getType();

test/SemaCXX/constexpr-default-arg.cpp

+// RUN: %clang_cc1 -std=c++1y -fsyntax-only -verify %s
+
+// expected-no-diagnostics
+
+constexpr bool equals(const float& arg = 1.0f) {
+  return arg == 1.0f;
+}
+
+constexpr bool test_default_arg() {
+  return equals() && equals();
+}