Changeset 4769
 Timestamp:
 Sep 13, 2015, 1:17:44 AM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4768 r4769 21 21 namespace pablo { 22 22 23 using TypeId = PabloAST::ClassTypeId; 23 24 using Graph = BooleanReassociationPass::Graph; 24 25 using Vertex = Graph::vertex_descriptor; … … 26 27 using Map = BooleanReassociationPass::Map; 27 28 using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>; 28 using TypeId = PabloAST::ClassTypeId;29 29 using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>; 30 30 using DistributionMap = flat_map<Graph::vertex_descriptor, DistributionGraph::vertex_descriptor>; … … 33 33 using Biclique = std::pair<VertexSet, VertexSet>; 34 34 using BicliqueSet = std::vector<Biclique>; 35 using DistributionSet = std::tuple< std::vector<Vertex>, std::vector<Vertex>, std::vector<Vertex>>;35 using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>; 36 36 using DistributionSets = std::vector<DistributionSet>; 37 37 … … 83 83 } 84 84 85 static unsigned distributionCount = 0;86 85 /**  * 87 86 * @brief optimize … … 138 137 139 138 /**  * 139 * @brief inCurrentBlock 140 **  */ 141 static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) { 142 return stmt>getParent() == █ 143 } 144 145 static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) { 146 return expr ? isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block) : true; 147 } 148 149 /**  * 140 150 * @brief isOptimizable 141 151 * … … 143 153 * safely rearrange expressions such as "((((a âš b) âš c) âš d) âš e) âš f" into "((a âš b) âš (c âš d)) âš (e âš f)". 144 154 **  */ 145 static inline bool isOptimizable(const PabloAST * const expr) { 146 assert (expr); 147 switch (expr>getClassTypeId()) { 155 inline bool BooleanReassociationPass::isOptimizable(const VertexData & data) { 156 switch (data.first) { 148 157 case PabloAST::ClassTypeId::And: 149 158 case PabloAST::ClassTypeId::Or: … … 155 164 } 156 165 157 /**  * 158 * @brief inCurrentBlock 159 **  */ 160 static inline bool inCurrentBlock(const Statement * stmt, const PabloBlock & block) { 161 return stmt>getParent() == █ 162 } 163 164 static inline bool inCurrentBlock(const PabloAST * expr, const PabloBlock & block) { 165 return isa<Statement>(expr) && inCurrentBlock(cast<Statement>(expr), block); 166 } 166 inline bool isNegated(const BooleanReassociationPass::VertexData & data) { 167 return (data.first == TypeId::Not) && (data.second != nullptr); 168 } 169 170 inline bool BooleanReassociationPass::isMutable(const VertexData & data, const PabloBlock &) { 171 return (data.first != TypeId::Var); 172 } 173 174 inline bool BooleanReassociationPass::isNonEscaping(const VertexData & data) { 175 return data.first != TypeId::Assign && data.first != TypeId::Next; 176 } 177 178 inline bool BooleanReassociationPass::isSameType(const VertexData & data1, const VertexData & data2) { 179 return data1.first == data2.first; 180 } 181 167 182 168 183 /**  * … … 185 200 static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) { 186 201 raw_os_ostream out(std::cerr); 187 188 std::vector<unsigned> component(num_vertices(G));189 strong_components(G, make_iterator_property_map(component.begin(), get(vertex_index, G)));190 191 std::vector<Vertex> ordering;192 ordering.reserve(num_vertices(G));193 topological_sort(G, std::back_inserter(ordering));194 std::reverse(ordering.begin(), ordering.end());195 196 202 out << "digraph " << name << " {\n"; 197 for (auto u : ordering) {203 for (auto u : make_iterator_range(vertices(G))) { 198 204 if (in_degree(u, G) == 0 && out_degree(u, G) == 0) { 199 205 continue; 200 206 } 201 207 out << "v" << u << " [label=\""; 202 PabloAST * expr = G[u]; 203 if (isa<Statement>(expr)) { 208 PabloAST * expr; 209 TypeId typeId; 210 std::tie(typeId, expr) = G[u]; 211 bool temporary = false; 212 bool error = false; 213 if (expr == nullptr) { 214 temporary = true; 215 out << u << ": "; 216 switch (typeId) { 217 case TypeId::And: 218 out << "And"; 219 break; 220 case TypeId::Or: 221 out << "Or"; 222 break; 223 case TypeId::Xor: 224 out << "Xor"; 225 break; 226 default: 227 out << "???"; 228 error = true; 229 break; 230 } 231 } else if (isa<Statement>(expr)) { 204 232 if (LLVM_UNLIKELY(isa<If>(expr))) { 205 233 out << "If "; … … 217 245 } 218 246 out << "\""; 219 if ( !inCurrentBlock(expr, block)) {247 if (BooleanReassociationPass::isMutable(G[u], block) == false) { 220 248 out << " style=dashed"; 221 249 } 250 if (error) { 251 out << " color=red"; 252 } else if (temporary) { 253 out << " color=blue"; 254 } 222 255 out << "];\n"; 223 256 } 224 225 257 for (auto e : make_iterator_range(edges(G))) { 226 const auto i = source(e, G), j = target(e, G); 227 out << "v" << i << " > v" << j; 228 if (LLVM_UNLIKELY(component[i] == component[j])) { 229 out << "[color=red]"; 258 out << "v" << source(e, G) << " > v" << target(e, G); 259 if (G[e]) { 260 out << " [label=\""; 261 PabloPrinter::print(G[e], out); 262 out << "\"]"; 230 263 } 231 264 out << ";\n"; … … 235 268 236 269 out << "{ rank=same;"; 237 for (auto u : ordering) {270 for (auto u : make_iterator_range(vertices(G))) { 238 271 if (in_degree(u, G) == 0 && out_degree(u, G) != 0) { 239 272 out << " v" << u; … … 243 276 244 277 out << "{ rank=same;"; 245 for (auto u : ordering) {278 for (auto u : make_iterator_range(vertices(G))) { 246 279 if (out_degree(u, G) == 0 && in_degree(u, G) != 0) { 247 280 out << " v" << u; … … 257 290 258 291 /**  * 259 * @brief printGraph260 **  */261 template<typename SubgraphType>262 static void printGraph(const PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) {263 raw_os_ostream out(std::cerr);264 out << "digraph " << name << " {\n";265 for (auto u : make_iterator_range(vertices(S))) {266 if (in_degree(u, S) == 0 && out_degree(u, S) == 0) {267 continue;268 }269 out << "v" << u << " [label=\"";270 PabloAST * expr = G[S[u]];271 if (isa<Statement>(expr)) {272 if (LLVM_UNLIKELY(isa<If>(expr))) {273 out << "If ";274 PabloPrinter::print(cast<If>(expr)>getOperand(0), out);275 out << ":";276 } else if (LLVM_UNLIKELY(isa<While>(expr))) {277 out << "While ";278 PabloPrinter::print(cast<While>(expr)>getOperand(0), out);279 out << ":";280 } else {281 PabloPrinter::print(cast<Statement>(expr), "", out);282 }283 } else {284 PabloPrinter::print(expr, out);285 }286 out << "\"";287 if (!inCurrentBlock(expr, block)) {288 out << " style=dashed";289 }290 out << "];\n";291 }292 for (auto e : make_iterator_range(edges(S))) {293 out << "v" << source(e, S) << " > v" << target(e, S) << ";\n";294 }295 296 if (num_vertices(S) > 0) {297 298 out << "{ rank=same;";299 for (auto u : make_iterator_range(vertices(S))) {300 if (in_degree(u, S) == 0 && out_degree(u, S) != 0) {301 out << " v" << u;302 }303 }304 out << "}\n";305 306 out << "{ rank=same;";307 for (auto u : make_iterator_range(vertices(S))) {308 if (out_degree(u, S) == 0 && in_degree(u, S) != 0) {309 out << " v" << u;310 }311 }312 out << "}\n";313 314 }315 316 out << "}\n\n";317 out.flush();318 }319 320 321 /**  *322 292 * @brief createTree 323 293 **  */ 324 static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) { 294 static Statement * createTree(PabloBlock & block, const Vertex u, Graph & G) { 295 circular_buffer<PabloAST *> Q(in_degree(u, G)); 296 for (const auto e : make_iterator_range(in_edges(u, G))) { 297 PabloAST * expr = G[source(e, G)].second; 298 assert (expr); 299 assert (std::find(Q.begin(), Q.end(), expr) == Q.end()); 300 Q.push_back(expr); 301 } 325 302 assert (Q.size() > 1); 303 const TypeId typeId = G[u].first; 326 304 while (Q.size() > 1) { 327 305 PabloAST * e1 = Q.front(); Q.pop_front(); … … 340 318 Q.push_back(expr); 341 319 } 342 PabloAST * const expr = Q.front();343 Q.clear();344 return expr;320 Statement * const result = cast<Statement>(Q.front()); 321 G[u].second = result; 322 return result; 345 323 } 346 324 … … 351 329 Graph G; 352 330 331 raw_os_ostream out(std::cerr); 332 out << "============================================================\n"; 333 PabloPrinter::print(function.getEntryBlock().statements(), out); 334 out << "\n"; 335 out.flush(); 336 353 337 summarizeAST(block, G); 354 assert (summarizeGraph(block, G) == false);355 338 redistributeAST(block, G); 356 assert (summarizeGraph(block, G) == false);357 358 raw_os_ostream out(std::cerr);359 out << "======================================================\n";360 PabloPrinter::print(block, " > ", out);361 out << "\n";362 out.flush();363 364 printGraph(block, G, "G");365 366 out << "\n";367 339 368 340 circular_buffer<Vertex> Q(num_vertices(G)); … … 372 344 while (!Q.empty()) { 373 345 const Vertex u = Q.back(); Q.pop_back(); 374 if (LLVM_LIKELY(i n_degree(u, G) != 0  out_degree(u, G) != 0)) {375 if (LLVM_LIKELY(inCurrentBlock(G[u], block))) {376 Statement * stmt = cast<Statement>(G[u]);377 PabloPrinter::print(stmt, "  ", out); out << '\n';378 if (isOptimizable(stmt)) {379 circular_buffer<PabloAST *> nodes(in_degree(u, G));380 for (auto e : make_iterator_range(in_edges(u, G))) {381 nodes.push_back(G[source(e, G)]);382 }383 Statement * replacement = cast<Statement>(createTree(block, stmt>getClassTypeId(), nodes));384 stmt>replaceWith(replacement, false, true);385 G[u] = stmt = replacement;386 PabloPrinter::print(replacement, " > replaced with ", out);out << '\n';387 } else {388 for (const auto e : make_iterator_range(in_edges(u, G))) {389 const auto v = source(e, G);390 if (LLVM_UNLIKELY(G[v] != G[e])) {391 392 393 394 395 396 397 398 399 400 } 401 402 out << "\n"; 403 PabloPrinter::print(block, " < ", out);404 out << "\n";346 if (LLVM_LIKELY(isMutable(G[u], block))) { 347 out << "Mutable: " << u << ": "; 348 PabloPrinter::print(G[u].second, out); 349 out.flush(); 350 Statement * stmt = nullptr; 351 if (isOptimizable(G[u])) { 352 stmt = createTree(block, u, G); 353 } else { // update any potential mappings 354 stmt = cast<Statement>(G[u].second); 355 } 356 assert (stmt); 357 PabloPrinter::print(stmt, " > ", out); 358 out << '\n'; 359 out.flush(); 360 assert (stmt>getParent() == &block); 361 for (auto e : make_iterator_range(out_edges(u, G))) { 362 if (G[e] && G[e] != stmt) { 363 PabloAST * expr = G[target(e, G)].second; 364 if (expr) { // processing a yettobe created value 365 cast<Statement>(expr)>replaceUsesOfWith(G[e], stmt); 366 } 367 } 368 } 369 block.insert(stmt); 370 } 371 } 372 373 Simplifier::deadCodeElimination(function.getEntryBlock()); 374 375 out << "\n"; 376 PabloPrinter::print(function.getEntryBlock().statements(), out); 405 377 out.flush(); 406 378 407 379 PabloVerifier::verify(function); 380 } 381 382 /**  * 383 * @brief getVertex 384 **  */ 385 static inline Vertex getVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block) { 386 const auto f = M.find(expr); 387 if (f != M.end()) { 388 return f>second; 389 } 390 // To simplify future analysis, every statement not in the current block will be recorded as a Var. 391 const TypeId typeId = inCurrentBlock(expr, block) ? expr>getClassTypeId() : TypeId::Var; 392 const auto u = add_vertex(std::make_pair(typeId, expr), G); 393 M.insert(std::make_pair(expr, u)); 394 return u; 408 395 } 409 396 … … 411 398 * @brief summarizeAST 412 399 * 413 * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences 414 * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to 415 * reassociate them in the most efficient way possible. 400 * This function scans through a scope blockand computes a DAG G in which any sequences of AND, OR or XOR functions 401 * are "flattened" (i.e., allowed to have any number of inputs.) 416 402 **  */ 417 403 void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const { … … 419 405 // Compute the base defuse graph ... 420 406 for (Statement * stmt : block) { 421 const Vertex u = getVertex(stmt, G, M );407 const Vertex u = getVertex(stmt, G, M, block); 422 408 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) { 423 409 PabloAST * const op = stmt>getOperand(i); … … 425 411 continue; 426 412 } 427 add_edge(op, getVertex(op, G, M), u, G); 413 const Vertex v = getVertex(op, G, M, block); 414 if (!edge(v, u, G).second) { 415 add_edge(op, v, u, G); 416 } 417 // If this operand is a Not operation that is not in this PabloBlock, 418 // pull its input operand in. It may lead to future optimizations. 419 if (LLVM_UNLIKELY(isa<Not>(op) && !inCurrentBlock(cast<Not>(op), block))) { 420 PabloAST * const neg = cast<Not>(op)>getExpr(); 421 const Vertex w = getVertex(neg, G, M, block); 422 if (!edge(w, v, G).second) { 423 add_edge(neg, w, v, G); 424 } 425 } 428 426 } 429 427 if (isa<If>(stmt)) { 430 428 for (Assign * def : cast<const If>(stmt)>getDefined()) { 431 const Vertex v = getVertex(def, G, M );429 const Vertex v = getVertex(def, G, M, block); 432 430 add_edge(def, u, v, G); 433 431 resolveUsages(v, def, block, G, M, stmt); … … 435 433 } else if (isa<While>(stmt)) { 436 434 for (Next * var : cast<const While>(stmt)>getVariants()) { 437 const Vertex v = getVertex(var, G, M );435 const Vertex v = getVertex(var, G, M, block); 438 436 add_edge(var, u, v, G); 439 437 resolveUsages(v, var, block, G, M, stmt); … … 443 441 } 444 442 } 445 summarizeGraph(block, G); 446 } 447 448 /**  * 449 * @brief resolveUsages 450 **  */ 451 bool BooleanReassociationPass::summarizeGraph(PabloBlock & block, Graph & G) { 452 bool modified = false; 453 std::vector<Vertex> reverseTopologicalOrdering; 454 reverseTopologicalOrdering.reserve(num_vertices(G)); 455 topological_sort(G, std::back_inserter(reverseTopologicalOrdering)); 456 for (const Vertex u : reverseTopologicalOrdering) { 457 if (isOptimizable(G[u]) && inCurrentBlock(G[u], block)) { 458 if (LLVM_UNLIKELY(in_degree(u, G) == 1)) { 459 // We have a redundant node here that'll simply end up being a duplicate 460 // of the input value. Remove it and add any of its outgoing edges to its 461 // input node. 462 const auto ei = first(in_edges(u, G)); 463 const Vertex v = source(ei, G); 464 for (auto ej : make_iterator_range(out_edges(u, G))) { 465 add_edge(G[ei], v, target(ej, G), G); 466 } 467 clear_vertex(u, G); 468 modified = true; 469 continue; 470 } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) { 471 // Otherwise if we have a single user, we have a similar case as above but 472 // we can only merge this vertex into the outgoing instruction if they are 473 // of the same type. 474 const auto ei = first(out_edges(u, G)); 475 const Vertex v = target(ei, G); 476 if (LLVM_UNLIKELY(G[v]>getClassTypeId() == G[u]>getClassTypeId())) { 477 for (auto ej : make_iterator_range(in_edges(u, G))) { 478 add_edge(G[ei], source(ej, G), v, G); 479 } 480 clear_vertex(u, G); 481 modified = true; 482 continue; 483 } 484 } 485 } 486 // Finally, eliminate any unnecessary instruction 487 if (LLVM_UNLIKELY(out_degree(u, G) == 0 && !(isa<Assign>(G[u])  isa<Next>(G[u])))) { 488 clear_in_edges(u, G); 489 } 490 } 491 assert (modified ? (summarizeGraph(block, G) == false) : true); 492 return modified; 443 std::vector<Vertex> mapping(num_vertices(G)); 444 summarizeGraph(G, mapping); 493 445 } 494 446 … … 512 464 throw std::runtime_error("Failed to resolve scope block!"); 513 465 } 514 if (LLVM_UNLIKELY(f>second == ignoreIfThis)) { 466 Statement * branch = f>second; 467 if (LLVM_UNLIKELY(branch == ignoreIfThis)) { 515 468 break; 516 469 } 517 add_edge(u, getVertex(f>second, G, M), G); 470 // Add in a Var denoting the user of this expression so that it can be updated if expr changes. 471 const Vertex v = getVertex(user, G, M, block); 472 add_edge(expr, u, v, G); 473 const Vertex w = getVertex(branch, G, M, block); 474 add_edge(nullptr, v, w, G); 518 475 break; 519 476 } … … 523 480 } 524 481 } 482 } 483 484 /**  * 485 * @brief summarizeGraph 486 **  */ 487 inline void BooleanReassociationPass::summarizeGraph(Graph & G, std::vector<Vertex> & mapping) { 488 std::vector<Vertex> reverse_topological_ordering; 489 reverse_topological_ordering.reserve(num_vertices(G)); 490 topological_sort(G, std::back_inserter(reverse_topological_ordering)); 491 assert(mapping.size() >= num_vertices(G)); 492 for (const Vertex u : reverse_topological_ordering) { 493 if (LLVM_LIKELY(out_degree(u, G) > 0)) { 494 if (isOptimizable(G[u])) { 495 if (LLVM_UNLIKELY(in_degree(u, G) == 1)) { 496 // We have a redundant node here that'll simply end up being a duplicate 497 // of the input value. Remove it and add any of its outgoing edges to its 498 // input node. 499 const auto ei = first(in_edges(u, G)); 500 const Vertex v = source(ei, G); 501 for (auto ej : make_iterator_range(out_edges(u, G))) { 502 const Vertex w = target(ej, G); 503 add_edge(G[ei], v, w, G); 504 if (mapping[w] == mapping[u]) { 505 mapping[w] = v; 506 } 507 } 508 clear_vertex(u, G); 509 G[u].first = TypeId::Var; 510 mapping[u] = v; 511 continue; 512 } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) { 513 // Otherwise if we have a single user, we have a similar case as above but 514 // we can only merge this vertex into the outgoing instruction if they are 515 // of the same type. 516 const auto ei = first(out_edges(u, G)); 517 const Vertex v = target(ei, G); 518 if (LLVM_UNLIKELY(isSameType(G[v], G[u]))) { 519 for (auto ej : make_iterator_range(in_edges(u, G))) { 520 add_edge(G[ei], source(ej, G), v, G); 521 } 522 clear_vertex(u, G); 523 G[u].first = TypeId::Var; 524 mapping[u] = v; 525 } 526 } 527 } 528 } else if (isNonEscaping(G[u])) { 529 clear_in_edges(u, G); 530 G[u].first = TypeId::Var; 531 } 532 } 533 534 // Test whether any operation has (A op2 B) op1 (Â¬A op3 C) contained within it, where op1, op2 and op3 are all 535 // optimizable operations; if so, modify G to reflect the result. The main goal is to optimize the underlying 536 // equations but this also eliminates a problematic case in which the internal boolean simplification logic 537 // could detect the contradiction and return an unexpected value. 538 539 // VertexSet inputs; 540 // VertexSets lit; 541 // VertexSets neg; 542 // for (const Vertex t : reverse_topological_ordering) { 543 // if (isOptimizable(G[t])) { 544 // for (auto e : make_iterator_range(in_edges(t, G))) { 545 // const Vertex u = source(e, G); 546 // if (isOptimizable(G[u])) { 547 // inputs.push_back(u); 548 // } 549 // } 550 // if (inputs.size() > 1) { 551 // unsigned count = 0; 552 553 // for (const Vertex u : inputs) { 554 // lit[count].clear(); 555 // neg[count].clear(); 556 // for (auto ei : make_iterator_range(in_edges(u, G))) { 557 // const Vertex w = source(ei, G); 558 // if (isOptimizable(G[w])) { 559 // lit[count].push_back(w); 560 // } else if (LLVM_UNLIKELY(isNegated(G[w]))) { 561 // assert (in_degree(w, G) > 0); 562 // neg[count].push_back(source(first(in_edges(w, G)), G)); 563 // } 564 // } 565 // std::sort(lit[count].begin(), lit[count].end()); 566 // std::sort(neg[count].begin(), neg[count].end()); 567 // ++count; 568 // } 569 570 571 // for (unsigned i = 0; i != count; ++i) { 572 // for (unsigned j = 0; j != count; ++j) { 573 // VertexSet cap; 574 // std::set_intersection(lit[i].begin(), lit[i].end(), neg[j].begin(), neg[j].end(), std::back_inserter(cap)); 575 576 577 // } 578 // } 579 580 581 582 // } 583 // inputs.clear(); 584 // } 585 // } 525 586 } 526 587 … … 696 757 * @brief safeDistributionSets 697 758 **  */ 698 static DistributionSets safeDistributionSets(const PabloBlock & block, constGraph & G, DistributionGraph & H) {759 static DistributionSets safeDistributionSets(const Graph & G, DistributionGraph & H) { 699 760 const auto F = makeGraphFacade(H); 700 761 DistributionSets T; … … 712 773 * @brief generateDistributionGraph 713 774 **  */ 714 void generateDistributionGraph(const PabloBlock & block, constGraph & G, DistributionGraph & H) {775 void generateDistributionGraph(const Graph & G, DistributionGraph & H) { 715 776 DistributionMap M; 716 777 for (const Vertex u : make_iterator_range(vertices(G))) { 717 if (in_degree(u, G) > 0) { 718 const TypeId outerTypeId = G[u]>getClassTypeId(); 719 if (outerTypeId == TypeId::And  outerTypeId == TypeId::Or) { 720 if (inCurrentBlock(cast<Statement>(G[u]), block)) { 721 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And; 722 flat_set<Vertex> distributable; 723 for (auto e : make_iterator_range(in_edges(u, G))) { 724 const Vertex v = source(e, G); 725 if (LLVM_UNLIKELY(G[v]>getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block))) { 726 bool safe = true; 727 for (const auto e : make_iterator_range(out_edges(v, G))) { 728 if (G[target(e, G)]>getClassTypeId() != outerTypeId) { 729 safe = false; 730 break; 731 } 732 } 733 if (safe) { 734 distributable.insert(v); 735 } 778 const TypeId outerTypeId = G[u].first; 779 if (outerTypeId == TypeId::And  outerTypeId == TypeId::Or) { 780 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And; 781 flat_set<Vertex> distributable; 782 for (auto e : make_iterator_range(in_edges(u, G))) { 783 const Vertex v = source(e, G); 784 if (LLVM_UNLIKELY(G[v].first == innerTypeId)) { 785 bool safe = true; 786 for (const auto e : make_iterator_range(out_edges(v, G))) { 787 if (G[target(e, G)].first != outerTypeId) { 788 safe = false; 789 break; 736 790 } 737 791 } 738 if (LLVM_LIKELY(distributable.size() > 1)) { 739 // We're only interested in computing a subgraph of G in which every source has an outdegree 740 // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical 741 // benefit. (Note: this does not consider register pressure / liveness.) 742 flat_map<Vertex, bool> observedMoreThanOnce; 743 bool anyOpportunities = false; 744 for (const Vertex v : distributable) { 745 for (auto e : make_iterator_range(in_edges(v, G))) { 746 const Vertex w = source(e, G); 747 auto ob = observedMoreThanOnce.find(w); 748 if (ob == observedMoreThanOnce.end()) { 749 observedMoreThanOnce.emplace(w, false); 750 } else { 751 ob>second = true; 752 anyOpportunities = true; 792 if (safe) { 793 distributable.insert(v); 794 } 795 } 796 } 797 if (LLVM_LIKELY(distributable.size() > 1)) { 798 // We're only interested in computing a subgraph of G in which every source has an outdegree 799 // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical 800 // benefit. (Note: this does not consider register pressure / liveness.) 801 flat_map<Vertex, bool> observedMoreThanOnce; 802 bool anyOpportunities = false; 803 for (const Vertex v : distributable) { 804 for (auto e : make_iterator_range(in_edges(v, G))) { 805 const Vertex w = source(e, G); 806 auto ob = observedMoreThanOnce.find(w); 807 if (ob == observedMoreThanOnce.end()) { 808 observedMoreThanOnce.emplace(w, false); 809 } else { 810 ob>second = true; 811 anyOpportunities = true; 812 } 813 } 814 } 815 if (anyOpportunities) { 816 for (const auto ob : observedMoreThanOnce) { 817 if (ob.second) { 818 const Vertex w = ob.first; 819 for (auto e : make_iterator_range(out_edges(w, G))) { 820 const Vertex v = target(e, G); 821 if (distributable.count(v)) { 822 const Vertex y = getVertex(v, H, M); 823 add_edge(y, getVertex(u, H, M), H); 824 add_edge(getVertex(w, H, M), y, H); 753 825 } 754 826 } 755 827 } 756 if (anyOpportunities) { 757 for (const auto ob : observedMoreThanOnce) { 758 if (ob.second) { 759 const Vertex w = ob.first; 760 for (auto e : make_iterator_range(out_edges(w, G))) { 761 const Vertex v = target(e, G); 762 if (distributable.count(v)) { 763 const Vertex y = getVertex(v, H, M); 764 add_edge(y, getVertex(u, H, M), H); 765 add_edge(getVertex(w, H, M), y, H); 766 } 767 } 768 } 769 } 770 } 771 } 772 } 773 } 774 } 775 } 776 } 828 } 829 } 830 } 831 } 832 } 833 } 834 835 777 836 778 837 /**  * … … 781 840 * Apply the distribution law to reduce computations whenever possible. 782 841 **  */ 783 bool BooleanReassociationPass::redistributeAST(PabloBlock & block, Graph & G) const { 784 bool anyChanges = false; 785 786 ++distributionCount; 842 void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G) const { 843 844 printGraph(block, G, "G0"); 845 846 unsigned count = 0; 847 848 std::vector<Vertex> mapping(num_vertices(G) + 16); 849 std::iota(mapping.begin(), mapping.end(), 0); // 0,1,.....n 787 850 788 851 for (;;) { … … 790 853 DistributionGraph H; 791 854 792 generateDistributionGraph( block,G, H);855 generateDistributionGraph(G, H); 793 856 794 857 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. … … 797 860 } 798 861 799 const DistributionSets distributionSets = safeDistributionSets( block,G, H);862 const DistributionSets distributionSets = safeDistributionSets(G, H); 800 863 801 864 if (LLVM_UNLIKELY(distributionSets.empty())) { … … 803 866 } 804 867 868 raw_os_ostream out(std::cerr); 869 out << "DISTRIBUTION SETS: " << distributionSets.size() << '\n'; 870 871 ++count; 872 873 unsigned subcount = 0; 874 875 876 805 877 for (const DistributionSet & set : distributionSets) { 878 806 879 // Each distribution tuple consists of the sources, intermediary, and sink nodes. 807 880 const VertexSet & sources = std::get<0>(set); … … 809 882 const VertexSet & sinks = std::get<2>(set); 810 883 811 const TypeId outerTypeId = G[H[sinks.front()]]>getClassTypeId(); 884 out << "SOURCES:"; 885 for (const Vertex u : sources) { 886 const Vertex x = mapping[H[u]]; 887 out << " " << x << ": "; PabloPrinter::print(G[x].second, out); 888 } 889 out << "\n"; 890 out << "INTERMEDIARY:"; 891 for (const Vertex u : intermediary) { 892 const Vertex x = mapping[H[u]]; 893 out << " " << x << ": "; PabloPrinter::print(G[x].second, out); 894 } 895 out << "\n"; 896 out << "SINKS:"; 897 for (const Vertex u : sinks) { 898 const Vertex x = mapping[H[u]]; 899 out << " " << x << ": "; PabloPrinter::print(G[x].second, out); 900 } 901 out << "\n"; 902 out.flush(); 903 904 const TypeId outerTypeId = G[mapping[H[sinks.front()]]].first; 812 905 assert (outerTypeId == TypeId::And  outerTypeId == TypeId::Or); 813 906 const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or; 814 907 815 // Eliminate the edges from our original graph G 816 for (const Vertex u : intermediary) { 817 const auto x = H[u]; 818 assert (G[x]>getClassTypeId() == innerTypeId); 819 for (const Vertex s : sources) { 820 assert (edge(H[s], x, G).second); 821 remove_edge(H[s], x, G); 822 } 908 // Update G to match the desired changes (TODO: modify this to reuse a discarded vertex instead) 909 const Vertex x = add_vertex(std::make_pair(outerTypeId, nullptr), G); 910 const Vertex y = add_vertex(std::make_pair(innerTypeId, nullptr), G); 911 mapping.resize(num_vertices(G)); 912 mapping[x] = x; 913 mapping[y] = y; 914 915 for (const Vertex i : intermediary) { 916 const auto u = mapping[H[i]]; 917 assert (G[u].first == innerTypeId); 823 918 for (const Vertex t : sinks) { 824 assert (edge(x, H[t], G).second); 825 assert (G[H[t]]>getClassTypeId() == outerTypeId); 826 remove_edge(x, H[t], G); 827 } 828 } 829 830 // Update G to match the desired changes 831 const Vertex x = add_vertex(nullptr, G); 832 const Vertex y = add_vertex(nullptr, G); 833 for (const Vertex u : intermediary) { 834 add_edge(nullptr, H[u], x, G); 835 } 919 const auto v = mapping[H[t]]; 920 assert (G[v].first == outerTypeId); 921 for (auto e : make_iterator_range(out_edges(u, G))) { 922 if (target(e, G) == v) { 923 remove_edge(e, G); 924 } 925 } 926 } 927 add_edge(nullptr, u, x, G); 928 } 929 836 930 for (const Vertex s : sources) { 837 add_edge(nullptr, H[s], y, G); 838 } 931 const auto u = mapping[H[s]]; 932 for (const Vertex i : intermediary) { 933 const auto v = mapping[H[i]]; 934 for (auto e : make_iterator_range(out_edges(u, G))) { 935 if (target(e, G) == v) { 936 remove_edge(e, G); 937 } 938 } 939 } 940 add_edge(nullptr, u, y, G); 941 } 942 943 add_edge(nullptr, x, y, G); 944 839 945 for (const Vertex t : sinks) { 840 add_edge(nullptr, y, H[t], G); 841 } 842 add_edge(nullptr, x, y, G); 843 844 // Now begin transforming the AST (TODO: fix the abstraction so I can defer creation until the final phase) 845 circular_buffer<PabloAST *> Q(std::max(in_degree(x, G), in_degree(y, G))); 846 for (auto e : make_iterator_range(in_edges(x, G))) { 847 Q.push_back(G[source(e, G)]); 848 } 849 G[x] = createTree(block, outerTypeId, Q); 850 for (auto e : make_iterator_range(in_edges(y, G))) { 851 Q.push_back(G[source(e, G)]); 852 } 853 G[y] = createTree(block, innerTypeId, Q); 854 855 // Summarize the graph after transforming G 856 summarizeGraph(block, G); 857 } 858 anyChanges = true; 859 } 860 return anyChanges; 861 } 862 863 } 946 const auto v = mapping[H[t]]; 947 add_edge(G[v].second, y, v, G); 948 } 949 950 summarizeGraph(G, mapping); 951 952 printGraph(block, G, "G" + std::to_string(count) + "_" + std::to_string(++subcount)); 953 } 954 } 955 } 956 957 } 
icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.h
r4768 r4769 3 3 4 4 #include <pablo/codegenstate.h> 5 #include <boost/container/flat_set.hpp> 5 6 #include <boost/container/flat_map.hpp> 6 7 #include <boost/graph/adjacency_list.hpp> … … 10 11 class BooleanReassociationPass { 11 12 public: 12 using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *, PabloAST *>; 13 using VertexData = std::pair<PabloAST::ClassTypeId, PabloAST *>; 14 using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexData, PabloAST *>; 13 15 using Vertex = Graph::vertex_descriptor; 14 16 using Map = std::unordered_map<const PabloAST *, Vertex>; … … 23 25 void processScope(PabloFunction & function, PabloBlock & block); 24 26 void summarizeAST(PabloBlock & block, Graph & G) const; 25 static bool summarizeGraph(PabloBlock & block, Graph & G);27 static void summarizeGraph(Graph & G, std::vector<Vertex> & mapping); 26 28 void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis = nullptr) const; 27 bool redistributeAST(PabloBlock & block, Graph & G) const; 29 void redistributeAST(const PabloBlock & block, Graph & G) const; 30 public: 31 static bool isOptimizable(const VertexData & data); 32 static bool isMutable(const VertexData & data, const PabloBlock &block); 33 static bool isNonEscaping(const VertexData & data); 34 static bool isSameType(const VertexData & data1, const VertexData & data2); 28 35 private: 29 36 boost::container::flat_map<PabloBlock *, Statement *> mResolvedScopes; 
icGREP/icgrepdevel/icgrep/pablo/printer_pablos.cpp
r4762 r4769 208 208 print(whl>getCondition(), strm); 209 209 } else if (const Statement * stmt = dyn_cast<Statement>(expr)) { 210 assert (stmt>getName()); 210 211 strm << stmt>getName(); 211 212 } else { 212 strm << " **UNKNOWN Pablo Expression type **\n" << "\n";213 } 214 } 215 216 213 strm << "???"; 214 } 215 } 216 217
Note: See TracChangeset
for help on using the changeset viewer.