| Message ID | CAO2gOZU+3A0g1O4isju=7N6_NFW+iaCZJfY4-eBf6Vm7bwWY8w@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
Ok. David On Mon, Nov 25, 2013 at 9:56 AM, Dehao Chen <dehao@google.com> wrote: > afdo_propagate_multi_edge can do everything afdo_propagate_single_edge > does. So we refactor the code to keep only one afdo_propagate_edge > function. > > Bootstrapped and passed all unittests and performance tests. > > OK for googlge branch? > > Thanks, > Dehao > > Index: gcc/auto-profile.c > =================================================================== > --- gcc/auto-profile.c (revision 205354) > +++ gcc/auto-profile.c (working copy) > @@ -1069,44 +1069,6 @@ afdo_find_equiv_class (void) > } > } > > -/* If a baisk block only has one in/out edge, then the bb count and he > - edge count should be the same. > - IS_SUCC is true if the out edge of the basic block is examined. > - Return TRUE if any basic block/edge count is changed. */ > - > -static bool > -afdo_propagate_single_edge (bool is_succ) > -{ > - basic_block bb; > - bool changed = false; > - > - FOR_EACH_BB (bb) > - if (is_succ ? single_succ_p (bb) : single_pred_p (bb)) > - { > - edge e = is_succ ? single_succ_edge (bb) : single_pred_edge (bb); > - if (((e->flags & EDGE_ANNOTATED) == 0) > - && ((bb->flags & BB_ANNOTATED) != 0)) > - { > - e->count = bb->count; > - e->flags |= EDGE_ANNOTATED; > - changed = true; > - } > - else if (((e->flags & EDGE_ANNOTATED) != 0) > - && ((bb->flags & BB_ANNOTATED) == 0)) > - { > - bb->count = e->count; > - bb->flags |= BB_ANNOTATED; > - changed = true; > - } > - else if (bb->count != e->count) > - { > - e->count = bb->count = MAX (bb->count, e->count); > - changed = true; > - } > - } > - return changed; > -} > - > /* If a basic block's count is known, and only one of its in/out edges' count > is unknown, its count can be calculated. > Meanwhile, if all of the in/out edges' counts are known, then the basic > @@ -1115,7 +1077,7 @@ afdo_find_equiv_class (void) > Return TRUE if any basic block/edge count is changed. */ > > static bool > -afdo_propagate_multi_edge (bool is_succ) > +afdo_propagate_edge (bool is_succ) > { > basic_block bb; > bool changed = false; > @@ -1281,14 +1243,10 @@ afdo_propagate (void) > { > changed = false; > > - if (afdo_propagate_single_edge (true)) > + if (afdo_propagate_edge (true)) > changed = true; > - if (afdo_propagate_single_edge (false)) > + if (afdo_propagate_edge (false)) > changed = true; > - if (afdo_propagate_multi_edge (true)) > - changed = true; > - if (afdo_propagate_multi_edge (false)) > - changed = true; > afdo_propagate_circuit (); > } > }
Thanks, Deaho. One other thing that I've found on the LLVM implementation (that I'm not sure happens in GCC): self-referential edges. If a loop consists of a single-basic block, the back edge will point to itself. I haven't been able to reproduce it with regular control flow constructs in GCC. When this happens, and if we've visited the block itself already (i.e., the block has weights), I've simply set the weight of the self-referential edge to the weight of the block itself. Do you see any problems with that heuristic? Thanks. Diego. On Mon, Nov 25, 2013 at 12:56 PM, Dehao Chen <dehao@google.com> wrote: > afdo_propagate_multi_edge can do everything afdo_propagate_single_edge > does. So we refactor the code to keep only one afdo_propagate_edge > function. > > Bootstrapped and passed all unittests and performance tests. > > OK for googlge branch? > > Thanks, > Dehao > > Index: gcc/auto-profile.c > =================================================================== > --- gcc/auto-profile.c (revision 205354) > +++ gcc/auto-profile.c (working copy) > @@ -1069,44 +1069,6 @@ afdo_find_equiv_class (void) > } > } > > -/* If a baisk block only has one in/out edge, then the bb count and he > - edge count should be the same. > - IS_SUCC is true if the out edge of the basic block is examined. > - Return TRUE if any basic block/edge count is changed. */ > - > -static bool > -afdo_propagate_single_edge (bool is_succ) > -{ > - basic_block bb; > - bool changed = false; > - > - FOR_EACH_BB (bb) > - if (is_succ ? single_succ_p (bb) : single_pred_p (bb)) > - { > - edge e = is_succ ? single_succ_edge (bb) : single_pred_edge (bb); > - if (((e->flags & EDGE_ANNOTATED) == 0) > - && ((bb->flags & BB_ANNOTATED) != 0)) > - { > - e->count = bb->count; > - e->flags |= EDGE_ANNOTATED; > - changed = true; > - } > - else if (((e->flags & EDGE_ANNOTATED) != 0) > - && ((bb->flags & BB_ANNOTATED) == 0)) > - { > - bb->count = e->count; > - bb->flags |= BB_ANNOTATED; > - changed = true; > - } > - else if (bb->count != e->count) > - { > - e->count = bb->count = MAX (bb->count, e->count); > - changed = true; > - } > - } > - return changed; > -} > - > /* If a basic block's count is known, and only one of its in/out edges' count > is unknown, its count can be calculated. > Meanwhile, if all of the in/out edges' counts are known, then the basic > @@ -1115,7 +1077,7 @@ afdo_find_equiv_class (void) > Return TRUE if any basic block/edge count is changed. */ > > static bool > -afdo_propagate_multi_edge (bool is_succ) > +afdo_propagate_edge (bool is_succ) > { > basic_block bb; > bool changed = false; > @@ -1281,14 +1243,10 @@ afdo_propagate (void) > { > changed = false; > > - if (afdo_propagate_single_edge (true)) > + if (afdo_propagate_edge (true)) > changed = true; > - if (afdo_propagate_single_edge (false)) > + if (afdo_propagate_edge (false)) > changed = true; > - if (afdo_propagate_multi_edge (true)) > - changed = true; > - if (afdo_propagate_multi_edge (false)) > - changed = true; > afdo_propagate_circuit (); > } > }
In this case the backedge will be a critical edge, which will be split by GCC. David On Mon, Nov 25, 2013 at 10:08 AM, Diego Novillo <dnovillo@google.com> wrote: > Thanks, Deaho. > > One other thing that I've found on the LLVM implementation (that I'm > not sure happens in GCC): self-referential edges. If a loop consists > of a single-basic block, the back edge will point to itself. I > haven't been able to reproduce it with regular control flow constructs > in GCC. > > When this happens, and if we've visited the block itself already > (i.e., the block has weights), I've simply set the weight of the > self-referential edge to the weight of the block itself. Do you see > any problems with that heuristic? > > > Thanks. Diego. > > On Mon, Nov 25, 2013 at 12:56 PM, Dehao Chen <dehao@google.com> wrote: >> afdo_propagate_multi_edge can do everything afdo_propagate_single_edge >> does. So we refactor the code to keep only one afdo_propagate_edge >> function. >> >> Bootstrapped and passed all unittests and performance tests. >> >> OK for googlge branch? >> >> Thanks, >> Dehao >> >> Index: gcc/auto-profile.c >> =================================================================== >> --- gcc/auto-profile.c (revision 205354) >> +++ gcc/auto-profile.c (working copy) >> @@ -1069,44 +1069,6 @@ afdo_find_equiv_class (void) >> } >> } >> >> -/* If a baisk block only has one in/out edge, then the bb count and he >> - edge count should be the same. >> - IS_SUCC is true if the out edge of the basic block is examined. >> - Return TRUE if any basic block/edge count is changed. */ >> - >> -static bool >> -afdo_propagate_single_edge (bool is_succ) >> -{ >> - basic_block bb; >> - bool changed = false; >> - >> - FOR_EACH_BB (bb) >> - if (is_succ ? single_succ_p (bb) : single_pred_p (bb)) >> - { >> - edge e = is_succ ? single_succ_edge (bb) : single_pred_edge (bb); >> - if (((e->flags & EDGE_ANNOTATED) == 0) >> - && ((bb->flags & BB_ANNOTATED) != 0)) >> - { >> - e->count = bb->count; >> - e->flags |= EDGE_ANNOTATED; >> - changed = true; >> - } >> - else if (((e->flags & EDGE_ANNOTATED) != 0) >> - && ((bb->flags & BB_ANNOTATED) == 0)) >> - { >> - bb->count = e->count; >> - bb->flags |= BB_ANNOTATED; >> - changed = true; >> - } >> - else if (bb->count != e->count) >> - { >> - e->count = bb->count = MAX (bb->count, e->count); >> - changed = true; >> - } >> - } >> - return changed; >> -} >> - >> /* If a basic block's count is known, and only one of its in/out edges' count >> is unknown, its count can be calculated. >> Meanwhile, if all of the in/out edges' counts are known, then the basic >> @@ -1115,7 +1077,7 @@ afdo_find_equiv_class (void) >> Return TRUE if any basic block/edge count is changed. */ >> >> static bool >> -afdo_propagate_multi_edge (bool is_succ) >> +afdo_propagate_edge (bool is_succ) >> { >> basic_block bb; >> bool changed = false; >> @@ -1281,14 +1243,10 @@ afdo_propagate (void) >> { >> changed = false; >> >> - if (afdo_propagate_single_edge (true)) >> + if (afdo_propagate_edge (true)) >> changed = true; >> - if (afdo_propagate_single_edge (false)) >> + if (afdo_propagate_edge (false)) >> changed = true; >> - if (afdo_propagate_multi_edge (true)) >> - changed = true; >> - if (afdo_propagate_multi_edge (false)) >> - changed = true; >> afdo_propagate_circuit (); >> } >> }
On Mon, Nov 25, 2013 at 10:08 AM, Diego Novillo <dnovillo@google.com> wrote: > Thanks, Deaho. > > One other thing that I've found on the LLVM implementation (that I'm > not sure happens in GCC): self-referential edges. If a loop consists > of a single-basic block, the back edge will point to itself. I > haven't been able to reproduce it with regular control flow constructs > in GCC. > > When this happens, and if we've visited the block itself already > (i.e., the block has weights), I've simply set the weight of the > self-referential edge to the weight of the block itself. Do you see > any problems with that heuristic? In this case, the propagate_edge function will keep increasing the BB count. We set a threshold (PARAM_AUTOFDO_MAX_PROPAGATE_ITERATIONS) to prevent it from making BB count too large. Dehao > > > Thanks. Diego. > > On Mon, Nov 25, 2013 at 12:56 PM, Dehao Chen <dehao@google.com> wrote: >> afdo_propagate_multi_edge can do everything afdo_propagate_single_edge >> does. So we refactor the code to keep only one afdo_propagate_edge >> function. >> >> Bootstrapped and passed all unittests and performance tests. >> >> OK for googlge branch? >> >> Thanks, >> Dehao >> >> Index: gcc/auto-profile.c >> =================================================================== >> --- gcc/auto-profile.c (revision 205354) >> +++ gcc/auto-profile.c (working copy) >> @@ -1069,44 +1069,6 @@ afdo_find_equiv_class (void) >> } >> } >> >> -/* If a baisk block only has one in/out edge, then the bb count and he >> - edge count should be the same. >> - IS_SUCC is true if the out edge of the basic block is examined. >> - Return TRUE if any basic block/edge count is changed. */ >> - >> -static bool >> -afdo_propagate_single_edge (bool is_succ) >> -{ >> - basic_block bb; >> - bool changed = false; >> - >> - FOR_EACH_BB (bb) >> - if (is_succ ? single_succ_p (bb) : single_pred_p (bb)) >> - { >> - edge e = is_succ ? single_succ_edge (bb) : single_pred_edge (bb); >> - if (((e->flags & EDGE_ANNOTATED) == 0) >> - && ((bb->flags & BB_ANNOTATED) != 0)) >> - { >> - e->count = bb->count; >> - e->flags |= EDGE_ANNOTATED; >> - changed = true; >> - } >> - else if (((e->flags & EDGE_ANNOTATED) != 0) >> - && ((bb->flags & BB_ANNOTATED) == 0)) >> - { >> - bb->count = e->count; >> - bb->flags |= BB_ANNOTATED; >> - changed = true; >> - } >> - else if (bb->count != e->count) >> - { >> - e->count = bb->count = MAX (bb->count, e->count); >> - changed = true; >> - } >> - } >> - return changed; >> -} >> - >> /* If a basic block's count is known, and only one of its in/out edges' count >> is unknown, its count can be calculated. >> Meanwhile, if all of the in/out edges' counts are known, then the basic >> @@ -1115,7 +1077,7 @@ afdo_find_equiv_class (void) >> Return TRUE if any basic block/edge count is changed. */ >> >> static bool >> -afdo_propagate_multi_edge (bool is_succ) >> +afdo_propagate_edge (bool is_succ) >> { >> basic_block bb; >> bool changed = false; >> @@ -1281,14 +1243,10 @@ afdo_propagate (void) >> { >> changed = false; >> >> - if (afdo_propagate_single_edge (true)) >> + if (afdo_propagate_edge (true)) >> changed = true; >> - if (afdo_propagate_single_edge (false)) >> + if (afdo_propagate_edge (false)) >> changed = true; >> - if (afdo_propagate_multi_edge (true)) >> - changed = true; >> - if (afdo_propagate_multi_edge (false)) >> - changed = true; >> afdo_propagate_circuit (); >> } >> }
On Mon, Nov 25, 2013 at 10:23 AM, Dehao Chen <dehao@google.com> wrote: > On Mon, Nov 25, 2013 at 10:08 AM, Diego Novillo <dnovillo@google.com> wrote: >> Thanks, Deaho. >> >> One other thing that I've found on the LLVM implementation (that I'm >> not sure happens in GCC): self-referential edges. If a loop consists >> of a single-basic block, the back edge will point to itself. I >> haven't been able to reproduce it with regular control flow constructs >> in GCC. >> >> When this happens, and if we've visited the block itself already >> (i.e., the block has weights), I've simply set the weight of the >> self-referential edge to the weight of the block itself. Do you see >> any problems with that heuristic? > > In this case, the propagate_edge function will keep increasing the BB > count. We set a threshold (PARAM_AUTOFDO_MAX_PROPAGATE_ITERATIONS) to > prevent it from making BB count too large. This is the infinite loop case .. David > > Dehao > >> >> >> Thanks. Diego. >> >> On Mon, Nov 25, 2013 at 12:56 PM, Dehao Chen <dehao@google.com> wrote: >>> afdo_propagate_multi_edge can do everything afdo_propagate_single_edge >>> does. So we refactor the code to keep only one afdo_propagate_edge >>> function. >>> >>> Bootstrapped and passed all unittests and performance tests. >>> >>> OK for googlge branch? >>> >>> Thanks, >>> Dehao >>> >>> Index: gcc/auto-profile.c >>> =================================================================== >>> --- gcc/auto-profile.c (revision 205354) >>> +++ gcc/auto-profile.c (working copy) >>> @@ -1069,44 +1069,6 @@ afdo_find_equiv_class (void) >>> } >>> } >>> >>> -/* If a baisk block only has one in/out edge, then the bb count and he >>> - edge count should be the same. >>> - IS_SUCC is true if the out edge of the basic block is examined. >>> - Return TRUE if any basic block/edge count is changed. */ >>> - >>> -static bool >>> -afdo_propagate_single_edge (bool is_succ) >>> -{ >>> - basic_block bb; >>> - bool changed = false; >>> - >>> - FOR_EACH_BB (bb) >>> - if (is_succ ? single_succ_p (bb) : single_pred_p (bb)) >>> - { >>> - edge e = is_succ ? single_succ_edge (bb) : single_pred_edge (bb); >>> - if (((e->flags & EDGE_ANNOTATED) == 0) >>> - && ((bb->flags & BB_ANNOTATED) != 0)) >>> - { >>> - e->count = bb->count; >>> - e->flags |= EDGE_ANNOTATED; >>> - changed = true; >>> - } >>> - else if (((e->flags & EDGE_ANNOTATED) != 0) >>> - && ((bb->flags & BB_ANNOTATED) == 0)) >>> - { >>> - bb->count = e->count; >>> - bb->flags |= BB_ANNOTATED; >>> - changed = true; >>> - } >>> - else if (bb->count != e->count) >>> - { >>> - e->count = bb->count = MAX (bb->count, e->count); >>> - changed = true; >>> - } >>> - } >>> - return changed; >>> -} >>> - >>> /* If a basic block's count is known, and only one of its in/out edges' count >>> is unknown, its count can be calculated. >>> Meanwhile, if all of the in/out edges' counts are known, then the basic >>> @@ -1115,7 +1077,7 @@ afdo_find_equiv_class (void) >>> Return TRUE if any basic block/edge count is changed. */ >>> >>> static bool >>> -afdo_propagate_multi_edge (bool is_succ) >>> +afdo_propagate_edge (bool is_succ) >>> { >>> basic_block bb; >>> bool changed = false; >>> @@ -1281,14 +1243,10 @@ afdo_propagate (void) >>> { >>> changed = false; >>> >>> - if (afdo_propagate_single_edge (true)) >>> + if (afdo_propagate_edge (true)) >>> changed = true; >>> - if (afdo_propagate_single_edge (false)) >>> + if (afdo_propagate_edge (false)) >>> changed = true; >>> - if (afdo_propagate_multi_edge (true)) >>> - changed = true; >>> - if (afdo_propagate_multi_edge (false)) >>> - changed = true; >>> afdo_propagate_circuit (); >>> } >>> }
On Mon, Nov 25, 2013 at 1:22 PM, Xinliang David Li <davidxl@google.com> wrote:
> In this case the backedge will be a critical edge, which will be split by GCC.
Right. So, if I split it, I will reach essentially the same
conclusion, I think. The new block will get the original block's
weight, which (in turn) will translate into the (now only outgoing)
edge.
Diego.
On Mon, Nov 25, 2013 at 10:26 AM, Diego Novillo <dnovillo@google.com> wrote: > On Mon, Nov 25, 2013 at 1:22 PM, Xinliang David Li <davidxl@google.com> wrote: >> In this case the backedge will be a critical edge, which will be split by GCC. > > Right. So, if I split it, I will reach essentially the same > conclusion, I think. The new block will get the original block's > weight, which (in turn) will translate into the (now only outgoing) > edge. Why do you want to set the back edge count as the BB count? I think the right formula is: count(back_edge) = count(BB) - count(entry_edge), in which entry_edge is the edge that enters the loop. Dehao > > > Diego.
On Mon, Nov 25, 2013 at 1:30 PM, Dehao Chen <dehao@google.com> wrote: > On Mon, Nov 25, 2013 at 10:26 AM, Diego Novillo <dnovillo@google.com> wrote: >> On Mon, Nov 25, 2013 at 1:22 PM, Xinliang David Li <davidxl@google.com> wrote: >>> In this case the backedge will be a critical edge, which will be split by GCC. >> >> Right. So, if I split it, I will reach essentially the same >> conclusion, I think. The new block will get the original block's >> weight, which (in turn) will translate into the (now only outgoing) >> edge. > > Why do you want to set the back edge count as the BB count? I think > the right formula is: count(back_edge) = count(BB) - > count(entry_edge), in which entry_edge is the edge that enters the > loop. Ah, yeah, you're right. The CFG I was looking at had an incoming weight of 0 (the code snippet spends 99.9% of its runtime in that loop. Thanks. Diego.
Index: gcc/auto-profile.c =================================================================== --- gcc/auto-profile.c (revision 205354) +++ gcc/auto-profile.c (working copy) @@ -1069,44 +1069,6 @@ afdo_find_equiv_class (void) } } -/* If a baisk block only has one in/out edge, then the bb count and he - edge count should be the same. - IS_SUCC is true if the out edge of the basic block is examined. - Return TRUE if any basic block/edge count is changed. */ - -static bool -afdo_propagate_single_edge (bool is_succ) -{ - basic_block bb; - bool changed = false; - - FOR_EACH_BB (bb) - if (is_succ ? single_succ_p (bb) : single_pred_p (bb)) - { - edge e = is_succ ? single_succ_edge (bb) : single_pred_edge (bb); - if (((e->flags & EDGE_ANNOTATED) == 0) - && ((bb->flags & BB_ANNOTATED) != 0)) - { - e->count = bb->count; - e->flags |= EDGE_ANNOTATED; - changed = true; - } - else if (((e->flags & EDGE_ANNOTATED) != 0) - && ((bb->flags & BB_ANNOTATED) == 0)) - { - bb->count = e->count; - bb->flags |= BB_ANNOTATED; - changed = true; - } - else if (bb->count != e->count) - { - e->count = bb->count = MAX (bb->count, e->count); - changed = true; - } - } - return changed; -} - /* If a basic block's count is known, and only one of its in/out edges' count is unknown, its count can be calculated. Meanwhile, if all of the in/out edges' counts are known, then the basic @@ -1115,7 +1077,7 @@ afdo_find_equiv_class (void) Return TRUE if any basic block/edge count is changed. */ static bool -afdo_propagate_multi_edge (bool is_succ) +afdo_propagate_edge (bool is_succ) { basic_block bb; bool changed = false; @@ -1281,14 +1243,10 @@ afdo_propagate (void) { changed = false; - if (afdo_propagate_single_edge (true)) + if (afdo_propagate_edge (true)) changed = true; - if (afdo_propagate_single_edge (false)) + if (afdo_propagate_edge (false)) changed = true; - if (afdo_propagate_multi_edge (true)) - changed = true; - if (afdo_propagate_multi_edge (false)) - changed = true; afdo_propagate_circuit (); } }