GVN.cpp revision 62bc33c954591039fa134fa251d570a2032cfa74
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 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/Instructions.h" 23#include "llvm/Value.h" 24#include "llvm/Analysis/Dominators.h" 25#include "llvm/ADT/BitVector.h" 26#include "llvm/ADT/DenseMap.h" 27#include "llvm/ADT/DepthFirstIterator.h" 28#include "llvm/ADT/SmallPtrSet.h" 29#include "llvm/ADT/SmallVector.h" 30#include "llvm/ADT/Statistic.h" 31#include "llvm/Analysis/MemoryDependenceAnalysis.h" 32#include "llvm/Support/CFG.h" 33#include "llvm/Support/Compiler.h" 34using namespace llvm; 35 36//===----------------------------------------------------------------------===// 37// ValueTable Class 38//===----------------------------------------------------------------------===// 39 40/// This class holds the mapping between values and value numbers. It is used 41/// as an efficient mechanism to determine the expression-wise equivalence of 42/// two values. 43namespace { 44 struct VISIBILITY_HIDDEN Expression { 45 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 46 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 47 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 48 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 49 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 50 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 51 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 52 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 53 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 54 PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY, 55 TOMBSTONE }; 56 57 ExpressionOpcode opcode; 58 const Type* type; 59 uint32_t firstVN; 60 uint32_t secondVN; 61 uint32_t thirdVN; 62 SmallVector<uint32_t, 4> varargs; 63 64 Expression() { } 65 Expression(ExpressionOpcode o) : opcode(o) { } 66 67 bool operator==(const Expression &other) const { 68 if (opcode != other.opcode) 69 return false; 70 else if (opcode == EMPTY || opcode == TOMBSTONE) 71 return true; 72 else if (type != other.type) 73 return false; 74 else if (firstVN != other.firstVN) 75 return false; 76 else if (secondVN != other.secondVN) 77 return false; 78 else if (thirdVN != other.thirdVN) 79 return false; 80 else { 81 if (varargs.size() != other.varargs.size()) 82 return false; 83 84 for (size_t i = 0; i < varargs.size(); ++i) 85 if (varargs[i] != other.varargs[i]) 86 return false; 87 88 return true; 89 } 90 } 91 92 bool operator!=(const Expression &other) const { 93 if (opcode != other.opcode) 94 return true; 95 else if (opcode == EMPTY || opcode == TOMBSTONE) 96 return false; 97 else if (type != other.type) 98 return true; 99 else if (firstVN != other.firstVN) 100 return true; 101 else if (secondVN != other.secondVN) 102 return true; 103 else if (thirdVN != other.thirdVN) 104 return true; 105 else { 106 if (varargs.size() != other.varargs.size()) 107 return true; 108 109 for (size_t i = 0; i < varargs.size(); ++i) 110 if (varargs[i] != other.varargs[i]) 111 return true; 112 113 return false; 114 } 115 } 116 }; 117 118 class VISIBILITY_HIDDEN ValueTable { 119 private: 120 DenseMap<Value*, uint32_t> valueNumbering; 121 DenseMap<Expression, uint32_t> expressionNumbering; 122 123 uint32_t nextValueNumber; 124 125 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 126 Expression::ExpressionOpcode getOpcode(CmpInst* C); 127 Expression::ExpressionOpcode getOpcode(CastInst* C); 128 Expression create_expression(BinaryOperator* BO); 129 Expression create_expression(CmpInst* C); 130 Expression create_expression(ShuffleVectorInst* V); 131 Expression create_expression(ExtractElementInst* C); 132 Expression create_expression(InsertElementInst* V); 133 Expression create_expression(SelectInst* V); 134 Expression create_expression(CastInst* C); 135 Expression create_expression(GetElementPtrInst* G); 136 public: 137 ValueTable() { nextValueNumber = 1; } 138 uint32_t lookup_or_add(Value* V); 139 uint32_t lookup(Value* V) const; 140 void add(Value* V, uint32_t num); 141 void clear(); 142 void erase(Value* v); 143 unsigned size(); 144 }; 145} 146 147namespace llvm { 148template <> struct DenseMapKeyInfo<Expression> { 149 static inline Expression getEmptyKey() { 150 return Expression(Expression::EMPTY); 151 } 152 153 static inline Expression getTombstoneKey() { 154 return Expression(Expression::TOMBSTONE); 155 } 156 157 static unsigned getHashValue(const Expression e) { 158 unsigned hash = e.opcode; 159 160 hash = e.firstVN + hash * 37; 161 hash = e.secondVN + hash * 37; 162 hash = e.thirdVN + hash * 37; 163 164 hash = (unsigned)((uintptr_t)e.type >> 4) ^ 165 (unsigned)((uintptr_t)e.type >> 9) + 166 hash * 37; 167 168 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 169 E = e.varargs.end(); I != E; ++I) 170 hash = *I + hash * 37; 171 172 return hash; 173 } 174 static bool isPod() { return true; } 175}; 176} 177 178//===----------------------------------------------------------------------===// 179// ValueTable Internal Functions 180//===----------------------------------------------------------------------===// 181Expression::ExpressionOpcode 182 ValueTable::getOpcode(BinaryOperator* BO) { 183 switch(BO->getOpcode()) { 184 case Instruction::Add: 185 return Expression::ADD; 186 case Instruction::Sub: 187 return Expression::SUB; 188 case Instruction::Mul: 189 return Expression::MUL; 190 case Instruction::UDiv: 191 return Expression::UDIV; 192 case Instruction::SDiv: 193 return Expression::SDIV; 194 case Instruction::FDiv: 195 return Expression::FDIV; 196 case Instruction::URem: 197 return Expression::UREM; 198 case Instruction::SRem: 199 return Expression::SREM; 200 case Instruction::FRem: 201 return Expression::FREM; 202 case Instruction::Shl: 203 return Expression::SHL; 204 case Instruction::LShr: 205 return Expression::LSHR; 206 case Instruction::AShr: 207 return Expression::ASHR; 208 case Instruction::And: 209 return Expression::AND; 210 case Instruction::Or: 211 return Expression::OR; 212 case Instruction::Xor: 213 return Expression::XOR; 214 215 // THIS SHOULD NEVER HAPPEN 216 default: 217 assert(0 && "Binary operator with unknown opcode?"); 218 return Expression::ADD; 219 } 220} 221 222Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 223 if (C->getOpcode() == Instruction::ICmp) { 224 switch (C->getPredicate()) { 225 case ICmpInst::ICMP_EQ: 226 return Expression::ICMPEQ; 227 case ICmpInst::ICMP_NE: 228 return Expression::ICMPNE; 229 case ICmpInst::ICMP_UGT: 230 return Expression::ICMPUGT; 231 case ICmpInst::ICMP_UGE: 232 return Expression::ICMPUGE; 233 case ICmpInst::ICMP_ULT: 234 return Expression::ICMPULT; 235 case ICmpInst::ICMP_ULE: 236 return Expression::ICMPULE; 237 case ICmpInst::ICMP_SGT: 238 return Expression::ICMPSGT; 239 case ICmpInst::ICMP_SGE: 240 return Expression::ICMPSGE; 241 case ICmpInst::ICMP_SLT: 242 return Expression::ICMPSLT; 243 case ICmpInst::ICMP_SLE: 244 return Expression::ICMPSLE; 245 246 // THIS SHOULD NEVER HAPPEN 247 default: 248 assert(0 && "Comparison with unknown predicate?"); 249 return Expression::ICMPEQ; 250 } 251 } else { 252 switch (C->getPredicate()) { 253 case FCmpInst::FCMP_OEQ: 254 return Expression::FCMPOEQ; 255 case FCmpInst::FCMP_OGT: 256 return Expression::FCMPOGT; 257 case FCmpInst::FCMP_OGE: 258 return Expression::FCMPOGE; 259 case FCmpInst::FCMP_OLT: 260 return Expression::FCMPOLT; 261 case FCmpInst::FCMP_OLE: 262 return Expression::FCMPOLE; 263 case FCmpInst::FCMP_ONE: 264 return Expression::FCMPONE; 265 case FCmpInst::FCMP_ORD: 266 return Expression::FCMPORD; 267 case FCmpInst::FCMP_UNO: 268 return Expression::FCMPUNO; 269 case FCmpInst::FCMP_UEQ: 270 return Expression::FCMPUEQ; 271 case FCmpInst::FCMP_UGT: 272 return Expression::FCMPUGT; 273 case FCmpInst::FCMP_UGE: 274 return Expression::FCMPUGE; 275 case FCmpInst::FCMP_ULT: 276 return Expression::FCMPULT; 277 case FCmpInst::FCMP_ULE: 278 return Expression::FCMPULE; 279 case FCmpInst::FCMP_UNE: 280 return Expression::FCMPUNE; 281 282 // THIS SHOULD NEVER HAPPEN 283 default: 284 assert(0 && "Comparison with unknown predicate?"); 285 return Expression::FCMPOEQ; 286 } 287 } 288} 289 290Expression::ExpressionOpcode 291 ValueTable::getOpcode(CastInst* C) { 292 switch(C->getOpcode()) { 293 case Instruction::Trunc: 294 return Expression::TRUNC; 295 case Instruction::ZExt: 296 return Expression::ZEXT; 297 case Instruction::SExt: 298 return Expression::SEXT; 299 case Instruction::FPToUI: 300 return Expression::FPTOUI; 301 case Instruction::FPToSI: 302 return Expression::FPTOSI; 303 case Instruction::UIToFP: 304 return Expression::UITOFP; 305 case Instruction::SIToFP: 306 return Expression::SITOFP; 307 case Instruction::FPTrunc: 308 return Expression::FPTRUNC; 309 case Instruction::FPExt: 310 return Expression::FPEXT; 311 case Instruction::PtrToInt: 312 return Expression::PTRTOINT; 313 case Instruction::IntToPtr: 314 return Expression::INTTOPTR; 315 case Instruction::BitCast: 316 return Expression::BITCAST; 317 318 // THIS SHOULD NEVER HAPPEN 319 default: 320 assert(0 && "Cast operator with unknown opcode?"); 321 return Expression::BITCAST; 322 } 323} 324 325Expression ValueTable::create_expression(BinaryOperator* BO) { 326 Expression e; 327 328 e.firstVN = lookup_or_add(BO->getOperand(0)); 329 e.secondVN = lookup_or_add(BO->getOperand(1)); 330 e.thirdVN = 0; 331 e.type = BO->getType(); 332 e.opcode = getOpcode(BO); 333 334 return e; 335} 336 337Expression ValueTable::create_expression(CmpInst* C) { 338 Expression e; 339 340 e.firstVN = lookup_or_add(C->getOperand(0)); 341 e.secondVN = lookup_or_add(C->getOperand(1)); 342 e.thirdVN = 0; 343 e.type = C->getType(); 344 e.opcode = getOpcode(C); 345 346 return e; 347} 348 349Expression ValueTable::create_expression(CastInst* C) { 350 Expression e; 351 352 e.firstVN = lookup_or_add(C->getOperand(0)); 353 e.secondVN = 0; 354 e.thirdVN = 0; 355 e.type = C->getType(); 356 e.opcode = getOpcode(C); 357 358 return e; 359} 360 361Expression ValueTable::create_expression(ShuffleVectorInst* S) { 362 Expression e; 363 364 e.firstVN = lookup_or_add(S->getOperand(0)); 365 e.secondVN = lookup_or_add(S->getOperand(1)); 366 e.thirdVN = lookup_or_add(S->getOperand(2)); 367 e.type = S->getType(); 368 e.opcode = Expression::SHUFFLE; 369 370 return e; 371} 372 373Expression ValueTable::create_expression(ExtractElementInst* E) { 374 Expression e; 375 376 e.firstVN = lookup_or_add(E->getOperand(0)); 377 e.secondVN = lookup_or_add(E->getOperand(1)); 378 e.thirdVN = 0; 379 e.type = E->getType(); 380 e.opcode = Expression::EXTRACT; 381 382 return e; 383} 384 385Expression ValueTable::create_expression(InsertElementInst* I) { 386 Expression e; 387 388 e.firstVN = lookup_or_add(I->getOperand(0)); 389 e.secondVN = lookup_or_add(I->getOperand(1)); 390 e.thirdVN = lookup_or_add(I->getOperand(2)); 391 e.type = I->getType(); 392 e.opcode = Expression::INSERT; 393 394 return e; 395} 396 397Expression ValueTable::create_expression(SelectInst* I) { 398 Expression e; 399 400 e.firstVN = lookup_or_add(I->getCondition()); 401 e.secondVN = lookup_or_add(I->getTrueValue()); 402 e.thirdVN = lookup_or_add(I->getFalseValue()); 403 e.type = I->getType(); 404 e.opcode = Expression::SELECT; 405 406 return e; 407} 408 409Expression ValueTable::create_expression(GetElementPtrInst* G) { 410 Expression e; 411 412 e.firstVN = lookup_or_add(G->getPointerOperand()); 413 e.secondVN = 0; 414 e.thirdVN = 0; 415 e.type = G->getType(); 416 e.opcode = Expression::GEP; 417 418 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 419 I != E; ++I) 420 e.varargs.push_back(lookup_or_add(*I)); 421 422 return e; 423} 424 425//===----------------------------------------------------------------------===// 426// ValueTable External Functions 427//===----------------------------------------------------------------------===// 428 429/// lookup_or_add - Returns the value number for the specified value, assigning 430/// it a new number if it did not have one before. 431uint32_t ValueTable::lookup_or_add(Value* V) { 432 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 433 if (VI != valueNumbering.end()) 434 return VI->second; 435 436 437 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 438 Expression e = create_expression(BO); 439 440 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 441 if (EI != expressionNumbering.end()) { 442 valueNumbering.insert(std::make_pair(V, EI->second)); 443 return EI->second; 444 } else { 445 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 446 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 447 448 return nextValueNumber++; 449 } 450 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 451 Expression e = create_expression(C); 452 453 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 454 if (EI != expressionNumbering.end()) { 455 valueNumbering.insert(std::make_pair(V, EI->second)); 456 return EI->second; 457 } else { 458 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 459 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 460 461 return nextValueNumber++; 462 } 463 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 464 Expression e = create_expression(U); 465 466 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 467 if (EI != expressionNumbering.end()) { 468 valueNumbering.insert(std::make_pair(V, EI->second)); 469 return EI->second; 470 } else { 471 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 472 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 473 474 return nextValueNumber++; 475 } 476 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 477 Expression e = create_expression(U); 478 479 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 480 if (EI != expressionNumbering.end()) { 481 valueNumbering.insert(std::make_pair(V, EI->second)); 482 return EI->second; 483 } else { 484 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 485 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 486 487 return nextValueNumber++; 488 } 489 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 490 Expression e = create_expression(U); 491 492 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 493 if (EI != expressionNumbering.end()) { 494 valueNumbering.insert(std::make_pair(V, EI->second)); 495 return EI->second; 496 } else { 497 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 498 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 499 500 return nextValueNumber++; 501 } 502 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 503 Expression e = create_expression(U); 504 505 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 506 if (EI != expressionNumbering.end()) { 507 valueNumbering.insert(std::make_pair(V, EI->second)); 508 return EI->second; 509 } else { 510 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 511 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 512 513 return nextValueNumber++; 514 } 515 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 516 Expression e = create_expression(U); 517 518 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 519 if (EI != expressionNumbering.end()) { 520 valueNumbering.insert(std::make_pair(V, EI->second)); 521 return EI->second; 522 } else { 523 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 524 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 525 526 return nextValueNumber++; 527 } 528 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 529 Expression e = create_expression(U); 530 531 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 532 if (EI != expressionNumbering.end()) { 533 valueNumbering.insert(std::make_pair(V, EI->second)); 534 return EI->second; 535 } else { 536 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 537 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 538 539 return nextValueNumber++; 540 } 541 } else { 542 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 543 return nextValueNumber++; 544 } 545} 546 547/// lookup - Returns the value number of the specified value. Fails if 548/// the value has not yet been numbered. 549uint32_t ValueTable::lookup(Value* V) const { 550 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 551 if (VI != valueNumbering.end()) 552 return VI->second; 553 else 554 assert(0 && "Value not numbered?"); 555 556 return 0; 557} 558 559/// clear - Remove all entries from the ValueTable 560void ValueTable::clear() { 561 valueNumbering.clear(); 562 expressionNumbering.clear(); 563 nextValueNumber = 1; 564} 565 566/// erase - Remove a value from the value numbering 567void ValueTable::erase(Value* V) { 568 valueNumbering.erase(V); 569} 570 571//===----------------------------------------------------------------------===// 572// ValueNumberedSet Class 573//===----------------------------------------------------------------------===// 574namespace { 575class ValueNumberedSet { 576 private: 577 SmallPtrSet<Value*, 8> contents; 578 BitVector numbers; 579 public: 580 ValueNumberedSet() { numbers.resize(1); } 581 ValueNumberedSet(const ValueNumberedSet& other) { 582 numbers = other.numbers; 583 contents = other.contents; 584 } 585 586 typedef SmallPtrSet<Value*, 8>::iterator iterator; 587 588 iterator begin() { return contents.begin(); } 589 iterator end() { return contents.end(); } 590 591 bool insert(Value* v) { return contents.insert(v); } 592 void insert(iterator I, iterator E) { contents.insert(I, E); } 593 void erase(Value* v) { contents.erase(v); } 594 unsigned count(Value* v) { return contents.count(v); } 595 size_t size() { return contents.size(); } 596 597 void set(unsigned i) { 598 if (i >= numbers.size()) 599 numbers.resize(i+1); 600 601 numbers.set(i); 602 } 603 604 void operator=(const ValueNumberedSet& other) { 605 contents = other.contents; 606 numbers = other.numbers; 607 } 608 609 void reset(unsigned i) { 610 if (i < numbers.size()) 611 numbers.reset(i); 612 } 613 614 bool test(unsigned i) { 615 if (i >= numbers.size()) 616 return false; 617 618 return numbers.test(i); 619 } 620 621 void clear() { 622 contents.clear(); 623 numbers.clear(); 624 } 625}; 626} 627 628//===----------------------------------------------------------------------===// 629// GVN Pass 630//===----------------------------------------------------------------------===// 631 632namespace { 633 634 class VISIBILITY_HIDDEN GVN : public FunctionPass { 635 bool runOnFunction(Function &F); 636 public: 637 static char ID; // Pass identification, replacement for typeid 638 GVN() : FunctionPass((intptr_t)&ID) { } 639 640 private: 641 ValueTable VN; 642 643 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 644 645 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 646 PhiMapType phiMap; 647 648 649 // This transformation requires dominator postdominator info 650 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 651 AU.setPreservesCFG(); 652 AU.addRequired<DominatorTree>(); 653 AU.addRequired<MemoryDependenceAnalysis>(); 654 AU.addPreserved<MemoryDependenceAnalysis>(); 655 } 656 657 // Helper fuctions 658 // FIXME: eliminate or document these better 659 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 660 void val_insert(ValueNumberedSet& s, Value* v); 661 bool processLoad(LoadInst* L, 662 DenseMap<Value*, LoadInst*>& lastLoad, 663 SmallVector<Instruction*, 4>& toErase); 664 bool processInstruction(Instruction* I, 665 ValueNumberedSet& currAvail, 666 DenseMap<Value*, LoadInst*>& lastSeenLoad, 667 SmallVector<Instruction*, 4>& toErase); 668 bool processNonLocalLoad(LoadInst* L, 669 SmallVector<Instruction*, 4>& toErase); 670 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 671 DenseMap<BasicBlock*, Value*> &Phis, 672 bool top_level = false); 673 void dump(DenseMap<BasicBlock*, Value*>& d); 674 bool iterateOnFunction(Function &F); 675 }; 676 677 char GVN::ID = 0; 678 679} 680 681// createGVNPass - The public interface to this file... 682FunctionPass *llvm::createGVNPass() { return new GVN(); } 683 684static RegisterPass<GVN> X("gvn", 685 "Global Value Numbering"); 686 687STATISTIC(NumGVNInstr, "Number of instructions deleted"); 688STATISTIC(NumGVNLoad, "Number of loads deleted"); 689 690/// find_leader - Given a set and a value number, return the first 691/// element of the set with that value number, or 0 if no such element 692/// is present 693Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 694 if (!vals.test(v)) 695 return 0; 696 697 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 698 I != E; ++I) 699 if (v == VN.lookup(*I)) 700 return *I; 701 702 assert(0 && "No leader found, but present bit is set?"); 703 return 0; 704} 705 706/// val_insert - Insert a value into a set only if there is not a value 707/// with the same value number already in the set 708void GVN::val_insert(ValueNumberedSet& s, Value* v) { 709 uint32_t num = VN.lookup(v); 710 if (!s.test(num)) 711 s.insert(v); 712} 713 714void GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 715 printf("{\n"); 716 for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 717 E = d.end(); I != E; ++I) { 718 if (I->second == MemoryDependenceAnalysis::None) 719 printf("None\n"); 720 else 721 I->second->dump(); 722 } 723 printf("}\n"); 724} 725 726 727/// GetValueForBlock - Get the value to use within the specified basic block. 728/// available values are in Phis. 729Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 730 DenseMap<BasicBlock*, Value*> &Phis, 731 bool top_level) { 732 733 // If we have already computed this value, return the previously computed val. 734 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 735 if (V != Phis.end() && !top_level) return V->second; 736 737 BasicBlock* singlePred = BB->getSinglePredecessor(); 738 if (singlePred) { 739 Value *ret = GetValueForBlock(singlePred, orig, Phis); 740 Phis[BB] = ret; 741 return ret; 742 } 743 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 744 // now, then get values to fill in the incoming values for the PHI. 745 PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", 746 BB->begin()); 747 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 748 749 if (Phis.count(BB) == 0) 750 Phis.insert(std::make_pair(BB, PN)); 751 752 // Fill in the incoming values for the block. 753 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 754 Value* val = GetValueForBlock(*PI, orig, Phis); 755 756 PN->addIncoming(val, *PI); 757 } 758 759 // Attempt to collapse PHI nodes that are trivially redundant 760 Value* v = PN->hasConstantValue(); 761 if (v) { 762 if (Instruction* inst = dyn_cast<Instruction>(v)) { 763 DominatorTree &DT = getAnalysis<DominatorTree>(); 764 if (DT.dominates(inst, PN)) { 765 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 766 767 MD.removeInstruction(PN); 768 PN->replaceAllUsesWith(inst); 769 770 SmallVector<BasicBlock*, 4> toRemove; 771 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 772 E = Phis.end(); I != E; ++I) 773 if (I->second == PN) 774 toRemove.push_back(I->first); 775 for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(), 776 E= toRemove.end(); I != E; ++I) 777 Phis[*I] = inst; 778 779 PN->eraseFromParent(); 780 781 Phis[BB] = inst; 782 783 return inst; 784 } 785 } else { 786 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 787 788 MD.removeInstruction(PN); 789 PN->replaceAllUsesWith(v); 790 791 SmallVector<BasicBlock*, 4> toRemove; 792 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 793 E = Phis.end(); I != E; ++I) 794 if (I->second == PN) 795 toRemove.push_back(I->first); 796 for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(), 797 E= toRemove.end(); I != E; ++I) 798 Phis[*I] = v; 799 800 PN->eraseFromParent(); 801 802 Phis[BB] = v; 803 804 return v; 805 } 806 } 807 808 // Cache our phi construction results 809 phiMap[orig->getPointerOperand()].insert(PN); 810 return PN; 811} 812 813/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 814/// non-local by performing PHI construction. 815bool GVN::processNonLocalLoad(LoadInst* L, 816 SmallVector<Instruction*, 4>& toErase) { 817 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 818 819 // Find the non-local dependencies of the load 820 DenseMap<BasicBlock*, Value*> deps; 821 MD.getNonLocalDependency(L, deps); 822 823 DenseMap<BasicBlock*, Value*> repl; 824 825 // Filter out useless results (non-locals, etc) 826 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 827 I != E; ++I) 828 if (I->second == MemoryDependenceAnalysis::None) { 829 return false; 830 } else if (I->second == MemoryDependenceAnalysis::NonLocal) { 831 continue; 832 }else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 833 if (S->getPointerOperand() == L->getPointerOperand()) 834 repl[I->first] = S->getOperand(0); 835 else 836 return false; 837 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 838 if (LD->getPointerOperand() == L->getPointerOperand()) 839 repl[I->first] = LD; 840 else 841 return false; 842 } else { 843 return false; 844 } 845 846 // Use cached PHI construction information from previous runs 847 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 848 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 849 I != E; ++I) { 850 if ((*I)->getParent() == L->getParent()) { 851 MD.removeInstruction(L); 852 L->replaceAllUsesWith(*I); 853 toErase.push_back(L); 854 NumGVNLoad++; 855 856 return true; 857 } else { 858 repl.insert(std::make_pair((*I)->getParent(), *I)); 859 } 860 } 861 862 // Perform PHI construction 863 SmallPtrSet<BasicBlock*, 4> visited; 864 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 865 866 MD.removeInstruction(L); 867 L->replaceAllUsesWith(v); 868 toErase.push_back(L); 869 NumGVNLoad++; 870 871 return true; 872} 873 874/// processLoad - Attempt to eliminate a load, first by eliminating it 875/// locally, and then attempting non-local elimination if that fails. 876bool GVN::processLoad(LoadInst* L, 877 DenseMap<Value*, LoadInst*>& lastLoad, 878 SmallVector<Instruction*, 4>& toErase) { 879 if (L->isVolatile()) { 880 lastLoad[L->getPointerOperand()] = L; 881 return false; 882 } 883 884 Value* pointer = L->getPointerOperand(); 885 LoadInst*& last = lastLoad[pointer]; 886 887 // ... to a pointer that has been loaded from before... 888 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 889 bool removedNonLocal = false; 890 Instruction* dep = MD.getDependency(L); 891 if (dep == MemoryDependenceAnalysis::NonLocal && 892 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 893 removedNonLocal = processNonLocalLoad(L, toErase); 894 895 if (!removedNonLocal) 896 last = L; 897 898 return removedNonLocal; 899 } 900 901 902 bool deletedLoad = false; 903 904 // Walk up the dependency chain until we either find 905 // a dependency we can use, or we can't walk any further 906 while (dep != MemoryDependenceAnalysis::None && 907 dep != MemoryDependenceAnalysis::NonLocal && 908 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 909 // ... that depends on a store ... 910 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 911 if (S->getPointerOperand() == pointer) { 912 // Remove it! 913 MD.removeInstruction(L); 914 915 L->replaceAllUsesWith(S->getOperand(0)); 916 toErase.push_back(L); 917 deletedLoad = true; 918 NumGVNLoad++; 919 } 920 921 // Whether we removed it or not, we can't 922 // go any further 923 break; 924 } else if (!last) { 925 // If we don't depend on a store, and we haven't 926 // been loaded before, bail. 927 break; 928 } else if (dep == last) { 929 // Remove it! 930 MD.removeInstruction(L); 931 932 L->replaceAllUsesWith(last); 933 toErase.push_back(L); 934 deletedLoad = true; 935 NumGVNLoad++; 936 937 break; 938 } else { 939 dep = MD.getDependency(L, dep); 940 } 941 } 942 943 if (!deletedLoad) 944 last = L; 945 946 return deletedLoad; 947} 948 949/// processInstruction - When calculating availability, handle an instruction 950/// by inserting it into the appropriate sets 951bool GVN::processInstruction(Instruction* I, 952 ValueNumberedSet& currAvail, 953 DenseMap<Value*, LoadInst*>& lastSeenLoad, 954 SmallVector<Instruction*, 4>& toErase) { 955 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 956 return processLoad(L, lastSeenLoad, toErase); 957 } 958 959 unsigned num = VN.lookup_or_add(I); 960 961 // Collapse PHI nodes 962 if (PHINode* p = dyn_cast<PHINode>(I)) { 963 Value* constVal = p->hasConstantValue(); 964 965 if (constVal) { 966 if (Instruction* inst = dyn_cast<Instruction>(constVal)) { 967 DominatorTree &DT = getAnalysis<DominatorTree>(); 968 if (DT.dominates(inst, p)) { 969 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 970 PI != PE; ++PI) 971 if (PI->second.count(p)) 972 PI->second.erase(p); 973 974 p->replaceAllUsesWith(inst); 975 toErase.push_back(p); 976 } 977 } else { 978 p->replaceAllUsesWith(constVal); 979 toErase.push_back(p); 980 } 981 } 982 // Perform value-number based elimination 983 } else if (currAvail.test(num)) { 984 Value* repl = find_leader(currAvail, num); 985 986 VN.erase(I); 987 I->replaceAllUsesWith(repl); 988 toErase.push_back(I); 989 return true; 990 } else if (!I->isTerminator()) { 991 currAvail.set(num); 992 currAvail.insert(I); 993 } 994 995 return false; 996} 997 998// GVN::runOnFunction - This is the main transformation entry point for a 999// function. 1000// 1001bool GVN::runOnFunction(Function& F) { 1002 bool changed = false; 1003 bool shouldContinue = true; 1004 1005 while (shouldContinue) { 1006 shouldContinue = iterateOnFunction(F); 1007 changed |= shouldContinue; 1008 } 1009 1010 return changed; 1011} 1012 1013 1014// GVN::iterateOnFunction - Executes one iteration of GVN 1015bool GVN::iterateOnFunction(Function &F) { 1016 // Clean out global sets from any previous functions 1017 VN.clear(); 1018 availableOut.clear(); 1019 phiMap.clear(); 1020 1021 bool changed_function = false; 1022 1023 DominatorTree &DT = getAnalysis<DominatorTree>(); 1024 1025 SmallVector<Instruction*, 4> toErase; 1026 1027 // Top-down walk of the dominator tree 1028 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 1029 E = df_end(DT.getRootNode()); DI != E; ++DI) { 1030 1031 // Get the set to update for this block 1032 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 1033 DenseMap<Value*, LoadInst*> lastSeenLoad; 1034 1035 BasicBlock* BB = DI->getBlock(); 1036 1037 // A block inherits AVAIL_OUT from its dominator 1038 if (DI->getIDom() != 0) 1039 currAvail = availableOut[DI->getIDom()->getBlock()]; 1040 1041 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1042 BI != BE; ) { 1043 changed_function |= processInstruction(BI, currAvail, 1044 lastSeenLoad, toErase); 1045 1046 NumGVNInstr += toErase.size(); 1047 1048 // Avoid iterator invalidation 1049 ++BI; 1050 1051 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1052 E = toErase.end(); I != E; ++I) 1053 (*I)->eraseFromParent(); 1054 1055 toErase.clear(); 1056 } 1057 } 1058 1059 return changed_function; 1060} 1061