On Tue, 24 Sep 2024, Jeff Law wrote: > > > 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.
OK, I quickly looked but a simple BLOCK_FOR_INSN match on insn and init_insn wouldn't be enough since I guess we can have the single DF_REG_DEF after its (then uninitialized) use even in a single BB which would run into the memref_used_between_p assert the bitmap was supposed to prevent running into (one could change the failure mode as well, of course). I'm leaving further cleanup possibilities to somebody else and have now pushed both patches in the series. Thanks, Richard. > > > > 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 > >
