אלכס לופ' via llvm-dev
2019-Oct-29 17:55 UTC
[llvm-dev] Where and how to report an optimisation issue that doesn't cause a crash
<div><div dir="rtl"><div dir="ltr"
align="left">
<div dir="ltr" align="left">So I have a couple of
question regarding the approach provided by Chill.</div>
<div dir="ltr" align="left"><br>1. How to
prevent such memory re-reads in the future? Is there any BKM (best known method)
for programming guidelines which could eliminate or reduce those
re-reads?</div>
<div dir="ltr" align="left">2. What could be the
downside of the flag -Xclang -new-struct-path-tbaa? Why not using it by default
if it makes better aliasing analysis?</div>
<div dir="ltr" align="left"> </div>
<div dir="ltr" align="left">Thanks,</div>
<div dir="ltr" align="left">Alex. </div>
<br><br></div></div><section
class="cust_msg_end"></section><blockquote
style="margin:0;margin-bottom:20px;border-top:1px solid
#e0e0e0;"><br>ב אוק׳ 28, 2019 12:33, Ivan Kosarev
כתב:<blockquote style="margin:0;margin-bottom:20px;border-top:1px solid
#e0e0e0">
It's just that the work on the new TBAA machinery is not completed
and we do not have all the required logic for the new representation
in place.<br>
<br>
<br>
<div>On 27/10/2019 20:23, אלכס לופ' wrote:<br>
</div>
<blockquote type="cite"
cite="mid:%5EBF2D89B43C699965E0B802DE2F492E563EFD477F@walla.com">
<div dir="rtl">
<div>
<div dir="rtl">
<div dir="ltr" align="left">
<div dir="ltr">"...The idea behind the new
representation
was to address existing limitations by giving the TBAA
accurate information about accesses. If memory servers
me, in this specific case of an unknown index, the tag
shall refer to the whole member array, which is supposed
to mean that all and any of its elements can actually be
accessed."</div>
<div dir="ltr"> </div>
<div dir="ltr">So what about this case <a
href="https://godbolt.org/z/xFC4Rp"
moz-do-not-send="true">https://godbolt.org/z/xFC4Rp</a>
:<br> <br>
</div>
<div dir="ltr"> </div>
<div dir="ltr">
<div>struct S {</div>
<div> int a[256];</div>
<div> int b;</div>
<div>};</div>
<div> </div>
<div>int f(struct S *p, unsigned char i) {</div>
<div> if (p->b)</div>
<div> return42;</div>
<div> </div>
<div> p->a[i] = 3;</div>
<div> return p->b;</div>
<div>}</div>
<div> </div>
<div>"p->b" is re-read althoug the index
"i" cannot
acces beyond the array boundary. What went wrong
here?</div>
<div> </div>
<div>Thanks,</div>
<div>Alex.</div>
</div>
<br>
<br>
</div>
</div>
<section></section>
<blockquote style="margin: 0; margin-bottom: 20px; border-top:
1px solid #e0e0e0;"><br>
ב אוק׳ 27, 2019 17:47, Ivan Kosarev כתב:
<blockquote style="margin: 0; margin-bottom: 20px;
border-top: 1px solid #e0e0e0;">Hi Momchil,<br>
<br>
> That seems like something that Clang can do by itself
for access<br>
> tags for index expressions with member arrays: state
that they<br>
> access the offset in the struct that corresponds to
the first<br>
> array element, so unknown indices would still
conservatively<br>
> alias between each other, but not with other struct
members.<br>
<br>
Then all by-known-index array accesses would need to be
encoded as if there were accessing the first element,
wouldn't they? The idea behind the new representation was
to address existing limitations by giving the TBAA
accurate information about accesses. If memory servers me,
in this specific case of an unknown index, the tag shall
refer to the whole member array, which is supposed to mean
that all and any of its elements can actually be
accessed.<br>
<br>
-- <br>
Regards,<br>
Ivan<br>
<br>
<br>
<br>
<div>On 26/10/2019 23:39, Momchil Velikov via llvm-dev
wrote:</div>
<blockquote
cite="mid:CAEjVhjRhVQ6PHA6G+O6zZtFeMf_c0jzcDR-PMDvrFXemN9+CCQ@mail.gmail.com">
<div style="font-size: 9pt; font-family:
'Calibri',sans-serif;">
<h3 style="background-color: #ffffff; font-size: 10pt;
border: 1px dotted #003333; padding: .8em;"><span
style="color: #ff6600;">CAUTION:<strong>
</strong></span>This
email originated from outside of the organization.
Do not click links or open attachments unless you
recognize the sender and know the content is
safe. If you suspect potential phishing or spam
email, report it to <a
href="mailto:ReportSpam@accesssoftek.com"
moz-do-not-send="true">ReportSpam@accesssoftek.com</a></h3>
</div>
<div>
<div dir="ltr">
<div dir="ltr">
<div style="font-family: monospace,monospace;
font-size: small;">Using the shorter test
case:<br>
<br>
struct S {<br>
int a[3];<br>
int b;<br>
};<br>
<br>
int f(struct S *p, int i) {<br>
if (p->b)<br>
return 42;<br>
<br>
p->a[i] = 3;<br>
return p->b;<br>
}<br>
<br>
one can see that the the TBAA metadata loses
information about the array member:<br>
<br>
!4 = !{!"S", !5, i64 0, !7, i64
12}<br>
!5 = !{!"omnipotent char", !6, i64
0}<br>
<br>
The "new struct path TBAA" looks better, it
seems to say "there are 12 bytes of<br>
`int`s at offset 0 in struct S"<br>
<br>
(Command line was ./bin/clang -target
armv7m-eabi -O2 -S y.c -emit-llvm -Xclang<br>
-new-struct-path-tbaa)<br>
<br>
<br>
!3 = !{!4, !7, i64 12, i64 4}<br>
!4 = !{!5, i64 16, !"S", !7, i64 0, i64
12,
!7, i64 12, i64 4}<br>
!5 = !{!6, i64 1, !"omnipotent
char"}<br>
!6 = !{!"Simple C/C++ TBAA"}<br>
!7 = !{!5, i64 4, !"int"}<br>
!8 = !{!7, !7, i64 0, i64 4}<br>
<br>
but then, the access tag for the store to the
array<br>
<br>
<br>
%arrayidx = getelementptr inbounds
%struct.S, %struct.S* %p, i32 0, i32 0, i32 %i<br>
store i32 3, i32* %arrayidx, align 4, !tbaa
!8<br>
<br>
says just "it's in int" and there it still
a
redundant load:<br>
<br>
f:<br>
ldr r2, [r0, #12]<br>
cmp r2, #0<br>
itt ne<br>
movne r0, #42<br>
bxne lr<br>
movs r2, #3<br>
str.w r2, [r0, r1, lsl #2]<br>
ldr r0, [r0, #12]<br>
bx lr<br>
<br>
So, I manually hacked the metadata too look
like:<br>
<br>
!8 = !{!4, !7, i64 0, i64 4}<br>
<br>
i.e. as if we access the first element of the
array.<br>
<br>
Running that through `opt -O2` and `llc`
yields:<br>
<br>
f:<br>
ldr r2, [r0, #12]<br>
cmp r2, #0<br>
iteee ne<br>
movne r0, #42<br>
moveq r2, #3<br>
streq.w r2, [r0, r1, lsl #2]<br>
moveq r0, #0<br>
bx lr<br>
<br>
That seems like something that Clang can do by
itself for access tags for index<br>
expressions with member arrays: state that they
access the offset in the struct<br>
that corresponds to the first array element, so
unknown indices would still<br>
conservatively alias between each other, but not
with other struct members.<br>
<br>
Thoughts? Pitfalls? I may give it a shot.</div>
<div style="font-family: monospace,monospace;
font-size: small;"> </div>
<div style="font-family: monospace,monospace;
font-size: small;">~chill</div>
<div style="font-family: monospace,monospace;
font-size: small;"> </div>
<div style="font-family: monospace,monospace;
font-size: small;">--</div>
<div style="font-family: monospace,monospace;
font-size: small;">Compiler scrub,
Arm</div>
<div style="font-family: monospace,monospace;
font-size: small;"> </div>
</div>
</div>
</div>
<br>
<fieldset></fieldset>
<pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
moz-do-not-send="true">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</blockquote>
</blockquote>
</div>
</div>
</blockquote>
<br>
<br></blockquote></blockquote><br></div>
David Blaikie via llvm-dev
2019-Oct-29 18:45 UTC
[llvm-dev] Where and how to report an optimisation issue that doesn't cause a crash
I don't think there's any particular set of recommendations for this specific missed optimization/issue - are you working in an environment where memory reads are exceptionally expensive (in comparison to all the other things that a compiler might optimize code for & might not do so perfectly (no compiler's perfect, even within the bounds of the language and non-standard extensions))? I think this falls under the general bucket of "write code" -> "optimize code". Use profilers, find the hot spots, look at the code to see if you can make it algorithmically better, look at the machine code if it comes to that & see if you can tweak the source to get the assembly you want, or hand-write portions, etc. 2) I'm guessing it's work-in-progress and might not be production-ready/tested yet On Tue, Oct 29, 2019 at 10:57 AM אלכס לופ' <alex_lop at walla.com> wrote:> So I have a couple of question regarding the approach provided by Chill. > > 1. How to prevent such memory re-reads in the future? Is there any BKM > (best known method) for programming guidelines which could eliminate or > reduce those re-reads? > 2. What could be the downside of the flag -Xclang -new-struct-path-tbaa? > Why not using it by default if it makes better aliasing analysis? > > Thanks, > Alex. > > > > ב אוק׳ 28, 2019 12:33, Ivan Kosarev כתב: > > It's just that the work on the new TBAA machinery is not completed and we > do not have all the required logic for the new representation in place. > > > On 27/10/2019 20:23, אלכס לופ' wrote: > > "...The idea behind the new representation was to address existing > limitations by giving the TBAA accurate information about accesses. If > memory servers me, in this specific case of an unknown index, the tag shall > refer to the whole member array, which is supposed to mean that all and any > of its elements can actually be accessed." > > So what about this case https://godbolt.org/z/xFC4Rp : > > > struct S { > int a[256]; > int b; > }; > > int f(struct S *p, unsigned char i) { > if (p->b) > return42; > > p->a[i] = 3; > return p->b; > } > > "p->b" is re-read althoug the index "i" cannot acces beyond the array > boundary. What went wrong here? > > Thanks, > Alex. > > > > ב אוק׳ 27, 2019 17:47, Ivan Kosarev כתב: > > Hi Momchil, > > > That seems like something that Clang can do by itself for access > > tags for index expressions with member arrays: state that they > > access the offset in the struct that corresponds to the first > > array element, so unknown indices would still conservatively > > alias between each other, but not with other struct members. > > Then all by-known-index array accesses would need to be encoded as if > there were accessing the first element, wouldn't they? The idea behind the > new representation was to address existing limitations by giving the TBAA > accurate information about accesses. If memory servers me, in this specific > case of an unknown index, the tag shall refer to the whole member array, > which is supposed to mean that all and any of its elements can actually be > accessed. > > -- > Regards, > Ivan > > > > On 26/10/2019 23:39, Momchil Velikov via llvm-dev wrote: > > CAUTION: This email originated from outside of the organization. Do not > click links or open attachments unless you recognize the sender and know > the content is safe. If you suspect potential phishing or spam email, > report it to ReportSpam at accesssoftek.com > Using the shorter test case: > > struct S { > int a[3]; > int b; > }; > > int f(struct S *p, int i) { > if (p->b) > return 42; > > p->a[i] = 3; > return p->b; > } > > one can see that the the TBAA metadata loses information about the array > member: > > !4 = !{!"S", !5, i64 0, !7, i64 12} > !5 = !{!"omnipotent char", !6, i64 0} > > The "new struct path TBAA" looks better, it seems to say "there are 12 > bytes of > `int`s at offset 0 in struct S" > > (Command line was ./bin/clang -target armv7m-eabi -O2 -S y.c -emit-llvm > -Xclang > -new-struct-path-tbaa) > > > !3 = !{!4, !7, i64 12, i64 4} > !4 = !{!5, i64 16, !"S", !7, i64 0, i64 12, !7, i64 12, i64 4} > !5 = !{!6, i64 1, !"omnipotent char"} > !6 = !{!"Simple C/C++ TBAA"} > !7 = !{!5, i64 4, !"int"} > !8 = !{!7, !7, i64 0, i64 4} > > but then, the access tag for the store to the array > > > %arrayidx = getelementptr inbounds %struct.S, %struct.S* %p, i32 0, > i32 0, i32 %i > store i32 3, i32* %arrayidx, align 4, !tbaa !8 > > says just "it's in int" and there it still a redundant load: > > f: > ldr r2, [r0, #12] > cmp r2, #0 > itt ne > movne r0, #42 > bxne lr > movs r2, #3 > str.w r2, [r0, r1, lsl #2] > ldr r0, [r0, #12] > bx lr > > So, I manually hacked the metadata too look like: > > !8 = !{!4, !7, i64 0, i64 4} > > i.e. as if we access the first element of the array. > > Running that through `opt -O2` and `llc` yields: > > f: > ldr r2, [r0, #12] > cmp r2, #0 > iteee ne > movne r0, #42 > moveq r2, #3 > streq.w r2, [r0, r1, lsl #2] > moveq r0, #0 > bx lr > > That seems like something that Clang can do by itself for access tags for > index > expressions with member arrays: state that they access the offset in the > struct > that corresponds to the first array element, so unknown indices would still > conservatively alias between each other, but not with other struct members. > > Thoughts? Pitfalls? I may give it a shot. > > ~chill > > -- > Compiler scrub, Arm > > > _______________________________________________ > LLVM Developers mailing listllvm-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/20191029/4efc5f86/attachment.html>
Ivan Kosarev via llvm-dev
2019-Oct-29 19:20 UTC
[llvm-dev] Where and how to report an optimisation issue that doesn't cause a crash
Answering the second question, the new TBAA representation is a work in progress; it's not mature enough to be enabled by default. On 29/10/2019 19:55, אלכס לופ' wrote:> So I have a couple of question regarding the approach provided by Chill. > > 1. How to prevent such memory re-reads in the future? Is there any BKM > (best known method) for programming guidelines which could eliminate > or reduce those re-reads? > 2. What could be the downside of the flag -Xclang > -new-struct-path-tbaa? Why not using it by default if it makes better > aliasing analysis? > Thanks, > Alex. > > > > ב אוק׳ 28, 2019 12:33, Ivan Kosarev כתב: > > It's just that the work on the new TBAA machinery is not > completed and we do not have all the required logic for the > new representation in place. > > > On 27/10/2019 20:23, אלכס לופ' wrote: >> "...The idea behind the new representation was to address >> existing limitations by giving the TBAA accurate information >> about accesses. If memory servers me, in this specific case >> of an unknown index, the tag shall refer to the whole member >> array, which is supposed to mean that all and any of its >> elements can actually be accessed." >> So what about this case https://godbolt.org/z/xFC4Rp : >> >> struct S { >> int a[256]; >> int b; >> }; >> int f(struct S *p, unsigned char i) { >> if (p->b) >> return42; >> p->a[i] = 3; >> return p->b; >> } >> "p->b" is re-read althoug the index "i" cannot acces beyond >> the array boundary. What went wrong here? >> Thanks, >> Alex. >> >> >> >> ב אוק׳ 27, 2019 17:47, Ivan Kosarev כתב: >> >> Hi Momchil, >> >> > That seems like something that Clang can do by >> itself for access >> > tags for index expressions with member arrays: >> state that they >> > access the offset in the struct that corresponds to >> the first >> > array element, so unknown indices would still >> conservatively >> > alias between each other, but not with other struct >> members. >> >> Then all by-known-index array accesses would need to >> be encoded as if there were accessing the first >> element, wouldn't they? The idea behind the new >> representation was to address existing limitations by >> giving the TBAA accurate information about accesses. >> If memory servers me, in this specific case of an >> unknown index, the tag shall refer to the whole >> member array, which is supposed to mean that all and >> any of its elements can actually be accessed. >> >> -- >> Regards, >> Ivan >> >> >> >> On 26/10/2019 23:39, Momchil Velikov via llvm-dev wrote: >> >> >> CAUTION:**This email originated from >> outside of the organization. Do not click >> links or open attachments unless you >> recognize the sender and know the content >> is safe. If you suspect potential phishing >> or spam email, report it to >> ReportSpam at accesssoftek.com >> <mailto:ReportSpam at accesssoftek.com> >> >> Using the shorter test case: >> >> struct S { >> int a[3]; >> int b; >> }; >> >> int f(struct S *p, int i) { >> if (p->b) >> return 42; >> >> p->a[i] = 3; >> return p->b; >> } >> >> one can see that the the TBAA metadata loses >> information about the array member: >> >> !4 = !{!"S", !5, i64 0, !7, i64 12} >> !5 = !{!"omnipotent char", !6, i64 0} >> >> The "new struct path TBAA" looks better, it seems >> to say "there are 12 bytes of >> `int`s at offset 0 in struct S" >> >> (Command line was ./bin/clang -target armv7m-eabi >> -O2 -S y.c -emit-llvm -Xclang >> -new-struct-path-tbaa) >> >> >> !3 = !{!4, !7, i64 12, i64 4} >> !4 = !{!5, i64 16, !"S", !7, i64 0, i64 12, >> !7, i64 12, i64 4} >> !5 = !{!6, i64 1, !"omnipotent char"} >> !6 = !{!"Simple C/C++ TBAA"} >> !7 = !{!5, i64 4, !"int"} >> !8 = !{!7, !7, i64 0, i64 4} >> >> but then, the access tag for the store to the array >> >> >> %arrayidx = getelementptr inbounds %struct.S, >> %struct.S* %p, i32 0, i32 0, i32 %i >> store i32 3, i32* %arrayidx, align 4, !tbaa !8 >> >> says just "it's in int" and there it still a >> redundant load: >> >> f: >> ldr r2, [r0, #12] >> cmp r2, #0 >> itt ne >> movne r0, #42 >> bxne lr >> movs r2, #3 >> str.w r2, [r0, r1, lsl #2] >> ldr r0, [r0, #12] >> bx lr >> >> So, I manually hacked the metadata too look like: >> >> !8 = !{!4, !7, i64 0, i64 4} >> >> i.e. as if we access the first element of the array. >> >> Running that through `opt -O2` and `llc` yields: >> >> f: >> ldr r2, [r0, #12] >> cmp r2, #0 >> iteee ne >> movne r0, #42 >> moveq r2, #3 >> streq.w r2, [r0, r1, lsl #2] >> moveq r0, #0 >> bx lr >> >> That seems like something that Clang can do by >> itself for access tags for index >> expressions with member arrays: state that they >> access the offset in the struct >> that corresponds to the first array element, so >> unknown indices would still >> conservatively alias between each other, but not >> with other struct members. >> >> Thoughts? Pitfalls? I may give it a shot. >> ~chill >> -- >> Compiler scrub, Arm >> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org <mailto: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/20191029/55900518/attachment.html>