[SimplifyCFG] try harder to forward switch condition to phi (PR34471)

[spatel]

Summary

The missed canonicalization/optimization in the motivating test from PR34471 leads to very different codegen:

int switcher(int x) {
    switch(x) {
    case 17: return 17;
    case 19: return 19;
    case 42: return 42;
    default: break;
    }
    return 0;
  }

int comparator(int x) {
  if (x == 17) return 17;
  if (x == 19) return 19;
  if (x == 42) return 42;
  return 0;
}

For the first example, we use a bit-test optimization to avoid a series of compare-and-branch:
https://godbolt.org/g/BivDsw

[hans]

lgtm

[davide]

What's the interaction between this code and constant propagation?

[spatel]

In D39011#900214, @davide wrote:

What's the interaction between this code and constant propagation?

This transform makes it less likely to combine constants I guess. Do you have an example in mind where that makes things worse?

[• dberlin]

Hey Sanjay,
GVN/NewGVN/et al will undo this transform, and propagate constants. In fact, i expect pretty much any pass that can, will.

This definitely belongs in the late simplification category at best.

More than that, i'm concerned this is the wrong fix.

Why is the right answer to undo the transform (which will cause fights between passes) in simplifycfg instead of improving the codegen to recognize the issue?

It seems the same code you are using to detect and undo the transforrm in simplification could be used to codegen it better.

[davide]

yes, that was my concern too. I think pretty much every forward data flow analysis that propagates facts can make this xform useless. If anything, it's too fragile.

[davide]

(sorry I didnt reply before but it was devmtg week)

[spatel]

In D39011#903093, @dberlin wrote:

Hey Sanjay,
GVN/NewGVN/et al will undo this transform, and propagate constants. In fact, i expect pretty much any pass that can, will.

This definitely belongs in the late simplification category at best.

More than that, i'm concerned this is the wrong fix.

Why is the right answer to undo the transform (which will cause fights between passes) in simplifycfg instead of improving the codegen to recognize the issue?

It seems the same code you are using to detect and undo the transforrm in simplification could be used to codegen it better.

I didn't realize other passes were undoing this transform. I thought I was just improving the existing canonical form favored by SimplifyCFG. Ie, the existing code in ForwardSwitchConditionToPHI() is already fighting with the other passes, correct?

So I'm certainly open to suggestions on how to proceed. Should I revert this change or delay everything in ForwardSwitchConditionToPHI() to -latesimplifycfg (note: I proposed a refinement of that in D38631)? And then follow that with moving everything to codegen (I haven't actually looked at switches in codegen yet, so that's definitely a follow-up step if I'm doing it).

[• dberlin]

So, in the original test and code it's hard to tell, but yes, if it's trying to undo the propagation of constants into phi nodes, it's already going to be fighting, because everything else is trying to do that transform specifically :)

It's probably worth taking a look at codegen and seeing how hard it is.
So i'd say "delay it all to latesimplifycfg for now, see how hard codegen is".
I'm hopeful it's not that tricky to fix codegen. But if it is, yeah let's see how far we want to go here, i don't think you should be on the hook for cleaning all of this up if it's hard.

(One could also argue about the value of constant propagation in this case. It's mostly useful for range analysis, jump threading, transformation into select, etc. I'm indifferent if we want to canonicalize late to some other form if we can show it's better)

[spatel]

In D39011#903105, @dberlin wrote:

So, in the original test and code it's hard to tell, but yes, if it's trying to undo the propagation of constants into phi nodes, it's already going to be fighting, because everything else is trying to do that transform specifically :)

It's probably worth taking a look at codegen and seeing how hard it is.
So i'd say "delay it all to latesimplifycfg for now, see how hard codegen is".
I'm hopeful it's not that tricky to fix codegen. But if it is, yeah let's see how far we want to go here, i don't think you should be on the hook for cleaning all of this up if it's hard.

(One could also argue about the value of constant propagation in this case. It's mostly useful for range analysis, jump threading, transformation into select, etc. I'm indifferent if we want to canonicalize late to some other form if we can show it's better)

Yeah, I can see the existing -simplifycfg code fights -gvn on this. Let me add another simplifycfg option bit to delay the whole thing. Then, I'll look at the codegen side. Thanks everyone for pointing out the problems!

[spatel]

Delay switch condition forwarding to -latesimplifycfg:
rL316298

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

 }
 
 /// Try to forward the condition of a switch instruction to a phi node
 /// dominated by the switch, if that would mean that some of the destination
 /// blocks of the switch can be folded away. Return true if a change is made.
 static bool ForwardSwitchConditionToPHI(SwitchInst *SI) {
   typedef DenseMap<PHINode *, SmallVector<int, 4>> ForwardingNodesMap;
   ForwardingNodesMap ForwardingNodes;
-
+  BasicBlock *SwitchBlock = SI->getParent();
+  bool Changed = false;
   for (auto &Case : SI->cases()) {
     ConstantInt *CaseValue = Case.getCaseValue();
     BasicBlock *CaseDest = Case.getCaseSuccessor();
+
+    // Replace phi operands in successor blocks that are using the constant case
+    // value rather than the switch condition variable:
+    //   switchbb:
+    //   switch i32 %x, label %default [
+    //     i32 17, label %succ
+    //   ...
+    //   succ:
+    //     %r = phi i32 ... [ 17, %switchbb ] ...
+    // -->
+    //     %r = phi i32 ... [ %x, %switchbb ] ...
+
+    for (Instruction &InstInCaseDest : *CaseDest) {
+      auto *Phi = dyn_cast<PHINode>(&InstInCaseDest);
+      if (!Phi) break;
+
+      // This only works if there is exactly 1 incoming edge from the switch to
+      // a phi. If there is >1, that means multiple cases of the switch map to 1
+      // value in the phi, and that phi value is not the switch condition. Thus,
+      // this transform would not make sense (the phi would be invalid because
+      // a phi can't have different incoming values from the same block).
+      int SwitchBBIdx = Phi->getBasicBlockIndex(SwitchBlock);
+      if (Phi->getIncomingValue(SwitchBBIdx) == CaseValue &&
+          count(Phi->blocks(), SwitchBlock) == 1) {
+        Phi->setIncomingValue(SwitchBBIdx, SI->getCondition());
+        Changed = true;
+      }
+    }
+
+    // Collect phi nodes that are indirectly using this switch's case constants.
     int PhiIdx;
     if (auto *Phi = FindPHIForConditionForwarding(CaseValue, CaseDest, &PhiIdx))
       ForwardingNodes[Phi].push_back(PhiIdx);
   }
 
-  bool Changed = false;
   for (auto &ForwardingNode : ForwardingNodes) {
     PHINode *Phi = ForwardingNode.first;
     SmallVectorImpl<int> &Indexes = ForwardingNode.second;
     if (Indexes.size() < 2)
       continue;
 
     for (int Index : Indexes)
       Phi->setIncomingValue(Index, SI->getCondition());

llvm/trunk/test/Transforms/SimplifyCFG/ForwardSwitchConditionToPHI.ll

 ; https://bugs.llvm.org/show_bug.cgi?id=34471
 ; This then subsequently should allow squashing of the other trivial case blocks.
 
 define i32 @PR34471(i32 %x) {
 ; CHECK-LABEL: @PR34471(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    switch i32 [[X:%.*]], label [[ELSE3:%.*]] [
 ; CHECK-NEXT:    i32 17, label [[RETURN:%.*]]
-; CHECK-NEXT:    i32 19, label [[IF19:%.*]]
-; CHECK-NEXT:    i32 42, label [[IF42:%.*]]
+; CHECK-NEXT:    i32 19, label [[RETURN]]
+; CHECK-NEXT:    i32 42, label [[RETURN]]
 ; CHECK-NEXT:    ]
-; CHECK:       if19:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       if42:
-; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       else3:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[X]], [[IF19]] ], [ [[X]], [[IF42]] ], [ 0, [[ELSE3]] ], [ 17, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ 0, [[ELSE3]] ], [ [[X]], [[ENTRY:%.*]] ], [ [[X]], [[ENTRY]] ], [ [[X]], [[ENTRY]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   switch i32 %x, label %else3 [
   i32 17, label %return
   i32 19, label %if19
   i32 42, label %if42
   ]