[NOT FOR REVIEW] Experimental support for zero-or-trap behavior for uninitialized variables.

[rsmith]

Summary

Add <type> @llvm.trapping.<type>(<type>) intrinsic.

This is intended to produce either the given value or, if we can trace a
use of the value to an instruction with side-effects, a trap.
Notionally, it behaves as a nondeterministic choice between the given
value and poison, where the choice is made angelically such that the
given value is always chosen when the program does not reach a trap.

Simplify trapping(x) and convert it into traps where possible.

Update Clang CodeGen to produce trapping(x) in trivial auto var init
mode.

[rsmith]

• The second operand of 'store' is the pointer, not the first.

[jfb]

Overall I like this approach.

I think it needs three more things to make it:

• Better size optimizations. I measured the code size impact on a codebase which deploys variable auto-init already, and it's a 0.5% code size hit. Considering that auto-init itself was 1%, it means the mitigation now costs 50% more. I haven't dug into why the increase is such, and I assume that there's low-lying fruits.
• I haven't measure performance impact. It might be zero.
• I think we'd need opt remarks support, because we'd want to audit all the places where a trap is left behind.

clang/lib/CodeGen/CGDecl.cpp

1166

Here you need something like:

auto *PointerTy = Ty->getPointerTo(Loc.getAddressSpace());
if (V->getType() != PointerTy)
  Loc = Builder.CreateBitCast(Loc, PointerTy);

Because you can be storing a constant which is layout-compatible with the location, but which doesn't have the same type (say, when we have an explicit padding array of bytes). Line 1184 does that already for other code paths.

[jdoerfert]

FWIW, I tried to solve something similar the other day. My solution sketch looked like this: https://godbolt.org/z/bRQPjd
The idea would be that we teach DSE (and others) to remove the llvm.undef.init intrinsic if the location is overwritten.
In the example above only SROA kicks in properly. I guess this solution is more powerful though.

clang/lib/CodeGen/CGDecl.cpp

static Address createUnnamedGlobalForMemcpyFrom(CodeGenModule &CGM,
   if (SrcPtr.getType() != BP)
     SrcPtr = Builder.CreateBitCast(SrcPtr, BP);
   return SrcPtr;
 }
 
 static void emitStoresForConstant(CodeGenModule &CGM, const VarDecl &D,
                                   Address Loc, bool isVolatile,
                                   CGBuilderTy &Builder,
-                                  llvm::Constant *constant) {
+                                  llvm::Constant *constant, bool Trapping) {
   auto *Ty = constant->getType();
   uint64_t ConstantSize = CGM.getDataLayout().getTypeAllocSize(Ty);
   if (!ConstantSize)
     return;
 
   bool canDoSingleStore = Ty->isIntOrIntVectorTy() ||
                           Ty->isPtrOrPtrVectorTy() || Ty->isFPOrFPVectorTy();
-  if (canDoSingleStore) {
-    Builder.CreateStore(constant, Loc, isVolatile);
+  if (canDoSingleStore || Trapping) {
+    llvm::Value *V = constant;
+
+    // Pass through @llvm.trapping if requested.
+    if (Trapping) {
+      llvm::Function *TrapFn = llvm::Intrinsic::getDeclaration(
+          &CGM.getModule(), llvm::Intrinsic::trapping, {V->getType()});
+      V = Builder.CreateCall(TrapFn, {V});
+    }
+
+    Builder.CreateStore(V, Loc, isVolatile);
     return;
   }
 
   auto *SizeVal = llvm::ConstantInt::get(CGM.IntPtrTy, ConstantSize);
 
   // If the initializer is all or mostly the same, codegen with bzero / memset
   // then do a few stores afterward.
   if (shouldUseBZeroPlusStoresToInitialize(constant, ConstantSize)) {
static void emitStoresForConstant(CodeGenModule &CGM, const VarDecl &D,
   if (shouldSplitConstantStore(CGM, ConstantSize)) {
     if (auto *STy = dyn_cast<llvm::StructType>(Ty)) {
       // FIXME: handle the case when STy != Loc.getElementType().
       if (STy == Loc.getElementType()) {
         for (unsigned i = 0; i != constant->getNumOperands(); i++) {
           Address EltPtr = Builder.CreateStructGEP(Loc, i);
           emitStoresForConstant(
               CGM, D, EltPtr, isVolatile, Builder,
-              cast<llvm::Constant>(Builder.CreateExtractValue(constant, i)));
+              cast<llvm::Constant>(Builder.CreateExtractValue(constant, i)),
+              Trapping);
         }
         return;
       }
     } else if (auto *ATy = dyn_cast<llvm::ArrayType>(Ty)) {
       // FIXME: handle the case when ATy != Loc.getElementType().
       if (ATy == Loc.getElementType()) {
         for (unsigned i = 0; i != ATy->getNumElements(); i++) {
           Address EltPtr = Builder.CreateConstArrayGEP(Loc, i);
           emitStoresForConstant(
               CGM, D, EltPtr, isVolatile, Builder,
-              cast<llvm::Constant>(Builder.CreateExtractValue(constant, i)));
+              cast<llvm::Constant>(Builder.CreateExtractValue(constant, i)),
+              Trapping);
         }
         return;
       }
     }
   }
 
   // Copy from a global.
   Builder.CreateMemCpy(Loc,
                        createUnnamedGlobalForMemcpyFrom(
                            CGM, D, Builder, constant, Loc.getAlignment()),
                        SizeVal, isVolatile);
 }
 
 static void emitStoresForZeroInit(CodeGenModule &CGM, const VarDecl &D,
                                   Address Loc, bool isVolatile,
                                   CGBuilderTy &Builder) {
   llvm::Type *ElTy = Loc.getElementType();
   llvm::Constant *constant =
       constWithPadding(CGM, IsPattern::No, llvm::Constant::getNullValue(ElTy));
-  emitStoresForConstant(CGM, D, Loc, isVolatile, Builder, constant);
+  emitStoresForConstant(CGM, D, Loc, isVolatile, Builder, constant, /*FIXME*/true);
 }
 
 static void emitStoresForPatternInit(CodeGenModule &CGM, const VarDecl &D,
                                      Address Loc, bool isVolatile,
                                      CGBuilderTy &Builder) {
   llvm::Type *ElTy = Loc.getElementType();
   llvm::Constant *constant = constWithPadding(
       CGM, IsPattern::Yes, initializationPatternFor(CGM, ElTy));
   assert(!isa<llvm::UndefValue>(constant));
-  emitStoresForConstant(CGM, D, Loc, isVolatile, Builder, constant);
+  emitStoresForConstant(CGM, D, Loc, isVolatile, Builder, constant, /*FIXME*/true);
 }
 
 static bool containsUndef(llvm::Constant *constant) {
   auto *Ty = constant->getType();
   if (isa<llvm::UndefValue>(constant))
     return true;
   if (Ty->isStructTy() || Ty->isArrayTy() || Ty->isVectorTy())
     for (llvm::Use &Op : constant->operands())
if (!emission.IsConstantAggregate) {
     LValue lv = MakeAddrLValue(Loc, type);
     lv.setNonGC(true);
     return EmitStoreThroughLValue(RValue::get(constant), lv, true);
   }
 
   llvm::Type *BP = CGM.Int8Ty->getPointerTo(Loc.getAddressSpace());
   emitStoresForConstant(
       CGM, D, (Loc.getType() == BP) ? Loc : Builder.CreateBitCast(Loc, BP),
-      type.isVolatileQualified(), Builder, constant);
+      type.isVolatileQualified(), Builder, constant, /*Trapping=*/false);
 }
 
 /// Emit an expression as an initializer for an object (variable, field, etc.)
 /// at the given location.  The expression is not necessarily the normal
 /// initializer for the object, and the address is not necessarily
 /// its normal location.
 ///
 /// \param init the initializing expression

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
     case Intrinsic::launder_invariant_group:
     case Intrinsic::strip_invariant_group:
     case Intrinsic::is_constant:
     case Intrinsic::lifetime_start:
     case Intrinsic::lifetime_end:
     case Intrinsic::objectsize:
     case Intrinsic::ptr_annotation:
     case Intrinsic::var_annotation:
+    case Intrinsic::trapping:
     case Intrinsic::experimental_gc_result:
     case Intrinsic::experimental_gc_relocate:
     case Intrinsic::coro_alloc:
     case Intrinsic::coro_begin:
     case Intrinsic::coro_free:
     case Intrinsic::coro_end:
     case Intrinsic::coro_frame:
     case Intrinsic::coro_size:

llvm/include/llvm/IR/Intrinsics.td

 ///===-------------------------- Other Intrinsics --------------------------===//
 //
 def int_flt_rounds : Intrinsic<[llvm_i32_ty]>,
                      GCCBuiltin<"__builtin_flt_rounds">;
 def int_trap : Intrinsic<[], [], [IntrNoReturn, IntrCold]>,
                GCCBuiltin<"__builtin_trap">;
 def int_debugtrap : Intrinsic<[]>,
                     GCCBuiltin<"__builtin_debugtrap">;
+def int_trapping : Intrinsic<[llvm_any_ty], [LLVMMatchType<0>],
+                             [IntrNoMem, IntrWillReturn, IntrSpeculatable]>;
 
 // Support for dynamic deoptimization (or de-specialization)
 def int_experimental_deoptimize : Intrinsic<[llvm_any_ty], [llvm_vararg_ty],
                                             [Throws]>;
 
 // Support for speculative runtime guards
 def int_experimental_guard : Intrinsic<[], [llvm_i1_ty, llvm_vararg_ty],
                                        [Throws]>;

llvm/lib/CodeGen/CodeGenPrepare.cpp

case Intrinsic::experimental_widenable_condition: {
         replaceAndRecursivelySimplify(CI, RetVal, TLInfo, nullptr);
       });
       return true;
     }
     case Intrinsic::objectsize:
       llvm_unreachable("llvm.objectsize.* should have been lowered already");
     case Intrinsic::is_constant:
       llvm_unreachable("llvm.is.constant.* should have been lowered already");
+    case Intrinsic::trapping:
+      llvm_unreachable("llvm.trapping.* should have been lowered already");
     case Intrinsic::aarch64_stlxr:
     case Intrinsic::aarch64_stxr: {
       ZExtInst *ExtVal = dyn_cast<ZExtInst>(CI->getArgOperand(0));
       if (!ExtVal || !ExtVal->hasOneUse() ||
           ExtVal->getParent() == CI->getParent())
         return false;
       // Sink a zext feeding stlxr/stxr before it, so it can be folded into it.
       ExtVal->moveBefore(CI);

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

case Intrinsic::eh_typeid_for: {
     return true;
   }
   case Intrinsic::objectsize:
     llvm_unreachable("llvm.objectsize.* should have been lowered already");
 
   case Intrinsic::is_constant:
     llvm_unreachable("llvm.is.constant.* should have been lowered already");
 
+  case Intrinsic::trapping:
+    llvm_unreachable("llvm.trapping.* should have been lowered already");
+
   case Intrinsic::stackguard:
     getStackGuard(getOrCreateVReg(CI), MIRBuilder);
     return true;
   case Intrinsic::stackprotector: {
     LLT PtrTy = getLLTForType(*CI.getArgOperand(0)->getType(), *DL);
     Register GuardVal = MRI->createGenericVirtualRegister(PtrTy);
     getStackGuard(GuardVal, MIRBuilder);
 

llvm/lib/CodeGen/SelectionDAG/FastISel.cpp

case Intrinsic::dbg_label: {
     return true;
   }
   case Intrinsic::objectsize:
     llvm_unreachable("llvm.objectsize.* should have been lowered already");
 
   case Intrinsic::is_constant:
     llvm_unreachable("llvm.is.constant.* should have been lowered already");
 
+  case Intrinsic::trapping:
+    llvm_unreachable("llvm.trapping.* should have been lowered already");
+
   case Intrinsic::launder_invariant_group:
   case Intrinsic::strip_invariant_group:
   case Intrinsic::expect: {
     Register ResultReg = getRegForValue(II->getArgOperand(0));
     if (!ResultReg)
       return false;
     updateValueMap(II, ResultReg);
     return true;

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::stackprotector: {
     return;
   }
   case Intrinsic::objectsize:
     llvm_unreachable("llvm.objectsize.* should have been lowered already");
 
   case Intrinsic::is_constant:
     llvm_unreachable("llvm.is.constant.* should have been lowered already");
 
+  case Intrinsic::trapping:
+    llvm_unreachable("llvm.trapping.* should have been lowered already");
+
   case Intrinsic::annotation:
   case Intrinsic::ptr_annotation:
   case Intrinsic::launder_invariant_group:
   case Intrinsic::strip_invariant_group:
     // Drop the intrinsic, but forward the value
     setValue(&I, getValue(I.getOperand(0)));
     return;
   case Intrinsic::assume:

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

Instruction *InstCombiner::foldIntrinsicWithOverflowCommon(IntrinsicInst *II) {
   Value *OperationResult = nullptr;
   Constant *OverflowResult = nullptr;
   if (OptimizeOverflowCheck(WO->getBinaryOp(), WO->isSigned(), WO->getLHS(),
                             WO->getRHS(), *WO, OperationResult, OverflowResult))
     return CreateOverflowTuple(WO, OperationResult, OverflowResult);
   return nullptr;
 }
 
+static bool canObservePoison(Use &U, Instruction *I) {
+  if (U.getOperandNo() == 0 &&
+      (isa<SwitchInst>(I) || isa<BranchInst>(I) || isa<IndirectBrInst>(I)))
+    return true;
+  if (auto *CB = dyn_cast<CallBase>(I))
+    if (CB->getCalledOperandUse().getOperandNo() == U.getOperandNo())
+      return true;
+  if (auto *LI = dyn_cast<LoadInst>(I))
+    if (LI->getPointerOperandIndex() == U.getOperandNo())
+      return true;
+  if (auto *SI = dyn_cast<StoreInst>(I))
+    if (SI->getPointerOperandIndex() == U.getOperandNo())
+      return true;
+  if (U.getOperandNo() == 1 && I->isIntDivRem())
+    return true;
+  // FIXME: More cases?
+  return false;
+}
+
+/// Simplify a use of @llvm.trapping.<type>(<type> %x)
+///
+/// Return true if we've performed a simplification and the use should be
+/// replaced by %x.
+bool InstCombiner::simplifyTrappingUse(Use &U) {
+  auto *I = dyn_cast<Instruction>(U.getUser());
+
+  // We only care about trapping indicators on instructions.
+  if (!I)
+    return true;
+
+  // FIXME: If all operands are trapping, we can convert to trapping(phi(...)).
+  if (isa<PHINode>(I))
+    return false;
+
+  // The result of select is trapping if its condition is trapping.
+  if (isa<SelectInst>(I) && U.getOperandNo() != 0)
+    return false;
+
+  // trapping(trapping(x)) -> trapping(x).
+  if (auto *II = dyn_cast<IntrinsicInst>(I))
+    if (II->getIntrinsicID() == Intrinsic::trapping)
+      return true;
+
+  // op(trapping(x)) -> @llvm.trap() where possible.
+  if (canObservePoison(U, I)) {
+    CallInst *Trap = CallInst::Create(
+        Intrinsic::getDeclaration(I->getModule(), Intrinsic::trap));
+    InsertNewInstBefore(Trap, *I);
+    return true;
+  }
+
+  // We can't propagate trapping to the result of a void-typed instruction and
+  // a few other cases.
+  if (I->getType()->isVoidTy() || I->getType()->isTokenTy() ||
+      I->isTerminator())
+    return false;
+
+  // Don't propagate through call arguments to the result of the function for
+  // now.
+  if (isa<CallBase>(I))
+    return false;
+
+  // op(trapping(x)) -> trapping(op(x)) otherwise.
+  CallInst *TrappingI =
+      CallInst::Create(Intrinsic::getDeclaration(
+                           I->getModule(), Intrinsic::trapping, {I->getType()}),
+                       {I});
+  TrappingI->insertAfter(I);
+  replaceInstUsesWith(*I, TrappingI);
+  // Undo effect of replaceInstUsesWith on TrappingI itself.
+  TrappingI->setArgOperand(0, I);
+  return true;
+}
+
 /// CallInst simplification. This mostly only handles folding of intrinsic
 /// instructions. For normal calls, it allows visitCallBase to do the heavy
 /// lifting.
 Instruction *InstCombiner::visitCallInst(CallInst &CI) {
   // Don't try to simplify calls without uses. It will not do anything useful,
   // but will result in the following folds being skipped.
   if (!CI.use_empty())
     if (Value *V = SimplifyCall(&CI, SQ.getWithInstruction(&CI)))
case Intrinsic::assume: {
     if (Known.isAllOnes() && isAssumeWithEmptyBundle(*II))
       return eraseInstFromFunction(*II);
 
     // Update the cache of affected values for this assumption (we might be
     // here because we just simplified the condition).
     AC.updateAffectedValues(II);
     break;
   }
+  case Intrinsic::trapping: {
+    bool RemovedAllUses = true;
+    // Note, it's not safe to change the uses of II while iterating over the
+    // same list.
+    llvm::SmallVector<Use*, 8> UsesToReplace;
+    for (Use &U : II->uses()) {
+      if (simplifyTrappingUse(U))
+        UsesToReplace.push_back(&U);
+      else
+        RemovedAllUses = false;
+    }
+    for (Use *U : UsesToReplace)
+      *U = II->getOperand(0);
+    if (!RemovedAllUses)
+      return nullptr;
+    return eraseInstFromFunction(*II);
+  }
   case Intrinsic::experimental_gc_relocate: {
     auto &GCR = *cast<GCRelocateInst>(II);
 
     // If we have two copies of the same pointer in the statepoint argument
     // list, canonicalize to one.  This may let us common gc.relocates.
     if (GCR.getBasePtr() == GCR.getDerivedPtr() &&
         GCR.getBasePtrIndex() != GCR.getDerivedPtrIndex()) {
       auto *OpIntTy = GCR.getOperand(2)->getType();

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
 
   Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
                                        BinaryOperator &Logic);
   Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
   Value *getSelectCondition(Value *A, Value *B);
 
   Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
 
+  bool simplifyTrappingUse(Use &U);
+
 public:
   /// Inserts an instruction \p New before instruction \p Old
   ///
   /// Also adds the new instruction to the worklist and returns \p New so that
   /// it is suitable for use as the return from the visitation patterns.
   Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
     assert(New && !New->getParent() &&
            "New instruction already inserted into a basic block!");

llvm/lib/Transforms/Scalar/LowerConstantIntrinsics.cpp

 //===- LowerConstantIntrinsics.cpp - Lower constant intrinsic calls -------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// This pass lowers all remaining 'objectsize' 'is.constant' intrinsic calls
-// and provides constant propagation and basic CFG cleanup on the result.
+// This pass lowers all remaining 'objectsize', 'is.constant', and 'trapping'
+// intrinsic calls and provides constant propagation and basic CFG cleanup on
+// the result.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LowerConstantIntrinsics.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"

 using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "lower-is-constant-intrinsic"
 
 STATISTIC(IsConstantIntrinsicsHandled,
           "Number of 'is.constant' intrinsic calls handled");
 STATISTIC(ObjectSizeIntrinsicsHandled,
           "Number of 'objectsize' intrinsic calls handled");
+STATISTIC(TrappingIntrinsicsHandled,
+          "Number of 'trapping' intrinsic calls handled");
 
 static Value *lowerIsConstantIntrinsic(IntrinsicInst *II) {
   Value *Op = II->getOperand(0);
 
   return isa<Constant>(Op) ? ConstantInt::getTrue(II->getType())
                            : ConstantInt::getFalse(II->getType());
 }
 
for (Instruction &I: *BB) {
       IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
       if (!II)
         continue;
       switch (II->getIntrinsicID()) {
       default:
         break;
       case Intrinsic::is_constant:
       case Intrinsic::objectsize:
+      case Intrinsic::trapping:
         Worklist.push_back(WeakTrackingVH(&I));
         break;
       }
     }
   }
   for (WeakTrackingVH &VH: Worklist) {
     // Items on the worklist can be mutated by earlier recursive replaces.
     // This can remove the intrinsic as dead (VH == null), but also replace
for (WeakTrackingVH &VH: Worklist) {
     case Intrinsic::is_constant:
       NewValue = lowerIsConstantIntrinsic(II);
       IsConstantIntrinsicsHandled++;
       break;
     case Intrinsic::objectsize:
       NewValue = lowerObjectSizeCall(II, DL, TLI, true);
       ObjectSizeIntrinsicsHandled++;
       break;
+    case Intrinsic::trapping:
+      NewValue = II->getOperand(0);
+      TrappingIntrinsicsHandled++;
+      break;
     }
     HasDeadBlocks |= replaceConditionalBranchesOnConstant(II, NewValue);
   }
   if (HasDeadBlocks)
     removeUnreachableBlocks(F);
   return !Worklist.empty();
 }