[Scalarizer] Remove unreachable blocks before scalarizing a function

[bjope]

Summary

When scalarizing PHI nodes we might try to examine/rewrite
InsertElement nodes in predecessors. If those predecessors
are unreachable from entry, then the IR in those blocks could
have unexpected properties resulting in infinite loops in
Scatterer::operator[]. So we better remove unreachable blocks
before scalarizing the function.

[bjope]

I've got another solution for this problem for our out-of-tree-target. So I'll abandon this.

lib/Transforms/Scalar/Scalarizer.cpp

 // It is mainly intended for targets that do not have vector units, but it
 // may also be useful for revectorizing code to different vector widths.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/VectorUtils.h"
+#include "llvm/Analysis/Utils/Local.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstVisitor.h"

 
 private:
   Scatterer scatter(Instruction *Point, Value *V);
   void gather(Instruction *Op, const ValueVector &CV);
   bool canTransferMetadata(unsigned Kind);
   void transferMetadata(Instruction *Op, const ValueVector &CV);
   bool getVectorLayout(Type *Ty, unsigned Alignment, VectorLayout &Layout,
                        const DataLayout &DL);
-  bool finish();
+  bool finish(bool Modified);
 
   template<typename T> bool splitBinary(Instruction &, const T &);
 
   bool splitCall(CallInst &CI);
 
   ScatterMap Scattered;
   GatherList Gathered;
   unsigned ParallelLoopAccessMDKind;
bool Scalarizer::doInitialization(Module &M) {
   ParallelLoopAccessMDKind =
       M.getContext().getMDKindID("llvm.mem.parallel_loop_access");
   ScalarizeLoadStore =
       M.getContext().getOption<bool, Scalarizer, &Scalarizer::ScalarizeLoadStore>();
   return false;
 }
 
 bool Scalarizer::runOnFunction(Function &F) {
+  bool Modified = false;
   if (skipFunction(F))
     return false;
+
+  // When scalarizing PHI nodes we might try to examine/rewrite InsertElement
+  // nodes in predecessors. If those predecessors are unreachable from entry,
+  // then the IR in those blocks could have unexpected properties resulting in
+  // infinite loops in Scatterer::operator[]. So we better remove unreachable
+  // blocks before scalarizing the function.
+  Modified |= removeUnreachableBlocks(F, nullptr, nullptr, false);
+
   assert(Gathered.empty() && Scattered.empty());
   for (BasicBlock &BB : F) {
     for (BasicBlock::iterator II = BB.begin(), IE = BB.end(); II != IE;) {
       Instruction *I = &*II;
       bool Done = visit(I);
       ++II;
       if (Done && I->getType()->isVoidTy())
         I->eraseFromParent();
     }
   }
-  return finish();
+  return finish(Modified);
 }
 
 // Return a scattered form of V that can be accessed by Point.  V must be a
 // vector or a pointer to a vector.
 Scatterer Scalarizer::scatter(Instruction *Point, Value *V) {
   if (Argument *VArg = dyn_cast<Argument>(V)) {
     // Put the scattered form of arguments in the entry block,
     // so that it can be used everywhere.

 }
 
 bool Scalarizer::visitCallInst(CallInst &CI) {
   return splitCall(CI);
 }
 
 // Delete the instructions that we scalarized.  If a full vector result
 // is still needed, recreate it using InsertElements.
-bool Scalarizer::finish() {
+bool Scalarizer::finish(bool Modified) {
   // The presence of data in Gathered or Scattered indicates changes
   // made to the Function.
   if (Gathered.empty() && Scattered.empty())
-    return false;
+    return Modified;
   for (const auto &GMI : Gathered) {
     Instruction *Op = GMI.first;
     ValueVector &CV = *GMI.second;
     if (!Op->use_empty()) {
       // The value is still needed, so recreate it using a series of
       // InsertElements.
       Type *Ty = Op->getType();
       Value *Res = UndefValue::get(Ty);

test/Transforms/Scalarizer/phi_unreachable_pred.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -scalarizer -S -o - | FileCheck %s
+
+@e = dso_local global i16 0, align 1
+
+define i16 @f1() {
+; CHECK-LABEL: @f1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_END10:%.*]]
+; CHECK:       for.end10:
+; CHECK-NEXT:    [[G_SROA_0_0_VEC_EXTRACT:%.*]] = extractelement <4 x i16> <i16 1, i16 1, i16 1, i16 1>, i32 0
+; CHECK-NEXT:    ret i16 [[G_SROA_0_0_VEC_EXTRACT]]
+;
+entry:
+  br label %for.end10
+
+for.cond3:
+  %inc = add nsw i16 %inc, 1
+  %tobool4 = icmp ne i16 %inc, 0
+  br i1 %tobool4, label %for.body5, label %for.end
+
+for.body5:
+  %g.sroa.0.0.vec.insert = insertelement <4 x i16> %g.sroa.0.0.vec.insert, i16 55, i32 0
+  %0 = load i16, i16* @e, align 1
+  %tobool7 = icmp ne i16 %0, 0
+  br i1 %tobool7, label %if.then8, label %for.cond3
+
+if.then8:
+  br label %for.cond3
+
+for.end:
+  br label %for.end10
+
+for.end10:
+  ; opt used to hang when scalarizing this code.  When scattering
+  ; %g.sroa.0.0.vec.insert we need to analyze the insertelement in the dead
+  ; block for.body5. But that insertelement instruction depends on itself, so
+  ; it is weird. Eliminating unreachable code before scalarizing solves the
+  ; problem.
+  %g.sroa.0.0 = phi <4 x i16> [ <i16 1, i16 1, i16 1, i16 1>, %entry ], [ %g.sroa.0.0.vec.insert, %for.end ]
+  %h.0 = phi i16 [ undef, %entry ], [ %inc, %for.end ]
+  %g.sroa.0.0.vec.extract = extractelement <4 x i16> %g.sroa.0.0, i32 0
+  ret i16 %g.sroa.0.0.vec.extract
+}