Changeset 5566
 Timestamp:
 Jul 13, 2017, 4:01:12 PM (22 months ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/codemotionpass.cpp
r5535 r5566 177 177 178 178 /**  * 179 * @brief doCodeSinking180 **  */181 void doCodeSinking(PabloBlock * const block) {182 Statement * stmt = block>back(); // note: reverse AST traversal183 while (stmt) {184 Statement * const prevNode = stmt>getPrevNode();185 sinkIfAcceptableTarget(stmt, block);186 stmt = prevNode;187 }188 }189 190 /**  *191 179 * @brief hoistLoopInvariants 192 180 **  */ … … 230 218 **  */ 231 219 void doCodeMovement(PabloBlock * const block) { 232 doCodeSinking(block); 233 for (Statement * stmt : *block) { 234 if (LLVM_UNLIKELY(isa<Branch>(stmt))) { 235 doCodeMovement(cast<Branch>(stmt)>getBody()); 236 if (isa<While>(stmt)) { 237 // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could 238 // determine whether hoisting will helpful or harmful to the expected run time. 239 hoistLoopInvariants(cast<While>(stmt)); 240 } 241 } 242 } 220 221 std::vector<Branch *> branches; 222 223 Statement * stmt = block>back(); // note: reverse AST traversal 224 while (stmt) { 225 Statement * const prevNode = stmt>getPrevNode(); 226 sinkIfAcceptableTarget(stmt, block); 227 if (isa<Branch>(stmt)) { 228 branches.push_back(cast<Branch>(stmt)); 229 } 230 stmt = prevNode; 231 } 232 233 while (!branches.empty()) { 234 Branch * const br = branches.back(); 235 branches.pop_back(); 236 doCodeMovement(br>getBody()); 237 if (isa<While>(br)) { 238 // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could 239 // determine whether hoisting will helpful or harmful to the expected run time. 240 hoistLoopInvariants(br); 241 } 242 243 } 244 243 245 } 244 246 
icGREP/icgrepdevel/icgrep/pablo/optimizers/distributivepass.cpp
r5510 r5566 3 3 #include <pablo/pablo_kernel.h> 4 4 #include <pablo/codegenstate.h> 5 6 #include <pablo/boolean.h> 5 7 #include <pablo/branch.h> 8 #include <pablo/pe_advance.h> 9 #include <pablo/pe_count.h> 10 #include <pablo/pe_infile.h> 11 #include <pablo/pe_integer.h> 12 #include <pablo/pe_lookahead.h> 13 #include <pablo/pe_matchstar.h> 14 #include <pablo/pe_ones.h> 15 #include <pablo/pe_scanthru.h> 6 16 #include <pablo/pe_string.h> 7 #include <pablo/pe_ integer.h>17 #include <pablo/pe_var.h> 8 18 #include <pablo/pe_zeroes.h> 9 #include <pablo/pe_ones.h> 10 #include <pablo/ boolean.h>11 #include <pablo/pe_var.h> 19 20 #include <pablo/optimizers/pablo_simplifier.hpp> 21 12 22 #include <boost/container/flat_set.hpp> 13 23 #include <boost/container/flat_map.hpp> … … 16 26 #include <boost/graph/topological_sort.hpp> 17 27 #include <boost/function_output_iterator.hpp> 28 #include <boost/functional/hash.hpp> 29 18 30 #include <set> 31 #include <random> 32 33 #ifndef NDEBUG 34 #include <pablo/analysis/pabloverifier.hpp> 35 #endif 19 36 20 37 #include <boost/graph/strong_components.hpp> 21 38 #include <llvm/Support/raw_ostream.h> 39 #include <pablo/printer_pablos.h> 40 #include <llvm/Support/CommandLine.h> 41 42 // #define PRINT_DEBUG 22 43 23 44 using namespace boost; … … 25 46 using namespace llvm; 26 47 48 namespace pablo { 49 27 50 using TypeId = pablo::PabloAST::ClassTypeId; 28 using VertexData = std::pair<pablo::PabloAST *, TypeId>; 29 30 using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, pablo::PabloAST *>; 51 enum class State { 52 Dead 53 , Live 54 , Modified 55 }; 56 57 using UsageTime = size_t; 58 59 using VertexData = std::tuple<pablo::PabloAST *, TypeId, State, UsageTime>; 60 61 using OperandIndex = unsigned; 62 63 using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, OperandIndex>; 31 64 using Vertex = Graph::vertex_descriptor; 32 65 using in_edge_iterator = graph_traits<Graph>::in_edge_iterator; 33 66 using out_edge_iterator = graph_traits<Graph>::out_edge_iterator; 34 67 35 using VertexSet = std::vector<Vertex>; 36 using Biclique = std::pair<VertexSet, VertexSet>; 68 using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>; 69 using DistributionVertex = DistributionGraph::vertex_descriptor; 70 71 using Sequence = std::vector<Vertex>; 72 using Biclique = std::pair<Sequence, Sequence>; 37 73 using BicliqueSet = std::vector<Biclique>; 38 using DistributionSet = std::tuple< VertexSet, VertexSet, VertexSet>;74 using DistributionSet = std::tuple<Sequence, Sequence, Sequence>; 39 75 using DistributionSets = std::vector<DistributionSet>; 40 76 41 77 using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>; 42 78 43 namespace pablo {44 45 46 /**  *47 * @brief printGraph48 **  */49 static void printGraph(const Graph & G, const std::string & name, llvm::raw_ostream & out) {50 51 std::vector<unsigned> c(num_vertices(G));52 strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));53 54 out << "digraph " << name << " {\n";55 for (auto u : make_iterator_range(vertices(G))) {56 if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {57 continue;58 }59 out << "v" << u << " [label=\"" << u << ": ";60 TypeId typeId;61 PabloAST * expr;62 std::tie(expr, typeId) = G[u];63 bool temporary = false;64 bool error = false;65 if (expr == nullptr  (typeId != expr>getClassTypeId() && typeId != TypeId::Var)) {66 temporary = true;67 switch (typeId) {68 case TypeId::And:69 out << "And";70 break;71 case TypeId::Or:72 out << "Or";73 break;74 case TypeId::Xor:75 out << "Xor";76 break;77 case TypeId::Not:78 out << "Not";79 break;80 default:81 out << "???";82 error = true;83 break;84 }85 if (expr) {86 out << " ("; expr>print(out); out << ")";87 }88 } else {89 expr>print(out);90 }91 out << "\"";92 if (typeId == TypeId::Var) {93 out << " style=dashed";94 }95 if (error) {96 out << " color=red";97 } else if (temporary) {98 out << " color=blue";99 }100 out << "];\n";101 }102 for (auto e : make_iterator_range(edges(G))) {103 const auto s = source(e, G);104 const auto t = target(e, G);105 out << "v" << s << " > v" << t;106 bool cyclic = (c[s] == c[t]);107 if (G[e]  cyclic) {108 out << " [";109 PabloAST * const expr = G[e];110 if (expr) {111 out << "label=\"";112 expr>print(out);113 out << "\" ";114 }115 if (cyclic) {116 out << "color=red ";117 }118 out << "]";119 }120 out << ";\n";121 }122 123 if (num_vertices(G) > 0) {124 125 out << "{ rank=same;";126 for (auto u : make_iterator_range(vertices(G))) {127 if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {128 out << " v" << u;129 }130 }131 out << "}\n";132 133 out << "{ rank=same;";134 for (auto u : make_iterator_range(vertices(G))) {135 if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {136 out << " v" << u;137 }138 }139 out << "}\n";140 141 }142 143 out << "}\n\n";144 out.flush();145 }146 147 79 struct PassContainer { 148 149 enum Modification {150 None, Trivial, Structural151 };152 80 153 81 /**  * … … 170 98 * (DISTRIBUTIVITY) (A â§ B) âš (A â§ C) â A â§ (B âš C) and (A âš B) â§ (A âš C) â A âš (B â§ C) 171 99 * 172 * Try to eliminate some of the unnecessary operations from the current Variadic expressions 173 **  */ 174 void run(PabloKernel * const kernel) { 175 run(kernel>getEntryBlock()); 176 177 printGraph(G, "G", errs()); 178 if (simplifyGraph() == Structural) { 179 // rewriteAST(first, stmt); 180 printGraph(G, "O", errs()); 181 } 182 183 } 184 185 void run(PabloBlock * const block) { 186 for (Statement * stmt : *block) { 100 * Try to simplify the equations and eliminate some of the unnecessary statements 101 **  */ 102 bool run(PabloKernel * const kernel) { 103 readAST(kernel>getEntryBlock()); 104 if (simplifyGraph()) { 105 rewriteAST(kernel>getEntryBlock()); 106 return true; 107 } 108 return false; 109 } 110 111 PassContainer() 112 : R(std::random_device()()) { 113 114 } 115 116 protected: 117 118 #if !defined(NDEBUG)  defined(PRINT_DEBUG) 119 /**  * 120 * @brief printGraph 121 **  */ 122 void printGraph(const std::string & name, llvm::raw_ostream & out, std::vector<Vertex> restricted = {}) { 123 124 const auto n = num_vertices(G); 125 std::vector<unsigned> c(n); 126 const auto components = strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0])); 127 128 std::vector<bool> show(n, false); 129 if (LLVM_LIKELY(restricted.empty() && n == components)) { 130 for (const auto u : make_iterator_range(vertices(G))) { 131 show[u] = isLive(u); 132 } 133 } else { 134 std::queue<Vertex> Q; 135 for (const auto m : restricted) { 136 if (m < n) { 137 show[m] = true; 138 assert (Q.empty()); 139 Q.push(m); 140 for (;;) { 141 const auto u = Q.front(); 142 Q.pop(); 143 for (auto e : make_iterator_range(in_edges(u, G))) { 144 const auto v = source(e, G); 145 if (show[v]  !isLive(v)) { 146 continue; 147 } 148 show[v] = true; 149 Q.push(v); 150 } 151 if (Q.empty()) { 152 break; 153 } 154 } 155 } 156 } 157 } 158 159 out << "digraph " << name << " {\n"; 160 for (auto u : make_iterator_range(vertices(G))) { 161 162 if (show[u]) { 163 164 out << "v" << u << " [label=\"" << u << ": "; 165 TypeId typeId; 166 PabloAST * expr; 167 State state; 168 169 std::tie(expr, typeId, state, std::ignore) = G[u]; 170 171 switch (typeId) { 172 case TypeId::And: 173 out << "(â§) "; 174 break; 175 case TypeId::Or: 176 out << "(âš) "; 177 break; 178 case TypeId::Xor: 179 out << "(â) "; 180 break; 181 case TypeId::Not: 182 out << "(Â¬) "; 183 break; 184 case TypeId::Zeroes: 185 out << "(0) "; 186 break; 187 case TypeId::Ones: 188 out << "(1) "; 189 default: 190 break; 191 } 192 193 if (expr) { 194 PabloPrinter::print(expr, out); 195 } 196 const bool error = !hasValidOperandIndicies(u); 197 198 out << "\""; 199 if (state == State::Modified) { 200 out << " style=dashed"; 201 } 202 if (error) { 203 out << " color=red"; 204 } else if (isRegenerable(typeId)) { 205 out << " color=blue"; 206 } 207 out << "];\n"; 208 } 209 } 210 for (auto e : make_iterator_range(edges(G))) { 211 const auto s = source(e, G); 212 const auto t = target(e, G); 213 if (show[s] && show[t]) { 214 const auto cyclic = (c[s] == c[t]); 215 const auto nonAssoc = !isAssociative(getType(t)); 216 out << "v" << s << " > v" << t; 217 if (cyclic  nonAssoc) { 218 out << " ["; 219 if (nonAssoc) { 220 out << " label=\"" << G[e] << "\""; 221 } 222 if (cyclic) { 223 out << " color=red"; 224 } 225 out << "]"; 226 } 227 out << ";\n"; 228 } 229 } 230 231 out << "}\n\n"; 232 out.flush(); 233 } 234 #endif 235 236 protected: 237 238 /**  * 239 * @brief readAST 240 **  */ 241 void readAST(PabloBlock * const block) { 242 for (Statement * stmt : *block) { 243 addStatement(stmt); 244 if (LLVM_UNLIKELY(isa<Branch>(stmt))) { 245 readAST(cast<Branch>(stmt)>getBody()); 246 } 247 } 248 } 249 250 /**  * 251 * @brief rewriteAST 252 * 253 * The goal here is to rewrite the AST with the minimal amount of perturbation to the sequence of instructions 254 * themselves. The exception is that associative instructions are regenerated w.r.t. their sequence in the AST 255 **  */ 256 size_t rewriteAST(PabloBlock * entry, size_t count = 0) { 257 258 for (Statement * stmt : *entry) { 259 260 const Vertex u = findVertex(stmt); 261 const auto typeId = getType(u); 262 263 if (isRegenerable(typeId)) { 264 continue; 265 } 266 267 #ifdef PRINT_DEBUG 268 errs() << u << ") "; 269 PabloPrinter::print(stmt, errs()); 270 errs() << "\n"; 271 #endif 272 273 #ifndef NDEBUG 274 if (LLVM_UNLIKELY(in_degree(u, G) != stmt>getNumOperands())) { 275 printGraph("E", errs()); 276 errs() << "in degree (" << in_degree(u, G) << ") of " << u << " does not match number of operands (" << stmt>getNumOperands() << ")\n"; 277 } 278 #endif 279 280 assert (stmt>getClassTypeId() == typeId); 281 assert (in_degree(u, G) == stmt>getNumOperands()); 282 283 in_edge_iterator ei_begin, ei_end; 284 std::tie(ei_begin, ei_end) = in_edges(u, G); 285 auto ei = ei_begin; 286 287 // For each associative operand, find the vertex that describes the operand in G 288 for (unsigned i = 0; i < stmt>getNumOperands(); ++i) { 289 290 // Does the vertex have a value and, if so, does value dominate this statement? 291 // If not, we need to regenerate it. 292 for (bool first_cycle = true;;) { 293 if (ei == ei_end) { 294 assert (first_cycle); 295 ei = ei_begin; 296 first_cycle = false; 297 } 298 if (G[*ei] == i) { 299 break; 300 } 301 ++ei; 302 } 303 304 entry>setInsertPoint(stmt>getPrevNode()); 305 306 PabloAST * const replacement = regenerateIfNecessary(stmt, entry, source(*ei, G), count); 307 PabloAST * const op = stmt>getOperand(i); 308 if (LLVM_UNLIKELY(replacement == op)) { 309 continue; 310 } 311 312 #ifdef PRINT_DEBUG 313 errs() << " " << source(*ei, G) << ") replacing "; 314 op>print(errs()); 315 errs() << " with "; 316 replacement>print(errs()); 317 errs() << "\n"; 318 #endif 319 320 stmt>setOperand(i, replacement); 321 } 322 323 if (LLVM_UNLIKELY(typeId == TypeId::Assign)) { 324 setLastUsageTime(findVertex(stmt>getOperand(0)), count); 325 } 326 setLastUsageTime(u, ++count); 327 setValue(u, stmt); 328 187 329 if (isa<Branch>(stmt)) { 188 addBranch(stmt); 189 run(cast<Branch>(stmt)>getBody()); 330 count = rewriteAST(cast<Branch>(stmt)>getBody(), count); 331 } 332 } 333 334 return count; 335 } 336 337 /**  * 338 * @brief regenerateIfNecessary 339 * 340 * Does vertex (u) have a value and, if so, does value dominate the statement? If not, regenerate it. 341 **  */ 342 PabloAST * regenerateIfNecessary(Statement * const stmt, PabloBlock * const entry, const Vertex u, size_t & count) { 343 344 assert (isLive(u)); 345 PabloAST * value = isModified(u) ? nullptr : getValue(u); 346 if (LLVM_LIKELY(!dominates(value, stmt))) { 347 348 const auto n = in_degree(u, G); 349 const TypeId typeId = getType(u); 350 351 #ifdef PRINT_DEBUG 352 errs() << " making " << u << " " << n << " " << (int)typeId << "\n"; 353 #endif 354 355 for (auto e : make_iterator_range(in_edges(u, G))) { 356 const auto v = source(e, G); 357 regenerateIfNecessary(stmt, entry, v, count); 358 assert (getValue(v)); 359 assert (dominates(getValue(v), stmt)); 360 } 361 362 if (LLVM_LIKELY(isAssociative(typeId))) { 363 364 assert (n >= 2); 365 366 Vertex input[n]; 367 unsigned i = 0; 368 for (auto e : make_iterator_range(in_edges(u, G))) { 369 input[i++] = source(e, G); 370 } 371 std::sort(input, input + n, [this](const Vertex u, const Vertex v) { 372 return getLastUsageTime(u) < getLastUsageTime(v); 373 }); 374 value = getValue(input[0]); 375 for (unsigned i = 1; i < n; ++i) { 376 PabloAST * const op = getValue(input[i]); 377 switch (typeId) { 378 case TypeId::And: 379 value = entry>createAnd(value, op); 380 break; 381 case TypeId::Or: 382 value = entry>createOr(value, op); 383 break; 384 case TypeId::Xor: 385 value = entry>createXor(value, op); 386 break; 387 default: 388 llvm_unreachable("impossible!"); 389 } 390 } 391 392 } else if (n == 1) { 393 assert (typeId == TypeId::Not); 394 value = getValue(first_source(in_edges(u, G))); 395 value = entry>createNot(value); 396 397 } else if (n > 1) { 398 399 PabloAST * op[n] = { nullptr }; 400 for (auto e : make_iterator_range(in_edges(u, G))) { 401 const auto i = G[e]; 402 assert (i < n); 403 assert (op[i] == nullptr); 404 op[i] = getValue(source(e, G)); 405 assert (op[i]); 406 } 407 408 switch (typeId) { 409 case TypeId::Advance: 410 value = entry>createAdvance(op[0], op[1]); 411 break; 412 case TypeId::ScanThru: 413 value = entry>createScanThru(op[0], op[1]); 414 break; 415 case TypeId::MatchStar: 416 value = entry>createMatchStar(op[0], op[1]); 417 break; 418 419 default: 420 llvm_unreachable("cannot regenerate this nonassocitive statement!"); 421 } 422 190 423 } else { 191 addStatement(stmt); 192 } 193 } 194 195 // G.clear(); 196 // M.clear(); 197 // for (Statement * stmt : *block) { 198 // addStatement(stmt); 199 // } 200 201 // printGraph(G, "G", errs()); 202 // if (simplifyGraph() == Structural) { 203 // // rewriteAST(first, stmt); 204 // printGraph(G, "O", errs()); 205 // } 206 207 } 424 assert (isConstant(typeId)); 425 if (typeId == TypeId::Zeroes) { 426 value = entry>createZeroes(); 427 } else { 428 value = entry>createOnes(); 429 } 430 } 431 432 setValue(u, value); 433 setUnmodified(u); 434 } 435 setLastUsageTime(u, ++count); 436 return value; 437 } 438 439 protected: 208 440 209 441 /**  * 210 442 * @brief simplifyGraph 211 443 **  */ 212 Modification simplifyGraph() { 213 Modification modified = None; 214 for (;;) { 215 const auto p1 = applyAssociativeIdentityAnnulmentLaws(); 216 const auto p2 = applyAbsorbtionComplementIdempotentLaws(); 217 const auto p3 = applyDistributivityLaw(); 218 if (std::max(std::max(p1, p2), p3) != Structural) { 219 break; 220 } 221 modified = Structural; 222 } 444 bool simplifyGraph() { 445 446 bool modified = false; 447 448 #ifdef PRINT_DEBUG 449 errs() << "********************************************\n"; 450 #endif 451 452 restart: 453 454 #ifdef PRINT_DEBUG 455 errs() << "============================================ (1)\n"; 456 #endif 457 458 getReverseTopologicalOrdering(); 459 460 #ifdef PRINT_DEBUG 461 errs() << "============================================ (2)\n"; 462 #endif 463 464 if (applyAnnulmentAssociativeIdentityIdempotentLaws()) { 465 modified = true; 466 goto restart; 467 } 468 469 #ifdef PRINT_DEBUG 470 errs() << "============================================ (3)\n"; 471 #endif 472 473 474 if (applyAbsorbtionComplementLaws()) { 475 modified = true; 476 goto restart; 477 } 478 479 #ifdef PRINT_DEBUG 480 errs() << "============================================ (4)\n"; 481 #endif 482 483 if (applyDistributivityLaw()) { 484 modified = true; 485 goto restart; 486 } 487 488 if (modified) { 489 490 #ifdef PRINT_DEBUG 491 errs() << "============================================ (5)\n"; 492 #endif 493 494 transitiveReduction(); 495 496 #ifdef PRINT_DEBUG 497 errs() << "============================================ (6)\n"; 498 #endif 499 500 factorizeGraph(); 501 502 #ifdef PRINT_DEBUG 503 // printGraph("G", errs()); 504 #endif 505 } 506 223 507 return modified; 224 508 } 225 509 226 protected: 227 228 /**  * 229 * @brief applyAssociativeIdentityAnnulmentLaws 230 **  */ 231 Modification applyAssociativeIdentityAnnulmentLaws() { 232 233 auto identityComparator = [this](const Vertex u, const Vertex v) > bool { 234 const auto typeA = getType(u); 235 assert (typeA != TypeId::Var); 236 const auto typeB = getType(v); 237 assert (typeB != TypeId::Var); 238 if (LLVM_LIKELY(typeA != typeB)) { 239 using value_of = std::underlying_type<TypeId>::type; 240 return static_cast<value_of>(typeA) < static_cast<value_of>(typeB); 241 } else { 242 const auto degA = in_degree(u, G); 243 const auto degB = in_degree(v, G); 244 if (degA != degB) { 245 return degA < degB; 246 } else { 247 Vertex adjA[degA]; 248 Vertex adjB[degA]; 249 in_edge_iterator ei, ej; 250 std::tie(ei, std::ignore) = in_edges(u, G); 251 std::tie(ej, std::ignore) = in_edges(v, G); 252 for (size_t i = 0; i < degA; ++i, ++ei, ++ej) { 253 adjA[i] = source(*ei, G); 254 adjB[i] = source(*ej, G); 255 } 256 std::sort(adjA, adjA + degA); 257 std::sort(adjB, adjB + degA); 258 for (size_t i = 0; i < degA; ++i) { 259 if (adjA[i] < adjB[i]) { 260 return true; 261 } 262 } 263 return false; 264 } 265 } 510 /**  * 511 * @brief getReverseTopologicalOrdering 512 **  */ 513 void getReverseTopologicalOrdering() { 514 515 struct PrePassInserter { 516 PrePassInserter & operator=(const Vertex u) { 517 if (LLVM_LIKELY(self.isLive(u))) { 518 assert(self.hasValidOperandIndicies(u)); 519 if (LLVM_LIKELY(isImmutable(self.getType(u))  out_degree(u, self.G) != 0)) { 520 self.ordering.push_back(u); 521 } else { 522 self.removeVertex(u); 523 } 524 } 525 return *this; 526 } 527 528 PrePassInserter(PassContainer & pc) : self(pc) { } 529 PrePassInserter & operator*() { return *this; } 530 PrePassInserter & operator++() { return *this; } 531 PrePassInserter & operator++(int) { return *this; } 532 533 public: 534 PassContainer & self; 266 535 }; 267 536 268 flat_set<Vertex, decltype(identityComparator)> V(identityComparator); 537 538 ordering.clear(); 539 ordering.reserve(num_vertices(G)); 540 topological_sort(G, PrePassInserter(*this)); 541 assert (!ordering.empty()); 542 } 543 544 /**  * 545 * @brief applyAnnulmentAssociativeIdentityIdempotentLaws 546 **  */ 547 bool applyAnnulmentAssociativeIdentityIdempotentLaws() { 548 549 auto IdentityHash = [this](const Vertex u) { 550 using value_of = std::underlying_type<TypeId>::type; 551 const auto n = in_degree(u, G); 552 Vertex operands[n]; 553 unsigned i = 0; 554 for (auto e : make_iterator_range(in_edges(u, G))) { 555 operands[i++] = source(e, G); 556 } 557 std::sort(operands, operands + n); 558 size_t h = 0; 559 boost::hash_combine(h, static_cast<value_of>(getType(u))); 560 for (unsigned j = 0; j < n; ++j) { 561 boost::hash_combine(h, operands[j]); 562 } 563 return h; 564 }; 565 566 auto IdentityComparator = [this](const Vertex u, const Vertex v) { 567 const auto typeId = getType(u); 568 if (LLVM_LIKELY(typeId == getType(v))) { 569 const unsigned n = in_degree(u, G); 570 if (LLVM_UNLIKELY(n == 0)) { 571 assert (isConstant(typeId) && in_degree(v, G) == 0); 572 return true; 573 } 574 if (in_degree(v, G) == n) { 575 Vertex adjA[n]; 576 Vertex adjB[n]; 577 auto ei = std::get<0>(in_edges(u, G)); 578 auto ej = std::get<0>(in_edges(v, G)); 579 // if this is an associative op, order doesn't matter 580 if (isAssociative(typeId)) { 581 for (unsigned i = 0; i < n; ++i, ++ei, ++ej) { 582 adjA[i] = source(*ei, G); 583 adjB[i] = source(*ej, G); 584 } 585 std::sort(adjA, adjA + n); 586 std::sort(adjB, adjB + n); 587 } else { // otherwise consider the order indicated by the edges 588 for (unsigned i = 0; i < n; ++i, ++ei, ++ej) { 589 adjA[G[*ei]] = source(*ei, G); 590 adjB[G[*ej]] = source(*ej, G); 591 } 592 } 593 for (unsigned i = 0; i < n; ++i) { 594 if (adjA[i] != adjB[i]) { 595 return false; 596 } 597 } 598 return true; 599 } 600 } 601 return false; 602 }; 603 604 using IdentitySet = std::unordered_set<Vertex, decltype(IdentityHash), decltype(IdentityComparator)>; 605 606 IdentitySet V{0, IdentityHash, IdentityComparator}; 269 607 V.reserve(num_vertices(G)); 270 608 271 VertexSet ordering; 272 ordering.reserve(num_vertices(G)); 273 274 topological_sort(G, std::back_inserter(ordering)); // note: ordering is in reverse topological order 275 276 Modification modified = None; 609 bool modified = false; 277 610 278 611 for (const auto u : boost::adaptors::reverse(ordering)) { 279 const TypeId typeId = getType(u); 280 if (isImmutable(typeId)) { 612 assert (isLive(u)); 613 assert(hasValidOperandIndicies(u)); 614 615 auto typeId = getType(u); 616 617 if (LLVM_UNLIKELY(isImmutable(typeId))) { 281 618 continue; 282 } else if (LLVM_UNLIKELY(typeId == TypeId::Zeroes  typeId == TypeId::Ones)) { 283 for(;;) { 284 bool done = true; 285 for (auto e : make_iterator_range(out_edges(u, G))) { 286 const auto v = target(e, G); 287 const auto targetTypeId = getType(v); 288 if (LLVM_UNLIKELY(isAssociative(targetTypeId))) { 289 290 errs() << "  identity relationship\n"; 291 292 if (isIdentityRelation(typeId, targetTypeId)) { 293 remove_edge(e, G); 294 } else { 295 setType(v, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones); 296 clear_in_edges(v, G); 297 } 298 done = false; 299 modified = Structural; 300 break; 301 } 302 } 303 if (done) { 304 break; 305 } 306 } 619 } else if (LLVM_UNLIKELY(out_degree(u, G) == 0)) { 620 removeVertex(u); 621 continue; 622 } 623 624 if (LLVM_UNLIKELY(isConstant(typeId))) { identity_or_annulment_check: 625 626 assert (typeId == getType(u)); 627 628 const auto n = out_degree(u, G); 629 Vertex T[n]; 630 unsigned count = 0; 631 632 for (auto e : make_iterator_range(out_edges(u, G))) { 633 const auto v = target(e, G); 634 if (LLVM_UNLIKELY(isDistributive(getType(v)))) { 635 assert (count < n); 636 assert (u != v); 637 T[count++] = v; 638 } 639 } 640 641 while (LLVM_UNLIKELY(count != 0)) { 642 643 // typeId targetTypeId Optimization 644 //    645 // Zeroes Or identity 646 // Zeroes And annulment (0) 647 // Ones Or annulment (1) 648 // Ones And identity 649 650 assert (count < n); 651 const auto v = T[count]; 652 setModified(v); 653 modified = true; 654 if (isIdentityRelation(typeId, getType(v))) { 655 #ifdef PRINT_DEBUG 656 errs() << "identity " << v << " >> " << u << "\n"; 657 #endif 658 assert (edge(u, v, G).second); 659 remove_edge(u, v, G); 660 } else { // annulment 661 #ifdef PRINT_DEBUG 662 errs() << "annulment (" << (int)(typeId) << ") " << u << " >> " << v << "\n"; 663 #endif 664 setType(v, typeId); 665 clear_in_edges(v, G); 666 } 667 } 668 307 669 } else if (isAssociative(typeId)) { 308 670 if (LLVM_UNLIKELY(in_degree(u, G) == 0)) { 671 #ifdef PRINT_DEBUG 672 errs() << "nullary associative " << u << "\n"; 673 #endif 674 setModified(u); 675 typeId = TypeId::Zeroes; 309 676 setType(u, TypeId::Zeroes); 677 modified = true; 678 goto identity_or_annulment_check; 679 } else if (LLVM_UNLIKELY(in_degree(u, G) == 1)) { 680 // An associative operation with only one element is always equivalent to the element 681 const auto v = first_source(in_edges(u, G)); 682 for (const auto e : make_iterator_range(out_edges(u, G))) { 683 addEdge(v, target(e, G), G[e]); 684 } 685 #ifdef PRINT_DEBUG 686 errs() << "unary associative " << v << " >> " << u << "\n"; 687 #endif 688 removeVertex(u); 689 continue; 310 690 } else { 311 // An associative operation with only one element is always equivalent to the element 312 bool contractable = true; 313 if (LLVM_LIKELY(in_degree(u, G) > 1)) { 314 for (auto e : make_iterator_range(out_edges(u, G))) { 315 if (LLVM_LIKELY(typeId != getType(target(e, G)))) { 316 contractable = false; 317 break; 691 // Take the transitive closure of these arcs, we may reveal the underlying equation 692 Vertex removed[out_degree(u, G)]; 693 unsigned n = 0; 694 for (auto ei : make_iterator_range(out_edges(u, G))) { 695 const auto v = target(ei, G); 696 if (typeId == getType(v)) { 697 assert(hasValidOperandIndicies(v)); 698 for (auto ej : make_iterator_range(in_edges(u, G))) { 699 addEdge(source(ej, G), v, G[ei]); 318 700 } 319 } 320 } 321 if (LLVM_UNLIKELY(contractable)) { 322 for (auto ei : make_iterator_range(in_edges(u, G))) { 323 for (auto ej : make_iterator_range(out_edges(u, G))) { 324 addEdge(source(ei, G), target(ej, G), G[ei]); 701 setModified(v); 702 removed[n++] = v; 703 #ifdef PRINT_DEBUG 704 errs() << "transitive associative " << v << " >> " << u << "\n"; 705 #endif 706 } 707 } 708 for (unsigned i = 0; i < n; ++i) { 709 const auto v = removed[i]; 710 assert (edge(u, v, G).second); 711 remove_edge(u, v, G); 712 assert(hasValidOperandIndicies(v)); 713 } 714 if (LLVM_UNLIKELY(out_degree(u, G) == 0)) { 715 removeVertex(u); 716 continue; 717 } 718 if (LLVM_UNLIKELY(typeId == TypeId::Xor)) { 719 // Canonicalize xor operations: (A â Â¬B) = (A â B â 1) 720 Vertex negation[in_degree(u, G)]; 721 unsigned count = 0; 722 for (const auto e : make_iterator_range(in_edges(u, G))) { 723 const auto v = source(e, G); 724 const auto typeId = getType(v); 725 if (LLVM_UNLIKELY(typeId == TypeId::Not)) { 726 negation[count++] = v; 325 727 } 326 728 } 327 removeVertex(u); 328 modified = std::max(modified, Trivial); 329 continue; 330 } 331 332 if (LLVM_UNLIKELY(typeId == TypeId::Xor)) { 333 // TODO:: (A â Â¬B) = (A â (B â 1)) = Â¬(A â B) 334 335 } 336 337 338 339 } 340 } 341 342 assert (getType(u) != TypeId::Var); 343 729 if (LLVM_UNLIKELY(count != 0)) { 730 #ifdef PRINT_DEBUG 731 errs() << "xor canonicalization (a) " << u << "\n"; 732 #endif 733 for (unsigned i = 0; i < count; ++i) { 734 const auto v = negation[i]; 735 assert (edge(v, u, G).second); 736 remove_edge(v, u, G); 737 addEdge(first_source(in_edges(v, G)), u); 738 } 739 if ((count & 1) != 0) { 740 addEdge(makeVertex(TypeId::Ones), u); 741 } 742 setModified(u); 743 assert(hasValidOperandIndicies(u)); 744 modified = true; 745 } 746 } 747 } 748 } else if (typeId == TypeId::Not) { 749 assert (in_degree(u, G) == 1); 750 const auto v = first_source(in_edges(u, G)); 751 const auto negatedTypeId = getType(v); 752 if (LLVM_UNLIKELY(negatedTypeId == TypeId::Not)) { 753 // handle double negation 754 assert (in_degree(v, G) == 1); 755 const auto w = first_source(in_edges(v, G)); 756 for (const auto e : make_iterator_range(out_edges(u, G))) { 757 const auto v = target(e, G); 758 addEdge(w, v, G[e]); 759 setModified(v); 760 } 761 modified = true; 762 #ifdef PRINT_DEBUG 763 errs() << "double negation " << u << " > " << w << "\n"; 764 #endif 765 removeVertex(u); 766 continue; 767 } else if (LLVM_UNLIKELY(isConstant(negatedTypeId))) { 768 setModified(u); 769 typeId = (negatedTypeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes; 770 #ifdef PRINT_DEBUG 771 errs() << "constant negation (" << (int)typeId << ") " << u << "\n"; 772 #endif 773 setType(u, typeId); 774 modified = true; 775 goto identity_or_annulment_check; 776 } else if (LLVM_UNLIKELY(negatedTypeId == TypeId::Xor)) { 777 // Canonicalize xor operations: Â¬(A â B) = (A â B â 1) 778 #ifdef PRINT_DEBUG 779 errs() << "xor canonicalization (n) " << u << "\n"; 780 #endif 781 setModified(u); 782 setType(u, TypeId::Xor); 783 clear_in_edges(u, G); 784 for (const auto e : make_iterator_range(in_edges(v, G))) { 785 add_edge(source(e, G), u, 0, G); 786 } 787 addEdge(makeVertex(TypeId::Ones), u); 788 assert(hasValidOperandIndicies(u)); 789 modified = true; 790 } 791 } 792 793 // check whether this vertex is a duplicate 344 794 const auto f = V.insert(u); 345 795 if (LLVM_UNLIKELY(!f.second)) { 346 const auto v = *f.first; 347 348 errs() << "  replacing " << u << " with " << v << "\n"; 349 350 for (auto e : make_iterator_range(out_edges(u, G))) { 351 addEdge(v, target(e, G), G[e]); 352 } 353 removeVertex(u); 354 modified = Structural; 355 } 356 } 796 remapVertex(u, *f.first); 797 } 798 } 799 357 800 return modified; 358 801 } 359 802 360 /**  * 361 * @brief applyAbsorbtionComplementIdempotentLaws 362 **  */ 363 Modification applyAbsorbtionComplementIdempotentLaws() { 364 Modification modified = None; 365 for (const Vertex u : make_iterator_range(vertices(G))) { 803 // A XOR NOT(A XOR B) = NOT B 804 805 // A AND NOT(A AND B) = A AND NOT B 806 807 // A AND NOT(A OR B) = 0 808 809 // A OR NOT(A AND B) = 1 810 811 // A OR NOT(A OR B) = A OR NOT B 812 813 // * (ABSORBTION) A âš (A â§ B) â A â§ (A âš B) â A 814 815 /**  * 816 * @brief applyAbsorbtionComplementLaws 817 **  */ 818 bool applyAbsorbtionComplementLaws() { 819 bool modified = false; 820 for (const Vertex u : ordering) { 821 assert (isLive(u)); 822 assert (hasValidOperandIndicies(u)); 366 823 const TypeId typeId = getType(u); 367 824 if (isDistributive(typeId)) { 368 restart_loop: in_edge_iterator ei_begin, ei_end; 369 std::tie(ei_begin, ei_end) = in_edges(u, G); 370 for (auto ei = ei_begin; ei != ei_end; ++ei) { 371 const auto v = source(*ei, G); 825 assert (in_degree(u, G) > 0); 826 Vertex A[in_degree(u, G)]; 827 unsigned n = 0; 828 for (const auto ei : make_iterator_range(in_edges(u, G))) { 829 const auto v = source(ei, G); 830 assert (isLive(v)); 372 831 const auto innerTypeId = getType(v); 373 if (isDistributive(innerTypeId)  innerTypeId == TypeId::Not) { 374 in_edge_iterator ek_begin, ek_end; 375 std::tie(ek_begin, ek_end) = in_edges(v, G); 376 for (auto ej = ei_begin; ej != ei_end; ++ej) { 377 for (auto ek = ek_begin; ek != ek_end; ++ek) { 378 if (LLVM_UNLIKELY(source(*ej, G) == source(*ek, G))) { 379 modified = Structural; 832 auto w = v; 833 if (innerTypeId == TypeId::Not) { 834 w = first_source(in_edges(v, G)); 835 assert ("G is cyclic!" && (w != v)); 836 assert (isLive(w)); 837 for (const auto ej : make_iterator_range(in_edges(u, G))) { 838 if (LLVM_UNLIKELY(source(ej, G) == w)) { 839 goto do_complement; 840 } 841 } 842 if (LLVM_UNLIKELY(getType(w) == oppositeTypeId(typeId))) { 843 // Check for implicit De Morgan's + Complement law application, e.g., A â§ Â¬(A âš B) â 0 844 goto check_demorgans_complement; 845 } 846 } else if (innerTypeId == oppositeTypeId(typeId)) { 847 check_demorgans_complement: 848 for (const auto ej : make_iterator_range(in_edges(w, G))) { 849 for (const auto ek : make_iterator_range(in_edges(u, G))) { 850 if (LLVM_UNLIKELY(source(ej, G) == source(ek, G))) { 380 851 if (LLVM_UNLIKELY(innerTypeId == TypeId::Not)) { 381 // complement 382 setType(u, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones); 383 clear_in_edges(u, G); 384 goto abort_loop; 852 goto do_complement; 385 853 } else { 386 if (LLVM_LIKELY(innerTypeId != typeId)) { 387 // idempotent 388 remove_edge(*ei, G); 389 } else { 390 // absorbtion 391 remove_edge(*ej, G); 392 } 393 // this seldom occurs so if it does, just restart the process rather than 394 // trying to keep the iterators valid. 395 goto restart_loop; 854 A[n++] = v; 855 goto next_variable; 396 856 } 397 857 } … … 399 859 } 400 860 } 401 } 402 } 403 abort_loop:; 861 next_variable: 862 continue; 863 } 864 if (LLVM_UNLIKELY(n != 0)) { 865 setModified(u); 866 modified = true; 867 for (;;) { 868 const auto v = A[n]; 869 #ifdef PRINT_DEBUG 870 errs() << "absorbing " << v << "," << u << "\n"; 871 #endif 872 assert (edge(v, u, G).second); 873 remove_edge(v, u, G);assert (isLive(u)); 874 if (LLVM_UNLIKELY(out_degree(v, G) == 0)) { 875 removeVertex(v); 876 } 877 if (LLVM_LIKELY(n == 0)) { 878 break; 879 } 880 } 881 } 882 } 883 continue; 884 do_complement: 885 //  886 const auto complementTypeId = (typeId == TypeId::And) ? TypeId::Zeroes : TypeId::Ones; 887 #ifdef PRINT_DEBUG 888 errs() << "complement (" << (int)complementTypeId << ") " << u << "\n"; 889 #endif 890 setModified(u); 891 setType(u, complementTypeId); 892 clear_in_edges(u, G); 893 modified = true; 404 894 } 405 895 return modified; 406 896 } 407 897 408 /**  * 409 * @brief identifyDistributableVertices 898 void print(raw_ostream & out, const Sequence & S) { 899 if (S.empty()) { 900 return; 901 } 902 out << Gd[S[0]]; 903 for (unsigned i = 1; i < S.size(); ++i) { 904 out << ',' << Gd[S[i]]; 905 } 906 } 907 908 /**  * 909 * @brief applyDistributivityLaw 410 910 * 411 * Let (u) â V(G) be a conjunction â§ or disjunction âš and (v) be a â§ or âš and the opposite type of (u). If (u,v) â 412 * E(G) and all outgoing edges of (v) lead to a vertex of the same type, add (u), (v) and any vertex (w) in which 413 * (w,v) â E(G) to the distribution graph H as well as the edges indicating their relationships within G. 911 * sources (s) inner (âš) (âš) 912 * / \ \ / 913 * inner (âš) (âš) x (â§) 914 * \ /  915 * outer (â§) sources  (s) 916 *  / 917 * y (âš) 918 *  919 * outer (â§) 414 920 * 415 * (?) (?) (?) < w1, w2, ... 416 * \  / 417 * (v) < v 418 * / \ 419 * u > (â§) (â§) 420 * 421 **  */ 422 void identifyDistributableVertices() { 423 424 assert (D.empty() && L.empty()); 425 426 for (const Vertex u : make_iterator_range(vertices(G))) { 427 const TypeId outerTypeId = getType(u); 428 if (isDistributive(outerTypeId)) { 429 bool beneficial = true; 430 const TypeId innerTypeId = oppositeTypeId(outerTypeId); 431 for (auto e : make_iterator_range(out_edges(u, G))) { 432 const Vertex v = target(e, G); 433 if (LLVM_UNLIKELY(getType(v) != innerTypeId)) { 434 beneficial = false; 435 break; 436 } 437 } 438 if (beneficial) { 439 for (auto e : make_iterator_range(out_edges(u, G))) { 440 const auto v = target(e, G); 441 const auto f = std::lower_bound(D.begin(), D.end(), v); 921 **  */ 922 bool applyDistributivityLaw() { 923 924 makeDistributionSubgraph(); 925 926 bool modified = false; 927 928 for (;;) { 929 930 assert (std::is_sorted(D.begin(), D.end())); 931 932 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 933 if (LLVM_UNLIKELY(D.empty())) { 934 break; 935 } 936 937 #ifdef PRINT_DEBUG 938 if (modified) { 939 errs() << "\n"; 940 } 941 #endif 942 943 const auto lowerSet = obtainDistributableClauses(D); 944 945 for (const auto & lower : lowerSet) { 946 const auto & outer = std::get<0>(lower); 947 const auto upperSet = obtainDistributableSources(std::get<1>(lower)); 948 for (const auto & upper : upperSet) { 949 950 const auto & sources = std::get<1>(upper); 951 const auto & inner = std::get<0>(upper); 952 953 const auto outerTypeId = getType(Gd[outer[0]]); 954 const auto innerTypeId = oppositeTypeId(outerTypeId); 955 956 // Update G to match the desired change 957 const auto x = makeVertex(outerTypeId); 958 const auto y = makeVertex(innerTypeId); 959 960 #ifdef PRINT_DEBUG 961 errs() << "distributing {"; 962 print(errs(), sources); 963 if (innerTypeId == TypeId::And) { 964 errs() << "} â§ {"; 965 } else { 966 errs() << "} âš {"; 967 } 968 print(errs(), inner); 969 if (outerTypeId == TypeId::Or) { 970 errs() << "} âš {"; 971 } else { 972 errs() << "} â§ {"; 973 } 974 print(errs(), outer); 975 errs() << "} > " << x << ',' << y << '\n'; 976 #endif 977 978 for (const auto i : inner) { 979 const auto u = Gd[i]; 980 assert (getType(u) == innerTypeId); 981 for (const Vertex j : outer) { 982 const auto v = Gd[j]; 983 assert (getType(v) == outerTypeId); 984 assert (edge(u, v, G).second); 985 remove_edge(i, j, Gd); 986 remove_edge(u, v, G); 987 } 988 addEdge(u, x); 989 } 990 991 for (const Vertex i : sources) { 992 const auto u = Gd[i]; 993 for (const Vertex j : inner) { 994 const auto v = Gd[j]; 995 assert (edge(u, v, G).second); 996 remove_edge(i, j, Gd); 997 remove_edge(u, v, G); 998 } 999 1000 addEdge(u, y); 1001 } 1002 1003 addEdge(x, y); 1004 1005 for (const Vertex i : outer) { 1006 const auto u = Gd[i]; 1007 setModified(u); 1008 addEdge(y, u); 1009 } 1010 1011 modified = true; 1012 } 1013 } 1014 1015 for (;;) { 1016 if (LLVM_UNLIKELY(D.size() == 1)) { 1017 D.clear(); 1018 break; 1019 } 1020 std::uniform_int_distribution<> dist(0, D.size()  1); 1021 const auto p = D.begin() + dist(R); 1022 const auto u = *p; 1023 D.erase(p); 1024 bool found = false; 1025 for (auto e : make_iterator_range(in_edges(u, Gd))) { 1026 const auto v = source(e, G); 1027 if (canDistribute(v, 1)) { 1028 auto f = std::lower_bound(D.begin(), D.end(), v); 442 1029 if (f == D.end()  *f != v) { 443 1030 D.insert(f, v); 444 assert (std::is_sorted(D.begin(), D.end())); 445 } 446 } 1031 found = true; 1032 } 1033 } 1034 } 1035 clear_in_edges(u, Gd); 1036 if (found) { 1037 break; 1038 } 1039 } 1040 } 1041 1042 Gd.clear(); 1043 Md.clear(); 1044 1045 return modified; 1046 } 1047 1048 /**  * 1049 * @brief makeDistributionSubgraph 1050 **  */ 1051 void makeDistributionSubgraph() { 1052 assert (D.empty()); 1053 for (const auto u : make_iterator_range(vertices(G))) { 1054 if (isLive(u)) { 1055 const auto outerTypeId = getType(u); 1056 if (isDistributive(outerTypeId)) { 1057 const auto innerTypeId = oppositeTypeId(outerTypeId); 1058 for (auto ei : make_iterator_range(in_edges(u, G))) { 1059 const auto v = source(ei, G); 1060 assert (isLive(v)); 1061 // can we distribute this vertex? 1062 if (getType(v) == innerTypeId) { 1063 // is it safe to add v to the distribution graph? I.e., do we need to calculate its value anyway? 1064 bool safe = true; 1065 for (auto ej : make_iterator_range(out_edges(v, G))) { 1066 const auto w = target(ej, G); 1067 if (isLive(w) && getType(w) != outerTypeId) { 1068 safe = false; 1069 break; 1070 } 1071 } 1072 if (safe) { 1073 D.push_back(v); 1074 } 1075 } 1076 } 1077 if (D.size() > 1) { 1078 std::sort(D.begin(), D.end()); 1079 D.erase(std::unique(D.begin(), D.end()), D.end()); 1080 if (LLVM_LIKELY(D.size() > 1)) { 1081 const auto du = addDistributionVertex(u); 1082 for (const auto v : D) { 1083 assert (isLive(v) && getType(v) == innerTypeId); 1084 const auto dv = addDistributionVertex(v); 1085 add_edge(dv, du, Gd); 1086 for (auto ej : make_iterator_range(in_edges(v, G))) { 1087 const auto x = source(ej, G); 1088 assert (isLive(x)); 1089 add_edge(addDistributionVertex(x), dv, Gd); 1090 } 1091 } 1092 } 1093 } 1094 D.clear(); 1095 } 1096 } 1097 } 1098 1099 assert (D.empty()); 1100 for (auto u : make_iterator_range(vertices(Gd))) { 1101 if (out_degree(u, Gd) == 0) { 1102 assert (canDistribute(u)); 1103 D.push_back(u); 1104 } 1105 } 1106 } 1107 1108 /**  * 1109 * @brief canDistribute 1110 **  */ 1111 bool canDistribute(const DistributionVertex u, const unsigned outDegree = 0) const { 1112 assert (u < num_vertices(Gd)); 1113 assert (isLive(Gd[u])); 1114 if (out_degree(u, Gd) == outDegree && in_degree(u, Gd) > 0) { 1115 const auto typeId = oppositeTypeId(getType(Gd[u])); 1116 unsigned count = 0; 1117 for (auto e : make_iterator_range(in_edges(u, Gd))) { 1118 if (getType(Gd[source(e, Gd)]) == typeId) { 1119 if (count == 1) { 1120 return true; 1121 } 1122 ++count; 1123 } 1124 } 1125 } 1126 return false; 1127 } 1128 1129 /**  * 1130 * @brief obtainDistributableClauses 1131 **  */ 1132 BicliqueSet obtainDistributableClauses(const Sequence & S) { 1133 1134 struct OppositeType { 1135 bool operator()(const DistributionVertex u) { 1136 return self.getType(self.Gd[u]) == typeId; 1137 } 1138 OppositeType(PassContainer * const pc, const DistributionVertex u) 1139 : self(*pc) 1140 , typeId(oppositeTypeId(self.getType(self.Gd[u]))) { 1141 1142 } 1143 private: 1144 PassContainer & self; 1145 const TypeId typeId; 1146 }; 1147 1148 struct AllUsers { 1149 bool operator()(const DistributionVertex u) { 1150 return out_degree(self.Gd[u], self.G) == degree; 1151 } 1152 AllUsers(PassContainer * const pc, const DistributionVertex u) 1153 : self(*pc) 1154 , degree(out_degree(self.Gd[u], self.G)) { 1155 1156 } 1157 private: 1158 PassContainer & self; 1159 const size_t degree; 1160 }; 1161 1162 // return makeIndependent(enumerateBicliques<OppositeType, AllUsers>(S, Gd, 1, 2), 1); 1163 1164 return enumerateBicliques<OppositeType, AllUsers>(S, Gd, 1, 2); 1165 } 1166 1167 /**  * 1168 * @brief obtainDistributableSources 1169 **  */ 1170 BicliqueSet obtainDistributableSources(const Sequence & S) { 1171 return makeIndependent(enumerateBicliques<>(S, Gd, 2, 1), 0); 1172 } 1173 1174 /**  * 1175 * @brief transitiveReduction 1176 **  */ 1177 void transitiveReduction() { 1178 flat_set<Vertex> T; 1179 for (const auto u : ordering) { 1180 if (isLive(u)) { 1181 const auto typeId = getType(u); 1182 if (isAssociative(typeId)) { 1183 assert (in_degree(u, G) != 0); 1184 for (auto ei : make_iterator_range(in_edges(u, G))) { 1185 const auto v = source(ei, G); 1186 assert (isLive(v)); 1187 if (getType(v) == typeId) { 1188 for (auto ej : make_iterator_range(in_edges(v, G))) { 1189 const auto w = source(ej, G); 1190 assert (isLive(w)); 1191 T.insert(w); 1192 } 1193 } 1194 } 1195 #ifndef NDEBUG 447 1196 for (auto e : make_iterator_range(in_edges(u, G))) { 448 const auto v = source(e, G); 449 const auto f = std::lower_bound(L.begin(), L.end(), v); 450 if (f == L.end()  *f != v) { 451 L.insert(f, v); 452 assert (std::is_sorted(L.begin(), L.end())); 453 } 454 } 455 } 456 } 457 } 458 459 // D = D  L 460 461 if (!L.empty()) { 462 if (!D.empty()) { 463 auto di = D.begin(), li = L.begin(), li_end = L.end(); 464 for (;;) { 465 if (*li < *di) { 466 if (++li == li_end) { 467 break; 468 } 469 } else { 470 if (*di < *li) { 471 ++di; 1197 assert (T.count(source(e, G)) == 0); 1198 } 1199 #endif 1200 const auto m = in_degree(u, G); 1201 for (const auto w : T) { 1202 remove_edge(w, u, G); 1203 } 1204 T.clear(); 1205 const auto n = in_degree(u, G); 1206 assert (n != 0 && n <= m); 1207 if (LLVM_UNLIKELY(n == 1)) { 1208 // An associative operation with only one element is always equivalent to the element 1209 const auto v = first_source(in_edges(u, G)); 1210 #ifdef PRINT_DEBUG 1211 errs() << "unary associative " << v << " >> " << u << " (tr)\n"; 1212 #endif 1213 for (auto e : make_iterator_range(out_edges(u, G))) { 1214 addEdge(v, target(e, G), G[e]); 1215 } 1216 removeVertex(u); 1217 } else if (LLVM_UNLIKELY(m != n)) { 1218 #ifdef PRINT_DEBUG 1219 errs() << "transitive reduction " << u << "\n"; 1220 #endif 1221 setModified(u); 1222 } 1223 } 1224 } 1225 } 1226 } 1227 1228 /**  * 1229 * @brief factorizeGraph 1230 * 1231 * Factorize the associative operations in the final graph 1232 **  */ 1233 void factorizeGraph() { 1234 1235 Sequence groups[3]; 1236 for (const auto u : make_iterator_range(vertices(G))) { 1237 if (isLive(u)) { 1238 switch (getType(u)) { 1239 case TypeId::And: 1240 groups[0].push_back(u); break; 1241 case TypeId::Or: 1242 groups[1].push_back(u); break; 1243 case TypeId::Xor: 1244 groups[2].push_back(u); break; 1245 default: break; 1246 } 1247 } 1248 } 1249 1250 const TypeId op[3] = { TypeId::And, TypeId::Or, TypeId::Xor }; 1251 1252 for (unsigned i = 0; i < 3; ++i) { 1253 1254 for (;;) { 1255 1256 auto factors = makeIndependent(enumerateBicliques<>(groups[i], G, 2, 2), 1); 1257 if (factors.empty()) { 1258 break; 1259 } 1260 1261 bool noChanges = true; 1262 1263 for (auto & factor : factors) { 1264 auto & targets = std::get<0>(factor); 1265 assert (targets.size() > 1); 1266 auto & sources = std::get<1>(factor); 1267 assert (sources.size() > 1); 1268 1269 // One of the targets may be our replacement vertex. 1270 // If so, its in degree will equal sources. 1271 Vertex x = 0; 1272 bool create = true; 1273 for (auto j = targets.begin(); j != targets.end(); ) { 1274 assert (hasValidOperandIndicies(*j)); 1275 if (in_degree(*j, G) == sources.size()) { 1276 x = *j; 1277 j = targets.erase(j); 1278 create = false; 472 1279 } else { 473 di = D.erase(di); 474 } 475 if (di == D.end()) { 476 break; 477 } 478 } 479 } 480 } 481 L.clear(); 482 } 483 } 484 485 /**  * 486 * @brief applyDistributivityLaw 487 **  */ 488 Modification applyDistributivityLaw() { 489 490 identifyDistributableVertices(); 491 492 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 493 if (D.empty()) { 494 return None; 495 } 496 497 Modification modified = None; 498 499 const auto lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(D)), 1); 500 501 for (auto & lower : lowerSet) { 502 const auto upperSet = independentCliqueSets<0>(enumerateBicliques(std::get<1>(lower)), 2); 503 for (const auto & upper : upperSet) { 504 505 const auto & sources = std::get<1>(upper); 506 const auto & intermediary = std::get<0>(upper); 507 const auto & sinks = std::get<0>(lower); 508 509 510 511 const auto outerTypeId = getType(sinks.front()); 512 const auto innerTypeId = oppositeTypeId(outerTypeId); 513 514 errs() << "  distributing\n"; 515 516 // Update G to match the desired change 517 const auto x = makeVertex(outerTypeId); 518 const auto y = makeVertex(innerTypeId); 519 520 for (const auto i : intermediary) { 521 assert (getType(i) == innerTypeId); 522 for (const Vertex t : sinks) { 523 assert (getType(t) == outerTypeId); 524 remove_edge(i, t, G); 525 } 526 addEdge(i, x); 527 } 528 529 for (const Vertex s : sources) { 530 for (const Vertex i : intermediary) { 531 remove_edge(s, i, G); 532 } 533 addEdge(s, y); 534 } 535 addEdge(x, y); 536 537 for (const Vertex t : sinks) { 538 addEdge(y, t, std::get<0>(G[t])); 539 } 540 541 modified = Structural; 542 } 543 } 544 545 D.clear(); 546 547 return modified; 548 } 549 1280 ++j; 1281 } 1282 } 1283 if (LLVM_UNLIKELY(targets.empty())) { 1284 continue; 1285 } 1286 if (create) { 1287 x = makeVertex(op[i]); 1288 groups[i].push_back(x); 1289 for (auto u : sources) { 1290 addEdge(u, x); 1291 } 1292 } 1293 1294 // Clear out the biclique between the source and target vertices. 1295 for (auto u : sources) { 1296 for (auto v : targets) { 1297 assert (edge(u, v, G).second); 1298 boost::remove_edge(u, v, G); 1299 } 1300 } 1301 1302 for (auto v : targets) { 1303 assert (getType(v) == op[i]); 1304 addEdge(x, v); 1305 setModified(v); 1306 assert(hasValidOperandIndicies(v)); 1307 } 1308 1309 noChanges = false; 1310 } 1311 if (LLVM_UNLIKELY(noChanges)) { 1312 break; 1313 } 1314 } 1315 } 1316 } 550 1317 551 1318 /**  * … … 555 1322 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in 556 1323 * bipartition A and their adjacencies to be in B. 557 **  */ 558 559 BicliqueSet enumerateBicliques(const VertexSet & A) { 560 using IntersectionSets = std::set<VertexSet>; 561 562 IntersectionSets B1; 563 for (auto u : A) { 564 if (in_degree(u, G) > 0) { 565 VertexSet incomingAdjacencies; 566 incomingAdjacencies.reserve(in_degree(u, G)); 567 for (auto e : make_iterator_range(in_edges(u, G))) { 568 incomingAdjacencies.push_back(source(e, G)); 569 } 570 std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end()); 571 B1.insert(std::move(incomingAdjacencies)); 572 } 573 } 574 575 IntersectionSets B(B1); 576 577 IntersectionSets Bi; 578 579 VertexSet clique; 580 for (auto i = B1.begin(); i != B1.end(); ++i) { 581 for (auto j = i; ++j != B1.end(); ) { 582 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 583 if (clique.size() > 0) { 584 if (B.count(clique) == 0) { 585 Bi.insert(clique); 1324 **  */ 1325 template <typename Graph> 1326 struct AcceptAny { 1327 bool operator()(const typename Graph::vertex_descriptor) { return true; } 1328 AcceptAny(PassContainer * const, const typename Graph::vertex_descriptor) { } 1329 }; 1330 1331 template <typename AcceptIntoA = AcceptAny<Graph>, typename AcceptIntoB = AcceptAny<Graph>, typename Graph> 1332 BicliqueSet enumerateBicliques(const Sequence & S, const Graph & G, const unsigned minimumSizeA = 1, const unsigned minimumSizeB = 1) { 1333 using IntersectionSets = std::set<Sequence>; 1334 1335 assert (std::is_sorted(S.begin(), S.end())); 1336 1337 BicliqueSet cliques(0); 1338 1339 if (S.size() >= minimumSizeA) { 1340 1341 IntersectionSets B1; 1342 for (auto u : S) { 1343 const auto n = in_degree(u, G); 1344 if (n > 0) { 1345 Sequence B; 1346 B.reserve(n); 1347 AcceptIntoB acceptor(this, u); 1348 for (auto e : make_iterator_range(in_edges(u, G))) { 1349 const auto v = source(e, G); 1350 if (acceptor(v)) { 1351 B.push_back(v); 1352 } 1353 } 1354 if (B.size() >= minimumSizeB) { 1355 std::sort(B.begin(), B.end()); 1356 assert(std::unique(B.begin(), B.end()) == B.end()); 1357 B1.insert(std::move(B)); 1358 } 1359 } 1360 } 1361 1362 IntersectionSets B(B1); 1363 1364 IntersectionSets Bi; 1365 1366 Sequence clique; 1367 for (auto i = B1.begin(); i != B1.end(); ++i) { 1368 assert (std::is_sorted(i>begin(), i>end())); 1369 for (auto j = i; ++j != B1.end(); ) { 1370 assert (std::is_sorted(j>begin(), j>end())); 1371 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 1372 if (clique.size() >= minimumSizeB) { 1373 if (B.count(clique) == 0) { 1374 Bi.insert(clique); 1375 } 586 1376 } 587 1377 clique.clear(); 588 1378 } 589 1379 } 590 } 591 592 for (;;) { 593 if (Bi.empty()) { 594 break; 595 } 596 B.insert(Bi.begin(), Bi.end()); 1380 597 1381 IntersectionSets Bk; 598 for (auto i = B1.begin(); i != B1.end(); ++i) { 599 for (auto j = Bi.begin(); j != Bi.end(); ++j) { 600 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 601 if (clique.size() > 0) { 602 if (B.count(clique) == 0) { 603 Bk.insert(clique); 1382 for (;;) { 1383 if (Bi.empty()) { 1384 break; 1385 } 1386 B.insert(Bi.begin(), Bi.end()); 1387 for (auto i = B1.begin(); i != B1.end(); ++i) { 1388 assert (std::is_sorted(i>begin(), i>end())); 1389 for (auto j = Bi.begin(); j != Bi.end(); ++j) { 1390 assert (std::is_sorted(j>begin(), j>end())); 1391 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 1392 if (clique.size() >= minimumSizeB) { 1393 if (B.count(clique) == 0) { 1394 Bk.insert(clique); 1395 } 604 1396 } 605 1397 clique.clear(); 606 1398 } 607 1399 } 608 } 609 Bi.swap(Bk); 610 } 611 612 BicliqueSet cliques; 613 cliques.reserve(B.size()); 614 for (auto Bi = B.begin(); Bi != B.end(); ++Bi) { 615 VertexSet Ai(A); 616 for (const Vertex u : *Bi) { 617 VertexSet Aj; 618 Aj.reserve(out_degree(u, G)); 619 for (auto e : make_iterator_range(out_edges(u, G))) { 620 Aj.push_back(target(e, G)); 621 } 622 std::sort(Aj.begin(), Aj.end()); 623 VertexSet Ak; 624 Ak.reserve(std::min(Ai.size(), Aj.size())); 625 std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak)); 626 Ai.swap(Ak); 627 } 628 assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly 629 cliques.emplace_back(std::move(Ai), std::move(*Bi)); 630 } 1400 Bi.swap(Bk); 1401 Bk.clear(); 1402 } 1403 1404 cliques.reserve(B.size()); 1405 1406 Sequence Aj; 1407 Sequence Ak; 1408 for (auto && Bi : B) { 1409 Sequence Ai(S); 1410 assert (Bi.size() >= minimumSizeB); 1411 bool valid = true; 1412 for (const Vertex u : Bi) { 1413 assert (std::is_sorted(Ai.begin(), Ai.end())); 1414 assert (Ai.size() >= minimumSizeA); 1415 Aj.clear(); 1416 Aj.reserve(out_degree(u, G)); 1417 AcceptIntoA acceptor(this, u); 1418 for (auto e : make_iterator_range(out_edges(u, G))) { 1419 const auto v = target(e, G); 1420 if (acceptor(v)) { 1421 Aj.push_back(v); 1422 } 1423 } 1424 if (Aj.size() < minimumSizeA) { 1425 valid = false; 1426 break; 1427 } 1428 std::sort(Aj.begin(), Aj.end()); 1429 assert(std::unique(Aj.begin(), Aj.end()) == Aj.end()); 1430 if (LLVM_UNLIKELY(Aj.size() < minimumSizeA)) { 1431 valid = false; 1432 break; 1433 } 1434 Ak.clear(); 1435 Ak.reserve(std::min(Ai.size(), Aj.size())); 1436 std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak)); 1437 if (Ak.size() < minimumSizeA) { 1438 valid = false; 1439 break; 1440 } 1441 Ai.swap(Ak); 1442 } 1443 if (valid) { 1444 cliques.emplace_back(std::move(Ai), std::move(Bi)); 1445 } 1446 } 1447 1448 } 1449 631 1450 return cliques; 632 1451 } 633 1452 634 635 /**  * 636 * @brief independentCliqueSets 637 **  */ 638 template <unsigned side> 639 BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) { 640 641 642 const auto l = cliques.size(); 1453 /**  * 1454 * @brief makeIndependent 1455 **  */ 1456 BicliqueSet && makeIndependent(BicliqueSet && S, const unsigned independentSide) { 1457 1458 const auto l = S.size(); 643 1459 IndependentSetGraph I(l); 1460 1461 assert (independentSide < 2); 644 1462 645 1463 // Initialize our weights 646 1464 for (unsigned i = 0; i != l; ++i) { 647 I[i] = std:: pow(std::get<side>(cliques[i]).size(), 2);1465 I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size(); 648 1466 } 649 1467 650 1468 // Determine our constraints 651 1469 for (unsigned i = 0; i != l; ++i) { 1470 const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]); 652 1471 for (unsigned j = i + 1; j != l; ++j) { 653 if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) { 1472 const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]); 1473 if (intersects(Si, Sj)) { 654 1474 boost::add_edge(i, j, I); 655 1475 } … … 658 1478 659 1479 // Use the greedy algorithm to choose our independent set 660 VertexSetselected;1480 Sequence selected; 661 1481 for (;;) { 662 1482 unsigned w = 0; … … 668 1488 } 669 1489 } 670 if ( w < minimum) break;1490 if (LLVM_UNLIKELY(w == 0)) break; 671 1491 selected.push_back(u); 672 1492 I[u] = 0; … … 678 1498 // Sort the selected list and then remove the unselected cliques 679 1499 std::sort(selected.begin(), selected.end(), std::greater<Vertex>()); 680 auto end = cliques.end();1500 auto end = S.end(); 681 1501 for (const unsigned offset : selected) { 682 end = cliques.erase(cliques.begin() + offset + 1, end)  1; 683 } 684 cliques.erase(cliques.begin(), end); 685 686 return std::move(cliques); 687 } 688 689 /**  * 690 * @brief removeUnhelpfulBicliques 691 * 692 * An intermediary vertex could have more than one outgoing edge but if any that are not directed to vertices in 693 * the lower biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if 694 * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique. 695 **  */ 696 BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques) { 697 for (auto ci = cliques.begin(); ci != cliques.end(); ) { 698 const auto cardinalityA = std::get<0>(*ci).size(); 699 VertexSet & B = std::get<1>(*ci); 700 for (auto bi = B.begin(); bi != B.end(); ) { 701 if (out_degree(*bi, G) == cardinalityA) { 702 ++bi; 703 } else { 704 bi = B.erase(bi); 705 } 706 } 707 if (B.size() > 1) { 708 ++ci; 709 } else { 710 ci = cliques.erase(ci); 711 } 712 } 713 return std::move(cliques); 1502 end = S.erase(S.begin() + offset + 1, end)  1; 1503 } 1504 S.erase(S.begin(), end); 1505 1506 return std::move(S); 1507 } 1508 1509 1510 /**  * 1511 * @brief addDistributionVertex 1512 **  */ 1513 DistributionVertex addDistributionVertex(const Vertex u) { 1514 assert (u < num_vertices(G)); 1515 const auto f = Md.find(u); 1516 if (f == Md.end()) { 1517 #ifndef NDEBUG 1518 for (auto v : make_iterator_range(vertices(Gd))) { 1519 assert (Gd[v] != u); 1520 } 1521 #endif 1522 const auto du = add_vertex(u, Gd); 1523 assert (Gd[du] == u); 1524 Md.emplace(u, du); 1525 return du; 1526 } 1527 return f>second; 714 1528 } 715 1529 … … 718 1532 **  */ 719 1533 Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) { 720 return add_vertex(std::make_ pair(expr, typeId), G);1534 return add_vertex(std::make_tuple(expr, typeId, expr ? State::Live : State::Modified, 0), G); 721 1535 } 722 1536 … … 725 1539 **  */ 726 1540 Vertex addExpression(PabloAST * const expr) { 1541 assert (expr); 727 1542 const auto f = M.find(expr); 728 1543 if (LLVM_LIKELY(f != M.end())) { 729 1544 return f>second; 730 1545 } 731 TypeId typeId = TypeId::Var; 732 if (isa<Zeroes>(expr)) { 733 typeId = TypeId::Zeroes; 734 } else if (isa<Ones>(expr)) { 735 typeId = TypeId::Ones; 736 } 737 const auto u = makeVertex(typeId, expr); 1546 assert (isConstant(expr>getClassTypeId())  isLiteral(expr>getClassTypeId())); 1547 const auto u = makeVertex(expr>getClassTypeId(), expr); 738 1548 M.emplace(expr, u); 739 if (LLVM_UNLIKELY(isa<Not>(expr))) {740 PabloAST * const negated = cast<Not>(expr)>getExpr();741 addEdge(addExpression(negated), u, negated);742 }743 1549 return u; 744 1550 } … … 748 1554 **  */ 749 1555 Vertex addStatement(Statement * const stmt) { 1556 assert (stmt); 750 1557 assert (M.count(stmt) == 0); 751 1558 const auto typeId = stmt>getClassTypeId(); 752 1559 if (LLVM_UNLIKELY(typeId == TypeId::Sel)) { 753 754 // expand Sel (C,T,F) statements into (C â§ T) âš (C â§ F)755 756 1560 const auto c = addExpression(cast<Sel>(stmt)>getCondition()); 757 1561 const auto t = addExpression(cast<Sel>(stmt)>getTrueExpr()); 758 const auto l = makeVertex(TypeId::And); 759 addEdge(c, l); 760 addEdge(t, l); 1562 const auto f = addExpression(cast<Sel>(stmt)>getFalseExpr()); 1563 const auto u = makeVertex(TypeId::And); 1564 add_edge(c, u, 0, G); 1565 add_edge(t, u, 1, G); 761 1566 const auto n = makeVertex(TypeId::Not); 762 addEdge(c, n); 763 const auto r = makeVertex(TypeId::And); 764 const auto f = addExpression(cast<Sel>(stmt)>getFalseExpr()); 765 addEdge(n, r); 766 addEdge(f, r); 767 const auto u = makeVertex(TypeId::Or, stmt); 768 M.emplace(stmt, u); 769 addEdge(l, u); 770 addEdge(r, u); 771 772 return u; 773 1567 add_edge(c, n, 0, G); 1568 const auto v = makeVertex(TypeId::And); 1569 add_edge(n, v, 0, G); 1570 add_edge(f, v, 1, G); 1571 const auto w = makeVertex(TypeId::Or); 1572 add_edge(u, w, 0, G); 1573 add_edge(v, w, 1, G); 1574 M.emplace(stmt, w); 1575 return w; 774 1576 } else { 775 776 1577 const auto u = makeVertex(typeId, stmt); 777 M.emplace(stmt, u);778 1578 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) { 779 1579 PabloAST * const op = stmt>getOperand(i); … … 781 1581 continue; 782 1582 } 783 addEdge(addExpression(op), u, op); 784 } 785 1583 add_edge(addExpression(op), u, i, G); 1584 } 1585 assert(hasValidOperandIndicies(u)); 1586 M.emplace(stmt, u); 786 1587 return u; 787 1588 } 788 789 } 790 791 /**  * 792 * @brief addBranch 793 **  */ 794 void addBranch(Statement * const br) { 795 const auto u = addStatement(br); 796 for (auto escaped : cast<Branch>(br)>getEscaped()) { 797 addEdge(u, addExpression(escaped), escaped); 798 } 799 } 800 1589 } 801 1590 802 1591 /**  * 803 1592 * @brief addEdge 804 1593 **  */ 805 void addEdge(const Vertex u, const Vertex v, PabloAST * const value = nullptr) {1594 bool addEdge(const Vertex u, const Vertex v, const OperandIndex index = 0) { 806 1595 const auto typeId = getType(v); 807 1596 if (isAssociative(typeId)) { 808 for ( auto e : make_iterator_range(in_edges(u, G))) {809 if (LLVM_UNLIKELY( source(e, G) == u)) {1597 for (const auto e : make_iterator_range(out_edges(u, G))) { 1598 if (LLVM_UNLIKELY(target(e, G) == v)) { 810 1599 if (LLVM_LIKELY(isDistributive(typeId))) { 811 G[e] = std::max(G[e], value);1600 G[e] = std::max(G[e], index); 812 1601 } else { 813 1602 remove_edge(e, G); 814 1603 } 815 return; 816 } 817 } 818 } 819 boost::add_edge(u, v, value, G); 820 } 1604 return false; 1605 } 1606 } 1607 } 1608 boost::add_edge(u, v, index, G); 1609 return true; 1610 } 1611 1612 #ifndef NDEBUG 1613 /**  * 1614 * @brief hasValidOperandIndicies 1615 **  */ 1616 bool hasValidOperandIndicies(const Vertex u) { 1617 if (isLive(u)) { 1618 const auto n = in_degree(u, G); 1619 const auto typeId = getType(u); 1620 if (LLVM_UNLIKELY(n == 0)) { 1621 if (LLVM_LIKELY(isAssociative(typeId)  isNullary(typeId))) { 1622 return true; 1623 } 1624 errs() << u << " cannot be nullary " << (int)typeId << "\n"; 1625 return false; 1626 } else if (isAssociative(typeId)) { 1627 Vertex V[n]; 1628 unsigned i = 0; 1629 for (auto e : make_iterator_range(in_edges(u, G))) { 1630 V[i++] = source(e, G); 1631 } 1632 std::sort(V, V + n); 1633 for (unsigned i = 1; i != n; ++i) { 1634 if (LLVM_UNLIKELY(V[i  1] == V[i])) { 1635 errs() << u << " has duplicate operands " << V[i] << "\n"; 1636 return false; 1637 } 1638 } 1639 } else if (requiredOperands(typeId) == n) { 1640 bool used[n] = { false }; 1641 for (auto e : make_iterator_range(in_edges(u, G))) { 1642 const auto i = G[e]; 1643 if (LLVM_UNLIKELY(i >= n)) { 1644 errs() << u << " has operand index " << i << " exceeds in degree " << n << "\n"; 1645 return false; 1646 } else if (LLVM_UNLIKELY(used[i])) { 1647 errs() << u << " has duplicate operand indicies " << i << "\n"; 1648 return false; 1649 } 1650 used[i] = true; 1651 } 1652 } else { 1653 errs() << u << " has " << n << " operands but requires " << requiredOperands(typeId) << "\n"; 1654 return false; 1655 } 1656 } 1657 for (auto e : make_iterator_range(in_edges(u, G))) { 1658 const auto v = source(e, G); 1659 if (!isLive(v)) { 1660 errs() << u << " has dead operand " << v << "\n"; 1661 return false; 1662 } 1663 } 1664 return true; 1665 } 1666 1667 static unsigned requiredOperands(const TypeId typeId) { 1668 switch (typeId) { 1669 case TypeId::Not: 1670 case TypeId::InFile: 1671 case TypeId::AtEOF: 1672 case TypeId::Count: 1673 case TypeId::If: 1674 case TypeId::While: 1675 return 1; 1676 case TypeId::Sel: 1677 llvm_unreachable("impossible"); 1678 default: 1679 return 2; 1680 } 1681 } 1682 #endif 821 1683 822 1684 /**  * … … 824 1686 **  */ 825 1687 void removeVertex(const Vertex u) { 826 clear_vertex(u, G); 827 setType(u, TypeId::Var); 1688 #ifdef PRINT_DEBUG 1689 errs() << "removing " << u << "\n"; 1690 #endif 1691 assert (!isImmutable(getType(u))); 1692 assert (isLive(u)); 1693 setDead(u); 1694 clear_out_edges(u, G); 1695 } 1696 1697 /**  * 1698 * @brief remapVertex 1699 **  */ 1700 void remapVertex(const Vertex u, const Vertex v) { 1701 #ifdef PRINT_DEBUG 1702 errs() << "remapping " << u << " > " << v << "\n"; 1703 #endif 1704 assert (u != v); 1705 assert (isLive(v)); 1706 for (auto e : make_iterator_range(out_edges(u, G))) { 1707 addEdge(v, target(e, G), G[e]); 1708 } 1709 removeVertex(u); 1710 } 1711 1712 /**  * 1713 * @brief findVertex 1714 **  */ 1715 Vertex findVertex(const PabloAST * const expr) const { 1716 assert (expr); 1717 const auto f = M.find(expr); 1718 assert (f != M.end()); 1719 return f>second; 828 1720 } 829 1721 … … 834 1726 inline bool intersects(Type & A, Type & B) { 835 1727 auto first1 = A.begin(), last1 = A.end(); 1728 assert (std::is_sorted(first1, last1)); 836 1729 auto first2 = B.begin(), last2 = B.end(); 1730 assert (std::is_sorted(first2, last2)); 837 1731 while (first1 != last1 && first2 != last2) { 838 1732 if (*first1 < *first2) { … … 847 1741 } 848 1742 849 TypeId getType(const Vertex u) { 1743 TypeId getType(const Vertex u) const { 1744 assert (u < num_vertices(G)); 850 1745 return std::get<1>(G[u]); 851 1746 } 852 1747 853 1748 void setType(const Vertex u, const TypeId typeId) { 1749 assert (u < num_vertices(G)); 854 1750 std::get<1>(G[u]) = typeId; 855 1751 } 856 1752 1753 PabloAST * getValue(const Vertex u) const { 1754 assert (u < num_vertices(G)); 1755 return std::get<0>(G[u]); 1756 } 1757 1758 void setValue(const Vertex u, PabloAST * const value) { 1759 assert (u < num_vertices(G)); 1760 std::get<0>(G[u]) = value; 1761 } 1762 1763 bool isLive(const Vertex u) const { 1764 return getState(u) != State::Dead; 1765 } 1766 1767 void setDead(const Vertex u) { 1768 setState(u, State::Dead); 1769 } 1770 1771 void setUnmodified(const Vertex u) { 1772 setState(u, State::Live); 1773 } 1774 1775 bool isModified(const Vertex u) const { 1776 return getState(u) == State::Modified; 1777 } 1778 1779 void setModified(const Vertex u) { 1780 assert(isAssociative(getType(u))  getType(u) == TypeId::Not); 1781 setState(u, State::Modified); 1782 } 1783 1784 State getState(const Vertex u) const { 1785 assert (u < num_vertices(G)); 1786 return std::get<2>(G[u]); 1787 } 1788 1789 void setState(const Vertex u, const State value) { 1790 assert (u < num_vertices(G)); 1791 std::get<2>(G[u]) = value; 1792 } 1793 1794 UsageTime getLastUsageTime(const Vertex u) const { 1795 assert (u < num_vertices(G)); 1796 return std::get<3>(G[u]); 1797 } 1798 1799 void setLastUsageTime(const Vertex u, const UsageTime time) { 1800 assert (u < num_vertices(G)); 1801 std::get<3>(G[u]) = time; 1802 } 1803 857 1804 static bool isIdentityRelation(const TypeId a, const TypeId b) { 1805 assert (isConstant(a) && isDistributive(b)); 858 1806 return !((a == TypeId::Zeroes) ^ (b == TypeId::Or)); 859 1807 } … … 863 1811 } 864 1812 1813 static bool isRegenerable(const TypeId typeId) { 1814 return (isConstant(typeId)  isAssociative(typeId)  typeId == TypeId::Not); 1815 } 1816 1817 static bool isAssociative(const PabloAST * const expr) { 1818 return isAssociative(expr>getClassTypeId()); 1819 } 1820 1821 static bool isConstant(const TypeId typeId) { 1822 return typeId == TypeId::Zeroes  typeId == TypeId::Ones; 1823 } 1824 1825 static bool isLiteral(const TypeId typeId) { 1826 return typeId == TypeId::Integer  typeId == TypeId::Var; 1827 } 1828 865 1829 static bool isDistributive(const TypeId typeId) { 866 1830 return (typeId == TypeId::And  typeId == TypeId::Or); … … 868 1832 869 1833 static bool isImmutable(const TypeId typeId) { 870 return (typeId == TypeId::Var  typeId == TypeId::Assign  typeId == TypeId::Extract); 1834 switch (typeId) { 1835 case TypeId::Extract: case TypeId::Assign: case TypeId::If: case TypeId::While: 1836 return true; 1837 default: 1838 return isLiteral(typeId); 1839 } 1840 } 1841 1842 static bool isNullary(const TypeId typeId) { 1843 return isConstant(typeId)  isLiteral(typeId); 871 1844 } 872 1845 … … 876 1849 } 877 1850 1851 Vertex first_source(const std::pair<in_edge_iterator, in_edge_iterator> & e) const { 1852 return source(*std::get<0>(e), G); 1853 } 1854 1855 bool inCurrentScope(const PabloAST * const expr, const PabloBlock * const scope) { 1856 return isa<Statement>(expr) && cast<Statement>(expr)>getParent() == scope; 1857 } 1858 878 1859 private: 879 1860 880 1861 Graph G; 881 flat_map<pablo::PabloAST *, Vertex> M; 882 VertexSet D; 883 VertexSet L; 1862 flat_map<const pablo::PabloAST *, Vertex> M; 1863 1864 Sequence ordering; 1865 1866 DistributionGraph Gd; 1867 flat_map<Vertex, DistributionVertex> Md; 1868 1869 Sequence D; 1870 1871 std::default_random_engine R; 1872 884 1873 885 1874 }; … … 889 1878 **  */ 890 1879 bool DistributivePass::optimize(PabloKernel * const kernel) { 891 #ifdef NDEBUG 892 report_fatal_error("DistributivePass is unsupported"); 893 #else 1880 894 1881 PassContainer C; 895 1882 C.run(kernel); 1883 #ifndef NDEBUG 1884 PabloVerifier::verify(kernel, "postdistributivepass"); 1885 #endif 1886 Simplifier::optimize(kernel); 896 1887 return true; 897 #endif898 1888 } 899 1889
Note: See TracChangeset
for help on using the changeset viewer.