Conversion of a switch table to a bitmap is not profitable for -Os and -Oz compilation

[ramred01]

Summary

When compiling for code size, conversion of a switch table into a bitmap is not profitable. The bitmap requires materializing a constant value of 32-bit or 64-bit width into a register, which usually requires 2 - 3 instructions followed by a either a left-shift followed by a right-shift _or_ a bit extract instruction to get the desired result. Whereas, indexing into a jump table would cost at most 2 instructions, plus the size of the jump table.

The bitmap is profitable when compiling for speed since it removes an indexed load, which is costly. But when compiling for size, it simply bloats the code without adding any real value for embedded targets.

The issue is pronounced when the switch result is a sub-word type (e.g., short or char). With word types, unless a double word type exists on the machine, this issue is not seen.

The following code demonstrates this behaviour:

short test(unsigned a) {

short t;
switch (a) {
case 0:
  t = 500;
  break;
case 1:
  t = 200;
  break;
case 2:
  t = 17000;    
  break;
default:
  t = 0;
  break;
}
return (t);

}

On AArch64, it uses 3 instructions to materialize 6 bytes of data and then performs a logical shift left followed by a logical shift right to get the result of the switch. Whereas, simply storing the data in a RO table and indexing into it would have generated two instructions to load the table address followed by one instruction to index into the table and load the result.

We fix the issue by adding a new Codegen option called -fno-switch-bitmap (and its converse -fswitch-bitmap) and make the generation of the Bitmap conditional. Then we modify the Clang FE to pass this switch when either the user explicitly passes this switch or the user is compiling for AArch64 with either -Os or -Oz. Currently we restrict this default option to AArch64 alone since we do not know which other architecture may benefit from this. Other architectures can also make this the default for -Os and -Oz once it is verified.

The clang patch is given in a separate revision.

[asl]

How many such switches are seen in e.g. LLVM test suite? Could you please share the size reduction statistics?

[hans]

First I was confused because your message mentions jump tables, but this is only about the switch-to-lookup table transformation in SimplifyCFG. So there are no jump tables involved, this is just about whether packing the lookup table into a "bitmap" scalar is a good idea or not.

Adding a -fno-switch-bitmap option doesn't seem like a great idea to me. Would it be possible to tweak the heuristic for when to emit the "bitmap lookup table" in some way instead? Currently we always do it if the table fits in a register. Maybe it should be more conservative, at least when optimizing for size, maybe depending on target?

include/llvm/Target/TargetOptions.h

TargetOptions()
           GuaranteedTailCallOpt(false), StackSymbolOrdering(true),
           EnableFastISel(false), EnableGlobalISel(false), UseInitArray(false),
           DisableIntegratedAS(false), RelaxELFRelocations(false),
           FunctionSections(false), DataSections(false),
           UniqueSectionNames(true), TrapUnreachable(false),
           NoTrapAfterNoreturn(false), EmulatedTLS(false),
           ExplicitEmulatedTLS(false), EnableIPRA(false),
           EmitStackSizeSection(false), EnableMachineOutliner(false),
-          SupportsDefaultOutlining(false), EmitAddrsig(false) {}
+          SupportsDefaultOutlining(false), EmitAddrsig(false),
+          EmitSwitchBitmap(false) {}
 
     /// PrintMachineCode - This flag is enabled when the -print-machineinstrs
     /// option is specified on the command line, and should enable debugging
     /// output from the code generator.
     unsigned PrintMachineCode : 1;
     
     /// DisableFramePointerElim - This returns true if frame pointer elimination
     /// optimization should be disabled for the given machine function.
     bool DisableFramePointerElim(const MachineFunction &MF) const;
 
     /// UnsafeFPMath - This flag is enabled when the
     /// -enable-unsafe-fp-math flag is specified on the command line.  When
     /// this flag is off (the default), the code generator is not allowed to
     /// produce results that are "less precise" than IEEE allows.  This includes
public:
     unsigned EnableMachineOutliner : 1;
 
     /// Set if the target supports default outlining behaviour.
     unsigned SupportsDefaultOutlining : 1;
 
     /// Emit address-significance table.
     unsigned EmitAddrsig : 1;
 
+    // Try to emit a Bitmap instead of a Switch Table.
+    unsigned EmitSwitchBitmap : 1;
+
     /// FloatABIType - This setting is set by -float-abi=xxx option is specfied
     /// on the command line. This setting may either be Default, Soft, or Hard.
     /// Default selects the target's default behavior. Soft selects the ABI for
     /// software floating point, but does not indicate that FP hardware may not
     /// be used. Such a combination is unfortunately popular (e.g.
     /// arm-apple-darwin). Hard presumes that the normal FP ABI is used.
     FloatABI::ABIType FloatABIType = FloatABI::Default;
 

include/llvm/Transforms/IPO/PassManagerBuilder.h

public:
   bool EnablePGOInstrGen;
   /// Profile data file name that the instrumentation will be written to.
   std::string PGOInstrGen;
   /// Path of the profile data file.
   std::string PGOInstrUse;
   /// Path of the sample Profile data file.
   std::string PGOSampleUse;
 
+  /// Don't convert a Switch Table into a Bitmap
+  bool NoSwitchBitmap;
+
 private:
   /// ExtensionList - This is list of all of the extensions that are registered.
   std::vector<std::pair<ExtensionPointTy, ExtensionFn>> Extensions;
 
 public:
   PassManagerBuilder();
   ~PassManagerBuilder();
   /// Adds an extension that will be used by all PassManagerBuilder instances.

include/llvm/Transforms/Scalar.h

 //
 FunctionPass *createJumpThreadingPass(int Threshold = -1);
 
 //===----------------------------------------------------------------------===//
 //
 // CFGSimplification - Merge basic blocks, eliminate unreachable blocks,
 // simplify terminator instructions, convert switches to lookup tables, etc.
 //
-FunctionPass *createCFGSimplificationPass(
-    unsigned Threshold = 1, bool ForwardSwitchCond = false,
-    bool ConvertSwitch = false, bool KeepLoops = true, bool SinkCommon = false,
+FunctionPass *createCFGSimplificationPass(unsigned Threshold = 1, 
+    bool ForwardSwitchCond = false, bool ConvertSwitch = false, 
+    bool KeepLoops = true, bool SinkCommon = false, 
+    bool noSwitchBitmap = false,
     std::function<bool(const Function &)> Ftor = nullptr);
 
 //===----------------------------------------------------------------------===//
 //
 // FlattenCFG - flatten CFG, reduce number of conditional branches by using
 // parallel-and and parallel-or mode, etc...
 //
 FunctionPass *createFlattenCFGPass();

include/llvm/Transforms/Utils/Local.h

 /// For example, canonical form that includes switches and branches may later be
 /// replaced by lookup tables and selects.
 struct SimplifyCFGOptions {
   int BonusInstThreshold;
   bool ForwardSwitchCondToPhi;
   bool ConvertSwitchToLookupTable;
   bool NeedCanonicalLoop;
   bool SinkCommonInsts;
+  bool NoSwitchBitmap;
   AssumptionCache *AC;
 
   SimplifyCFGOptions(unsigned BonusThreshold = 1,
                      bool ForwardSwitchCond = false,
                      bool SwitchToLookup = false, bool CanonicalLoops = true,
                      bool SinkCommon = false,
                      AssumptionCache *AssumpCache = nullptr)
       : BonusInstThreshold(BonusThreshold),

lib/Target/AArch64/AArch64TargetMachine.cpp

void AArch64PassConfig::addIRPasses() {
   // Always expand atomic operations, we don't deal with atomicrmw or cmpxchg
   // ourselves.
   addPass(createAtomicExpandPass());
 
   // Cmpxchg instructions are often used with a subsequent comparison to
   // determine whether it succeeded. We can exploit existing control-flow in
   // ldrex/strex loops to simplify this, but it needs tidying up.
   if (TM->getOptLevel() != CodeGenOpt::None && EnableAtomicTidy)
-    addPass(createCFGSimplificationPass(1, true, true, false, true));
+    addPass(createCFGSimplificationPass(1, true, true, false, true,
+                                        TM->Options.EmitSwitchBitmap));
 
   // Run LoopDataPrefetch
   //
   // Run this before LSR to remove the multiplies involved in computing the
   // pointer values N iterations ahead.
   if (TM->getOptLevel() != CodeGenOpt::None) {
     if (EnableLoopDataPrefetch)
       addPass(createLoopDataPrefetchPass());

lib/Target/ARM/ARMTargetMachine.cpp

void ARMPassConfig::addIRPasses() {
   else
     addPass(createAtomicExpandPass());
 
   // Cmpxchg instructions are often used with a subsequent comparison to
   // determine whether it succeeded. We can exploit existing control-flow in
   // ldrex/strex loops to simplify this, but it needs tidying up.
   if (TM->getOptLevel() != CodeGenOpt::None && EnableAtomicTidy)
     addPass(createCFGSimplificationPass(
-        1, false, false, true, true, [this](const Function &F) {
+        1, false, false, true, true, false, [this](const Function &F) {
           const auto &ST = this->TM->getSubtarget<ARMSubtarget>(F);
           return ST.hasAnyDataBarrier() && !ST.isThumb1Only();
         }));
 
   TargetPassConfig::addIRPasses();
 
   // Match interleaved memory accesses to ldN/stN intrinsics.
   if (TM->getOptLevel() != CodeGenOpt::None)

lib/Transforms/IPO/PassManagerBuilder.cpp

if (OptLevel > 1 && ExtraVectorizerPasses) {
     addInstructionCombiningPass(MPM);
   }
 
   // Cleanup after loop vectorization, etc. Simplification passes like CVP and
   // GVN, loop transforms, and others have already run, so it's now better to
   // convert to more optimized IR using more aggressive simplify CFG options.
   // The extra sinking transform can create larger basic blocks, so do this
   // before SLP vectorization.
-  MPM.add(createCFGSimplificationPass(1, true, true, false, true));
+  MPM.add(createCFGSimplificationPass(1, true, true, false, true,
+          NoSwitchBitmap));
 
   if (RunSLPAfterLoopVectorization && SLPVectorize) {
     MPM.add(createSLPVectorizerPass()); // Vectorize parallel scalar chains.
     if (OptLevel > 1 && ExtraVectorizerPasses) {
       MPM.add(createEarlyCSEPass());
     }
   }
 

lib/Transforms/Scalar/SimplifyCFGPass.cpp

 static cl::opt<bool> UserForwardSwitchCond(
     "forward-switch-cond", cl::Hidden, cl::init(false),
     cl::desc("Forward switch condition to phi ops (default = false)"));
 
 static cl::opt<bool> UserSinkCommonInsts(
     "sink-common-insts", cl::Hidden, cl::init(false),
     cl::desc("Sink common instructions (default = false)"));
 
-
 STATISTIC(NumSimpl, "Number of blocks simplified");
 
 /// If we have more than one empty (other than phi node) return blocks,
 /// merge them together to promote recursive block merging.
 static bool mergeEmptyReturnBlocks(Function &F) {
   bool Changed = false;
 
   BasicBlock *RetBlock = nullptr;

 struct CFGSimplifyPass : public FunctionPass {
   static char ID;
   SimplifyCFGOptions Options;
   std::function<bool(const Function &)> PredicateFtor;
 
   CFGSimplifyPass(unsigned Threshold = 1, bool ForwardSwitchCond = false,
                   bool ConvertSwitch = false, bool KeepLoops = true,
                   bool SinkCommon = false,
+                  bool noSwitchBitmap = false,
                   std::function<bool(const Function &)> Ftor = nullptr)
       : FunctionPass(ID), PredicateFtor(std::move(Ftor)) {
 
     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
 
     // Check for command-line overrides of options for debug/customization.
     Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
                                     ? UserBonusInstThreshold
                                     : Threshold;
 
     Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
                                          ? UserForwardSwitchCond
                                          : ForwardSwitchCond;
 
     Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
                                              ? UserSwitchToLookup
                                              : ConvertSwitch;
 
     Options.NeedCanonicalLoop =
         UserKeepLoops.getNumOccurrences() ? UserKeepLoops : KeepLoops;
 
     Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
                                   ? UserSinkCommonInsts
                                   : SinkCommon;
+
+    Options.NoSwitchBitmap = noSwitchBitmap;
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
       return false;
 
     Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);

 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
                     false)
 
 // Public interface to the CFGSimplification pass
 FunctionPass *
 llvm::createCFGSimplificationPass(unsigned Threshold, bool ForwardSwitchCond,
                                   bool ConvertSwitch, bool KeepLoops,
-                                  bool SinkCommon,
-                                  std::function<bool(const Function &)> Ftor) {
+                                  bool SinkCommon, bool noSwitchBitmap,
+                                  std::function<bool(const Function &)> Ftor) { 
   return new CFGSimplifyPass(Threshold, ForwardSwitchCond, ConvertSwitch,
-                             KeepLoops, SinkCommon, std::move(Ftor));
+                             KeepLoops, SinkCommon, noSwitchBitmap, 
+                             std::move(Ftor));
 }

lib/Transforms/Utils/SimplifyCFG.cpp

 /// This class represents a lookup table that can be used to replace a switch.
 class SwitchLookupTable {
 public:
   /// Create a lookup table to use as a switch replacement with the contents
   /// of Values, using DefaultValue to fill any holes in the table.
   SwitchLookupTable(
       Module &M, uint64_t TableSize, ConstantInt *Offset,
       const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
-      Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName);
+      Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName,
+      SimplifyCFGOptions &Options);
 
   /// Build instructions with Builder to retrieve the value at
   /// the position given by Index in the lookup table.
   Value *BuildLookup(Value *Index, IRBuilder<> &Builder);
 
   /// Return true if a table with TableSize elements of
   /// type ElementType would fit in a target-legal register.
   static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize,
private:
   GlobalVariable *Array = nullptr;
 };
 
 } // end anonymous namespace
 
 SwitchLookupTable::SwitchLookupTable(
     Module &M, uint64_t TableSize, ConstantInt *Offset,
     const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
-    Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName) {
+    Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName,
+    SimplifyCFGOptions &Options) {
   assert(Values.size() && "Can't build lookup table without values!");
   assert(TableSize >= Values.size() && "Can't fit values in table!");
   
   // If all values in the table are equal, this is that value.
   SingleValue = Values.begin()->second;
   
   Type *ValueType = Values.begin()->second->getType();
 
   // Build up the table contents.
   SmallVector<Constant *, 64> TableContents(TableSize);
   for (size_t I = 0, E = Values.size(); I != E; ++I) {
     ConstantInt *CaseVal = Values[I].first;
     Constant *CaseRes = Values[I].second;
     assert(CaseRes->getType() == ValueType);
if (LinearMappingPossible) {
       LinearOffset = cast<ConstantInt>(TableContents[0]);
       LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
       Kind = LinearMapKind;
       ++NumLinearMaps;
       return;
     }
   }
 
+  // if fno-switch-bitmap flag is on, will skip building of a bitmap in place
+  // of a switch table.
+  if (!Options.NoSwitchBitmap) {
     // If the type is integer and the table fits in a register, build a bitmap.
     if (WouldFitInRegister(DL, TableSize, ValueType)) {
       IntegerType *IT = cast<IntegerType>(ValueType);
       APInt TableInt(TableSize * IT->getBitWidth(), 0);
       for (uint64_t I = TableSize; I > 0; --I) {
         TableInt <<= IT->getBitWidth();
         // Insert values into the bitmap. Undef values are set to zero.
         if (!isa<UndefValue>(TableContents[I - 1])) {
           ConstantInt *Val = cast<ConstantInt>(TableContents[I - 1]);
           TableInt |= Val->getValue().zext(TableInt.getBitWidth());
         }
       }
       BitMap = ConstantInt::get(M.getContext(), TableInt);
       BitMapElementTy = IT;
       Kind = BitMapKind;
       ++NumBitMaps;
       return;
     }
-
+  }
   // Store the table in an array.
   ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize);
   Constant *Initializer = ConstantArray::get(ArrayTy, TableContents);
 
   Array = new GlobalVariable(M, ArrayTy, /*constant=*/true,
                              GlobalVariable::PrivateLinkage, Initializer,
                              "switch.table." + FuncName);
   Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
static void reuseTableCompare(
   }
 }
 
 /// If the switch is only used to initialize one or more phi nodes in a common
 /// successor block with different constant values, replace the switch with
 /// lookup tables.
 static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
                                 const DataLayout &DL,
-                                const TargetTransformInfo &TTI) {
+                                const TargetTransformInfo &TTI,
+                                SimplifyCFGOptions Options) {
   assert(SI->getNumCases() > 1 && "Degenerate switch?");
 
   Function *Fn = SI->getParent()->getParent();
   // Only build lookup table when we have a target that supports it or the
   // attribute is not set.
   if (!TTI.shouldBuildLookupTables() ||
       (Fn->getFnAttribute("no-jump-tables").getValueAsString() == "true"))
     return false;
static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
   bool ReturnedEarly = false;
   for (PHINode *PHI : PHIs) {
     const ResultListTy &ResultList = ResultLists[PHI];
 
     // If using a bitmask, use any value to fill the lookup table holes.
     Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI];
     StringRef FuncName = Fn->getName();
     SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL,
-                            FuncName);
+                            FuncName, Options);
 
     Value *Result = Table.BuildLookup(TableIndex, Builder);
 
     // If the result is used to return immediately from the function, we want to
     // do that right here.
     if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->user_begin()) &&
         PHI->user_back() == CommonDest->getFirstNonPHIOrDbg()) {
       Builder.CreateRet(Result);
if (Options.ForwardSwitchCondToPhi && ForwardSwitchConditionToPHI(SI))
     return requestResimplify();
 
   // The conversion from switch to lookup tables results in difficult-to-analyze
   // code and makes pruning branches much harder. This is a problem if the
   // switch expression itself can still be restricted as a result of inlining or
   // CVP. Therefore, only apply this transformation during late stages of the
   // optimisation pipeline.
   if (Options.ConvertSwitchToLookupTable &&
-      SwitchToLookupTable(SI, Builder, DL, TTI))
+      SwitchToLookupTable(SI, Builder, DL, TTI, Options))
     return requestResimplify();
 
   if (ReduceSwitchRange(SI, Builder, DL, TTI))
     return requestResimplify();
 
   return false;
 }
 

test/Transforms/Util/no_switch_bitmap.ll

+;RUN: llc %s -o - -verify-machineinstrs | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-arm-none-eabi"
+
[e-mail] = private unnamed_addr constant [3 x i16] [i16 500, i16 200, i16 17000], align 4
+
+; Function Attrs: minsize norecurse nounwind optsize readnone
+;CHECK-LABEL: @test
+;CHECK: cmp
+;CHECK: b 
+;CHECK: adrp
+;CHECK: add
+;CHECK: ldrh
+;CHECK: ret
+;CHECK: mov
+;CHECK: ret
+define dso_local i16 @test(i32) local_unnamed_addr #0 {
+  %2 = icmp ult i32 %0, 3
+  br i1 %2, label %3, label %7
+
+; <label>:3:                                      ; preds = %1
+  %4 = sext i32 %0 to i64
+  %5 = getelementptr inbounds [3 x i16], [3 x i16]* @switch.table.test, i64 0, i64 %4
+  %6 = load i16, i16* %5, align 2
+  ret i16 %6
+
+; <label>:7:                                      ; preds = %1
+  ret i16 0
+}
+
+attributes #0 = { minsize norecurse nounwind optsize readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="cortex-a53" "target-features"="+aes,+crc,+crypto,+fp-armv8,+neon,+sha2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 9.0.0 (https://git.llvm.org/git/clang.git/ 112a7a3c34df3dc506b52cd89e155287cdbcea55) (https://git.llvm.org/git/llvm.git/ feeb3cebe7a586a8e1b12735024389dd8d3bab53)"}