This is an archive of the discontinued LLVM Phabricator instance.

[ConstantHoisting] Avoid hoisting constants in GEPs that index into a struct type.
ClosedPublic

Authored by aoli on Jun 23 2017, 3:12 PM.

Details

Summary

Indices for GEPs that index into a struct type should always be
constants. This added more checks in collectConstantCandidates: which make
sure constants for GEP pointer type are not hoisted.

This fixed Bug https://bugs.llvm.org/show_bug.cgi?id=33538

Event Timeline

aoli created this revision.Jun 23 2017, 3:12 PM
aoli updated this revision to Diff 103786.Jun 23 2017, 3:15 PM

Move headers to a proper position.

aoli edited the summary of this revision. (Show Details)Jun 23 2017, 3:51 PM
aoli updated this revision to Diff 103791.Jun 23 2017, 3:52 PM

Update tests.

aoli added a subscriber: llvm-commits.
pirama added a reviewer: rnk.Jun 26 2017, 10:26 AM
pirama added inline comments.
test/Transforms/ConstantHoisting/ARM/gep-struct-index.ll
13

Can you add a comment here clarifying that the first index into the pointer is hoisted, but the second index into the struct isn't?

ributzka edited edge metadata.Jun 26 2017, 10:30 AM

Why not fix AddressingModeMatcher not to crash first?

aoli updated this revision to Diff 103991.Jun 26 2017, 10:36 AM

Update test comments.

ributzka accepted this revision.Jun 26 2017, 10:55 AM

Never mind. LGTM

This revision is now accepted and ready to land.Jun 26 2017, 10:55 AM
aoli added a comment.Jun 26 2017, 11:00 AM

@ributzka it seems that it is guaranteed that the indices into struct type must be constants. It is not only being used by AddressingModeMatcher. It is also being used by lib/IR/Instructions.cpp:getIndexedTypeInternal. We don't want to break this guarantee so that we want to fix the constant hoisting.

aoli added a comment.Jun 26 2017, 11:01 AM

Thank you for reviewing :)

aoli closed this revision.Jun 29 2017, 10:03 AM

The new code here seems to overlap with llvm::canReplaceOperandWithVariable. Can we unify them?

The new code here seems to overlap with llvm::canReplaceOperandWithVariable. Can we unify them?

Unifying with canReplaceOperandWithVariable can make the code simpler. However, we'd also end up iterating the GEP once for each operand. I couldn't find any limit on the number of indices in a GEP, but would a quadratic iteration of the indices be reasonable?

However, we'd also end up iterating the GEP once for each operand.

Oh, didn't think of that.

I couldn't find any limit on the number of indices in a GEP

No, there isn't a limit (although we probably have other algorithms that would explode with deeply nested types).

If we need to, we could special-case GEPs, and use canReplaceOperandWithVariable for other instructions.

aoli added a comment.Jun 29 2017, 4:01 PM

@efriedma thank you for pointing out!

I just did some tests and I found there still some potential bugs in constant hoisting.

For insertvalue

define void @test1(%T %P) {                                                     
  %A = insertvalue %T %P, i32 256, 256                                          
  %B = insertvalue %T %P, i32 256, 256                                          
  %C = insertvalue %T %P, i32 256, 256                                          
  ret void                                                                      
}

will be optimized to

define void @test1(%T %P) {
  %const = bitcast i32 256 to i32
  %A = insertvalue %T %P, i32 %const, 256
  %B = insertvalue %T %P, i32 %const, 256
  %C = insertvalue %T %P, i32 %const, 256
  ret void
}

which is wrong (? I'm not very sure here but based on the comments in llvm::canReplaceOperandWithVariable: )

It may good for us to use llvm::canReplaceOperandWithVariable: to maintain the constancy.

aoli added a comment.Jun 29 2017, 4:16 PM

And for quadratic iteration overhead. This function is being used in GVNSink.cpp and SimplifyCFG.cpp and there isn't any optimization for iterating the GEP. So it may okay for us also to do that?

For the quadratic overhead, maybe it's just not worth worrying about; GEPs usually only have a few operands.

For your insertvalue example, I don't see any problem with that transform; the important part is that we can't transform the indexes (see http://llvm.org/docs/LangRef.html#insertvalue-instruction)

aoli added a comment.Jun 29 2017, 5:07 PM

For your insertvalue example, I don't see any problem with that transform; the important part is that we can't transform the indexes (see http://llvm.org/docs/LangRef.html#insertvalue-instruction)

It may be a bug in canReplaceOperandWithVariable:

case Instruction::ExtractValue:
case Instruction::InsertValue:
  // All operands apart from the first are constant.
  return OpIdx == 0;

Only first operand is allowed to be set to a non-constant value.

Only first operand is allowed to be set to a non-constant value.

Ah...

It's supposed to check for the first two operands for insertvalue.

aoli added a comment.Jun 29 2017, 5:40 PM

Ah...

It's supposed to check for the first two operands for insertvalue.

Thank you for clarifying. I just want to make sure those two logic are identical.

I'll bring a new patch to fix this and unify the logic.