GVN.cpp revision 4bda6e47e95204e6d9e7bf2b82e8099e911c722a
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 45/// This class holds the mapping between values and value numbers. It is used 46/// as an efficient mechanism to determine the expression-wise equivalence of 47/// two values. 48namespace { 49 struct VISIBILITY_HIDDEN Expression { 50 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 51 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 52 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 53 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 54 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 55 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 56 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 57 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 58 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 59 PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY, 60 TOMBSTONE }; 61 62 ExpressionOpcode opcode; 63 const Type* type; 64 uint32_t firstVN; 65 uint32_t secondVN; 66 uint32_t thirdVN; 67 SmallVector<uint32_t, 4> varargs; 68 Value* function; 69 70 Expression() { } 71 Expression(ExpressionOpcode o) : opcode(o) { } 72 73 bool operator==(const Expression &other) const { 74 if (opcode != other.opcode) 75 return false; 76 else if (opcode == EMPTY || opcode == TOMBSTONE) 77 return true; 78 else if (type != other.type) 79 return false; 80 else if (function != other.function) 81 return false; 82 else if (firstVN != other.firstVN) 83 return false; 84 else if (secondVN != other.secondVN) 85 return false; 86 else if (thirdVN != other.thirdVN) 87 return false; 88 else { 89 if (varargs.size() != other.varargs.size()) 90 return false; 91 92 for (size_t i = 0; i < varargs.size(); ++i) 93 if (varargs[i] != other.varargs[i]) 94 return false; 95 96 return true; 97 } 98 } 99 100 bool operator!=(const Expression &other) const { 101 if (opcode != other.opcode) 102 return true; 103 else if (opcode == EMPTY || opcode == TOMBSTONE) 104 return false; 105 else if (type != other.type) 106 return true; 107 else if (function != other.function) 108 return true; 109 else if (firstVN != other.firstVN) 110 return true; 111 else if (secondVN != other.secondVN) 112 return true; 113 else if (thirdVN != other.thirdVN) 114 return true; 115 else { 116 if (varargs.size() != other.varargs.size()) 117 return true; 118 119 for (size_t i = 0; i < varargs.size(); ++i) 120 if (varargs[i] != other.varargs[i]) 121 return true; 122 123 return false; 124 } 125 } 126 }; 127 128 class VISIBILITY_HIDDEN ValueTable { 129 private: 130 DenseMap<Value*, uint32_t> valueNumbering; 131 DenseMap<Expression, uint32_t> expressionNumbering; 132 AliasAnalysis* AA; 133 MemoryDependenceAnalysis* MD; 134 135 uint32_t nextValueNumber; 136 137 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 138 Expression::ExpressionOpcode getOpcode(CmpInst* C); 139 Expression::ExpressionOpcode getOpcode(CastInst* C); 140 Expression create_expression(BinaryOperator* BO); 141 Expression create_expression(CmpInst* C); 142 Expression create_expression(ShuffleVectorInst* V); 143 Expression create_expression(ExtractElementInst* C); 144 Expression create_expression(InsertElementInst* V); 145 Expression create_expression(SelectInst* V); 146 Expression create_expression(CastInst* C); 147 Expression create_expression(GetElementPtrInst* G); 148 Expression create_expression(CallInst* C); 149 public: 150 ValueTable() : nextValueNumber(1) { } 151 uint32_t lookup_or_add(Value* V); 152 uint32_t lookup(Value* V) const; 153 void add(Value* V, uint32_t num); 154 void clear(); 155 void erase(Value* v); 156 unsigned size(); 157 void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 158 void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } 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 DominatorTree &DT = getAnalysis<DominatorTree>(); 738 Value* constVal = p->hasConstantValue(); 739 740 if (!constVal) return 0; 741 742 Instruction* inst = dyn_cast<Instruction>(constVal); 743 if (!inst) 744 return constVal; 745 746 if (DT.dominates(inst, p)) 747 if (isSafeReplacement(p, inst)) 748 return inst; 749 return 0; 750} 751 752bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 753 if (!isa<PHINode>(inst)) 754 return true; 755 756 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 757 UI != E; ++UI) 758 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 759 if (use_phi->getParent() == inst->getParent()) 760 return false; 761 762 return true; 763} 764 765/// GetValueForBlock - Get the value to use within the specified basic block. 766/// available values are in Phis. 767Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 768 DenseMap<BasicBlock*, Value*> &Phis, 769 bool top_level) { 770 771 // If we have already computed this value, return the previously computed val. 772 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 773 if (V != Phis.end() && !top_level) return V->second; 774 775 BasicBlock* singlePred = BB->getSinglePredecessor(); 776 if (singlePred) { 777 Value *ret = GetValueForBlock(singlePred, orig, Phis); 778 Phis[BB] = ret; 779 return ret; 780 } 781 782 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 783 // now, then get values to fill in the incoming values for the PHI. 784 PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle", 785 BB->begin()); 786 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 787 788 if (Phis.count(BB) == 0) 789 Phis.insert(std::make_pair(BB, PN)); 790 791 // Fill in the incoming values for the block. 792 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 793 Value* val = GetValueForBlock(*PI, orig, Phis); 794 PN->addIncoming(val, *PI); 795 } 796 797 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 798 AA.copyValue(orig, PN); 799 800 // Attempt to collapse PHI nodes that are trivially redundant 801 Value* v = CollapsePhi(PN); 802 if (!v) { 803 // Cache our phi construction results 804 phiMap[orig->getPointerOperand()].insert(PN); 805 return PN; 806 } 807 808 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 809 810 MD.removeInstruction(PN); 811 PN->replaceAllUsesWith(v); 812 813 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 814 E = Phis.end(); I != E; ++I) 815 if (I->second == PN) 816 I->second = v; 817 818 PN->eraseFromParent(); 819 820 Phis[BB] = v; 821 return v; 822} 823 824/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 825/// non-local by performing PHI construction. 826bool GVN::processNonLocalLoad(LoadInst* L, 827 SmallVectorImpl<Instruction*> &toErase) { 828 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 829 830 // Find the non-local dependencies of the load 831 DenseMap<BasicBlock*, Value*> deps; 832 MD.getNonLocalDependency(L, deps); 833 834 DenseMap<BasicBlock*, Value*> repl; 835 836 // Filter out useless results (non-locals, etc) 837 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 838 I != E; ++I) { 839 if (I->second == MemoryDependenceAnalysis::None) 840 return false; 841 842 if (I->second == MemoryDependenceAnalysis::NonLocal) 843 continue; 844 845 if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 846 if (S->getPointerOperand() != L->getPointerOperand()) 847 return false; 848 repl[I->first] = S->getOperand(0); 849 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 850 if (LD->getPointerOperand() != L->getPointerOperand()) 851 return false; 852 repl[I->first] = LD; 853 } else { 854 return false; 855 } 856 } 857 858 // Use cached PHI construction information from previous runs 859 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 860 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 861 I != E; ++I) { 862 if ((*I)->getParent() == L->getParent()) { 863 MD.removeInstruction(L); 864 L->replaceAllUsesWith(*I); 865 toErase.push_back(L); 866 NumGVNLoad++; 867 return true; 868 } 869 870 repl.insert(std::make_pair((*I)->getParent(), *I)); 871 } 872 873 // Perform PHI construction 874 SmallPtrSet<BasicBlock*, 4> visited; 875 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 876 877 MD.removeInstruction(L); 878 L->replaceAllUsesWith(v); 879 toErase.push_back(L); 880 NumGVNLoad++; 881 882 return true; 883} 884 885/// processLoad - Attempt to eliminate a load, first by eliminating it 886/// locally, and then attempting non-local elimination if that fails. 887bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad, 888 SmallVectorImpl<Instruction*> &toErase) { 889 if (L->isVolatile()) { 890 lastLoad[L->getPointerOperand()] = L; 891 return false; 892 } 893 894 Value* pointer = L->getPointerOperand(); 895 LoadInst*& last = lastLoad[pointer]; 896 897 // ... to a pointer that has been loaded from before... 898 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 899 bool removedNonLocal = false; 900 Instruction* dep = MD.getDependency(L); 901 if (dep == MemoryDependenceAnalysis::NonLocal && 902 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 903 removedNonLocal = processNonLocalLoad(L, toErase); 904 905 if (!removedNonLocal) 906 last = L; 907 908 return removedNonLocal; 909 } 910 911 912 bool deletedLoad = false; 913 914 // Walk up the dependency chain until we either find 915 // a dependency we can use, or we can't walk any further 916 while (dep != MemoryDependenceAnalysis::None && 917 dep != MemoryDependenceAnalysis::NonLocal && 918 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 919 // ... that depends on a store ... 920 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 921 if (S->getPointerOperand() == pointer) { 922 // Remove it! 923 MD.removeInstruction(L); 924 925 L->replaceAllUsesWith(S->getOperand(0)); 926 toErase.push_back(L); 927 deletedLoad = true; 928 NumGVNLoad++; 929 } 930 931 // Whether we removed it or not, we can't 932 // go any further 933 break; 934 } else if (!last) { 935 // If we don't depend on a store, and we haven't 936 // been loaded before, bail. 937 break; 938 } else if (dep == last) { 939 // Remove it! 940 MD.removeInstruction(L); 941 942 L->replaceAllUsesWith(last); 943 toErase.push_back(L); 944 deletedLoad = true; 945 NumGVNLoad++; 946 947 break; 948 } else { 949 dep = MD.getDependency(L, dep); 950 } 951 } 952 953 if (dep != MemoryDependenceAnalysis::None && 954 dep != MemoryDependenceAnalysis::NonLocal && 955 isa<AllocationInst>(dep)) { 956 // Check that this load is actually from the 957 // allocation we found 958 Value* v = L->getOperand(0); 959 while (true) { 960 if (BitCastInst *BC = dyn_cast<BitCastInst>(v)) 961 v = BC->getOperand(0); 962 else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v)) 963 v = GEP->getOperand(0); 964 else 965 break; 966 } 967 if (v == dep) { 968 // If this load depends directly on an allocation, there isn't 969 // anything stored there; therefore, we can optimize this load 970 // to undef. 971 MD.removeInstruction(L); 972 973 L->replaceAllUsesWith(UndefValue::get(L->getType())); 974 toErase.push_back(L); 975 deletedLoad = true; 976 NumGVNLoad++; 977 } 978 } 979 980 if (!deletedLoad) 981 last = L; 982 983 return deletedLoad; 984} 985 986/// processInstruction - When calculating availability, handle an instruction 987/// by inserting it into the appropriate sets 988bool GVN::processInstruction(Instruction *I, ValueNumberedSet &currAvail, 989 DenseMap<Value*, LoadInst*> &lastSeenLoad, 990 SmallVectorImpl<Instruction*> &toErase) { 991 if (LoadInst* L = dyn_cast<LoadInst>(I)) 992 return processLoad(L, lastSeenLoad, toErase); 993 994 // Allocations are always uniquely numbered, so we can save time and memory 995 // by fast failing them. 996 if (isa<AllocationInst>(I)) 997 return false; 998 999 unsigned num = VN.lookup_or_add(I); 1000 1001 // Collapse PHI nodes 1002 if (PHINode* p = dyn_cast<PHINode>(I)) { 1003 Value* constVal = CollapsePhi(p); 1004 1005 if (constVal) { 1006 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1007 PI != PE; ++PI) 1008 if (PI->second.count(p)) 1009 PI->second.erase(p); 1010 1011 p->replaceAllUsesWith(constVal); 1012 toErase.push_back(p); 1013 } 1014 // Perform value-number based elimination 1015 } else if (currAvail.test(num)) { 1016 Value* repl = find_leader(currAvail, num); 1017 1018 // Remove it! 1019 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1020 MD.removeInstruction(I); 1021 1022 VN.erase(I); 1023 I->replaceAllUsesWith(repl); 1024 toErase.push_back(I); 1025 return true; 1026 } else if (!I->isTerminator()) { 1027 currAvail.set(num); 1028 currAvail.insert(I); 1029 } 1030 1031 return false; 1032} 1033 1034// GVN::runOnFunction - This is the main transformation entry point for a 1035// function. 1036// 1037bool GVN::runOnFunction(Function& F) { 1038 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1039 VN.setMemDep(&getAnalysis<MemoryDependenceAnalysis>()); 1040 1041 bool changed = false; 1042 bool shouldContinue = true; 1043 1044 while (shouldContinue) { 1045 shouldContinue = iterateOnFunction(F); 1046 changed |= shouldContinue; 1047 } 1048 1049 return changed; 1050} 1051 1052 1053// GVN::iterateOnFunction - Executes one iteration of GVN 1054bool GVN::iterateOnFunction(Function &F) { 1055 // Clean out global sets from any previous functions 1056 VN.clear(); 1057 availableOut.clear(); 1058 phiMap.clear(); 1059 1060 bool changed_function = false; 1061 1062 DominatorTree &DT = getAnalysis<DominatorTree>(); 1063 1064 SmallVector<Instruction*, 8> toErase; 1065 DenseMap<Value*, LoadInst*> lastSeenLoad; 1066 DenseMap<DomTreeNode*, size_t> numChildrenVisited; 1067 1068 // Top-down walk of the dominator tree 1069 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 1070 E = df_end(DT.getRootNode()); DI != E; ++DI) { 1071 1072 // Get the set to update for this block 1073 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 1074 lastSeenLoad.clear(); 1075 1076 BasicBlock* BB = DI->getBlock(); 1077 1078 // A block inherits AVAIL_OUT from its dominator 1079 if (DI->getIDom() != 0) { 1080 currAvail = availableOut[DI->getIDom()->getBlock()]; 1081 1082 numChildrenVisited[DI->getIDom()]++; 1083 1084 if (numChildrenVisited[DI->getIDom()] == DI->getIDom()->getNumChildren()) { 1085 availableOut.erase(DI->getIDom()->getBlock()); 1086 numChildrenVisited.erase(DI->getIDom()); 1087 } 1088 } 1089 1090 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1091 BI != BE;) { 1092 changed_function |= processInstruction(BI, currAvail, 1093 lastSeenLoad, toErase); 1094 if (toErase.empty()) { 1095 ++BI; 1096 continue; 1097 } 1098 1099 // If we need some instructions deleted, do it now. 1100 NumGVNInstr += toErase.size(); 1101 1102 // Avoid iterator invalidation. 1103 bool AtStart = BI == BB->begin(); 1104 if (!AtStart) 1105 --BI; 1106 1107 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1108 E = toErase.end(); I != E; ++I) 1109 (*I)->eraseFromParent(); 1110 1111 if (AtStart) 1112 BI = BB->begin(); 1113 else 1114 ++BI; 1115 1116 toErase.clear(); 1117 } 1118 } 1119 1120 return changed_function; 1121} 1122