On Thu, Feb 22, 2018 at 04:30:34PM +0100, Peter Zijlstra wrote: > On Thu, Feb 22, 2018 at 11:12:10PM +0800, Boqun Feng wrote: > > On Thu, Feb 22, 2018 at 03:26:14PM +0100, Peter Zijlstra wrote: > > > > However, I would suggest: > > > > > > static inline bool is_xr(u16 dep) > > > { > > > return !!(dep & (DEP_NR_MASK | DEP_RR_MASK)); > > > } > > > > > > static inline bool is_rx(u16 dep) > > > { > > > return !!(dep & (DEP_RN_MASK | DEP_RR_MASK)); > > > } > > > > > > /* Skip *R -> R* relations */ > > > if (have_xr && is_rx(entry->dep)) > > > continue; > > > > I don't think this works, if we pick a *R for previous entry, and for > > current entry, we have RR, NN and NR, your approach will skip the > > current entry, but actually we can pick NN or NR (of course, in __bfs(), > > we can greedily pick NN, because if NR causes a deadlock, so does NN). > > I don't get it, afaict my suggestion is identical. > > You skip condition: pick_dep() < 0, evaluates to: > > is_rr && (!NN_MASK && !NR_MASK) := > is_rr && (RN_MASK | RR_MASK) > > Which is exactly what I have.
Ooh, I think I see what I did wrong, would something like: if (have_xr && !is_nx(entry-dep)) work? That's a lot harder to argue about though, still much better than that tri-state pick thing. > If that is satisfied, you set entry->is_rr to pick_dep(), which his > harder to evaluate, but is something like: > > is_rr && NR_MASK || !(NN_MASK | RN_MASK) := > is_rr && NR_MASK || (NR_MASK | RR_MASK) := > (NR_MASK | RR_MASK) > > (because is_rr && RR_MASK will have been skipped) > > > > > > > entry->have_xr = is_xr(entry->dep); This one I think is still correct though.