On Tue, Sep 24, 2013 at 10:57 AM, Jan Hubicka <hubi...@ucw.cz> wrote:
>>
>> I looked at one that failed after 100 as well (20031204-1.c). In this
>> case, it was due to expansion which was creating multiple branches/bbs
>> from a logical OR and guessing incorrectly on how to assign the
>> counts:
>>
>> if (octets == 4 && (*cp == ':' || *cp == '\0')) {
>>
>> The (*cp == ':' || *cp == '\0') part looked like the following going
>> into RTL expansion:
>>
>> [20031204-1.c : 31:33] _29 = _28 == 58;
>> [20031204-1.c : 31:33] _30 = _28 == 0;
>> [20031204-1.c : 31:33] _31 = _29 | _30;
>> [20031204-1.c : 31:18] if (_31 != 0)
>> goto <bb 16>;
>> else
>> goto <bb 19>;
>>
>> where the result of the OR was always true, so bb 16 had a count of
>> 100 and bb 19 a count of 0. When it was expanded, the expanded version
>> of the above turned into 2 bbs with a branch in between. Both
>> comparisons were done in the first bb, but the first bb checked
>> whether the result of the *cp == '\0' compare was true, and if not
>> branched to the check for whether the *cp == ':' compare was true. It
>> gave the branch to the second check against ':' a count of 0, so that
>> bb got a count of 0 and was split out, and put the count of 100 on the
>> fall through assuming the compare with '\0' always evaluated to true.
>> In reality, this OR condition was always true because *cp was ':', not
>> '\0'. Therefore, the count of 0 on the second block with the check for
>> ':' was incorrect, we ended up trying to execute it, and failed.
>
> I see, we produce:
> ;; if (_26 != 0)
>
> (insn 94 93 95 (set (reg:CCZ 17 flags)
> (compare:CCZ (reg:QI 107 [ D.2184 ])
> (const_int 0 [0]))) a.c:31 -1
> (nil))
>
> (insn 95 94 96 (set (reg:QI 122 [ D.2186 ])
> (eq:QI (reg:CCZ 17 flags)
> (const_int 0 [0]))) a.c:31 -1
> (nil))
>
> (insn 96 95 97 (set (reg:CCZ 17 flags)
> (compare:CCZ (reg:QI 122 [ D.2186 ])
> (const_int 0 [0]))) a.c:31 -1
> (nil))
>
> (jump_insn 97 96 98 (set (pc)
> (if_then_else (ne (reg:CCZ 17 flags)
> (const_int 0 [0]))
> (label_ref 100)
> (pc))) a.c:31 -1
> (expr_list:REG_BR_PROB (const_int 6100 [0x17d4])
> (nil)))
>
> (insn 98 97 99 (set (reg:CCZ 17 flags)
> (compare:CCZ (reg:QI 108 [ D.2186 ])
> (const_int 0 [0]))) a.c:31 -1
> (nil))
>
> (jump_insn 99 98 100 (set (pc)
> (if_then_else (eq (reg:CCZ 17 flags)
> (const_int 0 [0]))
> (label_ref 0)
> (pc))) a.c:31 -1
> (expr_list:REG_BR_PROB (const_int 3900 [0xf3c])
> (nil)))
>
> (code_label 100 99 0 14 "" [0 uses])
>
> That is because we TER together "_26 = _25 | _24" and "if (_26 != 0)"
>
> First I think the logic of do_jump should really be moved to trees. It is not
> doing things that can not be adequately represented by gimple.
>
> I am not that certain we want to move it before profiling though.
>>
>> Presumably we had the correct profile data for both blocks, but the
>> accuracy was reduced when the OR was represented as a logical
>> computation with a single branch. We could change the expansion code
>> to do something different, e.g. treat as a 50-50 branch. But we would
>> still end up with integer truncation issues when there was a single
>> training run. But that could be dealt with conservatively in the
>
> Yep, but it is still better than what we have now - if the test above was
> in hot part of program (i.e. not executed once), we will end up optimizing
> the second conditional for size.
>
> So I think it is do_jump bug to not distribute probabilities across the two
> conditoinals introduced.
>> bbpart code as I suggested for the jump threading issue above. I.e. a
>> cold block with incoming non-cold edges conservatively not marked cold
>> for splitting.
>
> Yep, we can probably do that, but we ought to fix the individual cases
> above at least for resonable number of runs.
I made this change and it removed a few of the failures.
I looked at another case that still failed with 1 train run but passed
with 100. It turned out to be another truncation issue exposed by RTL
expansion, where we created some control flow for a memset builtin
which was in a block with an execution count of 1. Some of the blocks
got frequencies less than half the original block, so the count was
rounded down or truncated to 0. I noticed that in this case (as well
as the jump threading case I fixed by looking for non-zero incoming
edges in partitioning) that the bb frequency was non-zero.
Why not just have probably_never_executed_bb_p return simply return
false bb->frequency is non-zero (right now it does the opposite -
returns true when bb->frequency is 0)? Making this change removed a
bunch of other failures. With this change as well, there are only 3
cases that still fail with 1 train run that pass with 100. Need to
look at those.
>
> Will you look into logic of do_jump or shall I try to dive in?
I can take a look, but probably won't have a chance until late this
week. If you don't get to it before then I will see if I can figure
out why it is applying the branch probabilities this way.
Teresa
>
> Honza
--
Teresa Johnson | Software Engineer | tejohn...@google.com | 408-460-2413
