RFC: Absolute or "fixed address" symbols as immediate operands

Project Infrastructure LLVM Dev List Archives
#1

Hi all,

I wanted to summarise some discussion on llvm-commits [0,1] as an RFC, as I felt it demanded wider circulation.

Our support for references to absolute symbols is not very good. The symbol will be resolved accurately in non-PIC code, but suboptimally: the symbol reference cannot currently appear as the immediate operand of an instruction, and the code generator cannot make any assumptions about the value of the symbol (so for example, it could not use a R_X86_64_8 relocation if the value is known to be in the range 0…255).

In PIC mode, if the reference is not known to be DSO-local, the value is loaded from the GOT (or a synthetic GOT entry), which again means suboptimal code. If the reference is known to be DSO-local, the symbol will be referenced with a PC relative relocation and therefore cannot be resolved properly to an absolute value (c.f. https://reviews.llvm.org/D19844). The latter case in particular would seem to indicate that a representational change is required for correctness to distinguish references to absolute symbols from references to regular symbols.

The specific change I have in mind is to allow !range metadata on GlobalObjects. This would
be similar to existing !range metadata, but it would apply to the “address” of the attached GlobalObject, rather than any value loaded from it. Its presence on a GlobalObject would also imply that the address of the GlobalObject is “fixed” at link time. Alongside !range we could potentially use other sources of information, such as the relocation model, code model and visibility, to identify “fixed” globals, although that can be done separately.

I have been experimenting with a number of approaches to representation in SDAG, and I have found one that seems to work best, and would be the least intrusive (unfortunately most approaches to this problem are somewhat intrusive).

Specifically, I want to:

  1. move most of the body of ConstantSDNode to a new class, ConstantIntSDNode, which would derives from ConstantSDNode. ConstantSDNode would act as the base class for immediates-post-static-linking. Change most references to ConstantSDNode in C++ code to refer to ConstantIntSDNode. However, “imm” in tblgen code would continue to match ConstantSDNode.
  2. introduce a new derived class of ConstantSDNode for references to globals with !range metadata, and teach SDAG to use this new derived class for fixed address references

I will shortly be sending out a patch that implements 1.

Thanks,

#2

Hi all,

I wanted to summarise some discussion on llvm-commits [0,1] as an RFC, as I felt it demanded wider circulation.

Our support for references to absolute symbols is not very good. The symbol will be resolved accurately in non-PIC code, but suboptimally: the symbol reference cannot currently appear as the immediate operand of an instruction, and the code generator cannot make any assumptions about the value of the symbol (so for example, it could not use a R_X86_64_8 relocation if the value is known to be in the range 0…255).

In PIC mode, if the reference is not known to be DSO-local, the value is loaded from the GOT (or a synthetic GOT entry), which again means suboptimal code. If the reference is known to be DSO-local, the symbol will be referenced with a PC relative relocation and therefore cannot be resolved properly to an absolute value (c.f. https://reviews.llvm.org/D19844). The latter case in particular would seem to indicate that a representational change is required for correctness to distinguish references to absolute symbols from references to regular symbols.

The specific change I have in mind is to allow !range metadata on GlobalObjects. This would
be similar to existing !range metadata, but it would apply to the “address” of the attached GlobalObject, rather than any value loaded from it. Its presence on a GlobalObject would also imply that the address of the GlobalObject is “fixed” at link time. Alongside !range we could potentially use other sources of information, such as the relocation model, code model and visibility, to identify “fixed” globals, although that can be done separately.

Ok, I think I understand the use-case.

I have been experimenting with a number of approaches to representation in SDAG, and I have found one that seems to work best, and would be the least intrusive (unfortunately most approaches to this problem are somewhat intrusive).

Specifically, I want to:

  1. move most of the body of ConstantSDNode to a new class, ConstantIntSDNode, which would derives from ConstantSDNode. ConstantSDNode would act as the base class for immediates-post-static-linking. Change most references to ConstantSDNode in C++ code to refer to ConstantIntSDNode. However, “imm” in tblgen code would continue to match ConstantSDNode.
  2. introduce a new derived class of ConstantSDNode for references to globals with !range metadata, and teach SDAG to use this new derived class for fixed address references

ConstantSDNode is poorly named, and renaming it to ConstantIntSDNode is probably the right thing to do independently of the other changes.

That said, I don’t understand why you’d keep ConstantSDNode around and introduce a new derived class of it. This seems like something that a new “imm" immediate matcher would handle: it would match constants in a certain range, or a GlobalAddressSDNode known-to-be-small.

-Chris

#3

Hi all,

I wanted to summarise some discussion on llvm-commits [0,1] as an RFC, as
I felt it demanded wider circulation.

Our support for references to absolute symbols is not very good. The
symbol will be resolved accurately in non-PIC code, but suboptimally: the
symbol reference cannot currently appear as the immediate operand of an
instruction, and the code generator cannot make any assumptions about the
value of the symbol (so for example, it could not use a R_X86_64_8
relocation if the value is known to be in the range 0..255).

In PIC mode, if the reference is not known to be DSO-local, the value is
loaded from the GOT (or a synthetic GOT entry), which again means
suboptimal code. If the reference is known to be DSO-local, the symbol will
be referenced with a PC relative relocation and therefore cannot be
resolved properly to an absolute value (c.f.
https://reviews.llvm.org/D19844). The latter case in particular would
seem to indicate that a representational change is required for correctness
to distinguish references to absolute symbols from references to regular
symbols.

The specific change I have in mind is to allow !range metadata on
GlobalObjects. This would
be similar to existing !range metadata, but it would apply to the
"address" of the attached GlobalObject, rather than any value loaded from
it. Its presence on a GlobalObject would also imply that the address of the
GlobalObject is "fixed" at link time. Alongside !range we could potentially
use other sources of information, such as the relocation model, code model
and visibility, to identify "fixed" globals, although that can be done
separately.

Ok, I think I understand the use-case.

I have been experimenting with a number of approaches to representation in
SDAG, and I have found one that seems to work best, and would be the least
intrusive (unfortunately most approaches to this problem are somewhat
intrusive).

Specifically, I want to:
1) move most of the body of ConstantSDNode to a new class,
ConstantIntSDNode, which would derives from ConstantSDNode. ConstantSDNode
would act as the base class for immediates-post-static-linking. Change
most references to ConstantSDNode in C++ code to refer to
ConstantIntSDNode. However, "imm" in tblgen code would continue to match
ConstantSDNode.
2) introduce a new derived class of ConstantSDNode for references to
globals with !range metadata, and teach SDAG to use this new derived class
for fixed address references

ConstantSDNode is poorly named, and renaming it to ConstantIntSDNode is
probably the right thing to do independently of the other changes.

That said, I don’t understand why you’d keep ConstantSDNode around and
introduce a new derived class of it. This seems like something that a new
“imm" immediate matcher would handle: it would match constants in a certain
range, or a GlobalAddressSDNode known-to-be-small.

To begin with: I'm not sure that GlobalAddressSDNode is the right node to
use for these types of immediates. It seems that we have two broad classes
of globals here: those with a fixed-at-link-time address (e.g. regular
non-PIC symbols, absolute symbols) and those where the address needs to be
computed (e.g. PC-relative addresses, TLS variables). To me it seems like
the first class is much more similar to immediates than to the second
class. That suggested to me that there ought to be two separate
representations for global variables, where the former are "morally"
immediates, and the latter are not (i.e. the existing GlobalAddressSDNode).

I went over a couple of approaches for representing "moral" immediates in
my llvm-commits post. The first one seems to be more like what you're
suggesting:

- Introduce a new opcode for absolute symbol constants. This intuitively

seemed like the least risky approach, as individual instructions could "opt
in" to the new absolute symbol references. However, this seems hard to fit
into the existing SDAG pattern matching engine, as the engine expects each
"variable" to have a specific opcode. I tried adding special support for
"either of the two constant opcodes" to the matcher, but I could not see a
good way to do it without making fundamental changes to how patterns are
matched.

- Use the ISD::Constant opcode for absolute symbol constants, but

introduce a separate class for them. This also seemed problematic, as there
is a strong assumption (both in existing SDAG code and in generated code)
of a many-to-one mapping from opcodes to classes.

We can solve part of the problem with the second approach with a base class
for ISD::Constant. As I worked on that approach, I found that it did turn
out to be a good fit overall: in many cases we're already adhering to a
principle that an unrestricted immediate maps onto potentially relocatable
bytes in the output file. The X86 and ARM backends illustrate this quite
well: the X86 instruction set generally uses power-of-2 wide immediate
forms that neatly map onto instruction bytes, and ARM generally uses
compressed immediate forms (e.g. "mod_imm") which would naturally match
only real constant integers. Using that principle, we can restrict (e.g.)
ImmLeaf to constant integers (see https://reviews.llvm.org/D25355). In
cases where this mapping isn't quite right, we can use more restrictive
matchers.

I'm still a little uneasy about the second approach, and would be
interested in my first approach, but I'm not sure if it would be practical.

Thanks,

#4

I understand what you’re saying, but I don’t think that is the key issue here. The relevant SDNode subclasses are concerned with representing the structural input code (in this case a GlobalValue*) not about representing the target-specific concept at work here (this particular GV has an address known to fit in this specific relocation). The structure of SelectionDAG types like SDNode needs to be target independent, and target specific matchers are the ones that handle discrepancies.

If you mean a new ISD opcode, then I don’t think this makes sense. We already have an opcode for that represents the address of a global value, we should use it. “absolute symbol constants” are a special case of them, and using a predicate to handle matching them should work fine. What am I missing?

I think you’ll have to define the matcher in C++ with ComplexPattern, analogously to how the addressing mode selection logic works. This allows you to specify multiple ISD nodes that it can match.

This also doesn’t make sense to me. The fundamental issue you’re grappling with is that you have two different “input” concepts (small immediates, and globals whose absolute address fits in that range) that you want to handle the same way. You need to do something like ComplexPattern to handle this.

-Chris

#5

Thanks Chris. I will take a closer look at ComplexPattern, I was somehow
unaware of it until now. From a brief look it does seem to allow me to do
what I need here while being less intrusive.

I think my main concerns with it are that using ComplexPattern pervasively
in instruction patterns may cause bloat in the pattern matching tables and
that it may cause FastISel to bail out more often. Those don't seem like
insurmountable problems though, we may just need a specialized variant of
it.

Thanks,

#6

I'm afraid I might be misunderstanding the basics here -- I tried to start
off by replacing an "imm" matcher in one of the x86 patterns with a
ComplexPattern that simply matches ConstantSDNodes, as shown in the
attached patch. I would have expected this to be a no-op change, but I
found that this change broke (i.e. caused assertion failures in) a large
number of test cases, e.g. "test/CodeGen/X86/2012-07-16-fp2ui-i1.ll".

Is there anything I'm doing wrong here, or are there just bugs that need to
be fixed?

Thanks,

0001-fancyimm.patch (2.08 KB)

#7

The result should be a TargetConstant. Something like

bool SelectFancyImm(SDValue N, SDValue &Op) {
   auto *CN = dyn_cast<ConstantSDNode>(N);
   if (!CN)
     return false;
   Op = CurDAG->getTargetConstant(CN->getZExtValue(), MVT::i32);
   return true;
}

-Krzysztof

#8

Thanks, that got me past that problem.

#9

Going back to IR-level representation: here is an alternative
representation based on a suggestion from Eli.

Introduce a new type of GlobalValue called GlobalConstant. GlobalConstant
would fit into the GlobalValue hierarchy like this:

   - GlobalValue
   - GlobalConstant
      - GlobalPointer
         - GlobalIndirectSymbol
            - GlobalAlias
            - GlobalIFunc
         - GlobalObject
            - Function
            - GlobalVariable

GlobalValue would no longer be assumed to be of pointer type. The getType()
overload that takes a PointerType, as well as getValueType() would be moved
down to GlobalPointer. (A nice side benefit of this is that it would help
flush out cases where we are unnecessarily depending on global pointee
types.)

A GlobalConstant can either be a definition or a declaration. A definition
would look like this:

@foo = globalconst i32 42

while a declaration would look like this:

@foo = external globalconst i32

GlobalConstant could also hold a linkage and visibility. Looking at the
other attributes that a GlobalValue can hold, many of them do not seem
appropriate for GlobalConstant and could potentially be moved to
GlobalPointer.

Thoughts?

Thanks,

#10

This is equivalent to writing “foo = 42” in assembly? How do you plan to use this? The concept makes sense, but I’ve never actually seen anyone use symbols this way. -Eli

#11

The specific change I have in mind is to allow !range metadata on
GlobalObjects. This would
be similar to existing !range metadata, but it would apply to the
"address" of the attached GlobalObject, rather than any value loaded from
it. Its presence on a GlobalObject would also imply that the address of the
GlobalObject is "fixed" at link time.

Going back to IR-level representation: here is an alternative
representation based on a suggestion from Eli.

Introduce a new type of GlobalValue called GlobalConstant. GlobalConstant
would fit into the GlobalValue hierarchy like this:

   - GlobalValue
   - GlobalConstant
      - GlobalPointer
         - GlobalIndirectSymbol
            - GlobalAlias
            - GlobalIFunc
         - GlobalObject
            - Function
            - GlobalVariable

GlobalValue would no longer be assumed to be of pointer type. The
getType() overload that takes a PointerType, as well as getValueType()
would be moved down to GlobalPointer. (A nice side benefit of this is that
it would help flush out cases where we are unnecessarily depending on
global pointee types.)

A GlobalConstant can either be a definition or a declaration. A definition
would look like this:

@foo = globalconst i32 42

This is equivalent to writing "foo = 42" in assembly?

Yes.

while a declaration would look like this:

@foo = external globalconst i32

GlobalConstant could also hold a linkage and visibility. Looking at the
other attributes that a GlobalValue can hold, many of them do not seem
appropriate for GlobalConstant and could potentially be moved to
GlobalPointer.

Thoughts?

How do you plan to use this? The concept makes sense, but I've never
actually seen anyone use symbols this way.

I plan to use this as part of the ThinLTO implementation of control flow
integrity. See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html
for a description of how the design currently works in regular LTO.

If you look at the asm snippets in that design doc, you will see a number
of hardcoded constants -- these constants are calculated at LTO time based
on whole program information. I want the intermediate object files to
depend on the constants so that their values can be substituted in at link
time. In ThinLTO, object files are cached, so if a value changes I want to
avoid invalidating the cache entries that depend on that value.

Thanks,

#12

This states the context you want to use these in (CFI with ThinLTO) without actually stating how you plan to use them within that context. I think the latter would help motivate specific designs.

Is there a write-up of the imagined CFI+ThinLTO design somewhere that (concisely) explains the plan?

Maybe you could give some small and easy to understand example usage to motivate this?

#13

The specific change I have in mind is to allow !range metadata on
GlobalObjects. This would
be similar to existing !range metadata, but it would apply to the
"address" of the attached GlobalObject, rather than any value loaded from
it. Its presence on a GlobalObject would also imply that the address of the
GlobalObject is "fixed" at link time.

Going back to IR-level representation: here is an alternative
representation based on a suggestion from Eli.

Introduce a new type of GlobalValue called GlobalConstant. GlobalConstant
would fit into the GlobalValue hierarchy like this:

   - GlobalValue
   - GlobalConstant
      - GlobalPointer
         - GlobalIndirectSymbol
            - GlobalAlias
            - GlobalIFunc
         - GlobalObject
            - Function
            - GlobalVariable

GlobalValue would no longer be assumed to be of pointer type. The
getType() overload that takes a PointerType, as well as getValueType()
would be moved down to GlobalPointer. (A nice side benefit of this is that
it would help flush out cases where we are unnecessarily depending on
global pointee types.)

A GlobalConstant can either be a definition or a declaration. A
definition would look like this:

@foo = globalconst i32 42

This is equivalent to writing "foo = 42" in assembly?

Yes.

while a declaration would look like this:

@foo = external globalconst i32

GlobalConstant could also hold a linkage and visibility. Looking at the
other attributes that a GlobalValue can hold, many of them do not seem
appropriate for GlobalConstant and could potentially be moved to
GlobalPointer.

Thoughts?

How do you plan to use this? The concept makes sense, but I've never
actually seen anyone use symbols this way.

I plan to use this as part of the ThinLTO implementation of control flow
integrity. See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html
for a description of how the design currently works in regular LTO.

If you look at the asm snippets in that design doc, you will see a number
of hardcoded constants -- these constants are calculated at LTO time based
on whole program information. I want the intermediate object files to
depend on the constants so that their values can be substituted in at link
time. In ThinLTO, object files are cached, so if a value changes I want to
avoid invalidating the cache entries that depend on that value.

This states the context you want to use these in (CFI with ThinLTO)
without actually stating how you plan to use them within that context. I
think the latter would help motivate specific designs.

Is there a write-up of the imagined CFI+ThinLTO design somewhere that
(concisely) explains the plan?

Not just yet, at least not regarding the part which requires constants. I
will send that to the list separately.

Maybe you could give some small and easy to understand example usage to
motivate this?

Sure. Suppose you have two modules:

m1.ll:

@foo = globalconst i8 1

m2.ll:

@foo = external globalconst i8

define i32 @f(i32 %x) {
  %1 = lshr i32 %x, zext i8 @foo to i32
  %2 = and i32 %1, 1
  ret i32 %2
}

These produce a pair of object files which when linked together produces a
function f that selects bit "foo" of its argument. I can link m2.ll with
some other object file with some other definition of foo to produce a
function f that selects some other bit. That other object file can be
produced independently of m2, which means that I can change the selected
bit without needing to recompile m2.

How is this more useful than a regular constant GlobalVariable? Let's look
at what the asm code for m2.ll would hypothetically look like:

.globl f
f:
shrl $foo, %edi
andl $1, %edi
movl %edi, %eax
retq

Compare this to the case where foo is a regular GlobalVariable which we
load from in f:

f:
movb foo(%rip), %cl
shrl %cl, %edi
andl $1, %edi
movl %edi, %eax
retq

As you can see there is a clear win in code size and register pressure.

Thanks,

#14

Hi Peter,

I agree that it makes sense to introduce a new GlobalConstant IR node for this sort of thing. That said, have you considered a design where GlobalConstant is still required to be a pointer type? If you did this, you would end up with a simpler and less invasive design of:

  • GlobalValue

  • GlobalConstant

  • GlobalIndirectSymbol

  • GlobalAlias

  • GlobalIFunc- GlobalObject

  • Function

  • GlobalVariable
    I think that this would be better for (e.g.) the X86 backend anyway, since global objects can be assigned to specific addresses with linker maps, and thus have small addresses (and this is expressible with the range metadata). This means that GlobalConstant and other GlobalValues should all be usable in the same places in principle.

-Chris

#15

Back in the day the idea was to use an alias whose ConstantExpr was
just 42. Would that work?

Cheers,
Rafael

#16

@foo = globalconst i32 42

This is equivalent to writing "foo = 42" in assembly?

Yes.

Back in the day the idea was to use an alias whose ConstantExpr was
just 42. Would that work?

In fact, it already works:

@foo = alias i64, inttoptr (i64 42 to i64*)

produces

foo = 42

Cheers,
Rafael

#17

If this works, it does seem better. But I can imagine it being hard to take the “load” of the global constant and turn it into a direct reference to a symbolic immediate operand to an instruction.

And it isn’t clear that you can assign the “foo” in Peter’s example an address even with a linker map – it isn’t a global object at all, it is a symbolic name for an immediate IIUC? (It’s entirely possible I’ve misunderstood either what Peter needs or what you’re suggesting, but I’d at least like to understand it! =D)

-Chandler

#18

The linker “could" do it I think. For example ld64 is pattern matching to "optimize away” load from the GOT when possible, replacing then with nop and propagating the constant address.

It is still not perfect, as a register has to be used sometimes, and the nop will still be there taking space. But that may be enough for this use case?

#19

Hi Peter,

I agree that it makes sense to introduce a new GlobalConstant IR node for this sort of thing. That said, have you considered a design where GlobalConstant is still required to be a pointer type? If you did this, you would end up with a simpler and less invasive design of:

  • GlobalValue

  • GlobalConstant

  • GlobalIndirectSymbol

  • GlobalAlias

  • GlobalIFunc- GlobalObject

  • Function

  • GlobalVariable

I think that this would be better for (e.g.) the X86 backend anyway, since global objects can be assigned to specific addresses with linker maps, and thus have small addresses (and this is expressible with the range metadata). This means that GlobalConstant and other GlobalValues should all be usable in the same places in principle.

If this works, it does seem better. But I can imagine it being hard to take the “load” of the global constant and turn it into a direct reference to a symbolic immediate operand to an instruction.

The linker “could" do it I think. For example ld64 is pattern matching to "optimize away” load from the GOT when possible, replacing then with nop and propagating the constant address.

It is still not perfect, as a register has to be used sometimes, and the nop will still be there taking space. But that may be enough for this use case?

For CFI, I think that would be a pretty frustrating overhead to pay for, and would require linker changes on at least some platforms.

Is there a reason to not directly support symbolic names for immediate values?

#20

To be clear: I just meant it as an extra piece of information. I don’t have a particular opposition to the “immediate value” solution (that looks pretty smart and optimal indeed).