help please: how to sort the contents of a "SymbolTableListTraits<GlobalVariable>"?

[Abe_Skolnik]

Dear all,

In the process of trying to add optimization for better layout of global variables, I have run up against a roadblock: I don`t seem to be able to sort the contents of a "SymbolTableListTraits<GlobalVariable>" -- or even swap two elements in that list -- without causing LLVM to crash.

I have tried writing a comparator class and then using "llvm::iplist< NodeTy, Traits >::sort(Compare comp)" [<http://llvm.org/docs/doxygen/html/classllvm_1_1iplist.html#a81afd2c47bb276cd50c78c74b3f92ec3&gt;\], since "llvm::Module::GlobalListType" [<http://llvm.org/docs/doxygen/html/classllvm_1_1Module.html#accd281de11bad056a32f319d7facafe3&gt;\] is an alias for "SymbolTableList<GlobalVariable>" and according to the Web-based documentation every instantiation of SymbolTableList [<http://llvm.org/docs/doxygen/html/classllvm_1_1SymbolTableList.html&gt;\] is-an instantiation of "iplist" [<http://llvm.org/docs/doxygen/html/classllvm_1_1iplist.html&gt;\]. This call to "sort" crashed badly. I`ll paste in the code for this attempt below [simplified for clarity], but not the code for the others since they are longer and more "desperate".

All my attempts to write anything that might be the innermost operation in a "sort" I would write myself either would not compile or would compile and crash at run-time. The ones that wouldn`t compile wouldn`t compile because GlobalVariable has an explicitly-deleted copy constructor and no move constructor [so "std::move(...)" was not usable to solve the problem].

BTW: I am [and was] doing this in the context of "OptimizeGlobalVars" which is in "llvm/lib/Transforms/IPO/GlobalOpt.cpp".

If anybody reading this can provide some assistance, I`d be much obliged.

Regards,

Abe

   struct GV_alignment_comparator {
     bool operator()(const GlobalVariable& L, const GlobalVariable& R) {
       return L.getAlignment() < R.getAlignment();
     }
   };

   // 'M' is a "Module &"

/* this crashes BADLY...
   M.getGlobalList().sort( GV_alignment_comparator() );
   Changed = true;
*/

[dexonsmith]

Dear all,

In the process of trying to add optimization for better layout of global variables, I have run up against a roadblock: I don`t seem to be able to sort the contents of a "SymbolTableListTraits<GlobalVariable>" -- or even swap two elements in that list -- without causing LLVM to crash.

I have tried writing a comparator class and then using "llvm::iplist< NodeTy, Traits >::sort(Compare comp)" [<LLVM: llvm::iplist< T, Options > Class Template Reference], since "llvm::Module::GlobalListType" [<LLVM: llvm::Module Class Reference] is an alias for "SymbolTableList<GlobalVariable>" and according to the Web-based documentation every instantiation of SymbolTableList [<http://llvm.org/docs/doxygen/html/classllvm_1_1SymbolTableList.html&gt;\] is-an instantiation of "iplist" [<http://llvm.org/docs/doxygen/html/classllvm_1_1iplist.html&gt;\]. This call to "sort" crashed badly.

Crashed how? Have you turned on ASan? You might file a PR (feel free to CC me). I recommend attaching a minimal reproduction... I assume you can reproduce this in a unit test? That's easiest.

I just had a look at the sort code, and I don't see anything obviously wrong.

[Abe_Skolnik]

Dear sir,

Thanks for your reply. I apologize for taking a few days to reply.

Crashed how?

Please see the below.

Have you turned on ASan?

Not yet, but thanks for the suggestion. I guess I will try to rebuild my modified Clang+LLVM with addr. san. and see what happens.

I recommend attaching a minimal reproduction...

Well, since I`m hacking on LLVM itself, this is not 100% trivial. I will explain.

The first hurdle I had to overcome was the fact that the "GlobalVariable" class had an explicitly-deleted copy ctor and no move ctor. I dealt with this by writing a copy ctor; I`ll paste that in below.

A perhaps-important point is that I don`t know _why_ the "GlobalVariable" class had an explicitly-deleted copy ctor and no move ctor. As an experiment, I moved forward with the hypothesis that this was simply because neither was needed at the time and the default [i.e. compiler-inserted] copy ctor would have been wrong. I hope the one _I_ wrote is _right_.

I assume you can reproduce this in a unit test?

Well, it doesn`t take a long program-under-compilation to make this fail. As before, I will paste something in after my sign-off.

Regards,

Abe

----- added near the end of "OptimizeGlobalVars" in "llvm/lib/Transforms/IPO/GlobalOpt.cpp", amongst many other things I added to that routine -----

struct GV_alignment_comparator {
    bool operator()(const GlobalVariable& L, const GlobalVariable& R) {
      return L.getAlignment() < R.getAlignment();
    }
};

if (unsorted) {
    M.getGlobalList().sort( GV_alignment_comparator() );
    Changed = true;
}

----- added to "llvm/lib/IR/Globals.cpp" [and commented out the relevant deletion in "llvm/include/llvm/IR/GlobalVariable.h"] -----

GlobalVariable::GlobalVariable(const GlobalVariable& GV) : GlobalVariable( GV.getValueType(), GV.isConstant(), GV.getLinkage() ) { // copy ctor
    copyAttributesFrom(&GV);
}

main_with_3_globals.c

[majnemer]

Dear sir,

Thanks for your reply. I apologize for taking a few days to reply.

Crashed how?

Please see the below.

Have you turned on ASan?

Not yet, but thanks for the suggestion. I guess I will try to rebuild my
modified Clang+LLVM with addr. san. and see what happens.

I recommend attaching a minimal reproduction...

Well, since I`m hacking on LLVM itself, this is not 100% trivial. I will
explain.

The first hurdle I had to overcome was the fact that the "GlobalVariable"
class had an explicitly-deleted copy ctor and no move ctor. I dealt with
this by writing a copy ctor; I`ll paste that in below.

A perhaps-important point is that I don`t know _why_ the "GlobalVariable"
class had an explicitly-deleted copy ctor and no move ctor. As an
experiment, I moved forward with the hypothesis that this was simply
because neither was needed at the time and the default [i.e.
compiler-inserted] copy ctor would have been wrong. I hope the one _I_
wrote is _right_.

You should never be copying or moving around Values. An llvm::Value (which
GlobalVariable is a subtype of) should exist only in the heap. We play
games where use lists are allocated before the object which will not work
at all with stack based allocations.

[Abe_Skolnik]

You should never be copying or moving around Values.

Why not? Is that because of this thing you also wrote in the same message: "use lists are allocated before the object"?

An llvm::Value (which GlobalVariable is a subtype of) should exist only in the heap.

Trying to sort a container of such objects doesn`t require me to contradict that advice. The code I have added only uses "GlobalVariable" via pointers and references, with the possible exception of the newly-added copy ctor.

Thanks for your reply.

Regards,

Abe

[Daniel_Berlin1]

Among other things.

They are simply not currently built to be relocated.
attempts to do so will likely result in a huge mess.

my strong recommendation here would be to stop trying to go down this path,
and instead, if you want a sorted list, just put them in a separate
container and sort them.

[mehdi_amini]

The issue is that the “sort” method of iplist is delegating a bunch of things to SymbolTableListTraits, and the later makes some assumption that are broken in this case.
The offending path is:

1. iplist:sort() wANTS to split the list in two
2. it creates a new empty list, and tries to splice a subpart of the existing list into the new one:

// Split the list into two.
iplist RightHalf;
RightHalf.splice(RightHalf.begin(), *this, Center, end());

3. split will call back into: SymbolTableListTraits::transferNodesFromList. Unfortunately this assumes that the list is owned by a Module (see SymbolTableListTraits ::getListOwner())

This obviously breaks badly in this case.

Note: I don’t know why you needed a copy/move ctor for global value, I was able to build with your “patch” to GlobalOpt.cpp without changing anything else.

[Abe_Skolnik]

David Majnemer wrote:

   You should never be copying or moving around Values.

Abe wrote:
   Why not? Is that because of this thing you also wrote in the same
   message: "use lists are allocated before the object"?

Daniel Berlin wrote:
   Among other things.

   They are simply not currently built to be relocated.
   attempts to do so will likely result in a huge mess.

   my strong recommendation here would be to stop trying to go down this path,

Abe: I tried.

[Daniel again]

   and instead, if you want a sorted list,
   just put them in a separate container and sort them.

Yup. I tried that. It went "boom".

Maybe the essence what I did wrong when I tried it earlier was that the objects were effectively on the stack. However, if/when using a typical implementation of either "std::list" or "std::vector", only the container metadata should be on the stack [when the container is a local], with the containees on the heap, no?

Regards,

Abe

[Abe_Skolnik]

The issue is that the “sort” method of iplist is delegating a bunch of things to SymbolTableListTraits, [...]

Thanks very much for explaining.

Note: I don’t know why you needed a copy/move ctor for global value,
I was able to build with your “patch” to GlobalOpt.cpp without changing anything else.

That was probably due to a copy/move ctor being needed for {my attempts at building a working "sort" for the GVs myself}. None of those attempts worked, in the end, but there was more than one failure modality. Some of the attempts wouldn`t even compile without a copy/move ctor for "GlobalVariable", which was understandable considering the code in question.

Regards,

Abe

[mehdi_amini]

The thing is that a “SymbolTable” is a “iplist” (it inherit from it) and, iplist has a “sort()” method, it is not clear why we can’t sort then?

The fact that SymbolTable implementation is breaking one of its public method does not seem right to me.

Also, in general, the design assuming any instance of a SymbolTable is owned by a Module and inspecting the “parent” using magic trick, seems … broken.

[Daniel_Berlin1]

You should never be copying or moving around Values.

Why not? Is that because of this thing you also wrote in the same
message: "use lists are allocated before the object"?

Among other things.

They are simply not currently built to be relocated.
attempts to do so will likely result in a huge mess.

my strong recommendation here would be to stop trying to go down this
path, and instead, if you want a sorted list, just put them in a separate
container and sort them.

The thing is that a “SymbolTable” is a “iplist” (it inherit from it) and,
iplist has a “sort()” method, it is not clear why we can’t sort then?

Sorry, let me be 100% clear: I think it sucks, and you are 100% right.
I just meant "in terms of path of least resistance" for a user who may not
want to go diving into the depths of deep llvm implementation details just
to try to get something simple working.

The fact that SymbolTable implementation is breaking one of its public
method does not seem right to me.

Also, in general, the design assuming any instance of a
SymbolTable<GlobalVariabl> is owned by a Module and inspecting the “parent”
using magic trick, seems … broken.

Yup.
But i think this is not the only iplist you will find this in.