GVN.cpp revision 36057c7834e54d4326bcdc9d182036b2ffa2aa3d
12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===- GVN.cpp - Eliminate redundant values and loads ------------===// 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The LLVM Compiler Infrastructure 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This file was developed by the Owen Anderson and is distributed under 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// the University of Illinois Open Source License. See LICENSE.TXT for details. 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This pass performs global value numbering to eliminate fully redundant 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// instructions. It also performs simple dead load elimination. 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 131320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 14cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define DEBUG_TYPE "gvn" 16a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Transforms/Scalar.h" 181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/BasicBlock.h" 191320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/Constants.h" 201320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/DerivedTypes.h" 211320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/Function.h" 221320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/Instructions.h" 231320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/Value.h" 241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "llvm/Analysis/Dominators.h" 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/BitVector.h" 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/DenseMap.h" 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/DepthFirstIterator.h" 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/SmallPtrSet.h" 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/SmallVector.h" 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/Statistic.h" 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Analysis/MemoryDependenceAnalysis.h" 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Support/CFG.h" 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Support/Compiler.h" 34c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdochusing namespace llvm; 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// ValueTable Class 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// This class holds the mapping between values and value numbers. It is used 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// as an efficient mechanism to determine the expression-wise equivalence of 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// two values. 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace { 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) struct VISIBILITY_HIDDEN Expression { 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 49f2477e01787aa58f445919b809d89e252beef54fTorne (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, 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY, 551320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci TOMBSTONE }; 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExpressionOpcode opcode; 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const Type* type; 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint32_t firstVN; 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint32_t secondVN; 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint32_t thirdVN; 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SmallVector<uint32_t, 4> varargs; 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Expression() { } 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Expression(ExpressionOpcode o) : opcode(o) { } 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 671320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool operator==(const Expression &other) const { 681320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (opcode != other.opcode) 691320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return false; 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (opcode == EMPTY || opcode == TOMBSTONE) 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (type != other.type) 731320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return false; 74f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) else if (firstVN != other.firstVN) 75f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return false; 76f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) else if (secondVN != other.secondVN) 77f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return false; 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (thirdVN != other.thirdVN) 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (varargs.size() != other.varargs.size()) 82cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return false; 83cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 84cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) for (size_t i = 0; i < varargs.size(); ++i) 85cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) if (varargs[i] != other.varargs[i]) 86cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return false; 87cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 88cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return true; 89cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool operator!=(const Expression &other) const { 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (opcode != other.opcode) 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (opcode == EMPTY || opcode == TOMBSTONE) 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 97f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) else if (type != other.type) 98f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return true; 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else if (firstVN != other.firstVN) 10058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) return true; 10158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) else if (secondVN != other.secondVN) 102f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return true; 103f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) else if (thirdVN != other.thirdVN) 1041320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return true; 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (varargs.size() != other.varargs.size()) 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < varargs.size(); ++i) 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (varargs[i] != other.varargs[i]) 111f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return true; 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 113f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return false; 1141320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 115f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 116f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) }; 117f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) class VISIBILITY_HIDDEN ValueTable { 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DenseMap<Value*, uint32_t> valueNumbering; 121cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) DenseMap<Expression, uint32_t> expressionNumbering; 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint32_t nextValueNumber; 124a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 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() { 150 return Expression(Expression::EMPTY); 151 } 152 153 static inline Expression getTombstoneKey() { 154 return Expression(Expression::TOMBSTONE); 155 } 156 157 static unsigned getHashValue(const Expression e) { 158 unsigned hash = e.opcode; 159 160 hash = e.firstVN + hash * 37; 161 hash = e.secondVN + hash * 37; 162 hash = e.thirdVN + hash * 37; 163 164 hash = (unsigned)((uintptr_t)e.type >> 4) ^ 165 (unsigned)((uintptr_t)e.type >> 9) + 166 hash * 37; 167 168 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 169 E = e.varargs.end(); I != E; ++I) 170 hash = *I + hash * 37; 171 172 return hash; 173 } 174 static bool isPod() { return true; } 175}; 176} 177 178//===----------------------------------------------------------------------===// 179// ValueTable Internal Functions 180//===----------------------------------------------------------------------===// 181Expression::ExpressionOpcode 182 ValueTable::getOpcode(BinaryOperator* BO) { 183 switch(BO->getOpcode()) { 184 case Instruction::Add: 185 return Expression::ADD; 186 case Instruction::Sub: 187 return Expression::SUB; 188 case Instruction::Mul: 189 return Expression::MUL; 190 case Instruction::UDiv: 191 return Expression::UDIV; 192 case Instruction::SDiv: 193 return Expression::SDIV; 194 case Instruction::FDiv: 195 return Expression::FDIV; 196 case Instruction::URem: 197 return Expression::UREM; 198 case Instruction::SRem: 199 return Expression::SREM; 200 case Instruction::FRem: 201 return Expression::FREM; 202 case Instruction::Shl: 203 return Expression::SHL; 204 case Instruction::LShr: 205 return Expression::LSHR; 206 case Instruction::AShr: 207 return Expression::ASHR; 208 case Instruction::And: 209 return Expression::AND; 210 case Instruction::Or: 211 return Expression::OR; 212 case Instruction::Xor: 213 return Expression::XOR; 214 215 // THIS SHOULD NEVER HAPPEN 216 default: 217 assert(0 && "Binary operator with unknown opcode?"); 218 return Expression::ADD; 219 } 220} 221 222Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 223 if (C->getOpcode() == Instruction::ICmp) { 224 switch (C->getPredicate()) { 225 case ICmpInst::ICMP_EQ: 226 return Expression::ICMPEQ; 227 case ICmpInst::ICMP_NE: 228 return Expression::ICMPNE; 229 case ICmpInst::ICMP_UGT: 230 return Expression::ICMPUGT; 231 case ICmpInst::ICMP_UGE: 232 return Expression::ICMPUGE; 233 case ICmpInst::ICMP_ULT: 234 return Expression::ICMPULT; 235 case ICmpInst::ICMP_ULE: 236 return Expression::ICMPULE; 237 case ICmpInst::ICMP_SGT: 238 return Expression::ICMPSGT; 239 case ICmpInst::ICMP_SGE: 240 return Expression::ICMPSGE; 241 case ICmpInst::ICMP_SLT: 242 return Expression::ICMPSLT; 243 case ICmpInst::ICMP_SLE: 244 return Expression::ICMPSLE; 245 246 // THIS SHOULD NEVER HAPPEN 247 default: 248 assert(0 && "Comparison with unknown predicate?"); 249 return Expression::ICMPEQ; 250 } 251 } else { 252 switch (C->getPredicate()) { 253 case FCmpInst::FCMP_OEQ: 254 return Expression::FCMPOEQ; 255 case FCmpInst::FCMP_OGT: 256 return Expression::FCMPOGT; 257 case FCmpInst::FCMP_OGE: 258 return Expression::FCMPOGE; 259 case FCmpInst::FCMP_OLT: 260 return Expression::FCMPOLT; 261 case FCmpInst::FCMP_OLE: 262 return Expression::FCMPOLE; 263 case FCmpInst::FCMP_ONE: 264 return Expression::FCMPONE; 265 case FCmpInst::FCMP_ORD: 266 return Expression::FCMPORD; 267 case FCmpInst::FCMP_UNO: 268 return Expression::FCMPUNO; 269 case FCmpInst::FCMP_UEQ: 270 return Expression::FCMPUEQ; 271 case FCmpInst::FCMP_UGT: 272 return Expression::FCMPUGT; 273 case FCmpInst::FCMP_UGE: 274 return Expression::FCMPUGE; 275 case FCmpInst::FCMP_ULT: 276 return Expression::FCMPULT; 277 case FCmpInst::FCMP_ULE: 278 return Expression::FCMPULE; 279 case FCmpInst::FCMP_UNE: 280 return Expression::FCMPUNE; 281 282 // THIS SHOULD NEVER HAPPEN 283 default: 284 assert(0 && "Comparison with unknown predicate?"); 285 return Expression::FCMPOEQ; 286 } 287 } 288} 289 290Expression::ExpressionOpcode 291 ValueTable::getOpcode(CastInst* C) { 292 switch(C->getOpcode()) { 293 case Instruction::Trunc: 294 return Expression::TRUNC; 295 case Instruction::ZExt: 296 return Expression::ZEXT; 297 case Instruction::SExt: 298 return Expression::SEXT; 299 case Instruction::FPToUI: 300 return Expression::FPTOUI; 301 case Instruction::FPToSI: 302 return Expression::FPTOSI; 303 case Instruction::UIToFP: 304 return Expression::UITOFP; 305 case Instruction::SIToFP: 306 return Expression::SITOFP; 307 case Instruction::FPTrunc: 308 return Expression::FPTRUNC; 309 case Instruction::FPExt: 310 return Expression::FPEXT; 311 case Instruction::PtrToInt: 312 return Expression::PTRTOINT; 313 case Instruction::IntToPtr: 314 return Expression::INTTOPTR; 315 case Instruction::BitCast: 316 return Expression::BITCAST; 317 318 // THIS SHOULD NEVER HAPPEN 319 default: 320 assert(0 && "Cast operator with unknown opcode?"); 321 return Expression::BITCAST; 322 } 323} 324 325Expression ValueTable::create_expression(BinaryOperator* BO) { 326 Expression e; 327 328 e.firstVN = lookup_or_add(BO->getOperand(0)); 329 e.secondVN = lookup_or_add(BO->getOperand(1)); 330 e.thirdVN = 0; 331 e.type = BO->getType(); 332 e.opcode = getOpcode(BO); 333 334 return e; 335} 336 337Expression ValueTable::create_expression(CmpInst* C) { 338 Expression e; 339 340 e.firstVN = lookup_or_add(C->getOperand(0)); 341 e.secondVN = lookup_or_add(C->getOperand(1)); 342 e.thirdVN = 0; 343 e.type = C->getType(); 344 e.opcode = getOpcode(C); 345 346 return e; 347} 348 349Expression ValueTable::create_expression(CastInst* C) { 350 Expression e; 351 352 e.firstVN = lookup_or_add(C->getOperand(0)); 353 e.secondVN = 0; 354 e.thirdVN = 0; 355 e.type = C->getType(); 356 e.opcode = getOpcode(C); 357 358 return e; 359} 360 361Expression ValueTable::create_expression(ShuffleVectorInst* S) { 362 Expression e; 363 364 e.firstVN = lookup_or_add(S->getOperand(0)); 365 e.secondVN = lookup_or_add(S->getOperand(1)); 366 e.thirdVN = lookup_or_add(S->getOperand(2)); 367 e.type = S->getType(); 368 e.opcode = Expression::SHUFFLE; 369 370 return e; 371} 372 373Expression ValueTable::create_expression(ExtractElementInst* E) { 374 Expression e; 375 376 e.firstVN = lookup_or_add(E->getOperand(0)); 377 e.secondVN = lookup_or_add(E->getOperand(1)); 378 e.thirdVN = 0; 379 e.type = E->getType(); 380 e.opcode = Expression::EXTRACT; 381 382 return e; 383} 384 385Expression ValueTable::create_expression(InsertElementInst* I) { 386 Expression e; 387 388 e.firstVN = lookup_or_add(I->getOperand(0)); 389 e.secondVN = lookup_or_add(I->getOperand(1)); 390 e.thirdVN = lookup_or_add(I->getOperand(2)); 391 e.type = I->getType(); 392 e.opcode = Expression::INSERT; 393 394 return e; 395} 396 397Expression ValueTable::create_expression(SelectInst* I) { 398 Expression e; 399 400 e.firstVN = lookup_or_add(I->getCondition()); 401 e.secondVN = lookup_or_add(I->getTrueValue()); 402 e.thirdVN = lookup_or_add(I->getFalseValue()); 403 e.type = I->getType(); 404 e.opcode = Expression::SELECT; 405 406 return e; 407} 408 409Expression ValueTable::create_expression(GetElementPtrInst* G) { 410 Expression e; 411 412 e.firstVN = lookup_or_add(G->getPointerOperand()); 413 e.secondVN = 0; 414 e.thirdVN = 0; 415 e.type = G->getType(); 416 e.opcode = Expression::GEP; 417 418 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 419 I != E; ++I) 420 e.varargs.push_back(lookup_or_add(*I)); 421 422 return e; 423} 424 425//===----------------------------------------------------------------------===// 426// ValueTable External Functions 427//===----------------------------------------------------------------------===// 428 429/// lookup_or_add - Returns the value number for the specified value, assigning 430/// it a new number if it did not have one before. 431uint32_t ValueTable::lookup_or_add(Value* V) { 432 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 433 if (VI != valueNumbering.end()) 434 return VI->second; 435 436 437 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 438 Expression e = create_expression(BO); 439 440 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 441 if (EI != expressionNumbering.end()) { 442 valueNumbering.insert(std::make_pair(V, EI->second)); 443 return EI->second; 444 } else { 445 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 446 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 447 448 return nextValueNumber++; 449 } 450 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 451 Expression e = create_expression(C); 452 453 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 454 if (EI != expressionNumbering.end()) { 455 valueNumbering.insert(std::make_pair(V, EI->second)); 456 return EI->second; 457 } else { 458 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 459 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 460 461 return nextValueNumber++; 462 } 463 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 464 Expression e = create_expression(U); 465 466 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 467 if (EI != expressionNumbering.end()) { 468 valueNumbering.insert(std::make_pair(V, EI->second)); 469 return EI->second; 470 } else { 471 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 472 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 473 474 return nextValueNumber++; 475 } 476 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 477 Expression e = create_expression(U); 478 479 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 480 if (EI != expressionNumbering.end()) { 481 valueNumbering.insert(std::make_pair(V, EI->second)); 482 return EI->second; 483 } else { 484 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 485 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 486 487 return nextValueNumber++; 488 } 489 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 490 Expression e = create_expression(U); 491 492 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 493 if (EI != expressionNumbering.end()) { 494 valueNumbering.insert(std::make_pair(V, EI->second)); 495 return EI->second; 496 } else { 497 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 498 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 499 500 return nextValueNumber++; 501 } 502 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 503 Expression e = create_expression(U); 504 505 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 506 if (EI != expressionNumbering.end()) { 507 valueNumbering.insert(std::make_pair(V, EI->second)); 508 return EI->second; 509 } else { 510 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 511 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 512 513 return nextValueNumber++; 514 } 515 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 516 Expression e = create_expression(U); 517 518 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 519 if (EI != expressionNumbering.end()) { 520 valueNumbering.insert(std::make_pair(V, EI->second)); 521 return EI->second; 522 } else { 523 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 524 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 525 526 return nextValueNumber++; 527 } 528 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 529 Expression e = create_expression(U); 530 531 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 532 if (EI != expressionNumbering.end()) { 533 valueNumbering.insert(std::make_pair(V, EI->second)); 534 return EI->second; 535 } else { 536 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 537 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 538 539 return nextValueNumber++; 540 } 541 } else { 542 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 543 return nextValueNumber++; 544 } 545} 546 547/// lookup - Returns the value number of the specified value. Fails if 548/// the value has not yet been numbered. 549uint32_t ValueTable::lookup(Value* V) const { 550 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 551 if (VI != valueNumbering.end()) 552 return VI->second; 553 else 554 assert(0 && "Value not numbered?"); 555 556 return 0; 557} 558 559/// clear - Remove all entries from the ValueTable 560void ValueTable::clear() { 561 valueNumbering.clear(); 562 expressionNumbering.clear(); 563 nextValueNumber = 1; 564} 565 566/// erase - Remove a value from the value numbering 567void ValueTable::erase(Value* V) { 568 valueNumbering.erase(V); 569} 570 571//===----------------------------------------------------------------------===// 572// ValueNumberedSet Class 573//===----------------------------------------------------------------------===// 574namespace { 575class ValueNumberedSet { 576 private: 577 SmallPtrSet<Value*, 8> contents; 578 BitVector numbers; 579 public: 580 ValueNumberedSet() { numbers.resize(1); } 581 ValueNumberedSet(const ValueNumberedSet& other) { 582 numbers = other.numbers; 583 contents = other.contents; 584 } 585 586 typedef SmallPtrSet<Value*, 8>::iterator iterator; 587 588 iterator begin() { return contents.begin(); } 589 iterator end() { return contents.end(); } 590 591 bool insert(Value* v) { return contents.insert(v); } 592 void insert(iterator I, iterator E) { contents.insert(I, E); } 593 void erase(Value* v) { contents.erase(v); } 594 unsigned count(Value* v) { return contents.count(v); } 595 size_t size() { return contents.size(); } 596 597 void set(unsigned i) { 598 if (i >= numbers.size()) 599 numbers.resize(i+1); 600 601 numbers.set(i); 602 } 603 604 void operator=(const ValueNumberedSet& other) { 605 contents = other.contents; 606 numbers = other.numbers; 607 } 608 609 void reset(unsigned i) { 610 if (i < numbers.size()) 611 numbers.reset(i); 612 } 613 614 bool test(unsigned i) { 615 if (i >= numbers.size()) 616 return false; 617 618 return numbers.test(i); 619 } 620 621 void clear() { 622 contents.clear(); 623 numbers.clear(); 624 } 625}; 626} 627 628//===----------------------------------------------------------------------===// 629// GVN Pass 630//===----------------------------------------------------------------------===// 631 632namespace { 633 634 class VISIBILITY_HIDDEN GVN : public FunctionPass { 635 bool runOnFunction(Function &F); 636 public: 637 static char ID; // Pass identification, replacement for typeid 638 GVN() : FunctionPass((intptr_t)&ID) { } 639 640 private: 641 ValueTable VN; 642 643 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 644 645 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 646 PhiMapType phiMap; 647 648 649 // This transformation requires dominator postdominator info 650 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 651 AU.setPreservesCFG(); 652 AU.addRequired<DominatorTree>(); 653 AU.addRequired<MemoryDependenceAnalysis>(); 654 AU.addPreserved<MemoryDependenceAnalysis>(); 655 } 656 657 // Helper fuctions 658 // FIXME: eliminate or document these better 659 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 660 void val_insert(ValueNumberedSet& s, Value* v); 661 bool processLoad(LoadInst* L, 662 DenseMap<Value*, LoadInst*>& lastLoad, 663 SmallVector<Instruction*, 4>& toErase); 664 bool processInstruction(Instruction* I, 665 ValueNumberedSet& currAvail, 666 DenseMap<Value*, LoadInst*>& lastSeenLoad, 667 SmallVector<Instruction*, 4>& toErase); 668 bool processNonLocalLoad(LoadInst* L, 669 SmallVector<Instruction*, 4>& toErase); 670 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 671 DenseMap<BasicBlock*, Value*> &Phis, 672 bool top_level = false); 673 void dump(DenseMap<BasicBlock*, Value*>& d); 674 bool iterateOnFunction(Function &F); 675 }; 676 677 char GVN::ID = 0; 678 679} 680 681// createGVNPass - The public interface to this file... 682FunctionPass *llvm::createGVNPass() { return new GVN(); } 683 684static RegisterPass<GVN> X("gvn", 685 "Global Value Numbering"); 686 687STATISTIC(NumGVNInstr, "Number of instructions deleted"); 688STATISTIC(NumGVNLoad, "Number of loads deleted"); 689 690/// find_leader - Given a set and a value number, return the first 691/// element of the set with that value number, or 0 if no such element 692/// is present 693Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 694 if (!vals.test(v)) 695 return 0; 696 697 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 698 I != E; ++I) 699 if (v == VN.lookup(*I)) 700 return *I; 701 702 assert(0 && "No leader found, but present bit is set?"); 703 return 0; 704} 705 706/// val_insert - Insert a value into a set only if there is not a value 707/// with the same value number already in the set 708void GVN::val_insert(ValueNumberedSet& s, Value* v) { 709 uint32_t num = VN.lookup(v); 710 if (!s.test(num)) 711 s.insert(v); 712} 713 714void GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 715 printf("{\n"); 716 for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 717 E = d.end(); I != E; ++I) { 718 if (I->second == MemoryDependenceAnalysis::None) 719 printf("None\n"); 720 else 721 I->second->dump(); 722 } 723 printf("}\n"); 724} 725 726 727/// GetValueForBlock - Get the value to use within the specified basic block. 728/// available values are in Phis. 729Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 730 DenseMap<BasicBlock*, Value*> &Phis, 731 bool top_level) { 732 733 // If we have already computed this value, return the previously computed val. 734 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 735 if (V != Phis.end() && !top_level) return V->second; 736 737 BasicBlock* singlePred = BB->getSinglePredecessor(); 738 if (singlePred) { 739 Value *ret = GetValueForBlock(singlePred, orig, Phis); 740 Phis[BB] = ret; 741 return ret; 742 } 743 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 744 // now, then get values to fill in the incoming values for the PHI. 745 PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", 746 BB->begin()); 747 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 748 749 if (Phis.count(BB) == 0) 750 Phis.insert(std::make_pair(BB, PN)); 751 752 // Fill in the incoming values for the block. 753 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 754 Value* val = GetValueForBlock(*PI, orig, Phis); 755 756 PN->addIncoming(val, *PI); 757 } 758 759 Value* v = PN->hasConstantValue(); 760 if (v) { 761 if (Instruction* inst = dyn_cast<Instruction>(v)) { 762 DominatorTree &DT = getAnalysis<DominatorTree>(); 763 if (DT.dominates(inst, PN)) { 764 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 765 766 MD.removeInstruction(PN); 767 PN->replaceAllUsesWith(inst); 768 769 SmallVector<BasicBlock*, 4> toRemove; 770 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 771 E = Phis.end(); I != E; ++I) 772 if (I->second == PN) 773 toRemove.push_back(I->first); 774 for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(), 775 E= toRemove.end(); I != E; ++I) 776 Phis[*I] = inst; 777 778 PN->eraseFromParent(); 779 780 Phis[BB] = inst; 781 782 return inst; 783 } 784 } else { 785 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 786 787 MD.removeInstruction(PN); 788 PN->replaceAllUsesWith(v); 789 790 SmallVector<BasicBlock*, 4> toRemove; 791 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 792 E = Phis.end(); I != E; ++I) 793 if (I->second == PN) 794 toRemove.push_back(I->first); 795 for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(), 796 E= toRemove.end(); I != E; ++I) 797 Phis[*I] = v; 798 799 PN->eraseFromParent(); 800 801 Phis[BB] = v; 802 803 return v; 804 } 805 } 806 807 phiMap[orig->getPointerOperand()].insert(PN); 808 return PN; 809} 810 811bool GVN::processNonLocalLoad(LoadInst* L, 812 SmallVector<Instruction*, 4>& toErase) { 813 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 814 815 DenseMap<BasicBlock*, Value*> deps; 816 MD.getNonLocalDependency(L, deps); 817 818 DenseMap<BasicBlock*, Value*> repl; 819 820 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 821 I != E; ++I) 822 if (I->second == MemoryDependenceAnalysis::None) { 823 return false; 824 } else if (I->second == MemoryDependenceAnalysis::NonLocal) { 825 continue; 826 }else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 827 if (S->getPointerOperand() == L->getPointerOperand()) 828 repl[I->first] = S->getOperand(0); 829 else 830 return false; 831 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 832 if (LD->getPointerOperand() == L->getPointerOperand()) 833 repl[I->first] = LD; 834 else 835 return false; 836 } else { 837 return false; 838 } 839 840 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 841 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 842 I != E; ++I) { 843 if ((*I)->getParent() == L->getParent()) { 844 MD.removeInstruction(L); 845 L->replaceAllUsesWith(*I); 846 toErase.push_back(L); 847 NumGVNLoad++; 848 849 return true; 850 } else { 851 repl.insert(std::make_pair((*I)->getParent(), *I)); 852 } 853 } 854 855 SmallPtrSet<BasicBlock*, 4> visited; 856 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 857 858 MD.removeInstruction(L); 859 L->replaceAllUsesWith(v); 860 toErase.push_back(L); 861 NumGVNLoad++; 862 863 return true; 864} 865 866bool GVN::processLoad(LoadInst* L, 867 DenseMap<Value*, LoadInst*>& lastLoad, 868 SmallVector<Instruction*, 4>& toErase) { 869 if (L->isVolatile()) { 870 lastLoad[L->getPointerOperand()] = L; 871 return false; 872 } 873 874 Value* pointer = L->getPointerOperand(); 875 LoadInst*& last = lastLoad[pointer]; 876 877 // ... to a pointer that has been loaded from before... 878 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 879 bool removedNonLocal = false; 880 Instruction* dep = MD.getDependency(L); 881 if (dep == MemoryDependenceAnalysis::NonLocal && 882 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 883 removedNonLocal = processNonLocalLoad(L, toErase); 884 885 if (!removedNonLocal) 886 last = L; 887 888 return removedNonLocal; 889 } 890 891 892 bool deletedLoad = false; 893 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 (!deletedLoad) 932 last = L; 933 934 return deletedLoad; 935} 936 937/// processInstruction - When calculating availability, handle an instruction 938/// by inserting it into the appropriate sets 939bool GVN::processInstruction(Instruction* I, 940 ValueNumberedSet& currAvail, 941 DenseMap<Value*, LoadInst*>& lastSeenLoad, 942 SmallVector<Instruction*, 4>& toErase) { 943 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 944 return processLoad(L, lastSeenLoad, toErase); 945 } 946 947 unsigned num = VN.lookup_or_add(I); 948 949 if (currAvail.test(num)) { 950 Value* repl = find_leader(currAvail, num); 951 952 VN.erase(I); 953 I->replaceAllUsesWith(repl); 954 toErase.push_back(I); 955 return true; 956 } else if (!I->isTerminator()) { 957 currAvail.set(num); 958 currAvail.insert(I); 959 } 960 961 return false; 962} 963 964// GVN::runOnFunction - This is the main transformation entry point for a 965// function. 966// 967bool GVN::runOnFunction(Function& F) { 968 bool changed = false; 969 bool shouldContinue = true; 970 971 while (shouldContinue) { 972 shouldContinue = iterateOnFunction(F); 973 changed |= shouldContinue; 974 } 975 976 return changed; 977} 978 979 980// GVN::iterateOnFunction - Executes one iteration of GVN 981bool GVN::iterateOnFunction(Function &F) { 982 // Clean out global sets from any previous functions 983 VN.clear(); 984 availableOut.clear(); 985 phiMap.clear(); 986 987 bool changed_function = false; 988 989 DominatorTree &DT = getAnalysis<DominatorTree>(); 990 991 SmallVector<Instruction*, 4> toErase; 992 993 // Top-down walk of the dominator tree 994 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 995 E = df_end(DT.getRootNode()); DI != E; ++DI) { 996 997 // Get the set to update for this block 998 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 999 DenseMap<Value*, LoadInst*> lastSeenLoad; 1000 1001 BasicBlock* BB = DI->getBlock(); 1002 1003 // A block inherits AVAIL_OUT from its dominator 1004 if (DI->getIDom() != 0) 1005 currAvail = availableOut[DI->getIDom()->getBlock()]; 1006 1007 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1008 BI != BE; ) { 1009 changed_function |= processInstruction(BI, currAvail, 1010 lastSeenLoad, toErase); 1011 1012 NumGVNInstr += toErase.size(); 1013 1014 // Avoid iterator invalidation 1015 ++BI; 1016 1017 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1018 E = toErase.end(); I != E; ++I) 1019 (*I)->eraseFromParent(); 1020 1021 toErase.clear(); 1022 } 1023 } 1024 1025 return changed_function; 1026} 1027