sameeran joshi via llvm-dev
2021-May-24 15:39 UTC
[llvm-dev] [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>
Johannes Doerfert via llvm-dev
2021-May-24 21:09 UTC
[llvm-dev] [loops in LLVM][CFG] Various methods to know weather 2 loops are identical in a given CFG.
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