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