llvm dev - Jul 2013 - [LLVMdev] Analysis of polly-detect overhead in oggenc

On 07/21/2013 07:33 PM, Star Tan wrote:
> At 2013-07-22 01:40:31,"Tobias Grosser" <tobias at
grosser.es> wrote:
>
>> On 07/21/2013 09:49 AM, Star Tan wrote:
>>> Hi all,
>>>
>>>
>>> I have attached a patch file to reduce the polly-detect overhead.
>>
>> Great.
>>
>>> My idea is to avoid calling TypeFinder in Non-DEBUG mode, so
>>> TypeFinder is only called in DEBUG mode with the DEBUG macro.  This
>>> patch file did this work with following modifications:
>>>
>>>
>>> First, it keeps most of string information by replacing 
"<<" with "+" operation. For example, code like this:
>>>       INVALID(CFG, "Non branch instruction terminates BB:
" + BB.getName());
>>> would be converted into:
>>>      LastFailure = "Non branch instruction terminates BB:
" + BB.getName().str();
>>>
>>>
>>> Second, it simplifies some complex operations like:
>>>          INVALID(AffFunc,
>>>                 "Non affine branch in BB '" <<
BB.getName() << "' with LHS: "
>>>                                             << *LHS <<
" and RHS: " << *RHS);
>>> into:
>>>         LastFailure = "Non affine branch in BB: " +
BB.getName().str();
>>
>>
>>> In such cases, some information for "LHS" and
"RHS" are missed.
>>
>> Yes. And unfortunately, we may also loose the 'name' of unnamed
basic
>> blocks. Basic blocks without a name get formatted as %111 with
'111'
>> being their sequence number. Your above change will not be able to
>> derive this number.
> Yes, but it is much cheaper by using BB.getName().str().
> Currently, I cannot find a better way to derive unnamed basic block without
calling TypeFinder.
Yes, that's the reason why it was used in the first place.
>>> However, it only has little affects on the variable
"LastFailure",
>>> while keeping all information for DEBUG information.
>>
>> Why is that? It seems the DEBUG output is the very same that gets
>> written to "LastFailure".
> No, they are different. For example, the code like this:
>          INVALID(AffFunc,
>                  "Non affine branch in BB '" <<
BB.getName() << "' with LHS: "
>                                              << *LHS << "
and RHS: " << *RHS);
> would be converted to:
>        LastFailure = "Non affine branch in BB: " +
BB.getName().str();
>         INVALID(AffFunc,
>                LastFailure << "' with LHS: " <<
*LHS << " and RHS: " << *RHS);
> You see, information about LHS and RHS would be kept in INVALID DEBUG
information.
> To keep the information about unnamed basic blocks, I think we can rewrite
it as:
>        FailString = "Non affine branch in BB: ";
>        INVALID(AffFunc,
>                FailString << BB.getName() << "' with
LHS: "
>                           << *LHS << " and RHS: "
<< *RHS);
>        LastFailure = FailString + BB.getName().str();
>>
>>> Since the
>>> variable "LastFailure" is only used in ScopGraphPrinter,
which should
>>> only show critical information in graph, I hope such modification
is
>>> acceptable.
>>
>> Why should we only show critical information? In the GraphPrinter we do
>> not worry about compile time so much, such that we can easily show
>> helpful information. We just need to make sure that we do not slow down
>> the compile-time in the generic case.
> To my knowledge, all of those expensive operations are only used for the
variable "LastFailure", which is only used in GraphPrinter. Do you
mean the Graph Printer does not execute in the generic case?  If that is true, I
think we should control those operations for "LastFailure" as follows:
> if (In GraphPrinter mode) {
>    LastFailure = ...
> }
> In this way, we can completely remove those operations for
"LastFailure" in the generic case except in GraphPrinter mode.
Yes.

> What do you mean with "Normal Execution"?  Does the GraphPrinter
executes in "normal case"?
> If GraphPrinter is not executes in "normal case", we should move
all operations for "LastFailure" under the condition of 
"GraphPrinter" mode.
It is not executed in normal mode. So yes, we should move all this under 
the condition of 'GraphPrintingMode'.
>> I am not yet fully sure how the reportInvalid* functions should look
>> like. However, the part of your patch that is easy to commit without
>> further discussion is to move the 'return false' out of the
INVALID
>> macro. Meaning, translating the above code to:
>>
>>   if (checkSomething()) {
>>     INVALID(AffFunc, "Test" << SCEV <<);
>>     return false;
>>   }
>>
>> I propose to submit such a patch first and then focus on the remaining
>> problems.
> Yes, I agree with you.  I have attached a patch file to move "return
false" out of INVALID macro.
Great. Committed in r186805.

I propose two more patches:

	1) Transform the INVALID macro into function calls, that format
            the text and that set LastFailure.

         2) Add checks at the beginning of those function calls and
            continue only if LogErrors is set

The second one is slightly more involved as we would like to turn this 
option on automatically either in -debug mode or if -polly-show or 
-polly-show-only is set.

What do you think? Does this sound right?

Cheers,
Tobias

At 2013-07-22 12:16:53,"Tobias Grosser" <tobias at grosser.es>
wrote:
>On 07/21/2013 07:33 PM, Star Tan wrote:
>> At 2013-07-22 01:40:31,"Tobias Grosser" <tobias at
grosser.es> wrote:
>>
>>> On 07/21/2013 09:49 AM, Star Tan wrote:
>>>> Hi all,
>>>>
>>>>
>>>> I have attached a patch file to reduce the polly-detect
overhead.
>>>
>>> Great.
>>>
>>>> My idea is to avoid calling TypeFinder in Non-DEBUG mode, so
>>>> TypeFinder is only called in DEBUG mode with the DEBUG macro. 
This
>>>> patch file did this work with following modifications:
>>>>
>>>>
>>>> First, it keeps most of string information by replacing 
"<<" with "+" operation. For example, code like this:
>>>>       INVALID(CFG, "Non branch instruction terminates BB:
" + BB.getName());
>>>> would be converted into:
>>>>      LastFailure = "Non branch instruction terminates BB:
" + BB.getName().str();
>>>>
>>>>
>>>> Second, it simplifies some complex operations like:
>>>>          INVALID(AffFunc,
>>>>                 "Non affine branch in BB '"
<< BB.getName() << "' with LHS: "
>>>>                                             << *LHS
<< " and RHS: " << *RHS);
>>>> into:
>>>>         LastFailure = "Non affine branch in BB: " +
BB.getName().str();
>>>
>>>
>>>> In such cases, some information for "LHS" and
"RHS" are missed.
>>>
>>> Yes. And unfortunately, we may also loose the 'name' of
unnamed basic
>>> blocks. Basic blocks without a name get formatted as %111 with
'111'
>>> being their sequence number. Your above change will not be able to
>>> derive this number.
>> Yes, but it is much cheaper by using BB.getName().str().
>> Currently, I cannot find a better way to derive unnamed basic block
without calling TypeFinder.
>
>Yes, that's the reason why it was used in the first place.
>
>>>> However, it only has little affects on the variable
"LastFailure",
>>>> while keeping all information for DEBUG information.
>>>
>>> Why is that? It seems the DEBUG output is the very same that gets
>>> written to "LastFailure".
>> No, they are different. For example, the code like this:
>>          INVALID(AffFunc,
>>                  "Non affine branch in BB '" <<
BB.getName() << "' with LHS: "
>>                                              << *LHS <<
" and RHS: " << *RHS);
>> would be converted to:
>>        LastFailure = "Non affine branch in BB: " +
BB.getName().str();
>>         INVALID(AffFunc,
>>                LastFailure << "' with LHS: "
<< *LHS << " and RHS: " << *RHS);
>> You see, information about LHS and RHS would be kept in INVALID DEBUG
information.
>> To keep the information about unnamed basic blocks, I think we can
rewrite it as:
>>        FailString = "Non affine branch in BB: ";
>>        INVALID(AffFunc,
>>                FailString << BB.getName() << "'
with LHS: "
>>                           << *LHS << " and RHS: "
<< *RHS);
>>        LastFailure = FailString + BB.getName().str();
>>>
>>>> Since the
>>>> variable "LastFailure" is only used in
ScopGraphPrinter, which should
>>>> only show critical information in graph, I hope such
modification is
>>>> acceptable.
>>>
>>> Why should we only show critical information? In the GraphPrinter
we do
>>> not worry about compile time so much, such that we can easily show
>>> helpful information. We just need to make sure that we do not slow
down
>>> the compile-time in the generic case.
>> To my knowledge, all of those expensive operations are only used for
the variable "LastFailure", which is only used in GraphPrinter. Do you
mean the Graph Printer does not execute in the generic case?  If that is true, I
think we should control those operations for "LastFailure" as follows:
>> if (In GraphPrinter mode) {
>>    LastFailure = ...
>> }
>> In this way, we can completely remove those operations for
"LastFailure" in the generic case except in GraphPrinter mode.
>
>Yes.
>
>
>> What do you mean with "Normal Execution"?  Does the
GraphPrinter executes in "normal case"?
>> If GraphPrinter is not executes in "normal case", we should
move all operations for "LastFailure" under the condition of 
"GraphPrinter" mode.
>
>It is not executed in normal mode. So yes, we should move all this under 
>the condition of 'GraphPrintingMode'.
>
>>> I am not yet fully sure how the reportInvalid* functions should
look
>>> like. However, the part of your patch that is easy to commit
without
>>> further discussion is to move the 'return false' out of the
INVALID
>>> macro. Meaning, translating the above code to:
>>>
>>>   if (checkSomething()) {
>>>     INVALID(AffFunc, "Test" << SCEV <<);
>>>     return false;
>>>   }
>>>
>>> I propose to submit such a patch first and then focus on the
remaining
>>> problems.
>> Yes, I agree with you.  I have attached a patch file to move
"return false" out of INVALID macro.
>
>Great. Committed in r186805.
>
>I propose two more patches:
>
>	1) Transform the INVALID macro into function calls, that format
>            the text and that set LastFailure.
Translating the INVALID macro into function calls would complicate the
operations for different counters.
For example, currently users can add a new counter by simply adding the
following line:
BADSCOP_STAT(SimpleLoop, "Loop not in -loop-simplify form");
But if we translate INVALID macro into function calls, then users has to add a
function for this counter:
void INVLIAD_SimpleLoop (...).
This is because we cannot use the following macro combination in function calls:
    if (!Context.Verifying)                      \
      ++Bad##NAME##ForScop; 
So, I do not think it is necessary to translate the INVALID macro into function
calls.
Do you still think we should translate INVALID macro into a serial of functions
like "invalid_CFG, invalid_IndVar, invalid_IndEdge, ...  ? In that case, I
could provide a small patch file for this purpose -:)

>         2) Add checks at the beginning of those function calls and
>            continue only if LogErrors is set
Those invalid log strings are used for two separate cases:
1) The first case is for detailed debugging, which is controlled by the macro
DEBUG(dbgs() << MESSAGE). In such a case, string operations will
automatically skipped in normal execution mode with the following if-statement:
if (::llvm::DebugFlag && ::llvm::isCurrentDebugType(TYPE)) 
That means string operations controlled by DEBUG will not execute in normal
case, so we should not worry about it.
2) The other case is for the variable "LastFailure", which is used
only in GraphPrinter. Currently string operations for "LastFailure"
always execute in normal cases.  My idea is to put such string operations under
the condition of "GraphPrinter" mode. For example, I would like to
translate the "INVALID" macro into:
#define INVALID(NAME, MESSAGE)                                                 \
  do {                                                                         \
    if (GraphViewMode) {                                                       \
      std::string Buf;                                                         \
      raw_string_ostream fmt(Buf);                                             \
      fmt << MESSAGE;                                                     
\
      fmt.flush();                                                             \
      LastFailure = Buf;                                                       \
    }                                                                          \
    DEBUG(dbgs() << MESSAGE);                                             
\
    DEBUG(dbgs() << "\n");                                      
\
    assert(!Context.Verifying &&#NAME);                                 
\
    if (!Context.Verifying)                                                    \
      ++Bad##NAME##ForScop;                                                    \
  } while (0)
As you have suggested, we can construct the condition GraphViewMode with
"-polly-show", "-polly-show-only", "polly-dot" and
"polly-dot-only". However, I see all  these options  are defined as
"static" variables in lib/RegisterPasses.cpp.  Do you think I should
translate these local variables into global variables or should I define another
option like "-polly-dot-scop" in ScopDetection.cpp?
Thanks,
Star Tan

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130722/2ae24e5b/attachment.html>

On 07/22/2013 01:46 AM, Star Tan wrote:
> At 2013-07-22 12:16:53,"Tobias Grosser" <tobias at
grosser.es> wrote:
>> I propose two more patches:
>>
>> 	1) Transform the INVALID macro into function calls, that format
>>             the text and that set LastFailure.
> Translating the INVALID macro into function calls would complicate the
operations for different counters.
> For example, currently users can add a new counter by simply adding the
following line:
> BADSCOP_STAT(SimpleLoop, "Loop not in -loop-simplify form");
> But if we translate INVALID macro into function calls, then users has to
add a function for this counter:
> void INVLIAD_SimpleLoop (...).                                             
\
        ^^ No uppercase in function names.
> This is because we cannot use the following macro combination in function
calls:
>      if (!Context.Verifying)                      \
>        ++Bad##NAME##ForScop;
> So, I do not think it is necessary to translate the INVALID macro into
function calls.
> Do you still think we should translate INVALID macro into a serial of
functions like "invalid_CFG, invalid_IndVar, invalid_IndEdge, ...  ? In
that case, I could provide a small patch file for this purpose -:)
I think it would still be nice to get rid of this macro. We could 
probably have a default function that takes an enum to report different
errors in the reportInvalid(enum errorKind) style. And then several 
others that would allow more complex formatting (e.g. 
reportInvalidAlias(AliasSet)). Especially the code after 'isMustAlias()'
would be nice to move out of the main scop detection.

However, this issue is not directly related to the speedup work, so
you are welcome to skip it for now.

(Btw. thanks for not blindly following my suggestions!)
>>          2) Add checks at the beginning of those function calls and
>>             continue only if LogErrors is set
> Those invalid log strings are used for two separate cases:
> 1) The first case is for detailed debugging, which is controlled by the
macro DEBUG(dbgs() << MESSAGE). In such a case, string operations will
automatically skipped in normal execution mode with the following if-statement:
> if (::llvm::DebugFlag && ::llvm::isCurrentDebugType(TYPE))
> That means string operations controlled by DEBUG will not execute in normal
case, so we should not worry about it.
> 2) The other case is for the variable "LastFailure", which is
used only in GraphPrinter. Currently string operations for
"LastFailure" always execute in normal cases.  My idea is to put such
string operations under the condition of "GraphPrinter" mode. For
example, I would like to translate the "INVALID" macro into:
> #define INVALID(NAME, MESSAGE)                                             
\
>    do {                                                                    
\
>      if (GraphViewMode) {                                                  
\
>        std::string Buf;                                                    
\
>        raw_string_ostream fmt(Buf);                                        
\
>        fmt << MESSAGE;                                               
\
>        fmt.flush();                                                        
\
>        LastFailure = Buf;                                                  
\
>      }                                                                     
\
>      DEBUG(dbgs() << MESSAGE);                                       
\
>      DEBUG(dbgs() << "\n");                                
\
>      assert(!Context.Verifying &&#NAME);                           
\
>      if (!Context.Verifying)                                               
\
>        ++Bad##NAME##ForScop;                                               
\
>    } while (0)
Looks good.
> As you have suggested, we can construct the condition GraphViewMode with
"-polly-show", "-polly-show-only", "polly-dot" and
"polly-dot-only". However, I see all  these options  are defined as
"static" variables in lib/RegisterPasses.cpp.  Do you think I should
translate these local variables into global variables or should I define another
option like "-polly-dot-scop" in ScopDetection.cpp?
You can define a new option -polly-detect-collect-errors that enables 
the error tracking. Adding cl::location to this option allows you to
store the option value externally. You can use this to automatically
set this option, in case in lib/RegisterPasses.cpp in case -polly-show, 
-polly-show-only, ... have been set.

Cheers,
Tobias