GVN.cpp revision 8295e49e768d0ece4204d41416d500f572a3faf8
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// Note that this pass does the value numbering itself, it does not use the 14// ValueNumbering analysis passes. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "gvn" 19#include "llvm/Transforms/Scalar.h" 20#include "llvm/BasicBlock.h" 21#include "llvm/Constants.h" 22#include "llvm/DerivedTypes.h" 23#include "llvm/Function.h" 24#include "llvm/Instructions.h" 25#include "llvm/Value.h" 26#include "llvm/ADT/DenseMap.h" 27#include "llvm/ADT/DepthFirstIterator.h" 28#include "llvm/ADT/SmallPtrSet.h" 29#include "llvm/ADT/SmallVector.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/Transforms/Utils/BasicBlockUtils.h" 39#include <cstdio> 40using namespace llvm; 41 42STATISTIC(NumGVNInstr, "Number of instructions deleted"); 43STATISTIC(NumGVNLoad, "Number of loads deleted"); 44STATISTIC(NumGVNPRE, "Number of instructions PRE'd"); 45STATISTIC(NumGVNBlocks, "Number of blocks merged"); 46STATISTIC(NumPRELoad, "Number of loads PRE'd"); 47 48static cl::opt<bool> EnablePRE("enable-pre", 49 cl::init(true), cl::Hidden); 50cl::opt<bool> EnableLoadPRE("enable-load-pre"/*, cl::init(true)*/); 51 52//===----------------------------------------------------------------------===// 53// ValueTable Class 54//===----------------------------------------------------------------------===// 55 56/// This class holds the mapping between values and value numbers. It is used 57/// as an efficient mechanism to determine the expression-wise equivalence of 58/// two values. 59namespace { 60 struct VISIBILITY_HIDDEN Expression { 61 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 62 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 63 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 64 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 65 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 66 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 67 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 68 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 69 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 70 PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT, 71 EMPTY, TOMBSTONE }; 72 73 ExpressionOpcode opcode; 74 const Type* type; 75 uint32_t firstVN; 76 uint32_t secondVN; 77 uint32_t thirdVN; 78 SmallVector<uint32_t, 4> varargs; 79 Value* function; 80 81 Expression() { } 82 Expression(ExpressionOpcode o) : opcode(o) { } 83 84 bool operator==(const Expression &other) const { 85 if (opcode != other.opcode) 86 return false; 87 else if (opcode == EMPTY || opcode == TOMBSTONE) 88 return true; 89 else if (type != other.type) 90 return false; 91 else if (function != other.function) 92 return false; 93 else if (firstVN != other.firstVN) 94 return false; 95 else if (secondVN != other.secondVN) 96 return false; 97 else if (thirdVN != other.thirdVN) 98 return false; 99 else { 100 if (varargs.size() != other.varargs.size()) 101 return false; 102 103 for (size_t i = 0; i < varargs.size(); ++i) 104 if (varargs[i] != other.varargs[i]) 105 return false; 106 107 return true; 108 } 109 } 110 111 bool operator!=(const Expression &other) const { 112 if (opcode != other.opcode) 113 return true; 114 else if (opcode == EMPTY || opcode == TOMBSTONE) 115 return false; 116 else if (type != other.type) 117 return true; 118 else if (function != other.function) 119 return true; 120 else if (firstVN != other.firstVN) 121 return true; 122 else if (secondVN != other.secondVN) 123 return true; 124 else if (thirdVN != other.thirdVN) 125 return true; 126 else { 127 if (varargs.size() != other.varargs.size()) 128 return true; 129 130 for (size_t i = 0; i < varargs.size(); ++i) 131 if (varargs[i] != other.varargs[i]) 132 return true; 133 134 return false; 135 } 136 } 137 }; 138 139 class VISIBILITY_HIDDEN ValueTable { 140 private: 141 DenseMap<Value*, uint32_t> valueNumbering; 142 DenseMap<Expression, uint32_t> expressionNumbering; 143 AliasAnalysis* AA; 144 MemoryDependenceAnalysis* MD; 145 DominatorTree* DT; 146 147 uint32_t nextValueNumber; 148 149 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 150 Expression::ExpressionOpcode getOpcode(CmpInst* C); 151 Expression::ExpressionOpcode getOpcode(CastInst* C); 152 Expression create_expression(BinaryOperator* BO); 153 Expression create_expression(CmpInst* C); 154 Expression create_expression(ShuffleVectorInst* V); 155 Expression create_expression(ExtractElementInst* C); 156 Expression create_expression(InsertElementInst* V); 157 Expression create_expression(SelectInst* V); 158 Expression create_expression(CastInst* C); 159 Expression create_expression(GetElementPtrInst* G); 160 Expression create_expression(CallInst* C); 161 Expression create_expression(Constant* C); 162 public: 163 ValueTable() : nextValueNumber(1) { } 164 uint32_t lookup_or_add(Value* V); 165 uint32_t lookup(Value* V) const; 166 void add(Value* V, uint32_t num); 167 void clear(); 168 void erase(Value* v); 169 unsigned size(); 170 void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 171 AliasAnalysis *getAliasAnalysis() const { return AA; } 172 void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } 173 void setDomTree(DominatorTree* D) { DT = D; } 174 uint32_t getNextUnusedValueNumber() { return nextValueNumber; } 175 }; 176} 177 178namespace llvm { 179template <> struct DenseMapInfo<Expression> { 180 static inline Expression getEmptyKey() { 181 return Expression(Expression::EMPTY); 182 } 183 184 static inline Expression getTombstoneKey() { 185 return Expression(Expression::TOMBSTONE); 186 } 187 188 static unsigned getHashValue(const Expression e) { 189 unsigned hash = e.opcode; 190 191 hash = e.firstVN + hash * 37; 192 hash = e.secondVN + hash * 37; 193 hash = e.thirdVN + hash * 37; 194 195 hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 196 (unsigned)((uintptr_t)e.type >> 9)) + 197 hash * 37; 198 199 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 200 E = e.varargs.end(); I != E; ++I) 201 hash = *I + hash * 37; 202 203 hash = ((unsigned)((uintptr_t)e.function >> 4) ^ 204 (unsigned)((uintptr_t)e.function >> 9)) + 205 hash * 37; 206 207 return hash; 208 } 209 static bool isEqual(const Expression &LHS, const Expression &RHS) { 210 return LHS == RHS; 211 } 212 static bool isPod() { return true; } 213}; 214} 215 216//===----------------------------------------------------------------------===// 217// ValueTable Internal Functions 218//===----------------------------------------------------------------------===// 219Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) { 220 switch(BO->getOpcode()) { 221 default: // THIS SHOULD NEVER HAPPEN 222 assert(0 && "Binary operator with unknown opcode?"); 223 case Instruction::Add: return Expression::ADD; 224 case Instruction::Sub: return Expression::SUB; 225 case Instruction::Mul: return Expression::MUL; 226 case Instruction::UDiv: return Expression::UDIV; 227 case Instruction::SDiv: return Expression::SDIV; 228 case Instruction::FDiv: return Expression::FDIV; 229 case Instruction::URem: return Expression::UREM; 230 case Instruction::SRem: return Expression::SREM; 231 case Instruction::FRem: return Expression::FREM; 232 case Instruction::Shl: return Expression::SHL; 233 case Instruction::LShr: return Expression::LSHR; 234 case Instruction::AShr: return Expression::ASHR; 235 case Instruction::And: return Expression::AND; 236 case Instruction::Or: return Expression::OR; 237 case Instruction::Xor: return Expression::XOR; 238 } 239} 240 241Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 242 if (isa<ICmpInst>(C) || isa<VICmpInst>(C)) { 243 switch (C->getPredicate()) { 244 default: // THIS SHOULD NEVER HAPPEN 245 assert(0 && "Comparison with unknown predicate?"); 246 case ICmpInst::ICMP_EQ: return Expression::ICMPEQ; 247 case ICmpInst::ICMP_NE: return Expression::ICMPNE; 248 case ICmpInst::ICMP_UGT: return Expression::ICMPUGT; 249 case ICmpInst::ICMP_UGE: return Expression::ICMPUGE; 250 case ICmpInst::ICMP_ULT: return Expression::ICMPULT; 251 case ICmpInst::ICMP_ULE: return Expression::ICMPULE; 252 case ICmpInst::ICMP_SGT: return Expression::ICMPSGT; 253 case ICmpInst::ICMP_SGE: return Expression::ICMPSGE; 254 case ICmpInst::ICMP_SLT: return Expression::ICMPSLT; 255 case ICmpInst::ICMP_SLE: return Expression::ICMPSLE; 256 } 257 } 258 assert((isa<FCmpInst>(C) || isa<VFCmpInst>(C)) && "Unknown compare"); 259 switch (C->getPredicate()) { 260 default: // THIS SHOULD NEVER HAPPEN 261 assert(0 && "Comparison with unknown predicate?"); 262 case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ; 263 case FCmpInst::FCMP_OGT: return Expression::FCMPOGT; 264 case FCmpInst::FCMP_OGE: return Expression::FCMPOGE; 265 case FCmpInst::FCMP_OLT: return Expression::FCMPOLT; 266 case FCmpInst::FCMP_OLE: return Expression::FCMPOLE; 267 case FCmpInst::FCMP_ONE: return Expression::FCMPONE; 268 case FCmpInst::FCMP_ORD: return Expression::FCMPORD; 269 case FCmpInst::FCMP_UNO: return Expression::FCMPUNO; 270 case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ; 271 case FCmpInst::FCMP_UGT: return Expression::FCMPUGT; 272 case FCmpInst::FCMP_UGE: return Expression::FCMPUGE; 273 case FCmpInst::FCMP_ULT: return Expression::FCMPULT; 274 case FCmpInst::FCMP_ULE: return Expression::FCMPULE; 275 case FCmpInst::FCMP_UNE: return Expression::FCMPUNE; 276 } 277} 278 279Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) { 280 switch(C->getOpcode()) { 281 default: // THIS SHOULD NEVER HAPPEN 282 assert(0 && "Cast operator with unknown opcode?"); 283 case Instruction::Trunc: return Expression::TRUNC; 284 case Instruction::ZExt: return Expression::ZEXT; 285 case Instruction::SExt: return Expression::SEXT; 286 case Instruction::FPToUI: return Expression::FPTOUI; 287 case Instruction::FPToSI: return Expression::FPTOSI; 288 case Instruction::UIToFP: return Expression::UITOFP; 289 case Instruction::SIToFP: return Expression::SITOFP; 290 case Instruction::FPTrunc: return Expression::FPTRUNC; 291 case Instruction::FPExt: return Expression::FPEXT; 292 case Instruction::PtrToInt: return Expression::PTRTOINT; 293 case Instruction::IntToPtr: return Expression::INTTOPTR; 294 case Instruction::BitCast: return Expression::BITCAST; 295 } 296} 297 298Expression ValueTable::create_expression(CallInst* C) { 299 Expression e; 300 301 e.type = C->getType(); 302 e.firstVN = 0; 303 e.secondVN = 0; 304 e.thirdVN = 0; 305 e.function = C->getCalledFunction(); 306 e.opcode = Expression::CALL; 307 308 for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 309 I != E; ++I) 310 e.varargs.push_back(lookup_or_add(*I)); 311 312 return e; 313} 314 315Expression ValueTable::create_expression(BinaryOperator* BO) { 316 Expression e; 317 318 e.firstVN = lookup_or_add(BO->getOperand(0)); 319 e.secondVN = lookup_or_add(BO->getOperand(1)); 320 e.thirdVN = 0; 321 e.function = 0; 322 e.type = BO->getType(); 323 e.opcode = getOpcode(BO); 324 325 return e; 326} 327 328Expression ValueTable::create_expression(CmpInst* C) { 329 Expression e; 330 331 e.firstVN = lookup_or_add(C->getOperand(0)); 332 e.secondVN = lookup_or_add(C->getOperand(1)); 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(CastInst* C) { 342 Expression e; 343 344 e.firstVN = lookup_or_add(C->getOperand(0)); 345 e.secondVN = 0; 346 e.thirdVN = 0; 347 e.function = 0; 348 e.type = C->getType(); 349 e.opcode = getOpcode(C); 350 351 return e; 352} 353 354Expression ValueTable::create_expression(ShuffleVectorInst* S) { 355 Expression e; 356 357 e.firstVN = lookup_or_add(S->getOperand(0)); 358 e.secondVN = lookup_or_add(S->getOperand(1)); 359 e.thirdVN = lookup_or_add(S->getOperand(2)); 360 e.function = 0; 361 e.type = S->getType(); 362 e.opcode = Expression::SHUFFLE; 363 364 return e; 365} 366 367Expression ValueTable::create_expression(ExtractElementInst* E) { 368 Expression e; 369 370 e.firstVN = lookup_or_add(E->getOperand(0)); 371 e.secondVN = lookup_or_add(E->getOperand(1)); 372 e.thirdVN = 0; 373 e.function = 0; 374 e.type = E->getType(); 375 e.opcode = Expression::EXTRACT; 376 377 return e; 378} 379 380Expression ValueTable::create_expression(InsertElementInst* I) { 381 Expression e; 382 383 e.firstVN = lookup_or_add(I->getOperand(0)); 384 e.secondVN = lookup_or_add(I->getOperand(1)); 385 e.thirdVN = lookup_or_add(I->getOperand(2)); 386 e.function = 0; 387 e.type = I->getType(); 388 e.opcode = Expression::INSERT; 389 390 return e; 391} 392 393Expression ValueTable::create_expression(SelectInst* I) { 394 Expression e; 395 396 e.firstVN = lookup_or_add(I->getCondition()); 397 e.secondVN = lookup_or_add(I->getTrueValue()); 398 e.thirdVN = lookup_or_add(I->getFalseValue()); 399 e.function = 0; 400 e.type = I->getType(); 401 e.opcode = Expression::SELECT; 402 403 return e; 404} 405 406Expression ValueTable::create_expression(GetElementPtrInst* G) { 407 Expression e; 408 409 e.firstVN = lookup_or_add(G->getPointerOperand()); 410 e.secondVN = 0; 411 e.thirdVN = 0; 412 e.function = 0; 413 e.type = G->getType(); 414 e.opcode = Expression::GEP; 415 416 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 417 I != E; ++I) 418 e.varargs.push_back(lookup_or_add(*I)); 419 420 return e; 421} 422 423//===----------------------------------------------------------------------===// 424// ValueTable External Functions 425//===----------------------------------------------------------------------===// 426 427/// add - Insert a value into the table with a specified value number. 428void ValueTable::add(Value* V, uint32_t num) { 429 valueNumbering.insert(std::make_pair(V, num)); 430} 431 432/// lookup_or_add - Returns the value number for the specified value, assigning 433/// it a new number if it did not have one before. 434uint32_t ValueTable::lookup_or_add(Value* V) { 435 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 436 if (VI != valueNumbering.end()) 437 return VI->second; 438 439 if (CallInst* C = dyn_cast<CallInst>(V)) { 440 if (AA->doesNotAccessMemory(C)) { 441 Expression e = create_expression(C); 442 443 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 444 if (EI != expressionNumbering.end()) { 445 valueNumbering.insert(std::make_pair(V, EI->second)); 446 return EI->second; 447 } else { 448 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 449 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 450 451 return nextValueNumber++; 452 } 453 } else if (AA->onlyReadsMemory(C)) { 454 Expression e = create_expression(C); 455 456 if (expressionNumbering.find(e) == expressionNumbering.end()) { 457 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 458 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 459 return nextValueNumber++; 460 } 461 462 MemDepResult local_dep = MD->getDependency(C); 463 464 if (!local_dep.isDef() && !local_dep.isNonLocal()) { 465 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 466 return nextValueNumber++; 467 } 468 469 if (local_dep.isDef()) { 470 CallInst* local_cdep = cast<CallInst>(local_dep.getInst()); 471 472 if (local_cdep->getNumOperands() != C->getNumOperands()) { 473 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 474 return nextValueNumber++; 475 } 476 477 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 478 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 479 uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); 480 if (c_vn != cd_vn) { 481 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 482 return nextValueNumber++; 483 } 484 } 485 486 uint32_t v = lookup_or_add(local_cdep); 487 valueNumbering.insert(std::make_pair(V, v)); 488 return v; 489 } 490 491 // Non-local case. 492 const MemoryDependenceAnalysis::NonLocalDepInfo &deps = 493 MD->getNonLocalCallDependency(CallSite(C)); 494 // FIXME: call/call dependencies for readonly calls should return def, not 495 // clobber! Move the checking logic to MemDep! 496 CallInst* cdep = 0; 497 498 // Check to see if we have a single dominating call instruction that is 499 // identical to C. 500 for (unsigned i = 0, e = deps.size(); i != e; ++i) { 501 const MemoryDependenceAnalysis::NonLocalDepEntry *I = &deps[i]; 502 // Ignore non-local dependencies. 503 if (I->second.isNonLocal()) 504 continue; 505 506 // We don't handle non-depedencies. If we already have a call, reject 507 // instruction dependencies. 508 if (I->second.isClobber() || cdep != 0) { 509 cdep = 0; 510 break; 511 } 512 513 CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->second.getInst()); 514 // FIXME: All duplicated with non-local case. 515 if (NonLocalDepCall && DT->properlyDominates(I->first, C->getParent())){ 516 cdep = NonLocalDepCall; 517 continue; 518 } 519 520 cdep = 0; 521 break; 522 } 523 524 if (!cdep) { 525 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 526 return nextValueNumber++; 527 } 528 529 if (cdep->getNumOperands() != C->getNumOperands()) { 530 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 531 return nextValueNumber++; 532 } 533 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 534 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 535 uint32_t cd_vn = lookup_or_add(cdep->getOperand(i)); 536 if (c_vn != cd_vn) { 537 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 538 return nextValueNumber++; 539 } 540 } 541 542 uint32_t v = lookup_or_add(cdep); 543 valueNumbering.insert(std::make_pair(V, v)); 544 return v; 545 546 } else { 547 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 548 return nextValueNumber++; 549 } 550 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 551 Expression e = create_expression(BO); 552 553 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 554 if (EI != expressionNumbering.end()) { 555 valueNumbering.insert(std::make_pair(V, EI->second)); 556 return EI->second; 557 } else { 558 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 559 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 560 561 return nextValueNumber++; 562 } 563 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 564 Expression e = create_expression(C); 565 566 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 567 if (EI != expressionNumbering.end()) { 568 valueNumbering.insert(std::make_pair(V, EI->second)); 569 return EI->second; 570 } else { 571 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 572 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 573 574 return nextValueNumber++; 575 } 576 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 577 Expression e = create_expression(U); 578 579 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 580 if (EI != expressionNumbering.end()) { 581 valueNumbering.insert(std::make_pair(V, EI->second)); 582 return EI->second; 583 } else { 584 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 585 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 586 587 return nextValueNumber++; 588 } 589 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 590 Expression e = create_expression(U); 591 592 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 593 if (EI != expressionNumbering.end()) { 594 valueNumbering.insert(std::make_pair(V, EI->second)); 595 return EI->second; 596 } else { 597 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 598 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 599 600 return nextValueNumber++; 601 } 602 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 603 Expression e = create_expression(U); 604 605 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 606 if (EI != expressionNumbering.end()) { 607 valueNumbering.insert(std::make_pair(V, EI->second)); 608 return EI->second; 609 } else { 610 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 611 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 612 613 return nextValueNumber++; 614 } 615 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 616 Expression e = create_expression(U); 617 618 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 619 if (EI != expressionNumbering.end()) { 620 valueNumbering.insert(std::make_pair(V, EI->second)); 621 return EI->second; 622 } else { 623 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 624 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 625 626 return nextValueNumber++; 627 } 628 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 629 Expression e = create_expression(U); 630 631 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 632 if (EI != expressionNumbering.end()) { 633 valueNumbering.insert(std::make_pair(V, EI->second)); 634 return EI->second; 635 } else { 636 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 637 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 638 639 return nextValueNumber++; 640 } 641 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 642 Expression e = create_expression(U); 643 644 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 645 if (EI != expressionNumbering.end()) { 646 valueNumbering.insert(std::make_pair(V, EI->second)); 647 return EI->second; 648 } else { 649 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 650 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 651 652 return nextValueNumber++; 653 } 654 } else { 655 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 656 return nextValueNumber++; 657 } 658} 659 660/// lookup - Returns the value number of the specified value. Fails if 661/// the value has not yet been numbered. 662uint32_t ValueTable::lookup(Value* V) const { 663 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 664 assert(VI != valueNumbering.end() && "Value not numbered?"); 665 return VI->second; 666} 667 668/// clear - Remove all entries from the ValueTable 669void ValueTable::clear() { 670 valueNumbering.clear(); 671 expressionNumbering.clear(); 672 nextValueNumber = 1; 673} 674 675/// erase - Remove a value from the value numbering 676void ValueTable::erase(Value* V) { 677 valueNumbering.erase(V); 678} 679 680//===----------------------------------------------------------------------===// 681// GVN Pass 682//===----------------------------------------------------------------------===// 683 684namespace { 685 struct VISIBILITY_HIDDEN ValueNumberScope { 686 ValueNumberScope* parent; 687 DenseMap<uint32_t, Value*> table; 688 689 ValueNumberScope(ValueNumberScope* p) : parent(p) { } 690 }; 691} 692 693namespace { 694 695 class VISIBILITY_HIDDEN GVN : public FunctionPass { 696 bool runOnFunction(Function &F); 697 public: 698 static char ID; // Pass identification, replacement for typeid 699 GVN() : FunctionPass(&ID) { } 700 701 private: 702 MemoryDependenceAnalysis *MD; 703 DominatorTree *DT; 704 705 ValueTable VN; 706 DenseMap<BasicBlock*, ValueNumberScope*> localAvail; 707 708 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 709 PhiMapType phiMap; 710 711 712 // This transformation requires dominator postdominator info 713 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 714 AU.addRequired<DominatorTree>(); 715 AU.addRequired<MemoryDependenceAnalysis>(); 716 AU.addRequired<AliasAnalysis>(); 717 718 AU.addPreserved<DominatorTree>(); 719 AU.addPreserved<AliasAnalysis>(); 720 } 721 722 // Helper fuctions 723 // FIXME: eliminate or document these better 724 bool processLoad(LoadInst* L, 725 SmallVectorImpl<Instruction*> &toErase); 726 bool processInstruction(Instruction* I, 727 SmallVectorImpl<Instruction*> &toErase); 728 bool processNonLocalLoad(LoadInst* L, 729 SmallVectorImpl<Instruction*> &toErase); 730 bool processBlock(DomTreeNode* DTN); 731 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 732 DenseMap<BasicBlock*, Value*> &Phis, 733 bool top_level = false); 734 void dump(DenseMap<uint32_t, Value*>& d); 735 bool iterateOnFunction(Function &F); 736 Value* CollapsePhi(PHINode* p); 737 bool isSafeReplacement(PHINode* p, Instruction* inst); 738 bool performPRE(Function& F); 739 Value* lookupNumber(BasicBlock* BB, uint32_t num); 740 bool mergeBlockIntoPredecessor(BasicBlock* BB); 741 void cleanupGlobalSets(); 742 }; 743 744 char GVN::ID = 0; 745} 746 747// createGVNPass - The public interface to this file... 748FunctionPass *llvm::createGVNPass() { return new GVN(); } 749 750static RegisterPass<GVN> X("gvn", 751 "Global Value Numbering"); 752 753void GVN::dump(DenseMap<uint32_t, Value*>& d) { 754 printf("{\n"); 755 for (DenseMap<uint32_t, Value*>::iterator I = d.begin(), 756 E = d.end(); I != E; ++I) { 757 printf("%d\n", I->first); 758 I->second->dump(); 759 } 760 printf("}\n"); 761} 762 763Value* GVN::CollapsePhi(PHINode* p) { 764 Value* constVal = p->hasConstantValue(); 765 if (!constVal) return 0; 766 767 Instruction* inst = dyn_cast<Instruction>(constVal); 768 if (!inst) 769 return constVal; 770 771 if (DT->dominates(inst, p)) 772 if (isSafeReplacement(p, inst)) 773 return inst; 774 return 0; 775} 776 777bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 778 if (!isa<PHINode>(inst)) 779 return true; 780 781 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 782 UI != E; ++UI) 783 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 784 if (use_phi->getParent() == inst->getParent()) 785 return false; 786 787 return true; 788} 789 790/// GetValueForBlock - Get the value to use within the specified basic block. 791/// available values are in Phis. 792Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 793 DenseMap<BasicBlock*, Value*> &Phis, 794 bool top_level) { 795 796 // If we have already computed this value, return the previously computed val. 797 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 798 if (V != Phis.end() && !top_level) return V->second; 799 800 // If the block is unreachable, just return undef, since this path 801 // can't actually occur at runtime. 802 if (!DT->isReachableFromEntry(BB)) 803 return Phis[BB] = UndefValue::get(orig->getType()); 804 805 if (BasicBlock *Pred = BB->getSinglePredecessor()) { 806 Value *ret = GetValueForBlock(Pred, orig, Phis); 807 Phis[BB] = ret; 808 return ret; 809 } 810 811 // Get the number of predecessors of this block so we can reserve space later. 812 // If there is already a PHI in it, use the #preds from it, otherwise count. 813 // Getting it from the PHI is constant time. 814 unsigned NumPreds; 815 if (PHINode *ExistingPN = dyn_cast<PHINode>(BB->begin())) 816 NumPreds = ExistingPN->getNumIncomingValues(); 817 else 818 NumPreds = std::distance(pred_begin(BB), pred_end(BB)); 819 820 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 821 // now, then get values to fill in the incoming values for the PHI. 822 PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle", 823 BB->begin()); 824 PN->reserveOperandSpace(NumPreds); 825 826 Phis.insert(std::make_pair(BB, PN)); 827 828 // Fill in the incoming values for the block. 829 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 830 Value* val = GetValueForBlock(*PI, orig, Phis); 831 PN->addIncoming(val, *PI); 832 } 833 834 VN.getAliasAnalysis()->copyValue(orig, PN); 835 836 // Attempt to collapse PHI nodes that are trivially redundant 837 Value* v = CollapsePhi(PN); 838 if (!v) { 839 // Cache our phi construction results 840 phiMap[orig->getPointerOperand()].insert(PN); 841 return PN; 842 } 843 844 PN->replaceAllUsesWith(v); 845 if (isa<PointerType>(v->getType())) 846 MD->invalidateCachedPointerInfo(v); 847 848 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 849 E = Phis.end(); I != E; ++I) 850 if (I->second == PN) 851 I->second = v; 852 853 DEBUG(cerr << "GVN removed: " << *PN); 854 MD->removeInstruction(PN); 855 PN->eraseFromParent(); 856 857 Phis[BB] = v; 858 return v; 859} 860 861/// IsValueFullyAvailableInBlock - Return true if we can prove that the value 862/// we're analyzing is fully available in the specified block. As we go, keep 863/// track of which blocks we know are fully alive in FullyAvailableBlocks. This 864/// map is actually a tri-state map with the following values: 865/// 0) we know the block *is not* fully available. 866/// 1) we know the block *is* fully available. 867/// 2) we do not know whether the block is fully available or not, but we are 868/// currently speculating that it will be. 869/// 3) we are speculating for this block and have used that to speculate for 870/// other blocks. 871static bool IsValueFullyAvailableInBlock(BasicBlock *BB, 872 DenseMap<BasicBlock*, char> &FullyAvailableBlocks) { 873 // Optimistically assume that the block is fully available and check to see 874 // if we already know about this block in one lookup. 875 std::pair<DenseMap<BasicBlock*, char>::iterator, char> IV = 876 FullyAvailableBlocks.insert(std::make_pair(BB, 2)); 877 878 // If the entry already existed for this block, return the precomputed value. 879 if (!IV.second) { 880 // If this is a speculative "available" value, mark it as being used for 881 // speculation of other blocks. 882 if (IV.first->second == 2) 883 IV.first->second = 3; 884 return IV.first->second != 0; 885 } 886 887 // Otherwise, see if it is fully available in all predecessors. 888 pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 889 890 // If this block has no predecessors, it isn't live-in here. 891 if (PI == PE) 892 goto SpeculationFailure; 893 894 for (; PI != PE; ++PI) 895 // If the value isn't fully available in one of our predecessors, then it 896 // isn't fully available in this block either. Undo our previous 897 // optimistic assumption and bail out. 898 if (!IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks)) 899 goto SpeculationFailure; 900 901 return true; 902 903// SpeculationFailure - If we get here, we found out that this is not, after 904// all, a fully-available block. We have a problem if we speculated on this and 905// used the speculation to mark other blocks as available. 906SpeculationFailure: 907 char &BBVal = FullyAvailableBlocks[BB]; 908 909 // If we didn't speculate on this, just return with it set to false. 910 if (BBVal == 2) { 911 BBVal = 0; 912 return false; 913 } 914 915 // If we did speculate on this value, we could have blocks set to 1 that are 916 // incorrect. Walk the (transitive) successors of this block and mark them as 917 // 0 if set to one. 918 SmallVector<BasicBlock*, 32> BBWorklist; 919 BBWorklist.push_back(BB); 920 921 while (!BBWorklist.empty()) { 922 BasicBlock *Entry = BBWorklist.pop_back_val(); 923 // Note that this sets blocks to 0 (unavailable) if they happen to not 924 // already be in FullyAvailableBlocks. This is safe. 925 char &EntryVal = FullyAvailableBlocks[Entry]; 926 if (EntryVal == 0) continue; // Already unavailable. 927 928 // Mark as unavailable. 929 EntryVal = 0; 930 931 for (succ_iterator I = succ_begin(Entry), E = succ_end(Entry); I != E; ++I) 932 BBWorklist.push_back(*I); 933 } 934 935 return false; 936} 937 938/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 939/// non-local by performing PHI construction. 940bool GVN::processNonLocalLoad(LoadInst *LI, 941 SmallVectorImpl<Instruction*> &toErase) { 942 // Find the non-local dependencies of the load. 943 SmallVector<MemoryDependenceAnalysis::NonLocalDepEntry, 64> Deps; 944 MD->getNonLocalPointerDependency(LI->getOperand(0), true, LI->getParent(), 945 Deps); 946 //DEBUG(cerr << "INVESTIGATING NONLOCAL LOAD: " << Deps.size() << *LI); 947 948 // If we had to process more than one hundred blocks to find the 949 // dependencies, this load isn't worth worrying about. Optimizing 950 // it will be too expensive. 951 if (Deps.size() > 100) 952 return false; 953 954 // Filter out useless results (non-locals, etc). Keep track of the blocks 955 // where we have a value available in repl, also keep track of whether we see 956 // dependencies that produce an unknown value for the load (such as a call 957 // that could potentially clobber the load). 958 SmallVector<std::pair<BasicBlock*, Value*>, 16> ValuesPerBlock; 959 SmallVector<BasicBlock*, 16> UnavailableBlocks; 960 961 for (unsigned i = 0, e = Deps.size(); i != e; ++i) { 962 BasicBlock *DepBB = Deps[i].first; 963 MemDepResult DepInfo = Deps[i].second; 964 965 if (DepInfo.isClobber()) { 966 UnavailableBlocks.push_back(DepBB); 967 continue; 968 } 969 970 Instruction *DepInst = DepInfo.getInst(); 971 972 // Loading the allocation -> undef. 973 if (isa<AllocationInst>(DepInst)) { 974 ValuesPerBlock.push_back(std::make_pair(DepBB, 975 UndefValue::get(LI->getType()))); 976 continue; 977 } 978 979 if (StoreInst* S = dyn_cast<StoreInst>(DepInst)) { 980 // Reject loads and stores that are to the same address but are of 981 // different types. 982 // NOTE: 403.gcc does have this case (e.g. in readonly_fields_p) because 983 // of bitfield access, it would be interesting to optimize for it at some 984 // point. 985 if (S->getOperand(0)->getType() != LI->getType()) { 986 UnavailableBlocks.push_back(DepBB); 987 continue; 988 } 989 990 ValuesPerBlock.push_back(std::make_pair(DepBB, S->getOperand(0))); 991 992 } else if (LoadInst* LD = dyn_cast<LoadInst>(DepInst)) { 993 if (LD->getType() != LI->getType()) { 994 UnavailableBlocks.push_back(DepBB); 995 continue; 996 } 997 ValuesPerBlock.push_back(std::make_pair(DepBB, LD)); 998 } else { 999 UnavailableBlocks.push_back(DepBB); 1000 continue; 1001 } 1002 } 1003 1004 // If we have no predecessors that produce a known value for this load, exit 1005 // early. 1006 if (ValuesPerBlock.empty()) return false; 1007 1008 // If all of the instructions we depend on produce a known value for this 1009 // load, then it is fully redundant and we can use PHI insertion to compute 1010 // its value. Insert PHIs and remove the fully redundant value now. 1011 if (UnavailableBlocks.empty()) { 1012 // Use cached PHI construction information from previous runs 1013 SmallPtrSet<Instruction*, 4> &p = phiMap[LI->getPointerOperand()]; 1014 // FIXME: What does phiMap do? Are we positive it isn't getting invalidated? 1015 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 1016 I != E; ++I) { 1017 if ((*I)->getParent() == LI->getParent()) { 1018 DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD #1: " << *LI); 1019 LI->replaceAllUsesWith(*I); 1020 if (isa<PointerType>((*I)->getType())) 1021 MD->invalidateCachedPointerInfo(*I); 1022 toErase.push_back(LI); 1023 NumGVNLoad++; 1024 return true; 1025 } 1026 1027 ValuesPerBlock.push_back(std::make_pair((*I)->getParent(), *I)); 1028 } 1029 1030 DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD: " << *LI); 1031 1032 DenseMap<BasicBlock*, Value*> BlockReplValues; 1033 BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 1034 // Perform PHI construction. 1035 Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 1036 LI->replaceAllUsesWith(v); 1037 if (isa<PointerType>(v->getType())) 1038 MD->invalidateCachedPointerInfo(v); 1039 toErase.push_back(LI); 1040 NumGVNLoad++; 1041 return true; 1042 } 1043 1044 if (!EnablePRE || !EnableLoadPRE) 1045 return false; 1046 1047 // Okay, we have *some* definitions of the value. This means that the value 1048 // is available in some of our (transitive) predecessors. Lets think about 1049 // doing PRE of this load. This will involve inserting a new load into the 1050 // predecessor when it's not available. We could do this in general, but 1051 // prefer to not increase code size. As such, we only do this when we know 1052 // that we only have to insert *one* load (which means we're basically moving 1053 // the load, not inserting a new one). 1054 1055 // Everything we do here is based on local predecessors of LI's block. If it 1056 // only has one predecessor, bail now. 1057 BasicBlock *LoadBB = LI->getParent(); 1058 if (LoadBB->getSinglePredecessor()) 1059 return false; 1060 1061 // If we have a repl set with LI itself in it, this means we have a loop where 1062 // at least one of the values is LI. Since this means that we won't be able 1063 // to eliminate LI even if we insert uses in the other predecessors, we will 1064 // end up increasing code size. Reject this by scanning for LI. 1065 for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 1066 if (ValuesPerBlock[i].second == LI) 1067 return false; 1068 1069 // Okay, we have some hope :). Check to see if the loaded value is fully 1070 // available in all but one predecessor. 1071 // FIXME: If we could restructure the CFG, we could make a common pred with 1072 // all the preds that don't have an available LI and insert a new load into 1073 // that one block. 1074 BasicBlock *UnavailablePred = 0; 1075 1076 DenseMap<BasicBlock*, char> FullyAvailableBlocks; 1077 for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 1078 FullyAvailableBlocks[ValuesPerBlock[i].first] = true; 1079 for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i) 1080 FullyAvailableBlocks[UnavailableBlocks[i]] = false; 1081 1082 for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); 1083 PI != E; ++PI) { 1084 if (IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks)) 1085 continue; 1086 1087 // If this load is not available in multiple predecessors, reject it. 1088 if (UnavailablePred && UnavailablePred != *PI) 1089 return false; 1090 UnavailablePred = *PI; 1091 } 1092 1093 assert(UnavailablePred != 0 && 1094 "Fully available value should be eliminated above!"); 1095 1096 // If the loaded pointer is PHI node defined in this block, do PHI translation 1097 // to get its value in the predecessor. 1098 Value *LoadPtr = LI->getOperand(0)->DoPHITranslation(LoadBB, UnavailablePred); 1099 1100 // Make sure the value is live in the predecessor. If it was defined by a 1101 // non-PHI instruction in this block, we don't know how to recompute it above. 1102 if (Instruction *LPInst = dyn_cast<Instruction>(LoadPtr)) 1103 if (!DT->dominates(LPInst->getParent(), UnavailablePred)) { 1104 DEBUG(cerr << "COULDN'T PRE LOAD BECAUSE PTR IS UNAVAILABLE IN PRED: " 1105 << *LPInst << *LI << "\n"); 1106 return false; 1107 } 1108 1109 // We don't currently handle critical edges :( 1110 if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) { 1111 DEBUG(cerr << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '" 1112 << UnavailablePred->getName() << "': " << *LI); 1113 return false; 1114 } 1115 1116 // Okay, we can eliminate this load by inserting a reload in the predecessor 1117 // and using PHI construction to get the value in the other predecessors, do 1118 // it. 1119 DEBUG(cerr << "GVN REMOVING PRE LOAD: " << *LI); 1120 1121 Value *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false, 1122 LI->getAlignment(), 1123 UnavailablePred->getTerminator()); 1124 1125 DenseMap<BasicBlock*, Value*> BlockReplValues; 1126 BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 1127 BlockReplValues[UnavailablePred] = NewLoad; 1128 1129 // Perform PHI construction. 1130 Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 1131 LI->replaceAllUsesWith(v); 1132 v->takeName(LI); 1133 if (isa<PointerType>(v->getType())) 1134 MD->invalidateCachedPointerInfo(v); 1135 toErase.push_back(LI); 1136 NumPRELoad++; 1137 return true; 1138} 1139 1140/// processLoad - Attempt to eliminate a load, first by eliminating it 1141/// locally, and then attempting non-local elimination if that fails. 1142bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) { 1143 if (L->isVolatile()) 1144 return false; 1145 1146 Value* pointer = L->getPointerOperand(); 1147 1148 // ... to a pointer that has been loaded from before... 1149 MemDepResult dep = MD->getDependency(L); 1150 1151 // If the value isn't available, don't do anything! 1152 if (dep.isClobber()) 1153 return false; 1154 1155 // If it is defined in another block, try harder. 1156 if (dep.isNonLocal()) 1157 return processNonLocalLoad(L, toErase); 1158 1159 Instruction *DepInst = dep.getInst(); 1160 if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) { 1161 // Only forward substitute stores to loads of the same type. 1162 // FIXME: Could do better! 1163 if (DepSI->getPointerOperand()->getType() != pointer->getType()) 1164 return false; 1165 1166 // Remove it! 1167 L->replaceAllUsesWith(DepSI->getOperand(0)); 1168 if (isa<PointerType>(DepSI->getOperand(0)->getType())) 1169 MD->invalidateCachedPointerInfo(DepSI->getOperand(0)); 1170 toErase.push_back(L); 1171 NumGVNLoad++; 1172 return true; 1173 } 1174 1175 if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) { 1176 // Only forward substitute stores to loads of the same type. 1177 // FIXME: Could do better! load i32 -> load i8 -> truncate on little endian. 1178 if (DepLI->getType() != L->getType()) 1179 return false; 1180 1181 // Remove it! 1182 L->replaceAllUsesWith(DepLI); 1183 if (isa<PointerType>(DepLI->getType())) 1184 MD->invalidateCachedPointerInfo(DepLI); 1185 toErase.push_back(L); 1186 NumGVNLoad++; 1187 return true; 1188 } 1189 1190 // If this load really doesn't depend on anything, then we must be loading an 1191 // undef value. This can happen when loading for a fresh allocation with no 1192 // intervening stores, for example. 1193 if (isa<AllocationInst>(DepInst)) { 1194 L->replaceAllUsesWith(UndefValue::get(L->getType())); 1195 toErase.push_back(L); 1196 NumGVNLoad++; 1197 return true; 1198 } 1199 1200 return false; 1201} 1202 1203Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { 1204 DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB); 1205 if (I == localAvail.end()) 1206 return 0; 1207 1208 ValueNumberScope* locals = I->second; 1209 1210 while (locals) { 1211 DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num); 1212 if (I != locals->table.end()) 1213 return I->second; 1214 else 1215 locals = locals->parent; 1216 } 1217 1218 return 0; 1219} 1220 1221/// processInstruction - When calculating availability, handle an instruction 1222/// by inserting it into the appropriate sets 1223bool GVN::processInstruction(Instruction *I, 1224 SmallVectorImpl<Instruction*> &toErase) { 1225 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1226 bool changed = processLoad(L, toErase); 1227 1228 if (!changed) { 1229 unsigned num = VN.lookup_or_add(L); 1230 localAvail[I->getParent()]->table.insert(std::make_pair(num, L)); 1231 } 1232 1233 return changed; 1234 } 1235 1236 uint32_t nextNum = VN.getNextUnusedValueNumber(); 1237 unsigned num = VN.lookup_or_add(I); 1238 1239 // Allocations are always uniquely numbered, so we can save time and memory 1240 // by fast failing them. 1241 if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) { 1242 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1243 return false; 1244 } 1245 1246 // Collapse PHI nodes 1247 if (PHINode* p = dyn_cast<PHINode>(I)) { 1248 Value* constVal = CollapsePhi(p); 1249 1250 if (constVal) { 1251 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1252 PI != PE; ++PI) 1253 PI->second.erase(p); 1254 1255 p->replaceAllUsesWith(constVal); 1256 if (isa<PointerType>(constVal->getType())) 1257 MD->invalidateCachedPointerInfo(constVal); 1258 toErase.push_back(p); 1259 } else { 1260 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1261 } 1262 1263 // If the number we were assigned was a brand new VN, then we don't 1264 // need to do a lookup to see if the number already exists 1265 // somewhere in the domtree: it can't! 1266 } else if (num == nextNum) { 1267 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1268 1269 // Perform value-number based elimination 1270 } else if (Value* repl = lookupNumber(I->getParent(), num)) { 1271 // Remove it! 1272 VN.erase(I); 1273 I->replaceAllUsesWith(repl); 1274 if (isa<PointerType>(repl->getType())) 1275 MD->invalidateCachedPointerInfo(repl); 1276 toErase.push_back(I); 1277 return true; 1278 } else { 1279 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1280 } 1281 1282 return false; 1283} 1284 1285// GVN::runOnFunction - This is the main transformation entry point for a 1286// function. 1287// 1288bool GVN::runOnFunction(Function& F) { 1289 MD = &getAnalysis<MemoryDependenceAnalysis>(); 1290 DT = &getAnalysis<DominatorTree>(); 1291 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1292 VN.setMemDep(MD); 1293 VN.setDomTree(DT); 1294 1295 bool changed = false; 1296 bool shouldContinue = true; 1297 1298 // Merge unconditional branches, allowing PRE to catch more 1299 // optimization opportunities. 1300 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { 1301 BasicBlock* BB = FI; 1302 ++FI; 1303 bool removedBlock = MergeBlockIntoPredecessor(BB, this); 1304 if (removedBlock) NumGVNBlocks++; 1305 1306 changed |= removedBlock; 1307 } 1308 1309 unsigned Iteration = 0; 1310 1311 while (shouldContinue) { 1312 DEBUG(cerr << "GVN iteration: " << Iteration << "\n"); 1313 shouldContinue = iterateOnFunction(F); 1314 changed |= shouldContinue; 1315 ++Iteration; 1316 } 1317 1318 if (EnablePRE) { 1319 bool PREChanged = true; 1320 while (PREChanged) { 1321 PREChanged = performPRE(F); 1322 changed |= PREChanged; 1323 } 1324 } 1325 // FIXME: Should perform GVN again after PRE does something. PRE can move 1326 // computations into blocks where they become fully redundant. Note that 1327 // we can't do this until PRE's critical edge splitting updates memdep. 1328 // Actually, when this happens, we should just fully integrate PRE into GVN. 1329 1330 cleanupGlobalSets(); 1331 1332 return changed; 1333} 1334 1335 1336bool GVN::processBlock(DomTreeNode* DTN) { 1337 BasicBlock* BB = DTN->getBlock(); 1338 // FIXME: Kill off toErase by doing erasing eagerly in a helper function (and 1339 // incrementing BI before processing an instruction). 1340 SmallVector<Instruction*, 8> toErase; 1341 bool changed_function = false; 1342 1343 if (DTN->getIDom()) 1344 localAvail[BB] = 1345 new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]); 1346 else 1347 localAvail[BB] = new ValueNumberScope(0); 1348 1349 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1350 BI != BE;) { 1351 changed_function |= processInstruction(BI, toErase); 1352 if (toErase.empty()) { 1353 ++BI; 1354 continue; 1355 } 1356 1357 // If we need some instructions deleted, do it now. 1358 NumGVNInstr += toErase.size(); 1359 1360 // Avoid iterator invalidation. 1361 bool AtStart = BI == BB->begin(); 1362 if (!AtStart) 1363 --BI; 1364 1365 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1366 E = toErase.end(); I != E; ++I) { 1367 DEBUG(cerr << "GVN removed: " << **I); 1368 MD->removeInstruction(*I); 1369 (*I)->eraseFromParent(); 1370 } 1371 toErase.clear(); 1372 1373 if (AtStart) 1374 BI = BB->begin(); 1375 else 1376 ++BI; 1377 } 1378 1379 return changed_function; 1380} 1381 1382/// performPRE - Perform a purely local form of PRE that looks for diamond 1383/// control flow patterns and attempts to perform simple PRE at the join point. 1384bool GVN::performPRE(Function& F) { 1385 bool Changed = false; 1386 SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit; 1387 DenseMap<BasicBlock*, Value*> predMap; 1388 for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()), 1389 DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { 1390 BasicBlock* CurrentBlock = *DI; 1391 1392 // Nothing to PRE in the entry block. 1393 if (CurrentBlock == &F.getEntryBlock()) continue; 1394 1395 for (BasicBlock::iterator BI = CurrentBlock->begin(), 1396 BE = CurrentBlock->end(); BI != BE; ) { 1397 Instruction *CurInst = BI++; 1398 1399 if (isa<AllocationInst>(CurInst) || isa<TerminatorInst>(CurInst) || 1400 isa<PHINode>(CurInst) || CurInst->mayReadFromMemory() || 1401 CurInst->mayWriteToMemory()) 1402 continue; 1403 1404 uint32_t valno = VN.lookup(CurInst); 1405 1406 // Look for the predecessors for PRE opportunities. We're 1407 // only trying to solve the basic diamond case, where 1408 // a value is computed in the successor and one predecessor, 1409 // but not the other. We also explicitly disallow cases 1410 // where the successor is its own predecessor, because they're 1411 // more complicated to get right. 1412 unsigned numWith = 0; 1413 unsigned numWithout = 0; 1414 BasicBlock* PREPred = 0; 1415 predMap.clear(); 1416 1417 for (pred_iterator PI = pred_begin(CurrentBlock), 1418 PE = pred_end(CurrentBlock); PI != PE; ++PI) { 1419 // We're not interested in PRE where the block is its 1420 // own predecessor, on in blocks with predecessors 1421 // that are not reachable. 1422 if (*PI == CurrentBlock) { 1423 numWithout = 2; 1424 break; 1425 } else if (!localAvail.count(*PI)) { 1426 numWithout = 2; 1427 break; 1428 } 1429 1430 DenseMap<uint32_t, Value*>::iterator predV = 1431 localAvail[*PI]->table.find(valno); 1432 if (predV == localAvail[*PI]->table.end()) { 1433 PREPred = *PI; 1434 numWithout++; 1435 } else if (predV->second == CurInst) { 1436 numWithout = 2; 1437 } else { 1438 predMap[*PI] = predV->second; 1439 numWith++; 1440 } 1441 } 1442 1443 // Don't do PRE when it might increase code size, i.e. when 1444 // we would need to insert instructions in more than one pred. 1445 if (numWithout != 1 || numWith == 0) 1446 continue; 1447 1448 // We can't do PRE safely on a critical edge, so instead we schedule 1449 // the edge to be split and perform the PRE the next time we iterate 1450 // on the function. 1451 unsigned succNum = 0; 1452 for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors(); 1453 i != e; ++i) 1454 if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) { 1455 succNum = i; 1456 break; 1457 } 1458 1459 if (isCriticalEdge(PREPred->getTerminator(), succNum)) { 1460 toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum)); 1461 continue; 1462 } 1463 1464 // Instantiate the expression the in predecessor that lacked it. 1465 // Because we are going top-down through the block, all value numbers 1466 // will be available in the predecessor by the time we need them. Any 1467 // that weren't original present will have been instantiated earlier 1468 // in this loop. 1469 Instruction* PREInstr = CurInst->clone(); 1470 bool success = true; 1471 for (unsigned i = 0, e = CurInst->getNumOperands(); i != e; ++i) { 1472 Value *Op = PREInstr->getOperand(i); 1473 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op)) 1474 continue; 1475 1476 if (Value *V = lookupNumber(PREPred, VN.lookup(Op))) { 1477 PREInstr->setOperand(i, V); 1478 } else { 1479 success = false; 1480 break; 1481 } 1482 } 1483 1484 // Fail out if we encounter an operand that is not available in 1485 // the PRE predecessor. This is typically because of loads which 1486 // are not value numbered precisely. 1487 if (!success) { 1488 delete PREInstr; 1489 continue; 1490 } 1491 1492 PREInstr->insertBefore(PREPred->getTerminator()); 1493 PREInstr->setName(CurInst->getName() + ".pre"); 1494 predMap[PREPred] = PREInstr; 1495 VN.add(PREInstr, valno); 1496 NumGVNPRE++; 1497 1498 // Update the availability map to include the new instruction. 1499 localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr)); 1500 1501 // Create a PHI to make the value available in this block. 1502 PHINode* Phi = PHINode::Create(CurInst->getType(), 1503 CurInst->getName() + ".pre-phi", 1504 CurrentBlock->begin()); 1505 for (pred_iterator PI = pred_begin(CurrentBlock), 1506 PE = pred_end(CurrentBlock); PI != PE; ++PI) 1507 Phi->addIncoming(predMap[*PI], *PI); 1508 1509 VN.add(Phi, valno); 1510 localAvail[CurrentBlock]->table[valno] = Phi; 1511 1512 CurInst->replaceAllUsesWith(Phi); 1513 if (isa<PointerType>(Phi->getType())) 1514 MD->invalidateCachedPointerInfo(Phi); 1515 VN.erase(CurInst); 1516 1517 DEBUG(cerr << "GVN PRE removed: " << *CurInst); 1518 MD->removeInstruction(CurInst); 1519 CurInst->eraseFromParent(); 1520 Changed = true; 1521 } 1522 } 1523 1524 for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator 1525 I = toSplit.begin(), E = toSplit.end(); I != E; ++I) 1526 SplitCriticalEdge(I->first, I->second, this); 1527 1528 return Changed || toSplit.size(); 1529} 1530 1531// iterateOnFunction - Executes one iteration of GVN 1532bool GVN::iterateOnFunction(Function &F) { 1533 cleanupGlobalSets(); 1534 1535 // Top-down walk of the dominator tree 1536 bool changed = false; 1537 for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()), 1538 DE = df_end(DT->getRootNode()); DI != DE; ++DI) 1539 changed |= processBlock(*DI); 1540 1541 return changed; 1542} 1543 1544void GVN::cleanupGlobalSets() { 1545 VN.clear(); 1546 phiMap.clear(); 1547 1548 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator 1549 I = localAvail.begin(), E = localAvail.end(); I != E; ++I) 1550 delete I->second; 1551 localAvail.clear(); 1552} 1553