home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / adaptor.zip / adapt.zip / adaptor / src / pred.c < prev    next >
C/C++ Source or Header  |  1993-07-08  |  11KB  |  370 lines
  1. /*************************************************************************
  2. *                                                                        *
  3. *  Name : pred.c                                                         *
  4. *  Purpose : Data Structures for Predicate Vectors and Predicates        *
  5. *                                                                        *
  6. *  Author : Dr. Thomas Brandes, GMD, Z1.HR                               *
  7. *  Date   : 3. 12. 1991                                                  *
  8. *                                                                        *
  9. **************************************************************************
  10.  
  11. /* Data Structures :
  12.  
  13.    PredSimple, PredVector, Predicate
  14.  
  15.    Operations :
  16.  
  17.    PVSetFalse, PVSetExact, PVAndComponent, PVMakeForLoopNest,
  18.    PVIsFalse, PVIsExact, PVGetDimension, PVGetComponent
  19.  
  20.    PMakeFalse, POrVector, PHoldConstant, PRestrict,
  21.    PIsFalse, PGetLevel
  22.  
  23.    PSOut (Str, ps), PVOut (Str, pv), POut (Str, p)
  24.  
  25. */
  26.  
  27. #include <stdio.h>
  28. #include <string.h>
  29. #include "pred.h"
  30.  
  31. void PredError (s)
  32. char *s;
  33. {
  34.    fprintf (stderr,"Internal Error for Predicates : %s\n", s);
  35.    exit (-1);
  36. }
  37.  
  38. /**************************************************************************
  39. *                                                                         *
  40. *  Generation of direction vectors                                        *
  41. *                                                                         *
  42. **************************************************************************/
  43.  
  44. void PVMakeForLoopNest (N, CommonL, ConstL, PV)
  45. int N, CommonL, ConstL;
  46. PredVector * PV;
  47.  
  48. /* means : Generate predicate  (0,0,...,0,>,T,...,T)
  49.                   1 .. ConstL : 0
  50.                   ConstL + 1  : '>' if ConstL < CommonL, 'T' otherwise
  51.  
  52.            at least N Loops, CommonL is common Loops,
  53.            ConstL are constant loops;
  54.            > only if ConstL < CommonL
  55.  
  56.            generated predicate is exact
  57.  
  58.   pre   : 0 <= ConstL <= CommonL <= N <= Max_Nested_Loops                  */
  59.  
  60. { int i;
  61.  
  62.   if ( (N < 0) || (ConstL < 0) )
  63.      PredError ("PVMakeForLoopNest: N or ConstL < 0");
  64.   if ( N > MAX_DIMENSIONS)
  65.      PredError ("PVMakeForLoopNest: N too large");
  66.   if ( ConstL > N )
  67.      PredError ("PVMakeForLoopNest: ConstL > N");
  68.   PV->pv_dim = N;
  69.   PV->pv_exact = 1;
  70.   for (i=0;i<ConstL;i++)
  71.      {  PV->pv_arr[i].Low =  0;
  72.         PV->pv_arr[i].High = 0;
  73.      }
  74.   if (ConstL < N)
  75.      { if (ConstL < CommonL)
  76.            PV->pv_arr[ConstL].Low = 1;         /* make '>' */
  77.          else
  78.            PV->pv_arr[ConstL].Low = -MaxInt;      /* make 'T' */
  79.        PV->pv_arr[ConstL].High = MaxInt;
  80.      }
  81.   for (i=ConstL+1;i<N;i++)
  82.      { PV->pv_arr[i].Low = -MaxInt;
  83.        PV->pv_arr[i].High = MaxInt;    /* make 'T' */
  84.      }
  85. } /* PVMakeForLoopNest */
  86.  
  87. /*************************************************************************
  88.  *                                                                       *
  89.  *   Modification operations for predicate vectors                       *
  90.  *                                                                       *
  91.  *************************************************************************/
  92.  
  93. void PVAndComponent (PV, k, Low1, High1)
  94. PredVector * PV;
  95. int k, Low1, High1;
  96.  
  97. /*  means : PV = (p1, ..., pn)   set pk to pk and [Low1,High1] */
  98.  
  99. {  if ((k > PV->pv_dim) || (k < 1))
  100.       PredError ("PVAndComponent: Illegal k");
  101.    if (PV->pv_arr[k-1].Low < Low1)
  102.       PV->pv_arr[k-1].Low = Low1;
  103.    if (PV->pv_arr[k-1].High > High1)
  104.       PV->pv_arr[k-1].High = High1;
  105.    if (PV->pv_arr[k-1].High < PV->pv_arr[k-1].Low)
  106.       PV->pv_dim = -1;     /* set PV to FALSE */
  107. }  /* PVAndComponent */
  108.  
  109. void PVSetFalse (PV)
  110. PredVector *PV;
  111. {  PV->pv_dim = -1;
  112. } /* PVSetFalse */
  113.  
  114. void PVSetNotExact (PV)
  115. /* PV is not exact, if PV is FALSE, PV becomes exact */
  116. PredVector *PV;
  117. { if ( PV->pv_dim >= 0 )
  118.     PV->pv_exact = 0;
  119. }
  120.  
  121. /**************************************************************************
  122. *                                                                         *
  123. *   Queries for predicate vectors                                         *
  124. *                                                                         *
  125. ***************************************************************************/
  126.  
  127. int PVIsFalse (PV)
  128. /* True if PV is FALSE */
  129. PredVector *PV;
  130. { return (PV->pv_dim == -1);
  131. }
  132.  
  133. int PVIsExact (PV)
  134. /* True if PV is EXACT */
  135. PredVector *PV;
  136. { return (PV->pv_exact);
  137. }
  138.  
  139. int PVGetDimension (PV)
  140. PredVector *PV;
  141. { if (PV->pv_dim == -1)
  142.      PredError ("PVGetDimension: False Pred Vector");
  143.   return (PV->pv_dim);
  144. }
  145.  
  146. void PVGetComponent (PV, k, Low, High)
  147. PredVector *PV;
  148. int k, *Low, *High;
  149.  
  150. /* means : PV = (p1, ..., pn)   pk = [Low,High]
  151.    pre   : 1 <= k <= PV_GET_DIMENSION (PV)          */
  152.  
  153. {  *Low = PV->pv_arr[k-1].Low;
  154.    *High = PV->pv_arr[k-1].High;
  155. }  /* PVGetComponent */
  156.  
  157. /**************************************************************************
  158. ***************************************************************************
  159. **                                                                       **
  160. **     General  Predicates                                               **
  161. **                                                                       **
  162. ***************************************************************************
  163. **************************************************************************/
  164.  
  165.  
  166. /**************************************************************************
  167. *                                                                         *
  168. *   Generation Operations for Predicates                                  *
  169. *                                                                         *
  170. **************************************************************************/
  171.  
  172. void PMakeFalse (P)
  173. Predicate *P;
  174.  
  175. /* generate Predicate for FALSE */
  176.  
  177. { P->p_dim = 0;
  178. } /* PMakeFalse */
  179.  
  180. void POrVector (P, PV)
  181. Predicate *P;
  182. PredVector *PV;
  183.  
  184. { if (! PVIsFalse (PV) )
  185.      {  P->p_arr[P->p_dim] = *PV;
  186.         P->p_dim += 1;
  187.      }
  188. } /* POrVector */
  189.  
  190. /**************************************************************************
  191. *                                                                         *
  192. *   Modification Operations for general Predicates                        *
  193. *                                                                         *
  194. **************************************************************************/
  195.  
  196. void PHoldConstant (P, n)
  197. Predicate *P;
  198. int n;
  199.  
  200. /* Hold n of the outer loops constant and look, which dependences remain
  201.  
  202.    P = ( ... (p1,....,pn,...,pm) ...)
  203.    p1, ..., pn = 0                                 */
  204.  
  205. {  int h_dim;
  206.    PredVector PV;
  207.    int i, j;
  208.    int Ok;
  209.  
  210.    h_dim = 0;
  211.    for (i=0; i<P->p_dim; i++)
  212.       { PV = P->p_arr[i];
  213.         if (PV.pv_dim < n)
  214.            PredError ("PVHoldConstant: Illegal Predicate");
  215.         Ok = 1;
  216.         for (j=0; j<n; j++)
  217.            Ok = (Ok && (PV.pv_arr[j].Low <= 0) && (PV.pv_arr[j].High >= 0));
  218.         if (Ok)
  219.           { for (j=n;j<PV.pv_dim;j++)
  220.                 PV.pv_arr[j-n] = PV.pv_arr[j];
  221.             PV.pv_dim -= n;
  222.             P->p_arr[h_dim] = PV;
  223.             h_dim += 1;
  224.           }
  225.       }
  226.    P->p_dim = h_dim;
  227. } /* PHoldConstant */
  228.  
  229. void PRestrict (P, n)
  230. Predicate *P;
  231. int n;
  232.  
  233. /* means : P = (....( p1, ..., pn, ..., pm) ... ) becomes
  234.                (....( p1, ..., pn) , ....)                   */
  235.  
  236. { int i;
  237.  
  238.   for (i=0; i<P->p_dim; i++)
  239.      {
  240.        if (n > P->p_arr[i].pv_dim)
  241.           PredError ("PVRestrict: Illegal");
  242.        P->p_arr[i].pv_dim = n;
  243.      } /* for all predicate vectors */
  244.  
  245. }  /* PRestrict */
  246.  
  247. /**************************************************************************
  248. *                                                                         *
  249. *   Queries for general predicates                                        *
  250. *                                                                         *
  251. **************************************************************************/
  252.  
  253. int PIsFalse (P)
  254. /* True if P is a predicate for False */
  255. Predicate *P;
  256. { return (P->p_dim == 0);
  257. }
  258.  
  259. int PGetLevel (P)
  260. Predicate *P;
  261.  
  262. /* means : get dependence level, this means the number of the
  263.            outermost loop, for which there are loop carried dependences
  264.  
  265.            returns MaxInt if there are only loop independent dependences    */
  266.  
  267. { int Level, PVLevel, i, j;
  268.   PredVector *PV;
  269.   /*  P = PA[1] or ... or PA[m] , Level = min (Level PA[i])  */
  270.  
  271.   if (P->p_dim == 0)
  272.      PredError ("Level for False");
  273.   Level = MaxInt;   /*  neutral element for minimum   */
  274.   for (i=0; i<P->p_dim; i++)
  275.       { PV = & (P->p_arr[i]);
  276.         /* determine Level of PV = (pv(1),..., pv(pn))  */
  277.         PVLevel = MaxInt;
  278.         for (j=PV->pv_dim-1;j>=0;j--)
  279.           {  if (PV->pv_arr[j].High > 0)
  280.                 PVLevel = j+1;
  281.              if (PVLevel < Level)
  282.                 Level = PVLevel;
  283.           }
  284.       } /* for every PredVector */
  285.   return (Level);
  286. } /* PGetLevel */
  287.  
  288. /**************************************************************************
  289. *                                                                         *
  290. *   String Representation of Predicates and PredVectors                   *
  291. *                                                                         *
  292. **************************************************************************/
  293.  
  294. char * PSOut (Str, ps)
  295. char * Str;
  296. PredSimple ps;
  297.  
  298. /* appends textual representation of ps to Str */
  299.  
  300. {  if (ps.Low == -MaxInt)
  301.       { if (ps.High == -1)
  302.            return (strcat (Str,"<"));
  303.         if (ps.High == 0)
  304.            return (strcat (Str,"<="));
  305.         if (ps.High == MaxInt)
  306.            return (strcat (Str,"T"));
  307.         sprintf (Str,"%s<=%d",Str,ps.High);
  308.         return Str;
  309.       }
  310.    if (ps.High == MaxInt)
  311.       { if (ps.Low == 1)
  312.            return (strcat (Str,">"));
  313.         if (ps.Low == 0)
  314.            return (strcat (Str,">="));
  315.         sprintf (Str,"%s>=%d",Str,ps.Low);
  316.         return Str;
  317.       }
  318.    if (ps.Low == ps.High)
  319.       { sprintf (Str,"%s%d",Str,ps.Low);
  320.         return (Str);
  321.       }
  322.    if (ps.Low > ps.High)
  323.        return (strcat (Str,"F"));
  324.    sprintf (Str,"%s[%d,%d]",Str, ps.Low, ps.High);
  325.    return (Str);
  326. } /* PSOut */
  327.  
  328. char * PVOut (Str, PV)
  329. char * Str;
  330. PredVector *PV;
  331.  
  332. /* appends the textual representation of PV to Str */
  333. { int i;
  334.   if (PV->pv_dim == 0)
  335.      return strcat (Str,"T");
  336.   if (PVIsFalse (PV))
  337.      return strcat (Str,"F");
  338.   Str = strcat (Str,"(");
  339.   for (i=0;i<PV->pv_dim;i++)
  340.      { Str = PSOut (Str, PV->pv_arr[i]);
  341.        if (i < PV->pv_dim-1)
  342.           Str = strcat (Str,",");
  343.      }
  344.   Str = strcat (Str,")");
  345.   if (PV->pv_exact)
  346.      return (strcat (Str,"!"));
  347.     else
  348.      return (strcat (Str,"?"));
  349. } /* PVOut */
  350.  
  351. char * POut (Str, P)
  352. char * Str;
  353. Predicate *P;
  354.  
  355. /* appends the textual representation of P to string Str */
  356.  
  357. { int i;
  358.  
  359.   if (P->p_dim == 0)
  360.      return (strcat (Str,"F"));
  361.   Str = strcat (Str,"[");
  362.   for (i=0;i<P->p_dim;i++)
  363.     {  Str = PVOut (Str, &(P->p_arr[i]) );
  364.        if (i < P->p_dim-1)
  365.           Str = strcat (Str,",");
  366.     }
  367.   return (strcat (Str,"]"));
  368. } /* POut */
  369.  
  370.