FW: RFC: Supporting different sized address space arithmetic

addr_space_variable_pointer.patch (8.85 KB)

Micah,

There are a number of variable names in this patch that don't follow
the naming convention (which specifies that they should start with an
uppercase letter).

         if (PtrBits < 64)
- OffsVal = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(),
- TLI.getPointerTy(),
+ OffsVal = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(),
PtrTy, DAG.getConstant(Offs, MVT::i64));

This is not necessarily specific to your patch, but can you explain the
special role of 64-bits here?

Thanks again,
Hal

Why do we need the change in lib/CodeGen/Analysis.cpp? If
TargetLowering::getValueType() doesn't work for arbitrary address
spaces, you should fix it.

I think my earlier comments about getIntPtrConstant still hold:
instead of "DAG.getIntPtrConstant(Offset, addrSpace)", you can just
write "DAG.getConstant(Offset, PtrTy)".

+ EVT NewPtrVT = TLI.getPointerTy(dyn_cast<PointerType>(
+ SV->getType())->getAddressSpace());
+ if (PtrVT != NewPtrVT) {
+ // Check to see if we want to change the size of the pointer
+ // based on the address space and if so extend or truncate the pointer.
+ Ptr = DAG.getSExtOrTrunc(Ptr, getCurDebugLoc(), NewPtrVT);
+ PtrVT = NewPtrVT;
+ }

This situation should be impossible: you're checking whether a pointer
has the same type as itself. If you're hitting this, it's just a
symptom of a bug elsewhere. The same applies to other places you
perform this sort of check outside of "bitcast" lowering.

The more broad issue I see here is that we need changes to the IR to
make sure the mid-level optimizers don't break your code;
specifically, using "bitcast" for lossy conversions is unsafe (so you
need a "ptrcast" operation which can perform potentially lossy
conversions), and you need to update TargetData so we can correctly
compute the size of an arbitrary pointer. I was under the impression
that you were planning to propose a fix for those separately, but it
doesn't look like you have.

-Eli

Most likely this code was added before getSExtOrTruncate was added, but not 100% sure. It seems to assume that no pointer can be more than 64bits in size.

From: Eli Friedman [mailto:eli.friedman@gmail.com]
Sent: Friday, August 24, 2012 5:37 PM
To: Villmow, Micah
Cc: LLVM Developers Mail
Subject: Re: [LLVMdev] FW: RFC: Supporting different sized address
space arithmetic

>
>
>> From: Villmow, Micah
>> Sent: Friday, August 24, 2012 2:56 PM
>> To: 'Eli Friedman'
>> Cc: LLVM Developers Mailing List
>> Subject: RE: [LLVMdev] RFC: Supporting different sized address space
>> arithmetic
>>
>> Eli,
>> There is a patch that implements the beginning what I think is the
>> correct approach to support the backend overloading the size of the
>> pointer for an address space.
>>
>> Does this seem like the right way to do this?
>>
>> I'm guessing I need to handle a few more nodes(IntToPtr/PtrToInt)
and
>> atomics, but this already works for what we want to do.

Why do we need the change in lib/CodeGen/Analysis.cpp? If
TargetLowering::getValueType() doesn't work for arbitrary address
spaces, you should fix it.

[Villmow, Micah] This is what I can figure out fixes it since we are overriding the address space. Since in this case we are trying to figure out what the correct value type is, I did not think the normal getValueType should be overloaded, but if you think it should be, I'll go ahead and make this change.

I think my earlier comments about getIntPtrConstant still hold:
instead of "DAG.getIntPtrConstant(Offset, addrSpace)", you can just
write "DAG.getConstant(Offset, PtrTy)".

[Villmow, Micah] I can make the change, just didn't want to make more changes than were necessary.

+ EVT NewPtrVT = TLI.getPointerTy(dyn_cast<PointerType>(
+ SV->getType())->getAddressSpace());
+ if (PtrVT != NewPtrVT) {
+ // Check to see if we want to change the size of the pointer
+ // based on the address space and if so extend or truncate the
pointer.
+ Ptr = DAG.getSExtOrTrunc(Ptr, getCurDebugLoc(), NewPtrVT);
+ PtrVT = NewPtrVT;
+ }

This situation should be impossible: you're checking whether a pointer
has the same type as itself. If you're hitting this, it's just a
symptom of a bug elsewhere. The same applies to other places you
perform this sort of check outside of "bitcast" lowering.

[Villmow, Micah] Nope, what I'm checking is if the backend has over wrote the pointer type for this address space. So in the case of 64bit pointers but local address space, this code gets triggered because the largest pointer size for the local address space is 16 bits.

The more broad issue I see here is that we need changes to the IR to
make sure the mid-level optimizers don't break your code;
specifically, using "bitcast" for lossy conversions is unsafe (so you
need a "ptrcast" operation which can perform potentially lossy
conversions), and you need to update TargetData so we can correctly
compute the size of an arbitrary pointer. I was under the impression
that you were planning to propose a fix for those separately, but it
doesn't look like you have.

[Villmow, Micah] I wasn't planning on assuming anything at the optimizer level would need to be changed. This was only to allow the code generator to override the pointer size to more correctly match the underlying hardware. If there is any optimization that this breaks, then the original code was broken anyways and there is a bug somewhere else. Any valid calculation in a larger pointer size must also be valid in the smaller pointer size for the address space to even work since the hardware size is limited by the smaller pointer size.

Most likely this code was added before getSExtOrTruncate was added,
but not 100% sure. It seems to assume that no pointer can be more
than 64bits in size.

Does LLVM generally support pointers of greater than 64 bits?

-Hal

From: Hal Finkel [mailto:hfinkel@anl.gov]
Sent: Monday, August 27, 2012 8:38 AM
To: Villmow, Micah
Cc: LLVM Developers Mail
Subject: Re: [LLVMdev] FW: RFC: Supporting different sized address
space arithmetic

> Most likely this code was added before getSExtOrTruncate was added,
> but not 100% sure. It seems to assume that no pointer can be more
> than 64bits in size.

Does LLVM generally support pointers of greater than 64 bits?

[Villmow, Micah] I really don't see why it couldn't, but there might be issues that exist since I don't think any backends do.

Eli,
Here is an updated patch. This is a lot smaller based on your feedback and still solves the same problem.

For your comment on the IR changes, I'm reluctant to introduce changes there because really the backend is overriding the default behavior at a device specific level. The optimizations themselves can be dangerous, but still should produce correct results, this only allows the backend to optimize certain cases and is opt-in.

Micah

addr_space_variable_pointer.patch (7.18 KB)

Eli,
Here is an updated patch. This is a lot smaller based on your feedback and still solves the same problem.

The patch appears to be corrupt; can you regenerate it?

For your comment on the IR changes, I'm reluctant to introduce changes there because really the backend is overriding the default behavior at a device specific level. The optimizations themselves can be dangerous, but still should produce correct results, this only allows the backend to optimize certain cases and is opt-in.

Suppose I have an array of ten pointers into some address-space which
uses 16-bit pointers, and the default pointer size is 64 bits. How
many bytes in memory does that take? To me, it seems like the obvious
answer is 20 bytes, but if you compute it using our current
TargetData, you'll come up with an answer of 80. That can't work.

If your answer is that it should be 80, and the size of a pointer
isn't something the frontend/IR optimizers should be aware of, I'm not
sure your approach makes sense; you could just introduce custom
load/store nodes in your target which truncate the pointer, and you
wouldn't need to mess with the size of a pointer at all.

-Eli

From: Eli Friedman [mailto:eli.friedman@gmail.com]
Sent: Thursday, August 30, 2012 3:03 PM
To: Villmow, Micah
Cc: LLVM Developers Mail
Subject: Re: [LLVMdev] FW: RFC: Supporting different sized address space
arithmetic

> Eli,
> Here is an updated patch. This is a lot smaller based on your
feedback and still solves the same problem.

The patch appears to be corrupt; can you regenerate it?

[Villmow, Micah] Attached.

> For your comment on the IR changes, I'm reluctant to introduce changes
there because really the backend is overriding the default behavior at a
device specific level. The optimizations themselves can be dangerous,
but still should produce correct results, this only allows the backend
to optimize certain cases and is opt-in.

Suppose I have an array of ten pointers into some address-space which
uses 16-bit pointers, and the default pointer size is 64 bits. How many
bytes in memory does that take? To me, it seems like the obvious answer
is 20 bytes, but if you compute it using our current TargetData, you'll
come up with an answer of 80. That can't work.

If your answer is that it should be 80, and the size of a pointer isn't
something the frontend/IR optimizers should be aware of, I'm not sure
your approach makes sense; you could just introduce custom load/store
nodes in your target which truncate the pointer, and you wouldn't need
to mess with the size of a pointer at all.

[Villmow, Micah] Yeah I see your point here. I don't deal with array of pointers in OpenCL, so didn't think of this case.

So, what about extending data layout to support something like:
p#:size:abi:pref <- specify the size, abi and preference for the pointer of address space '#'. Default behavior is p:size:abi:pref.

I think I could throw this together and get back to you within a week or so, but need to look into the code more to see how much work it would be.
Doing it this way might actually remove the need to make some of the changes I made as it becomes a more of a core LLVM issue and less of a codegen issue.

addr_space_variable_pointer.patch (7.18 KB)

That's fine.

(You'll also need to deal with the fact that LLVM assumes bit casts
across address-spaces are lossless.)

-Eli

From: Eli Friedman [mailto:eli.friedman@gmail.com]
Sent: Thursday, August 30, 2012 3:43 PM
To: Villmow, Micah
Cc: LLVM Developers Mail
Subject: Re: [LLVMdev] FW: RFC: Supporting different sized address space
arithmetic

>
>
>> From: Eli Friedman [mailto:eli.friedman@gmail.com]
>> Sent: Thursday, August 30, 2012 3:03 PM
>> To: Villmow, Micah
>> Cc: LLVM Developers Mail
>> Subject: Re: [LLVMdev] FW: RFC: Supporting different sized address
>> space arithmetic
>>
>> > Eli,
>> > Here is an updated patch. This is a lot smaller based on your
>> feedback and still solves the same problem.
>>
>> The patch appears to be corrupt; can you regenerate it?
> [Villmow, Micah] Attached.
>>
>> > For your comment on the IR changes, I'm reluctant to introduce
>> > changes
>> there because really the backend is overriding the default behavior
>> at a device specific level. The optimizations themselves can be
>> dangerous, but still should produce correct results, this only allows
>> the backend to optimize certain cases and is opt-in.
>>
>> Suppose I have an array of ten pointers into some address-space which
>> uses 16-bit pointers, and the default pointer size is 64 bits. How
>> many bytes in memory does that take? To me, it seems like the
>> obvious answer is 20 bytes, but if you compute it using our current
>> TargetData, you'll come up with an answer of 80. That can't work.
>>
>> If your answer is that it should be 80, and the size of a pointer
>> isn't something the frontend/IR optimizers should be aware of, I'm
>> not sure your approach makes sense; you could just introduce custom
>> load/store nodes in your target which truncate the pointer, and you
>> wouldn't need to mess with the size of a pointer at all.
> [Villmow, Micah] Yeah I see your point here. I don't deal with array
of pointers in OpenCL, so didn't think of this case.
>
> So, what about extending data layout to support something like:
> p#:size:abi:pref <- specify the size, abi and preference for the
pointer of address space '#'. Default behavior is p:size:abi:pref.

That's fine.

(You'll also need to deal with the fact that LLVM assumes bit casts
across address-spaces are lossless.)

[Villmow, Micah] Is that something that should be probably be reconsidered given adding support for variable sized address spaces?

My thinking is that we should ban bitcasts which cross address-spaces,
and introduce a new instruction to represent them. (I know it's a lot
of work to add a new instruction, but I don't see any good
alternative.)

-Eli

>
>
>> From: Eli Friedman [mailto:eli.friedman@gmail.com]
>> Sent: Thursday, August 30, 2012 3:43 PM
>> To: Villmow, Micah
>> Cc: LLVM Developers Mail
>> Subject: Re: [LLVMdev] FW: RFC: Supporting different sized address
>> space arithmetic
>>
>> >
>> >
>> >> From: Eli Friedman [mailto:eli.friedman@gmail.com]
>> >> Sent: Thursday, August 30, 2012 3:03 PM
>> >> To: Villmow, Micah
>> >> Cc: LLVM Developers Mail
>> >> Subject: Re: [LLVMdev] FW: RFC: Supporting different sized
>> >> address space arithmetic
>> >>
>> >> > Eli,
>> >> > Here is an updated patch. This is a lot smaller based on your
>> >> feedback and still solves the same problem.
>> >>
>> >> The patch appears to be corrupt; can you regenerate it?
>> > [Villmow, Micah] Attached.
>> >>
>> >> > For your comment on the IR changes, I'm reluctant to introduce
>> >> > changes
>> >> there because really the backend is overriding the default
>> >> behavior at a device specific level. The optimizations
>> >> themselves can be dangerous, but still should produce correct
>> >> results, this only allows the backend to optimize certain cases
>> >> and is opt-in.
>> >>
>> >> Suppose I have an array of ten pointers into some address-space
>> >> which uses 16-bit pointers, and the default pointer size is 64
>> >> bits. How many bytes in memory does that take? To me, it
>> >> seems like the obvious answer is 20 bytes, but if you compute
>> >> it using our current TargetData, you'll come up with an answer
>> >> of 80. That can't work.
>> >>
>> >> If your answer is that it should be 80, and the size of a
>> >> pointer isn't something the frontend/IR optimizers should be
>> >> aware of, I'm not sure your approach makes sense; you could
>> >> just introduce custom load/store nodes in your target which
>> >> truncate the pointer, and you wouldn't need to mess with the
>> >> size of a pointer at all.
>> > [Villmow, Micah] Yeah I see your point here. I don't deal with
>> > array
>> of pointers in OpenCL, so didn't think of this case.
>> >
>> > So, what about extending data layout to support something like:
>> > p#:size:abi:pref <- specify the size, abi and preference for the
>> pointer of address space '#'. Default behavior is p:size:abi:pref.
>>
>> That's fine.
>>
>> (You'll also need to deal with the fact that LLVM assumes bit casts
>> across address-spaces are lossless.)
> [Villmow, Micah] Is that something that should be probably be
> reconsidered given adding support for variable sized address spaces?

My thinking is that we should ban bitcasts which cross address-spaces,
and introduce a new instruction to represent them. (I know it's a lot
of work to add a new instruction, but I don't see any good
alternative.)

Out of curiosity, for what are these currently used? Unless you happen
to know that some aliasing exists, I don't see how bitcasting a pointer
in one address space to another makes any sense.

-Hal

From: Hal Finkel [mailto:hfinkel@anl.gov]
Sent: Thursday, August 30, 2012 4:09 PM
To: Eli Friedman
Cc: Villmow, Micah; LLVM Developers Mail
Subject: Re: [LLVMdev] FW: RFC: Supporting different sized address space
arithmetic

> >
> >
> >> From: Eli Friedman [mailto:eli.friedman@gmail.com]
> >> Sent: Thursday, August 30, 2012 3:43 PM
> >> To: Villmow, Micah
> >> Cc: LLVM Developers Mail
> >> Subject: Re: [LLVMdev] FW: RFC: Supporting different sized address
> >> space arithmetic
> >>
> >> >
> >> >
> >> >> From: Eli Friedman [mailto:eli.friedman@gmail.com]
> >> >> Sent: Thursday, August 30, 2012 3:03 PM
> >> >> To: Villmow, Micah
> >> >> Cc: LLVM Developers Mail
> >> >> Subject: Re: [LLVMdev] FW: RFC: Supporting different sized
> >> >> address space arithmetic
> >> >>
> >> >> > Eli,
> >> >> > Here is an updated patch. This is a lot smaller based on your
> >> >> feedback and still solves the same problem.
> >> >>
> >> >> The patch appears to be corrupt; can you regenerate it?
> >> > [Villmow, Micah] Attached.
> >> >>
> >> >> > For your comment on the IR changes, I'm reluctant to introduce
> >> >> > changes
> >> >> there because really the backend is overriding the default
> >> >> behavior at a device specific level. The optimizations
> >> >> themselves can be dangerous, but still should produce correct
> >> >> results, this only allows the backend to optimize certain cases
> >> >> and is opt-in.
> >> >>
> >> >> Suppose I have an array of ten pointers into some address-space
> >> >> which uses 16-bit pointers, and the default pointer size is 64
> >> >> bits. How many bytes in memory does that take? To me, it seems
> >> >> like the obvious answer is 20 bytes, but if you compute it using
> >> >> our current TargetData, you'll come up with an answer of 80.
> >> >> That can't work.
> >> >>
> >> >> If your answer is that it should be 80, and the size of a
> >> >> pointer isn't something the frontend/IR optimizers should be
> >> >> aware of, I'm not sure your approach makes sense; you could just
> >> >> introduce custom load/store nodes in your target which truncate
> >> >> the pointer, and you wouldn't need to mess with the size of a
> >> >> pointer at all.
> >> > [Villmow, Micah] Yeah I see your point here. I don't deal with
> >> > array
> >> of pointers in OpenCL, so didn't think of this case.
> >> >
> >> > So, what about extending data layout to support something like:
> >> > p#:size:abi:pref <- specify the size, abi and preference for the
> >> pointer of address space '#'. Default behavior is p:size:abi:pref.
> >>
> >> That's fine.
> >>
> >> (You'll also need to deal with the fact that LLVM assumes bit casts
> >> across address-spaces are lossless.)
> > [Villmow, Micah] Is that something that should be probably be
> > reconsidered given adding support for variable sized address spaces?
>
> My thinking is that we should ban bitcasts which cross address-spaces,
> and introduce a new instruction to represent them. (I know it's a lot
> of work to add a new instruction, but I don't see any good
> alternative.)

Out of curiosity, for what are these currently used? Unless you happen
to know that some aliasing exists, I don't see how bitcasting a pointer
in one address space to another makes any sense.

[Villmow, Micah] In OpenCL this is explicitely disallowed at the source level, but I could see this being useful for say the X86 backend where you really only have a global address space and other address spaces exist in the source language(i.e. local/constant in OpenCL). I'm not against adding this restriction, but I'm sure others are.

Eli,
Here is the first of many patches that adds support for specifying different pointer sizes for different address spaces.
This is only the modifications to TargetData and not all the changes to the backends/optimizers. There should be no functional changes here since the default value is what the current value is.

After this is approved, my goal is the following:
1) Add a few interfaces to various functions that simplify retrieving address space information.
2) Update all of the optimizations to use address space information when querying the pointer type.
3) Update the backends to follow suite
4) Update the clients(clang, etc..) to use the correct API.
5) remove the default arguments so that future users must explicitly specify an address space.

I'm not sure how to add tests for this since no backend uses it yet, but i'll try to figure something out.
Micah

Doh! hit send too soon, patch attached.

multiple_pointer_target_data.patch (16.8 KB)

Since the TargetData/Bitcast issue is on hold pending an LLVM dev meeting BOF it seems, I am revisiting this patch.

This should have no functional changes, but only allow LLVM to understand different pointer sizes for the backends that wish to use it.

Micah

multiple_pointer_target_data.patch (16.8 KB)