Kannel: Open Source WAP and SMS gateway  $Revision: 5037 $
wsopt.c
Go to the documentation of this file.
1 /* ====================================================================
2  * The Kannel Software License, Version 1.0
3  *
4  * Copyright (c) 2001-2016 Kannel Group
5  * Copyright (c) 1998-2001 WapIT Ltd.
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Kannel Group (http://www.kannel.org/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Kannel" and "Kannel Group" must not be used to
28  * endorse or promote products derived from this software without
29  * prior written permission. For written permission, please
30  * contact org@kannel.org.
31  *
32  * 5. Products derived from this software may not be called "Kannel",
33  * nor may "Kannel" appear in their name, without prior written
34  * permission of the Kannel Group.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE KANNEL GROUP OR ITS CONTRIBUTORS
40  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
41  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
42  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
43  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
44  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
45  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
46  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
47  * ====================================================================
48  *
49  * This software consists of voluntary contributions made by many
50  * individuals on behalf of the Kannel Group. For more information on
51  * the Kannel Group, please see <http://www.kannel.org/>.
52  *
53  * Portions of this software are based upon software originally written at
54  * WapIT Ltd., Helsinki, Finland for the Kannel project.
55  */
56 
57 /*
58  *
59  * wsopt.c
60  *
61  * Author: Markku Rossi <mtr@iki.fi>
62  *
63  * Copyright (c) 1999-2000 WAPIT OY LTD.
64  * All rights reserved.
65  *
66  * Optimizations for the WMLScript symbolic assembler.
67  *
68  */
69 
70 #include "wsint.h"
71 #include "wsasm.h"
72 
73 /* TODO: liveness analyzation */
74 /* TODO: jumps to return or return_es */
75 /* TODO: remove empty labels (helps peephole opt) */
76 /* TODO: i++; becomes "load, incr, pop", optimize to just incr. */
77 /* TODO: { const; tjump } -> { jump or nothing } */
78 
79 /********************* Optimization functions ***************************/
80 
82 {
83  WsAsmIns *i;
84  WsBool change = WS_TRUE;
85  unsigned int count = 0;
86 
87  ws_info(compiler, "optimize: jumps to jumps");
88 
89  while (change) {
90  count++;
91  change = WS_FALSE;
92 
93  for (i = compiler->asm_head; i; i = i->next) {
94  WsAsmIns * j;
95 
96  if (!WS_ASM_P_BRANCH(i))
97  continue;
98 
99  /* Find the next instruction following the label. */
100  for (j = i->ws_label; j && j->type == WS_ASM_P_LABEL; j = j->next)
101  ;
102 
103  if (j == NULL || j->type != WS_ASM_P_JUMP)
104  /* Can't optimize this case. */
105  continue;
106 
107  /* We can optimize the jump `i' directly to the label of
108  `j'. We must remember to update the reference counts
109  too. */
110 
111  i->ws_label->ws_label_refcount--;
112  j->ws_label->ws_label_refcount++;
113 
114  i->ws_label = j->ws_label;
115  change = WS_TRUE;
116  }
117  }
118 
119  return count > 1;
120 }
121 
122 
124 {
125  WsAsmIns *i;
126  WsBool change = WS_FALSE;
127 
128  ws_info(compiler, "optimize: jumps to next instruction");
129 
130  for (i = compiler->asm_head; i; i = i->next) {
131  WsAsmIns * j;
132 
133  if (i->type != WS_ASM_P_JUMP)
134  continue;
135 
136  for (j = i->next;
137  j && j->type == WS_ASM_P_LABEL && i->ws_label != j;
138  j = j->next)
139  ;
140 
141  if (i->ws_label != j)
142  /* Nop. */
143  continue;
144 
145  /* Remove the jump instruction `i'. */
146 
147  change = WS_TRUE;
148  i->ws_label->ws_label_refcount--;
149 
150  if (i->next)
151  i->next->prev = i->prev;
152  else
153  compiler->asm_tail = i->prev;
154 
155  if (i->prev)
156  i->prev->next = i->next;
157  else
158  compiler->asm_head = i->next;
159 
160  /* Continue from the label `j'. */
161  i = j;
162  }
163 
164  return change;
165 }
166 
167 
169 {
170  WsBool change = WS_FALSE;
171  WsAsmIns *i;
172 
173  ws_info(compiler, "optimize: dead code");
174 
175  for (i = compiler->asm_head; i; i = i->next) {
176  WsAsmIns * j;
177 
178  if (!(i->type == WS_ASM_P_JUMP ||
179  i->type == WS_ASM_RETURN ||
180  i->type == WS_ASM_RETURN_ES))
181  continue;
182 
183  /* Skip until the next referenced label is found. */
184  for (j = i->next;
185  j && (j->type != WS_ASM_P_LABEL || j->ws_label_refcount == 0);
186  j = j->next) {
187  /* Update label reference counts in the deleted block. */
188  if (WS_ASM_P_BRANCH(j))
189  j->ws_label->ws_label_refcount--;
190  }
191 
192  if (j == i->next)
193  /* Nothing to delete. */
194  continue;
195 
196  /* Delete everything between `i' and `j'. */
197  i->next = j;
198  if (j)
199  j->prev = i;
200  else
201  compiler->asm_tail = i;
202 
203  change = WS_TRUE;
204  }
205 
206  return change;
207 }
208 
209 
211 {
212  WsBool change = WS_FALSE;
213  WsAsmIns *i, *i2, *prev;
214  WsAsmIns *new;
215 
216  ws_info(compiler, "optimize: peephole");
217 
218  prev = NULL;
219  i = compiler->asm_head;
220  while (i) {
221  /* Two instructions wide peephole. */
222  if (i->next) {
223  i2 = i->next;
224 
225  /*
226  * {load*,const*} => -
227  * pop
228  */
229  if (i2->type == WS_ASM_POP
230  && (i->type == WS_ASM_P_LOAD_VAR
231  || i->type == WS_ASM_P_LOAD_CONST
232  || i->type == WS_ASM_CONST_0
233  || i->type == WS_ASM_CONST_1
234  || i->type == WS_ASM_CONST_M1
235  || i->type == WS_ASM_CONST_ES
236  || i->type == WS_ASM_CONST_INVALID
237  || i->type == WS_ASM_CONST_TRUE
238  || i->type == WS_ASM_CONST_FALSE)) {
239  /* Remove both instructions. */
240  change = WS_TRUE;
241 
242  if (prev)
243  prev->next = i2->next;
244  else
245  compiler->asm_head = i2->next;
246 
247  if (i2->next)
248  i2->next->prev = prev;
249  else
250  compiler->asm_tail = prev;
251 
252  i = i2->next;
253  continue;
254  }
255 
256  /*
257  * const_es => return_es
258  * return
259  */
260  if (i2->type == WS_ASM_RETURN && i->type == WS_ASM_CONST_ES) {
261  /* Replace with WS_ASM_RETURN_ES */
262  new = ws_asm_ins(compiler, i->line, WS_ASM_RETURN_ES);
263  if (new) {
264  change = WS_TRUE;
265 
266  if (prev)
267  prev->next = new;
268  else
269  compiler->asm_head = new;
270 
271  new->prev = prev;
272  new->next = i2->next;
273 
274  if (new->next)
275  new->next->prev = new;
276  else
277  compiler->asm_tail = new;
278 
279  i = new;
280  continue;
281  }
282  }
283  }
284 
285  /* Move forward. */
286  prev = i;
287  i = i->next;
288  }
289 
290  /* The interpreter will by default return the empty string if a
291  * function ends without a return statement, so returning the
292  * empty string at the end of a function is never useful. */
293  if (compiler->asm_tail && compiler->asm_tail->type == WS_ASM_RETURN_ES) {
294  compiler->asm_tail = compiler->asm_tail->prev;
295  if (compiler->asm_tail == NULL)
296  compiler->asm_head = NULL;
297  else
298  compiler->asm_tail->next = NULL;
299  }
300 
301  return change;
302 }
303 
304 /*
305  * Remove conversions that are followed by an opcode that does
306  * that conversion automatically anyway.
307  */
308 static WsBool opt_conv(WsCompilerPtr compiler)
309 {
310  WsBool change = WS_FALSE;
311  WsAsmIns *i, *next, *prev;
312 
313  ws_info(compiler, "optimize: peephole");
314 
315  prev = NULL;
316  i = compiler->asm_head;
317  while (i) {
318  if (i->type == WS_ASM_TOBOOL) {
319  next = i->next;
320 
321  /* Skip labels. They're not going to affect which instruction
322  * gets executed after this TOBOOL. */
323  while (next != NULL && next->type == WS_ASM_P_LABEL)
324  next = next->next;
325 
326  if (next != NULL &&
327  (next->type == WS_ASM_P_TJUMP ||
328  next->type == WS_ASM_NOT ||
329  next->type == WS_ASM_SCAND ||
330  next->type == WS_ASM_SCOR ||
331  next->type == WS_ASM_TOBOOL ||
332  next->type == WS_ASM_POP)) {
333  /* The next instruction will automatically convert its
334  * operand to boolean, or does not care about its operand
335  * (POP), so the TOBOOL is not necessary. Delete it. */
336  change = WS_TRUE;
337 
338  /* Use i->next here because next might have been incremented
339  * past a label, which we do not want to delete. */
340  if (prev)
341  prev->next = i->next;
342  else
343  compiler->asm_head = i->next;
344 
345  if (i->next)
346  i->next->prev = prev;
347  else
348  compiler->asm_tail = prev;
349  }
350  }
351 
352  prev = i;
353  i = i->next;
354  }
355 
356  return change;
357 }
358 
359 
360 /********************* Global entry point *******************************/
361 
363 {
364  WsBool change = WS_TRUE;
365 
366  /* While we manage to change the assembler, perform the requested
367  optimizations. */
368  while (change) {
369  change = WS_FALSE;
370 
371  /* Useless conversions */
372  if (!compiler->params.no_opt_conv && opt_conv(compiler))
373  change = WS_TRUE;
374 
375  /* Peephole. */
376  if (!compiler->params.no_opt_peephole && opt_peephole(compiler))
377  change = WS_TRUE;
378 
379  /* Jumps to jump instructions. */
380  if (!compiler->params.no_opt_jumps_to_jumps
381  && opt_jumps_to_jumps(compiler))
382  change = WS_TRUE;
383 
384  /* Jumps to the next instruction. */
386  && opt_jumps_to_next_instruction(compiler))
387  change = WS_TRUE;
388 
389  /* Unreachable code. */
390  if (!compiler->params.no_opt_dead_code && opt_dead_code(compiler))
391  change = WS_TRUE;
392  }
393 }
#define WS_ASM_CONST_TRUE
Definition: wsasm.h:175
#define WS_ASM_SCOR
Definition: wsasm.h:207
unsigned int no_opt_dead_code
Definition: ws.h:138
Definition: wsint.h:131
#define WS_ASM_P_LABEL
Definition: wsasm.h:225
unsigned int no_opt_conv
Definition: ws.h:141
static WsBool opt_jumps_to_jumps(WsCompilerPtr compiler)
Definition: wsopt.c:81
#define WS_ASM_NOT
Definition: wsasm.h:205
#define WS_ASM_RETURN
Definition: wsasm.h:215
WsAsmIns * asm_head
Definition: wsint.h:224
unsigned int no_opt_jumps_to_next_instruction
Definition: ws.h:135
WsAsmIns * asm_tail
Definition: wsint.h:225
#define WS_ASM_CONST_INVALID
Definition: wsasm.h:174
static WsBool opt_dead_code(WsCompilerPtr compiler)
Definition: wsopt.c:168
#define WS_ASM_CONST_M1
Definition: wsasm.h:172
#define WS_ASM_CONST_FALSE
Definition: wsasm.h:176
static WsBool opt_peephole(WsCompilerPtr compiler)
Definition: wsopt.c:210
#define WS_ASM_P_JUMP
Definition: wsasm.h:226
#define WS_ASM_P_TJUMP
Definition: wsasm.h:227
WsUInt16 type
Definition: wsasm.h:257
struct WsAsmInsRec * next
Definition: wsasm.h:255
#define WS_ASM_P_LOAD_VAR
Definition: wsasm.h:231
static WsBool opt_jumps_to_next_instruction(WsCompilerPtr compiler)
Definition: wsopt.c:123
WsAsmIns * ws_asm_ins(WsCompiler *compiler, WsUInt32 line, WsUInt8 opcode)
Definition: wsasm.c:920
#define WS_ASM_TOBOOL
Definition: wsasm.h:208
#define WS_ASM_POP
Definition: wsasm.h:210
unsigned int no_opt_peephole
Definition: ws.h:128
struct WsAsmInsRec * prev
Definition: wsasm.h:256
WsUInt32 line
Definition: wsasm.h:260
WsBool
Definition: wsint.h:128
#define WS_ASM_CONST_1
Definition: wsasm.h:171
static WsBool opt_conv(WsCompilerPtr compiler)
Definition: wsopt.c:308
void ws_asm_optimize(WsCompilerPtr compiler)
Definition: wsopt.c:362
#define WS_ASM_P_BRANCH(ins)
Definition: wsasm.h:238
WsCompilerParams params
Definition: wsint.h:193
#define WS_ASM_P_LOAD_CONST
Definition: wsasm.h:234
#define WS_ASM_CONST_0
Definition: wsasm.h:170
void ws_info(WsCompilerPtr compiler, char *message,...)
Definition: wserror.c:74
#define WS_ASM_CONST_ES
Definition: wsasm.h:173
#define WS_ASM_RETURN_ES
Definition: wsasm.h:216
unsigned int no_opt_jumps_to_jumps
Definition: ws.h:132
#define WS_ASM_SCAND
Definition: wsasm.h:206
See file LICENSE for details about the license agreement for using, modifying, copying or deriving work from this software.