[SROA] Fold a PHI node if all its incoming values are the same

[jingyue]

Summary

Fixes PR20425.

During slice building, if all of the incoming values of a PHI node are the same, replace the PHI node with the common value. This simplification makes alloca's used by PHI nodes easier to promote.

[eliben]

lib/Transforms/Scalar/SROA.cpp

3101

by "of the PHI nodes" do you mean "PN"?

3102

Please document all the arguments of this function

3140

Does the logic have to be inverted? If you only use this method in a "!" clause, can't it check positively - i.e. origination from only NewAI? This can make reasoning about it simpler.

3143

whitespace around ":"

[meheff]

Just a couple suggestions which might simplify the code.

lib/Transforms/Scalar/SROA.cpp

3106

Couple bike-shed suggestions:

Maybe name the function PHINodeEquivalentToSource?

You could also replace both ptr sets with a map<PHINode *, bool> where membership indicates it's been visited and the value indicates equivalence.

3141

If you use a map<PHINode *, bool> for equivalence as mentioned above, you can cleanly do away with ToDelete. Just iterate through the map and replace the nodes with a true value. I, think, necessarily those will all be in PHIUsers.

[jingyue]

Thanks Eli and Mark for your comments! I believe the logic is simpler now.

[jingyue]

lib/Transforms/Scalar/SROA.cpp

3101

Changed the comment to "incoming values of PN".

3102

done

3106

Merged these data structures to one DenseMap, and renamed the function to PHINodeEquivalentToNewAlloca.

3140

done

3141

Agreed. Done.

3143

Ack'ed.

[chandlerc]

lib/Transforms/Scalar/SROA.cpp

3097–3102

I think this is the wrong approach in several ways.

Depth first search when there is an early exit shortcut is usually more expensive than testing the predicate breadth first while adding the nodes to a worklist. Also you should use a worklist rather than recursion or you would easily blow out the stack. Finally, I agree that we shouldn't need a set for originating from other and just a visit....

But before we dive into the details to fix these issues -- why is this the right approach? Walking *up* from the PHI operands seems necessarily much more work than walking *down* from the alloca. In fact, we're already going to walk down from the alloca because we iterate on every non-promoted alloca. Why can't we fold no-op PHI nodes in the partition builder the same way we do no-op selects? I think that would solve the problem you have here with no extra use-list traversal.

For future reference, keep in mind that uselist traversal is a cache-hostile thing. We should minimize the number of traversals and merge traversals where possible.

3102

Wo don't actually insist on that usually. I'd rather the arguments have descriptive names than comments personally.

[jingyue]

Chandler, thanks for your suggestions! I think moving the logic to SliceBuilder makes perfect sense.

After modifying SliceBuilder::visitPHINode, I found it almost the same as visitSelectInst. Therefore, I also refactored the code to merge visitPHINode and visitSelectInst to one function. Let me know if it looks good to you.

[chandlerc]

Yea, this looks nice. I have a bunch of nit-picky comments below... Nothing really significant.

lib/Transforms/Scalar/SROA.cpp

332

Just use nullptr as the initial value?

333

I prefer to only use "I" (capitalized) for iterators. I'd use 'i' or 'Idx' here.

(and we should really add an iterator and range adaptor set to PHINode for these so you can use a range based for loop...)

336–344

I think this would be slightly simpler as:

if (isa<UndefValue>(IV))
  continue;

if (!CommanValue)
  CommonValue = IV;
else if (CommonValue != IV)
  return nullptr;

671–679

I'd probably put this in a 'foldPHINodeORSelectInst' static helper so you can write the if below:

if (Value *Result = foldPHINodeOrSelectInst(I)) {

699

How about just "Size"?

test/Transforms/SROA/phi-and-select.ll

567–568

I like to have all my CHECKs within the function body so I can find them and they don't get spliced. I also try to attach them to the instruction they reference. Can you put the label at the start of the function and then the -NOT after the alloca?

[jingyue]

All comments addressed

[jingyue]

lib/Transforms/Scalar/SROA.cpp

332

That would make foldPHINode return null for phi(undef, undef).

333

Done.

I agree. Will add a range for PHINode in a separate patch.

336–344

Done

671–679

done

699

done.

test/Transforms/SROA/phi-and-select.ll

567–568

done

[jingyue]

Hi Duncan,

I tried SimplifyPHINode and it worked pretty well. Thanks!

That makes me consider using SimplifySelectInst on select instructions too. However, I found one regression test PR16651.2 would fail after this potential modification. We would transform

define void @PR16651.2() {
; This test case caused a crash due to failing to promote given a select that
; can't be speculated. It shouldn't be promoted, but we missed that fact when
; analyzing whether we could form a vector promotion because that code didn't
; bail on select instructions.
;
; CHECK-LABEL: @PR16651.2(
; CHECK: alloca <2 x float>
; CHECK: ret void

entry:
  %tv1 = alloca { <2 x float>, <2 x float> }, align 8
  %0 = getelementptr { <2 x float>, <2 x float> }* %tv1, i64 0, i32 1
  store <2 x float> undef, <2 x float>* %0, align 8
  %1 = getelementptr inbounds { <2 x float>, <2 x float> }* %tv1, i64 0, i32 1, i64 0
  %cond105.in.i.i = select i1 undef, float* null, float* %1
  %cond105.i.i = load float* %cond105.in.i.i, align 8
  ret void
}

to

define void @PR16651.2() {
entry:
  %cond105.in.i.i = select i1 undef, float* null, float* undef
  %cond105.i.i = load float* %cond105.in.i.i, align 8
  ret void
}

Is this transformation on PR16651.2 valid? If no, can somebody help me understand why it isn't?

Thanks,
Jingyue

[hfinkel]

• Original Message -----

From: "Jingyue Wu" <[e-mail]>
To: [e-mail], [e-mail], [e-mail], [e-mail], [e-mail]
Cc: [e-mail]
Sent: Sunday, July 27, 2014 11:21:24 AM
Subject: Re: [PATCH] [SROA] Fold a PHI node if all its incoming values are the same

Hi Duncan,

I tried SimplifyPHINode and it worked pretty well. Thanks!

That makes me consider using SimplifySelectInst on select
instructions too. However, I found one regression test PR16651.2
would fail after this potential modification. We would transform

define void @PR16651.2() {
; This test case caused a crash due to failing to promote given a
select that
; can't be speculated. It shouldn't be promoted, but we missed that
fact when
; analyzing whether we could form a vector promotion because that
code didn't
; bail on select instructions.
;
; CHECK-LABEL: @PR16651.2(
; CHECK: alloca <2 x float>
; CHECK: ret void

entry:
  %tv1 = alloca { <2 x float>, <2 x float> }, align 8
  %0 = getelementptr { <2 x float>, <2 x float> }* %tv1, i64 0, i32 1
  store <2 x float> undef, <2 x float>* %0, align 8
  %1 = getelementptr inbounds { <2 x float>, <2 x float> }* %tv1, i64
  0, i32 1, i64 0
  %cond105.in.i.i = select i1 undef, float* null, float* %1
  %cond105.i.i = load float* %cond105.in.i.i, align 8
  ret void
}

to

define void @PR16651.2() {
entry:
  %cond105.in.i.i = select i1 undef, float* null, float* undef
  %cond105.i.i = load float* %cond105.in.i.i, align 8
  ret void
}

Is this transformation on PR16651.2 valid?

It looks like this transformation is valid only if loading from an undef address always produces an undef value (and never traps). In the original code, loading from %1 always produced an undef value (because undef was explicitly stored into that location, but would have been undef anyway because it is an otherwise-fresh alloca), but did not trap. So if we always replaced undef addresses with some equivalently-sized constant-pool load (or something like that), then this might work. I don't know that we do that, however.

-Hal

If no, can somebody help
me understand why it isn't?

Thanks,
Jingyue

http://reviews.llvm.org/D4659

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[jingyue]

To avoid redundancy, use SimplifyInstruction to fold PHI nodes and select instructions. One tricky case is when clobbering one operand in

select undef, a, b

we need to have the select always return the other operand by setting the condition "undef" to 0 or 1; otherwise, the transformation of clobbering dead operands may introduce new undefined behavior. Added test @simplify_undef in phi-and-select.ll to cover this case.

Updated basictest.ll per this change.

[jingyue]

Can anyone take a look at the latest diff?

In the latest diff, I use SimplifyInstruction to fold both PHI nodes and select instructions. Doing so requires a minor fix in the logic of clobbering dead uses in select instructions: to clobber x/y in "select undef, x, y", we should change the condition from "undef" to 0/1. Otherwise, "select undef, undef, y" or "select undef, x, undef" can introduce more undefined behavior. This wasn't an issue in the old code, because the old code does not fold a select with undef condition.

[jingyue]

ping?

[chandlerc]

Sorry, I've been chasing other bugs. Will look today.

[jingyue]

Hi Chandler,

I hope your bug chasing is going well. Wondering if you can get a chance to take a look at this patch.

Thanks a lot,
Jingyue

[jingyue]

ping?

[chandlerc]

Sorry. I tried to get back to this a couple of times but it required a lot of thought. And then your pings kept hitting me at bad times. =/

lib/Transforms/Scalar/SROA.cpp

689–708

This is pretty horrible. It makes me question the entire approach of cleaning up instructions here.

I hate phase ordering.

If we're going to go down the rabbit hole here if using instsimplify within SROA to address phase ordering issues, I think it would be much cleaner to do as part of the recursive user walk for the pointer value, and to actually RAUW the values as they simplify rather than doing the dead-operand-tracking thing here. Consider -- if we don't RAUW then we won't notice if doing so would cause some user of the select (perhaps another select or PHI) to collapse to all inputs being the same.

But that requires parameterizing PtrUseVisitor, teaching it to use instsimplify, teaching it to track RAUWs correctly, etc etc etc. Yuck. Absolutely terrible. This is why phase ordering problems are hard.

Ultimately, I think the suggestion to use instsimplify is wrong here. We really only want to handle the simplifications that arise *because* of mem2reg, and the primary one there is when all inputs to the PHI node become the same because we promoted them all to the same register (rather than N different loads). We don't need or want to handle the more complex simplifications because other passes will.

If we want to make SROA really powerful against phase ordering issues like this, I think it would need serious architectural changes.

So can we go back to the simpler patch after my round of nit-picky comments? Because I suspect that one is essentially "ready to go".

[jingyue]

Thanks for the review, Chandler.

I see what you are saying. I agree the current dead-operand-trackign mechanism is a little cumbersome for the use of SimplifyInstruction.

I reverted the use of SimplifyInstruction and left the architectural changes as TODO. PTAL.

[chandlerc]

Looks great, thanks!

lib/Transforms/Scalar/SROA.cpp

static Value *foldSelectInst(SelectInst &SI) {
   return nullptr;
 }
 
 /// \brief Builder for the alloca slices.
 ///
 /// This class builds a set of alloca slices by recursively visiting the uses
 /// of an alloca and making a slice for each load and store at each offset.
 class AllocaSlices::SliceBuilder : public PtrUseVisitor<SliceBuilder> {
   friend class PtrUseVisitor<SliceBuilder>;
   friend class InstVisitor<SliceBuilder>;
   typedef PtrUseVisitor<SliceBuilder> Base;
 
   const uint64_t AllocSize;
   AllocaSlices &S;
 
   SmallDenseMap<Instruction *, unsigned> MemTransferSliceMap;
   SmallDenseMap<Instruction *, uint64_t> PHIOrSelectSizes;
 
   /// \brief Set to de-duplicate dead instructions found in the use walk.
   SmallPtrSet<Instruction *, 4> VisitedDeadInsts;
 
 public:
   SliceBuilder(const DataLayout &DL, AllocaInst &AI, AllocaSlices &S)
       : PtrUseVisitor<SliceBuilder>(DL),
         AllocSize(DL.getTypeAllocSize(AI.getAllocatedType())), S(S) {}
 
 private:
   void markAsDead(Instruction &I) {
     if (VisitedDeadInsts.insert(&I))
void visitPHINode(PHINode &PN) {
     // For PHI and select operands outside the alloca, we can't nuke the entire
     // phi or select -- the other side might still be relevant, so we special
     // case them here and use a separate structure to track the operands
     // themselves which should be replaced with undef.
     // FIXME: This should instead be escaped in the event we're instrumenting
     // for address sanitization.
     if (Offset.uge(AllocSize)) {
       S.DeadOperands.push_back(U);
       return;
     }
 
     insertUse(PN, Offset, PHISize);
   }
 
   void visitSelectInst(SelectInst &SI) {
     if (SI.use_empty())
       return markAsDead(SI);
     if (Value *Result = foldSelectInst(SI)) {
       if (Result == *U)
         // If the result of the constant fold will be the pointer, recurse
         // through the select as if we had RAUW'ed it.
         enqueueUsers(SI);
       else
         // Otherwise the operand to the select is dead, and we can replace it
         // with undef.
         S.DeadOperands.push_back(U);
 
       return;
     }
     if (!IsOffsetKnown)
       return PI.setAborted(&SI);
 
     // See if we already have computed info on this node.
     uint64_t &SelectSize = PHIOrSelectSizes[&SI];
     if (!SelectSize) {
       // This is a new Select, check for an unsafe use of it.
       if (Instruction *UnsafeI = hasUnsafePHIOrSelectUse(&SI, SelectSize))
         return PI.setAborted(UnsafeI);
     }
 
     // For PHI and select operands outside the alloca, we can't nuke the entire
     // phi or select -- the other side might still be relevant, so we special
     // case them here and use a separate structure to track the operands
     // themselves which should be replaced with undef.
     // FIXME: This should instead be escaped in the event we're instrumenting
     // for address sanitization.
     if (Offset.uge(AllocSize)) {
       S.DeadOperands.push_back(U);
       return;
     }
 
     insertUse(SI, Offset, SelectSize);
   }
 
StructType *SubTy = StructType::get(STy->getContext(), makeArrayRef(EI, EE),
                                       STy->isPacked());
   const StructLayout *SubSL = DL.getStructLayout(SubTy);
   if (Size != SubSL->getSizeInBytes())
     return nullptr; // The sub-struct doesn't have quite the size needed.
 
   return SubTy;
 }
 
+/// \brief Return true if the value of PN originates from a value
+/// other than Source.
+///
+/// This function performs a standard depth-first search along the use-def
+/// chains of the PHI nodes. If the searching reaches a non-PHI other than
+/// Source, it stops and returns true.
+static bool
+PHINodeOriginatesFromOther(PHINode *PN, SmallPtrSetImpl<PHINode *> &Visited,
+                           SmallPtrSetImpl<PHINode *> &OriginatesFromOther,
+                           Value *Source) {
+  if (Visited.count(PN))
+    return OriginatesFromOther.count(PN);
+  Visited.insert(PN);
+  for (unsigned I = 0; I < PN->getNumIncomingValues(); ++I) {
+    Value *IV = PN->getIncomingValue(I);
+    if (PHINode *IncomingPN = dyn_cast<PHINode>(IV)) {
+      if (PHINodeOriginatesFromOther(IncomingPN, Visited, OriginatesFromOther,
+                                     Source)) {
+        OriginatesFromOther.insert(PN);
+        return true;
+      }
+    } else {
+      if (IV != Source) {
+        OriginatesFromOther.insert(PN);
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+/// \brief Simplify the PHI nodes in PHIUsers that are equivalent to NewAI.
+///
+/// Remove from PHIUsers PHI nodes that are equivalent to NewAI, and replace
+/// these PHI nodes with NewAI.
+static void
+simplifyPHINodesEquivalentToNewAlloca(SmallPtrSetImpl<PHINode *> &PHIUsers,
+                                      AllocaInst *NewAI) {
+  // Visited serves to break cycles during DFS.  OriginatesFromOther serves as a
+  // cache: if we already know that a PHI node originates from other values, we
+  // needn't search from it again.
+  SmallPtrSet<PHINode *, 8> Visited, OriginatesFromOther, ToDelete;
+  for (auto PN : PHIUsers) {
+    if (!PHINodeOriginatesFromOther(PN, Visited, OriginatesFromOther, NewAI))
+      ToDelete.insert(PN);
+  }
+  for (auto PN: ToDelete) {
+    PHIUsers.erase(PN);
+    PN->replaceAllUsesWith(NewAI);
+    PN->eraseFromParent();
+  }
+}
+
 /// \brief Rewrite an alloca partition's users.
 ///
 /// This routine drives both of the rewriting goals of the SROA pass. It tries
 /// to rewrite uses of an alloca partition to be conducive for SSA value
 /// promotion. If the partition needs a new, more refined alloca, this will
 /// build that new alloca, preserving as much type information as possible, and
 /// rewrite the uses of the old alloca to point at the new one and have the
 /// appropriate new offsets. It also evaluates how successful the rewrite was
for (AllocaSlices::iterator I = B; I != E; ++I) {
     Promotable &= Rewriter.visit(I);
     ++NumUses;
   }
 
   NumAllocaPartitionUses += NumUses;
   MaxUsesPerAllocaPartition =
       std::max<unsigned>(NumUses, MaxUsesPerAllocaPartition);
 
+  // Simplify PHI nodes in PHIUsers that are trivially equivalent to NewAI, so
+  // that we can promote them to registers more effectively.
+  simplifyPHINodesEquivalentToNewAlloca(PHIUsers, NewAI);
+
   // Now that we've processed all the slices in the new partition, check if any
   // PHIs or Selects would block promotion.
   for (SmallPtrSetImpl<PHINode *>::iterator I = PHIUsers.begin(),
                                             E = PHIUsers.end();
        I != E; ++I)
     if (!isSafePHIToSpeculate(**I, DL)) {
       Promotable = false;
       PHIUsers.clear();

test/Transforms/SROA/phi-and-select.ll

 end:
   %a.phi.f = phi float* [ %a.f, %then ], [ %a.raw.4.f, %else ]
   %f = load float* %a.phi.f
   ret float %f
 ; CHECK: %[[phi:.*]] = phi float [ %[[lo_cast]], %then ], [ %[[hi_cast]], %else ]
 ; CHECK-NOT: load
 ; CHECK: ret float %[[phi]]
 }
+
+; Verifies we fixed PR20425. We should be able to promote all alloca's to
+; registers in this test.
+;
+; %0 = slice
+; %1 = slice
+; %2 = phi(%0, %1) // == slice
+define float @simplify_phi_nodes_that_equal_slice(i1 %cond, float* %temp) {
+entry:
+  %arr = alloca [4 x float], align 4
+  br i1 %cond, label %then, label %else
+
+then:
+  %0 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3
+  store float 1.000000e+00, float* %0, align 4
+  br label %merge
+
+else:
+  %1 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3
+  store float 2.000000e+00, float* %1, align 4
+  br label %merge
+
+merge:
+  %2 = phi float* [ %0, %then ], [ %1, %else ]
+  store float 0.000000e+00, float* %temp, align 4
+  %3 = load float* %2, align 4
+  ret float %3
+}
+; CHECK-LABEL: @simplify_phi_nodes_that_equal_slice(
+; CHECK-NOT: alloca
+
+; A slightly complicated example for PR20425.
+;
+; %0 = slice
+; %1 = phi(%0) // == slice
+; %2 = slice
+; %3 = phi(%1, %2) // == slice
+define float @simplify_phi_nodes_that_equal_slice_2(i1 %cond, float* %temp) {
+entry:
+  %arr = alloca [4 x float], align 4
+  br i1 %cond, label %then, label %else
+
+then:
+  %0 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3
+  store float 1.000000e+00, float* %0, align 4
+  br label %then2
+
+then2:
+  %1 = phi float* [ %0, %then ]
+  store float 2.000000e+00, float* %1, align 4
+  br label %merge
+
+else:
+  %2 = getelementptr inbounds [4 x float]* %arr, i64 0, i64 3
+  store float 3.000000e+00, float* %2, align 4
+  br label %merge
+
+merge:
+  %3 = phi float* [ %1, %then2 ], [ %2, %else ]
+  store float 0.000000e+00, float* %temp, align 4
+  %4 = load float* %3, align 4
+  ret float %4
+}
+; CHECK-LABEL: @simplify_phi_nodes_that_equal_slice_2(
+; CHECK-NOT: alloca