Re: [PATCH] tree-optimization/109170 - bogus use-after-free with __builtin_expect

[Richard Biener <rguenther@suse.de>]

On Fri, 17 Mar 2023, Jakub Jelinek wrote:

> On Fri, Mar 17, 2023 at 02:18:52PM +0000, Richard Biener wrote:
> > > And as you show on the testcases, it probably isn't a good idea for
> > > BUILT_IN_EXPECT* either.
> > > 
> > > So, perhaps use op_cfn_pass_through_arg1 for the ERF_RETURNS_ARG functions
> > > and BUILT_IN_EXPECT* ?
> > 
> > But that already causes the problems (I didn't yet finish testing
> > adding RET1 to BUILT_IN_EXPECT*).  Note FRE currently does not use
> > returns_arg but I have old patches that do - but those replace
> > uses after a RET1 function with the return value to also reduce
> > spilling around a call (they of course CSE equal calls).
> 
> I meant in your patch drop the builtins.cc hunk and add from your
> other patch
> > > +    case CFN_BUILT_IN_EXPECT:
> > > +    case CFN_BUILT_IN_EXPECT_WITH_PROBABILITY:
> > > +      m_valid = true;
> > > +      m_op1 = gimple_call_arg (call, 0);
> > > +      m_int = &op_cfn_pass_through_arg1;
> > > +      break;
> 
> hunk to gimple_range_op_handler::maybe_builtin_call.
> Does that already cause the problems?

Yes, that's basically what the first variant of the patch did and
the FAILs quoted are from testing that variant.

There are no extra fails from the second more generic patch also
touching builtins.cc

> I mean, if we e.g. see that a range of the argument is singleton,
> then it is fine to optimize the __builtin_expect away.

Yes, it's somewhat odd that we handle the - case but not the +:

@@ -204,6 +206,7 @@
   _2 = b.0_1 < 0;
   # RANGE [irange] long int [0, 1] NONZERO 0x1
   _3 = (long int) _2;
+  # RANGE [irange] long int [0, 1] NONZERO 0x1
   _4 = __builtin_expect (_3, 0);
   if (_4 != 0)
     goto <bb 5>; [10.00%]
...
@@ -224,13 +228,14 @@
   goto <bb 3>; [100.00%]
 
   <bb 5> [local count: 977105059]:
-  # _9 = PHI <_4(3), 0(4)>
+  # RANGE [irange] long int [0, 1] NONZERO 0x1
+  # _9 = PHI <1(3), 0(4)>
   if (_9 != 0)
-    goto <bb 6>; [10.00%]
+    goto <bb 6>; [50.00%]
   else
-    goto <bb 7>; [90.00%]
+    goto <bb 7>; [50.00%]


 Predictions for bb 5
-  first match heuristics: 10.00%
-  combined heuristics: 10.00%
-  __builtin_expect heuristics of edge 5->6: 10.00%
+  no prediction heuristics: 50.00%
+  combined heuristics: 50.00%

the dumps don't get any hints on where the first matchor
__builtin_expect heuristic came from, but it looks like we
run expr_expected_value_1 on _9 != 0 which recurses for _9
and runs into the PHI handling which then looks for
a common value into the PHI.  In this case _4 is said
to be zero by PRED_BUILTIN_EXPECT and probability 9000.
But that seems wrong - it looks simply at the __builtin_expect
def here, not taking into account the edge this flows through
(the unlikely edge).

If we look at the recorded edge predictions we instead see

$28 = {ep_next = 0x43e4c80, ep_edge = <edge 0x7ffff67e0f00 (3 -> 5)>, 
  ep_predictor = PRED_BUILTIN_EXPECT, ep_probability = 1000}

so that's the same edge but unlikely now.  Of course there's
no value recorded for this.  For the other edge into the PHI
we get

$31 = {ep_next = 0x43c1e90, ep_edge = <edge 0x7ffff67e0f60 (4 -> 5)>, 
  ep_predictor = PRED_BUILTIN_EXPECT, ep_probability = 9000}

so to me a more reasonable approach would be to record '0' from
the 2nd edge with a probability of 9000 (or for the '+' case IL
'1' with a probability of 1000).  There's possibly a way to
combine predictor + value (here we'd simply take the more
probable value, or the constant for a PHI).  I also see that
we handle any PHI this way, not just PHIs defined in the same
BB as the condition which op we're ultimatively interested in.

So my conclusion is that currently it's pure luck the testcase
"works", and thus adjusting it and opening a bug with the
above findings would be appropriate?

Honza?

As for the LIM testcase, I'll try massaging it further, possibly
turning it into a GIMPLE testcase with fixed counts will make it
work.

Richard.