Page MenuHomePhabricator

[InstCombineAddSub] Added the transformation - "sub (or A B) (xor A B) -> (and A B)"
ClosedPublic

Authored by ankur29.garg on Oct 9 2014, 11:12 PM.

Details

Summary

Hi,
The following patch implements the tranformation sub (or A B) (xor A B) -> (and A B). It is similar to the one added in visitAdd()

Z3 Link: http://rise4fun.com/Z3/bNCG

Please help in reviewing it.

Thanks.
Ankur

Diff Detail

Event Timeline

ankur29.garg retitled this revision from to [InstCombineAddSub] Added the transformation - "sub (or A B) (xor A B) -> (and A B)".
ankur29.garg updated this object.
ankur29.garg edited the test plan for this revision. (Show Details)
ankur29.garg set the repository for this revision to rL LLVM.
ankur29.garg added a subscriber: Unknown Object (MLST).
majnemer edited edge metadata.Oct 18 2014, 2:23 AM

This canonicalization seems unlikely to ever fire on code in the wild.

Hi David,

Actually, similar tranformation is already present in the VisitAdd() function for add operation.

InstCombine is not supposed to handle every possible just because it is theoretically possible case. It's engineered to be a series of engineering tradeoffs. I don't know what the history of the similar transform is in VisitAdd, it's possible that it wasn't added in a principled way.

If we were to arbitrarily add patterns, we would eventually make InstCombine cripplingly slow.

Hi David,

Thanks for the comments.
You are right. I think I should run LLVM test suite and find out how many times, does this case actually arise.

Thanks.

  • Original Message -----

From: "David Majnemer" <david.majnemer@gmail.com>
To: "ankur29 garg" <ankur29.garg@samsung.com>, dexonsmith@apple.com, "suyog sarda" <suyog.sarda@samsung.com>, "david
majnemer" <david.majnemer@gmail.com>
Cc: llvm-commits@cs.uiuc.edu
Sent: Saturday, October 18, 2014 4:47:12 AM
Subject: Re: [PATCH] [InstCombineAddSub] Added the transformation - "sub (or A B) (xor A B) -> (and A B)"

InstCombine is not supposed to handle every possible just because it
is theoretically possible case. It's engineered to be a series of
engineering tradeoffs. I don't know what the history of the similar
transform is in VisitAdd, it's possible that it wasn't added in a
principled way.

If we were to arbitrarily add patterns, we would eventually make
InstCombine cripplingly slow.

To be honest, I think this position is unhelpful. A few thoughts:

  • In my experience (derived from my work on an instruction-level superoptimizer), it is really hard to predict what patterns will occur in practice -- and given knowledge of certain bits from switch statements, enums (range metadata), etc. combined with LLVM's canonicalization in terms of large integers, and several other factors, lead to many patterns that I would consider strange, and not-uncommonly in performance-sensitive regions of code.
  • We (obviously) should not engage in premature optimization -- I've seen no evidence that matching these kinds of patterns in InstCombine contributes a significant portion of its running time. And until such evidence is presented, we should not make statements about expense (there is no complexity argument here). In any case, looking at combinations of three binary operators, are there any more than a few hundred that could simplify in any reasonable sense? Probably not even that many. I see no reason we should not handle them all.
  • For simplifications that require certain bits to be known, calls into ValueTracking can be expensive, but making duplicate calls into ValueTracking is a separate issue that can be fixed if it becomes important.
  • I feel that, in the past, the real engineering tradeoff was slightly different: it used to be difficult to prove the transformations correct. As a result, there was a significant possibility of bugs being introduced by each of these transformations, and it made more sense to limit them. As you know, this is no longer anywhere near as true as it was: we now have good tools to verify these transformations.

Thanks again,
Hal

http://reviews.llvm.org/D5719


llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

  • Original Message -----

From: "Hal Finkel" <hfinkel@anl.gov>
To: reviews+D5719+public+3088893b38cafcf5@reviews.llvm.org
Cc: "ankur29 garg" <ankur29.garg@samsung.com>, "suyog sarda" <suyog.sarda@samsung.com>, llvm-commits@cs.uiuc.edu
Sent: Saturday, October 18, 2014 11:37:40 PM
Subject: Re: [PATCH] [InstCombineAddSub] Added the transformation - "sub (or A B) (xor A B) -> (and A B)"

    • Original Message ----- > From: "David Majnemer" <david.majnemer@gmail.com> > To: "ankur29 garg" <ankur29.garg@samsung.com>, > dexonsmith@apple.com, "suyog sarda" <suyog.sarda@samsung.com>, > "david > majnemer" <david.majnemer@gmail.com> > Cc: llvm-commits@cs.uiuc.edu > Sent: Saturday, October 18, 2014 4:47:12 AM > Subject: Re: [PATCH] [InstCombineAddSub] Added the transformation - > "sub (or A B) (xor A B) -> (and A B)" > > InstCombine is not supposed to handle every possible just because > it > is theoretically possible case. It's engineered to be a series of > engineering tradeoffs. I don't know what the history of the > similar > transform is in VisitAdd, it's possible that it wasn't added in a > principled way. > > If we were to arbitrarily add patterns, we would eventually make > InstCombine cripplingly slow.

      To be honest, I think this position is unhelpful. A few thoughts:
  • In my experience (derived from my work on an instruction-level superoptimizer), it is really hard to predict what patterns will occur in practice -- and given knowledge of certain bits from switch statements, enums (range metadata), etc. combined with LLVM's canonicalization in terms of large integers, and several other factors, lead to many patterns that I would consider strange, and not-uncommonly in performance-sensitive regions of code.

To add another anecdote, just when I thought I had classified the kinds of patterns that were occurring in practice, I started looking at instrumented code (address sanitizer, etc.), and I learned that I had a lot left to do.

-Hal

  • We (obviously) should not engage in premature optimization -- I've seen no evidence that matching these kinds of patterns in InstCombine contributes a significant portion of its running time. And until such evidence is presented, we should not make statements about expense (there is no complexity argument here). In any case, looking at combinations of three binary operators, are there any more than a few hundred that could simplify in any reasonable sense? Probably not even that many. I see no reason we should not handle them all.
  • For simplifications that require certain bits to be known, calls into ValueTracking can be expensive, but making duplicate calls into ValueTracking is a separate issue that can be fixed if it becomes important.
  • I feel that, in the past, the real engineering tradeoff was slightly different: it used to be difficult to prove the transformations correct. As a result, there was a significant possibility of bugs being introduced by each of these transformations, and it made more sense to limit them. As you know, this is no longer anywhere near as true as it was: we now have good tools to verify these transformations.

    Thanks again, Hal

    > > http://reviews.llvm.org/D5719 > > > > _______________________________________________ > llvm-commits mailing list > llvm-commits@cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits >

    -- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
majnemer accepted this revision.Oct 19 2014, 1:34 AM
majnemer edited edge metadata.

LGTM

This revision is now accepted and ready to land.Oct 19 2014, 1:34 AM
majnemer closed this revision.Oct 19 2014, 1:35 AM

Commited as rL220162.

Hi David,
Thanks for reviewing the patch.

Although, the link to the commit rL220162 seems to be of another patch. Please update it.

Thanks.