llvm dev - May 2021 - [loops in LLVM][CFG] Various methods to know weather 2 loops are identical in a given CFG.

Hello,
I am trying to identify from a given CFG for a function, if 2 loops
represented in LLVM's loop representation form are identical.

The simplest definition of identical loops could be loops with
1. same initialization
2. same trip count[1]
3. same increment value

Comparing 2 loops based on the instructions inside the loop seems
problematic for cases when some loop optimizations would try to remove/move
instructions out of the loop.

I was interested to know if there are other methods or already available
analysis to find if the 2 loops are identical apart from the above
mentioned methods?

[1]
https://github.com/llvm/llvm-project/blob/e42636d3c1a41a9b7c5d8095ae5ef6682e26d4a2/llvm/lib/Transforms/Scalar/LoopFuse.cpp#L704
~/Sameeran
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210524/fc1448b3/attachment.html>

Unsure what "identical" means if you are not looking at the
instructions.

Let me ask like this, what are equivalent loops to this one:

for (int i = 0; i < 10; ++i) { A[i] = i; }

A) for (int i = 0; i < 10; ++i) { A[i] = i + 1; }

B) for (int i = 0; i < 10; ++i) { A[i+1] = i; }

C) for (int i = 1; i <= 10; ++i) { A[i-1] = i-1; }

D) for (int i = 1; i < 11; ++i) { A[i-1] = i-1; }

E) for (int i = 9; i >= 0; --i) { A[9 - i] = 9 - i; }

While the answer does impact what I would recommend to do, I think
loop fusion code is a good start.

~ Johannes


On 5/24/21 10:39 AM, sameeran joshi via llvm-dev wrote:
> Hello,
> I am trying to identify from a given CFG for a function, if 2 loops
> represented in LLVM's loop representation form are identical.
>
> The simplest definition of identical loops could be loops with
> 1. same initialization
> 2. same trip count[1]
> 3. same increment value
>
> Comparing 2 loops based on the instructions inside the loop seems
> problematic for cases when some loop optimizations would try to remove/move
> instructions out of the loop.
>
> I was interested to know if there are other methods or already available
> analysis to find if the 2 loops are identical apart from the above
> mentioned methods?
>
> [1]
>
https://github.com/llvm/llvm-project/blob/e42636d3c1a41a9b7c5d8095ae5ef6682e26d4a2/llvm/lib/Transforms/Scalar/LoopFuse.cpp#L704
> ~/Sameeran
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev