coins memo no.6(final)

コンパイラ coins

前回の記事はこちら

coins関係はこちら

具体的な実装に入る．

で，コードはこんなかんじ．

ちなみに，実行しながら中身をチェックできる様にprintlnをめちゃくちゃ入れまくってる．

javaのデバッガ使いたい...

/*
CP.java
データフロー解析を用いた定数伝搬(Constant Propatation)最適化
coinsのLIRの懐石を行い，到達定義を計算し，定数伝播の最適化を行う．
*/

package coins.ssa;

import coins.backend.lir.LirIconst;
import coins.backend.lir.LirFconst;
import coins.backend.LocalTransformer;
import coins.backend.Data;
import coins.backend.Function;
import coins.backend.Type;
import coins.backend.lir.LirNode;
import coins.backend.lir.LirSymRef;
import coins.backend.cfg.BasicBlk;
import coins.backend.util.BiList;
import coins.backend.util.BiLink;
import coins.backend.Op;
import coins.backend.lir.LirLabelRef;
import coins.backend.sym.Symbol;
import coins.backend.util.ImList;
import java.util.Hashtable;
import java.util.Stack;
import java.util.Enumeration;
import java.util.Vector;
import coins.ssa.BitVector;

//import coins.ssa.LoopAnalysis2;


public class CP implements LocalTransformer {
    private boolean debugFlag;

    public boolean doIt(Data data, ImList args) { return true; }
    public String name() { return "CP"; }
    public String subject() {
	return "Optimizatin with Constant Propagation.";
    }

    int expallId = 0;//代入の発生する式の数を覚えておく
    int symbolId = 0;//シンボルの数を覚えておく

    int idBound;
    private Util util; // coins.ssa.Util
    private String tmpSymName="_cp";
    public static final int THR=SsaEnvironment.OptThr;
    /** The threshold of debug print **/
    public static final int THR2=SsaEnvironment.AllThr;
    private SsaEnvironment env;
    private SsaSymTab sstab;
    private Function f;

    private Stack worklist;
    private Stack expall;//代入の発生する全ての式を登録しておく
    private Stack expq;//シンボル登録した式を登録しておく
    //中身はLirクラスオブジェクト
    private Vector exp2sym;

    // Tables
    Hashtable symMap;//シンボルを貯めておくキー

    BitVector[] gen;
    BitVector[] kill;
    BitVector[] in;
    BitVector[] out;
    
    Stack compStk;
    Vector symPoint;

    // constructor
    public CP (SsaEnvironment e, SsaSymTab tab) {
      env = e;
      sstab = tab;
    }

    // 式をハッシュで検索する際のキー
    String makeExpKey(LirNode n) {
	return n.toString();
    }

    // BitVectorのoffsetだけがたってるかを調べる
    // たってるとtrueを返す
    boolean checkBit (int offset, BitVector bv) {
	for (int k = 0; k < expallId; k++) {
	    if (offset != k) {
		if (bv.getBit (k) == 1) {
		    return false;
		}
	    }
	}
	return true;
    }
    
    // 対象opコードを検索する
    // 結果は親ノードと子番号で返す
    // parentはnull，childnは0を関数に渡す必要がある
    // myFindTargetLir (対象ノード, null, 0, new Stack)
    Vector myFindTargetLir(LirNode root, LirNode parent, int childn, int opCode, Vector vec){
	if (parent == null) {
	    for(int i=0;i<root.nKids();i++){
		vec = myFindTargetLir(root.kid(i) , root, i, opCode, vec);
	    }
	} else if (root != null) {
	    if (root.opCode==opCode){// && !l.contains(root)){
		//env.output.println("Util.java : "+root);
		Integer ni = new Integer (childn);
		Object[] tmp = {parent, ni};
		vec.add(tmp);
	    }
	    for(int i=0;i<root.nKids();i++){
		vec = myFindTargetLir(root.kid (i), root, i, opCode, vec);
	    }
	}
	return vec;
    }

    // すべての式にidをふったりいろいろする
    void collectExp(BasicBlk v) {
	System.out.println ("----------------\n" +
			    "---collectExp---\n" +
			    "----------------");
	System.out.println ("Basic Block id : " + v.id);
	for(BiLink p=v.instrList().first();!p.atEnd();p=p.next()){
	    LirNode node=(LirNode)p.elem();

	    // symPointにシンボルの使用箇所をつっこむ
	    // あとでLirNodeを操作する都合上，少々めんどくさい方法をつかっている
	    // tmpstkには基本ブロックref, 対象LirNodeの親ノードref, 
	    // 親から見た子ノード番号をオブジェクト配列つっこむ
	    
	    // 代入，関数の呼び出しの場合
	    if (node.opCode == Op.SET ||
		node.opCode == Op.CALL) {
		myFindTargetLir (node, null, 0, Op.REG, new Vector ());
		
		Vector symPointLinks = myFindTargetLir (node.kid (1),
							null,
							0,
							Op.REG,
							new Vector ());


		for (int i = 0; i < symPointLinks.size (); i++) {
		    Object[] tmpObj = (Object[])symPointLinks.elementAt (i);
		    LirNode parent = (LirNode)tmpObj[0];
		    int id = ((Integer)tmpObj[1]).intValue ();
		    Object[] tmpstk = {v, parent, id};
		    symPoint.add (tmpstk);
		}

		//CJUMPの場合
	    } else if (node.opCode == Op.JUMPC) {
		Vector symPointLinks = myFindTargetLir (node.kid (0),
							null,
							0,
							Op.REG,
							new Vector ());
		for (int i = 0; i < symPointLinks.size (); i++) {
		    Object[] tmpObj = (Object[])symPointLinks.elementAt (i);
		    LirNode parent = (LirNode)tmpObj[0];
		    int id = ((Integer)tmpObj[1]).intValue ();
		    System.out.println ("\tparent : " + makeExpKey (parent) +
					", id : " + " stacked");
		    Object[] tmpstk = {v, parent, id};
		    symPoint.add (tmpstk);
		}
	    }
	    
	    if (node.opCode == Op.SET) {
		if(node.kid(0).opCode==Op.REG &&
		   node.kid(1).opCode!=Op.REG &&
		   node.kid(1).opCode!=Op.CALL &&
		   node.kid(1).opCode!=Op.USE &&
		   node.kid(1).opCode!=Op.CLOBBER) {
		    
		    // 全ての代入の発生する式を登録しておく
		    // 式番号は基本ブロック内部では出現順序が番号の大小関係となっているので
		    // killの計算時に利用可能である
		    expallId++;
		    Object[] tmp = {node, v};
		    expall.add (tmp);
		    String str = makeExpKey (node);
		    exp2sym.add (str);
		    
		    //シンボルが初出ならシンボルにユニークなidをふり
		    //テーブルに追加
		    //ノードの第一子ノード(シンボル名)を
		    //expqにつめておく
		    String newSym = makeExpKey(node.kid(0));
		    Integer newId = (Integer)symMap.get(newSym);
		    if (newId == null) {
			newId = new Integer(symbolId);
			symMap.put(newSym, newId);
			System.out.println ("Symbol " + newSym + " : " + symbolId +
					    " was registed");
			//expq : シンボルノードへのリンク
			//symMapに登録したidから呼び出せる
			expq.add(node.kid(0));
			symbolId++;
		    } else {
			
		    }
		    
		    //さらに定数の定義なら			
		    //定数の定義ならcompStkに詰めておく
		    if (node.kid(1).opCode == Op.INTCONST ||
			node.kid(1).opCode == Op.FLOATCONST) {
			//object型配列
			//BasicBlk, LirNode, String
			//  BssicBlok : 基本ブロック参照
			//  LirNode : ノード参照
			//  String : 定義される変数のmakeExpKeyにより生成された名前
			Object[] pair = {v,node};
			compStk.push(pair);
			System.out.println (newSym + " was stacked to compStk");
		    }
		}
	    }
	}
	System.out.println ("--------------------\n" +
			    "---end collectExp---\n" +
			    "--------------------");
    }	
    
    // gen と kill を初期化
    void initGen () {
	System.out.println ("-------------\n" +
			    "---initGen---\n" +
			    "-------------");
	for (int i = 0; i < expallId; i++) {// i : expression id
	    Object[] tmp = (Object[])expall.elementAt(i);
	    LirNode exp = (LirNode)tmp[0];//expression reference
	    BasicBlk expBB = (BasicBlk)tmp[1];//Basic Block Reference
	    int expBBId = expBB.id;// Basic Block ID
	    System.out.println ("set gen : \tBasicBlk" + expBBId + ", Expression" +
				i);
	    gen[expBBId].setBit (i);
	}
	System.out.println ("-----------------\n" +
			    "---end initGen---\n" +
			    "-----------------");
    }

    void initKill () {
	System.out.println ("--------------\n" +
			    "---initKill---\n" +
			    "--------------");
	for (int i = 0; i < expallId; i++) {// i : expression id
	    Object[] tmp = (Object[])expall.elementAt(i);
	    LirNode exp = (LirNode)tmp[0];//expression reference
	    BasicBlk expBB = (BasicBlk)tmp[1];//Basic Block Reference
	    int expBBId = expBB.id;// Basic Block ID
	    LirNode expSym = exp.kid (0);
	    String expSymKey = makeExpKey (expSym);//Symbol
	    Integer expSymId = (Integer)symMap.get (expSymKey);
	    int symId = expSymId.intValue ();// symbol id of left wing of substiotion
	    System.out.println ("---now checking Basic Block id\t" + expBBId +
				", exp id\t\t" + i + "---");
	    for (int j = 0; j < expallId; j++) {// j : expression id
		Object[] killTmp = (Object[])expall.elementAt(j);
		LirNode killExp = (LirNode)killTmp[0];//expression reference
		BasicBlk killExpBB = (BasicBlk)killTmp[1];//Basic Block Reference
		int killExpBBId = killExpBB.id;// Basic Block ID
		LirNode killExpSym = killExp.kid (0);
		String killExpSymKey = makeExpKey (killExpSym);//Symbol
		Integer killExpSymId = (Integer)symMap.get (killExpSymKey);
		int killSymId = killExpSymId.intValue ();// symbol id
		if (expBBId != killExpBBId) {
		    if (symId == killSymId) {
			kill[killExpBBId].setBit (i);
			System.out.println ("set kill : \tBasicBlk" + killExpBBId +
					    ", Expression" + i);
		    } 
		} else {
		    if (symId == killSymId && i < j) {
			kill[killExpBBId].setBit (i);
			kill[killExpBBId].setBit (j);
			gen[killExpBBId].resetBit (i);
			System.out.println ("set kill : \tBasicBlk" + killExpBBId +
					    ", Expression" + i);
			System.out.println ("reset gen : \tBasicBlk" + killExpBBId +
								    ", Expression" + i);
		    } else {
		    } 
		}
	    }
	}
	System.out.println ("------------------\n" +
			    "---end initKill---\n" +
			    "------------------");
    }

    // helper method
    // BitVectorの中身をダンプする
    void vectorDump (BitVector vec) {
	System.out.println ("---Dumper-vectorCump---");
	String tmp = "";
	for (int i = 0; i < expallId; i++) {
	    tmp = tmp + "\t" + vec.getBit (i);
	}
	System.out.println (tmp);
    }
    
    void init () {
	System.out.println ("----------\n" +
			    "---init---\n" +
			    "----------");
	for(BiLink bb=f.flowGraph().basicBlkList.first();!bb.atEnd();bb=bb.next()){
	    
	    BasicBlk v=(BasicBlk)bb.elem();

	    // 各節について，先行節のoutからinを計算
	    for(BiLink pd = v.predList().first(); !pd.atEnd(); pd=pd.next()){
		BasicBlk pred = (BasicBlk)pd.elem();
		if (pred != f.flowGraph ().entryBlk ()) {
		    gen[pred.id].vectorOr (in[v.id], in[v.id]);
		}
	    }
	    
	    // 各節について，in から out を計算．
	    System.out.println ("v.id : " + v.id);
	    BitVector tmpvec = new BitVector (symbolId);
	    BitVector tmpvec2 = new BitVector (symbolId);
	    in[v.id].vectorAnd (kill[v.id], tmpvec);
	    tmpvec.vectorXor (in[v.id] , tmpvec2);
	    gen[v.id].vectorOr (tmpvec2, out[v.id]);
	    
	    // ダンプして中身をチェック
	    vectorDump (out[v.id]);
	    
	    // outのいずれかのビットが0以外なら，stack に覚える．
	    // outの変更があったたので
	    for (int i = 0; i < expallId; i++) {
		if (out[v.id].getBit (i) == 1) {
		    Object[] pair = {v ,new Integer (i)};
		    worklist.push (pair);
		}
	    }
	}
	System.out.println ("--------------\n" +
			    "---end init---\n" +
			    "--------------");
    }
    
    
    void settle () {
	System.out.println ("------------\n" +
			    "---settle---\n" +
			    "------------");
	// stack から取り出し，伝播させる(propagateにわたしてやる)
	int i = 0;
	// Object[] worklist
	// worklist[0] : BasicBlk v : Reference of Basic Block
	// worklist[1] : Integer expid : expression id
	while(!worklist.empty()) {
	    System.out.println ("count : " + i);
	    Object[] pair = (Object[])worklist.pop();
	    BasicBlk bb = (BasicBlk)pair[0];
	    int exId = ((Integer)pair[1]).intValue();
	    propagate (bb, exId);
	}
	System.out.println ("----------------\n" +
			    "---end settle---\n" +
			    "----------------");
    }

    void propagate (BasicBlk v, int exId) {
	// 後続節への伝播．
	for(BiLink ss= v.succList().first();!ss.atEnd();ss=ss.next()){
	    BasicBlk succ = (BasicBlk)ss.elem();
	    // 後続節の in を更新．
	    // in = in & out
	    out[v.id].vectorOr (in[succ.id], in[succ.id]);
	    
	    BitVector oldOut = new BitVector (expallId);
	    out[succ.id].vectorCopy (oldOut);

	    // 後続節のinを更新し，out を計算．
	    System.out.println ("v.id : " + v.id);
	    BitVector tmpvec = new BitVector (symbolId);
	    BitVector tmpvec2 = new BitVector (symbolId);
	    in[succ.id].vectorAnd (kill[succ.id], tmpvec);
	    in[succ.id].vectorXor (tmpvec , tmpvec2);
	    tmpvec2.vectorOr (gen[succ.id], out[succ.id]);

	    // outのビットが変化したらもういっかい
	    for (int i = 0; i < expallId; i++) {
		if (out[succ.id].getBit (i) != oldOut.getBit (i)) {
		    propagate(succ, i);
		    continue;
		}
	    }
	}
    }

    void update () {
	System.out.println ("------------\n" +
			    "---update---\n" +
			    "------------");
	// 実際に，使える定数を置き換えていく
	int count = 0;//debug
	// cmpStkには定数の定義が発生した箇所が全部詰まっている
	while ( !compStk.empty() ) {
	    //compStkの中身を取り出す
	    Object[] pair = (Object[])compStk.pop();
	    //compStk : 定数の定義の起こるところ
	    //Object[] pair: BasicBlk, LirNode, String
	    //  BssicBlok : 基本ブロック参照
	    //  LirNode : ノード参照

	    // 中身をほどよいオブジェクトにする
	    BasicBlk compV = (BasicBlk)pair[0];//ターゲットとなる基本ブロック
	    LirNode compNode = (LirNode)pair[1];//ターゲットとなるノード
	    //ターゲットとなるノードのsymMapキー
	    String compKey = makeExpKey(compNode.kid(0));
	    System.out.println ("debug print : now searching key : " + compKey +
				"\nBasicBlk : " + compV.id);
	    //ビットベクターアクセッサ
	    int compId = ((Integer)symMap.get(compKey)).intValue ();
	    Symbol compNodeSymbol = ((LirSymRef)compNode.kid (0)).symbol;
	    LirNode compNodeCValue = compNode.kid (1);
		
	    // 他全ての式をチェックして(を用いて)
	    // もし，このシンボルを使用していて，なおかつ
	    // この定義が唯一その式まで到達するなら(in, outより)
	    // その式のシンボルを定数に置き換えられる
	    for (int i = 0; i < symPoint.size(); i++) {
		if (i != compId) {
		    Object[] targetObj = (Object[])symPoint.elementAt(i);
		    BasicBlk targetBlk = (BasicBlk)targetObj[0];
		    LirNode targetParentNode = (LirNode)targetObj[1];
		    int targetKidId = ((Integer)targetObj[2]).intValue ();
		    LirNode targetNode = targetParentNode.kid (targetKidId);
		    System.out.println (makeExpKey(targetNode));
		    Symbol targetSymbol = ((LirSymRef)targetNode).symbol;
		    //((LirSymRef)node.kid (0)).symbol;
		    
		    if (targetKidId > 0 &&
			(targetSymbol == compNodeSymbol)) {
			System.out.println ("kitakore pre");
			BitVector tmpBit = new BitVector (expallId);
			for (int j = 0; j < exp2sym.size (); j++) {
			    String tmpStr = (String)(exp2sym.elementAt (j));
			    if (makeExpKey (targetNode) == tmpStr)
				tmpBit.setBit (j);
			}
			tmpBit.vectorAnd (in[targetBlk.id],tmpBit);
			//boolean checkBit (int offset, BitVector bv)
			if (checkBit (compId, tmpBit)) {//ビットがcompIdだけたってる
			    symPoint.remove (i);//もういらないのでバイバイ
			    i--;//消した分次をいっこ進める
			    targetParentNode.setKid (targetKidId,
						     compNodeCValue.makeCopy (env.lir));
			}
		    }
		}
	    }
	}
	System.out.println ("----------------\n" +
			    "---end update---\n" +
			    "----------------");
    }
    
    public boolean doIt(Function function,ImList args) {
	System.out.println ("------------------------\n" +
			    "---CP.java debug prnt---\n" +
			    "------------------------");
	// 初期化
	f = function;
	// 環境と関数を考慮したユーティリティを提供する
	util=new Util(env,f); // coins.ssa.Util

	worklist = new Stack ();
	symMap = new Hashtable ();
	expall = new Stack ();
	expq = new Stack ();
	compStk = new Stack ();
	symPoint = new Vector ();
	exp2sym = new Vector ();
	
	idBound = f.flowGraph().idBound();//基本ブロック数
	//基本ブロックの数で初期化
	kill = new BitVector[idBound];
	gen = new BitVector[idBound];
	in = new BitVector[idBound];
	out = new BitVector[idBound];;

	// 各基本ブロックの式をチェック
	for(BiLink pp=f.flowGraph().basicBlkList.first();!pp.atEnd();pp=pp.next()){
	    BasicBlk v=(BasicBlk)pp.elem();
	    System.out.println ("v.id : " + v.id);
	    collectExp(v);
	}

	// 全ての代入の発生する式の数で初期化
	for (int i = 0; i < f.flowGraph().idBound(); i++) {
	    gen[i] = new BitVector (expallId);
	    kill[i] = new BitVector (expallId);
	    in[i] = new BitVector (expallId);
	    out[i] = new BitVector (expallId);
	}

	// PRINT DEBUG
	// 全てのシンボルを見せる
	System.out.println ("\nDumping all symMap");
	System.out.println ("dump all the symbols");
	System.out.println ("number of symbols : symbolId : " + symbolId + "\n");
	for (Enumeration e = symMap.keys (); e.hasMoreElements ();) {
	    String key = (String)e.nextElement ();
	    System.out.println ("\t" + key + ",\tvalue\t" + symMap.get (key));
	}
	System.out.println ("");

	// PRINT DEBUG
	// 全ての代入の発生する式を見せる
	System.out.println ("\nDumping all expression which occure substitution");
	System.out.println ("number of expression : expallId : " + expallId + "\n");
	for (int i = 0; i < expallId; i++) {
	    Object[] tmp = (Object[])expall.elementAt(i);
	    LirNode exp = (LirNode)tmp[0];
	    System.out.println ("\t" + i + "\t" + makeExpKey (exp));
	}
	System.out.println ("");
	
	// main
	// init
	initGen ();

	initKill ();
	
	init();

	// PRINT DEBUG
	System.out.println ("Dumping all gen");
	for (int i = 0; i < f.flowGraph().idBound(); i++) {
	    System.out.println ("\tgen[" + i + "] : ");
	    for (int j = 0; j < expallId; j++) {
		System.out.println ("\t\tBIT : " + gen[i].getBit (j));
	    }
	}
	
	System.out.println ("Dumping all kill");
	for (int i = 0; i < f.flowGraph().idBound(); i++) {
	    System.out.println ("\tkill[" + i + "] : ");
	    for (int j = 0; j < expallId; j++) {
		System.out.println ("\t\tBIT : " + kill[i].getBit (j));
	    }
	}

	System.out.println ("Dumping all in");
	for (int i = 0; i < f.flowGraph().idBound(); i++) {
	    System.out.println ("\tin[" + i + "] : ");
	    for (int j = 0; j < expallId; j++) {
		System.out.println ("\t\tBIT : " + in[i].getBit (j));
	    }
	}

	System.out.println ("print debug : dump : out");
	for (int i = 0; i < f.flowGraph().idBound(); i++) {
	    System.out.println ("\tout[" + i + "] : ");
	    for (int j = 0; j < expallId; j++) {
		System.out.println ("\t\tBIT : " + out[i].getBit (j));
	    }
	}
	System.out.println ("");

	// settle
	settle();
	// uddate
	update();
	
	System.out.println ("----------------------------\n" +
			    "---End CP.java debug prnt---\n" +
			    "----------------------------");
	f.flowGraph().touch();
	return(true);
    }
}

こいつを組み込む方法は前回に紹介したこちらを参考にする．

で，coinsをリビルドするとエラーが無ければちゃんと動くはず．

動かし方なんだけど，どうもcoinsはHIR(高水準中間表現)の最適化オプションを指定しないと，

勝手に定数伝播を計算する事が判明したので(www)，無理矢理はずして動作させる．

#アセンブラを吐く
java coins.driver.Driver -coins:assembler=as,hiropt=,ssa-opt=cp,target=x86 64-
mac -I../lang/c/include -S -o .s .c
#オブジェクトファイルの吐き出しとリンクをめんどくさいので一発で
gcc -arch x86_64 -lm -o .out .s

で．実験．今回はこんなCソースを食わせる．

#include <stdio.h>

int fun (int i, int j) {
  return i + j;
}

int main (void) {
  int b = 3;
  int c = 8;
  int d = b + c;
  c = 9;

  while (b < c) {
    b++;
  }

  c = fun (b, c);
  return 0;
}

で，最適化の前と後をLIR(低水準中間表現)でみてみると，

# 最適化前
Function "fun":
Local Symbol table:
("i.1" FRAME I32 4 0 &syminfo "fun_i" "./test_src/test.c" 3 0)
("j.2" FRAME I32 4 0 &syminfo "fun_j" "./test_src/test.c" 3 0)
("returnvalue.6" FRAME I32 4 0)

Control Flow Graph:

#1 Basic Block (.L1): DFN=(1,1), <-() ->(#2)
(PROLOGUE (0 0) (MEM I32 (FRAME I64 "i.1")) (MEM I32 (FRAME I64 "j.2")))
(JUMP (LABEL I64 ".L2"))

#2 Basic Block (.L2): DFN=(2,2), parent=#1, <-(#1) ->(#3)
(SET I32 (MEM I32 (FRAME I64 "returnvalue.6")) (ADD I32 (MEM I32 (FRAME I64 "i.1")) (MEM I32 (FRAME I64 "j.2"))))
(JUMP (LABEL I64 ".L3"))

#3 Basic Block (.L3): DFN=(3,3), parent=#2, <-(#2) ->()
(EPILOGUE (0 0) (MEM I32 (FRAME I64 "returnvalue.6")))
End Function


Function "main":
Local Symbol table:
("b.3" FRAME I32 4 0 &syminfo "main_b" "./test_src/test.c" 8 0)
("c.4" FRAME I32 4 0 &syminfo "main_c" "./test_src/test.c" 9 0)
("d.5" FRAME I32 4 0 &syminfo "main_d" "./test_src/test.c" 10 0)
("returnvalue.7" FRAME I32 4 0)

Control Flow Graph:

#1 Basic Block (.L4): DFN=(1,1), <-() ->(#2)
(PROLOGUE (0 0))
(JUMP (LABEL I64 ".L5"))

#2 Basic Block (.L5): DFN=(2,2), parent=#1, <-(#1) ->(#3)
(SET I32 (MEM I32 (FRAME I64 "b.3")) (INTCONST I32 3))
(SET I32 (MEM I32 (FRAME I64 "c.4")) (INTCONST I32 8))
(SET I32 (MEM I32 (FRAME I64 "d.5")) (ADD I32 (MEM I32 (FRAME I64 "b.3")) (MEM I32 (FRAME I64 "c.4"))))
(SET I32 (MEM I32 (FRAME I64 "c.4")) (INTCONST I32 9))
(JUMP (LABEL I64 ".L6"))

#3 Basic Block (.L6): DFN=(3,3), parent=#2, <-(#2,#4) ->(#4,#5)
(JUMPC (TSTLTS I32 (MEM I32 (FRAME I64 "b.3")) (MEM I32 (FRAME I64 "c.4"))) (LABEL I64 ".L7") (LABEL I64 ".L8"))

#4 Basic Block (.L7): DFN=(4,6), parent=#3, <-(#3) ->(#3)
(SET I32 (MEM I32 (FRAME I64 "b.3")) (ADD I32 (MEM I32 (FRAME I64 "b.3")) (INTCONST I32 1)))
(JUMP (LABEL I64 ".L6"))

#5 Basic Block (.L8): DFN=(5,4), parent=#3, <-(#3) ->(#6)
(CALL (STATIC I64 "fun") ( (MEM I32 (FRAME I64 "b.3")) (MEM I32 (FRAME I64 "c.4"))) *1 (INTCONST I32 0))
(JUMP (LABEL I64 ".L9"))

#6 Basic Block (.L9): DFN=(6,5), parent=#5, <-(#5) ->()
(EPILOGUE (0 0) (MEM I32 (FRAME I64 "returnvalue.7")))
End Function

# 最適化後

Function "fun":
Local Symbol table:
("i.1%" REG I32 4 0)
("j.2%" REG I32 4 0)
("returnvalue.6%" REG I32 4 0)

Control Flow Graph:

#1 Basic Block (.L1): DFN=(1,1), <-() ->(#2)
(PROLOGUE (0 0) (REG I32 "i.1%") (REG I32 "j.2%"))
(SET I32 (REG I32 "returnvalue.6%") (ADD I32 (REG I32 "i.1%") (REG I32 "j.2%")))
(JUMP (LABEL I64 ".L3"))

#2 Basic Block (.L3): DFN=(2,2), parent=#1, <-(#1) ->()
(EPILOGUE (0 0) (REG I32 "returnvalue.6%"))
End Function


Function "main":
Local Symbol table:
("b.3%" REG I32 4 0)
("c.4%" REG I32 4 0)
("d.5%" REG I32 4 0)
("returnvalue.7%" REG I32 4 0)

Control Flow Graph:

#1 Basic Block (.L4): DFN=(1,1), <-() ->(#3,#4)
(PROLOGUE (0 0))
(SET I32 (REG I32 "b.3%") (INTCONST I32 3))
(SET I32 (REG I32 "c.4%") (INTCONST I32 8))
(SET I32 (REG I32 "d.5%") (INTCONST I32 11))
(SET I32 (REG I32 "c.4%") (INTCONST I32 9))
(JUMPC (TSTLTS I32 (REG I32 "b.3%") (INTCONST I32 9)) (LABEL I64 ".L7") (LABEL I64 ".L8"))

#3 Basic Block (.L7): DFN=(2,2), parent=#1, <-(#1,#3) ->(#3,#4)
(SET I32 (REG I32 "b.3%") (ADD I32 (REG I32 "b.3%") (INTCONST I32 1)))
(JUMPC (TSTLTS I32 (REG I32 "b.3%") (INTCONST I32 9)) (LABEL I64 ".L7") (LABEL I64 ".L8"))

#4 Basic Block (.L8): DFN=(3,3), parent=#3, <-(#1,#3) ->(#5)
(CALL (STATIC I64 "fun") ( (REG I32 "b.3%") (INTCONST I32 8) ) *2
(JUMP (LABEL I64 ".L9"))

#5 Basic Block (.L9): DFN=(4,4), parent=#4, <-(#4) ->()
(EPILOGUE (0 0) (REG I32 "returnvalue.7%"))
End Function

となる．

一部の(FRAME I64 "*.*")が定数と置き換わってる事がわかるが，置き換えって無いところもある...

???

げ，バグだ．．．

どうやら，2項演算や，CALL(関数呼び出し)やTSTLTS(判定など)の2つの小ノードを参照する場合は

2個目の小ノードしか置き換わっていない．

おお，こまった....



まぁ，いろいろあって，このくらいで終わりにする．

まぁちゃんと動いた(!?)ので終了．

*1:MEM I32 (FRAME I64 "c.4")))) (SET I32 (MEM I32 (FRAME I64 "returnvalue.7"

*2:REG I32 "c.4%"))) (SET I32 (REG I32 "returnvalue.7%") (INTCONST I32 0