Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #2399

Re: The Indexed Instruction Problem Solved!

Message-ID <4E1552A7.2020305@SPAM.comp-arch.net> (permalink)
Date 2011-07-06 23:31 -0700
From "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net>
Organization comp-arch.net
Newsgroups comp.arch
Subject Re: The Indexed Instruction Problem Solved!
References <b4ebeaa5-411f-4ee8-8a18-71a49e4e0ed3@glegroupsg2000goo.googlegroups.com> <4E15524B.7090509@SPAM.comp-arch.net>

Show all headers | View raw

On 7/6/2011 11:29 PM, Andy "Krazy" Glew wrote:
> On 7/6/2011 2:12 PM, MitchAlsup wrote:

>
>> PDP-11, VAX, 68K family, National 32K family all got the
>> auto-increment and autodecrement wrong:: in that in many codes there
>> are as many postdecrements as there are predecrements. Favoring one
>> over the others is problematic (even though these directly support
>> stack structures.
>
> Except that pre-increment/decre more general form:
>
> mem_reference[ address_reg := address_reg+scale*index_reg + offset ]
>
> is a form of CSE (Common Subexpression Elimination), saving the result
> of the address calculatgion for future use,
> whereas post-incrementdecrement is not.


http://semipublic.comp-arch.net/wiki/Address_Generation_Writeback


= Hardware Motivation for Address Register Modifying Addressing Modes =

Apart from the software datastructure motivation,
there is a hardware motivation for addressing modes such as 
pre-increment or decrement.

In more generality - addressing modes that calculate an address, and 
then save the results of that calculation
in a register - typically one of the registers involved in the 
addressing mode.

Consider [[Mitch Alsup's Favorite Addressing Mode]],
the x86's [[Base+Scaled-Index+Offset]].

A succession of such instructions might look like:

;an [[RMW]]
   r1 := load( M[ rB+rO*4+offset1 ] )
   r1 := ... some calculation involving r1 ...
   store( M[ rB+rO*4+offset1 ] := r1 )

or

; nearby loads
   r1 := load( M[ rB+rO*4+offset1 ] )
   r2 := load( M[ rB+rO*4+offset2 ] )
   r3 := load( M[ rB+rO*4+offset3 ] )

Notice the possibility of [[CSE (Common Subexpression Elimination)]]:

For the [[RMW]] case, this is straightforward:

   rAtmp := [[lea]]( M[ rB+rO*4+offset1 ] )
   r1 := load( rAtmp ] )
   r1 := ... some calculation involving r1 ...
   store( M[ rAtmp ] := r1 )

Is this a win? It depends:
* in terms of performance, on a classic RISC, probably note: the extra 
instruction adds latency, probably costs a cycle.
* in terms of power, possibly

For the nearby load case, we could do:

   rAtmp := lea( M[ rB+rO*4 ] )
   r1 := load( M[ rAtmp+offset1 ] )
   r2 := load( M[ rAtmp*4+offset2 ] )
   r3 := load( M[ rAtmp*4+offset3 ] )

or

   rAtmp := lea( M[ rB+rO*4+offset1 ] )
   r1 := load( M[ rAtmp ] )
   r2 := load( M[ rAtmp*4+(offset2-offset1) ] )
   r3 := load( M[ rAtmp*4+(offset3-offset1) ] )

Is this a win? Again, it depends:
* probably not in performance
* possibly in terms of power.

<UL>
As an aside, let me note that if the base address rB+rO*4 is aligned,
then the subsequent addresses could use [[OR indexing]] rather than 
[[ADD indexing]].
Which may further save power.
At the cost of yet another piece of crap in the instruction set.
</UL>

To avoid conundrums like this - is it better to [[CSE]] the addressing 
mode or not?
- processors like the [[AMD 29K]]
abandoned addressing modes except for [[absolute addressing mode]] and 
[[register indirect addressing mode]]
- so to form any nomn-trivial address you had to save the results to a 
register, and thereby were
encouraged to CSE it whenever possible.

Generalized pre-increment/decrement is a less RISCy approach to this.
Instead of encouraging CSE via separate instructions,
it encourages CSE by making it "free" to save the result ofthe 
addressing mode calculation.

:Let's call this [[Address Generation Saving]], or, if it modifies a 
register used in the addressing mode, [[Address Register Modification]]:

In our examples:

;RMW
   rAtmp := [[lea]]( M[ rB+rO*4+offset1 ] )
   r1 := load( rAtmp := rB+rO*4+offset1 ] )
   r1 := ... some calculation involving r1 ...
   store( M[ rAtmp ] := r1 )

; nearby load
   r1 := load( M[ rAtnp :=rB+rO*4+offset1 ] )
   r2 := load( M[ rAtmp*4+(offset2-offset1) ] )
   r3 := load( M[ rAtmp*4+(offset3-offset1) ] )

Note  that the nearby case that changes the offsets is simpler than the 
nearby case that saves only part ofthe address calculation:

;Using C's comma expression:
   r1 := load( M[ (rAtmp := rB+rO*4, rAtmp+offset1) ] )
   r2 := load( M[ rAtmp*4+offset2 ] )
   r3 := load( M[ rAtmp*4+offset3 ] )

:: Again, [[OR indexing]] may benefit, for addressing mode 
[[(Base+Scaled-Index)}Offset]]

What is the probem with this?
* Writeback ports

Such an [[Address Generation Saving]] requires an extra writeback port, 
in addition to the result of an instruction like load.

For this reason, some instruction sets have proposed to NOT have 
[[address generation writeback]] for instructions that write other 
results, such as load,
but only to have [[address generation writeback]] for instructions that 
do not have a normal writeback, such as a store.

: Glew opinion: workable, minor benefit, but ugly.

Except that pre-increment/decre more general form:

Post-increment and decrement goes further, generalized in this way:
then the address calculation looks like

    { old := address_reg; address_reg := new_address; return old }

Not only does this require a writeback port for the updated address 
register,
but it also requires two paths from the AGU or RF to where the address 
is used
- one for the address, the other for the updated address_reg.

OVERALL OBSERVATION:  addressing modes begin the slippery slope to VLIW.

Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: The Indexed Instruction Problem Solved! MitchAlsup <MitchAlsup@aol.com> - 2011-07-06 14:12 -0700
  Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-06 15:48 -0700
  Re: The Indexed Instruction Problem Solved! EricP <ThatWouldBeTelling@thevillage.com> - 2011-07-06 20:36 -0400
  Re: The Indexed Instruction Problem Solved! "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-06 23:29 -0700
    Re: The Indexed Instruction Problem Solved! "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-06 23:31 -0700
      Re: The Indexed Instruction Problem Solved! "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-06 23:38 -0700
        Re: The Indexed Instruction Problem Solved! "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-06 23:39 -0700
          Re: The Indexed Instruction Problem Solved! timcaffrey@aol.com (Tim McCaffrey) - 2011-07-14 01:36 +0000
        Re: The Indexed Instruction Problem Solved! Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2011-07-07 08:12 -0700
        Re: The Indexed Instruction Problem Solved! EricP <ThatWouldBeTelling@thevillage.com> - 2011-07-07 12:24 -0400
          Re: The Indexed Instruction Problem Solved! John Levine <johnl@iecc.com> - 2011-07-08 01:29 +0000
            Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-07 18:53 -0700
              Re: The Indexed Instruction Problem Solved! John Levine <johnl@iecc.com> - 2011-07-08 02:17 +0000
            Re: The Indexed Instruction Problem Solved! EricP <ThatWouldBeTelling@thevillage.com> - 2011-07-09 13:15 -0400
              Re: The Indexed Instruction Problem Solved! John Levine <johnl@iecc.com> - 2011-07-09 18:37 +0000
                Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-09 11:53 -0700
                Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-09 11:55 -0700
              Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-09 11:49 -0700
              Re: The Indexed Instruction Problem Solved! Chris Jones <clj@panix.com> - 2011-07-09 16:21 -0400
        Re: The Indexed Instruction Problem Solved! Joe Chisolm <jchisolm6@earthlink.net> - 2011-07-07 13:19 -0500
          Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-07 12:11 -0700
          Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-07 12:13 -0700
            Re: The Indexed Instruction Problem Solved! jsavard@excxn.aNOSPAMb.cdn.invalid (John Savard) - 2011-07-07 19:32 +0000
      Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-07 04:09 -0700
  Re: The Indexed Instruction Problem Solved! Brett Davis <ggtgp@yahoo.com> - 2011-07-12 18:31 -0500
    Re: The Indexed Instruction Problem Solved! "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-13 22:31 -0700
    Re: The Indexed Instruction Problem Solved! mac <acolvin@efunct.com> - 2011-07-17 15:31 +0000
      Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-17 09:50 -0700
        Re: The Indexed Instruction Problem Solved! Andrew Reilly <areilly---@bigpond.net.au> - 2011-07-17 23:26 +0000
          Re: The Indexed Instruction Problem Solved! Brett Davis <ggtgp@yahoo.com> - 2011-07-17 19:52 -0500
          Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-17 18:22 -0700
            Re: The Indexed Instruction Problem Solved! "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-17 21:33 -0700
              Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-18 06:34 -0700
                Re: The Indexed Instruction Problem Solved! Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2011-07-18 09:22 -0700
              Re: The Indexed Instruction Problem Solved! nmm1@cam.ac.uk - 2011-07-18 14:13 +0100
                Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-18 07:27 -0700
                Re: The Indexed Instruction Problem Solved! nmm1@cam.ac.uk - 2011-07-18 16:22 +0100
                Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-18 09:56 -0700
                Re: The Indexed Instruction Problem Solved! nmm1@cam.ac.uk - 2011-07-18 17:43 +0100
                Re: The Indexed Instruction Problem Solved! Quadibloc <jsavard@ecn.ab.ca> - 2011-07-18 14:58 -0700
                Re: The Indexed Instruction Problem Solved! nmm1@cam.ac.uk - 2011-07-19 07:22 +0100

csiph-web