[InstCombine] Allow removal of PHI cycles which only contain PHIs

[sbaranga]

Summary

This teaches instcombine to be able to remove PHI cycles which
only contain PHIs.

When a PHI doesn't have a non-PHI incoming value, we will now
try to resolve the PHI to each of the incoming values.

[reames]

lib/Transforms/InstCombine/InstCombinePHI.cpp

972

Repeating this for each incoming value seems likely to be expensive. Can we do better? As one filter, we know that for the phi to be equal to some value, that value must dominate the phi or be a non-instruction value right? If so, can we use that?

Another option on how to approach this would be an inductive proof over the loop. On iteration 1, we know that %p2 = %p0 and thus that on every future iteration all inputes to the phis equal %p0. Framing this using a loop pass (possibly indvarsimplify?) might be another approach.

To be clear, I'm okay with the patch in it's current form if we can't find a better approach. I'm just asking to make sure we've explored all the options before eating the compile time.

[sbaranga]

lib/Transforms/InstCombine/InstCombinePHI.cpp

972

Correct, this might be a bit expensive when triggered. But the problem only occurs when all incoming values are phis and the phi that we processing has lots of incoming values. This should mean that the really expensive wouldn't trigger that often.

Filtering with DT sounds like a very good idea. Do you think that this transformation should only be done when DT is available, or should we only filter when DT is available?

I think this case can be triggered without needing the a loop, but I don't have an example for that.

[sbaranga]

Only test incoming values if they dominate PN.

Note that all incoming values need to be PHIs in order for us to do this test,
so there's no need to test for non-instructions (since PHIs are instructions).

[majnemer]

lib/Transforms/InstCombine/InstCombinePHI.cpp

969–983

Seeing as how you are not inventing a new instruction, couldn't this live in InstructionSimplify?

[sbaranga]

lib/Transforms/InstCombine/InstCombinePHI.cpp

969–983

I suppose we could. Would we also move the logic that tries to find an incoming value that is not a PHI?

In that case this would get triggered a lot more often (and might have an impact on compile time).

[sbaranga]

Any thoughts on the compile time impact of doing this in InstructionSimplify?
I have a version of this that does the simplification in InstructionSimplify, and if there are no concerns about compile time we can use that.

Cheers,
Silviu

[majnemer]

lib/Transforms/InstCombine/InstCombinePHI.cpp

969–983

We already have similar logic in InstructionSimplify, this would make it more powerful. [1]

Would you mind benchmarking this between trunk vs trunk w/ InstructionSimplify amended?

[1] https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/InstructionSimplify.cpp#L3684

[sbaranga]

lib/Transforms/InstCombine/InstCombinePHI.cpp

969–983

Sure! I'll post the data once I have it.

Cheers,
Silviu

lib/Transforms/InstCombine/InstCombinePHI.cpp

if (PotentiallyDeadPHIs.size() == 16)
     return false;
 
   if (PHINode *PU = dyn_cast<PHINode>(PN->user_back()))
     return DeadPHICycle(PU, PotentiallyDeadPHIs);
 
   return false;
 }
 
-/// Return true if this phi node is always equal to NonPhiInVal.
+/// Return true if this phi node is always equal to Val.
 /// This happens with mutually cyclic phi nodes like:
 ///   z = some value; x = phi (y, z); y = phi (x, z)
-static bool PHIsEqualValue(PHINode *PN, Value *NonPhiInVal,
+static bool PHIsEqualValue(PHINode *PN, Value *Val,
                            SmallPtrSetImpl<PHINode*> &ValueEqualPHIs) {
   // See if we already saw this PHI node.
   if (!ValueEqualPHIs.insert(PN).second)
     return true;
 
   // Don't scan crazily complex things.
   if (ValueEqualPHIs.size() == 16)
     return false;
 
   // Scan the operands to see if they are either phi nodes or are equal to
   // the value.
   for (Value *Op : PN->incoming_values()) {
-    if (PHINode *OpPN = dyn_cast<PHINode>(Op)) {
-      if (!PHIsEqualValue(OpPN, NonPhiInVal, ValueEqualPHIs))
-        return false;
-    } else if (Op != NonPhiInVal)
-      return false;
+    if (Val == Op)
+      continue;
+
+    if (PHINode *OpPN = dyn_cast<PHINode>(Op))
+      if (PHIsEqualValue(OpPN, Val, ValueEqualPHIs))
+        continue;
+
   }
 
   return true;
 }
 
 /// Return an existing non-zero constant if this phi node has one, otherwise
 /// return constant 1.
 static ConstantInt *GetAnyNonZeroConstInt(PHINode &PN) {
if (InValNo != NumIncomingVals) {
       // If we scanned over all operands, then we have one unique value plus
       // phi values.  Scan PHI nodes to see if they all merge in each other or
       // the value.
       if (InValNo == NumIncomingVals) {
         SmallPtrSet<PHINode*, 16> ValueEqualPHIs;
         if (PHIsEqualValue(&PN, NonPhiInVal, ValueEqualPHIs))
           return replaceInstUsesWith(PN, NonPhiInVal);
       }
+    } else {
+      // This is a PHI of PHIs. See if any one of the incoming values
+      // can be proven to be the equal with this PHI.
+      for (InValNo = 0; InValNo != NumIncomingVals; ++InValNo) {
+        PHINode *Val = cast<PHINode>(PN.getIncomingValue(InValNo));
+
+        // No need to check values that don't dominate the PHI.
+        if (!DT->dominates(Val, &PN))
+          continue;
+
+        // Scan to see if we can prove that this is a phi cycle equal to
+        // Val.
+        SmallPtrSet<PHINode*, 16> ValueEqualPHIs;
+        if (PHIsEqualValue(&PN, Val, ValueEqualPHIs))
+          return replaceInstUsesWith(PN, Val);
+      }
     }
   }
 
   // If there are multiple PHIs, sort their operands so that they all list
   // the blocks in the same order. This will help identical PHIs be eliminated
   // by other passes. Other passes shouldn't depend on this for correctness
   // however.
   PHINode *FirstPN = cast<PHINode>(PN.getParent()->begin());

test/Transforms/InstCombine/phi-cycle.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128:n8:16:32:64"
+
+; Check that we can remove a dead phi cycle made up
+; entirely out of PHIs.
+
+; CHECK-LABEL: func1
+define i32 @func1(i1 %c, i1 %c2, i32 %x) {
+entry:
+  br i1 %c, label %if.else, label %pre
+
+if.else:
+  br label %pre
+
+pre:
+  %p0 = phi i32 [ %x, %entry ], [ 1, %if.else ]
+  br label %loop
+
+loop:
+  %p1 = phi i32 [ %p2, %loop-bb1 ], [ %p0, %pre ]
+  br i1 %c2, label %loop-bb1, label %loop-bb2
+
+loop-bb2:
+  br label %loop-bb1
+
+loop-bb1:
+  %p2 = phi i32 [ %p0, %loop ] , [ %p1, %loop-bb2 ]
+  br i1 %c, label %loop, label %exit
+
+exit:
+
+; CHECK: ret i32 %p0
+  ret i32 %p1
+}
+