LLVM API Documentation
00001 //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass performs a hybrid of global value numbering and partial redundancy 00011 // elimination, known as GVN-PRE. It performs partial redundancy elimination on 00012 // values, rather than lexical expressions, allowing a more comprehensive view 00013 // the optimization. It replaces redundant values with uses of earlier 00014 // occurences of the same value. While this is beneficial in that it eliminates 00015 // unneeded computation, it also increases register pressure by creating large 00016 // live ranges, and should be used with caution on platforms that are very 00017 // sensitive to register pressure. 00018 // 00019 // Note that this pass does the value numbering itself, it does not use the 00020 // ValueNumbering analysis passes. 00021 // 00022 //===----------------------------------------------------------------------===// 00023 00024 #define DEBUG_TYPE "gvnpre" 00025 #include "llvm/Value.h" 00026 #include "llvm/Transforms/Scalar.h" 00027 #include "llvm/Instructions.h" 00028 #include "llvm/Function.h" 00029 #include "llvm/DerivedTypes.h" 00030 #include "llvm/Analysis/Dominators.h" 00031 #include "llvm/ADT/BitVector.h" 00032 #include "llvm/ADT/DenseMap.h" 00033 #include "llvm/ADT/DepthFirstIterator.h" 00034 #include "llvm/ADT/PostOrderIterator.h" 00035 #include "llvm/ADT/SmallPtrSet.h" 00036 #include "llvm/ADT/SmallVector.h" 00037 #include "llvm/ADT/Statistic.h" 00038 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 00039 #include "llvm/Support/CFG.h" 00040 #include "llvm/Support/Compiler.h" 00041 #include "llvm/Support/Debug.h" 00042 #include "llvm/Support/ErrorHandling.h" 00043 #include <algorithm> 00044 #include <deque> 00045 #include <map> 00046 using namespace llvm; 00047 00048 //===----------------------------------------------------------------------===// 00049 // ValueTable Class 00050 //===----------------------------------------------------------------------===// 00051 00052 namespace { 00053 00054 /// This class holds the mapping between values and value numbers. It is used 00055 /// as an efficient mechanism to determine the expression-wise equivalence of 00056 /// two values. 00057 00058 struct Expression { 00059 enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL, 00060 UDIV, SDIV, FDIV, UREM, SREM, 00061 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 00062 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 00063 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 00064 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 00065 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 00066 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 00067 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 00068 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 00069 PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY, 00070 TOMBSTONE }; 00071 00072 ExpressionOpcode opcode; 00073 const Type* type; 00074 uint32_t firstVN; 00075 uint32_t secondVN; 00076 uint32_t thirdVN; 00077 SmallVector<uint32_t, 4> varargs; 00078 00079 Expression() { } 00080 explicit Expression(ExpressionOpcode o) : opcode(o) { } 00081 00082 bool operator==(const Expression &other) const { 00083 if (opcode != other.opcode) 00084 return false; 00085 else if (opcode == EMPTY || opcode == TOMBSTONE) 00086 return true; 00087 else if (type != other.type) 00088 return false; 00089 else if (firstVN != other.firstVN) 00090 return false; 00091 else if (secondVN != other.secondVN) 00092 return false; 00093 else if (thirdVN != other.thirdVN) 00094 return false; 00095 else { 00096 if (varargs.size() != other.varargs.size()) 00097 return false; 00098 00099 for (size_t i = 0; i < varargs.size(); ++i) 00100 if (varargs[i] != other.varargs[i]) 00101 return false; 00102 00103 return true; 00104 } 00105 } 00106 00107 bool operator!=(const Expression &other) const { 00108 if (opcode != other.opcode) 00109 return true; 00110 else if (opcode == EMPTY || opcode == TOMBSTONE) 00111 return false; 00112 else if (type != other.type) 00113 return true; 00114 else if (firstVN != other.firstVN) 00115 return true; 00116 else if (secondVN != other.secondVN) 00117 return true; 00118 else if (thirdVN != other.thirdVN) 00119 return true; 00120 else { 00121 if (varargs.size() != other.varargs.size()) 00122 return true; 00123 00124 for (size_t i = 0; i < varargs.size(); ++i) 00125 if (varargs[i] != other.varargs[i]) 00126 return true; 00127 00128 return false; 00129 } 00130 } 00131 }; 00132 00133 } 00134 00135 namespace { 00136 class VISIBILITY_HIDDEN ValueTable { 00137 private: 00138 DenseMap<Value*, uint32_t> valueNumbering; 00139 DenseMap<Expression, uint32_t> expressionNumbering; 00140 00141 uint32_t nextValueNumber; 00142 00143 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 00144 Expression::ExpressionOpcode getOpcode(CmpInst* C); 00145 Expression::ExpressionOpcode getOpcode(CastInst* C); 00146 Expression create_expression(BinaryOperator* BO); 00147 Expression create_expression(CmpInst* C); 00148 Expression create_expression(ShuffleVectorInst* V); 00149 Expression create_expression(ExtractElementInst* C); 00150 Expression create_expression(InsertElementInst* V); 00151 Expression create_expression(SelectInst* V); 00152 Expression create_expression(CastInst* C); 00153 Expression create_expression(GetElementPtrInst* G); 00154 public: 00155 ValueTable() { nextValueNumber = 1; } 00156 uint32_t lookup_or_add(Value* V); 00157 uint32_t lookup(Value* V) const; 00158 void add(Value* V, uint32_t num); 00159 void clear(); 00160 void erase(Value* v); 00161 unsigned size(); 00162 }; 00163 } 00164 00165 namespace llvm { 00166 template <> struct DenseMapInfo<Expression> { 00167 static inline Expression getEmptyKey() { 00168 return Expression(Expression::EMPTY); 00169 } 00170 00171 static inline Expression getTombstoneKey() { 00172 return Expression(Expression::TOMBSTONE); 00173 } 00174 00175 static unsigned getHashValue(const Expression e) { 00176 unsigned hash = e.opcode; 00177 00178 hash = e.firstVN + hash * 37; 00179 hash = e.secondVN + hash * 37; 00180 hash = e.thirdVN + hash * 37; 00181 00182 hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 00183 (unsigned)((uintptr_t)e.type >> 9)) + 00184 hash * 37; 00185 00186 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 00187 E = e.varargs.end(); I != E; ++I) 00188 hash = *I + hash * 37; 00189 00190 return hash; 00191 } 00192 static bool isEqual(const Expression &LHS, const Expression &RHS) { 00193 return LHS == RHS; 00194 } 00195 static bool isPod() { return true; } 00196 }; 00197 } 00198 00199 //===----------------------------------------------------------------------===// 00200 // ValueTable Internal Functions 00201 //===----------------------------------------------------------------------===// 00202 Expression::ExpressionOpcode 00203 ValueTable::getOpcode(BinaryOperator* BO) { 00204 switch(BO->getOpcode()) { 00205 case Instruction::Add: 00206 return Expression::ADD; 00207 case Instruction::FAdd: 00208 return Expression::FADD; 00209 case Instruction::Sub: 00210 return Expression::SUB; 00211 case Instruction::FSub: 00212 return Expression::FSUB; 00213 case Instruction::Mul: 00214 return Expression::MUL; 00215 case Instruction::FMul: 00216 return Expression::FMUL; 00217 case Instruction::UDiv: 00218 return Expression::UDIV; 00219 case Instruction::SDiv: 00220 return Expression::SDIV; 00221 case Instruction::FDiv: 00222 return Expression::FDIV; 00223 case Instruction::URem: 00224 return Expression::UREM; 00225 case Instruction::SRem: 00226 return Expression::SREM; 00227 case Instruction::FRem: 00228 return Expression::FREM; 00229 case Instruction::Shl: 00230 return Expression::SHL; 00231 case Instruction::LShr: 00232 return Expression::LSHR; 00233 case Instruction::AShr: 00234 return Expression::ASHR; 00235 case Instruction::And: 00236 return Expression::AND; 00237 case Instruction::Or: 00238 return Expression::OR; 00239 case Instruction::Xor: 00240 return Expression::XOR; 00241 00242 // THIS SHOULD NEVER HAPPEN 00243 default: 00244 llvm_unreachable("Binary operator with unknown opcode?"); 00245 return Expression::ADD; 00246 } 00247 } 00248 00249 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 00250 if (C->getOpcode() == Instruction::ICmp) { 00251 switch (C->getPredicate()) { 00252 case ICmpInst::ICMP_EQ: 00253 return Expression::ICMPEQ; 00254 case ICmpInst::ICMP_NE: 00255 return Expression::ICMPNE; 00256 case ICmpInst::ICMP_UGT: 00257 return Expression::ICMPUGT; 00258 case ICmpInst::ICMP_UGE: 00259 return Expression::ICMPUGE; 00260 case ICmpInst::ICMP_ULT: 00261 return Expression::ICMPULT; 00262 case ICmpInst::ICMP_ULE: 00263 return Expression::ICMPULE; 00264 case ICmpInst::ICMP_SGT: 00265 return Expression::ICMPSGT; 00266 case ICmpInst::ICMP_SGE: 00267 return Expression::ICMPSGE; 00268 case ICmpInst::ICMP_SLT: 00269 return Expression::ICMPSLT; 00270 case ICmpInst::ICMP_SLE: 00271 return Expression::ICMPSLE; 00272 00273 // THIS SHOULD NEVER HAPPEN 00274 default: 00275 llvm_unreachable("Comparison with unknown predicate?"); 00276 return Expression::ICMPEQ; 00277 } 00278 } else { 00279 switch (C->getPredicate()) { 00280 case FCmpInst::FCMP_OEQ: 00281 return Expression::FCMPOEQ; 00282 case FCmpInst::FCMP_OGT: 00283 return Expression::FCMPOGT; 00284 case FCmpInst::FCMP_OGE: 00285 return Expression::FCMPOGE; 00286 case FCmpInst::FCMP_OLT: 00287 return Expression::FCMPOLT; 00288 case FCmpInst::FCMP_OLE: 00289 return Expression::FCMPOLE; 00290 case FCmpInst::FCMP_ONE: 00291 return Expression::FCMPONE; 00292 case FCmpInst::FCMP_ORD: 00293 return Expression::FCMPORD; 00294 case FCmpInst::FCMP_UNO: 00295 return Expression::FCMPUNO; 00296 case FCmpInst::FCMP_UEQ: 00297 return Expression::FCMPUEQ; 00298 case FCmpInst::FCMP_UGT: 00299 return Expression::FCMPUGT; 00300 case FCmpInst::FCMP_UGE: 00301 return Expression::FCMPUGE; 00302 case FCmpInst::FCMP_ULT: 00303 return Expression::FCMPULT; 00304 case FCmpInst::FCMP_ULE: 00305 return Expression::FCMPULE; 00306 case FCmpInst::FCMP_UNE: 00307 return Expression::FCMPUNE; 00308 00309 // THIS SHOULD NEVER HAPPEN 00310 default: 00311 llvm_unreachable("Comparison with unknown predicate?"); 00312 return Expression::FCMPOEQ; 00313 } 00314 } 00315 } 00316 00317 Expression::ExpressionOpcode 00318 ValueTable::getOpcode(CastInst* C) { 00319 switch(C->getOpcode()) { 00320 case Instruction::Trunc: 00321 return Expression::TRUNC; 00322 case Instruction::ZExt: 00323 return Expression::ZEXT; 00324 case Instruction::SExt: 00325 return Expression::SEXT; 00326 case Instruction::FPToUI: 00327 return Expression::FPTOUI; 00328 case Instruction::FPToSI: 00329 return Expression::FPTOSI; 00330 case Instruction::UIToFP: 00331 return Expression::UITOFP; 00332 case Instruction::SIToFP: 00333 return Expression::SITOFP; 00334 case Instruction::FPTrunc: 00335 return Expression::FPTRUNC; 00336 case Instruction::FPExt: 00337 return Expression::FPEXT; 00338 case Instruction::PtrToInt: 00339 return Expression::PTRTOINT; 00340 case Instruction::IntToPtr: 00341 return Expression::INTTOPTR; 00342 case Instruction::BitCast: 00343 return Expression::BITCAST; 00344 00345 // THIS SHOULD NEVER HAPPEN 00346 default: 00347 llvm_unreachable("Cast operator with unknown opcode?"); 00348 return Expression::BITCAST; 00349 } 00350 } 00351 00352 Expression ValueTable::create_expression(BinaryOperator* BO) { 00353 Expression e; 00354 00355 e.firstVN = lookup_or_add(BO->getOperand(0)); 00356 e.secondVN = lookup_or_add(BO->getOperand(1)); 00357 e.thirdVN = 0; 00358 e.type = BO->getType(); 00359 e.opcode = getOpcode(BO); 00360 00361 return e; 00362 } 00363 00364 Expression ValueTable::create_expression(CmpInst* C) { 00365 Expression e; 00366 00367 e.firstVN = lookup_or_add(C->getOperand(0)); 00368 e.secondVN = lookup_or_add(C->getOperand(1)); 00369 e.thirdVN = 0; 00370 e.type = C->getType(); 00371 e.opcode = getOpcode(C); 00372 00373 return e; 00374 } 00375 00376 Expression ValueTable::create_expression(CastInst* C) { 00377 Expression e; 00378 00379 e.firstVN = lookup_or_add(C->getOperand(0)); 00380 e.secondVN = 0; 00381 e.thirdVN = 0; 00382 e.type = C->getType(); 00383 e.opcode = getOpcode(C); 00384 00385 return e; 00386 } 00387 00388 Expression ValueTable::create_expression(ShuffleVectorInst* S) { 00389 Expression e; 00390 00391 e.firstVN = lookup_or_add(S->getOperand(0)); 00392 e.secondVN = lookup_or_add(S->getOperand(1)); 00393 e.thirdVN = lookup_or_add(S->getOperand(2)); 00394 e.type = S->getType(); 00395 e.opcode = Expression::SHUFFLE; 00396 00397 return e; 00398 } 00399 00400 Expression ValueTable::create_expression(ExtractElementInst* E) { 00401 Expression e; 00402 00403 e.firstVN = lookup_or_add(E->getOperand(0)); 00404 e.secondVN = lookup_or_add(E->getOperand(1)); 00405 e.thirdVN = 0; 00406 e.type = E->getType(); 00407 e.opcode = Expression::EXTRACT; 00408 00409 return e; 00410 } 00411 00412 Expression ValueTable::create_expression(InsertElementInst* I) { 00413 Expression e; 00414 00415 e.firstVN = lookup_or_add(I->getOperand(0)); 00416 e.secondVN = lookup_or_add(I->getOperand(1)); 00417 e.thirdVN = lookup_or_add(I->getOperand(2)); 00418 e.type = I->getType(); 00419 e.opcode = Expression::INSERT; 00420 00421 return e; 00422 } 00423 00424 Expression ValueTable::create_expression(SelectInst* I) { 00425 Expression e; 00426 00427 e.firstVN = lookup_or_add(I->getCondition()); 00428 e.secondVN = lookup_or_add(I->getTrueValue()); 00429 e.thirdVN = lookup_or_add(I->getFalseValue()); 00430 e.type = I->getType(); 00431 e.opcode = Expression::SELECT; 00432 00433 return e; 00434 } 00435 00436 Expression ValueTable::create_expression(GetElementPtrInst* G) { 00437 Expression e; 00438 00439 e.firstVN = lookup_or_add(G->getPointerOperand()); 00440 e.secondVN = 0; 00441 e.thirdVN = 0; 00442 e.type = G->getType(); 00443 e.opcode = Expression::GEP; 00444 00445 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 00446 I != E; ++I) 00447 e.varargs.push_back(lookup_or_add(*I)); 00448 00449 return e; 00450 } 00451 00452 //===----------------------------------------------------------------------===// 00453 // ValueTable External Functions 00454 //===----------------------------------------------------------------------===// 00455 00456 /// lookup_or_add - Returns the value number for the specified value, assigning 00457 /// it a new number if it did not have one before. 00458 uint32_t ValueTable::lookup_or_add(Value* V) { 00459 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 00460 if (VI != valueNumbering.end()) 00461 return VI->second; 00462 00463 00464 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 00465 Expression e = create_expression(BO); 00466 00467 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00468 if (EI != expressionNumbering.end()) { 00469 valueNumbering.insert(std::make_pair(V, EI->second)); 00470 return EI->second; 00471 } else { 00472 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00473 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00474 00475 return nextValueNumber++; 00476 } 00477 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 00478 Expression e = create_expression(C); 00479 00480 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00481 if (EI != expressionNumbering.end()) { 00482 valueNumbering.insert(std::make_pair(V, EI->second)); 00483 return EI->second; 00484 } else { 00485 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00486 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00487 00488 return nextValueNumber++; 00489 } 00490 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 00491 Expression e = create_expression(U); 00492 00493 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00494 if (EI != expressionNumbering.end()) { 00495 valueNumbering.insert(std::make_pair(V, EI->second)); 00496 return EI->second; 00497 } else { 00498 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00499 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00500 00501 return nextValueNumber++; 00502 } 00503 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 00504 Expression e = create_expression(U); 00505 00506 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00507 if (EI != expressionNumbering.end()) { 00508 valueNumbering.insert(std::make_pair(V, EI->second)); 00509 return EI->second; 00510 } else { 00511 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00512 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00513 00514 return nextValueNumber++; 00515 } 00516 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 00517 Expression e = create_expression(U); 00518 00519 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00520 if (EI != expressionNumbering.end()) { 00521 valueNumbering.insert(std::make_pair(V, EI->second)); 00522 return EI->second; 00523 } else { 00524 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00525 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00526 00527 return nextValueNumber++; 00528 } 00529 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 00530 Expression e = create_expression(U); 00531 00532 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00533 if (EI != expressionNumbering.end()) { 00534 valueNumbering.insert(std::make_pair(V, EI->second)); 00535 return EI->second; 00536 } else { 00537 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00538 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00539 00540 return nextValueNumber++; 00541 } 00542 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 00543 Expression e = create_expression(U); 00544 00545 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00546 if (EI != expressionNumbering.end()) { 00547 valueNumbering.insert(std::make_pair(V, EI->second)); 00548 return EI->second; 00549 } else { 00550 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00551 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00552 00553 return nextValueNumber++; 00554 } 00555 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 00556 Expression e = create_expression(U); 00557 00558 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00559 if (EI != expressionNumbering.end()) { 00560 valueNumbering.insert(std::make_pair(V, EI->second)); 00561 return EI->second; 00562 } else { 00563 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00564 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00565 00566 return nextValueNumber++; 00567 } 00568 } else { 00569 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00570 return nextValueNumber++; 00571 } 00572 } 00573 00574 /// lookup - Returns the value number of the specified value. Fails if 00575 /// the value has not yet been numbered. 00576 uint32_t ValueTable::lookup(Value* V) const { 00577 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 00578 if (VI != valueNumbering.end()) 00579 return VI->second; 00580 else 00581 llvm_unreachable("Value not numbered?"); 00582 00583 return 0; 00584 } 00585 00586 /// add - Add the specified value with the given value number, removing 00587 /// its old number, if any 00588 void ValueTable::add(Value* V, uint32_t num) { 00589 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 00590 if (VI != valueNumbering.end()) 00591 valueNumbering.erase(VI); 00592 valueNumbering.insert(std::make_pair(V, num)); 00593 } 00594 00595 /// clear - Remove all entries from the ValueTable 00596 void ValueTable::clear() { 00597 valueNumbering.clear(); 00598 expressionNumbering.clear(); 00599 nextValueNumber = 1; 00600 } 00601 00602 /// erase - Remove a value from the value numbering 00603 void ValueTable::erase(Value* V) { 00604 valueNumbering.erase(V); 00605 } 00606 00607 /// size - Return the number of assigned value numbers 00608 unsigned ValueTable::size() { 00609 // NOTE: zero is never assigned 00610 return nextValueNumber; 00611 } 00612 00613 namespace { 00614 00615 //===----------------------------------------------------------------------===// 00616 // ValueNumberedSet Class 00617 //===----------------------------------------------------------------------===// 00618 00619 class ValueNumberedSet { 00620 private: 00621 SmallPtrSet<Value*, 8> contents; 00622 BitVector numbers; 00623 public: 00624 ValueNumberedSet() { numbers.resize(1); } 00625 ValueNumberedSet(const ValueNumberedSet& other) { 00626 numbers = other.numbers; 00627 contents = other.contents; 00628 } 00629 00630 typedef SmallPtrSet<Value*, 8>::iterator iterator; 00631 00632 iterator begin() { return contents.begin(); } 00633 iterator end() { return contents.end(); } 00634 00635 bool insert(Value* v) { return contents.insert(v); } 00636 void insert(iterator I, iterator E) { contents.insert(I, E); } 00637 void erase(Value* v) { contents.erase(v); } 00638 unsigned count(Value* v) { return contents.count(v); } 00639 size_t size() { return contents.size(); } 00640 00641 void set(unsigned i) { 00642 if (i >= numbers.size()) 00643 numbers.resize(i+1); 00644 00645 numbers.set(i); 00646 } 00647 00648 void operator=(const ValueNumberedSet& other) { 00649 contents = other.contents; 00650 numbers = other.numbers; 00651 } 00652 00653 void reset(unsigned i) { 00654 if (i < numbers.size()) 00655 numbers.reset(i); 00656 } 00657 00658 bool test(unsigned i) { 00659 if (i >= numbers.size()) 00660 return false; 00661 00662 return numbers.test(i); 00663 } 00664 00665 void clear() { 00666 contents.clear(); 00667 numbers.clear(); 00668 } 00669 }; 00670 00671 } 00672 00673 //===----------------------------------------------------------------------===// 00674 // GVNPRE Pass 00675 //===----------------------------------------------------------------------===// 00676 00677 namespace { 00678 00679 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass { 00680 bool runOnFunction(Function &F); 00681 public: 00682 static char ID; // Pass identification, replacement for typeid 00683 GVNPRE() : FunctionPass(&ID) {} 00684 00685 private: 00686 ValueTable VN; 00687 SmallVector<Instruction*, 8> createdExpressions; 00688 00689 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 00690 DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn; 00691 DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis; 00692 00693 // This transformation requires dominator postdominator info 00694 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00695 AU.setPreservesCFG(); 00696 AU.addRequiredID(BreakCriticalEdgesID); 00697 AU.addRequired<UnifyFunctionExitNodes>(); 00698 AU.addRequired<DominatorTree>(); 00699 } 00700 00701 // Helper fuctions 00702 // FIXME: eliminate or document these better 00703 void dump(ValueNumberedSet& s) const ; 00704 void clean(ValueNumberedSet& set) ; 00705 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 00706 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ; 00707 void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred, 00708 BasicBlock* succ, ValueNumberedSet& out) ; 00709 00710 void topo_sort(ValueNumberedSet& set, 00711 SmallVector<Value*, 8>& vec) ; 00712 00713 void cleanup() ; 00714 bool elimination() ; 00715 00716 void val_insert(ValueNumberedSet& s, Value* v) ; 00717 void val_replace(ValueNumberedSet& s, Value* v) ; 00718 bool dependsOnInvoke(Value* V) ; 00719 void buildsets_availout(BasicBlock::iterator I, 00720 ValueNumberedSet& currAvail, 00721 ValueNumberedSet& currPhis, 00722 ValueNumberedSet& currExps, 00723 SmallPtrSet<Value*, 16>& currTemps); 00724 bool buildsets_anticout(BasicBlock* BB, 00725 ValueNumberedSet& anticOut, 00726 SmallPtrSet<BasicBlock*, 8>& visited); 00727 unsigned buildsets_anticin(BasicBlock* BB, 00728 ValueNumberedSet& anticOut, 00729 ValueNumberedSet& currExps, 00730 SmallPtrSet<Value*, 16>& currTemps, 00731 SmallPtrSet<BasicBlock*, 8>& visited); 00732 void buildsets(Function& F) ; 00733 00734 void insertion_pre(Value* e, BasicBlock* BB, 00735 DenseMap<BasicBlock*, Value*>& avail, 00736 std::map<BasicBlock*,ValueNumberedSet>& new_set); 00737 unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList, 00738 df_iterator<DomTreeNode*>& D, 00739 std::map<BasicBlock*, ValueNumberedSet>& new_set); 00740 bool insertion(Function& F) ; 00741 00742 }; 00743 00744 char GVNPRE::ID = 0; 00745 00746 } 00747 00748 // createGVNPREPass - The public interface to this file... 00749 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); } 00750 00751 static RegisterPass<GVNPRE> X("gvnpre", 00752 "Global Value Numbering/Partial Redundancy Elimination"); 00753 00754 00755 STATISTIC(NumInsertedVals, "Number of values inserted"); 00756 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted"); 00757 STATISTIC(NumEliminated, "Number of redundant instructions eliminated"); 00758 00759 /// find_leader - Given a set and a value number, return the first 00760 /// element of the set with that value number, or 0 if no such element 00761 /// is present 00762 Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) { 00763 if (!vals.test(v)) 00764 return 0; 00765 00766 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 00767 I != E; ++I) 00768 if (v == VN.lookup(*I)) 00769 return *I; 00770 00771 llvm_unreachable("No leader found, but present bit is set?"); 00772 return 0; 00773 } 00774 00775 /// val_insert - Insert a value into a set only if there is not a value 00776 /// with the same value number already in the set 00777 void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) { 00778 uint32_t num = VN.lookup(v); 00779 if (!s.test(num)) 00780 s.insert(v); 00781 } 00782 00783 /// val_replace - Insert a value into a set, replacing any values already in 00784 /// the set that have the same value number 00785 void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) { 00786 if (s.count(v)) return; 00787 00788 uint32_t num = VN.lookup(v); 00789 Value* leader = find_leader(s, num); 00790 if (leader != 0) 00791 s.erase(leader); 00792 s.insert(v); 00793 s.set(num); 00794 } 00795 00796 /// phi_translate - Given a value, its parent block, and a predecessor of its 00797 /// parent, translate the value into legal for the predecessor block. This 00798 /// means translating its operands (and recursively, their operands) through 00799 /// any phi nodes in the parent into values available in the predecessor 00800 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) { 00801 if (V == 0) 00802 return 0; 00803 00804 LLVMContext &Context = V->getContext(); 00805 00806 // Unary Operations 00807 if (CastInst* U = dyn_cast<CastInst>(V)) { 00808 Value* newOp1 = 0; 00809 if (isa<Instruction>(U->getOperand(0))) 00810 newOp1 = phi_translate(U->getOperand(0), pred, succ); 00811 else 00812 newOp1 = U->getOperand(0); 00813 00814 if (newOp1 == 0) 00815 return 0; 00816 00817 if (newOp1 != U->getOperand(0)) { 00818 Instruction* newVal = 0; 00819 if (CastInst* C = dyn_cast<CastInst>(U)) 00820 newVal = CastInst::Create(C->getOpcode(), 00821 newOp1, C->getType(), 00822 C->getName()+".expr"); 00823 00824 uint32_t v = VN.lookup_or_add(newVal); 00825 00826 Value* leader = find_leader(availableOut[pred], v); 00827 if (leader == 0) { 00828 createdExpressions.push_back(newVal); 00829 return newVal; 00830 } else { 00831 VN.erase(newVal); 00832 delete newVal; 00833 return leader; 00834 } 00835 } 00836 00837 // Binary Operations 00838 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) || 00839 isa<ExtractElementInst>(V)) { 00840 User* U = cast<User>(V); 00841 00842 Value* newOp1 = 0; 00843 if (isa<Instruction>(U->getOperand(0))) 00844 newOp1 = phi_translate(U->getOperand(0), pred, succ); 00845 else 00846 newOp1 = U->getOperand(0); 00847 00848 if (newOp1 == 0) 00849 return 0; 00850 00851 Value* newOp2 = 0; 00852 if (isa<Instruction>(U->getOperand(1))) 00853 newOp2 = phi_translate(U->getOperand(1), pred, succ); 00854 else 00855 newOp2 = U->getOperand(1); 00856 00857 if (newOp2 == 0) 00858 return 0; 00859 00860 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) { 00861 Instruction* newVal = 0; 00862 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U)) 00863 newVal = BinaryOperator::Create(BO->getOpcode(), 00864 newOp1, newOp2, 00865 BO->getName()+".expr"); 00866 else if (CmpInst* C = dyn_cast<CmpInst>(U)) 00867 newVal = CmpInst::Create(Context, C->getOpcode(), 00868 C->getPredicate(), 00869 newOp1, newOp2, 00870 C->getName()+".expr"); 00871 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U)) 00872 newVal = ExtractElementInst::Create(newOp1, newOp2, 00873 E->getName()+".expr"); 00874 00875 uint32_t v = VN.lookup_or_add(newVal); 00876 00877 Value* leader = find_leader(availableOut[pred], v); 00878 if (leader == 0) { 00879 createdExpressions.push_back(newVal); 00880 return newVal; 00881 } else { 00882 VN.erase(newVal); 00883 delete newVal; 00884 return leader; 00885 } 00886 } 00887 00888 // Ternary Operations 00889 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) || 00890 isa<SelectInst>(V)) { 00891 User* U = cast<User>(V); 00892 00893 Value* newOp1 = 0; 00894 if (isa<Instruction>(U->getOperand(0))) 00895 newOp1 = phi_translate(U->getOperand(0), pred, succ); 00896 else 00897 newOp1 = U->getOperand(0); 00898 00899 if (newOp1 == 0) 00900 return 0; 00901 00902 Value* newOp2 = 0; 00903 if (isa<Instruction>(U->getOperand(1))) 00904 newOp2 = phi_translate(U->getOperand(1), pred, succ); 00905 else 00906 newOp2 = U->getOperand(1); 00907 00908 if (newOp2 == 0) 00909 return 0; 00910 00911 Value* newOp3 = 0; 00912 if (isa<Instruction>(U->getOperand(2))) 00913 newOp3 = phi_translate(U->getOperand(2), pred, succ); 00914 else 00915 newOp3 = U->getOperand(2); 00916 00917 if (newOp3 == 0) 00918 return 0; 00919 00920 if (newOp1 != U->getOperand(0) || 00921 newOp2 != U->getOperand(1) || 00922 newOp3 != U->getOperand(2)) { 00923 Instruction* newVal = 0; 00924 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U)) 00925 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3, 00926 S->getName() + ".expr"); 00927 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U)) 00928 newVal = InsertElementInst::Create(newOp1, newOp2, newOp3, 00929 I->getName() + ".expr"); 00930 else if (SelectInst* I = dyn_cast<SelectInst>(U)) 00931 newVal = SelectInst::Create(newOp1, newOp2, newOp3, 00932 I->getName() + ".expr"); 00933 00934 uint32_t v = VN.lookup_or_add(newVal); 00935 00936 Value* leader = find_leader(availableOut[pred], v); 00937 if (leader == 0) { 00938 createdExpressions.push_back(newVal); 00939 return newVal; 00940 } else { 00941 VN.erase(newVal); 00942 delete newVal; 00943 return leader; 00944 } 00945 } 00946 00947 // Varargs operators 00948 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 00949 Value* newOp1 = 0; 00950 if (isa<Instruction>(U->getPointerOperand())) 00951 newOp1 = phi_translate(U->getPointerOperand(), pred, succ); 00952 else 00953 newOp1 = U->getPointerOperand(); 00954 00955 if (newOp1 == 0) 00956 return 0; 00957 00958 bool changed_idx = false; 00959 SmallVector<Value*, 4> newIdx; 00960 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end(); 00961 I != E; ++I) 00962 if (isa<Instruction>(*I)) { 00963 Value* newVal = phi_translate(*I, pred, succ); 00964 newIdx.push_back(newVal); 00965 if (newVal != *I) 00966 changed_idx = true; 00967 } else { 00968 newIdx.push_back(*I); 00969 } 00970 00971 if (newOp1 != U->getPointerOperand() || changed_idx) { 00972 Instruction* newVal = 00973 GetElementPtrInst::Create(newOp1, 00974 newIdx.begin(), newIdx.end(), 00975 U->getName()+".expr"); 00976 00977 uint32_t v = VN.lookup_or_add(newVal); 00978 00979 Value* leader = find_leader(availableOut[pred], v); 00980 if (leader == 0) { 00981 createdExpressions.push_back(newVal); 00982 return newVal; 00983 } else { 00984 VN.erase(newVal); 00985 delete newVal; 00986 return leader; 00987 } 00988 } 00989 00990 // PHI Nodes 00991 } else if (PHINode* P = dyn_cast<PHINode>(V)) { 00992 if (P->getParent() == succ) 00993 return P->getIncomingValueForBlock(pred); 00994 } 00995 00996 return V; 00997 } 00998 00999 /// phi_translate_set - Perform phi translation on every element of a set 01000 void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn, 01001 BasicBlock* pred, BasicBlock* succ, 01002 ValueNumberedSet& out) { 01003 for (ValueNumberedSet::iterator I = anticIn.begin(), 01004 E = anticIn.end(); I != E; ++I) { 01005 Value* V = phi_translate(*I, pred, succ); 01006 if (V != 0 && !out.test(VN.lookup_or_add(V))) { 01007 out.insert(V); 01008 out.set(VN.lookup(V)); 01009 } 01010 } 01011 } 01012 01013 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of 01014 /// whose inputs is an invoke instruction. If this is true, we cannot safely 01015 /// PRE the instruction or anything that depends on it. 01016 bool GVNPRE::dependsOnInvoke(Value* V) { 01017 if (PHINode* p = dyn_cast<PHINode>(V)) { 01018 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I) 01019 if (isa<InvokeInst>(*I)) 01020 return true; 01021 return false; 01022 } else { 01023 return false; 01024 } 01025 } 01026 01027 /// clean - Remove all non-opaque values from the set whose operands are not 01028 /// themselves in the set, as well as all values that depend on invokes (see 01029 /// above) 01030 void GVNPRE::clean(ValueNumberedSet& set) { 01031 SmallVector<Value*, 8> worklist; 01032 worklist.reserve(set.size()); 01033 topo_sort(set, worklist); 01034 01035 for (unsigned i = 0; i < worklist.size(); ++i) { 01036 Value* v = worklist[i]; 01037 01038 // Handle unary ops 01039 if (CastInst* U = dyn_cast<CastInst>(v)) { 01040 bool lhsValid = !isa<Instruction>(U->getOperand(0)); 01041 lhsValid |= set.test(VN.lookup(U->getOperand(0))); 01042 if (lhsValid) 01043 lhsValid = !dependsOnInvoke(U->getOperand(0)); 01044 01045 if (!lhsValid) { 01046 set.erase(U); 01047 set.reset(VN.lookup(U)); 01048 } 01049 01050 // Handle binary ops 01051 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) || 01052 isa<ExtractElementInst>(v)) { 01053 User* U = cast<User>(v); 01054 01055 bool lhsValid = !isa<Instruction>(U->getOperand(0)); 01056 lhsValid |= set.test(VN.lookup(U->getOperand(0))); 01057 if (lhsValid) 01058 lhsValid = !dependsOnInvoke(U->getOperand(0)); 01059 01060 bool rhsValid = !isa<Instruction>(U->getOperand(1)); 01061 rhsValid |= set.test(VN.lookup(U->getOperand(1))); 01062 if (rhsValid) 01063 rhsValid = !dependsOnInvoke(U->getOperand(1)); 01064 01065 if (!lhsValid || !rhsValid) { 01066 set.erase(U); 01067 set.reset(VN.lookup(U)); 01068 } 01069 01070 // Handle ternary ops 01071 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) || 01072 isa<SelectInst>(v)) { 01073 User* U = cast<User>(v); 01074 01075 bool lhsValid = !isa<Instruction>(U->getOperand(0)); 01076 lhsValid |= set.test(VN.lookup(U->getOperand(0))); 01077 if (lhsValid) 01078 lhsValid = !dependsOnInvoke(U->getOperand(0)); 01079 01080 bool rhsValid = !isa<Instruction>(U->getOperand(1)); 01081 rhsValid |= set.test(VN.lookup(U->getOperand(1))); 01082 if (rhsValid) 01083 rhsValid = !dependsOnInvoke(U->getOperand(1)); 01084 01085 bool thirdValid = !isa<Instruction>(U->getOperand(2)); 01086 thirdValid |= set.test(VN.lookup(U->getOperand(2))); 01087 if (thirdValid) 01088 thirdValid = !dependsOnInvoke(U->getOperand(2)); 01089 01090 if (!lhsValid || !rhsValid || !thirdValid) { 01091 set.erase(U); 01092 set.reset(VN.lookup(U)); 01093 } 01094 01095 // Handle varargs ops 01096 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) { 01097 bool ptrValid = !isa<Instruction>(U->getPointerOperand()); 01098 ptrValid |= set.test(VN.lookup(U->getPointerOperand())); 01099 if (ptrValid) 01100 ptrValid = !dependsOnInvoke(U->getPointerOperand()); 01101 01102 bool varValid = true; 01103 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end(); 01104 I != E; ++I) 01105 if (varValid) { 01106 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I)); 01107 varValid &= !dependsOnInvoke(*I); 01108 } 01109 01110 if (!ptrValid || !varValid) { 01111 set.erase(U); 01112 set.reset(VN.lookup(U)); 01113 } 01114 } 01115 } 01116 } 01117 01118 /// topo_sort - Given a set of values, sort them by topological 01119 /// order into the provided vector. 01120 void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) { 01121 SmallPtrSet<Value*, 16> visited; 01122 SmallVector<Value*, 8> stack; 01123 for (ValueNumberedSet::iterator I = set.begin(), E = set.end(); 01124 I != E; ++I) { 01125 if (visited.count(*I) == 0) 01126 stack.push_back(*I); 01127 01128 while (!stack.empty()) { 01129 Value* e = stack.back(); 01130 01131 // Handle unary ops 01132 if (CastInst* U = dyn_cast<CastInst>(e)) { 01133 Value* l = find_leader(set, VN.lookup(U->getOperand(0))); 01134 01135 if (l != 0 && isa<Instruction>(l) && 01136 visited.count(l) == 0) 01137 stack.push_back(l); 01138 else { 01139 vec.push_back(e); 01140 visited.insert(e); 01141 stack.pop_back(); 01142 } 01143 01144 // Handle binary ops 01145 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) || 01146 isa<ExtractElementInst>(e)) { 01147 User* U = cast<User>(e); 01148 Value* l = find_leader(set, VN.lookup(U->getOperand(0))); 01149 Value* r = find_leader(set, VN.lookup(U->getOperand(1))); 01150 01151 if (l != 0 && isa<Instruction>(l) && 01152 visited.count(l) == 0) 01153 stack.push_back(l); 01154 else if (r != 0 && isa<Instruction>(r) && 01155 visited.count(r) == 0) 01156 stack.push_back(r); 01157 else { 01158 vec.push_back(e); 01159 visited.insert(e); 01160 stack.pop_back(); 01161 } 01162 01163 // Handle ternary ops 01164 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) || 01165 isa<SelectInst>(e)) { 01166 User* U = cast<User>(e); 01167 Value* l = find_leader(set, VN.lookup(U->getOperand(0))); 01168 Value* r = find_leader(set, VN.lookup(U->getOperand(1))); 01169 Value* m = find_leader(set, VN.lookup(U->getOperand(2))); 01170 01171 if (l != 0 && isa<Instruction>(l) && 01172 visited.count(l) == 0) 01173 stack.push_back(l); 01174 else if (r != 0 && isa<Instruction>(r) && 01175 visited.count(r) == 0) 01176 stack.push_back(r); 01177 else if (m != 0 && isa<Instruction>(m) && 01178 visited.count(m) == 0) 01179 stack.push_back(m); 01180 else { 01181 vec.push_back(e); 01182 visited.insert(e); 01183 stack.pop_back(); 01184 } 01185 01186 // Handle vararg ops 01187 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) { 01188 Value* p = find_leader(set, VN.lookup(U->getPointerOperand())); 01189 01190 if (p != 0 && isa<Instruction>(p) && 01191 visited.count(p) == 0) 01192 stack.push_back(p); 01193 else { 01194 bool push_va = false; 01195 for (GetElementPtrInst::op_iterator I = U->idx_begin(), 01196 E = U->idx_end(); I != E; ++I) { 01197 Value * v = find_leader(set, VN.lookup(*I)); 01198 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) { 01199 stack.push_back(v); 01200 push_va = true; 01201 } 01202 } 01203 01204 if (!push_va) { 01205 vec.push_back(e); 01206 visited.insert(e); 01207 stack.pop_back(); 01208 } 01209 } 01210 01211 // Handle opaque ops 01212 } else { 01213 visited.insert(e); 01214 vec.push_back(e); 01215 stack.pop_back(); 01216 } 01217 } 01218 01219 stack.clear(); 01220 } 01221 } 01222 01223 /// dump - Dump a set of values to standard error 01224 void GVNPRE::dump(ValueNumberedSet& s) const { 01225 DOUT << "{ "; 01226 for (ValueNumberedSet::iterator I = s.begin(), E = s.end(); 01227 I != E; ++I) { 01228 DOUT << "" << VN.lookup(*I) << ": "; 01229 DEBUG((*I)->dump()); 01230 } 01231 DOUT << "}\n\n"; 01232 } 01233 01234 /// elimination - Phase 3 of the main algorithm. Perform full redundancy 01235 /// elimination by walking the dominator tree and removing any instruction that 01236 /// is dominated by another instruction with the same value number. 01237 bool GVNPRE::elimination() { 01238 bool changed_function = false; 01239 01240 SmallVector<std::pair<Instruction*, Value*>, 8> replace; 01241 SmallVector<Instruction*, 8> erase; 01242 01243 DominatorTree& DT = getAnalysis<DominatorTree>(); 01244 01245 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 01246 E = df_end(DT.getRootNode()); DI != E; ++DI) { 01247 BasicBlock* BB = DI->getBlock(); 01248 01249 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 01250 BI != BE; ++BI) { 01251 01252 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) || 01253 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) || 01254 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) || 01255 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) { 01256 01257 if (availableOut[BB].test(VN.lookup(BI)) && 01258 !availableOut[BB].count(BI)) { 01259 Value *leader = find_leader(availableOut[BB], VN.lookup(BI)); 01260 if (Instruction* Instr = dyn_cast<Instruction>(leader)) 01261 if (Instr->getParent() != 0 && Instr != BI) { 01262 replace.push_back(std::make_pair(BI, leader)); 01263 erase.push_back(BI); 01264 ++NumEliminated; 01265 } 01266 } 01267 } 01268 } 01269 } 01270 01271 while (!replace.empty()) { 01272 std::pair<Instruction*, Value*> rep = replace.back(); 01273 replace.pop_back(); 01274 rep.first->replaceAllUsesWith(rep.second); 01275 changed_function = true; 01276 } 01277 01278 for (SmallVector<Instruction*, 8>::iterator I = erase.begin(), 01279 E = erase.end(); I != E; ++I) 01280 (*I)->eraseFromParent(); 01281 01282 return changed_function; 01283 } 01284 01285 /// cleanup - Delete any extraneous values that were created to represent 01286 /// expressions without leaders. 01287 void GVNPRE::cleanup() { 01288 while (!createdExpressions.empty()) { 01289 Instruction* I = createdExpressions.back(); 01290 createdExpressions.pop_back(); 01291 01292 delete I; 01293 } 01294 } 01295 01296 /// buildsets_availout - When calculating availability, handle an instruction 01297 /// by inserting it into the appropriate sets 01298 void GVNPRE::buildsets_availout(BasicBlock::iterator I, 01299 ValueNumberedSet& currAvail, 01300 ValueNumberedSet& currPhis, 01301 ValueNumberedSet& currExps, 01302 SmallPtrSet<Value*, 16>& currTemps) { 01303 // Handle PHI nodes 01304 if (PHINode* p = dyn_cast<PHINode>(I)) { 01305 unsigned num = VN.lookup_or_add(p); 01306 01307 currPhis.insert(p); 01308 currPhis.set(num); 01309 01310 // Handle unary ops 01311 } else if (CastInst* U = dyn_cast<CastInst>(I)) { 01312 Value* leftValue = U->getOperand(0); 01313 01314 unsigned num = VN.lookup_or_add(U); 01315 01316 if (isa<Instruction>(leftValue)) 01317 if (!currExps.test(VN.lookup(leftValue))) { 01318 currExps.insert(leftValue); 01319 currExps.set(VN.lookup(leftValue)); 01320 } 01321 01322 if (!currExps.test(num)) { 01323 currExps.insert(U); 01324 currExps.set(num); 01325 } 01326 01327 // Handle binary ops 01328 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) || 01329 isa<ExtractElementInst>(I)) { 01330 User* U = cast<User>(I); 01331 Value* leftValue = U->getOperand(0); 01332 Value* rightValue = U->getOperand(1); 01333 01334 unsigned num = VN.lookup_or_add(U); 01335 01336 if (isa<Instruction>(leftValue)) 01337 if (!currExps.test(VN.lookup(leftValue))) { 01338 currExps.insert(leftValue); 01339 currExps.set(VN.lookup(leftValue)); 01340 } 01341 01342 if (isa<Instruction>(rightValue)) 01343 if (!currExps.test(VN.lookup(rightValue))) { 01344 currExps.insert(rightValue); 01345 currExps.set(VN.lookup(rightValue)); 01346 } 01347 01348 if (!currExps.test(num)) { 01349 currExps.insert(U); 01350 currExps.set(num); 01351 } 01352 01353 // Handle ternary ops 01354 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) || 01355 isa<SelectInst>(I)) { 01356 User* U = cast<User>(I); 01357 Value* leftValue = U->getOperand(0); 01358 Value* rightValue = U->getOperand(1); 01359 Value* thirdValue = U->getOperand(2); 01360 01361 VN.lookup_or_add(U); 01362 01363 unsigned num = VN.lookup_or_add(U); 01364 01365 if (isa<Instruction>(leftValue)) 01366 if (!currExps.test(VN.lookup(leftValue))) { 01367 currExps.insert(leftValue); 01368 currExps.set(VN.lookup(leftValue)); 01369 } 01370 if (isa<Instruction>(rightValue)) 01371 if (!currExps.test(VN.lookup(rightValue))) { 01372 currExps.insert(rightValue); 01373 currExps.set(VN.lookup(rightValue)); 01374 } 01375 if (isa<Instruction>(thirdValue)) 01376 if (!currExps.test(VN.lookup(thirdValue))) { 01377 currExps.insert(thirdValue); 01378 currExps.set(VN.lookup(thirdValue)); 01379 } 01380 01381 if (!currExps.test(num)) { 01382 currExps.insert(U); 01383 currExps.set(num); 01384 } 01385 01386 // Handle vararg ops 01387 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) { 01388 Value* ptrValue = U->getPointerOperand(); 01389 01390 VN.lookup_or_add(U); 01391 01392 unsigned num = VN.lookup_or_add(U); 01393 01394 if (isa<Instruction>(ptrValue)) 01395 if (!currExps.test(VN.lookup(ptrValue))) { 01396 currExps.insert(ptrValue); 01397 currExps.set(VN.lookup(ptrValue)); 01398 } 01399 01400 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end(); 01401 OI != OE; ++OI) 01402 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) { 01403 currExps.insert(*OI); 01404 currExps.set(VN.lookup(*OI)); 01405 } 01406 01407 if (!currExps.test(VN.lookup(U))) { 01408 currExps.insert(U); 01409 currExps.set(num); 01410 } 01411 01412 // Handle opaque ops 01413 } else if (!I->isTerminator()){ 01414 VN.lookup_or_add(I); 01415 01416 currTemps.insert(I); 01417 } 01418 01419 if (!I->isTerminator()) 01420 if (!currAvail.test(VN.lookup(I))) { 01421 currAvail.insert(I); 01422 currAvail.set(VN.lookup(I)); 01423 } 01424 } 01425 01426 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT 01427 /// set as a function of the ANTIC_IN set of the block's predecessors 01428 bool GVNPRE::buildsets_anticout(BasicBlock* BB, 01429 ValueNumberedSet& anticOut, 01430 SmallPtrSet<BasicBlock*, 8>& visited) { 01431 if (BB->getTerminator()->getNumSuccessors() == 1) { 01432 if (BB->getTerminator()->getSuccessor(0) != BB && 01433 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) { 01434 return true; 01435 } 01436 else { 01437 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)], 01438 BB, BB->getTerminator()->getSuccessor(0), anticOut); 01439 } 01440 } else if (BB->getTerminator()->getNumSuccessors() > 1) { 01441 BasicBlock* first = BB->getTerminator()->getSuccessor(0); 01442 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(), 01443 E = anticipatedIn[first].end(); I != E; ++I) { 01444 anticOut.insert(*I); 01445 anticOut.set(VN.lookup(*I)); 01446 } 01447 01448 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) { 01449 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i); 01450 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc]; 01451 01452 SmallVector<Value*, 16> temp; 01453 01454 for (ValueNumberedSet::iterator I = anticOut.begin(), 01455 E = anticOut.end(); I != E; ++I) 01456 if (!succAnticIn.test(VN.lookup(*I))) 01457 temp.push_back(*I); 01458 01459 for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end(); 01460 I != E; ++I) { 01461 anticOut.erase(*I); 01462 anticOut.reset(VN.lookup(*I)); 01463 } 01464 } 01465 } 01466 01467 return false; 01468 } 01469 01470 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for 01471 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN 01472 /// sets populated in buildsets_availout 01473 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB, 01474 ValueNumberedSet& anticOut, 01475 ValueNumberedSet& currExps, 01476 SmallPtrSet<Value*, 16>& currTemps, 01477 SmallPtrSet<BasicBlock*, 8>& visited) { 01478 ValueNumberedSet& anticIn = anticipatedIn[BB]; 01479 unsigned old = anticIn.size(); 01480 01481 bool defer = buildsets_anticout(BB, anticOut, visited); 01482 if (defer) 01483 return 0; 01484 01485 anticIn.clear(); 01486 01487 for (ValueNumberedSet::iterator I = anticOut.begin(), 01488 E = anticOut.end(); I != E; ++I) { 01489 anticIn.insert(*I); 01490 anticIn.set(VN.lookup(*I)); 01491 } 01492 for (ValueNumberedSet::iterator I = currExps.begin(), 01493 E = currExps.end(); I != E; ++I) { 01494 if (!anticIn.test(VN.lookup(*I))) { 01495 anticIn.insert(*I); 01496 anticIn.set(VN.lookup(*I)); 01497 } 01498 } 01499 01500 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(), 01501 E = currTemps.end(); I != E; ++I) { 01502 anticIn.erase(*I); 01503 anticIn.reset(VN.lookup(*I)); 01504 } 01505 01506 clean(anticIn); 01507 anticOut.clear(); 01508 01509 if (old != anticIn.size()) 01510 return 2; 01511 else 01512 return 1; 01513 } 01514 01515 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT 01516 /// and the ANTIC_IN sets. 01517 void GVNPRE::buildsets(Function& F) { 01518 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions; 01519 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries; 01520 01521 DominatorTree &DT = getAnalysis<DominatorTree>(); 01522 01523 // Phase 1, Part 1: calculate AVAIL_OUT 01524 01525 // Top-down walk of the dominator tree 01526 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 01527 E = df_end(DT.getRootNode()); DI != E; ++DI) { 01528 01529 // Get the sets to update for this block 01530 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()]; 01531 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()]; 01532 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()]; 01533 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 01534 01535 BasicBlock* BB = DI->getBlock(); 01536 01537 // A block inherits AVAIL_OUT from its dominator 01538 if (DI->getIDom() != 0) 01539 currAvail = availableOut[DI->getIDom()->getBlock()]; 01540 01541 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 01542 BI != BE; ++BI) 01543 buildsets_availout(BI, currAvail, currPhis, currExps, 01544 currTemps); 01545 01546 } 01547 01548 // Phase 1, Part 2: calculate ANTIC_IN 01549 01550 SmallPtrSet<BasicBlock*, 8> visited; 01551 SmallPtrSet<BasicBlock*, 4> block_changed; 01552 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 01553 block_changed.insert(FI); 01554 01555 bool changed = true; 01556 unsigned iterations = 0; 01557 01558 while (changed) { 01559 changed = false; 01560 ValueNumberedSet anticOut; 01561 01562 // Postorder walk of the CFG 01563 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()), 01564 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) { 01565 BasicBlock* BB = *BBI; 01566 01567 if (block_changed.count(BB) != 0) { 01568 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB], 01569 generatedTemporaries[BB], visited); 01570 01571 if (ret == 0) { 01572 changed = true; 01573 continue; 01574 } else { 01575 visited.insert(BB); 01576 01577 if (ret == 2) 01578 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 01579 PI != PE; ++PI) { 01580 block_changed.insert(*PI); 01581 } 01582 else 01583 block_changed.erase(BB); 01584 01585 changed |= (ret == 2); 01586 } 01587 } 01588 } 01589 01590 iterations++; 01591 } 01592 } 01593 01594 /// insertion_pre - When a partial redundancy has been identified, eliminate it 01595 /// by inserting appropriate values into the predecessors and a phi node in 01596 /// the main block 01597 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB, 01598 DenseMap<BasicBlock*, Value*>& avail, 01599 std::map<BasicBlock*, ValueNumberedSet>& new_sets) { 01600 LLVMContext &Context = e->getContext(); 01601 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 01602 Value* e2 = avail[*PI]; 01603 if (!availableOut[*PI].test(VN.lookup(e2))) { 01604 User* U = cast<User>(e2); 01605 01606 Value* s1 = 0; 01607 if (isa<BinaryOperator>(U->getOperand(0)) || 01608 isa<CmpInst>(U->getOperand(0)) || 01609 isa<ShuffleVectorInst>(U->getOperand(0)) || 01610 isa<ExtractElementInst>(U->getOperand(0)) || 01611 isa<InsertElementInst>(U->getOperand(0)) || 01612 isa<SelectInst>(U->getOperand(0)) || 01613 isa<CastInst>(U->getOperand(0)) || 01614 isa<GetElementPtrInst>(U->getOperand(0))) 01615 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0))); 01616 else 01617 s1 = U->getOperand(0); 01618 01619 Value* s2 = 0; 01620 01621 if (isa<BinaryOperator>(U) || 01622 isa<CmpInst>(U) || 01623 isa<ShuffleVectorInst>(U) || 01624 isa<ExtractElementInst>(U) || 01625 isa<InsertElementInst>(U) || 01626 isa<SelectInst>(U)) { 01627 if (isa<BinaryOperator>(U->getOperand(1)) || 01628 isa<CmpInst>(U->getOperand(1)) || 01629 isa<ShuffleVectorInst>(U->getOperand(1)) || 01630 isa<ExtractElementInst>(U->getOperand(1)) || 01631 isa<InsertElementInst>(U->getOperand(1)) || 01632 isa<SelectInst>(U->getOperand(1)) || 01633 isa<CastInst>(U->getOperand(1)) || 01634 isa<GetElementPtrInst>(U->getOperand(1))) { 01635 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1))); 01636 } else { 01637 s2 = U->getOperand(1); 01638 } 01639 } 01640 01641 // Ternary Operators 01642 Value* s3 = 0; 01643 if (isa<ShuffleVectorInst>(U) || 01644 isa<InsertElementInst>(U) || 01645 isa<SelectInst>(U)) { 01646 if (isa<BinaryOperator>(U->getOperand(2)) || 01647 isa<CmpInst>(U->getOperand(2)) || 01648 isa<ShuffleVectorInst>(U->getOperand(2)) || 01649 isa<ExtractElementInst>(U->getOperand(2)) || 01650 isa<InsertElementInst>(U->getOperand(2)) || 01651 isa<SelectInst>(U->getOperand(2)) || 01652 isa<CastInst>(U->getOperand(2)) || 01653 isa<GetElementPtrInst>(U->getOperand(2))) { 01654 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2))); 01655 } else { 01656 s3 = U->getOperand(2); 01657 } 01658 } 01659 01660 // Vararg operators 01661 SmallVector<Value*, 4> sVarargs; 01662 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) { 01663 for (GetElementPtrInst::op_iterator OI = G->idx_begin(), 01664 OE = G->idx_end(); OI != OE; ++OI) { 01665 if (isa<BinaryOperator>(*OI) || 01666 isa<CmpInst>(*OI) || 01667 isa<ShuffleVectorInst>(*OI) || 01668 isa<ExtractElementInst>(*OI) || 01669 isa<InsertElementInst>(*OI) || 01670 isa<SelectInst>(*OI) || 01671 isa<CastInst>(*OI) || 01672 isa<GetElementPtrInst>(*OI)) { 01673 sVarargs.push_back(find_leader(availableOut[*PI], 01674 VN.lookup(*OI))); 01675 } else { 01676 sVarargs.push_back(*OI); 01677 } 01678 } 01679 } 01680 01681 Value* newVal = 0; 01682 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U)) 01683 newVal = BinaryOperator::Create(BO->getOpcode(), s1, s2, 01684 BO->getName()+".gvnpre", 01685 (*PI)->getTerminator()); 01686 else if (CmpInst* C = dyn_cast<CmpInst>(U)) 01687 newVal = CmpInst::Create(Context, C->getOpcode(), 01688 C->getPredicate(), s1, s2, 01689 C->getName()+".gvnpre", 01690 (*PI)->getTerminator()); 01691 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U)) 01692 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre", 01693 (*PI)->getTerminator()); 01694 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U)) 01695 newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre", 01696 (*PI)->getTerminator()); 01697 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U)) 01698 newVal = ExtractElementInst::Create(s1, s2, S->getName()+".gvnpre", 01699 (*PI)->getTerminator()); 01700 else if (SelectInst* S = dyn_cast<SelectInst>(U)) 01701 newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre", 01702 (*PI)->getTerminator()); 01703 else if (CastInst* C = dyn_cast<CastInst>(U)) 01704 newVal = CastInst::Create(C->getOpcode(), s1, C->getType(), 01705 C->getName()+".gvnpre", 01706 (*PI)->getTerminator()); 01707 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) 01708 newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(), 01709 G->getName()+".gvnpre", 01710 (*PI)->getTerminator()); 01711 01712 VN.add(newVal, VN.lookup(U)); 01713 01714 ValueNumberedSet& predAvail = availableOut[*PI]; 01715 val_replace(predAvail, newVal); 01716 val_replace(new_sets[*PI], newVal); 01717 predAvail.set(VN.lookup(newVal)); 01718 01719 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI); 01720 if (av != avail.end()) 01721 avail.erase(av); 01722 avail.insert(std::make_pair(*PI, newVal)); 01723 01724 ++NumInsertedVals; 01725 } 01726 } 01727 01728 PHINode* p = 0; 01729 01730 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 01731 if (p == 0) 01732 p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin()); 01733 01734 p->addIncoming(avail[*PI], *PI); 01735 } 01736 01737 VN.add(p, VN.lookup(e)); 01738 val_replace(availableOut[BB], p); 01739 availableOut[BB].set(VN.lookup(e)); 01740 generatedPhis[BB].insert(p); 01741 generatedPhis[BB].set(VN.lookup(e)); 01742 new_sets[BB].insert(p); 01743 new_sets[BB].set(VN.lookup(e)); 01744 01745 ++NumInsertedPhis; 01746 } 01747 01748 /// insertion_mergepoint - When walking the dom tree, check at each merge 01749 /// block for the possibility of a partial redundancy. If present, eliminate it 01750 unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList, 01751 df_iterator<DomTreeNode*>& D, 01752 std::map<BasicBlock*, ValueNumberedSet >& new_sets) { 01753 bool changed_function = false; 01754 bool new_stuff = false; 01755 01756 BasicBlock* BB = D->getBlock(); 01757 for (unsigned i = 0; i < workList.size(); ++i) { 01758 Value* e = workList[i]; 01759 01760 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) || 01761 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) || 01762 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) || 01763 isa<GetElementPtrInst>(e)) { 01764 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e))) 01765 continue; 01766 01767 DenseMap<BasicBlock*, Value*> avail; 01768 bool by_some = false; 01769 bool all_same = true; 01770 Value * first_s = 0; 01771 01772 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; 01773 ++PI) { 01774 Value *e2 = phi_translate(e, *PI, BB); 01775 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2)); 01776 01777 if (e3 == 0) { 01778 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI); 01779 if (av != avail.end()) 01780 avail.erase(av); 01781 avail.insert(std::make_pair(*PI, e2)); 01782 all_same = false; 01783 } else { 01784 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI); 01785 if (av != avail.end()) 01786 avail.erase(av); 01787 avail.insert(std::make_pair(*PI, e3)); 01788 01789 by_some = true; 01790 if (first_s == 0) 01791 first_s = e3; 01792 else if (first_s != e3) 01793 all_same = false; 01794 } 01795 } 01796 01797 if (by_some && !all_same && 01798 !generatedPhis[BB].test(VN.lookup(e))) { 01799 insertion_pre(e, BB, avail, new_sets); 01800 01801 changed_function = true; 01802 new_stuff = true; 01803 } 01804 } 01805 } 01806 01807 unsigned retval = 0; 01808 if (changed_function) 01809 retval += 1; 01810 if (new_stuff) 01811 retval += 2; 01812 01813 return retval; 01814 } 01815 01816 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for 01817 /// merge points. When one is found, check for a partial redundancy. If one is 01818 /// present, eliminate it. Repeat this walk until no changes are made. 01819 bool GVNPRE::insertion(Function& F) { 01820 bool changed_function = false; 01821 01822 DominatorTree &DT = getAnalysis<DominatorTree>(); 01823 01824 std::map<BasicBlock*, ValueNumberedSet> new_sets; 01825 bool new_stuff = true; 01826 while (new_stuff) { 01827 new_stuff = false; 01828 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 01829 E = df_end(DT.getRootNode()); DI != E; ++DI) { 01830 BasicBlock* BB = DI->getBlock(); 01831 01832 if (BB == 0) 01833 continue; 01834 01835 ValueNumberedSet& availOut = availableOut[BB]; 01836 ValueNumberedSet& anticIn = anticipatedIn[BB]; 01837 01838 // Replace leaders with leaders inherited from dominator 01839 if (DI->getIDom() != 0) { 01840 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()]; 01841 for (ValueNumberedSet::iterator I = dom_set.begin(), 01842 E = dom_set.end(); I != E; ++I) { 01843 val_replace(new_sets[BB], *I); 01844 val_replace(availOut, *I); 01845 } 01846 } 01847 01848 // If there is more than one predecessor... 01849 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) { 01850 SmallVector<Value*, 8> workList; 01851 workList.reserve(anticIn.size()); 01852 topo_sort(anticIn, workList); 01853 01854 unsigned result = insertion_mergepoint(workList, DI, new_sets); 01855 if (result & 1) 01856 changed_function = true; 01857 if (result & 2) 01858 new_stuff = true; 01859 } 01860 } 01861 } 01862 01863 return changed_function; 01864 } 01865 01866 // GVNPRE::runOnFunction - This is the main transformation entry point for a 01867 // function. 01868 // 01869 bool GVNPRE::runOnFunction(Function &F) { 01870 // Clean out global sets from any previous functions 01871 VN.clear(); 01872 createdExpressions.clear(); 01873 availableOut.clear(); 01874 anticipatedIn.clear(); 01875 generatedPhis.clear(); 01876 01877 bool changed_function = false; 01878 01879 // Phase 1: BuildSets 01880 // This phase calculates the AVAIL_OUT and ANTIC_IN sets 01881 buildsets(F); 01882 01883 // Phase 2: Insert 01884 // This phase inserts values to make partially redundant values 01885 // fully redundant 01886 changed_function |= insertion(F); 01887 01888 // Phase 3: Eliminate 01889 // This phase performs trivial full redundancy elimination 01890 changed_function |= elimination(); 01891 01892 // Phase 4: Cleanup 01893 // This phase cleans up values that were created solely 01894 // as leaders for expressions 01895 cleanup(); 01896 01897 return changed_function; 01898 }