GVN.cpp revision 07e6e56f57e8781a8d7bc601cc9034a3741d84c2
1//===- GVN.cpp - Eliminate redundant values and loads ------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass performs global value numbering to eliminate fully redundant 11// instructions. It also performs simple dead load elimination. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "gvn" 16 17#include "llvm/Transforms/Scalar.h" 18#include "llvm/BasicBlock.h" 19#include "llvm/Constants.h" 20#include "llvm/DerivedTypes.h" 21#include "llvm/Function.h" 22#include "llvm/IntrinsicInst.h" 23#include "llvm/Instructions.h" 24#include "llvm/ParameterAttributes.h" 25#include "llvm/Value.h" 26#include "llvm/ADT/BitVector.h" 27#include "llvm/ADT/DenseMap.h" 28#include "llvm/ADT/DepthFirstIterator.h" 29#include "llvm/ADT/SmallPtrSet.h" 30#include "llvm/ADT/SmallVector.h" 31#include "llvm/ADT/Statistic.h" 32#include "llvm/Analysis/Dominators.h" 33#include "llvm/Analysis/AliasAnalysis.h" 34#include "llvm/Analysis/MemoryDependenceAnalysis.h" 35#include "llvm/Support/CFG.h" 36#include "llvm/Support/Compiler.h" 37#include "llvm/Target/TargetData.h" 38using namespace llvm; 39 40//===----------------------------------------------------------------------===// 41// ValueTable Class 42//===----------------------------------------------------------------------===// 43 44/// This class holds the mapping between values and value numbers. It is used 45/// as an efficient mechanism to determine the expression-wise equivalence of 46/// two values. 47namespace { 48 struct VISIBILITY_HIDDEN Expression { 49 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 50 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 51 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 52 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 53 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 54 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 55 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 56 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 57 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 58 PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY, 59 TOMBSTONE }; 60 61 ExpressionOpcode opcode; 62 const Type* type; 63 uint32_t firstVN; 64 uint32_t secondVN; 65 uint32_t thirdVN; 66 SmallVector<uint32_t, 4> varargs; 67 Value* function; 68 69 Expression() { } 70 Expression(ExpressionOpcode o) : opcode(o) { } 71 72 bool operator==(const Expression &other) const { 73 if (opcode != other.opcode) 74 return false; 75 else if (opcode == EMPTY || opcode == TOMBSTONE) 76 return true; 77 else if (type != other.type) 78 return false; 79 else if (function != other.function) 80 return false; 81 else if (firstVN != other.firstVN) 82 return false; 83 else if (secondVN != other.secondVN) 84 return false; 85 else if (thirdVN != other.thirdVN) 86 return false; 87 else { 88 if (varargs.size() != other.varargs.size()) 89 return false; 90 91 for (size_t i = 0; i < varargs.size(); ++i) 92 if (varargs[i] != other.varargs[i]) 93 return false; 94 95 return true; 96 } 97 } 98 99 bool operator!=(const Expression &other) const { 100 if (opcode != other.opcode) 101 return true; 102 else if (opcode == EMPTY || opcode == TOMBSTONE) 103 return false; 104 else if (type != other.type) 105 return true; 106 else if (function != other.function) 107 return true; 108 else if (firstVN != other.firstVN) 109 return true; 110 else if (secondVN != other.secondVN) 111 return true; 112 else if (thirdVN != other.thirdVN) 113 return true; 114 else { 115 if (varargs.size() != other.varargs.size()) 116 return true; 117 118 for (size_t i = 0; i < varargs.size(); ++i) 119 if (varargs[i] != other.varargs[i]) 120 return true; 121 122 return false; 123 } 124 } 125 }; 126 127 class VISIBILITY_HIDDEN ValueTable { 128 private: 129 DenseMap<Value*, uint32_t> valueNumbering; 130 DenseMap<Expression, uint32_t> expressionNumbering; 131 AliasAnalysis* AA; 132 133 uint32_t nextValueNumber; 134 135 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 136 Expression::ExpressionOpcode getOpcode(CmpInst* C); 137 Expression::ExpressionOpcode getOpcode(CastInst* C); 138 Expression create_expression(BinaryOperator* BO); 139 Expression create_expression(CmpInst* C); 140 Expression create_expression(ShuffleVectorInst* V); 141 Expression create_expression(ExtractElementInst* C); 142 Expression create_expression(InsertElementInst* V); 143 Expression create_expression(SelectInst* V); 144 Expression create_expression(CastInst* C); 145 Expression create_expression(GetElementPtrInst* G); 146 Expression create_expression(CallInst* C); 147 public: 148 ValueTable() : nextValueNumber(1) { } 149 uint32_t lookup_or_add(Value* V); 150 uint32_t lookup(Value* V) const; 151 void add(Value* V, uint32_t num); 152 void clear(); 153 void erase(Value* v); 154 unsigned size(); 155 void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 156 uint32_t hash_operand(Value* v); 157 }; 158} 159 160namespace llvm { 161template <> struct DenseMapInfo<Expression> { 162 static inline Expression getEmptyKey() { 163 return Expression(Expression::EMPTY); 164 } 165 166 static inline Expression getTombstoneKey() { 167 return Expression(Expression::TOMBSTONE); 168 } 169 170 static unsigned getHashValue(const Expression e) { 171 unsigned hash = e.opcode; 172 173 hash = e.firstVN + hash * 37; 174 hash = e.secondVN + hash * 37; 175 hash = e.thirdVN + hash * 37; 176 177 hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 178 (unsigned)((uintptr_t)e.type >> 9)) + 179 hash * 37; 180 181 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 182 E = e.varargs.end(); I != E; ++I) 183 hash = *I + hash * 37; 184 185 hash = ((unsigned)((uintptr_t)e.function >> 4) ^ 186 (unsigned)((uintptr_t)e.function >> 9)) + 187 hash * 37; 188 189 return hash; 190 } 191 static bool isEqual(const Expression &LHS, const Expression &RHS) { 192 return LHS == RHS; 193 } 194 static bool isPod() { return true; } 195}; 196} 197 198//===----------------------------------------------------------------------===// 199// ValueTable Internal Functions 200//===----------------------------------------------------------------------===// 201Expression::ExpressionOpcode 202 ValueTable::getOpcode(BinaryOperator* BO) { 203 switch(BO->getOpcode()) { 204 case Instruction::Add: 205 return Expression::ADD; 206 case Instruction::Sub: 207 return Expression::SUB; 208 case Instruction::Mul: 209 return Expression::MUL; 210 case Instruction::UDiv: 211 return Expression::UDIV; 212 case Instruction::SDiv: 213 return Expression::SDIV; 214 case Instruction::FDiv: 215 return Expression::FDIV; 216 case Instruction::URem: 217 return Expression::UREM; 218 case Instruction::SRem: 219 return Expression::SREM; 220 case Instruction::FRem: 221 return Expression::FREM; 222 case Instruction::Shl: 223 return Expression::SHL; 224 case Instruction::LShr: 225 return Expression::LSHR; 226 case Instruction::AShr: 227 return Expression::ASHR; 228 case Instruction::And: 229 return Expression::AND; 230 case Instruction::Or: 231 return Expression::OR; 232 case Instruction::Xor: 233 return Expression::XOR; 234 235 // THIS SHOULD NEVER HAPPEN 236 default: 237 assert(0 && "Binary operator with unknown opcode?"); 238 return Expression::ADD; 239 } 240} 241 242Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 243 if (C->getOpcode() == Instruction::ICmp) { 244 switch (C->getPredicate()) { 245 case ICmpInst::ICMP_EQ: 246 return Expression::ICMPEQ; 247 case ICmpInst::ICMP_NE: 248 return Expression::ICMPNE; 249 case ICmpInst::ICMP_UGT: 250 return Expression::ICMPUGT; 251 case ICmpInst::ICMP_UGE: 252 return Expression::ICMPUGE; 253 case ICmpInst::ICMP_ULT: 254 return Expression::ICMPULT; 255 case ICmpInst::ICMP_ULE: 256 return Expression::ICMPULE; 257 case ICmpInst::ICMP_SGT: 258 return Expression::ICMPSGT; 259 case ICmpInst::ICMP_SGE: 260 return Expression::ICMPSGE; 261 case ICmpInst::ICMP_SLT: 262 return Expression::ICMPSLT; 263 case ICmpInst::ICMP_SLE: 264 return Expression::ICMPSLE; 265 266 // THIS SHOULD NEVER HAPPEN 267 default: 268 assert(0 && "Comparison with unknown predicate?"); 269 return Expression::ICMPEQ; 270 } 271 } else { 272 switch (C->getPredicate()) { 273 case FCmpInst::FCMP_OEQ: 274 return Expression::FCMPOEQ; 275 case FCmpInst::FCMP_OGT: 276 return Expression::FCMPOGT; 277 case FCmpInst::FCMP_OGE: 278 return Expression::FCMPOGE; 279 case FCmpInst::FCMP_OLT: 280 return Expression::FCMPOLT; 281 case FCmpInst::FCMP_OLE: 282 return Expression::FCMPOLE; 283 case FCmpInst::FCMP_ONE: 284 return Expression::FCMPONE; 285 case FCmpInst::FCMP_ORD: 286 return Expression::FCMPORD; 287 case FCmpInst::FCMP_UNO: 288 return Expression::FCMPUNO; 289 case FCmpInst::FCMP_UEQ: 290 return Expression::FCMPUEQ; 291 case FCmpInst::FCMP_UGT: 292 return Expression::FCMPUGT; 293 case FCmpInst::FCMP_UGE: 294 return Expression::FCMPUGE; 295 case FCmpInst::FCMP_ULT: 296 return Expression::FCMPULT; 297 case FCmpInst::FCMP_ULE: 298 return Expression::FCMPULE; 299 case FCmpInst::FCMP_UNE: 300 return Expression::FCMPUNE; 301 302 // THIS SHOULD NEVER HAPPEN 303 default: 304 assert(0 && "Comparison with unknown predicate?"); 305 return Expression::FCMPOEQ; 306 } 307 } 308} 309 310Expression::ExpressionOpcode 311 ValueTable::getOpcode(CastInst* C) { 312 switch(C->getOpcode()) { 313 case Instruction::Trunc: 314 return Expression::TRUNC; 315 case Instruction::ZExt: 316 return Expression::ZEXT; 317 case Instruction::SExt: 318 return Expression::SEXT; 319 case Instruction::FPToUI: 320 return Expression::FPTOUI; 321 case Instruction::FPToSI: 322 return Expression::FPTOSI; 323 case Instruction::UIToFP: 324 return Expression::UITOFP; 325 case Instruction::SIToFP: 326 return Expression::SITOFP; 327 case Instruction::FPTrunc: 328 return Expression::FPTRUNC; 329 case Instruction::FPExt: 330 return Expression::FPEXT; 331 case Instruction::PtrToInt: 332 return Expression::PTRTOINT; 333 case Instruction::IntToPtr: 334 return Expression::INTTOPTR; 335 case Instruction::BitCast: 336 return Expression::BITCAST; 337 338 // THIS SHOULD NEVER HAPPEN 339 default: 340 assert(0 && "Cast operator with unknown opcode?"); 341 return Expression::BITCAST; 342 } 343} 344 345uint32_t ValueTable::hash_operand(Value* v) { 346 if (CallInst* CI = dyn_cast<CallInst>(v)) 347 if (!AA->doesNotAccessMemory(CI)) 348 return nextValueNumber++; 349 350 return lookup_or_add(v); 351} 352 353Expression ValueTable::create_expression(CallInst* C) { 354 Expression e; 355 356 e.type = C->getType(); 357 e.firstVN = 0; 358 e.secondVN = 0; 359 e.thirdVN = 0; 360 e.function = C->getCalledFunction(); 361 e.opcode = Expression::CALL; 362 363 for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 364 I != E; ++I) 365 e.varargs.push_back(hash_operand(*I)); 366 367 return e; 368} 369 370Expression ValueTable::create_expression(BinaryOperator* BO) { 371 Expression e; 372 373 e.firstVN = hash_operand(BO->getOperand(0)); 374 e.secondVN = hash_operand(BO->getOperand(1)); 375 e.thirdVN = 0; 376 e.function = 0; 377 e.type = BO->getType(); 378 e.opcode = getOpcode(BO); 379 380 return e; 381} 382 383Expression ValueTable::create_expression(CmpInst* C) { 384 Expression e; 385 386 e.firstVN = hash_operand(C->getOperand(0)); 387 e.secondVN = hash_operand(C->getOperand(1)); 388 e.thirdVN = 0; 389 e.function = 0; 390 e.type = C->getType(); 391 e.opcode = getOpcode(C); 392 393 return e; 394} 395 396Expression ValueTable::create_expression(CastInst* C) { 397 Expression e; 398 399 e.firstVN = hash_operand(C->getOperand(0)); 400 e.secondVN = 0; 401 e.thirdVN = 0; 402 e.function = 0; 403 e.type = C->getType(); 404 e.opcode = getOpcode(C); 405 406 return e; 407} 408 409Expression ValueTable::create_expression(ShuffleVectorInst* S) { 410 Expression e; 411 412 e.firstVN = hash_operand(S->getOperand(0)); 413 e.secondVN = hash_operand(S->getOperand(1)); 414 e.thirdVN = hash_operand(S->getOperand(2)); 415 e.function = 0; 416 e.type = S->getType(); 417 e.opcode = Expression::SHUFFLE; 418 419 return e; 420} 421 422Expression ValueTable::create_expression(ExtractElementInst* E) { 423 Expression e; 424 425 e.firstVN = hash_operand(E->getOperand(0)); 426 e.secondVN = hash_operand(E->getOperand(1)); 427 e.thirdVN = 0; 428 e.function = 0; 429 e.type = E->getType(); 430 e.opcode = Expression::EXTRACT; 431 432 return e; 433} 434 435Expression ValueTable::create_expression(InsertElementInst* I) { 436 Expression e; 437 438 e.firstVN = hash_operand(I->getOperand(0)); 439 e.secondVN = hash_operand(I->getOperand(1)); 440 e.thirdVN = hash_operand(I->getOperand(2)); 441 e.function = 0; 442 e.type = I->getType(); 443 e.opcode = Expression::INSERT; 444 445 return e; 446} 447 448Expression ValueTable::create_expression(SelectInst* I) { 449 Expression e; 450 451 e.firstVN = hash_operand(I->getCondition()); 452 e.secondVN = hash_operand(I->getTrueValue()); 453 e.thirdVN = hash_operand(I->getFalseValue()); 454 e.function = 0; 455 e.type = I->getType(); 456 e.opcode = Expression::SELECT; 457 458 return e; 459} 460 461Expression ValueTable::create_expression(GetElementPtrInst* G) { 462 Expression e; 463 464 e.firstVN = hash_operand(G->getPointerOperand()); 465 e.secondVN = 0; 466 e.thirdVN = 0; 467 e.function = 0; 468 e.type = G->getType(); 469 e.opcode = Expression::GEP; 470 471 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 472 I != E; ++I) 473 e.varargs.push_back(hash_operand(*I)); 474 475 return e; 476} 477 478//===----------------------------------------------------------------------===// 479// ValueTable External Functions 480//===----------------------------------------------------------------------===// 481 482/// lookup_or_add - Returns the value number for the specified value, assigning 483/// it a new number if it did not have one before. 484uint32_t ValueTable::lookup_or_add(Value* V) { 485 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 486 if (VI != valueNumbering.end()) 487 return VI->second; 488 489 if (CallInst* C = dyn_cast<CallInst>(V)) { 490 if (AA->onlyReadsMemory(C)) { // includes doesNotAccessMemory 491 Expression e = create_expression(C); 492 493 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 494 if (EI != expressionNumbering.end()) { 495 valueNumbering.insert(std::make_pair(V, EI->second)); 496 return EI->second; 497 } else { 498 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 499 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 500 501 return nextValueNumber++; 502 } 503 } else { 504 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 505 return nextValueNumber++; 506 } 507 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 508 Expression e = create_expression(BO); 509 510 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 511 if (EI != expressionNumbering.end()) { 512 valueNumbering.insert(std::make_pair(V, EI->second)); 513 return EI->second; 514 } else { 515 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 516 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 517 518 return nextValueNumber++; 519 } 520 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 521 Expression e = create_expression(C); 522 523 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 524 if (EI != expressionNumbering.end()) { 525 valueNumbering.insert(std::make_pair(V, EI->second)); 526 return EI->second; 527 } else { 528 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 529 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 530 531 return nextValueNumber++; 532 } 533 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 534 Expression e = create_expression(U); 535 536 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 537 if (EI != expressionNumbering.end()) { 538 valueNumbering.insert(std::make_pair(V, EI->second)); 539 return EI->second; 540 } else { 541 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 542 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 543 544 return nextValueNumber++; 545 } 546 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 547 Expression e = create_expression(U); 548 549 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 550 if (EI != expressionNumbering.end()) { 551 valueNumbering.insert(std::make_pair(V, EI->second)); 552 return EI->second; 553 } else { 554 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 555 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 556 557 return nextValueNumber++; 558 } 559 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 560 Expression e = create_expression(U); 561 562 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 563 if (EI != expressionNumbering.end()) { 564 valueNumbering.insert(std::make_pair(V, EI->second)); 565 return EI->second; 566 } else { 567 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 568 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 569 570 return nextValueNumber++; 571 } 572 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 573 Expression e = create_expression(U); 574 575 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 576 if (EI != expressionNumbering.end()) { 577 valueNumbering.insert(std::make_pair(V, EI->second)); 578 return EI->second; 579 } else { 580 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 581 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 582 583 return nextValueNumber++; 584 } 585 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 586 Expression e = create_expression(U); 587 588 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 589 if (EI != expressionNumbering.end()) { 590 valueNumbering.insert(std::make_pair(V, EI->second)); 591 return EI->second; 592 } else { 593 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 594 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 595 596 return nextValueNumber++; 597 } 598 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 599 Expression e = create_expression(U); 600 601 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 602 if (EI != expressionNumbering.end()) { 603 valueNumbering.insert(std::make_pair(V, EI->second)); 604 return EI->second; 605 } else { 606 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 607 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 608 609 return nextValueNumber++; 610 } 611 } else { 612 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 613 return nextValueNumber++; 614 } 615} 616 617/// lookup - Returns the value number of the specified value. Fails if 618/// the value has not yet been numbered. 619uint32_t ValueTable::lookup(Value* V) const { 620 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 621 if (VI != valueNumbering.end()) 622 return VI->second; 623 else 624 assert(0 && "Value not numbered?"); 625 626 return 0; 627} 628 629/// clear - Remove all entries from the ValueTable 630void ValueTable::clear() { 631 valueNumbering.clear(); 632 expressionNumbering.clear(); 633 nextValueNumber = 1; 634} 635 636/// erase - Remove a value from the value numbering 637void ValueTable::erase(Value* V) { 638 valueNumbering.erase(V); 639} 640 641//===----------------------------------------------------------------------===// 642// ValueNumberedSet Class 643//===----------------------------------------------------------------------===// 644namespace { 645class ValueNumberedSet { 646 private: 647 SmallPtrSet<Value*, 8> contents; 648 BitVector numbers; 649 public: 650 ValueNumberedSet() { numbers.resize(1); } 651 ValueNumberedSet(const ValueNumberedSet& other) { 652 numbers = other.numbers; 653 contents = other.contents; 654 } 655 656 typedef SmallPtrSet<Value*, 8>::iterator iterator; 657 658 iterator begin() { return contents.begin(); } 659 iterator end() { return contents.end(); } 660 661 bool insert(Value* v) { return contents.insert(v); } 662 void insert(iterator I, iterator E) { contents.insert(I, E); } 663 void erase(Value* v) { contents.erase(v); } 664 unsigned count(Value* v) { return contents.count(v); } 665 size_t size() { return contents.size(); } 666 667 void set(unsigned i) { 668 if (i >= numbers.size()) 669 numbers.resize(i+1); 670 671 numbers.set(i); 672 } 673 674 void operator=(const ValueNumberedSet& other) { 675 contents = other.contents; 676 numbers = other.numbers; 677 } 678 679 void reset(unsigned i) { 680 if (i < numbers.size()) 681 numbers.reset(i); 682 } 683 684 bool test(unsigned i) { 685 if (i >= numbers.size()) 686 return false; 687 688 return numbers.test(i); 689 } 690 691 void clear() { 692 contents.clear(); 693 numbers.clear(); 694 } 695}; 696} 697 698//===----------------------------------------------------------------------===// 699// GVN Pass 700//===----------------------------------------------------------------------===// 701 702namespace { 703 704 class VISIBILITY_HIDDEN GVN : public FunctionPass { 705 bool runOnFunction(Function &F); 706 public: 707 static char ID; // Pass identification, replacement for typeid 708 GVN() : FunctionPass((intptr_t)&ID) { } 709 710 private: 711 ValueTable VN; 712 713 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 714 715 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 716 PhiMapType phiMap; 717 718 719 // This transformation requires dominator postdominator info 720 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 721 AU.setPreservesCFG(); 722 AU.addRequired<DominatorTree>(); 723 AU.addRequired<MemoryDependenceAnalysis>(); 724 AU.addRequired<AliasAnalysis>(); 725 AU.addRequired<TargetData>(); 726 AU.addPreserved<AliasAnalysis>(); 727 AU.addPreserved<MemoryDependenceAnalysis>(); 728 AU.addPreserved<TargetData>(); 729 } 730 731 // Helper fuctions 732 // FIXME: eliminate or document these better 733 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 734 void val_insert(ValueNumberedSet& s, Value* v); 735 bool processLoad(LoadInst* L, 736 DenseMap<Value*, LoadInst*>& lastLoad, 737 SmallVector<Instruction*, 4>& toErase); 738 bool processInstruction(Instruction* I, 739 ValueNumberedSet& currAvail, 740 DenseMap<Value*, LoadInst*>& lastSeenLoad, 741 SmallVector<Instruction*, 4>& toErase); 742 bool processNonLocalLoad(LoadInst* L, 743 SmallVector<Instruction*, 4>& toErase); 744 bool processMemCpy(MemCpyInst* M, MemCpyInst* MDep, 745 SmallVector<Instruction*, 4>& toErase); 746 bool performReturnSlotOptzn(MemCpyInst* cpy, CallInst* C, 747 SmallVector<Instruction*, 4>& toErase); 748 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 749 DenseMap<BasicBlock*, Value*> &Phis, 750 bool top_level = false); 751 void dump(DenseMap<BasicBlock*, Value*>& d); 752 bool iterateOnFunction(Function &F); 753 Value* CollapsePhi(PHINode* p); 754 bool isSafeReplacement(PHINode* p, Instruction* inst); 755 }; 756 757 char GVN::ID = 0; 758 759} 760 761// createGVNPass - The public interface to this file... 762FunctionPass *llvm::createGVNPass() { return new GVN(); } 763 764static RegisterPass<GVN> X("gvn", 765 "Global Value Numbering"); 766 767STATISTIC(NumGVNInstr, "Number of instructions deleted"); 768STATISTIC(NumGVNLoad, "Number of loads deleted"); 769 770/// find_leader - Given a set and a value number, return the first 771/// element of the set with that value number, or 0 if no such element 772/// is present 773Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 774 if (!vals.test(v)) 775 return 0; 776 777 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 778 I != E; ++I) 779 if (v == VN.lookup(*I)) 780 return *I; 781 782 assert(0 && "No leader found, but present bit is set?"); 783 return 0; 784} 785 786/// val_insert - Insert a value into a set only if there is not a value 787/// with the same value number already in the set 788void GVN::val_insert(ValueNumberedSet& s, Value* v) { 789 uint32_t num = VN.lookup(v); 790 if (!s.test(num)) 791 s.insert(v); 792} 793 794void GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 795 printf("{\n"); 796 for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 797 E = d.end(); I != E; ++I) { 798 if (I->second == MemoryDependenceAnalysis::None) 799 printf("None\n"); 800 else 801 I->second->dump(); 802 } 803 printf("}\n"); 804} 805 806Value* GVN::CollapsePhi(PHINode* p) { 807 DominatorTree &DT = getAnalysis<DominatorTree>(); 808 Value* constVal = p->hasConstantValue(); 809 810 if (constVal) { 811 if (Instruction* inst = dyn_cast<Instruction>(constVal)) { 812 if (DT.dominates(inst, p)) 813 if (isSafeReplacement(p, inst)) 814 return inst; 815 } else { 816 return constVal; 817 } 818 } 819 820 return 0; 821} 822 823bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 824 if (!isa<PHINode>(inst)) 825 return true; 826 827 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 828 UI != E; ++UI) 829 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 830 if (use_phi->getParent() == inst->getParent()) 831 return false; 832 833 return true; 834} 835 836/// GetValueForBlock - Get the value to use within the specified basic block. 837/// available values are in Phis. 838Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 839 DenseMap<BasicBlock*, Value*> &Phis, 840 bool top_level) { 841 842 // If we have already computed this value, return the previously computed val. 843 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 844 if (V != Phis.end() && !top_level) return V->second; 845 846 BasicBlock* singlePred = BB->getSinglePredecessor(); 847 if (singlePred) { 848 Value *ret = GetValueForBlock(singlePred, orig, Phis); 849 Phis[BB] = ret; 850 return ret; 851 } 852 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 853 // now, then get values to fill in the incoming values for the PHI. 854 PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", 855 BB->begin()); 856 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 857 858 if (Phis.count(BB) == 0) 859 Phis.insert(std::make_pair(BB, PN)); 860 861 // Fill in the incoming values for the block. 862 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 863 Value* val = GetValueForBlock(*PI, orig, Phis); 864 865 PN->addIncoming(val, *PI); 866 } 867 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 868 AA.copyValue(orig, PN); 869 870 // Attempt to collapse PHI nodes that are trivially redundant 871 Value* v = CollapsePhi(PN); 872 if (v) { 873 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 874 875 MD.removeInstruction(PN); 876 PN->replaceAllUsesWith(v); 877 878 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 879 E = Phis.end(); I != E; ++I) 880 if (I->second == PN) 881 I->second = v; 882 883 PN->eraseFromParent(); 884 885 Phis[BB] = v; 886 887 return v; 888 } 889 890 // Cache our phi construction results 891 phiMap[orig->getPointerOperand()].insert(PN); 892 return PN; 893} 894 895/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 896/// non-local by performing PHI construction. 897bool GVN::processNonLocalLoad(LoadInst* L, 898 SmallVector<Instruction*, 4>& toErase) { 899 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 900 901 // Find the non-local dependencies of the load 902 DenseMap<BasicBlock*, Value*> deps; 903 MD.getNonLocalDependency(L, deps); 904 905 DenseMap<BasicBlock*, Value*> repl; 906 907 // Filter out useless results (non-locals, etc) 908 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 909 I != E; ++I) 910 if (I->second == MemoryDependenceAnalysis::None) { 911 return false; 912 } else if (I->second == MemoryDependenceAnalysis::NonLocal) { 913 continue; 914 } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 915 if (S->getPointerOperand() == L->getPointerOperand()) 916 repl[I->first] = S->getOperand(0); 917 else 918 return false; 919 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 920 if (LD->getPointerOperand() == L->getPointerOperand()) 921 repl[I->first] = LD; 922 else 923 return false; 924 } else { 925 return false; 926 } 927 928 // Use cached PHI construction information from previous runs 929 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 930 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 931 I != E; ++I) { 932 if ((*I)->getParent() == L->getParent()) { 933 MD.removeInstruction(L); 934 L->replaceAllUsesWith(*I); 935 toErase.push_back(L); 936 NumGVNLoad++; 937 938 return true; 939 } else { 940 repl.insert(std::make_pair((*I)->getParent(), *I)); 941 } 942 } 943 944 // Perform PHI construction 945 SmallPtrSet<BasicBlock*, 4> visited; 946 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 947 948 MD.removeInstruction(L); 949 L->replaceAllUsesWith(v); 950 toErase.push_back(L); 951 NumGVNLoad++; 952 953 return true; 954} 955 956/// processLoad - Attempt to eliminate a load, first by eliminating it 957/// locally, and then attempting non-local elimination if that fails. 958bool GVN::processLoad(LoadInst* L, 959 DenseMap<Value*, LoadInst*>& lastLoad, 960 SmallVector<Instruction*, 4>& toErase) { 961 if (L->isVolatile()) { 962 lastLoad[L->getPointerOperand()] = L; 963 return false; 964 } 965 966 Value* pointer = L->getPointerOperand(); 967 LoadInst*& last = lastLoad[pointer]; 968 969 // ... to a pointer that has been loaded from before... 970 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 971 bool removedNonLocal = false; 972 Instruction* dep = MD.getDependency(L); 973 if (dep == MemoryDependenceAnalysis::NonLocal && 974 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 975 removedNonLocal = processNonLocalLoad(L, toErase); 976 977 if (!removedNonLocal) 978 last = L; 979 980 return removedNonLocal; 981 } 982 983 984 bool deletedLoad = false; 985 986 // Walk up the dependency chain until we either find 987 // a dependency we can use, or we can't walk any further 988 while (dep != MemoryDependenceAnalysis::None && 989 dep != MemoryDependenceAnalysis::NonLocal && 990 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 991 // ... that depends on a store ... 992 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 993 if (S->getPointerOperand() == pointer) { 994 // Remove it! 995 MD.removeInstruction(L); 996 997 L->replaceAllUsesWith(S->getOperand(0)); 998 toErase.push_back(L); 999 deletedLoad = true; 1000 NumGVNLoad++; 1001 } 1002 1003 // Whether we removed it or not, we can't 1004 // go any further 1005 break; 1006 } else if (!last) { 1007 // If we don't depend on a store, and we haven't 1008 // been loaded before, bail. 1009 break; 1010 } else if (dep == last) { 1011 // Remove it! 1012 MD.removeInstruction(L); 1013 1014 L->replaceAllUsesWith(last); 1015 toErase.push_back(L); 1016 deletedLoad = true; 1017 NumGVNLoad++; 1018 1019 break; 1020 } else { 1021 dep = MD.getDependency(L, dep); 1022 } 1023 } 1024 1025 if (dep != MemoryDependenceAnalysis::None && 1026 dep != MemoryDependenceAnalysis::NonLocal && 1027 isa<AllocationInst>(dep)) { 1028 // Check that this load is actually from the 1029 // allocation we found 1030 Value* v = L->getOperand(0); 1031 while (true) { 1032 if (BitCastInst *BC = dyn_cast<BitCastInst>(v)) 1033 v = BC->getOperand(0); 1034 else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v)) 1035 v = GEP->getOperand(0); 1036 else 1037 break; 1038 } 1039 if (v == dep) { 1040 // If this load depends directly on an allocation, there isn't 1041 // anything stored there; therefore, we can optimize this load 1042 // to undef. 1043 MD.removeInstruction(L); 1044 1045 L->replaceAllUsesWith(UndefValue::get(L->getType())); 1046 toErase.push_back(L); 1047 deletedLoad = true; 1048 NumGVNLoad++; 1049 } 1050 } 1051 1052 if (!deletedLoad) 1053 last = L; 1054 1055 return deletedLoad; 1056} 1057 1058/// isReturnSlotOptznProfitable - Determine if performing a return slot 1059/// fusion with the slot dest is profitable 1060static bool isReturnSlotOptznProfitable(Value* dest, MemCpyInst* cpy) { 1061 // We currently consider it profitable if dest is otherwise dead. 1062 SmallVector<User*, 8> useList(dest->use_begin(), dest->use_end()); 1063 while (!useList.empty()) { 1064 User* UI = useList.back(); 1065 1066 if (isa<GetElementPtrInst>(UI) || isa<BitCastInst>(UI)) { 1067 useList.pop_back(); 1068 for (User::use_iterator I = UI->use_begin(), E = UI->use_end(); 1069 I != E; ++I) 1070 useList.push_back(*I); 1071 } else if (UI == cpy) 1072 useList.pop_back(); 1073 else 1074 return false; 1075 } 1076 1077 return true; 1078} 1079 1080/// performReturnSlotOptzn - takes a memcpy and a call that it depends on, 1081/// and checks for the possibility of a return slot optimization by having 1082/// the call write its result directly into the callees return parameter 1083/// rather than using memcpy 1084bool GVN::performReturnSlotOptzn(MemCpyInst* cpy, CallInst* C, 1085 SmallVector<Instruction*, 4>& toErase) { 1086 // Deliberately get the source and destination with bitcasts stripped away, 1087 // because we'll need to do type comparisons based on the underlying type. 1088 Value* cpyDest = cpy->getDest(); 1089 Value* cpySrc = cpy->getSource(); 1090 CallSite CS = CallSite::get(C); 1091 1092 // Since this is a return slot optimization, we need to make sure that 1093 // the value being copied is, in fact, in a return slot. We also need to 1094 // check that the return slot parameter is marked noalias, so that we can 1095 // be sure that changing it will not cause unexpected behavior changes due 1096 // to it being accessed through a global or another parameter. 1097 if (CS.arg_size() == 0 || 1098 cpySrc != CS.getArgument(0) || 1099 !CS.paramHasAttr(1, ParamAttr::NoAlias | ParamAttr::StructRet)) 1100 return false; 1101 1102 // Check that something sneaky is not happening involving casting 1103 // return slot types around. 1104 if (CS.getArgument(0)->getType() != cpyDest->getType()) 1105 return false; 1106 // sret --> pointer 1107 const PointerType* PT = cast<PointerType>(cpyDest->getType()); 1108 1109 // We can only perform the transformation if the size of the memcpy 1110 // is constant and equal to the size of the structure. 1111 ConstantInt* cpyLength = dyn_cast<ConstantInt>(cpy->getLength()); 1112 if (!cpyLength) 1113 return false; 1114 1115 TargetData& TD = getAnalysis<TargetData>(); 1116 if (TD.getTypeStoreSize(PT->getElementType()) != cpyLength->getZExtValue()) 1117 return false; 1118 1119 // We only perform the transformation if it will be profitable. 1120 if (!isReturnSlotOptznProfitable(cpyDest, cpy)) 1121 return false; 1122 1123 // In addition to knowing that the call does not access the return slot 1124 // in some unexpected manner, which we derive from the noalias attribute, 1125 // we also need to know that it does not sneakily modify the destination 1126 // slot in the caller. We don't have parameter attributes to go by 1127 // for this one, so we just rely on AA to figure it out for us. 1128 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 1129 if (AA.getModRefInfo(C, cpy->getRawDest(), cpyLength->getZExtValue()) != 1130 AliasAnalysis::NoModRef) 1131 return false; 1132 1133 // If all the checks have passed, then we're alright to do the transformation. 1134 CS.setArgument(0, cpyDest); 1135 1136 // Drop any cached information about the call, because we may have changed 1137 // its dependence information by changing its parameter. 1138 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1139 MD.dropInstruction(C); 1140 1141 // Remove the memcpy 1142 MD.removeInstruction(cpy); 1143 toErase.push_back(cpy); 1144 1145 return true; 1146} 1147 1148/// processMemCpy - perform simplication of memcpy's. If we have memcpy A which 1149/// copies X to Y, and memcpy B which copies Y to Z, then we can rewrite B to be 1150/// a memcpy from X to Z (or potentially a memmove, depending on circumstances). 1151/// This allows later passes to remove the first memcpy altogether. 1152bool GVN::processMemCpy(MemCpyInst* M, MemCpyInst* MDep, 1153 SmallVector<Instruction*, 4>& toErase) { 1154 // We can only transforms memcpy's where the dest of one is the source of the 1155 // other 1156 if (M->getSource() != MDep->getDest()) 1157 return false; 1158 1159 // Second, the length of the memcpy's must be the same, or the preceeding one 1160 // must be larger than the following one. 1161 ConstantInt* C1 = dyn_cast<ConstantInt>(MDep->getLength()); 1162 ConstantInt* C2 = dyn_cast<ConstantInt>(M->getLength()); 1163 if (!C1 || !C2) 1164 return false; 1165 1166 uint64_t CpySize = C1->getValue().getZExtValue(); 1167 uint64_t DepSize = C2->getValue().getZExtValue(); 1168 1169 if (DepSize < CpySize) 1170 return false; 1171 1172 // Finally, we have to make sure that the dest of the second does not 1173 // alias the source of the first 1174 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 1175 if (AA.alias(M->getRawDest(), CpySize, MDep->getRawSource(), DepSize) != 1176 AliasAnalysis::NoAlias) 1177 return false; 1178 else if (AA.alias(M->getRawDest(), CpySize, M->getRawSource(), CpySize) != 1179 AliasAnalysis::NoAlias) 1180 return false; 1181 else if (AA.alias(MDep->getRawDest(), DepSize, MDep->getRawSource(), DepSize) 1182 != AliasAnalysis::NoAlias) 1183 return false; 1184 1185 // If all checks passed, then we can transform these memcpy's 1186 Function* MemCpyFun = Intrinsic::getDeclaration( 1187 M->getParent()->getParent()->getParent(), 1188 M->getIntrinsicID()); 1189 1190 std::vector<Value*> args; 1191 args.push_back(M->getRawDest()); 1192 args.push_back(MDep->getRawSource()); 1193 args.push_back(M->getLength()); 1194 args.push_back(M->getAlignment()); 1195 1196 CallInst* C = new CallInst(MemCpyFun, args.begin(), args.end(), "", M); 1197 1198 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1199 if (MD.getDependency(C) == MDep) { 1200 MD.dropInstruction(M); 1201 toErase.push_back(M); 1202 return true; 1203 } else { 1204 MD.removeInstruction(C); 1205 toErase.push_back(C); 1206 return false; 1207 } 1208} 1209 1210/// processInstruction - When calculating availability, handle an instruction 1211/// by inserting it into the appropriate sets 1212bool GVN::processInstruction(Instruction* I, 1213 ValueNumberedSet& currAvail, 1214 DenseMap<Value*, LoadInst*>& lastSeenLoad, 1215 SmallVector<Instruction*, 4>& toErase) { 1216 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1217 return processLoad(L, lastSeenLoad, toErase); 1218 } else if (MemCpyInst* M = dyn_cast<MemCpyInst>(I)) { 1219 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1220 1221 // The are two possible optimizations we can do for memcpy: 1222 // a) memcpy-memcpy xform which exposes redundance for DSE 1223 // b) call-memcpy xform for sret return slot optimization 1224 Instruction* dep = MD.getDependency(M); 1225 if (dep == MemoryDependenceAnalysis::None || 1226 dep == MemoryDependenceAnalysis::NonLocal) 1227 return false; 1228 if (MemCpyInst *MemCpy = dyn_cast<MemCpyInst>(dep)) 1229 return processMemCpy(M, MemCpy, toErase); 1230 if (CallInst* C = dyn_cast<CallInst>(dep)) 1231 return performReturnSlotOptzn(M, C, toErase); 1232 return false; 1233 } 1234 1235 unsigned num = VN.lookup_or_add(I); 1236 1237 // Collapse PHI nodes 1238 if (PHINode* p = dyn_cast<PHINode>(I)) { 1239 Value* constVal = CollapsePhi(p); 1240 1241 if (constVal) { 1242 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1243 PI != PE; ++PI) 1244 if (PI->second.count(p)) 1245 PI->second.erase(p); 1246 1247 p->replaceAllUsesWith(constVal); 1248 toErase.push_back(p); 1249 } 1250 // Perform value-number based elimination 1251 } else if (currAvail.test(num)) { 1252 Value* repl = find_leader(currAvail, num); 1253 1254 if (CallInst* CI = dyn_cast<CallInst>(I)) { 1255 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 1256 if (!AA.doesNotAccessMemory(CI)) { 1257 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1258 if (cast<Instruction>(repl)->getParent() != CI->getParent() || 1259 MD.getDependency(CI) != MD.getDependency(cast<CallInst>(repl))) { 1260 // There must be an intervening may-alias store, so nothing from 1261 // this point on will be able to be replaced with the preceding call 1262 currAvail.erase(repl); 1263 currAvail.insert(I); 1264 1265 return false; 1266 } 1267 } 1268 } 1269 1270 // Remove it! 1271 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1272 MD.removeInstruction(I); 1273 1274 VN.erase(I); 1275 I->replaceAllUsesWith(repl); 1276 toErase.push_back(I); 1277 return true; 1278 } else if (!I->isTerminator()) { 1279 currAvail.set(num); 1280 currAvail.insert(I); 1281 } 1282 1283 return false; 1284} 1285 1286// GVN::runOnFunction - This is the main transformation entry point for a 1287// function. 1288// 1289bool GVN::runOnFunction(Function& F) { 1290 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1291 1292 bool changed = false; 1293 bool shouldContinue = true; 1294 1295 while (shouldContinue) { 1296 shouldContinue = iterateOnFunction(F); 1297 changed |= shouldContinue; 1298 } 1299 1300 return changed; 1301} 1302 1303 1304// GVN::iterateOnFunction - Executes one iteration of GVN 1305bool GVN::iterateOnFunction(Function &F) { 1306 // Clean out global sets from any previous functions 1307 VN.clear(); 1308 availableOut.clear(); 1309 phiMap.clear(); 1310 1311 bool changed_function = false; 1312 1313 DominatorTree &DT = getAnalysis<DominatorTree>(); 1314 1315 SmallVector<Instruction*, 4> toErase; 1316 1317 // Top-down walk of the dominator tree 1318 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 1319 E = df_end(DT.getRootNode()); DI != E; ++DI) { 1320 1321 // Get the set to update for this block 1322 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 1323 DenseMap<Value*, LoadInst*> lastSeenLoad; 1324 1325 BasicBlock* BB = DI->getBlock(); 1326 1327 // A block inherits AVAIL_OUT from its dominator 1328 if (DI->getIDom() != 0) 1329 currAvail = availableOut[DI->getIDom()->getBlock()]; 1330 1331 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1332 BI != BE; ) { 1333 changed_function |= processInstruction(BI, currAvail, 1334 lastSeenLoad, toErase); 1335 1336 NumGVNInstr += toErase.size(); 1337 1338 // Avoid iterator invalidation 1339 ++BI; 1340 1341 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1342 E = toErase.end(); I != E; ++I) { 1343 (*I)->eraseFromParent(); 1344 } 1345 1346 toErase.clear(); 1347 } 1348 } 1349 1350 return changed_function; 1351} 1352