[SimplifyCFG] Make the no-jump-tables attribute also disable switch lookup tables

[sgundapa]

Summary

[joerg]

lib/Transforms/Utils/SimplifyCFG.cpp

5155

Just use Fn->getName() below directly.

5157

...and the attribute "..." is not set.

test/Transforms/SimplifyCFG/Hexagon/disable-lookup-table.ll

61

Can you reduce this further?

test/Transforms/SimplifyCFG/disable-lookup-table.ll

30

Since this is a bit fragile when it comes to other optimizations deciding to merge the ranges, can you test the reverse as well? I.e. that it is turned into a lookup table when just the attribute is missing.

[hans]

What is the motivation for this?

[sgundapa]

For backends with "tightly coupled memory", in scenarios where the data is far away from text pays a good amount of penalty in terms of latency.
Hexagon is one such backend. The tables (both lookup and jump) which are being generated are treated as globals with internal linkage and by default
will be placed in read only data.

Interestingly when programmers specify the command line flag "-fno-jump-tables", they assume there is no data that goes in to other sections.
In case of llvm, the attribute "no-jump-tables" has no effect on simplifyCFG which generates the lookup table. This leads me to introduce "no-lookup-tables"

[mcrosier]

In D35579#814575, @sgundapa wrote:

For backends with "tightly coupled memory", in scenarios where the data is far away from text pays a good amount of penalty in terms of latency.
Hexagon is one such backend. The tables (both lookup and jump) which are being generated are treated as globals with internal linkage and by default
will be placed in read only data.

Interestingly when programmers specify the command line flag "-fno-jump-tables", they assume there is no data that goes in to other sections.
In case of llvm, the attribute "no-jump-tables" has no effect on simplifyCFG which generates the lookup table. This leads me to introduce "no-lookup-tables"

It looks like TargetTransformInfo already has a hook, shouldBuildLookupTables(), for disabling this optimization. Why not just set that to false for Hexagon?

[sgundapa]

Made changes as per reviewers comments

[sgundapa]

lib/Transforms/Utils/SimplifyCFG.cpp

5155

FuncName is being used below to set the name of the table to switch.table.<FuncName>

[sgundapa]

It looks like TargetTransformInfo already has a hook, shouldBuildLookupTables(), for disabling this optimization. Why not just set that to false for Hexagon?

TCM is often small and you don't want to either enable or disable the table generation for a specific backend. As of today,
hexagon-emit-lookup-tables llvm flag control the generation of lookup tables for hexagon backend.
The real problem here is , I do not want the user to use a combination of front end and backend flags to get the desired result.

[mcrosier]

Adding @echristo and @ddunbar who have been the primary owners of the driver for the past decade or so.

[sgundapa]

We have decided to have this feature under "-fno-jump-tables" clang flag.
To this affect, this patch updates the code to control the generation of
lookup tables based on the attribute "no-jump-tables"

[hans]

"Generate lookup tables based on a function attribute" is not very descriptive. How about "Make the no-jump-tables attribute also disable switch lookup tables"?

Also it makes me sad that the attribute isn't documented anywhere. Would you like to look into that, possible as a follow-up patch?

lib/Transforms/Utils/SimplifyCFG.cpp

5155

There doesn't seem to be any need to move FuncName up here anymore, since it's not used until further down.

[sgundapa]

Also it makes me sad that the attribute isn't documented anywhere. Would you like to look into that, possible as a follow-up patch?

Sure. I will push a follow up patch

[inouehrs]

I moved SimplifyCFG/disable-lookup-table.ll into SimplifyCFG/X86/disable-lookup-table.ll to avoid test failure when X86 backend is not enabled (rL309487).
Please update again if you prefer another way to avoid test failure. Thanks!

include/llvm/IR/Attributes.td

 def ZExt : EnumAttr<"zeroext">;
 
 /// Target-independent string attributes.
 def LessPreciseFPMAD : StrBoolAttr<"less-precise-fpmad">;
 def NoInfsFPMath : StrBoolAttr<"no-infs-fp-math">;
 def NoNansFPMath : StrBoolAttr<"no-nans-fp-math">;
 def UnsafeFPMath : StrBoolAttr<"unsafe-fp-math">;
 def NoJumpTables : StrBoolAttr<"no-jump-tables">;
+def NoLookupTables : StrBoolAttr<"no-lookup-tables">;
 
 class CompatRule<string F> {
   // The name of the function called to check the attribute of the caller and
   // callee and decide whether inlining should be allowed. The function's
   // signature must match "bool(const Function&, const Function &)", where the
   // first parameter is the reference to the caller and the second parameter is
   // the reference to the callee. It must return false if the attributes of the
   // caller and callee are incompatible, and true otherwise.

 }
 
 def : MergeRule<"setAND<LessPreciseFPMADAttr>">;
 def : MergeRule<"setAND<NoInfsFPMathAttr>">;
 def : MergeRule<"setAND<NoNansFPMathAttr>">;
 def : MergeRule<"setAND<UnsafeFPMathAttr>">;
 def : MergeRule<"setOR<NoImplicitFloatAttr>">;
 def : MergeRule<"setOR<NoJumpTablesAttr>">;
+def : MergeRule<"setOR<NoLookupTablesAttr>">;
 def : MergeRule<"adjustCallerSSPLevel">;
 def : MergeRule<"adjustCallerStackProbes">;
 def : MergeRule<"adjustCallerStackProbeSize">;

lib/Transforms/Utils/SimplifyCFG.cpp

 /// 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) {
   assert(SI->getNumCases() > 1 && "Degenerate switch?");
 
-  // Only build lookup table when we have a target that supports it.
-  if (!TTI.shouldBuildLookupTables())
+  Function *Fn = SI->getParent()->getParent();
+  StringRef FuncName = Fn->getName();
+  // Only build lookup table when we have a target that supports it or the
+  // attribute is not set.
+  if (!TTI.shouldBuildLookupTables() ||
+      (Fn->getFnAttribute("no-lookup-tables").getValueAsString() == "true"))
     return false;
 
   // FIXME: If the switch is too sparse for a lookup table, perhaps we could
   // split off a dense part and build a lookup table for that.
 
   // FIXME: This creates arrays of GEPs to constant strings, which means each
   // GEP needs a runtime relocation in PIC code. We should just build one big
   // string and lookup indices into that.
static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
 
   bool ReturnedEarly = false;
   for (size_t I = 0, E = PHIs.size(); I != E; ++I) {
     PHINode *PHI = PHIs[I];
     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 = SI->getParent()->getParent()->getName();
     SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL,
                             FuncName);
 
     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()) &&

test/Transforms/Inline/attributes.ll

 
 define i32 @test_no-use-jump-tables3(i32 %i) "no-jump-tables"="true" {
   %1 = call i32 @no-use-jump-tables_callee1(i32 %i)
   ret i32 %1
 ; CHECK: @test_no-use-jump-tables3(i32 %i) [[NOUSEJUMPTABLES]] {
 ; CHECK-NEXT: ret i32
 }
 
+; Check that no-lookup-tables flag propagates from inlined callee to caller
+
+define i32 @no-use-lookup-tables_callee0(i32 %i) {
+  ret i32 %i
+; CHECK: @no-use-lookup-tables_callee0(i32 %i) {
+; CHECK-NEXT: ret i32
+}
+
+define i32 @no-use-lookup-tables_callee1(i32 %i) "no-lookup-tables"="true" {
+  ret i32 %i
+; CHECK: @no-use-lookup-tables_callee1(i32 %i) [[NOUSELOOKUPTABLES:#[0-9]+]] {
+; CHECK-NEXT: ret i32
+}
+
+define i32 @test_no-use-lookup-tables0(i32 %i) {
+  %1 = call i32 @no-use-lookup-tables_callee0(i32 %i)
+  ret i32 %1
+; CHECK: @test_no-use-lookup-tables0(i32 %i) {
+; CHECK-NEXT: ret i32
+}
+
+define i32 @test_no-use-lookup-tables1(i32 %i) {
+  %1 = call i32 @no-use-lookup-tables_callee1(i32 %i)
+  ret i32 %1
+; CHECK: @test_no-use-lookup-tables1(i32 %i) [[NOUSELOOKUPTABLES]] {
+; CHECK-NEXT: ret i32
+}
+
+define i32 @test_no-use-lookup-tables2(i32 %i) "no-lookup-tables"="true" {
+  %1 = call i32 @no-use-lookup-tables_callee0(i32 %i)
+  ret i32 %1
+; CHECK: @test_no-use-lookup-tables2(i32 %i) [[NOUSELOOKUPTABLES]] {
+; CHECK-NEXT: ret i32
+}
+
+define i32 @test_no-use-lookup-tables3(i32 %i) "no-lookup-tables"="true" {
+  %1 = call i32 @no-use-lookup-tables_callee1(i32 %i)
+  ret i32 %1
+; CHECK: @test_no-use-lookup-tables3(i32 %i) [[NOUSELOOKUPTABLES]] {
+; CHECK-NEXT: ret i32
+}
+
 ; CHECK: attributes [[FPMAD_FALSE]] = { "less-precise-fpmad"="false" }
 ; CHECK: attributes [[FPMAD_TRUE]] = { "less-precise-fpmad"="true" }
 ; CHECK: attributes [[NOIMPLICITFLOAT]] = { noimplicitfloat }
 ; CHECK: attributes [[NOUSEJUMPTABLES]] = { "no-jump-tables"="true" }
+; CHECK: attributes [[NOUSELOOKUPTABLES]] = { "no-lookup-tables"="true" }

test/Transforms/SimplifyCFG/Hexagon/disable-lookup-table.ll

+; RUN: opt -S -O2 < %s | FileCheck %s -check-prefix=DISABLE
+; RUN: opt -S -hexagon-emit-lookup-tables=true -O2 < %s | FileCheck %s -check-prefix=DISABLE
+; RUN: opt -S -hexagon-emit-lookup-tables=false -O2 < %s | FileCheck %s -check-prefix=DISABLE
+; The attribute "no-lookup-table"="true" disables the generation of switch generated lookup tables
+
+; DISABLE-NOT: @{{.*}} = private unnamed_addr constant [6 x i32] [i32 9, i32 20, i32 14, i32 22, i32 12, i32 5]
+
+target datalayout = "e-m:e-p:32:32:32-a:0-n16:32-i64:64:64-i32:32:32-i16:16:16-i1:8:8-f32:32:32-f64:64:64-v32:32:32-v64:64:64-v512:512:512-v1024:1024:1024-v2048:2048:2048"
+target triple = "hexagon-unknown--elf"
+
+; Function Attrs: noinline nounwind
+define i32 @foo(i32 %c) #0 {
+entry:
+  switch i32 %c, label %sw.default [
+    i32 42, label %return
+    i32 43, label %sw.bb1
+    i32 44, label %sw.bb2
+    i32 45, label %sw.bb3
+    i32 46, label %sw.bb4
+    i32 47, label %sw.bb5
+    i32 48, label %sw.bb6
+  ]
+
+sw.bb1: br label %return
+sw.bb2: br label %return
+sw.bb3: br label %return
+sw.bb4: br label %return
+sw.bb5: br label %return
+sw.bb6: br label %return
+sw.default: br label %return
+return:
+  %retval.0 = phi i32 [ 15, %sw.default ], [ 1, %sw.bb6 ], [ 62, %sw.bb5 ], [ 27, %sw.bb4 ], [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
+  ret i32 %retval.0
+}
+
+attributes #0 = { noinline nounwind "no-lookup-tables"="true"}

test/Transforms/SimplifyCFG/disable-lookup-table.ll

+; RUN: opt < %s -latesimplifycfg -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+; In the presence of "-no-lookup-tables"="true", late simplifycfg should not
+; convert any switch cases to lookup tables.
+; CHECK: @switch.table.bar = private unnamed_addr constant [4 x i32] [i32 55, i32 123, i32 0, i32 -1]
+; CHECK-LABEL: foo
+; CHECK-NOT: @switch.table.foo = private unnamed_addr constant [4 x i32] [i32 55, i32 123, i32 0, i32 -1]
+
+define i32 @foo(i32 %c) "no-lookup-tables"="true" {
+entry:
+  switch i32 %c, label %sw.default [
+    i32 42, label %return
+    i32 43, label %sw.bb1
+    i32 44, label %sw.bb2
+    i32 45, label %sw.bb3
+  ]
+
+sw.bb1: br label %return
+sw.bb2: br label %return
+sw.bb3: br label %return
+sw.default: br label %return
+return:
+  %retval.0 = phi i32 [ 15, %sw.default ],  [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
+  ret i32 %retval.0
+}
+
+
+define i32 @bar(i32 %c) {
+entry:
+  switch i32 %c, label %sw.default [
+    i32 42, label %return
+    i32 43, label %sw.bb1
+    i32 44, label %sw.bb2
+    i32 45, label %sw.bb3
+  ]
+
+sw.bb1: br label %return
+sw.bb2: br label %return
+sw.bb3: br label %return
+sw.default: br label %return
+return:
+  %retval.0 = phi i32 [ 15, %sw.default ],  [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
+  ret i32 %retval.0
+}
+