[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Gulfem Savrun Yeniceri via Phabricator via cfe-commits]

gulfem added a comment.

@lebedev.ri based on your feedback, I added it as a separate pass and added 
support for user-defined lookup tables.
Please let me know if you have any comments.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Gulfem Savrun Yeniceri via Phabricator via cfe-commits]

gulfem updated this revision to Diff 324144.
gulfem marked an inline comment as not done.
gulfem added a comment.
Herald added a subscriber: mgorny.

Implement it as a separate pass and apply it to user-defined lookup tables as 
well.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

Files:
  clang/test/CodeGen/switch-to-lookup-table.c
  llvm/docs/Passes.rst
  llvm/include/llvm/InitializePasses.h
  llvm/include/llvm/Transforms/Scalar.h
  llvm/include/llvm/Transforms/Utils/RelLookupTableGenerator.h
  llvm/lib/Passes/PassBuilder.cpp
  llvm/lib/Passes/PassRegistry.def
  llvm/lib/Transforms/IPO/PassManagerBuilder.cpp
  llvm/lib/Transforms/Utils/CMakeLists.txt
  llvm/lib/Transforms/Utils/RelLookupTableGenerator.cpp
  llvm/lib/Transforms/Utils/Utils.cpp
  llvm/test/Other/pass-pipelines.ll
  llvm/test/Transforms/SimplifyCFG/X86/relative_lookup_table.ll
  llvm/utils/gn/secondary/llvm/lib/Transforms/Utils/BUILD.gn

Index: llvm/utils/gn/secondary/llvm/lib/Transforms/Utils/BUILD.gn
===
--- llvm/utils/gn/secondary/llvm/lib/Transforms/Utils/BUILD.gn
+++ llvm/utils/gn/secondary/llvm/lib/Transforms/Utils/BUILD.gn
@@ -60,6 +60,7 @@
 "NameAnonGlobals.cpp",
 "PredicateInfo.cpp",
 "PromoteMemoryToRegister.cpp",
+"RelLookupTableGenerator.cpp"
 "SSAUpdater.cpp",
 "SSAUpdaterBulk.cpp",
 "SampleProfileLoaderBaseUtil.cpp",
Index: llvm/test/Transforms/SimplifyCFG/X86/relative_lookup_table.ll
===
--- /dev/null
+++ llvm/test/Transforms/SimplifyCFG/X86/relative_lookup_table.ll
@@ -0,0 +1,187 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -rel-lookup-table-generator -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+; RUN: opt < %s -passes=rel-lookup-table-generator -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str = private unnamed_addr constant [5 x i8] c"zero\00", align 1
+@.str.1 = private unnamed_addr constant [4 x i8] c"one\00", align 1
+@.str.2 = private unnamed_addr constant [4 x i8] c"two\00", align 1
+@.str.3 = private unnamed_addr constant [8 x i8] c"default\00", align 1
+@.str.4 = private unnamed_addr constant [6 x i8] c"three\00", align 1
+@.str.5 = private unnamed_addr constant [5 x i8] c"str1\00", align 1
+@.str.6 = private unnamed_addr constant [5 x i8] c"str2\00", align 1
+@.str.7 = private unnamed_addr constant [12 x i8] c"singlevalue\00", align 1
+
+@switch.table.string_table = private unnamed_addr constant [3 x i8*]
+ [
+  i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0),
+  i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.1, i64 0, i64 0),
+  i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0)
+ ], align 8
+
+@switch.table.string_table_holes = private unnamed_addr constant [4 x i8*]
+  [
+i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0),
+i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.3, i64 0, i64 0),
+i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0),
+i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str.4, i64 0, i64 0)
+  ], align 8
+
+@switch.table.no_dso_local = private unnamed_addr constant [3 x i32*] [i32* @a, i32* @b, i32* @c], align 8
+
+@switch.table.single_value = private unnamed_addr constant [3 x i8*]
+  [
+i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0),
+i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.1, i64 0, i64 0),
+i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0)
+  ], align 8
+
+; Integer pointer table lookup
+; CHECK: @switch.table.no_dso_local = private unnamed_addr constant [3 x i32*] [i32* @a, i32* @b, i32* @c], align
+
+; Relative string table lookup
+; CHECK: @reltable.string_table = private unnamed_addr constant [3 x i32]
+; CHECK-SAME: [
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([3 x i32]* @reltable.string_table to i64)) to i32),
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.1 to i64), i64 ptrtoint ([3 x i32]* @reltable.string_table to i64)) to i32),
+; CHECK-SAME: i32 trunc (i64 

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Joerg Sonnenberger via Phabricator via cfe-commits]

joerg added a comment.

First of all, I find this patch to be nearly impossible to read. It seems to 
mix a lot of refactoring with a functional change, making it very hard to focus 
on the core.

The main difference to the jump table logic is that the latter knows that all 
referenced addresses are within a function and therefore well contained. 
Nothing of the like seems to be found here. E.g. if this is supposed to address 
only unnamed pointers, it should be grouping them together and compute the 
offsets and then pick the optimal size. That's a transformation that can be 
beneficial for all modes for a not too large table. But it is hard to see what 
is going on here with all the seemingly unrelated changes.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri added a comment.

In D94355#2531504 , @gulfem wrote:

> In D94355#2530225 , @lebedev.ri 
> wrote:
>
>> Can you please add an explanation to the patch's description as to why
>> we don't want to instead convert non-relative/relative LUT's elsewhere,
>> please.
>
> @mcgrathr gave some explanation to that:
>
>>> Many backends generate PIC-friendly jump tables. This is about generating 
>>> IR initializers that translate to the same kind of backend assembly 
>>> expressions as those backends use for their jump tables.
>
> I also want to add to that:
> This task specifically tries make switch-to-lookup tables PIC-friendly, but 
> it does not necessarily try to make all the jump tables PIC-friendly.
> There is also another work going on to generate PIC-friendly vtables.
> Therefore, converting non-relative lookup tables to relative tables elsewhere 
> can be explored as a separate task.

Personally, i read that as non-answer,
because this just reiterates that it can be done elsewhere,
and doesn't answer my question as to why that isn't the path taken.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Gulfem Savrun Yeniceri via Phabricator via cfe-commits]

gulfem marked an inline comment as done.
gulfem added a comment.

In D94355#2530225 , @lebedev.ri wrote:

> Can you please add an explanation to the patch's description as to why
> we don't want to instead convert non-relative/relative LUT's elsewhere,
> please.

@mcgrathr gave some explanation to that:

>> Many backends generate PIC-friendly jump tables. This is about generating IR 
>> initializers that translate to the same kind of backend assembly expressions 
>> as those backends use for their jump tables.

I also want to add to that:
This task specifically tries make switch-to-lookup tables PIC-friendly, but it 
does not necessarily try to make all the jump tables PIC-friendly.
There is also another work going on to generate PIC-friendly vtables.
Therefore, converting non-relative lookup tables to relative tables elsewhere 
can be explored as a separate task.




Comment at: llvm/lib/Transforms/Utils/SimplifyCFG.cpp:5512-5525
+  // If not in x86 or aarch64 mode, do not generate a relative lookup table.
+  Triple TargetTriple(M.getTargetTriple());
+  if (!(TargetTriple.getArch() == Triple::x86_64 ||
+TargetTriple.getArch() == Triple::aarch64))
+return false;
+
+  // If not tiny or small code model, do not generate a relative lookup table.

lebedev.ri wrote:
> This should be some TLI/TTI hook.
> This should be some TLI/TTI hook.
Could you please elaborate on that?
Are you talking about getting the PIC level?



Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri added inline comments.



Comment at: llvm/lib/Transforms/Utils/SimplifyCFG.cpp:5512-5525
+  // If not in x86 or aarch64 mode, do not generate a relative lookup table.
+  Triple TargetTriple(M.getTargetTriple());
+  if (!(TargetTriple.getArch() == Triple::x86_64 ||
+TargetTriple.getArch() == Triple::aarch64))
+return false;
+
+  // If not tiny or small code model, do not generate a relative lookup table.

This should be some TLI/TTI hook.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri added a comment.

Can you please add an explanation to the patch's description as to why
we don't want to instead convert non-relative/relative LUT's elsewhere,
please.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Gulfem Savrun Yeniceri via Phabricator via cfe-commits]

gulfem marked 9 inline comments as done.
gulfem added inline comments.



Comment at: clang/test/CodeGen/switch-to-lookup-table.c:2
+// Check switch to lookup optimization in fPIC and fno-PIC mode
+// RUN: %clang_cc1 %s -triple=aarch64-unknown-fuchsia -O2 -fno-PIC -S 
-emit-llvm -o - | FileCheck %s --check-prefix=CHECK --check-prefix=FNOPIC
+// RUN: %clang_cc1 %s -triple=aarch64-unknown-fuchsia -O2 -fPIC -S -emit-llvm 
-o - | FileCheck %s --check-prefix=CHECK --check-prefix=FPIC

hans wrote:
> Clang codegen tests are not normally used to test LLVM optimizations. I think 
> the tests for this should all live in LLVM, not Clang.
> 
> (Also aarch64 is not guaranteed to be included as a target in the LLVM build, 
> so this test would not necessarily run.)
I'm not able to use -fPIC and -fno-PIC options in the `opt` tool.
I am setting the `PIC Level` flag to enable -fPIC in `opt.
I thought that testing -fPIC and -fno-PIC in the same file seems easier and 
more readable  in CodeGen tests.
Please let me know if you have a good suggestion how to do that with `opt`.

I changed the target to `x86_64-linux` in this test.



Comment at: llvm/lib/Transforms/Utils/SimplifyCFG.cpp:5709
+  return llvm::ConstantExpr::getTrunc(RelOffset,
+  Type::getInt32Ty(M.getContext()));
 }

hans wrote:
> I do worry about hard-coding this to 32 bits. As someone pointed out, it 
> would not necessary hold in all code models for x86.
> 
> Similarly to the PIC check in ShouldBuildRelLookupTable(), is there some 
> check we could do to make sure 32 bits is appropriate?
I added `x86_64` and `aarch64` target check and tiny or small code mode check 
to ensure 32 offsets.
Please let me know if you have any other concerns about that.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Gulfem Savrun Yeniceri via Phabricator via cfe-commits]

gulfem updated this revision to Diff 320025.
gulfem added a comment.

1. Simplified test cases and increased readibility of the tables
2. Added x86_64 and aarch64 check and tiny or small code modes check to ensure 
32 offsets
3. Modified single value test case


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

Files:
  clang/test/CodeGen/switch-to-lookup-table.c
  llvm/lib/Transforms/Utils/SimplifyCFG.cpp
  llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll

Index: llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll
===
--- /dev/null
+++ llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll
@@ -0,0 +1,211 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -simplifycfg -switch-to-lookup=true -keep-loops=false -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+; RUN: opt < %s -passes='simplify-cfg' -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str = private unnamed_addr constant [5 x i8] c"zero\00", align 1
+@.str.1 = private unnamed_addr constant [4 x i8] c"one\00", align 1
+@.str.2 = private unnamed_addr constant [4 x i8] c"two\00", align 1
+@.str.3 = private unnamed_addr constant [8 x i8] c"default\00", align 1
+@.str.4 = private unnamed_addr constant [6 x i8] c"three\00", align 1
+@.str.5 = private unnamed_addr constant [5 x i8] c"str1\00", align 1
+@.str.6 = private unnamed_addr constant [5 x i8] c"str2\00", align 1
+@.str.7 = private unnamed_addr constant [12 x i8] c"singlevalue\00", align 1
+
+; Relative string table lookup
+; CHECK: @switch.reltable.string_table = private unnamed_addr constant [3 x i32]
+; CHECK-SAME: [
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([3 x i32]* @switch.reltable.string_table to i64)) to i32),
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.1 to i64), i64 ptrtoint ([3 x i32]* @switch.reltable.string_table to i64)) to i32),
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.2 to i64), i64 ptrtoint ([3 x i32]* @switch.reltable.string_table to i64)) to i32)
+; CHECK-SAME: ], align 4
+
+; Relative string table lookup that holes are filled with relative offset to default values
+; CHECK: @switch.reltable.string_table_holes = private unnamed_addr constant [4 x i32]
+; CHECK-SAME: [
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([4 x i32]* @switch.reltable.string_table_holes to i64)) to i32),
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([8 x i8]* @.str.3 to i64), i64 ptrtoint ([4 x i32]* @switch.reltable.string_table_holes to i64)) to i32),
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.2 to i64), i64 ptrtoint ([4 x i32]* @switch.reltable.string_table_holes to i64)) to i32),
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.4 to i64), i64 ptrtoint ([4 x i32]* @switch.reltable.string_table_holes to i64)) to i32)
+; CHECK-SAME: ], align 4
+
+; Integer pointer table lookup
+; CHECK: @switch.table.no_dso_local = private unnamed_addr constant [7 x i32*] [i32* @a, i32* @b, i32* @c, i32* @d, i32* @e, i32* @f, i32* @g], align 8
+
+; Single value check
+; CHECK: @switch.reltable.single_value = private unnamed_addr constant [3 x i32]
+; CHECK-SAME: [
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([3 x i32]* @switch.reltable.single_value to i64)) to i32),
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.1 to i64), i64 ptrtoint ([3 x i32]* @switch.reltable.single_value to i64)) to i32),
+; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.2 to i64), i64 ptrtoint ([3 x i32]* @switch.reltable.single_value to i64)) to i32)
+; CHECK-SAME: ], align 4
+
+; Switch used to return a string.
+; Relative lookup table should be generated.
+define i8* @string_table(i32 %cond) {
+  ; CHECK-LABEL: @string_table(
+  ; CHECK-NEXT:  entry:
+  ; CHECK-NEXT:[[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 3
+  ; CHECK-NEXT:br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+  ; CHECK:   switch.lookup:
+  ; CHECK-NEXT:[[SWITCH_RELTABLE_SHIFT:%.*]] = lshr i32 %cond, 2
+  ; CHECK-NEXT:[[SWITCH_RELTABLE_INTRINSIC:%.*]] = call i8* @llvm.load.relative.i32(i8* bitcast ([3 x i32]* @switch.reltable.string_table to i8*), i32 [[SWITCH_RELTABLE_SHIFT]])
+  ; CHECK-NEXT:ret i8* [[SWITCH_RELTABLE_INTRINSIC]]
+  ; CHECK:   return:
+  ; CHECK-NEXT:ret i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.3, i64 0, i64 0)
+entry:
+  switch i32 %cond, label %sw.default [
+i32 0, label %return
+ 

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Hans Wennborg via Phabricator via cfe-commits]

hans added inline comments.



Comment at: clang/test/CodeGen/switch-to-lookup-table.c:2
+// Check switch to lookup optimization in fPIC and fno-PIC mode
+// RUN: %clang_cc1 %s -triple=aarch64-unknown-fuchsia -O2 -fno-PIC -S 
-emit-llvm -o - | FileCheck %s --check-prefix=CHECK --check-prefix=FNOPIC
+// RUN: %clang_cc1 %s -triple=aarch64-unknown-fuchsia -O2 -fPIC -S -emit-llvm 
-o - | FileCheck %s --check-prefix=CHECK --check-prefix=FPIC

Clang codegen tests are not normally used to test LLVM optimizations. I think 
the tests for this should all live in LLVM, not Clang.

(Also aarch64 is not guaranteed to be included as a target in the LLVM build, 
so this test would not necessarily run.)



Comment at: clang/test/CodeGen/switch-to-lookup-table.c:6
+// Switch lookup table
+// FNOPIC: @switch.table.string_table = private unnamed_addr constant [9 x 
i8*] [i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i8* 
getelementptr inbounds ([4 x i8], [4 x i8]* @.str.1, i64 0, i64 0), i8* 
getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0), i8* 
getelementptr inbounds ([6 x i8], [6 x i8]* @.str.3, i64 0, i64 0), i8* 
getelementptr inbounds ([5 x i8], [5 x i8]* @.str.4, i64 0, i64 0), i8* 
getelementptr inbounds ([5 x i8], [5 x i8]* @.str.5, i64 0, i64 0), i8* 
getelementptr inbounds ([4 x i8], [4 x i8]* @.str.6, i64 0, i64 0), i8* 
getelementptr inbounds ([6 x i8], [6 x i8]* @.str.7, i64 0, i64 0), i8* 
getelementptr inbounds ([6 x i8], [6 x i8]* @.str.8, i64 0, i64 0)], align 8
+

This table and the one below are very hard to read like this. Could you split 
it into multiple lines using FNOPIC-SAME?



Comment at: clang/test/CodeGen/switch-to-lookup-table.c:36
+
+  switch (cond) {
+  case 0:

I think the minimum number of cases for the switch-to-lookup table 
transformation is only 4 or 5. To make the test easier to read, I'd suggest 
using the minimum number of cases in the switch.



Comment at: llvm/lib/Transforms/Utils/SimplifyCFG.cpp:5658
+
+// If relative table is generated, initialize the array with the table.
+Constant *Initializer = ConstantArray::get(ArrayTy, TableContents);

This comment seems unnecessary, at this point we know we're generating the 
relative table.



Comment at: llvm/lib/Transforms/Utils/SimplifyCFG.cpp:5695
+if (auto *GlobalVal = dyn_cast(CaseRes))
+  if (!GlobalVal->isDSOLocal())
+return false;

I don't remember, will isDSOLocal() return true also if it's a private or 
internal symbol? Otherwise maybe this should check isLocalLinkage() also.



Comment at: llvm/lib/Transforms/Utils/SimplifyCFG.cpp:5709
+  return llvm::ConstantExpr::getTrunc(RelOffset,
+  Type::getInt32Ty(M.getContext()));
 }

I do worry about hard-coding this to 32 bits. As someone pointed out, it would 
not necessary hold in all code models for x86.

Similarly to the PIC check in ShouldBuildRelLookupTable(), is there some check 
we could do to make sure 32 bits is appropriate?



Comment at: llvm/lib/Transforms/Utils/SimplifyCFG.cpp:5712
 
-Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> ) {
+Value *SwitchLookupTable::BuildLookup(Module , Value *Index, Type *ValueType,
+  IRBuilder<> ) {

The Builder points to a specific insertion point in a basic block for the 
lookup, so it knows the Module and adding the Module parameter is redundant.



Comment at: 
llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll:7
+
+@.str = private unnamed_addr constant [5 x i8] c"zero\00", align 1
+@.str.1 = private unnamed_addr constant [4 x i8] c"one\00", align 1

Same comment as I made for the test under clang/ above: I think fewer switch 
cases are probably enough to test this, and would make it easier to read. Also 
splitting the lookup tables over multiple lines would help too.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Leonard Chan via Phabricator via cfe-commits]

leonardchan added a comment.

Almost there! Just a few more comments on my end.




Comment at: llvm/lib/Transforms/Utils/SimplifyCFG.cpp:5694
+Constant *CaseRes = Values[I].second;
+if (auto *GlobalVal = dyn_cast(CaseRes))
+  if (!GlobalVal->isDSOLocal())

I think we should also return false if it doesn't turn out to be a GlobalValue 
here.



Comment at: 
llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll:201-203
+; If there is a lookup table, where each element contains the same value,
+; a relative lookup should not be generated
+define void @single_value(i32 %cond)  {

It looks like this might not be testing what the comment says it should. It 
looks like in the phi statements below that each of the cases have different 
values. I think maybe you'll want something like:

```
  %str1.0 = phi i8* [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, 
i64 0), %sw.default ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 
0, i64 0), %sw.bb2 ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 
0, i64 0), %sw.bb1 ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 
0, i64 0), %entry ]
  ret i8* %str1.0  ; instead of `ret void` to ensure the `%str1.0` isn't 
optimized out
```

Then ensure this just lowers directly to a GEP for `@.str` and no lookup table 
is generated.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D94355: [SimplifyCFG] Add relative switch lookup tables

[Gulfem Savrun Yeniceri via Phabricator via cfe-commits]

gulfem updated this revision to Diff 318372.
gulfem added a comment.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.

1. Apply relative lookup table generation in fPIC mode
2. Add a test case for single value case
3. Remove hard-coding 64 bit pointers
4. Improve implementation and test coverage


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D94355/new/

https://reviews.llvm.org/D94355

Files:
  clang/test/CodeGen/switch-to-lookup-table.c
  llvm/lib/Transforms/Utils/SimplifyCFG.cpp
  llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll

Index: llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll
===
--- /dev/null
+++ llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll
@@ -0,0 +1,239 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -simplifycfg -switch-to-lookup=true -keep-loops=false -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+; RUN: opt < %s -passes='simplify-cfg' -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str = private unnamed_addr constant [5 x i8] c"zero\00", align 1
+@.str.1 = private unnamed_addr constant [4 x i8] c"one\00", align 1
+@.str.2 = private unnamed_addr constant [4 x i8] c"two\00", align 1
+@.str.3 = private unnamed_addr constant [6 x i8] c"three\00", align 1
+@.str.4 = private unnamed_addr constant [5 x i8] c"four\00", align 1
+@.str.5 = private unnamed_addr constant [5 x i8] c"five\00", align 1
+@.str.6 = private unnamed_addr constant [4 x i8] c"six\00", align 1
+@.str.7 = private unnamed_addr constant [6 x i8] c"seven\00", align 1
+@.str.8 = private unnamed_addr constant [6 x i8] c"eight\00", align 1
+@.str.9 = private unnamed_addr constant [8 x i8] c"default\00", align 1
+@.str.10 = private unnamed_addr constant [12 x i8] c"singlevalue\00", align 1
+@.str.11 = private unnamed_addr constant [9 x i8] c"default1\00", align 1
+@.str.12 = private unnamed_addr constant [9 x i8] c"default2\00", align 1
+; Relative string table lookup
+; CHECK: @switch.reltable.string_table = private unnamed_addr constant [9 x i32] [i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.1 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.2 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.3 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.4 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.5 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.6 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.7 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.8 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32)], align 4
+
+; Relative string table lookup that holes are filled with relative offset to default values
+; CHECK: @switch.reltable.string_table_holes = private unnamed_addr constant [9 x i32] [i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([8 x i8]* @.str.9 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.2 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.3 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.4 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.5 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([8 x i8]* @.str.9 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.7 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]*