Fix SROA with a PHI mergig values from a same block

[rampitec]

Summary

This fixes the bug 47945. It is legal to have a PHI with values
from from the same block, but values must stay the same. In this
case it is illegal to merge different values.

[efriedma]

llvm/lib/Transforms/Scalar/SROA.cpp

3527

I don't think that's what you want to check. In particular, it doesn't handle the case where a block has multiple predecessors containing a construct like br i1 undef, label %cond.end.i, label %cond.end.i (or more commonly, a switch).

[rampitec]

llvm/lib/Transforms/Scalar/SROA.cpp

3527

Do you mean it is legal to have several incoming values from a same block and then some from another?

[efriedma]

llvm/lib/Transforms/Scalar/SROA.cpp

3527

Yes. For example, https://godbolt.org/z/6b86Ts .

[rampitec]

Changed check to only allow unique blocks.

[uabelho]

I don't know what the best fix is, but I've verified that this patch solves the problem I saw and I haven't seen anything weird pop up with the patch in some limited testing I've done with it.
Thanks!

[lebedev.ri]

llvm/lib/Transforms/Scalar/SROA.cpp

3534–3536

Am i correctly reading that this is preventing the fold if PHI has the same incoming BB more than once?

3541–3561

Can't you instead simply cache GEP's, i.e. have a map<basicblock, NewVal>,
and perform this GEP creation only if there is no previous gep for that incoming bb in the map?

[rampitec]

llvm/lib/Transforms/Scalar/SROA.cpp

3534–3536

Right.

3541–3561

I thought about it. but it seems to miss the target. It will not help SROA to eliminate an alloca as far as I understand, so there seems to be no reason to do it.

[lebedev.ri]

llvm/lib/Transforms/Scalar/SROA.cpp

3541–3561

I'm not sure why it would matter to SROA, that sounds like an unrelated bug that should be fixed..
I think it would be more future-proof fix.

[rampitec]

Reuse a value for the same block instead of bailing.

llvm/lib/Transforms/Scalar/SROA.cpp

3541–3561

Looks like it actually works as expected.

[lebedev.ri]

LGTM, thank you!

[efriedma]

llvm/lib/Transforms/Scalar/SROA.cpp

3550

getBasicBlockIndex is linear in the number of operands, so this is overall O(N^2) in the number of PHI operands. Unlikely to matter in most cases, but maybe we should bail out if there are too many operands.

[rampitec]

llvm/lib/Transforms/Scalar/SROA.cpp

3550

I think we can if we ever see such a PHI. Then alloca will remain, so overall it may be slower to work on a non-optimized code.

llvm/lib/Transforms/Scalar/SROA.cpp

private:
   }
 
   // Fold gep (phi ptr1, ptr2) => phi gep(ptr1), gep(ptr2)
   bool foldGEPPhi(GetElementPtrInst &GEPI) {
     if (!GEPI.hasAllConstantIndices())
       return false;
 
     PHINode *PHI = cast<PHINode>(GEPI.getPointerOperand());
     if (GEPI.getParent() != PHI->getParent() ||
         llvm::any_of(PHI->incoming_values(), [](Value *In)
           { Instruction *I = dyn_cast<Instruction>(In);
             return !I || isa<GetElementPtrInst>(I) || isa<PHINode>(I) ||
                    succ_empty(I->getParent()) ||
                    !I->getParent()->isLegalToHoistInto();
           }))
       return false;
 
     LLVM_DEBUG(dbgs() << "  Rewriting gep(phi) -> phi(gep):"
                       << "\n    original: " << *PHI
                       << "\n              " << GEPI
                       << "\n          to: ");
 
     SmallVector<Value *, 4> Index(GEPI.idx_begin(), GEPI.idx_end());
     bool IsInBounds = GEPI.isInBounds();
     IRBuilderTy PHIBuilder(GEPI.getParent()->getFirstNonPHI());
     PHINode *NewPN = PHIBuilder.CreatePHI(GEPI.getType(),
                                           PHI->getNumIncomingValues(),
                                           PHI->getName() + ".sroa.phi");
     for (unsigned I = 0, E = PHI->getNumIncomingValues(); I != E; ++I) {
+      BasicBlock *B = PHI->getIncomingBlock(I);
+      Value *NewVal = nullptr;
+      int Idx = NewPN->getBasicBlockIndex(B);
+      if (Idx >= 0) {
+        NewVal = NewPN->getIncomingValue(Idx);
+      } else {
         Instruction *In = cast<Instruction>(PHI->getIncomingValue(I));
 
         IRBuilderTy B(In->getParent(), std::next(In->getIterator()));
-      Value *NewVal = IsInBounds
+        NewVal = IsInBounds
             ? B.CreateInBoundsGEP(In, Index, In->getName() + ".sroa.gep")
             : B.CreateGEP(In, Index, In->getName() + ".sroa.gep");
-      NewPN->addIncoming(NewVal, PHI->getIncomingBlock(I));
+      }
+      NewPN->addIncoming(NewVal, B);
     }
 
     Visited.erase(&GEPI);
     GEPI.replaceAllUsesWith(NewPN);
     GEPI.eraseFromParent();
     Visited.insert(NewPN);
     enqueueUsers(*NewPN);
 

llvm/test/Transforms/SROA/phi-gep.ll

 
 exit:
   br label %bb2
 
 bb2:
   ret void
 }
 
+define void @constant_value_phi() {
+; CHECK-LABEL: @constant_value_phi(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LAND_LHS_TRUE_I:%.*]]
+; CHECK:       land.lhs.true.i:
+; CHECK-NEXT:    br i1 undef, label [[COND_END_I:%.*]], label [[COND_END_I]]
+; CHECK:       cond.end.i:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  %s1 = alloca [3 x i16]
+  %s = alloca [3 x i16]
+  %cast = bitcast [3 x i16]* %s1 to i16*
+  br label %land.lhs.true.i
+
+land.lhs.true.i:                                  ; preds = %entry
+  br i1 undef, label %cond.end.i, label %cond.end.i
+
+cond.end.i:                                       ; preds = %land.lhs.true.i, %land.lhs.true.i
+  %.pre-phi1 = phi i16* [ %cast, %land.lhs.true.i ], [ %cast, %land.lhs.true.i ]
+  %cast2 = bitcast [3 x i16]* %s to i16*
+  call void @llvm.memcpy.p0i16.p0i16.i64(i16* %.pre-phi1, i16* %cast2, i64 3, i1 false)
+  %gep = getelementptr inbounds [3 x i16], [3 x i16]* %s, i32 0, i32 0
+  %load = load i16, i16* %gep
+  unreachable
+}
+
+define i32 @test_sroa_phi_gep_multiple_values_from_same_block(i32 %arg) {
+; CHECK-LABEL: @test_sroa_phi_gep_multiple_values_from_same_block(
+; CHECK-NEXT:  bb.1:
+; CHECK-NEXT:    switch i32 [[ARG:%.*]], label [[BB_3:%.*]] [
+; CHECK-NEXT:    i32 1, label [[BB_2:%.*]]
+; CHECK-NEXT:    i32 2, label [[BB_2]]
+; CHECK-NEXT:    i32 3, label [[BB_4:%.*]]
+; CHECK-NEXT:    i32 4, label [[BB_4]]
+; CHECK-NEXT:    ]
+; CHECK:       bb.2:
+; CHECK-NEXT:    br label [[BB_4]]
+; CHECK:       bb.3:
+; CHECK-NEXT:    br label [[BB_4]]
+; CHECK:       bb.4:
+; CHECK-NEXT:    [[PHI_SROA_PHI_SROA_SPECULATED:%.*]] = phi i32 [ undef, [[BB_3]] ], [ undef, [[BB_2]] ], [ undef, [[BB_1:%.*]] ], [ undef, [[BB_1]] ]
+; CHECK-NEXT:    ret i32 [[PHI_SROA_PHI_SROA_SPECULATED]]
+;
+bb.1:
+  %a = alloca %pair, align 4
+  %b = alloca %pair, align 4
+  switch i32 %arg, label %bb.3 [
+  i32 1, label %bb.2
+  i32 2, label %bb.2
+  i32 3, label %bb.4
+  i32 4, label %bb.4
+  ]
+
+bb.2:                                                ; preds = %bb.1, %bb.1
+  br label %bb.4
+
+bb.3:                                                ; preds = %bb.1
+  br label %bb.4
+
+bb.4:                                                ; preds = %bb.1, %bb.1, %bb.3, %bb.2
+  %phi = phi %pair* [ %a, %bb.3 ], [ %a, %bb.2 ], [ %b, %bb.1 ], [ %b, %bb.1 ]
+  %gep = getelementptr inbounds %pair, %pair* %phi, i32 0, i32 1
+  %load = load i32, i32* %gep, align 4
+  ret i32 %load
+}
+
 declare %pair* @foo()
 
 declare i32 @__gxx_personality_v0(...)
+
+declare void @llvm.memcpy.p0i16.p0i16.i64(i16* noalias nocapture writeonly, i16* noalias nocapture readonly, i64, i1 immarg)