[SLP]Fix non-determinism in PHI sorting.

[ABataev]

Summary

Compare type IDs and DFS numbering for basic block instead of addresses
to fix non-determinism.

[RKSimon]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

8372

Avoid auto

llvm/test/Transforms/SLPVectorizer/X86/remark_unsupported.ll

5

update this comment? SLP isn't vectorizing x86_fp80 but why are you having to change the test?

[ABataev]

Address comments + fix a bug

[ABataev]

llvm/test/Transforms/SLPVectorizer/X86/remark_unsupported.ll

5

Previously root PHI nodes with x86_fp80 type were rejected during graph building, here we started to reject them earlier to avoid some extra work. This leads to the fact that the expected message won't be emitted for this test anymore, so have to rework the test to emit the message again, because we still may see it during graph building, if some instructions return x86_fp80 type

[RKSimon]

LGTM - cheers

[skatkov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

8371

Please note that we met triggering this assert. The reduced by bugpoint reproducer looks as follows:

define void @bar() {
bb:
  %tmp = load atomic i8*, i8** undef unordered, align 8
  br label %bb6

bb5:                                              ; No predecessors!
  %tmp4 = load atomic i8*, i8** undef unordered, align 8
  br label %bb6

bb6:                                              ; preds = %bb5, %bb
  %tmp7 = phi i8* [ %tmp, %bb5 ], [ undef, %bb ]
  %tmp8 = phi i8* [ %tmp4, %bb5 ], [ undef, %bb ]
  ret void
}

It looks like we can reach this code with unreachable instruction and it is not guarded in optimization.

Could you please fix it or revert the patch.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

8371

Will fix it ASAP.

[skatkov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

8371

Thanks in advance.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

while (HaveVectorizedPhiNodes) {
     for (Instruction &I : *BB) {
       PHINode *P = dyn_cast<PHINode>(&I);
       if (!P)
         break;
 
       // No need to analyze deleted, vectorized and non-vectorizable
       // instructions.
       if (!VisitedInstrs.count(P) && !R.isDeleted(P) &&
-          !P->getType()->isVectorTy())
+          isValidElementType(P->getType()))
         Incoming.push_back(P);
     }
 
     // Find the corresponding non-phi nodes for better matching when trying to
     // build the tree.
     for (Value *V : Incoming) {
       SmallVectorImpl<Value *> &Opcodes =
           PHIToOpcodes.try_emplace(V).first->getSecond();
for (Value *V : Incoming) {
             continue;
           }
           Opcodes.emplace_back(V);
         }
       }
     }
 
     // Sort by type, parent, operands.
-    stable_sort(Incoming, [&PHIToOpcodes](Value *V1, Value *V2) {
-      if (V1->getType() < V2->getType())
+    stable_sort(Incoming, [this, &PHIToOpcodes](Value *V1, Value *V2) {
+      assert(isValidElementType(V1->getType()) &&
+             isValidElementType(V2->getType()) &&
+             "Expected vectorizable types only.");
+      // It is fine to compare type IDs here, since we expect only vectorizable
+      // types, like ints, floats and pointers, we don't care about other type.
+      if (V1->getType()->getTypeID() < V2->getType()->getTypeID())
         return true;
-      if (V1->getType() > V2->getType())
+      if (V1->getType()->getTypeID() > V2->getType()->getTypeID())
         return false;
       ArrayRef<Value *> Opcodes1 = PHIToOpcodes[V1];
       ArrayRef<Value *> Opcodes2 = PHIToOpcodes[V2];
       if (Opcodes1.size() < Opcodes2.size())
         return true;
       if (Opcodes1.size() > Opcodes2.size())
         return false;
       for (int I = 0, E = Opcodes1.size(); I < E; ++I) {
         // Undefs are compatible with any other value.
         if (isa<UndefValue>(Opcodes1[I]) || isa<UndefValue>(Opcodes2[I]))
           continue;
         if (auto *I1 = dyn_cast<Instruction>(Opcodes1[I]))
           if (auto *I2 = dyn_cast<Instruction>(Opcodes2[I])) {
-            if (I1->getParent() < I2->getParent())
-              return true;
-            if (I1->getParent() > I2->getParent())
-              return false;
+            DomTreeNodeBase<BasicBlock> *NodeI1 = DT->getNode(I1->getParent());
+            DomTreeNodeBase<BasicBlock> *NodeI2 = DT->getNode(I2->getParent());
+            assert(NodeI1 && "Should only process reachable instructions");
+            assert(NodeI2 && "Should only process reachable instructions");
+            assert((NodeI1 == NodeI2) ==
+                       (NodeI1->getDFSNumIn() == NodeI2->getDFSNumIn()) &&
+                   "Different nodes should have different DFS numbers");
+            if (NodeI1 != NodeI2)
+              return NodeI1->getDFSNumIn() < NodeI2->getDFSNumIn();
             InstructionsState S = getSameOpcode({I1, I2});
             if (S.getOpcode())
               continue;
             return I1->getOpcode() < I2->getOpcode();
           }
         if (isa<Constant>(Opcodes1[I]) && isa<Constant>(Opcodes2[I]))
           continue;
         if (Opcodes1[I]->getValueID() < Opcodes2[I]->getValueID())

llvm/test/Transforms/SLPVectorizer/X86/remark_unsupported.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -mtriple=x86_64-pc-linux-gnu -mcpu=generic -slp-vectorizer --slp-max-reg-size=256 -pass-remarks-output=%t < %s | FileCheck %s
 ; RUN: FileCheck --input-file=%t --check-prefix=YAML %s
 
 ; This type is not supported by SLP
-define void @test(x86_fp80* %i1, x86_fp80* %i2, x86_fp80* %o) {
+define i1 @test(x86_fp80* %i1, x86_fp80* %i2) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[I1_0:%.*]] = load x86_fp80, x86_fp80* [[I1:%.*]], align 16
 ; CHECK-NEXT:    [[I1_GEP1:%.*]] = getelementptr x86_fp80, x86_fp80* [[I1]], i64 1
 ; CHECK-NEXT:    [[I1_1:%.*]] = load x86_fp80, x86_fp80* [[I1_GEP1]], align 16
 ; CHECK-NEXT:    br i1 undef, label [[THEN:%.*]], label [[END:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[I2_GEP0:%.*]] = getelementptr inbounds x86_fp80, x86_fp80* [[I2:%.*]], i64 0
 ; CHECK-NEXT:    [[I2_0:%.*]] = load x86_fp80, x86_fp80* [[I2_GEP0]], align 16
 ; CHECK-NEXT:    [[I2_GEP1:%.*]] = getelementptr inbounds x86_fp80, x86_fp80* [[I2]], i64 1
 ; CHECK-NEXT:    [[I2_1:%.*]] = load x86_fp80, x86_fp80* [[I2_GEP1]], align 16
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[PHI0:%.*]] = phi x86_fp80 [ [[I1_0]], [[ENTRY:%.*]] ], [ [[I2_0]], [[THEN]] ]
 ; CHECK-NEXT:    [[PHI1:%.*]] = phi x86_fp80 [ [[I1_1]], [[ENTRY]] ], [ [[I2_1]], [[THEN]] ]
-; CHECK-NEXT:    store x86_fp80 [[PHI0]], x86_fp80* [[O:%.*]], align 16
-; CHECK-NEXT:    [[O_GEP1:%.*]] = getelementptr inbounds x86_fp80, x86_fp80* [[O]], i64 1
-; CHECK-NEXT:    store x86_fp80 [[PHI1]], x86_fp80* [[O_GEP1]], align 16
-; CHECK-NEXT:    ret void
+; CHECK-NEXT:    [[RES:%.*]] = fcmp oeq x86_fp80 [[PHI0]], [[PHI1]]
+; CHECK-NEXT:    ret i1 [[RES]]
 ;
 entry:
   %i1.0 = load x86_fp80, x86_fp80* %i1, align 16
   %i1.gep1 = getelementptr x86_fp80, x86_fp80* %i1, i64 1
   %i1.1 = load x86_fp80, x86_fp80* %i1.gep1, align 16
   br i1 undef, label %then, label %end
 then:
   %i2.gep0 = getelementptr inbounds x86_fp80, x86_fp80* %i2, i64 0
   %i2.0 = load x86_fp80, x86_fp80* %i2.gep0, align 16
   %i2.gep1 = getelementptr inbounds x86_fp80, x86_fp80* %i2, i64 1
   %i2.1 = load x86_fp80, x86_fp80* %i2.gep1, align 16
   br label %end
 end:
   %phi0 = phi x86_fp80 [ %i1.0, %entry ], [ %i2.0, %then ]
-
   %phi1 = phi x86_fp80 [ %i1.1, %entry ], [ %i2.1, %then ]
-  store x86_fp80 %phi0, x86_fp80* %o, align 16
-  %o.gep1 = getelementptr inbounds x86_fp80, x86_fp80* %o, i64 1
-  store x86_fp80 %phi1, x86_fp80* %o.gep1, align 16
+  %res = fcmp oeq x86_fp80 %phi0, %phi1
   ; YAML:      Pass:            slp-vectorizer
   ; YAML-NEXT: Name:            UnsupportedType
   ; YAML-NEXT: Function:        test
   ; YAML-NEXT: Args:
   ; YAML-NEXT:   - String:          'Cannot SLP vectorize list: type '
   ; YAML-NEXT:   - String:          x86_fp80 is unsupported by vectorizer
 
-  ret void
+  ret i1 %res
 }