RFA: MN10300: Add support for SETLB and Lcc instructions

Hi Richard, Hi Jeff, Hi Alex,

  Below is a patch to add support for the SETLB and Lcc low overhead
  loop instructions to the MN10300 backend.

  The patch makes use of a machine reorg pass to find loops that can use
  these instructions.  I did try to use the doloop_begin and doloop_end
  patterns as well, but I just could not get them to work.  (Either
  because they caused reload failures when the patterns were too
  complex, or else code generation problems because the Lcc instruction
  were being duplicated).

  I plan to add support for the FLcc instruction in a later patch.

  Tested with an mn10300-elf toolchain with no regressions.

  OK to apply ?

Cheers
  Nick

gcc/ChangeLog
2011-02-25  Nick Clifton  <nickc@redhat.com>

	* config/mn10300/mn10300.c (cc_flags_for_mode): Add support for
        CC_LCCmode.
        (mn10300_insert_setlb_lcc): New function: Insert a SETLB
	instruction into the code and replace a conditional branch
	instruction with a Lcc instruction.
        (mn10300_scan_for_setlb): Scan insns for places where SETLB and
	Lcc can be used.
        (mn10300_reorg): Invoke mn10300_scan_for_setlb_lcc if allowed.
        (TARGET_DEFAULT_FLAGS): Enable SETLB transformations by default.
        * config/mn10300/mn10300.md (UNSPEC_SETLB): New constant.
        (cmpsi): Allow the creation of a gen_cmpsi function.
        (setlb): New pattern.
        (Lcc): New pattern.
        * config/mn10300/mn10300-modes.def (CC_LCC): New mode.
        * config/mn10300/predicates.md (int_mode_flags): Do not allow
	CC_LCCmode.
        * config/mn10300/mn10300.opt (msetlb): New command line option.
        * config/mn10300/mn10300.h (TARGET_CPU_CPP_BUILTINS): Add
	definition of __SETLB__ or __NO_SETLB__.
	* doc/invoke.texi: Document -mno-setlb.

On 02/25/2011 05:03 AM, Nick Clifton wrote:
>> +/* A special mode used to distinguish the Lcc branch instruction
> +   from the Bcc branch instruction.  */
> +CC_MODE (CC_LCC);

Why not just use an unspec on the lcc insn.  I think you want to 
preserve the existing CCmode, so that we DTRT with modes that do
not have the overflow bit.

> +  /* What we're doing here is looking for a conditional branch which
> +     branches backwards without crossing any non-debug labels.  I.e.
> +     the loop has to enter from the top.  */

Ug.  Surely we can re-use the existing loop detection code to find the
inner-most loops.  The existence of normal branches within the loop 
ought not make any sort of a difference.

You'll have to re-establish the CFG, which just got broken down, but
that shouldn't be any different from several other targets.  Then use
flow_loops_find and the rest of the bits in cfgloop.h.


r~

Hi Richard,

   Thanks for the review.  Attached is a revised patch which addresses 
the issues that you raised:

>>> +/* A special mode used to distinguish the Lcc branch instruction
>> +   from the Bcc branch instruction.  */
>> +CC_MODE (CC_LCC);
>
> Why not just use an unspec on the lcc insn.

I should have done.  The CC_LCC mode was a holdover from when I was 
trying to get the doloop patterns to work.  The doloop pattern 
recognizer does not accept UNSPECs, so I had to use a unique CC mode 
instead.  The revised patch uses an UNSPEC.

>> +  /* What we're doing here is looking for a conditional branch which
>> +     branches backwards without crossing any non-debug labels.  I.e.
>> +     the loop has to enter from the top.  */
>
> Ug.  Surely we can re-use the existing loop detection code to find the
> inner-most loops.

We can, but it is a lot more complicated than just performing a simple 
scan.  Still I have tried my best to follow up on this.  One thing that 
does worry me however is that I encountered a segmentation fault whilst 
trying to free the loop data.  (See a comment in the patch for more 
details).  I tried to follow the example of other passes that use the 
loop information, but I must have gotten something wrong.  Any pointers 
on how to fix this are greatly appreciated.

Cheers
   Nick

gcc/ChangeLog
2011-03-08  Nick Clifton  <nickc@redhat.com>

	* config/mn10300/mn10300.c: Include cfgloop.h.
	(DUMP): New macro.
	(mn10300_insert_setlb_lcc): New function.  Inserts a SETLB and a
	Lcc or a FLcc insn into the instruction stream.
	(mn10300_block_contains_call): New function.  Returns true if the
	given basic block contains a CALL insn.
	(mn10300_loop_contains_call_insn): New function.  Returns true if
	the given loop contains a CALL insn.
	(mn10300_scan_for_setlb_lcc): New function.  Finds opportunities
	to use the SETLB and Lcc or FLcc insns.
	(mn10300_reorg): Invoke mn10300_scan_for_setlb_lcc.
	(TARGET_FLAGS): Add MASK_ALLOW_SETLB.
	* config/mn10300/mn10300.opt (msetlb): New option.  Used to
	disable the SETLB optimization.
	* config/mn10300/mn10300.h (TARGET_CPU_CPP_BUILTINS): Add
	__SETLB__ or __NO_SETLB__.
	* config/mn10300/mn10300.md (UNSPEC_SETLB): New constant.
	(cmpsi): Make visible.
	(setlb): New pattern.
	(Lcc): New pattern.
	(FLcc): New pattern.
	* doc/invoke.texi: Document -mno-setlb option.

> +  /* If the comparison has not already been split out of the branch
> +     then do so now.  */
> +  if (REGNO (cmp_reg) != CC_REG)
> +    {
> +      rtx cmp;
> +
> +      cmp = emit_insn_before (gen_cmpsi (cmp_reg, XEXP (comparison, 1)), branch);
> +
> +      DUMP ("Extracted comparison from branch:", cmp);
> +    }

This should never ever fire.  These should have been split already,
at least with optimization, on which this pass is dependant.  Just
assert here, if you like.

> +mn10300_block_contains_call (struct basic_block_def * block)

  basic_block block

> +  for (insn = block->il.rtl->head_;
> +       insn != NULL_RTX;
> +       insn = NEXT_INSN (insn))
> +    {
> +      if (CALL_P (insn))
> +	return true;
> +
> +      if (insn == block->il.rtl->end_)
> +	break;
> +    }

  FOR_BB_INSNS (block, insn)
    if (CALL_P (insn))
      return true;

> +  df_analyze ();
> +  if (flow_loops_find (& loops) > 0)
> +    {
> +      unsigned int i;
> +      loop_p loop;
> +
> +      FOR_EACH_VEC_ELT (loop_p, loops.larray, i, loop)

You need compute_bb_for_insn, and to set up current_loops.
Then you can use 

  FOR_EACH_LOOP(liter, loop, LI_ONLY_INNERMOST)

instead of iterating over the array by hand.  This will eliminate
at least the fake loop and non-innermost loop check that you do
by hand.  Of course, current_loops must be cleared at the end.

> +	  else if (loop->header != loop->latch)
> +	    reason = "it is not a simple do-while loop";

Why?  A loop with multiple blocks should be fine with Lcc.
I do see that you've got loop->header and loop->latch backward
further below; perhaps that was your reason for this?

> +	      rtx branch = loop->header->il.rtl->end_;

  BB_END (loop->latch)

> +	      if (single_set (branch) == NULL_RTX
> +		  || GET_CODE (SET_SRC (single_set (branch))) != IF_THEN_ELSE)

  !any_condjump_p (branch)

> +		  label = loop->latch->il.rtl->head_;

  BB_HEAD (loop->header)

> +		  /* If necessary, extract the label from the branch insn.  */
> +		  if (! LABEL_P (label))

This should never ever fire -- how else can the loop have been created?
Again, you can just assert here.

> +      /* FIXME: Calling flow_loops_free() appears to be the correct thing to do,
> +	 but it results in a seg-fault when building regex.c in the target libiberty
> +	 library.  I have no idea why; so I have disabled the call for now.  */
> +      /* flow_loops_free (& loops); */

I'm having a look into this.  It's definitely non-obvious...


r~

Hi Richard,

   Thanks for the patch review.  Sorry for not responding earlier, but 
some other work got in the way.

   I have attached a revised patch which addresses all of the points you 
raised except one:

>> +	  else if (loop->header != loop->latch
>> +	    reason = "it is not a simple do-while loop";
>
> Why?  A loop with multiple blocks should be fine with Lcc.

   The problem I found here was that I did not know how to find all of 
the test-and-loop-back insns if the loop spanned multiple blocks.  The 
revised patch includes a comment saying that loops spanning multiple 
blocks could be supported, but I would like to leave that for a future 
patch rather than trying to get it all working now.

Cheers
   Nick

On 05/03/2011 05:13 AM, Nick Clifton wrote:
> The problem I found here was that I did not know how to find all of
> the test-and-loop-back insns if the loop spanned multiple blocks.
> The revised patch includes a comment saying that loops spanning
> multiple blocks could be supported, but I would like to leave that
> for a future patch rather than trying to get it all working now.

The patch is ok.

As for the finding the branches, I'm pretty sure that 

  /* Head of the cyclic list of the exits of the loop.  */
  struct loop_exit *exits;

means what it says and contains all of the edges that exit
the block.  But doing that in a separate patch is fine.


r~