On 6/20/16 3:46 PM, Yuxi Chen wrote:> Hi, > > Thanks for your reply. > But I still don't know how a transform pass updates a new analysis > pass after it modifies the IR. Can you explain it clearly? I am not > familiar with pass management and invocation.Passes can have methods that allow their internal state to be updated by other passes (the same way that their state can be queried by other passes). For example, the alias analysis passes have methods for querying alias information as well as methods that allow other passes to update the aliasing information when they make changes to the IR (so that friendly optimization passes don't invalidate alias analysis information when they make simple changes). Right now, your transform pass has a method which your other passes are using to query information (I am guessing that your transform pass is recording information on what it has done). I am suggesting that you create a new pass (call it "RK" for "Record Keeper") that implements this method (call it getInfo()). Additionally, the RK pass also implements a method called setInfo() which the transform pass uses to record any information that later passes will need. In their getAnalysisUsage<>() method, your passes preserve the results of the RK pass. In this way, your transform pass modifies the IR and dumps any information needed by your analysis passes into the RK pass. The RK pass does not modify the IR, so it doesn't create an impossible-to-schedule pass pipeline like your transform pass does. If this isn't clear, please let me know. I see that you're from UChicago, so I'm guessing that you need this for a research project. Regards, John Criswell> > Best, > Yuxi > ------------------------------------------------------------------------ > *From:* John Criswell [jtcriswel at gmail.com] > *Sent:* Sunday, June 19, 2016 10:05 AM > *To:* Mehdi Amini; Yuxi Chen > *Cc:* llvm-dev at lists.llvm.org; llvmdev-bounces at cs.uiuc.edu; > llvmdev at cs.uiuc.edu > *Subject:* Re: [llvm-dev] pass invalidation > > On 6/19/16 4:28 AM, Mehdi Amini via llvm-dev wrote: >> >>> On Jun 18, 2016, at 10:44 PM, Yuxi Chen via llvm-dev >>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: >>> >>> Hi All, >>> >>> When I use llvm, I encounter a problem like "unable to schedule pass >>> A required by C" >>> I investigated deeper. It's like: >>> I have three passes, say A, B, C(all are on function level) >>> A would modify IR code. (change instruction order) >>> >>> For pass B, >>> I would use the result of pass A, I use addRequired<B>(), and >>> &getAnalysis<B>(), it works. >>> >>> void getAnalysisUsage(AU){ >>> AU.addRequired<A>(); >>> } >>> >>> >>> For pass C, it will use the results of pass A and B. >>> I use the way as used for pass B, but it failed, even for LoopInfo >>> analysis pass(which is the built-in analysis pass). >>> void getAnalysisUsage(AU){ >>> AU.addRequired<A>(); >>> AU.addRequired<B>(); >>> } >>> >>> >>> It seems because A would modify IR code, so for pass C, I need first >>> load pass A then pass B, otherwise it will be invalidated. >>> However, when I change the using order, I still got error "unable to >>> schedule pass A required by C". >>> >>> Does anyone encounter the same problem before and have a solution? >>> Any help is appreciated. >> >> Depending on other transformations isn’t recommended, and isn’t >> supported by the soon-new-passmanager I believe. >> The expectation is that the passes are added in order to the pass >> manager by the client. > > Depending on transformation passes isn't supported by the legacy > PassManager, either. Occasionally some passes can get away with it, > but it often results in unschedule-able pass pipelines as above. > > If your transform pass does something to the code, other passes should > either infer what it did by examining the IR. the IR contains the > definitive information about the program (because it is the program). > > Alternatively, you could create an analysis pass upon which both your > transform and analysis passes depend. The transform pass would update > this new analysis pass with information on what it transformed; your > later analysis passes could then query this information. This > approach is fragile, but it could work. > > Regards, > > John Criswell > >> >> In you case, I expect that it would “work” by removing the dependency >> from C to A. If C requires B and B requires A, by scheduling C you’ll >> get A, B, C in sequence. >> >> — >> Mehdi >> >> >> >>> >>> Best, >>> Yuxi >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> >> >> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > -- > John Criswell > Assistant Professor > Department of Computer Science, University of Rochester > http://www.cs.rochester.edu/u/criswell-- John Criswell Assistant Professor Department of Computer Science, University of Rochester http://www.cs.rochester.edu/u/criswell -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160621/775f211c/attachment.html>
Hi Prof. John Criswell,
Really appreciate your detailed reply.
Yes, I am using llvm to analyse C code for my research, I am quite new for llvm
and clang.
I still have several questions.
1. To my understanding, if we add pass in getAnalysisUsage method(like
LoopInfo), every time(for function pass), when we invoke runOnFunction(), llvm
would automatically load result of LoopInfo, right? But when runOnFunction is
invoked? It's in constructor?
2. right now, my passes includes several transform passes and analysis passes.
For transform passes, they also use some built-in analysis passes, like
AliasAnalysis, LoopInfo. My transform passes are to move some instructions
around based on some analysis passes. Then other analysis passes would use those
modified IR code. Your suggestion is to dump information needed by my analysis
passes into a new RK pass. I am not clear about it. Do you mean dump the
modified IR code? Then pass those modified IR into my analysis pass? If so, if
my transform pass analyses IR based on basicblock, after analysing every
basicblock, I need dump something? Seem I misunderstood.
3. Is there elegant way to handle it? I tried like A = new transformPass(), but
if I use in this way, I can't use analysis pass needed in transformPass,
because llvm doesn't invoke getAnalysisUsage(). I guess your suggestion is
the best way to do that(invocation of transform pass and analysis pass). But I
still don't know how to deal with this problem. Usually, I keep
runOnFunction to do nothing expect some initialization. A concrete example are
followed:
AnalysisA{
doAnalysis();
runOnFunction(){}
getAnalysisUsage(){
AU.addRequired(LoopInfo);
}
}
TransformB{
doCodeMove(){}
runOnFunction(){}
getAnalysisUsage(){
AU.addrequired(AnalysisA);
}
}
AnalysisC{
doAnalysis();
runOnFunction(){}
getAnalysisUsage(){
AU.addRequired(LoopInfo);
AU.addRequired(AnalysisA);
AU.addRequired(TransformB);
}
}
It helps a lot if you can give more suggestion. I am struggle with this problem
for a really long time.
Best,
Yuxi
________________________________
From: John Criswell [jtcriswel at gmail.com]
Sent: Tuesday, June 21, 2016 11:01 AM
To: Yuxi Chen
Cc: llvm-dev at lists.llvm.org; llvmdev-bounces at cs.uiuc.edu; llvmdev at
cs.uiuc.edu
Subject: Re: [llvm-dev] pass invalidation
On 6/20/16 3:46 PM, Yuxi Chen wrote:
Hi,
Thanks for your reply.
But I still don't know how a transform pass updates a new analysis pass
after it modifies the IR. Can you explain it clearly? I am not familiar with
pass management and invocation.
Passes can have methods that allow their internal state to be updated by other
passes (the same way that their state can be queried by other passes). For
example, the alias analysis passes have methods for querying alias information
as well as methods that allow other passes to update the aliasing information
when they make changes to the IR (so that friendly optimization passes don't
invalidate alias analysis information when they make simple changes).
Right now, your transform pass has a method which your other passes are using to
query information (I am guessing that your transform pass is recording
information on what it has done). I am suggesting that you create a new pass
(call it "RK" for "Record Keeper") that implements this
method (call it getInfo()). Additionally, the RK pass also implements a method
called setInfo() which the transform pass uses to record any information that
later passes will need. In their getAnalysisUsage<>() method, your passes
preserve the results of the RK pass.
In this way, your transform pass modifies the IR and dumps any information
needed by your analysis passes into the RK pass. The RK pass does not modify
the IR, so it doesn't create an impossible-to-schedule pass pipeline like
your transform pass does.
If this isn't clear, please let me know. I see that you're from
UChicago, so I'm guessing that you need this for a research project.
Regards,
John Criswell
Best,
Yuxi
________________________________
From: John Criswell [jtcriswel at gmail.com<mailto:jtcriswel at
gmail.com>]
Sent: Sunday, June 19, 2016 10:05 AM
To: Mehdi Amini; Yuxi Chen
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>;
llvmdev-bounces at cs.uiuc.edu<mailto:llvmdev-bounces at cs.uiuc.edu>;
llvmdev at cs.uiuc.edu<mailto:llvmdev at cs.uiuc.edu>
Subject: Re: [llvm-dev] pass invalidation
On 6/19/16 4:28 AM, Mehdi Amini via llvm-dev wrote:
On Jun 18, 2016, at 10:44 PM, Yuxi Chen via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Hi All,
When I use llvm, I encounter a problem like "unable to schedule pass A
required by C"
I investigated deeper. It's like:
I have three passes, say A, B, C(all are on function level)
A would modify IR code. (change instruction order)
For pass B,
I would use the result of pass A, I use addRequired<B>(), and
&getAnalysis<B>(), it works.
void getAnalysisUsage(AU){
AU.addRequired<A>();
}
For pass C, it will use the results of pass A and B.
I use the way as used for pass B, but it failed, even for LoopInfo analysis
pass(which is the built-in analysis pass).
void getAnalysisUsage(AU){
AU.addRequired<A>();
AU.addRequired<B>();
}
It seems because A would modify IR code, so for pass C, I need first load pass A
then pass B, otherwise it will be invalidated.
However, when I change the using order, I still got error "unable to
schedule pass A required by C".
Does anyone encounter the same problem before and have a solution?
Any help is appreciated.
Depending on other transformations isn’t recommended, and isn’t supported by the
soon-new-passmanager I believe.
The expectation is that the passes are added in order to the pass manager by the
client.
Depending on transformation passes isn't supported by the legacy
PassManager, either. Occasionally some passes can get away with it, but it
often results in unschedule-able pass pipelines as above.
If your transform pass does something to the code, other passes should either
infer what it did by examining the IR. the IR contains the definitive
information about the program (because it is the program).
Alternatively, you could create an analysis pass upon which both your transform
and analysis passes depend. The transform pass would update this new analysis
pass with information on what it transformed; your later analysis passes could
then query this information. This approach is fragile, but it could work.
Regards,
John Criswell
In you case, I expect that it would “work” by removing the dependency from C to
A. If C requires B and B requires A, by scheduling C you’ll get A, B, C in
sequence.
—
Mehdi
Best,
Yuxi
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell
--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160622/504a893a/attachment-0001.html>
1. If I don't use getAnalysisUsage, are there other ways to implement
invocation of different passes.
2. Transform pass can't rely on other transform passes, if we really want to
do that, what can we do?
Best,
Yuxi
________________________________
From: John Criswell [jtcriswel at gmail.com]
Sent: Tuesday, June 21, 2016 11:01 AM
To: Yuxi Chen
Cc: llvm-dev at lists.llvm.org; llvmdev-bounces at cs.uiuc.edu; llvmdev at
cs.uiuc.edu
Subject: Re: [llvm-dev] pass invalidation
On 6/20/16 3:46 PM, Yuxi Chen wrote:
Hi,
Thanks for your reply.
But I still don't know how a transform pass updates a new analysis pass
after it modifies the IR. Can you explain it clearly? I am not familiar with
pass management and invocation.
Passes can have methods that allow their internal state to be updated by other
passes (the same way that their state can be queried by other passes). For
example, the alias analysis passes have methods for querying alias information
as well as methods that allow other passes to update the aliasing information
when they make changes to the IR (so that friendly optimization passes don't
invalidate alias analysis information when they make simple changes).
Right now, your transform pass has a method which your other passes are using to
query information (I am guessing that your transform pass is recording
information on what it has done). I am suggesting that you create a new pass
(call it "RK" for "Record Keeper") that implements this
method (call it getInfo()). Additionally, the RK pass also implements a method
called setInfo() which the transform pass uses to record any information that
later passes will need. In their getAnalysisUsage<>() method, your passes
preserve the results of the RK pass.
In this way, your transform pass modifies the IR and dumps any information
needed by your analysis passes into the RK pass. The RK pass does not modify
the IR, so it doesn't create an impossible-to-schedule pass pipeline like
your transform pass does.
If this isn't clear, please let me know. I see that you're from
UChicago, so I'm guessing that you need this for a research project.
Regards,
John Criswell
Best,
Yuxi
________________________________
From: John Criswell [jtcriswel at gmail.com<mailto:jtcriswel at
gmail.com>]
Sent: Sunday, June 19, 2016 10:05 AM
To: Mehdi Amini; Yuxi Chen
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>;
llvmdev-bounces at cs.uiuc.edu<mailto:llvmdev-bounces at cs.uiuc.edu>;
llvmdev at cs.uiuc.edu<mailto:llvmdev at cs.uiuc.edu>
Subject: Re: [llvm-dev] pass invalidation
On 6/19/16 4:28 AM, Mehdi Amini via llvm-dev wrote:
On Jun 18, 2016, at 10:44 PM, Yuxi Chen via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Hi All,
When I use llvm, I encounter a problem like "unable to schedule pass A
required by C"
I investigated deeper. It's like:
I have three passes, say A, B, C(all are on function level)
A would modify IR code. (change instruction order)
For pass B,
I would use the result of pass A, I use addRequired<B>(), and
&getAnalysis<B>(), it works.
void getAnalysisUsage(AU){
AU.addRequired<A>();
}
For pass C, it will use the results of pass A and B.
I use the way as used for pass B, but it failed, even for LoopInfo analysis
pass(which is the built-in analysis pass).
void getAnalysisUsage(AU){
AU.addRequired<A>();
AU.addRequired<B>();
}
It seems because A would modify IR code, so for pass C, I need first load pass A
then pass B, otherwise it will be invalidated.
However, when I change the using order, I still got error "unable to
schedule pass A required by C".
Does anyone encounter the same problem before and have a solution?
Any help is appreciated.
Depending on other transformations isn’t recommended, and isn’t supported by the
soon-new-passmanager I believe.
The expectation is that the passes are added in order to the pass manager by the
client.
Depending on transformation passes isn't supported by the legacy
PassManager, either. Occasionally some passes can get away with it, but it
often results in unschedule-able pass pipelines as above.
If your transform pass does something to the code, other passes should either
infer what it did by examining the IR. the IR contains the definitive
information about the program (because it is the program).
Alternatively, you could create an analysis pass upon which both your transform
and analysis passes depend. The transform pass would update this new analysis
pass with information on what it transformed; your later analysis passes could
then query this information. This approach is fragile, but it could work.
Regards,
John Criswell
In you case, I expect that it would “work” by removing the dependency from C to
A. If C requires B and B requires A, by scheduling C you’ll get A, B, C in
sequence.
—
Mehdi
Best,
Yuxi
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell
--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160622/ac4e20e0/attachment.html>
> On Jun 22, 2016, at 2:15 AM, Yuxi Chen via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > 1. If I don't use getAnalysisUsage, are there other ways to implement invocation of different passes.You can invoke other transformation directly, not as passes but just as utility (if they were designed such that it is possible)> 2. Transform pass can't rely on other transform passes, if we really want to do that, what can we do?Schedule them explicitly in the pass manager. — Mehdi> > Best, > Yuxi > From: John Criswell [jtcriswel at gmail.com] > Sent: Tuesday, June 21, 2016 11:01 AM > To: Yuxi Chen > Cc: llvm-dev at lists.llvm.org; llvmdev-bounces at cs.uiuc.edu; llvmdev at cs.uiuc.edu > Subject: Re: [llvm-dev] pass invalidation > > On 6/20/16 3:46 PM, Yuxi Chen wrote: >> Hi, >> >> Thanks for your reply. >> But I still don't know how a transform pass updates a new analysis pass after it modifies the IR. Can you explain it clearly? I am not familiar with pass management and invocation. > > Passes can have methods that allow their internal state to be updated by other passes (the same way that their state can be queried by other passes). For example, the alias analysis passes have methods for querying alias information as well as methods that allow other passes to update the aliasing information when they make changes to the IR (so that friendly optimization passes don't invalidate alias analysis information when they make simple changes). > > Right now, your transform pass has a method which your other passes are using to query information (I am guessing that your transform pass is recording information on what it has done). I am suggesting that you create a new pass (call it "RK" for "Record Keeper") that implements this method (call it getInfo()). Additionally, the RK pass also implements a method called setInfo() which the transform pass uses to record any information that later passes will need. In their getAnalysisUsage<>() method, your passes preserve the results of the RK pass. > > In this way, your transform pass modifies the IR and dumps any information needed by your analysis passes into the RK pass. The RK pass does not modify the IR, so it doesn't create an impossible-to-schedule pass pipeline like your transform pass does. > > If this isn't clear, please let me know. I see that you're from UChicago, so I'm guessing that you need this for a research project. > > Regards, > > John Criswell > > >> >> Best, >> Yuxi >> From: John Criswell [jtcriswel at gmail.com <mailto:jtcriswel at gmail.com>] >> Sent: Sunday, June 19, 2016 10:05 AM >> To: Mehdi Amini; Yuxi Chen >> Cc: llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>; llvmdev-bounces at cs.uiuc.edu <mailto:llvmdev-bounces at cs.uiuc.edu>; llvmdev at cs.uiuc.edu <mailto:llvmdev at cs.uiuc.edu> >> Subject: Re: [llvm-dev] pass invalidation >> >> On 6/19/16 4:28 AM, Mehdi Amini via llvm-dev wrote: >>> >>>> On Jun 18, 2016, at 10:44 PM, Yuxi Chen via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: >>>> >>>> Hi All, >>>> >>>> When I use llvm, I encounter a problem like "unable to schedule pass A required by C" >>>> I investigated deeper. It's like: >>>> I have three passes, say A, B, C(all are on function level) >>>> A would modify IR code. (change instruction order) >>>> >>>> For pass B, >>>> I would use the result of pass A, I use addRequired<B>(), and &getAnalysis<B>(), it works. >>>> >>>> void getAnalysisUsage(AU){ >>>> AU.addRequired<A>(); >>>> } >>>> >>>> >>>> For pass C, it will use the results of pass A and B. >>>> I use the way as used for pass B, but it failed, even for LoopInfo analysis pass(which is the built-in analysis pass). >>>> void getAnalysisUsage(AU){ >>>> AU.addRequired<A>(); >>>> AU.addRequired<B>(); >>>> } >>>> >>>> >>>> It seems because A would modify IR code, so for pass C, I need first load pass A then pass B, otherwise it will be invalidated. >>>> However, when I change the using order, I still got error "unable to schedule pass A required by C". >>>> >>>> Does anyone encounter the same problem before and have a solution? >>>> Any help is appreciated. >>> >>> Depending on other transformations isn’t recommended, and isn’t supported by the soon-new-passmanager I believe. >>> The expectation is that the passes are added in order to the pass manager by the client. >> >> Depending on transformation passes isn't supported by the legacy PassManager, either. Occasionally some passes can get away with it, but it often results in unschedule-able pass pipelines as above. >> >> If your transform pass does something to the code, other passes should either infer what it did by examining the IR. the IR contains the definitive information about the program (because it is the program). >> >> Alternatively, you could create an analysis pass upon which both your transform and analysis passes depend. The transform pass would update this new analysis pass with information on what it transformed; your later analysis passes could then query this information. This approach is fragile, but it could work. >> >> Regards, >> >> John Criswell >> >>> >>> In you case, I expect that it would “work” by removing the dependency from C to A. If C requires B and B requires A, by scheduling C you’ll get A, B, C in sequence. >>> >>> — >>> Mehdi >>> >>> >>> >>>> >>>> Best, >>>> Yuxi >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> >>> >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> >> >> >> -- >> John Criswell >> Assistant Professor >> Department of Computer Science, University of Rochester >> http://www.cs.rochester.edu/u/criswell <http://www.cs.rochester.edu/u/criswell> > > -- > John Criswell > Assistant Professor > Department of Computer Science, University of Rochester > http://www.cs.rochester.edu/u/criswell <http://www.cs.rochester.edu/u/criswell>_______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160622/233974ba/attachment.html>
On 6/22/16 1:15 AM, Yuxi Chen wrote:> 1. If I don't use getAnalysisUsage, are there other ways to implement > invocation of different passes.As Mehdi stated, you must explicitly run the other passes by scheduling them in the pass manager. If you're using opt to run your pass, you just tell opt to run the transform passes before your passes. If you're writing a tool, you have code that creates a PassManager object and adds passes to the PassManager object. In that case, you just add the tranform passes to the PassManager object in the correct order.> 2. Transform pass can't rely on other transform passes, if we really > want to do that, what can we do?To clarify, transform passes can depend upon *analysis* passes (i.e., passes that don't change the program). All passes should avoid using addRequired<>() in their getAnalysisUsage<>() methods to depend upon transform passes. Regards, John Criswell> > Best, > Yuxi > ------------------------------------------------------------------------ > *From:* John Criswell [jtcriswel at gmail.com] > *Sent:* Tuesday, June 21, 2016 11:01 AM > *To:* Yuxi Chen > *Cc:* llvm-dev at lists.llvm.org; llvmdev-bounces at cs.uiuc.edu; > llvmdev at cs.uiuc.edu > *Subject:* Re: [llvm-dev] pass invalidation > > On 6/20/16 3:46 PM, Yuxi Chen wrote: >> Hi, >> >> Thanks for your reply. >> But I still don't know how a transform pass updates a new analysis >> pass after it modifies the IR. Can you explain it clearly? I am not >> familiar with pass management and invocation. > > Passes can have methods that allow their internal state to be updated > by other passes (the same way that their state can be queried by other > passes). For example, the alias analysis passes have methods for > querying alias information as well as methods that allow other passes > to update the aliasing information when they make changes to the IR > (so that friendly optimization passes don't invalidate alias analysis > information when they make simple changes). > > Right now, your transform pass has a method which your other passes > are using to query information (I am guessing that your transform pass > is recording information on what it has done). I am suggesting that > you create a new pass (call it "RK" for "Record Keeper") that > implements this method (call it getInfo()). Additionally, the RK pass > also implements a method called setInfo() which the transform pass > uses to record any information that later passes will need. In their > getAnalysisUsage<>() method, your passes preserve the results of the > RK pass. > > In this way, your transform pass modifies the IR and dumps any > information needed by your analysis passes into the RK pass. The RK > pass does not modify the IR, so it doesn't create an > impossible-to-schedule pass pipeline like your transform pass does. > > If this isn't clear, please let me know. I see that you're from > UChicago, so I'm guessing that you need this for a research project. > > Regards, > > John Criswell > > >> >> Best, >> Yuxi >> ------------------------------------------------------------------------ >> *From:* John Criswell [jtcriswel at gmail.com] >> *Sent:* Sunday, June 19, 2016 10:05 AM >> *To:* Mehdi Amini; Yuxi Chen >> *Cc:* llvm-dev at lists.llvm.org; llvmdev-bounces at cs.uiuc.edu; >> llvmdev at cs.uiuc.edu >> *Subject:* Re: [llvm-dev] pass invalidation >> >> On 6/19/16 4:28 AM, Mehdi Amini via llvm-dev wrote: >>> >>>> On Jun 18, 2016, at 10:44 PM, Yuxi Chen via llvm-dev >>>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: >>>> >>>> Hi All, >>>> >>>> When I use llvm, I encounter a problem like "unable to schedule >>>> pass A required by C" >>>> I investigated deeper. It's like: >>>> I have three passes, say A, B, C(all are on function level) >>>> A would modify IR code. (change instruction order) >>>> >>>> For pass B, >>>> I would use the result of pass A, I use addRequired<B>(), and >>>> &getAnalysis<B>(), it works. >>>> >>>> void getAnalysisUsage(AU){ >>>> AU.addRequired<A>(); >>>> } >>>> >>>> >>>> For pass C, it will use the results of pass A and B. >>>> I use the way as used for pass B, but it failed, even for LoopInfo >>>> analysis pass(which is the built-in analysis pass). >>>> void getAnalysisUsage(AU){ >>>> AU.addRequired<A>(); >>>> AU.addRequired<B>(); >>>> } >>>> >>>> >>>> It seems because A would modify IR code, so for pass C, I need >>>> first load pass A then pass B, otherwise it will be invalidated. >>>> However, when I change the using order, I still got error "unable >>>> to schedule pass A required by C". >>>> >>>> Does anyone encounter the same problem before and have a solution? >>>> Any help is appreciated. >>> >>> Depending on other transformations isn’t recommended, and isn’t >>> supported by the soon-new-passmanager I believe. >>> The expectation is that the passes are added in order to the pass >>> manager by the client. >> >> Depending on transformation passes isn't supported by the legacy >> PassManager, either. Occasionally some passes can get away with it, >> but it often results in unschedule-able pass pipelines as above. >> >> If your transform pass does something to the code, other passes >> should either infer what it did by examining the IR. the IR contains >> the definitive information about the program (because it is the program). >> >> Alternatively, you could create an analysis pass upon which both your >> transform and analysis passes depend. The transform pass would >> update this new analysis pass with information on what it >> transformed; your later analysis passes could then query this >> information. This approach is fragile, but it could work. >> >> Regards, >> >> John Criswell >> >>> >>> In you case, I expect that it would “work” by removing the >>> dependency from C to A. If C requires B and B requires A, by >>> scheduling C you’ll get A, B, C in sequence. >>> >>> — >>> Mehdi >>> >>> >>> >>>> >>>> Best, >>>> Yuxi >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >>> >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> >> >> -- >> John Criswell >> Assistant Professor >> Department of Computer Science, University of Rochester >> http://www.cs.rochester.edu/u/criswell > > > -- > John Criswell > Assistant Professor > Department of Computer Science, University of Rochester > http://www.cs.rochester.edu/u/criswell-- John Criswell Assistant Professor Department of Computer Science, University of Rochester http://www.cs.rochester.edu/u/criswell -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160622/e7fdb62c/attachment-0001.html>
On 6/22/16 1:02 AM, Yuxi Chen wrote:> Hi Prof. John Criswell, > > Really appreciate your detailed reply. > Yes, I am using llvm to analyse C code for my research, I am quite new > for llvm and clang.Just to check, have you read the "How to Write an LLVM Pass" document on the LLVM web page?> I still have several questions. > 1. To my understanding, if we add pass in getAnalysisUsage method(like > LoopInfo), every time(for function pass), when we invoke > runOnFunction(), llvm would automatically load result of LoopInfo, > right? But when runOnFunction is invoked? It's in constructor?A pass is a C++ object. For a FunctionPass, the pass manager will create the pass object once and then call its runOnFunction() method for every function in the program. Additionally, if a ModulePass requires a FunctionPass, then the pass manager will call the runOnFunction() method on any function that the ModulePass requests. If you are using opt, use the -debug-pass=Structure argument to make opt print out the structure of passes. That will probably make it more clear as to how passes are scheduled and run. Finally, if you're confused about when your passes are run, it might be better to write your passes as a ModulePass first. You can almost never go wrong writing a ModulePass, and they are simpler to understand than FunctionPasses.> > 2. right now, my passes includes several transform passes and analysis > passes. For transform passes, they also use some built-in analysis > passes, like AliasAnalysis, LoopInfo.Your transform passes can safely use any existing LLVM passes that do not modify the IR (such as AliasAnalysis and LoopInfo). The only real restriction is that you want to avoid using getAnalysis<>() to get pointers/references to passes that modify the IR.> My transform passes are to move some instructions around based on some > analysis passes. Then other analysis passes would use those modified > IR code. Your suggestion is to dump information needed by my analysis > passes into a new RK pass. I am not clear about it. Do you mean dump > the modified IR code? Then pass those modified IR into my analysis > pass? If so, if my transform pass analyses IR based on basicblock, > after analysing every basicblock, I need dump something? Seem I > misunderstood.What, specifically, do your analysis passes need to know? Do they need to know which IR is the modified IR and which was left unmodified, or does it need to know something else? Can it infer everything it needs to know just by looking at the IR? If your analysis passes can determine everything they need to know by looking at the Module or Function passed into their runOnModule()/runOnFunction() methods, then you have no problem (and, in fact, you don't need your transform passes to communicate any additional information to your analysis passes). However, if you need your transform pass to communicate information to your analysis passes, then you need to do something more sophisticated. Copying LLVM IR would be a bad idea (too much memory consumption); you would probably record pointers to the relevant IR objects instead. Perhaps an example will be helpful. Let's say that you write a pass (call it Pass A) that creates a clone of every function in a program. You have an analysis pass (call it Pass B) that takes each function and finds the clone that Pass A created. Pass A could implement a data structure that maps original functions to the clones it created and then provide a method to Pass B that would query this information. However, that would require Pass B to use addRequired<>() and getAnalysis<>() to get a pointer to Pass A. That could create a scheduling conflict that the PassManager cannot handle (e.g., Pass A invalidates another pass that Pass B requires). Instead, you create a Pass C that contains an empty map of functions to their clones. The runOnModule() method of Pass C does nothing. Pass C provides a method to record a new function->clone in its internal map, and it provides another method that takes a function and returns a pointer to its clone. Pass A and Pass B both require Pass C as a dependency in their getAnalysisUsage<>() methods. Pass A tells Pass C about every clone it creates; Pass B queries Pass C any time it wants to lookup the clone of a function. Additionally, Pass A states that it preserves Pass C in its getAnalysisUsage<>() method. In this example, Pass C is simply a pass through which Pass A and B communicate without creating a scheduling conflict for the pass manager. It is needed because Pass B needs information which is readily available in Pass A that cannot be easily inferred from the LLVM Module that Pass B analyzes. There are, of course, alternatives to this approach. Pass A could put metadata on the clones it creates that indicate that they are clones of other functions; Pass B then looks for this metadata. As long as other transforms don't remove the metadata, this works. Regards, John Criswell -- John Criswell Assistant Professor Department of Computer Science, University of Rochester http://www.cs.rochester.edu/u/criswell -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160622/ddf3f777/attachment.html>