This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [Patch,tree-optimization]: Add new path Splitting pass on tree ssa representation


On 01/13/2016 01:10 AM, Jeff Law wrote:

I'm going to focus on adpcm for the moment, in particular adpcm_coder.
It appears the key blocks are:


;;   basic block 14, loop depth 1, count 0, freq 9100, maybe hot
;;    prev block 13, next block 15, flags: (NEW, REACHABLE)
;;    pred:       12 [100.0%]  (FALLTHRU,EXECUTABLE)
;;                13 [100.0%]  (FALLTHRU,EXECUTABLE)
   # valpred_12 = PHI <valpred_54(12), valpred_55(13)>
   _112 = MAX_EXPR <valpred_12, -32768>;
   valpred_18 = MIN_EXPR <_112, 32767>;
   delta_56 = delta_7 | iftmp.1_114;
   _57 = indexTable[delta_56];
   index_58 = _57 + index_107;
   _113 = MIN_EXPR <index_58, 88>;
   index_111 = MAX_EXPR <_113, 0>;
   step_59 = stepsizeTable[index_111];
   if (bufferstep_93 != 0)
     goto <bb 15>;
   else
     goto <bb 16>;
;;    succ:       15 [50.0%]  (TRUE_VALUE,EXECUTABLE)
;;                16 [50.0%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 15, loop depth 1, count 0, freq 4550, maybe hot
;;    prev block 14, next block 16, flags: (NEW, REACHABLE)
;;    pred:       14 [50.0%]  (TRUE_VALUE,EXECUTABLE)
   _60 = delta_56 << 4;
   goto <bb 17>;
;;    succ:       17 [100.0%]  (FALLTHRU,EXECUTABLE)

;;   basic block 16, loop depth 1, count 0, freq 4550, maybe hot
;;    prev block 15, next block 17, flags: (NEW, REACHABLE)
;;    pred:       14 [50.0%]  (FALSE_VALUE,EXECUTABLE)
   outp_62 = outp_83 + 1;
   _63 = (signed char) delta_56;
   _65 = (signed char) outputbuffer_90;
   _66 = _63 | _65;
   *outp_83 = _66;
;;    succ:       17 [100.0%]  (FALLTHRU,EXECUTABLE)

;;   basic block 17, loop depth 1, count 0, freq 9100, maybe hot
;;    prev block 16, next block 18, flags: (NEW, REACHABLE)
;;    pred:       15 [100.0%]  (FALLTHRU,EXECUTABLE)
;;                16 [100.0%]  (FALLTHRU,EXECUTABLE)
   # outp_3 = PHI <outp_83(15), outp_62(16)>
   # outputbuffer_21 = PHI <_60(15), outputbuffer_90(16)>
   _109 = bufferstep_93 ^ 1;
   _98 = _109 & 1;
   ivtmp.11_68 = ivtmp.11_105 + 2;
   if (ivtmp.11_68 != _116)
     goto <bb 4>;
   else
     goto <bb 18>;


Block #17 is the join point that we're going to effectively copy into
blocks #15 and #16.  Doing so in turn exposes bufferstep_93 as the
constant 0 in block #16, which in turn allows elimination of a couple
statements in the extended version of block #16 and we propagate the
constant 1 for bufferstep_93 to the top of the loop when reached via
block #16.  So we save a few instructions.  However, I think we're
actually doing a fairly poor job here.

bufferstep is a great example of a flip-flop variable and its value is
statically computable based on the path from the prior loop iteration
which, if exploited would allow the FSM threader to eliminate the
conditional at the end of bb14.  I'm going to have to play with that.
So I've extended DOM & uncprop to pick up the missed propagation opportunity, which in turn allows DOM to simplify this function even further and hopefully set ourselves up for either unrolling the loop or using the FSM threader to eliminate the test on bufferstep completely. But those are gcc-7 items.



Anyway, it's late and I want to rip this test apart a bit more and see
how it interacts with the heuristic that I've cobbled together as well
as see what it would take to have DOM or VRP get data on bufferstep_93
on the true path out of BB14 after a path-split.
As I expected, this showed a need for a minor tweak to the heuristic I'm poking at for path splitting. Nothing particularly hard, it needs further work (it's not compile-time efficient right now), but it's good enough to put away adpcm_code and continue looking more closely at adpcm_decode.

Jeff


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]