| Message ID | 0A4BF41A-322A-402F-9BC7-FBA50F926E54@comcast.net |
|---|---|
| State | New |
| Headers | show |
| Series | doc: update looping constructs | expand |
On 07/11/2018 06:20 PM, Paul Koning wrote: > This patch removes the obsolete documentation for decrement_and_branch_until_zero. It also adds detail to the description for doloop_end. In particular, it describes the required form of the conditional branch part of the pattern. > > Ok for trunk? > > paul > > ChangeLog: > > 2018-07-11 Paul Koning <ni1d@arrl.net> > > * doc/rtl.texi (REG_NONNEG): Remove decrement and branch until > zero reference, add doloop_end instead. > * doc/md.texi (decrement_and_branch_until_zero): Remove. > (Looping patterns): Remove decrement_and_branch_until_zero. Add > detail for doloop_end. OK. I wonder if we can eliminate REG_NONNEG at this point. I'm not sure if it's really being used anymore. I see a reference in the old m68k dbra pattern, but that pattern could well be dead at this point. jeff
> On Jul 12, 2018, at 12:55 PM, Jeff Law <law@redhat.com> wrote: > > On 07/11/2018 06:20 PM, Paul Koning wrote: >> This patch removes the obsolete documentation for decrement_and_branch_until_zero. It also adds detail to the description for doloop_end. In particular, it describes the required form of the conditional branch part of the pattern. >> >> Ok for trunk? >> >> paul >> >> ChangeLog: >> >> 2018-07-11 Paul Koning <ni1d@arrl.net> >> >> * doc/rtl.texi (REG_NONNEG): Remove decrement and branch until >> zero reference, add doloop_end instead. >> * doc/md.texi (decrement_and_branch_until_zero): Remove. >> (Looping patterns): Remove decrement_and_branch_until_zero. Add >> detail for doloop_end. > OK. I wonder if we can eliminate REG_NONNEG at this point. I'm not > sure if it's really being used anymore. I see a reference in the old > m68k dbra pattern, but that pattern could well be dead at this point. The original reasoning is that you'd need the note if you have a machine instruction that does a loop until negative, and you want to confirm that the input is a valid loop count (not negative -- otherwise you'd loop once rather than zero times). If you have a loop instruction that works this way, that still matters. If someone wants to convert m68000 to use doloop_end, for example. Or likewise for vax, which has an unnamed looping pattern that could be used but obviously isn't at the moment (since it's unnamed). Then again... does the code that generates this insn do the checking, i.e., avoid generating doloop_end unless it can confirm that the register is nonnegative? It doesn't seem to, at least not the code in "doloop_modify" that actually inserts the regnote. But how can that be valid? doloop_end by definition loops at least once. If you pass it a negative count, the loop is run once for "ge" comparisons, and MAXUINT + count times for insns that use the "ne" condition (i.e., all the current ones). So one would assume that's not possible, i.e., you couldn't come through there unless REG_NONNEG is guaranteed true. Currently the only doloop_end insns I can find all have the "ne" comparison so the regnote isn't generated. I'd like to leave this question separate from the doc cleanup. If we want to remove the note, that's easy enough, and the doc change would be pretty obvious as well. So is this patch OK to commit? paul
On 07/12/2018 11:17 AM, Paul Koning wrote: > > >> On Jul 12, 2018, at 12:55 PM, Jeff Law <law@redhat.com> wrote: >> >> On 07/11/2018 06:20 PM, Paul Koning wrote: >>> This patch removes the obsolete documentation for >>> decrement_and_branch_until_zero. It also adds detail to the >>> description for doloop_end. In particular, it describes the >>> required form of the conditional branch part of the pattern. >>> >>> Ok for trunk? >>> >>> paul >>> >>> ChangeLog: >>> >>> 2018-07-11 Paul Koning <ni1d@arrl.net> >>> >>> * doc/rtl.texi (REG_NONNEG): Remove decrement and branch until >>> zero reference, add doloop_end instead. * doc/md.texi >>> (decrement_and_branch_until_zero): Remove. (Looping patterns): >>> Remove decrement_and_branch_until_zero. Add detail for >>> doloop_end. >> OK. I wonder if we can eliminate REG_NONNEG at this point. I'm >> not sure if it's really being used anymore. I see a reference in >> the old m68k dbra pattern, but that pattern could well be dead at >> this point. > > The original reasoning is that you'd need the note if you have a > machine instruction that does a loop until negative, and you want to > confirm that the input is a valid loop count (not negative -- > otherwise you'd loop once rather than zero times). If you have a > loop instruction that works this way, that still matters. If someone > wants to convert m68000 to use doloop_end, for example. Or likewise > for vax, which has an unnamed looping pattern that could be used but > obviously isn't at the moment (since it's unnamed). Right. And that is now dbra works on the m68k. However I've got little confidence we're generating that instruction anymore. Though I guess it's easy enough to check since I can bootstrap m68k with qemu :-) It's always struck me as lame that we had to rely on the magic note and in the world of doloop.c we ought to be able to express things much more clearly. > > Then again... does the code that generates this insn do the checking, > i.e., avoid generating doloop_end unless it can confirm that the > register is nonnegative? It doesn't seem to, at least not the code > in "doloop_modify" that actually inserts the regnote. But how can > that be valid? doloop_end by definition loops at least once. If you > pass it a negative count, the loop is run once for "ge" comparisons, > and MAXUINT + count times for insns that use the "ne" condition > (i.e., all the current ones). So one would assume that's not > possible, i.e., you couldn't come through there unless REG_NONNEG is > guaranteed true. > > Currently the only doloop_end insns I can find all have the "ne" > comparison so the regnote isn't generated. I'd like to leave this > question separate from the doc cleanup. If we want to remove the > note, that's easy enough, and the doc change would be pretty obvious > as well. > > So is this patch OK to commit? SOrry I wasn't clear. I'm perfectly content to look at killing REG_NONNEG independent of the doc cleanup. The doc patch is fine to commit now. jeff
> On Jul 12, 2018, at 1:42 PM, Jeff Law <law@redhat.com> wrote: > > On 07/12/2018 11:17 AM, Paul Koning wrote: >> >> >>> On Jul 12, 2018, at 12:55 PM, Jeff Law <law@redhat.com> wrote: >>> >>> On 07/11/2018 06:20 PM, Paul Koning wrote: >>>> This patch removes the obsolete documentation for >>>> decrement_and_branch_until_zero. It also adds detail to the >>>> description for doloop_end. In particular, it describes the >>>> required form of the conditional branch part of the pattern. >>>> >>>> Ok for trunk? >>>> >>>> paul >>>> >>>> ChangeLog: >>>> >>>> 2018-07-11 Paul Koning <ni1d@arrl.net> >>>> >>>> * doc/rtl.texi (REG_NONNEG): Remove decrement and branch until >>>> zero reference, add doloop_end instead. * doc/md.texi >>>> (decrement_and_branch_until_zero): Remove. (Looping patterns): >>>> Remove decrement_and_branch_until_zero. Add detail for >>>> doloop_end. >>> OK. I wonder if we can eliminate REG_NONNEG at this point. I'm >>> not sure if it's really being used anymore. I see a reference in >>> the old m68k dbra pattern, but that pattern could well be dead at >>> this point. >> >> The original reasoning is that you'd need the note if you have a >> machine instruction that does a loop until negative, and you want to >> confirm that the input is a valid loop count (not negative -- >> otherwise you'd loop once rather than zero times). If you have a >> loop instruction that works this way, that still matters. If someone >> wants to convert m68000 to use doloop_end, for example. Or likewise >> for vax, which has an unnamed looping pattern that could be used but >> obviously isn't at the moment (since it's unnamed). > Right. And that is now dbra works on the m68k. However I've got little > confidence we're generating that instruction anymore. Though I guess > it's easy enough to check since I can bootstrap m68k with qemu :-) > > It's always struck me as lame that we had to rely on the magic note and > in the world of doloop.c we ought to be able to express things much more > clearly. Agreed. I'm pretty sure dbra is no longer working. It certainly didn't do anything when I tried to add it in pdp11, and when I asked about it on the gcc list I was told that it was removed a decade ago, or thereabouts. The new technique works fine. The only drawback is the "register can't be the induction variable" limitation, which makes sense if special registers are used but would be nice not to have on machines where the register used is a general register. >> Then again... does the code that generates this insn do the checking, >> i.e., avoid generating doloop_end unless it can confirm that the >> register is nonnegative? It doesn't seem to, at least not the code >> in "doloop_modify" that actually inserts the regnote. But how can >> that be valid? doloop_end by definition loops at least once. If you >> pass it a negative count, the loop is run once for "ge" comparisons, >> and MAXUINT + count times for insns that use the "ne" condition >> (i.e., all the current ones). So one would assume that's not >> possible, i.e., you couldn't come through there unless REG_NONNEG is >> guaranteed true. >> >> Currently the only doloop_end insns I can find all have the "ne" >> comparison so the regnote isn't generated. I'd like to leave this >> question separate from the doc cleanup. If we want to remove the >> note, that's easy enough, and the doc change would be pretty obvious >> as well. >> >> So is this patch OK to commit? > SOrry I wasn't clear. I'm perfectly content to look at killing > REG_NONNEG independent of the doc cleanup. > > The doc patch is fine to commit now. Thanks, done. paul
Index: doc/md.texi =================================================================== --- doc/md.texi (revision 262562) +++ doc/md.texi (working copy) @@ -6681,17 +6681,6 @@ second operand, but you should incorporate it in t that the jump optimizer will not delete the table as unreachable code. -@cindex @code{decrement_and_branch_until_zero} instruction pattern -@item @samp{decrement_and_branch_until_zero} -Conditional branch instruction that decrements a register and -jumps if the register is nonzero. Operand 0 is the register to -decrement and test; operand 1 is the label to jump to if the -register is nonzero. @xref{Looping Patterns}. - -This optional instruction pattern is only used by the combiner, -typically for loops reversed by the loop optimizer when strength -reduction is enabled. - @cindex @code{doloop_end} instruction pattern @item @samp{doloop_end} Conditional branch instruction that decrements a register and @@ -7515,67 +7504,12 @@ iterations. This avoids the need for fetching and @samp{dbra}-like instruction and avoids pipeline stalls associated with the jump. -GCC has three special named patterns to support low overhead looping. -They are @samp{decrement_and_branch_until_zero}, @samp{doloop_begin}, -and @samp{doloop_end}. The first pattern, -@samp{decrement_and_branch_until_zero}, is not emitted during RTL -generation but may be emitted during the instruction combination phase. -This requires the assistance of the loop optimizer, using information -collected during strength reduction, to reverse a loop to count down to -zero. Some targets also require the loop optimizer to add a -@code{REG_NONNEG} note to indicate that the iteration count is always -positive. This is needed if the target performs a signed loop -termination test. For example, the 68000 uses a pattern similar to the -following for its @code{dbra} instruction: +GCC has two special named patterns to support low overhead looping. +They are @samp{doloop_begin} and @samp{doloop_end}. These are emitted +by the loop optimizer for certain well-behaved loops with a finite +number of loop iterations using information collected during strength +reduction. -@smallexample -@group -(define_insn "decrement_and_branch_until_zero" - [(set (pc) - (if_then_else - (ge (plus:SI (match_operand:SI 0 "general_operand" "+d*am") - (const_int -1)) - (const_int 0)) - (label_ref (match_operand 1 "" "")) - (pc))) - (set (match_dup 0) - (plus:SI (match_dup 0) - (const_int -1)))] - "find_reg_note (insn, REG_NONNEG, 0)" - "@dots{}") -@end group -@end smallexample - -Note that since the insn is both a jump insn and has an output, it must -deal with its own reloads, hence the `m' constraints. Also note that -since this insn is generated by the instruction combination phase -combining two sequential insns together into an implicit parallel insn, -the iteration counter needs to be biased by the same amount as the -decrement operation, in this case @minus{}1. Note that the following similar -pattern will not be matched by the combiner. - -@smallexample -@group -(define_insn "decrement_and_branch_until_zero" - [(set (pc) - (if_then_else - (ge (match_operand:SI 0 "general_operand" "+d*am") - (const_int 1)) - (label_ref (match_operand 1 "" "")) - (pc))) - (set (match_dup 0) - (plus:SI (match_dup 0) - (const_int -1)))] - "find_reg_note (insn, REG_NONNEG, 0)" - "@dots{}") -@end group -@end smallexample - -The other two special looping patterns, @samp{doloop_begin} and -@samp{doloop_end}, are emitted by the loop optimizer for certain -well-behaved loops with a finite number of loop iterations using -information collected during strength reduction. - The @samp{doloop_end} pattern describes the actual looping instruction (or the implicit looping operation) and the @samp{doloop_begin} pattern is an optional companion pattern that can be used for initialization @@ -7594,15 +7528,65 @@ desired special iteration counter register was not machine dependent reorg pass could emit a traditional compare and jump instruction pair. -The essential difference between the -@samp{decrement_and_branch_until_zero} and the @samp{doloop_end} -patterns is that the loop optimizer allocates an additional pseudo -register for the latter as an iteration counter. This pseudo register -cannot be used within the loop (i.e., general induction variables cannot -be derived from it), however, in many cases the loop induction variable -may become redundant and removed by the flow pass. +For the @samp{doloop_end} pattern, the loop optimizer allocates an +additional pseudo register as an iteration counter. This pseudo +register cannot be used within the loop (i.e., general induction +variables cannot be derived from it), however, in many cases the loop +induction variable may become redundant and removed by the flow pass. +The @samp{doloop_end} pattern must have a specific structure to be +handled correctly by GCC. The example below is taken (slightly +simplified) from the PDP-11 target: +@smallexample +@group +(define_insn "doloop_end" + [(set (pc) + (if_then_else + (ne (match_operand:HI 0 "nonimmediate_operand" "+r,!m") + (const_int 1)) + (label_ref (match_operand 1 "" "")) + (pc))) + (set (match_dup 0) + (plus:HI (match_dup 0) + (const_int -1)))] + "" + + @{ + if (which_alternative == 0) + return "sob %0,%l1"; + + /* emulate sob */ + output_asm_insn ("dec %0", operands); + return "bne %l1"; + @}) +@end group +@end smallexample + +The first part of the pattern describes the branch condition. GCC +supports three cases for the way the target machine handles the loop +counter: +@itemize @bullet +@item Loop terminates when the loop register decrements to zero. This +is represented by a @code{ne} comparison of the register (its old value) +with constant 1 (as in the example above). +@item Loop terminates when the loop register decrements to @minus{}1. +This is represented by a @code{ne} comparison of the register with +constant zero. +@item Loop terminates when the loop register decrements to a negative +value. This is represented by a @code{ge} comparison of the register +with constant zero. For this case, GCC will attach a @code{REG_NONNEG} +note to the @code{doloop_end} insn if it can determine that the register +will be non-negative. +@end itemize + +Since the @code{doloop_end} insn is a jump insn that also has an output, +the reload pass does not handle the output operand. Therefore, the +constraint must allow for that operand to be in memory rather than a +register. In the example shown above, that is handled by using a loop +instruction sequence that can handle memory operands when the memory +alternative appears. + @end ifset @ifset INTERNALS @node Insn Canonicalizations Index: doc/rtl.texi =================================================================== --- doc/rtl.texi (revision 262560) +++ doc/rtl.texi (working copy) @@ -4151,11 +4151,11 @@ This means it appears in a @code{post_inc}, @code{ @findex REG_NONNEG @item REG_NONNEG The register @var{op} is known to have a nonnegative value when this -insn is reached. This is used so that decrement and branch until zero -instructions, such as the m68k dbra, can be matched. +insn is reached. This is used by special looping instructions +that terminate when the register goes negative. -The @code{REG_NONNEG} note is added to insns only if the machine -description has a @samp{decrement_and_branch_until_zero} pattern. +The @code{REG_NONNEG} note is added only to @samp{doloop_end} +insns, if its pattern uses a @code{ge} condition. @findex REG_LABEL_OPERAND @item REG_LABEL_OPERAND