llvm dev - Oct 2012 - [LLVMdev] 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

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

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.
> 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
>

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.


On Mon, Oct 15, 2012 at 11:00 AM, Matthew Curtis <mcurtis at
codeaurora.org> wrote:
> 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
>
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
by
> The Linux Foundation
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On 10/15/2012 11:23 AM, Duncan Sands wrote:
> 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.
>
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.


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The
Linux Foundation