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