ValueTracking's GetUnderlyingObject vs. ScheduleDAGInstrs' getUnderlyingObject

Hello all.

I'm investigating a problem with "Machine Instruction Scheduling" that is rooted in incorrect alias information.

Things go wrong in the "Merge disjoint stack slots"[1] pass when a store instruction fails to get updated after its stack slot is merged. As a result, when "Machine Instruction Scheduling" runs, it incorrectly re-orders the store and a subsequent load, thinking that they do not refer to the same underlying object when they actually do.

The logic in "Merge disjoint stack slots" seems ok, except that it relies on llvm::GetUnderlyingObject[2] to determine if an instruction needs to be updated. Unfortunately, unlike ScheduleDAGInstrs' getUnderlyingObject[3], llvm::GetUnderlyingObject doesn't handle ptrtoint instructions, and in this case, fails to see that the problematic store refers to the merged stack slot.

It seems to me that the logic in ScheduleDAGInstrs's getUnderlyingObject should be pushed into llvm::GetUnderlyingObject. And indeed, when I do this, "Merge disjoint stack slots" correctly updates all of the instructions and "Machine Instruction Scheduling" behaves correctly.

Is this the right thing to do? Would other callers to llvm::GetUnderlyingObject not want the additional behavior?

Thanks,
Matthew Curtis.

[1] http://llvm.org/docs/doxygen/html/StackColoring_8cpp_source.html
[2] http://llvm.org/docs/doxygen/html/ValueTracking_8cpp_source.html#l01780
[3] http://llvm.org/docs/doxygen/html/ScheduleDAGInstrs_8cpp_source.html#l00087

Hi Matthew,

I'm investigating a problem with "Machine Instruction Scheduling" that is rooted
in incorrect alias information.

Things go wrong in the "Merge disjoint stack slots"[1] pass when a store
instruction fails to get updated after its stack slot is merged. As a result,
when "Machine Instruction Scheduling" runs, it incorrectly re-orders the store
and a subsequent load, thinking that they do not refer to the same underlying
object when they actually do.

The logic in "Merge disjoint stack slots" seems ok, except that it relies on
llvm::GetUnderlyingObject[2] to determine if an instruction needs to be updated.

it sounds to me like this logic is broken. For example, GetUnderlyingObject
has a recursion limit that will bail out if it has to look through too many
instructions to find the underlying object. Thus you can't ever rely on
GetUnderlyingObject actually finding the real underlying object. But it
sounds like "Merge disjoint stack slots" *is* relying on this (I don't know the
code, it's just the impression I get from your description).

Ciao, Duncan.

It seems to me that this is a bug in StackColoring. It should not
assume that GetUnderlyingObject always returns the underlying alloca
(it might fail for several reason - e.g. the default max lookup depth
is 6).

// Climb up and find the original alloca.
00514 V = GetUnderlyingObject(V);
00515 // If we did not find one, or if the one that we found
is not in our
00516 // map, then move on.
00517 if (!V || !Allocas.count(V))
00518 continue;
00519
00520 MMO->setValue(Allocas[V]);
00521 FixedMemOp++;

Instead of continuing, it should probably clean the Memory Operand so
that future alias queries will return a conservative result.

Yes, After speaking with Arnold offline as well, I have come to realize that "Merge disjoint stack slots" is not correctly using GetUnderlyingObject. While we could still improve GetUnderlyingObject so that the pass works correctly in more cases, it still needs to conservatively handle the possibility that GetUnderlyingObject may not return the real underlying object.

I will be filing a bug shortly.

Thanks,
Matthew Curtis.