2の累乗の積または商は、ビットシフトで容易に書換可能だが、 どっちが良いか云々とかいう定番な話があるが… 

unsigned int div2ui(unsigned int x) {
  return x / 2;
}
int div2si(int x) {
  return x / 2;
}
unsigned int shiftdiv2ui(unsigned int x) {
  return x >> 1;
}

なお、ここではC言語を前提としているため、 符号付き整数での右シフトは書いていない （負数を与えた時の動作が規格上実装依存であるため）。

The result of E1 >> E2 is E1 right-shifted E2 bit positions. ... If E1 has a signed type and a negative value, the resulting value is implementation-defined.

―― ISO/IEC 9899:201x (C11) Committee Draft §6.5.7 Bitwise shift operators

LLIR

ひとまず clang が吐き出す中間言語―― LLIR をみてみる。 

% clang -c -S -emit-llvm hoge.c
% 
; Function Attrs: nounwind uwtable
define i32 @div2ui(i32 %x) #0 {
  %1 = alloca i32, align 4
  store i32 %x, i32* %1, align 4
  %2 = load i32, i32* %1, align 4
  %3 = udiv i32 %2, 2
  ret i32 %3
}

; Function Attrs: nounwind uwtable
define i32 @div2si(i32 %x) #0 {
  %1 = alloca i32, align 4
  store i32 %x, i32* %1, align 4
  %2 = load i32, i32* %1, align 4
  %3 = sdiv i32 %2, 2
  ret i32 %3
}

; Function Attrs: nounwind uwtable
define i32 @shiftdiv2ui(i32 %x) #0 {
  %1 = alloca i32, align 4
  store i32 %x, i32* %1, align 4
  %2 = load i32, i32* %1, align 4
  %3 = lshr i32 %2, 1
  ret i32 %3
}

LLIR を見るまでもなく予見できたことではあるが、 それぞれ udiv, sdiv, lshr に展開されていて、 それ以外の差が存在しないことがわかる。 言い換えると、以降はこのみっつの命令がそれぞれどのように アセンブリコードに展開するかを比較検討すればよい。

最適化

clang は LLVM IR によりプロセッサに独立したレベルでの最適化を実施する。 これを行った結果どのように最適化されるか見てみよう。 

% clang -c -S -emit-llvm hoge.c -O
% 
; Function Attrs: nounwind optsize readnone uwtable
define i32 @div2ui(i32 %x) #0 {
  %1 = lshr i32 %x, 1
  ret i32 %1
}

; Function Attrs: nounwind optsize readnone uwtable
define i32 @div2si(i32 %x) #0 {
  %1 = sdiv i32 %x, 2
  ret i32 %1
}

; Function Attrs: nounwind optsize readnone uwtable
define i32 @shiftdiv2ui(i32 %x) #0 {
  %1 = lshr i32 %x, 1
  ret i32 %1
}

敢えて -O と最も最適化レベルが低いものを指定したが、 注目するべきは udiv となっていた箇所が lshr を使った形に書き換えられていることである。 すなわち x / 2 が x >> 1 に展開されているため、 @div2ui の中身が @shiftdiv2ui と完全に同一となっている。

アセンブリ

もう前節で結論は出てしまっているが、一応アセンブリコードも見ておこう。 なお、アーキテクチャは x86_64 である。 

% clang -c -S hoge.c -O
% 
	.globl	div2ui
	.type	div2ui,@function
div2ui:                                 # @div2ui
	.cfi_startproc
# BB#0:
	shrl	%edi
	movl	%edi, %eax
	retq
.Lfunc_end0:
	.size	div2ui, .Lfunc_end0-div2ui
	.cfi_endproc

	.globl	div2si
	.type	div2si,@function
div2si:                                 # @div2si
	.cfi_startproc
# BB#0:
	movl	%edi, %eax
	shrl	$31, %eax
	leal	(%rax,%rdi), %eax
	sarl	%eax
	retq
.Lfunc_end1:
	.size	div2si, .Lfunc_end1-div2si
	.cfi_endproc

	.globl	shiftdiv2ui
	.type	shiftdiv2ui,@function
shiftdiv2ui:                            # @shiftdiv2ui
	.cfi_startproc
# BB#0:
	shrl	%edi
	movl	%edi, %eax
	retq
.Lfunc_end2:
	.size	shiftdiv2ui, .Lfunc_end2-shiftdiv2ui
	.cfi_endproc

当然のことながら、div2ui: と shiftdiv2ui: とで 同一のアセンブリコードになっている。

それに比べて div2si: は複雑なコードとなっている。 高級言語風（Java 言語風）に書くと、>>を論理シフト、 >>>を論理右シフトとして、 (x + (x >>> 31)) >> 1となる。 これは負の数の考慮((x >>> 31) == 1)をしている ためである。

まとめ

  • 2の累乗の積または商は、ビットシフトを使わずにソースを書いてもコンパイラがきちんと変換してくれる
  • なのでこの話は、コンパイラが優秀な今日では、単なるコードの可読性等の問題
  • どちらかというとシフト演算を使用するときは、負数が入るか、論理シフトなのか算術シフトなのかの考慮が重要という内容の話題になってしまった。

なお LLVM IR を使えてわかりやすいため LLVM clang を使って説明したが、 この最適化自体は古典的な gcc でも適用されている。

余談

2の累乗でない場合も同様にシフト演算などを駆使して書き直すことが 考えられるが、これも同様にして解析することができる。 

unsigned int mul10ui(unsigned int x) {
  return x * 10;
}
; Function Attrs: nounwind readnone uwtable
define i32 @mul10ui(i32 %x) #0 {
  %1 = mul i32 %x, 10
  ret i32 %1
}
	.globl	mul10ui
	.align	16, 0x90
	.type	mul10ui,@function
mul10ui:                                # @mul10ui
	.cfi_startproc
# BB#0:
	addl	%edi, %edi
	leal	(%rdi,%rdi,4), %eax
	retq
.Lfunc_end0:
	.size	mul10ui, .Lfunc_end0-mul10ui
	.cfi_endproc

この場合、x * 10が(x + x) + (x + x) * 4と展開されていることがわかる。

参考文献