// This is given as an example on how to do optimisations at the AST level.
// These examples are trivial.  It will be a student exercise to add more
// useful optimisations.

void Identities(int p, int *count)
{
  int op;
  int arity;

  if ((p == -1) || (astop(p) == -1)) return;

  op = astop(p); arity = children(p);

  if (arity == 2) {
    switch (op) {
    case AST_Idx:
      if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==0)) {
        // x[0] => &x+0 => &x
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      }
    case AST_Add:
      if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==0)) {
        // replace expr with right
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==0)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      }
      return;
    case AST_Sub:
      // to do: x - x  =>  0
      if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==0)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==0)) {
        // convert to AST_Neg
      }
      return;
    case AST_Mul: 
      if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==1)) {
        // replace expr with right
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==1)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==0)) {
        // replace expr with 0
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==0)) {
        // replace expr with 0
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      }
      return;
    case AST_Div:
      // to do:  x / x  =>  1
      if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==1)) {
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      }
      return;
    case AST_Mod:
      // TO DO: lower to &n-1 if power of two
      return;
    case AST_BoolAnd:
    case AST_ShortcutBoolAnd: // this is buggy in shortcut case if side-effects :- boolfn() && FALSE
      if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==TRUE)) {
        // replace expr with right
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==TRUE)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==FALSE)) {
        // result of whole expr is FALSE - but AST_BoolAnd should eval RHS anyway?
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==FALSE)) {
        // result of whole expr is FALSE - but AST_BoolAnd should eval LHS anyway?
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      }
      return;
    case AST_BoolOr:
    case AST_ShortcutBoolOr: // this is buggy in shortcut case if side-effects :- boolfn() || TRUE
      if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==FALSE)) {
        // replace expr with right
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==FALSE)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==TRUE)) {
        // whole expression is TRUE - but AST_BoolOr should eval RHS anyway?
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==TRUE)) {
        // whole expression is TRUE - but AST_BoolOr should eval LHS anyway?
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      }
      return;
    case AST_BitAnd:
      if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==-1)) {
        // replace expr with right
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==-1)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==0)) {
        // whole expression is 0
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==0)) {
        // whole expression is 0
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      }
      return;
    case AST_BitOr:
      if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==0)) {
        // replace expr with right
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==0)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==-1)) {
        // replace expr with -1
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==-1)) {
        // replace expr with -1
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      }
      return;
    case AST_BitXor:
      if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==0)) {
        // replace expr with right
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==0)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      }
      return;
    case AST_BitLsh:
      if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==0)) {
        // whole expr is 0
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==0)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      }
      return;
    case AST_BitRsh:
      if ((astop(leftchild(p)) == AST_Const) && (rightchild(leftchild(p))==0)) {
        // whole expr is 0
        replace_with_trip(p, rightchild(p)); *count = *count+1;
      } else if ((astop(rightchild(p)) == AST_Const) && (rightchild(rightchild(p))==0)) {
        // replace expr with left
        replace_with_trip(p, leftchild(p)); *count = *count+1;
      }
      return;

    default:
      return;
    }
  }
}

int fold_identities(int p)
{
  int count = 0;
  int i;
  int disp;
  int this;

  if ((p == -1) || (astop(p) == -1)) return 0;

  if ((astop(p) < AST_BASE) || (astop(p) > AST_TOP)) {
    fprintf(stderr, "* Internal Error: p=%d  astop(p) - %d\n", p, astop(p));
    exit(1);
  }
  disp = op[astop(p)-AST_BASE].Display_Children;
  this = 1<<(children(p)-1);
  for (i = 0; i < children(p); i++) {
    if ((nthchild(p, i) != -1) && (disp&this)) {
      count += fold_identities(nthchild(p, i));
      while (astop(nthchild(p, i)) == AST_REDIRECT) nthchild(p, i) = leftchild(nthchild(p,i));
      // perform redirection
    }
    this = this>>1;
  }
  Identities(p, &count);
  return count;
}