How to use map/set in LLVM to disable automatic sorting?

Project Infrastructure LLVM Dev List Archives
1

Hello LLVM,

We found that many LLVM passes use map/set containers to increase the searching efficiency.

Although map/set has automatic sorting feature, the results after the same pass transformation are still the same.

If native map/set, we think the order after inserting new element may change.

So, my question is, does LLVM use its own-defined structure instead of native map/set? Or, LLVM disables such feature for map/set?

Could you give a detailed explanation?

Thanks!

Kang

2

Hello LLVM,

We found that many LLVM passes use map/set containers to increase the
searching efficiency.

Although map/set has automatic sorting feature, the results after the
same pass transformation are still the same.

If native map/set, we think the order after inserting new element may
change.

So, my question is, does LLVM use its own-defined structure instead of
native map/set?

Yes, in places where iteration order matters, we try really hard to use ADT's that have a deterministic iteration order, so that the passes themselves remain deterministic.

See: LLVM Programmer’s Manual — LLVM 18.0.0git documentation

Jon

3

I don’t really understand the question, can you provide an example of passes and what problem do you expect?

4

Jon,

Thanks a lot for your reply!
We will look the detailed implementation in LLVM.
In my opinion, it seems that SetVector class just defines such type, which is has the same efficiency with set, but stays a stable order.

Time-efficiency for set lookup should be the same.

Space-efficiency on the other hand is lost because the addition of the vector storage needed for the stable iteration order.

Jon