ビットシフトと割り算はどっちが良いか、とはいうけれど
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.
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
と展開されていることがわかる。
参考文献
- 村井和夫「試しながらステップ・バイ・ステップ!Cortex-A時代の新コンパイラLLVM/Clangのしくみと使い方 (特集 高性能でフリー! 新時代コンパイラ入門 : 第2部 新時代コンパイラLLVMを定番ボードBeagleBone Blackで試す)」, Interface 2015年3月号 pp43-52
- N1570, the final draft of ISO/IEC 9899:201x (C1X), 12 April 2011