On Tue, Oct 03, 2023 at 11:41:01AM +0000, Tamar Christina wrote:
> > We have stablesort method instead of
> > qsort but that would require consistent ordering in the vector (std::sort
> > doesn't ensure stable sorting either).
> >
> > If it is a non-issue, the patch is ok with the above nits fixed. Otherwise
> > perhaps we'd need to push in the first loop into the vector (but that
> > if (!phi_arg_map.get (arg))
> > args.quick_push (arg);
> > phi_arg_map.get_or_insert (arg).safe_push (i); in there was quite
> > inefficient, better would be
> > bool existed;
> > phi_arg_map.get_or_insert (arg, &existed).safe_push (i);
> > if (!existed)
> > args.safe_push (ifcvt_arg_entry { arg, 0, 0, vNULL }); or something
> > similar), plus use stablesort. Or add another compared member which would
> > be the first position.
>
> Hmm the problem here is that it would make the second loop that fills in the
> len
> quadratic as it has to search for arg in the list. I suppose I could push a
> pointer
> to the struct instead of `i` in the hashmap and the element into args and
> update
> the pointer as we go along? Would that work?
Only if the second loop traverses the hashmap elements and for each tries to
find the corresponding vector element.
If instead you do what you've done before in the second loop, walk the
vector and for each arg in there lookup phi_args_map.get (v.arg) (but please
just once, vanilla trunk looks it up twice in
for (int index : phi_arg_map.get (args[i]))
{
edge e = gimple_phi_arg_edge (phi, index);
len += get_bb_num_predicate_stmts (e->src);
}
unsigned occur = phi_arg_map.get (args[i])->length ();
), then I don't think it would be quadratic.
Jakub
