Fold comparison of __builtin_object_size expression with -1 for non-const size

[siddhesh]

Summary

When __builtin_dynamic_object_size returns a non-constant expression, it cannot be -1 since that is an invalid return value for object size. However since passes running after the substitution don't know this, they are unable to optimize away the comparison and hence the comparison and branch stays in there. This change traverses uses of the object size when lowering the builtin to a constant or expression, and folds away comparisons with -1.

glibc is considering adopting __builtin_dynamic_object_size for additional protection[1] and this change will help reduce branching overhead in fortified implementations of all of the functions that don't have the __builtin___*_chk type builtins, e.g. __ppoll_chk.

Also remove the test limit-max-iterations.ll because it was deemed unnecessary during review.

[1] https://sourceware.org/pipermail/libc-alpha/2020-November/120191.html

[siddhesh]

Updated for coding style fixes.

[siddhesh]

More formatting fixes, sorry for the noise.

[serge-sans-paille]

When __builtin_dynamic_object_size returns a non-constant expression, it cannot be -1 since that is an invalid return value for object size

I disagree with that statement. For instance

void copy_into_buffer(char* buffer) {
   __builtin___strlcpy_chk(buffer, "some string", strlen("some string"), __builtin_dynamic_object_size(buffer, 0))
 }

In that case, __builtin_dynamic_object_size may return -1, e.g. if copy_into_buffer has external linkage, and thus no information on buffer is available

[siddhesh]

In D93015#2454403, @serge-sans-paille wrote:

When __builtin_dynamic_object_size returns a non-constant expression, it cannot be -1 since that is an invalid return value for object size

I disagree with that statement. For instance

void copy_into_buffer(char* buffer) {
   __builtin___strlcpy_chk(buffer, "some string", strlen("some string"), __builtin_dynamic_object_size(buffer, 0))
 }

In that case, __builtin_dynamic_object_size may return -1, e.g. if copy_into_buffer has external linkage, and thus no information on buffer is available

Ah sorry I should have been more specific: if __builtin_dynamic_object_size returns a non-constant expression, that expression returning -1 is undefined because none of the object allocators would return -1. In your example above, __builtin_dynamic_object_size evaluates to a constant -1.

Would you agree with that?

[serge-sans-paille]

llvm/lib/Analysis/MemoryBuiltins.cpp

538

It's probably better to walk through the I->uses(), filter out on getUser() and access the operand straight with getOperandNo()

549

This looks very similar to generating a call to llvm.assume, right?

You could generate a call to

%cmpnot = icmp ne i64 %objsize, -1
call void @llvm.assume(i1 %cmpnot)

And let the magic happen ;-)

610

ok, now I get it, you're folding only if you know for sure that the computation can be done. Generating an assume may help keeping the code easy to read here.

[siddhesh]

Updated version using Uses and getOperandNo as suggested. I have not used llvm.assume yet, more in another comment.

[siddhesh]

llvm/lib/Analysis/MemoryBuiltins.cpp

549

I tried, but left it as is for now. It works fine when it's just Builder.CreateAssumption(Cond), i.e. when the condition is true. However for the false condition, doing Builder.CreateAssumption(Builder.CreateNot(Cond)) does not work because llvm is unable to work out the relationships and fold the conditions away. I tried ordering the assume, cmp and the cmp.not instructions in different ways, but no dice.

ISTM the other alternative would be to invert the condition and then update the user branch instructions, thus allowing Builder.CreateAssumption(Cond) but that doesn't seem too different from replaceAllusesWith(). What do you think?

[serge-sans-paille]

@siddhesh what anout the following?

diff --git a/llvm/lib/Analysis/MemoryBuiltins.cpp b/llvm/lib/Analysis/MemoryBuiltins.cpp
index cbb54e8..7c4342d 100644
--- a/llvm/lib/Analysis/MemoryBuiltins.cpp
+++ b/llvm/lib/Analysis/MemoryBuiltins.cpp
@@ -559,6 +559,14 @@ Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,
       IRBuilder<TargetFolder> Builder(Ctx, TargetFolder(DL));
       Builder.SetInsertPoint(ObjectSize);
 
+      if (!isa<Constant>(SizeOffsetPair.first) ||
+          !isa<Constant>(SizeOffsetPair.second)) {
+        auto Iter = ObjectSize->getIterator();
+        ++Iter;
+        IRBuilder<> Builder(&*Iter);
+        Builder.CreateAssumption(Builder.CreateICmpSGE(ObjectSize, ConstantInt::get(ResultType, 0)));
+      }
+
       // If we've outside the end of the object, then we can always access
       // exactly 0 bytes.
       Value *ResultSize =

[siddhesh]

In D93015#2463046, @serge-sans-paille wrote:

@siddhesh what anout the following?

Oh!! Now I see what you mean. Patch coming up, thanks!

[siddhesh]

Updated patch. I'm not entirely sure if I 'fixed' the failing test case (limit-max-iterations.ll) correctly. Earlier it would reduce in two instcombine iterations but with this assumption, it reduces to its minimal form (i.e. with just the llvm.assume and ret) in just one iteration.

EDIT: Alternatively, I could add the assumption only when I find the != -1 comparison, which should make the change conservative enough. In other words, retain the foldObjectSizeCompare function but add the assumption about objectsize instead. What do you think?

[nikic]

llvm/test/Transforms/InstCombine/limit-max-iterations.ll

1 ↗

(On Diff #312857)

Feel free to simply delete this test. It's pretty annoying due to the reliance on iteration behavior of specific folds. We don't really need test coverage for these debugging options.

[siddhesh]

I ended up putting the assumption before the ObjectSize. Here's an update that puts the assumption on the expression we built since that's what the comment says anyway. @serge-sans-paille your method of shadowing Builder and inserting after ObjectSize would work too (I should have looked carefully the first time, sorry) but I thought this way flows better with the rest of the code in that block. I'll be happy to use your approach if you think that's better.

I have also added another test to make sure that computed expressions get built correctly. Finally, I've dropped the limit-max-iterations.ll test as Nikita suggested.

[siddhesh]

Fixed clang-format-patch failure.

[serge-sans-paille]

lgtm, thanks!

[siddhesh]

Thanks! Can you please commit for me? I don't have write access to the repo.

llvm/lib/Analysis/MemoryBuiltins.cpp

bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
   SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
   if (!Visitor.bothKnown(Data))
     return false;
 
   Size = getSizeWithOverflow(Data).getZExtValue();
   return true;
 }
 
+// Eliminate all branches that contain __builtin_dynamic_object_size when it
+// returns a non-constant expression.  The non-constant expression is a valid
+// size and hence is never -1.
+static void foldNonConstantCompares(Instruction *I) {
+  // Walk through all conditional branch users.
+  for (User *U : I->users()) {
+    ICmpInst *CI = dyn_cast<ICmpInst>(U);
+    if (!CI)
+      continue;
+
+    Value *Op0 = CI->getOperand(0);
+    Value *Op1 = CI->getOperand(1);
+    ConstantInt *Cst = nullptr;
+
+    // Find the constant part of the conditional branch.  If there is none,
+    // we bail out.
+    if (isa<Constant>(Op0))
+      Cst = dyn_cast<ConstantInt>(Op0);
+    else if (isa<Constant>(Op1))
+      Cst = dyn_cast<ConstantInt>(Op1);
+    else
+      continue;
+
+    // If the constant is not -1 then too we bail out.
+    if (!Cst || !Cst->isMinusOne())
+      continue;
+
+    ICmpInst::Predicate Pred = CI->getUnsignedPredicate();
+    LLVMContext &Ctx = I->getFunction()->getContext();
+    switch(Pred) {
+    case ICmpInst::ICMP_NE:
+    case ICmpInst::ICMP_ULE:
+    case ICmpInst::ICMP_ULT:
+      CI->replaceAllUsesWith(ConstantInt::getTrue(Ctx));
+      break;
+    case ICmpInst::ICMP_EQ:
+    case ICmpInst::ICMP_UGE:
+    case ICmpInst::ICMP_UGT:
+      CI->replaceAllUsesWith(ConstantInt::getFalse(Ctx));
+      break;
+    default:
+      continue;
+    }
+  }
+}
+
 Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,
                                  const DataLayout &DL,
                                  const TargetLibraryInfo *TLI,
                                  bool MustSucceed) {
   assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&
          "ObjectSize must be a call to llvm.objectsize!");
 
   bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero();
if (StaticOnly) {
     ObjectSizeOffsetEvaluator Eval(DL, TLI, Ctx, EvalOptions);
     SizeOffsetEvalType SizeOffsetPair =
         Eval.compute(ObjectSize->getArgOperand(0));
 
     if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {
       IRBuilder<TargetFolder> Builder(Ctx, TargetFolder(DL));
       Builder.SetInsertPoint(ObjectSize);
 
+      if (!isa<Constant>(SizeOffsetPair.first) ||
+          !isa<Constant>(SizeOffsetPair.second))
+        foldNonConstantCompares(ObjectSize);
+
       // If we've outside the end of the object, then we can always access
       // exactly 0 bytes.
       Value *ResultSize =
           Builder.CreateSub(SizeOffsetPair.first, SizeOffsetPair.second);
       Value *UseZero =
           Builder.CreateICmpULT(SizeOffsetPair.first, SizeOffsetPair.second);
       ResultSize = Builder.CreateZExtOrTrunc(ResultSize, ResultType);
       return Builder.CreateSelect(UseZero, ConstantInt::get(ResultType, 0),

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

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 ; CHECK:   define void @f()
 ; CHECK:     call i64 @llvm.objectsize.i64.p0i8(
 
+define void @bdos_impl(i64 %alloc) {
+entry:
+  %obj = call i8* @malloc(i64 %alloc)
+  %objsize = call i64 @llvm.objectsize.i64.p0i8(i8* %obj, i1 0, i1 0, i1 1)
+  %cmp.not = icmp eq i64 %objsize, -1
+  br i1 %cmp.not, label %if.else, label %if.then
+
+if.then:
+  call void @fortified_chk(i8* %obj, i64 %alloc)
+  br label %if.end
+
+if.else:
+  call void @unfortified(i8* %obj, i64 %alloc)
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+; CHECK:  define void @bdos_impl(
+; CHECK:    br i1 false, label %if.else, label %if.then
+; CHECK:    call void @fortified_chk(i8* %obj, i64 %alloc)
+
+
 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)
+
+declare void @fortified_chk(i8*, i64)
+
+declare void @unfortified(i8*, i64)