Skip to contentSkip to conversation

Make shr to divide by power of 2

PATCH In review Sergey Senozhatsky 3 participants 6 messages Aug 6, 2009 – Aug 9, 2009

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Make shr to divide by power of 2

Hello Andrew,

drivers/video/console/bitblit.c
'shr' is used to divide by 8 except 'static void bit_putcs'.

Of course, compiler supposed to do something like

	add    $0x7,%eax
	shr    $0x3,%eax

instead of div. Should we rely on this?
============

Make an arithmetic right shift to divide by power of 2.

---

drivers/video/console/bitblit.c +1 -1
index 69864b1..b816151 100644
@@ -144,7 +144,7 @@ static void bit_putcs(struct vc_data *vc, struct fb_info *info,
 		      int fg, int bg)
 {
 	struct fb_image image;
-	u32 width = (vc->vc_font.width + 7)/8;
+	u32 width = (vc->vc_font.width + 7) >> 3;
 	u32 cellsize = width * vc->vc_font.height;
 	u32 maxcnt = info->pixmap.size/cellsize;
 	u32 scan_align = info->pixmap.scan_align - 1;
#1 lore raw
Quoted 5 lines · Sergey Senozhatsky

Of course, compiler supposed to do something like

	add    $0x7,%eax
	shr    $0x3,%eax

instead of div. Should we rely on this?

Yes. We should rely on this.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#2 lore raw
Quoted 9 lines · Andi Kleen
Quoted 5 lines · Sergey Senozhatsky

Of course, compiler supposed to do something like

	add    $0x7,%eax
	shr    $0x3,%eax

instead of div. Should we rely on this?

Yes. We should rely on this.

grep -cR '>> 3' bitblit.c
5

and only 1 '/8'.

Sergey

#3 lore raw
In reply to Andi Kleen
Quoted 7 lines · Andi Kleen
Quoted 4 lines · Sergey Senozhatsky

Of course, compiler supposed to do something like

	add    $0x7,%eax
	shr    $0x3,%eax

instead of div. Should we rely on this?

Yes. We should rely on this.

It may depend on the selected CPU type that gcc is optimizing for - I believe that on some P4s the shift may actually be slower than the divide..

#4 lore raw
Quoted 11 lines · Robert Hancock
Quoted 7 lines · Andi Kleen
Quoted 4 lines · Sergey Senozhatsky

Of course, compiler supposed to do something like

	add    $0x7,%eax
	shr    $0x3,%eax

instead of div. Should we rely on this?

Yes. We should rely on this.

It may depend on the selected CPU type that gcc is optimizing for - I believe that on some P4s the shift may actually be slower than the divide..

DIV should be always slower than a SHIFT.

But it has nothing really to do with the CPU. The point is that the compiler always selects a suitable one by itself. Rewriting x / 2 to x >> 1 is one of the easiest exercises in compiler optimizations.

The only case when the compiler cannot do this easily by itself is when the dividend is not a constant.

That said -Os sometimes screws us up on this, but it's still not worth doing this change manually.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#5 lore raw
Quoted 8 lines · Robert Hancock

Actually, the Intel Architecture Optimization Reference Manual doesn't say divide may be faster, but it does say that "On processors based on Intel NetBurst microarchitecture, latencies of some instructions are relatively significant (including shifts, rotates, integer multiplies, and moves from memory with sign extension)." and that "The SHIFT and ROTATE instructions have a longer latency on processor with a CPUID signature corresponding to family 15 and model encoding of 0, 1, or 2. The latency of a sequence of adds will be shorter for left shifts of three or less."

Intel Architecture Optimization Reference Manual does say about latency:

Table C-13a. General Purpose Instructions
Instruction Latency Throughput
IDIV | 11-21 13-23 17-41 22 | 5-13 5-14 12-36 22
SAL/SAR/SHL/SHR | 1 1 1 | 0.33 0.33 0.33

For example,
Table 12-2. Intel® Atom™ Microarchitecture Instructions Latency Data
Instruction Latency Throughput
IDIV r/m8; IDIV r/m16; | 33;42; | 32;41;56;196
IDIV r/m32; IDIV r/m64; | 57;197 |

			|		|
ROL; ROR; SAL; 		| 1		| 1
SAR; SHL; SHR		|		|

*SHLD/SHRD |4;2-11 |3;1-10

Quoted 9 lines · Andi Kleen

DIV should be always slower than a SHIFT.

But it has nothing really to do with the CPU. The point is that the compiler always selects a suitable one by itself. Rewriting x / 2 to x >> 1 is one of the easiest exercises in compiler optimizations.

The only case when the compiler cannot do this easily by itself is when the dividend is not a constant.

        int width = (vc->vc_font.width + 7) >> 3;
Quoted 3 lines

That said -Os sometimes screws us up on this, but it's still not worth doing this change manually.

My point is that it should 'look the same'.
I mean there are 5

        int width = (vc->vc_font.width + 7) >> 3;

*not exactly this one, but vc->vc_font.width (+ 7)? >> 3

and _only_ one

        int width = (vc->vc_font.width + 7) / 8;

P.S.
Sorry, hit "reply", not "reply to all".

Sergey