GVN.cpp revision 4f9ba7c40c41cae3d9730c5416a2750dea4f0ff4
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===- GVN.cpp - Eliminate redundant values and loads ------------===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file was developed by the Owen Anderson and is distributed under 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the University of Illinois Open Source License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This pass performs global value numbering to eliminate fully redundant 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// instructions. It also performs simple dead load elimination. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_TYPE "gvn" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Transforms/Scalar.h" 18ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/BasicBlock.h" 19ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/Constants.h" 20ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/DerivedTypes.h" 21ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/Function.h" 22ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/Instructions.h" 23ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/Value.h" 24ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/Analysis/Dominators.h" 25ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/ADT/BitVector.h" 26ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/ADT/DenseMap.h" 27ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/ADT/DepthFirstIterator.h" 28ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "llvm/ADT/SmallPtrSet.h" 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/SmallVector.h" 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/Statistic.h" 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Analysis/MemoryDependenceAnalysis.h" 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/CFG.h" 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/Compiler.h" 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace llvm; 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ValueTable Class 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// This class holds the mapping between values and value numbers. It is used 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// as an efficient mechanism to determine the expression-wise equivalence of 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// two values. 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct VISIBILITY_HIDDEN Expression { 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY, 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TOMBSTONE }; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpressionOpcode opcode; 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Type* type; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t firstVN; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t secondVN; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t thirdVN; 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SmallVector<uint32_t, 4> varargs; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression() { } 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression(ExpressionOpcode o) : opcode(o) { } 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator==(const Expression &other) const { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (opcode != other.opcode) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (opcode == EMPTY || opcode == TOMBSTONE) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (type != other.type) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (firstVN != other.firstVN) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (secondVN != other.secondVN) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (thirdVN != other.thirdVN) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (varargs.size() != other.varargs.size()) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < varargs.size(); ++i) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (varargs[i] != other.varargs[i]) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator!=(const Expression &other) const { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (opcode != other.opcode) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (opcode == EMPTY || opcode == TOMBSTONE) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (type != other.type) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 99 else if (firstVN != other.firstVN) 100 return true; 101 else if (secondVN != other.secondVN) 102 return true; 103 else if (thirdVN != other.thirdVN) 104 return true; 105 else { 106 if (varargs.size() != other.varargs.size()) 107 return true; 108 109 for (size_t i = 0; i < varargs.size(); ++i) 110 if (varargs[i] != other.varargs[i]) 111 return true; 112 113 return false; 114 } 115 } 116 }; 117 118 class VISIBILITY_HIDDEN ValueTable { 119 private: 120 DenseMap<Value*, uint32_t> valueNumbering; 121 DenseMap<Expression, uint32_t> expressionNumbering; 122 123 uint32_t nextValueNumber; 124 125 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 126 Expression::ExpressionOpcode getOpcode(CmpInst* C); 127 Expression::ExpressionOpcode getOpcode(CastInst* C); 128 Expression create_expression(BinaryOperator* BO); 129 Expression create_expression(CmpInst* C); 130 Expression create_expression(ShuffleVectorInst* V); 131 Expression create_expression(ExtractElementInst* C); 132 Expression create_expression(InsertElementInst* V); 133 Expression create_expression(SelectInst* V); 134 Expression create_expression(CastInst* C); 135 Expression create_expression(GetElementPtrInst* G); 136 public: 137 ValueTable() { nextValueNumber = 1; } 138 uint32_t lookup_or_add(Value* V); 139 uint32_t lookup(Value* V) const; 140 void add(Value* V, uint32_t num); 141 void clear(); 142 void erase(Value* v); 143 unsigned size(); 144 }; 145} 146 147namespace llvm { 148template <> struct DenseMapKeyInfo<Expression> { 149 static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); } 150 static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); } 151 152 static unsigned getHashValue(const Expression e) { 153 unsigned hash = e.opcode; 154 155 hash = e.firstVN + hash * 37; 156 hash = e.secondVN + hash * 37; 157 hash = e.thirdVN + hash * 37; 158 159 hash = (unsigned)((uintptr_t)e.type >> 4) ^ 160 (unsigned)((uintptr_t)e.type >> 9) + 161 hash * 37; 162 163 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end(); 164 I != E; ++I) 165 hash = *I + hash * 37; 166 167 return hash; 168 } 169 static bool isPod() { return true; } 170}; 171} 172 173//===----------------------------------------------------------------------===// 174// ValueTable Internal Functions 175//===----------------------------------------------------------------------===// 176Expression::ExpressionOpcode 177 ValueTable::getOpcode(BinaryOperator* BO) { 178 switch(BO->getOpcode()) { 179 case Instruction::Add: 180 return Expression::ADD; 181 case Instruction::Sub: 182 return Expression::SUB; 183 case Instruction::Mul: 184 return Expression::MUL; 185 case Instruction::UDiv: 186 return Expression::UDIV; 187 case Instruction::SDiv: 188 return Expression::SDIV; 189 case Instruction::FDiv: 190 return Expression::FDIV; 191 case Instruction::URem: 192 return Expression::UREM; 193 case Instruction::SRem: 194 return Expression::SREM; 195 case Instruction::FRem: 196 return Expression::FREM; 197 case Instruction::Shl: 198 return Expression::SHL; 199 case Instruction::LShr: 200 return Expression::LSHR; 201 case Instruction::AShr: 202 return Expression::ASHR; 203 case Instruction::And: 204 return Expression::AND; 205 case Instruction::Or: 206 return Expression::OR; 207 case Instruction::Xor: 208 return Expression::XOR; 209 210 // THIS SHOULD NEVER HAPPEN 211 default: 212 assert(0 && "Binary operator with unknown opcode?"); 213 return Expression::ADD; 214 } 215} 216 217Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 218 if (C->getOpcode() == Instruction::ICmp) { 219 switch (C->getPredicate()) { 220 case ICmpInst::ICMP_EQ: 221 return Expression::ICMPEQ; 222 case ICmpInst::ICMP_NE: 223 return Expression::ICMPNE; 224 case ICmpInst::ICMP_UGT: 225 return Expression::ICMPUGT; 226 case ICmpInst::ICMP_UGE: 227 return Expression::ICMPUGE; 228 case ICmpInst::ICMP_ULT: 229 return Expression::ICMPULT; 230 case ICmpInst::ICMP_ULE: 231 return Expression::ICMPULE; 232 case ICmpInst::ICMP_SGT: 233 return Expression::ICMPSGT; 234 case ICmpInst::ICMP_SGE: 235 return Expression::ICMPSGE; 236 case ICmpInst::ICMP_SLT: 237 return Expression::ICMPSLT; 238 case ICmpInst::ICMP_SLE: 239 return Expression::ICMPSLE; 240 241 // THIS SHOULD NEVER HAPPEN 242 default: 243 assert(0 && "Comparison with unknown predicate?"); 244 return Expression::ICMPEQ; 245 } 246 } else { 247 switch (C->getPredicate()) { 248 case FCmpInst::FCMP_OEQ: 249 return Expression::FCMPOEQ; 250 case FCmpInst::FCMP_OGT: 251 return Expression::FCMPOGT; 252 case FCmpInst::FCMP_OGE: 253 return Expression::FCMPOGE; 254 case FCmpInst::FCMP_OLT: 255 return Expression::FCMPOLT; 256 case FCmpInst::FCMP_OLE: 257 return Expression::FCMPOLE; 258 case FCmpInst::FCMP_ONE: 259 return Expression::FCMPONE; 260 case FCmpInst::FCMP_ORD: 261 return Expression::FCMPORD; 262 case FCmpInst::FCMP_UNO: 263 return Expression::FCMPUNO; 264 case FCmpInst::FCMP_UEQ: 265 return Expression::FCMPUEQ; 266 case FCmpInst::FCMP_UGT: 267 return Expression::FCMPUGT; 268 case FCmpInst::FCMP_UGE: 269 return Expression::FCMPUGE; 270 case FCmpInst::FCMP_ULT: 271 return Expression::FCMPULT; 272 case FCmpInst::FCMP_ULE: 273 return Expression::FCMPULE; 274 case FCmpInst::FCMP_UNE: 275 return Expression::FCMPUNE; 276 277 // THIS SHOULD NEVER HAPPEN 278 default: 279 assert(0 && "Comparison with unknown predicate?"); 280 return Expression::FCMPOEQ; 281 } 282 } 283} 284 285Expression::ExpressionOpcode 286 ValueTable::getOpcode(CastInst* C) { 287 switch(C->getOpcode()) { 288 case Instruction::Trunc: 289 return Expression::TRUNC; 290 case Instruction::ZExt: 291 return Expression::ZEXT; 292 case Instruction::SExt: 293 return Expression::SEXT; 294 case Instruction::FPToUI: 295 return Expression::FPTOUI; 296 case Instruction::FPToSI: 297 return Expression::FPTOSI; 298 case Instruction::UIToFP: 299 return Expression::UITOFP; 300 case Instruction::SIToFP: 301 return Expression::SITOFP; 302 case Instruction::FPTrunc: 303 return Expression::FPTRUNC; 304 case Instruction::FPExt: 305 return Expression::FPEXT; 306 case Instruction::PtrToInt: 307 return Expression::PTRTOINT; 308 case Instruction::IntToPtr: 309 return Expression::INTTOPTR; 310 case Instruction::BitCast: 311 return Expression::BITCAST; 312 313 // THIS SHOULD NEVER HAPPEN 314 default: 315 assert(0 && "Cast operator with unknown opcode?"); 316 return Expression::BITCAST; 317 } 318} 319 320Expression ValueTable::create_expression(BinaryOperator* BO) { 321 Expression e; 322 323 e.firstVN = lookup_or_add(BO->getOperand(0)); 324 e.secondVN = lookup_or_add(BO->getOperand(1)); 325 e.thirdVN = 0; 326 e.type = BO->getType(); 327 e.opcode = getOpcode(BO); 328 329 return e; 330} 331 332Expression ValueTable::create_expression(CmpInst* C) { 333 Expression e; 334 335 e.firstVN = lookup_or_add(C->getOperand(0)); 336 e.secondVN = lookup_or_add(C->getOperand(1)); 337 e.thirdVN = 0; 338 e.type = C->getType(); 339 e.opcode = getOpcode(C); 340 341 return e; 342} 343 344Expression ValueTable::create_expression(CastInst* C) { 345 Expression e; 346 347 e.firstVN = lookup_or_add(C->getOperand(0)); 348 e.secondVN = 0; 349 e.thirdVN = 0; 350 e.type = C->getType(); 351 e.opcode = getOpcode(C); 352 353 return e; 354} 355 356Expression ValueTable::create_expression(ShuffleVectorInst* S) { 357 Expression e; 358 359 e.firstVN = lookup_or_add(S->getOperand(0)); 360 e.secondVN = lookup_or_add(S->getOperand(1)); 361 e.thirdVN = lookup_or_add(S->getOperand(2)); 362 e.type = S->getType(); 363 e.opcode = Expression::SHUFFLE; 364 365 return e; 366} 367 368Expression ValueTable::create_expression(ExtractElementInst* E) { 369 Expression e; 370 371 e.firstVN = lookup_or_add(E->getOperand(0)); 372 e.secondVN = lookup_or_add(E->getOperand(1)); 373 e.thirdVN = 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.type = I->getType(); 387 e.opcode = Expression::INSERT; 388 389 return e; 390} 391 392Expression ValueTable::create_expression(SelectInst* I) { 393 Expression e; 394 395 e.firstVN = lookup_or_add(I->getCondition()); 396 e.secondVN = lookup_or_add(I->getTrueValue()); 397 e.thirdVN = lookup_or_add(I->getFalseValue()); 398 e.type = I->getType(); 399 e.opcode = Expression::SELECT; 400 401 return e; 402} 403 404Expression ValueTable::create_expression(GetElementPtrInst* G) { 405 Expression e; 406 407 e.firstVN = lookup_or_add(G->getPointerOperand()); 408 e.secondVN = 0; 409 e.thirdVN = 0; 410 e.type = G->getType(); 411 e.opcode = Expression::GEP; 412 413 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 414 I != E; ++I) 415 e.varargs.push_back(lookup_or_add(*I)); 416 417 return e; 418} 419 420//===----------------------------------------------------------------------===// 421// ValueTable External Functions 422//===----------------------------------------------------------------------===// 423 424/// lookup_or_add - Returns the value number for the specified value, assigning 425/// it a new number if it did not have one before. 426uint32_t ValueTable::lookup_or_add(Value* V) { 427 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 428 if (VI != valueNumbering.end()) 429 return VI->second; 430 431 432 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 433 Expression e = create_expression(BO); 434 435 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 436 if (EI != expressionNumbering.end()) { 437 valueNumbering.insert(std::make_pair(V, EI->second)); 438 return EI->second; 439 } else { 440 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 441 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 442 443 return nextValueNumber++; 444 } 445 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 446 Expression e = create_expression(C); 447 448 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 449 if (EI != expressionNumbering.end()) { 450 valueNumbering.insert(std::make_pair(V, EI->second)); 451 return EI->second; 452 } else { 453 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 454 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 455 456 return nextValueNumber++; 457 } 458 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 459 Expression e = create_expression(U); 460 461 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 462 if (EI != expressionNumbering.end()) { 463 valueNumbering.insert(std::make_pair(V, EI->second)); 464 return EI->second; 465 } else { 466 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 467 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 468 469 return nextValueNumber++; 470 } 471 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 472 Expression e = create_expression(U); 473 474 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 475 if (EI != expressionNumbering.end()) { 476 valueNumbering.insert(std::make_pair(V, EI->second)); 477 return EI->second; 478 } else { 479 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 480 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 481 482 return nextValueNumber++; 483 } 484 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 485 Expression e = create_expression(U); 486 487 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 488 if (EI != expressionNumbering.end()) { 489 valueNumbering.insert(std::make_pair(V, EI->second)); 490 return EI->second; 491 } else { 492 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 493 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 494 495 return nextValueNumber++; 496 } 497 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 498 Expression e = create_expression(U); 499 500 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 501 if (EI != expressionNumbering.end()) { 502 valueNumbering.insert(std::make_pair(V, EI->second)); 503 return EI->second; 504 } else { 505 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 506 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 507 508 return nextValueNumber++; 509 } 510 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 511 Expression e = create_expression(U); 512 513 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 514 if (EI != expressionNumbering.end()) { 515 valueNumbering.insert(std::make_pair(V, EI->second)); 516 return EI->second; 517 } else { 518 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 519 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 520 521 return nextValueNumber++; 522 } 523 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 524 Expression e = create_expression(U); 525 526 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 527 if (EI != expressionNumbering.end()) { 528 valueNumbering.insert(std::make_pair(V, EI->second)); 529 return EI->second; 530 } else { 531 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 532 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 533 534 return nextValueNumber++; 535 } 536 } else { 537 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 538 return nextValueNumber++; 539 } 540} 541 542/// lookup - Returns the value number of the specified value. Fails if 543/// the value has not yet been numbered. 544uint32_t ValueTable::lookup(Value* V) const { 545 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 546 if (VI != valueNumbering.end()) 547 return VI->second; 548 else 549 assert(0 && "Value not numbered?"); 550 551 return 0; 552} 553 554/// clear - Remove all entries from the ValueTable 555void ValueTable::clear() { 556 valueNumbering.clear(); 557 expressionNumbering.clear(); 558 nextValueNumber = 1; 559} 560 561//===----------------------------------------------------------------------===// 562// ValueNumberedSet Class 563//===----------------------------------------------------------------------===// 564namespace { 565class ValueNumberedSet { 566 private: 567 SmallPtrSet<Value*, 8> contents; 568 BitVector numbers; 569 public: 570 ValueNumberedSet() { numbers.resize(1); } 571 ValueNumberedSet(const ValueNumberedSet& other) { 572 numbers = other.numbers; 573 contents = other.contents; 574 } 575 576 typedef SmallPtrSet<Value*, 8>::iterator iterator; 577 578 iterator begin() { return contents.begin(); } 579 iterator end() { return contents.end(); } 580 581 bool insert(Value* v) { return contents.insert(v); } 582 void insert(iterator I, iterator E) { contents.insert(I, E); } 583 void erase(Value* v) { contents.erase(v); } 584 unsigned count(Value* v) { return contents.count(v); } 585 size_t size() { return contents.size(); } 586 587 void set(unsigned i) { 588 if (i >= numbers.size()) 589 numbers.resize(i+1); 590 591 numbers.set(i); 592 } 593 594 void operator=(const ValueNumberedSet& other) { 595 contents = other.contents; 596 numbers = other.numbers; 597 } 598 599 void reset(unsigned i) { 600 if (i < numbers.size()) 601 numbers.reset(i); 602 } 603 604 bool test(unsigned i) { 605 if (i >= numbers.size()) 606 return false; 607 608 return numbers.test(i); 609 } 610 611 void clear() { 612 contents.clear(); 613 numbers.clear(); 614 } 615}; 616} 617 618//===----------------------------------------------------------------------===// 619// GVN Pass 620//===----------------------------------------------------------------------===// 621 622namespace { 623 624 class VISIBILITY_HIDDEN GVN : public FunctionPass { 625 bool runOnFunction(Function &F); 626 public: 627 static char ID; // Pass identification, replacement for typeid 628 GVN() : FunctionPass((intptr_t)&ID) { } 629 630 private: 631 ValueTable VN; 632 633 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 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.addPreserved<MemoryDependenceAnalysis>(); 641 } 642 643 // Helper fuctions 644 // FIXME: eliminate or document these better 645 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 646 void val_insert(ValueNumberedSet& s, Value* v); 647 bool processLoad(LoadInst* L, 648 DenseMap<Value*, LoadInst*>& lastLoad, 649 SmallVector<Instruction*, 4>& toErase); 650 bool processInstruction(Instruction* I, 651 ValueNumberedSet& currAvail, 652 DenseMap<Value*, LoadInst*>& lastSeenLoad, 653 SmallVector<Instruction*, 4>& toErase); 654 bool processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase); 655 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 656 DenseMap<BasicBlock*, Value*> &Phis); 657 void dump(DenseMap<BasicBlock*, Value*>& d); 658 }; 659 660 char GVN::ID = 0; 661 662} 663 664// createGVNPass - The public interface to this file... 665FunctionPass *llvm::createGVNPass() { return new GVN(); } 666 667static RegisterPass<GVN> X("gvn", 668 "Global Value Numbering"); 669 670STATISTIC(NumGVNInstr, "Number of instructions deleted"); 671STATISTIC(NumGVNLoad, "Number of loads deleted"); 672 673/// find_leader - Given a set and a value number, return the first 674/// element of the set with that value number, or 0 if no such element 675/// is present 676Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 677 if (!vals.test(v)) 678 return 0; 679 680 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 681 I != E; ++I) 682 if (v == VN.lookup(*I)) 683 return *I; 684 685 assert(0 && "No leader found, but present bit is set?"); 686 return 0; 687} 688 689/// val_insert - Insert a value into a set only if there is not a value 690/// with the same value number already in the set 691void GVN::val_insert(ValueNumberedSet& s, Value* v) { 692 uint32_t num = VN.lookup(v); 693 if (!s.test(num)) 694 s.insert(v); 695} 696 697void GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 698 printf("{\n"); 699 for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 700 E = d.end(); I != E; ++I) { 701 if (I->second == MemoryDependenceAnalysis::None) 702 printf("None\n"); 703 else 704 I->second->dump(); 705 } 706 printf("}\n"); 707} 708 709 710/// GetValueForBlock - Get the value to use within the specified basic block. 711/// available values are in Phis. 712Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 713 DenseMap<BasicBlock*, Value*> &Phis) { 714 DominatorTree &DT = getAnalysis<DominatorTree>(); 715 716 // If we have already computed this value, return the previously computed val. 717 Value *&V = Phis[BB]; 718 if (V) return V; 719 720 DomTreeNode *IDom = DT.getNode(BB)->getIDom(); 721 722 if (IDom && Phis.count(IDom->getBlock())) { 723 return V = GetValueForBlock(IDom->getBlock(), orig, Phis); 724 } 725 726 if (std::distance(pred_begin(BB), pred_end(BB)) == 1) 727 return V = GetValueForBlock(IDom->getBlock(), orig, Phis); 728 729 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 730 // now, then get values to fill in the incoming values for the PHI. 731 PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", 732 BB->begin()); 733 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 734 V = PN; 735 736 // Fill in the incoming values for the block. 737 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 738 PN->addIncoming(GetValueForBlock(*PI, orig, Phis), *PI); 739 return PN; 740} 741 742bool GVN::processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase) { 743 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 744 745 DenseMap<BasicBlock*, Value*> deps; 746 bool ret = MD.getNonLocalDependency(L, deps); 747 if (!ret) 748 return false; 749 750 DenseMap<BasicBlock*, Value*> repl; 751 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 752 I != E; ++I) 753 if (I->second == MemoryDependenceAnalysis::None) { 754 return false; 755 } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 756 if (S->getPointerOperand() == L->getPointerOperand()) 757 repl.insert(std::make_pair(I->first, S->getOperand(0))); 758 else 759 return false; 760 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 761 if (LD->getPointerOperand() == L->getPointerOperand()) 762 repl.insert(std::make_pair(I->first, LD)); 763 else 764 return false; 765 } else { 766 return false; 767 } 768 769 SmallPtrSet<BasicBlock*, 4> visited; 770 Value* v = GetValueForBlock(L->getParent(), L, repl); 771 772 MD.removeInstruction(L); 773 L->replaceAllUsesWith(v); 774 toErase.push_back(L); 775 776 return true; 777} 778 779bool GVN::processLoad(LoadInst* L, 780 DenseMap<Value*, LoadInst*>& lastLoad, 781 SmallVector<Instruction*, 4>& toErase) { 782 if (L->isVolatile()) { 783 lastLoad[L->getPointerOperand()] = L; 784 return false; 785 } 786 787 Value* pointer = L->getPointerOperand(); 788 LoadInst*& last = lastLoad[pointer]; 789 790 // ... to a pointer that has been loaded from before... 791 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 792 Instruction* dep = MD.getDependency(L); 793 if (dep == MemoryDependenceAnalysis::NonLocal && 794 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) 795 processNonLocalLoad(L, toErase); 796 bool deletedLoad = false; 797 798 while (dep != MemoryDependenceAnalysis::None && 799 dep != MemoryDependenceAnalysis::NonLocal && 800 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 801 // ... that depends on a store ... 802 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 803 if (S->getPointerOperand() == pointer) { 804 // Remove it! 805 MD.removeInstruction(L); 806 807 L->replaceAllUsesWith(S->getOperand(0)); 808 toErase.push_back(L); 809 deletedLoad = true; 810 NumGVNLoad++; 811 } 812 813 // Whether we removed it or not, we can't 814 // go any further 815 break; 816 } else if (!last) { 817 // If we don't depend on a store, and we haven't 818 // been loaded before, bail. 819 break; 820 } else if (dep == last) { 821 // Remove it! 822 MD.removeInstruction(L); 823 824 L->replaceAllUsesWith(last); 825 toErase.push_back(L); 826 deletedLoad = true; 827 NumGVNLoad++; 828 829 break; 830 } else { 831 dep = MD.getDependency(L, dep); 832 } 833 } 834 835 if (!deletedLoad) 836 last = L; 837 838 return deletedLoad; 839} 840 841/// buildsets_availout - When calculating availability, handle an instruction 842/// by inserting it into the appropriate sets 843bool GVN::processInstruction(Instruction* I, 844 ValueNumberedSet& currAvail, 845 DenseMap<Value*, LoadInst*>& lastSeenLoad, 846 SmallVector<Instruction*, 4>& toErase) { 847 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 848 return processLoad(L, lastSeenLoad, toErase); 849 } 850 851 unsigned num = VN.lookup_or_add(I); 852 853 if (currAvail.test(num)) { 854 Value* repl = find_leader(currAvail, num); 855 856 I->replaceAllUsesWith(repl); 857 toErase.push_back(I); 858 return true; 859 } else if (!I->isTerminator()) { 860 currAvail.set(num); 861 currAvail.insert(I); 862 } 863 864 return false; 865} 866 867// GVN::runOnFunction - This is the main transformation entry point for a 868// function. 869// 870bool GVN::runOnFunction(Function &F) { 871 // Clean out global sets from any previous functions 872 VN.clear(); 873 availableOut.clear(); 874 875 bool changed_function = false; 876 877 DominatorTree &DT = getAnalysis<DominatorTree>(); 878 879 SmallVector<Instruction*, 4> toErase; 880 881 // Top-down walk of the dominator tree 882 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 883 E = df_end(DT.getRootNode()); DI != E; ++DI) { 884 885 // Get the set to update for this block 886 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 887 DenseMap<Value*, LoadInst*> lastSeenLoad; 888 889 BasicBlock* BB = DI->getBlock(); 890 891 // A block inherits AVAIL_OUT from its dominator 892 if (DI->getIDom() != 0) 893 currAvail = availableOut[DI->getIDom()->getBlock()]; 894 895 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 896 BI != BE; ++BI) { 897 changed_function |= processInstruction(BI, currAvail, lastSeenLoad, toErase); 898 899 NumGVNInstr += toErase.size(); 900 901 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 902 E = toErase.end(); I != E; ++I) 903 (*I)->eraseFromParent(); 904 905 toErase.clear(); 906 } 907 } 908 909 return changed_function; 910} 911