Code generation support for lvalue bit-field conditionals.

[rsmith]

Summary

C++ permits use of (cond ? x.a : y.b) as an lvalue even when a and/or b is a
bit-field. We previously failed to generate IR for such constructs.

Handle these cases with a new form of LValue representing a choice between two
other LValues. Whenever we want to generate a primitive operation on a
conditional lvalue, generate a branch to perform the operation.

This would be sufficient to also support lvalue conditionals between other
kinds of non-simple lvalue, such as a conditional between the imaginary
component of a _Complex T and a vector element, but Sema rejects all the other
combinations for the moment.

One case that's not yet supported is atomic compare-exchange operations on
bitfield conditional lvalues. These only arise through #pragma omp atomic
constructs, and would probably not be too hard to support, but we need to teach
the OpenMP code to cope with its subexpression being emitted multiple times.

[rsmith]

• Remove development aid from test.

[rjmccall]

I always imagined that we'd implement this by just inverting the emission: emit the RHS of the assignment and then pass a callback down to a function that descended into conditional operators and called the callback when it hit a leaf. Having an LValue case that's an arbitrarily-nested conditional seems unfortunate.

[rsmith]

In D85710#2212174, @rjmccall wrote:

I always imagined that we'd implement this by just inverting the emission: emit the RHS of the assignment and then pass a callback down to a function that descended into conditional operators and called the callback when it hit a leaf. Having an LValue case that's an arbitrarily-nested conditional seems unfortunate.

I thought I'd convinced myself that that approach couldn't work, but I'm no longer so convinced. (I had thought there were cases where we would need to run arbitrary code between creating the lvalue and disposing of it, and that arbitrary code could be something we were only able to emit once for whatever reason.) The fact that assignment and compound-assignment operators all evaluate their RHS before their LHS (in the language modes where they're sequenced) helps a lot; expressions such as ((cond ? a.x : a.y) += f()) *= g() still seem like they could compositionally work with this model, and even things like (cond1 ? b : (cond2 ? a.x : a.y) += f()) += g(). Hm, but what about int n = (cond ? a.x : a.y) += 1;? I guess we'd need to carry the intent to perform a load of the conditional lvalue into the callback too.

OK, I think that all works, but I'm a lot less confident of the absence of surprising corners that would defeat that strategy than with the approach of this patch -- the correctness of doing this with a single branch seems to hinge crucially on subtle program structure restrictions, in particular the presumptive fact that we never need control flow to converge between creating the lvalue and consuming it. On the other hand, it would also let us emit better IR for things like (a += 1) *= 2 (removing the intermediate store to a) if we wanted, and maybe it's a good strategy to pursue for that reason?

I can give that a go next time I find some cycles to work on this.

clang/lib/CodeGen/CGAtomic.cpp

class AtomicInfo {
     TypeEvaluationKind EvaluationKind;
     bool UseLibcall;
     LValue LVal;
     CGBitFieldInfo BFI;
   public:
     AtomicInfo(CodeGenFunction &CGF, LValue &lvalue)
         : CGF(CGF), AtomicSizeInBits(0), ValueSizeInBits(0),
           EvaluationKind(TEK_Scalar), UseLibcall(true) {
-      assert(!lvalue.isGlobalReg());
+      assert(!lvalue.isGlobalReg() && !lvalue.isConditional());
       ASTContext &C = CGF.getContext();
       if (lvalue.isSimple()) {
         AtomicTy = lvalue.getType();
         if (auto *ATy = AtomicTy->getAs<AtomicType>())
           ValueTy = ATy->getValueType();
         else
           ValueTy = AtomicTy;
         EvaluationKind = CGF.getEvaluationKind(ValueTy);
llvm::Value *AtomicInfo::EmitAtomicLoadOp(llvm::AtomicOrdering AO,
 
   // Other decoration.
   if (IsVolatile)
     Load->setVolatile(true);
   CGF.CGM.DecorateInstructionWithTBAA(Load, LVal.getTBAAInfo());
   return Load;
 }
 
+/// Determine whether some condition is true for all conditional cases in the
+/// given LValue.
+template<typename Fn>
+static bool forAllConditionals(LValue LV, Fn F) {
+  if (LV.isConditional()) {
+    return forAllConditionals(LV.getConditionalValue(0), F) &&
+           forAllConditionals(LV.getConditionalValue(1), F);
+  }
+  return F(LV);
+}
+
 /// An LValue is a candidate for having its loads and stores be made atomic if
 /// we are operating under /volatile:ms *and* the LValue itself is volatile and
 /// performing such an operation can be performed without a libcall.
 bool CodeGenFunction::LValueIsSuitableForInlineAtomic(LValue LV) {
   if (!CGM.getCodeGenOpts().MSVolatile) return false;
-  AtomicInfo AI(*this, LV);
   bool IsVolatile = LV.isVolatile() || hasVolatileMember(LV.getType());
-  // An atomic is inline if we don't need to use a libcall.
-  bool AtomicIsInline = !AI.shouldUseLibcall();
+  if (!IsVolatile)
+    return false;
   // MSVC doesn't seem to do this for types wider than a pointer.
   if (getContext().getTypeSize(LV.getType()) >
       getContext().getTypeSize(getContext().getIntPtrType()))
     return false;
-  return IsVolatile && AtomicIsInline;
+  // An atomic is inline if we don't need to use a libcall.
+  bool AtomicIsInline = forAllConditionals(LV, [&](LValue LV) {
+    AtomicInfo Atomics(*this, LV);
+    return !Atomics.shouldUseLibcall();
+  });
+  return AtomicIsInline;
 }
 
 RValue CodeGenFunction::EmitAtomicLoad(LValue LV, SourceLocation SL,
                                        AggValueSlot Slot) {
   llvm::AtomicOrdering AO;
   bool IsVolatile = LV.isVolatileQualified();
   if (LV.getType()->isAtomicType()) {
     AO = llvm::AtomicOrdering::SequentiallyConsistent;
RValue AtomicInfo::EmitAtomicLoad(AggValueSlot ResultSlot, SourceLocation Loc,
   return ConvertIntToValueOrAtomic(Load, ResultSlot, Loc, AsValue);
 }
 
 /// Emit a load from an l-value of atomic type.  Note that the r-value
 /// we produce is an r-value of the atomic *value* type.
 RValue CodeGenFunction::EmitAtomicLoad(LValue src, SourceLocation loc,
                                        llvm::AtomicOrdering AO, bool IsVolatile,
                                        AggValueSlot resultSlot) {
+  if (src.isConditional()) {
+    return EmitBranchOnConditionalLValue(src, [&](LValue LV) {
+      return EmitAtomicLoad(LV, loc, AO, IsVolatile, resultSlot);
+    });
+  }
+
   AtomicInfo Atomics(*this, src);
   return Atomics.EmitAtomicLoad(resultSlot, loc, /*AsValue=*/true, AO,
                                 IsVolatile);
 }
 
 /// Copy an r-value into memory as part of storing to an atomic type.
 /// This needs to create a bit-pattern suitable for atomic operations.
 void AtomicInfo::emitCopyIntoMemory(RValue rvalue) const {
void CodeGenFunction::EmitAtomicStore(RValue rvalue, LValue dest,
                                       llvm::AtomicOrdering AO, bool IsVolatile,
                                       bool isInit) {
   // If this is an aggregate r-value, it should agree in type except
   // maybe for address-space qualification.
   assert(!rvalue.isAggregate() ||
          rvalue.getAggregateAddress().getElementType() ==
              dest.getAddress(*this).getElementType());
 
+  if (dest.isConditional()) {
+    return EmitBranchOnConditionalLValue(dest, [&](LValue LV) {
+      return EmitAtomicStore(rvalue, LV, AO, IsVolatile, isInit);
+    });
+  }
+
   AtomicInfo atomics(*this, dest);
   LValue LVal = atomics.getAtomicLValue();
 
   // If this is an initialization, just put the value there normally.
   if (LVal.isSimple()) {
     if (isInit) {
       atomics.emitCopyIntoMemory(rvalue);
       return;
std::pair<RValue, llvm::Value *> CodeGenFunction::EmitAtomicCompareExchange(
   // If this is an aggregate r-value, it should agree in type except
   // maybe for address-space qualification.
   assert(!Expected.isAggregate() ||
          Expected.getAggregateAddress().getElementType() ==
              Obj.getAddress(*this).getElementType());
   assert(!Desired.isAggregate() ||
          Desired.getAggregateAddress().getElementType() ==
              Obj.getAddress(*this).getElementType());
+
+  if (Obj.isConditional()) {
+    return EmitBranchOnConditionalLValue(Obj, [&](LValue LV) {
+      return EmitAtomicCompareExchange(LV, Expected, Desired, Loc, Success,
+                                       Failure, IsWeak, Slot);
+    });
+  }
+
   AtomicInfo Atomics(*this, Obj);
 
   return Atomics.EmitAtomicCompareExchange(Expected, Desired, Success, Failure,
                                            IsWeak);
 }
 
 void CodeGenFunction::EmitAtomicUpdate(
     LValue LVal, llvm::AtomicOrdering AO,
-    const llvm::function_ref<RValue(RValue)> &UpdateOp, bool IsVolatile) {
+    const llvm::function_ref<RValue(RValue)> &UpdateOp, bool IsVolatile,
+    SourceLocation Loc) {
+  if (LVal.isConditional()) {
+    // FIXME: We can mostly EmitBranchOnConditionalLValue here, but there are
+    // two problems with that:
+    // 1) That can result in emitting the same expression twice, which might
+    //    not be correct for some expression forms.
+    // 2) UpdateOp might expect to be called only once. That happens for the
+    //    various OpenMP atomic update expressions of the form
+    //      { v = x; x = f(x); }
+    //    which want to capture a single previous value of x.
+    CGM.Error(Loc, "cannot compile this OpenMP atomic bitfield conditional "
+                   "lvalue update yet");
+    // Recover by pretending we only saw the first case in the conditional.
+    while (LVal.isConditional())
+      LVal = LVal.getConditionalValue(0);
+  }
+
   AtomicInfo Atomics(*this, LVal);
   Atomics.EmitAtomicUpdate(AO, UpdateOp, IsVolatile);
 }
 
 void CodeGenFunction::EmitAtomicInit(Expr *init, LValue dest) {
   AtomicInfo atomics(*this, dest);
 
   switch (atomics.getEvaluationKind()) {

clang/lib/CodeGen/CGExpr.cpp

 }
 
 LValue CodeGenFunction::EmitCheckedLValue(const Expr *E, TypeCheckKind TCK) {
   LValue LV;
   if (SanOpts.has(SanitizerKind::ArrayBounds) && isa<ArraySubscriptExpr>(E))
     LV = EmitArraySubscriptExpr(cast<ArraySubscriptExpr>(E), /*Accessed*/true);
   else
     LV = EmitLValue(E);
-  if (!isa<DeclRefExpr>(E) && !LV.isBitField() && LV.isSimple()) {
+  if (!isa<DeclRefExpr>(E) && LV.isSimple()) {
     SanitizerSet SkippedChecks;
     if (const auto *ME = dyn_cast<MemberExpr>(E)) {
       bool IsBaseCXXThis = IsWrappedCXXThis(ME->getBase());
       if (IsBaseCXXThis)
         SkippedChecks.set(SanitizerKind::Alignment, true);
       if (IsBaseCXXThis || isa<DeclRefExpr>(ME->getBase()))
         SkippedChecks.set(SanitizerKind::Null, true);
     }
RValue CodeGenFunction::EmitLoadOfLValue(LValue LV, SourceLocation Loc) {
 
   if (LV.isMatrixElt()) {
     llvm::LoadInst *Load =
         Builder.CreateLoad(LV.getMatrixAddress(), LV.isVolatileQualified());
     return RValue::get(
         Builder.CreateExtractElement(Load, LV.getMatrixIdx(), "matrixext"));
   }
 
-  assert(LV.isBitField() && "Unknown LValue type!");
+  if (LV.isBitField())
     return EmitLoadOfBitfieldLValue(LV, Loc);
+
+  if (LV.isConditional()) {
+    return EmitBranchOnConditionalLValue(LV, [&](LValue LV) { //
+      return EmitLoadOfLValue(LV, Loc);
+    });
+  }
+
+  llvm_unreachable("unknown lvalue kind");
 }
 
 RValue CodeGenFunction::EmitLoadOfBitfieldLValue(LValue LV,
                                                  SourceLocation Loc) {
   const CGBitFieldInfo &Info = LV.getBitFieldInfo();
 
   // Get the output type.
   llvm::Type *ResLTy = ConvertType(LV.getType());
if (Dst.isMatrixElt()) {
       llvm::Value *Vec = Builder.CreateLoad(Dst.getMatrixAddress());
       Vec = Builder.CreateInsertElement(Vec, Src.getScalarVal(),
                                         Dst.getMatrixIdx(), "matins");
       Builder.CreateStore(Vec, Dst.getMatrixAddress(),
                           Dst.isVolatileQualified());
       return;
     }
 
-    assert(Dst.isBitField() && "Unknown LValue type");
+    if (Dst.isBitField())
       return EmitStoreThroughBitfieldLValue(Src, Dst);
+
+    if (Dst.isConditional()) {
+      return EmitBranchOnConditionalLValue(Dst, [&](LValue LV) {
+        return EmitStoreThroughLValue(Src, LV, isInit);
+      });
+    }
+
+    llvm_unreachable("unknown lvalue type");
   }
 
   // There's special magic for assigning into an ARC-qualified l-value.
   if (Qualifiers::ObjCLifetime Lifetime = Dst.getQuals().getObjCLifetime()) {
     switch (Lifetime) {
     case Qualifiers::OCL_None:
       llvm_unreachable("present but none");
 
static Optional<LValue> EmitLValueOrThrowExpression(CodeGenFunction &CGF,
   if (auto *ThrowExpr = dyn_cast<CXXThrowExpr>(Operand->IgnoreParens())) {
     CGF.EmitCXXThrowExpr(ThrowExpr, /*KeepInsertionPoint*/false);
     return None;
   }
 
   return CGF.EmitLValue(Operand);
 }
 
+LValue CodeGenFunction::MakeConditionalLValue(llvm::Value *Sel, LValue A,
+                                              LValue B) {
+  assert(getContext().hasSameUnqualifiedType(A.getType(), B.getType()) &&
+         "conditional between lvalues of different types");
+
+  TBAAAccessInfo TBAAInfo =
+      CGM.mergeTBAAInfoForConditionalOperator(A.getTBAAInfo(), B.getTBAAInfo());
+
+  auto Vals = std::make_unique<ConditionalLValueStorageType>(A, B);
+  LValue Result = LValue::MakeConditional(Sel, Vals->Values, TBAAInfo);
+  ConditionalLValueStorage.push_back(std::move(Vals));
+  return Result;
+}
+
+/// Given an LValue that is usable in predecessor \p Pred of the current block,
+/// get a corresponding LValue that is usable in this block. Replace the value
+/// with 'undef' if we came from the other predecessor \p OtherPred.
+static LValue getLValueOrUndef(CodeGenFunction &CGF, LValue LVal,
+                               llvm::BasicBlock *Pred,
+                               llvm::BasicBlock *OtherPred) {
+  auto MakeValuePHI = [&](llvm::Value *V) {
+    llvm::PHINode *NewV = CGF.Builder.CreatePHI(V->getType(), 2);
+    NewV->addIncoming(V, Pred);
+    NewV->addIncoming(llvm::UndefValue::get(V->getType()), OtherPred);
+    return NewV;
+  };
+
+  auto MakeAddressPHI = [&](Address Addr) {
+    if (!Addr.isValid())
+      return Addr;
+    return Address(MakeValuePHI(Addr.getPointer()), Addr.getAlignment());
+  };
+
+  if (LVal.isSimple())
+    return LValue::MakeAddr(MakeAddressPHI(LVal.getAddress(CGF)),
+                            LVal.getType(), CGF.getContext(),
+                            LVal.getBaseInfo(), LVal.getTBAAInfo());
+  if (LVal.isVectorElt()) {
+    Address A = MakeAddressPHI(LVal.getVectorAddress());
+    return LValue::MakeVectorElt(A, MakeValuePHI(LVal.getVectorIdx()),
+                                 LVal.getType(), LVal.getBaseInfo(),
+                                 LVal.getTBAAInfo());
+  }
+  if (LVal.isExtVectorElt())
+    return LValue::MakeExtVectorElt(MakeAddressPHI(LVal.getExtVectorAddress()),
+                                    LVal.getExtVectorElts(), LVal.getType(),
+                                    LVal.getBaseInfo(), LVal.getTBAAInfo());
+  if (LVal.isBitField())
+    return LValue::MakeBitfield(MakeAddressPHI(LVal.getBitFieldAddress()),
+                                LVal.getBitFieldInfo(), LVal.getType(),
+                                LVal.getBaseInfo(), LVal.getTBAAInfo());
+  if (LVal.isGlobalReg())
+    return LValue::MakeGlobalReg(MakeAddressPHI(LVal.getGlobalRegAddress()),
+                                 LVal.getType());
+  if (LVal.isMatrixElt()) {
+    Address A = MakeAddressPHI(LVal.getMatrixAddress());
+    return LValue::MakeMatrixElt(A, MakeValuePHI(LVal.getMatrixIdx()),
+                                 LVal.getType(), LVal.getBaseInfo(),
+                                 LVal.getTBAAInfo());
+  }
+
+  if (LVal.isConditional()) {
+    LValue LHS =
+        getLValueOrUndef(CGF, LVal.getConditionalValue(0), Pred, OtherPred);
+    LValue RHS =
+        getLValueOrUndef(CGF, LVal.getConditionalValue(1), Pred, OtherPred);
+    return CGF.MakeConditionalLValue(MakeValuePHI(LVal.getCondition()),
+                                     LHS, RHS);
+  }
+
+  llvm_unreachable("unknown lvalue kind");
+}
+
+LValue CodeGenFunction::EmitPHI(PHIValue<LValue> A, PHIValue<LValue> B) {
+  // Easy case: both lvalues are simple. In this case, we can just emit a single
+  // phi and produce a simple lvalue result.
+  if (A.Value.isSimple() && B.Value.isSimple()) {
+    llvm::PHINode *Phi = Builder.CreatePHI(A.Value.getPointer(*this)->getType(),
+                                           2, "cond-lvalue");
+    Phi->addIncoming(A.Value.getPointer(*this), A.Pred);
+    Phi->addIncoming(B.Value.getPointer(*this), B.Pred);
+
+    CharUnits Alignment =
+        std::min(A.Value.getAlignment(), B.Value.getAlignment());
+    AlignmentSource AlignSource =
+        std::max(A.Value.getBaseInfo().getAlignmentSource(),
+                 B.Value.getBaseInfo().getAlignmentSource());
+    TBAAAccessInfo TBAAInfo = CGM.mergeTBAAInfoForConditionalOperator(
+        A.Value.getTBAAInfo(), B.Value.getTBAAInfo());
+
+    Address Result(Phi, Alignment);
+    return MakeAddrLValue(Result, A.Value.getType(),
+                          LValueBaseInfo(AlignSource), TBAAInfo);
+  }
+
+  // Hard case: create a conditional lvalue merging the cases.
+  llvm::PHINode *Sel = Builder.CreatePHI(
+      llvm::Type::getInt1Ty(getLLVMContext()), 2, "cond.lval.sel");
+  Sel->addIncoming(llvm::ConstantInt::getFalse(getLLVMContext()), A.Pred);
+  Sel->addIncoming(llvm::ConstantInt::getTrue(getLLVMContext()), B.Pred);
+
+  // Make sure both LValues are usable in the continuation block.
+  LValue AVal = getLValueOrUndef(*this, A.Value, A.Pred, B.Pred);
+  LValue BVal = getLValueOrUndef(*this, B.Value, B.Pred, A.Pred);
+  return MakeConditionalLValue(Sel, AVal, BVal);
+}
+
+/// Apply 'Get' to each value in a collection and build a PHI node from the
+/// resulting values. Get should callable as if of type 'llvm::Value *Get(T)'.
+///
+/// The projection may produce null pointers for some inputs. If all inputs
+/// project to null pointers, a null pointer is returned. Otherwise, null
+/// inputs are replaced by undef values.
+template<typename T, typename Fn>
+static llvm::PHINode *makeProjectedPHI(CodeGenFunction &CGF,
+                                       ArrayRef<PHIValue<T>> Values, Fn Get) {
+  llvm::PHINode *Phi = nullptr;
+  for (auto &PhiV : Values) {
+    llvm::Value *V = Get(PhiV.Value);
+    if (V) {
+      if (!Phi) {
+        Phi = CGF.Builder.CreatePHI(V->getType(), Values.size());
+        for (auto &PrevPhiV : Values) {
+          if (PrevPhiV.Pred == PhiV.Pred)
+            break;
+          Phi->addIncoming(llvm::UndefValue::get(V->getType()), PrevPhiV.Pred);
+        }
+      }
+      Phi->addIncoming(V, PhiV.Pred);
+    } else if (Phi) {
+      Phi->addIncoming(llvm::UndefValue::get(Phi->getType()), PhiV.Pred);
+    }
+  }
+  return Phi;
+}
+
+llvm::Value *
+CodeGenFunction::EmitPHI(ArrayRef<PHIValue<llvm::Value *>> Values) {
+  return makeProjectedPHI(*this, Values, [](llvm::Value *V) { return V; });
+}
+
+RValue CodeGenFunction::EmitPHI(ArrayRef<PHIValue<RValue>> Values) {
+  assert(!Values.empty() && "no values to select between");
+  RValue First = Values.front().Value;
+
+  if (First.isScalar())
+    return RValue::get(makeProjectedPHI(
+        *this, Values, [](RValue V) { return V.getScalarVal(); }));
+
+  if (First.isComplex()) {
+    llvm::Value *Real = makeProjectedPHI(
+        *this, Values, [](RValue V) { return V.getComplexVal().first; });
+    llvm::Value *Imag = makeProjectedPHI(
+        *this, Values, [](RValue V) { return V.getComplexVal().second; });
+    return RValue::getComplex(Real, Imag);
+  }
+
+  if (First.isAggregate()) {
+    llvm::SmallVector<PHIValue<Address>, 2> Addresses;
+    bool Volatile = false;
+    for (auto &V : Values) {
+      Addresses.push_back({V.Value.getAggregateAddress(), V.Pred});
+      Volatile |= V.Value.isVolatileQualified();
+    }
+    Address Addr = EmitPHI(Addresses);
+    return RValue::getAggregate(Addr, Volatile);
+  }
+
+  llvm_unreachable("unknown rvalue kind");
+}
+
+Address CodeGenFunction::EmitPHI(ArrayRef<PHIValue<Address>> Values) {
+  CharUnits Alignment = CharUnits::Zero();
+  llvm::Value *Ptr =
+      makeProjectedPHI(*this, Values, [&](Address A) -> llvm::Value * {
+        if (!A.isValid())
+          return nullptr;
+        Alignment = Alignment.isZero() ? A.getAlignment()
+                                       : std::min(Alignment, A.getAlignment());
+        return A.getPointer();
+      });
+  if (!Ptr)
+    return Address::invalid();
+  assert(!Alignment.isZero() && "valid address had zero alignment?");
+  return Address(Ptr, Alignment);
+}
+
 LValue CodeGenFunction::
 EmitConditionalOperatorLValue(const AbstractConditionalOperator *expr) {
   if (!expr->isGLValue()) {
     // ?: here should be an aggregate.
     assert(hasAggregateEvaluationKind(expr->getType()) &&
            "Unexpected conditional operator!");
     return EmitAggExprToLValue(expr);
   }
EmitConditionalOperatorLValue(const AbstractConditionalOperator *expr) {
   // Any temporaries created here are conditional.
   EmitBlock(lhsBlock);
   incrementProfileCounter(expr);
   eval.begin(*this);
   Optional<LValue> lhs =
       EmitLValueOrThrowExpression(*this, expr->getTrueExpr());
   eval.end(*this);
 
-  if (lhs && !lhs->isSimple())
-    return EmitUnsupportedLValue(expr, "conditional operator");
-
   lhsBlock = Builder.GetInsertBlock();
   if (lhs)
     Builder.CreateBr(contBlock);
 
   // Any temporaries created here are conditional.
   EmitBlock(rhsBlock);
   eval.begin(*this);
   Optional<LValue> rhs =
       EmitLValueOrThrowExpression(*this, expr->getFalseExpr());
   eval.end(*this);
-  if (rhs && !rhs->isSimple())
-    return EmitUnsupportedLValue(expr, "conditional operator");
   rhsBlock = Builder.GetInsertBlock();
 
   EmitBlock(contBlock);
 
-  if (lhs && rhs) {
-    llvm::PHINode *phi =
-        Builder.CreatePHI(lhs->getPointer(*this)->getType(), 2, "cond-lvalue");
-    phi->addIncoming(lhs->getPointer(*this), lhsBlock);
-    phi->addIncoming(rhs->getPointer(*this), rhsBlock);
-    Address result(phi, std::min(lhs->getAlignment(), rhs->getAlignment()));
-    AlignmentSource alignSource =
-      std::max(lhs->getBaseInfo().getAlignmentSource(),
-               rhs->getBaseInfo().getAlignmentSource());
-    TBAAAccessInfo TBAAInfo = CGM.mergeTBAAInfoForConditionalOperator(
-        lhs->getTBAAInfo(), rhs->getTBAAInfo());
-    return MakeAddrLValue(result, expr->getType(), LValueBaseInfo(alignSource),
-                          TBAAInfo);
-  } else {
-    assert((lhs || rhs) &&
-           "both operands of glvalue conditional are throw-expressions?");
-    return lhs ? *lhs : *rhs;
-  }
-}
+  if (lhs && rhs)
+    return EmitPHI({*lhs, lhsBlock}, {*rhs, rhsBlock});
+
 
 /// EmitCastLValue - Casts are never lvalues unless that cast is to a reference
 /// type. If the cast is to a reference, we can have the usual lvalue result,
 /// otherwise if a cast is needed by the code generator in an lvalue context,
 /// then it must mean that we need the address of an aggregate in order to
 /// access one of its members.  This can happen for all the reasons that casts
 /// are permitted with aggregate result, including noop aggregate casts, and
 /// cast from scalar to union.

clang/lib/CodeGen/CGStmtOpenMP.cpp

std::pair<bool, RValue> CodeGenFunction::EmitOMPAtomicSimpleUpdateExpr(
   auto Res = emitOMPAtomicRMW(*this, X, E, BO, AO, IsXLHSInRHSPart);
   if (!Res.first) {
     if (X.isGlobalReg()) {
       // Emit an update expression: 'xrval' binop 'expr' or 'expr' binop
       // 'xrval'.
       EmitStoreThroughLValue(CommonGen(EmitLoadOfLValue(X, Loc)), X);
     } else {
       // Perform compare-and-swap procedure.
-      EmitAtomicUpdate(X, AO, CommonGen, X.getType().isVolatileQualified());
+      EmitAtomicUpdate(X, AO, CommonGen, X.getType().isVolatileQualified(),
+                       Loc);
     }
   }
   return Res;
 }
 
 static void emitOMPAtomicUpdateExpr(CodeGenFunction &CGF,
                                     llvm::AtomicOrdering AO, const Expr *X,
                                     const Expr *E, const Expr *UE,

clang/lib/CodeGen/CGValue.h

public:
   explicit LValueBaseInfo(AlignmentSource Source = AlignmentSource::Type)
     : AlignSource(Source) {}
   AlignmentSource getAlignmentSource() const { return AlignSource; }
   void setAlignmentSource(AlignmentSource Source) { AlignSource = Source; }
 
   void mergeForCast(const LValueBaseInfo &Info) {
     setAlignmentSource(Info.getAlignmentSource());
   }
+  static LValueBaseInfo mergeForConditional(LValueBaseInfo A,
+                                            LValueBaseInfo B) {
+    AlignmentSource Weakest = AlignmentSource(
+        std::max(unsigned(A.AlignSource), unsigned(B.AlignSource)));
+    return LValueBaseInfo(Weakest);
+  }
 };
 
 /// LValue - This represents an lvalue references.  Because C/C++ allow
 /// bitfields, this is not a simple LLVM pointer, it may be a pointer plus a
 /// bitrange.
 class LValue {
   enum {
     Simple,       // This is a normal l-value, use getAddress().
     VectorElt,    // This is a vector element l-value (V[i]), use getVector*
     BitField,     // This is a bitfield l-value, use getBitfield*.
     ExtVectorElt, // This is an extended vector subset, use getExtVectorComp
     GlobalReg,    // This is a register l-value, use getGlobalReg()
-    MatrixElt     // This is a matrix element, use getVector*
+    MatrixElt,    // This is a matrix element, use getVector*
+    Conditional   // This is a conditional involving a non-simple lvalue.
   } LVType;
 
   llvm::Value *V;
 
   union {
     // Index into a vector subscript: V[i]
     llvm::Value *VectorIdx;
 
     // ExtVector element subset: V.xyx
     llvm::Constant *VectorElts;
 
     // BitField start bit and size
     const CGBitFieldInfo *BitFieldInfo;
+
+    // For a conditional lvalue, the two possible underlying lvalues.
+    // V is an i1 indicating which one of these is selected.
+    LValue (*CondVals)[2];
   };
 
   QualType Type;
 
   // 'const' is unused here
   Qualifiers Quals;
 
   // The alignment to use when accessing this lvalue.  (For vector elements,

 
 public:
   bool isSimple() const { return LVType == Simple; }
   bool isVectorElt() const { return LVType == VectorElt; }
   bool isBitField() const { return LVType == BitField; }
   bool isExtVectorElt() const { return LVType == ExtVectorElt; }
   bool isGlobalReg() const { return LVType == GlobalReg; }
   bool isMatrixElt() const { return LVType == MatrixElt; }
+  bool isConditional() const { return LVType == Conditional; }
 
   bool isVolatileQualified() const { return Quals.hasVolatile(); }
   bool isRestrictQualified() const { return Quals.hasRestrict(); }
   unsigned getVRQualifiers() const {
     return Quals.getCVRQualifiers() & ~Qualifiers::Const;
   }
 
   QualType getType() const { return Type; }
public:
   const CGBitFieldInfo &getBitFieldInfo() const {
     assert(isBitField());
     return *BitFieldInfo;
   }
 
   // global register lvalue
   llvm::Value *getGlobalReg() const { assert(isGlobalReg()); return V; }
 
+  Address getGlobalRegAddress() const {
+    return Address(getGlobalReg(), getAlignment());
+  }
+
+  // conditional lvalue
+  llvm::Value *getCondition() const {
+    assert(isConditional());
+    return V;
+  }
+
+  LValue getConditionalValue(bool Which) const {
+    assert(isConditional());
+    return (*CondVals)[Which];
+  }
+
   static LValue MakeAddr(Address address, QualType type, ASTContext &Context,
                          LValueBaseInfo BaseInfo, TBAAAccessInfo TBAAInfo) {
     Qualifiers qs = type.getQualifiers();
     qs.setObjCGCAttr(Context.getObjCGCAttrKind(type));
 
     LValue R;
     R.LVType = Simple;
     assert(address.getPointer()->getType()->isPointerTy());
static LValue MakeMatrixElt(Address matAddress, llvm::Value *Idx,
     R.LVType = MatrixElt;
     R.V = matAddress.getPointer();
     R.VectorIdx = Idx;
     R.Initialize(type, type.getQualifiers(), matAddress.getAlignment(),
                  BaseInfo, TBAAInfo);
     return R;
   }
 
+  static LValue MakeConditional(llvm::Value *Cond, LValue (&Vals)[2],
+                                TBAAAccessInfo TBAAInfo) {
+    LValue R;
+    R.LVType = Conditional;
+    R.V = Cond;
+    R.CondVals = &Vals;
+    // The properties of a conditional LValue should generally not matter,
+    // because any use should generate a branch and handle the two cases
+    // independently.
+    R.Initialize(Vals[0].getType(), Vals[0].getQuals(),
+                 std::min(Vals[0].getAlignment(), Vals[1].getAlignment()),
+                 LValueBaseInfo::mergeForConditional(Vals[0].getBaseInfo(),
+                                                     Vals[1].getBaseInfo()),
+                 TBAAInfo);
+    return R;
+  }
+
   RValue asAggregateRValue(CodeGenFunction &CGF) const {
     return RValue::getAggregate(getAddress(CGF), isVolatileQualified());
   }
 };
 
 /// An aggregate value slot.
 class AggValueSlot {
   /// The address.

clang/lib/CodeGen/CodeGenFunction.h

template <> struct DominatingValue<RValue> {
   static saved_type save(CodeGenFunction &CGF, type value) {
     return saved_type::save(CGF, value);
   }
   static type restore(CodeGenFunction &CGF, saved_type value) {
     return value.restore(CGF);
   }
 };
 
+/// An input to a PHI node.
+template<typename T> struct PHIValue {
+  T Value;
+  llvm::BasicBlock *Pred;
+
+  template<typename Fn> static PHIValue make(llvm::BasicBlock *Pred, Fn F) {
+    return {F(), Pred};
+  }
+};
+template<> struct PHIValue<void> {
+  llvm::BasicBlock *Pred;
+
+  template<typename Fn> static PHIValue make(llvm::BasicBlock *Pred, Fn F) {
+    F();
+    return {Pred};
+  }
+};
+
 /// CodeGenFunction - This class organizes the per-function state that is used
 /// while generating LLVM code.
 class CodeGenFunction : public CodeGenTypeCache {
   CodeGenFunction(const CodeGenFunction &) = delete;
   void operator=(const CodeGenFunction &) = delete;
 
   friend class CGCXXABI;
 public:
private:
   // VLASizeMap - This keeps track of the associated size for each VLA type.
   // We track this by the size expression rather than the type itself because
   // in certain situations, like a const qualifier applied to an VLA typedef,
   // multiple VLA types can share the same size expression.
   // FIXME: Maybe this could be a stack of maps that is pushed/popped as we
   // enter/leave scopes.
   llvm::DenseMap<const Expr*, llvm::Value*> VLASizeMap;
 
+  struct ConditionalLValueStorageType {
+    ConditionalLValueStorageType(LValue A, LValue B) : Values{A, B} {}
+    LValue Values[2];
+  };
+  std::vector<std::unique_ptr<ConditionalLValueStorageType>>
+      ConditionalLValueStorage;
+
   /// A block containing a single 'unreachable' instruction.  Created
   /// lazily by getUnreachableBlock().
   llvm::BasicBlock *UnreachableBlock = nullptr;
 
   /// Counts of the number return expressions in the function.
   unsigned NumReturnExprs = 0;
 
   /// Count the number of simple (constant) return expressions in the function.
AggValueSlot CreateAggTemp(QualType T, const Twine &Name = "tmp",
     return AggValueSlot::forAddr(CreateMemTemp(T, Name, Alloca),
                                  T.getQualifiers(),
                                  AggValueSlot::IsNotDestructed,
                                  AggValueSlot::DoesNotNeedGCBarriers,
                                  AggValueSlot::IsNotAliased,
                                  AggValueSlot::DoesNotOverlap);
   }
 
+  /// Make a conditional lvalue that selects between the two given LValues.
+  LValue MakeConditionalLValue(llvm::Value *Sel, LValue A, LValue B);
+
+  /// Emit a PHI between values.
+  llvm::Value *EmitPHI(llvm::ArrayRef<PHIValue<llvm::Value*>> Values);
+  llvm::Value *EmitPHI(PHIValue<llvm::Value*> A, PHIValue<llvm::Value*> B) {
+    return EmitPHI({A, B});
+  }
+
+  LValue EmitPHI(PHIValue<LValue> A, PHIValue<LValue> B);
+
+  RValue EmitPHI(llvm::ArrayRef<PHIValue<RValue>> Values);
+  RValue EmitPHI(PHIValue<RValue> A, PHIValue<RValue> B) {
+    return EmitPHI({A, B});
+  }
+
+  Address EmitPHI(llvm::ArrayRef<PHIValue<Address>> Values);
+  Address EmitPHI(PHIValue<Address> A, PHIValue<Address> B) {
+    return EmitPHI({A, B});
+  }
+
+  template<typename T, typename U>
+  std::pair<T, U> EmitPHI(PHIValue<std::pair<T, U>> A,
+                          PHIValue<std::pair<T, U>> B) {
+    return {EmitPHI({A.Value.first, A.Pred}, {B.Value.first, B.Pred}),
+            EmitPHI({A.Value.second, A.Pred}, {B.Value.second, B.Pred})};
+  }
+
+  void EmitPHI(PHIValue<void> A, PHIValue<void> B) {}
+
+  /// Emit an atomic operation on both possible cases of an atomic lvalue.
+  template<typename Fn>
+  auto EmitBranchOnConditionalLValue(LValue CondLV, Fn F)
+      -> decltype(F(CondLV)) {
+    assert(CondLV.isConditional() && "not a conditional LValue");
+    using Result = decltype(F(CondLV));
+
+    llvm::BasicBlock *LHSBlock = createBasicBlock("cond.lval.lhs");
+    llvm::BasicBlock *RHSBlock = createBasicBlock("cond.lval.rhs");
+    llvm::BasicBlock *ContBlock = createBasicBlock("cond.lval.cont");
+    Builder.CreateCondBr(CondLV.getCondition(), RHSBlock, LHSBlock);
+
+    EmitBlock(LHSBlock);
+    PHIValue<Result> LHSValue = PHIValue<Result>::make(
+        LHSBlock, [&] { return F(CondLV.getConditionalValue(0)); });
+    EmitBranch(ContBlock);
+
+    EmitBlock(RHSBlock);
+    PHIValue<Result> RHSValue = PHIValue<Result>::make(
+        RHSBlock, [&] { return F(CondLV.getConditionalValue(1)); });
+    EmitBranch(ContBlock);
+
+    EmitBlock(ContBlock);
+    return EmitPHI(LHSValue, RHSValue);
+  }
+
   /// Emit a cast to void* in the appropriate address space.
   llvm::Value *EmitCastToVoidPtr(llvm::Value *value);
 
   /// EvaluateExprAsBool - Perform the usual unary conversions on the specified
   /// expression and compare the result against zero, returning an Int1Ty value.
   llvm::Value *EvaluateExprAsBool(const Expr *E);
 
   /// EmitIgnoredExpr - Emit an expression in a context which ignores the result.
std::pair<RValue, llvm::Value *> EmitAtomicCompareExchange(
       llvm::AtomicOrdering Success =
           llvm::AtomicOrdering::SequentiallyConsistent,
       llvm::AtomicOrdering Failure =
           llvm::AtomicOrdering::SequentiallyConsistent,
       bool IsWeak = false, AggValueSlot Slot = AggValueSlot::ignored());
 
   void EmitAtomicUpdate(LValue LVal, llvm::AtomicOrdering AO,
                         const llvm::function_ref<RValue(RValue)> &UpdateOp,
-                        bool IsVolatile);
+                        bool IsVolatile, SourceLocation Loc);
 
   /// EmitToMemory - Change a scalar value from its value
   /// representation to its in-memory representation.
   llvm::Value *EmitToMemory(llvm::Value *Value, QualType Ty);
 
   /// EmitFromMemory - Change a scalar value from its memory
   /// representation to its value representation.
   llvm::Value *EmitFromMemory(llvm::Value *Value, QualType Ty);

clang/test/CodeGenCXX/conditional-expr-lvalue.cpp

-// RUN: %clang_cc1 -emit-llvm-only %s
-void f(bool flag) {
+// RUN: %clang_cc1 -triple x86_64-linux-gnu -emit-llvm %s -o - -fopenmp | FileCheck %s
+
+// CHECK-LABEL: define {{.*}} @{{.*}}simple_scalar_cond
+void simple_scalar_cond(bool flag) {
+  // CHECK: store i32 1, i32* %[[A:.*]],
   int a = 1;
+  // CHECK: store i32 2, i32* %[[B:.*]],
   int b = 2;
   
+  // CHECK: %[[LVAL:.*]] = phi i32* [ %[[A]], {{.*}} ], [ %[[B]], {{.*}} ]
+  // CHECK: store i32 3, i32* %[[LVAL]],
   (flag ? a : b) = 3;
 }
 
 // PR10756
 namespace test0 {
   struct A {
     A(const A &);
     A &operator=(const A &);
     A sub() const;
     void foo() const;
   };
+  // CHECK-LABEL: define {{.*}} @{{.*}}test0
   void foo(bool cond, const A &a) {
+    // CHECK: %[[TMP:.*]] = alloca %"struct.test0::A",
+    // CHECK: br i1
+    //
+    // CHECK: call void @_ZN5test01AC1ERKS0_(%"struct.test0::A"* %[[TMP]],
+    // CHECK: br label
+    //
+    // CHECK: call void @_ZNK5test01A3subEv(%"struct.test0::A"* sret align 1 %[[TMP]],
+    // CHECK: br label
+    //
+    // CHECK: call void @_ZNK5test01A3fooEv(%"struct.test0::A"* %[[TMP]])
     (cond ? a : a.sub()).foo();
   }
 }
+
+namespace bitfields {
+  struct A {
+    int m : 3;
+    int n : 5;
+  } a1, a2;
+
+  // CHECK-LABEL: define {{.*}} @{{.*}}load
+  int load(bool b) {
+    // CHECK: br i1
+    //
+    // CHECK: load {{.*}}@_ZN9bitfields2a1E, i32 0, i32 0
+    // CHECK: shl {{.*}}, 5
+    // CHECK: ashr {{.*}}, 5
+    // CHECK: br
+    //
+    // CHECK: load {{.*}}@_ZN9bitfields2a2E, i32 0, i32 0
+    // CHECK: ashr {{.*}}, 3
+    // CHECK: br
+    return b ? a1.m : a2.n;
+  }
+
+  // CHECK-LABEL: define {{.*}} @{{.*}}store
+  void store(bool b, int k) {
+    // CHECK: br i1
+    // CHECK: %[[SEL:.*]] = phi i1
+    // CHECK: %[[A1:.*]] = phi i8* {{.*}} @_ZN9bitfields2a1E, {{.*}} [ undef,
+    // CHECK: %[[A2:.*]] = phi i8* {{.*}} @_ZN9bitfields2a2E, {{.*}} [ undef,
+    // CHECK: br i1 %[[SEL]]
+    //
+    // CHECK: load {{.*}}%[[A1]]
+    // CHECK: and {{.*}}, 7
+    // CHECK: and {{.*}}, -8
+    // CHECK: or
+    // CHECK: store
+    // CHECK: br label
+    //
+    // CHECK: load {{.*}}%[[A2]]
+    // CHECK: and {{.*}}, 31
+    // CHECK: shl {{.*}}, 3
+    // CHECK: and {{.*}}, 7
+    // CHECK: or
+    // CHECK: store
+    // CHECK: br label
+    (b ? a1.m : a2.n) = k;
+  }
+
+  // CHECK-LABEL: define {{.*}} @{{.*}}update
+  void update(bool b, int k) {
+    // 1: Branch on condition and evaluate the chosen lvalue.
+    //
+    // CHECK: br i1
+    // CHECK: %[[SEL:.*]] = phi i1
+    // CHECK: %[[A1:.*]] = phi i8* {{.*}} @_ZN9bitfields2a1E, {{.*}} [ undef,
+    // CHECK: %[[A2:.*]] = phi i8* {{.*}} @_ZN9bitfields2a2E, {{.*}} [ undef,
+    // CHECK: br i1 %[[SEL]]
+    //
+    // 2: Branch on condition and load the relevant value.
+    //
+    // CHECK: load {{.*}}%[[A1]]
+    // CHECK: shl {{.*}}, 5
+    // CHECK: ashr {{.*}}, 5
+    // CHECK: br
+    //
+    // CHECK: load {{.*}}%[[A2]]
+    // CHECK: ashr {{.*}}, 3
+    // CHECK: br
+    //
+    // 3: Add k.
+    //
+    // CHECK: add nsw
+    // CHECK: br i1
+    //
+    // 4: Branch on condition and store the new value.
+    //
+    // CHECK: load {{.*}}%[[A1]]
+    // CHECK: and {{.*}}, 7
+    // CHECK: and {{.*}}, -8
+    // CHECK: or
+    // CHECK: store
+    // CHECK: br label
+    //
+    // CHECK: load {{.*}}%[[A2]]
+    // CHECK: and {{.*}}, 31
+    // CHECK: shl {{.*}}, 3
+    // CHECK: and {{.*}}, 7
+    // CHECK: or
+    // CHECK: store
+    // CHECK: br label
+    (b ? a1.m : a2.n) += k;
+  }
+
+  // CHECK-LABEL: define {{.*}} @{{.*}}atomic_load
+  int atomic_load(bool b) {
+    // CHECK: br i1
+    // CHECK: %[[SEL:.*]] = phi i1
+    // CHECK: %[[A1:.*]] = phi i8* {{.*}} @_ZN9bitfields2a1E, {{.*}} [ undef,
+    // CHECK: %[[A2:.*]] = phi i8* {{.*}} @_ZN9bitfields2a2E, {{.*}} [ undef,
+    // CHECK: br i1 %[[SEL]]
+    //
+    // CHECK: %[[A1b:.*]] = getelementptr i8, i8* %[[A1]], i64 0
+    // CHECK: %[[A1c:.*]] = bitcast i8* %[[A1b]] to i32*
+    // CHECK: load atomic {{.*}}%[[A1c]]
+    // CHECK: shl i32 {{.*}}, 29
+    // CHECK: ashr i32 {{.*}}, 29
+    // CHECK: br label
+    //
+    // CHECK: %[[A2b:.*]] = getelementptr i8, i8* %[[A2]], i64 0
+    // CHECK: %[[A2c:.*]] = bitcast i8* %[[A2b]] to i32*
+    // CHECK: load atomic {{.*}}%[[A2c]]
+    // CHECK: shl i32 {{.*}}, 24
+    // CHECK: ashr i32 {{.*}}, 27
+    // CHECK: br label
+    //
+    // CHECK: call void @__kmpc_flush
+    int v;
+    #pragma omp atomic seq_cst read
+    v = (b ? a1.m : a2.n);
+    return v;
+  }
+
+  // CHECK-LABEL: define {{.*}} @{{.*}}atomic_store
+  void atomic_store(bool b, int k) {
+    // CHECK: br i1
+    // CHECK: %[[SEL:.*]] = phi i1
+    // CHECK: %[[A1:.*]] = phi i8* {{.*}} @_ZN9bitfields2a1E, {{.*}} [ undef,
+    // CHECK: %[[A2:.*]] = phi i8* {{.*}} @_ZN9bitfields2a2E, {{.*}} [ undef,
+    // CHECK: br i1 %[[SEL]]
+    //
+    // CHECK: %[[A1b:.*]] = getelementptr i8, i8* %[[A1]], i64 0
+    // CHECK: %[[A1c:.*]] = bitcast i8* %[[A1b]] to i32*
+    // CHECK: load atomic {{.*}}%[[A1c]]
+    // CHECK: and i32 {{.*}}, 7
+    // CHECK: and i32 {{.*}}, -8
+    // CHECK: or
+    // CHECK: cmpxchg
+    // CHECK: br i1
+    // CHECK: br label
+    //
+    // CHECK: %[[A2b:.*]] = getelementptr i8, i8* %[[A2]], i64 0
+    // CHECK: %[[A2c:.*]] = bitcast i8* %[[A2b]] to i32*
+    // CHECK: load atomic {{.*}}%[[A2c]]
+    // CHECK: and i32 {{.*}}, 31
+    // CHECK: shl i32 {{.*}}, 3
+    // CHECK: and i32 {{.*}}, -249
+    // CHECK: or
+    // CHECK: cmpxchg
+    // CHECK: br i1
+    // CHECK: br label
+    //
+    // CHECK: call void @__kmpc_flush
+    #pragma omp atomic seq_cst write
+    (b ? a1.m : a2.n) = k;
+  }
+}