This is an archive of the discontinued LLVM Phabricator instance.

[BasicAA] Integrate MaxObjSize for NoAlias
Needs ReviewPublic

Authored by atmnpatel on Sep 25 2020, 11:03 PM.

Details

Summary

With the introduction of the maxobjsize attribute (D87975, D87978), we should be able
to more easily determine when two objects cannot alias by using
dereferenceable as the lower bound on the object size and maxobjsize
as the upper bound on the object size, that is, if either object is
known to be at least larger than the other, we know that they cannot
alias. This patch implements these changes within BasicAliasAnalysis.

Diff Detail

Event Timeline

atmnpatel created this revision.Sep 25 2020, 11:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 25 2020, 11:03 PM
atmnpatel requested review of this revision.Sep 25 2020, 11:03 PM
fhahn added a subscriber: fhahn.Sep 27 2020, 3:25 AM
fhahn added inline comments.
llvm/test/Transforms/DeadStoreElimination/MSSA/calloc-store.ll
1 ↗(On Diff #294481)

are there any real changes in this test? It does not use the new attribute, so are there changes expected?

llvm/test/Transforms/LoopVectorize/X86/pr23997.ll
30 ↗(On Diff #294481)

are there any real changes in this test? looks like just renaming of value names in the IR?

We need new tests specifically for this. Using the maxobjsize attribute especially

llvm/lib/Analysis/BasicAliasAnalysis.cpp
263

Add a comment above getPointerMaxObjSizeBytes stating that this is an over-approximation of the "extend till the end". In fact it is multi kinds of over-approximation, one of which is that it is an over-approximation of the maximal extend of the object, regardless of the offset \p V has into it.

llvm/test/Transforms/Attributor/readattrs.ll
158 ↗(On Diff #294481)

We have to check if this is not unrelated. I'll run the update script on the attributor files again.

jdoerfert added a comment.EditedSep 29 2020, 12:03 PM

Statistics changes for CTMark, this patch w/o maxobjsize deduction.

before_base.json.stats vs after_base.json.stats
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%)
atmnpatel updated this revision to Diff 295331.Sep 30 2020, 9:47 AM

Added a specific basic-aa maxobjsize test.

The new test looks good. There are two tests in tree you need to fix (they improved), see the Unit test results from the pre-commit build.

atmnpatel updated this revision to Diff 295388.Sep 30 2020, 1:11 PM

Fixed broken tests, think the changes make sense.

Statistics changes for CTMark, this patch w/o maxobjsize deduction.

If this is profitable even without the maxobjsize actually being present anywhere, can we just land this before the maxobjsize attribute? I'm not sure I understand what this is doing differently from the existing isObjectSmallerThan check.

I think that phrase ("w/o maxobjsize deduction") could be a bit misleading, IINM, when @jdoerfert says w/o maxobjsize deduction he means without having the functionality built into the attributor to update the maximum object size estimate. So in the patch D87975, there's a crude over-approximation for the maxobjsize (getPointerMaxObjSize) and the numbers are for just using that over-approximation without including the changes in D87978 that refine it, so we would still need the maxobjsize attribute first in order to do this.

I think that phrase ("w/o maxobjsize deduction") could be a bit misleading, IINM, when @jdoerfert says w/o maxobjsize deduction he means without having the functionality built into the attributor to update the maximum object size estimate. So in the patch D87975, there's a crude over-approximation for the maxobjsize (getPointerMaxObjSize) and the numbers are for just using that over-approximation without including the changes in D87978 that refine it, so we would still need the maxobjsize attribute first in order to do this.

I don't think we do. All the logic is there but since we never manifest maxobjsize to see this improvements we can commit this w/o the attribute part just fine. The attribute will come in when the Attributor deduces it, and when we annotate malloc and other library functions accordingly.

I think that phrase ("w/o maxobjsize deduction") could be a bit misleading, IINM, when @jdoerfert says w/o maxobjsize deduction he means without having the functionality built into the attributor to update the maximum object size estimate. So in the patch D87975, there's a crude over-approximation for the maxobjsize (getPointerMaxObjSize) and the numbers are for just using that over-approximation without including the changes in D87978 that refine it, so we would still need the maxobjsize attribute first in order to do this.

As far as I can tell, without D87978, clang-generated IR won't contain any maxobjsize attributes. So any changes to the generated code are unrelated to maxobjsize attribute.

bollu removed a reviewer: bollu.Jan 15 2021, 8:42 PM
bollu removed a reviewer: bollu.Jan 15 2021, 8:46 PM