l4/pkg/valgrind/src/valgrind-3.6.0-svn/VEX/priv/ir_opt.c

   1
   2 /*---------------------------------------------------------------*/
   3 /*--- begin                                          ir_opt.c ---*/
   4 /*---------------------------------------------------------------*/
   5
   6 /*
   7    This file is part of Valgrind, a dynamic binary instrumentation
   8    framework.
   9
  10    Copyright (C) 2004-2010 OpenWorks LLP
  11       info@open-works.net
  12
  13    This program is free software; you can redistribute it and/or
  14    modify it under the terms of the GNU General Public License as
  15    published by the Free Software Foundation; either version 2 of the
  16    License, or (at your option) any later version.
  17
  18    This program is distributed in the hope that it will be useful, but
  19    WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21    General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program; if not, write to the Free Software
  25    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  26    02110-1301, USA.
  27
  28    The GNU General Public License is contained in the file COPYING.
  29
  30    Neither the names of the U.S. Department of Energy nor the
  31    University of California nor the names of its contributors may be
  32    used to endorse or promote products derived from this software
  33    without prior written permission.
  34 */
  35
  36 #include "libvex_basictypes.h"
  37 #include "libvex_ir.h"
  38 #include "libvex.h"
  39
  40 #include "main_util.h"
  41 #include "main_globals.h"
  42 #include "ir_opt.h"
  43
  44
  45 /* Set to 1 for lots of debugging output. */
  46 #define DEBUG_IROPT 0
  47
  48
  49 /* What iropt does, 29 Dec 04.
  50
  51    It takes an IRSB 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
  99
 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.
 109
 110    Level 2: the following sequence
 111       * Flatten into atomic form.
 112       * Cheap transformations.
 113       * If block contains any floating or vector types, CSE.
 114       * If block contains GetI or PutI, Expensive transformations.
 115       * Try unrolling loops.  Three possible outcomes:
 116         - No effect: do nothing more.
 117         - Unrolled a loop, and block does not contain GetI or PutI:
 118           Do: * CSE
 119               * Dead code removal
 120         - Unrolled a loop, and block contains GetI or PutI:
 121           Do: * Expensive transformations
 122               * Cheap transformations
 123 */
 124
 125 /* Implementation notes, 29 Dec 04.
 126
 127    TODO (important): I think rPutI removal ignores precise exceptions
 128    and is therefore in a sense, wrong.  In the sense that PutIs are
 129    assumed not to write parts of the guest state that we need to have
 130    up-to-date at loads/stores.  So far on x86 guest that has not
 131    mattered since indeed only the x87 FP registers and tags are
 132    accessed using GetI/PutI, and there is no need so far for them to
 133    be up to date at mem exception points.  The rPutI pass should be
 134    fixed.
 135
 136    TODO: improve pessimistic handling of precise exceptions
 137      in the tree builder.
 138
 139    TODO: check interaction of rGetI and dirty helpers.
 140
 141    F64i constants are treated differently from other constants.
 142    They are not regarded as atoms, and instead lifted off and
 143    bound to temps.  This allows them to participate in CSE, which
 144    is important for getting good performance for x86 guest code.
 145
 146    CSE up F64 literals (already doing F64is)
 147
 148    CSE: consider carefully the requirement for precise exns
 149         prior to making CSE any more aggressive.  */
 150
 151
 152 /*---------------------------------------------------------------*/
 153 /*--- Finite mappery, of a sort                               ---*/
 154 /*---------------------------------------------------------------*/
 155
 156 /* General map from HWord-sized thing HWord-sized thing.  Could be by
 157    hashing, but it's not clear whether or not this would really be any
 158    faster. */
 159
 160 typedef
 161    struct {
 162       Bool*  inuse;
 163       HWord* key;
 164       HWord* val;
 165       Int    size;
 166       Int    used;
 167    }
 168    HashHW;
 169
 170 static HashHW* newHHW ( void )
 171 {
 172    HashHW* h = LibVEX_Alloc(sizeof(HashHW));
 173    h->size   = 8;
 174    h->used   = 0;
 175    h->inuse  = LibVEX_Alloc(h->size * sizeof(Bool));
 176    h->key    = LibVEX_Alloc(h->size * sizeof(HWord));
 177    h->val    = LibVEX_Alloc(h->size * sizeof(HWord));
 178    return h;
 179 }
 180
 181
 182 /* Look up key in the map. */
 183
 184 static Bool lookupHHW ( HashHW* h, /*OUT*/HWord* val, HWord key )
 185 {
 186    Int i;
 187    /* vex_printf("lookupHHW(%llx)\n", key ); */
 188    for (i = 0; i < h->used; i++) {
 189       if (h->inuse[i] && h->key[i] == key) {
 190          if (val)
 191             *val = h->val[i];
 192          return True;
 193       }
 194    }
 195    return False;
 196 }
 197
 198
 199 /* Add key->val to the map.  Replaces any existing binding for key. */
 200
 201 static void addToHHW ( HashHW* h, HWord key, HWord val )
 202 {
 203    Int i, j;
 204    /* vex_printf("addToHHW(%llx, %llx)\n", key, val); */
 205
 206    /* Find and replace existing binding, if any. */
 207    for (i = 0; i < h->used; i++) {
 208       if (h->inuse[i] && h->key[i] == key) {
 209          h->val[i] = val;
 210          return;
 211       }
 212    }
 213
 214    /* Ensure a space is available. */
 215    if (h->used == h->size) {
 216       /* Copy into arrays twice the size. */
 217       Bool*  inuse2 = LibVEX_Alloc(2 * h->size * sizeof(Bool));
 218       HWord* key2   = LibVEX_Alloc(2 * h->size * sizeof(HWord));
 219       HWord* val2   = LibVEX_Alloc(2 * h->size * sizeof(HWord));
 220       for (i = j = 0; i < h->size; i++) {
 221          if (!h->inuse[i]) continue;
 222          inuse2[j] = True;
 223          key2[j] = h->key[i];
 224          val2[j] = h->val[i];
 225          j++;
 226       }
 227       h->used = j;
 228       h->size *= 2;
 229       h->inuse = inuse2;
 230       h->key = key2;
 231       h->val = val2;
 232    }
 233
 234    /* Finally, add it. */
 235    vassert(h->used < h->size);
 236    h->inuse[h->used] = True;
 237    h->key[h->used] = key;
 238    h->val[h->used] = val;
 239    h->used++;
 240 }
 241
 242
 243 /*---------------------------------------------------------------*/
 244 /*--- Flattening out a BB into atomic SSA form                ---*/
 245 /*---------------------------------------------------------------*/
 246
 247 /* Non-critical helper, heuristic for reducing the number of tmp-tmp
 248    copies made by flattening.  If in doubt return False. */
 249
 250 static Bool isFlat ( IRExpr* e )
 251 {
 252    if (e->tag == Iex_Get)
 253       return True;
 254    if (e->tag == Iex_Binop)
 255       return toBool( isIRAtom(e->Iex.Binop.arg1)
 256                      && isIRAtom(e->Iex.Binop.arg2) );
 257    if (e->tag == Iex_Load)
 258       return isIRAtom(e->Iex.Load.addr);
 259    return False;
 260 }
 261
 262 /* Flatten out 'ex' so it is atomic, returning a new expression with
 263    the same value, after having appended extra IRTemp assignments to
 264    the end of 'bb'. */
 265
 266 static IRExpr* flatten_Expr ( IRSB* bb, IRExpr* ex )
 267 {
 268    Int i;
 269    IRExpr** newargs;
 270    IRType ty = typeOfIRExpr(bb->tyenv, ex);
 271    IRTemp t1;
 272
 273    switch (ex->tag) {
 274
 275       case Iex_GetI:
 276          t1 = newIRTemp(bb->tyenv, ty);
 277          addStmtToIRSB(bb, IRStmt_WrTmp(t1,
 278             IRExpr_GetI(ex->Iex.GetI.descr,
 279                         flatten_Expr(bb, ex->Iex.GetI.ix),
 280                         ex->Iex.GetI.bias)));
 281          return IRExpr_RdTmp(t1);
 282
 283       case Iex_Get:
 284          t1 = newIRTemp(bb->tyenv, ty);
 285          addStmtToIRSB(bb,
 286             IRStmt_WrTmp(t1, ex));
 287          return IRExpr_RdTmp(t1);
 288
 289       case Iex_Qop:
 290          t1 = newIRTemp(bb->tyenv, ty);
 291          addStmtToIRSB(bb, IRStmt_WrTmp(t1,
 292             IRExpr_Qop(ex->Iex.Qop.op,
 293                          flatten_Expr(bb, ex->Iex.Qop.arg1),
 294                          flatten_Expr(bb, ex->Iex.Qop.arg2),
 295                          flatten_Expr(bb, ex->Iex.Qop.arg3),
 296                          flatten_Expr(bb, ex->Iex.Qop.arg4))));
 297          return IRExpr_RdTmp(t1);
 298
 299       case Iex_Triop:
 300          t1 = newIRTemp(bb->tyenv, ty);
 301          addStmtToIRSB(bb, IRStmt_WrTmp(t1,
 302             IRExpr_Triop(ex->Iex.Triop.op,
 303                          flatten_Expr(bb, ex->Iex.Triop.arg1),
 304                          flatten_Expr(bb, ex->Iex.Triop.arg2),
 305                          flatten_Expr(bb, ex->Iex.Triop.arg3))));
 306          return IRExpr_RdTmp(t1);
 307
 308       case Iex_Binop:
 309          t1 = newIRTemp(bb->tyenv, ty);
 310          addStmtToIRSB(bb, IRStmt_WrTmp(t1,
 311             IRExpr_Binop(ex->Iex.Binop.op,
 312                          flatten_Expr(bb, ex->Iex.Binop.arg1),
 313                          flatten_Expr(bb, ex->Iex.Binop.arg2))));
 314          return IRExpr_RdTmp(t1);
 315
 316       case Iex_Unop:
 317          t1 = newIRTemp(bb->tyenv, ty);
 318          addStmtToIRSB(bb, IRStmt_WrTmp(t1,
 319             IRExpr_Unop(ex->Iex.Unop.op,
 320                         flatten_Expr(bb, ex->Iex.Unop.arg))));
 321          return IRExpr_RdTmp(t1);
 322
 323       case Iex_Load:
 324          t1 = newIRTemp(bb->tyenv, ty);
 325          addStmtToIRSB(bb, IRStmt_WrTmp(t1,
 326             IRExpr_Load(ex->Iex.Load.end,
 327                         ex->Iex.Load.ty,
 328                         flatten_Expr(bb, ex->Iex.Load.addr))));
 329          return IRExpr_RdTmp(t1);
 330
 331       case Iex_CCall:
 332          newargs = shallowCopyIRExprVec(ex->Iex.CCall.args);
 333          for (i = 0; newargs[i]; i++)
 334             newargs[i] = flatten_Expr(bb, newargs[i]);
 335          t1 = newIRTemp(bb->tyenv, ty);
 336          addStmtToIRSB(bb, IRStmt_WrTmp(t1,
 337             IRExpr_CCall(ex->Iex.CCall.cee,
 338                          ex->Iex.CCall.retty,
 339                          newargs)));
 340          return IRExpr_RdTmp(t1);
 341
 342       case Iex_Mux0X:
 343          t1 = newIRTemp(bb->tyenv, ty);
 344          addStmtToIRSB(bb, IRStmt_WrTmp(t1,
 345             IRExpr_Mux0X(flatten_Expr(bb, ex->Iex.Mux0X.cond),
 346                          flatten_Expr(bb, ex->Iex.Mux0X.expr0),
 347                          flatten_Expr(bb, ex->Iex.Mux0X.exprX))));
 348          return IRExpr_RdTmp(t1);
 349
 350       case Iex_Const:
 351          /* Lift F64i constants out onto temps so they can be CSEd
 352             later. */
 353          if (ex->Iex.Const.con->tag == Ico_F64i) {
 354             t1 = newIRTemp(bb->tyenv, ty);
 355             addStmtToIRSB(bb, IRStmt_WrTmp(t1,
 356                IRExpr_Const(ex->Iex.Const.con)));
 357             return IRExpr_RdTmp(t1);
 358          } else {
 359             /* Leave all other constants alone. */
 360             return ex;
 361          }
 362
 363       case Iex_RdTmp:
 364          return ex;
 365
 366       default:
 367          vex_printf("\n");
 368          ppIRExpr(ex);
 369          vex_printf("\n");
 370          vpanic("flatten_Expr");
 371    }
 372 }
 373
 374
 375 /* Append a completely flattened form of 'st' to the end of 'bb'. */
 376
 377 static void flatten_Stmt ( IRSB* bb, IRStmt* st )
 378 {
 379    Int i;
 380    IRExpr  *e1, *e2, *e3, *e4, *e5;
 381    IRDirty *d,  *d2;
 382    IRCAS   *cas, *cas2;
 383    switch (st->tag) {
 384       case Ist_Put:
 385          if (isIRAtom(st->Ist.Put.data)) {
 386             /* optimisation to reduce the amount of heap wasted
 387                by the flattener */
 388             addStmtToIRSB(bb, st);
 389          } else {
 390             /* general case, always correct */
 391             e1 = flatten_Expr(bb, st->Ist.Put.data);
 392             addStmtToIRSB(bb, IRStmt_Put(st->Ist.Put.offset, e1));
 393          }
 394          break;
 395       case Ist_PutI:
 396          e1 = flatten_Expr(bb, st->Ist.PutI.ix);
 397          e2 = flatten_Expr(bb, st->Ist.PutI.data);
 398          addStmtToIRSB(bb, IRStmt_PutI(st->Ist.PutI.descr,
 399                                        e1,
 400                                        st->Ist.PutI.bias,
 401                                        e2));
 402          break;
 403       case Ist_WrTmp:
 404          if (isFlat(st->Ist.WrTmp.data)) {
 405             /* optimisation, to reduce the number of tmp-tmp
 406                copies generated */
 407             addStmtToIRSB(bb, st);
 408          } else {
 409             /* general case, always correct */
 410             e1 = flatten_Expr(bb, st->Ist.WrTmp.data);
 411             addStmtToIRSB(bb, IRStmt_WrTmp(st->Ist.WrTmp.tmp, e1));
 412          }
 413          break;
 414       case Ist_Store:
 415          e1 = flatten_Expr(bb, st->Ist.Store.addr);
 416          e2 = flatten_Expr(bb, st->Ist.Store.data);
 417          addStmtToIRSB(bb, IRStmt_Store(st->Ist.Store.end, e1,e2));
 418          break;
 419       case Ist_CAS:
 420          cas  = st->Ist.CAS.details;
 421          e1   = flatten_Expr(bb, cas->addr);
 422          e2   = cas->expdHi ? flatten_Expr(bb, cas->expdHi) : NULL;
 423          e3   = flatten_Expr(bb, cas->expdLo);
 424          e4   = cas->dataHi ? flatten_Expr(bb, cas->dataHi) : NULL;
 425          e5   = flatten_Expr(bb, cas->dataLo);
 426          cas2 = mkIRCAS( cas->oldHi, cas->oldLo, cas->end,
 427                          e1, e2, e3, e4, e5 );
 428          addStmtToIRSB(bb, IRStmt_CAS(cas2));
 429          break;
 430       case Ist_LLSC:
 431          e1 = flatten_Expr(bb, st->Ist.LLSC.addr);
 432          e2 = st->Ist.LLSC.storedata
 433                  ? flatten_Expr(bb, st->Ist.LLSC.storedata)
 434                  : NULL;
 435          addStmtToIRSB(bb, IRStmt_LLSC(st->Ist.LLSC.end,
 436                                        st->Ist.LLSC.result, e1, e2));
 437          break;
 438       case Ist_Dirty:
 439          d = st->Ist.Dirty.details;
 440          d2 = emptyIRDirty();
 441          *d2 = *d;
 442          d2->args = shallowCopyIRExprVec(d2->args);
 443          if (d2->mFx != Ifx_None) {
 444             d2->mAddr = flatten_Expr(bb, d2->mAddr);
 445          } else {
 446             vassert(d2->mAddr == NULL);
 447          }
 448          d2->guard = flatten_Expr(bb, d2->guard);
 449          for (i = 0; d2->args[i]; i++)
 450             d2->args[i] = flatten_Expr(bb, d2->args[i]);
 451          addStmtToIRSB(bb, IRStmt_Dirty(d2));
 452          break;
 453       case Ist_NoOp:
 454       case Ist_MBE:
 455       case Ist_IMark:
 456          addStmtToIRSB(bb, st);
 457          break;
 458       case Ist_AbiHint:
 459          e1 = flatten_Expr(bb, st->Ist.AbiHint.base);
 460          e2 = flatten_Expr(bb, st->Ist.AbiHint.nia);
 461          addStmtToIRSB(bb, IRStmt_AbiHint(e1, st->Ist.AbiHint.len, e2));
 462          break;
 463       case Ist_Exit:
 464          e1 = flatten_Expr(bb, st->Ist.Exit.guard);
 465          addStmtToIRSB(bb, IRStmt_Exit(e1, st->Ist.Exit.jk,
 466                                            st->Ist.Exit.dst));
 467          break;
 468       default:
 469          vex_printf("\n");
 470          ppIRStmt(st);
 471          vex_printf("\n");
 472          vpanic("flatten_Stmt");
 473    }
 474 }
 475
 476
 477 static IRSB* flatten_BB ( IRSB* in )
 478 {
 479    Int   i;
 480    IRSB* out;
 481    out = emptyIRSB();
 482    out->tyenv = deepCopyIRTypeEnv( in->tyenv );
 483    for (i = 0; i < in->stmts_used; i++)
 484       if (in->stmts[i])
 485          flatten_Stmt( out, in->stmts[i] );
 486    out->next     = flatten_Expr( out, in->next );
 487    out->jumpkind = in->jumpkind;
 488    return out;
 489 }
 490
 491
 492 /*---------------------------------------------------------------*/
 493 /*--- In-place removal of redundant GETs                      ---*/
 494 /*---------------------------------------------------------------*/
 495
 496 /* Scan forwards, building up an environment binding (min offset, max
 497    offset) pairs to values, which will either be temps or constants.
 498
 499    On seeing 't = Get(minoff,maxoff)', look up (minoff,maxoff) in the
 500    env and if it matches, replace the Get with the stored value.  If
 501    there is no match, add a (minoff,maxoff) :-> t binding.
 502
 503    On seeing 'Put (minoff,maxoff) = t or c', first remove in the env
 504    any binding which fully or partially overlaps with (minoff,maxoff).
 505    Then add a new (minoff,maxoff) :-> t or c binding.  */
 506
 507 /* Extract the min/max offsets from a guest state array descriptor. */
 508
 509 inline
 510 static void getArrayBounds ( IRRegArray* descr,
 511                              UInt* minoff, UInt* maxoff )
 512 {
 513    *minoff = descr->base;
 514    *maxoff = *minoff + descr->nElems*sizeofIRType(descr->elemTy) - 1;
 515    vassert((*minoff & ~0xFFFF) == 0);
 516    vassert((*maxoff & ~0xFFFF) == 0);
 517    vassert(*minoff <= *maxoff);
 518 }
 519
 520 /* Create keys, of the form ((minoffset << 16) | maxoffset). */
 521
 522 static UInt mk_key_GetPut ( Int offset, IRType ty )
 523 {
 524    /* offset should fit in 16 bits. */
 525    UInt minoff = offset;
 526    UInt maxoff = minoff + sizeofIRType(ty) - 1;
 527    vassert((minoff & ~0xFFFF) == 0);
 528    vassert((maxoff & ~0xFFFF) == 0);
 529    return (minoff << 16) | maxoff;
 530 }
 531
 532 static UInt mk_key_GetIPutI ( IRRegArray* descr )
 533 {
 534    UInt minoff, maxoff;
 535    getArrayBounds( descr, &minoff, &maxoff );
 536    vassert((minoff & ~0xFFFF) == 0);
 537    vassert((maxoff & ~0xFFFF) == 0);
 538    return (minoff << 16) | maxoff;
 539 }
 540
 541 /* Supposing h has keys of the form generated by mk_key_GetPut and
 542    mk_key_GetIPutI, invalidate any key which overlaps (k_lo
 543    .. k_hi).
 544 */
 545 static void invalidateOverlaps ( HashHW* h, UInt k_lo, UInt k_hi )
 546 {
 547    Int  j;
 548    UInt e_lo, e_hi;
 549    vassert(k_lo <= k_hi);
 550    /* invalidate any env entries which in any way overlap (k_lo
 551       .. k_hi) */
 552    /* vex_printf("invalidate %d .. %d\n", k_lo, k_hi ); */
 553
 554    for (j = 0; j < h->used; j++) {
 555       if (!h->inuse[j])
 556          continue;
 557       e_lo = (((UInt)h->key[j]) >> 16) & 0xFFFF;
 558       e_hi = ((UInt)h->key[j]) & 0xFFFF;
 559       vassert(e_lo <= e_hi);
 560       if (e_hi < k_lo || k_hi < e_lo)
 561          continue; /* no overlap possible */
 562       else
 563          /* overlap; invalidate */
 564          h->inuse[j] = False;
 565    }
 566 }
 567
 568
 569 static void redundant_get_removal_BB ( IRSB* bb )
 570 {
 571    HashHW* env = newHHW();
 572    UInt    key = 0; /* keep gcc -O happy */
 573    Int     i, j;
 574    HWord   val;
 575
 576    for (i = 0; i < bb->stmts_used; i++) {
 577       IRStmt* st = bb->stmts[i];
 578
 579       if (st->tag == Ist_NoOp)
 580          continue;
 581
 582       /* Deal with Gets */
 583       if (st->tag == Ist_WrTmp
 584           && st->Ist.WrTmp.data->tag == Iex_Get) {
 585          /* st is 't = Get(...)'.  Look up in the environment and see
 586             if the Get can be replaced. */
 587          IRExpr* get = st->Ist.WrTmp.data;
 588          key = (HWord)mk_key_GetPut( get->Iex.Get.offset,
 589                                      get->Iex.Get.ty );
 590          if (lookupHHW(env, &val, (HWord)key)) {
 591             /* found it */
 592             /* Note, we could do better here.  If the types are
 593                different we don't do the substitution, since doing so
 594                could lead to invalidly-typed IR.  An improvement would
 595                be to stick in a reinterpret-style cast, although that
 596                would make maintaining flatness more difficult. */
 597             IRExpr* valE    = (IRExpr*)val;
 598             Bool    typesOK = toBool( typeOfIRExpr(bb->tyenv,valE)
 599                                       == st->Ist.WrTmp.data->Iex.Get.ty );
 600             if (typesOK && DEBUG_IROPT) {
 601                vex_printf("rGET: "); ppIRExpr(get);
 602                vex_printf("  ->  "); ppIRExpr(valE);
 603                vex_printf("\n");
 604             }
 605             if (typesOK)
 606                bb->stmts[i] = IRStmt_WrTmp(st->Ist.WrTmp.tmp, valE);
 607          } else {
 608             /* Not found, but at least we know that t and the Get(...)
 609                are now associated.  So add a binding to reflect that
 610                fact. */
 611             addToHHW( env, (HWord)key,
 612                            (HWord)(void*)(IRExpr_RdTmp(st->Ist.WrTmp.tmp)) );
 613          }
 614       }
 615
 616       /* Deal with Puts: invalidate any env entries overlapped by this
 617          Put */
 618       if (st->tag == Ist_Put || st->tag == Ist_PutI) {
 619          UInt k_lo, k_hi;
 620          if (st->tag == Ist_Put) {
 621             key = mk_key_GetPut( st->Ist.Put.offset,
 622                                  typeOfIRExpr(bb->tyenv,st->Ist.Put.data) );
 623          } else {
 624             vassert(st->tag == Ist_PutI);
 625             key = mk_key_GetIPutI( st->Ist.PutI.descr );
 626          }
 627
 628          k_lo = (key >> 16) & 0xFFFF;
 629          k_hi = key & 0xFFFF;
 630          invalidateOverlaps(env, k_lo, k_hi);
 631       }
 632       else
 633       if (st->tag == Ist_Dirty) {
 634          /* Deal with dirty helpers which write or modify guest state.
 635             Invalidate the entire env.  We could do a lot better
 636             here. */
 637          IRDirty* d      = st->Ist.Dirty.details;
 638          Bool     writes = False;
 639          for (j = 0; j < d->nFxState; j++) {
 640             if (d->fxState[j].fx == Ifx_Modify
 641                 || d->fxState[j].fx == Ifx_Write)
 642             writes = True;
 643          }
 644          if (writes) {
 645             /* dump the entire env (not clever, but correct ...) */
 646             for (j = 0; j < env->used; j++)
 647                env->inuse[j] = False;
 648             if (0) vex_printf("rGET: trash env due to dirty helper\n");
 649          }
 650       }
 651
 652       /* add this one to the env, if appropriate */
 653       if (st->tag == Ist_Put) {
 654          vassert(isIRAtom(st->Ist.Put.data));
 655          addToHHW( env, (HWord)key, (HWord)(st->Ist.Put.data));
 656       }
 657
 658    } /* for (i = 0; i < bb->stmts_used; i++) */
 659
 660 }
 661
 662
 663 /*---------------------------------------------------------------*/
 664 /*--- In-place removal of redundant PUTs                      ---*/
 665 /*---------------------------------------------------------------*/
 666
 667 /* Find any Get uses in st and invalidate any partially or fully
 668    overlapping ranges listed in env.  Due to the flattening phase, the
 669    only stmt kind we expect to find a Get on is IRStmt_WrTmp. */
 670
 671 static void handle_gets_Stmt (
 672                HashHW* env,
 673                IRStmt* st,
 674                Bool (*preciseMemExnsFn)(Int,Int)
 675             )
 676 {
 677    Int     j;
 678    UInt    key = 0; /* keep gcc -O happy */
 679    Bool    isGet;
 680    Bool    memRW = False;
 681    IRExpr* e;
 682
 683    switch (st->tag) {
 684
 685       /* This is the only interesting case.  Deal with Gets in the RHS
 686          expression. */
 687       case Ist_WrTmp:
 688          e = st->Ist.WrTmp.data;
 689          switch (e->tag) {
 690             case Iex_Get:
 691                isGet = True;
 692                key = mk_key_GetPut ( e->Iex.Get.offset, e->Iex.Get.ty );
 693                break;
 694             case Iex_GetI:
 695                isGet = True;
 696                key = mk_key_GetIPutI ( e->Iex.GetI.descr );
 697                break;
 698             case Iex_Load:
 699                isGet = False;
 700                memRW = True;
 701                break;
 702             default:
 703                isGet = False;
 704          }
 705          if (isGet) {
 706             UInt k_lo, k_hi;
 707             k_lo = (key >> 16) & 0xFFFF;
 708             k_hi = key & 0xFFFF;
 709             invalidateOverlaps(env, k_lo, k_hi);
 710          }
 711          break;
 712
 713       /* Be very conservative for dirty helper calls; dump the entire
 714          environment.  The helper might read guest state, in which
 715          case it needs to be flushed first.  Also, the helper might
 716          access guest memory, in which case all parts of the guest
 717          state requiring precise exceptions needs to be flushed.  The
 718          crude solution is just to flush everything; we could easily
 719          enough do a lot better if needed. */
 720       /* Probably also overly-conservative, but also dump everything
 721          if we hit a memory bus event (fence, lock, unlock).  Ditto
 722          AbiHints, CASs, LLs and SCs. */
 723       case Ist_AbiHint:
 724          vassert(isIRAtom(st->Ist.AbiHint.base));
 725          vassert(isIRAtom(st->Ist.AbiHint.nia));
 726          /* fall through */
 727       case Ist_MBE:
 728       case Ist_Dirty:
 729       case Ist_CAS:
 730       case Ist_LLSC:
 731          for (j = 0; j < env->used; j++)
 732             env->inuse[j] = False;
 733          break;
 734
 735       /* all other cases are boring. */
 736       case Ist_Store:
 737          vassert(isIRAtom(st->Ist.Store.addr));
 738          vassert(isIRAtom(st->Ist.Store.data));
 739          memRW = True;
 740          break;
 741
 742       case Ist_Exit:
 743          vassert(isIRAtom(st->Ist.Exit.guard));
 744          break;
 745
 746       case Ist_PutI:
 747          vassert(isIRAtom(st->Ist.PutI.ix));
 748          vassert(isIRAtom(st->Ist.PutI.data));
 749          break;
 750
 751       case Ist_NoOp:
 752       case Ist_IMark:
 753          break;
 754
 755       default:
 756          vex_printf("\n");
 757          ppIRStmt(st);
 758          vex_printf("\n");
 759          vpanic("handle_gets_Stmt");
 760    }
 761
 762    if (memRW) {
 763       /* This statement accesses memory.  So we need to dump all parts
 764          of the environment corresponding to guest state that may not
 765          be reordered with respect to memory references.  That means
 766          at least the stack pointer. */
 767       for (j = 0; j < env->used; j++) {
 768          if (!env->inuse[j])
 769             continue;
 770          if (vex_control.iropt_precise_memory_exns) {
 771             /* Precise exceptions required.  Flush all guest state. */
 772             env->inuse[j] = False;
 773          } else {
 774             /* Just flush the minimal amount required, as computed by
 775                preciseMemExnsFn. */
 776             HWord k_lo = (env->key[j] >> 16) & 0xFFFF;
 777             HWord k_hi = env->key[j] & 0xFFFF;
 778             if (preciseMemExnsFn( k_lo, k_hi ))
 779                env->inuse[j] = False;
 780          }
 781       }
 782    } /* if (memRW) */
 783
 784 }
 785
 786
 787 /* Scan backwards, building up a set of (min offset, max
 788    offset) pairs, indicating those parts of the guest state
 789    for which the next event is a write.
 790
 791    On seeing a conditional exit, empty the set.
 792
 793    On seeing 'Put (minoff,maxoff) = t or c', if (minoff,maxoff) is
 794    completely within the set, remove the Put.  Otherwise, add
 795    (minoff,maxoff) to the set.
 796
 797    On seeing 'Get (minoff,maxoff)', remove any part of the set
 798    overlapping (minoff,maxoff).  The same has to happen for any events
 799    which implicitly read parts of the guest state: dirty helper calls
 800    and loads/stores.
 801 */
 802
 803 static void redundant_put_removal_BB (
 804                IRSB* bb,
 805                Bool (*preciseMemExnsFn)(Int,Int)
 806             )
 807 {
 808    Int     i, j;
 809    Bool    isPut;
 810    IRStmt* st;
 811    UInt    key = 0; /* keep gcc -O happy */
 812
 813    HashHW* env = newHHW();
 814    for (i = bb->stmts_used-1; i >= 0; i--) {
 815       st = bb->stmts[i];
 816
 817       if (st->tag == Ist_NoOp)
 818          continue;
 819
 820       /* Deal with conditional exits. */
 821       if (st->tag == Ist_Exit) {
 822          /* Since control may not get beyond this point, we must empty
 823             out the set, since we can no longer claim that the next
 824             event for any part of the guest state is definitely a
 825             write. */
 826          vassert(isIRAtom(st->Ist.Exit.guard));
 827          for (j = 0; j < env->used; j++)
 828             env->inuse[j] = False;
 829          continue;
 830       }
 831
 832       /* Deal with Puts */
 833       switch (st->tag) {
 834          case Ist_Put:
 835             isPut = True;
 836             key = mk_key_GetPut( st->Ist.Put.offset,
 837                                  typeOfIRExpr(bb->tyenv,st->Ist.Put.data) );
 838             vassert(isIRAtom(st->Ist.Put.data));
 839             break;
 840          case Ist_PutI:
 841             isPut = True;
 842             key = mk_key_GetIPutI( st->Ist.PutI.descr );
 843             vassert(isIRAtom(st->Ist.PutI.ix));
 844             vassert(isIRAtom(st->Ist.PutI.data));
 845             break;
 846          default:
 847             isPut = False;
 848       }
 849       if (isPut && st->tag != Ist_PutI) {
 850          /* See if any single entry in env overlaps this Put.  This is
 851             simplistic in that the transformation is valid if, say, two
 852             or more entries in the env overlap this Put, but the use of
 853             lookupHHW will only find a single entry which exactly
 854             overlaps this Put.  This is suboptimal but safe. */
 855          if (lookupHHW(env, NULL, (HWord)key)) {
 856             /* This Put is redundant because a later one will overwrite
 857                it.  So NULL (nop) it out. */
 858             if (DEBUG_IROPT) {
 859                vex_printf("rPUT: "); ppIRStmt(st);
 860                vex_printf("\n");
 861             }
 862             bb->stmts[i] = IRStmt_NoOp();
 863          } else {
 864             /* We can't demonstrate that this Put is redundant, so add it
 865                to the running collection. */
 866             addToHHW(env, (HWord)key, 0);
 867          }
 868          continue;
 869       }
 870
 871       /* Deal with Gets.  These remove bits of the environment since
 872          appearance of a Get means that the next event for that slice
 873          of the guest state is no longer a write, but a read.  Also
 874          deals with implicit reads of guest state needed to maintain
 875          precise exceptions. */
 876       handle_gets_Stmt( env, st, preciseMemExnsFn );
 877    }
 878 }
 879
 880
 881 /*---------------------------------------------------------------*/
 882 /*--- Constant propagation and folding                        ---*/
 883 /*---------------------------------------------------------------*/
 884
 885 /* The env in this section is a map from IRTemp to IRExpr*,
 886    that is, an array indexed by IRTemp. */
 887
 888 /* Are both expressions simply the same IRTemp ? */
 889 static Bool sameIRTemps ( IRExpr* e1, IRExpr* e2 )
 890 {
 891    return toBool( e1->tag == Iex_RdTmp
 892                   && e2->tag == Iex_RdTmp
 893                   && e1->Iex.RdTmp.tmp == e2->Iex.RdTmp.tmp );
 894 }
 895
 896 static Bool sameIcoU32s ( IRExpr* e1, IRExpr* e2 )
 897 {
 898    return toBool( e1->tag == Iex_Const
 899                   && e2->tag == Iex_Const
 900                   && e1->Iex.Const.con->tag == Ico_U32
 901                   && e2->Iex.Const.con->tag == Ico_U32
 902                   && e1->Iex.Const.con->Ico.U32
 903                      == e2->Iex.Const.con->Ico.U32 );
 904 }
 905
 906 /* Are both expressions either the same IRTemp or IRConst-U32s ?  If
 907    in doubt, say No. */
 908 static Bool sameIRTempsOrIcoU32s ( IRExpr* e1, IRExpr* e2 )
 909 {
 910    switch (e1->tag) {
 911       case Iex_RdTmp:
 912          return sameIRTemps(e1, e2);
 913       case Iex_Const:
 914          return sameIcoU32s(e1, e2);
 915       default:
 916          return False;
 917    }
 918 }
 919
 920 static Bool notBool ( Bool b )
 921 {
 922    if (b == True) return False;
 923    if (b == False) return True;
 924    vpanic("notBool");
 925 }
 926
 927 /* Make a zero which has the same type as the result of the given
 928    primop. */
 929 static IRExpr* mkZeroOfPrimopResultType ( IROp op )
 930 {
 931    switch (op) {
 932       case Iop_Xor8:  return IRExpr_Const(IRConst_U8(0));
 933       case Iop_Xor16: return IRExpr_Const(IRConst_U16(0));
 934       case Iop_Sub32:
 935       case Iop_Xor32: return IRExpr_Const(IRConst_U32(0));
 936       case Iop_Sub64:
 937       case Iop_Xor64: return IRExpr_Const(IRConst_U64(0));
 938       case Iop_XorV128: return IRExpr_Const(IRConst_V128(0));
 939       default: vpanic("mkZeroOfPrimopResultType: bad primop");
 940    }
 941 }
 942
 943 /* Make a value containing all 1-bits, which has the same type as the
 944    result of the given primop. */
 945 static IRExpr* mkOnesOfPrimopResultType ( IROp op )
 946 {
 947    switch (op) {
 948       case Iop_CmpEQ64:
 949          return IRExpr_Const(IRConst_U1(toBool(1)));
 950       case Iop_CmpEQ8x8:
 951          return IRExpr_Const(IRConst_U64(0xFFFFFFFFFFFFFFFFULL));
 952       case Iop_CmpEQ8x16:
 953          return IRExpr_Const(IRConst_V128(0xFFFF));
 954       default:
 955          vpanic("mkOnesOfPrimopResultType: bad primop");
 956    }
 957 }
 958
 959 /* Helpers for folding Clz32/64. */
 960 static UInt fold_Clz64 ( ULong value )
 961 {
 962    UInt i;
 963    vassert(value != 0ULL); /* no defined semantics for arg==0 */
 964    for (i = 0; i < 64; ++i) {
 965       if (0ULL != (value & (((ULong)1) << (63 - i)))) return i;
 966    }
 967    vassert(0);
 968    /*NOTREACHED*/
 969    return 0;
 970 }
 971
 972 static UInt fold_Clz32 ( UInt value )
 973 {
 974    UInt i;
 975    vassert(value != 0); /* no defined semantics for arg==0 */
 976    for (i = 0; i < 32; ++i) {
 977       if (0 != (value & (((UInt)1) << (31 - i)))) return i;
 978    }
 979    vassert(0);
 980    /*NOTREACHED*/
 981    return 0;
 982 }
 983
 984
 985 static IRExpr* fold_Expr ( IRExpr* e )
 986 {
 987    Int     shift;
 988    IRExpr* e2 = e; /* e2 is the result of folding e, if possible */
 989
 990    /* UNARY ops */
 991    if (e->tag == Iex_Unop
 992        && e->Iex.Unop.arg->tag == Iex_Const) {
 993       switch (e->Iex.Unop.op) {
 994          case Iop_1Uto8:
 995             e2 = IRExpr_Const(IRConst_U8(toUChar(
 996                     e->Iex.Unop.arg->Iex.Const.con->Ico.U1
 997                     ? 1 : 0)));
 998             break;
 999          case Iop_1Uto32:
1000             e2 = IRExpr_Const(IRConst_U32(
1001                     e->Iex.Unop.arg->Iex.Const.con->Ico.U1
1002                     ? 1 : 0));
1003             break;
1004          case Iop_1Uto64:
1005             e2 = IRExpr_Const(IRConst_U64(
1006                     e->Iex.Unop.arg->Iex.Const.con->Ico.U1
1007                     ? 1 : 0));
1008             break;
1009
1010          case Iop_1Sto8:
1011             e2 = IRExpr_Const(IRConst_U8(toUChar(
1012                     e->Iex.Unop.arg->Iex.Const.con->Ico.U1
1013                     ? 0xFF : 0)));
1014             break;
1015          case Iop_1Sto16:
1016             e2 = IRExpr_Const(IRConst_U16(toUShort(
1017                     e->Iex.Unop.arg->Iex.Const.con->Ico.U1
1018                     ? 0xFFFF : 0)));
1019             break;
1020          case Iop_1Sto32:
1021             e2 = IRExpr_Const(IRConst_U32(
1022                     e->Iex.Unop.arg->Iex.Const.con->Ico.U1
1023                     ? 0xFFFFFFFF : 0));
1024             break;
1025          case Iop_1Sto64:
1026             e2 = IRExpr_Const(IRConst_U64(
1027                     e->Iex.Unop.arg->Iex.Const.con->Ico.U1
1028                     ? 0xFFFFFFFFFFFFFFFFULL : 0));
1029             break;
1030
1031          case Iop_8Sto32: {
1032             /* signed */ Int s32 = e->Iex.Unop.arg->Iex.Const.con->Ico.U8;
1033             s32 <<= 24;
1034             s32 >>= 24;
1035             e2 = IRExpr_Const(IRConst_U32((UInt)s32));
1036             break;
1037          }
1038          case Iop_16Sto32: {
1039             /* signed */ Int s32 = e->Iex.Unop.arg->Iex.Const.con->Ico.U16;
1040             s32 <<= 16;
1041             s32 >>= 16;
1042             e2 = IRExpr_Const(IRConst_U32( (UInt)s32) );
1043             break;
1044          }
1045          case Iop_8Uto64:
1046             e2 = IRExpr_Const(IRConst_U64(
1047                     0xFFULL & e->Iex.Unop.arg->Iex.Const.con->Ico.U8));
1048             break;
1049          case Iop_16Uto64:
1050             e2 = IRExpr_Const(IRConst_U64(
1051                     0xFFFFULL & e->Iex.Unop.arg->Iex.Const.con->Ico.U16));
1052             break;
1053          case Iop_8Uto32:
1054             e2 = IRExpr_Const(IRConst_U32(
1055                     0xFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U8));
1056             break;
1057          case Iop_8Sto16: {
1058             /* signed */ Short s16 = e->Iex.Unop.arg->Iex.Const.con->Ico.U8;
1059             s16 <<= 8;
1060             s16 >>= 8;
1061             e2 = IRExpr_Const(IRConst_U16( (UShort)s16) );
1062             break;
1063          }
1064          case Iop_8Uto16:
1065             e2 = IRExpr_Const(IRConst_U16(
1066                     0xFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U8));
1067             break;
1068          case Iop_16Uto32:
1069             e2 = IRExpr_Const(IRConst_U32(
1070                     0xFFFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U16));
1071             break;
1072          case Iop_32to16:
1073             e2 = IRExpr_Const(IRConst_U16(toUShort(
1074                     0xFFFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U32)));
1075             break;
1076          case Iop_32to8:
1077             e2 = IRExpr_Const(IRConst_U8(toUChar(
1078                     0xFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U32)));
1079             break;
1080          case Iop_32to1:
1081             e2 = IRExpr_Const(IRConst_U1(toBool(
1082                     1 == (1 & e->Iex.Unop.arg->Iex.Const.con->Ico.U32)
1083                  )));
1084             break;
1085          case Iop_64to1:
1086             e2 = IRExpr_Const(IRConst_U1(toBool(
1087                     1 == (1 & e->Iex.Unop.arg->Iex.Const.con->Ico.U64)
1088                  )));
1089             break;
1090
1091          case Iop_Not64:
1092             e2 = IRExpr_Const(IRConst_U64(
1093                     ~ (e->Iex.Unop.arg->Iex.Const.con->Ico.U64)));
1094             break;
1095          case Iop_Not32:
1096             e2 = IRExpr_Const(IRConst_U32(
1097                     ~ (e->Iex.Unop.arg->Iex.Const.con->Ico.U32)));
1098             break;
1099          case Iop_Not16:
1100             e2 = IRExpr_Const(IRConst_U16(toUShort(
1101                     ~ (e->Iex.Unop.arg->Iex.Const.con->Ico.U16))));
1102             break;
1103          case Iop_Not8:
1104             e2 = IRExpr_Const(IRConst_U8(toUChar(
1105                     ~ (e->Iex.Unop.arg->Iex.Const.con->Ico.U8))));
1106             break;
1107
1108          case Iop_Not1:
1109             e2 = IRExpr_Const(IRConst_U1(
1110                     notBool(e->Iex.Unop.arg->Iex.Const.con->Ico.U1)));
1111             break;
1112
1113          case Iop_64to8: {
1114             ULong w64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
1115             w64 &= 0xFFULL;
1116             e2 = IRExpr_Const(IRConst_U8( (UChar)w64 ));
1117             break;
1118          }
1119          case Iop_64to16: {
1120             ULong w64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
1121             w64 &= 0xFFFFULL;
1122             e2 = IRExpr_Const(IRConst_U16( (UShort)w64 ));
1123             break;
1124          }
1125          case Iop_64to32: {
1126             ULong w64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
1127             w64 &= 0x00000000FFFFFFFFULL;
1128             e2 = IRExpr_Const(IRConst_U32( (UInt)w64 ));
1129             break;
1130          }
1131          case Iop_64HIto32: {
1132             ULong w64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
1133             w64 >>= 32;
1134             e2 = IRExpr_Const(IRConst_U32( (UInt)w64 ));
1135             break;
1136          }
1137          case Iop_32Uto64:
1138             e2 = IRExpr_Const(IRConst_U64(
1139                     0xFFFFFFFFULL
1140                     & e->Iex.Unop.arg->Iex.Const.con->Ico.U32));
1141             break;
1142          case Iop_16Sto64: {
1143             /* signed */ Long s64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U16;
1144             s64 <<= 48;
1145             s64 >>= 48;
1146             e2 = IRExpr_Const(IRConst_U64((ULong)s64));
1147             break;
1148          }
1149          case Iop_32Sto64: {
1150             /* signed */ Long s64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U32;
1151             s64 <<= 32;
1152             s64 >>= 32;
1153             e2 = IRExpr_Const(IRConst_U64((ULong)s64));
1154             break;
1155          }
1156
1157          case Iop_16to8: {
1158             UShort w16 = e->Iex.Unop.arg->Iex.Const.con->Ico.U16;
1159             w16 &= 0xFF;
1160             e2 = IRExpr_Const(IRConst_U8( (UChar)w16 ));
1161             break;
1162          }
1163          case Iop_16HIto8: {
1164             UShort w16 = e->Iex.Unop.arg->Iex.Const.con->Ico.U16;
1165             w16 >>= 8;
1166             w16 &= 0xFF;
1167             e2 = IRExpr_Const(IRConst_U8( (UChar)w16 ));
1168             break;
1169          }
1170
1171          case Iop_CmpNEZ8:
1172             e2 = IRExpr_Const(IRConst_U1(toBool(
1173                     0 !=
1174                     (0xFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U8)
1175                  )));
1176             break;
1177          case Iop_CmpNEZ32:
1178             e2 = IRExpr_Const(IRConst_U1(toBool(
1179                     0 !=
1180                     (0xFFFFFFFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U32)
1181                  )));
1182             break;
1183          case Iop_CmpNEZ64:
1184             e2 = IRExpr_Const(IRConst_U1(toBool(
1185                     0ULL != e->Iex.Unop.arg->Iex.Const.con->Ico.U64
1186                  )));
1187             break;
1188
1189          case Iop_CmpwNEZ32: {
1190             UInt w32 = e->Iex.Unop.arg->Iex.Const.con->Ico.U32;
1191             if (w32 == 0)
1192                e2 = IRExpr_Const(IRConst_U32( 0 ));
1193             else
1194                e2 = IRExpr_Const(IRConst_U32( 0xFFFFFFFF ));
1195             break;
1196          }
1197          case Iop_CmpwNEZ64: {
1198             ULong w64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
1199             if (w64 == 0)
1200                e2 = IRExpr_Const(IRConst_U64( 0 ));
1201             else
1202                e2 = IRExpr_Const(IRConst_U64( 0xFFFFFFFFFFFFFFFFULL ));
1203             break;
1204          }
1205
1206          case Iop_Left32: {
1207             UInt u32 = e->Iex.Unop.arg->Iex.Const.con->Ico.U32;
1208             Int  s32 = (Int)(u32 & 0xFFFFFFFF);
1209             s32 = (s32 | (-s32));
1210             e2 = IRExpr_Const( IRConst_U32( (UInt)s32 ));
1211             break;
1212          }
1213
1214          case Iop_Left64: {
1215             ULong u64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
1216             Long  s64 = (Long)u64;
1217             s64 = (s64 | (-s64));
1218             e2 = IRExpr_Const( IRConst_U64( (ULong)s64 ));
1219             break;
1220          }
1221
1222          case Iop_Clz32: {
1223             UInt u32 = e->Iex.Unop.arg->Iex.Const.con->Ico.U32;
1224             if (u32 != 0)
1225                e2 = IRExpr_Const(IRConst_U32(fold_Clz32(u32)));
1226             break;
1227          }
1228          case Iop_Clz64: {
1229             ULong u64 = e->Iex.Unop.arg->Iex.Const.con->Ico.U64;
1230             if (u64 != 0ULL)
1231                e2 = IRExpr_Const(IRConst_U64(fold_Clz64(u64)));
1232             break;
1233          }
1234
1235          default:
1236             goto unhandled;
1237       }
1238    }
1239
1240    /* BINARY ops */
1241    if (e->tag == Iex_Binop) {
1242       if (e->Iex.Binop.arg1->tag == Iex_Const
1243           && e->Iex.Binop.arg2->tag == Iex_Const) {
1244          /* cases where both args are consts */
1245          switch (e->Iex.Binop.op) {
1246
1247             /* -- Or -- */
1248             case Iop_Or8:
1249                e2 = IRExpr_Const(IRConst_U8(toUChar(
1250                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
1251                         | e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
1252                break;
1253             case Iop_Or16:
1254                e2 = IRExpr_Const(IRConst_U16(toUShort(
1255                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U16
1256                         | e->Iex.Binop.arg2->Iex.Const.con->Ico.U16))));
1257                break;
1258             case Iop_Or32:
1259                e2 = IRExpr_Const(IRConst_U32(
1260                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1261                         | e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1262                break;
1263             case Iop_Or64:
1264                e2 = IRExpr_Const(IRConst_U64(
1265                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1266                         | e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1267                break;
1268
1269             /* -- Xor -- */
1270             case Iop_Xor8:
1271                e2 = IRExpr_Const(IRConst_U8(toUChar(
1272                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
1273                         ^ e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
1274                break;
1275             case Iop_Xor16:
1276                e2 = IRExpr_Const(IRConst_U16(toUShort(
1277                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U16
1278                         ^ e->Iex.Binop.arg2->Iex.Const.con->Ico.U16))));
1279                break;
1280             case Iop_Xor32:
1281                e2 = IRExpr_Const(IRConst_U32(
1282                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1283                         ^ e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1284                break;
1285             case Iop_Xor64:
1286                e2 = IRExpr_Const(IRConst_U64(
1287                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1288                         ^ e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1289                break;
1290
1291             /* -- And -- */
1292             case Iop_And8:
1293                e2 = IRExpr_Const(IRConst_U8(toUChar(
1294                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
1295                         & e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
1296                break;
1297             case Iop_And16:
1298                e2 = IRExpr_Const(IRConst_U16(toUShort(
1299                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U16
1300                         & e->Iex.Binop.arg2->Iex.Const.con->Ico.U16))));
1301                break;
1302             case Iop_And32:
1303                e2 = IRExpr_Const(IRConst_U32(
1304                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1305                         & e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1306                break;
1307             case Iop_And64:
1308                e2 = IRExpr_Const(IRConst_U64(
1309                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1310                         & e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1311                break;
1312
1313             /* -- Add -- */
1314             case Iop_Add8:
1315                e2 = IRExpr_Const(IRConst_U8(toUChar(
1316                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
1317                         + e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
1318                break;
1319             case Iop_Add32:
1320                e2 = IRExpr_Const(IRConst_U32(
1321                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1322                         + e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1323                break;
1324             case Iop_Add64:
1325                e2 = IRExpr_Const(IRConst_U64(
1326                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1327                         + e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1328                break;
1329
1330             /* -- Sub -- */
1331             case Iop_Sub8:
1332                e2 = IRExpr_Const(IRConst_U8(toUChar(
1333                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
1334                         - e->Iex.Binop.arg2->Iex.Const.con->Ico.U8))));
1335                break;
1336             case Iop_Sub32:
1337                e2 = IRExpr_Const(IRConst_U32(
1338                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1339                         - e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1340                break;
1341             case Iop_Sub64:
1342                e2 = IRExpr_Const(IRConst_U64(
1343                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1344                         - e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1345                break;
1346
1347             /* -- Max32U -- */
1348             case Iop_Max32U: {
1349                UInt u32a = e->Iex.Binop.arg1->Iex.Const.con->Ico.U32;
1350                UInt u32b = e->Iex.Binop.arg2->Iex.Const.con->Ico.U32;
1351                UInt res  = u32a > u32b ? u32a : u32b;
1352                e2 = IRExpr_Const(IRConst_U32(res));
1353                break;
1354             }
1355
1356             /* -- Mul -- */
1357             case Iop_Mul32:
1358                e2 = IRExpr_Const(IRConst_U32(
1359                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1360                         * e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
1361                break;
1362             case Iop_Mul64:
1363                e2 = IRExpr_Const(IRConst_U64(
1364                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1365                         * e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)));
1366                break;
1367
1368             case Iop_MullS32: {
1369                /* very paranoid */
1370                UInt  u32a = e->Iex.Binop.arg1->Iex.Const.con->Ico.U32;
1371                UInt  u32b = e->Iex.Binop.arg2->Iex.Const.con->Ico.U32;
1372                Int   s32a = (Int)u32a;
1373                Int   s32b = (Int)u32b;
1374                Long  s64a = (Long)s32a;
1375                Long  s64b = (Long)s32b;
1376                Long  sres = s64a * s64b;
1377                ULong ures = (ULong)sres;
1378                e2 = IRExpr_Const(IRConst_U64(ures));
1379                break;
1380             }
1381
1382             /* -- Shl -- */
1383             case Iop_Shl32:
1384                vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1385                shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1386                if (shift >= 0 && shift <= 31)
1387                   e2 = IRExpr_Const(IRConst_U32(
1388                           (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1389                            << shift)));
1390                break;
1391             case Iop_Shl64:
1392                vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1393                shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1394                if (shift >= 0 && shift <= 63)
1395                   e2 = IRExpr_Const(IRConst_U64(
1396                           (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1397                            << shift)));
1398                break;
1399
1400             /* -- Sar -- */
1401             case Iop_Sar32: {
1402                /* paranoid ... */
1403                /*signed*/ Int s32;
1404                vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1405                s32   = (Int)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32);
1406                shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1407                if (shift >= 0 && shift <= 31) {
1408                   s32 >>=/*signed*/ shift;
1409                   e2 = IRExpr_Const(IRConst_U32((UInt)s32));
1410                }
1411                break;
1412             }
1413             case Iop_Sar64: {
1414                /* paranoid ... */
1415                /*signed*/ Long s64;
1416                vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1417                s64   = (Long)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U64);
1418                shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1419                if (shift >= 0 && shift <= 63) {
1420                   s64 >>=/*signed*/ shift;
1421                   e2 = IRExpr_Const(IRConst_U64((ULong)s64));
1422                }
1423                break;
1424             }
1425
1426             /* -- Shr -- */
1427             case Iop_Shr32: {
1428                /* paranoid ... */
1429                /*unsigned*/ UInt u32;
1430                vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1431                u32   = (UInt)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32);
1432                shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1433                if (shift >= 0 && shift <= 31) {
1434                   u32 >>=/*unsigned*/ shift;
1435                   e2 = IRExpr_Const(IRConst_U32(u32));
1436                }
1437                break;
1438             }
1439             case Iop_Shr64: {
1440                /* paranoid ... */
1441                /*unsigned*/ ULong u64;
1442                vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
1443                u64   = (ULong)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U64);
1444                shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
1445                if (shift >= 0 && shift <= 63) {
1446                   u64 >>=/*unsigned*/ shift;
1447                   e2 = IRExpr_Const(IRConst_U64(u64));
1448                }
1449                break;
1450             }
1451
1452             /* -- CmpEQ -- */
1453             case Iop_CmpEQ32:
1454                e2 = IRExpr_Const(IRConst_U1(toBool(
1455                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1456                         == e->Iex.Binop.arg2->Iex.Const.con->Ico.U32))));
1457                break;
1458             case Iop_CmpEQ64:
1459                e2 = IRExpr_Const(IRConst_U1(toBool(
1460                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1461                         == e->Iex.Binop.arg2->Iex.Const.con->Ico.U64))));
1462                break;
1463
1464             /* -- CmpNE -- */
1465             case Iop_CmpNE8:
1466                e2 = IRExpr_Const(IRConst_U1(toBool(
1467                        ((0xFF & e->Iex.Binop.arg1->Iex.Const.con->Ico.U8)
1468                         != (0xFF & e->Iex.Binop.arg2->Iex.Const.con->Ico.U8)))));
1469                break;
1470             case Iop_CmpNE32:
1471                e2 = IRExpr_Const(IRConst_U1(toBool(
1472                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
1473                         != e->Iex.Binop.arg2->Iex.Const.con->Ico.U32))));
1474                break;
1475             case Iop_CmpNE64:
1476                e2 = IRExpr_Const(IRConst_U1(toBool(
1477                        (e->Iex.Binop.arg1->Iex.Const.con->Ico.U64
1478                         != e->Iex.Binop.arg2->Iex.Const.con->Ico.U64))));
1479                break;
1480
1481             /* -- CmpLEU -- */
1482             case Iop_CmpLE32U:
1483                e2 = IRExpr_Const(IRConst_U1(toBool(
1484                        ((UInt)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)
1485                         <= (UInt)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)))));
1486                break;
1487             case Iop_CmpLE64U:
1488                e2 = IRExpr_Const(IRConst_U1(toBool(
1489                        ((ULong)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U64)
1490                         <= (ULong)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)))));
1491                break;
1492
1493             /* -- CmpLES -- */
1494             case Iop_CmpLE32S:
1495                e2 = IRExpr_Const(IRConst_U1(toBool(
1496                        ((Int)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)
1497                         <= (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)))));
1498                break;
1499             case Iop_CmpLE64S:
1500                e2 = IRExpr_Const(IRConst_U1(toBool(
1501                        ((Long)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U64)
1502                         <= (Long)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)))));
1503                break;
1504
1505             /* -- CmpLTS -- */
1506             case Iop_CmpLT32S:
1507                e2 = IRExpr_Const(IRConst_U1(toBool(
1508                        ((Int)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)
1509                         < (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)))));
1510                break;
1511             case Iop_CmpLT64S:
1512                e2 = IRExpr_Const(IRConst_U1(toBool(
1513                        ((Long)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U64)
1514                         < (Long)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)))));
1515                break;
1516
1517             /* -- CmpLTU -- */
1518             case Iop_CmpLT32U:
1519                e2 = IRExpr_Const(IRConst_U1(toBool(
1520                        ((UInt)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)
1521                         < (UInt)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)))));
1522                break;
1523             case Iop_CmpLT64U:
1524                e2 = IRExpr_Const(IRConst_U1(toBool(
1525                        ((ULong)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U64)
1526                         < (ULong)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U64)))));
1527                break;
1528
1529             /* -- CmpORD -- */
1530             case Iop_CmpORD32S: {
1531                /* very paranoid */
1532                UInt  u32a = e->Iex.Binop.arg1->Iex.Const.con->Ico.U32;
1533                UInt  u32b = e->Iex.Binop.arg2->Iex.Const.con->Ico.U32;
1534                Int   s32a = (Int)u32a;
1535                Int   s32b = (Int)u32b;
1536                Int   r = 0x2; /* EQ */
1537                if (s32a < s32b) {
1538                   r = 0x8; /* LT */
1539                }
1540                else if (s32a > s32b) {
1541                   r = 0x4; /* GT */
1542                }
1543                e2 = IRExpr_Const(IRConst_U32(r));
1544                break;
1545             }
1546
1547             /* -- nHLto2n -- */
1548             case Iop_32HLto64:
1549                e2 = IRExpr_Const(IRConst_U64(
1550                        (((ULong)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)) << 32)
1551                        | ((ULong)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32))
1552                     ));
1553                break;
1554             case Iop_64HLto128:
1555                /* We can't fold this, because there is no way to
1556                   express he result in IR, but at least pretend to
1557                   handle it, so as to stop getting blasted with
1558                   no-rule-for-this-primop messages. */
1559                break;
1560
1561             default:
1562                goto unhandled;
1563          }
1564
1565       } else {
1566
1567          /* other cases (identities, etc) */
1568
1569          /* Shl64/Shr64(x,0) ==> x */
1570          if ((e->Iex.Binop.op == Iop_Shl64 || e->Iex.Binop.op == Iop_Shr64)
1571              && e->Iex.Binop.arg2->tag == Iex_Const
1572              && e->Iex.Binop.arg2->Iex.Const.con->Ico.U8 == 0) {
1573             e2 = e->Iex.Binop.arg1;
1574          } else
1575
1576          /* Shl32/Shr32(x,0) ==> x */
1577          if ((e->Iex.Binop.op == Iop_Shl32 || e->Iex.Binop.op == Iop_Shr32)
1578              && e->Iex.Binop.arg2->tag == Iex_Const
1579              && e->Iex.Binop.arg2->Iex.Const.con->Ico.U8 == 0) {
1580             e2 = e->Iex.Binop.arg1;
1581          } else
1582
1583          /* Or8(x,0) ==> x */
1584          if ((e->Iex.Binop.op == Iop_Or8)
1585              && e->Iex.Binop.arg2->tag == Iex_Const
1586              && e->Iex.Binop.arg2->Iex.Const.con->Ico.U8 == 0) {
1587             e2 = e->Iex.Binop.arg1;
1588          } else
1589
1590          /* Or16(x,0) ==> x */
1591          if ((e->Iex.Binop.op == Iop_Or16)
1592              && e->Iex.Binop.arg2->tag == Iex_Const
1593              && e->Iex.Binop.arg2->Iex.Const.con->Ico.U16 == 0) {
1594             e2 = e->Iex.Binop.arg1;
1595          } else
1596
1597          /* Or32/Add32/Max32U(x,0) ==> x */
1598          if ((e->Iex.Binop.op == Iop_Add32
1599               || e->Iex.Binop.op == Iop_Or32 || e->Iex.Binop.op == Iop_Max32U)
1600              && e->Iex.Binop.arg2->tag == Iex_Const
1601              && e->Iex.Binop.arg2->Iex.Const.con->Ico.U32 == 0) {
1602             e2 = e->Iex.Binop.arg1;
1603          } else
1604
1605          /* Add32(t,t) ==> t << 1.  Memcheck doesn't understand that
1606             x+x produces a defined least significant bit, and it seems
1607             simplest just to get rid of the problem by rewriting it
1608             out, since the opportunity to do so exists. */
1609          if (e->Iex.Binop.op == Iop_Add32
1610              && e->Iex.Binop.arg1->tag == Iex_RdTmp
1611              && e->Iex.Binop.arg2->tag == Iex_RdTmp
1612              && e->Iex.Binop.arg1->Iex.RdTmp.tmp
1613                 == e->Iex.Binop.arg2->Iex.RdTmp.tmp) {
1614             e2 = IRExpr_Binop(Iop_Shl32,
1615                               e->Iex.Binop.arg1,
1616                               IRExpr_Const(IRConst_U8(1)));
1617          } else
1618
1619          /* Add64(t,t) ==> t << 1;  rationale as for Add32(t,t) above. */
1620          if (e->Iex.Binop.op == Iop_Add64
1621              && e->Iex.Binop.arg1->tag == Iex_RdTmp
1622              && e->Iex.Binop.arg2->tag == Iex_RdTmp
1623              && e->Iex.Binop.arg1->Iex.RdTmp.tmp
1624                 == e->Iex.Binop.arg2->Iex.RdTmp.tmp) {
1625             e2 = IRExpr_Binop(Iop_Shl64,
1626                               e->Iex.Binop.arg1,
1627                               IRExpr_Const(IRConst_U8(1)));
1628          } else
1629
1630          /* Add8(t,t) ==> t << 1;  rationale as for Add32(t,t) above. */
1631          if (e->Iex.Binop.op == Iop_Add8
1632              && e->Iex.Binop.arg1->tag == Iex_RdTmp
1633              && e->Iex.Binop.arg2->tag == Iex_RdTmp
1634              && e->Iex.Binop.arg1->Iex.RdTmp.tmp
1635                 == e->Iex.Binop.arg2->Iex.RdTmp.tmp) {
1636             e2 = IRExpr_Binop(Iop_Shl8,
1637                               e->Iex.Binop.arg1,
1638                               IRExpr_Const(IRConst_U8(1)));
1639          } else
1640          /* NB no Add16(t,t) case yet as no known test case exists */
1641
1642          /* Or64/Add64(x,0) ==> x */
1643          if ((e->Iex.Binop.op == Iop_Add64 || e->Iex.Binop.op == Iop_Or64)
1644              && e->Iex.Binop.arg2->tag == Iex_Const
1645              && e->Iex.Binop.arg2->Iex.Const.con->Ico.U64 == 0) {
1646             e2 = e->Iex.Binop.arg1;
1647          } else
1648
1649          /* And32(x,0xFFFFFFFF) ==> x */
1650          if (e->Iex.Binop.op == Iop_And32
1651              && e->Iex.Binop.arg2->tag == Iex_Const
1652              && e->Iex.Binop.arg2->Iex.Const.con->Ico.U32 == 0xFFFFFFFF) {
1653             e2 = e->Iex.Binop.arg1;
1654          } else
1655
1656          /* And32(x,0) ==> 0 */
1657          if (e->Iex.Binop.op == Iop_And32
1658              && e->Iex.Binop.arg2->tag == Iex_Const
1659              && e->Iex.Binop.arg2->Iex.Const.con->Ico.U32 == 0) {
1660             e2 = IRExpr_Const(IRConst_U32(0));
1661          } else
1662
1663          /* And32/Shl32(0,x) ==> 0 */
1664          if ((e->Iex.Binop.op == Iop_And32 || e->Iex.Binop.op == Iop_Shl32)
1665              && e->Iex.Binop.arg1->tag == Iex_Const
1666              && e->Iex.Binop.arg1->Iex.Const.con->Ico.U32 == 0) {
1667             e2 = IRExpr_Const(IRConst_U32(0));
1668          } else
1669
1670          /* Or8(0,x) ==> x */
1671          if (e->Iex.Binop.op == Iop_Or8
1672              && e->Iex.Binop.arg1->tag == Iex_Const
1673              && e->Iex.Binop.arg1->Iex.Const.con->Ico.U8 == 0) {
1674             e2 = e->Iex.Binop.arg2;
1675          } else
1676
1677          /* Or32/Max32U(0,x) ==> x */
1678          if ((e->Iex.Binop.op == Iop_Or32 || e->Iex.Binop.op == Iop_Max32U)
1679              && e->Iex.Binop.arg1->tag == Iex_Const
1680              && e->Iex.Binop.arg1->Iex.Const.con->Ico.U32 == 0) {
1681             e2 = e->Iex.Binop.arg2;
1682          } else
1683
1684          /* Or64(0,x) ==> x */
1685          if (e->Iex.Binop.op == Iop_Or64
1686              && e->Iex.Binop.arg1->tag == Iex_Const
1687              && e->Iex.Binop.arg1->Iex.Const.con->Ico.U64 == 0) {
1688             e2 = e->Iex.Binop.arg2;
1689          } else
1690
1691          /* Or8/16/32/64/V128(t,t) ==> t, for some IRTemp t */
1692          /* And8/16/32/64(t,t) ==> t, for some IRTemp t */
1693          /* Max32U(t,t) ==> t, for some IRTemp t */
1694          switch (e->Iex.Binop.op) {
1695             case Iop_And64: case Iop_And32:
1696             case Iop_And16: case Iop_And8:
1697             case Iop_Or64: case Iop_Or32:
1698             case Iop_Or16: case Iop_Or8: case Iop_OrV128:
1699             case Iop_Max32U:
1700                if (sameIRTemps(e->Iex.Binop.arg1, e->Iex.Binop.arg2))
1701                   e2 = e->Iex.Binop.arg1;
1702                break;
1703             default:
1704                break;
1705          }
1706
1707          /* Xor8/16/32/64/V128(t,t) ==> 0, for some IRTemp t */
1708          /* Sub32/64(t,t) ==> 0, for some IRTemp t */
1709          switch (e->Iex.Binop.op) {
1710             case Iop_Xor64: case Iop_Xor32:
1711             case Iop_Xor16: case Iop_Xor8:
1712             case Iop_XorV128:
1713             case Iop_Sub64: case Iop_Sub32:
1714                if (sameIRTemps(e->Iex.Binop.arg1, e->Iex.Binop.arg2))
1715                   e2 = mkZeroOfPrimopResultType(e->Iex.Binop.op);
1716                break;
1717             default:
1718                break;
1719          }
1720
1721          switch (e->Iex.Binop.op) {
1722             case Iop_CmpEQ64:
1723             case Iop_CmpEQ8x8:
1724             case Iop_CmpEQ8x16:
1725                if (sameIRTemps(e->Iex.Binop.arg1, e->Iex.Binop.arg2))
1726                   e2 = mkOnesOfPrimopResultType(e->Iex.Binop.op);
1727                break;
1728             default:
1729                break;
1730          }
1731
1732       }
1733    }
1734
1735    /* Mux0X */
1736    if (e->tag == Iex_Mux0X) {
1737       /* is the discriminant is a constant? */
1738       if (e->Iex.Mux0X.cond->tag == Iex_Const) {
1739          Bool zero;
1740          /* assured us by the IR type rules */
1741          vassert(e->Iex.Mux0X.cond->Iex.Const.con->tag == Ico_U8);
1742          zero = toBool(0 == (0xFF & e->Iex.Mux0X.cond
1743                                      ->Iex.Const.con->Ico.U8));
1744          e2 = zero ? e->Iex.Mux0X.expr0 : e->Iex.Mux0X.exprX;
1745       }
1746       else
1747       /* are the arms identical? (pretty weedy test) */
1748       if (sameIRTempsOrIcoU32s(e->Iex.Mux0X.expr0,
1749                                e->Iex.Mux0X.exprX)) {
1750          e2 = e->Iex.Mux0X.expr0;
1751       }
1752    }
1753
1754    /* Show cases where we've found but not folded 'op(t,t)'. */
1755    if (0 && e == e2 && e->tag == Iex_Binop
1756        && sameIRTemps(e->Iex.Binop.arg1, e->Iex.Binop.arg2)) {
1757       vex_printf("IDENT: ");
1758       ppIRExpr(e); vex_printf("\n");
1759    }
1760
1761    /* Show the overall results of folding. */
1762    if (DEBUG_IROPT && e2 != e) {
1763       vex_printf("FOLD: ");
1764       ppIRExpr(e); vex_printf("  ->  ");
1765       ppIRExpr(e2); vex_printf("\n");
1766    }
1767
1768    return e2;
1769
1770  unhandled:
1771 #  if 0
1772    vex_printf("\n\n");
1773    ppIRExpr(e);
1774    vpanic("fold_Expr: no rule for the above");
1775 #  else
1776    if (vex_control.iropt_verbosity > 0) {
1777       vex_printf("vex iropt: fold_Expr: no rule for: ");
1778       ppIRExpr(e);
1779       vex_printf("\n");
1780    }
1781    return e2;
1782 #  endif
1783 }
1784
1785
1786 /* Apply the subst to a simple 1-level expression -- guaranteed to be
1787    1-level due to previous flattening pass. */
1788
1789 static IRExpr* subst_Expr ( IRExpr** env, IRExpr* ex )
1790 {
1791    switch (ex->tag) {
1792       case Iex_RdTmp:
1793          if (env[(Int)ex->Iex.RdTmp.tmp] != NULL) {
1794             return env[(Int)ex->Iex.RdTmp.tmp];
1795          } else {
1796             /* not bound in env */
1797             return ex;
1798          }
1799
1800       case Iex_Const:
1801       case Iex_Get:
1802          return ex;
1803
1804       case Iex_GetI:
1805          vassert(isIRAtom(ex->Iex.GetI.ix));
1806          return IRExpr_GetI(
1807             ex->Iex.GetI.descr,
1808             subst_Expr(env, ex->Iex.GetI.ix),
1809             ex->Iex.GetI.bias
1810          );
1811
1812       case Iex_Qop:
1813          vassert(isIRAtom(ex->Iex.Qop.arg1));
1814          vassert(isIRAtom(ex->Iex.Qop.arg2));
1815          vassert(isIRAtom(ex->Iex.Qop.arg3));
1816          vassert(isIRAtom(ex->Iex.Qop.arg4));
1817          return IRExpr_Qop(
1818                    ex->Iex.Qop.op,
1819                    subst_Expr(env, ex->Iex.Qop.arg1),
1820                    subst_Expr(env, ex->Iex.Qop.arg2),
1821                    subst_Expr(env, ex->Iex.Qop.arg3),
1822                    subst_Expr(env, ex->Iex.Qop.arg4)
1823                 );
1824
1825       case Iex_Triop:
1826          vassert(isIRAtom(ex->Iex.Triop.arg1));
1827          vassert(isIRAtom(ex->Iex.Triop.arg2));
1828          vassert(isIRAtom(ex->Iex.Triop.arg3));
1829          return IRExpr_Triop(
1830                    ex->Iex.Triop.op,
1831                    subst_Expr(env, ex->Iex.Triop.arg1),
1832                    subst_Expr(env, ex->Iex.Triop.arg2),
1833                    subst_Expr(env, ex->Iex.Triop.arg3)
1834                 );
1835
1836       case Iex_Binop:
1837          vassert(isIRAtom(ex->Iex.Binop.arg1));
1838          vassert(isIRAtom(ex->Iex.Binop.arg2));
1839          return IRExpr_Binop(
1840                    ex->Iex.Binop.op,
1841                    subst_Expr(env, ex->Iex.Binop.arg1),
1842                    subst_Expr(env, ex->Iex.Binop.arg2)
1843                 );
1844
1845       case Iex_Unop:
1846          vassert(isIRAtom(ex->Iex.Unop.arg));
1847          return IRExpr_Unop(
1848                    ex->Iex.Unop.op,
1849                    subst_Expr(env, ex->Iex.Unop.arg)
1850                 );
1851
1852       case Iex_Load:
1853          vassert(isIRAtom(ex->Iex.Load.addr));
1854          return IRExpr_Load(
1855                    ex->Iex.Load.end,
1856                    ex->Iex.Load.ty,
1857                    subst_Expr(env, ex->Iex.Load.addr)
1858                 );
1859
1860       case Iex_CCall: {
1861          Int      i;
1862          IRExpr** args2 = shallowCopyIRExprVec(ex->Iex.CCall.args);
1863          for (i = 0; args2[i]; i++) {
1864             vassert(isIRAtom(args2[i]));
1865             args2[i] = subst_Expr(env, args2[i]);
1866          }
1867          return IRExpr_CCall(
1868                    ex->Iex.CCall.cee,
1869                    ex->Iex.CCall.retty,
1870                    args2
1871                 );
1872       }
1873
1874       case Iex_Mux0X:
1875          vassert(isIRAtom(ex->Iex.Mux0X.cond));
1876          vassert(isIRAtom(ex->Iex.Mux0X.expr0));
1877          vassert(isIRAtom(ex->Iex.Mux0X.exprX));
1878          return IRExpr_Mux0X(
1879                    subst_Expr(env, ex->Iex.Mux0X.cond),
1880                    subst_Expr(env, ex->Iex.Mux0X.expr0),
1881                    subst_Expr(env, ex->Iex.Mux0X.exprX)
1882                 );
1883
1884       default:
1885          vex_printf("\n\n"); ppIRExpr(ex);
1886          vpanic("subst_Expr");
1887
1888    }
1889 }
1890
1891
1892 /* Apply the subst to stmt, then fold the result as much as possible.
1893    Much simplified due to stmt being previously flattened.  As a
1894    result of this, the stmt may wind up being turned into a no-op.
1895 */
1896 static IRStmt* subst_and_fold_Stmt ( IRExpr** env, IRStmt* st )
1897 {
1898 #  if 0
1899    vex_printf("\nsubst and fold stmt\n");
1900    ppIRStmt(st);
1901    vex_printf("\n");
1902 #  endif
1903
1904    switch (st->tag) {
1905       case Ist_AbiHint:
1906          vassert(isIRAtom(st->Ist.AbiHint.base));
1907          vassert(isIRAtom(st->Ist.AbiHint.nia));
1908          return IRStmt_AbiHint(
1909                    fold_Expr(subst_Expr(env, st->Ist.AbiHint.base)),
1910                    st->Ist.AbiHint.len,
1911                    fold_Expr(subst_Expr(env, st->Ist.AbiHint.nia))
1912                 );
1913       case Ist_Put:
1914          vassert(isIRAtom(st->Ist.Put.data));
1915          return IRStmt_Put(
1916                    st->Ist.Put.offset,
1917                    fold_Expr(subst_Expr(env, st->Ist.Put.data))
1918                 );
1919
1920       case Ist_PutI:
1921          vassert(isIRAtom(st->Ist.PutI.ix));
1922          vassert(isIRAtom(st->Ist.PutI.data));
1923          return IRStmt_PutI(
1924                    st->Ist.PutI.descr,
1925                    fold_Expr(subst_Expr(env, st->Ist.PutI.ix)),
1926                    st->Ist.PutI.bias,
1927                    fold_Expr(subst_Expr(env, st->Ist.PutI.data))
1928                 );
1929
1930       case Ist_WrTmp:
1931          /* This is the one place where an expr (st->Ist.WrTmp.data) is
1932             allowed to be more than just a constant or a tmp. */
1933          return IRStmt_WrTmp(
1934                    st->Ist.WrTmp.tmp,
1935                    fold_Expr(subst_Expr(env, st->Ist.WrTmp.data))
1936                 );
1937
1938       case Ist_Store:
1939          vassert(isIRAtom(st->Ist.Store.addr));
1940          vassert(isIRAtom(st->Ist.Store.data));
1941          return IRStmt_Store(
1942                    st->Ist.Store.end,
1943                    fold_Expr(subst_Expr(env, st->Ist.Store.addr)),
1944                    fold_Expr(subst_Expr(env, st->Ist.Store.data))
1945                 );
1946
1947       case Ist_CAS: {
1948          IRCAS *cas, *cas2;
1949          cas = st->Ist.CAS.details;
1950          vassert(isIRAtom(cas->addr));
1951          vassert(cas->expdHi == NULL || isIRAtom(cas->expdHi));
1952          vassert(isIRAtom(cas->expdLo));
1953          vassert(cas->dataHi == NULL || isIRAtom(cas->dataHi));
1954          vassert(isIRAtom(cas->dataLo));
1955          cas2 = mkIRCAS(
1956                    cas->oldHi, cas->oldLo, cas->end,
1957                    fold_Expr(subst_Expr(env, cas->addr)),
1958                    cas->expdHi ? fold_Expr(subst_Expr(env, cas->expdHi)) : NULL,
1959                    fold_Expr(subst_Expr(env, cas->expdLo)),
1960                    cas->dataHi ? fold_Expr(subst_Expr(env, cas->dataHi)) : NULL,
1961                    fold_Expr(subst_Expr(env, cas->dataLo))
1962                 );
1963          return IRStmt_CAS(cas2);
1964       }
1965
1966       case Ist_LLSC:
1967          vassert(isIRAtom(st->Ist.LLSC.addr));
1968          if (st->Ist.LLSC.storedata)
1969             vassert(isIRAtom(st->Ist.LLSC.storedata));
1970          return IRStmt_LLSC(
1971                    st->Ist.LLSC.end,
1972                    st->Ist.LLSC.result,
1973                    fold_Expr(subst_Expr(env, st->Ist.LLSC.addr)),
1974                    st->Ist.LLSC.storedata
1975                       ? fold_Expr(subst_Expr(env, st->Ist.LLSC.storedata))
1976                       : NULL
1977                 );
1978
1979       case Ist_Dirty: {
1980          Int     i;
1981          IRDirty *d, *d2;
1982          d = st->Ist.Dirty.details;
1983          d2 = emptyIRDirty();
1984          *d2 = *d;
1985          d2->args = shallowCopyIRExprVec(d2->args);
1986          if (d2->mFx != Ifx_None) {
1987             vassert(isIRAtom(d2->mAddr));
1988             d2->mAddr = fold_Expr(subst_Expr(env, d2->mAddr));
1989          }
1990          vassert(isIRAtom(d2->guard));
1991          d2->guard = fold_Expr(subst_Expr(env, d2->guard));
1992          for (i = 0; d2->args[i]; i++) {
1993             vassert(isIRAtom(d2->args[i]));
1994             d2->args[i] = fold_Expr(subst_Expr(env, d2->args[i]));
1995          }
1996          return IRStmt_Dirty(d2);
1997       }
1998
1999       case Ist_IMark:
2000          return IRStmt_IMark(st->Ist.IMark.addr, st->Ist.IMark.len);
2001
2002       case Ist_NoOp:
2003          return IRStmt_NoOp();
2004
2005       case Ist_MBE:
2006          return IRStmt_MBE(st->Ist.MBE.event);
2007
2008       case Ist_Exit: {
2009          IRExpr* fcond;
2010          vassert(isIRAtom(st->Ist.Exit.guard));
2011          fcond = fold_Expr(subst_Expr(env, st->Ist.Exit.guard));
2012          if (fcond->tag == Iex_Const) {
2013             /* Interesting.  The condition on this exit has folded down to
2014                a constant. */
2015             vassert(fcond->Iex.Const.con->tag == Ico_U1);
2016             vassert(fcond->Iex.Const.con->Ico.U1 == False
2017                     || fcond->Iex.Const.con->Ico.U1 == True);
2018             if (fcond->Iex.Const.con->Ico.U1 == False) {
2019                /* exit is never going to happen, so dump the statement. */
2020                return IRStmt_NoOp();
2021             } else {
2022                vassert(fcond->Iex.Const.con->Ico.U1 == True);
2023                /* Hmmm.  The exit has become unconditional.  Leave it
2024                   as it is for now, since we'd have to truncate the BB
2025                   at this point, which is tricky.  Such truncation is
2026                   done later by the dead-code elimination pass. */
2027                /* fall out into the reconstruct-the-exit code. */
2028                if (vex_control.iropt_verbosity > 0)
2029                   /* really a misuse of vex_control.iropt_verbosity */
2030                   vex_printf("vex iropt: IRStmt_Exit became unconditional\n");
2031             }
2032          }
2033          return IRStmt_Exit(fcond, st->Ist.Exit.jk, st->Ist.Exit.dst);
2034       }
2035
2036    default:
2037       vex_printf("\n"); ppIRStmt(st);
2038       vpanic("subst_and_fold_Stmt");
2039    }
2040 }
2041
2042
2043 IRSB* cprop_BB ( IRSB* in )
2044 {
2045    Int      i;
2046    IRSB*    out;
2047    IRStmt*  st2;
2048    Int      n_tmps = in->tyenv->types_used;
2049    IRExpr** env = LibVEX_Alloc(n_tmps * sizeof(IRExpr*));
2050
2051    out = emptyIRSB();
2052    out->tyenv = deepCopyIRTypeEnv( in->tyenv );
2053
2054    /* Set up the env with which travels forward.  This holds a
2055       substitution, mapping IRTemps to atoms, that is, IRExprs which
2056       are either IRTemps or IRConsts.  Thus, copy and constant
2057       propagation is done.  The environment is to be applied as we
2058       move along.  Keys are IRTemps.  Values are IRExpr*s.
2059    */
2060    for (i = 0; i < n_tmps; i++)
2061       env[i] = NULL;
2062
2063    /* For each original SSA-form stmt ... */
2064    for (i = 0; i < in->stmts_used; i++) {
2065
2066       /* First apply the substitution to the current stmt.  This
2067          propagates in any constants and tmp-tmp assignments
2068          accumulated prior to this point.  As part of the subst_Stmt
2069          call, also then fold any constant expressions resulting. */
2070
2071       st2 = in->stmts[i];
2072
2073       /* perhaps st2 is already a no-op? */
2074       if (st2->tag == Ist_NoOp) continue;
2075
2076       st2 = subst_and_fold_Stmt( env, st2 );
2077
2078       /* If the statement has been folded into a no-op, forget it. */
2079       if (st2->tag == Ist_NoOp) continue;
2080
2081       /* Now consider what the stmt looks like.  If it's of the form
2082          't = const' or 't1 = t2', add it to the running environment
2083          and not to the output BB.  Otherwise, add it to the output
2084          BB.  Note, we choose not to propagate const when const is an
2085          F64i, so that F64i literals can be CSE'd later.  This helps
2086          x86 floating point code generation. */
2087
2088       if (st2->tag == Ist_WrTmp
2089           && st2->Ist.WrTmp.data->tag == Iex_Const
2090           && st2->Ist.WrTmp.data->Iex.Const.con->tag != Ico_F64i) {
2091          /* 't = const' -- add to env.
2092              The pair (IRTemp, IRExpr*) is added. */
2093          env[(Int)(st2->Ist.WrTmp.tmp)] = st2->Ist.WrTmp.data;
2094       }
2095       else
2096       if (st2->tag == Ist_WrTmp && st2->Ist.WrTmp.data->tag == Iex_RdTmp) {
2097          /* 't1 = t2' -- add to env.
2098              The pair (IRTemp, IRExpr*) is added. */
2099          env[(Int)(st2->Ist.WrTmp.tmp)] = st2->Ist.WrTmp.data;
2100       }
2101       else {
2102          /* Not interesting, copy st2 into the output block. */
2103          addStmtToIRSB( out, st2 );
2104       }
2105    }
2106
2107    out->next     = subst_Expr( env, in->next );
2108    out->jumpkind = in->jumpkind;
2109    return out;
2110 }
2111
2112
2113 /*---------------------------------------------------------------*/
2114 /*--- Dead code (t = E) removal                               ---*/
2115 /*---------------------------------------------------------------*/
2116
2117 /* As a side effect, also removes all code following an unconditional
2118    side exit. */
2119
2120 /* The type of the HashHW map is: a map from IRTemp to nothing
2121    -- really just operating a set or IRTemps.
2122 */
2123
2124 inline
2125 static void addUses_Temp ( Bool* set, IRTemp tmp )
2126 {
2127    set[(Int)tmp] = True;
2128 }
2129
2130 static void addUses_Expr ( Bool* set, IRExpr* e )
2131 {
2132    Int i;
2133    switch (e->tag) {
2134       case Iex_GetI:
2135          addUses_Expr(set, e->Iex.GetI.ix);
2136          return;
2137       case Iex_Mux0X:
2138          addUses_Expr(set, e->Iex.Mux0X.cond);
2139          addUses_Expr(set, e->Iex.Mux0X.expr0);
2140          addUses_Expr(set, e->Iex.Mux0X.exprX);
2141          return;
2142       case Iex_CCall:
2143          for (i = 0; e->Iex.CCall.args[i]; i++)
2144             addUses_Expr(set, e->Iex.CCall.args[i]);
2145          return;
2146       case Iex_Load:
2147          addUses_Expr(set, e->Iex.Load.addr);
2148          return;
2149       case Iex_Qop:
2150          addUses_Expr(set, e->Iex.Qop.arg1);
2151          addUses_Expr(set, e->Iex.Qop.arg2);
2152          addUses_Expr(set, e->Iex.Qop.arg3);
2153          addUses_Expr(set, e->Iex.Qop.arg4);
2154          return;
2155       case Iex_Triop:
2156          addUses_Expr(set, e->Iex.Triop.arg1);
2157          addUses_Expr(set, e->Iex.Triop.arg2);
2158          addUses_Expr(set, e->Iex.Triop.arg3);
2159          return;
2160       case Iex_Binop:
2161          addUses_Expr(set, e->Iex.Binop.arg1);
2162          addUses_Expr(set, e->Iex.Binop.arg2);
2163          return;
2164       case Iex_Unop:
2165          addUses_Expr(set, e->Iex.Unop.arg);
2166          return;
2167       case Iex_RdTmp:
2168          addUses_Temp(set, e->Iex.RdTmp.tmp);
2169          return;
2170       case Iex_Const:
2171       case Iex_Get:
2172          return;
2173       default:
2174          vex_printf("\n");
2175          ppIRExpr(e);
2176          vpanic("addUses_Expr");
2177    }
2178 }
2179
2180 static void addUses_Stmt ( Bool* set, IRStmt* st )
2181 {
2182    Int      i;
2183    IRDirty* d;
2184    IRCAS*   cas;
2185    switch (st->tag) {
2186       case Ist_AbiHint:
2187          addUses_Expr(set, st->Ist.AbiHint.base);
2188          addUses_Expr(set, st->Ist.AbiHint.nia);
2189          return;
2190       case Ist_PutI:
2191          addUses_Expr(set, st->Ist.PutI.ix);
2192          addUses_Expr(set, st->Ist.PutI.data);
2193          return;
2194       case Ist_WrTmp:
2195          addUses_Expr(set, st->Ist.WrTmp.data);
2196          return;
2197       case Ist_Put:
2198          addUses_Expr(set, st->Ist.Put.data);
2199          return;
2200       case Ist_Store:
2201          addUses_Expr(set, st->Ist.Store.addr);
2202          addUses_Expr(set, st->Ist.Store.data);
2203          return;
2204       case Ist_CAS:
2205          cas = st->Ist.CAS.details;
2206          addUses_Expr(set, cas->addr);
2207          if (cas->expdHi)
2208             addUses_Expr(set, cas->expdHi);
2209          addUses_Expr(set, cas->expdLo);
2210          if (cas->dataHi)
2211             addUses_Expr(set, cas->dataHi);
2212          addUses_Expr(set, cas->dataLo);
2213          return;
2214       case Ist_LLSC:
2215          addUses_Expr(set, st->Ist.LLSC.addr);
2216          if (st->Ist.LLSC.storedata)
2217             addUses_Expr(set, st->Ist.LLSC.storedata);
2218          return;
2219       case Ist_Dirty:
2220          d = st->Ist.Dirty.details;
2221          if (d->mFx != Ifx_None)
2222             addUses_Expr(set, d->mAddr);
2223          addUses_Expr(set, d->guard);
2224          for (i = 0; d->args[i] != NULL; i++)
2225             addUses_Expr(set, d->args[i]);
2226          return;
2227       case Ist_NoOp:
2228       case Ist_IMark:
2229       case Ist_MBE:
2230          return;
2231       case Ist_Exit:
2232          addUses_Expr(set, st->Ist.Exit.guard);
2233          return;
2234       default:
2235          vex_printf("\n");
2236          ppIRStmt(st);
2237          vpanic("addUses_Stmt");
2238    }
2239 }
2240
2241
2242 /* Is this literally IRExpr_Const(IRConst_U1(False)) ? */
2243 static Bool isZeroU1 ( IRExpr* e )
2244 {
2245    return toBool( e->tag == Iex_Const
2246                   && e->Iex.Const.con->tag == Ico_U1
2247                   && e->Iex.Const.con->Ico.U1 == False );
2248 }
2249
2250 /* Is this literally IRExpr_Const(IRConst_U1(True)) ? */
2251 static Bool isOneU1 ( IRExpr* e )
2252 {
2253    return toBool( e->tag == Iex_Const
2254                   && e->Iex.Const.con->tag == Ico_U1
2255                   && e->Iex.Const.con->Ico.U1 == True );
2256 }
2257
2258
2259 /* Note, this destructively modifies the given IRSB. */
2260
2261 /* Scan backwards through statements, carrying a set of IRTemps which
2262    are known to be used after the current point.  On encountering 't =
2263    E', delete the binding if it is not used.  Otherwise, add any temp
2264    uses to the set and keep on moving backwards.
2265
2266    As an enhancement, the first (backwards) pass searches for IR exits
2267    with always-taken conditions and notes the location of the earliest
2268    one in the block.  If any such are found, a second pass copies the
2269    exit destination and jump kind to the bb-end.  Then, the exit and
2270    all statements following it are turned into no-ops.
2271 */
2272
2273 /* notstatic */ void do_deadcode_BB ( IRSB* bb )
2274 {
2275    Int     i, i_unconditional_exit;
2276    Int     n_tmps = bb->tyenv->types_used;
2277    Bool*   set = LibVEX_Alloc(n_tmps * sizeof(Bool));
2278    IRStmt* st;
2279
2280    for (i = 0; i < n_tmps; i++)
2281       set[i] = False;
2282
2283    /* start off by recording IRTemp uses in the next field. */
2284    addUses_Expr(set, bb->next);
2285
2286    /* First pass */
2287
2288    /* Work backwards through the stmts */
2289    i_unconditional_exit = -1;
2290    for (i = bb->stmts_used-1; i >= 0; i--) {
2291       st = bb->stmts[i];
2292       if (st->tag == Ist_NoOp)
2293          continue;
2294       /* take note of any unconditional exits */
2295       if (st->tag == Ist_Exit
2296           && isOneU1(st->Ist.Exit.guard))
2297          i_unconditional_exit = i;
2298       if (st->tag == Ist_WrTmp
2299           && set[(Int)(st->Ist.WrTmp.tmp)] == False) {
2300           /* it's an IRTemp which never got used.  Delete it. */
2301          if (DEBUG_IROPT) {
2302             vex_printf("DEAD: ");
2303             ppIRStmt(st);
2304             vex_printf("\n");
2305          }
2306          bb->stmts[i] = IRStmt_NoOp();
2307       }
2308       else
2309       if (st->tag == Ist_Dirty
2310           && st->Ist.Dirty.details->guard
2311           && isZeroU1(st->Ist.Dirty.details->guard)) {
2312          /* This is a dirty helper which will never get called.
2313             Delete it. */
2314          bb->stmts[i] = IRStmt_NoOp();
2315        }
2316        else {
2317          /* Note any IRTemp uses made by the current statement. */
2318          addUses_Stmt(set, st);
2319       }
2320    }
2321
2322    /* Optional second pass: if any unconditional exits were found,
2323       delete them and all following statements. */
2324
2325    if (i_unconditional_exit != -1) {
2326       if (0) vex_printf("ZAPPING ALL FORWARDS from %d\n",
2327                         i_unconditional_exit);
2328       vassert(i_unconditional_exit >= 0
2329               && i_unconditional_exit < bb->stmts_used);
2330       bb->next
2331          = IRExpr_Const( bb->stmts[i_unconditional_exit]->Ist.Exit.dst );
2332       bb->jumpkind
2333          = bb->stmts[i_unconditional_exit]->Ist.Exit.jk;
2334       for (i = i_unconditional_exit; i < bb->stmts_used; i++)
2335          bb->stmts[i] = IRStmt_NoOp();
2336    }
2337 }
2338
2339
2340 /*---------------------------------------------------------------*/
2341 /*--- Specialisation of helper function calls, in             ---*/
2342 /*--- collaboration with the front end                        ---*/
2343 /*---------------------------------------------------------------*/
2344
2345 static
2346 IRSB* spec_helpers_BB(
2347          IRSB* bb,
2348          IRExpr* (*specHelper) (HChar*, IRExpr**, IRStmt**, Int)
2349       )
2350 {
2351    Int     i;
2352    IRStmt* st;
2353    IRExpr* ex;
2354    Bool    any = False;
2355
2356    for (i = bb->stmts_used-1; i >= 0; i--) {
2357       st = bb->stmts[i];
2358
2359       if (st->tag != Ist_WrTmp
2360           || st->Ist.WrTmp.data->tag != Iex_CCall)
2361          continue;
2362
2363       ex = (*specHelper)( st->Ist.WrTmp.data->Iex.CCall.cee->name,
2364                           st->Ist.WrTmp.data->Iex.CCall.args,
2365                           &bb->stmts[0], i );
2366       if (!ex)
2367         /* the front end can't think of a suitable replacement */
2368         continue;
2369
2370       /* We got something better.  Install it in the bb. */
2371       any = True;
2372       bb->stmts[i]
2373          = IRStmt_WrTmp(st->Ist.WrTmp.tmp, ex);
2374
2375       if (0) {
2376          vex_printf("SPEC: ");
2377          ppIRExpr(st->Ist.WrTmp.data);
2378          vex_printf("  -->  ");
2379          ppIRExpr(ex);
2380          vex_printf("\n");
2381       }
2382    }
2383
2384    if (any)
2385       bb = flatten_BB(bb);
2386    return bb;
2387 }
2388
2389
2390 /*---------------------------------------------------------------*/
2391 /*--- Determination of guest state aliasing relationships     ---*/
2392 /*---------------------------------------------------------------*/
2393
2394 /* These are helper functions for CSE and GetI/PutI transformations.
2395
2396    Determine, to the extent possible, the relationship between two
2397    guest state accesses.  The possible outcomes are:
2398
2399    * Exact alias.  These two accesses denote precisely the same
2400      piece of the guest state.
2401
2402    * Definitely no alias.  These two accesses are guaranteed not to
2403      overlap any part of the guest state.
2404
2405    * Unknown -- if neither of the above can be established.
2406
2407    If in doubt, return Unknown.  */
2408
2409 typedef
2410    enum { ExactAlias, NoAlias, UnknownAlias }
2411    GSAliasing;
2412
2413
2414 /* Produces the alias relation between an indexed guest
2415    state access and a non-indexed access. */
2416
2417 static
2418 GSAliasing getAliasingRelation_IC ( IRRegArray* descr1, IRExpr* ix1,
2419                                     Int offset2, IRType ty2 )
2420 {
2421    UInt minoff1, maxoff1, minoff2, maxoff2;
2422
2423    getArrayBounds( descr1, &minoff1, &maxoff1 );
2424    minoff2 = offset2;
2425    maxoff2 = minoff2 + sizeofIRType(ty2) - 1;
2426
2427    if (maxoff1 < minoff2 || maxoff2 < minoff1)
2428       return NoAlias;
2429
2430    /* Could probably do better here if required.  For the moment
2431       however just claim not to know anything more. */
2432    return UnknownAlias;
2433 }
2434
2435
2436 /* Produces the alias relation between two indexed guest state
2437    accesses. */
2438
2439 static
2440 GSAliasing getAliasingRelation_II (
2441               IRRegArray* descr1, IRExpr* ix1, Int bias1,
2442               IRRegArray* descr2, IRExpr* ix2, Int bias2
2443            )
2444 {
2445    UInt minoff1, maxoff1, minoff2, maxoff2;
2446    Int  iters;
2447
2448    /* First try hard to show they don't alias. */
2449    getArrayBounds( descr1, &minoff1, &maxoff1 );
2450    getArrayBounds( descr2, &minoff2, &maxoff2 );
2451    if (maxoff1 < minoff2 || maxoff2 < minoff1)
2452       return NoAlias;
2453
2454    /* So the two arrays at least partially overlap.  To get any
2455       further we'll have to be sure that the descriptors are
2456       identical. */
2457    if (!eqIRRegArray(descr1, descr2))
2458       return UnknownAlias;
2459
2460    /* The descriptors are identical.  Now the only difference can be
2461       in the index expressions.  If they cannot be shown to be
2462       identical, we have to say we don't know what the aliasing
2463       relation will be.  Now, since the IR is flattened, the index
2464       expressions should be atoms -- either consts or tmps.  So that
2465       makes the comparison simple. */
2466    vassert(isIRAtom(ix1));
2467    vassert(isIRAtom(ix2));
2468    if (!eqIRAtom(ix1,ix2))
2469       return UnknownAlias;
2470
2471    /* Ok, the index expressions are identical.  So now the only way
2472       they can be different is in the bias.  Normalise this
2473       paranoidly, to reliably establish equality/non-equality. */
2474
2475    /* So now we know that the GetI and PutI index the same array
2476       with the same base.  Are the offsets the same, modulo the
2477       array size?  Do this paranoidly. */
2478    vassert(descr1->nElems == descr2->nElems);
2479    vassert(descr1->elemTy == descr2->elemTy);
2480    vassert(descr1->base   == descr2->base);
2481    iters = 0;
2482    while (bias1 < 0 || bias2 < 0) {
2483       bias1 += descr1->nElems;
2484       bias2 += descr1->nElems;
2485       iters++;
2486       if (iters > 10)
2487          vpanic("getAliasingRelation: iters");
2488    }
2489    vassert(bias1 >= 0 && bias2 >= 0);
2490    bias1 %= descr1->nElems;
2491    bias2 %= descr1->nElems;
2492    vassert(bias1 >= 0 && bias1 < descr1->nElems);
2493    vassert(bias2 >= 0 && bias2 < descr1->nElems);
2494
2495    /* Finally, biasP and biasG are normalised into the range
2496       0 .. descrP/G->nElems - 1.  And so we can establish
2497       equality/non-equality. */
2498
2499    return bias1==bias2 ? ExactAlias : NoAlias;
2500 }
2501
2502
2503 /*---------------------------------------------------------------*/
2504 /*--- Common Subexpression Elimination                        ---*/
2505 /*---------------------------------------------------------------*/
2506
2507 /* Expensive in time and space. */
2508
2509 /* Uses two environments:
2510    a IRTemp -> IRTemp mapping
2511    a mapping from AvailExpr* to IRTemp
2512 */
2513
2514 typedef
2515    struct {
2516       enum { Ut, Btt, Btc, Bct, Cf64i, Mttt, GetIt } tag;
2517       union {
2518          /* unop(tmp) */
2519          struct {
2520             IROp   op;
2521             IRTemp arg;
2522          } Ut;
2523          /* binop(tmp,tmp) */
2524          struct {
2525             IROp   op;
2526             IRTemp arg1;
2527             IRTemp arg2;
2528          } Btt;
2529          /* binop(tmp,const) */
2530          struct {
2531             IROp    op;
2532             IRTemp  arg1;
2533             IRConst con2;
2534          } Btc;
2535          /* binop(const,tmp) */
2536          struct {
2537             IROp    op;
2538             IRConst con1;
2539             IRTemp  arg2;
2540          } Bct;
2541          /* F64i-style const */
2542          struct {
2543             ULong f64i;
2544          } Cf64i;
2545          /* Mux0X(tmp,tmp,tmp) */
2546          struct {
2547             IRTemp co;
2548             IRTemp e0;
2549             IRTemp eX;
2550          } Mttt;
2551          /* GetI(descr,tmp,bias)*/
2552          struct {
2553             IRRegArray* descr;
2554             IRTemp      ix;
2555             Int         bias;
2556          } GetIt;
2557       } u;
2558    }
2559    AvailExpr;
2560
2561 static Bool eq_AvailExpr ( AvailExpr* a1, AvailExpr* a2 )
2562 {
2563    if (a1->tag != a2->tag)
2564       return False;
2565    switch (a1->tag) {
2566       case Ut:
2567          return toBool(
2568                 a1->u.Ut.op == a2->u.Ut.op
2569                 && a1->u.Ut.arg == a2->u.Ut.arg);
2570       case Btt:
2571          return toBool(
2572                 a1->u.Btt.op == a2->u.Btt.op
2573                 && a1->u.Btt.arg1 == a2->u.Btt.arg1
2574                 && a1->u.Btt.arg2 == a2->u.Btt.arg2);
2575       case Btc:
2576          return toBool(
2577                 a1->u.Btc.op == a2->u.Btc.op
2578                 && a1->u.Btc.arg1 == a2->u.Btc.arg1
2579                 && eqIRConst(&a1->u.Btc.con2, &a2->u.Btc.con2));
2580       case Bct:
2581          return toBool(
2582                 a1->u.Bct.op == a2->u.Bct.op
2583                 && a1->u.Bct.arg2 == a2->u.Bct.arg2
2584                 && eqIRConst(&a1->u.Bct.con1, &a2->u.Bct.con1));
2585       case Cf64i:
2586          return toBool(a1->u.Cf64i.f64i == a2->u.Cf64i.f64i);
2587       case Mttt:
2588          return toBool(a1->u.Mttt.co == a2->u.Mttt.co
2589                        && a1->u.Mttt.e0 == a2->u.Mttt.e0
2590                        && a1->u.Mttt.eX == a2->u.Mttt.eX);
2591       case GetIt:
2592          return toBool(eqIRRegArray(a1->u.GetIt.descr, a2->u.GetIt.descr)
2593                        && a1->u.GetIt.ix == a2->u.GetIt.ix
2594                        && a1->u.GetIt.bias == a2->u.GetIt.bias);
2595       default: vpanic("eq_AvailExpr");
2596    }
2597 }
2598
2599 static IRExpr* availExpr_to_IRExpr ( AvailExpr* ae )
2600 {
2601    IRConst* con;
2602    switch (ae->tag) {
2603       case Ut:
2604          return IRExpr_Unop( ae->u.Ut.op, IRExpr_RdTmp(ae->u.Ut.arg) );
2605       case Btt:
2606          return IRExpr_Binop( ae->u.Btt.op,
2607                               IRExpr_RdTmp(ae->u.Btt.arg1),
2608                               IRExpr_RdTmp(ae->u.Btt.arg2) );
2609       case Btc:
2610          con = LibVEX_Alloc(sizeof(IRConst));
2611          *con = ae->u.Btc.con2;
2612          return IRExpr_Binop( ae->u.Btc.op,
2613                               IRExpr_RdTmp(ae->u.Btc.arg1),
2614                               IRExpr_Const(con) );
2615       case Bct:
2616          con = LibVEX_Alloc(sizeof(IRConst));
2617          *con = ae->u.Bct.con1;
2618          return IRExpr_Binop( ae->u.Bct.op,
2619                               IRExpr_Const(con),
2620                               IRExpr_RdTmp(ae->u.Bct.arg2) );
2621       case Cf64i:
2622          return IRExpr_Const(IRConst_F64i(ae->u.Cf64i.f64i));
2623       case Mttt:
2624          return IRExpr_Mux0X(IRExpr_RdTmp(ae->u.Mttt.co),
2625                              IRExpr_RdTmp(ae->u.Mttt.e0),
2626                              IRExpr_RdTmp(ae->u.Mttt.eX));
2627       case GetIt:
2628          return IRExpr_GetI(ae->u.GetIt.descr,
2629                             IRExpr_RdTmp(ae->u.GetIt.ix),
2630                             ae->u.GetIt.bias);
2631       default:
2632          vpanic("availExpr_to_IRExpr");
2633    }
2634 }
2635
2636 inline
2637 static IRTemp subst_AvailExpr_Temp ( HashHW* env, IRTemp tmp )
2638 {
2639    HWord res;
2640    /* env :: IRTemp -> IRTemp */
2641    if (lookupHHW( env, &res, (HWord)tmp ))
2642       return (IRTemp)res;
2643    else
2644       return tmp;
2645 }
2646
2647 static void subst_AvailExpr ( HashHW* env, AvailExpr* ae )
2648 {
2649    /* env :: IRTemp -> IRTemp */
2650    switch (ae->tag) {
2651       case Ut:
2652          ae->u.Ut.arg = subst_AvailExpr_Temp( env, ae->u.Ut.arg );
2653          break;
2654       case Btt:
2655          ae->u.Btt.arg1 = subst_AvailExpr_Temp( env, ae->u.Btt.arg1 );
2656          ae->u.Btt.arg2 = subst_AvailExpr_Temp( env, ae->u.Btt.arg2 );
2657          break;
2658       case Btc:
2659          ae->u.Btc.arg1 = subst_AvailExpr_Temp( env, ae->u.Btc.arg1 );
2660          break;
2661       case Bct:
2662          ae->u.Bct.arg2 = subst_AvailExpr_Temp( env, ae->u.Bct.arg2 );
2663          break;
2664       case Cf64i:
2665          break;
2666       case Mttt:
2667          ae->u.Mttt.co = subst_AvailExpr_Temp( env, ae->u.Mttt.co );
2668          ae->u.Mttt.e0 = subst_AvailExpr_Temp( env, ae->u.Mttt.e0 );
2669          ae->u.Mttt.eX = subst_AvailExpr_Temp( env, ae->u.Mttt.eX );
2670          break;
2671       case GetIt:
2672          ae->u.GetIt.ix = subst_AvailExpr_Temp( env, ae->u.GetIt.ix );
2673          break;
2674       default:
2675          vpanic("subst_AvailExpr");
2676    }
2677 }
2678
2679 static AvailExpr* irExpr_to_AvailExpr ( IRExpr* e )
2680 {
2681    AvailExpr* ae;
2682
2683    if (e->tag == Iex_Unop
2684        && e->Iex.Unop.arg->tag == Iex_RdTmp) {
2685       ae = LibVEX_Alloc(sizeof(AvailExpr));
2686       ae->tag      = Ut;
2687       ae->u.Ut.op  = e->Iex.Unop.op;
2688       ae->u.Ut.arg = e->Iex.Unop.arg->Iex.RdTmp.tmp;
2689       return ae;
2690    }
2691
2692    if (e->tag == Iex_Binop
2693        && e->Iex.Binop.arg1->tag == Iex_RdTmp
2694        && e->Iex.Binop.arg2->tag == Iex_RdTmp) {
2695       ae = LibVEX_Alloc(sizeof(AvailExpr));
2696       ae->tag        = Btt;
2697       ae->u.Btt.op   = e->Iex.Binop.op;
2698       ae->u.Btt.arg1 = e->Iex.Binop.arg1->Iex.RdTmp.tmp;
2699       ae->u.Btt.arg2 = e->Iex.Binop.arg2->Iex.RdTmp.tmp;
2700       return ae;
2701    }
2702
2703    if (e->tag == Iex_Binop
2704       && e->Iex.Binop.arg1->tag == Iex_RdTmp
2705       && e->Iex.Binop.arg2->tag == Iex_Const) {
2706       ae = LibVEX_Alloc(sizeof(AvailExpr));
2707       ae->tag        = Btc;
2708       ae->u.Btc.op   = e->Iex.Binop.op;
2709       ae->u.Btc.arg1 = e->Iex.Binop.arg1->Iex.RdTmp.tmp;
2710       ae->u.Btc.con2 = *(e->Iex.Binop.arg2->Iex.Const.con);
2711       return ae;
2712    }
2713
2714    if (e->tag == Iex_Binop
2715       && e->Iex.Binop.arg1->tag == Iex_Const
2716       && e->Iex.Binop.arg2->tag == Iex_RdTmp) {
2717       ae = LibVEX_Alloc(sizeof(AvailExpr));
2718       ae->tag        = Bct;
2719       ae->u.Bct.op   = e->Iex.Binop.op;
2720       ae->u.Bct.arg2 = e->Iex.Binop.arg2->Iex.RdTmp.tmp;
2721       ae->u.Bct.con1 = *(e->Iex.Binop.arg1->Iex.Const.con);
2722       return ae;
2723    }
2724
2725    if (e->tag == Iex_Const
2726        && e->Iex.Const.con->tag == Ico_F64i) {
2727       ae = LibVEX_Alloc(sizeof(AvailExpr));
2728       ae->tag          = Cf64i;
2729       ae->u.Cf64i.f64i = e->Iex.Const.con->Ico.F64i;
2730       return ae;
2731    }
2732
2733    if (e->tag == Iex_Mux0X
2734        && e->Iex.Mux0X.cond->tag == Iex_RdTmp
2735        && e->Iex.Mux0X.expr0->tag == Iex_RdTmp
2736        && e->Iex.Mux0X.exprX->tag == Iex_RdTmp) {
2737       ae = LibVEX_Alloc(sizeof(AvailExpr));
2738       ae->tag       = Mttt;
2739       ae->u.Mttt.co = e->Iex.Mux0X.cond->Iex.RdTmp.tmp;
2740       ae->u.Mttt.e0 = e->Iex.Mux0X.expr0->Iex.RdTmp.tmp;
2741       ae->u.Mttt.eX = e->Iex.Mux0X.exprX->Iex.RdTmp.tmp;
2742       return ae;
2743    }
2744
2745    if (e->tag == Iex_GetI
2746        && e->Iex.GetI.ix->tag == Iex_RdTmp) {
2747       ae = LibVEX_Alloc(sizeof(AvailExpr));
2748       ae->tag           = GetIt;
2749       ae->u.GetIt.descr = e->Iex.GetI.descr;
2750       ae->u.GetIt.ix    = e->Iex.GetI.ix->Iex.RdTmp.tmp;
2751       ae->u.GetIt.bias  = e->Iex.GetI.bias;
2752       return ae;
2753    }
2754
2755    return NULL;
2756 }
2757
2758
2759 /* The BB is modified in-place.  Returns True if any changes were
2760    made. */
2761
2762 static Bool do_cse_BB ( IRSB* bb )
2763 {
2764    Int        i, j, paranoia;
2765    IRTemp     t, q;
2766    IRStmt*    st;
2767    AvailExpr* eprime;
2768    AvailExpr* ae;
2769    Bool       invalidate;
2770    Bool       anyDone = False;
2771
2772    HashHW* tenv = newHHW(); /* :: IRTemp -> IRTemp */
2773    HashHW* aenv = newHHW(); /* :: AvailExpr* -> IRTemp */
2774
2775    vassert(sizeof(IRTemp) <= sizeof(HWord));
2776
2777    if (0) { ppIRSB(bb); vex_printf("\n\n"); }
2778
2779    /* Iterate forwards over the stmts.
2780       On seeing "t = E", where E is one of the 5 AvailExpr forms:
2781          let E' = apply tenv substitution to E
2782          search aenv for E'
2783             if a mapping E' -> q is found,
2784                replace this stmt by "t = q"
2785                and add binding t -> q to tenv
2786             else
2787                add binding E' -> t to aenv
2788                replace this stmt by "t = E'"
2789
2790       Other statements are only interesting to the extent that they
2791       might invalidate some of the expressions in aenv.  So there is
2792       an invalidate-bindings check for each statement seen.
2793    */
2794    for (i = 0; i < bb->stmts_used; i++) {
2795       st = bb->stmts[i];
2796
2797       /* ------ BEGIN invalidate aenv bindings ------ */
2798       /* This is critical: remove from aenv any E' -> .. bindings
2799          which might be invalidated by this statement.  The only
2800          vulnerable kind of bindings are the GetI kind.
2801             Dirty call - dump (paranoia level -> 2)
2802             Store      - dump (ditto)
2803             Put, PutI  - dump unless no-overlap is proven (.. -> 1)
2804          Uses getAliasingRelation_IC and getAliasingRelation_II
2805          to do the no-overlap assessments needed for Put/PutI.
2806       */
2807       switch (st->tag) {
2808          case Ist_Dirty: case Ist_Store: case Ist_MBE:
2809          case Ist_CAS: case Ist_LLSC:
2810             paranoia = 2; break;
2811          case Ist_Put: case Ist_PutI:
2812             paranoia = 1; break;
2813          case Ist_NoOp: case Ist_IMark: case Ist_AbiHint:
2814          case Ist_WrTmp: case Ist_Exit:
2815             paranoia = 0; break;
2816          default:
2817             vpanic("do_cse_BB(1)");
2818       }
2819
2820       if (paranoia > 0) {
2821          for (j = 0; j < aenv->used; j++) {
2822             if (!aenv->inuse[j])
2823                continue;
2824             ae = (AvailExpr*)aenv->key[j];
2825             if (ae->tag != GetIt)
2826                continue;
2827             invalidate = False;
2828             if (paranoia >= 2) {
2829                invalidate = True;
2830             } else {
2831                vassert(paranoia == 1);
2832                if (st->tag == Ist_Put) {
2833                   if (getAliasingRelation_IC(
2834                          ae->u.GetIt.descr,
2835                          IRExpr_RdTmp(ae->u.GetIt.ix),
2836                          st->Ist.Put.offset,
2837                          typeOfIRExpr(bb->tyenv,st->Ist.Put.data)
2838                       ) != NoAlias)
2839                      invalidate = True;
2840                }
2841                else
2842                if (st->tag == Ist_PutI) {
2843                   if (getAliasingRelation_II(
2844                          ae->u.GetIt.descr,
2845                          IRExpr_RdTmp(ae->u.GetIt.ix),
2846                          ae->u.GetIt.bias,
2847                          st->Ist.PutI.descr,
2848                          st->Ist.PutI.ix,
2849                          st->Ist.PutI.bias
2850                       ) != NoAlias)
2851                      invalidate = True;
2852                }
2853                else
2854                   vpanic("do_cse_BB(2)");
2855             }
2856
2857             if (invalidate) {
2858                aenv->inuse[j] = False;
2859                aenv->key[j]   = (HWord)NULL;  /* be sure */
2860             }
2861          } /* for j */
2862       } /* paranoia > 0 */
2863
2864       /* ------ ENV invalidate aenv bindings ------ */
2865
2866       /* ignore not-interestings */
2867       if (st->tag != Ist_WrTmp)
2868          continue;
2869
2870       t = st->Ist.WrTmp.tmp;
2871       eprime = irExpr_to_AvailExpr(st->Ist.WrTmp.data);
2872       /* ignore if not of AvailExpr form */
2873       if (!eprime)
2874          continue;
2875
2876       /* vex_printf("considering: " ); ppIRStmt(st); vex_printf("\n"); */
2877
2878       /* apply tenv */
2879       subst_AvailExpr( tenv, eprime );
2880
2881       /* search aenv for eprime, unfortunately the hard way */
2882       for (j = 0; j < aenv->used; j++)
2883          if (aenv->inuse[j] && eq_AvailExpr(eprime, (AvailExpr*)aenv->key[j]))
2884             break;
2885
2886       if (j < aenv->used) {
2887          /* A binding E' -> q was found.  Replace stmt by "t = q" and
2888             note the t->q binding in tenv. */
2889          /* (this is the core of the CSE action) */
2890          q = (IRTemp)aenv->val[j];
2891          bb->stmts[i] = IRStmt_WrTmp( t, IRExpr_RdTmp(q) );
2892          addToHHW( tenv, (HWord)t, (HWord)q );
2893          anyDone = True;
2894       } else {
2895          /* No binding was found, so instead we add E' -> t to our
2896             collection of available expressions, replace this stmt
2897             with "t = E'", and move on. */
2898          bb->stmts[i] = IRStmt_WrTmp( t, availExpr_to_IRExpr(eprime) );
2899          addToHHW( aenv, (HWord)eprime, (HWord)t );
2900       }
2901    }
2902
2903    /*
2904    ppIRSB(bb);
2905    sanityCheckIRSB(bb, Ity_I32);
2906    vex_printf("\n\n");
2907    */
2908    return anyDone;
2909 }
2910
2911
2912 /*---------------------------------------------------------------*/
2913 /*--- Add32/Sub32 chain collapsing                            ---*/
2914 /*---------------------------------------------------------------*/
2915
2916 /* ----- Helper functions for Add32/Sub32 chain collapsing ----- */
2917
2918 /* Is this expression "Add32(tmp,const)" or "Sub32(tmp,const)" ?  If
2919    yes, set *tmp and *i32 appropriately.  *i32 is set as if the
2920    root node is Add32, not Sub32. */
2921
2922 static Bool isAdd32OrSub32 ( IRExpr* e, IRTemp* tmp, Int* i32 )
2923 {
2924    if (e->tag != Iex_Binop)
2925       return False;
2926    if (e->Iex.Binop.op != Iop_Add32 && e->Iex.Binop.op != Iop_Sub32)
2927       return False;
2928    if (e->Iex.Binop.arg1->tag != Iex_RdTmp)
2929       return False;
2930    if (e->Iex.Binop.arg2->tag != Iex_Const)
2931       return False;
2932    *tmp = e->Iex.Binop.arg1->Iex.RdTmp.tmp;
2933    *i32 = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32);
2934    if (e->Iex.Binop.op == Iop_Sub32)
2935       *i32 = -*i32;
2936    return True;
2937 }
2938
2939
2940 /* Figure out if tmp can be expressed as tmp2 +32 const, for some
2941    other tmp2.  Scan backwards from the specified start point -- an
2942    optimisation. */
2943
2944 static Bool collapseChain ( IRSB* bb, Int startHere,
2945                             IRTemp tmp,
2946                             IRTemp* tmp2, Int* i32 )
2947 {
2948    Int     j, ii;
2949    IRTemp  vv;
2950    IRStmt* st;
2951    IRExpr* e;
2952
2953    /* the (var, con) pair contain the current 'representation' for
2954       'tmp'.  We start with 'tmp + 0'.  */
2955    IRTemp var = tmp;
2956    Int    con = 0;
2957
2958    /* Scan backwards to see if tmp can be replaced by some other tmp
2959      +/- a constant. */
2960    for (j = startHere; j >= 0; j--) {
2961       st = bb->stmts[j];
2962       if (st->tag != Ist_WrTmp)
2963          continue;
2964       if (st->Ist.WrTmp.tmp != var)
2965          continue;
2966       e = st->Ist.WrTmp.data;
2967       if (!isAdd32OrSub32(e, &vv, &ii))
2968          break;
2969       var = vv;
2970       con += ii;
2971    }
2972    if (j == -1)
2973       /* no earlier binding for var .. ill-formed IR */
2974       vpanic("collapseChain");
2975
2976    /* so, did we find anything interesting? */
2977    if (var == tmp)
2978       return False; /* no .. */
2979
2980    *tmp2 = var;
2981    *i32  = con;
2982    return True;
2983 }
2984
2985
2986 /* ------- Main function for Add32/Sub32 chain collapsing ------ */
2987
2988 static void collapse_AddSub_chains_BB ( IRSB* bb )
2989 {
2990    IRStmt *st;
2991    IRTemp var, var2;
2992    Int    i, con, con2;
2993
2994    for (i = bb->stmts_used-1; i >= 0; i--) {
2995       st = bb->stmts[i];
2996       if (st->tag == Ist_NoOp)
2997          continue;
2998
2999       /* Try to collapse 't1 = Add32/Sub32(t2, con)'. */
3000
3001       if (st->tag == Ist_WrTmp
3002           && isAdd32OrSub32(st->Ist.WrTmp.data, &var, &con)) {
3003
3004          /* So e1 is of the form Add32(var,con) or Sub32(var,-con).
3005             Find out if var can be expressed as var2 + con2. */
3006          if (collapseChain(bb, i-1, var, &var2, &con2)) {
3007             if (DEBUG_IROPT) {
3008                vex_printf("replacing1 ");
3009                ppIRStmt(st);
3010                vex_printf(" with ");
3011             }
3012             con2 += con;
3013             bb->stmts[i]
3014                = IRStmt_WrTmp(
3015                     st->Ist.WrTmp.tmp,
3016                     (con2 >= 0)
3017                       ? IRExpr_Binop(Iop_Add32,
3018                                      IRExpr_RdTmp(var2),
3019                                      IRExpr_Const(IRConst_U32(con2)))
3020                       : IRExpr_Binop(Iop_Sub32,
3021                                      IRExpr_RdTmp(var2),
3022                                      IRExpr_Const(IRConst_U32(-con2)))
3023                  );
3024             if (DEBUG_IROPT) {
3025                ppIRStmt(bb->stmts[i]);
3026                vex_printf("\n");
3027             }
3028          }
3029
3030          continue;
3031       }
3032
3033       /* Try to collapse 't1 = GetI[t2, con]'. */
3034
3035       if (st->tag == Ist_WrTmp
3036           && st->Ist.WrTmp.data->tag == Iex_GetI
3037           && st->Ist.WrTmp.data->Iex.GetI.ix->tag == Iex_RdTmp
3038           && collapseChain(bb, i-1, st->Ist.WrTmp.data->Iex.GetI.ix
3039                                       ->Iex.RdTmp.tmp, &var2, &con2)) {
3040          if (DEBUG_IROPT) {
3041             vex_printf("replacing3 ");
3042             ppIRStmt(st);
3043             vex_printf(" with ");
3044          }
3045          con2 += st->Ist.WrTmp.data->Iex.GetI.bias;
3046          bb->stmts[i]
3047             = IRStmt_WrTmp(
3048                  st->Ist.WrTmp.tmp,
3049                  IRExpr_GetI(st->Ist.WrTmp.data->Iex.GetI.descr,
3050                              IRExpr_RdTmp(var2),
3051                              con2));
3052          if (DEBUG_IROPT) {
3053             ppIRStmt(bb->stmts[i]);
3054             vex_printf("\n");
3055          }
3056          continue;
3057       }
3058
3059       /* Perhaps st is PutI[t, con] ? */
3060
3061       if (st->tag == Ist_PutI
3062           && st->Ist.PutI.ix->tag == Iex_RdTmp
3063           && collapseChain(bb, i-1, st->Ist.PutI.ix->Iex.RdTmp.tmp,
3064                                &var2, &con2)) {
3065          if (DEBUG_IROPT) {
3066             vex_printf("replacing2 ");
3067             ppIRStmt(st);
3068             vex_printf(" with ");
3069          }
3070          con2 += st->Ist.PutI.bias;
3071          bb->stmts[i]
3072            = IRStmt_PutI(st->Ist.PutI.descr,
3073                          IRExpr_RdTmp(var2),
3074                          con2,
3075                          st->Ist.PutI.data);
3076          if (DEBUG_IROPT) {
3077             ppIRStmt(bb->stmts[i]);
3078             vex_printf("\n");
3079          }
3080          continue;
3081       }
3082
3083    } /* for */
3084 }
3085
3086
3087 /*---------------------------------------------------------------*/
3088 /*--- PutI/GetI transformations                               ---*/
3089 /*---------------------------------------------------------------*/
3090
3091 /* Given the parts (descr, tmp, bias) for a GetI, scan backwards from
3092    the given starting point to find, if any, a PutI which writes
3093    exactly the same piece of guest state, and so return the expression
3094    that the PutI writes.  This is the core of PutI-GetI forwarding. */
3095
3096 static
3097 IRExpr* findPutI ( IRSB* bb, Int startHere,
3098                    IRRegArray* descrG, IRExpr* ixG, Int biasG )
3099 {
3100    Int        j;
3101    IRStmt*    st;
3102    GSAliasing relation;
3103
3104    if (0) {
3105       vex_printf("\nfindPutI ");
3106       ppIRRegArray(descrG);
3107       vex_printf(" ");
3108       ppIRExpr(ixG);
3109       vex_printf(" %d\n", biasG);
3110    }
3111
3112    /* Scan backwards in bb from startHere to find a suitable PutI
3113       binding for (descrG, ixG, biasG), if any. */
3114
3115    for (j = startHere; j >= 0; j--) {
3116       st = bb->stmts[j];
3117       if (st->tag == Ist_NoOp)
3118          continue;
3119
3120       if (st->tag == Ist_Put) {
3121          /* Non-indexed Put.  This can't give a binding, but we do
3122             need to check it doesn't invalidate the search by
3123             overlapping any part of the indexed guest state. */
3124
3125          relation
3126             = getAliasingRelation_IC(
3127                  descrG, ixG,
3128                  st->Ist.Put.offset,
3129                  typeOfIRExpr(bb->tyenv,st->Ist.Put.data) );
3130
3131          if (relation == NoAlias) {
3132             /* we're OK; keep going */
3133             continue;
3134          } else {
3135             /* relation == UnknownAlias || relation == ExactAlias */
3136             /* If this assertion fails, we've found a Put which writes
3137                an area of guest state which is read by a GetI.  Which
3138                is unlikely (although not per se wrong). */
3139             vassert(relation != ExactAlias);
3140             /* This Put potentially writes guest state that the GetI
3141                reads; we must fail. */
3142             return NULL;
3143          }
3144       }
3145
3146       if (st->tag == Ist_PutI) {
3147
3148          relation = getAliasingRelation_II(
3149                        descrG, ixG, biasG,
3150                        st->Ist.PutI.descr,
3151                        st->Ist.PutI.ix,
3152                        st->Ist.PutI.bias
3153                     );
3154
3155          if (relation == NoAlias) {
3156             /* This PutI definitely doesn't overlap.  Ignore it and
3157                keep going. */
3158             continue; /* the for j loop */
3159          }
3160
3161          if (relation == UnknownAlias) {
3162             /* We don't know if this PutI writes to the same guest
3163                state that the GetI, or not.  So we have to give up. */
3164             return NULL;
3165          }
3166
3167          /* Otherwise, we've found what we're looking for.  */
3168          vassert(relation == ExactAlias);
3169          return st->Ist.PutI.data;
3170
3171       } /* if (st->tag == Ist_PutI) */
3172
3173       if (st->tag == Ist_Dirty) {
3174          /* Be conservative.  If the dirty call has any guest effects at
3175             all, give up.  We could do better -- only give up if there
3176             are any guest writes/modifies. */
3177          if (st->Ist.Dirty.details->nFxState > 0)
3178             return NULL;
3179       }
3180
3181    } /* for */
3182
3183    /* No valid replacement was found. */
3184    return NULL;
3185 }
3186
3187
3188
3189 /* Assuming pi is a PutI stmt, is s2 identical to it (in the sense
3190    that it writes exactly the same piece of guest state) ?  Safe
3191    answer: False. */
3192
3193 static Bool identicalPutIs ( IRStmt* pi, IRStmt* s2 )
3194 {
3195    vassert(pi->tag == Ist_PutI);
3196    if (s2->tag != Ist_PutI)
3197       return False;
3198
3199    return toBool(
3200           getAliasingRelation_II(
3201              pi->Ist.PutI.descr, pi->Ist.PutI.ix, pi->Ist.PutI.bias,
3202              s2->Ist.PutI.descr, s2->Ist.PutI.ix, s2->Ist.PutI.bias
3203           )
3204           == ExactAlias
3205           );
3206 }
3207
3208
3209 /* Assuming pi is a PutI stmt, is s2 a Get/GetI/Put/PutI which might
3210    overlap it?  Safe answer: True.  Note, we could do a lot better
3211    than this if needed. */
3212
3213 static
3214 Bool guestAccessWhichMightOverlapPutI (
3215         IRTypeEnv* tyenv, IRStmt* pi, IRStmt* s2
3216      )
3217 {
3218    GSAliasing relation;
3219    UInt       minoffP, maxoffP;
3220
3221    vassert(pi->tag == Ist_PutI);
3222    getArrayBounds(pi->Ist.PutI.descr, &minoffP, &maxoffP);
3223    switch (s2->tag) {
3224
3225       case Ist_NoOp:
3226       case Ist_IMark:
3227          return False;
3228
3229       case Ist_MBE:
3230       case Ist_AbiHint:
3231          /* just be paranoid ... these should be rare. */
3232          return True;
3233
3234       case Ist_CAS:
3235          /* This is unbelievably lame, but it's probably not
3236             significant from a performance point of view.  Really, a
3237             CAS is a load-store op, so it should be safe to say False.
3238             However .. */
3239          return True;
3240
3241       case Ist_Dirty:
3242          /* If the dirty call has any guest effects at all, give up.
3243             Probably could do better. */
3244          if (s2->Ist.Dirty.details->nFxState > 0)
3245             return True;
3246          return False;
3247
3248       case Ist_Put:
3249          vassert(isIRAtom(s2->Ist.Put.data));
3250          relation
3251             = getAliasingRelation_IC(
3252                  pi->Ist.PutI.descr, pi->Ist.PutI.ix,
3253                  s2->Ist.Put.offset,
3254                  typeOfIRExpr(tyenv,s2->Ist.Put.data)
3255               );
3256          goto have_relation;
3257
3258       case Ist_PutI:
3259          vassert(isIRAtom(s2->Ist.PutI.ix));
3260          vassert(isIRAtom(s2->Ist.PutI.data));
3261          relation
3262             = getAliasingRelation_II(
3263                  pi->Ist.PutI.descr, pi->Ist.PutI.ix, pi->Ist.PutI.bias,
3264                  s2->Ist.PutI.descr, s2->Ist.PutI.ix, s2->Ist.PutI.bias
3265               );
3266          goto have_relation;
3267
3268       case Ist_WrTmp:
3269          if (s2->Ist.WrTmp.data->tag == Iex_GetI) {
3270             relation
3271                = getAliasingRelation_II(
3272                     pi->Ist.PutI.descr, pi->Ist.PutI.ix,
3273                                         pi->Ist.PutI.bias,
3274                     s2->Ist.WrTmp.data->Iex.GetI.descr,
3275                     s2->Ist.WrTmp.data->Iex.GetI.ix,
3276                     s2->Ist.WrTmp.data->Iex.GetI.bias
3277                  );
3278             goto have_relation;
3279          }
3280          if (s2->Ist.WrTmp.data->tag == Iex_Get) {
3281             relation
3282                = getAliasingRelation_IC(
3283                     pi->Ist.PutI.descr, pi->Ist.PutI.ix,
3284                     s2->Ist.WrTmp.data->Iex.Get.offset,
3285                     s2->Ist.WrTmp.data->Iex.Get.ty
3286                  );
3287             goto have_relation;
3288          }
3289          return False;
3290
3291       case Ist_Store:
3292          vassert(isIRAtom(s2->Ist.Store.addr));
3293          vassert(isIRAtom(s2->Ist.Store.data));
3294          return False;
3295
3296       default:
3297          vex_printf("\n"); ppIRStmt(s2); vex_printf("\n");
3298          vpanic("guestAccessWhichMightOverlapPutI");
3299    }
3300
3301   have_relation:
3302    if (relation == NoAlias)
3303       return False;
3304    else
3305       return True; /* ExactAlias or UnknownAlias */
3306 }
3307
3308
3309
3310 /* ---------- PutI/GetI transformations main functions --------- */
3311
3312 /* Remove redundant GetIs, to the extent that they can be detected.
3313    bb is modified in-place. */
3314
3315 static
3316 void do_redundant_GetI_elimination ( IRSB* bb )
3317 {
3318    Int     i;
3319    IRStmt* st;
3320
3321    for (i = bb->stmts_used-1; i >= 0; i--) {
3322       st = bb->stmts[i];
3323       if (st->tag == Ist_NoOp)
3324          continue;
3325
3326       if (st->tag == Ist_WrTmp
3327           && st->Ist.WrTmp.data->tag == Iex_GetI
3328           && st->Ist.WrTmp.data->Iex.GetI.ix->tag == Iex_RdTmp) {
3329          IRRegArray* descr = st->Ist.WrTmp.data->Iex.GetI.descr;
3330          IRExpr*     ix    = st->Ist.WrTmp.data->Iex.GetI.ix;
3331          Int         bias  = st->Ist.WrTmp.data->Iex.GetI.bias;
3332          IRExpr*     replacement = findPutI(bb, i-1, descr, ix, bias);
3333          if (replacement
3334              && isIRAtom(replacement)
3335              /* Make sure we're doing a type-safe transformation! */
3336              && typeOfIRExpr(bb->tyenv, replacement) == descr->elemTy) {
3337             if (DEBUG_IROPT) {
3338                vex_printf("rGI:  ");
3339                ppIRExpr(st->Ist.WrTmp.data);
3340                vex_printf(" -> ");
3341                ppIRExpr(replacement);
3342                vex_printf("\n");
3343             }
3344             bb->stmts[i] = IRStmt_WrTmp(st->Ist.WrTmp.tmp, replacement);
3345          }
3346       }
3347    }
3348
3349 }
3350
3351
3352 /* Remove redundant PutIs, to the extent which they can be detected.
3353    bb is modified in-place. */
3354
3355 static
3356 void do_redundant_PutI_elimination ( IRSB* bb )
3357 {
3358    Int    i, j;
3359    Bool   delete;
3360    IRStmt *st, *stj;
3361
3362    for (i = 0; i < bb->stmts_used; i++) {
3363       st = bb->stmts[i];
3364       if (st->tag != Ist_PutI)
3365          continue;
3366       /* Ok, search forwards from here to see if we can find another
3367          PutI which makes this one redundant, and dodging various
3368          hazards.  Search forwards:
3369          * If conditional exit, give up (because anything after that
3370            does not postdominate this put).
3371          * If a Get which might overlap, give up (because this PutI
3372            not necessarily dead).
3373          * If a Put which is identical, stop with success.
3374          * If a Put which might overlap, but is not identical, give up.
3375          * If a dirty helper call which might write guest state, give up.
3376          * If a Put which definitely doesn't overlap, or any other
3377            kind of stmt, continue.
3378       */
3379       delete = False;
3380       for (j = i+1; j < bb->stmts_used; j++) {
3381          stj = bb->stmts[j];
3382          if (stj->tag == Ist_NoOp)
3383             continue;
3384          if (identicalPutIs(st, stj)) {
3385             /* success! */
3386             delete = True;
3387             break;
3388          }
3389          if (stj->tag == Ist_Exit)
3390             /* give up */
3391             break;
3392          if (st->tag == Ist_Dirty)
3393             /* give up; could do better here */
3394             break;
3395          if (guestAccessWhichMightOverlapPutI(bb->tyenv, st, stj))
3396             /* give up */
3397            break;
3398       }
3399
3400       if (delete) {
3401          if (DEBUG_IROPT) {
3402             vex_printf("rPI:  ");
3403             ppIRStmt(st);
3404             vex_printf("\n");
3405          }
3406          bb->stmts[i] = IRStmt_NoOp();
3407       }
3408
3409    }
3410 }
3411
3412
3413 /*---------------------------------------------------------------*/
3414 /*--- Loop unrolling                                          ---*/
3415 /*---------------------------------------------------------------*/
3416
3417 /* Adjust all tmp values (names) in e by delta.  e is destructively
3418    modified. */
3419
3420 static void deltaIRExpr ( IRExpr* e, Int delta )
3421 {
3422    Int i;
3423    switch (e->tag) {
3424       case Iex_RdTmp:
3425          e->Iex.RdTmp.tmp += delta;
3426          break;
3427       case Iex_Get:
3428       case Iex_Const:
3429          break;
3430       case Iex_GetI:
3431          deltaIRExpr(e->Iex.GetI.ix, delta);
3432          break;
3433       case Iex_Qop:
3434          deltaIRExpr(e->Iex.Qop.arg1, delta);
3435          deltaIRExpr(e->Iex.Qop.arg2, delta);
3436          deltaIRExpr(e->Iex.Qop.arg3, delta);
3437          deltaIRExpr(e->Iex.Qop.arg4, delta);
3438          break;
3439       case Iex_Triop:
3440          deltaIRExpr(e->Iex.Triop.arg1, delta);
3441          deltaIRExpr(e->Iex.Triop.arg2, delta);
3442          deltaIRExpr(e->Iex.Triop.arg3, delta);
3443          break;
3444       case Iex_Binop:
3445          deltaIRExpr(e->Iex.Binop.arg1, delta);
3446          deltaIRExpr(e->Iex.Binop.arg2, delta);
3447          break;
3448       case Iex_Unop:
3449          deltaIRExpr(e->Iex.Unop.arg, delta);
3450          break;
3451       case Iex_Load:
3452          deltaIRExpr(e->Iex.Load.addr, delta);
3453          break;
3454       case Iex_CCall:
3455          for (i = 0; e->Iex.CCall.args[i]; i++)
3456             deltaIRExpr(e->Iex.CCall.args[i], delta);
3457          break;
3458       case Iex_Mux0X:
3459          deltaIRExpr(e->Iex.Mux0X.cond, delta);
3460          deltaIRExpr(e->Iex.Mux0X.expr0, delta);
3461          deltaIRExpr(e->Iex.Mux0X.exprX, delta);
3462          break;
3463       default:
3464          vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
3465          vpanic("deltaIRExpr");
3466    }
3467 }
3468
3469 /* Adjust all tmp values (names) in st by delta.  st is destructively
3470    modified. */
3471
3472 static void deltaIRStmt ( IRStmt* st, Int delta )
3473 {
3474    Int      i;
3475    IRDirty* d;
3476    switch (st->tag) {
3477       case Ist_NoOp:
3478       case Ist_IMark:
3479       case Ist_MBE:
3480          break;
3481       case Ist_AbiHint:
3482          deltaIRExpr(st->Ist.AbiHint.base, delta);
3483          deltaIRExpr(st->Ist.AbiHint.nia, delta);
3484          break;
3485       case Ist_Put:
3486          deltaIRExpr(st->Ist.Put.data, delta);
3487          break;
3488       case Ist_PutI:
3489          deltaIRExpr(st->Ist.PutI.ix, delta);
3490          deltaIRExpr(st->Ist.PutI.data, delta);
3491          break;
3492       case Ist_WrTmp:
3493          st->Ist.WrTmp.tmp += delta;
3494          deltaIRExpr(st->Ist.WrTmp.data, delta);
3495          break;
3496       case Ist_Exit:
3497          deltaIRExpr(st->Ist.Exit.guard, delta);
3498          break;
3499       case Ist_Store:
3500          deltaIRExpr(st->Ist.Store.addr, delta);
3501          deltaIRExpr(st->Ist.Store.data, delta);
3502          break;
3503       case Ist_CAS:
3504          if (st->Ist.CAS.details->oldHi != IRTemp_INVALID)
3505             st->Ist.CAS.details->oldHi += delta;
3506          st->Ist.CAS.details->oldLo += delta;
3507          deltaIRExpr(st->Ist.CAS.details->addr, delta);
3508          if (st->Ist.CAS.details->expdHi)
3509             deltaIRExpr(st->Ist.CAS.details->expdHi, delta);
3510          deltaIRExpr(st->Ist.CAS.details->expdLo, delta);
3511          if (st->Ist.CAS.details->dataHi)
3512             deltaIRExpr(st->Ist.CAS.details->dataHi, delta);
3513          deltaIRExpr(st->Ist.CAS.details->dataLo, delta);
3514          break;
3515       case Ist_LLSC:
3516          st->Ist.LLSC.result += delta;
3517          deltaIRExpr(st->Ist.LLSC.addr, delta);
3518          if (st->Ist.LLSC.storedata)
3519             deltaIRExpr(st->Ist.LLSC.storedata, delta);
3520          break;
3521       case Ist_Dirty:
3522          d = st->Ist.Dirty.details;
3523          deltaIRExpr(d->guard, delta);
3524          for (i = 0; d->args[i]; i++)
3525             deltaIRExpr(d->args[i], delta);
3526          if (d->tmp != IRTemp_INVALID)
3527             d->tmp += delta;
3528          if (d->mAddr)
3529             deltaIRExpr(d->mAddr, delta);
3530          break;
3531       default:
3532          vex_printf("\n"); ppIRStmt(st); vex_printf("\n");
3533          vpanic("deltaIRStmt");
3534    }
3535 }
3536
3537
3538 /* If possible, return a loop-unrolled version of bb0.  The original
3539    is changed.  If not possible, return NULL.  */
3540
3541 /* The two schemas considered are:
3542
3543      X: BODY; goto X
3544
3545      which unrolls to (eg)  X: BODY;BODY; goto X
3546
3547    and
3548
3549        X: BODY; if (c) goto X; goto Y
3550    which trivially transforms to
3551        X: BODY; if (!c) goto Y; goto X;
3552    so it falls in the scope of the first case.
3553
3554    X and Y must be literal (guest) addresses.
3555 */
3556
3557 static Int calc_unroll_factor( IRSB* bb )
3558 {
3559    Int n_stmts, i;
3560
3561    n_stmts = 0;
3562    for (i = 0; i < bb->stmts_used; i++) {
3563       if (bb->stmts[i]->tag != Ist_NoOp)
3564          n_stmts++;
3565    }
3566
3567    if (n_stmts <= vex_control.iropt_unroll_thresh/8) {
3568       if (vex_control.iropt_verbosity > 0)
3569          vex_printf("vex iropt: 8 x unrolling (%d sts -> %d sts)\n",
3570                     n_stmts, 8* n_stmts);
3571       return 8;
3572    }
3573    if (n_stmts <= vex_control.iropt_unroll_thresh/4) {
3574       if (vex_control.iropt_verbosity > 0)
3575          vex_printf("vex iropt: 4 x unrolling (%d sts -> %d sts)\n",
3576                     n_stmts, 4* n_stmts);
3577       return 4;
3578    }
3579
3580    if (n_stmts <= vex_control.iropt_unroll_thresh/2) {
3581       if (vex_control.iropt_verbosity > 0)
3582          vex_printf("vex iropt: 2 x unrolling (%d sts -> %d sts)\n",
3583                     n_stmts, 2* n_stmts);
3584       return 2;
3585    }
3586
3587    if (vex_control.iropt_verbosity > 0)
3588       vex_printf("vex iropt: not unrolling (%d sts)\n", n_stmts);
3589
3590    return 1;
3591 }
3592
3593
3594 static IRSB* maybe_loop_unroll_BB ( IRSB* bb0, Addr64 my_addr )
3595 {
3596    Int      i, j, jmax, n_vars;
3597    Bool     xxx_known;
3598    Addr64   xxx_value, yyy_value;
3599    IRExpr*  udst;
3600    IRStmt*  st;
3601    IRConst* con;
3602    IRSB     *bb1, *bb2;
3603    Int      unroll_factor;
3604
3605    if (vex_control.iropt_unroll_thresh <= 0)
3606       return NULL;
3607
3608    /* First off, figure out if we can unroll this loop.  Do this
3609       without modifying bb0. */
3610
3611    if (bb0->jumpkind != Ijk_Boring)
3612       return NULL;
3613
3614    xxx_known = False;
3615    xxx_value = 0;
3616
3617    /* Extract the next-guest address.  If it isn't a literal, we
3618       have to give up. */
3619
3620    udst = bb0->next;
3621    if (udst->tag == Iex_Const
3622        && (udst->Iex.Const.con->tag == Ico_U32
3623            || udst->Iex.Const.con->tag == Ico_U64)) {
3624       /* The BB ends in a jump to a literal location. */
3625       xxx_known = True;
3626       xxx_value = udst->Iex.Const.con->tag == Ico_U64
3627                     ?  udst->Iex.Const.con->Ico.U64
3628                     : (Addr64)(udst->Iex.Const.con->Ico.U32);
3629    }
3630
3631    if (!xxx_known)
3632       return NULL;
3633
3634    /* Now we know the BB ends to a jump to a literal location.  If
3635       it's a jump to itself (viz, idiom #1), move directly to the
3636       unrolling stage, first cloning the bb so the original isn't
3637       modified. */
3638    if (xxx_value == my_addr) {
3639       unroll_factor = calc_unroll_factor( bb0 );
3640       if (unroll_factor < 2)
3641          return NULL;
3642       bb1 = deepCopyIRSB( bb0 );
3643       bb0 = NULL;
3644       udst = NULL; /* is now invalid */
3645       goto do_unroll;
3646    }
3647
3648    /* Search for the second idiomatic form:
3649         X: BODY; if (c) goto X; goto Y
3650       We know Y, but need to establish that the last stmt
3651       is 'if (c) goto X'.
3652    */
3653    yyy_value = xxx_value;
3654    for (i = bb0->stmts_used-1; i >= 0; i--)
3655       if (bb0->stmts[i])
3656          break;
3657
3658    if (i < 0)
3659       return NULL; /* block with no stmts.  Strange. */
3660
3661    st = bb0->stmts[i];
3662    if (st->tag != Ist_Exit)
3663       return NULL;
3664    if (st->Ist.Exit.jk != Ijk_Boring)
3665       return NULL;
3666
3667    con = st->Ist.Exit.dst;
3668    vassert(con->tag == Ico_U32 || con->tag == Ico_U64);
3669
3670    xxx_value = con->tag == Ico_U64
3671                   ? st->Ist.Exit.dst->Ico.U64
3672                   : (Addr64)(st->Ist.Exit.dst->Ico.U32);
3673
3674    /* If this assertion fails, we have some kind of type error. */
3675    vassert(con->tag == udst->Iex.Const.con->tag);
3676
3677    if (xxx_value != my_addr)
3678       /* We didn't find either idiom.  Give up. */
3679       return NULL;
3680
3681    /* Ok, we found idiom #2.  Copy the BB, switch around the xxx and
3682       yyy values (which makes it look like idiom #1), and go into
3683       unrolling proper.  This means finding (again) the last stmt, in
3684       the copied BB. */
3685
3686    unroll_factor = calc_unroll_factor( bb0 );
3687    if (unroll_factor < 2)
3688       return NULL;
3689
3690    bb1 = deepCopyIRSB( bb0 );
3691    bb0 = NULL;
3692    udst = NULL; /* is now invalid */
3693    for (i = bb1->stmts_used-1; i >= 0; i--)
3694       if (bb1->stmts[i])
3695          break;
3696
3697    /* The next bunch of assertions should be true since we already
3698       found and checked the last stmt in the original bb. */
3699
3700    vassert(i >= 0);
3701
3702    st = bb1->stmts[i];
3703    vassert(st->tag == Ist_Exit);
3704
3705    con = st->Ist.Exit.dst;
3706    vassert(con->tag == Ico_U32 || con->tag == Ico_U64);
3707
3708    udst = bb1->next;
3709    vassert(udst->tag == Iex_Const);
3710    vassert(udst->Iex.Const.con->tag == Ico_U32
3711           || udst->Iex.Const.con->tag == Ico_U64);
3712    vassert(con->tag == udst->Iex.Const.con->tag);
3713
3714    /* switch the xxx and yyy fields around */
3715    if (con->tag == Ico_U64) {
3716       udst->Iex.Const.con->Ico.U64 = xxx_value;
3717       con->Ico.U64 = yyy_value;
3718    } else {
3719       udst->Iex.Const.con->Ico.U32 = (UInt)xxx_value;
3720       con->Ico.U32 = (UInt)yyy_value;
3721    }
3722
3723    /* negate the test condition */
3724    st->Ist.Exit.guard
3725       = IRExpr_Unop(Iop_Not1,deepCopyIRExpr(st->Ist.Exit.guard));
3726
3727    /* --- The unroller proper.  Both idioms are by now --- */
3728    /* --- now converted to idiom 1. --- */
3729
3730   do_unroll:
3731
3732    vassert(unroll_factor == 2
3733            || unroll_factor == 4
3734            || unroll_factor == 8);
3735
3736    jmax = unroll_factor==8 ? 3 : (unroll_factor==4 ? 2 : 1);
3737    for (j = 1; j <= jmax; j++) {
3738
3739       n_vars = bb1->tyenv->types_used;
3740
3741       bb2 = deepCopyIRSB(bb1);
3742       for (i = 0; i < n_vars; i++)
3743          (void)newIRTemp(bb1->tyenv, bb2->tyenv->types[i]);
3744
3745       for (i = 0; i < bb2->stmts_used; i++) {
3746          /* deltaIRStmt destructively modifies the stmt, but
3747             that's OK since bb2 is a complete fresh copy of bb1. */
3748          deltaIRStmt(bb2->stmts[i], n_vars);
3749          addStmtToIRSB(bb1, bb2->stmts[i]);
3750       }
3751    }
3752
3753    if (DEBUG_IROPT) {
3754       vex_printf("\nUNROLLED (%llx)\n", my_addr);
3755       ppIRSB(bb1);
3756       vex_printf("\n");
3757    }
3758
3759    /* Flattening; sigh.  The unroller succeeds in breaking flatness
3760       by negating the test condition.  This should be fixed properly.
3761       For the moment use this shotgun approach.  */
3762    return flatten_BB(bb1);
3763 }
3764
3765
3766 /*---------------------------------------------------------------*/
3767 /*--- The tree builder                                        ---*/
3768 /*---------------------------------------------------------------*/
3769
3770 /* This isn't part of IR optimisation.  Really it's a pass done prior
3771    to instruction selection, which improves the code that the
3772    instruction selector can produce. */
3773
3774 /* --- The 'tmp' environment is the central data structure here --- */
3775
3776 /* The number of outstanding bindings we're prepared to track.
3777    The number of times the env becomes full and we have to dump
3778    the oldest binding (hence reducing code quality) falls very
3779    rapidly as the env size increases.  8 gives reasonable performance
3780    under most circumstances. */
3781 #define A_NENV 10
3782
3783 /* bindee == NULL   ===  slot is not in use
3784    bindee != NULL   ===  slot is in use
3785 */
3786 typedef
3787    struct {
3788       IRTemp  binder;
3789       IRExpr* bindee;
3790       Bool    doesLoad;
3791       Bool    doesGet;
3792    }
3793    ATmpInfo;
3794
3795 __attribute__((unused))
3796 static void ppAEnv ( ATmpInfo* env )
3797 {
3798    Int i;
3799    for (i = 0; i < A_NENV; i++) {
3800       vex_printf("%d  tmp %d  val ", i, (Int)env[i].binder);
3801       if (env[i].bindee)
3802          ppIRExpr(env[i].bindee);
3803       else
3804          vex_printf("(null)");
3805       vex_printf("\n");
3806    }
3807 }
3808
3809 /* --- Tree-traversal fns --- */
3810
3811 /* Traverse an expr, and detect if any part of it reads memory or does
3812    a Get.  Be careful ... this really controls how much the
3813    tree-builder can reorder the code, so getting it right is critical.
3814 */
3815 static void setHints_Expr (Bool* doesLoad, Bool* doesGet, IRExpr* e )
3816 {
3817    Int i;
3818    switch (e->tag) {
3819       case Iex_CCall:
3820          for (i = 0; e->Iex.CCall.args[i]; i++)
3821             setHints_Expr(doesLoad, doesGet, e->Iex.CCall.args[i]);
3822          return;
3823       case Iex_Mux0X:
3824          setHints_Expr(doesLoad, doesGet, e->Iex.Mux0X.cond);
3825          setHints_Expr(doesLoad, doesGet, e->Iex.Mux0X.expr0);
3826          setHints_Expr(doesLoad, doesGet, e->Iex.Mux0X.exprX);
3827          return;
3828       case Iex_Qop:
3829          setHints_Expr(doesLoad, doesGet, e->Iex.Qop.arg1);
3830          setHints_Expr(doesLoad, doesGet, e->Iex.Qop.arg2);
3831          setHints_Expr(doesLoad, doesGet, e->Iex.Qop.arg3);
3832          setHints_Expr(doesLoad, doesGet, e->Iex.Qop.arg4);
3833          return;
3834       case Iex_Triop:
3835          setHints_Expr(doesLoad, doesGet, e->Iex.Triop.arg1);
3836          setHints_Expr(doesLoad, doesGet, e->Iex.Triop.arg2);
3837          setHints_Expr(doesLoad, doesGet, e->Iex.Triop.arg3);
3838          return;
3839       case Iex_Binop:
3840          setHints_Expr(doesLoad, doesGet, e->Iex.Binop.arg1);
3841          setHints_Expr(doesLoad, doesGet, e->Iex.Binop.arg2);
3842          return;
3843       case Iex_Unop:
3844          setHints_Expr(doesLoad, doesGet, e->Iex.Unop.arg);
3845          return;
3846       case Iex_Load:
3847          *doesLoad = True;
3848          setHints_Expr(doesLoad, doesGet, e->Iex.Load.addr);
3849          return;
3850       case Iex_Get:
3851          *doesGet = True;
3852          return;
3853       case Iex_GetI:
3854          *doesGet = True;
3855          setHints_Expr(doesLoad, doesGet, e->Iex.GetI.ix);
3856          return;
3857       case Iex_RdTmp:
3858       case Iex_Const:
3859          return;
3860       default:
3861          vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
3862          vpanic("setHints_Expr");
3863    }
3864 }
3865
3866
3867 /* Add a binding to the front of the env and slide all the rest
3868    backwards.  It should be the case that the last slot is free. */
3869 static void addToEnvFront ( ATmpInfo* env, IRTemp binder, IRExpr* bindee )
3870 {
3871    Int i;
3872    vassert(env[A_NENV-1].bindee == NULL);
3873    for (i = A_NENV-1; i >= 1; i--)
3874       env[i] = env[i-1];
3875    env[0].binder   = binder;
3876    env[0].bindee   = bindee;
3877    env[0].doesLoad = False; /* filled in later */
3878    env[0].doesGet  = False; /* filled in later */
3879 }
3880
3881 /* Given uses :: array of UShort, indexed by IRTemp
3882    Add the use-occurrences of temps in this expression
3883    to the env.
3884 */
3885 static void aoccCount_Expr ( UShort* uses, IRExpr* e )
3886 {
3887    Int i;
3888
3889    switch (e->tag) {
3890
3891       case Iex_RdTmp: /* the only interesting case */
3892          uses[e->Iex.RdTmp.tmp]++;
3893          return;
3894
3895       case Iex_Mux0X:
3896          aoccCount_Expr(uses, e->Iex.Mux0X.cond);
3897          aoccCount_Expr(uses, e->Iex.Mux0X.expr0);
3898          aoccCount_Expr(uses, e->Iex.Mux0X.exprX);
3899          return;
3900
3901       case Iex_Qop:
3902          aoccCount_Expr(uses, e->Iex.Qop.arg1);
3903          aoccCount_Expr(uses, e->Iex.Qop.arg2);
3904          aoccCount_Expr(uses, e->Iex.Qop.arg3);
3905          aoccCount_Expr(uses, e->Iex.Qop.arg4);
3906          return;
3907
3908       case Iex_Triop:
3909          aoccCount_Expr(uses, e->Iex.Triop.arg1);
3910          aoccCount_Expr(uses, e->Iex.Triop.arg2);
3911          aoccCount_Expr(uses, e->Iex.Triop.arg3);
3912          return;
3913
3914       case Iex_Binop:
3915          aoccCount_Expr(uses, e->Iex.Binop.arg1);
3916          aoccCount_Expr(uses, e->Iex.Binop.arg2);
3917          return;
3918
3919       case Iex_Unop:
3920          aoccCount_Expr(uses, e->Iex.Unop.arg);
3921          return;
3922
3923       case Iex_Load:
3924          aoccCount_Expr(uses, e->Iex.Load.addr);
3925          return;
3926
3927       case Iex_CCall:
3928          for (i = 0; e->Iex.CCall.args[i]; i++)
3929             aoccCount_Expr(uses, e->Iex.CCall.args[i]);
3930          return;
3931
3932       case Iex_GetI:
3933          aoccCount_Expr(uses, e->Iex.GetI.ix);
3934          return;
3935
3936       case Iex_Const:
3937       case Iex_Get:
3938          return;
3939
3940       default:
3941          vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
3942          vpanic("aoccCount_Expr");
3943     }
3944 }
3945
3946
3947 /* Given uses :: array of UShort, indexed by IRTemp
3948    Add the use-occurrences of temps in this statement
3949    to the env.
3950 */
3951 static void aoccCount_Stmt ( UShort* uses, IRStmt* st )
3952 {
3953    Int      i;
3954    IRDirty* d;
3955    IRCAS*   cas;
3956    switch (st->tag) {
3957       case Ist_AbiHint:
3958          aoccCount_Expr(uses, st->Ist.AbiHint.base);
3959          aoccCount_Expr(uses, st->Ist.AbiHint.nia);
3960          return;
3961       case Ist_WrTmp:
3962          aoccCount_Expr(uses, st->Ist.WrTmp.data);
3963          return;
3964       case Ist_Put:
3965          aoccCount_Expr(uses, st->Ist.Put.data);
3966          return;
3967       case Ist_PutI:
3968          aoccCount_Expr(uses, st->Ist.PutI.ix);
3969          aoccCount_Expr(uses, st->Ist.PutI.data);
3970          return;
3971       case Ist_Store:
3972          aoccCount_Expr(uses, st->Ist.Store.addr);
3973          aoccCount_Expr(uses, st->Ist.Store.data);
3974          return;
3975       case Ist_CAS:
3976          cas = st->Ist.CAS.details;
3977          aoccCount_Expr(uses, cas->addr);
3978          if (cas->expdHi)
3979             aoccCount_Expr(uses, cas->expdHi);
3980          aoccCount_Expr(uses, cas->expdLo);
3981          if (cas->dataHi)
3982             aoccCount_Expr(uses, cas->dataHi);
3983          aoccCount_Expr(uses, cas->dataLo);
3984          return;
3985       case Ist_LLSC:
3986          aoccCount_Expr(uses, st->Ist.LLSC.addr);
3987          if (st->Ist.LLSC.storedata)
3988             aoccCount_Expr(uses, st->Ist.LLSC.storedata);
3989          return;
3990       case Ist_Dirty:
3991          d = st->Ist.Dirty.details;
3992          if (d->mFx != Ifx_None)
3993             aoccCount_Expr(uses, d->mAddr);
3994          aoccCount_Expr(uses, d->guard);
3995          for (i = 0; d->args[i]; i++)
3996             aoccCount_Expr(uses, d->args[i]);
3997          return;
3998       case Ist_NoOp:
3999       case Ist_IMark:
4000       case Ist_MBE:
4001          return;
4002       case Ist_Exit:
4003          aoccCount_Expr(uses, st->Ist.Exit.guard);
4004          return;
4005       default:
4006          vex_printf("\n"); ppIRStmt(st); vex_printf("\n");
4007          vpanic("aoccCount_Stmt");
4008    }
4009 }
4010
4011 /* Look up a binding for tmp in the env.  If found, return the bound
4012    expression, and set the env's binding to NULL so it is marked as
4013    used.  If not found, return NULL. */
4014
4015 static IRExpr* atbSubst_Temp ( ATmpInfo* env, IRTemp tmp )
4016 {
4017    Int i;
4018    for (i = 0; i < A_NENV; i++) {
4019       if (env[i].binder == tmp && env[i].bindee != NULL) {
4020          IRExpr* bindee = env[i].bindee;
4021          env[i].bindee = NULL;
4022          return bindee;
4023       }
4024    }
4025    return NULL;
4026 }
4027
4028 /* Traverse e, looking for temps.  For each observed temp, see if env
4029    contains a binding for the temp, and if so return the bound value.
4030    The env has the property that any binding it holds is
4031    'single-shot', so once a binding is used, it is marked as no longer
4032    available, by setting its .bindee field to NULL. */
4033
4034 static inline Bool is_Unop ( IRExpr* e, IROp op ) {
4035    return e->tag == Iex_Unop && e->Iex.Unop.op == op;
4036 }
4037 static inline Bool is_Binop ( IRExpr* e, IROp op ) {
4038    return e->tag == Iex_Binop && e->Iex.Binop.op == op;
4039 }
4040
4041 static IRExpr* fold_IRExpr_Binop ( IROp op, IRExpr* a1, IRExpr* a2 )
4042 {
4043    switch (op) {
4044    case Iop_Or32:
4045       /* Or32( CmpwNEZ32(x), CmpwNEZ32(y) ) --> CmpwNEZ32( Or32( x, y ) )  */
4046       if (is_Unop(a1, Iop_CmpwNEZ32) && is_Unop(a2, Iop_CmpwNEZ32))
4047          return IRExpr_Unop( Iop_CmpwNEZ32,
4048                              IRExpr_Binop( Iop_Or32, a1->Iex.Unop.arg,
4049                                                      a2->Iex.Unop.arg ) );
4050       break;
4051    default:
4052       break;
4053    }
4054    /* no reduction rule applies */
4055    return IRExpr_Binop( op, a1, a2 );
4056 }
4057
4058 static IRExpr* fold_IRExpr_Unop ( IROp op, IRExpr* aa )
4059 {
4060    switch (op) {
4061    case Iop_CmpwNEZ64:
4062       /* CmpwNEZ64( Or64 ( CmpwNEZ64(x), y ) ) --> CmpwNEZ64( Or64( x, y ) ) */
4063       if (is_Binop(aa, Iop_Or64)
4064           && is_Unop(aa->Iex.Binop.arg1, Iop_CmpwNEZ64))
4065          return fold_IRExpr_Unop(
4066                    Iop_CmpwNEZ64,
4067                    IRExpr_Binop(Iop_Or64,
4068                                 aa->Iex.Binop.arg1->Iex.Unop.arg,
4069                                 aa->Iex.Binop.arg2));
4070       /* CmpwNEZ64( Or64 ( x, CmpwNEZ64(y) ) ) --> CmpwNEZ64( Or64( x, y ) ) */
4071       if (is_Binop(aa, Iop_Or64)
4072           && is_Unop(aa->Iex.Binop.arg2, Iop_CmpwNEZ64))
4073          return fold_IRExpr_Unop(
4074                    Iop_CmpwNEZ64,
4075                    IRExpr_Binop(Iop_Or64,
4076                                 aa->Iex.Binop.arg1,
4077                                 aa->Iex.Binop.arg2->Iex.Unop.arg));
4078       break;
4079    case Iop_CmpNEZ64:
4080       /* CmpNEZ64( Left64(x) ) --> CmpNEZ64(x) */
4081       if (is_Unop(aa, Iop_Left64))
4082          return IRExpr_Unop(Iop_CmpNEZ64, aa->Iex.Unop.arg);
4083       break;
4084    case Iop_CmpwNEZ32:
4085       /* CmpwNEZ32( CmpwNEZ32 ( x ) ) --> CmpwNEZ32 ( x ) */
4086       if (is_Unop(aa, Iop_CmpwNEZ32))
4087          return IRExpr_Unop( Iop_CmpwNEZ32, aa->Iex.Unop.arg );
4088       break;
4089    case Iop_CmpNEZ32:
4090       /* CmpNEZ32( Left32(x) ) --> CmpNEZ32(x) */
4091       if (is_Unop(aa, Iop_Left32))
4092          return IRExpr_Unop(Iop_CmpNEZ32, aa->Iex.Unop.arg);
4093       break;
4094    case Iop_Left32:
4095       /* Left32( Left32(x) ) --> Left32(x) */
4096       if (is_Unop(aa, Iop_Left32))
4097          return IRExpr_Unop( Iop_Left32, aa->Iex.Unop.arg );
4098       break;
4099    case Iop_32to1:
4100       /* 32to1( 1Uto32 ( x ) ) --> x */
4101       if (is_Unop(aa, Iop_1Uto32))
4102          return aa->Iex.Unop.arg;
4103       /* 32to1( CmpwNEZ32 ( x )) --> CmpNEZ32(x) */
4104       if (is_Unop(aa, Iop_CmpwNEZ32))
4105          return IRExpr_Unop( Iop_CmpNEZ32, aa->Iex.Unop.arg );
4106       break;
4107    case Iop_64to1:
4108       /* 64to1( 1Uto64 ( x ) ) --> x */
4109       if (is_Unop(aa, Iop_1Uto64))
4110          return aa->Iex.Unop.arg;
4111       /* 64to1( CmpwNEZ64 ( x )) --> CmpNEZ64(x) */
4112       if (is_Unop(aa, Iop_CmpwNEZ64))
4113          return IRExpr_Unop( Iop_CmpNEZ64, aa->Iex.Unop.arg );
4114       break;
4115    case Iop_64to32:
4116       /* 64to32( 32Uto64 ( x )) --> x */
4117       if (is_Unop(aa, Iop_32Uto64))
4118          return aa->Iex.Unop.arg;
4119       /* 64to32( 8Uto64 ( x )) --> 8Uto32(x) */
4120       if (is_Unop(aa, Iop_8Uto64))
4121          return IRExpr_Unop(Iop_8Uto32, aa->Iex.Unop.arg);
4122       break;
4123
4124    case Iop_32Uto64:
4125       /* 32Uto64( 8Uto32( x )) --> 8Uto64(x) */
4126       if (is_Unop(aa, Iop_8Uto32))
4127          return IRExpr_Unop(Iop_8Uto64, aa->Iex.Unop.arg);
4128       /* 32Uto64( 16Uto32( x )) --> 16Uto64(x) */
4129       if (is_Unop(aa, Iop_16Uto32))
4130          return IRExpr_Unop(Iop_16Uto64, aa->Iex.Unop.arg);
4131       break;
4132
4133    case Iop_1Sto32:
4134       /* 1Sto32( CmpNEZ8( 32to8( 1Uto32( CmpNEZ32( x ))))) -> CmpwNEZ32(x) */
4135       if (is_Unop(aa, Iop_CmpNEZ8)
4136           && is_Unop(aa->Iex.Unop.arg, Iop_32to8)
4137           && is_Unop(aa->Iex.Unop.arg->Iex.Unop.arg, Iop_1Uto32)
4138           && is_Unop(aa->Iex.Unop.arg->Iex.Unop.arg->Iex.Unop.arg,
4139                      Iop_CmpNEZ32)) {
4140          return IRExpr_Unop( Iop_CmpwNEZ32,
4141                              aa->Iex.Unop.arg->Iex.Unop.arg
4142                                ->Iex.Unop.arg->Iex.Unop.arg);
4143       }
4144       break;
4145
4146
4147    default:
4148       break;
4149    }
4150    /* no reduction rule applies */
4151    return IRExpr_Unop( op, aa );
4152 }
4153
4154 static IRExpr* atbSubst_Expr ( ATmpInfo* env, IRExpr* e )
4155 {
4156    IRExpr*  e2;
4157    IRExpr** args2;
4158    Int      i;
4159
4160    switch (e->tag) {
4161
4162       case Iex_CCall:
4163          args2 = shallowCopyIRExprVec(e->Iex.CCall.args);
4164          for (i = 0; args2[i]; i++)
4165             args2[i] = atbSubst_Expr(env,args2[i]);
4166          return IRExpr_CCall(
4167                    e->Iex.CCall.cee,
4168                    e->Iex.CCall.retty,
4169                    args2
4170                 );
4171       case Iex_RdTmp:
4172          e2 = atbSubst_Temp(env, e->Iex.RdTmp.tmp);
4173          return e2 ? e2 : e;
4174       case Iex_Mux0X:
4175          return IRExpr_Mux0X(
4176                    atbSubst_Expr(env, e->Iex.Mux0X.cond),
4177                    atbSubst_Expr(env, e->Iex.Mux0X.expr0),
4178                    atbSubst_Expr(env, e->Iex.Mux0X.exprX)
4179                 );
4180       case Iex_Qop:
4181          return IRExpr_Qop(
4182                    e->Iex.Qop.op,
4183                    atbSubst_Expr(env, e->Iex.Qop.arg1),
4184                    atbSubst_Expr(env, e->Iex.Qop.arg2),
4185                    atbSubst_Expr(env, e->Iex.Qop.arg3),
4186                    atbSubst_Expr(env, e->Iex.Qop.arg4)
4187                 );
4188       case Iex_Triop:
4189          return IRExpr_Triop(
4190                    e->Iex.Triop.op,
4191                    atbSubst_Expr(env, e->Iex.Triop.arg1),
4192                    atbSubst_Expr(env, e->Iex.Triop.arg2),
4193                    atbSubst_Expr(env, e->Iex.Triop.arg3)
4194                 );
4195       case Iex_Binop:
4196          return fold_IRExpr_Binop(
4197                    e->Iex.Binop.op,
4198                    atbSubst_Expr(env, e->Iex.Binop.arg1),
4199                    atbSubst_Expr(env, e->Iex.Binop.arg2)
4200                 );
4201       case Iex_Unop:
4202          return fold_IRExpr_Unop(
4203                    e->Iex.Unop.op,
4204                    atbSubst_Expr(env, e->Iex.Unop.arg)
4205                 );
4206       case Iex_Load:
4207          return IRExpr_Load(
4208                    e->Iex.Load.end,
4209                    e->Iex.Load.ty,
4210                    atbSubst_Expr(env, e->Iex.Load.addr)
4211                 );
4212       case Iex_GetI:
4213          return IRExpr_GetI(
4214                    e->Iex.GetI.descr,
4215                    atbSubst_Expr(env, e->Iex.GetI.ix),
4216                    e->Iex.GetI.bias
4217                 );
4218       case Iex_Const:
4219       case Iex_Get:
4220          return e;
4221       default:
4222          vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
4223          vpanic("atbSubst_Expr");
4224    }
4225 }
4226
4227 /* Same deal as atbSubst_Expr, except for stmts. */
4228
4229 static IRStmt* atbSubst_Stmt ( ATmpInfo* env, IRStmt* st )
4230 {
4231    Int     i;
4232    IRDirty *d, *d2;
4233    IRCAS   *cas, *cas2;
4234    switch (st->tag) {
4235       case Ist_AbiHint:
4236          return IRStmt_AbiHint(
4237                    atbSubst_Expr(env, st->Ist.AbiHint.base),
4238                    st->Ist.AbiHint.len,
4239                    atbSubst_Expr(env, st->Ist.AbiHint.nia)
4240                 );
4241       case Ist_Store:
4242          return IRStmt_Store(
4243                    st->Ist.Store.end,
4244                    atbSubst_Expr(env, st->Ist.Store.addr),
4245                    atbSubst_Expr(env, st->Ist.Store.data)
4246                 );
4247       case Ist_WrTmp:
4248          return IRStmt_WrTmp(
4249                    st->Ist.WrTmp.tmp,
4250                    atbSubst_Expr(env, st->Ist.WrTmp.data)
4251                 );
4252       case Ist_Put:
4253          return IRStmt_Put(
4254                    st->Ist.Put.offset,
4255                    atbSubst_Expr(env, st->Ist.Put.data)
4256                 );
4257       case Ist_PutI:
4258          return IRStmt_PutI(
4259                    st->Ist.PutI.descr,
4260                    atbSubst_Expr(env, st->Ist.PutI.ix),
4261                    st->Ist.PutI.bias,
4262                    atbSubst_Expr(env, st->Ist.PutI.data)
4263                 );
4264
4265       case Ist_Exit:
4266          return IRStmt_Exit(
4267                    atbSubst_Expr(env, st->Ist.Exit.guard),
4268                    st->Ist.Exit.jk,
4269                    st->Ist.Exit.dst
4270                 );
4271       case Ist_IMark:
4272          return IRStmt_IMark(st->Ist.IMark.addr, st->Ist.IMark.len);
4273       case Ist_NoOp:
4274          return IRStmt_NoOp();
4275       case Ist_MBE:
4276          return IRStmt_MBE(st->Ist.MBE.event);
4277       case Ist_CAS:
4278          cas  = st->Ist.CAS.details;
4279          cas2 = mkIRCAS(
4280                    cas->oldHi, cas->oldLo, cas->end,
4281                    atbSubst_Expr(env, cas->addr),
4282                    cas->expdHi ? atbSubst_Expr(env, cas->expdHi) : NULL,
4283                    atbSubst_Expr(env, cas->expdLo),
4284                    cas->dataHi ? atbSubst_Expr(env, cas->dataHi) : NULL,
4285                    atbSubst_Expr(env, cas->dataLo)
4286                 );
4287          return IRStmt_CAS(cas2);
4288       case Ist_LLSC:
4289          return IRStmt_LLSC(
4290                    st->Ist.LLSC.end,
4291                    st->Ist.LLSC.result,
4292                    atbSubst_Expr(env, st->Ist.LLSC.addr),
4293                    st->Ist.LLSC.storedata
4294                       ? atbSubst_Expr(env, st->Ist.LLSC.storedata) : NULL
4295                 );
4296       case Ist_Dirty:
4297          d  = st->Ist.Dirty.details;
4298          d2 = emptyIRDirty();
4299          *d2 = *d;
4300          if (d2->mFx != Ifx_None)
4301             d2->mAddr = atbSubst_Expr(env, d2->mAddr);
4302          d2->guard = atbSubst_Expr(env, d2->guard);
4303          for (i = 0; d2->args[i]; i++)
4304             d2->args[i] = atbSubst_Expr(env, d2->args[i]);
4305          return IRStmt_Dirty(d2);
4306       default:
4307          vex_printf("\n"); ppIRStmt(st); vex_printf("\n");
4308          vpanic("atbSubst_Stmt");
4309    }
4310 }
4311
4312 /* notstatic */ void ado_treebuild_BB ( IRSB* bb )
4313 {
4314    Int      i, j, k, m;
4315    Bool     stmtPuts, stmtStores, invalidateMe;
4316    IRStmt*  st;
4317    IRStmt*  st2;
4318    ATmpInfo env[A_NENV];
4319
4320    Int       n_tmps = bb->tyenv->types_used;
4321    UShort*   uses   = LibVEX_Alloc(n_tmps * sizeof(UShort));
4322
4323    /* Phase 1.  Scan forwards in bb, counting use occurrences of each
4324       temp.  Also count occurrences in the bb->next field. */
4325
4326    for (i = 0; i < n_tmps; i++)
4327       uses[i] = 0;
4328
4329    for (i = 0; i < bb->stmts_used; i++) {
4330       st = bb->stmts[i];
4331       if (st->tag == Ist_NoOp)
4332          continue;
4333       aoccCount_Stmt( uses, st );
4334    }
4335    aoccCount_Expr(uses, bb->next );
4336
4337 #  if 0
4338    for (i = 0; i < n_tmps; i++) {
4339       if (uses[i] == 0)
4340         continue;
4341       ppIRTemp( (IRTemp)i );
4342       vex_printf("  used %d\n", (Int)uses[i] );
4343    }
4344 #  endif
4345
4346    /* Phase 2.  Scan forwards in bb.  For each statement in turn:
4347
4348          If the env is full, emit the end element.  This guarantees
4349          there is at least one free slot in the following.
4350
4351          On seeing 't = E', occ(t)==1,
4352             let E'=env(E)
4353             delete this stmt
4354             add t -> E' to the front of the env
4355             Examine E' and set the hints for E' appropriately
4356               (doesLoad? doesGet?)
4357
4358          On seeing any other stmt,
4359             let stmt' = env(stmt)
4360             remove from env any 't=E' binds invalidated by stmt
4361                 emit the invalidated stmts
4362             emit stmt'
4363             compact any holes in env
4364               by sliding entries towards the front
4365
4366       Finally, apply env to bb->next.
4367    */
4368
4369    for (i = 0; i < A_NENV; i++) {
4370       env[i].bindee = NULL;
4371       env[i].binder = IRTemp_INVALID;
4372    }
4373
4374    /* The stmts in bb are being reordered, and we are guaranteed to
4375       end up with no more than the number we started with.  Use i to
4376       be the cursor of the current stmt examined and j <= i to be that
4377       for the current stmt being written.
4378    */
4379    j = 0;
4380    for (i = 0; i < bb->stmts_used; i++) {
4381
4382       st = bb->stmts[i];
4383       if (st->tag == Ist_NoOp)
4384          continue;
4385
4386       /* Ensure there's at least one space in the env, by emitting
4387          the oldest binding if necessary. */
4388       if (env[A_NENV-1].bindee != NULL) {
4389          bb->stmts[j] = IRStmt_WrTmp( env[A_NENV-1].binder,
4390                                       env[A_NENV-1].bindee );
4391          j++;
4392          vassert(j <= i);
4393          env[A_NENV-1].bindee = NULL;
4394       }
4395
4396       /* Consider current stmt. */
4397       if (st->tag == Ist_WrTmp && uses[st->Ist.WrTmp.tmp] <= 1) {
4398          IRExpr *e, *e2;
4399
4400          /* optional extra: dump dead bindings as we find them.
4401             Removes the need for a prior dead-code removal pass. */
4402          if (uses[st->Ist.WrTmp.tmp] == 0) {
4403             if (0) vex_printf("DEAD binding\n");
4404             continue; /* for (i = 0; i < bb->stmts_used; i++) loop */
4405          }
4406          vassert(uses[st->Ist.WrTmp.tmp] == 1);
4407
4408          /* ok, we have 't = E', occ(t)==1.  Do the abovementioned
4409             actions. */
4410          e  = st->Ist.WrTmp.data;
4411          e2 = atbSubst_Expr(env, e);
4412          addToEnvFront(env, st->Ist.WrTmp.tmp, e2);
4413          setHints_Expr(&env[0].doesLoad, &env[0].doesGet, e2);
4414          /* don't advance j, as we are deleting this stmt and instead
4415             holding it temporarily in the env. */
4416          continue; /* for (i = 0; i < bb->stmts_used; i++) loop */
4417       }
4418
4419       /* we get here for any other kind of statement. */
4420       /* 'use up' any bindings required by the current statement. */
4421       st2 = atbSubst_Stmt(env, st);
4422
4423       /* Now, before this stmt, dump any bindings in env that it
4424          invalidates.  These need to be dumped in the order in which
4425          they originally entered env -- that means from oldest to
4426          youngest. */
4427
4428       /* stmtPuts/stmtStores characterise what the stmt under
4429          consideration does, or might do (sidely safe @ True). */
4430       stmtPuts
4431          = toBool( st->tag == Ist_Put
4432                    || st->tag == Ist_PutI
4433                    || st->tag == Ist_Dirty );
4434
4435       /* be True if this stmt writes memory or might do (==> we don't
4436          want to reorder other loads or stores relative to it).  Also,
4437          both LL and SC fall under this classification, since we
4438          really ought to be conservative and not reorder any other
4439          memory transactions relative to them. */
4440       stmtStores
4441          = toBool( st->tag == Ist_Store
4442                    || st->tag == Ist_Dirty
4443                    || st->tag == Ist_LLSC );
4444
4445       for (k = A_NENV-1; k >= 0; k--) {
4446          if (env[k].bindee == NULL)
4447             continue;
4448          /* Compare the actions of this stmt with the actions of
4449             binding 'k', to see if they invalidate the binding. */
4450          invalidateMe
4451             = toBool(
4452               /* a store invalidates loaded data */
4453               (env[k].doesLoad && stmtStores)
4454               /* a put invalidates get'd data */
4455               || (env[k].doesGet && stmtPuts)
4456               /* a put invalidates loaded data.  Note, we could do
4457                  much better here in the sense that we only need to
4458                  invalidate trees containing loads if the Put in
4459                  question is marked as requiring precise
4460                  exceptions. */
4461               || (env[k].doesLoad && stmtPuts)
4462               /* probably overly conservative: a memory bus event
4463                  invalidates absolutely everything, so that all
4464                  computation prior to it is forced to complete before
4465                  proceeding with the event (fence,lock,unlock). */
4466               || st->tag == Ist_MBE
4467               /* also be (probably overly) paranoid re AbiHints */
4468               || st->tag == Ist_AbiHint
4469               );
4470          if (invalidateMe) {
4471             bb->stmts[j] = IRStmt_WrTmp( env[k].binder, env[k].bindee );
4472             j++;
4473             vassert(j <= i);
4474             env[k].bindee = NULL;
4475          }
4476       }
4477
4478       /* Slide in-use entries in env up to the front */
4479       m = 0;
4480       for (k = 0; k < A_NENV; k++) {
4481          if (env[k].bindee != NULL) {
4482             env[m] = env[k];
4483             m++;
4484          }
4485       }
4486       for (m = m; m < A_NENV; m++) {
4487          env[m].bindee = NULL;
4488       }
4489
4490       /* finally, emit the substituted statement */
4491       bb->stmts[j] = st2;
4492       /* vex_printf("**2  "); ppIRStmt(bb->stmts[j]); vex_printf("\n"); */
4493       j++;
4494
4495       vassert(j <= i+1);
4496    } /* for each stmt in the original bb ... */
4497
4498    /* Finally ... substitute the ->next field as much as possible, and
4499       dump any left-over bindings.  Hmm.  Perhaps there should be no
4500       left over bindings?  Or any left-over bindings are
4501       by definition dead? */
4502    bb->next = atbSubst_Expr(env, bb->next);
4503    bb->stmts_used = j;
4504 }
4505
4506
4507 /*---------------------------------------------------------------*/
4508 /*--- iropt main                                              ---*/
4509 /*---------------------------------------------------------------*/
4510
4511 static Bool iropt_verbose = False; /* True; */
4512
4513
4514 /* Do a simple cleanup pass on bb.  This is: redundant Get removal,
4515    redundant Put removal, constant propagation, dead code removal,
4516    clean helper specialisation, and dead code removal (again).
4517 */
4518
4519
4520 static
4521 IRSB* cheap_transformations (
4522          IRSB* bb,
4523          IRExpr* (*specHelper) (HChar*, IRExpr**, IRStmt**, Int),
4524          Bool (*preciseMemExnsFn)(Int,Int)
4525       )
4526 {
4527    redundant_get_removal_BB ( bb );
4528    if (iropt_verbose) {
4529       vex_printf("\n========= REDUNDANT GET\n\n" );
4530       ppIRSB(bb);
4531    }
4532
4533    redundant_put_removal_BB ( bb, preciseMemExnsFn );
4534    if (iropt_verbose) {
4535       vex_printf("\n========= REDUNDANT PUT\n\n" );
4536       ppIRSB(bb);
4537    }
4538
4539    bb = cprop_BB ( bb );
4540    if (iropt_verbose) {
4541       vex_printf("\n========= CPROPD\n\n" );
4542       ppIRSB(bb);
4543    }
4544
4545    do_deadcode_BB ( bb );
4546    if (iropt_verbose) {
4547       vex_printf("\n========= DEAD\n\n" );
4548       ppIRSB(bb);
4549    }
4550
4551    bb = spec_helpers_BB ( bb, specHelper );
4552    do_deadcode_BB ( bb );
4553    if (iropt_verbose) {
4554       vex_printf("\n========= SPECd \n\n" );
4555       ppIRSB(bb);
4556    }
4557
4558    return bb;
4559 }
4560
4561
4562 /* Do some more expensive transformations on bb, which are aimed at
4563    optimising as much as possible in the presence of GetI and PutI.  */
4564
4565 static
4566 IRSB* expensive_transformations( IRSB* bb )
4567 {
4568    (void)do_cse_BB( bb );
4569    collapse_AddSub_chains_BB( bb );
4570    do_redundant_GetI_elimination( bb );
4571    do_redundant_PutI_elimination( bb );
4572    do_deadcode_BB( bb );
4573    return bb;
4574 }
4575
4576
4577 /* Scan a flattened BB to look for signs that more expensive
4578    optimisations might be useful:
4579    - find out if there are any GetIs and PutIs
4580    - find out if there are any floating or vector-typed temporaries
4581 */
4582
4583 static void considerExpensives ( /*OUT*/Bool* hasGetIorPutI,
4584                                  /*OUT*/Bool* hasVorFtemps,
4585                                  IRSB* bb )
4586 {
4587    Int      i, j;
4588    IRStmt*  st;
4589    IRDirty* d;
4590    IRCAS*   cas;
4591
4592    *hasGetIorPutI = False;
4593    *hasVorFtemps  = False;
4594
4595    for (i = 0; i < bb->stmts_used; i++) {
4596       st = bb->stmts[i];
4597       switch (st->tag) {
4598          case Ist_AbiHint:
4599             vassert(isIRAtom(st->Ist.AbiHint.base));
4600             vassert(isIRAtom(st->Ist.AbiHint.nia));
4601             break;
4602          case Ist_PutI:
4603             *hasGetIorPutI = True;
4604             break;
4605          case Ist_WrTmp:
4606             if (st->Ist.WrTmp.data->tag == Iex_GetI)
4607                *hasGetIorPutI = True;
4608             switch (typeOfIRTemp(bb->tyenv, st->Ist.WrTmp.tmp)) {
4609                case Ity_I1: case Ity_I8: case Ity_I16:
4610                case Ity_I32: case Ity_I64: case Ity_I128:
4611                   break;
4612                case Ity_F32: case Ity_F64: case Ity_F128: case Ity_V128:
4613                   *hasVorFtemps = True;
4614                   break;
4615                default:
4616                   goto bad;
4617             }
4618             break;
4619          case Ist_Put:
4620             vassert(isIRAtom(st->Ist.Put.data));
4621             break;
4622          case Ist_Store:
4623             vassert(isIRAtom(st->Ist.Store.addr));
4624             vassert(isIRAtom(st->Ist.Store.data));
4625             break;
4626          case Ist_CAS:
4627             cas = st->Ist.CAS.details;
4628             vassert(isIRAtom(cas->addr));
4629             vassert(cas->expdHi == NULL || isIRAtom(cas->expdHi));
4630             vassert(isIRAtom(cas->expdLo));
4631             vassert(cas->dataHi == NULL || isIRAtom(cas->dataHi));
4632             vassert(isIRAtom(cas->dataLo));
4633             break;
4634          case Ist_LLSC:
4635             vassert(isIRAtom(st->Ist.LLSC.addr));
4636             if (st->Ist.LLSC.storedata)
4637                vassert(isIRAtom(st->Ist.LLSC.storedata));
4638             break;
4639          case Ist_Dirty:
4640             d = st->Ist.Dirty.details;
4641             vassert(isIRAtom(d->guard));
4642             for (j = 0; d->args[j]; j++)
4643                vassert(isIRAtom(d->args[j]));
4644             if (d->mFx != Ifx_None)
4645                vassert(isIRAtom(d->mAddr));
4646             break;
4647          case Ist_NoOp:
4648          case Ist_IMark:
4649          case Ist_MBE:
4650             break;
4651          case Ist_Exit:
4652             vassert(isIRAtom(st->Ist.Exit.guard));
4653             break;
4654          default:
4655          bad:
4656             ppIRStmt(st);
4657             vpanic("considerExpensives");
4658       }
4659    }
4660 }
4661
4662
4663 /* ---------------- The main iropt entry point. ---------------- */
4664
4665 /* exported from this file */
4666 /* Rules of the game:
4667
4668    - IRExpr/IRStmt trees should be treated as immutable, as they
4669      may get shared.  So never change a field of such a tree node;
4670      instead construct and return a new one if needed.
4671 */
4672
4673
4674 IRSB* do_iropt_BB(
4675          IRSB* bb0,
4676          IRExpr* (*specHelper) (HChar*, IRExpr**, IRStmt**, Int),
4677          Bool (*preciseMemExnsFn)(Int,Int),
4678          Addr64 guest_addr,
4679          VexArch guest_arch
4680       )
4681 {
4682    static Int n_total     = 0;
4683    static Int n_expensive = 0;
4684
4685    Bool hasGetIorPutI, hasVorFtemps;
4686    IRSB *bb, *bb2;
4687
4688    n_total++;
4689
4690    /* First flatten the block out, since all other
4691       phases assume flat code. */
4692
4693    bb = flatten_BB ( bb0 );
4694
4695    if (iropt_verbose) {
4696       vex_printf("\n========= FLAT\n\n" );
4697       ppIRSB(bb);
4698    }
4699
4700    /* If at level 0, stop now. */
4701    if (vex_control.iropt_level <= 0) return bb;
4702
4703    /* Now do a preliminary cleanup pass, and figure out if we also
4704       need to do 'expensive' optimisations.  Expensive optimisations
4705       are deemed necessary if the block contains any GetIs or PutIs.
4706       If needed, do expensive transformations and then another cheap
4707       cleanup pass. */
4708
4709    bb = cheap_transformations( bb, specHelper, preciseMemExnsFn );
4710
4711    if (guest_arch == VexArchARM) {
4712       /* Translating Thumb2 code produces a lot of chaff.  We have to
4713          work extra hard to get rid of it. */
4714       bb = cprop_BB(bb);
4715       bb = spec_helpers_BB ( bb, specHelper );
4716       redundant_put_removal_BB ( bb, preciseMemExnsFn );
4717       do_cse_BB( bb );
4718       do_deadcode_BB( bb );
4719    }
4720
4721    if (vex_control.iropt_level > 1) {
4722
4723       /* Peer at what we have, to decide how much more effort to throw
4724          at it. */
4725       considerExpensives( &hasGetIorPutI, &hasVorFtemps, bb );
4726
4727       if (hasVorFtemps && !hasGetIorPutI) {
4728          /* If any evidence of FP or Vector activity, CSE, as that
4729             tends to mop up all manner of lardy code to do with
4730             rounding modes.  Don't bother if hasGetIorPutI since that
4731             case leads into the expensive transformations, which do
4732             CSE anyway. */
4733          (void)do_cse_BB( bb );
4734          do_deadcode_BB( bb );
4735       }
4736
4737       if (hasGetIorPutI) {
4738          Bool cses;
4739          n_expensive++;
4740          if (DEBUG_IROPT)
4741             vex_printf("***** EXPENSIVE %d %d\n", n_total, n_expensive);
4742          bb = expensive_transformations( bb );
4743          bb = cheap_transformations( bb, specHelper, preciseMemExnsFn );
4744          /* Potentially common up GetIs */
4745          cses = do_cse_BB( bb );
4746          if (cses)
4747             bb = cheap_transformations( bb, specHelper, preciseMemExnsFn );
4748       }
4749
4750       /* Now have a go at unrolling simple (single-BB) loops.  If
4751          successful, clean up the results as much as possible. */
4752
4753       bb2 = maybe_loop_unroll_BB( bb, guest_addr );
4754       if (bb2) {
4755          bb = cheap_transformations( bb2, specHelper, preciseMemExnsFn );
4756          if (hasGetIorPutI) {
4757             bb = expensive_transformations( bb );
4758             bb = cheap_transformations( bb, specHelper, preciseMemExnsFn );
4759          } else {
4760             /* at least do CSE and dead code removal */
4761             do_cse_BB( bb );
4762             do_deadcode_BB( bb );
4763          }
4764          if (0) vex_printf("vex iropt: unrolled a loop\n");
4765       }
4766
4767    }
4768
4769    return bb;
4770 }
4771
4772
4773 /*---------------------------------------------------------------*/
4774 /*--- end                                            ir_opt.c ---*/
4775 /*---------------------------------------------------------------*/