Changeset 4861 for icGREP/icgrepdevel/icgrep/pablo
 Timestamp:
 Nov 6, 2015, 4:54:29 PM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/codegenstate.cpp
r4860 r4861 27 27 if (mFirst) { 28 28 statement>insertBefore(mFirst); 29 } 30 else { 29 } else { 31 30 statement>removeFromParent(); 32 31 statement>mParent = this; 33 32 mFirst = mLast = statement; 34 33 } 35 } 36 else if (LLVM_LIKELY(statement != mInsertionPoint)) { 34 } else if (LLVM_LIKELY(statement != mInsertionPoint)) { 37 35 statement>insertAfter(mInsertionPoint); 38 36 mLast = (mLast == mInsertionPoint) ? statement : mLast; 
icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4860 r4861 159 159 } 160 160 161 / **  *162 * @brief printGraph163 **  */164 static void printGraph(const Graph & G, const std::string name, raw_ostream & out) {165 166 std::vector<unsigned> c(num_vertices(G));167 strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));168 169 out << "digraph " << name << " {\n";170 for (auto u : make_iterator_range(vertices(G))) {171 if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {172 continue;173 }174 out << "v" << u << " [label=\"" << u << ": ";175 PabloAST * expr;176 TypeId typeId;177 std::tie(typeId, expr) = G[u];178 bool temporary = false;179 bool error = false;180 if (expr == nullptr) {181 temporary = true;182 switch (typeId) {183 case TypeId::And:184 out << "And";185 break;186 case TypeId::Or:187 out << "Or";188 break;189 case TypeId::Xor:190 out << "Xor";191 break;192 default:193 out << "???";194 error = true;195 break;196 }197 } else if (isMutable(G[u])) {198 if (LLVM_UNLIKELY(isa<If>(expr))) {199 out << "If ";200 PabloPrinter::print(cast<If>(expr)>getOperand(0), out);201 out << ":";202 } else if (LLVM_UNLIKELY(isa<While>(expr))) {203 out << "While ";204 PabloPrinter::print(cast<While>(expr)>getOperand(0), out);205 out << ":";206 } else {207 PabloPrinter::print(cast<Statement>(expr), "", out);208 }209 } else {210 PabloPrinter::print(expr, out);211 }212 out << "\"";213 if (!isMutable(G[u])) {214 out << " style=dashed";215 }216 if (error) {217 out << " color=red";218 } else if (temporary) {219 out << " color=blue";220 }221 out << "];\n";222 }223 for (auto e : make_iterator_range(edges(G))) {224 const auto s = source(e, G);225 const auto t = target(e, G);226 out << "v" << s << " > v" << t;227 bool cyclic = (c[s] == c[t]);228 if (G[e]  cyclic) {229 out << " [";230 if (G[e]) {231 out << "label=\"";232 PabloPrinter::print(G[e], out);233 out << "\" ";234 }235 if (cyclic) {236 out << "color=red ";237 }238 out << "]";239 }240 out << ";\n";241 }242 243 if (num_vertices(G) > 0) {244 245 out << "{ rank=same;";246 for (auto u : make_iterator_range(vertices(G))) {247 if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {248 out << " v" << u;249 }250 }251 out << "}\n";252 253 out << "{ rank=same;";254 for (auto u : make_iterator_range(vertices(G))) {255 if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {256 out << " v" << u;257 }258 }259 out << "}\n";260 261 }262 263 out << "}\n\n";264 out.flush();265 }161 ///**  * 162 // * @brief printGraph 163 // **  */ 164 //static void printGraph(const Graph & G, const std::string name, raw_ostream & out) { 165 166 // std::vector<unsigned> c(num_vertices(G)); 167 // strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0])); 168 169 // out << "digraph " << name << " {\n"; 170 // for (auto u : make_iterator_range(vertices(G))) { 171 // if (in_degree(u, G) == 0 && out_degree(u, G) == 0) { 172 // continue; 173 // } 174 // out << "v" << u << " [label=\"" << u << ": "; 175 // PabloAST * expr; 176 // TypeId typeId; 177 // std::tie(typeId, expr) = G[u]; 178 // bool temporary = false; 179 // bool error = false; 180 // if (expr == nullptr) { 181 // temporary = true; 182 // switch (typeId) { 183 // case TypeId::And: 184 // out << "And"; 185 // break; 186 // case TypeId::Or: 187 // out << "Or"; 188 // break; 189 // case TypeId::Xor: 190 // out << "Xor"; 191 // break; 192 // default: 193 // out << "???"; 194 // error = true; 195 // break; 196 // } 197 // } else if (isMutable(G[u])) { 198 // if (LLVM_UNLIKELY(isa<If>(expr))) { 199 // out << "If "; 200 // PabloPrinter::print(cast<If>(expr)>getOperand(0), out); 201 // out << ":"; 202 // } else if (LLVM_UNLIKELY(isa<While>(expr))) { 203 // out << "While "; 204 // PabloPrinter::print(cast<While>(expr)>getOperand(0), out); 205 // out << ":"; 206 // } else { 207 // PabloPrinter::print(cast<Statement>(expr), "", out); 208 // } 209 // } else { 210 // PabloPrinter::print(expr, out); 211 // } 212 // out << "\""; 213 // if (!isMutable(G[u])) { 214 // out << " style=dashed"; 215 // } 216 // if (error) { 217 // out << " color=red"; 218 // } else if (temporary) { 219 // out << " color=blue"; 220 // } 221 // out << "];\n"; 222 // } 223 // for (auto e : make_iterator_range(edges(G))) { 224 // const auto s = source(e, G); 225 // const auto t = target(e, G); 226 // out << "v" << s << " > v" << t; 227 // bool cyclic = (c[s] == c[t]); 228 // if (G[e]  cyclic) { 229 // out << " ["; 230 // if (G[e]) { 231 // out << "label=\""; 232 // PabloPrinter::print(G[e], out); 233 // out << "\" "; 234 // } 235 // if (cyclic) { 236 // out << "color=red "; 237 // } 238 // out << "]"; 239 // } 240 // out << ";\n"; 241 // } 242 243 // if (num_vertices(G) > 0) { 244 245 // out << "{ rank=same;"; 246 // for (auto u : make_iterator_range(vertices(G))) { 247 // if (in_degree(u, G) == 0 && out_degree(u, G) != 0) { 248 // out << " v" << u; 249 // } 250 // } 251 // out << "}\n"; 252 253 // out << "{ rank=same;"; 254 // for (auto u : make_iterator_range(vertices(G))) { 255 // if (out_degree(u, G) == 0 && in_degree(u, G) != 0) { 256 // out << " v" << u; 257 // } 258 // } 259 // out << "}\n"; 260 261 // } 262 263 // out << "}\n\n"; 264 // out.flush(); 265 //} 266 266 267 267 /**  * … … 338 338 * @brief writeTree 339 339 **  */ 340 inline voidwriteTree(PabloBlock & block, const TypeId typeId, circular_buffer<PabloAST *> & Q) {340 inline PabloAST * writeTree(PabloBlock & block, const TypeId typeId, circular_buffer<PabloAST *> & Q) { 341 341 while (Q.size() > 1) { 342 342 PabloAST * e1 = Q.front(); Q.pop_front(); … … 353 353 } 354 354 Q.push_back(expr); 355 } 355 } 356 return Q.front(); 357 } 358 359 /**  * 360 * @brief isReachableAtEntryPoint 361 **  */ 362 bool isReachableAtEntryPoint(const PabloAST * const expr, const PabloBlock & block) { 363 // if expr is not a statement, it's always reachable 364 if (isa<Statement>(expr)) { 365 const PabloBlock * const parent = cast<Statement>(expr)>getParent(); 366 // if expr is in the current block, it's not reachable at the entry point of this block 367 if (parent == &block) { 368 return false; 369 } 370 const PabloBlock * current = block.getParent(); 371 // if we can find expr in a preceeding block, it's reachable 372 while (current) { 373 if (parent == current) { 374 return true; 375 } 376 current = current>getParent(); 377 } 378 // otherwise it must be in a nested block and therefore unreachable 379 return false; 380 } 381 return true; 356 382 } 357 383 … … 361 387 PabloAST * BooleanReassociationPass::createTree(PabloBlock & block, const Vertex u, Graph & G) { 362 388 363 flat_set<PabloAST *> sources; 389 flat_set<PabloAST *> internalVars; 390 391 flat_set<PabloAST *> externalVars; 392 393 assert (in_degree(u, G) > 0); 364 394 365 395 for (const auto e : make_iterator_range(in_edges(u, G))) { 366 396 PabloAST * const expr = getValue(G[source(e, G)]); 367 397 assert ("G contains a null input variable!" && (expr != nullptr)); 368 sources.insert(expr); 369 } 370 371 circular_buffer<PabloAST *> Q(sources.size()); 372 373 for (auto si = sources.begin(); si != sources.end(); ) { 374 if (inCurrentBlock(*si, block)) { 375 ++si; 376 } else { // combine any nonStatements or statements from a preceeding block at the beginning of this block. 377 Q.push_back(*si); 378 si = sources.erase(si); 379 } 398 if (isReachableAtEntryPoint(expr, block)) { 399 externalVars.insert(expr); 400 } else { 401 internalVars.insert(expr); 402 } 403 } 404 405 circular_buffer<PabloAST *> Q(in_degree(u, G)); 406 for (auto expr : externalVars) { 407 Q.push_back(expr); 380 408 } 381 409 382 410 const TypeId typeId = getType(G[u]); 383 Statement * current = block.front();411 Statement * stmt = block.front(); 384 412 if (Q.size() > 1) { 385 413 block.setInsertPoint(nullptr); 386 414 writeTree(block, typeId, Q); 387 current = block.getInsertPoint(); 388 } 389 390 unsigned distance = 0; 391 while (current) { 392 if (sources.count(current)) { 393 if (distance > 2) { // write out the current Q 394 writeTree(block, typeId, Q); 395 } else { 396 block.setInsertPoint(current); 397 } 398 Q.push_back(current); 415 assert (Q.size() == 1); 416 } 417 418 for (unsigned distance = 0; stmt; ++distance, stmt = stmt>getNextNode()) { 419 420 if (distance > 3 && Q.size() > 1) { // write out the current Q 421 writeTree(block, typeId, Q); 422 assert (Q.size() == 1); 423 } 424 425 bool found = false; 426 if (isa<If>(stmt)) { 427 for (Assign * def : cast<If>(stmt)>getDefined()) { 428 if (internalVars.erase(def) != 0) { 429 assert (!Q.full()); 430 Q.push_back(def); 431 found = true; 432 } 433 } 434 } else if (isa<While>(stmt)) { 435 for (Next * var : cast<While>(stmt)>getVariants()) { 436 if (internalVars.erase(var) != 0) { 437 assert (!Q.full()); 438 Q.push_back(var); 439 found = true; 440 } 441 } 442 } else if (internalVars.erase(stmt) != 0) { 443 Q.push_back(stmt); 444 found = true; 445 } 446 447 if (found) { 448 block.setInsertPoint(stmt); 399 449 distance = 0; 400 450 } 401 ++distance; 402 current = current>getNextNode(); 403 } 451 } 452 453 assert (internalVars.empty()); 454 455 block.setInsertPoint(block.back()); 456 404 457 writeTree(block, typeId, Q); 405 458 assert (Q.size() == 1); … … 407 460 assert (result); 408 461 getValue(G[u]) = result; 409 block.setInsertPoint(block.back()); 462 410 463 return result; 411 464 } … … 427 480 void BooleanReassociationPass::rewriteAST(PabloBlock & block, Graph & G) { 428 481 429 using ReadySetQueue = std::priority_queue<std::pair<unsigned, Vertex>, std::deque<std::pair<unsigned, Vertex>>, std::greater<std::pair<unsigned, Vertex>>>; 430 431 raw_os_ostream out(std::cerr); 432 out << "***************************************************\n"; 433 printGraph(G, "G_" + std::to_string((unsigned long)(&block)), out); 434 482 using ReadyPair = std::pair<unsigned, Vertex>; 483 using ReadySet = std::vector<ReadyPair>; 435 484 436 485 // Determine the bottomup ordering of G … … 472 521 } 473 522 474 ReadySetQueue readySet; 523 // Compute the initial ready set 524 ReadySet readySet; 475 525 for (const Vertex u : make_iterator_range(vertices(G))) { 476 526 if (in_degree(u, G) == 0 && out_degree(u, G) != 0) { 477 readySet.emplace(ordering[u], u); 478 } 479 } 480 481 out << "\n"; 482 out.flush(); 527 readySet.emplace_back(ordering[u], u); 528 } 529 } 530 531 struct { 532 bool operator()(const ReadyPair a, const ReadyPair b) { 533 return std::get<0>(a) > std::get<0>(b); 534 } 535 } readyComparator; 536 537 std::sort(readySet.begin(), readySet.end(), readyComparator); 483 538 484 539 // Store the original AST then clear the block 485 540 std::vector<Statement *> originalAST(block.begin(), block.end()); 486 541 block.clear(); 487 flat_set<Vertex> contains;542 flat_set<Vertex> tested; 488 543 489 544 // Rewrite the AST using the bottomup ordering 490 545 while (!readySet.empty()) { 491 546 547 // Scan through the ready set to determine which one 'kills' the greatest number of inputs 548 // NOTE: the readySet is kept in sorted "distance to sink" order; thus those closest to a 549 // sink will be evaluated first. 550 unsigned best = 0; 551 auto chosen = readySet.begin(); 552 for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) { 553 const Vertex u = std::get<1>(*ri); 554 unsigned kills = 0; 555 for (auto ei : make_iterator_range(in_edges(u, G))) { 556 const auto v = source(ei, G); 557 unsigned remaining = 0; 558 for (auto ej : make_iterator_range(out_edges(v, G))) { 559 const auto w = target(ej, G); 560 PabloAST * expr = getValue(G[w]); 561 if (expr == nullptr  (isa<Statement>(expr) && cast<Statement>(expr)>getParent() == nullptr)) { 562 if (++remaining > 1) { 563 break; 564 } 565 } 566 } 567 if (remaining < 2) { 568 ++kills; 569 } 570 } 571 if (kills > best) { 572 chosen = ri; 573 best = kills; 574 } 575 } 492 576 Vertex u; unsigned weight; 493 std::tie(weight, u) = readySet.top();494 readySet. pop();577 std::tie(weight, u) = *chosen; 578 readySet.erase(chosen); 495 579 496 580 PabloAST * expr = getValue(G[u]); 497 498 out << " * processing " << u << ' ';499 PabloPrinter::print(expr, out);500 out << ", weight=" << weight;501 out.flush();502 581 503 582 assert (weight > 0); … … 525 604 } 526 605 // Make sure that optimization doesn't reduce this to an already written statement 527 if (stmt>getParent()) { 528 goto check_ready; 529 } 530 block.insert(stmt); 606 if (stmt>getParent() == nullptr) { 607 block.insert(stmt); 608 } 531 609 expr = stmt; 532 610 } 533 611 check_ready: 534 535 out << ", wrote ";536 PabloPrinter::print(expr, out);537 out << '\n';538 out.flush();539 540 612 // mark this instruction as written 541 613 ordering[u] = 0; … … 545 617 const auto v = target(ei, G); 546 618 // since G may be a multigraph, we need to check whether we've already tested v 547 if ( contains.insert(v).second) {619 if (tested.insert(v).second) { 548 620 for (auto ej : make_iterator_range(in_edges(v, G))) { 549 621 if (ordering[source(ej, G)]) { … … 553 625 } 554 626 if (ready) { 555 556 out << " adding " << v << ' '; 557 PabloPrinter::print(getValue(G[v]), out); 558 out << " to ready set, weight=" << ordering[v] << '\n'; 559 560 readySet.emplace(ordering[v], v); 561 } 562 } 563 } 564 contains.clear(); 565 566 out << "\n"; 567 out.flush(); 627 auto entry = std::make_pair(ordering[v], v); 628 auto li = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator); 629 while (li != readySet.end()) { 630 auto next = li + 1; 631 if (next == readySet.end()  std::get<0>(*next) == ordering[v]) { 632 li = next; 633 continue; 634 } 635 break; 636 } 637 readySet.insert(li, entry); 638 } 639 } 640 } 641 tested.clear(); 568 642 } 569 643 … … 573 647 } 574 648 } 575 576 PabloPrinter::print(block.statements(), out);577 578 649 } 579 650 
icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.h
r4860 r4861 3 3 4 4 #include <pablo/codegenstate.h> 5 #include <boost/container/flat_set.hpp>6 5 #include <boost/container/flat_map.hpp> 7 6 #include <boost/graph/adjacency_list.hpp> 
icGREP/icgrepdevel/icgrep/pablo/pabloAST.cpp
r4860 r4861 345 345 } 346 346 347 return removeFromParent(); 347 Statement * const next = removeFromParent(); 348 mAllocator.deallocate(reinterpret_cast<Allocator::pointer>(this)); 349 return next; 348 350 } 349 351
Note: See TracChangeset
for help on using the changeset viewer.