llvm dev - Mar 2010 - [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please look at my jpg.

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 <nicholas at mxc.ca> 写道：
> 发件人: Nick Lewycky <nicholas at mxc.ca>
> 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please
look at my jpg.
> 收件人: "任坤" <hbrenkun at yahoo.cn>
> 抄送: "Benoit Boissinot" <bboissin+llvm at gmail.com>,
"llvm" <llvmdev at cs.uiuc.edu>
> 日期: 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<bboissin+llvm at gmail.com> 
> 写道：
> >
> >> 发件人: Benoit Boissinot<bboissin+llvm at gmail.com>
> >> 主题: Re: [LLVMdev] Find all backedges of CFG by
> MachineDominatorTree.  please look at my jpg.
> >> 收件人: "任坤"<hbrenkun at yahoo.cn>
> >> 抄送: "llvm"<llvmdev at cs.uiuc.edu>
> >> 日期: 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
> > LLVMdev at cs.uiuc.edu 
>        http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
>

      
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dominatorTree.jpg
Type: image/jpeg
Size: 71233 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100309/f9f17ce2/attachment.jpg>

On Tue, Mar 9, 2010 at 9:14 AM, renkun <hbrenkun at yahoo.cn>
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