Re: Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

任坤
Hi:
   I want to do some optimization on MachineLoop.
So I want to get MachineLoopInfo from MachineFunction.

I reference MachineLICM.cpp.
So I try to write a pass in Target/mytarget directory.
I find there is Error.
llvm/include/llvm/PassAnalysisSupport.h:198: AnalysisType& llvm::Pass::getAnalysisID(const llvm::PassInfo*) const [with AnalysisType = llvm::MachineLoopInfo]: Assertion `ResultPass && "getAnalysis*() called on an analysis that was not 'required' by pass!"' failed.

****************************
runOnMachineFunction(MachineFunction &MF) {
   LI = &getAnalysis<MachineLoopInfo>();
   DT = &getAnalysis<MachineDominatorTree>();

   for (MachineLoopInfo::iterator
          I = LI->begin(), E = LI->end(); I != E; ++I) {
    CurLoop = *I;
  }
}
******************************
I copy find from MachineLICM.cpp, and change class name.
What is different ??

Thanks.

Ren Kun




--- 10年1月26日,周二, Benoit Boissinot <[hidden email]> 写道:

> 发件人: Benoit Boissinot <[hidden email]>
> 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree.  please look at my jpg.
> 收件人: "任坤" <[hidden email]>
> 抄送: "llvm" <[hidden email]>
> 日期: 2010年1月26日,周二,下午10:13
> On Tue, Jan 26, 2010 at 10:04:16PM
> +0800, 浠诲潳   wrote:
> > Hi, Dear Boissinot:
> >
> > 1. When I have irreducible CFG, I travel its nodes by
> DFS.
> >    search backedge for every node. After I
> finish one node,
> >    push it into a stack.
> >    [0, 1, 2, M]     
> <---push.
> >    [0, 1, 2, M,...N] <---push.
> >     
> >    When resolving node M, find a edge from
> node N to node M,
> >    N is not in stack(M < N), It is a
> backedge.
> >    N is in stack(M > N), It is NOT a
> backedge.
> >
> >    I treat these backedges as loop-edges. M
> is Loop header node.
> >    If I cut these edges from CFG, CFG can be
> topological sort.
> > 
> >    Am I right???
>
> yes, exactly.
>
> regards,
>
> Benoit
>
> --
> :wq
>



     


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

Nick Lewycky
任坤   wrote:
> Hi:
>     I want to do some optimization on MachineLoop.
> So I want to get MachineLoopInfo from MachineFunction.
>
> I reference MachineLICM.cpp.
> So I try to write a pass in Target/mytarget directory.
> I find there is Error.
> llvm/include/llvm/PassAnalysisSupport.h:198: AnalysisType&  llvm::Pass::getAnalysisID(const llvm::PassInfo*) const [with AnalysisType = llvm::MachineLoopInfo]: Assertion `ResultPass&&  "getAnalysis*() called on an analysis that was not 'required' by pass!"' failed.

Did you copy getAnalysisUsage too? The way it works is that you need
getAnalysisUsage to declare all the passes you need to exist before your
pass starts, then getAnalysis<>() inside your runOnMachineFunction can
use them. If you call getAnalysis on a Pass that you didn't request,
you'll hit this assertion.

Nick

> ****************************
> runOnMachineFunction(MachineFunction&MF) {
>     LI =&getAnalysis<MachineLoopInfo>();
>     DT =&getAnalysis<MachineDominatorTree>();
>
>     for (MachineLoopInfo::iterator
>            I = LI->begin(), E = LI->end(); I != E; ++I) {
>      CurLoop = *I;
>    }
> }
> ******************************
> I copy find from MachineLICM.cpp, and change class name.
> What is different ??
>
> Thanks.
>
> Ren Kun
>
>
>
>
> --- 10年1月26日,周二, Benoit Boissinot<[hidden email]>  写道:
>
>> 发件人: Benoit Boissinot<[hidden email]>
>> 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree.  please look at my jpg.
>> 收件人: "任坤"<[hidden email]>
>> 抄送: "llvm"<[hidden email]>
>> 日期: 2010年1月26日,周二,下午10:13
>> On Tue, Jan 26, 2010 at 10:04:16PM
>> +0800, 浠诲潳   wrote:
>>> Hi, Dear Boissinot:
>>>
>>> 1. When I have irreducible CFG, I travel its nodes by
>> DFS.
>>>      search backedge for every node. After I
>> finish one node,
>>>      push it into a stack.
>>>      [0, 1, 2, M]
>> <---push.
>>>      [0, 1, 2, M,...N]<---push.
>>>
>>>      When resolving node M, find a edge from
>> node N to node M,
>>>      N is not in stack(M<  N), It is a
>> backedge.
>>>      N is in stack(M>  N), It is NOT a
>> backedge.
>>>
>>>      I treat these backedges as loop-edges. M
>> is Loop header node.
>>>      If I cut these edges from CFG, CFG can be
>> topological sort.
>>>
>>>      Am I right???
>>
>> yes, exactly.
>>
>> regards,
>>
>> Benoit
>>
>> --
>> :wq
>>
>
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

任坤
In reply to this post by 任坤
Thank you, Nick.
Yes, I have add getAnalysisUsage.
As I know, some CFG is irreducible.
At this time, Dominator Tree can not find
some backedge. Is it means some MachineLoop is
not be found?
dominatorTree.jpg is a previous exmaple.

best regards!
renkun


--- 10年3月9日,周二, Nick Lewycky <[hidden email]> 写道:

> 发件人: Nick Lewycky <[hidden email]>
> 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please look at my jpg.
> 收件人: "任坤" <[hidden email]>
> 抄送: "Benoit Boissinot" <[hidden email]>, "llvm" <[hidden email]>
> 日期: 2010年3月9日,周二,下午2:02
> 任坤   wrote:
> > Hi:
> >     I want to do some optimization
> on MachineLoop.
> > So I want to get MachineLoopInfo from
> MachineFunction.
> >
> > I reference MachineLICM.cpp.
> > So I try to write a pass in Target/mytarget
> directory.
> > I find there is Error.
> > llvm/include/llvm/PassAnalysisSupport.h:198:
> AnalysisType&  llvm::Pass::getAnalysisID(const
> llvm::PassInfo*) const [with AnalysisType =
> llvm::MachineLoopInfo]: Assertion
> `ResultPass&&  "getAnalysis*() called on an
> analysis that was not 'required' by pass!"' failed.
>
> Did you copy getAnalysisUsage too? The way it works is that
> you need
> getAnalysisUsage to declare all the passes you need to
> exist before your
> pass starts, then getAnalysis<>() inside your
> runOnMachineFunction can
> use them. If you call getAnalysis on a Pass that you didn't
> request,
> you'll hit this assertion.
>
> Nick
>
> > ****************************
> > runOnMachineFunction(MachineFunction&MF) {
> >     LI
> =&getAnalysis<MachineLoopInfo>();
> >     DT
> =&getAnalysis<MachineDominatorTree>();
> >
> >     for
> (MachineLoopInfo::iterator
> >            I =
> LI->begin(), E = LI->end(); I != E; ++I) {
> >      CurLoop = *I;
> >    }
> > }
> > ******************************
> > I copy find from MachineLICM.cpp, and change class
> name.
> > What is different ??
> >
> > Thanks.
> >
> > Ren Kun
> >
> >
> >
> >
> > --- 10年1月26日,周二, Benoit
> Boissinot<[hidden email]
> 写道:
> >
> >> 发件人: Benoit Boissinot<[hidden email]>
> >> 主题: Re: [LLVMdev] Find all backedges of CFG by
> MachineDominatorTree.  please look at my jpg.
> >> 收件人: "任坤"<[hidden email]>
> >> 抄送: "llvm"<[hidden email]>
> >> 日期: 2010年1月26日,周二,下午10:13
> >> On Tue, Jan 26, 2010 at 10:04:16PM
> >> +0800, 浠诲潳   wrote:
> >>> Hi, Dear Boissinot:
> >>>
> >>> 1. When I have irreducible CFG, I travel its
> nodes by
> >> DFS.
> >>>      search backedge for every
> node. After I
> >> finish one node,
> >>>      push it into a stack.
> >>>      [0, 1, 2, M]
> >> <---push.
> >>>      [0, 1, 2,
> M,...N]<---push.
> >>>
> >>>      When resolving node M,
> find a edge from
> >> node N to node M,
> >>>      N is not in
> stack(M<  N), It is a
> >> backedge.
> >>>      N is in stack(M> 
> N), It is NOT a
> >> backedge.
> >>>
> >>>      I treat these backedges as
> loop-edges. M
> >> is Loop header node.
> >>>      If I cut these edges from
> CFG, CFG can be
> >> topological sort.
> >>>
> >>>      Am I right???
> >>
> >> yes, exactly.
> >>
> >> regards,
> >>
> >> Benoit
> >>
> >> --
> >> :wq
> >>
> >
> >
> >
> >
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > [hidden email] 
>        http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

dominatorTree.jpg (95K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

Benoit Boissinot-4
On Tue, Mar 9, 2010 at 9:14 AM, renkun <[hidden email]> wrote:
> Thank you, Nick.
> Yes, I have add getAnalysisUsage.
> As I know, some CFG is irreducible.
> At this time, Dominator Tree can not find
> some backedge. Is it means some MachineLoop is
> not be found?
> dominatorTree.jpg is a previous exmaple.

Just remember that for irreducible graphs, there are several
definitions of loops (and thus several definitions of loopedges).
Back-edge (edge pointer to an ancestor during a DFS walk) are
loop-edge, but the converse isn't necessarily true.

And, depending on the DFS, MBB173->MBB172 is not necessarely a
backedge (visiting MBB167 before MBB173 will indeed mark
MBB173->MBB172 as a tree-edge, not as a back-edge).
For loop-edge, you might instead find MBB170->MBB172, or
MBB180->MBB170 plus MBB174->MBB170, or some combinations of those
(MBB170, MBB172, MBB173 are all undominated, any subset from these
three nodes can be choosen as headers).

Cheers,

Benoit
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev