Moving towards a singular pointer type

Yea, this is very close to the line. I'm mildly in favor of it, mostly
because of the truly pervasive nature of the change and the trivial nature
of support.... But it wouldn't be hard to argue me out of it honestly....

I think we should keep GEP essentially the same, but disassociate the
type being GEPd over from the type of the operands. So, assuming the new
ptr type is spelled "ptr", we could use this syntax:
%inner.ptr = getelementptr ptr, ptr %x, i32 1

Or if I was adding 1 to a "struct A*" value in C:
%next_elt = getelementptr %struct.A, ptr %x, i32 1

Ditto for all other instructions that care about pointee types, like load
and store:
%v = load i32, ptr %p ; loads already know (and store!) their loaded type
internally
store i32 %v, ptr %p ; no need to duplicate that %p points to, we have
the type on %v

Emphatically agree. No instruction should really change semantics here.
GEPs should keep working the exact same way, the type involved should just
be separate from the pointer's type.

I don't think this can be incremental, I think it all goes at once.

I have some ideas of how to make it incremental:

I think you might need to add a new GEP bitcode opcode, since that
instruction grows a new type operand that doesn't come from an operand type
or result type.

Yep. And you can add this first, defining the semantics to be as-if the
pointer operand was bit casted to a pointer to the new type. Then we could
(in theory, not in practice!) even use and test it with the current IR,
passing an i8* or any other pointer type operand.

I’m not sure we need the new instructions at all.

Really what we want is for Load and GEP to carry around a Type* alongside
all their operands. This can be added now to the existing Load and GEP
insts, and to their constructors/create methods.

I'm good with either option (what Chandler described or what Pete's
described here). I am actually leaning towards what you've got here, Pete,
unless people have objections.

At a first pass we wouldn't even need to break LLVM IRBuilder API
compatibility - we can take the type from the operand and use that to
create the GEP/Load. Add the alternative builder calls that accept the type
explicitly and start migrating callers to pass it in explicitly before
removing the old version.

Frontend test cases would need to be cleaned up up-front, because we'd
start generating the new GEP/Load syntax as soon as it was introduced in
this way.

Then, once GEP/Load (anything else that consumes a pointer & cares about
its type?) are done I could introduce the new ptr type, start making
instructions be of that type instead - probably at this point I'd spend
time cleaning up clang so it doesn't depend on the type of a pointer type
at all (I imagine there will be things I can't catch in the first pass even
if I do my best to push the types through the stack and not depend on the
ones in the pointer operand).

Sound plausible?

I’m not sure we need the new instructions at all.

Really what we want is for Load and GEP to carry around a Type* alongside all their operands. This can be added now to the existing Load and GEP insts, and to their constructors/create methods.

I’m good with either option (what Chandler described or what Pete’s described here). I am actually leaning towards what you’ve got here, Pete, unless people have objections.

At a first pass we wouldn’t even need to break LLVM IRBuilder API compatibility - we can take the type from the operand and use that to create the GEP/Load. Add the alternative builder calls that accept the type explicitly and start migrating callers to pass it in explicitly before removing the old version.

Frontend test cases would need to be cleaned up up-front, because we’d start generating the new GEP/Load syntax as soon as it was introduced in this way.

Then, once GEP/Load (anything else that consumes a pointer & cares about its type?) are done I could introduce the new ptr type, start making instructions be of that type instead - probably at this point I’d spend time cleaning up clang so it doesn’t depend on the type of a pointer type at all (I imagine there will be things I can’t catch in the first pass even if I do my best to push the types through the stack and not depend on the ones in the pointer operand).

Sound plausible?

Yeah, sounds great.

Thanks,
Pete

+1 from me.

+1 as well. Good luck!

—Owen

As with David, I know of no issues moving to a singular pointer type per address space. Having the type on the load or store instruction is perfectly adequate for GC barrier and safepoint insertion purposes.

Philip

+1 and thank you so much for working on this!

Hi David,

You can emulate this by having clang always generate "i8*” as the general type, then bitcast to "%Foo*” before doing a GEP. Have you prototyped this change (with this approach, or any other one) to see what it does to the optimizers?

-Chris

It's an idea been thrown around in a few different threads (including
Rafael's recent
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20141201/247285.html
and Chandler's http://llvm.org/viewvc/llvm-project?rev=226781&view=rev )
so I'm putting up my hand to volunteer to do the work & interested in
getting a bit more feedback, thoughts on best approaches, timing, etc.

For some more detail: pointer types (i32*, %foo*, etc) complicate IR
canonicalization. store + load should be the same instructions given the
same number of bytes stored to memory, but instead we can have store float,
store int, etc, etc. Another point Chandler made was that the bitcasts
involved when a pointer isn't of the right type results in extra IR
instructions we don't really need.

So the general idea is that all pointers would just be called "ptr"
(pointer? void*?).

Is this something everyone feels is the right direction? Any reason why it
wouldn't be?

Hi David,

You can emulate this by having clang always generate "i8*” as the general
type, then bitcast to "%Foo*” before doing a GEP. Have you prototyped this
change (with this approach, or any other one) to see what it does to the
optimizers?

No, I haven't tried prototyping it. It's a fair point, though I'm not sure
how much of that work would be thrown out (some of it would be reusable -
since it'll force the front end to track type information wehre it might've
previously been relying on the IR types). Reckon it's worthwhile? (I can
certainly see that side of it - throwing all this churn in when we don't
quite know how it'll play out in the end seem risky, but it seemed like
those who're invested in this stuff felt pretty certain it was the right
way to go)

- David

This idea seems to have good merits to me. It seems like any functionality related to pointer types could determined at load/store time without the overhead of specifying pointer types in IR only to cast it away right before usage.

I often found myself doing the i8* trick any time what I was pointing to didn’t easy fit in to the type system since, as others pointed out, the frontend should know what the actual types are anyway.

One migration issue I could see is any time a frontend depends on the LLVM type system for tracking types rather than doing it itself.

You could say with more certainty, but I see this as an incremental way to move towards the singular pointer type model. I suspect that there will be some impact on the optimizer, but that the optimizer can be taught how to handle it.

If you go through the effort to build a huge patch that switches the universe over to a singular pointer type, you won’t be able to land it until the optimizer regressions are fixed. This could be a very long time maintaining a large patch out of tree (never fun).

In the worst case, doing this could also expose an unforeseen problem with doing this. I don’t expect that personally, but it is possible.

-Chris

For some more detail: pointer types (i32*, %foo*, etc) complicate IR

canonicalization. store + load should be the same instructions given the
same number of bytes stored to memory, but instead we can have store float,
store int, etc, etc. Another point Chandler made was that the bitcasts
involved when a pointer isn't of the right type results in extra IR
instructions we don't really need.

So the general idea is that all pointers would just be called "ptr"
(pointer? void*?).

Is this something everyone feels is the right direction? Any reason why
it wouldn't be?

Hi David,

You can emulate this by having clang always generate "i8*” as the general
type, then bitcast to "%Foo*” before doing a GEP. Have you prototyped this
change (with this approach, or any other one) to see what it does to the
optimizers?

No, I haven't tried prototyping it. It's a fair point, though I'm not sure
how much of that work would be thrown out (some of it would be reusable -
since it'll force the front end to track type information wehre it might've
previously been relying on the IR types). Reckon it's worthwhile? (I can
certainly see that side of it - throwing all this churn in when we don't
quite know how it'll play out in the end seem risky, but it seemed like
those who're invested in this stuff felt pretty certain it was the right
way to go)

You could say with more certainty, but I see this as an incremental way to
move towards the singular pointer type model. I suspect that there will be
*some* impact on the optimizer, but that the optimizer can be taught how to
handle it.

If you go through the effort to build a huge patch that switches the
universe over to a singular pointer type, you won’t be able to land it
until the optimizer regressions are fixed. This could be a very long time
maintaining a large patch out of tree (never fun).

Yeah, possibly - chatted about this a bit with Chandler too & his
experience has been that shaking these sort of things out is often
out-of-tree (granted, that's with small changes to the canonicalization of
pointer types in specific places - this kind of widescale change might hit
quite a few tests in-tree first before reaching the long-tail of random
out-of-tree tests people run/care about) so having an out-of-tree patch
won't necessarily get us far, and as you say - comes at a bit of a cost to
maintain it out of tree and then transform it into the final version later
once we introduce a true opaque pointer type.

In the worst case, doing this could also expose an unforeseen problem with
doing this. I don’t expect that personally, but it is possible.

Yeah, that's my personal concern just due to my unfamiliarity with this
sort of thing - but I'm going to take everyone else's word for it that this
is the preferred way forward & just keep pushing on with it. Sooner it can
be in tree the sooner we'll have good coverage/results on it, I think. (&
yeah, at various points we might have a few rounds on specific patches
after they reveal perf regressions, but that seems fine - having everyone
on the same code should make it easier to find/share reproductions, etc)

- David

To clarify, I have consistently found almost all of the optimizer
regressions due to in tree tests and relatively easily. There were just
some small number of long-tail problems that were only really exposed by
flipping the switch and shaking out the regressions.

I'm not actually worried about this change though Chris, at least w.r.t.
optimizer changes being necessary. There are a few reasons:

1) The old ScalarRepl pass cared a *lot* about pointer type, but the new
SROA doesn't care at all, so the biggest offender is essentially handled.

2) We've recently changed our pointer canonicalization rules several times
and in different ways. Each of those changes helped shake out bugs where
the optimizer was relying on the pointer type for something. The number of
things found has dropped dramatically with each change, so I don't think
there is a huge pile of problems left hiding somewhere.

3) Almost all of the problems we found with the changes to canonicalization
were actually cases where *casts* impeded optimizations, not the different
pointer type. This change will be a strict reduction in the need for casts,
and thus I expect it to actually be safer than the other changes. All
evidence is that most of the remaining reliance on these kinds of things
are actually relying on an absence of casts. With this change, the casts
will all go away.

So, I'm not as worried about having a very drawn out period of fixing the
optimizer. I think we'll probably uncover a few minor things that we have
to fix immediately, and then when we make the change some small number of
benchmarks will regress (likely on some small number of platforms). We'll
have to track those down, no doubt, but I'm not worried about it preventing
progress for a long time.

This. An idiom I've used extensively is
pointer-to-struct-with-name-mangled-type-information. Because of this I can
rely on LLVM entirely for type tracking, which feels like a good thing. It
shouldn't be a big migration issue in my case, but I'd appreciate any words
of wisdom from the LLVM community.

v/r,
Josh

I'm not actually worried about this change though Chris, at least w.r.t. optimizer changes being necessary. There are a few reasons:

1) The old ScalarRepl pass cared a *lot* about pointer type, but the new SROA doesn't care at all, so the biggest offender is essentially handled.

Why do you think that SRoA is the biggest “offender”? This will pretty fundamentally changing the shape of the IR (in a good way) by presumably eliminating a ton of bitcasts etc. This has the potential to provoke instcombine regressions, tickle things like globalopt and load/store elimination, etc. I don’t think that any of these will be particularly difficult to fix, but I imagine that there will be a long tail of minor things.

2) We've recently changed our pointer canonicalization rules several times and in different ways. Each of those changes helped shake out bugs where the optimizer was relying on the pointer type for something. The number of things found has dropped dramatically with each change, so I don't think there is a huge pile of problems left hiding somewhere.

This is more reassuring for me.

3) Almost all of the problems we found with the changes to canonicalization were actually cases where *casts* impeded optimizations, not the different pointer type. This change will be a strict reduction in the need for casts, and thus I expect it to actually be safer than the other changes. All evidence is that most of the remaining reliance on these kinds of things are actually relying on an absence of casts. With this change, the casts will all go away.

Yes, I like this change for a number of reasons: reduction of casts, simplified type resolution stuff in libIR, etc.

So, I'm not as worried about having a very drawn out period of fixing the optimizer. I think we'll probably uncover a few minor things that we have to fix immediately, and then when we make the change some small number of benchmarks will regress (likely on some small number of platforms). We'll have to track those down, no doubt, but I'm not worried about it preventing progress for a long time.

So long as the regressions are tracked down and fixed before the mega-patch is landed, I’m ok with making this change. I just think that finding any ways to make it more incremental and stage it will be very well rewarded. It will be impossible to review the resultant patch otherwise.

-Chris

> I'm not actually worried about this change though Chris, at least w.r.t.
optimizer changes being necessary. There are a few reasons:
>
> 1) The old ScalarRepl pass cared a *lot* about pointer type, but the new
SROA doesn't care at all, so the biggest offender is essentially handled.

Why do you think that SRoA is the biggest “offender”? This will pretty
fundamentally changing the shape of the IR (in a good way) by presumably
eliminating a ton of bitcasts etc. This has the potential to provoke
instcombine regressions, tickle things like globalopt and load/store
elimination, etc. I don’t think that any of these will be particularly
difficult to fix, but I imagine that there will be a long tail of minor
things.

> 2) We've recently changed our pointer canonicalization rules several
times and in different ways. Each of those changes helped shake out bugs
where the optimizer was relying on the pointer type for something. The
number of things found has dropped dramatically with each change, so I
don't think there is a huge pile of problems left hiding somewhere.

This is more reassuring for me.

> 3) Almost all of the problems we found with the changes to
canonicalization were actually cases where *casts* impeded optimizations,
not the different pointer type. This change will be a strict reduction in
the need for casts, and thus I expect it to actually be safer than the
other changes. All evidence is that most of the remaining reliance on these
kinds of things are actually relying on an absence of casts. With this
change, the casts will all go away.

Yes, I like this change for a number of reasons: reduction of casts,
simplified type resolution stuff in libIR, etc.

> So, I'm not as worried about having a very drawn out period of fixing
the optimizer. I think we'll probably uncover a few minor things that we
have to fix immediately, and then when we make the change some small number
of benchmarks will regress (likely on some small number of platforms).
We'll have to track those down, no doubt, but I'm not worried about it
preventing progress for a long time.

So long as the regressions are tracked down and fixed before the
mega-patch is landed, I’m ok with making this change. I just think that
finding any ways to make it more incremental and stage it will be very well
rewarded. It will be impossible to review the resultant patch otherwise.

It should come out somewhat incremental, I think. Here's how it's shaping
up/I see it going:

1) add explicit types where required in IR instructions - gep, load, byval,
anything else I can find...
  a) Provide the mechanism to specify it (in textual IR, bitcode, and LLVM
IR APIs)
  b) Update callers to Clang, LLVM, and Polly, to pass that information
(initially just asserting that it's the same information as was provided by
the typed-pointer operands)
  c) /rely/ on that information in LLVM - stop using the pointee types

After that it might be monolithic - though I'll be trying to do it
incrementally for my own sanity.

<I was thinking I might remove ptr-to-ptr bitcasts here, before introducing
the ptr type - since at this point they'll be pointless (har har) already,
since the pointer-using instructions will no longer need the type from them

2) introduce opaque pointer type (initially unused)
3) Repeat:
  a) choose an instruction or other source of pointer type
  b) update type to opaque pointer
  c) find & fix frontend bugs where it was relying on pointer type in the IR
  d) commit LLVM change

It could be monolithic there (do all the ptrs in one go), though I don't
think it needs to be.

4) Remove non-opaque pointer types... - maybe. Might need to leave them in
to make the back-compat bitcode reading easy, but I'm not sure.

> I'm not actually worried about this change though Chris, at least
w.r.t. optimizer changes being necessary. There are a few reasons:
>
> 1) The old ScalarRepl pass cared a *lot* about pointer type, but the
new SROA doesn't care at all, so the biggest offender is essentially
handled.

Why do you think that SRoA is the biggest “offender”? This will pretty
fundamentally changing the shape of the IR (in a good way) by presumably
eliminating a ton of bitcasts etc. This has the potential to provoke
instcombine regressions, tickle things like globalopt and load/store
elimination, etc. I don’t think that any of these will be particularly
difficult to fix, but I imagine that there will be a long tail of minor
things.

> 2) We've recently changed our pointer canonicalization rules several
times and in different ways. Each of those changes helped shake out bugs
where the optimizer was relying on the pointer type for something. The
number of things found has dropped dramatically with each change, so I
don't think there is a huge pile of problems left hiding somewhere.

This is more reassuring for me.

> 3) Almost all of the problems we found with the changes to
canonicalization were actually cases where *casts* impeded optimizations,
not the different pointer type. This change will be a strict reduction in
the need for casts, and thus I expect it to actually be safer than the
other changes. All evidence is that most of the remaining reliance on these
kinds of things are actually relying on an absence of casts. With this
change, the casts will all go away.

Yes, I like this change for a number of reasons: reduction of casts,
simplified type resolution stuff in libIR, etc.

> So, I'm not as worried about having a very drawn out period of fixing
the optimizer. I think we'll probably uncover a few minor things that we
have to fix immediately, and then when we make the change some small number
of benchmarks will regress (likely on some small number of platforms).
We'll have to track those down, no doubt, but I'm not worried about it
preventing progress for a long time.

So long as the regressions are tracked down and fixed before the
mega-patch is landed, I’m ok with making this change. I just think that
finding any ways to make it more incremental and stage it will be very well
rewarded. It will be impossible to review the resultant patch otherwise.

It should come out somewhat incremental, I think. Here's how it's shaping
up/I see it going:

1) add explicit types where required in IR instructions - gep, load,
byval, anything else I can find...
  a) Provide the mechanism to specify it (in textual IR, bitcode, and LLVM
IR APIs)
  b) Update callers to Clang, LLVM, and Polly, to pass that information
(initially just asserting that it's the same information as was provided by
the typed-pointer operands)
  c) /rely/ on that information in LLVM - stop using the pointee types

After that it might be monolithic - though I'll be trying to do it
incrementally for my own sanity.

<I was thinking I might remove ptr-to-ptr bitcasts here, before
introducing the ptr type - since at this point they'll be pointless (har
har) already, since the pointer-using instructions will no longer need the
type from them anyway>

2) introduce opaque pointer type (initially unused)
3) Repeat:
  a) choose an instruction or other source of pointer type
  b) update type to opaque pointer
  c) find & fix frontend bugs where it was relying on pointer type in the
IR
  d) commit LLVM change

It could be monolithic there (do all the ptrs in one go), though I don't
think it needs to be.

On further reflection this step will probably be monolithic - it'd be
really hard to script updating only some pointer types when the type is
written at the use, not the def, so I'd lose the context from "this
instruction now produces ptr". (why do we put the type on the use instead
of the def? *shrug*)

Ah well.

It might help after adding explicit types where needed and before adding the opaque pointer type, to change all pointers to a single type in the existing type system, i8* could work or maybe a weird type that would shake out any issues like i99*.

If all pointers were changed to this weird type and all GEP, load, store, etc were told to use their explicit type instead you might be able to find places where we’re still relying on pointer types before adding and converting to the opaque type.

It might help after adding explicit types where needed and before adding
the opaque pointer type, to change all pointers to a single type in the
existing type system, i8* could work or maybe a weird type that would shake
out any issues like i99*.

I'm not sure this would help things very much - it'd just add two major
churns rather than one, no? (one to transform all the tests from T* to i42*
then another to change from i42* to ptr)

If we included back-compat textual IR support then it would be different
(but we could include that while transitioning to ptr as easily as
transitioning to i42*, I think).

It’s a good point it wouldn’t help with the textual test churn. It seemed like a good way to isolate issues related to depending on the pointed-to-type from issues related to converting to the opaque pointer class which might be in a different class inheritance tree and cause runtime issues due to dyn_cast failures etc.

I don’t have a full picture of what things will break so I won’t double-down on the suggestion :wink: