Add default address space for functions to the data layout (1/3)

[dylanmckay]

Summary

This adds initial support for letting targets specify which address
spaces their functions should reside in by default.

If a function is created by a frontend, it will get the default address space specified in the DataLayout, unless the frontend explicitly uses a more general llvm::Function constructor. Function address spaces will become a part of the bitcode and textual IR forms, as we do not have access to a data layout whilst parsing LL.

It will be possible to write IR that explicitly has addrspace(n) on a function. In this case, the function will reside in the specified space, ignoring the default in the DL.

This is the first step towards placing functions into the correct
address space for Harvard architectures.

Full patchset

• Add program address space to data layout D37052
• Require address space to be specified when creating functions D37054
• [clang] Require address space to be specified when creating functions D37057

[dylanmckay]

Fix a bug with parsing the address space

I seem to have lost this piece of code at some point, it used to exist.

[dylanmckay]

Add tests

[dylanmckay]

Uploaded the wrong diff, here's the right one

[asb]

From the perspective of "does the code do what it intends to and meet LLVM coding standards?" this looks good to me.

[kparzysz]

docs/LangRef.rst

1883 ↗

(On Diff #112341)

Aren't switch tables considered "data" in a Harvard architecture?

[dylanmckay]

docs/LangRef.rst

1883 ↗

(On Diff #112341)

I think in the strictest sense, you are correct.

However, I think in the real world, it makes more sense for this kind of data to live in program memory.

For example, in the AVR, all global variables (regardless of address space) live inside the executable, and this live inside program memory. The routines that run on device startup will find all variables that live in RAM, and then must copy everything over.

This is necessary because RAM is always initialised to zero on startup, if you want to have specific data in RAM, it _needs_ to be copied over.

In the cast of switch tables, we should not need to copy them over to RAM. They will never change, along with the fact that RAM accesses take longer than program memory. I imagine this is true of other Harvard architectures as well.

On top of this, if switch tables lived in RAM it would mean that any switches converted into tables by SimplifyCFG will branch on uninitialised memory if run without startup code. This is not a particularly strong argument as lots of bad things happen when run without startup code, but I would hope that we could at least evaluate a switch without it.

One other side note is that not all AVRs have RAM, and so switch tables would need to live in program memory in these chips. Again, not a super strong argument though because if you have no stack, you probably shouldn't be using LLVM.

tl;dr I think this is more a matter of practicality rather than what we consider data versus code in the academic sense.

[kparzysz]

docs/LangRef.rst

1883 ↗

(On Diff #112341)

My concern here is that a subsequent patch always puts switch tables in the program memory. I don't know if that's valid for all architectures.

[theraven]

docs/LangRef.rst

1883 ↗

(On Diff #112341)

I agree. Program memory is correct for us as well, but on a number of microcontrollers you don't have load instructions at all for the program memory and so they need to be in the data-ROM address space.

[arsenm]

Is the intent to allow different functions to have different address spaces and this is the default, or all functions have the one address space in the datalayout? I think the description should clarify.

lib/Target/AVR/AVRTargetMachine.cpp

28 ↗

(On Diff #112341)

I think changing the AVR layout is a separate patch

[asb]

docs/LangRef.rst

1883 ↗

(On Diff #112341)

Putting jump tables in a data section is something the ARM backend supported as of rL289784 in order to support execute-only code (i.e. no loads allowed from the code section). Would this sort of thing be better off moving towards using separating address spaces for code and data?

[dylanmckay]

Is the intent to allow different functions to have different address spaces and this is the default

Yes. I will update the description to be clearer.

docs/LangRef.rst

1883 ↗

(On Diff #112341)

That makes sense - what are thoughts on creating some sort of target-specific hook (probably TargetTransformInfo) specific to switch tables that can be overridden and use that instead?

[asb]

docs/LangRef.rst

1883 ↗

(On Diff #112341)

That sounds interesting to me, but it could be a bit of a rabbit hole. @prakhar, @rengolin - do you have any thoughts on this? Did you consider such an approach for the ARM execute-only support?

[rengolin]

Has there been an RFC on this?

Despite being a simple change, I can't foresee all the consequences. Superficially, it looks harmless, but I'd rather more people on the list could have a look at it too.

lib/Target/AVR/AVRTargetMachine.cpp

28 ↗

(On Diff #112341)

Indeed. It would be easier to just revert this one change on its own if bots start break, without reverting the whole set of changes.

[uabelho]

In D37052#853636, @rengolin wrote:

Has there been an RFC on this?

http://lists.llvm.org/pipermail/llvm-dev/2017-July/115245.html

[prakhar]

docs/LangRef.rst

1883 ↗

(On Diff #112341)

For execute-only on Arm, the only concern at the compiler level is ensuring that all literal loads are performed from a separate data section and not from a code section. The actual enforcement of the execute-only policy is implementation dependent, so this was not considered. Additionally, I believe it is possible for these sections to be loaded into the same address space, but with the code section at a specific execute-only base address, so this feature may not be directly applicable. Again, this is all dependent on the implementation.

I have no further comment wrt this patch.

[dylanmckay]

• Remove the switch table stuff for a later patch
• Rebased on top of trunk

[dylanmckay]

Remove switch table from the docs

[dylanmckay]

docs/LangRef.rst

1883 ↗

(On Diff #112341)

Very helpful comments, thanks everyone.

It is clear that a more general solution must be found for placing lookup tables into the right address space.

This might be tricky because if we require a target-specific hook, it cannot live in TargetTransformInfo as I've recently read that logic in this class must not be required for correctness as there may not be a TTI present. In that case, I am unsure at the moment where such a hook could live whilst still being accessible to the SimplifyCfg pass. Anyway, I'll look into that further in a later patch.

For now, I've removed the switch table related code from this patchset.

[bjope]

include/llvm/IR/GlobalValue.h

185 ↗

(On Diff #125888)

Is this a preparation for some future patch? I can't see that it is used in this patch (and it does not seem to be related to adding support for "P" in DataLayout).

[bjope]

lib/IR/DataLayout.cpp

417 ↗

(On Diff #125888)

I'm not exactly sure what the criteria is for this method (or how it is used).
But maybe the ProgramAddrSpace member should be compared as well?

PS. I'm trying to compare your solution with the solution we have in our out-of-tree target, and we have something similar to the ProgramAddrSpace member (we call it FunctionPointerAddressSpace and use 'F' instead of 'P'). As it happens we do not compare the FunctionPointerAddressSpace in this operator==, but I guess that is just something we forgot to add.

[dylanmckay]

• Move GlobalValue::getAddressSpace() to next patch
• Add ProgramAddressSpace to DataLayout::operator==

[dylanmckay]

include/llvm/IR/GlobalValue.h

185 ↗

(On Diff #125888)

You are right - this is for a future patch. There is no reason why it should be on this patch however.

Moved to D37054,

lib/IR/DataLayout.cpp

417 ↗

(On Diff #125888)

Good catch, I have added this check

[dylanmckay]

Ping

[theraven]

Looks fine to me.

[arichardson]

test/Assembler/invalid-datalayout-alloca-addrspace.ll

3 ↗

(On Diff #126267)

Shouldn't this be P16777216

[dylanmckay]

Rebase and typo fix from @arichardson

[dylanmckay]

test/Assembler/invalid-datalayout-alloca-addrspace.ll

3 ↗

(On Diff #126267)

Good catch, fixed

llvm/trunk/docs/LangRef.rst

``e``
     location.
 ``S<size>``
     Specifies the natural alignment of the stack in bits. Alignment
     promotion of stack variables is limited to the natural stack
     alignment to avoid dynamic stack realignment. The stack alignment
     must be a multiple of 8-bits. If omitted, the natural stack
     alignment defaults to "unspecified", which does not prevent any
     alignment promotions.
+``P<address space>``
+    Specifies the address space that corresponds to program memory.
+    Harvard architectures can use this to specify what space LLVM
+    should place things such as functions into. If omitted, the
+    program memory space defaults to the default address space of 0,
+    which corresponds to a Von Neumann architecture that has code
+    and data in the same space.
 ``A<address space>``
-    Specifies the address space of  objects created by '``alloca``'.
+    Specifies the address space of objects created by '``alloca``'.
     Defaults to the default address space of 0.
 ``p[n]:<size>:<abi>:<pref>:<idx>``
     This specifies the *size* of a pointer and its ``<abi>`` and
     ``<pref>``\erred alignments for address space ``n``. The fourth parameter
     ``<idx>`` is a size of index that used for address calculation. If not
     specified, the default index size is equal to the pointer size. All sizes
     are in bits. The address space, ``n``, is optional, and if not specified,
     denotes the default address space 0. The value of ``n`` must be

llvm/trunk/include/llvm/IR/DataLayout.h

 /// target being codegen'd to.
 class DataLayout {
 private:
   /// Defaults to false.
   bool BigEndian;
 
   unsigned AllocaAddrSpace;
   unsigned StackNaturalAlign;
+  unsigned ProgramAddrSpace;
 
   enum ManglingModeT {
     MM_None,
     MM_ELF,
     MM_MachO,
     MM_WinCOFF,
     MM_WinCOFFX86,
     MM_Mips
public:
   ~DataLayout(); // Not virtual, do not subclass this class
 
   DataLayout &operator=(const DataLayout &DL) {
     clear();
     StringRepresentation = DL.StringRepresentation;
     BigEndian = DL.isBigEndian();
     AllocaAddrSpace = DL.AllocaAddrSpace;
     StackNaturalAlign = DL.StackNaturalAlign;
+    ProgramAddrSpace = DL.ProgramAddrSpace;
     ManglingMode = DL.ManglingMode;
     LegalIntWidths = DL.LegalIntWidths;
     Alignments = DL.Alignments;
     Pointers = DL.Pointers;
     NonIntegralAddressSpaces = DL.NonIntegralAddressSpaces;
     return *this;
   }
 
public:
   /// Returns true if the given alignment exceeds the natural stack alignment.
   bool exceedsNaturalStackAlignment(unsigned Align) const {
     return (StackNaturalAlign != 0) && (Align > StackNaturalAlign);
   }
 
   unsigned getStackAlignment() const { return StackNaturalAlign; }
   unsigned getAllocaAddrSpace() const { return AllocaAddrSpace; }
 
+  unsigned getProgramAddressSpace() const { return ProgramAddrSpace; }
+
   bool hasMicrosoftFastStdCallMangling() const {
     return ManglingMode == MM_WinCOFFX86;
   }
 
   bool hasLinkerPrivateGlobalPrefix() const { return ManglingMode == MM_MachO; }
 
   StringRef getLinkerPrivateGlobalPrefix() const {
     if (ManglingMode == MM_MachO)

llvm/trunk/lib/IR/DataLayout.cpp

 
 void DataLayout::reset(StringRef Desc) {
   clear();
 
   LayoutMap = nullptr;
   BigEndian = false;
   AllocaAddrSpace = 0;
   StackNaturalAlign = 0;
+  ProgramAddrSpace = 0;
   ManglingMode = MM_None;
   NonIntegralAddressSpaces.clear();
 
   // Default alignments
   for (const LayoutAlignElem &E : DefaultAlignments) {
     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
                  E.TypeBitWidth);
   }

 
 /// Convert bits into bytes. Assert if not a byte width multiple.
 static unsigned inBytes(unsigned Bits) {
   if (Bits % 8)
     report_fatal_error("number of bits must be a byte width multiple");
   return Bits / 8;
 }
 
+static unsigned getAddrSpace(StringRef R) {
+  unsigned AddrSpace = getInt(R);
+  if (!isUInt<24>(AddrSpace))
+    report_fatal_error("Invalid address space, must be a 24-bit integer");
+  return AddrSpace;
+}
+
 void DataLayout::parseSpecifier(StringRef Desc) {
   StringRepresentation = Desc;
   while (!Desc.empty()) {
     // Split at '-'.
     std::pair<StringRef, StringRef> Split = split(Desc, '-');
     Desc = Split.second;
 
     // Split at ':'.
case 'n':  // Native integer types.
           break;
         Split = split(Rest, ':');
       }
       break;
     case 'S': { // Stack natural alignment.
       StackNaturalAlign = inBytes(getInt(Tok));
       break;
     }
+    case 'P': { // Function address space.
+      ProgramAddrSpace = getAddrSpace(Tok);
+      break;
+    }
     case 'A': { // Default stack/alloca address space.
-      AllocaAddrSpace = getInt(Tok);
-      if (!isUInt<24>(AllocaAddrSpace))
-        report_fatal_error("Invalid address space, must be a 24bit integer");
+      AllocaAddrSpace = getAddrSpace(Tok);
       break;
     }
     case 'm':
       if (!Tok.empty())
         report_fatal_error("Unexpected trailing characters after mangling specifier in datalayout string");
       if (Rest.empty())
         report_fatal_error("Expected mangling specifier in datalayout string");
       if (Rest.size() > 1)

 }
 
 void DataLayout::init(const Module *M) { *this = M->getDataLayout(); }
 
 bool DataLayout::operator==(const DataLayout &Other) const {
   bool Ret = BigEndian == Other.BigEndian &&
              AllocaAddrSpace == Other.AllocaAddrSpace &&
              StackNaturalAlign == Other.StackNaturalAlign &&
+             ProgramAddrSpace == Other.ProgramAddrSpace &&
              ManglingMode == Other.ManglingMode &&
              LegalIntWidths == Other.LegalIntWidths &&
              Alignments == Other.Alignments && Pointers == Other.Pointers;
   // Note: getStringRepresentation() might differs, it is not canonicalized
   return Ret;
 }
 
 DataLayout::AlignmentsTy::iterator

llvm/trunk/test/Assembler/datalayout-program-addrspace.ll

+; RUN: llvm-as < %s | llvm-dis | FileCheck %s
+
+; CHECK: target datalayout = "P1"
+target datalayout = "P1"
+

llvm/trunk/test/Assembler/invalid-datalayout-alloca-addrspace.ll

 ; RUN: not llvm-as < %s 2>&1 | FileCheck %s
 
 target datalayout = "A16777216"
-; CHECK: Invalid address space, must be a 24bit integer
+; CHECK: Invalid address space, must be a 24-bit integer

llvm/trunk/test/Assembler/invalid-datalayout-program-addrspace.ll

+; RUN: not llvm-as < %s 2>&1 | FileCheck %s
+
+; CHECK: Invalid address space, must be a 24-bit integer
+target datalayout = "P16777216"