blob: 7f1628dd6f5db755aec8d5a48a26925e1eff4e84 [file] [log] [blame]
sewardja1a370f2004-08-17 13:31:55 +00001
2/*---------------------------------------------------------------*/
3/*--- ---*/
4/*--- This file (ir/iropt.c) is ---*/
sewardjdbcfae72005-08-02 11:14:04 +00005/*--- Copyright (C) OpenWorks LLP. All rights reserved. ---*/
sewardja1a370f2004-08-17 13:31:55 +00006/*--- ---*/
7/*---------------------------------------------------------------*/
8
sewardjf8ed9d82004-11-12 17:40:23 +00009/*
10 This file is part of LibVEX, a library for dynamic binary
11 instrumentation and translation.
12
sewardj496a58d2005-03-20 18:44:44 +000013 Copyright (C) 2004-2005 OpenWorks LLP.
sewardjf8ed9d82004-11-12 17:40:23 +000014
15 This program is free software; you can redistribute it and/or modify
16 it under the terms of the GNU General Public License as published by
17 the Free Software Foundation; Version 2 dated June 1991 of the
18 license.
19
20 This program is distributed in the hope that it will be useful,
21 but WITHOUT ANY WARRANTY; without even the implied warranty of
22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or liability
23 for damages. See the GNU General Public License for more details.
24
25 Neither the names of the U.S. Department of Energy nor the
26 University of California nor the names of its contributors may be
27 used to endorse or promote products derived from this software
28 without prior written permission.
29
30 You should have received a copy of the GNU General Public License
31 along with this program; if not, write to the Free Software
32 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
33 USA.
34*/
35
sewardja1a370f2004-08-17 13:31:55 +000036#include "libvex_basictypes.h"
sewardjedf4d692004-08-17 13:52:58 +000037#include "libvex_ir.h"
sewardja1a370f2004-08-17 13:31:55 +000038#include "libvex.h"
39
40#include "main/vex_util.h"
sewardj08613742004-10-25 13:01:45 +000041#include "main/vex_globals.h"
sewardjedf4d692004-08-17 13:52:58 +000042#include "ir/iropt.h"
sewardja1a370f2004-08-17 13:31:55 +000043
sewardjd0863ff2004-10-23 00:22:32 +000044
sewardj088bcb42004-08-19 17:16:52 +000045/* Set to 1 for lots of debugging output. */
46#define DEBUG_IROPT 0
47
sewardja1a370f2004-08-17 13:31:55 +000048
sewardj08210532004-12-29 17:09:11 +000049/* What iropt does, 29 Dec 04.
50
51 It takes an IRBB and produces a new one with the same meaning,
52 defined thus:
53
54 After execution of the new BB, all guest state and guest memory is
55 the same as after execution of the original. This is true
56 regardless of how the block was exited (at the end vs side exit).
57
58 In addition, parts of the guest state will be identical to that
59 created by execution of the original at the following observation
60 points:
61
62 * In a dirty helper call, any parts of the guest state that the
63 helper states that it reads or modifies will be up to date.
64 Also, guest memory will be up to date. Parts of the guest state
65 not marked as being read or modified by the helper cannot be
66 assumed to be up-to-date at the point where the helper is called.
67
68 * Immediately prior to any load or store, those parts of the guest
69 state marked as requiring precise exceptions will be up to date.
70 Also, guest memory will be up to date. Parts of the guest state
71 not marked as requiring precise exceptions cannot be assumed to
72 be up-to-date at the point of the load/store.
73
74 The relative order of loads and stores (including loads/stores of
75 guest memory done by dirty helpers annotated as such) is not
76 changed. However, the relative order of loads with no intervening
77 stores/modifies may be changed.
78
79 Transformation order
80 ~~~~~~~~~~~~~~~~~~~~
81
82 There are three levels of optimisation, controlled by
83 vex_control.iropt_level. Define first:
84
85 "Cheap transformations" are the following sequence:
86 * Redundant-Get removal
87 * Redundant-Put removal
88 * Constant propagation/folding
89 * Dead code removal
90 * Specialisation of clean helper functions
91 * Dead code removal
92
93 "Expensive transformations" are the following sequence:
94 * CSE
95 * Folding of add/sub chains
96 * Redundant-GetI removal
97 * Redundant-PutI removal
98 * Dead code removal
sewardj08210532004-12-29 17:09:11 +000099
100 Then the transformations are as follows, as defined by
101 vex_control.iropt_level:
102
103 Level 0:
104 * Flatten into atomic form.
105
106 Level 1: the following sequence:
107 * Flatten into atomic form.
108 * Cheap transformations.
sewardj08210532004-12-29 17:09:11 +0000109
110 Level 2: the following sequence
111 * Flatten into atomic form.
112 * Cheap transformations.
113 * If block contains GetI or PutI, Expensive transformations.
114 * Try unrolling loops. Three possible outcomes:
115 - No effect: do nothing more.
116 - Unrolled a loop, and block does not contain GetI or PutI:
117 Do: * CSE
118 * Dead code removal
sewardj08210532004-12-29 17:09:11 +0000119 - Unrolled a loop, and block contains GetI or PutI:
120 Do: * Expensive transformations
121 * Cheap transformations
sewardj08210532004-12-29 17:09:11 +0000122*/
123
sewardj98430292004-12-29 17:34:50 +0000124/* Implementation notes, 29 Dec 04.
125
126 TODO (important): I think rPutI removal ignores precise exceptions
127 and is therefore in a sense, wrong. In the sense that PutIs are
128 assumed not to write parts of the guest state that we need to have
129 up-to-date at loads/stores. So far on x86 guest that has not
130 mattered since indeed only the x87 FP registers and tags are
131 accessed using GetI/PutI, and there is no need so far for them to
132 be up to date at mem exception points. The rPutI pass should be
133 fixed.
sewardjfb44d552004-10-25 09:48:47 +0000134
sewardj4c5f6d52004-10-26 13:25:33 +0000135 TODO: improve pessimistic handling of precise exceptions
136 in the tree builder.
137
sewardjfb44d552004-10-25 09:48:47 +0000138 TODO: check interaction of rGetI and dirty helpers.
sewardjc0b42282004-10-12 13:44:12 +0000139
140 F64i constants are treated differently from other constants.
141 They are not regarded as atoms, and instead lifted off and
142 bound to temps. This allows them to participate in CSE, which
143 is important for getting good performance for x86 guest code.
sewardj695cff92004-10-13 14:50:14 +0000144
sewardja5aa9cf2004-10-15 22:56:38 +0000145 CSE up F64 literals (already doing F64is)
sewardj4c5f6d52004-10-26 13:25:33 +0000146
147 CSE: consider carefully the requirement for precise exns
sewardj98430292004-12-29 17:34:50 +0000148 prior to making CSE any more aggressive. */
sewardjc0b42282004-10-12 13:44:12 +0000149
150
sewardja1a370f2004-08-17 13:31:55 +0000151/*---------------------------------------------------------------*/
152/*--- Finite mappery, of a sort ---*/
153/*---------------------------------------------------------------*/
154
sewardj08210532004-12-29 17:09:11 +0000155/* General map from HWord-sized thing HWord-sized thing. Could be by
156 hashing, but it's not clear whether or not this would really be any
157 faster. */
sewardja1a370f2004-08-17 13:31:55 +0000158
159typedef
160 struct {
161 Bool* inuse;
sewardjea602bc2004-10-14 21:40:12 +0000162 HWord* key;
163 HWord* val;
sewardja1a370f2004-08-17 13:31:55 +0000164 Int size;
165 Int used;
166 }
sewardjea602bc2004-10-14 21:40:12 +0000167 HashHW;
sewardja1a370f2004-08-17 13:31:55 +0000168
sewardjea602bc2004-10-14 21:40:12 +0000169static HashHW* newHHW ( void )
sewardja1a370f2004-08-17 13:31:55 +0000170{
sewardjea602bc2004-10-14 21:40:12 +0000171 HashHW* h = LibVEX_Alloc(sizeof(HashHW));
sewardj29632392004-08-22 02:38:11 +0000172 h->size = 8;
sewardja1a370f2004-08-17 13:31:55 +0000173 h->used = 0;
174 h->inuse = LibVEX_Alloc(h->size * sizeof(Bool));
sewardjea602bc2004-10-14 21:40:12 +0000175 h->key = LibVEX_Alloc(h->size * sizeof(HWord));
176 h->val = LibVEX_Alloc(h->size * sizeof(HWord));
sewardja1a370f2004-08-17 13:31:55 +0000177 return h;
178}
179
180
sewardj84be7372004-08-18 13:59:33 +0000181/* Look up key in the map. */
sewardja1a370f2004-08-17 13:31:55 +0000182
sewardjea602bc2004-10-14 21:40:12 +0000183static Bool lookupHHW ( HashHW* h, /*OUT*/HWord* val, HWord key )
sewardja1a370f2004-08-17 13:31:55 +0000184{
185 Int i;
sewardj08210532004-12-29 17:09:11 +0000186 /* vex_printf("lookupHHW(%llx)\n", key ); */
sewardja1a370f2004-08-17 13:31:55 +0000187 for (i = 0; i < h->used; i++) {
188 if (h->inuse[i] && h->key[i] == key) {
sewardj39e3f242004-08-18 16:54:52 +0000189 if (val)
190 *val = h->val[i];
sewardja1a370f2004-08-17 13:31:55 +0000191 return True;
192 }
193 }
194 return False;
195}
196
197
sewardja1a370f2004-08-17 13:31:55 +0000198/* Add key->val to the map. Replaces any existing binding for key. */
199
sewardjea602bc2004-10-14 21:40:12 +0000200static void addToHHW ( HashHW* h, HWord key, HWord val )
sewardja1a370f2004-08-17 13:31:55 +0000201{
202 Int i, j;
sewardj08210532004-12-29 17:09:11 +0000203 /* vex_printf("addToHHW(%llx, %llx)\n", key, val); */
sewardja1a370f2004-08-17 13:31:55 +0000204
205 /* Find and replace existing binding, if any. */
206 for (i = 0; i < h->used; i++) {
207 if (h->inuse[i] && h->key[i] == key) {
208 h->val[i] = val;
209 return;
210 }
211 }
212
213 /* Ensure a space is available. */
214 if (h->used == h->size) {
215 /* Copy into arrays twice the size. */
216 Bool* inuse2 = LibVEX_Alloc(2 * h->size * sizeof(Bool));
sewardjea602bc2004-10-14 21:40:12 +0000217 HWord* key2 = LibVEX_Alloc(2 * h->size * sizeof(HWord));
218 HWord* val2 = LibVEX_Alloc(2 * h->size * sizeof(HWord));
sewardja1a370f2004-08-17 13:31:55 +0000219 for (i = j = 0; i < h->size; i++) {
220 if (!h->inuse[i]) continue;
221 inuse2[j] = True;
222 key2[j] = h->key[i];
223 val2[j] = h->val[i];
224 j++;
225 }
226 h->used = j;
227 h->size *= 2;
228 h->inuse = inuse2;
229 h->key = key2;
230 h->val = val2;
231 }
232
233 /* Finally, add it. */
234 vassert(h->used < h->size);
235 h->inuse[h->used] = True;
236 h->key[h->used] = key;
sewardj84be7372004-08-18 13:59:33 +0000237 h->val[h->used] = val;
sewardja1a370f2004-08-17 13:31:55 +0000238 h->used++;
239}
240
sewardj84be7372004-08-18 13:59:33 +0000241
sewardjd7cb8532004-08-17 23:59:23 +0000242/*---------------------------------------------------------------*/
sewardj08210532004-12-29 17:09:11 +0000243/*--- Flattening out a BB into atomic SSA form ---*/
sewardjd7cb8532004-08-17 23:59:23 +0000244/*---------------------------------------------------------------*/
245
sewardje80679a2004-09-21 23:00:11 +0000246/* Non-critical helper, heuristic for reducing the number of tmp-tmp
247 copies made by flattening. If in doubt return False. */
248
249static Bool isFlat ( IRExpr* e )
250{
sewardj695cff92004-10-13 14:50:14 +0000251 if (e->tag == Iex_Get)
252 return True;
sewardje80679a2004-09-21 23:00:11 +0000253 if (e->tag == Iex_Binop)
sewardj496a58d2005-03-20 18:44:44 +0000254 return toBool( isIRAtom(e->Iex.Binop.arg1)
255 && isIRAtom(e->Iex.Binop.arg2) );
sewardjaf1ceca2005-06-30 23:31:27 +0000256 if (e->tag == Iex_Load)
257 return isIRAtom(e->Iex.Load.addr);
sewardje80679a2004-09-21 23:00:11 +0000258 return False;
259}
260
sewardjd7cb8532004-08-17 23:59:23 +0000261/* Flatten out 'ex' so it is atomic, returning a new expression with
262 the same value, after having appended extra IRTemp assignments to
263 the end of 'bb'. */
264
265static IRExpr* flatten_Expr ( IRBB* bb, IRExpr* ex )
266{
267 Int i;
268 IRExpr** newargs;
269 IRType ty = typeOfIRExpr(bb->tyenv, ex);
270 IRTemp t1;
271
272 switch (ex->tag) {
273
sewardjd7217032004-08-19 10:49:10 +0000274 case Iex_GetI:
275 t1 = newIRTemp(bb->tyenv, ty);
276 addStmtToIRBB(bb, IRStmt_Tmp(t1,
sewardj2d3f77c2004-09-22 23:49:09 +0000277 IRExpr_GetI(ex->Iex.GetI.descr,
sewardjeeac8412004-11-02 00:26:55 +0000278 flatten_Expr(bb, ex->Iex.GetI.ix),
sewardj2d3f77c2004-09-22 23:49:09 +0000279 ex->Iex.GetI.bias)));
sewardjd7217032004-08-19 10:49:10 +0000280 return IRExpr_Tmp(t1);
281
sewardjd7cb8532004-08-17 23:59:23 +0000282 case Iex_Get:
283 t1 = newIRTemp(bb->tyenv, ty);
284 addStmtToIRBB(bb,
285 IRStmt_Tmp(t1, ex));
286 return IRExpr_Tmp(t1);
287
288 case Iex_Binop:
289 t1 = newIRTemp(bb->tyenv, ty);
290 addStmtToIRBB(bb, IRStmt_Tmp(t1,
291 IRExpr_Binop(ex->Iex.Binop.op,
292 flatten_Expr(bb, ex->Iex.Binop.arg1),
293 flatten_Expr(bb, ex->Iex.Binop.arg2))));
294 return IRExpr_Tmp(t1);
295
296 case Iex_Unop:
297 t1 = newIRTemp(bb->tyenv, ty);
298 addStmtToIRBB(bb, IRStmt_Tmp(t1,
299 IRExpr_Unop(ex->Iex.Unop.op,
300 flatten_Expr(bb, ex->Iex.Unop.arg))));
301 return IRExpr_Tmp(t1);
302
sewardjaf1ceca2005-06-30 23:31:27 +0000303 case Iex_Load:
sewardjd7cb8532004-08-17 23:59:23 +0000304 t1 = newIRTemp(bb->tyenv, ty);
305 addStmtToIRBB(bb, IRStmt_Tmp(t1,
sewardjaf1ceca2005-06-30 23:31:27 +0000306 IRExpr_Load(ex->Iex.Load.end,
307 ex->Iex.Load.ty,
308 flatten_Expr(bb, ex->Iex.Load.addr))));
sewardjd7cb8532004-08-17 23:59:23 +0000309 return IRExpr_Tmp(t1);
310
311 case Iex_CCall:
sewardj695cff92004-10-13 14:50:14 +0000312 newargs = sopyIRExprVec(ex->Iex.CCall.args);
sewardjd7cb8532004-08-17 23:59:23 +0000313 for (i = 0; newargs[i]; i++)
314 newargs[i] = flatten_Expr(bb, newargs[i]);
315 t1 = newIRTemp(bb->tyenv, ty);
316 addStmtToIRBB(bb, IRStmt_Tmp(t1,
sewardj8ea867b2004-10-30 19:03:02 +0000317 IRExpr_CCall(ex->Iex.CCall.cee,
sewardjd7cb8532004-08-17 23:59:23 +0000318 ex->Iex.CCall.retty,
319 newargs)));
320 return IRExpr_Tmp(t1);
321
322 case Iex_Mux0X:
323 t1 = newIRTemp(bb->tyenv, ty);
324 addStmtToIRBB(bb, IRStmt_Tmp(t1,
325 IRExpr_Mux0X(flatten_Expr(bb, ex->Iex.Mux0X.cond),
326 flatten_Expr(bb, ex->Iex.Mux0X.expr0),
327 flatten_Expr(bb, ex->Iex.Mux0X.exprX))));
328 return IRExpr_Tmp(t1);
329
330 case Iex_Const:
sewardjc0b42282004-10-12 13:44:12 +0000331 /* Lift F64i constants out onto temps so they can be CSEd
332 later. */
333 if (ex->Iex.Const.con->tag == Ico_F64i) {
334 t1 = newIRTemp(bb->tyenv, ty);
335 addStmtToIRBB(bb, IRStmt_Tmp(t1,
336 IRExpr_Const(ex->Iex.Const.con)));
337 return IRExpr_Tmp(t1);
338 } else {
339 /* Leave all other constants alone. */
340 return ex;
341 }
342
sewardjd7cb8532004-08-17 23:59:23 +0000343 case Iex_Tmp:
344 return ex;
345
346 default:
347 vex_printf("\n");
348 ppIRExpr(ex);
349 vex_printf("\n");
350 vpanic("flatten_Expr");
351 }
352}
353
354
355/* Append a completely flattened form of 'st' to the end of 'bb'. */
356
357static void flatten_Stmt ( IRBB* bb, IRStmt* st )
358{
sewardj17442fe2004-09-20 14:54:28 +0000359 Int i;
360 IRExpr *e1, *e2;
361 IRDirty *d, *d2;
sewardjd7cb8532004-08-17 23:59:23 +0000362 switch (st->tag) {
363 case Ist_Put:
sewardj496a58d2005-03-20 18:44:44 +0000364 if (isIRAtom(st->Ist.Put.data)) {
sewardj49651f42004-10-28 22:11:04 +0000365 /* optimisation to reduce the amount of heap wasted
366 by the flattener */
367 addStmtToIRBB(bb, st);
368 } else {
369 /* general case, always correct */
370 e1 = flatten_Expr(bb, st->Ist.Put.data);
371 addStmtToIRBB(bb, IRStmt_Put(st->Ist.Put.offset, e1));
372 }
sewardjd7cb8532004-08-17 23:59:23 +0000373 break;
sewardjd7cb8532004-08-17 23:59:23 +0000374 case Ist_PutI:
sewardjeeac8412004-11-02 00:26:55 +0000375 e1 = flatten_Expr(bb, st->Ist.PutI.ix);
sewardj2d3f77c2004-09-22 23:49:09 +0000376 e2 = flatten_Expr(bb, st->Ist.PutI.data);
377 addStmtToIRBB(bb, IRStmt_PutI(st->Ist.PutI.descr,
378 e1,
379 st->Ist.PutI.bias,
380 e2));
sewardjd7217032004-08-19 10:49:10 +0000381 break;
sewardjd7cb8532004-08-17 23:59:23 +0000382 case Ist_Tmp:
sewardj6d076362004-09-23 11:06:17 +0000383 if (isFlat(st->Ist.Tmp.data)) {
sewardje80679a2004-09-21 23:00:11 +0000384 /* optimisation, to reduce the number of tmp-tmp
385 copies generated */
386 addStmtToIRBB(bb, st);
387 } else {
388 /* general case, always correct */
sewardj6d076362004-09-23 11:06:17 +0000389 e1 = flatten_Expr(bb, st->Ist.Tmp.data);
sewardje80679a2004-09-21 23:00:11 +0000390 addStmtToIRBB(bb, IRStmt_Tmp(st->Ist.Tmp.tmp, e1));
391 }
sewardjd7cb8532004-08-17 23:59:23 +0000392 break;
sewardjaf1ceca2005-06-30 23:31:27 +0000393 case Ist_Store:
394 e1 = flatten_Expr(bb, st->Ist.Store.addr);
395 e2 = flatten_Expr(bb, st->Ist.Store.data);
396 addStmtToIRBB(bb, IRStmt_Store(st->Ist.Store.end, e1,e2));
sewardjd7cb8532004-08-17 23:59:23 +0000397 break;
sewardj17442fe2004-09-20 14:54:28 +0000398 case Ist_Dirty:
399 d = st->Ist.Dirty.details;
400 d2 = emptyIRDirty();
401 *d2 = *d;
sewardj695cff92004-10-13 14:50:14 +0000402 d2->args = sopyIRExprVec(d2->args);
sewardj17442fe2004-09-20 14:54:28 +0000403 if (d2->mFx != Ifx_None) {
404 d2->mAddr = flatten_Expr(bb, d2->mAddr);
405 } else {
406 vassert(d2->mAddr == NULL);
407 }
sewardjb8385d82004-11-02 01:34:15 +0000408 d2->guard = flatten_Expr(bb, d2->guard);
sewardj17442fe2004-09-20 14:54:28 +0000409 for (i = 0; d2->args[i]; i++)
410 d2->args[i] = flatten_Expr(bb, d2->args[i]);
411 addStmtToIRBB(bb, IRStmt_Dirty(d2));
412 break;
sewardjd2445f62005-03-21 00:15:53 +0000413 case Ist_NoOp:
sewardj3e838932005-01-07 12:09:15 +0000414 case Ist_MFence:
sewardjd2445f62005-03-21 00:15:53 +0000415 case Ist_IMark:
sewardj3e838932005-01-07 12:09:15 +0000416 addStmtToIRBB(bb, st);
417 break;
sewardj5a9ffab2005-05-12 17:55:01 +0000418 case Ist_AbiHint:
419 e1 = flatten_Expr(bb, st->Ist.AbiHint.base);
420 addStmtToIRBB(bb, IRStmt_AbiHint(e1, st->Ist.AbiHint.len));
421 break;
sewardjd7cb8532004-08-17 23:59:23 +0000422 case Ist_Exit:
sewardj0276d4b2004-11-15 15:30:21 +0000423 e1 = flatten_Expr(bb, st->Ist.Exit.guard);
sewardj893aada2004-11-29 19:57:54 +0000424 addStmtToIRBB(bb, IRStmt_Exit(e1, st->Ist.Exit.jk,
425 st->Ist.Exit.dst));
sewardjd7cb8532004-08-17 23:59:23 +0000426 break;
427 default:
428 vex_printf("\n");
429 ppIRStmt(st);
430 vex_printf("\n");
431 vpanic("flatten_Stmt");
432 }
433}
434
sewardj08210532004-12-29 17:09:11 +0000435
sewardjd7cb8532004-08-17 23:59:23 +0000436static IRBB* flatten_BB ( IRBB* in )
437{
438 Int i;
439 IRBB* out;
440 out = emptyIRBB();
sewardj695cff92004-10-13 14:50:14 +0000441 out->tyenv = dopyIRTypeEnv( in->tyenv );
sewardjd7cb8532004-08-17 23:59:23 +0000442 for (i = 0; i < in->stmts_used; i++)
sewardj4345f7a2004-09-22 19:49:27 +0000443 if (in->stmts[i])
444 flatten_Stmt( out, in->stmts[i] );
sewardjd7cb8532004-08-17 23:59:23 +0000445 out->next = flatten_Expr( out, in->next );
446 out->jumpkind = in->jumpkind;
447 return out;
448}
449
sewardjedf4d692004-08-17 13:52:58 +0000450
sewardj08210532004-12-29 17:09:11 +0000451/*---------------------------------------------------------------*/
452/*--- In-place removal of redundant GETs ---*/
453/*---------------------------------------------------------------*/
454
455/* Scan forwards, building up an environment binding (min offset, max
456 offset) pairs to values, which will either be temps or constants.
457
458 On seeing 't = Get(minoff,maxoff)', look up (minoff,maxoff) in the
459 env and if it matches, replace the Get with the stored value. If
460 there is no match, add a (minoff,maxoff) :-> t binding.
461
462 On seeing 'Put (minoff,maxoff) = t or c', first remove in the env
463 any binding which fully or partially overlaps with (minoff,maxoff).
464 Then add a new (minoff,maxoff) :-> t or c binding. */
465
466/* Extract the min/max offsets from a guest state array descriptor. */
467
468inline
469static void getArrayBounds ( IRArray* descr, UInt* minoff, UInt* maxoff )
470{
471 *minoff = descr->base;
472 *maxoff = *minoff + descr->nElems*sizeofIRType(descr->elemTy) - 1;
473 vassert((*minoff & ~0xFFFF) == 0);
474 vassert((*maxoff & ~0xFFFF) == 0);
475 vassert(*minoff <= *maxoff);
476}
477
478/* Create keys, of the form ((minoffset << 16) | maxoffset). */
479
480static UInt mk_key_GetPut ( Int offset, IRType ty )
481{
482 /* offset should fit in 16 bits. */
483 UInt minoff = offset;
484 UInt maxoff = minoff + sizeofIRType(ty) - 1;
485 vassert((minoff & ~0xFFFF) == 0);
486 vassert((maxoff & ~0xFFFF) == 0);
487 return (minoff << 16) | maxoff;
488}
489
490static UInt mk_key_GetIPutI ( IRArray* descr )
491{
492 UInt minoff, maxoff;
493 getArrayBounds( descr, &minoff, &maxoff );
494 vassert((minoff & ~0xFFFF) == 0);
495 vassert((maxoff & ~0xFFFF) == 0);
496 return (minoff << 16) | maxoff;
497}
498
499/* Supposing h has keys of the form generated by mk_key_GetPut and
500 mk_key_GetIPutI, invalidate any key which overlaps (k_lo
501 .. k_hi).
502*/
503static void invalidateOverlaps ( HashHW* h, UInt k_lo, UInt k_hi )
504{
505 Int j;
506 UInt e_lo, e_hi;
507 vassert(k_lo <= k_hi);
508 /* invalidate any env entries which in any way overlap (k_lo
509 .. k_hi) */
510 /* vex_printf("invalidate %d .. %d\n", k_lo, k_hi ); */
511
512 for (j = 0; j < h->used; j++) {
513 if (!h->inuse[j])
514 continue;
515 e_lo = (((UInt)h->key[j]) >> 16) & 0xFFFF;
516 e_hi = ((UInt)h->key[j]) & 0xFFFF;
517 vassert(e_lo <= e_hi);
518 if (e_hi < k_lo || k_hi < e_lo)
519 continue; /* no overlap possible */
520 else
521 /* overlap; invalidate */
522 h->inuse[j] = False;
523 }
524}
525
526
527static void redundant_get_removal_BB ( IRBB* bb )
528{
529 HashHW* env = newHHW();
530 UInt key = 0; /* keep gcc -O happy */
531 Int i, j;
532 HWord val;
533
534 for (i = 0; i < bb->stmts_used; i++) {
535 IRStmt* st = bb->stmts[i];
536
sewardj8bee6d12005-03-22 02:24:05 +0000537 if (st->tag == Ist_NoOp)
sewardj08210532004-12-29 17:09:11 +0000538 continue;
539
540 /* Deal with Gets */
541 if (st->tag == Ist_Tmp
542 && st->Ist.Tmp.data->tag == Iex_Get) {
543 /* st is 't = Get(...)'. Look up in the environment and see
544 if the Get can be replaced. */
545 IRExpr* get = st->Ist.Tmp.data;
546 key = (HWord)mk_key_GetPut( get->Iex.Get.offset,
547 get->Iex.Get.ty );
548 if (lookupHHW(env, &val, (HWord)key)) {
549 /* found it */
550 /* Note, we could do better here. If the types are
551 different we don't do the substitution, since doing so
552 could lead to invalidly-typed IR. An improvement would
553 be to stick in a reinterpret-style cast, although that
554 would make maintaining flatness more difficult. */
555 IRExpr* valE = (IRExpr*)val;
sewardj9d2e7692005-02-07 01:11:31 +0000556 Bool typesOK = toBool( typeOfIRExpr(bb->tyenv,valE)
557 == st->Ist.Tmp.data->Iex.Get.ty );
sewardj08210532004-12-29 17:09:11 +0000558 if (typesOK && DEBUG_IROPT) {
559 vex_printf("rGET: "); ppIRExpr(get);
560 vex_printf(" -> "); ppIRExpr(valE);
561 vex_printf("\n");
562 }
563 if (typesOK)
564 bb->stmts[i] = IRStmt_Tmp(st->Ist.Tmp.tmp, valE);
565 } else {
566 /* Not found, but at least we know that t and the Get(...)
567 are now associated. So add a binding to reflect that
568 fact. */
569 addToHHW( env, (HWord)key,
sewardj59c07782005-01-21 21:23:07 +0000570 (HWord)(void*)(IRExpr_Tmp(st->Ist.Tmp.tmp)) );
sewardj08210532004-12-29 17:09:11 +0000571 }
572 }
573
574 /* Deal with Puts: invalidate any env entries overlapped by this
575 Put */
576 if (st->tag == Ist_Put || st->tag == Ist_PutI) {
577 UInt k_lo, k_hi;
578 if (st->tag == Ist_Put) {
579 key = mk_key_GetPut( st->Ist.Put.offset,
580 typeOfIRExpr(bb->tyenv,st->Ist.Put.data) );
581 } else {
582 vassert(st->tag == Ist_PutI);
583 key = mk_key_GetIPutI( st->Ist.PutI.descr );
584 }
585
586 k_lo = (key >> 16) & 0xFFFF;
587 k_hi = key & 0xFFFF;
588 invalidateOverlaps(env, k_lo, k_hi);
589 }
590 else
591 if (st->tag == Ist_Dirty) {
592 /* Deal with dirty helpers which write or modify guest state.
593 Invalidate the entire env. We could do a lot better
594 here. */
595 IRDirty* d = st->Ist.Dirty.details;
596 Bool writes = False;
597 for (j = 0; j < d->nFxState; j++) {
598 if (d->fxState[j].fx == Ifx_Modify
599 || d->fxState[j].fx == Ifx_Write)
600 writes = True;
601 }
602 if (writes) {
603 /* dump the entire env (not clever, but correct ...) */
604 for (j = 0; j < env->used; j++)
605 env->inuse[j] = False;
606 if (0) vex_printf("rGET: trash env due to dirty helper\n");
607 }
608 }
609
610 /* add this one to the env, if appropriate */
611 if (st->tag == Ist_Put) {
sewardj496a58d2005-03-20 18:44:44 +0000612 vassert(isIRAtom(st->Ist.Put.data));
sewardj08210532004-12-29 17:09:11 +0000613 addToHHW( env, (HWord)key, (HWord)(st->Ist.Put.data));
614 }
615
616 } /* for (i = 0; i < bb->stmts_used; i++) */
617
618}
619
620
621/*---------------------------------------------------------------*/
622/*--- In-place removal of redundant PUTs ---*/
623/*---------------------------------------------------------------*/
624
625/* Find any Get uses in st and invalidate any partially or fully
626 overlapping ranges listed in env. Due to the flattening phase, the
627 only stmt kind we expect to find a Get on is IRStmt_Tmp. */
628
629static void handle_gets_Stmt (
630 HashHW* env,
631 IRStmt* st,
632 Bool (*preciseMemExnsFn)(Int,Int)
633 )
634{
635 Int j;
636 UInt key = 0; /* keep gcc -O happy */
637 Bool isGet;
638 Bool memRW = False;
639 IRExpr* e;
640
641 switch (st->tag) {
642
643 /* This is the only interesting case. Deal with Gets in the RHS
644 expression. */
645 case Ist_Tmp:
646 e = st->Ist.Tmp.data;
647 switch (e->tag) {
648 case Iex_Get:
649 isGet = True;
650 key = mk_key_GetPut ( e->Iex.Get.offset, e->Iex.Get.ty );
651 break;
652 case Iex_GetI:
653 isGet = True;
654 key = mk_key_GetIPutI ( e->Iex.GetI.descr );
655 break;
sewardjaf1ceca2005-06-30 23:31:27 +0000656 case Iex_Load:
sewardj08210532004-12-29 17:09:11 +0000657 isGet = False;
658 memRW = True;
659 break;
660 default:
661 isGet = False;
662 }
663 if (isGet) {
664 UInt k_lo, k_hi;
665 k_lo = (key >> 16) & 0xFFFF;
666 k_hi = key & 0xFFFF;
667 invalidateOverlaps(env, k_lo, k_hi);
668 }
669 break;
670
671 /* Be very conservative for dirty helper calls; dump the entire
672 environment. The helper might read guest state, in which
673 case it needs to be flushed first. Also, the helper might
674 access guest memory, in which case all parts of the guest
675 state requiring precise exceptions needs to be flushed. The
676 crude solution is just to flush everything; we could easily
677 enough do a lot better if needed. */
sewardj3e838932005-01-07 12:09:15 +0000678 /* Probably also overly-conservative, but also dump everything
sewardj5a9ffab2005-05-12 17:55:01 +0000679 if we hit a memory fence. Ditto AbiHints.*/
680 case Ist_AbiHint:
681 vassert(isIRAtom(st->Ist.AbiHint.base));
682 /* fall through */
sewardj3e838932005-01-07 12:09:15 +0000683 case Ist_MFence:
sewardj08210532004-12-29 17:09:11 +0000684 case Ist_Dirty:
685 for (j = 0; j < env->used; j++)
686 env->inuse[j] = False;
687 break;
688
689 /* all other cases are boring. */
sewardjaf1ceca2005-06-30 23:31:27 +0000690 case Ist_Store:
691 vassert(isIRAtom(st->Ist.Store.addr));
692 vassert(isIRAtom(st->Ist.Store.data));
sewardj08210532004-12-29 17:09:11 +0000693 memRW = True;
694 break;
695
696 case Ist_Exit:
sewardj496a58d2005-03-20 18:44:44 +0000697 vassert(isIRAtom(st->Ist.Exit.guard));
sewardj08210532004-12-29 17:09:11 +0000698 break;
699
700 case Ist_PutI:
sewardj496a58d2005-03-20 18:44:44 +0000701 vassert(isIRAtom(st->Ist.PutI.ix));
702 vassert(isIRAtom(st->Ist.PutI.data));
sewardj08210532004-12-29 17:09:11 +0000703 break;
704
sewardjd2445f62005-03-21 00:15:53 +0000705 case Ist_NoOp:
sewardjf1689312005-03-16 18:19:10 +0000706 case Ist_IMark:
707 break;
708
sewardj08210532004-12-29 17:09:11 +0000709 default:
710 vex_printf("\n");
711 ppIRStmt(st);
712 vex_printf("\n");
713 vpanic("handle_gets_Stmt");
714 }
715
716 if (memRW) {
717 /* This statement accesses memory. So we need to dump all parts
718 of the environment corresponding to guest state that may not
719 be reordered with respect to memory references. That means
720 at least the stack pointer. */
721 for (j = 0; j < env->used; j++) {
722 if (!env->inuse[j])
723 continue;
724 if (vex_control.iropt_precise_memory_exns) {
725 /* Precise exceptions required. Flush all guest state. */
726 env->inuse[j] = False;
727 } else {
728 /* Just flush the minimal amount required, as computed by
729 preciseMemExnsFn. */
730 HWord k_lo = (env->key[j] >> 16) & 0xFFFF;
731 HWord k_hi = env->key[j] & 0xFFFF;
732 if (preciseMemExnsFn( k_lo, k_hi ))
733 env->inuse[j] = False;
734 }
735 }
736 } /* if (memRW) */
737
738}
739
740
741/* Scan backwards, building up a set of (min offset, max
742 offset) pairs, indicating those parts of the guest state
743 for which the next event is a write.
744
745 On seeing a conditional exit, empty the set.
746
747 On seeing 'Put (minoff,maxoff) = t or c', if (minoff,maxoff) is
748 completely within the set, remove the Put. Otherwise, add
749 (minoff,maxoff) to the set.
750
751 On seeing 'Get (minoff,maxoff)', remove any part of the set
sewardj98430292004-12-29 17:34:50 +0000752 overlapping (minoff,maxoff). The same has to happen for any events
753 which implicitly read parts of the guest state: dirty helper calls
754 and loads/stores.
sewardj08210532004-12-29 17:09:11 +0000755*/
756
757static void redundant_put_removal_BB (
758 IRBB* bb,
759 Bool (*preciseMemExnsFn)(Int,Int)
760 )
761{
762 Int i, j;
763 Bool isPut;
764 IRStmt* st;
765 UInt key = 0; /* keep gcc -O happy */
766
767 HashHW* env = newHHW();
768 for (i = bb->stmts_used-1; i >= 0; i--) {
769 st = bb->stmts[i];
sewardj8bee6d12005-03-22 02:24:05 +0000770
771 if (st->tag == Ist_NoOp)
sewardj08210532004-12-29 17:09:11 +0000772 continue;
773
774 /* Deal with conditional exits. */
775 if (st->tag == Ist_Exit) {
776 /* Since control may not get beyond this point, we must empty
777 out the set, since we can no longer claim that the next
778 event for any part of the guest state is definitely a
779 write. */
sewardj496a58d2005-03-20 18:44:44 +0000780 vassert(isIRAtom(st->Ist.Exit.guard));
sewardj08210532004-12-29 17:09:11 +0000781 for (j = 0; j < env->used; j++)
782 env->inuse[j] = False;
783 continue;
784 }
785
786 /* Deal with Puts */
787 switch (st->tag) {
788 case Ist_Put:
789 isPut = True;
790 key = mk_key_GetPut( st->Ist.Put.offset,
791 typeOfIRExpr(bb->tyenv,st->Ist.Put.data) );
sewardj496a58d2005-03-20 18:44:44 +0000792 vassert(isIRAtom(st->Ist.Put.data));
sewardj08210532004-12-29 17:09:11 +0000793 break;
794 case Ist_PutI:
795 isPut = True;
796 key = mk_key_GetIPutI( st->Ist.PutI.descr );
sewardj496a58d2005-03-20 18:44:44 +0000797 vassert(isIRAtom(st->Ist.PutI.ix));
798 vassert(isIRAtom(st->Ist.PutI.data));
sewardj08210532004-12-29 17:09:11 +0000799 break;
800 default:
801 isPut = False;
802 }
803 if (isPut && st->tag != Ist_PutI) {
804 /* See if any single entry in env overlaps this Put. This is
805 simplistic in that the transformation is valid if, say, two
806 or more entries in the env overlap this Put, but the use of
807 lookupHHW will only find a single entry which exactly
808 overlaps this Put. This is suboptimal but safe. */
809 if (lookupHHW(env, NULL, (HWord)key)) {
810 /* This Put is redundant because a later one will overwrite
811 it. So NULL (nop) it out. */
812 if (DEBUG_IROPT) {
813 vex_printf("rPUT: "); ppIRStmt(st);
814 vex_printf("\n");
815 }
sewardjd2445f62005-03-21 00:15:53 +0000816 bb->stmts[i] = IRStmt_NoOp();
sewardj08210532004-12-29 17:09:11 +0000817 } else {
818 /* We can't demonstrate that this Put is redundant, so add it
819 to the running collection. */
820 addToHHW(env, (HWord)key, 0);
821 }
822 continue;
823 }
824
825 /* Deal with Gets. These remove bits of the environment since
826 appearance of a Get means that the next event for that slice
sewardj98430292004-12-29 17:34:50 +0000827 of the guest state is no longer a write, but a read. Also
828 deals with implicit reads of guest state needed to maintain
829 precise exceptions. */
sewardj08210532004-12-29 17:09:11 +0000830 handle_gets_Stmt( env, st, preciseMemExnsFn );
831 }
832}
833
sewardj84be7372004-08-18 13:59:33 +0000834
835/*---------------------------------------------------------------*/
836/*--- Constant propagation and folding ---*/
837/*---------------------------------------------------------------*/
838
sewardj62617ef2004-10-13 23:29:22 +0000839/* The env in this section is a map from IRTemp to IRExpr*,
840 that is, an array indexed by IRTemp. */
sewardjf6501992004-08-27 11:58:24 +0000841
sewardjf6729012004-08-25 12:45:13 +0000842/* Are both expressions simply the same IRTemp ? */
843static Bool sameIRTemps ( IRExpr* e1, IRExpr* e2 )
844{
sewardj9d2e7692005-02-07 01:11:31 +0000845 return toBool( e1->tag == Iex_Tmp
846 && e2->tag == Iex_Tmp
847 && e1->Iex.Tmp.tmp == e2->Iex.Tmp.tmp );
sewardjf6729012004-08-25 12:45:13 +0000848}
849
sewardje1d45da2004-11-12 00:13:21 +0000850static Bool notBool ( Bool b )
851{
852 if (b == True) return False;
853 if (b == False) return True;
854 vpanic("notBool");
855}
856
sewardj0033ddc2005-04-26 23:34:34 +0000857/* Make a zero which has the same type as the result of the given
858 primop. */
859static IRExpr* mkZeroForXor ( IROp op )
860{
861 switch (op) {
862 case Iop_Xor8: return IRExpr_Const(IRConst_U8(0));
863 case Iop_Xor16: return IRExpr_Const(IRConst_U16(0));
864 case Iop_Xor32: return IRExpr_Const(IRConst_U32(0));
865 case Iop_Xor64: return IRExpr_Const(IRConst_U64(0));
866 default: vpanic("mkZeroForXor: bad primop");
867 }
868}
869
870
sewardj84be7372004-08-18 13:59:33 +0000871static IRExpr* fold_Expr ( IRExpr* e )
872{
sewardj278c44c2004-08-20 00:28:13 +0000873 Int shift;
sewardj84be7372004-08-18 13:59:33 +0000874 IRExpr* e2 = e; /* e2 is the result of folding e, if possible */
875
876 /* UNARY ops */
877 if (e->tag == Iex_Unop
878 && e->Iex.Unop.arg->tag == Iex_Const) {
879 switch (e->Iex.Unop.op) {
sewardjae27ab62004-10-15 21:21:46 +0000880 case Iop_1Uto8:
sewardj9d2e7692005-02-07 01:11:31 +0000881 e2 = IRExpr_Const(IRConst_U8(toUChar(
sewardjba999312004-11-15 15:21:17 +0000882 e->Iex.Unop.arg->Iex.Const.con->Ico.U1
sewardj9d2e7692005-02-07 01:11:31 +0000883 ? 1 : 0)));
sewardjae27ab62004-10-15 21:21:46 +0000884 break;
sewardjf4a821d2004-10-09 00:58:19 +0000885 case Iop_1Uto32:
886 e2 = IRExpr_Const(IRConst_U32(
sewardjba999312004-11-15 15:21:17 +0000887 e->Iex.Unop.arg->Iex.Const.con->Ico.U1
sewardjf4a821d2004-10-09 00:58:19 +0000888 ? 1 : 0));
889 break;
sewardj2716ff12005-05-20 19:21:45 +0000890 case Iop_1Uto64:
891 e2 = IRExpr_Const(IRConst_U64(
892 e->Iex.Unop.arg->Iex.Const.con->Ico.U1
893 ? 1 : 0));
894 break;
sewardje6b39932004-11-06 17:01:15 +0000895
sewardj68884ef2005-07-18 13:58:49 +0000896 case Iop_1Sto16:
sewardj743d8f02005-07-27 00:22:37 +0000897 e2 = IRExpr_Const(IRConst_U16(toUShort(
sewardj68884ef2005-07-18 13:58:49 +0000898 e->Iex.Unop.arg->Iex.Const.con->Ico.U1
sewardj743d8f02005-07-27 00:22:37 +0000899 ? 0xFFFF : 0)));
sewardj68884ef2005-07-18 13:58:49 +0000900 break;
sewardjd9997882004-11-04 19:42:59 +0000901 case Iop_1Sto32:
902 e2 = IRExpr_Const(IRConst_U32(
sewardjba999312004-11-15 15:21:17 +0000903 e->Iex.Unop.arg->Iex.Const.con->Ico.U1
sewardjd9997882004-11-04 19:42:59 +0000904 ? 0xFFFFFFFF : 0));
905 break;
sewardje6b39932004-11-06 17:01:15 +0000906 case Iop_1Sto64:
907 e2 = IRExpr_Const(IRConst_U64(
sewardjba999312004-11-15 15:21:17 +0000908 e->Iex.Unop.arg->Iex.Const.con->Ico.U1
sewardje6b39932004-11-06 17:01:15 +0000909 ? 0xFFFFFFFFFFFFFFFFULL : 0));
910 break;
911
sewardj883b00b2004-09-11 09:30:24 +0000912 case Iop_8Sto32: {
913 /* signed */ Int s32 = e->Iex.Unop.arg->Iex.Const.con->Ico.U8;
914 s32 <<= 24;
915 s32 >>= 24;
916 e2 = IRExpr_Const(IRConst_U32((UInt)s32));
917 break;
918 }
sewardj291a7e82005-04-27 11:42:44 +0000919 case Iop_8Uto64:
920 e2 = IRExpr_Const(IRConst_U64(
921 0xFFULL & e->Iex.Unop.arg->Iex.Const.con->Ico.U8));
922 break;
923 case Iop_16Uto64:
924 e2 = IRExpr_Const(IRConst_U64(
925 0xFFFFULL & e->Iex.Unop.arg->Iex.Const.con->Ico.U16));
926 break;
sewardj84be7372004-08-18 13:59:33 +0000927 case Iop_8Uto32:
928 e2 = IRExpr_Const(IRConst_U32(
929 0xFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U8));
930 break;
931 case Iop_16Uto32:
932 e2 = IRExpr_Const(IRConst_U32(
933 0xFFFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U16));
934 break;
sewardj73017432004-10-14 19:33:25 +0000935 case Iop_32to16:
sewardj9d2e7692005-02-07 01:11:31 +0000936 e2 = IRExpr_Const(IRConst_U16(toUShort(
937 0xFFFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U32)));
sewardj73017432004-10-14 19:33:25 +0000938 break;
sewardj4345f7a2004-09-22 19:49:27 +0000939 case Iop_32to8:
sewardj9d2e7692005-02-07 01:11:31 +0000940 e2 = IRExpr_Const(IRConst_U8(toUChar(
941 0xFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U32)));
sewardj4345f7a2004-09-22 19:49:27 +0000942 break;
sewardj7447b5b2004-10-16 11:30:42 +0000943 case Iop_32to1:
sewardj9d2e7692005-02-07 01:11:31 +0000944 e2 = IRExpr_Const(IRConst_U1(toBool(
945 1 == (1 & e->Iex.Unop.arg->Iex.Const.con->Ico.U32)
946 )));
sewardj7447b5b2004-10-16 11:30:42 +0000947 break;
sewardj291a7e82005-04-27 11:42:44 +0000948 case Iop_64to1:
949 e2 = IRExpr_Const(IRConst_U1(toBool(
950 1 == (1 & e->Iex.Unop.arg->Iex.Const.con->Ico.U64)
951 )));
952 break;
sewardje6b39932004-11-06 17:01:15 +0000953
sewardjf057afb2005-02-27 13:35:41 +0000954 case Iop_Not64:
955 e2 = IRExpr_Const(IRConst_U64(
956 ~ (e->Iex.Unop.arg->Iex.Const.con->Ico.U64)));
957 break;
sewardj883b00b2004-09-11 09:30:24 +0000958 case Iop_Not32:
959 e2 = IRExpr_Const(IRConst_U32(
960 ~ (e->Iex.Unop.arg->Iex.Const.con->Ico.U32)));
961 break;
sewardje6b39932004-11-06 17:01:15 +0000962 case Iop_Not16:
sewardj9d2e7692005-02-07 01:11:31 +0000963 e2 = IRExpr_Const(IRConst_U16(toUShort(
964 ~ (e->Iex.Unop.arg->Iex.Const.con->Ico.U16))));
sewardje6b39932004-11-06 17:01:15 +0000965 break;
sewardjd9997882004-11-04 19:42:59 +0000966 case Iop_Not8:
sewardj9d2e7692005-02-07 01:11:31 +0000967 e2 = IRExpr_Const(IRConst_U8(toUChar(
968 ~ (e->Iex.Unop.arg->Iex.Const.con->Ico.U8))));
sewardjd9997882004-11-04 19:42:59 +0000969 break;
sewardje6b39932004-11-06 17:01:15 +0000970
sewardje1d45da2004-11-12 00:13:21 +0000971 case Iop_Not1:
sewardjba999312004-11-15 15:21:17 +0000972 e2 = IRExpr_Const(IRConst_U1(
973 notBool(e->Iex.Unop.arg->Iex.Const.con->Ico.U1)));
sewardje1d45da2004-11-12 00:13:21 +0000974 break;
975
sewardj291a7e82005-04-27 11:42:44 +0000976 case Iop_Neg64:
977 e2 = IRExpr_Const(IRConst_U64(
978 - (e->Iex.Unop.arg->Iex.Const.con->Ico.U64)));
979 break;
sewardj0033ddc2005-04-26 23:34:34 +0000980 case Iop_Neg32:
981 e2 = IRExpr_Const(IRConst_U32(
982 - (e->Iex.Unop.arg->Iex.Const.con->Ico.U32)));
983 break;
984 case Iop_Neg8:
sewardj65b17c62005-05-02 15:52:44 +0000985 e2 = IRExpr_Const(IRConst_U8(toUChar(
986 - (e->Iex.Unop.arg->Iex.Const.con->Ico.U8))));
sewardj0033ddc2005-04-26 23:34:34 +0000987 break;
988
sewardj291a7e82005-04-27 11:42:44 +0000989 case Iop_64to8: {
990 ULong w64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
991 w64 &= 0xFFULL;
992 e2 = IRExpr_Const(IRConst_U8( (UChar)w64 ));
993 break;
994 }
995 case Iop_64to16: {
996 ULong w64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
997 w64 &= 0xFFFFULL;
sewardje85bc402005-05-06 16:29:26 +0000998 e2 = IRExpr_Const(IRConst_U16( (UShort)w64 ));
sewardj291a7e82005-04-27 11:42:44 +0000999 break;
1000 }
sewardj1d8ce202004-12-13 14:14:16 +00001001 case Iop_64to32: {
1002 ULong w64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
1003 w64 &= 0x00000000FFFFFFFFULL;
1004 e2 = IRExpr_Const(IRConst_U32( (UInt)w64 ));
sewardj37010592004-12-13 10:47:15 +00001005 break;
sewardj1d8ce202004-12-13 14:14:16 +00001006 }
sewardj1d8ce202004-12-13 14:14:16 +00001007 case Iop_64HIto32: {
1008 ULong w64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
1009 w64 >>= 32;
1010 e2 = IRExpr_Const(IRConst_U32( (UInt)w64 ));
1011 break;
1012 }
sewardjb5710b82005-01-27 16:05:09 +00001013 case Iop_32Uto64:
1014 e2 = IRExpr_Const(IRConst_U64(
1015 0xFFFFFFFFULL
1016 & e->Iex.Unop.arg->Iex.Const.con->Ico.U32));
1017 break;
sewardj37010592004-12-13 10:47:15 +00001018
sewardj0033ddc2005-04-26 23:34:34 +00001019 case Iop_CmpNEZ8:
1020 e2 = IRExpr_Const(IRConst_U1(toBool(
1021 0 !=
1022 (0xFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U8)
1023 )));
1024 break;
1025 case Iop_CmpNEZ32:
1026 e2 = IRExpr_Const(IRConst_U1(toBool(
1027 0 !=
1028 (0xFFFFFFFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U32)
1029 )));
1030 break;
1031 case Iop_CmpNEZ64:
1032 e2 = IRExpr_Const(IRConst_U1(toBool(
1033 0ULL != e->Iex.Unop.arg->Iex.Const.con->Ico.U64
1034 )));
1035 break;
1036
sewardj84be7372004-08-18 13:59:33 +00001037 default:
1038 goto unhandled;
1039 }
1040 }
1041
1042 /* BINARY ops */
1043 if (e->tag == Iex_Binop) {
1044 if (e->Iex.Binop.arg1->tag == Iex_Const
1045 && e->Iex.Binop.arg2->tag == Iex_Const) {
1046 /* cases where both args are consts */
1047 switch (e->Iex.Binop.op) {
sewardje6b39932004-11-06 17:01:15 +00001048
sewardj855dc722005-02-17 09:26:05 +00001049 /* -- Or -- */
sewardjd9997882004-11-04 19:42:59 +00001050 case Iop_Or8:
sewardj9d2e7692005-02-07 01:11:31 +00001051 e2 = IRExpr_Const(IRConst_U8(toUChar(
sewardjd9997882004-11-04 19:42:59 +00001052 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
sewardj9d2e7692005-02-07 01:11:31 +00001053 | e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
sewardjd9997882004-11-04 19:42:59 +00001054 break;
sewardje6b39932004-11-06 17:01:15 +00001055 case Iop_Or16:
sewardj9d2e7692005-02-07 01:11:31 +00001056 e2 = IRExpr_Const(IRConst_U16(toUShort(
sewardje6b39932004-11-06 17:01:15 +00001057 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U16
sewardj9d2e7692005-02-07 01:11:31 +00001058 | e->Iex.Binop.arg2->Iex.Const.con->Ico.U16))));
sewardje6b39932004-11-06 17:01:15 +00001059 break;
1060 case Iop_Or32:
1061 e2 = IRExpr_Const(IRConst_U32(
1062 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1063 | e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1064 break;
sewardjf057afb2005-02-27 13:35:41 +00001065 case Iop_Or64:
1066 e2 = IRExpr_Const(IRConst_U64(
1067 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1068 | e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1069 break;
sewardje6b39932004-11-06 17:01:15 +00001070
sewardj855dc722005-02-17 09:26:05 +00001071 /* -- Xor -- */
sewardj883b00b2004-09-11 09:30:24 +00001072 case Iop_Xor8:
sewardj9d2e7692005-02-07 01:11:31 +00001073 e2 = IRExpr_Const(IRConst_U8(toUChar(
sewardj883b00b2004-09-11 09:30:24 +00001074 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
sewardj9d2e7692005-02-07 01:11:31 +00001075 ^ e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
sewardj883b00b2004-09-11 09:30:24 +00001076 break;
sewardj82c9f2f2005-03-02 16:05:13 +00001077 case Iop_Xor16:
sewardjc7c098f2005-03-21 01:06:20 +00001078 e2 = IRExpr_Const(IRConst_U16(toUShort(
sewardj82c9f2f2005-03-02 16:05:13 +00001079 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U16
sewardjc7c098f2005-03-21 01:06:20 +00001080 ^ e->Iex.Binop.arg2->Iex.Const.con->Ico.U16))));
sewardj82c9f2f2005-03-02 16:05:13 +00001081 break;
sewardj855dc722005-02-17 09:26:05 +00001082 case Iop_Xor32:
1083 e2 = IRExpr_Const(IRConst_U32(
1084 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1085 ^ e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1086 break;
sewardjf057afb2005-02-27 13:35:41 +00001087 case Iop_Xor64:
1088 e2 = IRExpr_Const(IRConst_U64(
1089 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1090 ^ e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1091 break;
sewardj855dc722005-02-17 09:26:05 +00001092
1093 /* -- And -- */
sewardj84be7372004-08-18 13:59:33 +00001094 case Iop_And8:
sewardj9d2e7692005-02-07 01:11:31 +00001095 e2 = IRExpr_Const(IRConst_U8(toUChar(
sewardj84be7372004-08-18 13:59:33 +00001096 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
sewardj9d2e7692005-02-07 01:11:31 +00001097 & e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
sewardj84be7372004-08-18 13:59:33 +00001098 break;
sewardj855dc722005-02-17 09:26:05 +00001099 case Iop_And32:
1100 e2 = IRExpr_Const(IRConst_U32(
1101 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1102 & e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1103 break;
1104 case Iop_And64:
1105 e2 = IRExpr_Const(IRConst_U64(
1106 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1107 & e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1108 break;
1109
1110 /* -- Add -- */
sewardj4345f7a2004-09-22 19:49:27 +00001111 case Iop_Add8:
sewardj9d2e7692005-02-07 01:11:31 +00001112 e2 = IRExpr_Const(IRConst_U8(toUChar(
sewardj4345f7a2004-09-22 19:49:27 +00001113 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
sewardj9d2e7692005-02-07 01:11:31 +00001114 + e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
sewardj4345f7a2004-09-22 19:49:27 +00001115 break;
sewardj855dc722005-02-17 09:26:05 +00001116 case Iop_Add32:
1117 e2 = IRExpr_Const(IRConst_U32(
1118 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1119 + e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1120 break;
1121 case Iop_Add64:
1122 e2 = IRExpr_Const(IRConst_U64(
1123 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1124 + e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1125 break;
1126
1127 /* -- Sub -- */
sewardj84be7372004-08-18 13:59:33 +00001128 case Iop_Sub8:
sewardj9d2e7692005-02-07 01:11:31 +00001129 e2 = IRExpr_Const(IRConst_U8(toUChar(
sewardj84be7372004-08-18 13:59:33 +00001130 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
sewardj9d2e7692005-02-07 01:11:31 +00001131 - e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
sewardj84be7372004-08-18 13:59:33 +00001132 break;
sewardjd7217032004-08-19 10:49:10 +00001133 case Iop_Sub32:
1134 e2 = IRExpr_Const(IRConst_U32(
1135 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1136 - e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1137 break;
sewardj70a8ddf2005-02-13 02:24:26 +00001138 case Iop_Sub64:
1139 e2 = IRExpr_Const(IRConst_U64(
1140 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1141 - e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1142 break;
sewardjc2bcb6f2005-02-07 00:17:12 +00001143
sewardj855dc722005-02-17 09:26:05 +00001144 /* -- Mul -- */
sewardjb9c5cf62004-08-24 15:10:38 +00001145 case Iop_Mul32:
1146 e2 = IRExpr_Const(IRConst_U32(
1147 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1148 * e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1149 break;
sewardja34c0712005-03-30 23:19:46 +00001150 case Iop_Mul64:
1151 e2 = IRExpr_Const(IRConst_U64(
1152 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1153 * e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1154 break;
1155
sewardjea6bccb2005-03-01 10:19:23 +00001156 case Iop_MullS32: {
1157 /* very paranoid */
1158 UInt u32a = e->Iex.Binop.arg1->Iex.Const.con->Ico.U32;
1159 UInt u32b = e->Iex.Binop.arg2->Iex.Const.con->Ico.U32;
1160 Int s32a = (Int)u32a;
1161 Int s32b = (Int)u32b;
1162 Long s64a = (Long)s32a;
1163 Long s64b = (Long)s32b;
1164 Long sres = s64a * s64b;
1165 ULong ures = (ULong)sres;
1166 e2 = IRExpr_Const(IRConst_U64(ures));
1167 break;
1168 }
sewardjb095fba2005-02-13 14:13:04 +00001169
sewardj855dc722005-02-17 09:26:05 +00001170 /* -- Shl -- */
sewardjd7217032004-08-19 10:49:10 +00001171 case Iop_Shl32:
sewardj61348472004-08-20 01:01:04 +00001172 vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1173 shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
sewardj29632392004-08-22 02:38:11 +00001174 if (shift >= 0 && shift <= 31)
sewardj278c44c2004-08-20 00:28:13 +00001175 e2 = IRExpr_Const(IRConst_U32(
1176 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1177 << shift)));
sewardjd7217032004-08-19 10:49:10 +00001178 break;
sewardjb095fba2005-02-13 14:13:04 +00001179 case Iop_Shl64:
1180 vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1181 shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1182 if (shift >= 0 && shift <= 63)
1183 e2 = IRExpr_Const(IRConst_U64(
1184 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1185 << shift)));
1186 break;
1187
sewardj855dc722005-02-17 09:26:05 +00001188 /* -- Sar -- */
sewardj278c44c2004-08-20 00:28:13 +00001189 case Iop_Sar32: {
1190 /* paranoid ... */
1191 /*signed*/ Int s32;
sewardj61348472004-08-20 01:01:04 +00001192 vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
sewardj278c44c2004-08-20 00:28:13 +00001193 s32 = (Int)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32);
sewardj61348472004-08-20 01:01:04 +00001194 shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
sewardj278c44c2004-08-20 00:28:13 +00001195 if (shift >= 0 && shift <= 31) {
1196 s32 >>=/*signed*/ shift;
1197 e2 = IRExpr_Const(IRConst_U32((UInt)s32));
1198 }
1199 break;
1200 }
sewardj855dc722005-02-17 09:26:05 +00001201 case Iop_Sar64: {
1202 /* paranoid ... */
1203 /*signed*/ Long s64;
1204 vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1205 s64 = (Long)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U64);
1206 shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1207 if (shift >= 0 && shift <= 63) {
1208 s64 >>=/*signed*/ shift;
1209 e2 = IRExpr_Const(IRConst_U64((ULong)s64));
1210 }
1211 break;
1212 }
1213
1214 /* -- Shr -- */
sewardj61348472004-08-20 01:01:04 +00001215 case Iop_Shr32: {
1216 /* paranoid ... */
sewardj4add7142005-02-21 08:20:22 +00001217 /*unsigned*/ UInt u32;
sewardj61348472004-08-20 01:01:04 +00001218 vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
sewardj4add7142005-02-21 08:20:22 +00001219 u32 = (UInt)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32);
sewardj61348472004-08-20 01:01:04 +00001220 shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1221 if (shift >= 0 && shift <= 31) {
sewardj4add7142005-02-21 08:20:22 +00001222 u32 >>=/*unsigned*/ shift;
1223 e2 = IRExpr_Const(IRConst_U32(u32));
1224 }
1225 break;
1226 }
1227 case Iop_Shr64: {
1228 /* paranoid ... */
1229 /*unsigned*/ ULong u64;
1230 vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1231 u64 = (ULong)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U64);
1232 shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1233 if (shift >= 0 && shift <= 63) {
1234 u64 >>=/*unsigned*/ shift;
1235 e2 = IRExpr_Const(IRConst_U64(u64));
sewardj61348472004-08-20 01:01:04 +00001236 }
1237 break;
1238 }
sewardj855dc722005-02-17 09:26:05 +00001239
1240 /* -- CmpEQ -- */
sewardjb8e75862004-08-19 17:58:45 +00001241 case Iop_CmpEQ32:
sewardj9d2e7692005-02-07 01:11:31 +00001242 e2 = IRExpr_Const(IRConst_U1(toBool(
sewardjb8e75862004-08-19 17:58:45 +00001243 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
sewardj9d2e7692005-02-07 01:11:31 +00001244 == e->Iex.Binop.arg2->Iex.Const.con->Ico.U32))));
sewardjb8e75862004-08-19 17:58:45 +00001245 break;
sewardj855dc722005-02-17 09:26:05 +00001246 case Iop_CmpEQ64:
1247 e2 = IRExpr_Const(IRConst_U1(toBool(
1248 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1249 == e->Iex.Binop.arg2->Iex.Const.con->Ico.U64))));
1250 break;
1251
1252 /* -- CmpNE -- */
1253 case Iop_CmpNE8:
1254 e2 = IRExpr_Const(IRConst_U1(toBool(
1255 ((0xFF & e->Iex.Binop.arg1->Iex.Const.con->Ico.U8)
1256 != (0xFF & e->Iex.Binop.arg2->Iex.Const.con->Ico.U8)))));
1257 break;
sewardjae27ab62004-10-15 21:21:46 +00001258 case Iop_CmpNE32:
sewardj9d2e7692005-02-07 01:11:31 +00001259 e2 = IRExpr_Const(IRConst_U1(toBool(
sewardjae27ab62004-10-15 21:21:46 +00001260 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
sewardj9d2e7692005-02-07 01:11:31 +00001261 != e->Iex.Binop.arg2->Iex.Const.con->Ico.U32))));
sewardjae27ab62004-10-15 21:21:46 +00001262 break;
sewardje6b39932004-11-06 17:01:15 +00001263 case Iop_CmpNE64:
sewardj9d2e7692005-02-07 01:11:31 +00001264 e2 = IRExpr_Const(IRConst_U1(toBool(
sewardje6b39932004-11-06 17:01:15 +00001265 (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
sewardj9d2e7692005-02-07 01:11:31 +00001266 != e->Iex.Binop.arg2->Iex.Const.con->Ico.U64))));
sewardje6b39932004-11-06 17:01:15 +00001267 break;
1268
sewardj855dc722005-02-17 09:26:05 +00001269 /* -- CmpLEU -- */
sewardj7447b5b2004-10-16 11:30:42 +00001270 case Iop_CmpLE32U:
sewardj9d2e7692005-02-07 01:11:31 +00001271 e2 = IRExpr_Const(IRConst_U1(toBool(
sewardj7447b5b2004-10-16 11:30:42 +00001272 ((UInt)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)
sewardj9d2e7692005-02-07 01:11:31 +00001273 <= (UInt)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)))));
sewardj7447b5b2004-10-16 11:30:42 +00001274 break;
sewardj855dc722005-02-17 09:26:05 +00001275
1276 /* -- CmpLES -- */
sewardj088e4f72004-10-19 01:25:02 +00001277 case Iop_CmpLE32S:
sewardj9d2e7692005-02-07 01:11:31 +00001278 e2 = IRExpr_Const(IRConst_U1(toBool(
sewardj088e4f72004-10-19 01:25:02 +00001279 ((Int)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)
sewardj9d2e7692005-02-07 01:11:31 +00001280 <= (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)))));
sewardj088e4f72004-10-19 01:25:02 +00001281 break;
sewardje1d45da2004-11-12 00:13:21 +00001282
sewardj855dc722005-02-17 09:26:05 +00001283 /* -- CmpLTS -- */
sewardj9bdd2652004-10-19 12:56:33 +00001284 case Iop_CmpLT32S:
sewardj9d2e7692005-02-07 01:11:31 +00001285 e2 = IRExpr_Const(IRConst_U1(toBool(
sewardj9bdd2652004-10-19 12:56:33 +00001286 ((Int)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)
sewardj9d2e7692005-02-07 01:11:31 +00001287 < (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)))));
sewardj9bdd2652004-10-19 12:56:33 +00001288 break;
sewardj855dc722005-02-17 09:26:05 +00001289
1290 /* -- CmpLTU -- */
sewardje1d45da2004-11-12 00:13:21 +00001291 case Iop_CmpLT32U:
sewardj9d2e7692005-02-07 01:11:31 +00001292 e2 = IRExpr_Const(IRConst_U1(toBool(
sewardje1d45da2004-11-12 00:13:21 +00001293 ((UInt)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)
sewardj9d2e7692005-02-07 01:11:31 +00001294 < (UInt)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)))));
sewardje1d45da2004-11-12 00:13:21 +00001295 break;
sewardj7447b5b2004-10-16 11:30:42 +00001296
sewardjb51f0f42005-07-18 11:38:02 +00001297 /* -- CmpORD -- */
1298 case Iop_CmpORD32S: {
1299 /* very paranoid */
1300 UInt u32a = e->Iex.Binop.arg1->Iex.Const.con->Ico.U32;
1301 UInt u32b = e->Iex.Binop.arg2->Iex.Const.con->Ico.U32;
1302 Int s32a = (Int)u32a;
1303 Int s32b = (Int)u32b;
1304 Int r = 0x2; /* EQ */
1305 if (s32a < s32b) {
1306 r = 0x8; /* LT */
1307 }
1308 else if (s32a > s32b) {
1309 r = 0x4; /* GT */
1310 }
1311 e2 = IRExpr_Const(IRConst_U32(r));
1312 break;
1313 }
1314
sewardj855dc722005-02-17 09:26:05 +00001315 /* -- nHLto2n -- */
sewardj088bcb42004-08-19 17:16:52 +00001316 case Iop_32HLto64:
1317 e2 = IRExpr_Const(IRConst_U64(
1318 (((ULong)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)) << 32)
1319 | ((ULong)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32))
1320 ));
1321 break;
sewardj3bc8a592005-05-02 10:47:22 +00001322 case Iop_64HLto128:
1323 /* We can't fold this, because there is no way to
1324 express he result in IR, but at least pretend to
1325 handle it, so as to stop getting blasted with
1326 no-rule-for-this-primop messages. */
1327 break;
sewardj855dc722005-02-17 09:26:05 +00001328
sewardj607dd4f2004-09-08 18:20:19 +00001329 default:
1330 goto unhandled;
sewardjd7217032004-08-19 10:49:10 +00001331 }
sewardjf6729012004-08-25 12:45:13 +00001332
sewardj84be7372004-08-18 13:59:33 +00001333 } else {
sewardjf6729012004-08-25 12:45:13 +00001334
sewardj84be7372004-08-18 13:59:33 +00001335 /* other cases (identities, etc) */
sewardj291a7e82005-04-27 11:42:44 +00001336
1337 /* Shl64/Shr64(x,0) ==> x */
1338 if ((e->Iex.Binop.op == Iop_Shl64 || e->Iex.Binop.op == Iop_Shr64)
1339 && e->Iex.Binop.arg2->tag == Iex_Const
1340 && e->Iex.Binop.arg2->Iex.Const.con->Ico.U8 == 0) {
1341 e2 = e->Iex.Binop.arg1;
1342 } else
1343
sewardj4afab822005-01-20 10:04:05 +00001344 /* Shl32/Shr32(x,0) ==> x */
1345 if ((e->Iex.Binop.op == Iop_Shl32 || e->Iex.Binop.op == Iop_Shr32)
sewardj52345402004-10-13 16:08:14 +00001346 && e->Iex.Binop.arg2->tag == Iex_Const
sewardj4980c6b2004-10-13 16:16:27 +00001347 && e->Iex.Binop.arg2->Iex.Const.con->Ico.U8 == 0) {
sewardj52345402004-10-13 16:08:14 +00001348 e2 = e->Iex.Binop.arg1;
1349 } else
1350
sewardj8ac9bc92005-04-21 01:35:48 +00001351 /* Or8(x,0) ==> x */
1352 if ((e->Iex.Binop.op == Iop_Or8)
1353 && e->Iex.Binop.arg2->tag == Iex_Const
1354 && e->Iex.Binop.arg2->Iex.Const.con->Ico.U8 == 0) {
1355 e2 = e->Iex.Binop.arg1;
1356 } else
1357
sewardj0033ddc2005-04-26 23:34:34 +00001358 /* Or16(x,0) ==> x */
1359 if ((e->Iex.Binop.op == Iop_Or16)
1360 && e->Iex.Binop.arg2->tag == Iex_Const
1361 && e->Iex.Binop.arg2->Iex.Const.con->Ico.U16 == 0) {
1362 e2 = e->Iex.Binop.arg1;
1363 } else
1364
sewardjd9997882004-11-04 19:42:59 +00001365 /* Or32/Add32(x,0) ==> x */
1366 if ((e->Iex.Binop.op == Iop_Add32 || e->Iex.Binop.op == Iop_Or32)
sewardj84be7372004-08-18 13:59:33 +00001367 && e->Iex.Binop.arg2->tag == Iex_Const
1368 && e->Iex.Binop.arg2->Iex.Const.con->Ico.U32 == 0) {
1369 e2 = e->Iex.Binop.arg1;
sewardjf6729012004-08-25 12:45:13 +00001370 } else
1371
sewardjdcd6c882004-12-16 11:41:06 +00001372 /* Or64/Add64(x,0) ==> x */
1373 if ((e->Iex.Binop.op == Iop_Add64 || e->Iex.Binop.op == Iop_Or64)
1374 && e->Iex.Binop.arg2->tag == Iex_Const
1375 && e->Iex.Binop.arg2->Iex.Const.con->Ico.U64 == 0) {
1376 e2 = e->Iex.Binop.arg1;
1377 } else
1378
sewardj832853b2004-11-06 12:10:04 +00001379 /* And32(x,0xFFFFFFFF) ==> x */
1380 if (e->Iex.Binop.op == Iop_And32
1381 && e->Iex.Binop.arg2->tag == Iex_Const
1382 && e->Iex.Binop.arg2->Iex.Const.con->Ico.U32 == 0xFFFFFFFF) {
1383 e2 = e->Iex.Binop.arg1;
1384 } else
1385
sewardj23256992005-07-01 10:51:24 +00001386 /* And32(x,0) ==> 0 */
1387 if (e->Iex.Binop.op == Iop_And32
1388 && e->Iex.Binop.arg2->tag == Iex_Const
1389 && e->Iex.Binop.arg2->Iex.Const.con->Ico.U32 == 0) {
1390 e2 = IRExpr_Const(IRConst_U32(0));
1391 } else
1392
sewardjd9997882004-11-04 19:42:59 +00001393 /* Or32(0,x) ==> x */
1394 if (e->Iex.Binop.op == Iop_Or32
1395 && e->Iex.Binop.arg1->tag == Iex_Const
1396 && e->Iex.Binop.arg1->Iex.Const.con->Ico.U32 == 0) {
1397 e2 = e->Iex.Binop.arg2;
1398 } else
1399
sewardjdcd6c882004-12-16 11:41:06 +00001400 /* Or8/16/32/64(t,t) ==> t, for some IRTemp t */
1401 /* And8/16/32/64(t,t) ==> t, for some IRTemp t */
1402 if ( (e->Iex.Binop.op == Iop_And64
1403 || e->Iex.Binop.op == Iop_And32
sewardjf6729012004-08-25 12:45:13 +00001404 || e->Iex.Binop.op == Iop_And16
sewardjdcd6c882004-12-16 11:41:06 +00001405 || e->Iex.Binop.op == Iop_And8
1406 || e->Iex.Binop.op == Iop_Or64
1407 || e->Iex.Binop.op == Iop_Or32
1408 || e->Iex.Binop.op == Iop_Or16
1409 || e->Iex.Binop.op == Iop_Or8)
sewardjf6729012004-08-25 12:45:13 +00001410 && sameIRTemps(e->Iex.Binop.arg1, e->Iex.Binop.arg2)) {
1411 e2 = e->Iex.Binop.arg1;
sewardjaba4fff2004-10-08 21:37:15 +00001412 }
sewardjf6729012004-08-25 12:45:13 +00001413
sewardj0033ddc2005-04-26 23:34:34 +00001414 /* Xor8/16/32/64(t,t) ==> 0, for some IRTemp t */
1415 if ( (e->Iex.Binop.op == Iop_Xor64
1416 || e->Iex.Binop.op == Iop_Xor32
1417 || e->Iex.Binop.op == Iop_Xor16
1418 || e->Iex.Binop.op == Iop_Xor8)
1419 && sameIRTemps(e->Iex.Binop.arg1, e->Iex.Binop.arg2)) {
sewardj0033ddc2005-04-26 23:34:34 +00001420 e2 = mkZeroForXor(e->Iex.Binop.op);
1421 }
1422
sewardj84be7372004-08-18 13:59:33 +00001423 }
1424 }
1425
1426 /* Mux0X */
1427 if (e->tag == Iex_Mux0X
1428 && e->Iex.Mux0X.cond->tag == Iex_Const) {
1429 Bool zero;
1430 /* assured us by the IR type rules */
1431 vassert(e->Iex.Mux0X.cond->Iex.Const.con->tag == Ico_U8);
sewardj9d2e7692005-02-07 01:11:31 +00001432 zero = toBool(0 == (0xFF & e->Iex.Mux0X.cond
1433 ->Iex.Const.con->Ico.U8));
sewardj84be7372004-08-18 13:59:33 +00001434 e2 = zero ? e->Iex.Mux0X.expr0 : e->Iex.Mux0X.exprX;
1435 }
1436
sewardj088bcb42004-08-19 17:16:52 +00001437 if (DEBUG_IROPT && e2 != e) {
1438 vex_printf("FOLD: ");
sewardj84be7372004-08-18 13:59:33 +00001439 ppIRExpr(e); vex_printf(" -> ");
1440 ppIRExpr(e2); vex_printf("\n");
1441 }
1442
1443 return e2;
1444
1445 unhandled:
sewardj883b00b2004-09-11 09:30:24 +00001446# if 0
sewardj84be7372004-08-18 13:59:33 +00001447 vex_printf("\n\n");
1448 ppIRExpr(e);
1449 vpanic("fold_Expr: no rule for the above");
sewardj883b00b2004-09-11 09:30:24 +00001450# else
sewardj328b54b2005-06-13 16:30:18 +00001451 if (vex_control.iropt_verbosity > 0) {
1452 vex_printf("vex iropt: fold_Expr: no rule for: ");
1453 ppIRExpr(e);
1454 vex_printf("\n");
1455 }
sewardj883b00b2004-09-11 09:30:24 +00001456 return e2;
1457# endif
sewardj84be7372004-08-18 13:59:33 +00001458}
1459
1460
sewardj84be7372004-08-18 13:59:33 +00001461/* Apply the subst to a simple 1-level expression -- guaranteed to be
1462 1-level due to previous flattening pass. */
1463
sewardj62617ef2004-10-13 23:29:22 +00001464static IRExpr* subst_Expr ( IRExpr** env, IRExpr* ex )
sewardj84be7372004-08-18 13:59:33 +00001465{
sewardj62617ef2004-10-13 23:29:22 +00001466 switch (ex->tag) {
1467 case Iex_Tmp:
1468 if (env[(Int)ex->Iex.Tmp.tmp] != NULL) {
1469 return env[(Int)ex->Iex.Tmp.tmp];
1470 } else {
1471 /* not bound in env */
1472 return ex;
1473 }
1474
1475 case Iex_Const:
1476 case Iex_Get:
sewardj84be7372004-08-18 13:59:33 +00001477 return ex;
sewardj62617ef2004-10-13 23:29:22 +00001478
1479 case Iex_GetI:
sewardj496a58d2005-03-20 18:44:44 +00001480 vassert(isIRAtom(ex->Iex.GetI.ix));
sewardj62617ef2004-10-13 23:29:22 +00001481 return IRExpr_GetI(
1482 ex->Iex.GetI.descr,
sewardjeeac8412004-11-02 00:26:55 +00001483 subst_Expr(env, ex->Iex.GetI.ix),
sewardj62617ef2004-10-13 23:29:22 +00001484 ex->Iex.GetI.bias
1485 );
1486
1487 case Iex_Binop:
sewardj496a58d2005-03-20 18:44:44 +00001488 vassert(isIRAtom(ex->Iex.Binop.arg1));
1489 vassert(isIRAtom(ex->Iex.Binop.arg2));
sewardj62617ef2004-10-13 23:29:22 +00001490 return IRExpr_Binop(
1491 ex->Iex.Binop.op,
1492 subst_Expr(env, ex->Iex.Binop.arg1),
1493 subst_Expr(env, ex->Iex.Binop.arg2)
1494 );
1495
1496 case Iex_Unop:
sewardj496a58d2005-03-20 18:44:44 +00001497 vassert(isIRAtom(ex->Iex.Unop.arg));
sewardj62617ef2004-10-13 23:29:22 +00001498 return IRExpr_Unop(
1499 ex->Iex.Unop.op,
1500 subst_Expr(env, ex->Iex.Unop.arg)
1501 );
1502
sewardjaf1ceca2005-06-30 23:31:27 +00001503 case Iex_Load:
1504 vassert(isIRAtom(ex->Iex.Load.addr));
1505 return IRExpr_Load(
1506 ex->Iex.Load.end,
1507 ex->Iex.Load.ty,
1508 subst_Expr(env, ex->Iex.Load.addr)
sewardj62617ef2004-10-13 23:29:22 +00001509 );
1510
1511 case Iex_CCall: {
1512 Int i;
1513 IRExpr** args2 = sopyIRExprVec(ex->Iex.CCall.args);
1514 for (i = 0; args2[i]; i++) {
sewardj496a58d2005-03-20 18:44:44 +00001515 vassert(isIRAtom(args2[i]));
sewardj62617ef2004-10-13 23:29:22 +00001516 args2[i] = subst_Expr(env, args2[i]);
1517 }
1518 return IRExpr_CCall(
sewardj8ea867b2004-10-30 19:03:02 +00001519 ex->Iex.CCall.cee,
sewardj62617ef2004-10-13 23:29:22 +00001520 ex->Iex.CCall.retty,
1521 args2
1522 );
sewardj84be7372004-08-18 13:59:33 +00001523 }
sewardj62617ef2004-10-13 23:29:22 +00001524
1525 case Iex_Mux0X:
sewardj496a58d2005-03-20 18:44:44 +00001526 vassert(isIRAtom(ex->Iex.Mux0X.cond));
1527 vassert(isIRAtom(ex->Iex.Mux0X.expr0));
1528 vassert(isIRAtom(ex->Iex.Mux0X.exprX));
sewardj62617ef2004-10-13 23:29:22 +00001529 return IRExpr_Mux0X(
1530 subst_Expr(env, ex->Iex.Mux0X.cond),
1531 subst_Expr(env, ex->Iex.Mux0X.expr0),
1532 subst_Expr(env, ex->Iex.Mux0X.exprX)
1533 );
1534
1535 default:
1536 vex_printf("\n\n"); ppIRExpr(ex);
1537 vpanic("subst_Expr");
1538
sewardj84be7372004-08-18 13:59:33 +00001539 }
sewardj84be7372004-08-18 13:59:33 +00001540}
1541
1542
1543/* Apply the subst to stmt, then fold the result as much as possible.
sewardjd2445f62005-03-21 00:15:53 +00001544 Much simplified due to stmt being previously flattened. As a
1545 result of this, the stmt may wind up being turned into a no-op.
1546*/
sewardj62617ef2004-10-13 23:29:22 +00001547static IRStmt* subst_and_fold_Stmt ( IRExpr** env, IRStmt* st )
sewardj84be7372004-08-18 13:59:33 +00001548{
1549# if 0
1550 vex_printf("\nsubst and fold stmt\n");
1551 ppIRStmt(st);
1552 vex_printf("\n");
1553# endif
1554
sewardj62617ef2004-10-13 23:29:22 +00001555 switch (st->tag) {
sewardj5a9ffab2005-05-12 17:55:01 +00001556 case Ist_AbiHint:
1557 vassert(isIRAtom(st->Ist.AbiHint.base));
1558 return IRStmt_AbiHint(
1559 fold_Expr(subst_Expr(env, st->Ist.AbiHint.base)),
1560 st->Ist.AbiHint.len
1561 );
sewardj62617ef2004-10-13 23:29:22 +00001562 case Ist_Put:
sewardj496a58d2005-03-20 18:44:44 +00001563 vassert(isIRAtom(st->Ist.Put.data));
sewardj62617ef2004-10-13 23:29:22 +00001564 return IRStmt_Put(
1565 st->Ist.Put.offset,
1566 fold_Expr(subst_Expr(env, st->Ist.Put.data))
1567 );
sewardj84be7372004-08-18 13:59:33 +00001568
sewardj62617ef2004-10-13 23:29:22 +00001569 case Ist_PutI:
sewardj496a58d2005-03-20 18:44:44 +00001570 vassert(isIRAtom(st->Ist.PutI.ix));
1571 vassert(isIRAtom(st->Ist.PutI.data));
sewardj62617ef2004-10-13 23:29:22 +00001572 return IRStmt_PutI(
1573 st->Ist.PutI.descr,
sewardjeeac8412004-11-02 00:26:55 +00001574 fold_Expr(subst_Expr(env, st->Ist.PutI.ix)),
sewardj62617ef2004-10-13 23:29:22 +00001575 st->Ist.PutI.bias,
1576 fold_Expr(subst_Expr(env, st->Ist.PutI.data))
1577 );
sewardjd7217032004-08-19 10:49:10 +00001578
sewardj62617ef2004-10-13 23:29:22 +00001579 case Ist_Tmp:
1580 /* This is the one place where an expr (st->Ist.Tmp.data) is
1581 allowed to be more than just a constant or a tmp. */
1582 return IRStmt_Tmp(
1583 st->Ist.Tmp.tmp,
1584 fold_Expr(subst_Expr(env, st->Ist.Tmp.data))
1585 );
sewardj84be7372004-08-18 13:59:33 +00001586
sewardjaf1ceca2005-06-30 23:31:27 +00001587 case Ist_Store:
1588 vassert(isIRAtom(st->Ist.Store.addr));
1589 vassert(isIRAtom(st->Ist.Store.data));
1590 return IRStmt_Store(
1591 st->Ist.Store.end,
1592 fold_Expr(subst_Expr(env, st->Ist.Store.addr)),
1593 fold_Expr(subst_Expr(env, st->Ist.Store.data))
sewardj62617ef2004-10-13 23:29:22 +00001594 );
sewardj84be7372004-08-18 13:59:33 +00001595
sewardj62617ef2004-10-13 23:29:22 +00001596 case Ist_Dirty: {
1597 Int i;
1598 IRDirty *d, *d2;
1599 d = st->Ist.Dirty.details;
1600 d2 = emptyIRDirty();
1601 *d2 = *d;
1602 d2->args = sopyIRExprVec(d2->args);
1603 if (d2->mFx != Ifx_None) {
sewardj496a58d2005-03-20 18:44:44 +00001604 vassert(isIRAtom(d2->mAddr));
sewardj62617ef2004-10-13 23:29:22 +00001605 d2->mAddr = fold_Expr(subst_Expr(env, d2->mAddr));
sewardjb8e75862004-08-19 17:58:45 +00001606 }
sewardj496a58d2005-03-20 18:44:44 +00001607 vassert(isIRAtom(d2->guard));
sewardjb8385d82004-11-02 01:34:15 +00001608 d2->guard = fold_Expr(subst_Expr(env, d2->guard));
sewardj62617ef2004-10-13 23:29:22 +00001609 for (i = 0; d2->args[i]; i++) {
sewardj496a58d2005-03-20 18:44:44 +00001610 vassert(isIRAtom(d2->args[i]));
sewardj62617ef2004-10-13 23:29:22 +00001611 d2->args[i] = fold_Expr(subst_Expr(env, d2->args[i]));
1612 }
1613 return IRStmt_Dirty(d2);
sewardjb8e75862004-08-19 17:58:45 +00001614 }
sewardj84be7372004-08-18 13:59:33 +00001615
sewardjf1689312005-03-16 18:19:10 +00001616 case Ist_IMark:
1617 return IRStmt_IMark(st->Ist.IMark.addr, st->Ist.IMark.len);
1618
sewardjd2445f62005-03-21 00:15:53 +00001619 case Ist_NoOp:
1620 return IRStmt_NoOp();
1621
sewardj3e838932005-01-07 12:09:15 +00001622 case Ist_MFence:
1623 return IRStmt_MFence();
1624
sewardj62617ef2004-10-13 23:29:22 +00001625 case Ist_Exit: {
1626 IRExpr* fcond;
sewardj496a58d2005-03-20 18:44:44 +00001627 vassert(isIRAtom(st->Ist.Exit.guard));
sewardj0276d4b2004-11-15 15:30:21 +00001628 fcond = fold_Expr(subst_Expr(env, st->Ist.Exit.guard));
sewardj62617ef2004-10-13 23:29:22 +00001629 if (fcond->tag == Iex_Const) {
1630 /* Interesting. The condition on this exit has folded down to
1631 a constant. */
sewardjba999312004-11-15 15:21:17 +00001632 vassert(fcond->Iex.Const.con->tag == Ico_U1);
sewardj98430292004-12-29 17:34:50 +00001633 vassert(fcond->Iex.Const.con->Ico.U1 == False
1634 || fcond->Iex.Const.con->Ico.U1 == True);
sewardjba999312004-11-15 15:21:17 +00001635 if (fcond->Iex.Const.con->Ico.U1 == False) {
sewardj62617ef2004-10-13 23:29:22 +00001636 /* exit is never going to happen, so dump the statement. */
sewardjd2445f62005-03-21 00:15:53 +00001637 return IRStmt_NoOp();
sewardj62617ef2004-10-13 23:29:22 +00001638 } else {
sewardjba999312004-11-15 15:21:17 +00001639 vassert(fcond->Iex.Const.con->Ico.U1 == True);
sewardj62617ef2004-10-13 23:29:22 +00001640 /* Hmmm. The exit has become unconditional. Leave it as
1641 it is for now, since we'd have to truncate the BB at
1642 this point, which is tricky. */
1643 /* fall out into the reconstruct-the-exit code. */
sewardj08613742004-10-25 13:01:45 +00001644 if (vex_control.iropt_verbosity > 0)
1645 /* really a misuse of vex_control.iropt_verbosity */
sewardj8c2c10b2004-10-16 20:51:52 +00001646 vex_printf("vex iropt: IRStmt_Exit became unconditional\n");
sewardj62617ef2004-10-13 23:29:22 +00001647 }
1648 }
sewardj893aada2004-11-29 19:57:54 +00001649 return IRStmt_Exit(fcond, st->Ist.Exit.jk, st->Ist.Exit.dst);
sewardj62617ef2004-10-13 23:29:22 +00001650 }
1651
1652 default:
1653 vex_printf("\n"); ppIRStmt(st);
1654 vpanic("subst_and_fold_Stmt");
1655 }
sewardj84be7372004-08-18 13:59:33 +00001656}
1657
1658
sewardjd9997882004-11-04 19:42:59 +00001659IRBB* cprop_BB ( IRBB* in )
sewardj84be7372004-08-18 13:59:33 +00001660{
sewardj62617ef2004-10-13 23:29:22 +00001661 Int i;
1662 IRBB* out;
1663 IRStmt* st2;
1664 Int n_tmps = in->tyenv->types_used;
1665 IRExpr** env = LibVEX_Alloc(n_tmps * sizeof(IRExpr*));
sewardj84be7372004-08-18 13:59:33 +00001666
1667 out = emptyIRBB();
sewardj695cff92004-10-13 14:50:14 +00001668 out->tyenv = dopyIRTypeEnv( in->tyenv );
sewardj84be7372004-08-18 13:59:33 +00001669
1670 /* Set up the env with which travels forward. This holds a
1671 substitution, mapping IRTemps to atoms, that is, IRExprs which
1672 are either IRTemps or IRConsts. Thus, copy and constant
1673 propagation is done. The environment is to be applied as we
1674 move along. Keys are IRTemps. Values are IRExpr*s.
1675 */
sewardj62617ef2004-10-13 23:29:22 +00001676 for (i = 0; i < n_tmps; i++)
1677 env[i] = NULL;
sewardj84be7372004-08-18 13:59:33 +00001678
1679 /* For each original SSA-form stmt ... */
1680 for (i = 0; i < in->stmts_used; i++) {
1681
1682 /* First apply the substitution to the current stmt. This
1683 propagates in any constants and tmp-tmp assignments
1684 accumulated prior to this point. As part of the subst_Stmt
1685 call, also then fold any constant expressions resulting. */
1686
sewardjf0e43162004-08-20 00:11:12 +00001687 st2 = in->stmts[i];
1688
1689 /* perhaps st2 is already a no-op? */
sewardj8bee6d12005-03-22 02:24:05 +00001690 if (st2->tag == Ist_NoOp) continue;
sewardjf0e43162004-08-20 00:11:12 +00001691
1692 st2 = subst_and_fold_Stmt( env, st2 );
sewardj84be7372004-08-18 13:59:33 +00001693
sewardjb8e75862004-08-19 17:58:45 +00001694 /* If the statement has been folded into a no-op, forget it. */
sewardj8bee6d12005-03-22 02:24:05 +00001695 if (st2->tag == Ist_NoOp) continue;
sewardjb8e75862004-08-19 17:58:45 +00001696
sewardj84be7372004-08-18 13:59:33 +00001697 /* Now consider what the stmt looks like. If it's of the form
1698 't = const' or 't1 = t2', add it to the running environment
1699 and not to the output BB. Otherwise, add it to the output
sewardjc0b42282004-10-12 13:44:12 +00001700 BB. Note, we choose not to propagate const when const is an
1701 F64i, so that F64i literals can be CSE'd later. This helps
1702 x86 floating point code generation. */
sewardj84be7372004-08-18 13:59:33 +00001703
sewardjc0b42282004-10-12 13:44:12 +00001704 if (st2->tag == Ist_Tmp
1705 && st2->Ist.Tmp.data->tag == Iex_Const
1706 && st2->Ist.Tmp.data->Iex.Const.con->tag != Ico_F64i) {
sewardj84be7372004-08-18 13:59:33 +00001707 /* 't = const' -- add to env.
1708 The pair (IRTemp, IRExpr*) is added. */
sewardj62617ef2004-10-13 23:29:22 +00001709 env[(Int)(st2->Ist.Tmp.tmp)] = st2->Ist.Tmp.data;
sewardj84be7372004-08-18 13:59:33 +00001710 }
1711 else
sewardj6d076362004-09-23 11:06:17 +00001712 if (st2->tag == Ist_Tmp && st2->Ist.Tmp.data->tag == Iex_Tmp) {
sewardj84be7372004-08-18 13:59:33 +00001713 /* 't1 = t2' -- add to env.
1714 The pair (IRTemp, IRExpr*) is added. */
sewardj62617ef2004-10-13 23:29:22 +00001715 env[(Int)(st2->Ist.Tmp.tmp)] = st2->Ist.Tmp.data;
sewardj84be7372004-08-18 13:59:33 +00001716 }
1717 else {
1718 /* Not interesting, copy st2 into the output block. */
1719 addStmtToIRBB( out, st2 );
1720 }
1721 }
1722
sewardj84be7372004-08-18 13:59:33 +00001723 out->next = subst_Expr( env, in->next );
1724 out->jumpkind = in->jumpkind;
1725 return out;
1726}
1727
1728
1729
sewardjedf4d692004-08-17 13:52:58 +00001730/*---------------------------------------------------------------*/
sewardj39e3f242004-08-18 16:54:52 +00001731/*--- Dead code (t = E) removal ---*/
1732/*---------------------------------------------------------------*/
1733
sewardjea602bc2004-10-14 21:40:12 +00001734/* The type of the HashHW map is: a map from IRTemp to nothing
sewardj39e3f242004-08-18 16:54:52 +00001735 -- really just operating a set or IRTemps.
1736*/
1737
sewardjd503a322004-10-13 22:41:16 +00001738inline
1739static void addUses_Temp ( Bool* set, IRTemp tmp )
sewardj17442fe2004-09-20 14:54:28 +00001740{
sewardjd503a322004-10-13 22:41:16 +00001741 set[(Int)tmp] = True;
sewardj17442fe2004-09-20 14:54:28 +00001742}
1743
sewardjd503a322004-10-13 22:41:16 +00001744static void addUses_Expr ( Bool* set, IRExpr* e )
sewardj39e3f242004-08-18 16:54:52 +00001745{
1746 Int i;
1747 switch (e->tag) {
sewardjd7217032004-08-19 10:49:10 +00001748 case Iex_GetI:
sewardjeeac8412004-11-02 00:26:55 +00001749 addUses_Expr(set, e->Iex.GetI.ix);
sewardjd7217032004-08-19 10:49:10 +00001750 return;
sewardj39e3f242004-08-18 16:54:52 +00001751 case Iex_Mux0X:
1752 addUses_Expr(set, e->Iex.Mux0X.cond);
1753 addUses_Expr(set, e->Iex.Mux0X.expr0);
1754 addUses_Expr(set, e->Iex.Mux0X.exprX);
1755 return;
1756 case Iex_CCall:
1757 for (i = 0; e->Iex.CCall.args[i]; i++)
1758 addUses_Expr(set, e->Iex.CCall.args[i]);
1759 return;
sewardjaf1ceca2005-06-30 23:31:27 +00001760 case Iex_Load:
1761 addUses_Expr(set, e->Iex.Load.addr);
sewardj39e3f242004-08-18 16:54:52 +00001762 return;
1763 case Iex_Binop:
1764 addUses_Expr(set, e->Iex.Binop.arg1);
1765 addUses_Expr(set, e->Iex.Binop.arg2);
1766 return;
1767 case Iex_Unop:
1768 addUses_Expr(set, e->Iex.Unop.arg);
1769 return;
1770 case Iex_Tmp:
sewardj17442fe2004-09-20 14:54:28 +00001771 addUses_Temp(set, e->Iex.Tmp.tmp);
sewardj39e3f242004-08-18 16:54:52 +00001772 return;
1773 case Iex_Const:
1774 case Iex_Get:
1775 return;
1776 default:
1777 vex_printf("\n");
1778 ppIRExpr(e);
1779 vpanic("addUses_Expr");
1780 }
1781}
1782
sewardjd503a322004-10-13 22:41:16 +00001783static void addUses_Stmt ( Bool* set, IRStmt* st )
sewardj39e3f242004-08-18 16:54:52 +00001784{
sewardj17442fe2004-09-20 14:54:28 +00001785 Int i;
1786 IRDirty* d;
sewardj39e3f242004-08-18 16:54:52 +00001787 switch (st->tag) {
sewardj5a9ffab2005-05-12 17:55:01 +00001788 case Ist_AbiHint:
1789 addUses_Expr(set, st->Ist.AbiHint.base);
1790 return;
sewardjd7217032004-08-19 10:49:10 +00001791 case Ist_PutI:
sewardjeeac8412004-11-02 00:26:55 +00001792 addUses_Expr(set, st->Ist.PutI.ix);
sewardj2d3f77c2004-09-22 23:49:09 +00001793 addUses_Expr(set, st->Ist.PutI.data);
sewardjd7217032004-08-19 10:49:10 +00001794 return;
sewardj39e3f242004-08-18 16:54:52 +00001795 case Ist_Tmp:
sewardj6d076362004-09-23 11:06:17 +00001796 addUses_Expr(set, st->Ist.Tmp.data);
sewardj39e3f242004-08-18 16:54:52 +00001797 return;
1798 case Ist_Put:
sewardj6d076362004-09-23 11:06:17 +00001799 addUses_Expr(set, st->Ist.Put.data);
sewardj39e3f242004-08-18 16:54:52 +00001800 return;
sewardjaf1ceca2005-06-30 23:31:27 +00001801 case Ist_Store:
1802 addUses_Expr(set, st->Ist.Store.addr);
1803 addUses_Expr(set, st->Ist.Store.data);
sewardj39e3f242004-08-18 16:54:52 +00001804 return;
sewardj17442fe2004-09-20 14:54:28 +00001805 case Ist_Dirty:
1806 d = st->Ist.Dirty.details;
1807 if (d->mFx != Ifx_None)
1808 addUses_Expr(set, d->mAddr);
sewardjb8385d82004-11-02 01:34:15 +00001809 addUses_Expr(set, d->guard);
sewardj17442fe2004-09-20 14:54:28 +00001810 for (i = 0; d->args[i] != NULL; i++)
1811 addUses_Expr(set, d->args[i]);
1812 return;
sewardjd2445f62005-03-21 00:15:53 +00001813 case Ist_NoOp:
sewardjf1689312005-03-16 18:19:10 +00001814 case Ist_IMark:
sewardj3e838932005-01-07 12:09:15 +00001815 case Ist_MFence:
1816 return;
sewardj17442fe2004-09-20 14:54:28 +00001817 case Ist_Exit:
sewardj0276d4b2004-11-15 15:30:21 +00001818 addUses_Expr(set, st->Ist.Exit.guard);
sewardj17442fe2004-09-20 14:54:28 +00001819 return;
sewardj39e3f242004-08-18 16:54:52 +00001820 default:
1821 vex_printf("\n");
1822 ppIRStmt(st);
1823 vpanic("addUses_Stmt");
sewardjd503a322004-10-13 22:41:16 +00001824 }
sewardj39e3f242004-08-18 16:54:52 +00001825}
1826
1827
sewardjba999312004-11-15 15:21:17 +00001828/* Is this literally IRExpr_Const(IRConst_U1(False)) ? */
1829static Bool isZeroU1 ( IRExpr* e )
sewardjd9997882004-11-04 19:42:59 +00001830{
sewardj9d2e7692005-02-07 01:11:31 +00001831 return toBool( e->tag == Iex_Const
1832 && e->Iex.Const.con->tag == Ico_U1
1833 && e->Iex.Const.con->Ico.U1 == False );
sewardjd9997882004-11-04 19:42:59 +00001834}
1835
sewardj39e3f242004-08-18 16:54:52 +00001836
1837/* Note, this destructively modifies the given IRBB. */
1838
1839/* Scan backwards through statements, carrying a set of IRTemps which
1840 are known to be used after the current point. On encountering 't =
1841 E', delete the binding if it is not used. Otherwise, add any temp
1842 uses to the set and keep on moving backwards. */
1843
sewardj49651f42004-10-28 22:11:04 +00001844/* notstatic */ void do_deadcode_BB ( IRBB* bb )
sewardj39e3f242004-08-18 16:54:52 +00001845{
1846 Int i;
sewardjd503a322004-10-13 22:41:16 +00001847 Int n_tmps = bb->tyenv->types_used;
1848 Bool* set = LibVEX_Alloc(n_tmps * sizeof(Bool));
sewardj39e3f242004-08-18 16:54:52 +00001849 IRStmt* st;
1850
sewardjd503a322004-10-13 22:41:16 +00001851 for (i = 0; i < n_tmps; i++)
1852 set[i] = False;
1853
sewardj39e3f242004-08-18 16:54:52 +00001854 /* start off by recording IRTemp uses in the next field. */
1855 addUses_Expr(set, bb->next);
1856
1857 /* Work backwards through the stmts */
1858 for (i = bb->stmts_used-1; i >= 0; i--) {
1859 st = bb->stmts[i];
sewardj8bee6d12005-03-22 02:24:05 +00001860 if (st->tag == Ist_NoOp)
sewardj84ff0652004-08-23 16:16:08 +00001861 continue;
sewardj39e3f242004-08-18 16:54:52 +00001862 if (st->tag == Ist_Tmp
sewardjd503a322004-10-13 22:41:16 +00001863 && set[(Int)(st->Ist.Tmp.tmp)] == False) {
sewardj39e3f242004-08-18 16:54:52 +00001864 /* it's an IRTemp which never got used. Delete it. */
sewardj088bcb42004-08-19 17:16:52 +00001865 if (DEBUG_IROPT) {
sewardj39e3f242004-08-18 16:54:52 +00001866 vex_printf("DEAD: ");
1867 ppIRStmt(st);
1868 vex_printf("\n");
1869 }
sewardjd2445f62005-03-21 00:15:53 +00001870 bb->stmts[i] = IRStmt_NoOp();
sewardjd9997882004-11-04 19:42:59 +00001871 }
1872 else
1873 if (st->tag == Ist_Dirty
1874 && st->Ist.Dirty.details->guard
sewardjba999312004-11-15 15:21:17 +00001875 && isZeroU1(st->Ist.Dirty.details->guard)) {
sewardjd2445f62005-03-21 00:15:53 +00001876 /* This is a dirty helper which will never get called.
1877 Delete it. */
1878 bb->stmts[i] = IRStmt_NoOp();
sewardjd9997882004-11-04 19:42:59 +00001879 }
1880 else {
sewardj39e3f242004-08-18 16:54:52 +00001881 /* Note any IRTemp uses made by the current statement. */
1882 addUses_Stmt(set, st);
1883 }
1884 }
1885}
1886
sewardj84ff0652004-08-23 16:16:08 +00001887/*---------------------------------------------------------------*/
1888/*--- Specialisation of helper function calls, in ---*/
1889/*--- collaboration with the front end ---*/
1890/*---------------------------------------------------------------*/
1891
1892static
sewardjb9230752004-12-29 19:25:06 +00001893IRBB* spec_helpers_BB ( IRBB* bb,
sewardj9d2e7692005-02-07 01:11:31 +00001894 IRExpr* (*specHelper) ( HChar*, IRExpr**) )
sewardj84ff0652004-08-23 16:16:08 +00001895{
sewardjb9230752004-12-29 19:25:06 +00001896 Int i;
sewardj84ff0652004-08-23 16:16:08 +00001897 IRStmt* st;
1898 IRExpr* ex;
sewardjb9230752004-12-29 19:25:06 +00001899 Bool any = False;
sewardj84ff0652004-08-23 16:16:08 +00001900
1901 for (i = bb->stmts_used-1; i >= 0; i--) {
1902 st = bb->stmts[i];
1903
sewardj8bee6d12005-03-22 02:24:05 +00001904 if (st->tag != Ist_Tmp
sewardj6d076362004-09-23 11:06:17 +00001905 || st->Ist.Tmp.data->tag != Iex_CCall)
sewardj8bee6d12005-03-22 02:24:05 +00001906 continue;
sewardj84ff0652004-08-23 16:16:08 +00001907
sewardj8ea867b2004-10-30 19:03:02 +00001908 ex = (*specHelper)( st->Ist.Tmp.data->Iex.CCall.cee->name,
sewardj6d076362004-09-23 11:06:17 +00001909 st->Ist.Tmp.data->Iex.CCall.args );
sewardj84ff0652004-08-23 16:16:08 +00001910 if (!ex)
sewardjaba4fff2004-10-08 21:37:15 +00001911 /* the front end can't think of a suitable replacement */
1912 continue;
sewardj84ff0652004-08-23 16:16:08 +00001913
1914 /* We got something better. Install it in the bb. */
sewardjb9230752004-12-29 19:25:06 +00001915 any = True;
sewardj84ff0652004-08-23 16:16:08 +00001916 bb->stmts[i]
1917 = IRStmt_Tmp(st->Ist.Tmp.tmp, ex);
1918
1919 if (0) {
1920 vex_printf("SPEC: ");
sewardj6d076362004-09-23 11:06:17 +00001921 ppIRExpr(st->Ist.Tmp.data);
sewardj84ff0652004-08-23 16:16:08 +00001922 vex_printf(" --> ");
1923 ppIRExpr(ex);
1924 vex_printf("\n");
1925 }
1926 }
sewardjb9230752004-12-29 19:25:06 +00001927
1928 if (any)
1929 bb = flatten_BB(bb);
1930 return bb;
sewardj84ff0652004-08-23 16:16:08 +00001931}
1932
sewardj29632392004-08-22 02:38:11 +00001933
1934/*---------------------------------------------------------------*/
sewardj08210532004-12-29 17:09:11 +00001935/*--- Common Subexpression Elimination ---*/
1936/*---------------------------------------------------------------*/
1937
1938/* Expensive in time and space. */
1939
1940/* Uses two environments:
1941 a IRTemp -> IRTemp mapping
1942 a mapping from AvailExpr* to IRTemp
1943*/
1944
1945typedef
1946 struct {
1947 enum { Ut, Btt, Btc, Bct, Cf64i } tag;
1948 union {
1949 /* unop(tmp) */
1950 struct {
1951 IROp op;
1952 IRTemp arg;
1953 } Ut;
1954 /* binop(tmp,tmp) */
1955 struct {
1956 IROp op;
1957 IRTemp arg1;
1958 IRTemp arg2;
1959 } Btt;
1960 /* binop(tmp,const) */
1961 struct {
1962 IROp op;
1963 IRTemp arg1;
1964 IRConst con2;
1965 } Btc;
1966 /* binop(const,tmp) */
1967 struct {
1968 IROp op;
1969 IRConst con1;
1970 IRTemp arg2;
1971 } Bct;
1972 /* F64i-style const */
1973 struct {
1974 ULong f64i;
1975 } Cf64i;
1976 } u;
1977 }
1978 AvailExpr;
1979
1980static Bool eq_AvailExpr ( AvailExpr* a1, AvailExpr* a2 )
1981{
1982 if (a1->tag != a2->tag)
1983 return False;
1984 switch (a1->tag) {
1985 case Ut:
sewardj9d2e7692005-02-07 01:11:31 +00001986 return toBool(
1987 a1->u.Ut.op == a2->u.Ut.op
1988 && a1->u.Ut.arg == a2->u.Ut.arg);
sewardj08210532004-12-29 17:09:11 +00001989 case Btt:
sewardj9d2e7692005-02-07 01:11:31 +00001990 return toBool(
1991 a1->u.Btt.op == a2->u.Btt.op
sewardj08210532004-12-29 17:09:11 +00001992 && a1->u.Btt.arg1 == a2->u.Btt.arg1
sewardj9d2e7692005-02-07 01:11:31 +00001993 && a1->u.Btt.arg2 == a2->u.Btt.arg2);
sewardj08210532004-12-29 17:09:11 +00001994 case Btc:
sewardj9d2e7692005-02-07 01:11:31 +00001995 return toBool(
1996 a1->u.Btc.op == a2->u.Btc.op
sewardj08210532004-12-29 17:09:11 +00001997 && a1->u.Btc.arg1 == a2->u.Btc.arg1
sewardj9d2e7692005-02-07 01:11:31 +00001998 && eqIRConst(&a1->u.Btc.con2, &a2->u.Btc.con2));
sewardj08210532004-12-29 17:09:11 +00001999 case Bct:
sewardj9d2e7692005-02-07 01:11:31 +00002000 return toBool(
2001 a1->u.Bct.op == a2->u.Bct.op
sewardj08210532004-12-29 17:09:11 +00002002 && a1->u.Bct.arg2 == a2->u.Bct.arg2
sewardj9d2e7692005-02-07 01:11:31 +00002003 && eqIRConst(&a1->u.Bct.con1, &a2->u.Bct.con1));
sewardj08210532004-12-29 17:09:11 +00002004 case Cf64i:
sewardj9d2e7692005-02-07 01:11:31 +00002005 return toBool(a1->u.Cf64i.f64i == a2->u.Cf64i.f64i);
sewardj08210532004-12-29 17:09:11 +00002006 default: vpanic("eq_AvailExpr");
2007 }
2008}
2009
2010static IRExpr* availExpr_to_IRExpr ( AvailExpr* ae )
2011{
2012 IRConst* con;
2013 switch (ae->tag) {
2014 case Ut:
2015 return IRExpr_Unop( ae->u.Ut.op, IRExpr_Tmp(ae->u.Ut.arg) );
2016 case Btt:
2017 return IRExpr_Binop( ae->u.Btt.op,
2018 IRExpr_Tmp(ae->u.Btt.arg1),
2019 IRExpr_Tmp(ae->u.Btt.arg2) );
2020 case Btc:
2021 con = LibVEX_Alloc(sizeof(IRConst));
2022 *con = ae->u.Btc.con2;
2023 return IRExpr_Binop( ae->u.Btc.op,
2024 IRExpr_Tmp(ae->u.Btc.arg1), IRExpr_Const(con) );
2025 case Bct:
2026 con = LibVEX_Alloc(sizeof(IRConst));
2027 *con = ae->u.Bct.con1;
2028 return IRExpr_Binop( ae->u.Bct.op,
2029 IRExpr_Const(con), IRExpr_Tmp(ae->u.Bct.arg2) );
2030 case Cf64i:
2031 return IRExpr_Const(IRConst_F64i(ae->u.Cf64i.f64i));
2032 default:
2033 vpanic("availExpr_to_IRExpr");
2034 }
2035}
2036
2037inline
2038static IRTemp subst_AvailExpr_Temp ( HashHW* env, IRTemp tmp )
2039{
2040 HWord res;
2041 /* env :: IRTemp -> IRTemp */
2042 if (lookupHHW( env, &res, (HWord)tmp ))
2043 return (IRTemp)res;
2044 else
2045 return tmp;
2046}
2047
2048static void subst_AvailExpr ( HashHW* env, AvailExpr* ae )
2049{
2050 /* env :: IRTemp -> IRTemp */
2051 switch (ae->tag) {
2052 case Ut:
2053 ae->u.Ut.arg = subst_AvailExpr_Temp( env, ae->u.Ut.arg );
2054 break;
2055 case Btt:
2056 ae->u.Btt.arg1 = subst_AvailExpr_Temp( env, ae->u.Btt.arg1 );
2057 ae->u.Btt.arg2 = subst_AvailExpr_Temp( env, ae->u.Btt.arg2 );
2058 break;
2059 case Btc:
2060 ae->u.Btc.arg1 = subst_AvailExpr_Temp( env, ae->u.Btc.arg1 );
2061 break;
2062 case Bct:
2063 ae->u.Bct.arg2 = subst_AvailExpr_Temp( env, ae->u.Bct.arg2 );
2064 break;
2065 case Cf64i:
2066 break;
2067 default:
2068 vpanic("subst_AvailExpr");
2069 }
2070}
2071
2072static AvailExpr* irExpr_to_AvailExpr ( IRExpr* e )
2073{
2074 AvailExpr* ae;
2075
2076 if (e->tag == Iex_Unop
2077 && e->Iex.Unop.arg->tag == Iex_Tmp) {
2078 ae = LibVEX_Alloc(sizeof(AvailExpr));
2079 ae->tag = Ut;
2080 ae->u.Ut.op = e->Iex.Unop.op;
2081 ae->u.Ut.arg = e->Iex.Unop.arg->Iex.Tmp.tmp;
2082 return ae;
2083 }
2084
2085 if (e->tag == Iex_Binop
2086 && e->Iex.Binop.arg1->tag == Iex_Tmp
2087 && e->Iex.Binop.arg2->tag == Iex_Tmp) {
2088 ae = LibVEX_Alloc(sizeof(AvailExpr));
2089 ae->tag = Btt;
2090 ae->u.Btt.op = e->Iex.Binop.op;
2091 ae->u.Btt.arg1 = e->Iex.Binop.arg1->Iex.Tmp.tmp;
2092 ae->u.Btt.arg2 = e->Iex.Binop.arg2->Iex.Tmp.tmp;
2093 return ae;
2094 }
2095
2096 if (e->tag == Iex_Binop
2097 && e->Iex.Binop.arg1->tag == Iex_Tmp
2098 && e->Iex.Binop.arg2->tag == Iex_Const) {
2099 ae = LibVEX_Alloc(sizeof(AvailExpr));
2100 ae->tag = Btc;
2101 ae->u.Btc.op = e->Iex.Binop.op;
2102 ae->u.Btc.arg1 = e->Iex.Binop.arg1->Iex.Tmp.tmp;
2103 ae->u.Btc.con2 = *(e->Iex.Binop.arg2->Iex.Const.con);
2104 return ae;
2105 }
2106
2107 if (e->tag == Iex_Binop
2108 && e->Iex.Binop.arg1->tag == Iex_Const
2109 && e->Iex.Binop.arg2->tag == Iex_Tmp) {
2110 ae = LibVEX_Alloc(sizeof(AvailExpr));
2111 ae->tag = Bct;
2112 ae->u.Bct.op = e->Iex.Binop.op;
2113 ae->u.Bct.arg2 = e->Iex.Binop.arg2->Iex.Tmp.tmp;
2114 ae->u.Bct.con1 = *(e->Iex.Binop.arg1->Iex.Const.con);
2115 return ae;
2116 }
2117
2118 if (e->tag == Iex_Const
2119 && e->Iex.Const.con->tag == Ico_F64i) {
2120 ae = LibVEX_Alloc(sizeof(AvailExpr));
2121 ae->tag = Cf64i;
2122 ae->u.Cf64i.f64i = e->Iex.Const.con->Ico.F64i;
2123 return ae;
2124 }
2125
2126 return NULL;
2127}
2128
2129
2130/* The BB is modified in-place. */
2131
2132void do_cse_BB ( IRBB* bb )
2133{
2134 Int i, j;
2135 IRTemp t, q;
2136 IRStmt* st;
2137 AvailExpr* eprime;
2138
2139 HashHW* tenv = newHHW(); /* :: IRTemp -> IRTemp */
2140 HashHW* aenv = newHHW(); /* :: AvailExpr* -> IRTemp */
2141
2142 vassert(sizeof(IRTemp) <= sizeof(HWord));
2143
2144 //ppIRBB(bb);
2145 //vex_printf("\n\n");
2146
2147 /* Iterate forwards over the stmts.
2148 On seeing "t = E", where E is one of the 3 AvailExpr forms:
2149 let E' = apply tenv substitution to E
2150 search aenv for E'
2151 if a mapping E' -> q is found,
2152 replace this stmt by "t = q"
2153 and add binding t -> q to tenv
2154 else
2155 add binding E' -> t to aenv
2156 replace this stmt by "t = E'"
2157 Ignore any other kind of stmt.
2158 */
2159 for (i = 0; i < bb->stmts_used; i++) {
2160 st = bb->stmts[i];
2161
2162 /* ignore not-interestings */
sewardj8bee6d12005-03-22 02:24:05 +00002163 if (st->tag != Ist_Tmp)
sewardj08210532004-12-29 17:09:11 +00002164 continue;
2165
2166 t = st->Ist.Tmp.tmp;
2167 eprime = irExpr_to_AvailExpr(st->Ist.Tmp.data);
2168 /* ignore if not of AvailExpr form */
2169 if (!eprime)
2170 continue;
2171
2172 /* vex_printf("considering: " ); ppIRStmt(st); vex_printf("\n"); */
2173
2174 /* apply tenv */
2175 subst_AvailExpr( tenv, eprime );
2176
2177 /* search aenv for eprime, unfortunately the hard way */
2178 for (j = 0; j < aenv->used; j++)
2179 if (aenv->inuse[j] && eq_AvailExpr(eprime, (AvailExpr*)aenv->key[j]))
2180 break;
2181
2182 if (j < aenv->used) {
2183 /* A binding E' -> q was found. Replace stmt by "t = q" and
2184 note the t->q binding in tenv. */
2185 /* (this is the core of the CSE action) */
2186 q = (IRTemp)aenv->val[j];
2187 bb->stmts[i] = IRStmt_Tmp( t, IRExpr_Tmp(q) );
2188 addToHHW( tenv, (HWord)t, (HWord)q );
2189 } else {
2190 /* No binding was found, so instead we add E' -> t to our
2191 collection of available expressions, replace this stmt
2192 with "t = E'", and move on. */
2193 bb->stmts[i] = IRStmt_Tmp( t, availExpr_to_IRExpr(eprime) );
2194 addToHHW( aenv, (HWord)eprime, (HWord)t );
2195 }
2196 }
2197
2198 //ppIRBB(bb);
2199 //sanityCheckIRBB(bb, Ity_I32);
2200 //vex_printf("\n\n");
2201
2202}
2203
2204
2205/*---------------------------------------------------------------*/
2206/*--- Add32/Sub32 chain collapsing ---*/
2207/*---------------------------------------------------------------*/
2208
2209/* ----- Helper functions for Add32/Sub32 chain collapsing ----- */
2210
2211/* Is this expression "Add32(tmp,const)" or "Sub32(tmp,const)" ? If
2212 yes, set *tmp and *i32 appropriately. *i32 is set as if the
2213 root node is Add32, not Sub32. */
2214
2215static Bool isAdd32OrSub32 ( IRExpr* e, IRTemp* tmp, Int* i32 )
2216{
2217 if (e->tag != Iex_Binop)
2218 return False;
2219 if (e->Iex.Binop.op != Iop_Add32 && e->Iex.Binop.op != Iop_Sub32)
2220 return False;
2221 if (e->Iex.Binop.arg1->tag != Iex_Tmp)
2222 return False;
2223 if (e->Iex.Binop.arg2->tag != Iex_Const)
2224 return False;
2225 *tmp = e->Iex.Binop.arg1->Iex.Tmp.tmp;
2226 *i32 = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32);
2227 if (e->Iex.Binop.op == Iop_Sub32)
2228 *i32 = -*i32;
2229 return True;
2230}
2231
2232
2233/* Figure out if tmp can be expressed as tmp2 +32 const, for some
2234 other tmp2. Scan backwards from the specified start point -- an
2235 optimisation. */
2236
2237static Bool collapseChain ( IRBB* bb, Int startHere,
2238 IRTemp tmp,
2239 IRTemp* tmp2, Int* i32 )
2240{
2241 Int j, ii;
2242 IRTemp vv;
2243 IRStmt* st;
2244 IRExpr* e;
2245
2246 /* the (var, con) pair contain the current 'representation' for
2247 'tmp'. We start with 'tmp + 0'. */
2248 IRTemp var = tmp;
2249 Int con = 0;
2250
2251 /* Scan backwards to see if tmp can be replaced by some other tmp
2252 +/- a constant. */
2253 for (j = startHere; j >= 0; j--) {
2254 st = bb->stmts[j];
sewardj8bee6d12005-03-22 02:24:05 +00002255 if (st->tag != Ist_Tmp)
sewardj08210532004-12-29 17:09:11 +00002256 continue;
2257 if (st->Ist.Tmp.tmp != var)
2258 continue;
2259 e = st->Ist.Tmp.data;
2260 if (!isAdd32OrSub32(e, &vv, &ii))
2261 break;
2262 var = vv;
2263 con += ii;
2264 }
2265 if (j == -1)
2266 /* no earlier binding for var .. ill-formed IR */
2267 vpanic("collapseChain");
2268
2269 /* so, did we find anything interesting? */
2270 if (var == tmp)
2271 return False; /* no .. */
2272
2273 *tmp2 = var;
2274 *i32 = con;
2275 return True;
2276}
2277
2278
2279/* ------- Main function for Add32/Sub32 chain collapsing ------ */
2280
2281static void collapse_AddSub_chains_BB ( IRBB* bb )
2282{
2283 IRStmt *st;
2284 IRTemp var, var2;
2285 Int i, con, con2;
2286
2287 for (i = bb->stmts_used-1; i >= 0; i--) {
2288 st = bb->stmts[i];
sewardj8bee6d12005-03-22 02:24:05 +00002289 if (st->tag == Ist_NoOp)
sewardj08210532004-12-29 17:09:11 +00002290 continue;
2291
2292 /* Try to collapse 't1 = Add32/Sub32(t2, con)'. */
2293
2294 if (st->tag == Ist_Tmp
2295 && isAdd32OrSub32(st->Ist.Tmp.data, &var, &con)) {
2296
2297 /* So e1 is of the form Add32(var,con) or Sub32(var,-con).
2298 Find out if var can be expressed as var2 + con2. */
2299 if (collapseChain(bb, i-1, var, &var2, &con2)) {
2300 if (DEBUG_IROPT) {
2301 vex_printf("replacing1 ");
2302 ppIRStmt(st);
2303 vex_printf(" with ");
2304 }
2305 con2 += con;
2306 bb->stmts[i]
2307 = IRStmt_Tmp(
2308 st->Ist.Tmp.tmp,
2309 (con2 >= 0)
2310 ? IRExpr_Binop(Iop_Add32,
2311 IRExpr_Tmp(var2),
2312 IRExpr_Const(IRConst_U32(con2)))
2313 : IRExpr_Binop(Iop_Sub32,
2314 IRExpr_Tmp(var2),
2315 IRExpr_Const(IRConst_U32(-con2)))
2316 );
2317 if (DEBUG_IROPT) {
2318 ppIRStmt(bb->stmts[i]);
2319 vex_printf("\n");
2320 }
2321 }
2322
2323 continue;
2324 }
2325
2326 /* Try to collapse 't1 = GetI[t2, con]'. */
2327
2328 if (st->tag == Ist_Tmp
2329 && st->Ist.Tmp.data->tag == Iex_GetI
2330 && st->Ist.Tmp.data->Iex.GetI.ix->tag == Iex_Tmp
2331 && collapseChain(bb, i-1, st->Ist.Tmp.data->Iex.GetI.ix
2332 ->Iex.Tmp.tmp, &var2, &con2)) {
2333 if (DEBUG_IROPT) {
2334 vex_printf("replacing3 ");
2335 ppIRStmt(st);
2336 vex_printf(" with ");
2337 }
2338 con2 += st->Ist.Tmp.data->Iex.GetI.bias;
2339 bb->stmts[i]
2340 = IRStmt_Tmp(
2341 st->Ist.Tmp.tmp,
2342 IRExpr_GetI(st->Ist.Tmp.data->Iex.GetI.descr,
2343 IRExpr_Tmp(var2),
2344 con2));
2345 if (DEBUG_IROPT) {
2346 ppIRStmt(bb->stmts[i]);
2347 vex_printf("\n");
2348 }
2349 continue;
2350 }
2351
2352 /* Perhaps st is PutI[t, con] ? */
2353
2354 if (st->tag == Ist_PutI
2355 && st->Ist.PutI.ix->tag == Iex_Tmp
2356 && collapseChain(bb, i-1, st->Ist.PutI.ix->Iex.Tmp.tmp,
2357 &var2, &con2)) {
2358 if (DEBUG_IROPT) {
2359 vex_printf("replacing2 ");
2360 ppIRStmt(st);
2361 vex_printf(" with ");
2362 }
2363 con2 += st->Ist.PutI.bias;
2364 bb->stmts[i]
2365 = IRStmt_PutI(st->Ist.PutI.descr,
2366 IRExpr_Tmp(var2),
2367 con2,
2368 st->Ist.PutI.data);
2369 if (DEBUG_IROPT) {
2370 ppIRStmt(bb->stmts[i]);
2371 vex_printf("\n");
2372 }
2373 continue;
2374 }
2375
2376 } /* for */
2377}
2378
2379
2380/*---------------------------------------------------------------*/
2381/*--- PutI/GetI transformations ---*/
2382/*---------------------------------------------------------------*/
2383
2384/* ------- Helper functions for PutI/GetI transformations ------ */
2385
sewardj08210532004-12-29 17:09:11 +00002386/* Determine, to the extent possible, the relationship between two
2387 guest state accesses. The possible outcomes are:
2388
2389 * Exact alias. These two accesses denote precisely the same
2390 piece of the guest state.
2391
2392 * Definitely no alias. These two accesses are guaranteed not to
2393 overlap any part of the guest state.
2394
2395 * Unknown -- if neither of the above can be established.
2396
2397 If in doubt, return Unknown. */
2398
2399typedef
2400 enum { ExactAlias, NoAlias, UnknownAlias }
2401 GSAliasing;
2402
2403
2404/* Produces the alias relation between an indexed guest
2405 state access and a non-indexed access. */
2406
2407static
2408GSAliasing getAliasingRelation_IC ( IRArray* descr1, IRExpr* ix1,
2409 Int offset2, IRType ty2 )
2410{
2411 UInt minoff1, maxoff1, minoff2, maxoff2;
2412
2413 getArrayBounds( descr1, &minoff1, &maxoff1 );
2414 minoff2 = offset2;
2415 maxoff2 = minoff2 + sizeofIRType(ty2) - 1;
2416
2417 if (maxoff1 < minoff2 || maxoff2 < minoff1)
2418 return NoAlias;
2419
2420 /* Could probably do better here if required. For the moment
2421 however just claim not to know anything more. */
2422 return UnknownAlias;
2423}
2424
2425
2426/* Produces the alias relation between two indexed guest state
2427 accesses. */
2428
2429static
2430GSAliasing getAliasingRelation_II (
2431 IRArray* descr1, IRExpr* ix1, Int bias1,
2432 IRArray* descr2, IRExpr* ix2, Int bias2
2433 )
2434{
2435 UInt minoff1, maxoff1, minoff2, maxoff2;
2436 Int iters;
2437
2438 /* First try hard to show they don't alias. */
2439 getArrayBounds( descr1, &minoff1, &maxoff1 );
2440 getArrayBounds( descr2, &minoff2, &maxoff2 );
2441 if (maxoff1 < minoff2 || maxoff2 < minoff1)
2442 return NoAlias;
2443
2444 /* So the two arrays at least partially overlap. To get any
2445 further we'll have to be sure that the descriptors are
2446 identical. */
2447 if (!eqIRArray(descr1, descr2))
2448 return UnknownAlias;
2449
2450 /* The descriptors are identical. Now the only difference can be
2451 in the index expressions. If they cannot be shown to be
2452 identical, we have to say we don't know what the aliasing
2453 relation will be. Now, since the IR is flattened, the index
2454 expressions should be atoms -- either consts or tmps. So that
2455 makes the comparison simple. */
sewardj496a58d2005-03-20 18:44:44 +00002456 vassert(isIRAtom(ix1));
2457 vassert(isIRAtom(ix2));
2458 if (!eqIRAtom(ix1,ix2))
sewardj08210532004-12-29 17:09:11 +00002459 return UnknownAlias;
2460
2461 /* Ok, the index expressions are identical. So now the only way
2462 they can be different is in the bias. Normalise this
2463 paranoidly, to reliably establish equality/non-equality. */
2464
2465 /* So now we know that the GetI and PutI index the same array
2466 with the same base. Are the offsets the same, modulo the
2467 array size? Do this paranoidly. */
2468 vassert(descr1->nElems == descr2->nElems);
2469 vassert(descr1->elemTy == descr2->elemTy);
2470 vassert(descr1->base == descr2->base);
2471 iters = 0;
2472 while (bias1 < 0 || bias2 < 0) {
2473 bias1 += descr1->nElems;
2474 bias2 += descr1->nElems;
2475 iters++;
2476 if (iters > 10)
2477 vpanic("getAliasingRelation: iters");
2478 }
2479 vassert(bias1 >= 0 && bias2 >= 0);
2480 bias1 %= descr1->nElems;
2481 bias2 %= descr1->nElems;
2482 vassert(bias1 >= 0 && bias1 < descr1->nElems);
2483 vassert(bias2 >= 0 && bias2 < descr1->nElems);
2484
2485 /* Finally, biasP and biasG are normalised into the range
2486 0 .. descrP/G->nElems - 1. And so we can establish
2487 equality/non-equality. */
2488
2489 return bias1==bias2 ? ExactAlias : NoAlias;
2490}
2491
2492
2493/* Given the parts (descr, tmp, bias) for a GetI, scan backwards from
2494 the given starting point to find, if any, a PutI which writes
2495 exactly the same piece of guest state, and so return the expression
2496 that the PutI writes. This is the core of PutI-GetI forwarding. */
2497
2498static
2499IRExpr* findPutI ( IRBB* bb, Int startHere,
2500 IRArray* descrG, IRExpr* ixG, Int biasG )
2501{
2502 Int j;
2503 IRStmt* st;
2504 GSAliasing relation;
2505
2506 if (0) {
2507 vex_printf("\nfindPutI ");
2508 ppIRArray(descrG);
2509 vex_printf(" ");
2510 ppIRExpr(ixG);
2511 vex_printf(" %d\n", biasG);
2512 }
2513
2514 /* Scan backwards in bb from startHere to find a suitable PutI
2515 binding for (descrG, ixG, biasG), if any. */
2516
2517 for (j = startHere; j >= 0; j--) {
2518 st = bb->stmts[j];
sewardj8bee6d12005-03-22 02:24:05 +00002519 if (st->tag == Ist_NoOp)
2520 continue;
sewardj08210532004-12-29 17:09:11 +00002521
2522 if (st->tag == Ist_Put) {
2523 /* Non-indexed Put. This can't give a binding, but we do
2524 need to check it doesn't invalidate the search by
2525 overlapping any part of the indexed guest state. */
2526
2527 relation
2528 = getAliasingRelation_IC(
2529 descrG, ixG,
2530 st->Ist.Put.offset,
2531 typeOfIRExpr(bb->tyenv,st->Ist.Put.data) );
2532
2533 if (relation == NoAlias) {
2534 /* we're OK; keep going */
2535 continue;
2536 } else {
2537 /* relation == UnknownAlias || relation == ExactAlias */
2538 /* If this assertion fails, we've found a Put which writes
2539 an area of guest state which is read by a GetI. Which
2540 is unlikely (although not per se wrong). */
2541 vassert(relation != ExactAlias);
2542 /* This Put potentially writes guest state that the GetI
2543 reads; we must fail. */
2544 return NULL;
2545 }
2546 }
2547
2548 if (st->tag == Ist_PutI) {
2549
2550 relation = getAliasingRelation_II(
2551 descrG, ixG, biasG,
2552 st->Ist.PutI.descr,
2553 st->Ist.PutI.ix,
2554 st->Ist.PutI.bias
2555 );
2556
2557 if (relation == NoAlias) {
2558 /* This PutI definitely doesn't overlap. Ignore it and
2559 keep going. */
2560 continue; /* the for j loop */
2561 }
2562
2563 if (relation == UnknownAlias) {
2564 /* We don't know if this PutI writes to the same guest
2565 state that the GetI, or not. So we have to give up. */
2566 return NULL;
2567 }
2568
2569 /* Otherwise, we've found what we're looking for. */
2570 vassert(relation == ExactAlias);
2571 return st->Ist.PutI.data;
2572
2573 } /* if (st->tag == Ist_PutI) */
2574
2575 if (st->tag == Ist_Dirty) {
2576 /* Be conservative. If the dirty call has any guest effects at
2577 all, give up. We could do better -- only give up if there
2578 are any guest writes/modifies. */
2579 if (st->Ist.Dirty.details->nFxState > 0)
2580 return NULL;
2581 }
2582
2583 } /* for */
2584
2585 /* No valid replacement was found. */
2586 return NULL;
2587}
2588
2589
2590
2591/* Assuming pi is a PutI stmt, is s2 identical to it (in the sense
2592 that it writes exactly the same piece of guest state) ? Safe
2593 answer: False. */
2594
2595static Bool identicalPutIs ( IRStmt* pi, IRStmt* s2 )
2596{
2597 vassert(pi->tag == Ist_PutI);
2598 if (s2->tag != Ist_PutI)
2599 return False;
2600
sewardj9d2e7692005-02-07 01:11:31 +00002601 return toBool(
2602 getAliasingRelation_II(
sewardj08210532004-12-29 17:09:11 +00002603 pi->Ist.PutI.descr, pi->Ist.PutI.ix, pi->Ist.PutI.bias,
2604 s2->Ist.PutI.descr, s2->Ist.PutI.ix, s2->Ist.PutI.bias
2605 )
sewardj9d2e7692005-02-07 01:11:31 +00002606 == ExactAlias
2607 );
sewardj08210532004-12-29 17:09:11 +00002608}
2609
2610
2611/* Assuming pi is a PutI stmt, is s2 a Get/GetI/Put/PutI which might
2612 overlap it? Safe answer: True. Note, we could do a lot better
2613 than this if needed. */
2614
2615static
2616Bool guestAccessWhichMightOverlapPutI (
2617 IRTypeEnv* tyenv, IRStmt* pi, IRStmt* s2
2618 )
2619{
2620 GSAliasing relation;
2621 UInt minoffP, maxoffP;
2622
2623 vassert(pi->tag == Ist_PutI);
2624 getArrayBounds(pi->Ist.PutI.descr, &minoffP, &maxoffP);
2625 switch (s2->tag) {
2626
sewardjd2445f62005-03-21 00:15:53 +00002627 case Ist_NoOp:
sewardjf1689312005-03-16 18:19:10 +00002628 case Ist_IMark:
2629 return False;
2630
sewardjbb3f52d2005-01-07 14:14:50 +00002631 case Ist_MFence:
sewardj5a9ffab2005-05-12 17:55:01 +00002632 case Ist_AbiHint:
2633 /* just be paranoid ... these should be rare. */
sewardjbb3f52d2005-01-07 14:14:50 +00002634 return True;
2635
sewardj08210532004-12-29 17:09:11 +00002636 case Ist_Dirty:
2637 /* If the dirty call has any guest effects at all, give up.
2638 Probably could do better. */
2639 if (s2->Ist.Dirty.details->nFxState > 0)
2640 return True;
2641 return False;
2642
2643 case Ist_Put:
sewardj496a58d2005-03-20 18:44:44 +00002644 vassert(isIRAtom(s2->Ist.Put.data));
sewardj08210532004-12-29 17:09:11 +00002645 relation
2646 = getAliasingRelation_IC(
2647 pi->Ist.PutI.descr, pi->Ist.PutI.ix,
2648 s2->Ist.Put.offset,
2649 typeOfIRExpr(tyenv,s2->Ist.Put.data)
2650 );
2651 goto have_relation;
2652
2653 case Ist_PutI:
sewardj496a58d2005-03-20 18:44:44 +00002654 vassert(isIRAtom(s2->Ist.PutI.ix));
2655 vassert(isIRAtom(s2->Ist.PutI.data));
sewardj08210532004-12-29 17:09:11 +00002656 relation
2657 = getAliasingRelation_II(
2658 pi->Ist.PutI.descr, pi->Ist.PutI.ix, pi->Ist.PutI.bias,
2659 s2->Ist.PutI.descr, s2->Ist.PutI.ix, s2->Ist.PutI.bias
2660 );
2661 goto have_relation;
2662
2663 case Ist_Tmp:
2664 if (s2->Ist.Tmp.data->tag == Iex_GetI) {
2665 relation
2666 = getAliasingRelation_II(
2667 pi->Ist.PutI.descr, pi->Ist.PutI.ix,
2668 pi->Ist.PutI.bias,
2669 s2->Ist.Tmp.data->Iex.GetI.descr,
2670 s2->Ist.Tmp.data->Iex.GetI.ix,
2671 s2->Ist.Tmp.data->Iex.GetI.bias
2672 );
2673 goto have_relation;
2674 }
2675 if (s2->Ist.Tmp.data->tag == Iex_Get) {
2676 relation
2677 = getAliasingRelation_IC(
2678 pi->Ist.PutI.descr, pi->Ist.PutI.ix,
2679 s2->Ist.Tmp.data->Iex.Get.offset,
2680 s2->Ist.Tmp.data->Iex.Get.ty
2681 );
2682 goto have_relation;
2683 }
2684 return False;
2685
sewardjaf1ceca2005-06-30 23:31:27 +00002686 case Ist_Store:
2687 vassert(isIRAtom(s2->Ist.Store.addr));
2688 vassert(isIRAtom(s2->Ist.Store.data));
sewardj08210532004-12-29 17:09:11 +00002689 return False;
2690
2691 default:
2692 vex_printf("\n"); ppIRStmt(s2); vex_printf("\n");
2693 vpanic("guestAccessWhichMightOverlapPutI");
2694 }
2695
2696 have_relation:
2697 if (relation == NoAlias)
2698 return False;
2699 else
2700 return True; /* ExactAlias or UnknownAlias */
2701}
2702
2703
2704
2705/* ---------- PutI/GetI transformations main functions --------- */
2706
2707/* Remove redundant GetIs, to the extent that they can be detected.
2708 bb is modified in-place. */
2709
2710static
2711void do_redundant_GetI_elimination ( IRBB* bb )
2712{
2713 Int i;
2714 IRStmt* st;
2715
2716 for (i = bb->stmts_used-1; i >= 0; i--) {
2717 st = bb->stmts[i];
sewardj8bee6d12005-03-22 02:24:05 +00002718 if (st->tag == Ist_NoOp)
sewardj08210532004-12-29 17:09:11 +00002719 continue;
2720
2721 if (st->tag == Ist_Tmp
2722 && st->Ist.Tmp.data->tag == Iex_GetI
2723 && st->Ist.Tmp.data->Iex.GetI.ix->tag == Iex_Tmp) {
2724 IRArray* descr = st->Ist.Tmp.data->Iex.GetI.descr;
2725 IRExpr* ix = st->Ist.Tmp.data->Iex.GetI.ix;
2726 Int bias = st->Ist.Tmp.data->Iex.GetI.bias;
2727 IRExpr* replacement = findPutI(bb, i-1, descr, ix, bias);
2728 if (replacement
sewardj496a58d2005-03-20 18:44:44 +00002729 && isIRAtom(replacement)
sewardj08210532004-12-29 17:09:11 +00002730 /* Make sure we're doing a type-safe transformation! */
2731 && typeOfIRExpr(bb->tyenv, replacement) == descr->elemTy) {
2732 if (DEBUG_IROPT) {
2733 vex_printf("rGI: ");
2734 ppIRExpr(st->Ist.Tmp.data);
2735 vex_printf(" -> ");
2736 ppIRExpr(replacement);
2737 vex_printf("\n");
2738 }
2739 bb->stmts[i] = IRStmt_Tmp(st->Ist.Tmp.tmp, replacement);
2740 }
2741 }
2742 }
2743
2744}
2745
2746
2747/* Remove redundant PutIs, to the extent which they can be detected.
2748 bb is modified in-place. */
2749
2750static
2751void do_redundant_PutI_elimination ( IRBB* bb )
2752{
2753 Int i, j;
2754 Bool delete;
2755 IRStmt *st, *stj;
2756
2757 for (i = 0; i < bb->stmts_used; i++) {
2758 st = bb->stmts[i];
sewardj8bee6d12005-03-22 02:24:05 +00002759 if (st->tag != Ist_PutI)
sewardj08210532004-12-29 17:09:11 +00002760 continue;
2761 /* Ok, search forwards from here to see if we can find another
2762 PutI which makes this one redundant, and dodging various
2763 hazards. Search forwards:
2764 * If conditional exit, give up (because anything after that
2765 does not postdominate this put).
2766 * If a Get which might overlap, give up (because this PutI
2767 not necessarily dead).
2768 * If a Put which is identical, stop with success.
2769 * If a Put which might overlap, but is not identical, give up.
2770 * If a dirty helper call which might write guest state, give up.
2771 * If a Put which definitely doesn't overlap, or any other
2772 kind of stmt, continue.
2773 */
2774 delete = False;
2775 for (j = i+1; j < bb->stmts_used; j++) {
2776 stj = bb->stmts[j];
sewardj8bee6d12005-03-22 02:24:05 +00002777 if (stj->tag == Ist_NoOp)
sewardj08210532004-12-29 17:09:11 +00002778 continue;
2779 if (identicalPutIs(st, stj)) {
2780 /* success! */
2781 delete = True;
2782 break;
2783 }
2784 if (stj->tag == Ist_Exit)
2785 /* give up */
2786 break;
2787 if (st->tag == Ist_Dirty)
2788 /* give up; could do better here */
2789 break;
2790 if (guestAccessWhichMightOverlapPutI(bb->tyenv, st, stj))
2791 /* give up */
2792 break;
2793 }
2794
2795 if (delete) {
2796 if (DEBUG_IROPT) {
2797 vex_printf("rPI: ");
2798 ppIRStmt(st);
2799 vex_printf("\n");
2800 }
sewardjd2445f62005-03-21 00:15:53 +00002801 bb->stmts[i] = IRStmt_NoOp();
sewardj08210532004-12-29 17:09:11 +00002802 }
2803
2804 }
2805}
2806
2807
2808/*---------------------------------------------------------------*/
2809/*--- Loop unrolling ---*/
2810/*---------------------------------------------------------------*/
2811
2812/* Adjust all tmp values (names) in e by delta. e is destructively
2813 modified. */
2814
2815static void deltaIRExpr ( IRExpr* e, Int delta )
2816{
2817 Int i;
2818 switch (e->tag) {
2819 case Iex_Tmp:
2820 e->Iex.Tmp.tmp += delta;
2821 break;
2822 case Iex_Get:
2823 case Iex_Const:
2824 break;
2825 case Iex_GetI:
2826 deltaIRExpr(e->Iex.GetI.ix, delta);
2827 break;
2828 case Iex_Binop:
2829 deltaIRExpr(e->Iex.Binop.arg1, delta);
2830 deltaIRExpr(e->Iex.Binop.arg2, delta);
2831 break;
2832 case Iex_Unop:
2833 deltaIRExpr(e->Iex.Unop.arg, delta);
2834 break;
sewardjaf1ceca2005-06-30 23:31:27 +00002835 case Iex_Load:
2836 deltaIRExpr(e->Iex.Load.addr, delta);
sewardj08210532004-12-29 17:09:11 +00002837 break;
2838 case Iex_CCall:
2839 for (i = 0; e->Iex.CCall.args[i]; i++)
2840 deltaIRExpr(e->Iex.CCall.args[i], delta);
2841 break;
2842 case Iex_Mux0X:
2843 deltaIRExpr(e->Iex.Mux0X.cond, delta);
2844 deltaIRExpr(e->Iex.Mux0X.expr0, delta);
2845 deltaIRExpr(e->Iex.Mux0X.exprX, delta);
2846 break;
2847 default:
2848 vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
2849 vpanic("deltaIRExpr");
2850 }
2851}
2852
2853/* Adjust all tmp values (names) in st by delta. st is destructively
2854 modified. */
2855
2856static void deltaIRStmt ( IRStmt* st, Int delta )
2857{
2858 Int i;
2859 IRDirty* d;
2860 switch (st->tag) {
sewardjd2445f62005-03-21 00:15:53 +00002861 case Ist_NoOp:
sewardjf1689312005-03-16 18:19:10 +00002862 case Ist_IMark:
sewardjf4860352005-06-30 13:38:38 +00002863 case Ist_MFence:
sewardjf1689312005-03-16 18:19:10 +00002864 break;
sewardj5a9ffab2005-05-12 17:55:01 +00002865 case Ist_AbiHint:
2866 deltaIRExpr(st->Ist.AbiHint.base, delta);
2867 break;
sewardj08210532004-12-29 17:09:11 +00002868 case Ist_Put:
2869 deltaIRExpr(st->Ist.Put.data, delta);
2870 break;
2871 case Ist_PutI:
2872 deltaIRExpr(st->Ist.PutI.ix, delta);
2873 deltaIRExpr(st->Ist.PutI.data, delta);
2874 break;
2875 case Ist_Tmp:
2876 st->Ist.Tmp.tmp += delta;
2877 deltaIRExpr(st->Ist.Tmp.data, delta);
2878 break;
2879 case Ist_Exit:
2880 deltaIRExpr(st->Ist.Exit.guard, delta);
2881 break;
sewardjaf1ceca2005-06-30 23:31:27 +00002882 case Ist_Store:
2883 deltaIRExpr(st->Ist.Store.addr, delta);
2884 deltaIRExpr(st->Ist.Store.data, delta);
sewardj08210532004-12-29 17:09:11 +00002885 break;
2886 case Ist_Dirty:
2887 d = st->Ist.Dirty.details;
2888 deltaIRExpr(d->guard, delta);
2889 for (i = 0; d->args[i]; i++)
2890 deltaIRExpr(d->args[i], delta);
2891 if (d->tmp != IRTemp_INVALID)
2892 d->tmp += delta;
2893 if (d->mAddr)
2894 deltaIRExpr(d->mAddr, delta);
2895 break;
2896 default:
2897 vex_printf("\n"); ppIRStmt(st); vex_printf("\n");
2898 vpanic("deltaIRStmt");
2899 }
2900}
2901
2902
2903/* If possible, return a loop-unrolled version of bb0. The original
2904 is changed. If not possible, return NULL. */
2905
2906/* The two schemas considered are:
2907
2908 X: BODY; goto X
2909
2910 which unrolls to (eg) X: BODY;BODY; goto X
2911
2912 and
2913
2914 X: BODY; if (c) goto X; goto Y
2915 which trivially transforms to
2916 X: BODY; if (!c) goto Y; goto X;
2917 so it falls in the scope of the first case.
2918
2919 X and Y must be literal (guest) addresses.
2920*/
2921
2922static Int calc_unroll_factor( IRBB* bb )
2923{
2924 Int n_stmts, i;
2925
2926 n_stmts = 0;
sewardj0ddbf792005-04-04 23:12:54 +00002927 for (i = 0; i < bb->stmts_used; i++) {
2928 if (bb->stmts[i]->tag != Ist_NoOp)
2929 n_stmts++;
2930 }
sewardj08210532004-12-29 17:09:11 +00002931
2932 if (n_stmts <= vex_control.iropt_unroll_thresh/8) {
2933 if (vex_control.iropt_verbosity > 0)
2934 vex_printf("vex iropt: 8 x unrolling (%d sts -> %d sts)\n",
2935 n_stmts, 8* n_stmts);
2936 return 8;
2937 }
2938 if (n_stmts <= vex_control.iropt_unroll_thresh/4) {
2939 if (vex_control.iropt_verbosity > 0)
2940 vex_printf("vex iropt: 4 x unrolling (%d sts -> %d sts)\n",
2941 n_stmts, 4* n_stmts);
2942 return 4;
2943 }
2944
2945 if (n_stmts <= vex_control.iropt_unroll_thresh/2) {
2946 if (vex_control.iropt_verbosity > 0)
2947 vex_printf("vex iropt: 2 x unrolling (%d sts -> %d sts)\n",
2948 n_stmts, 2* n_stmts);
2949 return 2;
2950 }
2951
2952 if (vex_control.iropt_verbosity > 0)
2953 vex_printf("vex iropt: not unrolling (%d sts)\n", n_stmts);
2954
2955 return 1;
2956}
2957
2958
2959static IRBB* maybe_loop_unroll_BB ( IRBB* bb0, Addr64 my_addr )
2960{
2961 Int i, j, jmax, n_vars;
2962 Bool xxx_known;
2963 Addr64 xxx_value, yyy_value;
2964 IRExpr* udst;
2965 IRStmt* st;
2966 IRConst* con;
2967 IRBB *bb1, *bb2;
2968 Int unroll_factor;
2969
2970 if (vex_control.iropt_unroll_thresh <= 0)
2971 return NULL;
2972
2973 /* First off, figure out if we can unroll this loop. Do this
2974 without modifying bb0. */
2975
2976 if (bb0->jumpkind != Ijk_Boring)
2977 return NULL;
2978
2979 xxx_known = False;
2980 xxx_value = 0;
2981
2982 /* Extract the next-guest address. If it isn't a literal, we
2983 have to give up. */
2984
2985 udst = bb0->next;
2986 if (udst->tag == Iex_Const
2987 && (udst->Iex.Const.con->tag == Ico_U32
2988 || udst->Iex.Const.con->tag == Ico_U64)) {
2989 /* The BB ends in a jump to a literal location. */
2990 xxx_known = True;
2991 xxx_value = udst->Iex.Const.con->tag == Ico_U64
2992 ? udst->Iex.Const.con->Ico.U64
2993 : (Addr64)(udst->Iex.Const.con->Ico.U32);
2994 }
2995
2996 if (!xxx_known)
2997 return NULL;
2998
2999 /* Now we know the BB ends to a jump to a literal location. If
3000 it's a jump to itself (viz, idiom #1), move directly to the
3001 unrolling stage, first cloning the bb so the original isn't
3002 modified. */
3003 if (xxx_value == my_addr) {
3004 unroll_factor = calc_unroll_factor( bb0 );
3005 if (unroll_factor < 2)
3006 return NULL;
3007 bb1 = dopyIRBB( bb0 );
3008 bb0 = NULL;
3009 udst = NULL; /* is now invalid */
3010 goto do_unroll;
3011 }
3012
3013 /* Search for the second idiomatic form:
3014 X: BODY; if (c) goto X; goto Y
3015 We know Y, but need to establish that the last stmt
3016 is 'if (c) goto X'.
3017 */
3018 yyy_value = xxx_value;
3019 for (i = bb0->stmts_used-1; i >= 0; i--)
3020 if (bb0->stmts[i])
3021 break;
3022
3023 if (i < 0)
3024 return NULL; /* block with no stmts. Strange. */
3025
3026 st = bb0->stmts[i];
3027 if (st->tag != Ist_Exit)
3028 return NULL;
3029 if (st->Ist.Exit.jk != Ijk_Boring)
3030 return NULL;
3031
3032 con = st->Ist.Exit.dst;
3033 vassert(con->tag == Ico_U32 || con->tag == Ico_U64);
3034
3035 xxx_value = con->tag == Ico_U64
3036 ? st->Ist.Exit.dst->Ico.U64
3037 : (Addr64)(st->Ist.Exit.dst->Ico.U32);
3038
3039 /* If this assertion fails, we have some kind of type error. */
3040 vassert(con->tag == udst->Iex.Const.con->tag);
3041
3042 if (xxx_value != my_addr)
3043 /* We didn't find either idiom. Give up. */
3044 return NULL;
3045
3046 /* Ok, we found idiom #2. Copy the BB, switch around the xxx and
3047 yyy values (which makes it look like idiom #1), and go into
3048 unrolling proper. This means finding (again) the last stmt, in
3049 the copied BB. */
3050
3051 unroll_factor = calc_unroll_factor( bb0 );
3052 if (unroll_factor < 2)
3053 return NULL;
3054
3055 bb1 = dopyIRBB( bb0 );
3056 bb0 = NULL;
3057 udst = NULL; /* is now invalid */
3058 for (i = bb1->stmts_used-1; i >= 0; i--)
3059 if (bb1->stmts[i])
3060 break;
3061
3062 /* The next bunch of assertions should be true since we already
3063 found and checked the last stmt in the original bb. */
3064
3065 vassert(i >= 0);
3066
3067 st = bb1->stmts[i];
3068 vassert(st->tag == Ist_Exit);
3069
3070 con = st->Ist.Exit.dst;
3071 vassert(con->tag == Ico_U32 || con->tag == Ico_U64);
3072
3073 udst = bb1->next;
3074 vassert(udst->tag == Iex_Const);
3075 vassert(udst->Iex.Const.con->tag == Ico_U32
3076 || udst->Iex.Const.con->tag == Ico_U64);
3077 vassert(con->tag == udst->Iex.Const.con->tag);
3078
3079 /* switch the xxx and yyy fields around */
3080 if (con->tag == Ico_U64) {
3081 udst->Iex.Const.con->Ico.U64 = xxx_value;
3082 con->Ico.U64 = yyy_value;
3083 } else {
3084 udst->Iex.Const.con->Ico.U32 = (UInt)xxx_value;
cerion57b4c6d2005-02-22 11:07:35 +00003085 con->Ico.U32 = (UInt)yyy_value;
sewardj08210532004-12-29 17:09:11 +00003086 }
3087
3088 /* negate the test condition */
3089 st->Ist.Exit.guard
3090 = IRExpr_Unop(Iop_Not1,dopyIRExpr(st->Ist.Exit.guard));
3091
3092 /* --- The unroller proper. Both idioms are by now --- */
3093 /* --- now converted to idiom 1. --- */
3094
3095 do_unroll:
3096
3097 vassert(unroll_factor == 2
3098 || unroll_factor == 4
3099 || unroll_factor == 8);
3100
3101 jmax = unroll_factor==8 ? 3 : (unroll_factor==4 ? 2 : 1);
3102 for (j = 1; j <= jmax; j++) {
3103
3104 n_vars = bb1->tyenv->types_used;
3105
3106 bb2 = dopyIRBB(bb1);
3107 for (i = 0; i < n_vars; i++)
3108 (void)newIRTemp(bb1->tyenv, bb2->tyenv->types[i]);
3109
3110 for (i = 0; i < bb2->stmts_used; i++) {
sewardj08210532004-12-29 17:09:11 +00003111 /* deltaIRStmt destructively modifies the stmt, but
3112 that's OK since bb2 is a complete fresh copy of bb1. */
3113 deltaIRStmt(bb2->stmts[i], n_vars);
3114 addStmtToIRBB(bb1, bb2->stmts[i]);
3115 }
3116 }
3117
3118 if (DEBUG_IROPT) {
3119 vex_printf("\nUNROLLED (%llx)\n", my_addr);
3120 ppIRBB(bb1);
3121 vex_printf("\n");
3122 }
3123
3124 /* Flattening; sigh. The unroller succeeds in breaking flatness
3125 by negating the test condition. This should be fixed properly.
3126 For the moment use this shotgun approach. */
3127 return flatten_BB(bb1);
3128}
3129
3130
3131/*---------------------------------------------------------------*/
sewardj29632392004-08-22 02:38:11 +00003132/*--- The tree builder ---*/
3133/*---------------------------------------------------------------*/
3134
sewardj08210532004-12-29 17:09:11 +00003135/* This isn't part of IR optimisation. Really it's a pass done prior
3136 to instruction selection, which improves the code that the
3137 instruction selector can produce. */
3138
sewardj29632392004-08-22 02:38:11 +00003139typedef
3140 struct {
3141 Int occ; /* occurrence count for this tmp */
sewardj84ff0652004-08-23 16:16:08 +00003142 IRExpr* expr; /* expr it is bound to,
3143 or NULL if already 'used' */
sewardj29632392004-08-22 02:38:11 +00003144 Bool eDoesLoad; /* True <=> expr reads mem */
3145 Bool eDoesGet; /* True <=> expr reads guest state */
3146 Bool invalidateMe; /* used when dumping bindings */
3147 Int origPos; /* posn of the binder in the original bb */
3148 }
3149 TmpInfo;
3150
3151/* Given env :: IRTemp -> TmpInfo*
3152 Add the use-occurrences of temps in this expression
3153 to the environment.
3154*/
sewardjc9ad1152004-10-14 00:08:21 +00003155static void occCount_Temp ( TmpInfo** env, IRTemp tmp )
sewardj17442fe2004-09-20 14:54:28 +00003156{
sewardjc9ad1152004-10-14 00:08:21 +00003157 TmpInfo* ti = env[(Int)tmp];
3158 if (ti) {
sewardj17442fe2004-09-20 14:54:28 +00003159 ti->occ++;
3160 } else {
3161 ti = LibVEX_Alloc(sizeof(TmpInfo));
3162 ti->occ = 1;
3163 ti->expr = NULL;
3164 ti->eDoesLoad = False;
3165 ti->eDoesGet = False;
3166 ti->invalidateMe = False;
3167 ti->origPos = -1; /* filed in properly later */
sewardjc9ad1152004-10-14 00:08:21 +00003168 env[(Int)tmp] = ti;
sewardj17442fe2004-09-20 14:54:28 +00003169 }
3170}
3171
sewardjc9ad1152004-10-14 00:08:21 +00003172static void occCount_Expr ( TmpInfo** env, IRExpr* e )
sewardj29632392004-08-22 02:38:11 +00003173{
sewardj17442fe2004-09-20 14:54:28 +00003174 Int i;
sewardj29632392004-08-22 02:38:11 +00003175
3176 switch (e->tag) {
3177
3178 case Iex_Tmp: /* the only interesting case */
sewardj17442fe2004-09-20 14:54:28 +00003179 occCount_Temp(env, e->Iex.Tmp.tmp);
sewardj29632392004-08-22 02:38:11 +00003180 return;
3181
3182 case Iex_Mux0X:
3183 occCount_Expr(env, e->Iex.Mux0X.cond);
3184 occCount_Expr(env, e->Iex.Mux0X.expr0);
3185 occCount_Expr(env, e->Iex.Mux0X.exprX);
3186 return;
3187
3188 case Iex_Binop:
3189 occCount_Expr(env, e->Iex.Binop.arg1);
3190 occCount_Expr(env, e->Iex.Binop.arg2);
3191 return;
3192
3193 case Iex_Unop:
3194 occCount_Expr(env, e->Iex.Unop.arg);
3195 return;
3196
sewardjaf1ceca2005-06-30 23:31:27 +00003197 case Iex_Load:
3198 occCount_Expr(env, e->Iex.Load.addr);
sewardj29632392004-08-22 02:38:11 +00003199 return;
3200
3201 case Iex_CCall:
3202 for (i = 0; e->Iex.CCall.args[i]; i++)
3203 occCount_Expr(env, e->Iex.CCall.args[i]);
3204 return;
3205
sewardjf6501992004-08-27 11:58:24 +00003206 case Iex_GetI:
sewardjeeac8412004-11-02 00:26:55 +00003207 occCount_Expr(env, e->Iex.GetI.ix);
sewardjf6501992004-08-27 11:58:24 +00003208 return;
3209
sewardj29632392004-08-22 02:38:11 +00003210 case Iex_Const:
3211 case Iex_Get:
3212 return;
3213
3214 default:
3215 vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
3216 vpanic("occCount_Expr");
3217 }
3218}
3219
3220
3221/* Given env :: IRTemp -> TmpInfo*
3222 Add the use-occurrences of temps in this expression
3223 to the environment.
3224*/
sewardjc9ad1152004-10-14 00:08:21 +00003225static void occCount_Stmt ( TmpInfo** env, IRStmt* st )
sewardj29632392004-08-22 02:38:11 +00003226{
sewardj17442fe2004-09-20 14:54:28 +00003227 Int i;
3228 IRDirty* d;
sewardj29632392004-08-22 02:38:11 +00003229 switch (st->tag) {
sewardj5a9ffab2005-05-12 17:55:01 +00003230 case Ist_AbiHint:
3231 occCount_Expr(env, st->Ist.AbiHint.base);
3232 return;
sewardj29632392004-08-22 02:38:11 +00003233 case Ist_Tmp:
sewardj6d076362004-09-23 11:06:17 +00003234 occCount_Expr(env, st->Ist.Tmp.data);
sewardj29632392004-08-22 02:38:11 +00003235 return;
3236 case Ist_Put:
sewardj6d076362004-09-23 11:06:17 +00003237 occCount_Expr(env, st->Ist.Put.data);
sewardj29632392004-08-22 02:38:11 +00003238 return;
sewardjf6501992004-08-27 11:58:24 +00003239 case Ist_PutI:
sewardjeeac8412004-11-02 00:26:55 +00003240 occCount_Expr(env, st->Ist.PutI.ix);
sewardj2d3f77c2004-09-22 23:49:09 +00003241 occCount_Expr(env, st->Ist.PutI.data);
sewardjf6501992004-08-27 11:58:24 +00003242 return;
sewardjaf1ceca2005-06-30 23:31:27 +00003243 case Ist_Store:
3244 occCount_Expr(env, st->Ist.Store.addr);
3245 occCount_Expr(env, st->Ist.Store.data);
sewardj29632392004-08-22 02:38:11 +00003246 return;
sewardj17442fe2004-09-20 14:54:28 +00003247 case Ist_Dirty:
3248 d = st->Ist.Dirty.details;
3249 if (d->mFx != Ifx_None)
3250 occCount_Expr(env, d->mAddr);
sewardjb8385d82004-11-02 01:34:15 +00003251 occCount_Expr(env, d->guard);
sewardj17442fe2004-09-20 14:54:28 +00003252 for (i = 0; d->args[i]; i++)
3253 occCount_Expr(env, d->args[i]);
3254 return;
sewardjd2445f62005-03-21 00:15:53 +00003255 case Ist_NoOp:
sewardjf1689312005-03-16 18:19:10 +00003256 case Ist_IMark:
sewardj3e838932005-01-07 12:09:15 +00003257 case Ist_MFence:
3258 return;
sewardj29632392004-08-22 02:38:11 +00003259 case Ist_Exit:
sewardj0276d4b2004-11-15 15:30:21 +00003260 occCount_Expr(env, st->Ist.Exit.guard);
sewardj29632392004-08-22 02:38:11 +00003261 return;
3262 default:
3263 vex_printf("\n"); ppIRStmt(st); vex_printf("\n");
3264 vpanic("occCount_Stmt");
3265 }
3266}
3267
sewardj17442fe2004-09-20 14:54:28 +00003268/* Look up a binding for tmp in the env. If found, return the bound
3269 expression, and set the env's binding to NULL so it is marked as
3270 used. If not found, return NULL. */
3271
sewardjc9ad1152004-10-14 00:08:21 +00003272static IRExpr* tbSubst_Temp ( TmpInfo** env, IRTemp tmp )
sewardj17442fe2004-09-20 14:54:28 +00003273{
3274 TmpInfo* ti;
sewardj17442fe2004-09-20 14:54:28 +00003275 IRExpr* e;
sewardjc9ad1152004-10-14 00:08:21 +00003276 ti = env[(Int)tmp];
3277 if (ti){
3278 e = ti->expr;
sewardj17442fe2004-09-20 14:54:28 +00003279 if (e) {
3280 ti->expr = NULL;
3281 return e;
3282 } else {
3283 return NULL;
3284 }
3285 } else {
3286 return NULL;
3287 }
3288}
sewardj29632392004-08-22 02:38:11 +00003289
3290/* Traverse e, looking for temps. For each observed temp, see if env
3291 contains a binding for the temp, and if so return the bound value.
3292 The env has the property that any binding it holds is
3293 'single-shot', so once a binding is used, it is marked as no longer
3294 available, by setting its .expr field to NULL. */
3295
sewardjc9ad1152004-10-14 00:08:21 +00003296static IRExpr* tbSubst_Expr ( TmpInfo** env, IRExpr* e )
sewardj29632392004-08-22 02:38:11 +00003297{
sewardjc41f1fb2004-08-22 09:48:08 +00003298 IRExpr* e2;
3299 IRExpr** args2;
3300 Int i;
sewardj29632392004-08-22 02:38:11 +00003301
3302 switch (e->tag) {
3303
sewardjc41f1fb2004-08-22 09:48:08 +00003304 case Iex_CCall:
sewardj695cff92004-10-13 14:50:14 +00003305 args2 = sopyIRExprVec(e->Iex.CCall.args);
sewardjc41f1fb2004-08-22 09:48:08 +00003306 for (i = 0; args2[i]; i++)
3307 args2[i] = tbSubst_Expr(env,args2[i]);
sewardj8ea867b2004-10-30 19:03:02 +00003308 return IRExpr_CCall(e->Iex.CCall.cee,
sewardjc41f1fb2004-08-22 09:48:08 +00003309 e->Iex.CCall.retty,
3310 args2
3311 );
sewardj29632392004-08-22 02:38:11 +00003312 case Iex_Tmp:
sewardj17442fe2004-09-20 14:54:28 +00003313 e2 = tbSubst_Temp(env, e->Iex.Tmp.tmp);
3314 return e2 ? e2 : e;
sewardjc41f1fb2004-08-22 09:48:08 +00003315 case Iex_Mux0X:
3316 return IRExpr_Mux0X(
3317 tbSubst_Expr(env, e->Iex.Mux0X.cond),
3318 tbSubst_Expr(env, e->Iex.Mux0X.expr0),
3319 tbSubst_Expr(env, e->Iex.Mux0X.exprX)
3320 );
3321 case Iex_Binop:
3322 return IRExpr_Binop(
3323 e->Iex.Binop.op,
3324 tbSubst_Expr(env, e->Iex.Binop.arg1),
3325 tbSubst_Expr(env, e->Iex.Binop.arg2)
3326 );
3327 case Iex_Unop:
3328 return IRExpr_Unop(
3329 e->Iex.Unop.op,
3330 tbSubst_Expr(env, e->Iex.Unop.arg)
3331 );
sewardjaf1ceca2005-06-30 23:31:27 +00003332 case Iex_Load:
3333 return IRExpr_Load(
3334 e->Iex.Load.end,
3335 e->Iex.Load.ty,
3336 tbSubst_Expr(env, e->Iex.Load.addr)
sewardjc41f1fb2004-08-22 09:48:08 +00003337 );
sewardjf6501992004-08-27 11:58:24 +00003338 case Iex_GetI:
3339 return IRExpr_GetI(
sewardj2d3f77c2004-09-22 23:49:09 +00003340 e->Iex.GetI.descr,
sewardjeeac8412004-11-02 00:26:55 +00003341 tbSubst_Expr(env, e->Iex.GetI.ix),
sewardj2d3f77c2004-09-22 23:49:09 +00003342 e->Iex.GetI.bias
3343 );
sewardjc41f1fb2004-08-22 09:48:08 +00003344 case Iex_Const:
sewardj29632392004-08-22 02:38:11 +00003345 case Iex_Get:
3346 return e;
3347 default:
3348 vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
3349 vpanic("tbSubst_Expr");
3350 }
3351}
3352
3353/* Same deal as tbSubst_Expr, except for stmts. */
3354
sewardjc9ad1152004-10-14 00:08:21 +00003355static IRStmt* tbSubst_Stmt ( TmpInfo** env, IRStmt* st )
sewardj29632392004-08-22 02:38:11 +00003356{
sewardj17442fe2004-09-20 14:54:28 +00003357 Int i;
3358 IRDirty* d;
3359 IRDirty* d2;
sewardj29632392004-08-22 02:38:11 +00003360 switch (st->tag) {
sewardj5a9ffab2005-05-12 17:55:01 +00003361 case Ist_AbiHint:
3362 return IRStmt_AbiHint(
3363 tbSubst_Expr(env, st->Ist.AbiHint.base),
3364 st->Ist.AbiHint.len
3365 );
sewardjaf1ceca2005-06-30 23:31:27 +00003366 case Ist_Store:
3367 return IRStmt_Store(
3368 st->Ist.Store.end,
3369 tbSubst_Expr(env, st->Ist.Store.addr),
3370 tbSubst_Expr(env, st->Ist.Store.data)
sewardj17442fe2004-09-20 14:54:28 +00003371 );
sewardj29632392004-08-22 02:38:11 +00003372 case Ist_Tmp:
3373 return IRStmt_Tmp(
3374 st->Ist.Tmp.tmp,
sewardj6d076362004-09-23 11:06:17 +00003375 tbSubst_Expr(env, st->Ist.Tmp.data)
sewardj29632392004-08-22 02:38:11 +00003376 );
3377 case Ist_Put:
3378 return IRStmt_Put(
3379 st->Ist.Put.offset,
sewardj6d076362004-09-23 11:06:17 +00003380 tbSubst_Expr(env, st->Ist.Put.data)
sewardj29632392004-08-22 02:38:11 +00003381 );
sewardjf6501992004-08-27 11:58:24 +00003382 case Ist_PutI:
3383 return IRStmt_PutI(
sewardj2d3f77c2004-09-22 23:49:09 +00003384 st->Ist.PutI.descr,
sewardjeeac8412004-11-02 00:26:55 +00003385 tbSubst_Expr(env, st->Ist.PutI.ix),
sewardj2d3f77c2004-09-22 23:49:09 +00003386 st->Ist.PutI.bias,
3387 tbSubst_Expr(env, st->Ist.PutI.data)
3388 );
sewardjf6501992004-08-27 11:58:24 +00003389
sewardj29632392004-08-22 02:38:11 +00003390 case Ist_Exit:
3391 return IRStmt_Exit(
sewardj0276d4b2004-11-15 15:30:21 +00003392 tbSubst_Expr(env, st->Ist.Exit.guard),
sewardj893aada2004-11-29 19:57:54 +00003393 st->Ist.Exit.jk,
sewardj29632392004-08-22 02:38:11 +00003394 st->Ist.Exit.dst
3395 );
sewardjf1689312005-03-16 18:19:10 +00003396 case Ist_IMark:
3397 return IRStmt_IMark(st->Ist.IMark.addr, st->Ist.IMark.len);
sewardjd2445f62005-03-21 00:15:53 +00003398 case Ist_NoOp:
3399 return IRStmt_NoOp();
sewardj3e838932005-01-07 12:09:15 +00003400 case Ist_MFence:
3401 return IRStmt_MFence();
sewardj17442fe2004-09-20 14:54:28 +00003402 case Ist_Dirty:
3403 d = st->Ist.Dirty.details;
3404 d2 = emptyIRDirty();
3405 *d2 = *d;
3406 if (d2->mFx != Ifx_None)
3407 d2->mAddr = tbSubst_Expr(env, d2->mAddr);
sewardjb8385d82004-11-02 01:34:15 +00003408 d2->guard = tbSubst_Expr(env, d2->guard);
sewardj17442fe2004-09-20 14:54:28 +00003409 for (i = 0; d2->args[i]; i++)
3410 d2->args[i] = tbSubst_Expr(env, d2->args[i]);
3411 return IRStmt_Dirty(d2);
sewardj29632392004-08-22 02:38:11 +00003412 default:
3413 vex_printf("\n"); ppIRStmt(st); vex_printf("\n");
3414 vpanic("tbSubst_Stmt");
3415 }
3416}
3417
3418
sewardj37d38012004-08-24 00:37:04 +00003419/* Traverse an expr, and detect if any part of it reads memory or does
3420 a Get. Be careful ... this really controls how much the
3421 tree-builder can reorder the code, so getting it right is critical.
3422*/
sewardj29632392004-08-22 02:38:11 +00003423static void setHints_Expr (Bool* doesLoad, Bool* doesGet, IRExpr* e )
3424{
sewardjc41f1fb2004-08-22 09:48:08 +00003425 Int i;
sewardj29632392004-08-22 02:38:11 +00003426 switch (e->tag) {
sewardjc41f1fb2004-08-22 09:48:08 +00003427 case Iex_CCall:
3428 for (i = 0; e->Iex.CCall.args[i]; i++)
3429 setHints_Expr(doesLoad, doesGet, e->Iex.CCall.args[i]);
3430 return;
3431 case Iex_Mux0X:
3432 setHints_Expr(doesLoad, doesGet, e->Iex.Mux0X.cond);
3433 setHints_Expr(doesLoad, doesGet, e->Iex.Mux0X.expr0);
3434 setHints_Expr(doesLoad, doesGet, e->Iex.Mux0X.exprX);
3435 return;
3436 case Iex_Binop:
3437 setHints_Expr(doesLoad, doesGet, e->Iex.Binop.arg1);
3438 setHints_Expr(doesLoad, doesGet, e->Iex.Binop.arg2);
3439 return;
3440 case Iex_Unop:
3441 setHints_Expr(doesLoad, doesGet, e->Iex.Unop.arg);
3442 return;
sewardjaf1ceca2005-06-30 23:31:27 +00003443 case Iex_Load:
sewardjc9ad1152004-10-14 00:08:21 +00003444 *doesLoad = True;
sewardjaf1ceca2005-06-30 23:31:27 +00003445 setHints_Expr(doesLoad, doesGet, e->Iex.Load.addr);
sewardjc41f1fb2004-08-22 09:48:08 +00003446 return;
sewardj29632392004-08-22 02:38:11 +00003447 case Iex_Get:
sewardjc9ad1152004-10-14 00:08:21 +00003448 *doesGet = True;
sewardj29632392004-08-22 02:38:11 +00003449 return;
sewardjf6501992004-08-27 11:58:24 +00003450 case Iex_GetI:
sewardjc9ad1152004-10-14 00:08:21 +00003451 *doesGet = True;
sewardjeeac8412004-11-02 00:26:55 +00003452 setHints_Expr(doesLoad, doesGet, e->Iex.GetI.ix);
sewardjf6501992004-08-27 11:58:24 +00003453 return;
sewardjc41f1fb2004-08-22 09:48:08 +00003454 case Iex_Tmp:
3455 case Iex_Const:
3456 return;
sewardj29632392004-08-22 02:38:11 +00003457 default:
3458 vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
3459 vpanic("setHints_Expr");
3460 }
3461}
3462
3463
sewardjc9ad1152004-10-14 00:08:21 +00003464static void dumpInvalidated ( TmpInfo** env, IRBB* bb, /*INOUT*/Int* j )
sewardj29632392004-08-22 02:38:11 +00003465{
3466 Int k, oldest_op, oldest_k;
3467 TmpInfo* ti;
3468
3469 /* Dump all the bindings to marked as invalidated, in order. */
3470 while (True) {
3471
3472 /* find the oldest bind marked 'invalidateMe'. */
3473 oldest_op = 1<<30;
3474 oldest_k = 1<<30;
sewardjc9ad1152004-10-14 00:08:21 +00003475 for (k = 0; k < bb->tyenv->types_used; k++) {
3476 ti = env[k];
3477 if (!ti)
sewardj29632392004-08-22 02:38:11 +00003478 continue;
sewardj29632392004-08-22 02:38:11 +00003479 if (!ti->expr)
3480 continue;
3481 if (!ti->invalidateMe)
3482 continue;
sewardjc41f1fb2004-08-22 09:48:08 +00003483 /* vex_printf("FOUND INVAL %d %d\n", ti->origPos, oldest_op); */
sewardj29632392004-08-22 02:38:11 +00003484 if (ti->origPos < oldest_op) {
3485 oldest_op = ti->origPos;
3486 oldest_k = k;
3487 }
3488 }
3489
3490 /* No more binds to invalidate. */
3491 if (oldest_op == 1<<30)
sewardj8bee6d12005-03-22 02:24:05 +00003492 return;
sewardj29632392004-08-22 02:38:11 +00003493
3494 /* the oldest bind to invalidate has been identified */
3495 vassert(oldest_op != 1<<31 && oldest_k != 1<<31);
sewardjc9ad1152004-10-14 00:08:21 +00003496 ti = env[oldest_k];
sewardj29632392004-08-22 02:38:11 +00003497 vassert(ti->expr && ti->invalidateMe);
3498
3499 /* and invalidate it ... */
sewardjc9ad1152004-10-14 00:08:21 +00003500 bb->stmts[*j] = IRStmt_Tmp( (IRTemp)oldest_k, ti->expr );
sewardj29632392004-08-22 02:38:11 +00003501 /* vex_printf("**1 "); ppIRStmt(bb->stmts[*j]); vex_printf("\n"); */
3502 (*j)++;
3503 ti->invalidateMe = False;
3504 ti->expr = NULL; /* no longer available for substitution */
3505
3506 } /* loop which dumps the binds marked for invalidation */
3507}
3508
3509
3510
sewardj49651f42004-10-28 22:11:04 +00003511/* notstatic */ void do_treebuild_BB ( IRBB* bb )
sewardj29632392004-08-22 02:38:11 +00003512{
3513 Int i, j, k;
sewardj29632392004-08-22 02:38:11 +00003514 Bool invPut, invStore;
3515 IRStmt* st;
3516 IRStmt* st2;
3517 TmpInfo* ti;
3518 IRExpr* next2;
3519
3520 /* Mapping from IRTemp to TmpInfo*. */
sewardjc9ad1152004-10-14 00:08:21 +00003521 Int n_tmps = bb->tyenv->types_used;
3522 TmpInfo** env = LibVEX_Alloc(n_tmps * sizeof(TmpInfo*));
3523
3524 for (i = 0; i < n_tmps; i++)
3525 env[i] = NULL;
sewardj29632392004-08-22 02:38:11 +00003526
3527 /* Phase 1. Scan forwards in bb, counting use occurrences of each
3528 temp. Also count occurrences in the bb->next field. */
3529
3530 for (i = 0; i < bb->stmts_used; i++) {
3531 st = bb->stmts[i];
sewardj8bee6d12005-03-22 02:24:05 +00003532 if (st->tag == Ist_NoOp)
sewardj29632392004-08-22 02:38:11 +00003533 continue;
3534 occCount_Stmt( env, st );
3535 }
3536 occCount_Expr(env, bb->next );
3537
sewardjc9ad1152004-10-14 00:08:21 +00003538# if 0
sewardj29632392004-08-22 02:38:11 +00003539 for (i = 0; i < env->used; i++) {
3540 if (!env->inuse[i])
3541 continue;
3542 ppIRTemp( (IRTemp)(env->key[i]) );
3543 vex_printf(" used %d\n", ((TmpInfo*)env->val[i])->occ );
3544 }
sewardjc9ad1152004-10-14 00:08:21 +00003545# endif
sewardj29632392004-08-22 02:38:11 +00003546
3547 /* Phase 2. Fill in the origPos fields. */
3548
3549 for (i = 0; i < bb->stmts_used; i++) {
3550 st = bb->stmts[i];
sewardj29632392004-08-22 02:38:11 +00003551 if (st->tag != Ist_Tmp)
3552 continue;
3553
sewardjc9ad1152004-10-14 00:08:21 +00003554 ti = env[(Int)st->Ist.Tmp.tmp];
3555 if (!ti) {
sewardj84ff0652004-08-23 16:16:08 +00003556 vex_printf("\n");
3557 ppIRTemp(st->Ist.Tmp.tmp);
3558 vex_printf("\n");
sewardj29632392004-08-22 02:38:11 +00003559 vpanic("treebuild_BB (phase 2): unmapped IRTemp");
3560 }
sewardj29632392004-08-22 02:38:11 +00003561 ti->origPos = i;
3562 }
3563
3564 /* Phase 3. Scan forwards in bb.
3565
3566 On seeing 't = E', occ(t)==1,
3567 let E'=env(E), set t's binding to be E', and
3568 delete this stmt.
3569 Also examine E' and set the hints for E' appropriately
3570 (doesLoad? doesGet?)
3571
3572 On seeing any other stmt,
3573 let stmt' = env(stmt)
3574 remove from env any 't=E' binds invalidated by stmt
3575 emit the invalidated stmts
3576 emit stmt'
3577
3578 Apply env to bb->next.
3579 */
3580
3581 /* The stmts in bb are being reordered, and we are guaranteed to
3582 end up with no more than the number we started with. Use i to
3583 be the cursor of the current stmt examined and j <= i to be that
3584 for the current stmt being written.
3585 */
3586 j = 0;
3587 for (i = 0; i < bb->stmts_used; i++) {
3588 st = bb->stmts[i];
sewardj8bee6d12005-03-22 02:24:05 +00003589 if (st->tag == Ist_NoOp)
sewardj29632392004-08-22 02:38:11 +00003590 continue;
3591
3592 if (st->tag == Ist_Tmp) {
sewardje80679a2004-09-21 23:00:11 +00003593 /* vex_printf("acquire binding\n"); */
sewardjc9ad1152004-10-14 00:08:21 +00003594 ti = env[st->Ist.Tmp.tmp];
3595 if (!ti) {
sewardj29632392004-08-22 02:38:11 +00003596 vpanic("treebuild_BB (phase 2): unmapped IRTemp");
3597 }
sewardj29632392004-08-22 02:38:11 +00003598 if (ti->occ == 1) {
3599 /* ok, we have 't = E', occ(t)==1. Do the abovementioned actions. */
sewardj6d076362004-09-23 11:06:17 +00003600 IRExpr* e = st->Ist.Tmp.data;
sewardj29632392004-08-22 02:38:11 +00003601 IRExpr* e2 = tbSubst_Expr(env, e);
3602 ti->expr = e2;
3603 ti->eDoesLoad = ti->eDoesGet = False;
3604 setHints_Expr(&ti->eDoesLoad, &ti->eDoesGet, e2);
3605 /* don't advance j, as we are deleting this stmt and instead
3606 holding it temporarily in the env. */
3607 continue; /* the for (i = 0; i < bb->stmts_used; i++) loop */
3608 }
3609 }
3610
3611 /* we get here for any other kind of statement. */
3612 /* 'use up' any bindings required by the current statement. */
3613 st2 = tbSubst_Stmt(env, st);
3614
3615 /* Now, before this stmt, dump any bindings it invalidates.
3616 These need to be dumped in the order in which they originally
3617 appeared. (Stupid algorithm): first, mark all bindings which
3618 need to be dumped. Then, dump them in the order in which
3619 they were defined. */
sewardj3e838932005-01-07 12:09:15 +00003620
sewardj9d2e7692005-02-07 01:11:31 +00003621 invPut = toBool(st->tag == Ist_Put
3622 || st->tag == Ist_PutI
3623 || st->tag == Ist_Dirty);
sewardj3e838932005-01-07 12:09:15 +00003624
sewardjaf1ceca2005-06-30 23:31:27 +00003625 invStore = toBool(st->tag == Ist_Store
sewardj9d2e7692005-02-07 01:11:31 +00003626 || st->tag == Ist_Dirty);
sewardj29632392004-08-22 02:38:11 +00003627
sewardjc9ad1152004-10-14 00:08:21 +00003628 for (k = 0; k < n_tmps; k++) {
3629 ti = env[k];
3630 if (!ti)
sewardj29632392004-08-22 02:38:11 +00003631 continue;
sewardj29632392004-08-22 02:38:11 +00003632 if (!ti->expr)
3633 continue;
3634
sewardj3e838932005-01-07 12:09:15 +00003635 /* Do we have to invalidate this binding? */
3636
sewardj29632392004-08-22 02:38:11 +00003637 ti->invalidateMe
sewardj9d2e7692005-02-07 01:11:31 +00003638 = toBool(
3639 /* a store invalidates loaded data */
sewardj4c5f6d52004-10-26 13:25:33 +00003640 (ti->eDoesLoad && invStore)
3641 /* a put invalidates get'd data */
3642 || (ti->eDoesGet && invPut)
3643 /* a put invalidates loaded data. Note, we could do
3644 much better here in the sense that we only need to
3645 invalidate trees containing loads if the Put in
3646 question is marked as requiring precise
3647 exceptions. */
sewardj3e838932005-01-07 12:09:15 +00003648 || (ti->eDoesLoad && invPut)
3649 /* probably overly conservative: a memory fence
3650 invalidates absolutely everything, so that all
3651 computation prior to it is forced to complete before
3652 proceeding with the fence. */
sewardj9d2e7692005-02-07 01:11:31 +00003653 || st->tag == Ist_MFence
sewardj5a9ffab2005-05-12 17:55:01 +00003654 /* also be (probably overly) paranoid re AbiHints */
3655 || st->tag == Ist_AbiHint
sewardj9d2e7692005-02-07 01:11:31 +00003656 );
sewardjc41f1fb2004-08-22 09:48:08 +00003657 /*
3658 if (ti->invalidateMe)
sewardj3e838932005-01-07 12:09:15 +00003659 vex_printf("SET INVAL\n");
3660 */
sewardj29632392004-08-22 02:38:11 +00003661 }
3662
3663 dumpInvalidated ( env, bb, &j );
3664
3665 /* finally, emit the substituted statement */
3666 bb->stmts[j] = st2;
3667 /* vex_printf("**2 "); ppIRStmt(bb->stmts[j]); vex_printf("\n"); */
3668 j++;
3669
3670 vassert(j <= i+1);
3671 } /* for each stmt in the original bb ... */
3672
3673 /* Finally ... substitute the ->next field as much as possible, and
3674 dump any left-over bindings. Hmm. Perhaps there should be no
3675 left over bindings? Or any left-over bindings are
3676 by definition dead? */
3677 next2 = tbSubst_Expr(env, bb->next);
3678 bb->next = next2;
3679 bb->stmts_used = j;
3680}
3681
3682
sewardj695cff92004-10-13 14:50:14 +00003683/*---------------------------------------------------------------*/
sewardjedf4d692004-08-17 13:52:58 +00003684/*--- iropt main ---*/
3685/*---------------------------------------------------------------*/
3686
sewardj695cff92004-10-13 14:50:14 +00003687static Bool iropt_verbose = False; //True;
sewardj4345f7a2004-09-22 19:49:27 +00003688
3689
sewardj4345f7a2004-09-22 19:49:27 +00003690/* Do a simple cleanup pass on bb. This is: redundant Get removal,
3691 redundant Put removal, constant propagation, dead code removal,
3692 clean helper specialisation, and dead code removal (again).
sewardjb9230752004-12-29 19:25:06 +00003693*/
sewardj695cff92004-10-13 14:50:14 +00003694
sewardj4345f7a2004-09-22 19:49:27 +00003695
3696static
sewardj695cff92004-10-13 14:50:14 +00003697IRBB* cheap_transformations (
3698 IRBB* bb,
sewardj9d2e7692005-02-07 01:11:31 +00003699 IRExpr* (*specHelper) (HChar*, IRExpr**),
sewardj8d2291c2004-10-25 14:50:21 +00003700 Bool (*preciseMemExnsFn)(Int,Int)
3701 )
sewardj4345f7a2004-09-22 19:49:27 +00003702{
3703 redundant_get_removal_BB ( bb );
3704 if (iropt_verbose) {
3705 vex_printf("\n========= REDUNDANT GET\n\n" );
3706 ppIRBB(bb);
3707 }
sewardj044a2152004-10-21 10:22:10 +00003708
sewardj8d2291c2004-10-25 14:50:21 +00003709 redundant_put_removal_BB ( bb, preciseMemExnsFn );
sewardj4345f7a2004-09-22 19:49:27 +00003710 if (iropt_verbose) {
3711 vex_printf("\n========= REDUNDANT PUT\n\n" );
3712 ppIRBB(bb);
3713 }
sewardj044a2152004-10-21 10:22:10 +00003714
sewardj4345f7a2004-09-22 19:49:27 +00003715 bb = cprop_BB ( bb );
3716 if (iropt_verbose) {
3717 vex_printf("\n========= CPROPD\n\n" );
3718 ppIRBB(bb);
3719 }
3720
sewardj49651f42004-10-28 22:11:04 +00003721 do_deadcode_BB ( bb );
sewardj4345f7a2004-09-22 19:49:27 +00003722 if (iropt_verbose) {
3723 vex_printf("\n========= DEAD\n\n" );
3724 ppIRBB(bb);
3725 }
3726
sewardjb9230752004-12-29 19:25:06 +00003727 bb = spec_helpers_BB ( bb, specHelper );
sewardj49651f42004-10-28 22:11:04 +00003728 do_deadcode_BB ( bb );
sewardj4345f7a2004-09-22 19:49:27 +00003729 if (iropt_verbose) {
3730 vex_printf("\n========= SPECd \n\n" );
3731 ppIRBB(bb);
3732 }
3733
3734 return bb;
3735}
3736
sewardj695cff92004-10-13 14:50:14 +00003737
3738/* Do some more expensive transformations on bb, which are aimed at
3739 optimising as much as possible in the presence of GetI and PutI. */
3740
3741static
3742IRBB* expensive_transformations( IRBB* bb )
3743{
sewardjfe1ccfc2004-11-11 02:14:45 +00003744 do_cse_BB( bb );
sewardj695cff92004-10-13 14:50:14 +00003745 collapse_AddSub_chains_BB( bb );
sewardj08210532004-12-29 17:09:11 +00003746 do_redundant_GetI_elimination( bb );
sewardj695cff92004-10-13 14:50:14 +00003747 do_redundant_PutI_elimination( bb );
sewardj49651f42004-10-28 22:11:04 +00003748 do_deadcode_BB( bb );
sewardjb9230752004-12-29 19:25:06 +00003749 return bb;
sewardj695cff92004-10-13 14:50:14 +00003750}
3751
3752
sewardj4345f7a2004-09-22 19:49:27 +00003753/* Scan a flattened BB to see if it has any GetI or PutIs in it. Used
3754 as a heuristic hack to see if iropt needs to do expensive
sewardj695cff92004-10-13 14:50:14 +00003755 optimisations (CSE, PutI -> GetI forwarding, redundant PutI
3756 elimination) to improve code containing GetI or PutI. */
3757
sewardj4345f7a2004-09-22 19:49:27 +00003758static Bool hasGetIorPutI ( IRBB* bb )
3759{
3760 Int i, j;
3761 IRStmt* st;
3762 IRDirty* d;
3763
3764 for (i = 0; i < bb->stmts_used; i++) {
3765 st = bb->stmts[i];
sewardj4345f7a2004-09-22 19:49:27 +00003766 switch (st->tag) {
sewardj5a9ffab2005-05-12 17:55:01 +00003767 case Ist_AbiHint:
3768 vassert(isIRAtom(st->Ist.AbiHint.base));
3769 break;
sewardj4345f7a2004-09-22 19:49:27 +00003770 case Ist_PutI:
3771 return True;
3772 case Ist_Tmp:
sewardj6d076362004-09-23 11:06:17 +00003773 if (st->Ist.Tmp.data->tag == Iex_GetI)
sewardj4345f7a2004-09-22 19:49:27 +00003774 return True;
3775 break;
3776 case Ist_Put:
sewardj496a58d2005-03-20 18:44:44 +00003777 vassert(isIRAtom(st->Ist.Put.data));
sewardj4345f7a2004-09-22 19:49:27 +00003778 break;
sewardjaf1ceca2005-06-30 23:31:27 +00003779 case Ist_Store:
3780 vassert(isIRAtom(st->Ist.Store.addr));
3781 vassert(isIRAtom(st->Ist.Store.data));
sewardj4345f7a2004-09-22 19:49:27 +00003782 break;
sewardj4345f7a2004-09-22 19:49:27 +00003783 case Ist_Dirty:
3784 d = st->Ist.Dirty.details;
sewardj496a58d2005-03-20 18:44:44 +00003785 vassert(isIRAtom(d->guard));
sewardj4345f7a2004-09-22 19:49:27 +00003786 for (j = 0; d->args[j]; j++)
sewardj496a58d2005-03-20 18:44:44 +00003787 vassert(isIRAtom(d->args[j]));
sewardj4345f7a2004-09-22 19:49:27 +00003788 if (d->mFx != Ifx_None)
sewardj496a58d2005-03-20 18:44:44 +00003789 vassert(isIRAtom(d->mAddr));
sewardj4345f7a2004-09-22 19:49:27 +00003790 break;
sewardjd2445f62005-03-21 00:15:53 +00003791 case Ist_NoOp:
sewardjf1689312005-03-16 18:19:10 +00003792 case Ist_IMark:
sewardj3e838932005-01-07 12:09:15 +00003793 case Ist_MFence:
3794 break;
3795 case Ist_Exit:
sewardj496a58d2005-03-20 18:44:44 +00003796 vassert(isIRAtom(st->Ist.Exit.guard));
sewardj3e838932005-01-07 12:09:15 +00003797 break;
sewardj4345f7a2004-09-22 19:49:27 +00003798 default:
3799 ppIRStmt(st);
3800 vpanic("hasGetIorPutI");
3801 }
3802
3803 }
3804 return False;
3805
3806}
3807
3808
sewardj695cff92004-10-13 14:50:14 +00003809/* ---------------- The main iropt entry point. ---------------- */
3810
sewardjedf4d692004-08-17 13:52:58 +00003811/* exported from this file */
sewardj695cff92004-10-13 14:50:14 +00003812/* Rules of the game:
3813
3814 - IRExpr/IRStmt trees should be treated as immutable, as they
3815 may get shared. So never change a field of such a tree node;
3816 instead construct and return a new one if needed.
3817*/
3818
sewardj4345f7a2004-09-22 19:49:27 +00003819
sewardj84ff0652004-08-23 16:16:08 +00003820IRBB* do_iropt_BB ( IRBB* bb0,
sewardj9d2e7692005-02-07 01:11:31 +00003821 IRExpr* (*specHelper) (HChar*, IRExpr**),
sewardj8d2291c2004-10-25 14:50:21 +00003822 Bool (*preciseMemExnsFn)(Int,Int),
sewardj695cff92004-10-13 14:50:14 +00003823 Addr64 guest_addr )
sewardjedf4d692004-08-17 13:52:58 +00003824{
sewardj9d2e7692005-02-07 01:11:31 +00003825 static Int n_total = 0;
3826 static Int n_expensive = 0;
sewardj29632392004-08-22 02:38:11 +00003827
sewardj695cff92004-10-13 14:50:14 +00003828 Bool do_expensive;
sewardj695cff92004-10-13 14:50:14 +00003829 IRBB *bb, *bb2;
sewardj8c2c10b2004-10-16 20:51:52 +00003830
sewardj4345f7a2004-09-22 19:49:27 +00003831 n_total++;
3832
3833 /* First flatten the block out, since all other
3834 phases assume flat code. */
3835
3836 bb = flatten_BB ( bb0 );
3837
3838 if (iropt_verbose) {
3839 vex_printf("\n========= FLAT\n\n" );
3840 ppIRBB(bb);
sewardj84be7372004-08-18 13:59:33 +00003841 }
sewardjd7217032004-08-19 10:49:10 +00003842
sewardj08210532004-12-29 17:09:11 +00003843 /* If at level 0, stop now. */
3844 if (vex_control.iropt_level <= 0) return bb;
3845
sewardj695cff92004-10-13 14:50:14 +00003846 /* Now do a preliminary cleanup pass, and figure out if we also
3847 need to do 'expensive' optimisations. Expensive optimisations
3848 are deemed necessary if the block contains any GetIs or PutIs.
3849 If needed, do expensive transformations and then another cheap
3850 cleanup pass. */
sewardj4345f7a2004-09-22 19:49:27 +00003851
sewardj8d2291c2004-10-25 14:50:21 +00003852 bb = cheap_transformations( bb, specHelper, preciseMemExnsFn );
sewardj695cff92004-10-13 14:50:14 +00003853
sewardj08613742004-10-25 13:01:45 +00003854 if (vex_control.iropt_level > 1) {
sewardj39555aa2004-10-24 22:29:19 +00003855 do_expensive = hasGetIorPutI(bb);
sewardj695cff92004-10-13 14:50:14 +00003856 if (do_expensive) {
sewardj39555aa2004-10-24 22:29:19 +00003857 n_expensive++;
sewardj39555aa2004-10-24 22:29:19 +00003858 if (DEBUG_IROPT)
3859 vex_printf("***** EXPENSIVE %d %d\n", n_total, n_expensive);
sewardj695cff92004-10-13 14:50:14 +00003860 bb = expensive_transformations( bb );
sewardj8d2291c2004-10-25 14:50:21 +00003861 bb = cheap_transformations( bb, specHelper, preciseMemExnsFn );
sewardj695cff92004-10-13 14:50:14 +00003862 }
sewardj39555aa2004-10-24 22:29:19 +00003863
3864 /* Now have a go at unrolling simple (single-BB) loops. If
3865 successful, clean up the results as much as possible. */
3866
3867 bb2 = maybe_loop_unroll_BB( bb, guest_addr );
3868 if (bb2) {
sewardj8d2291c2004-10-25 14:50:21 +00003869 bb = cheap_transformations( bb2, specHelper, preciseMemExnsFn );
sewardj39555aa2004-10-24 22:29:19 +00003870 if (do_expensive) {
3871 bb = expensive_transformations( bb );
sewardj8d2291c2004-10-25 14:50:21 +00003872 bb = cheap_transformations( bb, specHelper, preciseMemExnsFn );
sewardj39555aa2004-10-24 22:29:19 +00003873 } else {
3874 /* at least do CSE and dead code removal */
sewardjfe1ccfc2004-11-11 02:14:45 +00003875 do_cse_BB( bb );
sewardj49651f42004-10-28 22:11:04 +00003876 do_deadcode_BB( bb );
sewardj39555aa2004-10-24 22:29:19 +00003877 }
3878 if (0) vex_printf("vex iropt: unrolled a loop\n");
3879 }
3880
sewardjd7217032004-08-19 10:49:10 +00003881 }
3882
sewardj4345f7a2004-09-22 19:49:27 +00003883 return bb;
sewardjedf4d692004-08-17 13:52:58 +00003884}
3885
3886
sewardja1a370f2004-08-17 13:31:55 +00003887/*---------------------------------------------------------------*/
3888/*--- end ir/iropt.c ---*/
3889/*---------------------------------------------------------------*/