GVN.cpp revision 1ad2cb75553a30bcec9fdc15733a20df6bc50431
1//===- GVN.cpp - Eliminate redundant values and loads ------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the Owen Anderson and is distributed under 6// the University of Illinois Open Source 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#include "llvm/Value.h" 17#include "llvm/Transforms/Scalar.h" 18#include "llvm/Instructions.h" 19#include "llvm/Function.h" 20#include "llvm/DerivedTypes.h" 21#include "llvm/Analysis/Dominators.h" 22#include "llvm/ADT/BitVector.h" 23#include "llvm/ADT/DenseMap.h" 24#include "llvm/ADT/DepthFirstIterator.h" 25#include "llvm/ADT/SmallPtrSet.h" 26#include "llvm/ADT/SmallVector.h" 27#include "llvm/ADT/Statistic.h" 28#include "llvm/Analysis/MemoryDependenceAnalysis.h" 29#include "llvm/Support/CFG.h" 30#include "llvm/Support/Compiler.h" 31using namespace llvm; 32 33//===----------------------------------------------------------------------===// 34// ValueTable Class 35//===----------------------------------------------------------------------===// 36 37/// This class holds the mapping between values and value numbers. It is used 38/// as an efficient mechanism to determine the expression-wise equivalence of 39/// two values. 40namespace { 41 struct VISIBILITY_HIDDEN Expression { 42 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 43 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 44 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 45 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 46 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 47 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 48 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 49 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 50 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 51 PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY, 52 TOMBSTONE }; 53 54 ExpressionOpcode opcode; 55 const Type* type; 56 uint32_t firstVN; 57 uint32_t secondVN; 58 uint32_t thirdVN; 59 SmallVector<uint32_t, 4> varargs; 60 61 Expression() { } 62 Expression(ExpressionOpcode o) : opcode(o) { } 63 64 bool operator==(const Expression &other) const { 65 if (opcode != other.opcode) 66 return false; 67 else if (opcode == EMPTY || opcode == TOMBSTONE) 68 return true; 69 else if (type != other.type) 70 return false; 71 else if (firstVN != other.firstVN) 72 return false; 73 else if (secondVN != other.secondVN) 74 return false; 75 else if (thirdVN != other.thirdVN) 76 return false; 77 else { 78 if (varargs.size() != other.varargs.size()) 79 return false; 80 81 for (size_t i = 0; i < varargs.size(); ++i) 82 if (varargs[i] != other.varargs[i]) 83 return false; 84 85 return true; 86 } 87 } 88 89 bool operator!=(const Expression &other) const { 90 if (opcode != other.opcode) 91 return true; 92 else if (opcode == EMPTY || opcode == TOMBSTONE) 93 return false; 94 else if (type != other.type) 95 return true; 96 else if (firstVN != other.firstVN) 97 return true; 98 else if (secondVN != other.secondVN) 99 return true; 100 else if (thirdVN != other.thirdVN) 101 return true; 102 else { 103 if (varargs.size() != other.varargs.size()) 104 return true; 105 106 for (size_t i = 0; i < varargs.size(); ++i) 107 if (varargs[i] != other.varargs[i]) 108 return true; 109 110 return false; 111 } 112 } 113 }; 114 115 class VISIBILITY_HIDDEN ValueTable { 116 private: 117 DenseMap<Value*, uint32_t> valueNumbering; 118 DenseMap<Expression, uint32_t> expressionNumbering; 119 120 uint32_t nextValueNumber; 121 122 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 123 Expression::ExpressionOpcode getOpcode(CmpInst* C); 124 Expression::ExpressionOpcode getOpcode(CastInst* C); 125 Expression create_expression(BinaryOperator* BO); 126 Expression create_expression(CmpInst* C); 127 Expression create_expression(ShuffleVectorInst* V); 128 Expression create_expression(ExtractElementInst* C); 129 Expression create_expression(InsertElementInst* V); 130 Expression create_expression(SelectInst* V); 131 Expression create_expression(CastInst* C); 132 Expression create_expression(GetElementPtrInst* G); 133 public: 134 ValueTable() { nextValueNumber = 1; } 135 uint32_t lookup_or_add(Value* V); 136 uint32_t lookup(Value* V) const; 137 void add(Value* V, uint32_t num); 138 void clear(); 139 void erase(Value* v); 140 unsigned size(); 141 }; 142} 143 144namespace llvm { 145template <> struct DenseMapKeyInfo<Expression> { 146 static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); } 147 static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); } 148 149 static unsigned getHashValue(const Expression e) { 150 unsigned hash = e.opcode; 151 152 hash = e.firstVN + hash * 37; 153 hash = e.secondVN + hash * 37; 154 hash = e.thirdVN + hash * 37; 155 156 hash = (unsigned)((uintptr_t)e.type >> 4) ^ 157 (unsigned)((uintptr_t)e.type >> 9) + 158 hash * 37; 159 160 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end(); 161 I != E; ++I) 162 hash = *I + hash * 37; 163 164 return hash; 165 } 166 static bool isPod() { return true; } 167}; 168} 169 170//===----------------------------------------------------------------------===// 171// ValueTable Internal Functions 172//===----------------------------------------------------------------------===// 173Expression::ExpressionOpcode 174 ValueTable::getOpcode(BinaryOperator* BO) { 175 switch(BO->getOpcode()) { 176 case Instruction::Add: 177 return Expression::ADD; 178 case Instruction::Sub: 179 return Expression::SUB; 180 case Instruction::Mul: 181 return Expression::MUL; 182 case Instruction::UDiv: 183 return Expression::UDIV; 184 case Instruction::SDiv: 185 return Expression::SDIV; 186 case Instruction::FDiv: 187 return Expression::FDIV; 188 case Instruction::URem: 189 return Expression::UREM; 190 case Instruction::SRem: 191 return Expression::SREM; 192 case Instruction::FRem: 193 return Expression::FREM; 194 case Instruction::Shl: 195 return Expression::SHL; 196 case Instruction::LShr: 197 return Expression::LSHR; 198 case Instruction::AShr: 199 return Expression::ASHR; 200 case Instruction::And: 201 return Expression::AND; 202 case Instruction::Or: 203 return Expression::OR; 204 case Instruction::Xor: 205 return Expression::XOR; 206 207 // THIS SHOULD NEVER HAPPEN 208 default: 209 assert(0 && "Binary operator with unknown opcode?"); 210 return Expression::ADD; 211 } 212} 213 214Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 215 if (C->getOpcode() == Instruction::ICmp) { 216 switch (C->getPredicate()) { 217 case ICmpInst::ICMP_EQ: 218 return Expression::ICMPEQ; 219 case ICmpInst::ICMP_NE: 220 return Expression::ICMPNE; 221 case ICmpInst::ICMP_UGT: 222 return Expression::ICMPUGT; 223 case ICmpInst::ICMP_UGE: 224 return Expression::ICMPUGE; 225 case ICmpInst::ICMP_ULT: 226 return Expression::ICMPULT; 227 case ICmpInst::ICMP_ULE: 228 return Expression::ICMPULE; 229 case ICmpInst::ICMP_SGT: 230 return Expression::ICMPSGT; 231 case ICmpInst::ICMP_SGE: 232 return Expression::ICMPSGE; 233 case ICmpInst::ICMP_SLT: 234 return Expression::ICMPSLT; 235 case ICmpInst::ICMP_SLE: 236 return Expression::ICMPSLE; 237 238 // THIS SHOULD NEVER HAPPEN 239 default: 240 assert(0 && "Comparison with unknown predicate?"); 241 return Expression::ICMPEQ; 242 } 243 } else { 244 switch (C->getPredicate()) { 245 case FCmpInst::FCMP_OEQ: 246 return Expression::FCMPOEQ; 247 case FCmpInst::FCMP_OGT: 248 return Expression::FCMPOGT; 249 case FCmpInst::FCMP_OGE: 250 return Expression::FCMPOGE; 251 case FCmpInst::FCMP_OLT: 252 return Expression::FCMPOLT; 253 case FCmpInst::FCMP_OLE: 254 return Expression::FCMPOLE; 255 case FCmpInst::FCMP_ONE: 256 return Expression::FCMPONE; 257 case FCmpInst::FCMP_ORD: 258 return Expression::FCMPORD; 259 case FCmpInst::FCMP_UNO: 260 return Expression::FCMPUNO; 261 case FCmpInst::FCMP_UEQ: 262 return Expression::FCMPUEQ; 263 case FCmpInst::FCMP_UGT: 264 return Expression::FCMPUGT; 265 case FCmpInst::FCMP_UGE: 266 return Expression::FCMPUGE; 267 case FCmpInst::FCMP_ULT: 268 return Expression::FCMPULT; 269 case FCmpInst::FCMP_ULE: 270 return Expression::FCMPULE; 271 case FCmpInst::FCMP_UNE: 272 return Expression::FCMPUNE; 273 274 // THIS SHOULD NEVER HAPPEN 275 default: 276 assert(0 && "Comparison with unknown predicate?"); 277 return Expression::FCMPOEQ; 278 } 279 } 280} 281 282Expression::ExpressionOpcode 283 ValueTable::getOpcode(CastInst* C) { 284 switch(C->getOpcode()) { 285 case Instruction::Trunc: 286 return Expression::TRUNC; 287 case Instruction::ZExt: 288 return Expression::ZEXT; 289 case Instruction::SExt: 290 return Expression::SEXT; 291 case Instruction::FPToUI: 292 return Expression::FPTOUI; 293 case Instruction::FPToSI: 294 return Expression::FPTOSI; 295 case Instruction::UIToFP: 296 return Expression::UITOFP; 297 case Instruction::SIToFP: 298 return Expression::SITOFP; 299 case Instruction::FPTrunc: 300 return Expression::FPTRUNC; 301 case Instruction::FPExt: 302 return Expression::FPEXT; 303 case Instruction::PtrToInt: 304 return Expression::PTRTOINT; 305 case Instruction::IntToPtr: 306 return Expression::INTTOPTR; 307 case Instruction::BitCast: 308 return Expression::BITCAST; 309 310 // THIS SHOULD NEVER HAPPEN 311 default: 312 assert(0 && "Cast operator with unknown opcode?"); 313 return Expression::BITCAST; 314 } 315} 316 317Expression ValueTable::create_expression(BinaryOperator* BO) { 318 Expression e; 319 320 e.firstVN = lookup_or_add(BO->getOperand(0)); 321 e.secondVN = lookup_or_add(BO->getOperand(1)); 322 e.thirdVN = 0; 323 e.type = BO->getType(); 324 e.opcode = getOpcode(BO); 325 326 return e; 327} 328 329Expression ValueTable::create_expression(CmpInst* C) { 330 Expression e; 331 332 e.firstVN = lookup_or_add(C->getOperand(0)); 333 e.secondVN = lookup_or_add(C->getOperand(1)); 334 e.thirdVN = 0; 335 e.type = C->getType(); 336 e.opcode = getOpcode(C); 337 338 return e; 339} 340 341Expression ValueTable::create_expression(CastInst* C) { 342 Expression e; 343 344 e.firstVN = lookup_or_add(C->getOperand(0)); 345 e.secondVN = 0; 346 e.thirdVN = 0; 347 e.type = C->getType(); 348 e.opcode = getOpcode(C); 349 350 return e; 351} 352 353Expression ValueTable::create_expression(ShuffleVectorInst* S) { 354 Expression e; 355 356 e.firstVN = lookup_or_add(S->getOperand(0)); 357 e.secondVN = lookup_or_add(S->getOperand(1)); 358 e.thirdVN = lookup_or_add(S->getOperand(2)); 359 e.type = S->getType(); 360 e.opcode = Expression::SHUFFLE; 361 362 return e; 363} 364 365Expression ValueTable::create_expression(ExtractElementInst* E) { 366 Expression e; 367 368 e.firstVN = lookup_or_add(E->getOperand(0)); 369 e.secondVN = lookup_or_add(E->getOperand(1)); 370 e.thirdVN = 0; 371 e.type = E->getType(); 372 e.opcode = Expression::EXTRACT; 373 374 return e; 375} 376 377Expression ValueTable::create_expression(InsertElementInst* I) { 378 Expression e; 379 380 e.firstVN = lookup_or_add(I->getOperand(0)); 381 e.secondVN = lookup_or_add(I->getOperand(1)); 382 e.thirdVN = lookup_or_add(I->getOperand(2)); 383 e.type = I->getType(); 384 e.opcode = Expression::INSERT; 385 386 return e; 387} 388 389Expression ValueTable::create_expression(SelectInst* I) { 390 Expression e; 391 392 e.firstVN = lookup_or_add(I->getCondition()); 393 e.secondVN = lookup_or_add(I->getTrueValue()); 394 e.thirdVN = lookup_or_add(I->getFalseValue()); 395 e.type = I->getType(); 396 e.opcode = Expression::SELECT; 397 398 return e; 399} 400 401Expression ValueTable::create_expression(GetElementPtrInst* G) { 402 Expression e; 403 404 e.firstVN = lookup_or_add(G->getPointerOperand()); 405 e.secondVN = 0; 406 e.thirdVN = 0; 407 e.type = G->getType(); 408 e.opcode = Expression::GEP; 409 410 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 411 I != E; ++I) 412 e.varargs.push_back(lookup_or_add(*I)); 413 414 return e; 415} 416 417//===----------------------------------------------------------------------===// 418// ValueTable External Functions 419//===----------------------------------------------------------------------===// 420 421/// lookup_or_add - Returns the value number for the specified value, assigning 422/// it a new number if it did not have one before. 423uint32_t ValueTable::lookup_or_add(Value* V) { 424 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 425 if (VI != valueNumbering.end()) 426 return VI->second; 427 428 429 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 430 Expression e = create_expression(BO); 431 432 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 433 if (EI != expressionNumbering.end()) { 434 valueNumbering.insert(std::make_pair(V, EI->second)); 435 return EI->second; 436 } else { 437 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 438 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 439 440 return nextValueNumber++; 441 } 442 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 443 Expression e = create_expression(C); 444 445 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 446 if (EI != expressionNumbering.end()) { 447 valueNumbering.insert(std::make_pair(V, EI->second)); 448 return EI->second; 449 } else { 450 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 451 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 452 453 return nextValueNumber++; 454 } 455 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 456 Expression e = create_expression(U); 457 458 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 459 if (EI != expressionNumbering.end()) { 460 valueNumbering.insert(std::make_pair(V, EI->second)); 461 return EI->second; 462 } else { 463 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 464 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 465 466 return nextValueNumber++; 467 } 468 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 469 Expression e = create_expression(U); 470 471 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 472 if (EI != expressionNumbering.end()) { 473 valueNumbering.insert(std::make_pair(V, EI->second)); 474 return EI->second; 475 } else { 476 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 477 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 478 479 return nextValueNumber++; 480 } 481 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 482 Expression e = create_expression(U); 483 484 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 485 if (EI != expressionNumbering.end()) { 486 valueNumbering.insert(std::make_pair(V, EI->second)); 487 return EI->second; 488 } else { 489 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 490 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 491 492 return nextValueNumber++; 493 } 494 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 495 Expression e = create_expression(U); 496 497 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 498 if (EI != expressionNumbering.end()) { 499 valueNumbering.insert(std::make_pair(V, EI->second)); 500 return EI->second; 501 } else { 502 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 503 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 504 505 return nextValueNumber++; 506 } 507 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 508 Expression e = create_expression(U); 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 (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 521 Expression e = create_expression(U); 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 { 534 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 535 return nextValueNumber++; 536 } 537} 538 539/// lookup - Returns the value number of the specified value. Fails if 540/// the value has not yet been numbered. 541uint32_t ValueTable::lookup(Value* V) const { 542 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 543 if (VI != valueNumbering.end()) 544 return VI->second; 545 else 546 assert(0 && "Value not numbered?"); 547 548 return 0; 549} 550 551/// clear - Remove all entries from the ValueTable 552void ValueTable::clear() { 553 valueNumbering.clear(); 554 expressionNumbering.clear(); 555 nextValueNumber = 1; 556} 557 558//===----------------------------------------------------------------------===// 559// ValueNumberedSet Class 560//===----------------------------------------------------------------------===// 561namespace { 562class ValueNumberedSet { 563 private: 564 SmallPtrSet<Value*, 8> contents; 565 BitVector numbers; 566 public: 567 ValueNumberedSet() { numbers.resize(1); } 568 ValueNumberedSet(const ValueNumberedSet& other) { 569 numbers = other.numbers; 570 contents = other.contents; 571 } 572 573 typedef SmallPtrSet<Value*, 8>::iterator iterator; 574 575 iterator begin() { return contents.begin(); } 576 iterator end() { return contents.end(); } 577 578 bool insert(Value* v) { return contents.insert(v); } 579 void insert(iterator I, iterator E) { contents.insert(I, E); } 580 void erase(Value* v) { contents.erase(v); } 581 unsigned count(Value* v) { return contents.count(v); } 582 size_t size() { return contents.size(); } 583 584 void set(unsigned i) { 585 if (i >= numbers.size()) 586 numbers.resize(i+1); 587 588 numbers.set(i); 589 } 590 591 void operator=(const ValueNumberedSet& other) { 592 contents = other.contents; 593 numbers = other.numbers; 594 } 595 596 void reset(unsigned i) { 597 if (i < numbers.size()) 598 numbers.reset(i); 599 } 600 601 bool test(unsigned i) { 602 if (i >= numbers.size()) 603 return false; 604 605 return numbers.test(i); 606 } 607 608 void clear() { 609 contents.clear(); 610 numbers.clear(); 611 } 612}; 613} 614 615//===----------------------------------------------------------------------===// 616// GVN Pass 617//===----------------------------------------------------------------------===// 618 619namespace { 620 621 class VISIBILITY_HIDDEN GVN : public FunctionPass { 622 bool runOnFunction(Function &F); 623 public: 624 static char ID; // Pass identification, replacement for typeid 625 GVN() : FunctionPass((intptr_t)&ID) { } 626 627 private: 628 ValueTable VN; 629 630 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 631 632 // This transformation requires dominator postdominator info 633 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 634 AU.setPreservesCFG(); 635 AU.addRequired<DominatorTree>(); 636 AU.addRequired<MemoryDependenceAnalysis>(); 637 AU.addPreserved<MemoryDependenceAnalysis>(); 638 } 639 640 // Helper fuctions 641 // FIXME: eliminate or document these better 642 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 643 void val_insert(ValueNumberedSet& s, Value* v); 644 bool processLoad(LoadInst* L, 645 DenseMap<Value*, LoadInst*>& lastLoad, 646 SmallVector<Instruction*, 4>& toErase); 647 bool processInstruction(Instruction* I, 648 ValueNumberedSet& currAvail, 649 DenseMap<Value*, LoadInst*>& lastSeenLoad, 650 SmallVector<Instruction*, 4>& toErase); 651 }; 652 653 char GVN::ID = 0; 654 655} 656 657// createGVNPass - The public interface to this file... 658FunctionPass *llvm::createGVNPass() { return new GVN(); } 659 660static RegisterPass<GVN> X("gvn", 661 "Global Value Numbering"); 662 663STATISTIC(NumGVNInstr, "Number of instructions deleted"); 664STATISTIC(NumGVNLoad, "Number of loads deleted"); 665 666/// find_leader - Given a set and a value number, return the first 667/// element of the set with that value number, or 0 if no such element 668/// is present 669Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 670 if (!vals.test(v)) 671 return 0; 672 673 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 674 I != E; ++I) 675 if (v == VN.lookup(*I)) 676 return *I; 677 678 assert(0 && "No leader found, but present bit is set?"); 679 return 0; 680} 681 682/// val_insert - Insert a value into a set only if there is not a value 683/// with the same value number already in the set 684void GVN::val_insert(ValueNumberedSet& s, Value* v) { 685 uint32_t num = VN.lookup(v); 686 if (!s.test(num)) 687 s.insert(v); 688} 689 690bool GVN::processLoad(LoadInst* L, 691 DenseMap<Value*, LoadInst*>& lastLoad, 692 SmallVector<Instruction*, 4>& toErase) { 693 if (L->isVolatile()) { 694 lastLoad[L->getPointerOperand()] = L; 695 return false; 696 } 697 698 Value* pointer = L->getPointerOperand(); 699 LoadInst*& last = lastLoad[pointer]; 700 701 // ... to a pointer that has been loaded from before... 702 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 703 Instruction* dep = MD.getDependency(L); 704 bool deletedLoad = false; 705 706 while (dep != MemoryDependenceAnalysis::None && 707 dep != MemoryDependenceAnalysis::NonLocal && 708 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 709 // ... that depends on a store ... 710 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 711 if (S->getPointerOperand() == pointer) { 712 // Remove it! 713 MD.removeInstruction(L); 714 715 L->replaceAllUsesWith(S->getOperand(0)); 716 toErase.push_back(L); 717 deletedLoad = true; 718 NumGVNLoad++; 719 } 720 721 // Whether we removed it or not, we can't 722 // go any further 723 break; 724 } else if (!last) { 725 // If we don't depend on a store, and we haven't 726 // been loaded before, bail. 727 break; 728 } else if (dep == last) { 729 // Remove it! 730 MD.removeInstruction(L); 731 732 L->replaceAllUsesWith(last); 733 toErase.push_back(L); 734 deletedLoad = true; 735 NumGVNLoad++; 736 737 break; 738 } else { 739 dep = MD.getDependency(L, dep); 740 } 741 } 742 743 if (!deletedLoad) 744 last = L; 745 746 return deletedLoad; 747} 748 749/// buildsets_availout - When calculating availability, handle an instruction 750/// by inserting it into the appropriate sets 751bool GVN::processInstruction(Instruction* I, 752 ValueNumberedSet& currAvail, 753 DenseMap<Value*, LoadInst*>& lastSeenLoad, 754 SmallVector<Instruction*, 4>& toErase) { 755 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 756 return processLoad(L, lastSeenLoad, toErase); 757 } 758 759 unsigned num = VN.lookup_or_add(I); 760 761 if (currAvail.test(num)) { 762 Value* repl = find_leader(currAvail, num); 763 764 I->replaceAllUsesWith(repl); 765 toErase.push_back(I); 766 return true; 767 } else if (!I->isTerminator()) { 768 currAvail.set(num); 769 currAvail.insert(I); 770 } 771 772 return false; 773} 774 775// GVN::runOnFunction - This is the main transformation entry point for a 776// function. 777// 778bool GVN::runOnFunction(Function &F) { 779 // Clean out global sets from any previous functions 780 VN.clear(); 781 availableOut.clear(); 782 783 bool changed_function = false; 784 785 DominatorTree &DT = getAnalysis<DominatorTree>(); 786 787 SmallVector<Instruction*, 4> toErase; 788 789 // Top-down walk of the dominator tree 790 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 791 E = df_end(DT.getRootNode()); DI != E; ++DI) { 792 793 // Get the set to update for this block 794 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 795 DenseMap<Value*, LoadInst*> lastSeenLoad; 796 797 BasicBlock* BB = DI->getBlock(); 798 799 // A block inherits AVAIL_OUT from its dominator 800 if (DI->getIDom() != 0) 801 currAvail = availableOut[DI->getIDom()->getBlock()]; 802 803 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 804 BI != BE; ++BI) { 805 processInstruction(BI, currAvail, lastSeenLoad, toErase); 806 } 807 } 808 809 NumGVNInstr = toErase.size(); 810 811 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 812 E = toErase.end(); I != E; ++I) 813 (*I)->eraseFromParent(); 814 815 return changed_function; 816} 817