This is an archive of the discontinued LLVM Phabricator instance.

[GlobalISel][NFC]: Add interface to reserve memory in GISelWorklist
ClosedPublic

Authored by aditya_nandakumar on Feb 11 2019, 1:19 PM.

Details

Summary

Added an interface to specify how many elements to reserve to GISelWorkList.
This change resulted in a 12% compile time improvement in the combiner pass(es), and 2.5% improvement in the legalizer.

Diff Detail

Event Timeline

arsenm added inline comments.Feb 11 2019, 1:50 PM
include/llvm/CodeGen/GlobalISel/GISelWorkList.h
46

size_t

lib/CodeGen/GlobalISel/Combiner.cpp
114

size_t

115

It seems weird to me to scan over the function just to estimate this. Can you start with some large constant and increase with each block as it's seen?

paquette added inline comments.Feb 11 2019, 2:09 PM
lib/CodeGen/GlobalISel/Combiner.cpp
114

MFSize?

115

MF.getInstructionCount() does this

aditya_nandakumar marked 3 inline comments as done.Feb 11 2019, 2:11 PM
aditya_nandakumar added inline comments.
lib/CodeGen/GlobalISel/Combiner.cpp
115

What according to you is a large constant? Also could you elaborate on what you mean by increase with each block as it's seen? IIUC are you suggesting NumBlocks * some_large_constant?

aditya_nandakumar marked 2 inline comments as done.Feb 11 2019, 2:15 PM
aditya_nandakumar added inline comments.
lib/CodeGen/GlobalISel/Combiner.cpp
114

Thanks. Will update.

115

Didn't know it existed. Will change to it.

arsenm added inline comments.Feb 11 2019, 3:08 PM
lib/CodeGen/GlobalISel/Combiner.cpp
115

Well both the number of blocks and count of instructions in the block are scans of the entire linked lists IIRC. You could update the estimate at the end of the loop when you can know how many instructions are around. I don't know if it matters. If I were to randomly pick an initial number I would guess thousands?

aditya_nandakumar marked an inline comment as done.Feb 11 2019, 3:23 PM
aditya_nandakumar added inline comments.
lib/CodeGen/GlobalISel/Combiner.cpp
115

I just realized that in the combiner it's silly that we're recomputing this for every loop - I'm not sure if your original comment was addressing that or in general about traversing linked lists even once (I assumed it was the latter). I also don't think it matters if we care about the exact size during each iteration - if we're doing the full list traversal, I'll definitely move this out of the main loop and use an old estimate.
Alternatively I can use something like 4096 * getNumBlocks() if that works better.. I can run some numbers to see how this performs.

aemerson added inline comments.Feb 11 2019, 4:36 PM
lib/CodeGen/GlobalISel/Combiner.cpp
115

I think that ilist's size() is a linear time linked list walk.

Changed the strategy to fix problems of DenseMap migration as well as silly traversals of MachineFunction just to estimate the size.

arsenm added inline comments.Feb 13 2019, 1:13 PM
include/llvm/CodeGen/GlobalISel/GISelWorkList.h
86

This is redundant

103

Ditto

paquette added inline comments.Feb 13 2019, 1:30 PM
include/llvm/CodeGen/GlobalISel/GISelWorkList.h
70–72

Don't need braces here.

88–89

I think that in standard LLVM code style, the return should be on a newline. (Or, that's what clang-format does on my end anyway)

if (It == WorklistMap.end())
    return;

Removed redundant NDEBUG checks.

aditya_nandakumar marked an inline comment as done.Feb 13 2019, 1:39 PM
aditya_nandakumar added inline comments.
include/llvm/CodeGen/GlobalISel/GISelWorkList.h
88–89

Clang format does not do that for me.

Addressed some formatting related feedback.

aditya_nandakumar marked 4 inline comments as done.Feb 13 2019, 1:40 PM
aemerson accepted this revision.Feb 14 2019, 3:05 PM

LGTM, thanks.

This revision is now accepted and ready to land.Feb 14 2019, 3:05 PM