[LSR] do not replace PHI nodes if its scev is SCEVUnknown

[shchenz]

Summary

This fixes a bug related to LSR PHI node elimination.

In the touching case, LSR should not eliminate %lsr.iv30, it is not congruent with %lsr.iv99. Their start value are not same.
But for now, Scalar Evolution returns same SCEVUnknown SCEV to them. This should be a bug for scalar evolution.

%scevgep26 = getelementptr [0 x %_elem_type_of_ap], [0 x %_elem_type_of_ap]* %.ap, i64 0, i64 28
%scevgep2627 = bitcast %_elem_type_of_ap* %scevgep26 to [0 x %_elem_type_of_ap]*
%lsr.iv30 = phi [0 x %_elem_type_of_ap]* [ %24, %_scf_2_skip_ ], [ %scevgep2627, %_loop_1_do_.lr.ph ]

%scevgep97 = getelementptr [0 x %_elem_type_of_ap], [0 x %_elem_type_of_ap]* %.ap, i64 0, i64 -1
%scevgep9798 = bitcast %_elem_type_of_ap* %scevgep97 to [0 x %_elem_type_of_ap]*
%lsr.iv99 = phi [0 x %_elem_type_of_ap]* [ %24, %_scf_2_skip_ ], [ %scevgep9798, %_loop_1_do_.lr.ph ]

This patch solves the issue when Scalar Evolution wrongly returns the same SCEVUnknown SCEV object for two Values.

But of course, we should find out the bug inside scalar evolution and fix it there.
Here we make some protection when Scalar Evolution gets some bug and will meet functionality issues.

[fhahn]

I think it would be helpful to describe what goes wrong in the patch description.

[lebedev.ri]

I feel like the patch doesn't actually describe what the problem is, or why giving up on SCEVUnknown resolves (hides?) it.

[samparker]

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2040

From your description of the problem, can we just check the incoming values of the phis too?

[shchenz]

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2040

I think we should not check the incoming value of the phi from loop preheader to decide whether we should eliminate the PHI. SCEV for the phi should be the only factor to do this. Reason why it checks incoming value from loop latch is to eliminate iv.inc in loop latch early. Hope I get a right understanding here. Thanks for your comments Sam

[shchenz]

We decide to fix it in scalar evolution. I will abandon this patch.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

 
 using namespace llvm;
 
 cl::opt<unsigned> llvm::SCEVCheapExpansionBudget(
     "scev-cheap-expansion-budget", cl::Hidden, cl::init(4),
     cl::desc("When performing SCEV expansion only if it is cheap to do, this "
              "controls the budget that is considered cheap (default = 4)"));
 
+cl::opt<bool> EliminateSCEVUnknownPHI(
+    "eliminate-SCEVUnknown-phi", cl::Hidden, cl::init(false),
+    cl::desc("This controls congruent SCEVUnknown PHI node can be replaced."));
+
 using namespace PatternMatch;
 
 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
 /// reusing an existing cast if a suitable one exists, moving an existing
 /// cast if a suitable one exists but isn't in the right place, or
 /// creating a new one.
 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
                                        Instruction::CastOps Op,
if (Value *V = SimplifyPHINode(Phi)) {
       DEBUG_WITH_TYPE(DebugType, dbgs()
                       << "INDVARS: Eliminated constant iv: " << *Phi << '\n');
       continue;
     }
 
     if (!SE.isSCEVable(Phi->getType()))
       continue;
 
-    PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
+    const SCEV* S = SE.getSCEV(Phi);
+    if (!EliminateSCEVUnknownPHI && isa<SCEVUnknown>(S))
+      continue;
+
+    PHINode *&OrigPhiRef = ExprToIVMap[S];
     if (!OrigPhiRef) {
       OrigPhiRef = Phi;
       if (Phi->getType()->isIntegerTy() && TTI &&
           TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
         // This phi can be freely truncated to the narrowest phi type. Map the
         // truncated expression to it so it will be reused for narrow types.
         const SCEV *TruncExpr =
           SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
for (PHINode *Phi : Phis) {
     if (BasicBlock *LatchBlock = L->getLoopLatch()) {
       Instruction *OrigInc = dyn_cast<Instruction>(
           OrigPhiRef->getIncomingValueForBlock(LatchBlock));
       Instruction *IsomorphicInc =
           dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
 
       if (OrigInc && IsomorphicInc) {
         // If this phi has the same width but is more canonical, replace the
         // original with it. As part of the "more canonical" determination,
         // respect a prior decision to use an IV chain.
         if (OrigPhiRef->getType() == Phi->getType() &&
             !(ChainedPhis.count(Phi) ||
               isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) &&
             (ChainedPhis.count(Phi) ||
              isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
           std::swap(OrigPhiRef, Phi);
           std::swap(OrigInc, IsomorphicInc);

llvm/test/Transforms/LoopStrengthReduce/phi-unknownscev.ll

 ; %scevgep26 = getelementptr [0 x %_elem_type_of_ap], [0 x %_elem_type_of_ap]* %.ap, i64 0, i64 28
 ; %scevgep2627 = bitcast %_elem_type_of_ap* %scevgep26 to [0 x %_elem_type_of_ap]*
 ; %lsr.iv30 = phi [0 x %_elem_type_of_ap]* [ %24, %_scf_2_skip_ ], [ %scevgep2627, %_loop_1_do_.lr.ph ]
 ;
 ; %scevgep97 = getelementptr [0 x %_elem_type_of_ap], [0 x %_elem_type_of_ap]* %.ap, i64 0, i64 -1
 ; %scevgep9798 = bitcast %_elem_type_of_ap* %scevgep97 to [0 x %_elem_type_of_ap]*
 ; %lsr.iv99 = phi [0 x %_elem_type_of_ap]* [ %24, %_scf_2_skip_ ], [ %scevgep9798, %_loop_1_do_.lr.ph ]
 
-; CHECK: INDVARS: Eliminated congruent iv:
-; CHECK-NEXT: INDVARS: Original iv:
+; CHECK-NOT: INDVARS: Eliminated congruent iv:
+; CHECK-NOT: INDVARS: Original iv:
 
 define void @foo(i64* noalias %.n, float* noalias %.alpha, [0 x %_elem_type_of_x]* noalias %.x, [0 x %_elem_type_of_y]* noalias %.y, [0 x %_elem_type_of_ap]* noalias %.ap, i64* noalias %.lda) {
 entry:
   %_val_n_ = load i64, i64* %.n, align 8
   %_mod_tmp = srem i64 %_val_n_, 2
   %_add_tmp = add nsw i64 %_mod_tmp, 16
   %_les_tmp = icmp slt i64 %_val_n_, %_add_tmp
   %min = select i1 %_les_tmp, i64 %_val_n_, i64 %_add_tmp