llvm dev - Jul 2020 - Allowed operations for passes that report "no change"

I’m digging through a build failure [1], and it looks like the loop idiom
recognizer adds some instructions [2], and then removes them again [3]. I don’t
understand why yet, but the LegacyPassManager detects that the structural hash
of the function has changed, and complains that the pass didn’t correctly report
that it changed the function [4] (even though materially, it didn’t).

This raises a broader question of what we really mean when we say that a pass is
allowed to report it made no changes through its runOn* function(s):

A) The obvious, and most restrictive condition would be that the pass can only
return false if it treated the Function/Module/etc that it visited purely as
read-only. From what I can tell, a lot of passes conservatively assume this is
the required condition.

B) Less obvious would be that we allow passes to add instructions speculatively,
so long as they remove whatever they added before returning false. If one were
to dump the IR before & after such a pass, you should see no change in the
text/bitcode. If you compared the in-memory representations, you should see no
semantic differences in the two, modulo “allowed” differences like unordered
lists of pointers (I vaguely remember a few cases of this existing, but can’t
remember the details).

C) Even less obvious would be that we allow a pass that removes instructions /
globals, and then re-adds them. These changes would be semantics-preserving, but
would of course not preserve the removed bits of IR’s addresses in memory.

I believe (A) to be the spirit of the contract between passes and the pass
manager. (B) seems like a stretch, but depending on the analysis invalidation
needs of the PM, might still be ok. (C) seems totally off base, and does not
seem like a productive interpretation.

Does this match everyone else’s intuition, and is (B) even a valid
interpretation?


Cheers,

Jon 


1:
http://lab.llvm.org:8080/green/job/clang-stage1-cmake-RA-expensive/16803/consoleFull#-1371525106d489585b-5106-414a-ac11-3ff90657619c
<http://lab.llvm.org:8080/green/job/clang-stage1-cmake-RA-expensive/16803/consoleFull#-1371525106d489585b-5106-414a-ac11-3ff90657619c>
2:
https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L931
<https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L931>
3:
https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L936
<https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L936>
4:
https://github.com/llvm/llvm-project/blob/master/llvm/lib/IR/LegacyPassManager.cpp#L1591
<https://github.com/llvm/llvm-project/blob/master/llvm/lib/IR/LegacyPassManager.cpp#L1591>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200717/71976db4/attachment.html>

On Fri, Jul 17, 2020 at 9:30 PM Jonathan Roelofs via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I’m digging through a build failure [1], and it looks like the loop idiom
> recognizer adds some instructions [2], and then removes them again [3]. I
> don’t understand why yet, but the LegacyPassManager detects that the
> structural hash of the function has changed, and complains that the pass
> didn’t correctly report that it changed the function [4] (even though
> materially, it didn’t).
>
> This raises a broader question of what we really mean when we say that a
> pass is allowed to report it made no changes through its runOn*
function(s):
>
> A) The obvious, and most restrictive condition would be that the pass can
> only return false if it treated the Function/Module/etc that it visited
> purely as read-only. From what I can tell, a lot of passes conservatively
> assume this is the required condition.
>
> B) Less obvious would be that we allow passes to add instructions
> speculatively, so long as they remove whatever they added before returning
> false. If one were to dump the IR before & after such a pass, you
should
> see no change in the text/bitcode. If you compared the in-memory
> representations, you should see no semantic differences in the two, modulo
> “allowed” differences like unordered lists of pointers (I vaguely remember
> a few cases of this existing, but can’t remember the details).
>
> C) Even less obvious would be that we allow a pass that removes
> instructions / globals, and then re-adds them. These changes would be
> semantics-preserving, but would of course not preserve the removed bits of
> IR’s addresses in memory.
>
> I believe (A) to be the spirit of the contract between passes and the pass
> manager. (B) seems like a stretch, but depending on the analysis
> invalidation needs of the PM, might still be ok. (C) seems totally off
> base, and does not seem like a productive interpretation.
>
> Does this match everyone else’s intuition, and is (B) even a valid
> interpretation?
>
This concern was brought up in the relevant review (
https://reviews.llvm.org/D81230) as well. I think we can safely go with (A)
here. It's unambiguous, and I don't think there's any practical
benefit to
be had from (B) or (C).

Regards,
Nikita
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200717/45518a49/attachment.html>

On Fri, Jul 17, 2020 at 10:52 PM Nikita Popov via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> On Fri, Jul 17, 2020 at 9:30 PM Jonathan Roelofs via llvm-dev <llvm-dev
at lists.llvm.org> wrote:
>>
>> I’m digging through a build failure [1], and it looks like the loop
idiom recognizer adds some instructions [2], and then removes them again [3]. I
don’t understand why yet, but the LegacyPassManager detects that the structural
hash of the function has changed, and complains that the pass didn’t correctly
report that it changed the function [4] (even though materially, it didn’t).
>>
>> This raises a broader question of what we really mean when we say that
a pass is allowed to report it made no changes through its runOn* function(s):
>>
>> A) The obvious, and most restrictive condition would be that the pass
can only return false if it treated the Function/Module/etc that it visited
purely as read-only. From what I can tell, a lot of passes conservatively assume
this is the required condition.
>>
>> B) Less obvious would be that we allow passes to add instructions
speculatively, so long as they remove whatever they added before returning
false. If one were to dump the IR before & after such a pass, you should see
no change in the text/bitcode. If you compared the in-memory representations,
you should see no semantic differences in the two, modulo “allowed” differences
like unordered lists of pointers (I vaguely remember a few cases of this
existing, but can’t remember the details).
>>
>> C) Even less obvious would be that we allow a pass that removes
instructions / globals, and then re-adds them. These changes would be
semantics-preserving, but would of course not preserve the removed bits of IR’s
addresses in memory.
>>
>> I believe (A) to be the spirit of the contract between passes and the
pass manager. (B) seems like a stretch, but depending on the analysis
invalidation needs of the PM, might still be ok. (C) seems totally off base, and
does not seem like a productive interpretation.
>>
>> Does this match everyone else’s intuition, and is (B) even a valid
interpretation?
>
>
> This concern was brought up in the relevant review
(https://reviews.llvm.org/D81230) as well.
> I think we can safely go with (A) here. It's unambiguous, and I
don't think there's any practical benefit to be had from (B) or (C).
+1
> Regards,
> Nikita
Roman
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

> On Jul 17, 2020, at 1:51 PM, Nikita Popov <nikita.ppv at gmail.com>
wrote:
> 
> On Fri, Jul 17, 2020 at 9:30 PM Jonathan Roelofs via llvm-dev <llvm-dev
at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> I’m digging through a build failure [1], and it looks like the loop idiom
recognizer adds some instructions [2], and then removes them again [3]. I don’t
understand why yet, but the LegacyPassManager detects that the structural hash
of the function has changed, and complains that the pass didn’t correctly report
that it changed the function [4] (even though materially, it didn’t).
> 
> This raises a broader question of what we really mean when we say that a
pass is allowed to report it made no changes through its runOn* function(s):
> 
> A) The obvious, and most restrictive condition would be that the pass can
only return false if it treated the Function/Module/etc that it visited purely
as read-only. From what I can tell, a lot of passes conservatively assume this
is the required condition.
> 
> B) Less obvious would be that we allow passes to add instructions
speculatively, so long as they remove whatever they added before returning
false. If one were to dump the IR before & after such a pass, you should see
no change in the text/bitcode. If you compared the in-memory representations,
you should see no semantic differences in the two, modulo “allowed” differences
like unordered lists of pointers (I vaguely remember a few cases of this
existing, but can’t remember the details).
> 
> C) Even less obvious would be that we allow a pass that removes
instructions / globals, and then re-adds them. These changes would be
semantics-preserving, but would of course not preserve the removed bits of IR’s
addresses in memory.
> 
> I believe (A) to be the spirit of the contract between passes and the pass
manager. (B) seems like a stretch, but depending on the analysis invalidation
needs of the PM, might still be ok. (C) seems totally off base, and does not
seem like a productive interpretation.
> 
> Does this match everyone else’s intuition, and is (B) even a valid
interpretation?
> 
> This concern was brought up in the relevant review
(https://reviews.llvm.org/D81230 <https://reviews.llvm.org/D81230>) as
well. I think we can safely go with (A) here. It's unambiguous, and I
don't think there's any practical benefit to be had from (B) or (C).
Thanks for the perfect reference!

https://reviews.llvm.org/D84071 <https://reviews.llvm.org/D84071>


Jon
> 
> Regards,
> Nikita
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200717/cda03537/attachment.html>

On Fri, Jul 17, 2020 at 12:31 PM Jonathan Roelofs via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I’m digging through a build failure [1], and it looks like the loop idiom
> recognizer adds some instructions [2], and then removes them again [3]. I
> don’t understand why yet, but the LegacyPassManager detects that the
> structural hash of the function has changed, and complains that the pass
> didn’t correctly report that it changed the function [4] (even though
> materially, it didn’t).
>
It may change the use-list order, which won't show up on a usual
"print"
but changes the visitation order of the def-use chain in the IR and so the
result of some algorithm.

-- 
Mehdi


>
> This raises a broader question of what we really mean when we say that a
> pass is allowed to report it made no changes through its runOn*
function(s):
>
> A) The obvious, and most restrictive condition would be that the pass can
> only return false if it treated the Function/Module/etc that it visited
> purely as read-only. From what I can tell, a lot of passes conservatively
> assume this is the required condition.
>
> B) Less obvious would be that we allow passes to add instructions
> speculatively, so long as they remove whatever they added before returning
> false. If one were to dump the IR before & after such a pass, you
should
> see no change in the text/bitcode. If you compared the in-memory
> representations, you should see no semantic differences in the two, modulo
> “allowed” differences like unordered lists of pointers (I vaguely remember
> a few cases of this existing, but can’t remember the details).
>
> C) Even less obvious would be that we allow a pass that removes
> instructions / globals, and then re-adds them. These changes would be
> semantics-preserving, but would of course not preserve the removed bits of
> IR’s addresses in memory.
>
> I believe (A) to be the spirit of the contract between passes and the pass
> manager. (B) seems like a stretch, but depending on the analysis
> invalidation needs of the PM, might still be ok. (C) seems totally off
> base, and does not seem like a productive interpretation.
>
> Does this match everyone else’s intuition, and is (B) even a valid
> interpretation?
>
>
> Cheers,
>
> Jon
>
>
> 1:
>
http://lab.llvm.org:8080/green/job/clang-stage1-cmake-RA-expensive/16803/consoleFull#-1371525106d489585b-5106-414a-ac11-3ff90657619c
> 2:
>
https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L931
> 3:
>
https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L936
> 4:
>
https://github.com/llvm/llvm-project/blob/master/llvm/lib/IR/LegacyPassManager.cpp#L1591
> _______________________________________________
> 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/20200717/2e718d31/attachment.html>