- 技术人生
- ［转载］LCC编译器的源程序分析(54)指令模式匹配
在
LCC
编译器里，先把下面的语句翻译成中间表示，
int nTest1 = 1;
其中间表示的树如下：
ASGNI4(ADDRLP4(nTest1), CNSTI4(1))
然后根据上述的中间表示进行指令模式匹配。
下面的函数
_label
就是进行这样的工作：
#001 static void _label(NODEPTR_TYPE a) {
#002 int c;
#003 struct _state *p;
#004
#005 if (!a)
#006 fatal("_label", "Null tree/n", 0);
#007 STATE_LABEL(a) = p = allocate(sizeof *p, FUNC);
#008 p->rule._stmt = 0;
#009 ...
#010 switch (OP_LABEL(a)) {
#011 case 41: /* ARGB */
#012
#013 ...
#014 case 4149: /* ASGNI4 */
#015 _label(LEFT_CHILD(a));
#016 _label(RIGHT_CHILD(a));
#017 if ( /* stmt: ASGNI4(VREGP,reg) */
#018 LEFT_CHILD(a)->op == 711 /* VREGP */
#019 ) {
#020 c = ((struct _state *)(RIGHT_CHILD(a)->x.state))->cost[_reg_NT] + 0;
#021 if (c + 0 < p->cost[_stmt_NT]) {
#022 p->cost[_stmt_NT] = c + 0;
#023 p->rule._stmt = 6;
#024 }
#025 }
#026 if ( /* stmt: ASGNI4(addr,ADDI4(mem,con1)) */
#027 RIGHT_CHILD(a)->op == 4405 /* ADDI4 */
#028 ) {
#029 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#030 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_con1_NT] + (memop(a));
#031 if (c + 0 < p->cost[_stmt_NT]) {
#032 p->cost[_stmt_NT] = c + 0;
#033 p->rule._stmt = 14;
#034 }
#035 }
#036 if ( /* stmt: ASGNI4(addr,ADDU4(mem,con1)) */
#037 RIGHT_CHILD(a)->op == 4406 /* ADDU4 */
#038 ) {
#039 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#040 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_con1_NT] + (memop(a));
#041 if (c + 0 < p->cost[_stmt_NT]) {
#042 p->cost[_stmt_NT] = c + 0;
#043 p->rule._stmt = 15;
#044 }
#045 }
#046 if ( /* stmt: ASGNI4(addr,SUBI4(mem,con1)) */
#047 RIGHT_CHILD(a)->op == 4421 /* SUBI4 */
#048 ) {
#049 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#050 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_con1_NT] + (memop(a));
#051 if (c + 0 < p->cost[_stmt_NT]) {
#052 p->cost[_stmt_NT] = c + 0;
#053 p->rule._stmt = 17;
#054 }
#055 }
#056 if ( /* stmt: ASGNI4(addr,SUBU4(mem,con1)) */
#057 RIGHT_CHILD(a)->op == 4422 /* SUBU4 */
#058 ) {
#059 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#060 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_con1_NT] + (memop(a));
#061 if (c + 0 < p->cost[_stmt_NT]) {
#062 p->cost[_stmt_NT] = c + 0;
#063 p->rule._stmt = 18;
#064 }
#065 }
#066 if ( /* stmt: ASGNI4(addr,ADDI4(mem,rc)) */
#067 RIGHT_CHILD(a)->op == 4405 /* ADDI4 */
#068 ) {
#069 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#070 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_rc_NT] + (memop(a));
#071 if (c + 0 < p->cost[_stmt_NT]) {
#072 p->cost[_stmt_NT] = c + 0;
#073 p->rule._stmt = 20;
#074 }
#075 }
#076 if ( /* stmt: ASGNI4(addr,SUBI4(mem,rc)) */
#077 RIGHT_CHILD(a)->op == 4421 /* SUBI4 */
#078 ) {
#079 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#080 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_rc_NT] + (memop(a));
#081 if (c + 0 < p->cost[_stmt_NT]) {
#082 p->cost[_stmt_NT] = c + 0;
#083 p->rule._stmt = 21;
#084 }
#085 }
#086 if ( /* stmt: ASGNI4(addr,BANDI4(mem,rc)) */
#087 RIGHT_CHILD(a)->op == 4485 /* BANDI4 */
#088 ) {
#089 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#090 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_rc_NT] + (memop(a));
#091 if (c + 0 < p->cost[_stmt_NT]) {
#092 p->cost[_stmt_NT] = c + 0;
#093 p->rule._stmt = 24;
#094 }
#095 }
#096 if ( /* stmt: ASGNI4(addr,BORI4(mem,rc)) */
#097 RIGHT_CHILD(a)->op == 4517 /* BORI4 */
#098 ) {
#099 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#100 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_rc_NT] + (memop(a));
#101 if (c + 0 < p->cost[_stmt_NT]) {
#102 p->cost[_stmt_NT] = c + 0;
#103 p->rule._stmt = 25;
#104 }
#105 }
#106 if ( /* stmt: ASGNI4(addr,BXORI4(mem,rc)) */
#107 RIGHT_CHILD(a)->op == 4533 /* BXORI4 */
#108 ) {
#109 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#110 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_rc_NT] + (memop(a));
#111 if (c + 0 < p->cost[_stmt_NT]) {
#112 p->cost[_stmt_NT] = c + 0;
#113 p->rule._stmt = 26;
#114 }
#115 }
#116 if ( /* stmt: ASGNI4(addr,BCOMI4(mem)) */
#117 RIGHT_CHILD(a)->op == 4501 /* BCOMI4 */
#118 ) {
#119 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#120 [_mem_NT] + (memop(a));
#121 if (c + 0 < p->cost[_stmt_NT]) {
#122 p->cost[_stmt_NT] = c + 0;
#123 p->rule._stmt = 30;
#124 }
#125 }
#126 if ( /* stmt: ASGNI4(addr,NEGI4(mem)) */
#127 RIGHT_CHILD(a)->op == 4293 /* NEGI4 */
#128 ) {
#129 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#130 [_mem_NT] + (memop(a));
#131 if (c + 0 < p->cost[_stmt_NT]) {
#132 p->cost[_stmt_NT] = c + 0;
#133 p->rule._stmt = 32;
#134 }
#135 }
#136 if ( /* stmt: ASGNI4(addr,LSHI4(mem,con5)) */
#137 RIGHT_CHILD(a)->op == 4437 /* LSHI4 */
#138 ) {
#139 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#140 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_con5_NT] + (memop(a));
#141 if (c + 0 < p->cost[_stmt_NT]) {
#142 p->cost[_stmt_NT] = c + 0;
#143 p->rule._stmt = 33;
#144 }
#145 }
#146 if ( /* stmt: ASGNI4(addr,LSHU4(mem,con5)) */
#147 RIGHT_CHILD(a)->op == 4438 /* LSHU4 */
#148 ) {
#149 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#150 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_con5_NT] + (memop(a));
#151 if (c + 0 < p->cost[_stmt_NT]) {
#152 p->cost[_stmt_NT] = c + 0;
#153 p->rule._stmt = 34;
#154 }
#155 }
#156 if ( /* stmt: ASGNI4(addr,RSHI4(mem,con5)) */
#157 RIGHT_CHILD(a)->op == 4469 /* RSHI4 */
#158 ) {
#159 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#160 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_con5_NT] + (memop(a));
#161 if (c + 0 < p->cost[_stmt_NT]) {
#162 p->cost[_stmt_NT] = c + 0;
#163 p->rule._stmt = 35;
#164 }
#165 }
#166 if ( /* stmt: ASGNI4(addr,RSHU4(mem,con5)) */
#167 RIGHT_CHILD(a)->op == 4470 /* RSHU4 */
#168 ) {
#169 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost
#170 [_mem_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_con5_NT] + (memop(a));
#171 if (c + 0 < p->cost[_stmt_NT]) {
#172 p->cost[_stmt_NT] = c + 0;
#173 p->rule._stmt = 36;
#174 }
#175 }
#176 /* stmt: ASGNI4(addr,rc) */
#177 c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(RIGHT_CHILD(a)->x.state))->cost[_rc_NT] + 1;
#178 if (c + 0 < p->cost[_stmt_NT]) {
#179 p->cost[_stmt_NT] = c + 0;
#180 p->rule._stmt = 39;
#181 }
#182 break;
#183 ...
#184
第
7
行创建一个节点的状态空间。
第
10
行根据节点的类型选择不同的操作，也就是进行指令选择。
由分析中间表示树可知，第一个节点是
ASGNI4
，所以就运行到第
14
行那里。
第
15
行进行左子树递归处理。
第
16
行进行右子树递归处理。
接着下来的程序就会根据左子树和右子树的类型，从下面的语句里选择出合适的指令，
stmt: ASGNI4(VREGP,reg)
stmt: ASGNI4(addr,ADDI4(mem,con1))
stmt: ASGNI4(addr,ADDU4(mem,con1))
stmt: ASGNI4(addr,SUBI4(mem,con1))
stmt: ASGNI4(addr,SUBU4(mem,con1))
stmt: ASGNI4(addr,ADDI4(mem,rc))
stmt: ASGNI4(addr,SUBI4(mem,rc))
stmt: ASGNI4(addr,BANDI4(mem,rc))
stmt: ASGNI4(addr,BORI4(mem,rc))
stmt: ASGNI4(addr,BXORI4(mem,rc))
stmt: ASGNI4(addr,BCOMI4(mem))
stmt: ASGNI4(addr,NEGI4(mem))
stmt: ASGNI4(addr,LSHI4(mem,con5))
stmt: ASGNI4(addr,LSHU4(mem,con5))
stmt: ASGNI4(addr,RSHI4(mem,con5))
stmt: ASGNI4(addr,RSHU4(mem,con5))
stmt: ASGNI4(addr,rc)
由于中间表示就可以知道从上面的指令里是选择最后一条指令生成，所以在第
179
行里设置了这条指令的开销，第
180
行里设置指令编码为
39
。
通过这样的计算，就可以选择出合适的指令。有了这两个值，后面会通过其它函数来生成上面的目标代码，下一次再解释怎么样生成目标代码。
