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

[Johannes Doerfert via llvm-dev]

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