GVN.cpp revision a16bbc9aa77c9e22a67e9b0a8be17321990a7ccc
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/ADT/BitVector.h" 25#include "llvm/ADT/DenseMap.h" 26#include "llvm/ADT/DepthFirstIterator.h" 27#include "llvm/ADT/SmallPtrSet.h" 28#include "llvm/ADT/SmallVector.h" 29#include "llvm/ADT/Statistic.h" 30#include "llvm/Analysis/Dominators.h" 31#include "llvm/Analysis/AliasAnalysis.h" 32#include "llvm/Analysis/MemoryDependenceAnalysis.h" 33#include "llvm/Support/CFG.h" 34#include "llvm/Support/Compiler.h" 35using namespace llvm; 36 37//===----------------------------------------------------------------------===// 38// ValueTable Class 39//===----------------------------------------------------------------------===// 40 41/// This class holds the mapping between values and value numbers. It is used 42/// as an efficient mechanism to determine the expression-wise equivalence of 43/// two values. 44namespace { 45 struct VISIBILITY_HIDDEN Expression { 46 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 47 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 48 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 49 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 50 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 51 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 52 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 53 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 54 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 55 PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY, 56 TOMBSTONE }; 57 58 ExpressionOpcode opcode; 59 const Type* type; 60 uint32_t firstVN; 61 uint32_t secondVN; 62 uint32_t thirdVN; 63 SmallVector<uint32_t, 4> varargs; 64 Value* function; 65 66 Expression() { } 67 Expression(ExpressionOpcode o) : opcode(o) { } 68 69 bool operator==(const Expression &other) const { 70 if (opcode != other.opcode) 71 return false; 72 else if (opcode == EMPTY || opcode == TOMBSTONE) 73 return true; 74 else if (type != other.type) 75 return false; 76 else if (function != other.function) 77 return false; 78 else if (firstVN != other.firstVN) 79 return false; 80 else if (secondVN != other.secondVN) 81 return false; 82 else if (thirdVN != other.thirdVN) 83 return false; 84 else { 85 if (varargs.size() != other.varargs.size()) 86 return false; 87 88 for (size_t i = 0; i < varargs.size(); ++i) 89 if (varargs[i] != other.varargs[i]) 90 return false; 91 92 return true; 93 } 94 } 95 96 bool operator!=(const Expression &other) const { 97 if (opcode != other.opcode) 98 return true; 99 else if (opcode == EMPTY || opcode == TOMBSTONE) 100 return false; 101 else if (type != other.type) 102 return true; 103 else if (function != other.function) 104 return true; 105 else if (firstVN != other.firstVN) 106 return true; 107 else if (secondVN != other.secondVN) 108 return true; 109 else if (thirdVN != other.thirdVN) 110 return true; 111 else { 112 if (varargs.size() != other.varargs.size()) 113 return true; 114 115 for (size_t i = 0; i < varargs.size(); ++i) 116 if (varargs[i] != other.varargs[i]) 117 return true; 118 119 return false; 120 } 121 } 122 }; 123 124 class VISIBILITY_HIDDEN ValueTable { 125 private: 126 DenseMap<Value*, uint32_t> valueNumbering; 127 DenseMap<Expression, uint32_t> expressionNumbering; 128 AliasAnalysis* AA; 129 130 uint32_t nextValueNumber; 131 132 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 133 Expression::ExpressionOpcode getOpcode(CmpInst* C); 134 Expression::ExpressionOpcode getOpcode(CastInst* C); 135 Expression create_expression(BinaryOperator* BO); 136 Expression create_expression(CmpInst* C); 137 Expression create_expression(ShuffleVectorInst* V); 138 Expression create_expression(ExtractElementInst* C); 139 Expression create_expression(InsertElementInst* V); 140 Expression create_expression(SelectInst* V); 141 Expression create_expression(CastInst* C); 142 Expression create_expression(GetElementPtrInst* G); 143 Expression create_expression(CallInst* C); 144 public: 145 ValueTable() : nextValueNumber(1) { } 146 uint32_t lookup_or_add(Value* V); 147 uint32_t lookup(Value* V) const; 148 void add(Value* V, uint32_t num); 149 void clear(); 150 void erase(Value* v); 151 unsigned size(); 152 void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 153 uint32_t hash_operand(Value* v); 154 }; 155} 156 157namespace llvm { 158template <> struct DenseMapInfo<Expression> { 159 static inline Expression getEmptyKey() { 160 return Expression(Expression::EMPTY); 161 } 162 163 static inline Expression getTombstoneKey() { 164 return Expression(Expression::TOMBSTONE); 165 } 166 167 static unsigned getHashValue(const Expression e) { 168 unsigned hash = e.opcode; 169 170 hash = e.firstVN + hash * 37; 171 hash = e.secondVN + hash * 37; 172 hash = e.thirdVN + hash * 37; 173 174 hash = (unsigned)((uintptr_t)e.type >> 4) ^ 175 (unsigned)((uintptr_t)e.type >> 9) + 176 hash * 37; 177 178 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 179 E = e.varargs.end(); I != E; ++I) 180 hash = *I + hash * 37; 181 182 hash = (unsigned)((uintptr_t)e.function >> 4) ^ 183 (unsigned)((uintptr_t)e.function >> 9) + 184 hash * 37; 185 186 return hash; 187 } 188 static bool isEqual(const Expression &LHS, const Expression &RHS) { 189 return LHS == RHS; 190 } 191 static bool isPod() { return true; } 192}; 193} 194 195//===----------------------------------------------------------------------===// 196// ValueTable Internal Functions 197//===----------------------------------------------------------------------===// 198Expression::ExpressionOpcode 199 ValueTable::getOpcode(BinaryOperator* BO) { 200 switch(BO->getOpcode()) { 201 case Instruction::Add: 202 return Expression::ADD; 203 case Instruction::Sub: 204 return Expression::SUB; 205 case Instruction::Mul: 206 return Expression::MUL; 207 case Instruction::UDiv: 208 return Expression::UDIV; 209 case Instruction::SDiv: 210 return Expression::SDIV; 211 case Instruction::FDiv: 212 return Expression::FDIV; 213 case Instruction::URem: 214 return Expression::UREM; 215 case Instruction::SRem: 216 return Expression::SREM; 217 case Instruction::FRem: 218 return Expression::FREM; 219 case Instruction::Shl: 220 return Expression::SHL; 221 case Instruction::LShr: 222 return Expression::LSHR; 223 case Instruction::AShr: 224 return Expression::ASHR; 225 case Instruction::And: 226 return Expression::AND; 227 case Instruction::Or: 228 return Expression::OR; 229 case Instruction::Xor: 230 return Expression::XOR; 231 232 // THIS SHOULD NEVER HAPPEN 233 default: 234 assert(0 && "Binary operator with unknown opcode?"); 235 return Expression::ADD; 236 } 237} 238 239Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 240 if (C->getOpcode() == Instruction::ICmp) { 241 switch (C->getPredicate()) { 242 case ICmpInst::ICMP_EQ: 243 return Expression::ICMPEQ; 244 case ICmpInst::ICMP_NE: 245 return Expression::ICMPNE; 246 case ICmpInst::ICMP_UGT: 247 return Expression::ICMPUGT; 248 case ICmpInst::ICMP_UGE: 249 return Expression::ICMPUGE; 250 case ICmpInst::ICMP_ULT: 251 return Expression::ICMPULT; 252 case ICmpInst::ICMP_ULE: 253 return Expression::ICMPULE; 254 case ICmpInst::ICMP_SGT: 255 return Expression::ICMPSGT; 256 case ICmpInst::ICMP_SGE: 257 return Expression::ICMPSGE; 258 case ICmpInst::ICMP_SLT: 259 return Expression::ICMPSLT; 260 case ICmpInst::ICMP_SLE: 261 return Expression::ICMPSLE; 262 263 // THIS SHOULD NEVER HAPPEN 264 default: 265 assert(0 && "Comparison with unknown predicate?"); 266 return Expression::ICMPEQ; 267 } 268 } else { 269 switch (C->getPredicate()) { 270 case FCmpInst::FCMP_OEQ: 271 return Expression::FCMPOEQ; 272 case FCmpInst::FCMP_OGT: 273 return Expression::FCMPOGT; 274 case FCmpInst::FCMP_OGE: 275 return Expression::FCMPOGE; 276 case FCmpInst::FCMP_OLT: 277 return Expression::FCMPOLT; 278 case FCmpInst::FCMP_OLE: 279 return Expression::FCMPOLE; 280 case FCmpInst::FCMP_ONE: 281 return Expression::FCMPONE; 282 case FCmpInst::FCMP_ORD: 283 return Expression::FCMPORD; 284 case FCmpInst::FCMP_UNO: 285 return Expression::FCMPUNO; 286 case FCmpInst::FCMP_UEQ: 287 return Expression::FCMPUEQ; 288 case FCmpInst::FCMP_UGT: 289 return Expression::FCMPUGT; 290 case FCmpInst::FCMP_UGE: 291 return Expression::FCMPUGE; 292 case FCmpInst::FCMP_ULT: 293 return Expression::FCMPULT; 294 case FCmpInst::FCMP_ULE: 295 return Expression::FCMPULE; 296 case FCmpInst::FCMP_UNE: 297 return Expression::FCMPUNE; 298 299 // THIS SHOULD NEVER HAPPEN 300 default: 301 assert(0 && "Comparison with unknown predicate?"); 302 return Expression::FCMPOEQ; 303 } 304 } 305} 306 307Expression::ExpressionOpcode 308 ValueTable::getOpcode(CastInst* C) { 309 switch(C->getOpcode()) { 310 case Instruction::Trunc: 311 return Expression::TRUNC; 312 case Instruction::ZExt: 313 return Expression::ZEXT; 314 case Instruction::SExt: 315 return Expression::SEXT; 316 case Instruction::FPToUI: 317 return Expression::FPTOUI; 318 case Instruction::FPToSI: 319 return Expression::FPTOSI; 320 case Instruction::UIToFP: 321 return Expression::UITOFP; 322 case Instruction::SIToFP: 323 return Expression::SITOFP; 324 case Instruction::FPTrunc: 325 return Expression::FPTRUNC; 326 case Instruction::FPExt: 327 return Expression::FPEXT; 328 case Instruction::PtrToInt: 329 return Expression::PTRTOINT; 330 case Instruction::IntToPtr: 331 return Expression::INTTOPTR; 332 case Instruction::BitCast: 333 return Expression::BITCAST; 334 335 // THIS SHOULD NEVER HAPPEN 336 default: 337 assert(0 && "Cast operator with unknown opcode?"); 338 return Expression::BITCAST; 339 } 340} 341 342uint32_t ValueTable::hash_operand(Value* v) { 343 if (CallInst* CI = dyn_cast<CallInst>(v)) 344 if (CI->getCalledFunction() && 345 !AA->doesNotAccessMemory(CI->getCalledFunction())) 346 return nextValueNumber++; 347 348 return lookup_or_add(v); 349} 350 351Expression ValueTable::create_expression(CallInst* C) { 352 Expression e; 353 354 e.type = C->getType(); 355 e.firstVN = 0; 356 e.secondVN = 0; 357 e.thirdVN = 0; 358 e.function = C->getCalledFunction(); 359 e.opcode = Expression::CALL; 360 361 for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 362 I != E; ++I) 363 e.varargs.push_back(hash_operand(*I)); 364 365 return e; 366} 367 368Expression ValueTable::create_expression(BinaryOperator* BO) { 369 Expression e; 370 371 e.firstVN = hash_operand(BO->getOperand(0)); 372 e.secondVN = hash_operand(BO->getOperand(1)); 373 e.thirdVN = 0; 374 e.function = 0; 375 e.type = BO->getType(); 376 e.opcode = getOpcode(BO); 377 378 return e; 379} 380 381Expression ValueTable::create_expression(CmpInst* C) { 382 Expression e; 383 384 e.firstVN = hash_operand(C->getOperand(0)); 385 e.secondVN = hash_operand(C->getOperand(1)); 386 e.thirdVN = 0; 387 e.function = 0; 388 e.type = C->getType(); 389 e.opcode = getOpcode(C); 390 391 return e; 392} 393 394Expression ValueTable::create_expression(CastInst* C) { 395 Expression e; 396 397 e.firstVN = hash_operand(C->getOperand(0)); 398 e.secondVN = 0; 399 e.thirdVN = 0; 400 e.function = 0; 401 e.type = C->getType(); 402 e.opcode = getOpcode(C); 403 404 return e; 405} 406 407Expression ValueTable::create_expression(ShuffleVectorInst* S) { 408 Expression e; 409 410 e.firstVN = hash_operand(S->getOperand(0)); 411 e.secondVN = hash_operand(S->getOperand(1)); 412 e.thirdVN = hash_operand(S->getOperand(2)); 413 e.function = 0; 414 e.type = S->getType(); 415 e.opcode = Expression::SHUFFLE; 416 417 return e; 418} 419 420Expression ValueTable::create_expression(ExtractElementInst* E) { 421 Expression e; 422 423 e.firstVN = hash_operand(E->getOperand(0)); 424 e.secondVN = hash_operand(E->getOperand(1)); 425 e.thirdVN = 0; 426 e.function = 0; 427 e.type = E->getType(); 428 e.opcode = Expression::EXTRACT; 429 430 return e; 431} 432 433Expression ValueTable::create_expression(InsertElementInst* I) { 434 Expression e; 435 436 e.firstVN = hash_operand(I->getOperand(0)); 437 e.secondVN = hash_operand(I->getOperand(1)); 438 e.thirdVN = hash_operand(I->getOperand(2)); 439 e.function = 0; 440 e.type = I->getType(); 441 e.opcode = Expression::INSERT; 442 443 return e; 444} 445 446Expression ValueTable::create_expression(SelectInst* I) { 447 Expression e; 448 449 e.firstVN = hash_operand(I->getCondition()); 450 e.secondVN = hash_operand(I->getTrueValue()); 451 e.thirdVN = hash_operand(I->getFalseValue()); 452 e.function = 0; 453 e.type = I->getType(); 454 e.opcode = Expression::SELECT; 455 456 return e; 457} 458 459Expression ValueTable::create_expression(GetElementPtrInst* G) { 460 Expression e; 461 462 e.firstVN = hash_operand(G->getPointerOperand()); 463 e.secondVN = 0; 464 e.thirdVN = 0; 465 e.function = 0; 466 e.type = G->getType(); 467 e.opcode = Expression::GEP; 468 469 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 470 I != E; ++I) 471 e.varargs.push_back(hash_operand(*I)); 472 473 return e; 474} 475 476//===----------------------------------------------------------------------===// 477// ValueTable External Functions 478//===----------------------------------------------------------------------===// 479 480/// lookup_or_add - Returns the value number for the specified value, assigning 481/// it a new number if it did not have one before. 482uint32_t ValueTable::lookup_or_add(Value* V) { 483 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 484 if (VI != valueNumbering.end()) 485 return VI->second; 486 487 if (CallInst* C = dyn_cast<CallInst>(V)) { 488 if (C->getCalledFunction() && 489 (AA->doesNotAccessMemory(C->getCalledFunction()) || 490 AA->onlyReadsMemory(C->getCalledFunction()))) { 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.addPreserved<AliasAnalysis>(); 726 AU.addPreserved<MemoryDependenceAnalysis>(); 727 } 728 729 // Helper fuctions 730 // FIXME: eliminate or document these better 731 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 732 void val_insert(ValueNumberedSet& s, Value* v); 733 bool processLoad(LoadInst* L, 734 DenseMap<Value*, LoadInst*>& lastLoad, 735 SmallVector<Instruction*, 4>& toErase); 736 bool processInstruction(Instruction* I, 737 ValueNumberedSet& currAvail, 738 DenseMap<Value*, LoadInst*>& lastSeenLoad, 739 SmallVector<Instruction*, 4>& toErase); 740 bool processNonLocalLoad(LoadInst* L, 741 SmallVector<Instruction*, 4>& toErase); 742 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 743 DenseMap<BasicBlock*, Value*> &Phis, 744 bool top_level = false); 745 void dump(DenseMap<BasicBlock*, Value*>& d); 746 bool iterateOnFunction(Function &F); 747 Value* CollapsePhi(PHINode* p); 748 bool isSafeReplacement(PHINode* p, Instruction* inst); 749 }; 750 751 char GVN::ID = 0; 752 753} 754 755// createGVNPass - The public interface to this file... 756FunctionPass *llvm::createGVNPass() { return new GVN(); } 757 758static RegisterPass<GVN> X("gvn", 759 "Global Value Numbering"); 760 761STATISTIC(NumGVNInstr, "Number of instructions deleted"); 762STATISTIC(NumGVNLoad, "Number of loads deleted"); 763 764/// find_leader - Given a set and a value number, return the first 765/// element of the set with that value number, or 0 if no such element 766/// is present 767Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 768 if (!vals.test(v)) 769 return 0; 770 771 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 772 I != E; ++I) 773 if (v == VN.lookup(*I)) 774 return *I; 775 776 assert(0 && "No leader found, but present bit is set?"); 777 return 0; 778} 779 780/// val_insert - Insert a value into a set only if there is not a value 781/// with the same value number already in the set 782void GVN::val_insert(ValueNumberedSet& s, Value* v) { 783 uint32_t num = VN.lookup(v); 784 if (!s.test(num)) 785 s.insert(v); 786} 787 788void GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 789 printf("{\n"); 790 for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 791 E = d.end(); I != E; ++I) { 792 if (I->second == MemoryDependenceAnalysis::None) 793 printf("None\n"); 794 else 795 I->second->dump(); 796 } 797 printf("}\n"); 798} 799 800Value* GVN::CollapsePhi(PHINode* p) { 801 DominatorTree &DT = getAnalysis<DominatorTree>(); 802 Value* constVal = p->hasConstantValue(); 803 804 if (constVal) { 805 if (Instruction* inst = dyn_cast<Instruction>(constVal)) { 806 if (DT.dominates(inst, p)) 807 if (isSafeReplacement(p, inst)) 808 return inst; 809 } else { 810 return constVal; 811 } 812 } 813 814 return 0; 815} 816 817bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 818 if (!isa<PHINode>(inst)) 819 return true; 820 821 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 822 UI != E; ++UI) 823 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 824 if (use_phi->getParent() == inst->getParent()) 825 return false; 826 827 return true; 828} 829 830/// GetValueForBlock - Get the value to use within the specified basic block. 831/// available values are in Phis. 832Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 833 DenseMap<BasicBlock*, Value*> &Phis, 834 bool top_level) { 835 836 // If we have already computed this value, return the previously computed val. 837 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 838 if (V != Phis.end() && !top_level) return V->second; 839 840 BasicBlock* singlePred = BB->getSinglePredecessor(); 841 if (singlePred) { 842 Value *ret = GetValueForBlock(singlePred, orig, Phis); 843 Phis[BB] = ret; 844 return ret; 845 } 846 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 847 // now, then get values to fill in the incoming values for the PHI. 848 PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", 849 BB->begin()); 850 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 851 852 if (Phis.count(BB) == 0) 853 Phis.insert(std::make_pair(BB, PN)); 854 855 // Fill in the incoming values for the block. 856 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 857 Value* val = GetValueForBlock(*PI, orig, Phis); 858 859 PN->addIncoming(val, *PI); 860 } 861 862 // Attempt to collapse PHI nodes that are trivially redundant 863 Value* v = CollapsePhi(PN); 864 if (v) { 865 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 866 867 MD.removeInstruction(PN); 868 PN->replaceAllUsesWith(v); 869 870 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 871 E = Phis.end(); I != E; ++I) 872 if (I->second == PN) 873 I->second = v; 874 875 PN->eraseFromParent(); 876 877 Phis[BB] = v; 878 879 return v; 880 } 881 882 // Cache our phi construction results 883 phiMap[orig->getPointerOperand()].insert(PN); 884 return PN; 885} 886 887/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 888/// non-local by performing PHI construction. 889bool GVN::processNonLocalLoad(LoadInst* L, 890 SmallVector<Instruction*, 4>& toErase) { 891 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 892 893 // Find the non-local dependencies of the load 894 DenseMap<BasicBlock*, Value*> deps; 895 MD.getNonLocalDependency(L, deps); 896 897 DenseMap<BasicBlock*, Value*> repl; 898 899 // Filter out useless results (non-locals, etc) 900 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 901 I != E; ++I) 902 if (I->second == MemoryDependenceAnalysis::None) { 903 return false; 904 } else if (I->second == MemoryDependenceAnalysis::NonLocal) { 905 continue; 906 } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 907 if (S->getPointerOperand() == L->getPointerOperand()) 908 repl[I->first] = S->getOperand(0); 909 else 910 return false; 911 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 912 if (LD->getPointerOperand() == L->getPointerOperand()) 913 repl[I->first] = LD; 914 else 915 return false; 916 } else { 917 return false; 918 } 919 920 // Use cached PHI construction information from previous runs 921 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 922 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 923 I != E; ++I) { 924 if ((*I)->getParent() == L->getParent()) { 925 MD.removeInstruction(L); 926 L->replaceAllUsesWith(*I); 927 toErase.push_back(L); 928 NumGVNLoad++; 929 930 return true; 931 } else { 932 repl.insert(std::make_pair((*I)->getParent(), *I)); 933 } 934 } 935 936 // Perform PHI construction 937 SmallPtrSet<BasicBlock*, 4> visited; 938 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 939 940 MD.removeInstruction(L); 941 L->replaceAllUsesWith(v); 942 toErase.push_back(L); 943 NumGVNLoad++; 944 945 return true; 946} 947 948/// processLoad - Attempt to eliminate a load, first by eliminating it 949/// locally, and then attempting non-local elimination if that fails. 950bool GVN::processLoad(LoadInst* L, 951 DenseMap<Value*, LoadInst*>& lastLoad, 952 SmallVector<Instruction*, 4>& toErase) { 953 if (L->isVolatile()) { 954 lastLoad[L->getPointerOperand()] = L; 955 return false; 956 } 957 958 Value* pointer = L->getPointerOperand(); 959 LoadInst*& last = lastLoad[pointer]; 960 961 // ... to a pointer that has been loaded from before... 962 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 963 bool removedNonLocal = false; 964 Instruction* dep = MD.getDependency(L); 965 if (dep == MemoryDependenceAnalysis::NonLocal && 966 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 967 removedNonLocal = processNonLocalLoad(L, toErase); 968 969 if (!removedNonLocal) 970 last = L; 971 972 return removedNonLocal; 973 } 974 975 976 bool deletedLoad = false; 977 978 // Walk up the dependency chain until we either find 979 // a dependency we can use, or we can't walk any further 980 while (dep != MemoryDependenceAnalysis::None && 981 dep != MemoryDependenceAnalysis::NonLocal && 982 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 983 // ... that depends on a store ... 984 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 985 if (S->getPointerOperand() == pointer) { 986 // Remove it! 987 MD.removeInstruction(L); 988 989 L->replaceAllUsesWith(S->getOperand(0)); 990 toErase.push_back(L); 991 deletedLoad = true; 992 NumGVNLoad++; 993 } 994 995 // Whether we removed it or not, we can't 996 // go any further 997 break; 998 } else if (!last) { 999 // If we don't depend on a store, and we haven't 1000 // been loaded before, bail. 1001 break; 1002 } else if (dep == last) { 1003 // Remove it! 1004 MD.removeInstruction(L); 1005 1006 L->replaceAllUsesWith(last); 1007 toErase.push_back(L); 1008 deletedLoad = true; 1009 NumGVNLoad++; 1010 1011 break; 1012 } else { 1013 dep = MD.getDependency(L, dep); 1014 } 1015 } 1016 1017 if (!deletedLoad) 1018 last = L; 1019 1020 return deletedLoad; 1021} 1022 1023/// processInstruction - When calculating availability, handle an instruction 1024/// by inserting it into the appropriate sets 1025bool GVN::processInstruction(Instruction* I, 1026 ValueNumberedSet& currAvail, 1027 DenseMap<Value*, LoadInst*>& lastSeenLoad, 1028 SmallVector<Instruction*, 4>& toErase) { 1029 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1030 return processLoad(L, lastSeenLoad, toErase); 1031 } 1032 1033 unsigned num = VN.lookup_or_add(I); 1034 1035 // Collapse PHI nodes 1036 if (PHINode* p = dyn_cast<PHINode>(I)) { 1037 Value* constVal = CollapsePhi(p); 1038 1039 if (constVal) { 1040 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1041 PI != PE; ++PI) 1042 if (PI->second.count(p)) 1043 PI->second.erase(p); 1044 1045 p->replaceAllUsesWith(constVal); 1046 toErase.push_back(p); 1047 } 1048 // Perform value-number based elimination 1049 } else if (currAvail.test(num)) { 1050 Value* repl = find_leader(currAvail, num); 1051 1052 if (CallInst* CI = dyn_cast<CallInst>(I)) { 1053 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 1054 if (CI->getCalledFunction() && 1055 !AA.doesNotAccessMemory(CI->getCalledFunction())) { 1056 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1057 if (MD.getDependency(CI) != MD.getDependency(cast<CallInst>(repl))) { 1058 // There must be an intervening may-alias store, so nothing from 1059 // this point on will be able to be replaced with the preceding call 1060 currAvail.erase(repl); 1061 currAvail.insert(I); 1062 1063 return false; 1064 } 1065 } 1066 } 1067 1068 VN.erase(I); 1069 I->replaceAllUsesWith(repl); 1070 toErase.push_back(I); 1071 return true; 1072 } else if (!I->isTerminator()) { 1073 currAvail.set(num); 1074 currAvail.insert(I); 1075 } 1076 1077 return false; 1078} 1079 1080// GVN::runOnFunction - This is the main transformation entry point for a 1081// function. 1082// 1083bool GVN::runOnFunction(Function& F) { 1084 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1085 1086 bool changed = false; 1087 bool shouldContinue = true; 1088 1089 while (shouldContinue) { 1090 shouldContinue = iterateOnFunction(F); 1091 changed |= shouldContinue; 1092 } 1093 1094 return changed; 1095} 1096 1097 1098// GVN::iterateOnFunction - Executes one iteration of GVN 1099bool GVN::iterateOnFunction(Function &F) { 1100 // Clean out global sets from any previous functions 1101 VN.clear(); 1102 availableOut.clear(); 1103 phiMap.clear(); 1104 1105 bool changed_function = false; 1106 1107 DominatorTree &DT = getAnalysis<DominatorTree>(); 1108 1109 SmallVector<Instruction*, 4> toErase; 1110 1111 // Top-down walk of the dominator tree 1112 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 1113 E = df_end(DT.getRootNode()); DI != E; ++DI) { 1114 1115 // Get the set to update for this block 1116 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 1117 DenseMap<Value*, LoadInst*> lastSeenLoad; 1118 1119 BasicBlock* BB = DI->getBlock(); 1120 1121 // A block inherits AVAIL_OUT from its dominator 1122 if (DI->getIDom() != 0) 1123 currAvail = availableOut[DI->getIDom()->getBlock()]; 1124 1125 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1126 BI != BE; ) { 1127 changed_function |= processInstruction(BI, currAvail, 1128 lastSeenLoad, toErase); 1129 1130 NumGVNInstr += toErase.size(); 1131 1132 // Avoid iterator invalidation 1133 ++BI; 1134 1135 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1136 E = toErase.end(); I != E; ++I) 1137 (*I)->eraseFromParent(); 1138 1139 toErase.clear(); 1140 } 1141 } 1142 1143 return changed_function; 1144} 1145