ARMの命令セットの条件指定について (2)

昨日の続き。

mcommit.hatenadiary.com

ARMの命令では最上位4ビットで条件指定ができることがわかりましたがAL(無条件実行)以外の使い方がよく分かりませんでした。

命令の実行条件を指定するというのはイメージ的には

r0 = 1 if flag == true
r0 += 2 

のようにRubyの後置ifのようなおしゃれなイメージがあります。
何が嬉しいかというとこの書き方だとelseを書かなくてよいのでソースコードレベルでのステップ数は削減できます。
分岐の結果に関わらず後続の処理を必ず行う場合はこの条件指定を使ったほうがよさそうに見えます。

さて、ARMの命令として具体的にどのように条件指定をするかを調べてみたところ、アセンブラだと命令の後ろに条件のサフィックスを指定するようです。

例えば、

MOV r0, #1

であれば

CMP       r0, #1
MOVEQ r0, #1

とすると、事前の比較命令の結果に応じてMOVを実行するか判断してくれるようです。
MOVEQ以外にもADDEQとかあります。

もちろん条件指定もEQ以外にあります。

条件指定実行のメリット

1. 分岐命令を使うより命令数が少なくできる場合がある→サイズの節約
2. 条件指定実行だと、条件が成立していない場合は後続の命令が実行されるので、ジャンプ先アドレスを別途取得する必要がない。

といったところでしょうか。

条件指定実行のデメリット

よく分かりません・・・なんとなく使える状況では使って行ったほうがよい気がしますが。

実際

実験のために、raspberrypiでMOVEQを使ってくれそうなコードを書いてビルドしてみました。

int add(int oneOriginFlg, int a, int b)
{
   int ret = 0;
   if (oneOriginFlg == 1)
   {
      ret = 1;
   }
   ret += a;
   ret += b;
   return ret;
}

コンパイルの結果、残念ながら普通にコンパイルしただけでは、MOVEQを使うコードははいてくれませんでした。

gcc -Osとか O1とかつけるとMOVEQをつかってくれていたのでgccだと必要に迫られないとこういった条件指定実行のコードははいてくれないようです。
gccは多くのアーキテクチャをサポートしているので当然といえば当然かも知れません。

参考書籍

今回も調査にはARMで学ぶアセンブリ言語入門を参考にしました。

ARMで学ぶ アセンブリ言語入門

条件実行についてもP62-P63で説明されています。ARMのアセンブラを学習するのには重宝しています。

ARMの命令セットの条件指定について

ARMの命令セット(v7)について調べていたので備忘録のためメモを残しておきます。

■ARMv7のマニュアル

https://www.macs.hw.ac.uk/~hwloidl/Courses/F28HS/Docu/DDI0406C_C_arm_architecture_reference_manual.pdf

とりあえず命令セットのところを読んでみる。
参考用に簡単な加算と条件分岐を含むコードを書いてみる。

■サンプルコード hoge.c

int add(void)
{
    int a = 0;
    a += 0x10;
    if ( a == 0x10) {
      return a;
    }
    return 0;
}

$ arm-linux-gnueabi-gcc -g -c hoge.c

$ arm-linux-gnueabi-objdump -S hoge.o

■サンプルアセンブラコード

00000000 <add>:
int add(void)
{
   0:   e52db004        push    {fp}            ; (str fp, [sp, #-4]!)
   4:   e28db000        add     fp, sp, #0
   8:   e24dd00c        sub     sp, sp, #12
    int a = 0;
   c:   e3a03000        mov     r3, #0
  10:   e50b3008        str     r3, [fp, #-8]
    a += 0x10;
  14:   e51b3008        ldr     r3, [fp, #-8]
  18:   e2833010        add     r3, r3, #16
  1c:   e50b3008        str     r3, [fp, #-8]
    if ( a == 0x10) {
  20:   e51b3008        ldr     r3, [fp, #-8]
  24:   e3530010        cmp     r3, #16
  28:   1a000001        bne     34 <add+0x34>
      return a;
  2c:   e51b3008        ldr     r3, [fp, #-8]
  30:   ea000000        b       38 <add+0x38>
    }
    return 0;
  34:   e3a03000        mov     r3, #0
}
  38:   e1a00003        mov     r0, r3
  3c:   e24bd000        sub     sp, fp, #0
  40:   e49db004        pop     {fp}            ; (ldr fp, [sp], #4)
  44:   e12fff1e        bx      lr

条件指定について

ARMの命令のうち、最上位の4bitは条件指定のビット(cond)として割り当てられているそうです。

逆アセンブラを見るとこのcondビットはほぼほぼ1111(0xE..)になっていることが多い。
ここまでは過去の経験として知っていたのですが、このcondビットの意味がいまいちよく分かっていませんでした。※そういえばpine64のダンプとか読んだときも少し調べていました。

mcommit.hatenadiary.com

結論ですが、ARMでは(ほとんどの)命令に対して実行するかしないかの条件をつけることができるそうです。これだけだとピンとこないのですが、条件と言うのは要するにフラグレジスタの各種フラグビット(ゼロフラグとかキャリーフラグ...etc)に応じて実行するかしないかを命令に対して指定できるという意味になります。

実際に、上記のhoge.oの逆アセンブルですとbneだとcondは1になっています。
条件指定実行ができるということは
addとかmov命令をフラグレジスタの値を元に実行するかしないか切り替えれるというような意味だと思います。*1

というわけで実際にどの命令で条件指定が可能なのか、適当に試してみたいと思います。

が、今日眠いので続きは明日にします。

[2018/06/06 追記]

条件実行について更に調べてみた続きです。

mcommit.hatenadiary.com

*1:なんかrubyの後置記法みたいでおしゃれ

スタックの状態を可視化するWebツールを書いてみた。

Webページ上でStackの状態を可視化するコードを書いてみました。

stack viewer

Stackを可視化するツール自体に目新しい感じはしないのですが、Web上でこういうツールってありそうでなかったので作ってみました。
かなりざっくりしたものですが、よかったら使ってください。

個人的なニーズとして普段Cとかアセンブラをガチでデバッグするとき、紙のノートにスタックの状態を書きながらデバッグしたりしているのですが、ノートだと動的にイメージし続けるのが辛いのであると便利な気がします。*1

課題

現状だと、pushするたびにページが下に伸びていくのでなんかしっくりこない気もするので、時間があるときに改善したいと思います。*2

その他

ついでにずっとほったらかしにしていたホームページも書き換えてみました。シンプルにindex.htmlだけにしてみました。

mcommit toppage

*1:GDBを使うとスタックとかレジスタの状態を見ることはできますが、いかんせんCUIなのが地味で直感的じゃない気がしていました

*2:もちろんpushはスタックトップに積まれて、popはスタックトップから取り出されていくのでご安心ください

構文解析ハンズオン 関西出張版に参加させて頂きました

lang-impl.connpass.com

参加させて頂きました。

目次

良かった点

久しぶりにパーサ系のコード書きました。普段パーサ系のコードを書くことはあまりありませんが、時々必要に迫られるときがあるので定石やいろいろなテクニックや流行とか知っておくというのは大切な気がします。ハンズオンでいろいろ実際に書いてみるというのは自分にはぴったりでした。

あと、普段は再帰を使ってコードを書く機会が少ないので再帰を使うちょうどよい練習になりました。

苦労した点

Javaのコード書くのが久しぶりすぎてやばかった・・・
事前にJavaでハンズオンをするので環境を用意しておいてくださいと告知があったのですが、環境は構築していましたが、心と体の準備が追い付いていませんでした。
「Javaはもう何年も書いていないけどまぁなんとかなるだろう」と思っていたら、コード書くのと実行するのに戸惑いました。やはり事前に復習をしておけばよかったように思います。

構文解析について思ったこと

パーサを書く場合に気を付けないといけないポイントとして、パースをする際の入出力と内部状態をしっかりと把握しておく必要があると思います。
入出力と状態は、

入力

• 文字列

出力

• 解析結果(AST)
• 解析の成否(正常に解析できたのか、解析できなかったのか)

パーサ内部で保持する状態

• 現在の解析位置
• 入力文字列長

のような構成になります。

再帰下降的にパースする場合、各非終端記号に対応する関数は呼び出し元に

• 解析結果(AST)
• 解析の成否(正常に解析できたのか、解析できなかったのか)

を返す必要があります。

パーサを作る時に話がややこしくなるのは出力が複数存在するというのが１つの要因なのかなと思いました。
例えば戻り値をASTとした場合、解析の成否の情報は戻り値以外の方法で返す必要があります。

例外がサポートされている言語だと例外が１つの選択肢としてありますが、その場合例外クラスの設計をきちんと考えておく必要があります。
NULLやそれに類するものがある言語であれば戻り値のASTがNULLであれば解析異常とするのもありかなと思います。*1

Rubyで式の構文解析をしてみた

復習がてらハンズオンの課題の数式の解析コードを書いてみました。

gist.github.com

書いてみて気づいたこと

上記コードを書いていて気づいたのですが、入力が不正な場合の異常系に対応できていません。
非終端記号に対応する各関数は、解析異常時はnilを返すというポリシーで実装してみたのですが、再帰下降型で書くと想定していない文字が出てきたときに関数レベルではエラーハンドリングができないです。やはり字句解析フェーズがないというのはつらい気がする。
この辺は好みだと思いますが、個人的には先に入力を全てレキサーにかけるのが好きです。*2

再帰か状態遷移か

再帰を使わず状態遷移で書けば、適切に入力を弾けるので、仕様が小さくて手書きでパーサを書くのであれば状態遷移の方がいいようにも思いました。*3

再帰を使うメリットは何か考えてみたのですが、コードが短くなるというのはあるかも知れません。あと仕様が大きくなると状態遷移を考えるのがかえって面倒になる気がする。デバッグは状態遷移の方が断然しやすい気がしました。*4

今後やってみたいこと

パーサジェネレータを書く

パーサ系の実装についてはパーサジェネレータを書いてみたいです。*5
あまり難しくないはずですがBNFパーサを書かないといけないというところでいつも面倒くさくなって挫折してしまいます・・・あと、懇親会でPEGというものを教えてもらったので勉強してみると何か開けてきそうな気がしました。

関数型言語でパーサを書く

勉強会や懇親会でもイミュータブルとかパーサコンビネータの話題が挙がっていましたが、オブジェクト指向言語に囚われずに関数型の頭で何かパーサを書いてみたいです。

その他

ハンズオンの課題でJSONのパーサを書こうというのがありましたが、twitterで最近JSONのパーサに関して面白そうな論文が紹介されていました。

https://www.microsoft.com/en-us/research/publication/mison-fast-json-parser-data-analytics/

ざっと読んでみたところ

1. JSONニーズ高まってて大きなデータ扱うことが増えてきたけど、パース遅いので何とかせねば。
2. どうやってやるか→投機的解析と並列化で高速化してみた。
3. やってみた結果→いい感じ。CSVとかHTMLとかXMLにも適用したい。

といった感じでしょうか。rustのプロジェクトが実装になるのかな。

github.com

解析する際にDBのようにインデックスをつけたり、SIMDとビット演算を使った並列化したりするらしい。
大量のデータとか扱う機会があれば、SIMD・GPU・FPGAあたりをデータの解析を目的として勉強してみたいです。

感想

勉強会も懇親会も色々と勉強になることが多かったです。

参加して思ったのは、構文解析を短い時間で「理解する、誰かに教える」というのは結構難しいのではないかと思いました。勉強会への参加だけでなく予習とか復習が欠かせない気がします。
あと、勉強会だと主催者の方や周りの詳しい方に質問できるので、やはりこういった場があるのはいいなぁと感じます。

kmizu様、チューターの皆様、いろいろ教えてくださった参加者の皆様、会場を使わせて頂いたはてな様、ありがとうございました。

*1:もしかしたら複数のオブジェクトを返せる言語(goとか!?)というのはパーサを書くのに向いているのかもしれない。Rubyでも複数返せるけど、そういう場合はなぜかHashを使いたくなる

*2:パーサに渡った時点で不正な文字が登場しないことが保証されるので

*3:組込だとスタックサイズの見積りの事情により再帰が使えない場合がある

*4:再帰のパースをデバッグする場合はログをしっかりと入れておかないとデバッグが難しいです

*5:せっかく勉強会に参加して気持ちが高ぶったので

Goでバイナリファイルを読み込んでHexダンプしてみた

最近触り始めたGo言語で、勉強としてバイナリファイルを読み込んでHexダンプしてみました。
バイナリファイルといってもfile.Readを使った読み込みなのでバイナリかどうかはあまり関係ないかもしれない。

package main

import (
  "fmt"
  "os"
)

func main() {
  argc := len(os.Args)
  if argc < 2 {
    fmt.Println("input file name.")
    return
  }

  filename := os.Args[1]
  f, err := os.Open(filename)
  if err != nil {
    fmt.Println("err:", err)
    return
  }

  c := make([]byte, 1)
  var buf []byte
  size := 0
  for {
    len, r_err := f.Read(c)
    if len == 0 {
      break
    }
    size += len
    if r_err != nil {
      fmt.Println("err:", err)
      return
    }
    buf = append(buf, c[0])
  }

  fmt.Printf("size:[%d]\n", size)
  for i := 0; i < size; i++ {
      fmt.Printf("%02X ", buf[i])
      if i % 16 == 15 {
        fmt.Println("")
      }
  }
}

感想

Go言語的な書き方がよくわからない

なんとなくC言語っぽく書いてみたけど、Go言語的に正しい書き方がよくわからない。
特にファイルから全データをリードする場合C言語だと大抵、EOFまで1byteずつreadするけどgoでもそんなのりでいいのかな・・・

配列とslice

RubyのArray的なのが使いたいけどgoだと配列とsliceを組み合わせて使うみたい。
sliceって機能と名前があってない気がする。

そもそも、goって名前自体英語だと普通の動詞になるので検索性がよくない。
例えば、for文について調べようとしたら

みたいな結果になった。やはり名前重要。

参考

Go言語を勉強するにあたって「基礎からわかるGo言語」を手元に置いて読んでいます。

改訂2版 基礎からわかる Go言語

この書籍では前半で言語の基本的な機能について解説されていて、後半で逆引きサンプルが載っているのでかなり役に立っています。
今のところやりたいことに合わせて前半と後半をいったり来たりしながら読んでいます。

goらしい書き方についてはこの書籍だけでは掴めないので、go好きな人が書いたコードとかもっと読んだり写経した方がよさそう。