llvm dev - Nov 2011 - [LLVMdev] alias analysis in ScheduleDagInstr class

Hi Sergei, thanks for considering my question. We if-convert some code, such
that the basic block looks as follows after if-conversion:

ld char from A into R1
p1 = R1>255? (generate the predicate)
p1 |  R1 =  255 (conditional execution)
st char R1 to A
ld char from A+1 into R2
p2 = R2>255? (generate the predicate)
p2 |  R2 =  255 (conditional execution)
store char R2 to A+1

The problem is that the compiler does not seem to know that the second ld can be
scheduled before the first st.
 
On 14 Nov 2011, at 16:50, Sergei Larin wrote:
> I am working on something very(very) similar, what is the exact nature of
> your question?
> 
> Sergei Larin
> 
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.
> 
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu] On
> Behalf Of Bjorn De Sutter
> Sent: Friday, November 11, 2011 7:59 AM
> To: llvmdev at cs.uiuc.edu
> Subject: [LLVMdev] alias analysis in ScheduleDagInstr class
> 
> In ScheduleDagInstr.cpp, a todo is mentioned to make this pass use real
> alias analysis information. Is anybody working on this already?
> 
> I am working on a VLIW-like backend and have If-conversion working rather
> well, but the problem is that independent loads and stores in the
> if-converted blocks are not scheduled well at all. 
> 
> Thanks,
> 
> prof. Bjorn De Sutter
> Computer Systems Lab
> Ghent University
> 
> 
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

We observed exact same problem, and I did put in place a mechanism to
recognize and break such false dependencies right before pre-RA scheduler
(in DAG->DAG lowering), but the immediate observed effect for our back end
was performance reduction, since none of the current schedulers were capable
of dealing with newly presented parallelism in BB (resulted in high reg
pressure and "unintelligent" code sequences). That in turn prompted a
revision of the scheduling mechanism, which I am still working on. 

If I am to submit the AA patch by itself right now, I am afraid it would
cause negative reaction from reviewers (due to the above described issue),
so I cherish a hope to have both patches (to use AA and newer/updated
scheduler) presented at the same time. 

  What is your timeline? How much time you can afford until you must have
this? 

Also, are you attending the LLVM meeting in San Jose this week?

Sergei Larin

--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.


-----Original Message-----
From: Bjorn De Sutter [mailto:bjorn.desutter at elis.ugent.be] 
Sent: Monday, November 14, 2011 10:18 AM
To: Sergei Larin
Cc: llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] alias analysis in ScheduleDagInstr class

Hi Sergei, thanks for considering my question. We if-convert some code, such
that the basic block looks as follows after if-conversion:

ld char from A into R1
p1 = R1>255? (generate the predicate)
p1 |  R1 =  255 (conditional execution)
st char R1 to A
ld char from A+1 into R2
p2 = R2>255? (generate the predicate)
p2 |  R2 =  255 (conditional execution)
store char R2 to A+1

The problem is that the compiler does not seem to know that the second ld
can be scheduled before the first st.
 
On 14 Nov 2011, at 16:50, Sergei Larin wrote:
> I am working on something very(very) similar, what is the exact nature of
> your question?
> 
> Sergei Larin
> 
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.
> 
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu] On
> Behalf Of Bjorn De Sutter
> Sent: Friday, November 11, 2011 7:59 AM
> To: llvmdev at cs.uiuc.edu
> Subject: [LLVMdev] alias analysis in ScheduleDagInstr class
> 
> In ScheduleDagInstr.cpp, a todo is mentioned to make this pass use real
> alias analysis information. Is anybody working on this already?
> 
> I am working on a VLIW-like backend and have If-conversion working rather
> well, but the problem is that independent loads and stores in the
> if-converted blocks are not scheduled well at all. 
> 
> Thanks,
> 
> prof. Bjorn De Sutter
> Computer Systems Lab
> Ghent University
> 
> 
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

We don't need this urgently. I mainly wanted to avoid double work.  We use
LLVM as a front-end to a research CGRA compiler.

I will not make it to the LLVM meeting.

Best,

Bjorn

On 14 Nov 2011, at 17:38, Sergei Larin wrote:
> We observed exact same problem, and I did put in place a mechanism to
> recognize and break such false dependencies right before pre-RA scheduler
> (in DAG->DAG lowering), but the immediate observed effect for our back
end
> was performance reduction, since none of the current schedulers were
capable
> of dealing with newly presented parallelism in BB (resulted in high reg
> pressure and "unintelligent" code sequences). That in turn
prompted a
> revision of the scheduling mechanism, which I am still working on. 
> 
> If I am to submit the AA patch by itself right now, I am afraid it would
> cause negative reaction from reviewers (due to the above described issue),
> so I cherish a hope to have both patches (to use AA and newer/updated
> scheduler) presented at the same time. 
> 
> What is your timeline? How much time you can afford until you must have
> this? 
> 
> Also, are you attending the LLVM meeting in San Jose this week?
> 
> Sergei Larin
> 
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.
> 
> 
> -----Original Message-----
> From: Bjorn De Sutter [mailto:bjorn.desutter at elis.ugent.be] 
> Sent: Monday, November 14, 2011 10:18 AM
> To: Sergei Larin
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: [LLVMdev] alias analysis in ScheduleDagInstr class
> 
> Hi Sergei, thanks for considering my question. We if-convert some code,
such
> that the basic block looks as follows after if-conversion:
> 
> ld char from A into R1
> p1 = R1>255? (generate the predicate)
> p1 |  R1 =  255 (conditional execution)
> st char R1 to A
> ld char from A+1 into R2
> p2 = R2>255? (generate the predicate)
> p2 |  R2 =  255 (conditional execution)
> store char R2 to A+1
> 
> The problem is that the compiler does not seem to know that the second ld
> can be scheduled before the first st.
> 
> On 14 Nov 2011, at 16:50, Sergei Larin wrote:
> 
>> I am working on something very(very) similar, what is the exact nature
of
>> your question?
>> 
>> Sergei Larin
>> 
>> --
>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.
>> 
>> -----Original Message-----
>> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu] On
>> Behalf Of Bjorn De Sutter
>> Sent: Friday, November 11, 2011 7:59 AM
>> To: llvmdev at cs.uiuc.edu
>> Subject: [LLVMdev] alias analysis in ScheduleDagInstr class
>> 
>> In ScheduleDagInstr.cpp, a todo is mentioned to make this pass use real
>> alias analysis information. Is anybody working on this already?
>> 
>> I am working on a VLIW-like backend and have If-conversion working
rather
>> well, but the problem is that independent loads and stores in the
>> if-converted blocks are not scheduled well at all. 
>> 
>> Thanks,
>> 
>> prof. Bjorn De Sutter
>> Computer Systems Lab
>> Ghent University
>> 
>> 
>> 
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>> 
> 
>