Newer
Older
//===---------------- PBQP.cpp --------- PBQP Solver ------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Developed by: Bernhard Scholz
// The Univesity of Sydney
// http://www.it.usyd.edu.au/~scholz
//===----------------------------------------------------------------------===//
#include <limits>
#include <cassert>
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include "PBQP.h"
namespace llvm {
/**************************************************************************
* Data Structures
**************************************************************************/
/* edge of PBQP graph */
typedef struct adjnode {
struct adjnode *prev, /* doubly chained list */
*succ,
*reverse; /* reverse edge */
int adj; /* adj. node */
PBQPMatrix *costs; /* cost matrix of edge */
bool tc_valid; /* flag whether following fields are valid */
int *tc_safe_regs; /* safe registers */
int tc_impact; /* impact */
} adjnode;
/* bucket node */
typedef struct bucketnode {
struct bucketnode *prev; /* doubly chained list */
struct bucketnode *succ;
int u; /* node */
} bucketnode;
/* data structure of partitioned boolean quadratic problem */
struct pbqp {
int num_nodes; /* number of nodes */
int max_deg; /* maximal degree of a node */
bool solved; /* flag that indicates whether PBQP has been solved yet */
bool optimal; /* flag that indicates whether PBQP is optimal */
PBQPNum min;
bool changed; /* flag whether graph has changed in simplification */
/* node fields */
PBQPVector **node_costs; /* cost vectors of nodes */
int *node_deg; /* node degree of nodes */
int *solution; /* solution for node */
adjnode **adj_list; /* adj. list */
bucketnode **bucket_ptr; /* bucket pointer of a node */
/* node stack */
int *stack; /* stack of nodes */
int stack_ptr; /* stack pointer */
/* bucket fields */
bucketnode **bucket_list; /* bucket list */
int num_r0; /* counters for number statistics */
int num_ri;
int num_rii;
int num_rn;
int num_rn_special;
};
bool isInf(PBQPNum n) { return n == std::numeric_limits<PBQPNum>::infinity(); }
/*****************************************************************************
* allocation/de-allocation of pbqp problem
****************************************************************************/
/* allocate new partitioned boolean quadratic program problem */
pbqp *alloc_pbqp(int num_nodes)
{
pbqp *this_;
int u;
assert(num_nodes > 0);
/* allocate memory for pbqp data structure */
this_ = (pbqp *)malloc(sizeof(pbqp));
/* Initialize pbqp fields */
this_->num_nodes = num_nodes;
this_->solved = false;
this_->optimal = true;
this_->min = 0.0;
this_->max_deg = 0;
this_->changed = false;
this_->num_r0 = 0;
this_->num_ri = 0;
this_->num_rii = 0;
this_->num_rn = 0;
this_->num_rn_special = 0;
/* initialize/allocate stack fields of pbqp */
this_->stack = (int *) malloc(sizeof(int)*num_nodes);
this_->stack_ptr = 0;
/* initialize/allocate node fields of pbqp */
this_->adj_list = (adjnode **) malloc(sizeof(adjnode *)*num_nodes);
this_->node_deg = (int *) malloc(sizeof(int)*num_nodes);
this_->solution = (int *) malloc(sizeof(int)*num_nodes);
this_->bucket_ptr = (bucketnode **) malloc(sizeof(bucketnode **)*num_nodes);
this_->node_costs = (PBQPVector**) malloc(sizeof(PBQPVector*) * num_nodes);
for(u=0;u<num_nodes;u++) {
this_->solution[u]=-1;
this_->adj_list[u]=NULL;
this_->node_deg[u]=0;
this_->bucket_ptr[u]=NULL;
this_->node_costs[u]=NULL;
}
/* initialize bucket list */
this_->bucket_list = NULL;
return this_;
}
/* free pbqp problem */
void free_pbqp(pbqp *this_)
{
int u;
int deg;
adjnode *adj_ptr,*adj_next;
bucketnode *bucket,*bucket_next;
assert(this_ != NULL);
/* free node cost fields */
for(u=0;u < this_->num_nodes;u++) {
delete this_->node_costs[u];
}
free(this_->node_costs);
/* free bucket list */
for(deg=0;deg<=this_->max_deg;deg++) {
for(bucket=this_->bucket_list[deg];bucket!=NULL;bucket=bucket_next) {
this_->bucket_ptr[bucket->u] = NULL;
bucket_next = bucket-> succ;
free(bucket);
}
}
free(this_->bucket_list);
/* free adj. list */
assert(this_->adj_list != NULL);
for(u=0;u < this_->num_nodes; u++) {
for(adj_ptr = this_->adj_list[u]; adj_ptr != NULL; adj_ptr = adj_next) {
adj_next = adj_ptr -> succ;
if (u < adj_ptr->adj) {
assert(adj_ptr != NULL);
delete adj_ptr->costs;
}
if (adj_ptr -> tc_safe_regs != NULL) {
free(adj_ptr -> tc_safe_regs);
}
free(adj_ptr);
}
}
free(this_->adj_list);
/* free other node fields */
free(this_->node_deg);
free(this_->solution);
free(this_->bucket_ptr);
/* free stack */
free(this_->stack);
/* free pbqp data structure itself */
free(this_);
}
/****************************************************************************
* adj. node routines
****************************************************************************/
/* find data structure of adj. node of a given node */
static
adjnode *find_adjnode(pbqp *this_,int u,int v)
{
adjnode *adj_ptr;
assert (this_ != NULL);
assert (u >= 0 && u < this_->num_nodes);
assert (v >= 0 && v < this_->num_nodes);
Loading
Loading full blame...