1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#ifndef DEP_HH
#define DEP_HH
#include <omega.h>
#include "graph.hh"
#include "ir_code.hh"
#include "chill_error.hh"
/*!
* \file
* \brief Data dependence vector and graph.
*
* All dependence vectors are normalized, i.e., the first non-zero distance
* must be positve. Thus the correct dependence meaning can be given based on
* source/destination pair's read/write type. Suppose for a dependence vector
* 1, 0~5, -3), we want to permute the first and the second dimension,
* the result would be two dependence vectors (0, 1, -3) and (1~5, 1, -3).
* All operations on dependence vectors are non-destructive, i.e., new
* dependence vectors are returned.
*/
enum DependenceType {
DEP_W2R, DEP_R2W, DEP_W2W, DEP_R2R, DEP_CONTROL, DEP_UNKNOWN
};
class DependenceVector;
typedef std::vector<DependenceVector> DependenceList;
struct DependenceVector {
DependenceType type;
IR_Symbol *sym;
bool from_same_stmt; // Manu
bool is_reduction_cand; // Manu
bool is_reduction; //!< used to identify a class of flow dependencies that can be broken
std::vector<omega::coef_t> lbounds;
std::vector<omega::coef_t> ubounds;
bool quasi;
bool is_scalar_dependence;
DependenceVector() {
type = DEP_UNKNOWN;
sym = NULL;
is_reduction = false;
from_same_stmt = false; // Manu
is_reduction_cand = false; // Manu
quasi = false;
is_scalar_dependence = false;
}
DependenceVector(const DependenceVector &that);
~DependenceVector() { delete sym; } // is this legal? TODO
DependenceVector &operator=(const DependenceVector &that);
bool is_data_dependence() const;
bool is_control_dependence() const;
bool has_negative_been_carried_at(int dim) const;
bool has_been_carried_at(int dim) const;
bool has_been_carried_before(int dim) const;
// TODO the following functions will be cleaned up or removed later
bool isZero() const;
bool isPositive() const;
bool isNegative() const;
bool isAllPositive() const;
bool isAllNegative() const;
bool isZero(int dim) const;
bool hasPositive(int dim) const;
bool hasNegative(int dim) const;
bool isCarried(int dim, omega::coef_t distance = posInfinity) const;
bool canPermute(const std::vector<int> &pi) const;
std::vector<DependenceVector> normalize() const;
std::vector<DependenceVector> permute(const std::vector<int> &pi) const;
DependenceVector reverse() const;
DependenceType getType() const;
friend std::ostream &operator<<(std::ostream &os, const DependenceVector &d);
};
class DependenceGraph : public Graph<Empty, DependenceVector> {
protected:
int num_dim_;
public:
DependenceGraph(int n) { num_dim_ = n; }
DependenceGraph() { num_dim_ = 0; }
~DependenceGraph() {}
int num_dim() const { return num_dim_; }
DependenceGraph permute(const std::vector<int> &pi,
const std::set<int> &active = std::set<int>()) const;
DependenceGraph subspace(int dim) const;
bool isPositive() const;
bool hasPositive(int dim) const;
bool hasNegative(int dim) const;
};
#endif
|
