GVN.cpp revision 5fc4abac3db46b6e6b3824163c0f1252c1ab0ebb
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 (!AA->doesNotAccessMemory(CI)) 345 return nextValueNumber++; 346 347 return lookup_or_add(v); 348} 349 350Expression ValueTable::create_expression(CallInst* C) { 351 Expression e; 352 353 e.type = C->getType(); 354 e.firstVN = 0; 355 e.secondVN = 0; 356 e.thirdVN = 0; 357 e.function = C->getCalledFunction(); 358 e.opcode = Expression::CALL; 359 360 for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 361 I != E; ++I) 362 e.varargs.push_back(hash_operand(*I)); 363 364 return e; 365} 366 367Expression ValueTable::create_expression(BinaryOperator* BO) { 368 Expression e; 369 370 e.firstVN = hash_operand(BO->getOperand(0)); 371 e.secondVN = hash_operand(BO->getOperand(1)); 372 e.thirdVN = 0; 373 e.function = 0; 374 e.type = BO->getType(); 375 e.opcode = getOpcode(BO); 376 377 return e; 378} 379 380Expression ValueTable::create_expression(CmpInst* C) { 381 Expression e; 382 383 e.firstVN = hash_operand(C->getOperand(0)); 384 e.secondVN = hash_operand(C->getOperand(1)); 385 e.thirdVN = 0; 386 e.function = 0; 387 e.type = C->getType(); 388 e.opcode = getOpcode(C); 389 390 return e; 391} 392 393Expression ValueTable::create_expression(CastInst* C) { 394 Expression e; 395 396 e.firstVN = hash_operand(C->getOperand(0)); 397 e.secondVN = 0; 398 e.thirdVN = 0; 399 e.function = 0; 400 e.type = C->getType(); 401 e.opcode = getOpcode(C); 402 403 return e; 404} 405 406Expression ValueTable::create_expression(ShuffleVectorInst* S) { 407 Expression e; 408 409 e.firstVN = hash_operand(S->getOperand(0)); 410 e.secondVN = hash_operand(S->getOperand(1)); 411 e.thirdVN = hash_operand(S->getOperand(2)); 412 e.function = 0; 413 e.type = S->getType(); 414 e.opcode = Expression::SHUFFLE; 415 416 return e; 417} 418 419Expression ValueTable::create_expression(ExtractElementInst* E) { 420 Expression e; 421 422 e.firstVN = hash_operand(E->getOperand(0)); 423 e.secondVN = hash_operand(E->getOperand(1)); 424 e.thirdVN = 0; 425 e.function = 0; 426 e.type = E->getType(); 427 e.opcode = Expression::EXTRACT; 428 429 return e; 430} 431 432Expression ValueTable::create_expression(InsertElementInst* I) { 433 Expression e; 434 435 e.firstVN = hash_operand(I->getOperand(0)); 436 e.secondVN = hash_operand(I->getOperand(1)); 437 e.thirdVN = hash_operand(I->getOperand(2)); 438 e.function = 0; 439 e.type = I->getType(); 440 e.opcode = Expression::INSERT; 441 442 return e; 443} 444 445Expression ValueTable::create_expression(SelectInst* I) { 446 Expression e; 447 448 e.firstVN = hash_operand(I->getCondition()); 449 e.secondVN = hash_operand(I->getTrueValue()); 450 e.thirdVN = hash_operand(I->getFalseValue()); 451 e.function = 0; 452 e.type = I->getType(); 453 e.opcode = Expression::SELECT; 454 455 return e; 456} 457 458Expression ValueTable::create_expression(GetElementPtrInst* G) { 459 Expression e; 460 461 e.firstVN = hash_operand(G->getPointerOperand()); 462 e.secondVN = 0; 463 e.thirdVN = 0; 464 e.function = 0; 465 e.type = G->getType(); 466 e.opcode = Expression::GEP; 467 468 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 469 I != E; ++I) 470 e.varargs.push_back(hash_operand(*I)); 471 472 return e; 473} 474 475//===----------------------------------------------------------------------===// 476// ValueTable External Functions 477//===----------------------------------------------------------------------===// 478 479/// lookup_or_add - Returns the value number for the specified value, assigning 480/// it a new number if it did not have one before. 481uint32_t ValueTable::lookup_or_add(Value* V) { 482 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 483 if (VI != valueNumbering.end()) 484 return VI->second; 485 486 if (CallInst* C = dyn_cast<CallInst>(V)) { 487 if (AA->onlyReadsMemory(C)) { // includes doesNotAccessMemory 488 Expression e = create_expression(C); 489 490 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 491 if (EI != expressionNumbering.end()) { 492 valueNumbering.insert(std::make_pair(V, EI->second)); 493 return EI->second; 494 } else { 495 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 496 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 497 498 return nextValueNumber++; 499 } 500 } else { 501 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 502 return nextValueNumber++; 503 } 504 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 505 Expression e = create_expression(BO); 506 507 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 508 if (EI != expressionNumbering.end()) { 509 valueNumbering.insert(std::make_pair(V, EI->second)); 510 return EI->second; 511 } else { 512 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 513 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 514 515 return nextValueNumber++; 516 } 517 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 518 Expression e = create_expression(C); 519 520 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 521 if (EI != expressionNumbering.end()) { 522 valueNumbering.insert(std::make_pair(V, EI->second)); 523 return EI->second; 524 } else { 525 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 526 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 527 528 return nextValueNumber++; 529 } 530 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 531 Expression e = create_expression(U); 532 533 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 534 if (EI != expressionNumbering.end()) { 535 valueNumbering.insert(std::make_pair(V, EI->second)); 536 return EI->second; 537 } else { 538 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 539 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 540 541 return nextValueNumber++; 542 } 543 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 544 Expression e = create_expression(U); 545 546 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 547 if (EI != expressionNumbering.end()) { 548 valueNumbering.insert(std::make_pair(V, EI->second)); 549 return EI->second; 550 } else { 551 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 552 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 553 554 return nextValueNumber++; 555 } 556 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 557 Expression e = create_expression(U); 558 559 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 560 if (EI != expressionNumbering.end()) { 561 valueNumbering.insert(std::make_pair(V, EI->second)); 562 return EI->second; 563 } else { 564 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 565 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 566 567 return nextValueNumber++; 568 } 569 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 570 Expression e = create_expression(U); 571 572 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 573 if (EI != expressionNumbering.end()) { 574 valueNumbering.insert(std::make_pair(V, EI->second)); 575 return EI->second; 576 } else { 577 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 578 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 579 580 return nextValueNumber++; 581 } 582 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 583 Expression e = create_expression(U); 584 585 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 586 if (EI != expressionNumbering.end()) { 587 valueNumbering.insert(std::make_pair(V, EI->second)); 588 return EI->second; 589 } else { 590 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 591 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 592 593 return nextValueNumber++; 594 } 595 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 596 Expression e = create_expression(U); 597 598 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 599 if (EI != expressionNumbering.end()) { 600 valueNumbering.insert(std::make_pair(V, EI->second)); 601 return EI->second; 602 } else { 603 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 604 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 605 606 return nextValueNumber++; 607 } 608 } else { 609 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 610 return nextValueNumber++; 611 } 612} 613 614/// lookup - Returns the value number of the specified value. Fails if 615/// the value has not yet been numbered. 616uint32_t ValueTable::lookup(Value* V) const { 617 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 618 if (VI != valueNumbering.end()) 619 return VI->second; 620 else 621 assert(0 && "Value not numbered?"); 622 623 return 0; 624} 625 626/// clear - Remove all entries from the ValueTable 627void ValueTable::clear() { 628 valueNumbering.clear(); 629 expressionNumbering.clear(); 630 nextValueNumber = 1; 631} 632 633/// erase - Remove a value from the value numbering 634void ValueTable::erase(Value* V) { 635 valueNumbering.erase(V); 636} 637 638//===----------------------------------------------------------------------===// 639// ValueNumberedSet Class 640//===----------------------------------------------------------------------===// 641namespace { 642class ValueNumberedSet { 643 private: 644 SmallPtrSet<Value*, 8> contents; 645 BitVector numbers; 646 public: 647 ValueNumberedSet() { numbers.resize(1); } 648 ValueNumberedSet(const ValueNumberedSet& other) { 649 numbers = other.numbers; 650 contents = other.contents; 651 } 652 653 typedef SmallPtrSet<Value*, 8>::iterator iterator; 654 655 iterator begin() { return contents.begin(); } 656 iterator end() { return contents.end(); } 657 658 bool insert(Value* v) { return contents.insert(v); } 659 void insert(iterator I, iterator E) { contents.insert(I, E); } 660 void erase(Value* v) { contents.erase(v); } 661 unsigned count(Value* v) { return contents.count(v); } 662 size_t size() { return contents.size(); } 663 664 void set(unsigned i) { 665 if (i >= numbers.size()) 666 numbers.resize(i+1); 667 668 numbers.set(i); 669 } 670 671 void operator=(const ValueNumberedSet& other) { 672 contents = other.contents; 673 numbers = other.numbers; 674 } 675 676 void reset(unsigned i) { 677 if (i < numbers.size()) 678 numbers.reset(i); 679 } 680 681 bool test(unsigned i) { 682 if (i >= numbers.size()) 683 return false; 684 685 return numbers.test(i); 686 } 687 688 void clear() { 689 contents.clear(); 690 numbers.clear(); 691 } 692}; 693} 694 695//===----------------------------------------------------------------------===// 696// GVN Pass 697//===----------------------------------------------------------------------===// 698 699namespace { 700 701 class VISIBILITY_HIDDEN GVN : public FunctionPass { 702 bool runOnFunction(Function &F); 703 public: 704 static char ID; // Pass identification, replacement for typeid 705 GVN() : FunctionPass((intptr_t)&ID) { } 706 707 private: 708 ValueTable VN; 709 710 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 711 712 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 713 PhiMapType phiMap; 714 715 716 // This transformation requires dominator postdominator info 717 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 718 AU.setPreservesCFG(); 719 AU.addRequired<DominatorTree>(); 720 AU.addRequired<MemoryDependenceAnalysis>(); 721 AU.addRequired<AliasAnalysis>(); 722 AU.addPreserved<AliasAnalysis>(); 723 AU.addPreserved<MemoryDependenceAnalysis>(); 724 } 725 726 // Helper fuctions 727 // FIXME: eliminate or document these better 728 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 729 void val_insert(ValueNumberedSet& s, Value* v); 730 bool processLoad(LoadInst* L, 731 DenseMap<Value*, LoadInst*>& lastLoad, 732 SmallVector<Instruction*, 4>& toErase); 733 bool processInstruction(Instruction* I, 734 ValueNumberedSet& currAvail, 735 DenseMap<Value*, LoadInst*>& lastSeenLoad, 736 SmallVector<Instruction*, 4>& toErase); 737 bool processNonLocalLoad(LoadInst* L, 738 SmallVector<Instruction*, 4>& toErase); 739 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 740 DenseMap<BasicBlock*, Value*> &Phis, 741 bool top_level = false); 742 void dump(DenseMap<BasicBlock*, Value*>& d); 743 bool iterateOnFunction(Function &F); 744 Value* CollapsePhi(PHINode* p); 745 bool isSafeReplacement(PHINode* p, Instruction* inst); 746 }; 747 748 char GVN::ID = 0; 749 750} 751 752// createGVNPass - The public interface to this file... 753FunctionPass *llvm::createGVNPass() { return new GVN(); } 754 755static RegisterPass<GVN> X("gvn", 756 "Global Value Numbering"); 757 758STATISTIC(NumGVNInstr, "Number of instructions deleted"); 759STATISTIC(NumGVNLoad, "Number of loads deleted"); 760 761/// find_leader - Given a set and a value number, return the first 762/// element of the set with that value number, or 0 if no such element 763/// is present 764Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 765 if (!vals.test(v)) 766 return 0; 767 768 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 769 I != E; ++I) 770 if (v == VN.lookup(*I)) 771 return *I; 772 773 assert(0 && "No leader found, but present bit is set?"); 774 return 0; 775} 776 777/// val_insert - Insert a value into a set only if there is not a value 778/// with the same value number already in the set 779void GVN::val_insert(ValueNumberedSet& s, Value* v) { 780 uint32_t num = VN.lookup(v); 781 if (!s.test(num)) 782 s.insert(v); 783} 784 785void GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 786 printf("{\n"); 787 for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 788 E = d.end(); I != E; ++I) { 789 if (I->second == MemoryDependenceAnalysis::None) 790 printf("None\n"); 791 else 792 I->second->dump(); 793 } 794 printf("}\n"); 795} 796 797Value* GVN::CollapsePhi(PHINode* p) { 798 DominatorTree &DT = getAnalysis<DominatorTree>(); 799 Value* constVal = p->hasConstantValue(); 800 801 if (constVal) { 802 if (Instruction* inst = dyn_cast<Instruction>(constVal)) { 803 if (DT.dominates(inst, p)) 804 if (isSafeReplacement(p, inst)) 805 return inst; 806 } else { 807 return constVal; 808 } 809 } 810 811 return 0; 812} 813 814bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 815 if (!isa<PHINode>(inst)) 816 return true; 817 818 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 819 UI != E; ++UI) 820 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 821 if (use_phi->getParent() == inst->getParent()) 822 return false; 823 824 return true; 825} 826 827/// GetValueForBlock - Get the value to use within the specified basic block. 828/// available values are in Phis. 829Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 830 DenseMap<BasicBlock*, Value*> &Phis, 831 bool top_level) { 832 833 // If we have already computed this value, return the previously computed val. 834 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 835 if (V != Phis.end() && !top_level) return V->second; 836 837 BasicBlock* singlePred = BB->getSinglePredecessor(); 838 if (singlePred) { 839 Value *ret = GetValueForBlock(singlePred, orig, Phis); 840 Phis[BB] = ret; 841 return ret; 842 } 843 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 844 // now, then get values to fill in the incoming values for the PHI. 845 PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", 846 BB->begin()); 847 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 848 849 if (Phis.count(BB) == 0) 850 Phis.insert(std::make_pair(BB, PN)); 851 852 // Fill in the incoming values for the block. 853 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 854 Value* val = GetValueForBlock(*PI, orig, Phis); 855 856 PN->addIncoming(val, *PI); 857 } 858 859 // Attempt to collapse PHI nodes that are trivially redundant 860 Value* v = CollapsePhi(PN); 861 if (v) { 862 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 863 864 MD.removeInstruction(PN); 865 PN->replaceAllUsesWith(v); 866 867 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 868 E = Phis.end(); I != E; ++I) 869 if (I->second == PN) 870 I->second = v; 871 872 PN->eraseFromParent(); 873 874 Phis[BB] = v; 875 876 return v; 877 } 878 879 // Cache our phi construction results 880 phiMap[orig->getPointerOperand()].insert(PN); 881 return PN; 882} 883 884/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 885/// non-local by performing PHI construction. 886bool GVN::processNonLocalLoad(LoadInst* L, 887 SmallVector<Instruction*, 4>& toErase) { 888 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 889 890 // Find the non-local dependencies of the load 891 DenseMap<BasicBlock*, Value*> deps; 892 MD.getNonLocalDependency(L, deps); 893 894 DenseMap<BasicBlock*, Value*> repl; 895 896 // Filter out useless results (non-locals, etc) 897 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 898 I != E; ++I) 899 if (I->second == MemoryDependenceAnalysis::None) { 900 return false; 901 } else if (I->second == MemoryDependenceAnalysis::NonLocal) { 902 continue; 903 } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 904 if (S->getPointerOperand() == L->getPointerOperand()) 905 repl[I->first] = S->getOperand(0); 906 else 907 return false; 908 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 909 if (LD->getPointerOperand() == L->getPointerOperand()) 910 repl[I->first] = LD; 911 else 912 return false; 913 } else { 914 return false; 915 } 916 917 // Use cached PHI construction information from previous runs 918 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 919 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 920 I != E; ++I) { 921 if ((*I)->getParent() == L->getParent()) { 922 MD.removeInstruction(L); 923 L->replaceAllUsesWith(*I); 924 toErase.push_back(L); 925 NumGVNLoad++; 926 927 return true; 928 } else { 929 repl.insert(std::make_pair((*I)->getParent(), *I)); 930 } 931 } 932 933 // Perform PHI construction 934 SmallPtrSet<BasicBlock*, 4> visited; 935 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 936 937 MD.removeInstruction(L); 938 L->replaceAllUsesWith(v); 939 toErase.push_back(L); 940 NumGVNLoad++; 941 942 return true; 943} 944 945/// processLoad - Attempt to eliminate a load, first by eliminating it 946/// locally, and then attempting non-local elimination if that fails. 947bool GVN::processLoad(LoadInst* L, 948 DenseMap<Value*, LoadInst*>& lastLoad, 949 SmallVector<Instruction*, 4>& toErase) { 950 if (L->isVolatile()) { 951 lastLoad[L->getPointerOperand()] = L; 952 return false; 953 } 954 955 Value* pointer = L->getPointerOperand(); 956 LoadInst*& last = lastLoad[pointer]; 957 958 // ... to a pointer that has been loaded from before... 959 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 960 bool removedNonLocal = false; 961 Instruction* dep = MD.getDependency(L); 962 if (dep == MemoryDependenceAnalysis::NonLocal && 963 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 964 removedNonLocal = processNonLocalLoad(L, toErase); 965 966 if (!removedNonLocal) 967 last = L; 968 969 return removedNonLocal; 970 } 971 972 973 bool deletedLoad = false; 974 975 // Walk up the dependency chain until we either find 976 // a dependency we can use, or we can't walk any further 977 while (dep != MemoryDependenceAnalysis::None && 978 dep != MemoryDependenceAnalysis::NonLocal && 979 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 980 // ... that depends on a store ... 981 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 982 if (S->getPointerOperand() == pointer) { 983 // Remove it! 984 MD.removeInstruction(L); 985 986 L->replaceAllUsesWith(S->getOperand(0)); 987 toErase.push_back(L); 988 deletedLoad = true; 989 NumGVNLoad++; 990 } 991 992 // Whether we removed it or not, we can't 993 // go any further 994 break; 995 } else if (!last) { 996 // If we don't depend on a store, and we haven't 997 // been loaded before, bail. 998 break; 999 } else if (dep == last) { 1000 // Remove it! 1001 MD.removeInstruction(L); 1002 1003 L->replaceAllUsesWith(last); 1004 toErase.push_back(L); 1005 deletedLoad = true; 1006 NumGVNLoad++; 1007 1008 break; 1009 } else { 1010 dep = MD.getDependency(L, dep); 1011 } 1012 } 1013 1014 if (!deletedLoad) 1015 last = L; 1016 1017 return deletedLoad; 1018} 1019 1020/// processInstruction - When calculating availability, handle an instruction 1021/// by inserting it into the appropriate sets 1022bool GVN::processInstruction(Instruction* I, 1023 ValueNumberedSet& currAvail, 1024 DenseMap<Value*, LoadInst*>& lastSeenLoad, 1025 SmallVector<Instruction*, 4>& toErase) { 1026 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1027 return processLoad(L, lastSeenLoad, toErase); 1028 } 1029 1030 unsigned num = VN.lookup_or_add(I); 1031 1032 // Collapse PHI nodes 1033 if (PHINode* p = dyn_cast<PHINode>(I)) { 1034 Value* constVal = CollapsePhi(p); 1035 1036 if (constVal) { 1037 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1038 PI != PE; ++PI) 1039 if (PI->second.count(p)) 1040 PI->second.erase(p); 1041 1042 p->replaceAllUsesWith(constVal); 1043 toErase.push_back(p); 1044 } 1045 // Perform value-number based elimination 1046 } else if (currAvail.test(num)) { 1047 Value* repl = find_leader(currAvail, num); 1048 1049 if (CallInst* CI = dyn_cast<CallInst>(I)) { 1050 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 1051 if (!AA.doesNotAccessMemory(CI)) { 1052 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1053 if (cast<Instruction>(repl)->getParent() != CI->getParent() || 1054 MD.getDependency(CI) != MD.getDependency(cast<CallInst>(repl))) { 1055 // There must be an intervening may-alias store, so nothing from 1056 // this point on will be able to be replaced with the preceding call 1057 currAvail.erase(repl); 1058 currAvail.insert(I); 1059 1060 return false; 1061 } 1062 } 1063 } 1064 1065 // Remove it! 1066 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1067 MD.removeInstruction(I); 1068 1069 VN.erase(I); 1070 I->replaceAllUsesWith(repl); 1071 toErase.push_back(I); 1072 return true; 1073 } else if (!I->isTerminator()) { 1074 currAvail.set(num); 1075 currAvail.insert(I); 1076 } 1077 1078 return false; 1079} 1080 1081// GVN::runOnFunction - This is the main transformation entry point for a 1082// function. 1083// 1084bool GVN::runOnFunction(Function& F) { 1085 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1086 1087 bool changed = false; 1088 bool shouldContinue = true; 1089 1090 while (shouldContinue) { 1091 shouldContinue = iterateOnFunction(F); 1092 changed |= shouldContinue; 1093 } 1094 1095 return changed; 1096} 1097 1098 1099// GVN::iterateOnFunction - Executes one iteration of GVN 1100bool GVN::iterateOnFunction(Function &F) { 1101 // Clean out global sets from any previous functions 1102 VN.clear(); 1103 availableOut.clear(); 1104 phiMap.clear(); 1105 1106 bool changed_function = false; 1107 1108 DominatorTree &DT = getAnalysis<DominatorTree>(); 1109 1110 SmallVector<Instruction*, 4> toErase; 1111 1112 // Top-down walk of the dominator tree 1113 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 1114 E = df_end(DT.getRootNode()); DI != E; ++DI) { 1115 1116 // Get the set to update for this block 1117 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 1118 DenseMap<Value*, LoadInst*> lastSeenLoad; 1119 1120 BasicBlock* BB = DI->getBlock(); 1121 1122 // A block inherits AVAIL_OUT from its dominator 1123 if (DI->getIDom() != 0) 1124 currAvail = availableOut[DI->getIDom()->getBlock()]; 1125 1126 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1127 BI != BE; ) { 1128 changed_function |= processInstruction(BI, currAvail, 1129 lastSeenLoad, toErase); 1130 1131 NumGVNInstr += toErase.size(); 1132 1133 // Avoid iterator invalidation 1134 ++BI; 1135 1136 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1137 E = toErase.end(); I != E; ++I) 1138 (*I)->eraseFromParent(); 1139 1140 toErase.clear(); 1141 } 1142 } 1143 1144 return changed_function; 1145} 1146