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

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

On 23 July 2013 16:50, Tobias Grosser <tobias at grosser.es> wrote:
> 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.
>
>
Is there any way to make the debug messages themselves more efficient?
Perhaps reimplementing it so that any table lookups are quick and no
malloc/free is done in the process.

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

On 07/23/2013 10:13 AM, James Courtier-Dutton wrote:
> On 23 July 2013 16:50, Tobias Grosser <tobias at grosser.es> wrote:
>
>> 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.
Hi James,
> Is there any way to make the debug messages themselves more efficient?
Yes, there are two ways:

1) Use the getName() function instead of the ostream writer

This is significantly faster than what we have today, but does not 
format unnamed instructions correctly (It does not create the %123 
instruction namings). Even though this is fast, it is probably still
slower than not doing any formatting at all.

2) Fix the AssemblyWriter as decribed by Daniel Berlin

There seems to be a larger issue in the printing infrastructure. It does
not seem to be written to print values many times.
> Perhaps reimplementing it so that any table lookups are quick and no
> malloc/free is done in the process.
Citing Daniel:

"The real fix is either to stop recreating these AssemblyWriter
objects, or improve caching in the bowels of it so that it doesn't
need to rerun typefinder again and again if nothing has changed."

So there is something that needs to be fixed when using the ostream 
formatter as we do. However, I do not think we should do this in this 
patch. Doing any kind of debug message formatting in the normal pass is 
unnecessary overhead that we should not have at all. The change Star 
proposes, moves this overhead out of the hot path, such that for debug 
messages we can now prioritize understandable formatting over performance.

Cheers,
Tobias