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