Do not traverse ConstantData use-list in LoopInterchange

[willir]

Summary

The findInnerReductionPhi function is looking for reduction variables,
which cannot be constants; also, walking users of some Constants (particularly ConstantData)
doesn't make semantic sense in a function pass since its users can be spread among different
functions or modules that happen to be in the same LLVMContext

[dexonsmith]

@fhahn, can you help with the review here? This is one of only a few instances of walking the use-list of ConstantData. The broader context is an old RFC that @willir is working with me on:
https://lists.llvm.org/pipermail/llvm-dev/2016-September/105157.html

(I know the motivation and context, but I'm not the right person to review functional changes to this pass.)

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

663–675

It looks like sometimes findInnerReductionPhi is running on ConstantData, which can come from another function (or module), and will eventually lose its use-lists (no one should walk the use-list of i1 0; usually anything they learn from that will be wrong).

• @willir's current patch changes the order of iteration. I think we'll need to check compile-time if we do this.
• Another option would be to return nullptr on isa<ConstantData>(), if it's correct.
• If that's correct, should this return nullptr on isa<Constant>() more generally?

[fhahn]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

663–675

If that's correct, should this return nullptr on isa<Constant>() more generally?

I think findInnerReductionPhi should never return anything other than nullptr for constants; it is looking for a reduction results, which should always be an instruction.

So returning nullptr on isa<Constant> seems the best way forward. It would also be good to add a test with LCSSA phis with constant incoming values, e.g something like the below to llvm/test/Transforms/LoopInterchange/reductions-across-inner-and-outer-loop.ll

define i64 @test1([100 x [100 x i64]]* %Arr) {
entry:
  br label %for1.header

for1.header:                                         ; preds = %for1.inc, %entry
  %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
  %sum.outer = phi i64 [ 0, %entry ], [ %const.lcssa, %for1.inc ]
  br label %for2

for2:                                        ; preds = %for2, %for1.header
  %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
  %sum.inner = phi i64 [ %sum.outer, %for1.header ], [ %sum.inc, %for2 ]
  %arrayidx = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
  %lv = load i64, i64* %arrayidx, align 4
  %sum.inc = add i64 %sum.inner, %lv
  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
  %exit1 = icmp eq i64 %indvars.iv.next.3, 100
  br i1 %exit1, label %for1.inc, label %for2

for1.inc:                                ; preds = %for2
  %const.lcssa = phi i64 [ 1, %for2 ]
  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
  %exit2 = icmp eq i64 %indvars.iv.next24, 100
  br i1 %exit2, label %for1.loopexit, label %for1.header

for1.loopexit:                                 ; preds = %for1.inc
  %const.lcssa2 = phi i64 [ %const.lcssa, %for1.inc ]
  ret i64 %const.lcssa2
}

[willir]

Make findInnerReductionPhi return nullptr on isa<Constant> as suggested
by @fhahn.
Add a test for that case.

[fhahn]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

664

Could you add a comment with the reasoning for the early exit here?

[willir]

Add a comment with the reasoning for the early exit

[fhahn]

LGTM, thanks!

Do not traverse ConstantData use-list in LookInterchange

There's a typo in the title: LookInterchange -> LoopInterchange. Please adjust before committing.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

666

thanks for the comment. The bit about walking users of constants seems a bit verbose and I think it would be better to have this rule documented in a single place, rather than adding it at all the places that are going to be updated. I'd remove it here.

[dexonsmith]

LGTM too; agreed the comment could be trimmed down too, but I think it's important to have something about that in the commit message.

@willir, I can commit this for you once you update the patch.

[willir]

Trim down the comment

[willir]

Thanks for the review. I hope the current comment looks better.

Here is my git info:

• GIT_AUTHOR_NAME="Anton Rapetov"
• GIT_AUTHOR_EMAIL="[e-mail]"

[dexonsmith]

Pushed in bfec9148a042c8fd6093ae0d54c784211a295c6c with some minor tweaks to the comments and commit message.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

if (!PHI)
     return SV;
 
   if (PHI->getNumIncomingValues() != 1)
     return SV;
   return followLCSSA(PHI->getIncomingValue(0));
 }
 
 // Check V's users to see if it is involved in a reduction in L.
 static PHINode *findInnerReductionPhi(Loop *L, Value *V) {
+  if (isa<Constant>(V))
+    return nullptr;
   for (Value *User : V->users()) {
     if (PHINode *PHI = dyn_cast<PHINode>(User)) {
       if (PHI->getNumIncomingValues() == 1)
         continue;
       RecurrenceDescriptor RD;
       if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
         return PHI;
       return nullptr;
     }
   }
 
   return nullptr;
 }
 
 bool LoopInterchangeLegality::findInductionAndReductions(
     Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) {
   if (!L->getLoopLatch() || !L->getLoopPredecessor())
     return false;

llvm/test/Transforms/LoopInterchange/reductions-across-inner-and-outer-loop.ll

for1.inc:                                ; preds = %for2
   %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
   %exit2 = icmp eq i64 %indvars.iv.next24, 100
   br i1 %exit2, label %for1.loopexit, label %for1.header
 
 for1.loopexit:                                 ; preds = %for1.inc
   %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]
   ret i64 %sum.inc.lcssa2
 }
+
+; Check that we do not interchange or crush if PHI in the outer loop gets
+; a constant from the inner loop
+; REMARKS: --- !Missed
+; REMARKS-NEXT: Pass:            loop-interchange
+; REMARKS-NEXT: Name:            UnsupportedPHIOuter
+; REMARKS-NEXT: Function:        test_constant_inner_loop_res
+
+define i64 @test_constant_inner_loop_res([100 x [100 x i64]]* %Arr) {
+entry:
+  br label %for1.header
+
+for1.header:                                         ; preds = %for1.inc, %entry
+  %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
+  %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.amend, %for1.inc ]
+  br label %for2
+
+for2:                                        ; preds = %for2, %for1.header
+  %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
+  %sum.inner = phi i64 [ %sum.outer, %for1.header ], [ %sum.inc, %for2 ]
+  %arrayidx = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
+  %lv = load i64, i64* %arrayidx, align 4
+  %sum.inc = add i64 %sum.inner, %lv
+  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
+  %exit1 = icmp eq i64 %indvars.iv.next.3, 100
+  br i1 %exit1, label %for1.inc, label %for2
+
+for1.inc:                                ; preds = %for2
+  %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]
+  %const.lcssa = phi i64 [ 0, %for2 ]
+  %sum.inc.amend = add i64 %const.lcssa, %sum.inc.lcssa
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %exit2 = icmp eq i64 %indvars.iv.next24, 100
+  br i1 %exit2, label %for1.loopexit, label %for1.header
+
+for1.loopexit:                                 ; preds = %for1.inc
+  %il.res.lcssa2 = phi i64 [ %sum.inc.amend, %for1.inc ]
+  ret i64 %il.res.lcssa2
+}