 Timestamp:
 Aug 24, 2015, 4:14:48 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4747 r4748 62 62 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>; 63 63 using Vertex = Graph::vertex_descriptor; 64 using VertexQueue = circular_buffer<Vertex>; 64 65 65 66 /**  * … … 78 79 79 80 /**  * 81 * @brief push 82 **  */ 83 static inline void push(const Vertex u, VertexQueue & Q) { 84 if (LLVM_UNLIKELY(Q.full())) { 85 Q.set_capacity(Q.capacity() * 2); 86 } 87 Q.push_back(u); 88 assert (Q.back() == u); 89 } 90 91 /**  * 92 * @brief pop 93 **  */ 94 static inline Vertex pop(VertexQueue & Q) { 95 assert (!Q.empty() && "Popping an empty vertex queue"); 96 const Vertex u = Q.front(); 97 Q.pop_front(); 98 return u; 99 } 100 101 /**  * 80 102 * @brief scan 81 103 **  */ … … 83 105 84 106 using Map = std::unordered_map<PabloAST *, Vertex>; 85 using VertexQueue = std::queue<Vertex>;86 107 using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>; 87 88 PabloBuilder builder(block);89 108 90 109 for (Statement * stmt : block) { … … 97 116 Terminals terminals(vars.begin(), vars.end()); 98 117 scan(cast<While>(stmt)>getBody(), std::move(terminals)); 99 } else { 100 builder.record(stmt); 101 } 102 118 } 103 119 } 104 120 … … 106 122 // safely rearrange expressions such as "((((a âš b) âš c) âš d) âš e) âš f" into "((a âš b) âš (c âš d)) âš (e âš f)". 107 123 108 bool modifiedAST = false;124 VertexQueue Q(128); 109 125 110 126 for (;;) { … … 114 130 115 131 // Generate a graph depicting the relationships between the terminals. If the original terminals 116 // cannot be optimized with this algorithm bypass them in favour of their operands. 117 118 VertexQueue Q; 119 unsigned count = 0; 132 // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot 133 // be optimized, they'll be left as the initial terminals for the next "layer" of the AST. 134 120 135 for (Statement * const term : terminals) { 121 136 assert (term); 122 assert (Q.size() == count);123 137 if (isaBooleanOperation(term)) { 124 138 if (LLVM_LIKELY(M.count(term) == 0)) { 125 const autov = add_vertex(term, G);139 const Vertex v = add_vertex(term, G); 126 140 assert (v < num_vertices(G)); 127 141 M.insert(std::make_pair(term, v)); 128 Q.push(v); 129 ++count; 142 push(v, Q); 130 143 } 131 144 } else { … … 134 147 assert (op); 135 148 if (LLVM_LIKELY(isa<Statement>(op) && M.count(op) == 0)) { 136 const autov = add_vertex(op, G);149 const Vertex v = add_vertex(op, G); 137 150 assert (v < num_vertices(G)); 138 151 M.insert(std::make_pair(op, v)); 139 Q.push(v); 140 ++count; 152 push(v, Q); 141 153 } 142 154 } … … 144 156 } 145 157 158 if (Q.empty()) { 159 break; 160 } 161 146 162 for (;;) { 147 assert (Q.size() == count); 148 const Vertex u = Q.front(); Q.pop(); 149 count; 163 const Vertex u = pop(Q); 150 164 assert (u < num_vertices(G)); 151 165 if (isaBooleanOperation(G[u])) { … … 156 170 auto f = M.find(op); 157 171 if (f == M.end()) { 158 const autov = add_vertex(op, G);172 const Vertex v = add_vertex(op, G); 159 173 assert (v < num_vertices(G)); 160 174 f = M.insert(std::make_pair(op, v)).first; 161 175 if (op>getClassTypeId() == stmt>getClassTypeId() && cast<Statement>(op)>getParent() == &block) { 162 Q.push(v); 163 ++count; 176 push(v, Q); 164 177 } 165 178 } … … 199 212 // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because 200 213 // the instructions corresponding to the pair of nodes differs. 201 EdgeQueue Q;214 EdgeQueue E; 202 215 graph_traits<Graph>::edge_iterator ei, ei_end; 203 216 for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) { … … 206 219 const Vertex v = target(e, G); 207 220 if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) { 208 Q.push(std::make_pair(u, v));221 E.push(std::make_pair(u, v)); 209 222 remove_edge(u, v, G); 210 223 } … … 212 225 213 226 // If no cuts are necessary, we're done. 214 if ( Q.empty()) {227 if (E.empty()) { 215 228 break; 216 229 } … … 219 232 220 233 Vertex u, v; 221 std::tie(u, v) = Q.front(); Q.pop();234 std::tie(u, v) = E.front(); E.pop(); 222 235 223 236 // The vertex belonging to a component with a greater number must come "earlier" … … 242 255 if (in_degree(u, G) != 0) { 243 256 for (auto e : make_iterator_range(out_edges(u, G))) { 244 Q.push(std::make_pair(source(e, G), target(e, G)));257 E.push(std::make_pair(source(e, G), target(e, G))); 245 258 } 246 259 clear_out_edges(u, G); 247 260 } 248 261 249 if ( Q.empty()) {262 if (E.empty()) { 250 263 break; 251 264 } … … 263 276 flat_map<Vertex, unsigned> L; 264 277 flat_set<PabloAST *> V; 265 VertexQueue Q;266 278 267 279 Vertex v = u; … … 282 294 f>second = std::max(f>second, l); 283 295 } 284 Q.push(w);296 push(w, Q); 285 297 } 286 298 } … … 288 300 break; 289 301 } 290 v = Q.front(); 291 Q.pop(); 302 v = pop(Q); 292 303 } 293 304 … … 307 318 PabloAST * e1 = Q.front(); Q.pop_front(); 308 319 PabloAST * e2 = Q.front(); Q.pop_front(); 309 Q.push_back(b uilder.createAnd(e1, e2));320 Q.push_back(block.createAnd(e1, e2)); 310 321 } 311 322 } else if (isa<Or>(stmt)) { … … 313 324 PabloAST * e1 = Q.front(); Q.pop_front(); 314 325 PabloAST * e2 = Q.front(); Q.pop_front(); 315 Q.push_back(b uilder.createOr(e1, e2));326 Q.push_back(block.createOr(e1, e2)); 316 327 } 317 328 } else { assert(isa<Xor>(stmt)); … … 319 330 PabloAST * e1 = Q.front(); Q.pop_front(); 320 331 PabloAST * e2 = Q.front(); Q.pop_front(); 321 Q.push_back(builder.createXor(e1, e2)); 322 } 323 } 324 stmt>replaceWith(Q.front(), true, false); 325 modifiedAST = true; 332 Q.push_back(block.createXor(e1, e2)); 333 } 334 } 335 stmt>replaceWith(Q.front(), true, true); 326 336 } 327 337 } … … 350 360 terminals.assign(nextSet.begin(), nextSet.end()); 351 361 } 352 353 // If we modified the AST, we likely left dead code in it. Go through and remove any from this block.354 if (modifiedAST) {355 Statement * stmt = block.front();356 while (stmt) {357 if (stmt>getNumUses() == 0 && !(isa<If>(stmt)  isa<While>(stmt))){358 stmt = stmt>eraseFromParent(true);359 } else {360 stmt = stmt>getNextNode();361 }362 }363 }364 362 } 365 363
Note: See TracChangeset
for help on using the changeset viewer.