java开发C语言编译器:消除冗余语句和把ifelse控制语句编译成字节码

当前编译器已经能够把很多C语言的源程序编译成可以在java虚拟机上运行的字节码,但一直存在一个问题是,编译出的字节码存有冗余语句,例如赋值语句: a = 1; 它编译成java字节码后情况如下:

aload 0
sipush 1
astore 0

假设变量a在虚拟机局部变量队列中的存储位置为0,那么上面代码冗余之处在于多出了一条语句aload 0, 要给变量a赋值,只需下面两条语句便足够了。之所以产生冗余语句,是因为编译器的实现有问题,在编译器解析代码时,一旦遇到变量名,它就会把该变量加载到虚拟机的执行堆栈上,或者是解析到数字字符常量时,它也会把字符代表的数值压到堆栈上。解析数字字符常量和代码变量的语法表达式是: NUMBER -> UNARY NAME -> UNARY

所以产生冗余语句的编译器实现代码如下:

public class UnaryNodeExecutor extends BaseExecutor implements IExecutorReceiver{
    private Symbol structObjSymbol = null;
    private Symbol monitorSymbol = null;

    @Override
    public Object Execute(ICodeNode root) {
    ....
    case CGrammarInitializer.Number_TO_Unary:
            text = (String)root.getAttribute(ICodeKey.TEXT);
            boolean isFloat = text.indexOf('.') != -1;
            if (isFloat) {
                value = Float.valueOf(text);
                root.setAttribute(ICodeKey.VALUE, Float.valueOf(text));    
            } else {
                value = Integer.valueOf(text);
                root.setAttribute(ICodeKey.VALUE, Integer.valueOf(text));
            }
            ProgramGenerator.getInstance().emit(Instruction.SIPUSH, "" + value);
            break;

        case CGrammarInitializer.Name_TO_Unary:
            symbol = (Symbol)root.getAttribute(ICodeKey.SYMBOL);
            if (symbol != null) {
                root.setAttribute(ICodeKey.VALUE, symbol.getValue());
                root.setAttribute(ICodeKey.TEXT, symbol.getName());

                ICodeNode func = CodeTreeBuilder.getCodeTreeBuilder().getFunctionNodeByName(symbol.getName());
                if (func == null && symbol.getValue() != null) {

                    ProgramGenerator generator = ProgramGenerator.getInstance();
                    int idx = generator.getLocalVariableIndex(symbol);
                    generator.emit(Instruction.ILOAD, "" + idx);    

                }

            }
            break;

    ....
    }
}

上面代码是编译器解析变量名和数字字符常量的地方,其中有一部分代码是使用sipush指令把数字常量压入堆栈或是通过iload指令把变量从队列加载到堆栈的,产生冗余语句的也正是这部分代码,要消除冗余,我们需要把带有generator.emit的语句给注释掉。

为了保证代码修改不影响编译器的正确性,我们还需对相关部分进行修改。编译器解析赋值语句,例如 a = 1;是通过NoCommaExprExecutor实现的,所以该执行器的代码需要做相应修改如下:

public class NoCommaExprExecutor extends BaseExecutor{
    ExecutorFactory factory = ExecutorFactory.getExecutorFactory();
    ProgramGenerator generator = ProgramGenerator.getInstance();

    @Override 
    public Object Execute(ICodeNode root) {
    ....
    child = root.getChildren().get(0);
            String t = (String)child.getAttribute(ICodeKey.TEXT);
            IValueSetter setter;
            setter = (IValueSetter)child.getAttribute(ICodeKey.SYMBOL);
            child = root.getChildren().get(1);
            //newly add
            value = child.getAttribute(ICodeKey.SYMBOL);
            if (value == null) {
                value = child.getAttribute(ICodeKey.VALUE);
            }
            try {
                setter.setValue(value);
            } catch (Exception e) {
                ....
            }
    ....
    }
}

如果赋值语句形式为 a = b; 也就是用一个变量给另一个变量赋值,那么通过ICodeKey.Symbol 就可以得到变量b对应的Symbol对象,如果赋值语句形式为 a = 1; 那么ICodeKey.VALUE 就会把数值1返回给变量value, setter对应的是变量a的Symol对象,调用其setValue函数完成赋值功能,因此我们需要进入Symbol.java修改相应代码:

public void setValue(Object obj) {
    ....
    ProgramGenerator generator = ProgramGenerator.getInstance();

        if (obj instanceof Symbol) {
            Symbol symbol = (Symbol)obj;
            this.value = symbol.value;
            int i = generator.getLocalVariableIndex(symbol);
            generator.emit(Instruction.ILOAD, "" + i);
        } else if (obj instanceof Integer){
            Integer val = (Integer)obj;
            generator.emit(Instruction.SIPUSH, "" + val);
            this.value = obj;
        }
    ....
}

执行赋值操作时,如果是用变量给变量赋值,那么编译器生成iload语句,把用来赋值的变量加载到虚拟机的堆栈上,如果用数字字符常量赋值,那么需要使用sipush语句把该数值压到堆栈上。 最后我们还需修改下实现printf函数调用的代码,在clibcall.java里:

private void generateJavaAssemblyForPrintf(String argStr, int argCount) {
.....
ArrayList<Object> argList = FunctionArgumentList.getFunctionArgumentList().getFuncArgSymsList(true);
        int localVariableNum = list.size();
        int count = 0;
        int argSymCount = 0;
        while (count < argCount) {
            Symbol argSym = (Symbol)argList.get(argSymCount);
            argSymCount++;
            int d = generator.getLocalVariableIndex(argSym);
            generator.emit(Instruction.ILOAD, "" + d);
            generator.emit(Instruction.ISTORE, "" + (localVariableNum + count));
            count++;
        }
   ....
}

这部分代码用于把printf语句中的变量加载到虚拟机堆栈上,例如printf(“value of a and b is %d, %d”, a, b); 代码会把变量a,b从虚拟机的局部变量队列加载到堆栈上,以便打印输出。经过上面的修改后,在生成java字节码时,就不再会有冗余语句了。现在我们看看,如何把if else 这些分支控制语句转换为java字节码。

在jvm中,有专门用于比较大小然后跳转到指定分支的指令,例如 Int1>=Int2 对应的指令为if_icmpge, Int1> Int2对应的指令为if_icmpgt, Int1<=Int2对应的指令为if_icmplt,Int1<Int2对应的指令为if_icmple,Int1==Int2 对应的指令为if_icmpeq, Int1 != Int2 对应指令为:if_icmpne。

要使用比较指令时,需要把相互比较的对象压到堆栈上,比较指令会把堆栈上的两个对象取出,比较大小后,根据比较结果进行代码跳转,例如C语言代码:

if ( 1 < 2) {
  a = 1;
} else {
  a = 2;
}
a = 3;

编译成java字节码后如下:

sipush 1
sipush 2
if_cmpge  branch0
sipush 1
astore 0
goto out_branch0
branch0:
sipush 2
istore 0
out_branch0:
sipush 3
istore 0

要比较1和2大小,先要把两个数值压到堆栈上,C语言代码使用的是1<2,编译成字节码时,我们要使用指令if_cmpge 也就是>=, 于是当堆栈上两个数的值是大于等于关系时,跳转到branch0所在位置的代码去执行,要不然继续往下执行,然后通过goto 直接跳转到out_branch0的位置去执行代码,上面指令执行的分支跳转逻辑与C语言是一致的。

如果有多个平行并列的if else, 我们则把branch 和 out_branch后面的0加1,变成branch1和out_branch1,需要注意的还有间套的if else, 例如下面的C代码:

if (a > 1 ) {
       if (b > 2) {
           b = 5;
       }
   }
   else {
       b = 4;
    }

我们编译间套里面的if else时,把内部的ifelse对应的分支名称在前面加上i,比如一层间套,那么它对应的就是ibranch0,两层就是iibranch0,同理一层间套对应iout_branch0,两层就是iiout_branch0. 由于存在间套原因,ifelse语句编译比较困难,且容易出错。我们看看实现编译的代码实现,首先是修改program_generator.java:

public class ProgramGenerator extends CodeGenerator {
....
    private int branch_count = 0;
    private int branch_out = 0;
    private String embedded = "";
    public int getIfElseEmbedCount() {
        return embedded.length();
    }

    public void incraseIfElseEmbed() {
        embedded += "i";
    }

    public void decraseIfElseEmbed() {
        embedded = embedded.substring(1);
    }

    public void  emitBranchOut() {
        String s = "\n" + embedded+"branch_out" + branch_out + ":\n";
        this.emitString(s);
        branch_out++;
    }

    public String getBranchOut() {
        String s = embedded + "branch_out" + branch_out;
        return s;
    }

    public String getCurrentBranch() {
        String str = embedded + "branch" + branch_count;
        return str;
    }

    public void increaseBranch() {
        branch_count++;
    }

    public String getAheadBranch(int ahead) {
        String str =  embedded + "branch" + branch_count + ahead + ":";
        this.emitString(str);
        return str;
    }
....
}

如果编译时发现有ifelse间套,那么需要调用getIfElseEmbedCount这样使得编译出的跳转分支名称前面能加上一个字母i,完成间套后要调用decraseIfElseEmbed(), 其余接口调用都是用来编译ifelse跳转时的分支名称的。

如果ifelse 在代码中一起出现时,ElseStatementExecutor会被执行,如果代码中只有if出现时,那么只有IfStatementExecutor会被执行,我们看看相关代码:

public class ElseStatementExecutor extends BaseExecutor {
    private ProgramGenerator generator = ProgramGenerator.getInstance();
    @Override
    public Object Execute(ICodeNode root) {
         BaseExecutor.inIfElseStatement = true;

        //先执行if 部分
         ICodeNode res = executeChild(root, 0);

         BaseExecutor.inIfElseStatement = false;

         String branch = generator.getCurrentBranch();
         branch = "\n" + branch + ":\n";
         generator.emitString(branch);
         if (generator.getIfElseEmbedCount() == 0) {
             generator.increaseBranch();     
         }


         Object obj = res.getAttribute(ICodeKey.VALUE);
         if ((Integer)obj == 0 || BaseExecutor.isCompileMode) {
             generator.incraseIfElseEmbed();
             //if 部分没有执行,所以执行else部分
             res = executeChild(root, 1); 
             generator.decraseIfElseEmbed();
         }

         copyChild(root, res);

         generator.emitBranchOut();

         return root;
    }

}

在编译ifelse时,如果if条件不成立就会跳转到else部分,我们用’branchX’来表示else部分代码分支开始之处,由于编译器在执行ifelse语句时,IfStatementExecutor先会被执行,当它执行时需要知道当前代码是ifelse还是仅仅包含if语句,如果inIfElseStatement设置成true,那表明当前代码是ifelse形式,如果是false表明当前代码是if形式,两种形式不同,输出的字节码就不同。在输出else部分的指令时,编译器先把else部分的代码分支名称输出来。else之后的代码就是branch_outX分支所对应的代码,如果if条件成立,那么if接下来的指令会被执行,执行完后直接通过goto跳转到branch_outX部分,避开else部分指令的执行。

在看看IfStatementExecutor的实现:

public class IfStatementExecutor extends BaseExecutor {

     @Override 
     public Object Execute(ICodeNode root) {
         ProgramGenerator generator = ProgramGenerator.getInstance();
         ICodeNode res = executeChild(root, 0); 
         Integer val = (Integer)res.getAttribute(ICodeKey.VALUE);
         copyChild(root, res);  
         if ((val != null && val != 0) || BaseExecutor.isCompileMode) {
             generator.incraseIfElseEmbed();
             boolean b = BaseExecutor.inIfElseStatement;
             BaseExecutor.inIfElseStatement = false;
             executeChild(root, 1);
             BaseExecutor.inIfElseStatement = b;
             generator.decraseIfElseEmbed();
         }

         if (BaseExecutor.inIfElseStatement == true) {
             String branchOut = generator.getBranchOut();
             generator.emitString(Instruction.GOTO.toString() + " " + branchOut);     
         } else {
             String curBranch = generator.getCurrentBranch();
             generator.emitString(curBranch + ":\n");
         }



        return root;
    }

}

在编译if部分的指令时,如果没有else部分,那么就不需要输出goto指令,执行完if部分的代码后,继续往下执行就可以,如果有else部分,那么需要输出goto指令,越过else部分的代码。

在编译if部分的代码时,一定要调用incraseIfElseEmbed,因为if内部很可能会出现ifelse的间套,同理在编译else部分的代码时,也要调用这个接口,因为else部分也会出现ifelse间套。

完成上面的代码后,我们尝试编译下面的C语言代码:

void main () {
   int a;
   int b;
   a = 2;
   b = 3;
   if (a > 1 ) {
       if (b > 2) {
           b = 5;
       }
   }
   else {
       b = 4;
    }

    printf("value of b is :%d", b);
}

上面代码中存有ifelse间套,我们看看编译出来的java字节码时怎样的,运行修改代码后的编译器,然后输入上面C语言代码,得到的编译结果如下:

.class public CSourceToJava
.super java/lang/Object

.method public static main([Ljava/lang/String;)V
    sipush    2
    istore    1
    sipush    3
    istore    0
    iload    1
    sipush    1
if_icmple branch0
    iload    0
    sipush    2
if_icmple ibranch0
    sipush    5
    istore    0
ibranch0:
goto branch_out0
branch0:
    sipush    4
    istore    0

branch_out0:
    iload    0
    istore    2
    getstatic    java/lang/System/out Ljava/io/PrintStream;
    ldc    "value of b is :"
    invokevirtual    java/io/PrintStream/print(Ljava/lang/String;)V
    getstatic    java/lang/System/out Ljava/io/PrintStream;
    iload    2
    invokevirtual    java/io/PrintStream/print(I)V
    getstatic    java/lang/System/out Ljava/io/PrintStream;
    ldc    "
"
    invokevirtual    java/io/PrintStream/print(Ljava/lang/String;)V
    return
.end method
.end class

在ifcmple指令前,iload 1表示把变量a加入堆栈,sipush 1把数字常量1压入堆栈,如果变量a的值小于1的话则跳转到branch0处执行,branch0处的指令作用是把数值4赋值给变量b, 如果a的值大于1,则继续往下执行,iload 0表示把变量b加载到堆栈,sipush 2表示把数值2压入堆栈如果变量b的值小于数值2则跳转到ibranch0执行,这个分支名称前面的i就是因为ifelse间套而添加的。branch_out0处指令的意识是通过printf把相关信息打印出来。

把编译出来的java汇编转换成二进制字节码运行后结果如下:

从结果上看,打印出来的b的值是5,由此可见我们编译输出的结果应该是正确的。ifelse编译由于需要考虑到间套,所以逻辑上比较复杂,具体的理解需要通过视频讲解后,并亲手调试代码才好掌握,请参看视频用java开发C语言编译器

当前我们的编译方法面对更复杂的ifelse间套时可能还会有问题,基于尽可能简单原则,我们先这么做,以后遇到问题时才进一步完善。

原文发布于微信公众号 - Coding迪斯尼(gh_c9f933e7765d)

原文发表时间:2017-09-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Create Sun

python 3.x 爬虫基础---正则表达式(案例:爬取猫眼信息,写入txt,csv,下载图片)

  正则表达式是对字符串的一种逻辑公式,用事先定义好的一些特定字符、及这些特定字符的组合,组成一个“规则的字符串”,此字符串用来表示对字符串的一种“过滤”逻辑。...

57440
来自专栏用户2442861的专栏

Java内存管理(一、内存分配)

关于Java内存分配,很多问题都模模糊糊,不能全面贯通理解。今查阅资料,欲求深入挖掘,彻底理清java内存分配脉络,只因水平有限,没达到预期效果,仅以此文对所...

1K30
来自专栏码云1024

JAVA 第二天 内部类

294110
来自专栏landv

java修饰符

17630
来自专栏漏斗社区

代码审计|PHP代码执行函数进阶版实力上线了!

本篇涉及函数:call_user_func()、call_user_func_array(),array_filter,usort,uasort() 0x0...

34340
来自专栏TungHsu

这或许是对小白最友好的python入门了吧——11,if语句初体验

在python中,if语句是很常见的一个语句。今天,我们就来简单认识一下这个语句。 在学习if语句之前,我们还要学习一下条件测试: ? 首先我们用一个等号将na...

38550
来自专栏along的开发之旅

Sevlet的生命周期

Servlet的生命周期是指: servlet类对象什么时候创建,什么时候调用什么方法,什么时候销毁。

10920
来自专栏Dato

关于 Integer 值比较的问题

今天刚好遇到这样的问题,别的不说,先上代码 public class TestInteger { public static void main(fi...

28080
来自专栏数据结构与算法

BZOJ3585: mex(主席树)

Description   有一个长度为n的数组{a1,a2,...,an}。m次询问,每次询问一个区间内最小没有出现过的自然数。 Input   第一行n,m...

43290
来自专栏xcywt

《Linux命令行与shell脚本编程大全》第二十章 正则表达式

20.1 什么是正则表达式 20.1.1 定义 正则表达式是你所定义的模式模板。linux工具可以用它来过滤文本。 正则表达式利用通配符来描述数据流中第一个或多...

29960

扫码关注云+社区

领取腾讯云代金券