This is an archive of the discontinued LLVM Phabricator instance.

[StackColoring] Update AliasAnalysis information in stack coloring pass
ClosedPublic

Authored by inouehrs on Jul 26 2017, 11:00 AM.

Details

Summary

Stack coloring pass need to maintain TBAA metadata when merging stack slots of different types.
Actually, there is a FIXME comment in StackColoring.cpp

// FIXME: In order to enable the use of TBAA when using AA in CodeGen,
// we'll also need to update the TBAA nodes in MMOs with values
// derived from the merged allocas.

But, TBAA has been already enabled in CodeGen without fixing this pass.
The incorrect TBAA metadata results in recent failures in bootstrap test on ppc64le (PR33928) by allowing unsafe instruction scheduling.
Although we observed the problem on ppc64le, this is a platform neutral issue.

This patch makes the stack coloring pass maintains TBAA metadata (somewhat conservatively) when merging multiple stack slots.

This patch fixes PR33928.

Diff Detail

Event Timeline

inouehrs created this revision.Jul 26 2017, 11:00 AM
grandinj added inline comments.
include/llvm/CodeGen/MachineFunction.h
665

AliasAnalisys -> AliasAnalysis

jtony added inline comments.Jul 26 2017, 1:31 PM
lib/CodeGen/MachineFunction.cpp
338

If we add a temp variable for the first parameter and assign a different value to it according to the guard if(MMO->getValue()), won't the code be simpler? I am talking something like this:

const PseudoSourceValue *Value = MMO->getValue() ?  MMO->getValue() : MMO->getPseudoValue();

return new (Allocator)
             MachineMemOperand(MachinePointerInfo(Value, MMO->getOffset()),
                               MMO->getFlags(), MMO->getSize(),
                               MMO->getBaseAlignment(), AAInfo, 
                               MMO->getRanges(), MMO->getSyncScopeID(),
                               MMO->getOrdering(), MMO->getFailureOrdering());
}
lib/CodeGen/StackColoring.cpp
874

Can we get rid of the static key word for these two functions and and put their declaration into a header and just keep one copy of the source code?

echristo edited edge metadata.

Tagging in Matthias here.

inouehrs updated this revision to Diff 108420.Jul 26 2017, 11:37 PM
  • avoid eliminating non-TBAA alias analysis information
  • minor touchups
inouehrs marked 3 inline comments as done.Jul 26 2017, 11:42 PM
inouehrs added inline comments.
include/llvm/CodeGen/MachineFunction.h
665

Fixed. Thanks!

lib/CodeGen/MachineFunction.cpp
338

I hope this looks better than the old code.
Since getValue() and getPseudoValue() return different types, I think this is easier to understand.

lib/CodeGen/StackColoring.cpp
874

Done.

sanjoy added a subscriber: sanjoy.Jul 27 2017, 12:37 AM
MatzeB accepted this revision.Jul 27 2017, 4:40 PM

I don't know much about our alias analysis infrastructure.

That said the description and changes seem reasonable. Please double check your getUnderlyingObject refactoring before submitting.

include/llvm/CodeGen/MachineFunction.h
664

Don't repeat the method name in the doxygen comment (old code does it, new code shouldn't).

include/llvm/CodeGen/ScheduleDAGInstrs.h
86 ↗(On Diff #108420)

Explain more what the function does and less what it should be used for.

Also this isn't scheduler related, so at least move it to MachineMemoryOperand or better to ValueTracking.h (which already has a few variations of it, maybe you can even use one of those instead of roling another one).

lib/CodeGen/StackColoring.cpp
40

Instead of documenting why you need to import a scheduling header here, just put the function into an apropriate header (as above) :)

1084

Is MergedAllocas changing here? Looks like you can move the check further up outside this loop.

This revision is now accepted and ready to land.Jul 27 2017, 4:40 PM

We need to be very careful to document the contracts here and explain what's going on. The implementation of getUnderlyingObjects in ScheduleDAGInstrs.cpp calls its helper function getUnderlyingObjectFromInt which contains this comment:

// If we find an add of a constant, a multiplied value, or a phi, it's
// likely that the other operand will lead us to the base
// object. We don't have to worry about the case where the
// object address is somehow being computed by the multiply,
// because our callers only care when the result is an
// identifiable object.

and this is indeed true. The only existing caller, getUnderlyingObjectsForInstr, does this:

} else if (const Value *V = MMO->getValue()) {
  SmallVector<Value *, 4> Objs;
  getUnderlyingObjects(V, Objs, DL);

  for (Value *V : Objs) {
    if (!isIdentifiedObject(V))
      return false;

    Objects.push_back(UnderlyingObjectsVector::value_type(V, true));
  }

and this is important because, if GetUnderlyingObjects hits its depth cutoff, it can return arbitrary instructions in the use/def chain of the pointer.

If we're going to make this function a utility that can be used elsewhere, we should make this safer. I'd advocate for moving the isIdentifiedObject check into the implementation of getUnderlyingObjects before:

Objects.push_back(const_cast<Value *>(V));

such that if the check fails we clear the Objects array and return. That should make the interface safe. We should document this part of the functions behavior and remove the corresponding check in getUnderlyingObjectsForInstr.

lib/CodeGen/ScheduleDAGInstrs.cpp
154 ↗(On Diff #108420)

Please rename this function if you make it non-static. The function we have right now in ValueTracking is called GetUnderlyingObjects, but if we were to rename it follow our coding conventions we'd have a conflict with the name of function function. How about getUnderlyingObjectsForCodeGen?

lib/CodeGen/StackColoring.cpp
976

I'd remove this FIXME. It is not clear to me that there is a well-defined way to do this in general. A single alloca could be accessed at different times by accesses with incompatible TBAA metadata so long as some access compatible with both, or data dependence, keeps the correct ordering. As a result, there's not necessarily a single thing to merge the metadata with. I suppose merging everything (derived from one) with everything (derived from the other) might work, but in any event, it seems non-trivial. I'm happy to have someone revisit this if they find this needs to be more precise.

1064

This is not specific to TBAA. You should replace TBAA with AA metadata in all of the comments.

1073

I don't understand this name. How about MayHaveConflictingAAMD?

1093

This situation is not specific to TBAA. If affects all of the AA metadata. You'll need to unset it all.

qcolombet added a subscriber: qcolombet.

+Hal

I think Hal would like to double check that.

Haha, never mind me, Hal already replied. (Sloppy tab!)

inouehrs updated this revision to Diff 108791.Jul 29 2017, 8:55 AM
inouehrs marked 3 inline comments as done.
inouehrs retitled this revision from [WIP] Update TBAA information in stack coloring pass to [StackColoring] Update TBAA information in stack coloring pass.
  • move getUnderlyingObjects from ScheduleDAGInstrs.cpp to ValueTracking.cpp and also renamed to getUnderlyingObjectsForCodeGen.
  • check the validity of Values returned from getUnderlyingObjectsForCodeGen.
  • remove information on all types of AA as well as information on TBAA.
inouehrs marked 7 inline comments as done.Jul 29 2017, 9:04 AM
inouehrs added inline comments.
include/llvm/CodeGen/MachineFunction.h
664

Fixed.

lib/CodeGen/ScheduleDAGInstrs.cpp
154 ↗(On Diff #108420)

I renamed it getUnderlyingObjectsForCodeGen and moved into ValueTracking.cpp.

lib/CodeGen/StackColoring.cpp
40

Moved to ValueTracking.h.

976

I agree. I removed this FIXME.

1064

Done.

1073

Fixed.

1084

We need to check each Value V (and hence AI) with MergedAllocas. So I do this check in the loop.

1093

Done.

inouehrs updated this revision to Diff 108793.Jul 29 2017, 9:34 AM
inouehrs marked 7 inline comments as done.
  • minor fix
inouehrs updated this revision to Diff 108802.Jul 29 2017, 1:07 PM
inouehrs retitled this revision from [StackColoring] Update TBAA information in stack coloring pass to [StackColoring] Update AliasAnalysis information in stack coloring pass.

Move check with isIdentifiedObject into getUnderlyingObjectsForCodeGen

@hfinkel I am going to commit this soon to fix the buildbot failures. Please let me know if you have further comments. Thanks!

MatzeB added inline comments.Aug 1 2017, 11:32 AM
lib/CodeGen/StackColoring.cpp
1094–1095
  • Does AAMDNodes() mean it can alias with anything? In that case you could simply use I.dropMemRefs() as we make the same assumption for an instruction without any memory operands.
  • Can't you simplify to MemOps[MemOpIdx++] to *MMO = ... and avoid the extra counter?
MatzeB added inline comments.Aug 1 2017, 11:36 AM
lib/CodeGen/StackColoring.cpp
1094–1095

Ignore my last point about the MemOps. I missed that fact that you are duplicating the information and not just replacing the existing operands (may help understand if you renamed the variable to NewMemOps).

inouehrs updated this revision to Diff 109284.Aug 2 2017, 12:34 AM

updated based on post-commit comments

inouehrs marked 2 inline comments as done.Aug 2 2017, 12:42 AM
inouehrs added inline comments.
lib/Analysis/ValueTracking.cpp
3332 ↗(On Diff #109284)

Comments from Hal

I don't think this check does that you want because, if V is a inttoptr,
this will always be false (i.e. the check for inttoptr will be dead).

To preserve functionality, I believe you need the check here instead.

Yes, exactly. I moved the check with isIdentifiedObject() after check of IntToPtr.

lib/CodeGen/StackColoring.cpp
1094–1095
  • AAMDNodes() means no AA information and so optimizers think this instruction can alias with anything. I replace only AAInfo and other information in MMO (e.g. pointer, size etc) are still needed. So I eliminate only AAInfo.
  • I renamed MemOps to NewMemOps for readability. Thank you for the suggestion.
MatzeB added a comment.Aug 2 2017, 8:40 AM

Thanks, LGTM