Trivial memset optimization not applied to loops under -Oz (LoopIdiomRecognize)

[jeffy1009]

Bugzilla Link	50964
Version	12.0
OS	All
CC	@fhahn,@TH3CHARLie

Extended Description

Issue description:
https://llvm.discourse.group/t/loops-not-optimized-under-oz-that-should-have-been/3734/1

[fhahn]

LoopIdiomRecognize currently fails because the loop does not get rotated with -Oz. It should still be possible to convert loops as the one below to memcpy in LoopIdomRecognize, even if it is not rotated.

define void @​test(i8* noalias nonnull align 1 %start, i8* %end) {
entry:
  br label %loop.header

loop.header:
  %ptr.iv = phi i8* [ %start, %entry ], [ %ptr.iv.next, %loop.latch ]
  %_12.i = icmp eq i8* %ptr.iv, %end
  br i1 %_12.i, label %exit, label %loop.latch

loop.latch:
  %ptr.iv.next = getelementptr inbounds i8, i8* %ptr.iv, i64 1
  store i8 1, i8* %ptr.iv, align 1
  br label %loop.header

exit:
  ret void
}

https://llvm.godbolt.org/z/53Pb1hGzx

I'd be happy to provide help/guidance if anyone is interested in tackling this.

[TH3CHARLie]

Hi Florian! I am interested in working on this, I'll look it and will let you know if anything blocks me.

[llvmbot]

Hi Florian,
Do you intend to solve it by teaching LIR to perform "loop-rotate" here?

[fhahn]

Hi Florian,
Do you intend to solve it by teaching LIR to perform "loop-rotate" here?

I won’t be able to work on this, but can help with the review.

[fhahn]

I think Xuanda mentioned they might be looking into the issue, but that was a while ago so I am not sure about the status.

I don’t think we need to rotate, we should be able to do the analysis on unrotated loops as well.

[TH3CHARLie]

Hi Florian and Yueh-Ting, I've tried this one month ago but didn't make some meaningful progress. So please feel free to pick it up.

[llvmbot]

I don’t think we need to rotate, we should be able to do the analysis on unrotated loops as well.

Eventually the optimization would still need to generate guards for it? (plz correct me if I'm wrong)

Hi Florian and Yueh-Ting, I've tried this one month ago but didn't make some meaningful progress. So please feel free to pick it up.

I'm curious on how to solve the question and happy to contribute!
Thank you Xuanda for the prompt reply.

[fhahn]

I don’t think we need to rotate, we should be able to do the analysis on unrotated loops as well.

Eventually the optimization would still need to generate guards for it? (plz
correct me if I'm wrong)

Yes, but I think for Oz we should initially only focus on the case where no loop remains after memset conversion

[llvmbot]

I don’t think we need to rotate, we should be able to do the analysis on unrotated loops as well.

Eventually the optimization would still need to generate guards for it? (plz
correct me if I'm wrong)

Yes, but I think for Oz we should initially only focus on the case where no
loop remains after memset conversion
Ah, I see.
The expected optimization would be something like the below?

for (int i=start; i<end; ++i) {
  A[i] = CONST_VAL; // single store instruction
}

and optimized to

if (start < end) {
  memset(A + start, CONST_VAL, sizeof(A[0));
}

---

Then I guess the thing to figure out here will be - how does the pass check whether the store inst. is the only inst. inside the loop. (Is there API for it?

[razetime]

I'd be happy to provide help/guidance if anyone is interested in tackling this.

@fhahn Hello, I'm new to the project, and I'd like to solve this issue. I'm currently trying to replicate this bug in C++ so i can figure out what i should modify. This is what I've made to try and reproduce the issue(hope it is correct):

#include <vector>
#include <stdint.h>

using namespace std;
int main() {
	vector<uint8_t> v(8);
}
void memzero(vector<uint8_t> vec) {
	for(auto i : vec) {
		i = 0;
	}
}

Currently I only know that this has something to do with llvm-project\llvm\lib\Transforms\Scalar\LoopIdiomRecognize.cpp. I would like to get some pointers on where the changes should be implemented.

[fhahn]

I don't think you really need to have a C++ example. It should be sufficient to run opt -loop-idiom on the LLVM IR from https://llvm.godbolt.org/z/YrGqGhnE9 .

As a starting point, you can take a look at what loop-idiom does and why it fails for the example. Adding -debug should provide a bit of additional information, but using GDB/additional print statements may also be helpful.

[razetime]

Oh, good to know. What I'm currently doing is

opt -loop-idiom -debug OZtest.ll -o OZtestloopid.ll
llc OZtestloopid.ll
clang-14 OZtestloopid.s

But I get this error on the last command:

/usr/bin/ld: /lib/x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
clang-14: error: linker command failed with exit code 1 (use -v to see invocation)

I assume I should be running gdb on the result of clang file.s and check what is happening there, but i'd like help with rectifying this error first.

[fhahn]

There is no need to run llc or clang after opt -loop-idiom.

You can just check the output generated by opt -loop-idiom -S. At the moment, there's no memset call because the transformation does not trigger. After a fix, loop-idiom should create a memset and it is sufficient to check the output after opt to verify.

[razetime]

in this area a comment says the following:

// The following transforms hoist stores/memsets into the loop pre-header.
// Give up if the loop has instructions that may throw.

is this relevant to the problem?

SimpleLoopSafetyInfo's docs say that it may give false positives to avoid complicated analysis.