This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by siddhesh on Dec 10 2020, 2:10 AM.

Details

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

Diff Detail

Event Timeline

siddhesh created this revision.Dec 10 2020, 2:10 AM
siddhesh requested review of this revision.Dec 10 2020, 2:10 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 10 2020, 2:10 AM
siddhesh updated this revision to Diff 310817.Dec 10 2020, 3:09 AM

Updated for coding style fixes.

siddhesh updated this revision to Diff 310825.Dec 10 2020, 3:44 AM

More formatting fixes, sorry for the noise.

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

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?

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 this revision to Diff 312447.Dec 17 2020, 4:19 AM
siddhesh set the repository for this revision to rG LLVM Github Monorepo.

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

siddhesh marked an inline comment as done.Dec 17 2020, 4:28 AM
siddhesh added inline comments.
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?

@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 what anout the following?

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

siddhesh updated this revision to Diff 312857.EditedDec 18 2020, 11:19 AM

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?

siddhesh updated this revision to Diff 312858.Dec 18 2020, 11:22 AM
nikic added a subscriber: nikic.Dec 18 2020, 12:20 PM
nikic added inline comments.
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 updated this revision to Diff 312918.Dec 18 2020, 9:32 PM
siddhesh edited the summary of this revision. (Show Details)
siddhesh set the repository for this revision to rG LLVM Github Monorepo.

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 updated this revision to Diff 313037.Dec 21 2020, 1:48 AM

Fixed clang-format-patch failure.

lgtm, thanks!

This revision is now accepted and ready to land.Dec 21 2020, 5:48 AM

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