On 9/24/24 6:34 AM, Richard Biener wrote:
For the testcase in PR114855 at -O1 add_store_equivs shows up as the
main sink for bitmap_set_bit because it uses a bitmap to mark all
seen insns by UID to make sure the forward walk in memref_used_between_p
will find the insn in question. Given we do have a CFG here the
functions operation is questionable, given memref_used_between_p
together with the walk of all insns is obviously quadratic in the
worst case that whole thing should be re-done ... but, for the
testcase, using a sbitmap of size get_max_uid () + 1 gets
bitmap_set_bit off the profile and improves IRA time from 15.58s (8%)
to 3.46s (2%).
Now, given above quadraticness I wonder whether we should instead
gate add_store_equivs on optimize > 1 or flag_expensive_optimizations.
Jeff, you added the bitmap in r6-7529-g14d7d4be52585b, I have no idea
how get_insns () works at this point and in which CFG mode we are but
a simplification might be to simply verify both insns are in the same
BB and hopefully get_insns gets us walk the insns in order there, thus
we could elide the bitmap completely (with some loss of cases, but
the function comment suggests it is supposed to catch single-BB
cases only anyway?!).
I don't recall the work, but looking at the PR and history, I'm pretty
confident the equivalence code here is assuming linear IL, so BB or
perhaps EBB. In retrospect it probably would have been better to
restrict the check to a BB/EBB.
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
OK if that succeeds?
Thanks,
Richard.
PR rtl-optimization/114855
* ira.cc (add_store_equivs): Use sbitmap for tracking
visited insns.
OK
jeff
