Fix a hang when lowering __builtin_dynamic_object_size

[erik.pilkington]

Summary

If the ObjectSizeOffsetEvaluator fails to fold the object size call, then it may litter some unused instructions in the function. When done repeatably in InstCombine, this results in an infinite loop. Fix this by tracking the set of instructions that were inserted, then removing them on failure.

Fixes rdar://49172227

Thanks!
Erik

llvm/include/llvm/Analysis/MemoryBuiltins.h

 };
 
 using SizeOffsetEvalType = std::pair<Value *, Value *>;
 
 /// Evaluate the size and offset of an object pointed to by a Value*.
 /// May create code to compute the result at run-time.
 class ObjectSizeOffsetEvaluator
   : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
-  using BuilderTy = IRBuilder<TargetFolder>;
+  using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
   using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
   using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
   using PtrSetTy = SmallPtrSet<const Value *, 8>;
 
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
   LLVMContext &Context;
   BuilderTy Builder;
   IntegerType *IntTy;
   Value *Zero;
   CacheMapTy CacheMap;
   PtrSetTy SeenVals;
   ObjectSizeOpts EvalOpts;
+  SmallPtrSet<Instruction *, 8> InsertedInstructions;
 
   SizeOffsetEvalType compute_(Value *V);
 
 public:
   static SizeOffsetEvalType unknown() {
     return std::make_pair(nullptr, nullptr);
   }
 

llvm/lib/Analysis/MemoryBuiltins.cpp

   LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
                     << '\n');
   return unknown();
 }
 
 ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(
     const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
     ObjectSizeOpts EvalOpts)
-    : DL(DL), TLI(TLI), Context(Context), Builder(Context, TargetFolder(DL)),
+    : DL(DL), TLI(TLI), Context(Context),
+      Builder(Context, TargetFolder(DL),
+              IRBuilderCallbackInserter(
+                  [&](Instruction *I) { InsertedInstructions.insert(I); })),
       EvalOpts(EvalOpts) {
   // IntTy and Zero must be set for each compute() since the address space may
   // be different for later objects.
 }
 
 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) {
   // XXX - Are vectors of pointers possible here?
   IntTy = cast<IntegerType>(DL.getIntPtrType(V->getType()));
   Zero = ConstantInt::get(IntTy, 0);
 
   SizeOffsetEvalType Result = compute_(V);
 
   if (!bothKnown(Result)) {
     // Erase everything that was computed in this iteration from the cache, so
     // that no dangling references are left behind. We could be a bit smarter if
     // we kept a dependency graph. It's probably not worth the complexity.
     for (const Value *SeenVal : SeenVals) {
       CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);
       // non-computable results can be safely cached
       if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
         CacheMap.erase(CacheIt);
     }
+
+    // Erase any instructions we inserted as part of the traversal.
+    for (Instruction *I : InsertedInstructions) {
+      I->replaceAllUsesWith(UndefValue::get(I->getType()));
+      I->eraseFromParent();
+    }
   }
 
   SeenVals.clear();
+  InsertedInstructions.clear();
   return Result;
 }
 
 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
   ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, EvalOpts);
   SizeOffsetType Const = Visitor.compute(V);
   if (Visitor.bothKnown(Const))
     return std::make_pair(ConstantInt::get(Context, Const.first),

   // Compute offset/size for each PHI incoming pointer.
   for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
     Builder.SetInsertPoint(&*PHI.getIncomingBlock(i)->getFirstInsertionPt());
     SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
 
     if (!bothKnown(EdgeData)) {
       OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy));
       OffsetPHI->eraseFromParent();
+      InsertedInstructions.erase(OffsetPHI);
       SizePHI->replaceAllUsesWith(UndefValue::get(IntTy));
       SizePHI->eraseFromParent();
+      InsertedInstructions.erase(SizePHI);
       return unknown();
     }
     SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i));
     OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i));
   }
 
-  Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp;
-  if ((Tmp = SizePHI->hasConstantValue())) {
+  Value *Size = SizePHI, *Offset = OffsetPHI;
+  if (Value *Tmp = SizePHI->hasConstantValue()) {
     Size = Tmp;
     SizePHI->replaceAllUsesWith(Size);
     SizePHI->eraseFromParent();
+    InsertedInstructions.erase(SizePHI);
   }
-  if ((Tmp = OffsetPHI->hasConstantValue())) {
+  if (Value *Tmp = OffsetPHI->hasConstantValue()) {
     Offset = Tmp;
     OffsetPHI->replaceAllUsesWith(Offset);
     OffsetPHI->eraseFromParent();
+    InsertedInstructions.erase(OffsetPHI);
   }
   return std::make_pair(Size, Offset);
 }
 
 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) {
   SizeOffsetEvalType TrueSide  = compute_(I.getTrueValue());
   SizeOffsetEvalType FalseSide = compute_(I.getFalseValue());
 

llvm/test/Instrumentation/BoundsChecking/phi.ll

 
 
 @global_as1 = private unnamed_addr addrspace(1) constant [10 x i8] c"ola\00mundo\00", align 1
 
 define void @f1_as1(i8 addrspace(1)* nocapture %c) {
 ; CHECK: @f1_as1
 ; no checks are possible here
 ; CHECK-NOT: trap
-; CHECK: add i16 undef, -1
-; CHECK-NOT: trap
 entry:
   %0 = load i8, i8 addrspace(1)* %c, align 1
   %tobool1 = icmp eq i8 %0, 0
   br i1 %tobool1, label %while.end, label %while.body
 
 while.body:
   %c.addr.02 = phi i8 addrspace(1)* [ %incdec.ptr, %while.body ], [ %c, %entry ]
   %incdec.ptr = getelementptr inbounds i8, i8 addrspace(1)* %c.addr.02, i64 -1

llvm/test/Transforms/InstCombine/builtin-dynamic-object-size.ll

 entry:
   ; NOTE: the third parameter to this call is false, unlike above.
   %res = call i64 @llvm.objectsize.i64.p0i8(i8* null, i1 false, i1 false, i1 true)
   ret i64 %res
 }
 
 ; CHECK: ret i64 0
 
+@d = common global i8 0, align 1
+@c = common global i32 0, align 4
+
+; Function Attrs: nounwind
+define void @f() {
+entry:
+  %.pr = load i32, i32* @c, align 4
+  %tobool4 = icmp eq i32 %.pr, 0
+  br i1 %tobool4, label %for.end, label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %dp.05 = phi i8* [ %add.ptr, %for.body ], [ @d, %entry ]
+  %0 = tail call i64 @llvm.objectsize.i64.p0i8(i8* %dp.05, i1 false, i1 true, i1 true)
+  %conv = trunc i64 %0 to i32
+  tail call void @bury(i32 %conv) #3
+  %1 = load i32, i32* @c, align 4
+  %idx.ext = sext i32 %1 to i64
+  %add.ptr.offs = add i64 %idx.ext, 0
+  %2 = add i64 undef, %add.ptr.offs
+  %add.ptr = getelementptr inbounds i8, i8* %dp.05, i64 %idx.ext
+  %add = shl nsw i32 %1, 1
+  store i32 %add, i32* @c, align 4
+  %tobool = icmp eq i32 %1, 0
+  br i1 %tobool, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; CHECK:   define void @f()
+; CHECK:     call i64 @llvm.objectsize.i64.p0i8(
+
+declare void @bury(i32) local_unnamed_addr #2
+
 ; Function Attrs: nounwind allocsize(0)
 declare i8* @malloc(i64)
 
 declare i8* @get_unknown_buffer()
 
 ; Function Attrs: nounwind
 declare void @free(i8* nocapture)
 
 ; Function Attrs: nounwind readnone speculatable
 declare i64 @llvm.objectsize.i64.p0i8(i8*, i1, i1, i1)