[LSR] Address a special case involving NULL.

[stefanp]

Summary

While looking at tests with opaque pointers it was noticed that Loop Strength Reduction behaved differently in cases when a pointer is NULL.
This patch adds a special case to deal with NULL.

[nikic]

Please add some tests for the new conditions.

[stefanp]

In D133426#3774603, @nikic wrote:

Please add some tests for the new conditions.

Yes. Good point. I will try to get a small test for each condition that was changed.

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

2101 ↗

(On Diff #458454)

So, the null special case doesn't make a lot of sense to me, in that promoting a null pointer is pretty pointless -- those accesses are UB anyway, right?

However, I do think that that this bailout can be removed entirely: https://reviews.llvm.org/D133485

[stefanp]

llvm/lib/Transforms/Scalar/LICM.cpp

2101 ↗

(On Diff #458454)

So, the null special case doesn't make a lot of sense to me, in that promoting a null pointer is pretty pointless -- those accesses are UB anyway, right?

However, I do think that that this bailout can be removed entirely: https://reviews.llvm.org/D133485

I took a look at that patch and I agree that is a better solution than what I have here.
I was trying to be very conservative and make changes only for NULL values but if the bailout can be removed completely that's much better.

I will change this patch to remove the changes in LICM.

[stefanp]

Sorry that this took a few days.
Removed the code from LICM.
Added a test for the loop strength reduction. The test shows simpler code when
the guard for the NULL is added. However, there may be other tests where the
reverse is true.

[nikic]

llvm/test/Transforms/LoopStrengthReduce/Power/opaque-null-ptr.ll

2

As this is just testing the IR transform, it would be better to use opt -S -mtriple=powerpc64le-unknown-linux-gnu -mcpu=pwr8 -loop-reduce < %s or so (in which case you can also use update_test_checks.py).

[efriedma]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3478

NULL has a live range.

If you assume all the users of the NULL are GEPs, then I guess in practice the null is going to get eliminated... but GEPs from null should be extremely rare: it implies you're loading from an absolute address. And it's undefined behavior to load from a null pointer unless the function is marked null_pointer_is_valid (or you're in a non-zero address space).

llvm/test/Transforms/LoopStrengthReduce/Power/opaque-null-ptr.ll

27

Does this really reflect actual user code? The first iteration of the loop loads from the constant addresses "4" and "8".

[stefanp]

Thank you both for looking at this patch.
Looking at the comments I feel like I made an incorrect assumption about NULL pointers in this case and I'm just going to abandon this patch.

However, I have also replied to the comments below.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3478

Fair enough. I agree with you.
This was actually my initial assumption and it seems to me that I was wrong. Therefore, I would like to abandon this patch.

However, I would like to give more background on the motivation of the patch because that is what I was trying to address in the first place. I have been looking at switching some tests from typed pointers to opaque pointers. The issue I have found is that certain passes (including this one) behave differently and sometimes produce different code when we switch from typed to opaque pointers. The reason for this is that we are asking for the "users" of ptr null (here: for (const Use &U : V->uses()) {).
For example:

%i1 = getelementptr inbounds i8, i8* null, i64 %adr1
%f2 = getelementptr inbounds float, float* null, i64 %adr2

vs.

%i1 = getelementptr inbounds i8, ptr null, i64 %adr1
%f2 = getelementptr inbounds float, ptr null, i64 %adr2

In the first example there is one use of i8* null and one use of float* null. However, in the second example we have two uses of ptr null. This then takes a different path through the compiler and we may end up with different code.

Anyway, I agree with you that GEPs from NULL (basically a form of inttoptr) are not common. However, should we be concerned about this behaviour? Would we need to document it? Or it is just rare enough that we don't really care?

llvm/test/Transforms/LoopStrengthReduce/Power/opaque-null-ptr.ll

2

I did try this initially but for some reason I was getting different results for this test.

Anyway, I plan on abandoning this patch so I'm not going to look further into exactly why I am getting different results.

27

This is actually a reduced test from user code.
Unfortunately the resulting test is not realistic user code because the way that it was reduced discarded a lot of the code that would have given the function any real meaning.

[efriedma]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3478

If you're iterating over the use-list of "null", you're probably doing something which doesn't make sense, anyway... it should be rare enough that it doesn't really matter.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

while (!Worklist.empty()) {
     else if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
       Worklist.push_back(D->getLHS());
       Worklist.push_back(D->getRHS());
     } else if (const SCEVUnknown *US = dyn_cast<SCEVUnknown>(S)) {
       const Value *V = US->getValue();
       if (const Instruction *Inst = dyn_cast<Instruction>(V)) {
         // Look for instructions defined outside the loop.
         if (L->contains(Inst)) continue;
-      } else if (isa<UndefValue>(V))
+      } else if (isa<UndefValue>(V)) {
         // Undef doesn't have a live range, so it doesn't matter.
         continue;
+      } else if (const Constant *Const = dyn_cast<Constant>(V)) {
+        // NULL values don't really have a live range. They are just NULL.
+        if (Const->isNullValue())
+          continue;
+      }
       for (const Use &U : V->uses()) {
         const Instruction *UserInst = dyn_cast<Instruction>(U.getUser());
         // Ignore non-instructions.
         if (!UserInst)
           continue;
         // Don't bother if the instruction is an EHPad.
         if (UserInst->isEHPad())
           continue;

llvm/test/Transforms/LoopStrengthReduce/Power/opaque-null-ptr.ll

+; RUN: llc -O3 -mtriple=powerpc64le-unknown-linux-gnu -mcpu=pwr8 \
+; RUN:   -stop-after=loop-reduce %s -o - | FileCheck %s
+
+ %0 = type <{ float }>
+
+define void @test(ptr %arg1, ptr %arg2, float %storeval) local_unnamed_addr {
+; CHECK-LABEL: test
+; CHECK:       bb175:
+; CHECK-NEXT:    %lsr.iv = phi i64 [ %lsr.iv.next, %bb175 ], [ 0, %bb ]
+; CHECK-NEXT:    %i176 = phi i64 [ %i237, %bb175 ], [ 1, %bb ]
+; CHECK-NEXT:    %i237 = add nuw nsw i64 %i176, 2
+; CHECK-NEXT:    %lsr.iv.next = add nuw nsw i64 %lsr.iv, 8
+; CHECK-NEXT:    %i238 = icmp slt i64 %i237, -1
+; CHECK-NEXT:    br i1 %i238, label %bb175, label %bb239
+
+bb:
+  %i21 = getelementptr [0 x float], ptr %arg2, i64 0, i64 -1
+  br label %bb175
+
+bb175:                                            ; preds = %bb175, %bb
+  %i176 = phi i64 [ %i237, %bb175 ], [ 1, %bb ]
+  %i177 = phi float [ %i198, %bb175 ], [ 0.000000e+00, %bb ]
+  %i184 = shl i64 %i176, 2
+  %i185 = getelementptr %0, ptr %i21, i64 %i176, i32 0
+  %i186 = load float, ptr %i185, align 4
+  %uglygep = getelementptr i8, ptr null, i64 %i184
+  %uglygep2 = getelementptr i8, ptr %uglygep, i64 4
+  %i190 = load float, ptr %uglygep2, align 4
+  %i193 = load float, ptr %uglygep, align 4
+  %i194 = fmul contract float %i186, %i193
+  %i195 = fadd contract float %i177, %i194
+  %i198 = fsub contract float %i195, %i190
+  %i237 = add nuw nsw i64 %i176, 2
+  %i238 = icmp slt i64 %i237, -1
+  br i1 %i238, label %bb175, label %bb239
+
+bb239:                                            ; preds = %bb175
+  store float %storeval, ptr null, align 4
+  ret void
+}