PATCH: Pad short functions for Atom

Hi,

On Atom, the function return address isn't ready until 4 cycles after
function is entered. This patch assumes that the most of instructions
in short functions take 1 cycle and pads short functions to 4 cycles,
from function extrance to where the return address is consumed, with
nops which takes half cycle.  OK for trunk?

Thanks.


H.J.
---
gcc/

2010-09-13  H.J. Lu  <hongjiu.lu@intel.com>

	* config/i386/i386.c (block_info): New.
	(BLOCK_INFO): Likewise.
	(ix86_count_insn): Likewise.
	(initial_ix86_tune_features): Add X86_TUNE_PAD_SHORT_FUNCTION.
	(ix86_code_end): Pad with 8 NOPs for TARGET_PAD_SHORT_FUNCTION.
	(ix86_pad_short_function): New.
	(ix86_reorg): Support TARGET_PAD_SHORT_FUNCTION.

	* config/i386/i386.h (ix86_tune_indices): Add
	X86_TUNE_PAD_SHORT_FUNCTION.
	(TARGET_PAD_SHORT_FUNCTION): New.

	* config/i386/i386.md (UNSPEC_RETURN_NOPS): New.
	(return_nops): Likewise.

gcc/testsuite/

2010-09-13  H.J. Lu  <hongjiu.lu@intel.com>

	* gcc.target/i386/pad-1.c: New.
	* gcc.target/i386/pad-2.c: Likewise.
	* gcc.target/i386/pad-3.c: Likewise.
	* gcc.target/i386/pad-4.c: Likewise.
	* gcc.target/i386/pad-5a.c: Likewise.
	* gcc.target/i386/pad-5b.c: Likewise.
	* gcc.target/i386/pad-6a.c: Likewise.
	* gcc.target/i386/pad-6b.c: Likewise.
	* gcc.target/i386/pad-7.c: Likewise.
	* gcc.target/i386/pad-8.c: Likewise.
	* gcc.target/i386/pad-9.c: Likewise.

> Hi,
> 
> On Atom, the function return address isn't ready until 4 cycles after
> function is entered. This patch assumes that the most of instructions
> in short functions take 1 cycle and pads short functions to 4 cycles,
> from function extrance to where the return address is consumed, with
> nops which takes half cycle.  OK for trunk?
> +/* Count the minimum number of instructions in code path in BB.  
> +   Return 4 if the number of instructions >= 4.  */
> +
> +static int 
> +ix86_count_insn (basic_block bb)
> +{
> +  edge e;
> +  edge_iterator ei;
> +  rtx insn;
> +  int insn_count;
> +  int pred_insn_count;
> +
> +  /* Check if we have seen this block.  The minimum number of
> +     instructions is stored in value.  */
> +  if (BLOCK_INFO (bb)->done)
> +    return BLOCK_INFO (bb)->value;

I don't think you need saving.  Exit block has as predecestor all return blocks
and we don't have duplicated edges in CFG.
> +
> +  BLOCK_INFO (bb)->done = true;
> +
> +  /* Count number of instructions in this block.  Return 4 if the number
> +     of instructions >= 4.  */
> +  insn_count = 0;

Hmm, if NOP counts as half of instructions, it is really cycle count rather than
insn count, right?  Isn't our DFA API simple to use enough so we can actually
use it to get cycle count of BB?
> +
> +  /* This block has less than 4 instructions.  Count all predecessor
> +     edges of this block.  */
> +  pred_insn_count = 0;
> +  FOR_EACH_EDGE (e, ei, bb->preds)
> +    {
> +      int count = ix86_count_insn (e->src);
> +      if (pred_insn_count == 0)
> +	pred_insn_count = count;
> +      else if (count < pred_insn_count)
> +	pred_insn_count = count;
> +    }
> +
> +  BLOCK_INFO (bb)->value = pred_insn_count + insn_count;
> +  return pred_insn_count + insn_count;

Ahh, you are actually trying to compute hot path through the function leading to the return
statement.  I think you really want to use profile info here.

Otherwise the patch seems resonable...

Honza

On Mon, Sep 13, 2010 at 8:03 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Hi,
>>
>> On Atom, the function return address isn't ready until 4 cycles after
>> function is entered. This patch assumes that the most of instructions
>> in short functions take 1 cycle and pads short functions to 4 cycles,
>> from function extrance to where the return address is consumed, with
>> nops which takes half cycle.  OK for trunk?
>> +/* Count the minimum number of instructions in code path in BB.
>> +   Return 4 if the number of instructions >= 4.  */
>> +
>> +static int
>> +ix86_count_insn (basic_block bb)
>> +{
>> +  edge e;
>> +  edge_iterator ei;
>> +  rtx insn;
>> +  int insn_count;
>> +  int pred_insn_count;
>> +
>> +  /* Check if we have seen this block.  The minimum number of
>> +     instructions is stored in value.  */
>> +  if (BLOCK_INFO (bb)->done)
>> +    return BLOCK_INFO (bb)->value;
>
> I don't think you need saving.  Exit block has as predecestor all return blocks
> and we don't have duplicated edges in CFG.

Without it, I ran into loops which turn this into infinite recursive call.
Is there a way to terminate loop?

>> +
>> +  BLOCK_INFO (bb)->done = true;
>> +
>> +  /* Count number of instructions in this block.  Return 4 if the number
>> +     of instructions >= 4.  */
>> +  insn_count = 0;
>
> Hmm, if NOP counts as half of instructions, it is really cycle count rather than
> insn count, right?  Isn't our DFA API simple to use enough so we can actually
> use it to get cycle count of BB?

I want cycle counts. I looked at DFA.  I couldn't find an easy way to
use it.  Are
there any examples?

>> +
>> +  /* This block has less than 4 instructions.  Count all predecessor
>> +     edges of this block.  */
>> +  pred_insn_count = 0;
>> +  FOR_EACH_EDGE (e, ei, bb->preds)
>> +    {
>> +      int count = ix86_count_insn (e->src);
>> +      if (pred_insn_count == 0)
>> +     pred_insn_count = count;
>> +      else if (count < pred_insn_count)
>> +     pred_insn_count = count;
>> +    }
>> +
>> +  BLOCK_INFO (bb)->value = pred_insn_count + insn_count;
>> +  return pred_insn_count + insn_count;
>
> Ahh, you are actually trying to compute hot path through the function leading to the return
> statement.  I think you really want to use profile info here.

That is a good idea. Are there any examples I can look at?

> Otherwise the patch seems resonable...
>

Thanks.

> > I don't think you need saving.  Exit block has as predecestor all return blocks
> > and we don't have duplicated edges in CFG.
> 
> Without it, I ran into loops which turn this into infinite recursive call.
> Is there a way to terminate loop?

Yes, I only later noticed you are walking backwards the CFG.
> 
> >> +
> >> +  BLOCK_INFO (bb)->done = true;
> >> +
> >> +  /* Count number of instructions in this block.  Return 4 if the number
> >> +     of instructions >= 4.  */
> >> +  insn_count = 0;
> >
> > Hmm, if NOP counts as half of instructions, it is really cycle count rather than
> > insn count, right?  Isn't our DFA API simple to use enough so we can actually
> > use it to get cycle count of BB?
> 
> I want cycle counts. I looked at DFA.  I couldn't find an easy way to
> use it.  Are
> there any examples?

I guess you will need to look into scheduler.  If I remember correctly DFA provides basically
capabilities to answer question "can I insert this insn in current cycle" and "advance cycle"
so combining those should give you cycle count.
> 
> >> +
> >> +  /* This block has less than 4 instructions.  Count all predecessor
> >> +     edges of this block.  */
> >> +  pred_insn_count = 0;
> >> +  FOR_EACH_EDGE (e, ei, bb->preds)
> >> +    {
> >> +      int count = ix86_count_insn (e->src);
> >> +      if (pred_insn_count == 0)
> >> +     pred_insn_count = count;
> >> +      else if (count < pred_insn_count)
> >> +     pred_insn_count = count;
> >> +    }
> >> +
> >> +  BLOCK_INFO (bb)->value = pred_insn_count + insn_count;
> >> +  return pred_insn_count + insn_count;
> >
> > Ahh, you are actually trying to compute hot path through the function leading to the return
> > statement.  I think you really want to use profile info here.
> 
> That is a good idea. Are there any examples I can look at?

I would just try to compute in what probability program arrives to the return BB when
return value is not ready yet.  Basically you get recursive function:

walk_bb (BB, time, probability)

where time is amount of cycles you took to reach to BB, probability is probability that you
get there.

walk_bb will bail out if probability is too small so we don't care or time
is over 4 cycles.
When this does not happen, it will walk the BB, compute time it takes and if it has return BB
and time is too small it could decide to insert nops.  if it reach conditional at the end it
recursively calls itself on both branches with combining the probability it has with probability
of the edge...

and then call walk_bb (ENTRY_BLOCK_PTR, 0, REG_BR_PROB_BASE)...

Honza
> 
> > Otherwise the patch seems resonable...
> >
> 
> Thanks.
> 
> -- 
> H.J.

On Mon, Sep 13, 2010 at 7:54 AM, H.J. Lu <hongjiu.lu@intel.com> wrote:
> Hi,
>
> On Atom, the function return address isn't ready until 4 cycles after
> function is entered. This patch assumes that the most of instructions
> in short functions take 1 cycle and pads short functions to 4 cycles,
> from function extrance to where the return address is consumed, with
> nops which takes half cycle.  OK for trunk?


Maybe test -Os -march=atom (and add a testcase) as I think this
"optimization" should be turned off if we are optimizing for size.

Thanks,
Andrew Pinski

> On Mon, Sep 13, 2010 at 7:54 AM, H.J. Lu <hongjiu.lu@intel.com> wrote:
> > Hi,
> >
> > On Atom, the function return address isn't ready until 4 cycles after
> > function is entered. This patch assumes that the most of instructions
> > in short functions take 1 cycle and pads short functions to 4 cycles,
> > from function extrance to where the return address is consumed, with
> > nops which takes half cycle.  OK for trunk?
> 
> 
> Maybe test -Os -march=atom (and add a testcase) as I think this
> "optimization" should be turned off if we are optimizing for size.

We pobably should not pad returns in optimize_bb_for_size blocks...

Honza
> 
> Thanks,
> Andrew Pinski

On 09/13/2010 07:54 AM, H.J. Lu wrote:
> On Atom, the function return address isn't ready until 4 cycles after
> function is entered. This patch assumes that the most of instructions
> in short functions take 1 cycle and pads short functions to 4 cycles,
> from function extrance to where the return address is consumed, with
> nops which takes half cycle.  OK for trunk?

The Atom doesn't just stall for the remaining cycles,
but aborts the insn and restarts it later?

Because, frankly, with the description you've given,
I have so say "so what", since there's nothing else
useful that we can do.


r~

On Tue, Sep 14, 2010 at 1:53 PM, Richard Henderson <rth@redhat.com> wrote:
> On 09/13/2010 07:54 AM, H.J. Lu wrote:
>> On Atom, the function return address isn't ready until 4 cycles after
>> function is entered. This patch assumes that the most of instructions
>> in short functions take 1 cycle and pads short functions to 4 cycles,
>> from function extrance to where the return address is consumed, with
>> nops which takes half cycle.  OK for trunk?
>
> The Atom doesn't just stall for the remaining cycles,
> but aborts the insn and restarts it later?
>
> Because, frankly, with the description you've given,
> I have so say "so what", since there's nothing else
> useful that we can do.

The machine does more than just stall. It replays, which
ends up costing more than just "waiting".

On Tue, Sep 14, 2010 at 2:20 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
> The machine does more than just stall. It replays, which
> ends up costing more than just "waiting".

I think the biggest question is that people who care about atom will
they be compiling with -Os (which should disable this optimization by
default)?  If that is true, should we be worrying about this
optimization in general?

-- Pinski

On Tue, Sep 14, 2010 at 2:22 PM, Andrew Pinski <pinskia@gmail.com> wrote:
> On Tue, Sep 14, 2010 at 2:20 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
>> The machine does more than just stall. It replays, which
>> ends up costing more than just "waiting".
>
> I think the biggest question is that people who care about atom will
> they be compiling with -Os (which should disable this optimization by

Not necessarily.

> default)?  If that is true, should we be worrying about this
> optimization in general?
>

One DSO only has one PIC thunk.. I think adding 8bytes
is worth it even for -Os.

On 09/13/2010 07:54 AM, H.J. Lu wrote:
>        xops[1] = gen_rtx_MEM (Pmode, stack_pointer_rtx);
> +      /* Pad stack IP move with 4 instructions.  2 NOPs count as 1
> +         instruction.  */
> +      if (TARGET_PAD_SHORT_FUNCTION)
> +	output_asm_insn (".byte 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, "
> +			 "0x90, 0x90", xops);

What's wrong with "nop" instead of ".byte"?
Similarly for "return_nops".

> +/* Pad short funtion to 4 instructions.   */
> +
> +static void
> +ix86_pad_short_function (void)
> +{
> +  edge e;
> +  edge_iterator ei;
> +
> +  /* Set up block info for each basic block.  */
> +  alloc_aux_for_blocks (sizeof (struct block_info_def));
> +
> +  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
> +    {
> +      rtx ret = BB_END (e->src);
> +      if (JUMP_P (ret) && GET_CODE (PATTERN (ret)) == RETURN)
> +	{
> +	  int insn_count = ix86_count_insn (e->src);
> +
> +	  /* Pad short function.  */
> +	  if (insn_count < 4)
> +	    {
> +	      emit_jump_insn_before (gen_return_nops (GEN_INT (insn_count)),
> +				     ret);
> +	      delete_insn (ret);
> +	    }
> +	}
> +    }

Surely this is overkill.  Why not assume that any function
with more than a single basic block is not short?  You can
then significantly simplify these two functions.

I'll also say that this will break the as-yet unsubmitted
Windows x64 SEH code.  In order to reduce the size of the
unwind information, the form of epilogues is tightly
constrained.  See

  http://msdn.microsoft.com/en-US/library/tawsa7cb%28v=VS.80%29.aspx

In order to work with SEH, you'll need to put the nops
before the epilogue, and not attach them to the return pattern.


r~

On Wed, Sep 15, 2010 at 3:37 PM, Richard Henderson <rth@redhat.com> wrote:
> On 09/13/2010 07:54 AM, H.J. Lu wrote:
>>        xops[1] = gen_rtx_MEM (Pmode, stack_pointer_rtx);
>> +      /* Pad stack IP move with 4 instructions.  2 NOPs count as 1
>> +         instruction.  */
>> +      if (TARGET_PAD_SHORT_FUNCTION)
>> +     output_asm_insn (".byte 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, "
>> +                      "0x90, 0x90", xops);
>
> What's wrong with "nop" instead of ".byte"?
> Similarly for "return_nops".

I will change to nop.

>> +/* Pad short funtion to 4 instructions.   */
>> +
>> +static void
>> +ix86_pad_short_function (void)
>> +{
>> +  edge e;
>> +  edge_iterator ei;
>> +
>> +  /* Set up block info for each basic block.  */
>> +  alloc_aux_for_blocks (sizeof (struct block_info_def));
>> +
>> +  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
>> +    {
>> +      rtx ret = BB_END (e->src);
>> +      if (JUMP_P (ret) && GET_CODE (PATTERN (ret)) == RETURN)
>> +     {
>> +       int insn_count = ix86_count_insn (e->src);
>> +
>> +       /* Pad short function.  */
>> +       if (insn_count < 4)
>> +         {
>> +           emit_jump_insn_before (gen_return_nops (GEN_INT (insn_count)),
>> +                                  ret);
>> +           delete_insn (ret);
>> +         }
>> +     }
>> +    }
>
> Surely this is overkill.  Why not assume that any function
> with more than a single basic block is not short?  You can
> then significantly simplify these two functions.

I will check it out.

> I'll also say that this will break the as-yet unsubmitted
> Windows x64 SEH code.  In order to reduce the size of the
> unwind information, the form of epilogues is tightly
> constrained.  See
>
>  http://msdn.microsoft.com/en-US/library/tawsa7cb%28v=VS.80%29.aspx
>
> In order to work with SEH, you'll need to put the nops
> before the epilogue, and not attach them to the return pattern.
>
>

I will investigate it.

Thanks.