Page MenuHomePhabricator

MergeFuncs should handle dynamic GEPs
Needs ReviewPublic

Authored by pete on Jan 25 2015, 11:19 PM.

Details

Reviewers
dyatkovskiy
Summary

When compiling std::vector<float> and std::vector<int>, both get a function called push_back_slow_path. This function could be merged except that one does float[i] and the other int[i]. These are identical given that int and float have the same size and alignment.

This patch teaches MergeFunctions about dynamic GEPs, which must return the same offset given 'index * element size' for both LHS and RHS.

This reduces the size of an LTO'd llc by almost 1.5%.

Diff Detail

Event Timeline

pete updated this revision to Diff 18742.Jan 25 2015, 11:19 PM
pete retitled this revision from to MergeFuncs should handle dynamic GEPs.
pete updated this object.
pete edited the test plan for this revision. (Show Details)
pete added a reviewer: dyatkovskiy.
pete added a subscriber: Unknown Object (MLST).

Added Stepan as a reviewer.

dyatkovskiy edited edge metadata.Jan 28 2015, 6:02 AM

Hi Pete,
Thanks for patch. The idea looks good, but I'm still in middle of review..

lib/Transforms/IPO/MergeFunctions.cpp
959

"fielf" => "field"

964

May be "cast<ConstantInt>"?

990

I stopped here :-)

pete added inline comments.Jan 28 2015, 1:26 PM
lib/Transforms/IPO/MergeFunctions.cpp
959

Missed that. Thanks.

964

I thought that too at first, but then i discovered the magic of vector GEPs. About to upload a patch which does this the right way, i.e., we handle the scalar and vector cases.

pete updated this revision to Diff 18918.Jan 28 2015, 1:28 PM
pete edited edge metadata.

Updated to actually handle vector GEPs. Added positive and negative test cases for vector GEP merging.

Hello Pete,
I've looked at this patch. You add support for dynamic GEPs. I was on non-llvm project for a while, and dynamic GEP is quite new thing, at least when you can use arrays as indices. It also a bit strange, that we can use only splat arrays.. Anyways, I suppose we should get vector of pointers in this case, right? Can you provide me with links, where I can read more about?

I've left few inline comments.
Also, I've launched test-suite for it..

test/Transforms/MergeFunc/gep.ll
64

Dynamic GEP is quite new thing. Do we have specs for dynamic GEPs somewhere already? In particular rule definition for splat values?

test/Transforms/MergeFunc/gep2.ll
55

What would happen, if I'll create same method, but change this line to:
%offset_i = getelementptr %vector_char4_ptr %bc_ptr, <4 x i32><i32 0, i32 0, i32 0, i32 0>, <4 x i32><i32 1, i32 1, i32 1, i32 1>, <4 x i64> %i, <4 x i32><i32 2, i32 2, i32 2, i32 0>
It looks like your patch gonna merge such functions. Is it right?

pete added a comment.Feb 2 2015, 9:54 AM

Hi Stepan

From LangRef (http://llvm.org/docs/LangRef.html#getelementptr-instruction), the interesting part for structures is that the GEP indices must be the same value. If using a vector, it must be a splat of a constant. I guess using a vector of the same constant is redundant (compared to a scalar) except that it keeps all the GEP indices matching in terms of all being vectors or all being scalar. The part you want here is:

"When indexing into a (optionally packed) structure, only i32 integerconstants are allowed (when using a vector of indices they must all be the same i32 integer constant)”

For arrays or pointers, it says:

"When indexing into an array, pointer or vector, integers of any width are allowed, and they are not required to be constant”

The main new piece of functionality in MergeFuncs here is that for dynamic GEPs, it should be able to work out that 2 GEPs are equivalent even when the index is dynamic. This is true when the underlying type has the same offset from a[i] to a[i + 1]. Eg, indexing a float[] vs int[] will give you the same offset for the same index ‘i’. If any of this is unclear in the tests or patch comments, please let me know and i’ll be happy to improve them.

test/Transforms/MergeFunc/gep.ll
64

I think I answered this in the main comment at the end. Let me know if anything else needs clarification.

test/Transforms/MergeFunc/gep2.ll
55

Ah, you're totally right. If you try to merge 2 GEPs, both with non-splat vectors, then both will give nullptr on these lines:

ConstIntL = dyn_cast_or_null<ConstantInt>(ConstL->getSplatValue());
ConstIntR = dyn_cast_or_null<ConstantInt>(ConstR->getSplatValue());

and then we'll get past this test, and crash

if (int Res = cmpNumbers(!!ConstIntL, !!ConstIntR))
  return Res;

Nice catch! I'll update the code and tests to handle this.

Hi Pete, I'll go on vocation from next week. And will offline till 10th of March. If you have some diffs to show, please don't hesitate for too long ;-)

pete updated this revision to Diff 19604.Feb 9 2015, 1:04 PM

Ah, sorry about that. I forgot you were waiting on me. I was about to ping this :)

Updated code to handle non-splat vector constants.

I actually reordered a bunch of stuff here so that we detect early if the GEPs have identical types and operands, and can just return on that case. If that fails, we check for a DataLayout, and if we have one we do the offset checking for dynamic offsets. If we fail to find a splat constant, then at that point we know the GEPs weren't identical so we just use their types to order them which is what would have happened in the code prior to this patch.

I added a new test case in gep2.ll which checks that 2 vector GEPs with different non-splat constants don't merge. Before I made this fix that test would fire the assert you spotted.