Add support for no-jump-tables

[niravd]

Summary

Add function attribute to represent the avoidance of generation of jump tables.
This is an initial step to supporting gcc's -fno-jump-tables flag.

[hans]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

7978

There is already a helper function in this file that decides whether or not to build jump tables: areJTsAllowed(). That's a better place to do this check.

If we really want to disable jump tables, maybe the proper thing to do is to make TLI.isOperationLegalOrCustom(BR_JT) return false. I don't know if that's more or less convenient to do, though.

[niravd]

Rebased no-jump-tables to key on Function Attributes not target options and removed
added llc command line flag as we can now pass this information textually in the file

[mehdi_amini]

Code look straightforward. Using a function attribute looks good to me. See a nit below.

test/CodeGen/X86/switch.ll

46

Update comment: Should never be lowered as a jump table because of the attribute.

[niravd]

Comment added to switch.ll

[hans]

I missed where someone suggested making this a function attribute.

What's the motivation for wanting some functions to get jump tables, and not others? Isn't it something you'd want for the whole program?

What happens if a function with nousejumptable gets inlined into a function without the attribute?

[echristo]

So having it as a function attribute was my idea :)

Otherwise, it's a good question. What should happen in LTO when you ask for one translation unit to be compiled without jump table support and the other one to be compiled with jump table support? Which one wins here? For some things it's more obvious, I'm not sure here.

-eric

[hans]

In D18321#381998, @echristo wrote:

So having it as a function attribute was my idea :)

Otherwise, it's a good question. What should happen in LTO when you ask for one translation unit to be compiled without jump table support and the other one to be compiled with jump table support? Which one wins here? For some things it's more obvious, I'm not sure here.

I suppose it depends on the motivation for this patch. Why would one be compiling with -no-jump-tables? Is it just an optimization thing, or could there be a situation where a jump table would actually not work, despite the target supporting it in general? (Apologies if this is obvious, but it would be great to have it explained in the description of this patch.)

[echristo]

I don't know either so I'm somewhat curious myself :)

-eric

[mehdi_amini]

The GCC doc for the option is:

[echristo]

OK, sounds like it should poison on inlining then. (And likely is going to be used everywhere, but maximum safety here).

[niravd]

Make no-jump-tables soft attribute as suggested in D18407 and union merged no-jump-tables flags on inline

[niravd]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

7978

Realized I hadn't addressed this. This was probably the right thing originally, but isn't possible now that no-jump-tables is a function attribute.

[hans]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

7978

Please make areJTsAllowed() take a Function* parameter and do the check there instead. That way, the code will not waste time in findJumpTables() only to decide later to not build any.

[hans]

Please make areJTsAllowed() take a Function* parameter and do the check there instead. That way, the code will not waste time in findJumpTables() only to decide later to not build any.

[niravd]

Move no-jump-tables code into areJTsAllowed

[niravd]

Apply clang-format

[mehdi_amini]

test/Transforms/Inline/attributes.ll

246

Why are you killing the noimplicitfloat test?

[niravd]

test/Transforms/Inline/attributes.ll

246

That's a good question. This was copied over at one point. I must have botched a rebase. Will fix.

[niravd]

Fix test.

[hans]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

7961

I don't think the comment adds value here; it's very clear that this is what the code below does.

7962

The variable should be named Fn.

7964

Would just

if (Fn->getFnAttribute("no-jump-tables").getValueAsString() == "true")

work?

[niravd]

Cleanup FnAttr lookup

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

7964

It does. There are a few more instances of this pattern in the codebase. I'll submit those separately.

[hans]

Thanks! This looks good to me.

include/llvm/IR/Attributes.td

 /// Zero extended before/after call.
 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">;
 
 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.
class MergeRule<string F> {
   string MergeFunc = F;
 }
 
 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<"adjustCallerSSPLevel">;

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

uint64_t NumCases =
       TotalCases[Last] - (First == 0 ? 0 : TotalCases[First - 1]);
 
   assert(NumCases < UINT64_MAX / 100);
   assert(Range >= NumCases);
 
   return NumCases * 100 >= Range * Density;
 }
 
-static inline bool areJTsAllowed(const TargetLowering &TLI) {
+static inline bool areJTsAllowed(const TargetLowering &TLI,
+                                 const SwitchInst *SI) {
+  // return false if function containing SI has NoUseJumpTable Attribute set
+  const Function *fn = SI->getParent()->getParent();
+  if (fn->hasFnAttribute("no-jump-tables") &&
+      fn->getFnAttribute("no-jump-tables").getValueAsString() == "true")
+    return false;
+
   return TLI.isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) ||
          TLI.isOperationLegalOrCustom(ISD::BRIND, MVT::Other);
 }
 
 bool SelectionDAGBuilder::buildJumpTable(CaseClusterVector &Clusters,
                                          unsigned First, unsigned Last,
                                          const SwitchInst *SI,
                                          MachineBasicBlock *DefaultMBB,
                                          CaseCluster &JTCluster) {
   assert(First <= Last);
 
   auto Prob = BranchProbability::getZero();
   unsigned NumCmps = 0;
   std::vector<MachineBasicBlock*> Table;
   DenseMap<MachineBasicBlock*, BranchProbability> JTProbs;
 
   // Initialize probabilities in JTProbs.
   for (unsigned I = First; I <= Last; ++I)
     JTProbs[Clusters[I].MBB] = BranchProbability::getZero();
 
#ifndef NDEBUG
   assert(!Clusters.empty());
   for (CaseCluster &C : Clusters)
     assert(C.Kind == CC_Range);
   for (unsigned i = 1, e = Clusters.size(); i < e; ++i)
     assert(Clusters[i - 1].High->getValue().slt(Clusters[i].Low->getValue()));
 #endif
 
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
-  if (!areJTsAllowed(TLI))
+  if (!areJTsAllowed(TLI, SI))
     return;
 
   const int64_t N = Clusters.size();
   const unsigned MinJumpTableSize = TLI.getMinimumJumpTableEntries();
 
   // TotalCases[i]: Total nbr of cases in Clusters[0..i].
   SmallVector<unsigned, 8> TotalCases(N);
 

test/CodeGen/X86/switch.ll

 ; NOOPT-LABEL: basic
 ; NOOPT: decl
 ; NOOPT: subl $4
 ; NOOPT: ja
 ; NOOPT: movq .LJTI
 ; NOOPT: jmpq
 }
 
+; Should never be lowered as a jump table because of the attribute
+define void @basic_nojumptable(i32 %x) "no-jump-tables"="true" {
+entry:
+  switch i32 %x, label %return [
+    i32 3, label %bb0
+    i32 1, label %bb1
+    i32 4, label %bb1
+    i32 5, label %bb2
+  ]
+bb0: tail call void @g(i32 0) br label %return
+bb1: tail call void @g(i32 1) br label %return
+bb2: tail call void @g(i32 1) br label %return
+return: ret void
+
+; Lowered as a jump table, both with and without optimization.
+; CHECK-LABEL: basic_nojumptable
+; CHECK-NOT: jmpq *.LJTI
+}
+
+; Should be lowered as a jump table because of the attribute
+define void @basic_nojumptable_false(i32 %x) "no-jump-tables"="false" {
+entry:
+  switch i32 %x, label %return [
+    i32 3, label %bb0
+    i32 1, label %bb1
+    i32 4, label %bb1
+    i32 5, label %bb2
+  ]
+bb0: tail call void @g(i32 0) br label %return
+bb1: tail call void @g(i32 1) br label %return
+bb2: tail call void @g(i32 1) br label %return
+return: ret void
+
+; Lowered as a jump table, both with and without optimization.
+; CHECK-LABEL: basic_nojumptable_false
+; CHECK: decl
+; CHECK: cmpl $4
+; CHECK: ja
+; CHECK: jmpq *.LJTI
+}
+
 
 define void @simple_ranges(i32 %x) {
 entry:
   switch i32 %x, label %return [
     i32 0, label %bb0
     i32 1, label %bb0
     i32 2, label %bb0
     i32 3, label %bb0
     i32 100, label %bb1
     i32 101, label %bb1
     i32 102, label %bb1
     i32 103, label %bb1
   ]
 bb0: tail call void @g(i32 0) br label %return
 bb1: tail call void @g(i32 1) br label %return
 return: ret void
 
+
+
 ; Should be lowered to two range checks.
 ; CHECK-LABEL: simple_ranges
 ; CHECK: leal -100
 ; CHECK: cmpl $4
 ; CHECK: jb
 ; CHECK: cmpl $3
 ; CHECK: ja
 

test/Transforms/Inline/attributes.ll

 
 define i32 @test_no-implicit-float3(i32 %i) noimplicitfloat {
   %1 = call i32 @no-implicit-float_callee1(i32 %i)
   ret i32 %1
 ; CHECK: @test_no-implicit-float3(i32 %i) [[NOIMPLICITFLOAT]] {
 ; CHECK-NEXT: ret i32
 }
 
+; Check that no-jump-tables flag propagates from inlined callee to caller 
+
+define i32 @no-use-jump-tables_callee0(i32 %i) {
+  ret i32 %i
+; CHECK: @no-use-jump-tables_callee0(i32 %i) {
+; CHECK-NEXT: ret i32
+}
+
+define i32 @no-use-jump-tables_callee1(i32 %i) "no-jump-tables"="true" {
+  ret i32 %i
+; CHECK: @no-use-jump-tables_callee1(i32 %i) [[NOUSEJUMPTABLES:#[0-9]+]] {
+; CHECK-NEXT: ret i32
+}
+
+define i32 @test_no-use-jump-tables0(i32 %i) {
+  %1 = call i32 @no-use-jump-tables_callee0(i32 %i)
+  ret i32 %1
+; CHECK: @test_no-use-jump-tables0(i32 %i) {
+; CHECK-NEXT: ret i32
+}
+
+define i32 @test_no-use-jump-tables1(i32 %i) {
+  %1 = call i32 @no-use-jump-tables_callee1(i32 %i)
+  ret i32 %1
+; CHECK: @test_no-use-jump-tables1(i32 %i) [[NOUSEJUMPTABLES]] {
+; CHECK-NEXT: ret i32
+}
+
+define i32 @test_no-use-jump-tables2(i32 %i) "no-jump-tables"="true" {
+  %1 = call i32 @no-use-jump-tables_callee0(i32 %i)
+  ret i32 %1
+; CHECK: @test_no-use-jump-tables2(i32 %i) [[NOUSEJUMPTABLES]] {
+; CHECK-NEXT: ret i32
+}
+
+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: 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" }
 No newline at end of file