Artyom,
Can you please measure the performance impact of your patch and provide the
timing information along with the patch? Testing with the preprocessed files
we've sent you is a must.
Below are the results comparing the baseline with the revert of r218296 + the
other 2 patches you sent to be applied on top of it. I see an 84% slowdown with
the patches on gram.c, see below.
Anna.
--- baseline ---
Zakss-Mac-Pro:build-clang zaks$ time ./bin/clang --analyze ~/tmp/gram.c
gram.c:18574:200: warning: Value stored to 'yyptr' is never read
...* sizeof (*yyls) + (sizeof (union yyalloc) - 1); yyptr += yynewbytes /
sizeof (*yyptr); } while (0);
^
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gram.y:11400:18: warning: Assigned value is garbage or undefined
c->location = yylsp[-4];
^ ~~~~~~~~~
gram.y:11417:18: warning: Assigned value is garbage or undefined
w->location = yylsp[-3];
^ ~~~~~~~~~
gram.y:11715:18: warning: Assigned value is garbage or undefined
t->location = yylsp[-4];
^ ~~~~~~~~~
gram.y:11734:287: warning: Function call argument is an uninitialized value
...<< 24))), errmsg("interval precision specified twice"),
scanner_errposition(yylsp[-5], yyscanner))) : (voi...
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gram.y:11738:43: warning: Function call argument is an uninitialized value
t->typmods = lappend(yyvsp[0].list, makeIntConst(yyvsp[-3].ival,
yylsp[-3]));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gram.y:11741:60: warning: Function call argument is an uninitialized value
t->typmods = lcons(makeIntConst((0x7FFF), -1),
lcons(makeIntConst(yyvsp[-3].ival, yylsp[-3]), ((Lis...
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
7 warnings generated.
real 0m17.958s
user 0m17.020s
sys 0m0.302s
--- latest patches ---
Zakss-Mac-Pro:build-clang zaks$ time ./bin/clang --analyze ~/tmp/gram.c
gram.c:18574:200: warning: Value stored to 'yyptr' is never read
...* sizeof (*yyls) + (sizeof (union yyalloc) - 1); yyptr += yynewbytes /
sizeof (*yyptr); } while (0);
^
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gram.y:11400:18: warning: Assigned value is garbage or undefined
c->location = yylsp[-4];
^ ~~~~~~~~~
gram.y:11417:18: warning: Assigned value is garbage or undefined
w->location = yylsp[-3];
^ ~~~~~~~~~
gram.y:11715:18: warning: Assigned value is garbage or undefined
t->location = yylsp[-4];
^ ~~~~~~~~~
gram.y:11734:287: warning: Function call argument is an uninitialized value
...<< 24))), errmsg("interval precision specified twice"),
scanner_errposition(yylsp[-5], yyscanner))) : (voi...
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gram.y:11738:43: warning: Function call argument is an uninitialized value
t->typmods = lappend(yyvsp[0].list, makeIntConst(yyvsp[-3].ival,
yylsp[-3]));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gram.y:11741:60: warning: Function call argument is an uninitialized value
t->typmods = lcons(makeIntConst((0x7FFF), -1),
lcons(makeIntConst(yyvsp[-3].ival, yylsp[-3]), ((Lis...
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
7 warnings generated.
real 1m45.005s
user 1m43.871s
sys 0m0.418s
> On Oct 6, 2014, at 2:27 AM, Artyom Skrobov <[email protected]> wrote:
>
> Anna, sorry, now I see what you mean (I needed to pass --fblocks on the
> command line).
>
> The following simple patch fixes the performance in this case, as well as
> brings the implementation in line with the comment just above it (dequeue
> rather than unstack).
>
> Index: lib/Analysis/DataflowWorklist.cpp
> ===================================================================
> --- lib/Analysis/DataflowWorklist.cpp (revision 218295)
> +++ lib/Analysis/DataflowWorklist.cpp (working copy)
> @@ -58,8 +101,10 @@
> // First dequeue from the worklist. This can represent
> // updates along backedges that we want propagated as quickly as possible.
> - if (!worklist.empty())
> - B = worklist.pop_back_val();
> + if (!worklist.empty()) {
> + B = worklist.front();
> + worklist.erase(worklist.begin());
> + }
> // Next dequeue from the initial graph traversal (either post order or
> // reverse post order). This is the theoretical ideal in the presence
>
> The two patches are independent one from the other.
>
>
> From: Anna Zaks [mailto:[email protected]]
> Sent: 03 October 2014 19:56
> To: Artyom Skrobov
> Cc: Alexander Kornienko; Ted Kremenek; [email protected]
> Subject: Re: [PATCH] Inverse post-order traversal for LiveVariables analysis,
> to recover the performance after r214064
>
> The analyzer is still timing out for me on postgresql.
>
> I am going to send a preprocessed file off line.
>
> Maybe you will find some answers by looking at other performance related
> patches for LiveVariables that have been committed over years.
>
> Anna.
>> On Oct 2, 2014, at 4:45 AM, Artyom Skrobov <[email protected]
>> <mailto:[email protected]>> wrote:
>>
>> Hello,
>>
>> I see now that the CFG iteration orders, so painstakingly defined during the
>> previous round of reviews in Aug, didn’t entirely match the pre-r214064
>> behaviour.
>>
>> Attached is a patch that simplifies PostOrderCFGView significantly, making
>> the two possible iteration orders really obvious.
>>
>> I have tested it with both Alexander’s testcases (analyzer-regression1.c
>> from Sep, and options.c from Aug), and it shows good performance on both.
>>
>> OK to un-revert r218296, and to commit this patch on top of that?
>>
>>
>> From: Alexander Kornienko [mailto:[email protected]
>> <mailto:[email protected]>]
>> Sent: 21 September 2014 01:16
>> To: Artyom Skrobov
>> Cc: Anna Zaks; [email protected] <mailto:[email protected]>
>> Commits
>> Subject: Re: [PATCH] Inverse post-order traversal for LiveVariables
>> analysis, to recover the performance after r214064
>>
>> I'm attaching one of the files that regressed after r214064 and never got
>> fixed (preprocessed ceval.c from Python 3.3).
>>
>> On Sat, Sep 20, 2014 at 5:38 PM, Alexander Kornienko <[email protected]
>> <mailto:[email protected]>> wrote:
>> I actually still think, that I have some code that started taking large time
>> to be analyzed after r214064 and didn't recover after r215650. But I didn't
>> get to creating a reasonable repro for you. And the number of files left
>> affected after r215650 is so small, that I didn't prioritize this high
>> enough. I'll still try to provide a repro soon.
>> On 20 Sep 2014 17:10, "Artyom Skrobov" <[email protected]
>> <mailto:[email protected]>> wrote:
>> Anna, do you mean the performance had been acceptable after r214064, but
>> degraded after r215650, which fixed the performance regression introduced in
>> r214064?
>>
>> Do you have any specific example of code that takes longer to compile after
>> r215650?
>>
>> Not hearing back from Alexander since August, I assumed the performance
>> regression he observed after r215650 was not in fact related to that commit.
>>
>>
>> From: Anna Zaks [mailto:[email protected] <mailto:[email protected]>]
>> Sent: 20 September 2014 01:19
>> To: Artyom Skrobov
>> Cc: [email protected] <mailto:[email protected]> Commits; Ted
>> Kremenek; Jordan Rose; Alexander Kornienko
>> Subject: Re: [PATCH] Inverse post-order traversal for LiveVariables
>> analysis, to recover the performance after r214064
>>
>> Hi Artyom,
>>
>> Unfortunately, this commit (r215650) causes major performance regressions on
>> our buildbots. In particular, building postgresql-9.1 times out.
>>
>> Please, revert as soon as possible.
>>
>> Thank you,
>> Anna.
>>> On Aug 20, 2014, at 3:13 AM, Alexander Kornienko <[email protected]
>>> <mailto:[email protected]>> wrote:
>>>
>>> On Fri, Aug 15, 2014 at 10:38 AM, Artyom Skrobov <[email protected]
>>> <mailto:[email protected]>> wrote:
>>> Many thanks -- committed as r215650
>>>
>>> Alexander, can you confirm that the analyzer performance is now acceptable
>>> for your use cases?
>>>
>>> Artyom, sorry for the long delay. These files now work fine, but I still
>>> see up to 8-10 hours analysis time on a couple of other files. I'm sure I
>>> didn't see this before your first patch, but I can't yet tell in which
>>> revision it was introduced. I'll post more details and a repro later today.
>>>
>>>>
>>>>
>>>> -----Original Message-----
>>>> From: Ted kremenek [mailto:[email protected] <mailto:[email protected]>]
>>>> Sent: 14 August 2014 16:36
>>>> To: Artyom Skrobov
>>>> Cc: Alexander Kornienko; [email protected]
>>>> <mailto:[email protected]>
>>>> Subject: Re: [PATCH] Inverse post-order traversal for LiveVariables
>>>> analysis, to recover the performance after r214064
>>>>
>>>> Looks great to me.
>>>>
>>>> > On Aug 14, 2014, at 3:08 AM, Artyom Skrobov <[email protected]
>>>> > <mailto:[email protected]>>
>>>> wrote:
>>>> >
>>>> > Thank you Ted!
>>>> >
>>>> > Attaching the updated patch for a final review.
>>>> >
>>>> > Summary of changes:
>>>> >
>>>> > * Comments updated to reflect the two possible CFG traversal orders
>>>> > * PostOrderCFGView::po_iterator taken out of the header file
>>>> > * Iteration order for PostOrderCFGView changed to "reverse inverse
>>>> > post-order", the one required for a backward analysis
>>>> > * ReversePostOrderCFGView created, with the same iteration order that
>>>> > PostOrderCFGView used to have, the one required for a forward analysis
>>>> > * The two previous consumers of PostOrderCFGView, ThreadSafetyCommon.h
>>>> > and
>>>> > Consumed.cpp, switched to use ReversePostOrderCFGView
>>>> > * DataflowWorklistBase renamed to DataflowWorklist, and the two
>>>> > specializations named BackwardDataflowWorklist and
>>>> > ForwardDataflowWorklist
>>>> >
>>>> > I believe this naming scheme matches the accepted terminology best.
>>>>
>>>
>>> _______________________________________________
>>> cfe-commits mailing list
>>> [email protected] <mailto:[email protected]>
>>> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
>>> <http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits>
>>
>> <PostOrderCFGView.patch>
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
