This is an archive of the discontinued LLVM Phabricator instance.

TableGen support for parameterized register class information
ClosedPublic

Authored by kparzysz on Apr 11 2017, 10:55 AM.

Details

Summary

This is the patch that implements the majority of the parameterized register class information. Most of it is related to type inference in TableGen and to the generation of instruction selection matchers and register class information.

Motivation

The main idea here is to implement register classes where the register size (also spill alignment, etc.) may not be known at the execution time of TableGen. This happens on architectures where the register size is a configurable parameter. And example of that could be the HVX coprocessor on Hexagon: it has two modes, one where the registers are 64 bytes long and one with 128 byte registers. The instruction sets and their encodings for both modes are identical, however since RegisterClass has a fixed size, and a fixed set of value types, two separate register classes are needed to represent the registers in the two modes. This, in turn, requires two separate instruction sets to be defined (and handled) internally by the compiler, which is an unnecessary duplication.

Overview

This patch introduces the concept of a "hardware mode", i.e. HwMode, which serves a similar role to a predicate. A HwMode is defined via a list of target features, which will be checked to determine whether a given hardware mode is active. This check will happen not at the run time of TableGen, but at the run time of the compiler, when the compilation target is known.
TableGen will generate code to perform these checks. There is also a "default" mode, which is active is no other mode is active.

For backends that do not use this feature, the "default" mode will be the only mode. The existence of that mode is mostly transparent (limited to TableGen internals), and requires no changes to these backends.

Within TableGen, information that depends on HwMode is a map of values, where HwMode is the key. One example of that is ValueTypeByHwMode, which is a ValueType dependent on HwMode. For defining register classes, there is RegSizeInfoByHwMode, which associates register size, spill size and alignment, and the set of legal value types with each HwMode. For use with maps, the HwMode is stored as an unsigned value, where 0 represents the default mode.

NOTE: the set-theoretical lattice of register classes must remain the same regardless of HwMode. In other words, if class B is a subclass of class A in one mode, B must be a subclass of A in each mode. The reason for that is that the lattice structure is used to generate class information that is not parameterizable without a major overhaul.

Type inference

This parameterization of value types for a register class lead to the necessity of having a new type inference that can deal with sets of parameterized value types. Internally, instead of keeping track of a set of individual parameterized value type, type inference has a map (keyed by HwMode) of sets of non-parameterized value types. Type inference succeeds when for each HwMode, the corresponding set has at most one value type in it, and there exists a non-empty set in the map. Allowing empty sets for some HwModes is motivated by intrinsics: argument types of intrinsics are exposed to the front-end (clang), and so they cannot be parameterized (without making this a clang-wide project). An empty set of value types for a particular mode implies that the given intrinsic is not valid for a particular mode.

At the end of type inference, each pattern tree node has a map of value types associated with it. The next step is to generate instruction selection matchers. The feature sets defining each HwMode are used to create selection Predicates, and each pattern tree with parameterized types at each node is replicated into a set of trees, one for each HwMode, where the value types at each node are no longer parameterized individually. For each such pattern tree, a selection Predicate is associated with it, and at this point the existing matcher generating code is used.

Register class information

The register class information is generated as an array of blocks, one block for each HwMode. Each block contains whatever information depends on the HwMode. At the compiler run time, the TargetRegisterInfo's query functions (such as getRegisterSizeInBits) will obtain the active mode, use it as an index into the array of blocks, and return the information from the appropriate block.

Interaction with FastISel and GlobalISel

Both FastISel and GlobalISel can only be used when the parameterized register classes are not used by a given target. This is not an inherent limitation, it's just that non-trivial changes would be needed for them to accommodate the support for parameterization.

Diff Detail

Repository
rL LLVM

Event Timeline

kparzysz created this revision.Apr 11 2017, 10:55 AM

Each HW mode is defined via a set of subtarget features (that need to be either enabled or disabled). Since the mode serves as a predicate for the generated patterns, the check for subtarget features has to take place in the same context as Predicate checks for the usual pattern predicated. This context is the SelectionDAGISel, and to facilitate the feature check, the generated code calls a function "TargetSubtargetInfo::checkFeatures", which takes a feature string and returns a boolean value.

There is another patch on the way that implements the "checkFeatures" function in subtarget.

I don't like some of the names I used, but I didn't want to spend time thinking about the best possible names. For example anything that starts with "Variable..." should probably have a better name. The RegisterClass member VRI (in Target.td) should likely have a more descriptive name too.

asb edited edge metadata.Apr 20 2017, 4:59 AM

Phew, this is a monster patch to review but clearly there's no real way it could be reduced further. I have no real experience with the TableGen implementation, which limits my ability to contribute to this code review. I have at least carefully read through the code to try to spot any obvious logic errors or issues.

One question I'd welcome a second opinion on - is the introduction of the vi:: namespace justified?

utils/TableGen/CodeGenDAGPatterns.cpp
495 ↗(On Diff #94857)

Is it worth having a more meaningful error message for these? Maybe "Set unexpectedly empty (ref 2a)"?

In D31951#731960, @asb wrote:

One question I'd welcome a second opinion on - is the introduction of the vi:: namespace justified?

Justified? Good question. I added some common functions at the top level in VariableValueType.h, and I didn't want to pollute the global name space with them, or at least wanted to make it clearer what these functions are related to. I'm not convinced that this is an elegant solution, and I'm open to other suggestions.

Thank you for taking time to review all these patches!

utils/TableGen/CodeGenDAGPatterns.cpp
495 ↗(On Diff #94857)

Certainly. I will change it to something better, or at least less cryptic. Same for the other cases in this function.

As a part of changing the type inference, I planned on generating meaningful error messages (with optional traces of what steps have been taken), but that would require more refactoring that was not directly related to the goals of this patch. For this work I didn't spend too much time on the error reporting, as illustrated by this example.

In D31951#731960, @asb wrote:

One question I'd welcome a second opinion on - is the introduction of the vi:: namespace justified?

Justified? Good question. I added some common functions at the top level in VariableValueType.h, and I didn't want to pollute the global name space with them, or at least wanted to make it clearer what these functions are related to. I'm not convinced that this is an elegant solution, and I'm open to other suggestions.

Thank you for taking time to review all these patches!

sdardis edited edge metadata.May 24 2017, 10:51 AM

Hi Krzysztof,

I'll try and dedicate some time this week and next week to looking at this.

Thanks,
Simon

Hi Krzysztof,

I've gone over this patch and I am in broad agreement with it.

My biggest concern is how we need to have HwModes and ValueTypes & RegInfos as two equally long lists, we should have compile time checks for this.

The nits I see are assertions without error strings, new files lacking the standard header, also the error messages for type inferencing.

I will examine this patch more over the next week or two.

Thanks for doing this,
Simon

include/llvm/Target/Target.td
55 ↗(On Diff #94857)

See my comment on utils/TableGen/CodeGenHwModes.cpp about how I believe we should enforce this.

69 ↗(On Diff #94857)

Likewise.

208 ↗(On Diff #94857)

Tinsy nit: I think you should reuse the comment from line 66 here, or work "hw mode" into the comment.

sdardis added inline comments.Jun 1 2017, 7:24 AM
utils/TableGen/CodeGenDAGPatterns.cpp
85 ↗(On Diff #94857)

This needs an error string.

295 ↗(On Diff #94857)

Needs an error string.

938–946 ↗(On Diff #94857)

Should we ensure the old constraint that the check string has some notion of a canonical order?

utils/TableGen/CodeGenDAGPatterns.h
682 ↗(On Diff #94857)

This could do with a comment documenting it's purpose.

utils/TableGen/CodeGenHwModes.cpp
1 ↗(On Diff #94857)

Requires LLVM's standard header.

22–23 ↗(On Diff #94857)

I think this check should be promoted to report_fatal_error--rather than an assert--with a location of the problematic record if possible.

utils/TableGen/CodeGenHwModes.h
1 ↗(On Diff #94857)

Requires LLVM's standard header.

kparzysz marked 10 inline comments as done.Jun 2 2017, 7:42 AM
kparzysz updated this revision to Diff 101210.Jun 2 2017, 7:44 AM

Addressed all the comments, in particular:

  • added more informative diagnostic for matching list sizes, plus a testcase,
  • improved type inference error messages,
  • added sorting of Predicate objects.
kparzysz updated this revision to Diff 101215.Jun 2 2017, 8:00 AM

Two small changes:

  • removed an outdated comment,
  • removed the static version of getPredicateCheck (moved the body back into the PatternToMatch class).
reames resigned from this revision.Jun 22 2017, 2:05 PM

Hi Krzysztof,

I haven't forgotten about this patch, I'm currently on and off looking at this and testing it for MIPS.

Another round of comments.

Thanks,
Simon

utils/TableGen/CodeGenDAGPatterns.cpp
235–237 ↗(On Diff #101215)

Mark this method as LLVM_DUMP_METHOD - see include/llvm/Support/Compiler.h.

292 ↗(On Diff #101215)

contradition -> contradiction.

620 ↗(On Diff #101215)

Comment needed here.

utils/TableGen/CodeGenHwModes.cpp
1 ↗(On Diff #94857)

C++ tag required here too.

utils/TableGen/CodeGenHwModes.h
1 ↗(On Diff #94857)

Requires C++ tag.

utils/TableGen/CodeGenRegisters.cpp
728 ↗(On Diff #101215)

Requires an error string.

utils/TableGen/FastISelEmitter.cpp
164 ↗(On Diff #101215)

Error string required here.

utils/TableGen/RegisterInfoEmitter.cpp
1209–1210 ↗(On Diff #101215)

Can you commit this separately?

1274–1275 ↗(On Diff #101215)

Can you commit this separately?

utils/TableGen/VariableValueType.cpp
40 ↗(On Diff #101215)

Needs an error string.

51 ↗(On Diff #101215)

Needs an error string.

98 ↗(On Diff #101215)

Needs standard LLVM_DUMP_METHOD wrapping.

utils/TableGen/VariableValueType.h
9 ↗(On Diff #101215)

Needs documentation describing purpose.

kparzysz marked 13 inline comments as done.Jun 28 2017, 1:24 PM
kparzysz added a reviewer: dsanders.

Adding Daniel as a reviewer, since his work on GlobalISel is touching some common parts...

kparzysz updated this revision to Diff 104498.Jun 28 2017, 1:27 PM

Addressed the comments from the previous round.

niosHD added a subscriber: niosHD.Jul 11 2017, 12:53 AM
theraven edited edge metadata.Aug 10 2017, 3:23 AM

Looking forward to this landing, as we currently have some horrible #ifdefs to support different register sizes. We also currently have a *really* ugly hack that allows intrinsics that take iPTR to map to multiple types. I wonder if the same infrastructure could be used to allow iPTR to map to multiple types depending on address space?

Intrinsics are not handled here because their types are exposed to outside of TableGen, specifically to the front-end. We have two sets of HVX intrinsics on Hexagon, one for 64-byte and one for 128-byte mode, and they are not going away. The rest of clang/LLVM would need to be changed to deal with that. I've tried to handle intrinsics too, but quickly realized that it wouldn't be possible to have that done within the scope of TableGen.

I think that iPTR with different addressing modes could be handled by TableGen. It would probably not fall under this infrastructure, and could actually be simpler. All we need is to be able to annotate iPTR with the address space somehow, treating the unannotated iPTR as if it had the default address space.

kparzysz updated this revision to Diff 110807.Aug 11 2017, 1:55 PM

Changed the type/variable names to something I find more accurate.

Removed the namespace vi.

I think the code is in its final shape and ready to go in.

kparzysz edited the summary of this revision. (Show Details)Aug 29 2017, 7:18 AM
asb accepted this revision.Sep 7 2017, 1:10 PM

I'm adding my accept to this. I carefully reviewed the details of the code once it was first posted (see earlier comments), and believe this is a valuable improvement. There are others on the review list with more TableGen who may be better placed to comment on the high level design decisions. If somebody else with more TableGen insight (e.g. @sdardis, @MatzeB) can add their LGTM I think this is ready to go on.

It's worth also noting that this change has had a public RFC back in September http://lists.llvm.org/pipermail/llvm-dev/2016-September/105027.html

This revision is now accepted and ready to land.Sep 7 2017, 1:10 PM
sdardis accepted this revision.Sep 12 2017, 4:40 AM

Adding my LGTM to this, I'm not seeing any major issues. Please see my inline comments, there's a number of changes that can be pulled out of this patch and committed separately as they're formatting changes.

You have two NFC changes in this patch which change commented out or #ifdef 0'd code. Looking at the history of that code suggests they have been unused for over 5 years, and should probably be removed.

Can you follow-up this work by improving the error messages from type inferencing failures? Ideally we should always be highlighting the problematic record.

Finally can you wait a day or two before committing this to allow anyone else to comment?

Thanks for doing this.

Simon

include/llvm/Target/Target.td
59 ↗(On Diff #113075)

"A class representing the register size, spill size and spill alignment in bits of a register."

I think it is worth repeating the fact that the values here measure the size in bits, it hit me when I was testing for MIPS.

66 ↗(On Diff #113075)

parametrized -> parameterized.

208 ↗(On Diff #113075)

parametrized -> parameterized.

include/llvm/Target/TargetRegisterInfo.h
323 ↗(On Diff #113075)

"Return the minimum required alignment in bytes for a spill slot for a register of this class."

This can be committed separately.

338 ↗(On Diff #113075)

Replace the double slash here with a triple slash.

This can be committed separately.

test/TableGen/HwModeSelect.td
2 ↗(On Diff #113075)

Add a single sentence describing the purpose of this test.

utils/TableGen/CodeGenDAGPatterns.cpp
61 ↗(On Diff #113075)

parametrized -> parameterized.

708–711 ↗(On Diff #113075)

Comment needs updating to match the function declaration.

1813 ↗(On Diff #113075)

Restore this comment.

2103–2109 ↗(On Diff #113075)

Aside: it appears this code has been commented out since rL98534. I suspect that hunk could be completely removed as a separate commit.

2537 ↗(On Diff #113075)

parametrized -> parameterized.

3265–3266 ↗(On Diff #113075)

This can be committed separately.

3807 ↗(On Diff #113075)

Full stop at the end of the sentence.

3820 ↗(On Diff #113075)

Full stop at the end of the sentence.

3831 ↗(On Diff #113075)

: -> .

3832 ↗(On Diff #113075)

Requires LLVM_DUMP_METHOD.

utils/TableGen/CodeGenDAGPatterns.h
62 ↗(On Diff #113075)

Whitespace consistency: Add a blank line before this function declaration.

99–130 ↗(On Diff #113075)

Can you restore the comments that these functions had and document the new functions?

691 ↗(On Diff #113075)

This assert needs an error string.

697 ↗(On Diff #113075)

Return a string which contains the predicates for instruction selection. (or similar).

This comment should be a comment above the function as it describes the function's purpose. The comment below can stay in the function's scope as it's an implementation detail.

776–777 ↗(On Diff #113075)

This formatting change can be committed separately.

utils/TableGen/CodeGenHwModes.cpp
27 ↗(On Diff #113075)

Requires LLVM_DUMP_METHOD.

46 ↗(On Diff #113075)

Requires LLVM_DUMP_METHOD.

82 ↗(On Diff #113075)

Requires an error string.

88 ↗(On Diff #113075)

Requires an error string.

92 ↗(On Diff #113075)

Requires LLVM_DUM_METHOD.

utils/TableGen/CodeGenHwModes.h
9 ↗(On Diff #113075)

Full stop at the end of the sentence.

49 ↗(On Diff #113075)

Requires an error string.

utils/TableGen/DAGISelMatcherGen.cpp
45 ↗(On Diff #113075)

This requires an error string.

utils/TableGen/FastISelEmitter.cpp
221–223 ↗(On Diff #113075)

This has been commented out since rL129691 and can probably be removed in a separate commit.

utils/TableGen/InfoByHwMode.cpp
9 ↗(On Diff #113075)

parametrized -> parameterized and the two occurrences below.

112–115 ↗(On Diff #113075)

Is this debugging code left over from development?

116 ↗(On Diff #113075)

Requires an error string.

utils/TableGen/InfoByHwMode.h
10 ↗(On Diff #113075)

parametrized -> parameterized. And below too.

131 ↗(On Diff #113075)

Unnecessary blank line.

kparzysz marked 34 inline comments as done.Sep 12 2017, 11:11 AM
kparzysz added inline comments.
utils/TableGen/InfoByHwMode.cpp
112–115 ↗(On Diff #113075)

No, this is actually intended to show which record caused the problem. Since it shows information that is internal to TableGen, it's disabled in a release build (as it's probably of little value to people other than compiler developers).

kparzysz updated this revision to Diff 114867.Sep 12 2017, 11:14 AM
kparzysz retitled this revision from TableGen support for parametrized register class information to TableGen support for parameterized register class information.
kparzysz edited the summary of this revision. (Show Details)

Addressed Simon's comments.

This revision was automatically updated to reflect the committed changes.

Please see https://bugs.llvm.org/show_bug.cgi?id=28222#c20 for a discussion of the performance implications of this patch. TL;DR - This has introduced a severe performance regression in tblgen (on the order of 4x slowdown) even for architectures such as X86 which according to the patch description should not be affected by this change.

Unless some algorithmic fix can be found relatively quickly, I'd like to open the possibility of reverting this patch until it can be re-worked to have more desirable performance characteristics, or at the very least be limited only to specific architectures.

rnk added a subscriber: rnk.Sep 18 2017, 10:24 AM

Please see https://bugs.llvm.org/show_bug.cgi?id=28222#c20 for a discussion of the performance implications of this patch. TL;DR - This has introduced a severe performance regression in tblgen (on the order of 4x slowdown) even for architectures such as X86 which according to the patch description should not be affected by this change.

Unless some algorithmic fix can be found relatively quickly, I'd like to open the possibility of reverting this patch until it can be re-worked to have more desirable performance characteristics, or at the very least be limited only to specific architectures.

+1, a 4x runtime regression in tablegen isn't acceptable, and is something that definitely should've been caught before hand.

rengolin edited edge metadata.Sep 18 2017, 10:42 AM
In D31951#873924, @rnk wrote:

+1, a 4x runtime regression in tablegen isn't acceptable, and is something that definitely should've been caught before hand.

+1. Ditto.