🚀 go-pugleaf

In article <4i805f$47d@solutions.solon.com>,
Dan T. Abell <dabell@quark.umd.edu> wrote:
>This may sound like a dumb question, but can someone tell me how C  
>compilers do pointer arithmetic?  In particular, consider an integer array
>	p[0], p[1], ... , p[n]
>whose entry p[k] we might access using *(p + k).  I imagine the typical  
>compiler would multiply the size of an integer by k, add the result to p,  
>and then report the integer located at that address.  Now for my question:  
>Do most compilers use plain ol' multiplication or do they use bit-shift  
>operators.  Also, does the answer depend on the type of the array p?

The answer is, as so often, "it depends".
What the compiler will generate for an int array acces depends on

- the sizeof int, which might well be 3, 5, or 42. Pointer values
  probably wont be calculated with bit shifts here.
  For other types, as you seemed to be ware of, it depends even more :-)
- What the instruction set of the machine supports.
  There may be machines that have instructions to compute
  base+(index * somesize) [I bet there are!]
- How smart the compiler is. Nobody prevents an implementor from
  adding repeatedly 1 to the pointer until it points to the
  desired object. It might not use the efficient instructions mentioned
  above, even when they are available.

If you want to be sure how your compiler does it, trying the -S option
might give an assembler source of your C code. I once investigated it with
gcc on an i486 machine with sizeof int = 4. It does use bit shifts
to compute adresses in int arrays. You don't need to be an assembler
guru to see what's going on in a small program.

To put it in a nutshell:
  You only can be sure by looking at the compiler output.

Bye, Jens

-- 
SIGSIG -- signature too long (core dumped)

schweikh@itosun.ito.uni-stuttgart.de (Jens Schweikhardt) writes:

>- the sizeof int, which might well be 3, 5, or 42.

It's allowed to be, but Real machines hardly use word lengths that are
not either powers of two or quite small (i.e. not exceeding, say, 3
chars), do they?

>- What the instruction set of the machine supports.
>  There may be machines that have instructions to compute
>  base+(index * somesize) [I bet there are!]

i386 and followers have these addressing modes available when running
32-bit and somesize is (I think) either 2, 4 or 8. I'm not sure
whether they're to be preferred over explicit shifts and additions on
later members of the family...

-- 

Henning Makholm - math and CS student - University of Copenhagen
makholm@diku.dk - http://www.diku.dk/students/makholm - fido 2:235/224.92

Jens Schweikhardt (schweikh@itosun.ito.uni-stuttgart.de) wrote:
: In article <4i805f$47d@solutions.solon.com>,
: Dan T. Abell <dabell@quark.umd.edu> wrote:
[snip]
: >Do most compilers use plain ol' multiplication or do they use bit-shift  
: >operators.  Also, does the answer depend on the type of the array p?

: The answer is, as so often, "it depends".
: What the compiler will generate for an int array acces depends on

[Among other things...]

: - What the instruction set of the machine supports.
:   There may be machines that have instructions to compute
:   base+(index * somesize) [I bet there are!]

Intel 80386 and up have such a mode for 32-bit addressing.
Valid values of somesize are 1,2,4,8.

16-bit addressing is still stuck with bit shifting.

(According to the references I have.)

: If you want to be sure how your compiler does it, trying the -S option
: might give an assembler source of your C code. I once investigated it with
: gcc on an i486 machine with sizeof int = 4. It does use bit shifts
: to compute adresses in int arrays. You don't need to be an assembler
: guru to see what's going on in a small program.

I tried "result=int_array[index];" with gcc 2.7.2 (and 2.5.8) on an i486 
and got:

	movl index,%eax
	movl int_array(,%eax,4),%edx
	movl %edx,result

Which looks like at least the current gcc uses scaled indexes.

: To put it in a nutshell:
:   You only can be sure by looking at the compiler output.

: Bye, Jens

: -- 
: SIGSIG -- signature too long (core dumped)

--
Nathan Green			(ngreen@plains.nodak.edu)
GCS d? s: a21.3>21.4 C+++ UV P>+ L++>+++ E W N++ o+>++ K+ 
w---(--) M- V PS PE Y t+ 5 X R tv-(--) b++>+++ DI++>+++ D+ 
G+>++++ e(*)>+ h!>++ !r !y+ (Version 3.1)

Dan T. Abell wrote:
> 
> This may sound like a dumb question, but can someone tell me how C
> compilers do pointer arithmetic?  In particular, consider an integer array
>         p[0], p[1], ... , p[n]
> whose entry p[k] we might access using *(p + k).  I imagine the typical
> compiler would multiply the size of an integer by k, add the result to p,
> and then report the integer located at that address.  Now for my question:
> Do most compilers use plain ol' multiplication or do they use bit-shift
> operators.  Also, does the answer depend on the type of the array p?
> 

It is implementation dependant, but I'd guess that most compilers use multiplication since 
it's easier to implement. Shifts would be faster, but in many cases you would have to use 
a few shifts and additions to accomplish the same task. For instance, if the size of the 
element is 80 bytes, you would have to do shifts by 10 and 8 and add the results together, 
which is harder to implement in a compiler.

Later,
 AriL
-- 
All my opinions are mine and mine alone.

In article <4ijp8i$1cf@solutions.solon.com>,
Ari Lukumies  <aril@cmt.lpr.mail.carel.fi> wrote:

[snip]

[edited to get lines under 72 chars]
>It is implementation dependant, but I'd guess that most compilers
> use multiplication since 
>it's easier to implement. Shifts would be faster, but in many cases
> you would have to use 
>a few shifts and additions to accomplish the same task. For
> instance, if the size of the 
>element is 80 bytes, you would have to do shifts by 10 and 8 and
> add the results together, 
>which is harder to implement in a compiler.

Well, that wouldn't work  :-)  For 80, you'd shift by 6 and 4 and
add the results.  (80 == 64 + 16).

It's not that much harder to implement this in a compiler.  I used
one on a 68000-based system that did all multiplies by constants
in this manner, both for indexing and for expressions, and used
the MUL instruction if it would be faster.  So, i*0x555 would use
the MUL instruction, but i*0x7ff would use shifts (multiply by 0x800
with a shift, then subtract the original).  It "knew" how expensive
the instructions were, and used whatever it thought best.

(That compiler was dumb in other things though; it insisted on
generating code to multiply by 1, for example, though not for
indexing char arrays.)

Cheers,
Stan.
--
Stan Ryckman  (stanr@tiac.net)
  (Apologies for non-responses or late responses to some posts;
  .newsrc was trashed and I'm trying to get it back to where it was.)

Stan Ryckman wrote:
> 
> 
> Well, that wouldn't work  :-)  For 80, you'd shift by 6 and 4 and
> add the results.  (80 == 64 + 16).
> 

Yes, you're right. I was half asleep when I wrote that you'd shift by 10 and 
8... Well, I'll try to pay more attention. Another thought about shifting just 
emerged. At one time I was writing a program that did something like this:

	short	n = 10, m;
	m = n << 8;
	...

That worked in a debug version, but when compiled using optimization, the 
compiler (MSC 7 for NT) produced incorrect code:

	MOV	AX,[n]
	MOV	AH,AL
	...

It decided MOV AH,AL would be faster than

	MOV	CL,8
	SHL	AX,CL

but it left out XOR AL,AL (ie. resetting the low byte). To get around this I 
used a variable:

	short	c = 8, n = 10, m;
	m = n << c;

Surprising enough, the compiler didn't optimize use of c out, but produced 
correct code (MOV CL,8 and SHL AX,CL).

> It's not that much harder to implement this in a compiler.  I used
> one on a 68000-based system that did all multiplies by constants
> in this manner, both for indexing and for expressions, and used
> the MUL instruction if it would be faster.  So, i*0x555 would use
> the MUL instruction, but i*0x7ff would use shifts (multiply by 0x800
> with a shift, then subtract the original).  It "knew" how expensive
> the instructions were, and used whatever it thought best.
> 

That's a clever compiler. I haven't come across one yet in the Intel world, 
though. It seems that the compiler writers here spend more time to add features 
that make your programs bulkier (like OOP) rather than make better optimizers. 
The optimizers have become a _little_ better nowadays, however. Maybe one day...

Later,
 AriL
-- 
All my opinions are mine and mine alone.

In article <4ip9k0$sqs@solutions.solon.com> Ari Lukumies
<aril@cmt.lpr.mail.carel.fi> writes:
[given m,n of type short]
>	m = n << 8;
>... when compiled using optimization, the compiler (MSC 7 for NT)
>produced incorrect code:
>
>	MOV	AX,[n]
>	MOV	AH,AL
>... it left out XOR AL,AL ...

(Actually, I would expect to see something along the lines of `xor
al,al; mov ah,[n]' for a case like this -- note that my optimization
depends on byte order.)  I would find a bug this serious quite
troubling, and perhaps look for another compiler.

In article <4imabr$duc@solutions.solon.com> Stan Ryckman wrote:
>>It's not that much harder to implement [multiply by shifting] in a
>>compiler.

This is true; also, if it is done correctly, index-multiplication by
shifting falls naturally out of multiplication by shifting (simply
turn the indexing into multiplication before doing the multiplication
optimizations).

>That's a clever compiler. I haven't come across one yet in the Intel world,

Gcc 2.7.2 generates this (perhaps surprising) code for `i*15':

	movl 8(%ebp),%eax	# i [supplied as a parameter, hence 8(frame)]
	leal (%eax,%eax,2),%eax # i <- i + i*2 = i*3
	leal (%eax,%eax,4),%eax # i <- i + i*4 = i*5
				# since 3*5=15, final i <- original i * 15

For i*31 we get:

	movl 8(%ebp),%eax
	sall $5,%eax
	subl 8(%ebp),%eax

which is just `(i << 5) - i'.

GCC also optimizes division by constants, particularly in the case
when the division is known to have no remainder (e.g., when producing
an index from pointer subtraction).

To see how it works, pick up the gcc source and look at `synth_mult'
in expmed.c (touching on another thread, I note that this makes
gratuitous use of `alloca'; the two `struct algorithm' objects
could simply be local variables inside synth_mult).  Note also that
there are three variants using synth_mult (`basic', `negate', and
`add'; see expand_mult for details).
-- 
In-Real-Life: Chris Torek, Berkeley Software Design Inc
El Cerrito, CA	Domain:	torek@bsdi.com	+1 510 234 3167

Hi Ari & Chris!

Chris Torek wrote:

> In article <4ip9k0$sqs@solutions.solon.com> Ari Lukumies
> <aril@cmt.lpr.mail.carel.fi> writes:
 [...]
> In article <4imabr$duc@solutions.solon.com> Stan Ryckman wrote:
> >>It's not that much harder to implement [multiply by shifting] in a
> >>compiler.
> 
> This is true; also, if it is done correctly, index-multiplication by
> shifting falls naturally out of multiplication by shifting (simply
> turn the indexing into multiplication before doing the multiplication
> optimizations).
> 
> >That's a clever compiler. I haven't come across one yet in the Intel > >world,

Maybe you could take a look at Watcom's C/C++ compiler. I've used
it for a while now, and it is really the best optimizing compiler I've
seen for Intel platforms so far. It doesn't have all those fancy
development tools, but it sure generates fast and compact code (much 
better than MS's).


   Bart