sdcc-3.9.0 fork implementing GNU assembler syntax

This fork aims to provide better support for stm8-binutils

1 files changed, 351 insertions, 0 deletions

diff --git a/src/SDCClospre.cc b/src/SDCClospre.cc
new file mode 100644
index 0000000..18541d8
--- /dev/null
+++ b/src/SDCClospre.cc
@@ -0,0 +1,351 @@
+// 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);
+        }
+    }
+}
+