problem with gep

gep.md

何がわからないのか

common subexpression elimination や loop invariant code motion を行うと， getelementptr が，本来含まれていた基本ブロックの外へと移動することがある．

一見問題なさそうだが，場合によっては生成される命令数が増える．(これは自作コンパイラ基盤の実装上の問題)

例

次のコードは，

A:
   a = gep ...
   b = load a

次のように解釈されるから，

A:
   b = load (gep ...)

最終的に combine されて

A:
   b = mov [...]

みたいな感じになる．

でも次のコードは，

A:
   a = gep ...
   br B
B:
   b = load a

ブロックBからブロックA内のaを参照するから，どうしてもgep ...の結果がaに代入されてしまう．(liveoutする値は，仮想レジスタ(ここではa)に代入されることになっている)

だから，最終的にこうなる．

A:
   a = lea ...
   br B
B:
   b = mov [a]

さっきは mov 一個で済んでいたのに，今回は lea と mov を使ってしまっている．

解決方法

gep を移動させない，liveoutする値の挙動を変えるなど． これ以外に思いつかないので，何か良い方法があれば教えていただきたい．

こんにちは。LLVMではCodgGenのlib/CodeGen/CodeGenPrepare.cppでa = gep ...の部分をb = load ..の直前に戻す操作を（速くなりそうなら)LLVM IRレベルで行っています(LICMした後に戻しています)。
例えば以下のIRで

define i32 @f(i32* nocapture readonly %p) local_unnamed_addr #0 {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %p, i64 1
  br label %for.body
for.cond.cleanup:                                 ; preds = %for.body
  ret i32 %call
for.body:                                         ; preds = %for.body, %entry
  %i.05 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %0 = load i32, i32* %add.ptr, align 4, !tbaa !3
  %call = tail call i32 @nondet(i32 %0) #2
  %inc = add nuw nsw i32 %i.05, 1
  %exitcond = icmp eq i32 %inc, 100
  br i1 %exitcond, label %for.cond.cleanup, label %for.body
}

これを-print-after-allすると

define i32 @f(i32* nocapture readonly %p) local_unnamed_addr {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %p, i64 1
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body
  ret i32 %call

for.body:                                         ; preds = %for.body, %entry
  %lsr.iv = phi i32 [ %lsr.iv.next, %for.body ], [ 100, %entry ]
  %0 = load i32, i32* %add.ptr, align 4
  %call = tail call i32 @nondet(i32 %0)
  %lsr.iv.next = add nsw i32 %lsr.iv, -1
  %exitcond = icmp eq i32 %lsr.iv.next, 0
  br i1 %exitcond, label %for.cond.cleanup, label %for.body
}
*** IR Dump After CodeGen Prepare ***
define i32 @f(i32* nocapture readonly %p) local_unnamed_addr {
entry:
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body
  ret i32 %call

for.body:                                         ; preds = %for.body, %entry
  %lsr.iv = phi i32 [ %lsr.iv.next, %for.body ], [ 100, %entry ]
  %0 = bitcast i32* %p to i8*
  %sunkaddr = getelementptr inbounds i8, i8* %0, i64 4
  %1 = bitcast i8* %sunkaddr to i32*
  %2 = load i32, i32* %1, align 4
  %call = tail call i32 @nondet(i32 %2)
  %lsr.iv.next = add nsw i32 %lsr.iv, -1
  %exitcond = icmp eq i32 %lsr.iv.next, 0
  br i1 %exitcond, label %for.cond.cleanup, label %for.body
}

になり%addr.ptrがsunkされることが分かります。CodeGenPrepareで実際にsunkしたほうがいいか判定しているのはこの辺り(たぶん）だと思っていて（実際I->hasOneUse()を消したらsunkされませんでした）、同じようにUseが1つなら直前に持ってくと上手く行きそうな気がします(isProfitableToFoldIntoAddressingMode辺りも参考になりそうです)

CodeGenPrepareというものが存在することを知らなかったのと，調べものをしているときによく見かけるsinkやsunkという言葉の意味がようやく理解できました．
本当にありがとうございます．解決できそうです．

いえいえ、自分もあまり知らなかったので勉強になりました🙌