priv/ir/iropt.c

/*---------------------------------------------------------------*/
/*---                                                         ---*/
/*--- This file (ir/iropt.c) is                               ---*/
/*--- Copyright (c) 2004 OpenWorks LLP.  All rights reserved. ---*/
/*---                                                         ---*/
/*---------------------------------------------------------------*/

#include "libvex_basictypes.h"
#include "libvex_ir.h"
#include "libvex.h"

#include "main/vex_util.h"
#include "ir/iropt.h"

/* Set to 1 for lots of debugging output. */
#define DEBUG_IROPT 0


/*---------------------------------------------------------------*/
/*--- Should be made public (to vex)                          ---*/
/*---------------------------------------------------------------*/

static Int sizeofIRType ( IRType ty )
{
   switch (ty) {
      case Ity_I8:  return 1;
      case Ity_I16: return 2;
      case Ity_I32: return 4;
      default: vex_printf("\n"); ppIRType(ty); vex_printf("\n");
               vpanic("sizeofIType");
   }
}


/*---------------------------------------------------------------*/
/*--- Finite mappery, of a sort                               ---*/
/*---------------------------------------------------------------*/

/* General map from 64-bit thing 64-bit thing.  Could be done faster
   by hashing. */

typedef
   struct {
      Bool*  inuse;
      ULong* key;
      ULong* val;
      Int    size;
      Int    used;
   }
   Hash64;

static Hash64* newH64 ( void )
{
   Hash64* h = LibVEX_Alloc(sizeof(Hash64));
   h->size   = 8;
   h->used   = 0;
   h->inuse  = LibVEX_Alloc(h->size * sizeof(Bool));
   h->key    = LibVEX_Alloc(h->size * sizeof(ULong));
   h->val    = LibVEX_Alloc(h->size * sizeof(ULong));
   return h;
}


/* Look up key in the map. */

static Bool lookupH64 ( Hash64* h, /*OUT*/ULong* val, ULong key )
{
   Int i;
   //vex_printf("lookupH64(%llx)\n", key );
   for (i = 0; i < h->used; i++) {
      if (h->inuse[i] && h->key[i] == key) {
         if (val)
            *val = h->val[i];
         return True;
      }
   }
   return False;
}


/* Delete any binding for key in h. */

static void delFromH64 ( Hash64* h, ULong key )
{
   Int i;
   for (i = 0; i < h->used; i++) {
      if (h->inuse[i] && h->key[i] == key) {
         h->inuse[i] = False;
         return;
      }
   }
}



/* Add key->val to the map.  Replaces any existing binding for key. */

static void addToH64 ( Hash64* h, ULong key, ULong val )
{
   Int i, j;

   //vex_printf("addToH64(%llx, %llx)\n", key, val);
   /* Find and replace existing binding, if any. */
   for (i = 0; i < h->used; i++) {
      if (h->inuse[i] && h->key[i] == key) {
         h->val[i] = val;
         return;
      }
   }

   /* Ensure a space is available. */
   if (h->used == h->size) {
      /* Copy into arrays twice the size. */
      Bool*  inuse2 = LibVEX_Alloc(2 * h->size * sizeof(Bool));
      ULong* key2   = LibVEX_Alloc(2 * h->size * sizeof(ULong));
      ULong* val2   = LibVEX_Alloc(2 * h->size * sizeof(ULong));
      for (i = j = 0; i < h->size; i++) {
         if (!h->inuse[i]) continue;
         inuse2[j] = True;
         key2[j] = h->key[i];
         val2[j] = h->val[i];
         j++;
      }
      h->used = j;
      h->size *= 2;
      h->inuse = inuse2;
      h->key = key2;
      h->val = val2;
   }

   /* Finally, add it. */
   vassert(h->used < h->size);
   h->inuse[h->used] = True;
   h->key[h->used] = key;
   h->val[h->used] = val;
   h->used++;
}


/*---------------------------------------------------------------*/
/*--- Flattening out a BB into pure SSA form                  ---*/
/*---------------------------------------------------------------*/

/* Clone the NULL-terminated vector of IRExpr*s attached to a
   CCall. */

static IRExpr** copyIexCCallArgs ( IRExpr** vec )
{
   Int      i;
   IRExpr** newvec;
   for (i = 0; vec[i]; i++)
      ;
   newvec = LibVEX_Alloc((i+1)*sizeof(IRExpr*));
   for (i = 0; vec[i]; i++)
      newvec[i] = vec[i];
   newvec[i] = NULL;
   return newvec;
}


/* Flatten out 'ex' so it is atomic, returning a new expression with
   the same value, after having appended extra IRTemp assignments to
   the end of 'bb'. */

static IRExpr* flatten_Expr ( IRBB* bb, IRExpr* ex )
{
   Int i;
   IRExpr** newargs;
   IRType ty = typeOfIRExpr(bb->tyenv, ex);
   IRTemp t1;

   switch (ex->tag) {

      case Iex_GetI:
         t1 = newIRTemp(bb->tyenv, ty);
         addStmtToIRBB(bb, IRStmt_Tmp(t1,
            IRExpr_GetI(flatten_Expr(bb, ex->Iex.GetI.offset),
                        ex->Iex.GetI.ty,
                        ex->Iex.GetI.minoff,
                        ex->Iex.GetI.maxoff)));
         return IRExpr_Tmp(t1);

      case Iex_Get:
         t1 = newIRTemp(bb->tyenv, ty);
         addStmtToIRBB(bb, 
            IRStmt_Tmp(t1, ex));
         return IRExpr_Tmp(t1);

      case Iex_Binop:
         t1 = newIRTemp(bb->tyenv, ty);
         addStmtToIRBB(bb, IRStmt_Tmp(t1, 
            IRExpr_Binop(ex->Iex.Binop.op,
                         flatten_Expr(bb, ex->Iex.Binop.arg1),
                         flatten_Expr(bb, ex->Iex.Binop.arg2))));
         return IRExpr_Tmp(t1);

      case Iex_Unop:
         t1 = newIRTemp(bb->tyenv, ty);
         addStmtToIRBB(bb, IRStmt_Tmp(t1, 
            IRExpr_Unop(ex->Iex.Unop.op,
                        flatten_Expr(bb, ex->Iex.Unop.arg))));
         return IRExpr_Tmp(t1);

      case Iex_LDle:
         t1 = newIRTemp(bb->tyenv, ty);
         addStmtToIRBB(bb, IRStmt_Tmp(t1,
            IRExpr_LDle(ex->Iex.LDle.ty, 
                        flatten_Expr(bb, ex->Iex.LDle.addr))));
         return IRExpr_Tmp(t1);

      case Iex_CCall:
         newargs = copyIexCCallArgs(ex->Iex.CCall.args);
         for (i = 0; newargs[i]; i++)
            newargs[i] = flatten_Expr(bb, newargs[i]);
         t1 = newIRTemp(bb->tyenv, ty);
         addStmtToIRBB(bb, IRStmt_Tmp(t1,
            IRExpr_CCall(ex->Iex.CCall.name,
                         ex->Iex.CCall.retty,
                         newargs)));
         return IRExpr_Tmp(t1);

      case Iex_Mux0X:
         t1 = newIRTemp(bb->tyenv, ty);
         addStmtToIRBB(bb, IRStmt_Tmp(t1,
            IRExpr_Mux0X(flatten_Expr(bb, ex->Iex.Mux0X.cond),
                         flatten_Expr(bb, ex->Iex.Mux0X.expr0),
                         flatten_Expr(bb, ex->Iex.Mux0X.exprX))));
         return IRExpr_Tmp(t1);

      case Iex_Const:
      case Iex_Tmp:
         return ex;

      default:
         vex_printf("\n");
         ppIRExpr(ex); 
         vex_printf("\n");
         vpanic("flatten_Expr");
   }
}


/* Append a completely flattened form of 'st' to the end of 'bb'. */

static void flatten_Stmt ( IRBB* bb, IRStmt* st )
{
   IRExpr *e1, *e2;
   switch (st->tag) {
      case Ist_Put:
         e1 = flatten_Expr(bb, st->Ist.Put.expr);
         addStmtToIRBB(bb, IRStmt_Put(st->Ist.Put.offset, e1));
         break;
      case Ist_PutI:
         e1 = flatten_Expr(bb, st->Ist.PutI.offset);
         e2 = flatten_Expr(bb, st->Ist.PutI.expr);
         addStmtToIRBB(bb, IRStmt_PutI(e1, e2, 
                                       st->Ist.PutI.minoff,
                                       st->Ist.PutI.maxoff));
         break;
      case Ist_Tmp:
         e1 = flatten_Expr(bb, st->Ist.Tmp.expr);
         addStmtToIRBB(bb, IRStmt_Tmp(st->Ist.Tmp.tmp, e1));
         break;
      case Ist_STle:
         e1 = flatten_Expr(bb, st->Ist.STle.addr);
         e2 = flatten_Expr(bb, st->Ist.STle.data);
         addStmtToIRBB(bb, IRStmt_STle(e1,e2));
         break;
      case Ist_Exit:
         e1 = flatten_Expr(bb, st->Ist.Exit.cond);
         addStmtToIRBB(bb, IRStmt_Exit(e1, st->Ist.Exit.dst));
         break;
      default:
         vex_printf("\n");
         ppIRStmt(st); 
         vex_printf("\n");
         vpanic("flatten_Stmt");
   }
}

static IRBB* flatten_BB ( IRBB* in )
{
   Int   i;
   IRBB* out;
   out = emptyIRBB();
   out->tyenv = copyIRTypeEnv( in->tyenv );
   for (i = 0; i < in->stmts_used; i++)
      flatten_Stmt( out, in->stmts[i] );
   out->next     = flatten_Expr( out, in->next );
   out->jumpkind = in->jumpkind;
   return out;
}



/*---------------------------------------------------------------*/
/*--- Constant propagation and folding                        ---*/
/*---------------------------------------------------------------*/

/* The env in this section is a map from IRTemp to IRExpr*. */

/* Are both expressions simply the same IRTemp ? */
static Bool sameIRTemps ( IRExpr* e1, IRExpr* e2 )
{
   return e1->tag == Iex_Tmp
          && e2->tag == Iex_Tmp
          && e1->Iex.Tmp.tmp == e2->Iex.Tmp.tmp;
}

static IRExpr* fold_Expr ( IRExpr* e )
{
   Int     shift;
   IRExpr* e2 = e; /* e2 is the result of folding e, if possible */

   /* UNARY ops */
   if (e->tag == Iex_Unop
       && e->Iex.Unop.arg->tag == Iex_Const) {
      switch (e->Iex.Unop.op) {
         case Iop_8Uto32:
            e2 = IRExpr_Const(IRConst_U32(
                    0xFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U8));
            break;
         case Iop_16Uto32:
            e2 = IRExpr_Const(IRConst_U32(
                    0xFFFF & e->Iex.Unop.arg->Iex.Const.con->Ico.U16));
            break;
         default: 
            goto unhandled;
      }
   }

   /* BINARY ops */
   if (e->tag == Iex_Binop) {
      if (e->Iex.Binop.arg1->tag == Iex_Const
          && e->Iex.Binop.arg2->tag == Iex_Const) {
         /* cases where both args are consts */
         switch (e->Iex.Binop.op) {
            case Iop_And8:
               e2 = IRExpr_Const(IRConst_U8(0xFF & 
                       (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
                        & e->Iex.Binop.arg2->Iex.Const.con->Ico.U8)));
               break;
            case Iop_Sub8:
               e2 = IRExpr_Const(IRConst_U8(0xFF & 
                       (e->Iex.Binop.arg1->Iex.Const.con->Ico.U8
                        - e->Iex.Binop.arg2->Iex.Const.con->Ico.U8)));
               break;
            case Iop_Sub32:
               e2 = IRExpr_Const(IRConst_U32(
                       (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
                        - e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
               break;
            case Iop_Add32:
               e2 = IRExpr_Const(IRConst_U32(
                       (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
                        + e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
               break;
            case Iop_And32:
               e2 = IRExpr_Const(IRConst_U32(
                       (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
                        & e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
               break;
            case Iop_Or32:
               e2 = IRExpr_Const(IRConst_U32(
                       (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
                        | e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
               break;
            case Iop_Mul32:
               e2 = IRExpr_Const(IRConst_U32(
                       (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
                        * e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
               break;
            case Iop_Shl32:
               vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
               shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
               if (shift >= 0 && shift <= 31)
                  e2 = IRExpr_Const(IRConst_U32(
                          (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
                           << shift)));
               break;
            case Iop_Sar32: {
               /* paranoid ... */
               /*signed*/ Int s32;
               vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
               s32   = (Int)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32);
               shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
               if (shift >= 0 && shift <= 31) {
                  s32 >>=/*signed*/ shift;
                  e2 = IRExpr_Const(IRConst_U32((UInt)s32));
               }
               break;
            }
            case Iop_Shr32: {
               /* paranoid ... */
               /*unsigned*/ UInt s32;
               vassert(e->Iex.Binop.arg2->Iex.Const.con->tag == Ico_U8);
               s32   = (Int)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32);
               shift = (Int)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U8);
               if (shift >= 0 && shift <= 31) {
                  s32 >>=/*unsigned*/ shift;
                  e2 = IRExpr_Const(IRConst_U32((UInt)s32));
               }
               break;
            }
            case Iop_CmpEQ32:
               e2 = IRExpr_Const(IRConst_Bit(
                       (e->Iex.Binop.arg1->Iex.Const.con->Ico.U32
                        == e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)));
               break;
            case Iop_32HLto64:
               e2 = IRExpr_Const(IRConst_U64(
                       (((ULong)(e->Iex.Binop.arg1->Iex.Const.con->Ico.U32)) << 32)
                       | ((ULong)(e->Iex.Binop.arg2->Iex.Const.con->Ico.U32)) 
                    ));
               break;
           default:
              goto unhandled;
         }

      } else {

         /* other cases (identities, etc) */
         /* Add32(x,0) ==> x */
         if (e->Iex.Binop.op == Iop_Add32
             && e->Iex.Binop.arg2->tag == Iex_Const
             && e->Iex.Binop.arg2->Iex.Const.con->Ico.U32 == 0) {
            e2 = e->Iex.Binop.arg1;
         } else

         /* And8/16/32(t,t) ==> t, for some IRTemp t */
         if ((e->Iex.Binop.op == Iop_And32
              || e->Iex.Binop.op == Iop_And16
              || e->Iex.Binop.op == Iop_And8)
             && sameIRTemps(e->Iex.Binop.arg1, e->Iex.Binop.arg2)) {
            e2 = e->Iex.Binop.arg1;
	 }

      }
   }

   /* Mux0X */
   if (e->tag == Iex_Mux0X
       && e->Iex.Mux0X.cond->tag == Iex_Const) {
      Bool zero;
      /* assured us by the IR type rules */
      vassert(e->Iex.Mux0X.cond->Iex.Const.con->tag == Ico_U8);
      zero = 0 == e->Iex.Mux0X.cond->Iex.Const.con->Ico.U8;
      e2 = zero ? e->Iex.Mux0X.expr0 : e->Iex.Mux0X.exprX;
   }

   if (DEBUG_IROPT && e2 != e) {
      vex_printf("FOLD: "); 
      ppIRExpr(e); vex_printf("  ->  ");
      ppIRExpr(e2); vex_printf("\n");
   }

   return e2;

 unhandled:
   vex_printf("\n\n");
   ppIRExpr(e);
   vpanic("fold_Expr: no rule for the above");
}


static Bool isAtom ( IRExpr* e )
{
   return e->tag == Iex_Tmp || e->tag == Iex_Const;
}


/* Apply the subst to a simple 1-level expression -- guaranteed to be
   1-level due to previous flattening pass. */

static IRExpr* subst_Expr ( Hash64* env, IRExpr* ex )
{
   if (ex->tag == Iex_Tmp) {
      ULong res;
      if (lookupH64(env, &res, (ULong)ex->Iex.Tmp.tmp)) {
         return (IRExpr*)res;
      } else {
         /* not bound in env */
         return ex;
      }
   }

   if (ex->tag == Iex_Const)
      return ex;
   if (ex->tag == Iex_Get)
      return ex;

   if (ex->tag == Iex_GetI) {
      vassert(isAtom(ex->Iex.GetI.offset));
      return IRExpr_GetI(
         subst_Expr(env, ex->Iex.GetI.offset),
         ex->Iex.GetI.ty,
         ex->Iex.GetI.minoff,
         ex->Iex.GetI.maxoff
      );
   }

   if (ex->tag == Iex_Binop) {
      vassert(isAtom(ex->Iex.Binop.arg1));
      vassert(isAtom(ex->Iex.Binop.arg2));
      return IRExpr_Binop(
                ex->Iex.Binop.op,
                subst_Expr(env, ex->Iex.Binop.arg1),
                subst_Expr(env, ex->Iex.Binop.arg2)
             );
   }

   if (ex->tag == Iex_Unop) {
      vassert(isAtom(ex->Iex.Unop.arg));
      return IRExpr_Unop(
                ex->Iex.Unop.op,
                subst_Expr(env, ex->Iex.Unop.arg)
             );
   }

   if (ex->tag == Iex_LDle) {
      vassert(isAtom(ex->Iex.LDle.addr));
      return IRExpr_LDle(
                ex->Iex.LDle.ty,
                subst_Expr(env, ex->Iex.LDle.addr)
             );
   }

   if (ex->tag == Iex_CCall) {
      Int      i;
      IRExpr** args2 = copyIexCCallArgs ( ex->Iex.CCall.args );
      for (i = 0; args2[i]; i++) {
         vassert(isAtom(args2[i]));
         args2[i] = subst_Expr(env, args2[i]);
      }
      return IRExpr_CCall(
                ex->Iex.CCall.name,
                ex->Iex.CCall.retty,
                args2 
             );
   }

   if (ex->tag == Iex_Mux0X) {
      vassert(isAtom(ex->Iex.Mux0X.cond));
      vassert(isAtom(ex->Iex.Mux0X.expr0));
      vassert(isAtom(ex->Iex.Mux0X.exprX));
      return IRExpr_Mux0X(
                subst_Expr(env, ex->Iex.Mux0X.cond),
                subst_Expr(env, ex->Iex.Mux0X.expr0),
                subst_Expr(env, ex->Iex.Mux0X.exprX)
             );
   }

   vex_printf("\n\n");
   ppIRExpr(ex);
   vpanic("subst_Expr");
}


/* Apply the subst to stmt, then fold the result as much as possible.
   Much simplified due to stmt being previously flattened.  Returning
   NULL means the statement has been turned into a no-op. */

static IRStmt* subst_and_fold_Stmt ( Hash64* env, IRStmt* st )
{
#  if 0
   vex_printf("\nsubst and fold stmt\n");
   ppIRStmt(st);
   vex_printf("\n");
#  endif

   if (st->tag == Ist_Put) {
      vassert(isAtom(st->Ist.Put.expr));
      return IRStmt_Put(
                st->Ist.Put.offset, 
                fold_Expr(subst_Expr(env, st->Ist.Put.expr)) 
             );
   }

   if (st->tag == Ist_PutI) {
      vassert(isAtom(st->Ist.PutI.offset));
      vassert(isAtom(st->Ist.PutI.expr));
      return IRStmt_PutI(
                fold_Expr(subst_Expr(env, st->Ist.PutI.offset)),
                fold_Expr(subst_Expr(env, st->Ist.PutI.expr)),
                st->Ist.PutI.minoff,
                st->Ist.PutI.maxoff
             );
   }

   if (st->tag == Ist_Tmp) {
      /* This is the one place where an expr (st->Ist.Tmp.expr) is
         allowed to be more than just a constant or a tmp. */
      return IRStmt_Tmp(
                st->Ist.Tmp.tmp,
                fold_Expr(subst_Expr(env, st->Ist.Tmp.expr))
             );
   }

   if (st->tag == Ist_STle) {
      vassert(isAtom(st->Ist.STle.addr));
      vassert(isAtom(st->Ist.STle.data));
      return IRStmt_STle(
                fold_Expr(subst_Expr(env, st->Ist.STle.addr)),
                fold_Expr(subst_Expr(env, st->Ist.STle.data))
             );
   }

   if (st->tag == Ist_Exit) {
      IRExpr* fcond;
      vassert(isAtom(st->Ist.Exit.cond));
      fcond = fold_Expr(subst_Expr(env, st->Ist.Exit.cond));
      if (fcond->tag == Iex_Const) {
         /* Interesting.  The condition on this exit has folded down to
            a constant. */
         vassert(fcond->Iex.Const.con->tag == Ico_Bit);
         if (fcond->Iex.Const.con->Ico.Bit == False) {
            /* exit is never going to happen, so dump the statement. */
            return NULL;
         } else {
            vassert(fcond->Iex.Const.con->Ico.Bit == True);
            /* Hmmm.  The exit has become unconditional.  Leave it as
               it is for now, since we'd have to truncate the BB at
               this point, which is tricky. */
            /* fall out into the reconstruct-the-exit code. */
            vex_printf("subst_and_fold_Stmt: IRStmt_Exit became unconditional\n");
         }
      }
      return IRStmt_Exit(fcond,st->Ist.Exit.dst);
   }

   vex_printf("\n");
   ppIRStmt(st);
   vpanic("subst_and_fold_Stmt");
}


static IRBB* cprop_BB ( IRBB* in )
{
   Int     i;
   IRBB*   out;
   Hash64* env;
   IRStmt* st2;

   out = emptyIRBB();
   out->tyenv = copyIRTypeEnv( in->tyenv );

   /* Set up the env with which travels forward.  This holds a
      substitution, mapping IRTemps to atoms, that is, IRExprs which
      are either IRTemps or IRConsts.  Thus, copy and constant
      propagation is done.  The environment is to be applied as we
      move along.  Keys are IRTemps.  Values are IRExpr*s.
   */
   env = newH64();

   /* For each original SSA-form stmt ... */
   for (i = 0; i < in->stmts_used; i++) {

      /* First apply the substitution to the current stmt.  This
         propagates in any constants and tmp-tmp assignments
         accumulated prior to this point.  As part of the subst_Stmt
         call, also then fold any constant expressions resulting. */

      st2 = in->stmts[i];

      /* perhaps st2 is already a no-op? */
      if (!st2) continue;

      st2 = subst_and_fold_Stmt( env, st2 );

      /* If the statement has been folded into a no-op, forget it. */
      if (!st2) continue;

      /* Now consider what the stmt looks like.  If it's of the form
         't = const' or 't1 = t2', add it to the running environment
         and not to the output BB.  Otherwise, add it to the output
         BB. */

      if (st2->tag == Ist_Tmp && st2->Ist.Tmp.expr->tag == Iex_Const) {
         /* 't = const' -- add to env.  
             The pair (IRTemp, IRExpr*) is added. */
         addToH64(env, (ULong)(st2->Ist.Tmp.tmp),
                       (ULong)(st2->Ist.Tmp.expr) );
      }
      else
      if (st2->tag == Ist_Tmp && st2->Ist.Tmp.expr->tag == Iex_Tmp) {
         /* 't1 = t2' -- add to env.  
             The pair (IRTemp, IRExpr*) is added. */
         addToH64(env, (ULong)(st2->Ist.Tmp.tmp),
                       (ULong)(st2->Ist.Tmp.expr) );
      }
      else {
         /* Not interesting, copy st2 into the output block. */
         addStmtToIRBB( out, st2 );
      }
   }

   out->next     = subst_Expr( env, in->next );
   out->jumpkind = in->jumpkind;
   return out;
}



/*---------------------------------------------------------------*/
/*--- Dead code (t = E) removal                               ---*/
/*---------------------------------------------------------------*/

/* The type of the Hash64 map is: a map from IRTemp to nothing
   -- really just operating a set or IRTemps.
*/

static void addUses_Expr ( Hash64* set, IRExpr* e )
{
   Int i;
   switch (e->tag) {
      case Iex_GetI:
         addUses_Expr(set, e->Iex.GetI.offset);
         return;
      case Iex_Mux0X:
         addUses_Expr(set, e->Iex.Mux0X.cond);
         addUses_Expr(set, e->Iex.Mux0X.expr0);
         addUses_Expr(set, e->Iex.Mux0X.exprX);
         return;
      case Iex_CCall:
         for (i = 0; e->Iex.CCall.args[i]; i++)
            addUses_Expr(set, e->Iex.CCall.args[i]);
         return;
      case Iex_LDle:
         addUses_Expr(set, e->Iex.LDle.addr);
         return;
      case Iex_Binop:
         addUses_Expr(set, e->Iex.Binop.arg1);
         addUses_Expr(set, e->Iex.Binop.arg2);
         return;
      case Iex_Unop:
         addUses_Expr(set, e->Iex.Unop.arg);
         return;
      case Iex_Tmp:
         addToH64(set, (ULong)(e->Iex.Tmp.tmp), 0);
         return;
      case Iex_Const:
      case Iex_Get:
         return;
      default:
         vex_printf("\n");
         ppIRExpr(e);
         vpanic("addUses_Expr");
   }
}

static void addUses_Stmt ( Hash64* set, IRStmt* st )
{
   switch (st->tag) {
      case Ist_PutI:
         addUses_Expr(set, st->Ist.PutI.offset);
         addUses_Expr(set, st->Ist.PutI.expr);
         return;
      case Ist_Exit:
         addUses_Expr(set, st->Ist.Exit.cond);
         return;
      case Ist_Tmp:
         addUses_Expr(set, st->Ist.Tmp.expr);
         return;
      case Ist_Put:
         addUses_Expr(set, st->Ist.Put.expr);
         return;
      case Ist_STle:
         addUses_Expr(set, st->Ist.STle.addr);
         addUses_Expr(set, st->Ist.STle.data);
         return;
      default:
         vex_printf("\n");
         ppIRStmt(st);
         vpanic("addUses_Stmt");
      }
}



/* Note, this destructively modifies the given IRBB. */

/* Scan backwards through statements, carrying a set of IRTemps which
   are known to be used after the current point.  On encountering 't =
   E', delete the binding if it is not used.  Otherwise, add any temp
   uses to the set and keep on moving backwards. */

static void dead_BB ( IRBB* bb )
{
   Int     i;
   Hash64* set = newH64();
   IRStmt* st;

   /* start off by recording IRTemp uses in the next field. */
   addUses_Expr(set, bb->next);

   /* Work backwards through the stmts */
   for (i = bb->stmts_used-1; i >= 0; i--) {
      st = bb->stmts[i];
      if (!st)
         continue;
      if (st->tag == Ist_Tmp
          && !lookupH64(set, NULL, (ULong)(st->Ist.Tmp.tmp))) {
          /* it's an IRTemp which never got used.  Delete it. */
         if (DEBUG_IROPT) {
            vex_printf("DEAD: ");
            ppIRStmt(st);
            vex_printf("\n");
         }
         bb->stmts[i] = NULL;
      } else {
         /* Note any IRTemp uses made by the current statement. */
         addUses_Stmt(set, st);
      }
   }
}


/*---------------------------------------------------------------*/
/*--- In-place removal of redundant GETs                      ---*/
/*---------------------------------------------------------------*/

/* Scan forwards, building up an environment binding (min offset, max
   offset) pairs to values, which will either be temps or constants.

   On seeing 't = Get(minoff,maxoff)', look up (minoff,maxoff) in the
   env and if it matches, replace the Get with the stored value.  If
   there is no match, add a (minoff,maxoff) :-> t binding.

   On seeing 'Put (minoff,maxoff) = t or c', first remove in the env
   any binding which fully or partially overlaps with (minoff,maxoff).
   Then add a new (minoff,maxoff) :-> t or c binding.  */

/* Create keys, of the form ((minoffset << 16) | maxoffset). */

static UInt mk_key_GetPut ( Int offset, IRType ty )
{
   /* offset should fit in 16 bits. */
   UInt minoff = offset;
   UInt maxoff = minoff + sizeofIRType(ty) - 1;
   vassert((minoff & 0xFFFF0000) == 0);
   vassert((maxoff & 0xFFFF0000) == 0);
   return (minoff << 16) | maxoff;
}

static UInt mk_key_GetIPutI ( UShort minoff16, UShort maxoff16 )
{
   UInt minoff = (UInt)minoff16;
   UInt maxoff = (UInt)maxoff16;
   return (minoff << 16) | maxoff;
}

/* Supposing h has keys of the form generated by mk_key_GetPut and
   mk_key_GetIPutI, invalidate any key which overlaps (k_lo
   .. k_hi). 
*/

static void invalidateOverlaps ( Hash64* h, UInt k_lo, UInt k_hi )
{
   Int  j;
   UInt e_lo, e_hi;
   vassert(k_lo <= k_hi);
   /* invalidate any env entries which in any way overlap (k_lo
      .. k_hi) */
   /* vex_printf("invalidate %d .. %d\n", k_lo, k_hi ); */

   for (j = 0; j < h->used; j++) {
      if (!h->inuse[j]) 
         continue;
      e_lo = (((UInt)h->key[j]) >> 16) & 0xFFFF;
      e_hi = ((UInt)h->key[j]) & 0xFFFF;
      vassert(e_lo <= e_hi);
      if (e_hi < k_lo || k_hi < e_lo)
         continue; /* no overlap possible */
      else
         /* overlap; invalidate */
         h->inuse[j] = False;
   }
}


static void redundant_get_removal_BB ( IRBB* bb )
{
   Hash64* env = newH64();
   UInt    key;
   Int     i;
   Bool    isPut;
   ULong   val;

   for (i = 0; i < bb->stmts_used; i++) {
      IRStmt* st = bb->stmts[i];

      if (!st)
         continue;

      /* Deal with Gets */
      if (st->tag == Ist_Tmp
          && st->Ist.Tmp.expr->tag == Iex_Get) {
         /* st is 't = Get(...)'.  Look up in the environment and see
            if the Get can be replaced. */
         IRExpr* get = st->Ist.Tmp.expr;
         key = (ULong)mk_key_GetPut( get->Iex.Get.offset, 
                                     get->Iex.Get.ty );
         if (lookupH64(env, &val, (ULong)key)) {
            /* found it */
            if (DEBUG_IROPT) {
               vex_printf("rGET: "); ppIRExpr(get);
               vex_printf("  ->  "); ppIRExpr((IRExpr*)val);
               vex_printf("\n");
            }
            bb->stmts[i] = IRStmt_Tmp(st->Ist.Tmp.tmp,
                                      (IRExpr*)val);
         } else {
            /* Not found, but at least we know that t and the Get(...)
               are now associated.  So add a binding to reflect that
               fact. */
            addToH64( env, (ULong)key, 
                           (ULong)(IRExpr_Tmp(st->Ist.Tmp.tmp)) );
         }
      }

      /* Deal with Puts */
      switch (st->tag) {
         case Ist_Put: 
            isPut = True;
            key = mk_key_GetPut( st->Ist.Put.offset, 
                                 typeOfIRExpr(bb->tyenv,st->Ist.Put.expr) );
            break;
         case Ist_PutI:
            isPut = True;
            key = mk_key_GetIPutI( st->Ist.PutI.minoff, 
                                   st->Ist.PutI.maxoff );
            break;
         default: 
            isPut = False;
      }

      /* invalidate any env entries overlapped by this Put */
      if (isPut) {
         UInt k_lo, k_hi;
         k_lo = (key >> 16) & 0xFFFF;
         k_hi = key & 0xFFFF;
         invalidateOverlaps(env, k_lo, k_hi);
      }

      /* add this one to the env, if appropriate */
      if (st->tag == Ist_Put) {
         vassert(isAtom(st->Ist.Put.expr));
         addToH64( env, (ULong)key, (ULong)(st->Ist.Put.expr));
      }

   } /* for (i = 0; i < bb->stmts_used; i++) */

}


/*---------------------------------------------------------------*/
/*--- In-place removal of redundant PUTs                      ---*/
/*---------------------------------------------------------------*/

/* Find any Get uses in st and invalidate any partially or fully
   overlapping ranges listed in env.  Due to the flattening phase, the
   only stmt kind we expect to find a Get on is IRStmt_Tmp. */

static void handle_gets_Stmt ( Hash64* env, IRStmt* st )
{
   UInt    key;
   Bool    isGet;
   IRExpr* e;
   switch (st->tag) {

      /* This is the only interesting case.  Deal with Gets in the RHS
         expression. */
      case Ist_Tmp:
         e = st->Ist.Tmp.expr;
         switch (e->tag) {
            case Iex_Get:
               isGet = True;
               key = mk_key_GetPut ( e->Iex.Get.offset, e->Iex.Get.ty );
               break;
            case Iex_GetI:
               isGet = True;
               key = mk_key_GetIPutI ( e->Iex.GetI.minoff, e->Iex.GetI.maxoff );
               break;
            default: 
               isGet = False;
         }
         if (isGet) {
            UInt k_lo, k_hi;
            k_lo = (key >> 16) & 0xFFFF;
            k_hi = key & 0xFFFF;
            invalidateOverlaps(env, k_lo, k_hi);
         }
         break;

      /* all other cases are boring. */
      case Ist_STle:
         vassert(isAtom(st->Ist.STle.addr));
         vassert(isAtom(st->Ist.STle.data));
         return;

      case Ist_Exit:
         vassert(isAtom(st->Ist.Exit.cond));
         return;

      default:
         vex_printf("\n");
         ppIRStmt(st);
         vex_printf("\n");
         vpanic("handle_gets_Stmt");
   }
}


/* Scan backwards, building up a set of (min offset, max
   offset) pairs, indicating those parts of the guest state
   for which the next event is a write.

   On seeing a conditional exit, empty the set.

   On seeing 'Put (minoff,maxoff) = t or c', if (minoff,maxoff) is
   completely within the set, remove the Put.  Otherwise, add
   (minoff,maxoff) to the set.

   On seeing 'Get (minoff,maxoff)', remove any part of the set
   overlapping (minoff,maxoff).
*/

static void redundant_put_removal_BB ( IRBB* bb )
{
   Int     i, j;
   Bool    isPut;
   IRStmt* st;
   UInt    key;

   Hash64* env = newH64();
   for (i = bb->stmts_used-1; i >= 0; i--) {
      st = bb->stmts[i];

      /* Deal with conditional exits. */
      if (st->tag == Ist_Exit) {
         /* Since control may not get beyond this point, we must empty
            out the set, since we can no longer claim that the next
            event for any part of the guest state is definitely a
            write. */
         vassert(isAtom(st->Ist.Exit.cond));
         for (j = 0; j < env->used; j++)
            env->inuse[j] = False;
         continue;
      }

      /* Deal with Puts */
      switch (st->tag) {
         case Ist_Put: 
            isPut = True;
            key = mk_key_GetPut( st->Ist.Put.offset, 
                                 typeOfIRExpr(bb->tyenv,st->Ist.Put.expr) );
            vassert(isAtom(st->Ist.Put.expr));
            break;
         case Ist_PutI:
            isPut = True;
            key = mk_key_GetIPutI( st->Ist.PutI.minoff, 
                                   st->Ist.PutI.maxoff );
            vassert(isAtom(st->Ist.PutI.expr));
            break;
         default: 
            isPut = False;
      }
      if (isPut) {
         /* See if any single entry in env overlaps this Put.  This is
            simplistic in that the transformation is valid if, say, two
            or more entries in the env overlap this Put, but the use of
            lookupH64 will only find a single entry which exactly
            overlaps this Put.  This is suboptimal but safe. */
         if (lookupH64(env, NULL, (ULong)key)) {
            /* This Put is redundant because a later one will overwrite
               it.  So NULL (nop) it out. */
            if (DEBUG_IROPT) {
               vex_printf("rPUT: "); ppIRStmt(st);
               vex_printf("\n");
            }
            bb->stmts[i] = NULL;
         } else {
            /* We can't demonstrate that this Put is redundant, so add it
               to the running collection. */
            addToH64(env, (ULong)key, 0);
         }
         continue;
      }

      /* Deal with Gets.  These remove bits of the environment since
         appearance of a Get means that the next event for that slice
         of the guest state is no longer a write, but a read. */
      handle_gets_Stmt( env, st );
   }
}


/*---------------------------------------------------------------*/
/*--- Specialisation of helper function calls, in             ---*/
/*--- collaboration with the front end                        ---*/
/*---------------------------------------------------------------*/

static 
void spec_helpers_BB ( IRBB* bb,
                       IRExpr* (*specHelper) ( Char*, IRExpr**) )   
{
   Int i;
   IRStmt* st;
   IRExpr* ex;

   for (i = bb->stmts_used-1; i >= 0; i--) {
      st = bb->stmts[i];

      if (!st 
          || st->tag != Ist_Tmp
          || st->Ist.Tmp.expr->tag != Iex_CCall)
	continue;

      ex = (*specHelper)( st->Ist.Tmp.expr->Iex.CCall.name,
                          st->Ist.Tmp.expr->Iex.CCall.args );
      if (!ex)
	/* the front end can't think of a suitable replacement */
	continue;

      /* We got something better.  Install it in the bb. */
      bb->stmts[i]
         = IRStmt_Tmp(st->Ist.Tmp.tmp, ex);

      if (0) {
         vex_printf("SPEC: ");
         ppIRExpr(st->Ist.Tmp.expr);
         vex_printf("  -->  ");
         ppIRExpr(ex);
         vex_printf("\n");
      }
   }
}


/*---------------------------------------------------------------*/
/*--- The tree builder                                        ---*/
/*---------------------------------------------------------------*/

typedef
   struct { 
      Int     occ;          /* occurrence count for this tmp */
      IRExpr* expr;         /* expr it is bound to, 
                               or NULL if already 'used' */
      Bool    eDoesLoad;    /* True <=> expr reads mem */
      Bool    eDoesGet;     /* True <=> expr reads guest state */
      Bool    invalidateMe; /* used when dumping bindings */
      Int     origPos;      /* posn of the binder in the original bb */
   }
   TmpInfo;

/* Given env :: IRTemp -> TmpInfo*
   Add the use-occurrences of temps in this expression 
   to the environment. 
*/
static void occCount_Expr ( Hash64* env, IRExpr* e )
{
   Int      i;
   TmpInfo* ti;
   ULong    res;

   switch (e->tag) {

      case Iex_Tmp: /* the only interesting case */
         if (lookupH64(env, &res, (ULong)(e->Iex.Tmp.tmp))) {
            ti = (TmpInfo*)res;
            ti->occ++;
         } else {
            ti = LibVEX_Alloc(sizeof(TmpInfo));
            ti->occ = 1;
            ti->expr = NULL;
            ti->eDoesLoad = False;
            ti->eDoesGet = False;
            ti->invalidateMe = False;
            ti->origPos = -1; /* filed in properly later */
            addToH64(env, (ULong)(e->Iex.Tmp.tmp), (ULong)ti );
         }
         return;

      case Iex_Mux0X:
         occCount_Expr(env, e->Iex.Mux0X.cond);
         occCount_Expr(env, e->Iex.Mux0X.expr0);
         occCount_Expr(env, e->Iex.Mux0X.exprX);
         return;

      case Iex_Binop: 
         occCount_Expr(env, e->Iex.Binop.arg1);
         occCount_Expr(env, e->Iex.Binop.arg2);
         return;

      case Iex_Unop: 
         occCount_Expr(env, e->Iex.Unop.arg);
         return;

      case Iex_LDle: 
         occCount_Expr(env, e->Iex.LDle.addr);
         return;

      case Iex_CCall:
         for (i = 0; e->Iex.CCall.args[i]; i++)
            occCount_Expr(env, e->Iex.CCall.args[i]);
         return;

      case Iex_GetI:
         occCount_Expr(env, e->Iex.GetI.offset);
         return;

      case Iex_Const:
      case Iex_Get:
         return;

      default: 
         vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
         vpanic("occCount_Expr");
    }
}


/* Given env :: IRTemp -> TmpInfo*
   Add the use-occurrences of temps in this expression 
   to the environment. 
*/
static void occCount_Stmt ( Hash64* env, IRStmt* st )
{
   switch (st->tag) {
      case Ist_Tmp: 
         occCount_Expr(env, st->Ist.Tmp.expr); 
         return; 
      case Ist_Put: 
         occCount_Expr(env, st->Ist.Put.expr);
         return;
      case Ist_PutI:
         occCount_Expr(env, st->Ist.PutI.offset);
         occCount_Expr(env, st->Ist.PutI.expr);
         return;
      case Ist_STle: 
         occCount_Expr(env, st->Ist.STle.addr);
         occCount_Expr(env, st->Ist.STle.data);
         return;
      case Ist_Exit:
         occCount_Expr(env, st->Ist.Exit.cond);
         return;
      default: 
         vex_printf("\n"); ppIRStmt(st); vex_printf("\n");
         vpanic("occCount_Stmt");
   }
}


/* Traverse e, looking for temps.  For each observed temp, see if env
   contains a binding for the temp, and if so return the bound value.
   The env has the property that any binding it holds is
   'single-shot', so once a binding is used, it is marked as no longer
   available, by setting its .expr field to NULL. */

static IRExpr* tbSubst_Expr ( Hash64* env, IRExpr* e )
{
   TmpInfo* ti;
   ULong    res;
   IRExpr*  e2;
   IRExpr** args2;
   Int      i;

   switch (e->tag) {

      case Iex_CCall:
         args2 = copyIexCCallArgs(e->Iex.CCall.args);
         for (i = 0; args2[i]; i++)
            args2[i] = tbSubst_Expr(env,args2[i]);
         return IRExpr_CCall(e->Iex.CCall.name,
                   e->Iex.CCall.retty,
                   args2
                );
      case Iex_Tmp:
         if (lookupH64(env, &res, (ULong)(e->Iex.Tmp.tmp))) {
            ti = (TmpInfo*)res;
            e2 = ti->expr;
            if (e2) {
               ti->expr = NULL;
               return e2;
            } else {
               return e;
            }
         } else {
            return e;
         }
      case Iex_Mux0X:
         return IRExpr_Mux0X(
                   tbSubst_Expr(env, e->Iex.Mux0X.cond),
                   tbSubst_Expr(env, e->Iex.Mux0X.expr0),
                   tbSubst_Expr(env, e->Iex.Mux0X.exprX)
                );
      case Iex_Binop:
         return IRExpr_Binop(
                   e->Iex.Binop.op,
                   tbSubst_Expr(env, e->Iex.Binop.arg1),
                   tbSubst_Expr(env, e->Iex.Binop.arg2)
                );
      case Iex_Unop:
         return IRExpr_Unop(
                   e->Iex.Unop.op,
                   tbSubst_Expr(env, e->Iex.Unop.arg)
                );
      case Iex_LDle:
         return IRExpr_LDle(
                   e->Iex.LDle.ty,
                  tbSubst_Expr(env, e->Iex.LDle.addr)
                );
      case Iex_GetI:
         return IRExpr_GetI(
                   tbSubst_Expr(env, e->Iex.GetI.offset),
                   e->Iex.GetI.ty,
                   e->Iex.GetI.minoff,
                   e->Iex.GetI.maxoff
         );
      case Iex_Const:
      case Iex_Get:
         return e;
      default: 
         vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
         vpanic("tbSubst_Expr");
   }
}

/* Same deal as tbSubst_Expr, except for stmts. */

static IRStmt* tbSubst_Stmt ( Hash64* env, IRStmt* st )
{
   switch (st->tag) {
   case Ist_STle:
     return IRStmt_STle(
                        tbSubst_Expr(env, st->Ist.STle.addr),
                        tbSubst_Expr(env, st->Ist.STle.data)
                        );
      case Ist_Tmp:
         return IRStmt_Tmp(
                   st->Ist.Tmp.tmp,
                   tbSubst_Expr(env, st->Ist.Tmp.expr)
                );
      case Ist_Put:
         return IRStmt_Put(
                   st->Ist.Put.offset,
                   tbSubst_Expr(env, st->Ist.Put.expr)
                );
      case Ist_PutI:
         return IRStmt_PutI(
                   tbSubst_Expr(env, st->Ist.PutI.offset),
                   tbSubst_Expr(env, st->Ist.PutI.expr),
                   st->Ist.PutI.minoff,
                   st->Ist.PutI.maxoff
         );

      case Ist_Exit:
         return IRStmt_Exit(
                   tbSubst_Expr(env, st->Ist.Exit.cond),
                   st->Ist.Exit.dst
                );
      default: 
         vex_printf("\n"); ppIRStmt(st); vex_printf("\n");
         vpanic("tbSubst_Stmt");
   }
}


/* Traverse an expr, and detect if any part of it reads memory or does
   a Get.  Be careful ... this really controls how much the
   tree-builder can reorder the code, so getting it right is critical.
*/
static void setHints_Expr (Bool* doesLoad, Bool* doesGet, IRExpr* e )
{
   Int i;
   switch (e->tag) {
      case Iex_CCall:
         for (i = 0; e->Iex.CCall.args[i]; i++)
            setHints_Expr(doesLoad, doesGet, e->Iex.CCall.args[i]);
         return;
      case Iex_Mux0X:
         setHints_Expr(doesLoad, doesGet, e->Iex.Mux0X.cond);
         setHints_Expr(doesLoad, doesGet, e->Iex.Mux0X.expr0);
         setHints_Expr(doesLoad, doesGet, e->Iex.Mux0X.exprX);
         return;
      case Iex_Binop:
         setHints_Expr(doesLoad, doesGet, e->Iex.Binop.arg1);
         setHints_Expr(doesLoad, doesGet, e->Iex.Binop.arg2);
         return;
      case Iex_Unop:
         setHints_Expr(doesLoad, doesGet, e->Iex.Unop.arg);
         return;
      case Iex_LDle:
         *doesLoad |= True;
	 setHints_Expr(doesLoad, doesGet, e->Iex.LDle.addr);
         return;
      case Iex_Get:
         *doesGet |= True;
         return;
      case Iex_GetI:
         *doesGet |= True;
         setHints_Expr(doesLoad, doesGet, e->Iex.GetI.offset);
         return;
      case Iex_Tmp:
      case Iex_Const:
         return;
      default: 
         vex_printf("\n"); ppIRExpr(e); vex_printf("\n");
         vpanic("setHints_Expr");
   }
}


static void dumpInvalidated ( Hash64* env, IRBB* bb, /*INOUT*/Int* j )
{
   Int k, oldest_op, oldest_k;
   TmpInfo* ti;

   /* Dump all the bindings to marked as invalidated, in order. */
   while (True) {
  
      /* find the oldest bind marked 'invalidateMe'. */
      oldest_op = 1<<30;
      oldest_k =  1<<30;
      for (k = 0;  k < env->used; k++) {
         if (!env->inuse[k])
            continue;
         ti = (TmpInfo*)(env->val[k]);
         if (!ti->expr)
            continue;
         if (!ti->invalidateMe)
           continue;
         /* vex_printf("FOUND INVAL %d %d\n", ti->origPos, oldest_op); */
         if (ti->origPos < oldest_op) {
            oldest_op = ti->origPos;
            oldest_k = k;
         }
      }

      /* No more binds to invalidate. */
      if (oldest_op == 1<<30)
        return;

      /* the oldest bind to invalidate has been identified */
      vassert(oldest_op != 1<<31 && oldest_k != 1<<31);
      ti = (TmpInfo*)(env->val[oldest_k]);
      vassert(ti->expr && ti->invalidateMe);

      /* and invalidate it ... */
      bb->stmts[*j] = IRStmt_Tmp( (IRTemp)(env->key[oldest_k]), ti->expr);
      /*  vex_printf("**1  "); ppIRStmt(bb->stmts[*j]); vex_printf("\n"); */
      (*j)++;
      ti->invalidateMe = False;
      ti->expr = NULL; /* no longer available for substitution */

   } /* loop which dumps the binds marked for invalidation */
}



static void treebuild_BB ( IRBB* bb )
{
   Int      i, j, k;
   ULong    res;
   Bool     invPut, invStore;
   IRStmt*  st;
   IRStmt*  st2;
   TmpInfo* ti;
   IRExpr*  next2;

   /* Mapping from IRTemp to TmpInfo*. */
   Hash64* env = newH64();

   /* Phase 1.  Scan forwards in bb, counting use occurrences of each
      temp.  Also count occurrences in the bb->next field. */

   for (i = 0; i < bb->stmts_used; i++) {
      st = bb->stmts[i];
      if (!st)
         continue;
      occCount_Stmt( env, st );
   }
   occCount_Expr(env, bb->next );

#if 0
   for (i = 0; i < env->used; i++) {
      if (!env->inuse[i])
        continue;
      ppIRTemp( (IRTemp)(env->key[i]) );
      vex_printf("  used %d\n", ((TmpInfo*)env->val[i])->occ );
   }
#endif

   /* Phase 2.  Fill in the origPos fields. */

   for (i = 0; i < bb->stmts_used; i++) {
      st = bb->stmts[i];
      if (!st)
         continue;
      if (st->tag != Ist_Tmp)
         continue;

      if (!lookupH64(env, &res, (ULong)(st->Ist.Tmp.tmp))) {
         vex_printf("\n");
         ppIRTemp(st->Ist.Tmp.tmp);
         vex_printf("\n");
         vpanic("treebuild_BB (phase 2): unmapped IRTemp");
      }
      ti = (TmpInfo*)res;
      ti->origPos = i;
   }

   /* Phase 3.  Scan forwards in bb.  

      On seeing 't = E', occ(t)==1,  
            let E'=env(E), set t's binding to be E', and
            delete this stmt.
            Also examine E' and set the hints for E' appropriately
              (doesLoad? doesGet?)

      On seeing any other stmt, 
            let stmt' = env(stmt)
            remove from env any 't=E' binds invalidated by stmt
                emit the invalidated stmts
            emit stmt'

      Apply env to bb->next.
   */

   /* The stmts in bb are being reordered, and we are guaranteed to
      end up with no more than the number we started with.  Use i to
      be the cursor of the current stmt examined and j <= i to be that
      for the current stmt being written. 
   */
   j = 0;
   for (i = 0; i < bb->stmts_used; i++) {
      st = bb->stmts[i];
      if (!st)
         continue;
     
      if (st->tag == Ist_Tmp) {
        /* vex_printf("acquire binding\n"); */
         if (!lookupH64(env, &res, (ULong)(st->Ist.Tmp.tmp))) {
            vpanic("treebuild_BB (phase 2): unmapped IRTemp");
         }
         ti = (TmpInfo*)res;
         if (ti->occ == 1) {
            /* ok, we have 't = E', occ(t)==1.  Do the abovementioned actions. */
            IRExpr* e = st->Ist.Tmp.expr;
            IRExpr* e2 = tbSubst_Expr(env, e);
            ti->expr = e2;
            ti->eDoesLoad = ti->eDoesGet = False;
            setHints_Expr(&ti->eDoesLoad, &ti->eDoesGet, e2);
            /* don't advance j, as we are deleting this stmt and instead
               holding it temporarily in the env. */
            continue; /* the for (i = 0; i < bb->stmts_used; i++) loop */
         }
      }

      /* we get here for any other kind of statement. */
      /* 'use up' any bindings required by the current statement. */
      st2 = tbSubst_Stmt(env, st);

      /* Now, before this stmt, dump any bindings it invalidates.
         These need to be dumped in the order in which they originally
         appeared.  (Stupid algorithm): first, mark all bindings which
         need to be dumped.  Then, dump them in the order in which
         they were defined. */
      invPut = st->tag == Ist_Put || st->tag == Ist_PutI;
      invStore = st->tag == Ist_STle;

      for (k = 0; k < env->used; k++) {
         if (!env->inuse[k])
            continue;
         ti = (TmpInfo*)(env->val[k]);
         if (!ti->expr)
            continue;

         /* We have to invalidate this binding. */
         ti->invalidateMe 
            = (ti->eDoesLoad && invStore) || (ti->eDoesGet && invPut);
         /*
         if (ti->invalidateMe)
           vex_printf("SET INVAL\n");
           */
      }

      dumpInvalidated ( env, bb, &j );

      /* finally, emit the substituted statement */
      bb->stmts[j] = st2;
      /*  vex_printf("**2  "); ppIRStmt(bb->stmts[j]); vex_printf("\n"); */
      j++;

      vassert(j <= i+1);
   } /* for each stmt in the original bb ... */

   /* Finally ... substitute the ->next field as much as possible, and
      dump any left-over bindings.  Hmm.  Perhaps there should be no
      left over bindings?  Or any left-over bindings are
      by definition dead? */
   next2 = tbSubst_Expr(env, bb->next);
   bb->next = next2;
   bb->stmts_used = j;
}



/*---------------------------------------------------------------*/
/*--- iropt main                                              ---*/
/*---------------------------------------------------------------*/

/* Rules of the game:

   - IRExpr/IRStmt trees should be treated as immutable, as they
     may get shared.  So never change a field of such a tree node;
     instead construct and return a new one if needed.
*/

/* exported from this file */
IRBB* do_iropt_BB ( IRBB* bb0,
                    IRExpr* (*specHelper) ( Char*, IRExpr**) )
{
   Bool verbose = False;
   IRBB *flat, *cpd;

   flat = flatten_BB ( bb0 );
   if (verbose) {
      vex_printf("\n************************ FLAT\n\n" );
      ppIRBB(flat);
   }

   redundant_get_removal_BB ( flat );
   if (verbose) {
      vex_printf("\n========= REDUNDANT GET\n\n" );
      ppIRBB(flat);
   }

   redundant_put_removal_BB ( flat );
   if (verbose) {
      vex_printf("\n========= REDUNDANT PUT\n\n" );
      ppIRBB(flat);
   }

   cpd = cprop_BB ( flat );
   if (verbose) {
      vex_printf("\n========= CPROPD\n\n" );
      ppIRBB(cpd);
   }

   dead_BB ( cpd );
   if (verbose) {
      vex_printf("\n========= DEAD\n\n" );
      ppIRBB(cpd);
   }

   spec_helpers_BB ( cpd, specHelper );
   dead_BB ( cpd );
   if (verbose) {
      vex_printf("\n========= SPECd \n\n" );
      ppIRBB(cpd);
   }

   treebuild_BB ( cpd );
   if (verbose) {
      vex_printf("\n========= TREEd \n\n" );
      ppIRBB(cpd);
   }

   return cpd;

}


/*---------------------------------------------------------------*/
/*--- end                                          ir/iropt.c ---*/
/*---------------------------------------------------------------*/