home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Professional
/
OS2PRO194.ISO
/
os2
/
prgramer
/
adaptor
/
src
/
pred.c
< prev
next >
Wrap
C/C++ Source or Header
|
1993-07-08
|
11KB
|
370 lines
/*************************************************************************
* *
* Name : pred.c *
* Purpose : Data Structures for Predicate Vectors and Predicates *
* *
* Author : Dr. Thomas Brandes, GMD, Z1.HR *
* Date : 3. 12. 1991 *
* *
**************************************************************************
/* Data Structures :
PredSimple, PredVector, Predicate
Operations :
PVSetFalse, PVSetExact, PVAndComponent, PVMakeForLoopNest,
PVIsFalse, PVIsExact, PVGetDimension, PVGetComponent
PMakeFalse, POrVector, PHoldConstant, PRestrict,
PIsFalse, PGetLevel
PSOut (Str, ps), PVOut (Str, pv), POut (Str, p)
*/
#include <stdio.h>
#include <string.h>
#include "pred.h"
void PredError (s)
char *s;
{
fprintf (stderr,"Internal Error for Predicates : %s\n", s);
exit (-1);
}
/**************************************************************************
* *
* Generation of direction vectors *
* *
**************************************************************************/
void PVMakeForLoopNest (N, CommonL, ConstL, PV)
int N, CommonL, ConstL;
PredVector * PV;
/* means : Generate predicate (0,0,...,0,>,T,...,T)
1 .. ConstL : 0
ConstL + 1 : '>' if ConstL < CommonL, 'T' otherwise
at least N Loops, CommonL is common Loops,
ConstL are constant loops;
> only if ConstL < CommonL
generated predicate is exact
pre : 0 <= ConstL <= CommonL <= N <= Max_Nested_Loops */
{ int i;
if ( (N < 0) || (ConstL < 0) )
PredError ("PVMakeForLoopNest: N or ConstL < 0");
if ( N > MAX_DIMENSIONS)
PredError ("PVMakeForLoopNest: N too large");
if ( ConstL > N )
PredError ("PVMakeForLoopNest: ConstL > N");
PV->pv_dim = N;
PV->pv_exact = 1;
for (i=0;i<ConstL;i++)
{ PV->pv_arr[i].Low = 0;
PV->pv_arr[i].High = 0;
}
if (ConstL < N)
{ if (ConstL < CommonL)
PV->pv_arr[ConstL].Low = 1; /* make '>' */
else
PV->pv_arr[ConstL].Low = -MaxInt; /* make 'T' */
PV->pv_arr[ConstL].High = MaxInt;
}
for (i=ConstL+1;i<N;i++)
{ PV->pv_arr[i].Low = -MaxInt;
PV->pv_arr[i].High = MaxInt; /* make 'T' */
}
} /* PVMakeForLoopNest */
/*************************************************************************
* *
* Modification operations for predicate vectors *
* *
*************************************************************************/
void PVAndComponent (PV, k, Low1, High1)
PredVector * PV;
int k, Low1, High1;
/* means : PV = (p1, ..., pn) set pk to pk and [Low1,High1] */
{ if ((k > PV->pv_dim) || (k < 1))
PredError ("PVAndComponent: Illegal k");
if (PV->pv_arr[k-1].Low < Low1)
PV->pv_arr[k-1].Low = Low1;
if (PV->pv_arr[k-1].High > High1)
PV->pv_arr[k-1].High = High1;
if (PV->pv_arr[k-1].High < PV->pv_arr[k-1].Low)
PV->pv_dim = -1; /* set PV to FALSE */
} /* PVAndComponent */
void PVSetFalse (PV)
PredVector *PV;
{ PV->pv_dim = -1;
} /* PVSetFalse */
void PVSetNotExact (PV)
/* PV is not exact, if PV is FALSE, PV becomes exact */
PredVector *PV;
{ if ( PV->pv_dim >= 0 )
PV->pv_exact = 0;
}
/**************************************************************************
* *
* Queries for predicate vectors *
* *
***************************************************************************/
int PVIsFalse (PV)
/* True if PV is FALSE */
PredVector *PV;
{ return (PV->pv_dim == -1);
}
int PVIsExact (PV)
/* True if PV is EXACT */
PredVector *PV;
{ return (PV->pv_exact);
}
int PVGetDimension (PV)
PredVector *PV;
{ if (PV->pv_dim == -1)
PredError ("PVGetDimension: False Pred Vector");
return (PV->pv_dim);
}
void PVGetComponent (PV, k, Low, High)
PredVector *PV;
int k, *Low, *High;
/* means : PV = (p1, ..., pn) pk = [Low,High]
pre : 1 <= k <= PV_GET_DIMENSION (PV) */
{ *Low = PV->pv_arr[k-1].Low;
*High = PV->pv_arr[k-1].High;
} /* PVGetComponent */
/**************************************************************************
***************************************************************************
** **
** General Predicates **
** **
***************************************************************************
**************************************************************************/
/**************************************************************************
* *
* Generation Operations for Predicates *
* *
**************************************************************************/
void PMakeFalse (P)
Predicate *P;
/* generate Predicate for FALSE */
{ P->p_dim = 0;
} /* PMakeFalse */
void POrVector (P, PV)
Predicate *P;
PredVector *PV;
{ if (! PVIsFalse (PV) )
{ P->p_arr[P->p_dim] = *PV;
P->p_dim += 1;
}
} /* POrVector */
/**************************************************************************
* *
* Modification Operations for general Predicates *
* *
**************************************************************************/
void PHoldConstant (P, n)
Predicate *P;
int n;
/* Hold n of the outer loops constant and look, which dependences remain
P = ( ... (p1,....,pn,...,pm) ...)
p1, ..., pn = 0 */
{ int h_dim;
PredVector PV;
int i, j;
int Ok;
h_dim = 0;
for (i=0; i<P->p_dim; i++)
{ PV = P->p_arr[i];
if (PV.pv_dim < n)
PredError ("PVHoldConstant: Illegal Predicate");
Ok = 1;
for (j=0; j<n; j++)
Ok = (Ok && (PV.pv_arr[j].Low <= 0) && (PV.pv_arr[j].High >= 0));
if (Ok)
{ for (j=n;j<PV.pv_dim;j++)
PV.pv_arr[j-n] = PV.pv_arr[j];
PV.pv_dim -= n;
P->p_arr[h_dim] = PV;
h_dim += 1;
}
}
P->p_dim = h_dim;
} /* PHoldConstant */
void PRestrict (P, n)
Predicate *P;
int n;
/* means : P = (....( p1, ..., pn, ..., pm) ... ) becomes
(....( p1, ..., pn) , ....) */
{ int i;
for (i=0; i<P->p_dim; i++)
{
if (n > P->p_arr[i].pv_dim)
PredError ("PVRestrict: Illegal");
P->p_arr[i].pv_dim = n;
} /* for all predicate vectors */
} /* PRestrict */
/**************************************************************************
* *
* Queries for general predicates *
* *
**************************************************************************/
int PIsFalse (P)
/* True if P is a predicate for False */
Predicate *P;
{ return (P->p_dim == 0);
}
int PGetLevel (P)
Predicate *P;
/* means : get dependence level, this means the number of the
outermost loop, for which there are loop carried dependences
returns MaxInt if there are only loop independent dependences */
{ int Level, PVLevel, i, j;
PredVector *PV;
/* P = PA[1] or ... or PA[m] , Level = min (Level PA[i]) */
if (P->p_dim == 0)
PredError ("Level for False");
Level = MaxInt; /* neutral element for minimum */
for (i=0; i<P->p_dim; i++)
{ PV = & (P->p_arr[i]);
/* determine Level of PV = (pv(1),..., pv(pn)) */
PVLevel = MaxInt;
for (j=PV->pv_dim-1;j>=0;j--)
{ if (PV->pv_arr[j].High > 0)
PVLevel = j+1;
if (PVLevel < Level)
Level = PVLevel;
}
} /* for every PredVector */
return (Level);
} /* PGetLevel */
/**************************************************************************
* *
* String Representation of Predicates and PredVectors *
* *
**************************************************************************/
char * PSOut (Str, ps)
char * Str;
PredSimple ps;
/* appends textual representation of ps to Str */
{ if (ps.Low == -MaxInt)
{ if (ps.High == -1)
return (strcat (Str,"<"));
if (ps.High == 0)
return (strcat (Str,"<="));
if (ps.High == MaxInt)
return (strcat (Str,"T"));
sprintf (Str,"%s<=%d",Str,ps.High);
return Str;
}
if (ps.High == MaxInt)
{ if (ps.Low == 1)
return (strcat (Str,">"));
if (ps.Low == 0)
return (strcat (Str,">="));
sprintf (Str,"%s>=%d",Str,ps.Low);
return Str;
}
if (ps.Low == ps.High)
{ sprintf (Str,"%s%d",Str,ps.Low);
return (Str);
}
if (ps.Low > ps.High)
return (strcat (Str,"F"));
sprintf (Str,"%s[%d,%d]",Str, ps.Low, ps.High);
return (Str);
} /* PSOut */
char * PVOut (Str, PV)
char * Str;
PredVector *PV;
/* appends the textual representation of PV to Str */
{ int i;
if (PV->pv_dim == 0)
return strcat (Str,"T");
if (PVIsFalse (PV))
return strcat (Str,"F");
Str = strcat (Str,"(");
for (i=0;i<PV->pv_dim;i++)
{ Str = PSOut (Str, PV->pv_arr[i]);
if (i < PV->pv_dim-1)
Str = strcat (Str,",");
}
Str = strcat (Str,")");
if (PV->pv_exact)
return (strcat (Str,"!"));
else
return (strcat (Str,"?"));
} /* PVOut */
char * POut (Str, P)
char * Str;
Predicate *P;
/* appends the textual representation of P to string Str */
{ int i;
if (P->p_dim == 0)
return (strcat (Str,"F"));
Str = strcat (Str,"[");
for (i=0;i<P->p_dim;i++)
{ Str = PVOut (Str, &(P->p_arr[i]) );
if (i < P->p_dim-1)
Str = strcat (Str,",");
}
return (strcat (Str,"]"));
} /* POut */