<div dir="ltr"><div class="gmail_default" style="font-family:monospace">Thank you for the clarification with an example.<br><br>Here's what I meant by identical, there are 2 forms I could think of<br>*Strongly identical* - <br> 1. Exact match of loop headers and loop bodys between 2 loops.<br> e.g Loop mentioned below <br> for (int i = 0; i < 10; ++i) { A[i] = i; }<br> is not identical to any options mentioned, Whereas a matching candidate which is strongly identical could be an exact loop with flexibility to change the iteration variable name.<br> for (int j = 0; j < 10; ++j) { A[j] = j; }<br> or <br> for (int i = 0; i < 10; ++i) { A[i] = i; }<br><br>*Weakly identical* - <br>Loops are matched based on only header and the body is skipped for check.<br>e.g A,B are identical from the above mentioned question.<br><br>Given that it becomes difficult to have strongly identical loops, reverting back to weakly identical loops might help to identify if the compiler does make changes to the other loops whereas it misses doing so in the first loop.<br>e.g <br>*Sample loop*<br> for (int i = 0; i < 10; ++i) { <br> X = 100;<br> A[i] = i; <br> }<br> and <br> for (int i = 0; i < 10; ++i) { <br> A[i] = i; <br> X = 100; <br> }<br>From the definition of strongly identical they are not equal (as their headers match, whereas bodies don't).<br>But having a strongly identical definition makes it harder to identify if in some cases the instructions in the loop's body are moved and optimized.<br>e.g. When X is pulled out, it becomes weakly identical to *sample loop*.<br> X = 100;<br> for (int i = 0; i < 10; ++i) { <br> A[i] = i; <br> }<br><br>This loop though not identical as per strongly identical definition but it is identical when compared using weakly identical definition( as the header are same), this usage of weakly identical helps to figure out if some loops are getting optimized whereas others aren't.<br>On top of that, if 2 loops seem weakly identical, we can do more metric checks like count the number of instructions in them to know if there is some missing/different approach followed for the other loop.<br><br></div><div class="gmail_default" style="font-family:monospace">~/Sameeran<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, May 25, 2021 at 2:39 AM Johannes Doerfert <<a href="mailto:johannesdoerfert@gmail.com">johannesdoerfert@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Unsure what "identical" means if you are not looking at the instructions.<br>
<br>
Let me ask like this, what are equivalent loops to this one:<br>
<br>
for (int i = 0; i < 10; ++i) { A[i] = i; }<br>
<br>
A) for (int i = 0; i < 10; ++i) { A[i] = i + 1; }<br>
<br>
B) for (int i = 0; i < 10; ++i) { A[i+1] = i; }<br>
<br>
C) for (int i = 1; i <= 10; ++i) { A[i-1] = i-1; }<br>
<br>
D) for (int i = 1; i < 11; ++i) { A[i-1] = i-1; }<br>
<br>
E) for (int i = 9; i >= 0; --i) { A[9 - i] = 9 - i; }<br>
<br>
While the answer does impact what I would recommend to do, I think<br>
loop fusion code is a good start.<br>
<br>
~ Johannes<br>
<br>
<br>
On 5/24/21 10:39 AM, sameeran joshi via llvm-dev wrote:<br>
> Hello,<br>
> I am trying to identify from a given CFG for a function, if 2 loops<br>
> represented in LLVM's loop representation form are identical.<br>
><br>
> The simplest definition of identical loops could be loops with<br>
> 1. same initialization<br>
> 2. same trip count[1]<br>
> 3. same increment value<br>
><br>
> Comparing 2 loops based on the instructions inside the loop seems<br>
> problematic for cases when some loop optimizations would try to remove/move<br>
> instructions out of the loop.<br>
><br>
> I was interested to know if there are other methods or already available<br>
> analysis to find if the 2 loops are identical apart from the above<br>
> mentioned methods?<br>
><br>
> [1]<br>
> <a href="https://github.com/llvm/llvm-project/blob/e42636d3c1a41a9b7c5d8095ae5ef6682e26d4a2/llvm/lib/Transforms/Scalar/LoopFuse.cpp#L704" rel="noreferrer" target="_blank">https://github.com/llvm/llvm-project/blob/e42636d3c1a41a9b7c5d8095ae5ef6682e26d4a2/llvm/lib/Transforms/Scalar/LoopFuse.cpp#L704</a><br>
> ~/Sameeran<br>
><br>
><br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> <a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>