Don't assume cleanup emission preserves dominance in expr evaluation

[rnk]

Summary

Because of the existence branches out of GNU statement expressions, it
is possible that emitting cleanups for a full expression may cause the
new insertion point to not be dominated by the result of the inner
expression. Consider this example:

struct Foo { Foo(); ~Foo(); int x; };
int g(Foo, int);
int f(bool cond) {
  int n = g(Foo(), ({ if (cond) return 0; 42; }));
  return n;
}

Before this change, result of the call to 'g' did not dominate its use
in the store to 'n'. The early return exit from the statement expression
branches to a shared cleanup block, which ends in a switch between the
fallthrough destination (the assignment to 'n') or the function exit
block.

This change solves the problem by spilling and reloading expression
evaluation results when any of the active cleanups have branches.

I audited the other call sites of enterFullExpression, and they don't
appear to keep and Values live across the site of the cleanup, except in
ARC code. I wasn't able to create a test case for ARC that exhibits this
problem, though.

[rsmith]

Hal and I discussed exactly the same problem (in the context of coroutines) on Saturday and came up with exactly the same approach :) I think this is the right direction.

lib/CodeGen/CGExprComplex.cpp

204–206 ↗

(On Diff #90528)

I'm a little concerned about the loose connection between ensureDominatingValue and ForrceCleanup here -- if you forget the ForceCleanup, you get silent misbehavior. How about removing ensureDominatingValue and instead passing a std::initializer_list<Value**> to ForceCleanup?

lib/CodeGen/CodeGenFunction.h

539 ↗

(On Diff #90528)

If you keep a SmallVector here, set its inline size to 2 to avoid allocations for the _Complex case.

[rnk]

lib/CodeGen/CGExprComplex.cpp

204–206 ↗

(On Diff #90528)

Done.

lib/CodeGen/CodeGenFunction.h

539 ↗

(On Diff #90528)

I removed it. Also, who wants to waste a whole pointer of stack space for _Complex expression evaluation. ;)

[rnk]

• comments

cfe/trunk/lib/CodeGen/CGCleanup.cpp

for (unsigned I = 0, E = EHStack.getNumBranchFixups(); I != E; ++I) {
     Switch->addCase(Builder.getInt32(Fixup.DestinationIndex), Block);
   }
 
   if (ResolvedAny)
     EHStack.popNullFixups();
 }
 
 /// Pops cleanup blocks until the given savepoint is reached.
-void CodeGenFunction::PopCleanupBlocks(EHScopeStack::stable_iterator Old) {
+void CodeGenFunction::PopCleanupBlocks(
+    EHScopeStack::stable_iterator Old,
+    std::initializer_list<llvm::Value **> ValuesToReload) {
   assert(Old.isValid());
 
+  bool HadBranches = false;
   while (EHStack.stable_begin() != Old) {
     EHCleanupScope &Scope = cast<EHCleanupScope>(*EHStack.begin());
+    HadBranches |= Scope.hasBranches();
 
     // As long as Old strictly encloses the scope's enclosing normal
     // cleanup, we're going to emit another normal cleanup which
     // fallthrough can propagate through.
     bool FallThroughIsBranchThrough =
       Old.strictlyEncloses(Scope.getEnclosingNormalCleanup());
 
     PopCleanupBlock(FallThroughIsBranchThrough);
   }
+
+  // If we didn't have any branches, the insertion point before cleanups must
+  // dominate the current insertion point and we don't need to reload any
+  // values.
+  if (!HadBranches)
+    return;
+
+  // Spill and reload all values that the caller wants to be live at the current
+  // insertion point.
+  for (llvm::Value **ReloadedValue : ValuesToReload) {
+    auto *Inst = dyn_cast_or_null<llvm::Instruction>(*ReloadedValue);
+    if (!Inst)
+      continue;
+    Address Tmp =
+        CreateDefaultAlignTempAlloca(Inst->getType(), "tmp.exprcleanup");
+
+    // Find an insertion point after Inst and spill it to the temporary.
+    llvm::BasicBlock::iterator InsertBefore;
+    if (auto *Invoke = dyn_cast<llvm::InvokeInst>(Inst))
+      InsertBefore = Invoke->getNormalDest()->getFirstInsertionPt();
+    else
+      InsertBefore = std::next(Inst->getIterator());
+    CGBuilderTy(CGM, &*InsertBefore).CreateStore(Inst, Tmp);
+
+    // Reload the value at the current insertion point.
+    *ReloadedValue = Builder.CreateLoad(Tmp);
+  }
 }
 
 /// Pops cleanup blocks until the given savepoint is reached, then add the
 /// cleanups from the given savepoint in the lifetime-extended cleanups stack.
-void
-CodeGenFunction::PopCleanupBlocks(EHScopeStack::stable_iterator Old,
-                                  size_t OldLifetimeExtendedSize) {
-  PopCleanupBlocks(Old);
+void CodeGenFunction::PopCleanupBlocks(
+    EHScopeStack::stable_iterator Old, size_t OldLifetimeExtendedSize,
+    std::initializer_list<llvm::Value **> ValuesToReload) {
+  PopCleanupBlocks(Old, ValuesToReload);
 
   // Move our deferred cleanups onto the EH stack.
   for (size_t I = OldLifetimeExtendedSize,
               E = LifetimeExtendedCleanupStack.size(); I != E; /**/) {
     // Alignment should be guaranteed by the vptrs in the individual cleanups.
     assert((I % alignof(LifetimeExtendedCleanupHeader) == 0) &&
            "misaligned cleanup stack entry");
 

cfe/trunk/lib/CodeGen/CGExpr.cpp

case Expr::CXXUuidofExprClass:
     return EmitCXXUuidofLValue(cast<CXXUuidofExpr>(E));
   case Expr::LambdaExprClass:
     return EmitLambdaLValue(cast<LambdaExpr>(E));
 
   case Expr::ExprWithCleanupsClass: {
     const auto *cleanups = cast<ExprWithCleanups>(E);
     enterFullExpression(cleanups);
     RunCleanupsScope Scope(*this);
-    return EmitLValue(cleanups->getSubExpr());
+    LValue LV = EmitLValue(cleanups->getSubExpr());
+    if (LV.isSimple()) {
+      // Defend against branches out of gnu statement expressions surrounded by
+      // cleanups.
+      llvm::Value *V = LV.getPointer();
+      Scope.ForceCleanup({&V});
+      return LValue::MakeAddr(Address(V, LV.getAlignment()), LV.getType(),
+                              getContext(), LV.getAlignmentSource(),
+                              LV.getTBAAInfo());
+    }
+    // FIXME: Is it possible to create an ExprWithCleanups that produces a
+    // bitfield lvalue or some other non-simple lvalue?
+    return LV;
   }
 
   case Expr::CXXDefaultArgExprClass:
     return EmitLValue(cast<CXXDefaultArgExpr>(E)->getExpr());
   case Expr::CXXDefaultInitExprClass: {
     CXXDefaultInitExprScope Scope(*this);
     return EmitLValue(cast<CXXDefaultInitExpr>(E)->getExpr());
   }

cfe/trunk/lib/CodeGen/CGExprComplex.cpp

public:
   }
   ComplexPairTy VisitCXXDefaultInitExpr(CXXDefaultInitExpr *DIE) {
     CodeGenFunction::CXXDefaultInitExprScope Scope(CGF);
     return Visit(DIE->getExpr());
   }
   ComplexPairTy VisitExprWithCleanups(ExprWithCleanups *E) {
     CGF.enterFullExpression(E);
     CodeGenFunction::RunCleanupsScope Scope(CGF);
-    return Visit(E->getSubExpr());
+    ComplexPairTy Vals = Visit(E->getSubExpr());
+    // Defend against dominance problems caused by jumps out of expression
+    // evaluation through the shared cleanup block.
+    Scope.ForceCleanup({&Vals.first, &Vals.second});
+    return Vals;
   }
   ComplexPairTy VisitCXXScalarValueInitExpr(CXXScalarValueInitExpr *E) {
     assert(E->getType()->isAnyComplexType() && "Expected complex type!");
     QualType Elem = E->getType()->castAs<ComplexType>()->getElementType();
     llvm::Constant *Null = llvm::Constant::getNullValue(CGF.ConvertType(Elem));
     return ComplexPairTy(Null, Null);
   }
   ComplexPairTy VisitImplicitValueInitExpr(ImplicitValueInitExpr *E) {

cfe/trunk/lib/CodeGen/CGExprScalar.cpp

 //===--- CGExprScalar.cpp - Emit LLVM Code for Scalar Exprs ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This contains code to emit Expr nodes with scalar LLVM types as LLVM code.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenFunction.h"
+#include "CGCleanup.h"
 #include "CGCXXABI.h"
 #include "CGDebugInfo.h"
 #include "CGObjCRuntime.h"
 #include "CodeGenModule.h"
 #include "TargetInfo.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/Expr.h"
public:
   Value *VisitCXXDefaultInitExpr(CXXDefaultInitExpr *DIE) {
     CodeGenFunction::CXXDefaultInitExprScope Scope(CGF);
     return Visit(DIE->getExpr());
   }
   Value *VisitCXXThisExpr(CXXThisExpr *TE) {
     return CGF.LoadCXXThis();
   }
 
-  Value *VisitExprWithCleanups(ExprWithCleanups *E) {
-    CGF.enterFullExpression(E);
-    CodeGenFunction::RunCleanupsScope Scope(CGF);
-    return Visit(E->getSubExpr());
-  }
+  Value *VisitExprWithCleanups(ExprWithCleanups *E);
   Value *VisitCXXNewExpr(const CXXNewExpr *E) {
     return CGF.EmitCXXNewExpr(E);
   }
   Value *VisitCXXDeleteExpr(const CXXDeleteExpr *E) {
     CGF.EmitCXXDeleteExpr(E);
     return nullptr;
   }
 
Value *ScalarExprEmitter::VisitStmtExpr(const StmtExpr *E) {
   Address RetAlloca = CGF.EmitCompoundStmt(*E->getSubStmt(),
                                            !E->getType()->isVoidType());
   if (!RetAlloca.isValid())
     return nullptr;
   return CGF.EmitLoadOfScalar(CGF.MakeAddrLValue(RetAlloca, E->getType()),
                               E->getExprLoc());
 }
 
+Value *ScalarExprEmitter::VisitExprWithCleanups(ExprWithCleanups *E) {
+  CGF.enterFullExpression(E);
+  CodeGenFunction::RunCleanupsScope Scope(CGF);
+  Value *V = Visit(E->getSubExpr());
+  // Defend against dominance problems caused by jumps out of expression
+  // evaluation through the shared cleanup block.
+  Scope.ForceCleanup({&V});
+  return V;
+}
+
 //===----------------------------------------------------------------------===//
 //                             Unary Operators
 //===----------------------------------------------------------------------===//
 
 static BinOpInfo createBinOpInfoFromIncDec(const UnaryOperator *E,
                                            llvm::Value *InVal, bool IsInc) {
   BinOpInfo BinOp;
   BinOp.LHS = InVal;

cfe/trunk/lib/CodeGen/CodeGenFunction.h

public:
     {
       CleanupStackDepth = CGF.EHStack.stable_begin();
       LifetimeExtendedCleanupStackSize =
           CGF.LifetimeExtendedCleanupStack.size();
       OldDidCallStackSave = CGF.DidCallStackSave;
       CGF.DidCallStackSave = false;
     }
 
-    /// \brief Exit this cleanup scope, emitting any accumulated
-    /// cleanups.
+    /// \brief Exit this cleanup scope, emitting any accumulated cleanups.
     ~RunCleanupsScope() {
-      if (PerformCleanup) {
-        CGF.DidCallStackSave = OldDidCallStackSave;
-        CGF.PopCleanupBlocks(CleanupStackDepth,
-                             LifetimeExtendedCleanupStackSize);
-      }
+      if (PerformCleanup)
+        ForceCleanup();
     }
 
     /// \brief Determine whether this scope requires any cleanups.
     bool requiresCleanups() const {
       return CGF.EHStack.stable_begin() != CleanupStackDepth;
     }
 
     /// \brief Force the emission of cleanups now, instead of waiting
     /// until this object is destroyed.
-    void ForceCleanup() {
+    /// \param ValuesToReload - A list of values that need to be available at
+    /// the insertion point after cleanup emission. If cleanup emission created
+    /// a shared cleanup block, these value pointers will be rewritten.
+    /// Otherwise, they not will be modified.
+    void ForceCleanup(std::initializer_list<llvm::Value**> ValuesToReload = {}) {
       assert(PerformCleanup && "Already forced cleanup");
       CGF.DidCallStackSave = OldDidCallStackSave;
-      CGF.PopCleanupBlocks(CleanupStackDepth,
-                           LifetimeExtendedCleanupStackSize);
+      CGF.PopCleanupBlocks(CleanupStackDepth, LifetimeExtendedCleanupStackSize,
+                           ValuesToReload);
       PerformCleanup = false;
     }
   };
 
   class LexicalScope : public RunCleanupsScope {
     SourceRange Range;
     SmallVector<const LabelDecl*, 4> Labels;
     LexicalScope *ParentScope;
static void copyInto(const DeclMapTy &src, DeclMapTy &dest) {
           dest.insert(pair);
         }
       }
     }
   };
 
   /// \brief Takes the old cleanup stack size and emits the cleanup blocks
   /// that have been added.
-  void PopCleanupBlocks(EHScopeStack::stable_iterator OldCleanupStackSize);
+  void
+  PopCleanupBlocks(EHScopeStack::stable_iterator OldCleanupStackSize,
+                   std::initializer_list<llvm::Value **> ValuesToReload = {});
 
   /// \brief Takes the old cleanup stack size and emits the cleanup blocks
   /// that have been added, then adds all lifetime-extended cleanups from
   /// the given position to the stack.
-  void PopCleanupBlocks(EHScopeStack::stable_iterator OldCleanupStackSize,
-                        size_t OldLifetimeExtendedStackSize);
+  void
+  PopCleanupBlocks(EHScopeStack::stable_iterator OldCleanupStackSize,
+                   size_t OldLifetimeExtendedStackSize,
+                   std::initializer_list<llvm::Value **> ValuesToReload = {});
 
   void ResolveBranchFixups(llvm::BasicBlock *Target);
 
   /// The given basic block lies in the current EH scope, but may be a
   /// target of a potentially scope-crossing jump; get a stable handle
   /// to which we can perform this jump later.
   JumpDest getJumpDestInCurrentScope(llvm::BasicBlock *Target) {
     return JumpDest(Target,

cfe/trunk/test/CodeGenCXX/stmtexpr.cpp

 
 // <rdar://problem/14074868>
 // Make sure this doesn't crash.
 int foo5(bool b) {
   int y = 0;
   y = ({ A a(1); if (b) goto G; a.i; });
   G: return y;
 }
+
+// When we emit a full expression with cleanups that contains branches out of
+// the full expression, the result of the inner expression (the call to
+// call_with_cleanups in this case) may not dominate the fallthrough destination
+// of the shared cleanup block.
+//
+// In this case the CFG will be a sequence of two diamonds, but the only
+// dynamically possible execution paths are both left hand branches and both
+// right hand branches. The first diamond LHS will call bar, and the second
+// diamond LHS will assign the result to v, but the call to bar does not
+// dominate the assignment.
+int bar(A, int);
+extern "C" int cleanup_exit_scalar(bool b) {
+  int v = bar(A(1), ({ if (b) return 42; 13; }));
+  return v;
+}
+
+// CHECK-LABEL: define i32 @cleanup_exit_scalar({{.*}})
+// CHECK: call {{.*}} @_ZN1AC1Ei
+//    Spill after bar.
+// CHECK: %[[v:[^ ]*]] = call i32 @_Z3bar1Ai({{.*}})
+// CHECK-NEXT: store i32 %[[v]], i32* %[[tmp:[^, ]*]]
+//    Do cleanup.
+// CHECK: call {{.*}} @_ZN1AD1Ev
+// CHECK: switch
+//    Reload before v assignment.
+// CHECK: %[[v:[^ ]*]] = load i32, i32* %[[tmp]]
+// CHECK-NEXT: store i32 %[[v]], i32* %v
+
+// No need to spill when the expression result is a constant, constants don't
+// have dominance problems.
+extern "C" int cleanup_exit_scalar_constant(bool b) {
+  int v = (A(1), (void)({ if (b) return 42; 0; }), 13);
+  return v;
+}
+
+// CHECK-LABEL: define i32 @cleanup_exit_scalar_constant({{.*}})
+// CHECK: store i32 13, i32* %v
+
+// Check for the same bug for lvalue expression evaluation kind.
+// FIXME: What about non-reference lvalues, like bitfield lvalues and vector
+// lvalues?
+int &getref();
+extern "C" int cleanup_exit_lvalue(bool cond) {
+  int &r = (A(1), ({ if (cond) return 0; (void)0; }), getref());
+  return r;
+}
+// CHECK-LABEL: define i32 @cleanup_exit_lvalue({{.*}})
+// CHECK: call {{.*}} @_ZN1AC1Ei
+//    Spill after bar.
+// CHECK: %[[v:[^ ]*]] = call dereferenceable(4) i32* @_Z6getrefv({{.*}})
+// CHECK-NEXT: store i32* %[[v]], i32** %[[tmp:[^, ]*]]
+//    Do cleanup.
+// CHECK: call {{.*}} @_ZN1AD1Ev
+// CHECK: switch
+//    Reload before v assignment.
+// CHECK: %[[v:[^ ]*]] = load i32*, i32** %[[tmp]]
+// CHECK-NEXT: store i32* %[[v]], i32** %r
+
+
+// We handle ExprWithCleanups for complex evaluation type separately, and it had
+// the same bug.
+_Complex float bar_complex(A, int);
+extern "C" int cleanup_exit_complex(bool b) {
+  _Complex float v = bar_complex(A(1), ({ if (b) return 42; 13; }));
+  return v;
+}
+
+// CHECK-LABEL: define i32 @cleanup_exit_complex({{.*}})
+// CHECK: call {{.*}} @_ZN1AC1Ei
+//    Spill after bar.
+// CHECK: call {{.*}} @_Z11bar_complex1Ai({{.*}})
+// CHECK: store float %{{.*}}, float* %[[tmp1:[^, ]*]]
+// CHECK: store float %{{.*}}, float* %[[tmp2:[^, ]*]]
+//    Do cleanup.
+// CHECK: call {{.*}} @_ZN1AD1Ev
+// CHECK: switch
+//    Reload before v assignment.
+// CHECK: %[[v1:[^ ]*]] = load float, float* %[[tmp1]]
+// CHECK: %[[v2:[^ ]*]] = load float, float* %[[tmp2]]
+// CHECK: store float %[[v1]], float* %v.realp
+// CHECK: store float %[[v2]], float* %v.imagp