Target hook to control Switch lowering.

[kariddi]

Summary

This patch adds a target hook to control the lowering of switch instructions in our default switch lowering pass.

The assumption is that there are certain kinds of switch instructions that can more efficiently lowered by the target because of how the targets handles control-flow.
Certain GPUs for example could lower switch more efficiently in certain cases than using a tree of conditions.

[hans]

This adds to the confusion about the two different switch lowering implementations.

As far as I can tell, none of the in-tree targets in LLVM use this "default lower switch pass" except AMDGPU. All the others use SelectionDAGBuilder.

For example, on X86 your TargetTransformInfo::shouldLowerSwitch() method would return true, indicating that it wants to use LowerSwitch, except that it doesn't, and that pass isn't even in the pipeline for X86. Pretty confusing.

IIUC, LowerSwitch gets run because StructurizeCFG depends on it. Could you make this dependency optional, and then instead of running LowerSwitch directly in your target, run a custom pass that looks at the switches and either runs LowerSwitch on them or leaves them alone / does something else?

This patch is also missing tests.

[kariddi]

Hmm, that is actually a possible interesting approach. Right now processSwitchInst is not callable from outside, the LowerSwitch pass, but maybe we could make it a utility function, like SimplifyCFG.

Otherwise, the original idea of the patch is to give more control to the target about the way switches are lowered.

You are right that the SelectionDAGBuilder lowering wouldn't be addressed by this and I'm wondering if it would actually make sense to add a custom lowering hook in SelectionDAGBuilder to be able to emit a target instruction representing a switch instead of an expansion of branches that would be very difficult to understand we are dealing with a switch and roll it back.

What do you think? I'm not very familiar on how the selectiondagbuilder emits the expansion. It seems to be creating the same kind of tree if jump tables are not available and creates additional basic blocks, so doesn't look easily "rollbackable".

[hans]

In D18604#387052, @kariddi wrote:

Hmm, that is actually a possible interesting approach. Right now processSwitchInst is not callable from outside, the LowerSwitch pass, but maybe we could make it a utility function, like SimplifyCFG.

I think that might be a good approach. It already lives in lib/Transforms/Utils after all :-)

Otherwise, the original idea of the patch is to give more control to the target about the way switches are lowered.

You are right that the SelectionDAGBuilder lowering wouldn't be addressed by this and I'm wondering if it would actually make sense to add a custom lowering hook in SelectionDAGBuilder to be able to emit a target instruction representing a switch instead of an expansion of branches that would be very difficult to understand we are dealing with a switch and roll it back.

What do you think? I'm not very familiar on how the selectiondagbuilder emits the expansion. It seems to be creating the same kind of tree if jump tables are not available and creates additional basic blocks, so doesn't look easily "rollbackable".

Yes, it would be very hard to roll back what SelectionDAGBuilder does to switches.

Having a hook to allow a custom switch lowering in SelectionDAGBuilder would work, I suppose.

include/llvm/Analysis/TargetTransformInfo.h

   /// target.
   bool shouldBuildLookupTables() const;
 
+  /// \brief Return true if the switch instruction should be lowered and false
+  /// if the target has a better lowering for this kind of switches that is not
+  /// what the default lower switch pass can do.
+  bool shouldLowerSwitch(const SwitchInst *SI) const;
+
   /// \brief Don't restrict interleaved unrolling to small loops.
   bool enableAggressiveInterleaving(bool LoopHasReductions) const;
 

   virtual unsigned getJumpBufAlignment() = 0;
   virtual unsigned getJumpBufSize() = 0;
   virtual bool shouldBuildLookupTables() = 0;
+  virtual bool shouldLowerSwitch(const SwitchInst *SI) = 0;
   virtual bool enableAggressiveInterleaving(bool LoopHasReductions) = 0;
   virtual bool enableInterleavedAccessVectorization() = 0;
   virtual PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) = 0;

   bool shouldBuildLookupTables() override {
     return Impl.shouldBuildLookupTables();
   }
+  bool shouldLowerSwitch(const SwitchInst *SI) override {
+    return Impl.shouldLowerSwitch(SI);
+  }
   bool enableAggressiveInterleaving(bool LoopHasReductions) override {
     return Impl.enableAggressiveInterleaving(LoopHasReductions);
   }

include/llvm/Analysis/TargetTransformInfoImpl.h

 
   bool shouldBuildLookupTables() { return true; }
 
+  bool shouldLowerSwitch(const SwitchInst *SI) { return true; }
+
   bool enableAggressiveInterleaving(bool LoopHasReductions) { return false; }
 
   bool enableInterleavedAccessVectorization() { return false; }

lib/Analysis/TargetTransformInfo.cpp

   return TTIImpl->shouldBuildLookupTables();
 }
 
+bool TargetTransformInfo::shouldLowerSwitch(const SwitchInst *SI) const {
+  return TTIImpl->shouldLowerSwitch(SI);
+}
+
 bool TargetTransformInfo::enableAggressiveInterleaving(bool LoopHasReductions) const {
   return TTIImpl->enableAggressiveInterleaving(LoopHasReductions);
 }

lib/Transforms/Utils/LowerSwitch.cpp

 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"

       // This is a cluster of orthogonal Transforms
       AU.addPreserved<UnifyFunctionExitNodes>();
       AU.addPreservedID(LowerInvokePassID);
+      AU.addRequired<TargetTransformInfoWrapperPass>();
     }
 
     struct CaseRange {

 }
 
 char LowerSwitch::ID = 0;
-INITIALIZE_PASS(LowerSwitch, "lowerswitch",
+INITIALIZE_PASS_BEGIN(LowerSwitch, "lowerswitch",
                       "Lower SwitchInst's to branches", false, false)
-
+INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_END(LowerSwitch, "lowerswitch",
+                    "Lower SwitchInst's to branches", false, false)
 // Publicly exposed interface to pass...
 char &llvm::LowerSwitchID = LowerSwitch::ID;
 // createLowerSwitchPass - Interface to this file...

 }
 
 bool LowerSwitch::runOnFunction(Function &F) {
+  const TargetTransformInfo &TTI =
+      getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   bool Changed = false;
   SmallPtrSet<BasicBlock*, 8> DeleteList;
 

       continue;
 
     if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
-      Changed = true;
-      processSwitchInst(SI, DeleteList);
+      if (TTI.shouldLowerSwitch(SI)) {
+        Changed = true;
+        processSwitchInst(SI, DeleteList);
+      }
     }
   }