| Message ID | nycvar.YFH.7.76.1910291107150.5566@zhemvz.fhfr.qr |
|---|---|
| State | New |
| Headers | show |
| Series | [RFC] C++-style iterators for FOR_EACH_IMM_USE_STMT | expand |
On Tue, 2019-10-29 at 11:26 +0100, Richard Biener wrote: > While I converted other iterators requiring special BREAK_FROM_XYZ > a few years ago FOR_EACH_IMM_USE_STMT is remaining. I've pondered > a bit but cannot arrive at a "nice" solution here with just one > iterator as the macros happen to use. For reference, the macro use > is > > imm_use_iterator iter; > gimple *use_stmt; > FOR_EACH_IMM_USE_STMT (use_stmt, iter, name) > { > use_operand_p use_p; > FOR_EACH_IMM_USE_ON_STMT (use_p, iter) > ; > } > > which expands to (w/o macros) > > imm_use_iterator iter; > for (gimple *use_stmt = first_imm_use_stmt (&iter, name); > !end_imm_use_stmt_p (&iter); > use_stmt = nest_imm_use_stmt (&iter)) > for (use_operand_p use_p = first_imm_use_on_stmt (&iter); > !end_imm_use_on_stmt_p (&iter); > use_p = next_imm_use_on_stmt (&iter)) > ; > > and my foolish C++ attempt results in > > for (imm_use_stmt_iter it = SSAVAR; !it.end_p (); ++it) > for (imm_use_stmt_iter::use_on_stmt it2 = it; !it2.end_p (); > ++it2) > ; > > with *it providing the gimple * USE_STMT and *it2 the use_operand_p. > The complication here is to map the two-level iteration to "the C++ > way". > Are there any STL examples mimicing this? Of course with C++11 we > could > do > > for (imm_use_stmt_iter it = SSAVAR; !it.end_p (); ++it) > for (auto it2 = it.first_use_on_stmt (); !it2.end_p (); ++it2) > ; > > but that's not much nicer either. Is there a way to put it in such a way that the iterators follow standard concepts for iterators? It would increase chances of it becoming nicer by utilizing range based for loops. Cheers, Oleg
On Tue, 29 Oct 2019, Oleg Endo wrote: > On Tue, 2019-10-29 at 11:26 +0100, Richard Biener wrote: > > While I converted other iterators requiring special BREAK_FROM_XYZ > > a few years ago FOR_EACH_IMM_USE_STMT is remaining. I've pondered > > a bit but cannot arrive at a "nice" solution here with just one > > iterator as the macros happen to use. For reference, the macro use > > is > > > > imm_use_iterator iter; > > gimple *use_stmt; > > FOR_EACH_IMM_USE_STMT (use_stmt, iter, name) > > { > > use_operand_p use_p; > > FOR_EACH_IMM_USE_ON_STMT (use_p, iter) > > ; > > } > > > > which expands to (w/o macros) > > > > imm_use_iterator iter; > > for (gimple *use_stmt = first_imm_use_stmt (&iter, name); > > !end_imm_use_stmt_p (&iter); > > use_stmt = nest_imm_use_stmt (&iter)) > > for (use_operand_p use_p = first_imm_use_on_stmt (&iter); > > !end_imm_use_on_stmt_p (&iter); > > use_p = next_imm_use_on_stmt (&iter)) > > ; > > > > and my foolish C++ attempt results in > > > > for (imm_use_stmt_iter it = SSAVAR; !it.end_p (); ++it) > > for (imm_use_stmt_iter::use_on_stmt it2 = it; !it2.end_p (); > > ++it2) > > ; > > > > with *it providing the gimple * USE_STMT and *it2 the use_operand_p. > > The complication here is to map the two-level iteration to "the C++ > > way". > > Are there any STL examples mimicing this? Of course with C++11 we > > could > > do > > > > for (imm_use_stmt_iter it = SSAVAR; !it.end_p (); ++it) > > for (auto it2 = it.first_use_on_stmt (); !it2.end_p (); ++it2) > > ; > > > > but that's not much nicer either. > > Is there a way to put it in such a way that the iterators follow > standard concepts for iterators? It would increase chances of it > becoming nicer by utilizing range based for loops. Hmm, not sure - I'd like to write for (gimple *use_stmt : imm_stmt_uses (SSAVAR)) for (use_operand_p use_p : <need to refer to the iterator object from above>) ... I don't see how that's possible. It would need to be "awkward" like for (auto it : imm_stmt_uses (SSAVAR)) { gimple *use_stmt = *it; for (use_operand_p use_p : it) ... } so the first loops iteration object are the actual iterator and you'd have to do extra indirection to get at the actual stmt you iterated to. So I'd extend C++ (hah) to allow for (gimple *use_stmt : imm_stmt_uses (SSAVAR)) for (use_operand_p use_p : auto) ... where 'auto' magically selects the next iterator object in scope [that matches]. ;) But yeah, range-based for looks like a nice possibility for most of our IL iteration besides this special one. Guess nobody thought of "multi-level" iteration (and yes, we sometimes terminate the inner loop but continue the outer, so flattening the iteration isn't a solution here). Richard.
On Wed, 2019-10-30 at 10:27 +0100, Richard Biener wrote: > > Hmm, not sure - I'd like to write > > for (gimple *use_stmt : imm_stmt_uses (SSAVAR)) > for (use_operand_p use_p : <need to refer to the iterator object > from > above>) > ... > > I don't see how that's possible. It would need to be "awkward" like > > for (auto it : imm_stmt_uses (SSAVAR)) > { > gimple *use_stmt = *it; > for (use_operand_p use_p : it) > ... > } > > so the first loops iteration object are the actual iterator and you'd > have to do extra indirection to get at the actual stmt you iterated > to. > > So I'd extend C++ (hah) to allow > > for (gimple *use_stmt : imm_stmt_uses (SSAVAR)) > for (use_operand_p use_p : auto) > ... > > where 'auto' magically selects the next iterator object in scope > [that matches]. > > ;) Have you applied for a patent yet? :D How about this one? for (gimple* use_stmt : imm_stmt_uses (SSAVAR)) for (use_operand_p use_p : imm_uses_on_stmt (*use_stmt)) ... where helper function "imm_uses_on_stmt" returns a range object that offers a begin and end function and its own iterator type. Another concept that could be interesting are filter iterators. We used a simplistic re-implementation (c++03) to avoid dragging in boost when working on AMS https://github.com/erikvarga/gcc/blob/master/gcc/filter_iterator.h Example uses are https://github.com/erikvarga/gcc/blob/master/gcc/ams.h#L845 https://github.com/erikvarga/gcc/blob/master/gcc/ams.cc#L3715 I think there are also some places in RTL where filter iterators could be used, e.g. "iterate over all MEMs in an RTL" could be made to look something like that: for (auto&& i : filter_rtl (my_rtl_obj, MEM_P)) ... Anyway, maybe it can plant some ideas. Cheers, Oleg
On Sun, 3 Nov 2019, Oleg Endo wrote: > On Wed, 2019-10-30 at 10:27 +0100, Richard Biener wrote: > > > > Hmm, not sure - I'd like to write > > > > for (gimple *use_stmt : imm_stmt_uses (SSAVAR)) > > for (use_operand_p use_p : <need to refer to the iterator object > > from > > above>) > > ... > > > > I don't see how that's possible. It would need to be "awkward" like > > > > for (auto it : imm_stmt_uses (SSAVAR)) > > { > > gimple *use_stmt = *it; > > for (use_operand_p use_p : it) > > ... > > } > > > > so the first loops iteration object are the actual iterator and you'd > > have to do extra indirection to get at the actual stmt you iterated > > to. > > > > So I'd extend C++ (hah) to allow > > > > for (gimple *use_stmt : imm_stmt_uses (SSAVAR)) > > for (use_operand_p use_p : auto) > > ... > > > > where 'auto' magically selects the next iterator object in scope > > [that matches]. > > > > ;) > > Have you applied for a patent yet? :D > > How about this one? > > for (gimple* use_stmt : imm_stmt_uses (SSAVAR)) > for (use_operand_p use_p : imm_uses_on_stmt (*use_stmt)) > > ... where helper function "imm_uses_on_stmt" returns a range object > that offers a begin and end function and its own iterator type. The issue is that 'use_stmt' isn't enough to compute it. Internally we just use the same iterator object as for the outer loop but with range-based for the iterator object isn't accessible. So we'd need to wrap 'use_stmt' and the iterator object somehow. Closest would then be for (auto use_stmt : imm_stmt_uses (SSAVAR)) for (use_operand_p use_p : imm_uses_on_stmt (use_stmt)) ... where use_stmt auto-converts to gimple * and auto hides the ugliness. Not very satisfying. So what we are really doing is iterate over a sorted vector of use_operand_p sorted after USE_STMT (so uses on the same stmt come in succession). The inner loop iterates over all uses on a single USE_STMT and conveniently lets us skip to the next USE_STMT plus do some common update on a USE_STMT once we saw all uses on it. Thus.. for (auto_vec<use_operand_p> uses : imm_stmt_uses (SSAVAR)) for (use_operand_p : uses) ... that is, using a special iterator type for the outer loop iteration var might be conceptually OK (it's a sub-range of all immediate uses). So supposedly it's OK to use 'auto' to hide that subrange 'class' > Another concept that could be interesting are filter iterators. > > We used a simplistic re-implementation (c++03) to avoid dragging in > boost when working on AMS > https://github.com/erikvarga/gcc/blob/master/gcc/filter_iterator.h > > Example uses are > https://github.com/erikvarga/gcc/blob/master/gcc/ams.h#L845 > https://github.com/erikvarga/gcc/blob/master/gcc/ams.cc#L3715 > > > I think there are also some places in RTL where filter iterators could > be used, e.g. "iterate over all MEMs in an RTL" could be made to look > something like that: > > for (auto&& i : filter_rtl (my_rtl_obj, MEM_P)) > ... > > > Anyway, maybe it can plant some ideas. :) Thanks, Richard.
Index: gcc/ssa-iterators.h =================================================================== --- gcc/ssa-iterators.h (revision 277566) +++ gcc/ssa-iterators.h (working copy) @@ -1007,4 +1007,62 @@ delink_stmt_imm_use (gimple *stmt) delink_imm_use (use_p); } +/* Use this iterator to visit each stmt which has a use of SSAVAR. + for (imm_use_stmt_iter it = SSAVAR; !it.end_p (); ++it) + for (imm_use_stmt_iter::use_on_stmt it2 = it; !it2.end_p (); ++it2) + ; + + The macros above expand to the following and require the special + BREAK/RETURN_FROM_IMM_USE_STMT for breaking/returning. + + imm_use_iterator iter; + for (gimple *use_stmt = first_imm_use_stmt (&iter, name); + !end_imm_use_stmt_p (&iter); + use_stmt = nest_imm_use_stmt (&iter)) + for (use_operand_p use_p = first_imm_use_on_stmt (&iter); + !end_imm_use_on_stmt_p (&iter); + use_p = next_imm_use_on_stmt (&iter)) + ; + */ + + +class imm_use_stmt_iter +{ +public: + imm_use_stmt_iter (tree name) + { + m_stmt = first_imm_use_stmt (&m_iter, name); + } + + ~imm_use_stmt_iter () + { + delink_imm_use (&(m_iter.iter_node)); + } + + gimple *operator* () const { return m_stmt; } + imm_use_stmt_iter& operator++() { next_imm_use_stmt (&m_iter); return *this; } + bool end_p() { return m_iter.imm_use == m_iter.end_p; } + +class use_on_stmt +{ +public: + use_on_stmt (imm_use_stmt_iter &it) : m_iter (it.m_iter) + { + m_use_p = first_imm_use_on_stmt (&m_iter); + } + + use_operand_p operator*() { return m_use_p; } + use_on_stmt& operator++() { next_imm_use_on_stmt (&m_iter); return *this; } + bool end_p() { return m_iter.imm_use == &m_iter.iter_node; } + +private: + imm_use_iterator &m_iter; + use_operand_p m_use_p; +}; + +private: + imm_use_iterator m_iter; + gimple *m_stmt; +}; + #endif /* GCC_TREE_SSA_ITERATORS_H */ Index: gcc/tree-ssa-ccp.c =================================================================== --- gcc/tree-ssa-ccp.c (revision 277566) +++ gcc/tree-ssa-ccp.c (working copy) @@ -2931,8 +2931,9 @@ optimize_atomic_bit_test_and (gimple_stm if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs)) use_bool = false; - FOR_EACH_IMM_USE_STMT (g, iter, use_lhs) + for (imm_use_stmt_iter it = use_lhs; !it.end_p (); ++it) { + g = *it; enum tree_code code = ERROR_MARK; tree op0 = NULL_TREE, op1 = NULL_TREE; if (is_gimple_debug (g)) @@ -2969,16 +2970,15 @@ optimize_atomic_bit_test_and (gimple_stm && op0 == use_lhs && integer_zerop (op1)) { - use_operand_p use_p; int n = 0; - FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + for (imm_use_stmt_iter::use_on_stmt it2 = it; !it2.end_p (); ++it2) n++; if (n == 1) continue; } use_bool = false; - BREAK_FROM_IMM_USE_STMT (iter); + break; } tree new_lhs = make_ssa_name (TREE_TYPE (lhs));
While I converted other iterators requiring special BREAK_FROM_XYZ a few years ago FOR_EACH_IMM_USE_STMT is remaining. I've pondered a bit but cannot arrive at a "nice" solution here with just one iterator as the macros happen to use. For reference, the macro use is imm_use_iterator iter; gimple *use_stmt; FOR_EACH_IMM_USE_STMT (use_stmt, iter, name) { use_operand_p use_p; FOR_EACH_IMM_USE_ON_STMT (use_p, iter) ; } which expands to (w/o macros) imm_use_iterator iter; for (gimple *use_stmt = first_imm_use_stmt (&iter, name); !end_imm_use_stmt_p (&iter); use_stmt = nest_imm_use_stmt (&iter)) for (use_operand_p use_p = first_imm_use_on_stmt (&iter); !end_imm_use_on_stmt_p (&iter); use_p = next_imm_use_on_stmt (&iter)) ; and my foolish C++ attempt results in for (imm_use_stmt_iter it = SSAVAR; !it.end_p (); ++it) for (imm_use_stmt_iter::use_on_stmt it2 = it; !it2.end_p (); ++it2) ; with *it providing the gimple * USE_STMT and *it2 the use_operand_p. The complication here is to map the two-level iteration to "the C++ way". Are there any STL examples mimicing this? Of course with C++11 we could do for (imm_use_stmt_iter it = SSAVAR; !it.end_p (); ++it) for (auto it2 = it.first_use_on_stmt (); !it2.end_p (); ++it2) ; but that's not much nicer either. Doing away with operator++ might work, doing it.next_stmt () / it.next_use () and end_stmt () / end_use () but there's no (type) safety at using the wrong one in the wrong nest. The FOR_EACH_IMM_USE_STMT iterator is also quite special in that you can have at most one (safely) on the same chain and that it does work not on the order of the number of uses but on the order of the number of uses times the number of operands in the used stmts (so we should maybe rather get rid of it... for which Micha has patches as usual). For the fast imm use iterations and also the SSA operand iterators it's easy to make iterator classes which uses look nice enough. Richard.