[VectorUtils] Don't try and truncate PHIs to a smaller bitwidth

[jmolloy]

Summary

We already try not to truncate PHIs in computeMinimalBitwidths. LoopVectorize can't handle it and we really don't need to, because both induction and reduction PHIs are truncated by other means.

However, we weren't bailing out in all the places we should have, and we ended up by returning a PHI to be truncated, which has caused PR27018.

This fixes PR17018.

[sbaranga]

lib/Analysis/VectorUtils.cpp

557

Hi James,

Why would this be a problem for the loop vectorizer (we should state this here)? Also, won't indvars generally extend the phi?

Cheers,
Silviu

[jmolloy]

Hi Silviu,

Primarily because the LV just doesn’t support PHIs and teaching it would be quite some work. We already have a comment above saying we don’t support PHIs; we just weren’t catching all of them at that point!

Indvars is one of the reasons we don’t support PHI truncation - it’s a minefield. Induction variables often hold pointer values, and calculating the exact situations where these can be truncated successfully was rather tricky when I originally wrote this code.

I could probably put effort into supporting PHIs, but it’s most important to fix this crasher at least in the meantime.

James

[sbaranga]

In D18445#382505, @jmolloy wrote:

I could probably put effort into supporting PHIs, but it’s most important to fix this crasher at least in the meantime.

I don't think there's any need for this, I was just trying to better understand what was going on.

LGTM!

lib/Analysis/VectorUtils.cpp

while (!Worklist.empty()) {
 
     // If we encounter a type that is larger than 64 bits, we can't represent
     // it so bail out.
     if (DB.getDemandedBits(I).getBitWidth() > 64)
       return MapVector<Instruction *, uint64_t>();
 
     uint64_t V = DB.getDemandedBits(I).getZExtValue();
     DBits[Leader] |= V;
+    DBits[I] = V;
 
     // Casts, loads and instructions outside of our range terminate a chain
     // successfully.
     if (isa<SExtInst>(I) || isa<ZExtInst>(I) || isa<LoadInst>(I) ||
         !InstructionSet.count(I))
       continue;
 
     // Unsafe casts terminate a chain unsuccessfully. We can't do anything
for (auto I = ECs.begin(), E = ECs.end(); I != E; ++I) {
     for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI)
       LeaderDemandedBits |= DBits[*MI];
 
     uint64_t MinBW = (sizeof(LeaderDemandedBits) * 8) -
                      llvm::countLeadingZeros(LeaderDemandedBits);
     // Round up to a power of 2
     if (!isPowerOf2_64((uint64_t)MinBW))
       MinBW = NextPowerOf2(MinBW);
+
+    // We don't modify the types of PHIs. Reductions will already have been
+    // truncated if possible, and inductions' sizes will have been chosen by
+    // indvars.
+    // If we are required to shrink a PHI, abandon this entire equivalence class.
+    bool Abort = false;
+    for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI)
+      if (isa<PHINode>(*MI) && MinBW < (*MI)->getType()->getScalarSizeInBits()) {
+        Abort = true;
+        break;
+      }
+    if (Abort)
+      continue;
+
     for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI) {
       if (!isa<Instruction>(*MI))
         continue;
       Type *Ty = (*MI)->getType();
       if (Roots.count(*MI))
         Ty = cast<Instruction>(*MI)->getOperand(0)->getType();
       if (MinBW < Ty->getScalarSizeInBits())
         MinBWs[cast<Instruction>(*MI)] = MinBW;
     }
   }
 
   return MinBWs;
 }

test/Transforms/LoopVectorize/AArch64/loop-vectorization-factors.ll

for.body:                                         ; preds = %for.body, %for.body.lr.ph
   %arrayidx21 = getelementptr inbounds i8, i8* %q, i64 %indvars.iv
   store i8 %conv19, i8* %arrayidx21
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, %len
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
+; CHECK-LABEL: @add_phifail(
+; CHECK: load <16 x i8>, <16 x i8>*
+; CHECK: add nuw nsw <16 x i32>
+; CHECK: store <16 x i8>
+; Function Attrs: nounwind
+define void @add_phifail(i8* noalias nocapture readonly %p, i8* noalias nocapture %q, i32 %len) #0 {
+entry:
+  %cmp8 = icmp sgt i32 %len, 0
+  br i1 %cmp8, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
+  %a_phi = phi i32 [ %conv, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i8, i8* %p, i64 %indvars.iv
+  %0 = load i8, i8* %arrayidx
+  %conv = zext i8 %0 to i32
+  %add = add nuw nsw i32 %conv, 2
+  %conv1 = trunc i32 %add to i8
+  %arrayidx3 = getelementptr inbounds i8, i8* %q, i64 %indvars.iv
+  store i8 %conv1, i8* %arrayidx3
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %len
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: @add_phifail2(
+; CHECK: load <16 x i8>, <16 x i8>*
+; CHECK: add nuw nsw <16 x i32>
+; CHECK: store <16 x i8>
+; Function Attrs: nounwind
+define i8 @add_phifail2(i8* noalias nocapture readonly %p, i8* noalias nocapture %q, i32 %len) #0 {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  %ret = trunc i32 %a_phi to i8
+  ret i8 %ret
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
+  %a_phi = phi i32 [ %conv, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i8, i8* %p, i64 %indvars.iv
+  %0 = load i8, i8* %arrayidx
+  %conv = zext i8 %0 to i32
+  %add = add nuw nsw i32 %conv, 2
+  %conv1 = trunc i32 %add to i8
+  %arrayidx3 = getelementptr inbounds i8, i8* %q, i64 %indvars.iv
+  store i8 %conv1, i8* %arrayidx3
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %len
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
 
 attributes #0 = { nounwind }
+