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

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

Hi Tobias,


I have attached a patch file to optimize string operations in Polly-Detect pass.
In this patch file, I put most of long string operations in the condition
variable of "PollyViewMode" or in the DEBUG mode.


Bests,
Star Tan




At 2013-07-22 22:27:48,"Tobias Grosser" <tobias at grosser.es>
wrote:
>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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130723/eaf056d0/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-ScopDetect-Optimize-compile-time-cost-for-log-string.patch
Type: application/octet-stream
Size: 9481 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130723/eaf056d0/attachment.obj>

On 07/22/2013 11:58 PM, Star Tan wrote:
> Hi Tobias,
>
>
> I have attached a patch file to optimize string operations in Polly-Detect
pass.
> In this patch file, I put most of long string operations in the condition
variable of "PollyViewMode" or in the DEBUG mode.
OK.
> From 448482106e8d815afa40e4ce8543ba3f6f0237f1 Mon Sep 17 00:00:00 2001
> From: Star Tan <tanmx_star at yeah.net>
> Date: Mon, 22 Jul 2013 23:48:45 -0700
> Subject: [PATCH] ScopDetect: Optimize compile-time cost for log string
>  operations.
>
> String operatioins resulted by raw_string_ostream in the INVALID macro can
lead
> to significant compile-time overhead when compiling large size source code.
> This is because raw_string_ostream relies on TypeFinder class, whose
> compile-time cost increases as the size of the module increases. This patch
> targets to avoid calling TypeFinder in normal case, so TypeFinder class is
only
> called in DEBUG mode with DEBUG macro or in PollyView mode.
>
> With this patch file, the relative compile-time cost of Polly-detect pass
does
> not increase even compiling very large size source code.
> ---
>  include/polly/Options.h        |  3 ++
>  include/polly/ScopDetection.h  |  6 +++
>  lib/Analysis/ScopDetection.cpp | 93
+++++++++++++++++++++++-------------------
>  lib/RegisterPasses.cpp         | 22 ++++++----
>  4 files changed, 75 insertions(+), 49 deletions(-)
>
> diff --git a/include/polly/Options.h b/include/polly/Options.h
> index 62e0960..733edd0 100644
> --- a/include/polly/Options.h
> +++ b/include/polly/Options.h
> @@ -17,4 +17,7 @@
>  #include "llvm/Support/CommandLine.h"
>
>  extern llvm::cl::OptionCategory PollyCategory;
> +namespace polly {
> +  extern bool PollyViewMode;
> +}
>  #endif
> diff --git a/include/polly/ScopDetection.h b/include/polly/ScopDetection.h
> index 6ee48ee..5a5d7d1 100755
> --- a/include/polly/ScopDetection.h
> +++ b/include/polly/ScopDetection.h
> @@ -145,6 +145,12 @@ class ScopDetection : public FunctionPass {
>    /// @return True if the call instruction is valid, false otherwise.
>    static bool isValidCallInst(CallInst &CI);
>
> +  /// @brief Report invalid alias.
> +  ///
> +  /// @param AS The alias set.
> +  /// @param Context The context of scop detection.
> +  void reportInvalidAlias(AliasSet &AS, DetectionContext &Context)
const;
Nice.
> diff --git a/lib/Analysis/ScopDetection.cpp
b/lib/Analysis/ScopDetection.cpp
> index 9b2a9a8..4f33f6c 100644
> --- a/lib/Analysis/ScopDetection.cpp
> +++ b/lib/Analysis/ScopDetection.cpp
> @@ -108,11 +108,13 @@ STATISTIC(ValidRegion, "Number of regions that a
valid part of Scop");
>
>  #define INVALID(NAME, MESSAGE)                                            
\
>    do {                                                                    
\
> -    std::string Buf;                                                      
\
> -    raw_string_ostream fmt(Buf);                                          
\
> -    fmt << MESSAGE;                                                 
\
> -    fmt.flush();                                                          
\
> -    LastFailure = Buf;                                                    
\
> +    if (PollyViewMode) {                                                  
\
I believe this variable should describe what we do, rather than if a
a certain user of this feature is enabled.

Something like

if (TrackFailures) {

}
> +void ScopDetection::reportInvalidAlias(AliasSet &AS,
> +                                       DetectionContext &Context)
const {
It is great that you extracted this function.
> +  std::string Message;
> +  raw_string_ostream OS(Message);
> +
> +  if (PollyViewMode || ::llvm::DebugFlag) {
This is a little unsatisfying. We now have two conditions that need to
be in sync. I think you can avoid this, if you rename the function to

std::string ScopDetection::formatInvalidAlias(AliasSet &AS)

and keep the INVALID_ macro at the place where the error happens.
> diff --git a/lib/RegisterPasses.cpp b/lib/RegisterPasses.cpp
> index 7fc0960..2e25e4d 100644
> --- a/lib/RegisterPasses.cpp
> +++ b/lib/RegisterPasses.cpp
> @@ -125,28 +125,34 @@ static cl::opt<bool>
DeadCodeElim("polly-run-dce",
>                                    cl::Hidden, cl::init(false),
cl::ZeroOrMore,
>                                    cl::cat(PollyCategory));
>
> -static cl::opt<bool>
> +bool polly::PollyViewMode;
> +
> +static cl::opt<bool, true>
>  PollyViewer("polly-show",
>              cl::desc("Highlight the code regions that will be
optimized in a "
>                       "(CFG BBs and LLVM-IR instructions)"),
> -            cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
> +            cl::location(polly::PollyViewMode), cl::init(false),
cl::ZeroOrMore,
> +            cl::cat(PollyCategory));
>
> -static cl::opt<bool>
> +static cl::opt<bool, true>
>  PollyOnlyViewer("polly-show-only",
>                  cl::desc("Highlight the code regions that will be
optimized in "
>                           "a (CFG only BBs)"),
> -                cl::init(false), cl::cat(PollyCategory));
> +                cl::location(polly::PollyViewMode), cl::init(false),
> +                cl::cat(PollyCategory));
> -static cl::opt<bool>
> +static cl::opt<bool, true>
>  PollyPrinter("polly-dot", cl::desc("Enable the Polly DOT
printer in -O3"),
>               cl::Hidden, cl::value_desc("Run the Polly DOT printer at
-O3"),
> -             cl::init(false), cl::cat(PollyCategory));
> +             cl::location(polly::PollyViewMode), cl::init(false),
> +             cl::cat(PollyCategory));
>
> -static cl::opt<bool> PollyOnlyPrinter(
> +static cl::opt<bool, true> PollyOnlyPrinter(
>      "polly-dot-only",
>      cl::desc("Enable the Polly DOT printer in -O3 (no BB
content)"), cl::Hidden,
>      cl::value_desc("Run the Polly DOT printer at -O3 (no BB
content"),
> -    cl::init(false), cl::cat(PollyCategory));
> +    cl::location(polly::PollyViewMode), cl::init(false),
> +    cl::cat(PollyCategory));
Sorry. Having all options storing their value in the very same location
does not look right.

When I was talking about cl::location() I rather ment that you introduce
a new option -polly-detect-track-failures that can also be set by an
cl::location.

Another alternative is that you add a parameter to Pass
*polly::createScopDetectionPass() { return new ScopDetection(); } which
can be used to enable the failure tracking.

Cheers,
Tobias