Re: [LLVMdev] 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 <bboiss...@gmail.com> 写道：

> 发件人: Benoit Boissinot <bboiss...@gmail.com>
> 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree.  please look at my jpg.
> 收件人: "任坤" <hbre...@yahoo.cn>
> 抄送: "llvm" <llv...@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
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[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>();

[renkun]

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 <nich...@mxc.ca> 写道：

> 发件人: Nick Lewycky <nich...@mxc.ca>

> 主题: Re: [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please look at my jpg.
> 收件人: "任坤" <hbre...@yahoo.cn>

> 抄送: "Benoit Boissinot" <bboiss...@gmail.com>, "llvm" <llv...@cs.uiuc.edu>
> 日期: 2010年3月9日,周二,下午2:02

[Benoit Boissinot]

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