sdcc-3.9.0 fork implementing GNU assembler syntax

This fork aims to provide better support for stm8-binutils

1 files changed, 483 insertions, 0 deletions

diff --git a/src/SDCCcflow.c b/src/SDCCcflow.c
new file mode 100644
index 0000000..cc487d7
--- /dev/null
+++ b/src/SDCCcflow.c
@@ -0,0 +1,483 @@
+/*-------------------------------------------------------------------------
+
+  SDCCcflow.c - source file for control flow analysis
+
+             Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
+
+   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.
+   
+   In other words, you are welcome to use, share and improve this program.
+   You are forbidden to forbid anyone else to use, share and improve
+   what you give them.   Help stamp out software-hoarding!  
+-------------------------------------------------------------------------*/
+
+#include "common.h"
+
+static void computeDFOrdering (eBBlock *, int *);
+
+/*-----------------------------------------------------------------*/
+/* domSetFromVect - creates a domset from the vector               */
+/*-----------------------------------------------------------------*/
+static set *
+domSetFromVect (ebbIndex *ebbi, bitVect * domVect)
+{
+  int i = 0;
+  set *domSet = NULL;
+
+  if (!domVect)
+    return NULL;
+
+  for (i = 0; i < domVect->size; i++)
+    if (bitVectBitValue (domVect, i))
+      addSet (&domSet, ebbi->bbOrder[i]);
+  return domSet;
+}
+
+
+/*-----------------------------------------------------------------*/
+/* addSuccessor - will add bb to succ also add it to the pred of   */
+/*                the next one :                                   */
+/*-----------------------------------------------------------------*/
+static void 
+addSuccessor (eBBlock * thisBlock, eBBlock * succ)
+{
+  /* check for boundary conditions */
+  if (!thisBlock || !succ)
+    return;
+
+  /* add it to the succ of thisBlock */
+  addSetIfnotP (&thisBlock->succList, succ);
+
+  thisBlock->succVect =
+    bitVectSetBit (thisBlock->succVect, succ->bbnum);
+  /* add this edge to the list of edges */
+  addSet (&graphEdges, newEdge (thisBlock, succ));
+
+}
+
+/*-----------------------------------------------------------------*/
+/* eBBPredecessors - find the predecessors for each block          */
+/*-----------------------------------------------------------------*/
+static void 
+eBBPredecessors (ebbIndex * ebbi)
+{
+  eBBlock ** ebbs = ebbi->bbOrder;
+  int count = ebbi->count;
+  int i = 0, j;
+
+  /* for each block do */
+  for (i = 0; i < count; i++)
+    {
+
+      /* if there is no path to this then continue */
+      if (ebbs[i]->noPath)
+	continue;
+
+      /* for each successor of this block if */
+      /* it has depth first number > this block */
+      /* then this block precedes the successor  */
+      for (j = 0; j < ebbs[i]->succVect->size; j++)
+
+	if (bitVectBitValue (ebbs[i]->succVect, j) &&
+	    ebbs[j]->dfnum > ebbs[i]->dfnum)
+
+	  addSet (&ebbs[j]->predList, ebbs[i]);
+    }
+}
+
+/*-----------------------------------------------------------------*/
+/* eBBSuccessors- find out the successors of all the nodes         */
+/*-----------------------------------------------------------------*/
+static void 
+eBBSuccessors (ebbIndex * ebbi)
+{
+  eBBlock ** ebbs = ebbi->bbOrder;
+  int count = ebbi->count;
+  int i = 0;
+
+  /* for all the blocks do */
+  for (; i < count; i++)
+    {
+      iCode *ic;
+
+      if (ebbs[i]->noPath)
+	continue;
+
+      ebbs[i]->succVect = newBitVect (count);
+
+      /* if the next on exists & this one does not */
+      /* end in a GOTO or RETURN then the next is  */
+      /* a natural successor of this. Note we have */
+      /* consider eBBlocks with no instructions    */
+      if (ebbs[i + 1])
+	{
+
+	  if (ebbs[i]->ech)
+	    {
+              bool foundNoReturn = FALSE;
+              if (ebbs[i]->ech->op == CALL || ebbs[i]->ech->op == PCALL)
+                {
+                  sym_link *type = operandType (IC_LEFT (ebbs[i]->ech));
+                  if (IS_FUNCPTR (type))
+                    type = type->next;
+                  if (type && FUNC_ISNORETURN (type))
+                    foundNoReturn = TRUE;
+                }
+	      if (!foundNoReturn &&
+                 ebbs[i]->ech->op != GOTO &&
+		  ebbs[i]->ech->op != RETURN &&
+		  ebbs[i]->ech->op != JUMPTABLE)
+		{
+		  int j = i + 1;
+
+		  while (ebbs[j] && ebbs[j]->noPath)
+		    j++;
+
+		  addSuccessor (ebbs[i], ebbs[j]);	/* add it */
+		}
+	      else
+		{
+		  if (i && ebbs[i-1]->ech && ebbs[i-1]->ech->op==IFX) {
+		    ebbs[i]->isConditionalExitFrom=ebbs[i-1];
+		  }
+		}
+	    }			/* no instructions in the block */
+	  /* could happen for dummy blocks */
+	  else
+	    addSuccessor (ebbs[i], ebbs[i + 1]);
+	}
+
+      /* go thru all the instructions: if we find a */
+      /* goto or ifx or a return then we have a succ */
+      if ((ic = ebbs[i]->ech))
+	{
+	  eBBlock *succ;
+
+	  /* special case for jumptable */
+	  if (ic->op == JUMPTABLE)
+	    {
+	      symbol *lbl;
+	      for (lbl = setFirstItem (IC_JTLABELS (ic)); lbl;
+		   lbl = setNextItem (IC_JTLABELS (ic)))
+		addSuccessor (ebbs[i],
+			      eBBWithEntryLabel (ebbi, lbl));
+	    }
+	  else
+	    {
+
+	      succ = NULL;
+	      /* depending on the instruction operator */
+	      switch (ic->op)
+		{
+		case GOTO:	/* goto has edge to label */
+		  succ = eBBWithEntryLabel (ebbi, ic->label);
+
+                  /* Sometimes a block has a GOTO added after the original */
+                  /* final IFX (due to loop optimizations). If IFX found,  */
+                  /* fall through to handle the IFX too. */
+                  if (ic->prev && ic->prev->op == IFX)
+                    {
+                      if (succ)
+                        addSuccessor (ebbs[i], succ); /* add the GOTO target */
+                      ic = ic->prev;       /* get ready to handle IFX too. */
+                    }
+                  else
+                    break;
+
+		case IFX:	/* conditional jump */
+		  /* if true label is present */
+		  if (IC_TRUE (ic))
+		    succ = eBBWithEntryLabel (ebbi, IC_TRUE (ic));
+		  else
+		    succ = eBBWithEntryLabel (ebbi, IC_FALSE (ic));
+		  break;
+
+		case RETURN:	/* block with return */
+		  succ = eBBWithEntryLabel (ebbi, returnLabel);
+		  break;
+		}
+
+	      /* if there is a successor add to the list */
+	      /* if it is not already present in the list */
+	      if (succ)
+		addSuccessor (ebbs[i], succ);
+	    }
+	}
+    }
+}
+
+/*-----------------------------------------------------------------*/
+/* computeDominance - computes the dominance graph                 */
+/* for algorithm look at Dragon book section 10.10, algo 10.16     */
+/*-----------------------------------------------------------------*/
+static void 
+computeDominance (ebbIndex * ebbi)
+{
+  eBBlock ** ebbs = ebbi->bbOrder;
+  int count = ebbi->count;
+  int i, j;
+
+  /* now do the initialisation */
+  /* D(n0) := { n0 } */
+  ebbs[0]->domVect =
+    bitVectSetBit (ebbs[0]->domVect = newBitVect (count), ebbs[0]->bbnum);
+
+
+  /* for n in N - { n0 } do D(n) = N */
+  for (i = 1; i < count; i++)
+    {
+      ebbs[i]->domVect = newBitVect (count);
+      for (j = 0; j < count; j++)
+	{
+	  ebbs[i]->domVect =
+	    bitVectSetBit (ebbs[i]->domVect, ebbs[j]->bbnum);
+	}
+    }
+
+  /* end of initialisation */
+
+  /* while changes to any D(n) occur do */
+  /*   for n in N - { n0 } do           */
+  /*       D(n) := { n } U  (intersection of D( all predecessors of n)) */
+  while (1)
+    {
+      int change;
+
+      change = 0;
+      for (i = 1; i < count; i++)
+	{
+	  bitVect *cDomVect;
+	  eBBlock *pred;
+
+	  cDomVect = NULL;
+
+	  /* get the intersection of the dominance of all predecessors */
+	  for (pred = setFirstItem (ebbs[i]->predList),
+	       cDomVect = (pred ? bitVectCopy (pred->domVect) : NULL);
+	       pred;
+	       pred = setNextItem (ebbs[i]->predList))
+	    {
+	      cDomVect = bitVectInplaceIntersect (cDomVect, pred->domVect);
+	    }
+	  if (!cDomVect)
+	    cDomVect = newBitVect (count);
+	  /* this node to the list */
+	  cDomVect = bitVectSetBit (cDomVect, ebbs[i]->bbnum);
+
+
+	  if (!bitVectEqual (cDomVect, ebbs[i]->domVect))
+	    {
+        freeBitVect (ebbs[i]->domVect);
+	      ebbs[i]->domVect = cDomVect;
+	      change = 1;
+	    }
+	}
+
+      /* if no change then exit */
+      if (!change)
+	break;
+    }
+  
+}
+
+/*-----------------------------------------------------------------*/
+/* immedDom - returns the immediate dominator of a block           */
+/*-----------------------------------------------------------------*/
+eBBlock *
+immedDom (ebbIndex * ebbi, eBBlock * ebp)
+{
+  /* first delete self from the list */
+  set *iset = domSetFromVect (ebbi, ebp->domVect);
+  eBBlock *loop;
+  eBBlock *idom = NULL;
+
+  deleteSetItem (&iset, ebp);
+  /* then just return the one with the greatest */
+  /* depthfirst number, this will be the immed dominator */
+  if ((loop = setFirstItem (iset)))
+    idom = loop;
+  for (; loop; loop = setNextItem (iset))
+    if (loop->dfnum > idom->dfnum)
+      idom = loop;
+
+  setToNull ((void *) &iset);
+  return idom;
+
+}
+
+/*-----------------------------------------------------------------*/
+/* DFOrdering - is visited then nothing else call DFOrdering this  */
+/*-----------------------------------------------------------------*/
+DEFSETFUNC (DFOrdering)
+{
+  eBBlock *ebbp = item;
+  V_ARG (int *, count);
+
+  if (ebbp->visited)
+    return 0;
+
+  computeDFOrdering (ebbp, count);	/* depthfirst */
+
+  return 0;
+}
+
+/*-----------------------------------------------------------------*/
+/* computeDFOrdering - computes the depth first ordering of the    */
+/*                     flowgraph                                   */
+/*-----------------------------------------------------------------*/
+static void 
+computeDFOrdering (eBBlock * ebbp, int *count)
+{
+
+  ebbp->visited = 1;
+  /* for each successor that is not visited */
+  applyToSet (ebbp->succList, DFOrdering, count);
+
+  /* set the depth first number */
+  ebbp->dfnum = *count;
+  *count -= 1;
+}
+
+/*-----------------------------------------------------------------*/
+/* disconBBlock - removes all control flow links for a block       */
+/*-----------------------------------------------------------------*/
+void 
+disconBBlock (eBBlock * ebp, ebbIndex * ebbi)
+{
+  /* mark this block as noPath & recompute control flow */
+  ebp->noPath = 1;
+  computeControlFlow (ebbi);
+}
+
+/*-----------------------------------------------------------------*/
+/* markNoPath - marks those blocks which cannot be reached from top */
+/*-----------------------------------------------------------------*/
+static void 
+markNoPath (ebbIndex * ebbi)
+{
+  eBBlock ** ebbs = ebbi->bbOrder;
+  int count = ebbi->count;
+  int i;
+
+  /* for all blocks if the visited flag is not set : then there */
+  /* is no path from _entry to this block push them down in the */
+  /* depth first order */
+  for (i = 0; i < count; i++)
+    if (!ebbs[i]->visited)
+      ebbs[i]->noPath = 1;
+}
+
+/*-----------------------------------------------------------------*/
+/* dfNumCompare - used by qsort to sort by dfNumber                */
+/*-----------------------------------------------------------------*/
+int 
+dfNumCompare (const void *a, const void *b)
+{
+  const eBBlock *const *i = a;
+  const eBBlock *const *j = b;
+
+  if ((*i)->dfnum > (*j)->dfnum)
+    return 1;
+
+  if ((*i)->dfnum < (*j)->dfnum)
+    return -1;
+
+  return 0;
+}
+
+/*-----------------------------------------------------------------*/
+/* computeControlFlow - does the control flow computation          */
+/*-----------------------------------------------------------------*/
+void 
+computeControlFlow (ebbIndex * ebbi)
+{
+  eBBlock ** ebbs = ebbi->bbOrder;
+  int dfCount = ebbi->count;
+  int i;
+
+  /* initialise some things */
+
+  for (i = 0; i < ebbi->count; i++)
+    {
+      deleteSet (&ebbs[i]->predList);
+      freeBitVect (ebbs[i]->domVect); ebbs[i]->domVect = NULL;
+      deleteSet (&ebbs[i]->succList);
+      freeBitVect (ebbs[i]->succVect); ebbs[i]->succVect = NULL;
+      ebbs[i]->visited = 0;
+      ebbs[i]->dfnum = 0;
+    }
+
+  setToNull ((void *) &graphEdges);
+  /* this will put in the  */
+  /* successor information for each blk */
+  eBBSuccessors (ebbi);
+
+  /* compute the depth first ordering */
+  computeDFOrdering (ebbi->bbOrder[0], &dfCount);
+
+  /* mark blocks with no paths to them */
+  markNoPath (ebbi);
+
+  /* with the depth first info in place */
+  /* add the predecessors for the blocks */
+  eBBPredecessors (ebbi);
+
+  /* compute the dominance graph */
+  computeDominance (ebbi);
+
+  /* sort it by dfnumber */
+  if (!ebbi->dfOrder)
+    ebbi->dfOrder = Safe_alloc ((ebbi->count+1) * sizeof (eBBlock *));
+  for (i = 0; i < (ebbi->count+1); i++)
+    {
+      ebbi->dfOrder[i] = ebbi->bbOrder[i];
+    }
+      
+  qsort (ebbi->dfOrder, ebbi->count, sizeof (eBBlock *), dfNumCompare);
+
+}
+
+/*-----------------------------------------------------------------*/
+/* returnAtEnd - returns 1 if Basic Block has a return at the end  */
+/*               of it                                             */
+/*-----------------------------------------------------------------*/
+int returnAtEnd (eBBlock *ebp)
+{
+    /* case 1.
+       This basic block ends in a return statment 
+    */
+    if (ebp->ech && ebp->ech->op == RETURN) return 1;
+
+    /* case 2.
+       This basic block has only one successor and that
+       successor has only one return statement
+    */
+    if (elementsInSet(ebp->succList) == 1) {
+	eBBlock *succ = setFirstItem(ebp->succList);
+	/* could happen for dummy blocks */
+	if (!succ->sch || !succ->ech) return 0;
+
+	/* first iCode is a return */
+	if (succ->sch->op == RETURN) return 2;
+
+	/* or first iCode is a label & the next &
+	   last icode is a return */
+	if (succ->sch->op == LABEL && succ->sch->next == succ->ech &&
+	    succ->ech->op == RETURN ) return 2;
+    }
+
+    return 0;
+}
+