Atmn Patel via llvm-dev
2020-Oct-13 16:35 UTC
[llvm-dev] [RFC] Introducing the maxobjsize attribute
Hi All,
We've prepared a new attribute `maxobjsize(<n>)` that tracks the
maximum
size of the object that a pointer points to. This attribute will be deduced
through the Attributor framework and it is used for aliasing queries. The
`maxobjsize` of an object, and number of `dereferenceable` bytes can be
used as upper and lower bounds on the object size, and if there is no
overlap, we can determine that the underlying objects cannot alias.
Basically, an object that is at most N bytes long is not aliasing one that
is at least N+1 bytes long.
These changes are in:
- D87975 - [IR] Introduce MaxObjSize Attribute
- D87978 - [Attributor] Adds deduction for the MaxObjSize Attribute
- D88353 - [BasicAA] Integrate MaxobjSize for NoAlias
These are the Statistics changes for CTMark *without* the actual deduction (
https://reviews.llvm.org/D88353#2301597):
CHANGED: branch-folder NumHoist
438 -> 431 ( -1.598%)
CHANGED: codegenprepare NumBlocksElim
16093 -> 15885 ( -1.292%)
CHANGED: codegenprepare NumExtsMoved
6373 -> 6439 ( +1.036%)
CHANGED: gvn
IsValueFullyAvailableInBlockNumSpeculationsMax 6746 -> 6858 (
+1.660%)
CHANGED: gvn NumGVNInstr
78434 -> 79330 ( +1.142%)
CHANGED: instcombine NumReassoc
22830 -> 23213 ( +1.678%)
CHANGED: instsimplify NumSimplified
21278 -> 21495 ( +1.020%)
CHANGED: licm NumPromoted
407 -> 497 ( +22.113%)
CHANGED: loop-rotate NumNotRotatedDueToHeaderSize
37 -> 35 ( -5.405%)
CHANGED: loop-simplify NumNested
126 -> 128 ( +1.587%)
CHANGED: machinelicm NumPostRAHoisted
131 -> 134 ( +2.290%)
CHANGED: memory-builtins ObjectVisitorLoad
96077 -> 97496 ( +1.477%)
CHANGED: regalloc NumDCEFoldedLoads
38 -> 37 ( -2.632%)
CHANGED: regalloc NumLaneConflicts
4408 -> 4332 ( -1.724%)
CHANGED: regalloc NumReloadsRemoved
1062 -> 1050 ( -1.130%)
CHANGED: regalloc NumSnippets
1168 -> 1152 ( -1.370%)
CHANGED: regalloc NumSpillsRemoved
672 -> 665 ( -1.042%)
CHANGED: stack-slot-coloring NumDead
14 -> 18 ( +28.571%)
CHANGED: twoaddressinstruction NumConvertedTo3Addr
27054 -> 26695 ( -1.327%)
These are the Statistic Changes in CTMark w/O3 before/after these patches (
https://reviews.llvm.org/D87978#2307622):
CHANGED: codegenprepare NumExtsMoved
3631 -> 3699 ( +1.873%)
CHANGED: dse NumFastOther
192 -> 194 ( +1.042%)
CHANGED: gvn
IsValueFullyAvailableInBlockNumSpeculationsMax 4958 -> 5060 (
+2.057%)
CHANGED: gvn NumGVNInstr
46657 -> 47534 ( +1.880%)
CHANGED: jump-threading NumDupes
91 -> 92 ( +1.099%)
CHANGED: licm NumMovedLoads
6272 -> 6344 ( +1.148%)
CHANGED: licm NumPromoted
381 -> 438 ( +14.961%)
CHANGED: loop-rotate NumNotRotatedDueToHeaderSize
31 -> 29 ( -6.452%)
CHANGED: machinelicm NumPostRAHoisted
88 -> 89 ( +1.136%)
CHANGED: memdep NumCacheNonLocalPtr
1005887 -> 1016671 ( +1.072%)
CHANGED: memory-builtins ObjectVisitorLoad
62048 -> 63473 ( +2.297%)
CHANGED: peephole-opt NumCmps
532 -> 526 ( -1.128%)
CHANGED: regalloc NumDCEFoldedLoads
27 -> 26 ( -3.704%)
CHANGED: regalloc NumLocalSplits
1891 -> 1870 ( -1.111%)
Feedback Welcome.
Atmn and Johannes
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201013/24d501f7/attachment.html>
Philip Reames via llvm-dev
2020-Oct-15 23:00 UTC
[llvm-dev] [RFC] Introducing the maxobjsize attribute
On 10/13/20 9:35 AM, Atmn Patel via llvm-dev wrote:> Hi All, > > We've prepared a new attribute `maxobjsize(<n>)` that tracks the > maximum size of the object that a pointer points to. This attribute > will be deduced through the Attributor framework and it is used for > aliasing queries. The `maxobjsize` of an object, and number of > `dereferenceable` bytes can be used as upper and lower bounds on the > object size, and if there is no overlap, we can determine that the > underlying objects cannot alias. Basically, an object that is at most > N bytes long is not aliasing one that is at least N+1 bytes long.This is commingling two separate concerns. At minimum, a wording clarification is needed, it's possible the proposed use case does not work. Deferenceability is the amount of space which can be accessed without a runtime fault. Of key importance is the dereferenceability is disconnected from object size. There may be space beyond an object which is dereferenceable, but outside the object. As a simple example, imagine an allocator which allocates 32 byte blocks of memory, 32 byte aligned. If the actual object allocated is only 16 bytes, the pointer is still known to be 32 byte aligned and deref for 32 bytes. The contents past the object are simply unspecified. Saying that a 32 byte derefenceable pointer doesn't alias one with a maximum object size of 16 bytes would be wrong and lead to miscompiles in practice.> > These changes are in: > - D87975 - [IR] Introduce MaxObjSize Attribute > - D87978 - [Attributor] Adds deduction for the MaxObjSize Attribute > - D88353 - [BasicAA] Integrate MaxobjSize for NoAlias > > These are the Statistics changes for CTMark *without* the actual > deduction (https://reviews.llvm.org/D88353#2301597): > CHANGED: branch-folder NumHoist > 438 -> 431 ( -1.598%) > CHANGED: codegenprepare NumBlocksElim > 16093 -> 15885 ( -1.292%) > CHANGED: codegenprepare NumExtsMoved > 6373 -> 6439 ( +1.036%) > CHANGED: gvn IsValueFullyAvailableInBlockNumSpeculationsMax > 6746 -> 6858 ( +1.660%) > CHANGED: gvn NumGVNInstr > 78434 -> 79330 ( +1.142%) > CHANGED: instcombine NumReassoc > 22830 -> 23213 ( +1.678%) > CHANGED: instsimplify NumSimplified > 21278 -> 21495 ( +1.020%) > CHANGED: licm NumPromoted > 407 -> 497 ( +22.113%) > CHANGED: loop-rotate NumNotRotatedDueToHeaderSize > 37 -> 35 ( -5.405%) > CHANGED: loop-simplify NumNested > 126 -> 128 ( +1.587%) > CHANGED: machinelicm NumPostRAHoisted > 131 -> 134 ( +2.290%) > CHANGED: memory-builtins ObjectVisitorLoad > 96077 -> 97496 ( +1.477%) > CHANGED: regalloc NumDCEFoldedLoads > 38 -> 37 ( -2.632%) > CHANGED: regalloc NumLaneConflicts > 4408 -> 4332 ( -1.724%) > CHANGED: regalloc NumReloadsRemoved > 1062 -> 1050 ( -1.130%) > CHANGED: regalloc NumSnippets > 1168 -> 1152 ( -1.370%) > CHANGED: regalloc NumSpillsRemoved > 672 -> 665 ( -1.042%) > CHANGED: stack-slot-coloring NumDead > 14 -> 18 ( +28.571%) > CHANGED: twoaddressinstruction NumConvertedTo3Addr > 27054 -> 26695 ( -1.327%) > > These are the Statistic Changes in CTMark w/O3 before/after these > patches (https://reviews.llvm.org/D87978#2307622): > CHANGED: codegenprepare NumExtsMoved > 3631 -> 3699 ( +1.873%) > CHANGED: dse NumFastOther > 192 -> 194 ( +1.042%) > CHANGED: gvn IsValueFullyAvailableInBlockNumSpeculationsMax > 4958 -> 5060 ( +2.057%) > CHANGED: gvn NumGVNInstr > 46657 -> 47534 ( +1.880%) > CHANGED: jump-threading NumDupes > 91 -> 92 ( +1.099%) > CHANGED: licm NumMovedLoads > 6272 -> 6344 ( +1.148%) > CHANGED: licm NumPromoted > 381 -> 438 ( +14.961%) > CHANGED: loop-rotate NumNotRotatedDueToHeaderSize > 31 -> 29 ( -6.452%) > CHANGED: machinelicm NumPostRAHoisted > 88 -> 89 ( +1.136%) > CHANGED: memdep NumCacheNonLocalPtr > 1005887 -> 1016671 ( +1.072%) > CHANGED: memory-builtins ObjectVisitorLoad > 62048 -> 63473 ( +2.297%) > CHANGED: peephole-opt NumCmps > 532 -> 526 ( -1.128%) > CHANGED: regalloc NumDCEFoldedLoads > 27 -> 26 ( -3.704%) > CHANGED: regalloc NumLocalSplits > 1891 -> 1870 ( -1.111%) > > Feedback Welcome. > > Atmn and Johannes > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201015/ee81c943/attachment.html>
Johannes Doerfert via llvm-dev
2020-Oct-16 01:30 UTC
[llvm-dev] [RFC] Introducing the maxobjsize attribute
On 10/15/20 6:00 PM, Philip Reames via llvm-dev wrote:> > On 10/13/20 9:35 AM, Atmn Patel via llvm-dev wrote: >> Hi All, >> >> We've prepared a new attribute `maxobjsize(<n>)` that tracks the >> maximum size of the object that a pointer points to. This attribute >> will be deduced through the Attributor framework and it is used for >> aliasing queries. The `maxobjsize` of an object, and number of >> `dereferenceable` bytes can be used as upper and lower bounds on the >> object size, and if there is no overlap, we can determine that the >> underlying objects cannot alias. Basically, an object that is at most >> N bytes long is not aliasing one that is at least N+1 bytes long. > > This is commingling two separate concerns. At minimum, a wording > clarification is needed, it's possible the proposed use case does not > work. > > Deferenceability is the amount of space which can be accessed without > a runtime fault. Of key importance is the dereferenceability is > disconnected from object size. There may be space beyond an object > which is dereferenceable, but outside the object. > > As a simple example, imagine an allocator which allocates 32 byte > blocks of memory, 32 byte aligned. If the actual object allocated is > only 16 bytes, the pointer is still known to be 32 byte aligned and > deref for 32 bytes. The contents past the object are simply unspecified. > > Saying that a 32 byte derefenceable pointer doesn't alias one with a > maximum object size of 16 bytes would be wrong and lead to miscompiles > in practice.We already perform exactly this deduction in BasicAA right now, except that max object size is not made explicit. You just assumed the allocated object is 16 bytes and therefore it will imply `maxobjsize(16)` while the underlying memory region is `dereferenceable(32)`. You cannot have both in our object-driven model. ~ Johannes>> >> These changes are in: >> - D87975 - [IR] Introduce MaxObjSize Attribute >> - D87978 - [Attributor] Adds deduction for the MaxObjSize Attribute >> - D88353 - [BasicAA] Integrate MaxobjSize for NoAlias >> >> These are the Statistics changes for CTMark *without* the actual >> deduction (https://reviews.llvm.org/D88353#2301597): >> CHANGED: branch-folder NumHoist 438 -> >> 431 ( -1.598%) >> CHANGED: codegenprepare NumBlocksElim >> 16093 -> 15885 ( -1.292%) >> CHANGED: codegenprepare NumExtsMoved >> 6373 -> 6439 ( +1.036%) >> CHANGED: gvn IsValueFullyAvailableInBlockNumSpeculationsMax 6746 >> -> 6858 ( +1.660%) >> CHANGED: gvn NumGVNInstr >> 78434 -> 79330 ( +1.142%) >> CHANGED: instcombine NumReassoc 22830 >> -> 23213 ( +1.678%) >> CHANGED: instsimplify NumSimplified >> 21278 -> 21495 ( +1.020%) >> CHANGED: licm NumPromoted >> 407 -> 497 ( +22.113%) >> CHANGED: loop-rotate NumNotRotatedDueToHeaderSize 37 -> >> 35 ( -5.405%) >> CHANGED: loop-simplify NumNested 126 >> -> 128 ( +1.587%) >> CHANGED: machinelicm NumPostRAHoisted >> 131 -> 134 ( +2.290%) >> CHANGED: memory-builtins ObjectVisitorLoad >> 96077 -> 97496 ( +1.477%) >> CHANGED: regalloc NumDCEFoldedLoads >> 38 -> 37 ( -2.632%) >> CHANGED: regalloc NumLaneConflicts >> 4408 -> 4332 ( -1.724%) >> CHANGED: regalloc NumReloadsRemoved >> 1062 -> 1050 ( -1.130%) >> CHANGED: regalloc NumSnippets >> 1168 -> 1152 ( -1.370%) >> CHANGED: regalloc NumSpillsRemoved >> 672 -> 665 ( -1.042%) >> CHANGED: stack-slot-coloring NumDead 14 -> >> 18 ( +28.571%) >> CHANGED: twoaddressinstruction NumConvertedTo3Addr >> 27054 -> 26695 ( -1.327%) >> >> These are the Statistic Changes in CTMark w/O3 before/after these >> patches (https://reviews.llvm.org/D87978#2307622): >> CHANGED: codegenprepare NumExtsMoved >> 3631 -> 3699 ( +1.873%) >> CHANGED: dse NumFastOther >> 192 -> 194 ( +1.042%) >> CHANGED: gvn IsValueFullyAvailableInBlockNumSpeculationsMax 4958 >> -> 5060 ( +2.057%) >> CHANGED: gvn NumGVNInstr >> 46657 -> 47534 ( +1.880%) >> CHANGED: jump-threading NumDupes 91 -> >> 92 ( +1.099%) >> CHANGED: licm NumMovedLoads >> 6272 -> 6344 ( +1.148%) >> CHANGED: licm NumPromoted >> 381 -> 438 ( +14.961%) >> CHANGED: loop-rotate NumNotRotatedDueToHeaderSize 31 -> >> 29 ( -6.452%) >> CHANGED: machinelicm NumPostRAHoisted >> 88 -> 89 ( +1.136%) >> CHANGED: memdep NumCacheNonLocalPtr >> 1005887 -> 1016671 ( +1.072%) >> CHANGED: memory-builtins ObjectVisitorLoad >> 62048 -> 63473 ( +2.297%) >> CHANGED: peephole-opt NumCmps 532 -> >> 526 ( -1.128%) >> CHANGED: regalloc NumDCEFoldedLoads >> 27 -> 26 ( -3.704%) >> CHANGED: regalloc NumLocalSplits >> 1891 -> 1870 ( -1.111%) >> >> Feedback Welcome. >> >> Atmn and Johannes >> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Johannes Doerfert via llvm-dev
2020-Nov-01 18:46 UTC
[llvm-dev] [RFC] Introducing the maxobjsize attribute
Slight change of plans. After talking to Philip, we agreed that it's unclear if we want to use `dereferenceable` for the object-based property or the "hardware-based" property. So if it is the extend remaining of the allocated object or of the memory region that can be accessed without causing observable behavior. Since the use of `dereferenceable` was out of convenience, it is already existing, there is a good argument to be made to go for the other option instead: Create a "min-object-size" attribute matching the one described below. Instead of introducing two attributes we'll go with a single one that takes two values instead, a lower and upper bound for the minimal and maximal object size can always be provided. Given the way attributes are implemented right now, the min and max size will probably be limited to ~2^32, though that seems OK to me. (Bigger objects just don't get an attribute.) The code will be updated shortly and the logic in BasicAA will be adjusted to use the minimal object size not the dereferenceable bytes. We'll also teach the ObjectSize deduction about the new attribute. Please let us know if you have concerns with this, any feedback is welcome. ~ Johannes On 10/13/20 11:35 AM, Atmn Patel via llvm-dev wrote:> Hi All, > > We've prepared a new attribute `maxobjsize(<n>)` that tracks the maximum > size of the object that a pointer points to. This attribute will be deduced > through the Attributor framework and it is used for aliasing queries. The > `maxobjsize` of an object, and number of `dereferenceable` bytes can be > used as upper and lower bounds on the object size, and if there is no > overlap, we can determine that the underlying objects cannot alias. > Basically, an object that is at most N bytes long is not aliasing one that > is at least N+1 bytes long. > > These changes are in: > - D87975 - [IR] Introduce MaxObjSize Attribute > - D87978 - [Attributor] Adds deduction for the MaxObjSize Attribute > - D88353 - [BasicAA] Integrate MaxobjSize for NoAlias > > These are the Statistics changes for CTMark *without* the actual deduction ( > https://reviews.llvm.org/D88353#2301597): > CHANGED: branch-folder NumHoist > 438 -> 431 ( -1.598%) > CHANGED: codegenprepare NumBlocksElim > 16093 -> 15885 ( -1.292%) > CHANGED: codegenprepare NumExtsMoved > 6373 -> 6439 ( +1.036%) > CHANGED: gvn > IsValueFullyAvailableInBlockNumSpeculationsMax 6746 -> 6858 ( > +1.660%) > CHANGED: gvn NumGVNInstr > 78434 -> 79330 ( +1.142%) > CHANGED: instcombine NumReassoc > 22830 -> 23213 ( +1.678%) > CHANGED: instsimplify NumSimplified > 21278 -> 21495 ( +1.020%) > CHANGED: licm NumPromoted > 407 -> 497 ( +22.113%) > CHANGED: loop-rotate NumNotRotatedDueToHeaderSize > 37 -> 35 ( -5.405%) > CHANGED: loop-simplify NumNested > 126 -> 128 ( +1.587%) > CHANGED: machinelicm NumPostRAHoisted > 131 -> 134 ( +2.290%) > CHANGED: memory-builtins ObjectVisitorLoad > 96077 -> 97496 ( +1.477%) > CHANGED: regalloc NumDCEFoldedLoads > 38 -> 37 ( -2.632%) > CHANGED: regalloc NumLaneConflicts > 4408 -> 4332 ( -1.724%) > CHANGED: regalloc NumReloadsRemoved > 1062 -> 1050 ( -1.130%) > CHANGED: regalloc NumSnippets > 1168 -> 1152 ( -1.370%) > CHANGED: regalloc NumSpillsRemoved > 672 -> 665 ( -1.042%) > CHANGED: stack-slot-coloring NumDead > 14 -> 18 ( +28.571%) > CHANGED: twoaddressinstruction NumConvertedTo3Addr > 27054 -> 26695 ( -1.327%) > > These are the Statistic Changes in CTMark w/O3 before/after these patches ( > https://reviews.llvm.org/D87978#2307622): > CHANGED: codegenprepare NumExtsMoved > 3631 -> 3699 ( +1.873%) > CHANGED: dse NumFastOther > 192 -> 194 ( +1.042%) > CHANGED: gvn > IsValueFullyAvailableInBlockNumSpeculationsMax 4958 -> 5060 ( > +2.057%) > CHANGED: gvn NumGVNInstr > 46657 -> 47534 ( +1.880%) > CHANGED: jump-threading NumDupes > 91 -> 92 ( +1.099%) > CHANGED: licm NumMovedLoads > 6272 -> 6344 ( +1.148%) > CHANGED: licm NumPromoted > 381 -> 438 ( +14.961%) > CHANGED: loop-rotate NumNotRotatedDueToHeaderSize > 31 -> 29 ( -6.452%) > CHANGED: machinelicm NumPostRAHoisted > 88 -> 89 ( +1.136%) > CHANGED: memdep NumCacheNonLocalPtr > 1005887 -> 1016671 ( +1.072%) > CHANGED: memory-builtins ObjectVisitorLoad > 62048 -> 63473 ( +2.297%) > CHANGED: peephole-opt NumCmps > 532 -> 526 ( -1.128%) > CHANGED: regalloc NumDCEFoldedLoads > 27 -> 26 ( -3.704%) > CHANGED: regalloc NumLocalSplits > 1891 -> 1870 ( -1.111%) > > Feedback Welcome. > > Atmn and Johannes > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev