HomePhabricator

[IR] Use a binary search in DataLayout::getAlignmentInfo

Description

[IR] Use a binary search in DataLayout::getAlignmentInfo

Summary:
We currently do a linear scan through all of the Alignments array entries anytime getAlignmentInfo is called. I noticed while profiling compile time on a -O2 opt run that this function can be called quite frequently and was showing about as about 1% of the time in callgrind.

This patch puts the Alignments array into a sorted order by type and then by bitwidth. We can then do a binary search. And use the sorted nature to handle the special cases for INTEGER_ALIGN. Some of this is modeled after the sorting/searching we do for pointers already.

This reduced the time spent in this routine by about 2/3 in the one compilation I was looking at.

We could maybe improve this more by using a DenseMap to cache the results, but just sorting was easy and didn't require extra data structure. And I think it made the integer handling simpler.

Reviewers: sanjoy, davide, majnemer, resistor, arsenm, mehdi_amini

Reviewed By: arsenm

Subscribers: arsenm, llvm-commits

Differential Revision: https://reviews.llvm.org/D31232

Details

Committed
ctopperMar 22 2017, 11:15 PM
Reviewer
arsenm
Differential Revision
D31232: [IR] Use a binary search in DataLayout::getAlignmentInfo
Parents
rL298578: [IR] Mark Use::getUser and Use::getImpliedUse as LLVM_READONLY.
Branches
Unknown
Tags
Unknown