path: root/src/SDCClospre.cc

// Philipp Klaus Krause, philipp@informatik.uni-frankfurt.de, pkk@spth.de, 2012
//
// (c) 2012 Goethe-Universität Frankfurt
//
// This program is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option) any
// later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//
//
// Lifetime-optimal speculative partial redundancy elimination.

// #define DEBUG_LOSPRE // Uncomment to get debug messages while doing lospre.
// #define DEBUG_LOSPRE_ASS // Uncomment to get debug messages on considered assignmentd while doing lospre.

#include "SDCClospre.hpp"

// A quick-and-dirty function to get the CFG from sdcc (a simplified version of the function from SDCCralloc.hpp).
void
create_cfg_lospre (cfg_lospre_t &cfg, iCode *start_ic, ebbIndex *ebbi)
{
  iCode *ic;

  std::map<int, unsigned int> key_to_index;
  {
    int i;

    for (ic = start_ic, i = 0; ic; ic = ic->next, i++)
      {
        boost::add_vertex(cfg);
        key_to_index[ic->key] = i;
        cfg[i].ic = ic;
      }
  }

  // Get control flow graph from sdcc.
  for (ic = start_ic; ic; ic = ic->next)
    {
      if((ic->op == '>' || ic->op == '<' || ic->op == LE_OP || ic->op == GE_OP || ic->op == EQ_OP || ic->op == NE_OP || ic->op == '^' || ic->op == '|' || ic->op == BITWISEAND) && ifxForOp (IC_RESULT (ic), ic))
        boost::add_edge(key_to_index[ic->key], key_to_index[ic->next->key], 4.0f, cfg); // Try not to separate op from ifx.
      else if (ic->op != GOTO && ic->op != RETURN && ic->op != JUMPTABLE && ic->next)
        boost::add_edge(key_to_index[ic->key], key_to_index[ic->next->key], 3.0f, cfg);

      if (ic->op == GOTO)
        boost::add_edge(key_to_index[ic->key], key_to_index[eBBWithEntryLabel(ebbi, ic->label)->sch->key], 6.0f, cfg);
      else if (ic->op == RETURN)
        boost::add_edge(key_to_index[ic->key], key_to_index[eBBWithEntryLabel(ebbi, returnLabel)->sch->key], 6.0f, cfg);
      else if (ic->op == IFX)
        boost::add_edge(key_to_index[ic->key], key_to_index[eBBWithEntryLabel(ebbi, IC_TRUE(ic) ? IC_TRUE(ic) : IC_FALSE(ic))->sch->key], 6.0f, cfg);
      else if (ic->op == JUMPTABLE)
        for (symbol *lbl = (symbol *)(setFirstItem (IC_JTLABELS (ic))); lbl; lbl = (symbol *)(setNextItem (IC_JTLABELS (ic))))
          boost::add_edge(key_to_index[ic->key], key_to_index[eBBWithEntryLabel(ebbi, lbl)->sch->key], 6.0f, cfg);
    }
}

static bool
candidate_expression (const iCode *const ic, int lkey)
{
  wassert(ic);

  if (
    ic->op != '!' &&
    ic->op != '~' &&
    ic->op != UNARYMINUS &&
    ic->op != '+' &&
    ic->op != '-' &&
    ic->op != '*' &&
    ic->op != '/' &&
    ic->op != '%' &&
    ic->op != '>' &&
    ic->op != '<' &&
    ic->op != LE_OP &&
    ic->op != GE_OP &&
    ic->op != NE_OP &&
    ic->op != EQ_OP &&
    ic->op != AND_OP &&
    ic->op != OR_OP &&
    ic->op != '^' &&
    ic->op != '|' &&
    ic->op != BITWISEAND &&
    ic->op != RRC &&
    ic->op != RLC &&
    ic->op != GETABIT &&
    ic->op != GETHBIT &&
    ic->op != LEFT_OP &&
    ic->op != RIGHT_OP &&
    !(ic->op == '=' && !POINTER_SET(ic) && !(IS_ITEMP(IC_RIGHT(ic)) /*&& IC_RIGHT(ic)->key > lkey*/)) &&
    ic->op != GET_VALUE_AT_ADDRESS &&
    ic->op != CAST)
    return (false);

  const operand *const left = IC_LEFT (ic);
  const operand *const right = IC_RIGHT (ic);
  const operand *const result = IC_RESULT (ic);

  // Todo: Allow literal right operand once backends can rematerialize literals!
  if(ic->op == '=' && IS_OP_LITERAL (right))
    return (false);

  // Todo: Allow more operands!
  if (ic->op != CAST && left && !(IS_SYMOP (left) || IS_OP_LITERAL (left)) ||
    right && !(IS_SYMOP (right) || IS_OP_LITERAL (right)) ||
    result && !(IS_SYMOP (result) || IS_OP_LITERAL (result)))
    return (false);

  return (true);
}

static bool
same_expression (const iCode *const lic, const iCode *const ric)
{
  wassert(lic);
  wassert(ric);

  if (lic->op != ric->op)
    return (false);

  const operand *lleft = IC_LEFT (lic);
  const operand *lright = IC_RIGHT (lic);
  const operand *lresult = IC_RESULT (lic);
  const operand *rleft = IC_LEFT (ric);
  const operand *rright = IC_RIGHT (ric);
  const operand *rresult = IC_RESULT (ric);

  if ((isOperandEqual (lleft, rleft) && isOperandEqual (lright, rright) ||
    IS_COMMUTATIVE (lic) && isOperandEqual (lleft, rright) && isOperandEqual (lright, rleft)) &&
    (lresult && rresult && compareTypeInexact (operandType (lresult), operandType (rresult)) > 0) &&
    IS_FLOAT (operandType (lresult)) == IS_FLOAT (operandType (rresult)))
    return (true);

  return (false);
}

static void
get_candidate_set(std::set<int> *c, const iCode *const sic, int lkey)
{
  // TODO: For loop invariant code motion allow expression that only occurs once, too - will be needed when optimizing for speed.
  for (const iCode *ic = sic; ic; ic = ic->next)
    {
      if (!candidate_expression (ic, lkey))
        continue;
      for (const iCode *pic = sic; pic != ic; pic = pic->next)
        if (candidate_expression (pic, lkey) && same_expression (ic, pic) && c->find (pic->key) == c->end ())
          {
            // Found expression that occurs at least twice.
            c->insert (pic->key);
            break;
          }
    }
}

static bool
invalidates_expression(const iCode *const eic, const iCode *const iic)
{
  const operand *const eleft = IC_LEFT (eic);
  const operand *const eright = IC_RIGHT (eic);
  const bool uses_global = (eic->op == GET_VALUE_AT_ADDRESS || isOperandGlobal (eleft) || isOperandGlobal (eright) || IS_SYMOP (eleft) && OP_SYMBOL_CONST (eleft)->addrtaken || IS_SYMOP (eright) && OP_SYMBOL_CONST (eright)->addrtaken);
  const bool uses_volatile = POINTER_GET (eic) && IS_VOLATILE (operandType (eleft)->next) || IS_OP_VOLATILE (eleft) || IS_OP_VOLATILE (eright);

  const operand *const left = IC_LEFT (iic);
  const operand *const right = IC_RIGHT (iic);
  const operand *const result = IC_RESULT (iic);

  if (IC_RESULT (iic) && !IS_OP_LITERAL (result) && !POINTER_SET(iic) &&
    (eleft && isOperandEqual (eleft, result) || eright && isOperandEqual (eright, result)))
    return(true);
  if (iic->op == FUNCTION || iic->op == ENDFUNCTION || iic->op == RECEIVE)
    return(true);
  if ((uses_global || uses_volatile) && (iic->op == CALL || iic->op == PCALL))
    return(true);
  if (uses_volatile && (POINTER_GET (iic) && IS_VOLATILE (operandType (left)->next)) || IS_OP_VOLATILE (left) || IS_OP_VOLATILE (right))
    return(true);
  if (uses_global && POINTER_SET (iic)) // TODO: More accuracy here!
    return(true);

  return(false);
}

static bool
setup_cfg_for_expression (cfg_lospre_t *const cfg, const iCode *const eic)
{
  typedef boost::graph_traits<cfg_lospre_t>::vertex_descriptor vertex_t;
  bool safety_required = false;

  // In redundancy elimination, safety means not doing a computation on any path were it was not done before.
  // This is important, if the compuation can have side-effects, which depends on the target architecure.
  // E.g. On some systems division requires safety, since division by zero might result in an interrupt.
  // When there are memory-mapped devices or there is memory management, reading from a pointer requires
  // safety, since reading from an unknown location could result in making the device do something or in a SIGSEGV. 
  // On the other hand, addition is something that typically does not require safety, since adding two undefined
  // operands gives just another undefined (the C standard allows trap representations, which, could result
  // in addition requiring safety though; AFAIK none of the targets currently supported by SDCC have trap representations).
  // Philipp, 2012-07-06.
  //
  // For now we just always require safety for "dangerous" operations.
  //
  // TODO: Replace the current one  by a more exact mechanism, that takes into account information from
  // (not yet implemented) generalized constant propagation, pointer analysis, etc.

  // Function calls can have any side effects.
  if (eic->op == CALL || eic->op == PCALL)
    safety_required = true;

  // volatile requires safety.
  if (POINTER_GET (eic) && IS_VOLATILE (operandType (IC_LEFT (eic))->next) || IS_OP_VOLATILE (IC_LEFT (eic)) || IS_OP_VOLATILE (IC_RIGHT (eic)))
    safety_required = true;

  // Reading from an invalid address might be dangerous, since there could be memory-mapped I/O.
  if (eic->op == GET_VALUE_AT_ADDRESS && !optimize.allow_unsafe_read)
    safety_required = true;

  // The division routines for z80-like ports and the hc08/s08's and stm8's hardware division just give an undefined result
  // for division by zero, but there are no harmful side effects. I don't know about the other ports.
  if ((eic->op == '/' || eic->op == '%') && !TARGET_Z80_LIKE && !TARGET_HC08_LIKE && !TARGET_IS_STM8)
    safety_required = true;

  // TODO: Relax this! There are cases where allowing unsafe optimizations will improve speed.
  // This probably needs implementation of profile-guided optimization though.
  if (optimize.codeSpeed)
    safety_required = true;

#ifdef DEBUG_LOSPRE
  std::cout << "Invalidation set I: ";
#endif
  for (vertex_t i = 0; i < boost::num_vertices (*cfg); i++)
    {
       const iCode *const ic = (*cfg)[i].ic;

       (*cfg)[i].uses = same_expression (eic, ic);
       (*cfg)[i].invalidates = invalidates_expression (eic, ic);

       (*cfg)[i].forward = std::pair<int, int>(-1, -1);

#ifdef DEBUG_LOSPRE
       if ((*cfg)[i].invalidates)
         std::cout << i << ", ";
#endif
    }
#ifdef DEBUG_LOSPRE
  std::cout << "\n";
#endif

  return (safety_required);
}

// Dump cfg, with numbered nodes.
void dump_cfg_lospre (const cfg_lospre_t &cfg)
{
  if (!currFunc)
    return;

  std::ofstream dump_file((std::string(dstFileName) + ".dumplosprecfg" + currFunc->rname + ".dot").c_str());

  std::string *name = new std::string[num_vertices(cfg)];
  for (unsigned int i = 0; i < boost::num_vertices(cfg); i++)
    {
      const char *iLine = printILine (cfg[i].ic);
      std::ostringstream os;
      os << i << ", " << cfg[i].ic->key << " : " << iLine;
      dbuf_free (iLine);
      name[i] = os.str();
    }
  boost::write_graphviz(dump_file, cfg, boost::make_label_writer(name), boost::default_writer(), cfg_titlewriter(currFunc->rname, "lospre"));
  delete[] name;
}

// Dump tree decomposition.
static void dump_dec_lospre(const tree_dec_t &tree_dec)
{
  wassert (currFunc);

  std::ofstream dump_file((std::string(dstFileName) + ".dumplospredec" + currFunc->rname + ".dot").c_str());

  unsigned int w = 0;

  std::string *name = new std::string[num_vertices(tree_dec)];
  for (unsigned int i = 0; i < boost::num_vertices(tree_dec); i++)
    {
      if (tree_dec[i].bag.size() > w)
        w = tree_dec[i].bag.size();
      std::ostringstream os;
      typename decltype(tree_dec[0].bag)::const_iterator v1;
       os << i << " | ";
      for (v1 = tree_dec[i].bag.begin(); v1 != tree_dec[i].bag.end(); ++v1)
        os << *v1 << " ";
      name[i] = os.str();
    }
  boost::write_graphviz(dump_file, tree_dec, boost::make_label_writer(name));
  delete[] name;
}

void
lospre (iCode *sic, ebbIndex *ebbi)
{
  cfg_lospre_t control_flow_graph;
  tree_dec_t tree_decomposition;

  wassert (sic);

#ifdef DEBUG_LOSPRE
  if (currFunc)
    std::cout << "lospre for " << currFunc->rname << "()\n";
#endif

  create_cfg_lospre (control_flow_graph, sic, ebbi);

  if(options.dump_graphs)
    dump_cfg_lospre(control_flow_graph);

  get_nice_tree_decomposition (tree_decomposition, control_flow_graph);

  if(options.dump_graphs)
    dump_dec_lospre(tree_decomposition);

  int lkey = operandKey;

  for (bool change = true; change;)
    {
      change = false;

      std::set<int> candidate_set;
      get_candidate_set (&candidate_set, sic, lkey);

      std::set<int>::iterator ci, ci_end;
      for (ci = candidate_set.begin(), ci_end = candidate_set.end(); ci != ci_end; ++ci)
        {
          const iCode *ic;
          for (ic = sic; ic && ic->key != *ci; ic = ic->next);

          if (!ic || !candidate_expression (ic, lkey))
            continue;

          bool safety = setup_cfg_for_expression (&control_flow_graph, ic);

          if (safety && tree_dec_safety (tree_decomposition, control_flow_graph, ic) < 0)
            continue;

          change |= (tree_dec_lospre (tree_decomposition, control_flow_graph, ic) > 0);
        }
    }
}