GVN.cpp revision 9f435740b1c652926c80529e00c92925a3196d79
147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org//===- GVN.cpp - Eliminate redundant values and loads ------------===// 247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// 347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// The LLVM Compiler Infrastructure 447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// 547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// This file was developed by the Owen Anderson and is distributed under 647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// the University of Illinois Open Source License. See LICENSE.TXT for details. 747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// 847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org//===----------------------------------------------------------------------===// 947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// 1047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// This pass performs global value numbering to eliminate fully redundant 1147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// instructions. It also performs simple dead load elimination. 1247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// 1347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org//===----------------------------------------------------------------------===// 1447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 1547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#define DEBUG_TYPE "gvn" 1647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/Value.h" 1747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/Transforms/Scalar.h" 1847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/BasicBlock.h" 1947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/Instructions.h" 2047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/Function.h" 2147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/DerivedTypes.h" 2247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/Analysis/Dominators.h" 2347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/ADT/BitVector.h" 2447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/ADT/DenseMap.h" 2547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/ADT/DepthFirstIterator.h" 2647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/ADT/SmallPtrSet.h" 2747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/ADT/SmallVector.h" 2847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/ADT/Statistic.h" 2947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/Analysis/MemoryDependenceAnalysis.h" 3047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/Support/CFG.h" 3147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "llvm/Support/Compiler.h" 3247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.orgusing namespace llvm; 3347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 3447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org//===----------------------------------------------------------------------===// 3547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// ValueTable Class 3647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org//===----------------------------------------------------------------------===// 3747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 3847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org/// This class holds the mapping between values and value numbers. It is used 3947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org/// as an efficient mechanism to determine the expression-wise equivalence of 4047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org/// two values. 4147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.orgnamespace { 4247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org struct VISIBILITY_HIDDEN Expression { 4347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 4447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 4547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 4647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 4747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 4847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 4947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 5047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 5147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 5247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY, 5347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org TOMBSTONE }; 5447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 5547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org ExpressionOpcode opcode; 5647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org const Type* type; 5747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org uint32_t firstVN; 5847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org uint32_t secondVN; 5947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org uint32_t thirdVN; 6047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org SmallVector<uint32_t, 4> varargs; 6147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 6247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression() { } 6347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression(ExpressionOpcode o) : opcode(o) { } 6447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 6547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org bool operator==(const Expression &other) const { 6647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (opcode != other.opcode) 6747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 6847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (opcode == EMPTY || opcode == TOMBSTONE) 6947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 7047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (type != other.type) 7147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 7247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (firstVN != other.firstVN) 7347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 7447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (secondVN != other.secondVN) 7547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 7647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (thirdVN != other.thirdVN) 7747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 7847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else { 7947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (varargs.size() != other.varargs.size()) 8047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 8147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 8247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org for (size_t i = 0; i < varargs.size(); ++i) 8347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (varargs[i] != other.varargs[i]) 8447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 8547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 8647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 8747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 8847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 8947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 9047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org bool operator!=(const Expression &other) const { 9147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (opcode != other.opcode) 9247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 9347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (opcode == EMPTY || opcode == TOMBSTONE) 9447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 9547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (type != other.type) 9647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 9747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (firstVN != other.firstVN) 9847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 9947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (secondVN != other.secondVN) 10047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 10147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else if (thirdVN != other.thirdVN) 10247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 10347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org else { 10447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (varargs.size() != other.varargs.size()) 10547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 10647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 10747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org for (size_t i = 0; i < varargs.size(); ++i) 10847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (varargs[i] != other.varargs[i]) 10947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 11047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 11147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 11247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 11347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 11447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org }; 11547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 11647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org class VISIBILITY_HIDDEN ValueTable { 11747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org private: 11847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org DenseMap<Value*, uint32_t> valueNumbering; 11947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org DenseMap<Expression, uint32_t> expressionNumbering; 12047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 12147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org uint32_t nextValueNumber; 12247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 12347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 12447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression::ExpressionOpcode getOpcode(CmpInst* C); 12547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression::ExpressionOpcode getOpcode(CastInst* C); 12647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression create_expression(BinaryOperator* BO); 12747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression create_expression(CmpInst* C); 12847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression create_expression(ShuffleVectorInst* V); 12947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression create_expression(ExtractElementInst* C); 13047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression create_expression(InsertElementInst* V); 13147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression create_expression(SelectInst* V); 13247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression create_expression(CastInst* C); 13347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Expression create_expression(GetElementPtrInst* G); 13447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org public: 13547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org ValueTable() { nextValueNumber = 1; } 136 uint32_t lookup_or_add(Value* V); 137 uint32_t lookup(Value* V) const; 138 void add(Value* V, uint32_t num); 139 void clear(); 140 void erase(Value* v); 141 unsigned size(); 142 }; 143} 144 145namespace llvm { 146template <> struct DenseMapKeyInfo<Expression> { 147 static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); } 148 static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); } 149 150 static unsigned getHashValue(const Expression e) { 151 unsigned hash = e.opcode; 152 153 hash = e.firstVN + hash * 37; 154 hash = e.secondVN + hash * 37; 155 hash = e.thirdVN + hash * 37; 156 157 hash = (unsigned)((uintptr_t)e.type >> 4) ^ 158 (unsigned)((uintptr_t)e.type >> 9) + 159 hash * 37; 160 161 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end(); 162 I != E; ++I) 163 hash = *I + hash * 37; 164 165 return hash; 166 } 167 static bool isPod() { return true; } 168}; 169} 170 171//===----------------------------------------------------------------------===// 172// ValueTable Internal Functions 173//===----------------------------------------------------------------------===// 174Expression::ExpressionOpcode 175 ValueTable::getOpcode(BinaryOperator* BO) { 176 switch(BO->getOpcode()) { 177 case Instruction::Add: 178 return Expression::ADD; 179 case Instruction::Sub: 180 return Expression::SUB; 181 case Instruction::Mul: 182 return Expression::MUL; 183 case Instruction::UDiv: 184 return Expression::UDIV; 185 case Instruction::SDiv: 186 return Expression::SDIV; 187 case Instruction::FDiv: 188 return Expression::FDIV; 189 case Instruction::URem: 190 return Expression::UREM; 191 case Instruction::SRem: 192 return Expression::SREM; 193 case Instruction::FRem: 194 return Expression::FREM; 195 case Instruction::Shl: 196 return Expression::SHL; 197 case Instruction::LShr: 198 return Expression::LSHR; 199 case Instruction::AShr: 200 return Expression::ASHR; 201 case Instruction::And: 202 return Expression::AND; 203 case Instruction::Or: 204 return Expression::OR; 205 case Instruction::Xor: 206 return Expression::XOR; 207 208 // THIS SHOULD NEVER HAPPEN 209 default: 210 assert(0 && "Binary operator with unknown opcode?"); 211 return Expression::ADD; 212 } 213} 214 215Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 216 if (C->getOpcode() == Instruction::ICmp) { 217 switch (C->getPredicate()) { 218 case ICmpInst::ICMP_EQ: 219 return Expression::ICMPEQ; 220 case ICmpInst::ICMP_NE: 221 return Expression::ICMPNE; 222 case ICmpInst::ICMP_UGT: 223 return Expression::ICMPUGT; 224 case ICmpInst::ICMP_UGE: 225 return Expression::ICMPUGE; 226 case ICmpInst::ICMP_ULT: 227 return Expression::ICMPULT; 228 case ICmpInst::ICMP_ULE: 229 return Expression::ICMPULE; 230 case ICmpInst::ICMP_SGT: 231 return Expression::ICMPSGT; 232 case ICmpInst::ICMP_SGE: 233 return Expression::ICMPSGE; 234 case ICmpInst::ICMP_SLT: 235 return Expression::ICMPSLT; 236 case ICmpInst::ICMP_SLE: 237 return Expression::ICMPSLE; 238 239 // THIS SHOULD NEVER HAPPEN 240 default: 241 assert(0 && "Comparison with unknown predicate?"); 242 return Expression::ICMPEQ; 243 } 244 } else { 245 switch (C->getPredicate()) { 246 case FCmpInst::FCMP_OEQ: 247 return Expression::FCMPOEQ; 248 case FCmpInst::FCMP_OGT: 249 return Expression::FCMPOGT; 250 case FCmpInst::FCMP_OGE: 251 return Expression::FCMPOGE; 252 case FCmpInst::FCMP_OLT: 253 return Expression::FCMPOLT; 254 case FCmpInst::FCMP_OLE: 255 return Expression::FCMPOLE; 256 case FCmpInst::FCMP_ONE: 257 return Expression::FCMPONE; 258 case FCmpInst::FCMP_ORD: 259 return Expression::FCMPORD; 260 case FCmpInst::FCMP_UNO: 261 return Expression::FCMPUNO; 262 case FCmpInst::FCMP_UEQ: 263 return Expression::FCMPUEQ; 264 case FCmpInst::FCMP_UGT: 265 return Expression::FCMPUGT; 266 case FCmpInst::FCMP_UGE: 267 return Expression::FCMPUGE; 268 case FCmpInst::FCMP_ULT: 269 return Expression::FCMPULT; 270 case FCmpInst::FCMP_ULE: 271 return Expression::FCMPULE; 272 case FCmpInst::FCMP_UNE: 273 return Expression::FCMPUNE; 274 275 // THIS SHOULD NEVER HAPPEN 276 default: 277 assert(0 && "Comparison with unknown predicate?"); 278 return Expression::FCMPOEQ; 279 } 280 } 281} 282 283Expression::ExpressionOpcode 284 ValueTable::getOpcode(CastInst* C) { 285 switch(C->getOpcode()) { 286 case Instruction::Trunc: 287 return Expression::TRUNC; 288 case Instruction::ZExt: 289 return Expression::ZEXT; 290 case Instruction::SExt: 291 return Expression::SEXT; 292 case Instruction::FPToUI: 293 return Expression::FPTOUI; 294 case Instruction::FPToSI: 295 return Expression::FPTOSI; 296 case Instruction::UIToFP: 297 return Expression::UITOFP; 298 case Instruction::SIToFP: 299 return Expression::SITOFP; 300 case Instruction::FPTrunc: 301 return Expression::FPTRUNC; 302 case Instruction::FPExt: 303 return Expression::FPEXT; 304 case Instruction::PtrToInt: 305 return Expression::PTRTOINT; 306 case Instruction::IntToPtr: 307 return Expression::INTTOPTR; 308 case Instruction::BitCast: 309 return Expression::BITCAST; 310 311 // THIS SHOULD NEVER HAPPEN 312 default: 313 assert(0 && "Cast operator with unknown opcode?"); 314 return Expression::BITCAST; 315 } 316} 317 318Expression ValueTable::create_expression(BinaryOperator* BO) { 319 Expression e; 320 321 e.firstVN = lookup_or_add(BO->getOperand(0)); 322 e.secondVN = lookup_or_add(BO->getOperand(1)); 323 e.thirdVN = 0; 324 e.type = BO->getType(); 325 e.opcode = getOpcode(BO); 326 327 return e; 328} 329 330Expression ValueTable::create_expression(CmpInst* C) { 331 Expression e; 332 333 e.firstVN = lookup_or_add(C->getOperand(0)); 334 e.secondVN = lookup_or_add(C->getOperand(1)); 335 e.thirdVN = 0; 336 e.type = C->getType(); 337 e.opcode = getOpcode(C); 338 339 return e; 340} 341 342Expression ValueTable::create_expression(CastInst* C) { 343 Expression e; 344 345 e.firstVN = lookup_or_add(C->getOperand(0)); 346 e.secondVN = 0; 347 e.thirdVN = 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.type = S->getType(); 361 e.opcode = Expression::SHUFFLE; 362 363 return e; 364} 365 366Expression ValueTable::create_expression(ExtractElementInst* E) { 367 Expression e; 368 369 e.firstVN = lookup_or_add(E->getOperand(0)); 370 e.secondVN = lookup_or_add(E->getOperand(1)); 371 e.thirdVN = 0; 372 e.type = E->getType(); 373 e.opcode = Expression::EXTRACT; 374 375 return e; 376} 377 378Expression ValueTable::create_expression(InsertElementInst* I) { 379 Expression e; 380 381 e.firstVN = lookup_or_add(I->getOperand(0)); 382 e.secondVN = lookup_or_add(I->getOperand(1)); 383 e.thirdVN = lookup_or_add(I->getOperand(2)); 384 e.type = I->getType(); 385 e.opcode = Expression::INSERT; 386 387 return e; 388} 389 390Expression ValueTable::create_expression(SelectInst* I) { 391 Expression e; 392 393 e.firstVN = lookup_or_add(I->getCondition()); 394 e.secondVN = lookup_or_add(I->getTrueValue()); 395 e.thirdVN = lookup_or_add(I->getFalseValue()); 396 e.type = I->getType(); 397 e.opcode = Expression::SELECT; 398 399 return e; 400} 401 402Expression ValueTable::create_expression(GetElementPtrInst* G) { 403 Expression e; 404 405 e.firstVN = lookup_or_add(G->getPointerOperand()); 406 e.secondVN = 0; 407 e.thirdVN = 0; 408 e.type = G->getType(); 409 e.opcode = Expression::GEP; 410 411 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 412 I != E; ++I) 413 e.varargs.push_back(lookup_or_add(*I)); 414 415 return e; 416} 417 418//===----------------------------------------------------------------------===// 419// ValueTable External Functions 420//===----------------------------------------------------------------------===// 421 422/// lookup_or_add - Returns the value number for the specified value, assigning 423/// it a new number if it did not have one before. 424uint32_t ValueTable::lookup_or_add(Value* V) { 425 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 426 if (VI != valueNumbering.end()) 427 return VI->second; 428 429 430 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 431 Expression e = create_expression(BO); 432 433 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 434 if (EI != expressionNumbering.end()) { 435 valueNumbering.insert(std::make_pair(V, EI->second)); 436 return EI->second; 437 } else { 438 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 439 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 440 441 return nextValueNumber++; 442 } 443 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 444 Expression e = create_expression(C); 445 446 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 447 if (EI != expressionNumbering.end()) { 448 valueNumbering.insert(std::make_pair(V, EI->second)); 449 return EI->second; 450 } else { 451 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 452 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 453 454 return nextValueNumber++; 455 } 456 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 457 Expression e = create_expression(U); 458 459 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 460 if (EI != expressionNumbering.end()) { 461 valueNumbering.insert(std::make_pair(V, EI->second)); 462 return EI->second; 463 } else { 464 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 465 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 466 467 return nextValueNumber++; 468 } 469 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 470 Expression e = create_expression(U); 471 472 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 473 if (EI != expressionNumbering.end()) { 474 valueNumbering.insert(std::make_pair(V, EI->second)); 475 return EI->second; 476 } else { 477 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 478 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 479 480 return nextValueNumber++; 481 } 482 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 483 Expression e = create_expression(U); 484 485 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 486 if (EI != expressionNumbering.end()) { 487 valueNumbering.insert(std::make_pair(V, EI->second)); 488 return EI->second; 489 } else { 490 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 491 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 492 493 return nextValueNumber++; 494 } 495 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 496 Expression e = create_expression(U); 497 498 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 499 if (EI != expressionNumbering.end()) { 500 valueNumbering.insert(std::make_pair(V, EI->second)); 501 return EI->second; 502 } else { 503 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 504 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 505 506 return nextValueNumber++; 507 } 508 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 509 Expression e = create_expression(U); 510 511 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 512 if (EI != expressionNumbering.end()) { 513 valueNumbering.insert(std::make_pair(V, EI->second)); 514 return EI->second; 515 } else { 516 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 517 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 518 519 return nextValueNumber++; 520 } 521 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 522 Expression e = create_expression(U); 523 524 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 525 if (EI != expressionNumbering.end()) { 526 valueNumbering.insert(std::make_pair(V, EI->second)); 527 return EI->second; 528 } else { 529 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 530 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 531 532 return nextValueNumber++; 533 } 534 } else { 535 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 536 return nextValueNumber++; 537 } 538} 539 540/// lookup - Returns the value number of the specified value. Fails if 541/// the value has not yet been numbered. 542uint32_t ValueTable::lookup(Value* V) const { 543 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 544 if (VI != valueNumbering.end()) 545 return VI->second; 546 else 547 assert(0 && "Value not numbered?"); 548 549 return 0; 550} 551 552/// clear - Remove all entries from the ValueTable 553void ValueTable::clear() { 554 valueNumbering.clear(); 555 expressionNumbering.clear(); 556 nextValueNumber = 1; 557} 558 559//===----------------------------------------------------------------------===// 560// ValueNumberedSet Class 561//===----------------------------------------------------------------------===// 562namespace { 563class ValueNumberedSet { 564 private: 565 SmallPtrSet<Value*, 8> contents; 566 BitVector numbers; 567 public: 568 ValueNumberedSet() { numbers.resize(1); } 569 ValueNumberedSet(const ValueNumberedSet& other) { 570 numbers = other.numbers; 571 contents = other.contents; 572 } 573 574 typedef SmallPtrSet<Value*, 8>::iterator iterator; 575 576 iterator begin() { return contents.begin(); } 577 iterator end() { return contents.end(); } 578 579 bool insert(Value* v) { return contents.insert(v); } 580 void insert(iterator I, iterator E) { contents.insert(I, E); } 581 void erase(Value* v) { contents.erase(v); } 582 unsigned count(Value* v) { return contents.count(v); } 583 size_t size() { return contents.size(); } 584 585 void set(unsigned i) { 586 if (i >= numbers.size()) 587 numbers.resize(i+1); 588 589 numbers.set(i); 590 } 591 592 void operator=(const ValueNumberedSet& other) { 593 contents = other.contents; 594 numbers = other.numbers; 595 } 596 597 void reset(unsigned i) { 598 if (i < numbers.size()) 599 numbers.reset(i); 600 } 601 602 bool test(unsigned i) { 603 if (i >= numbers.size()) 604 return false; 605 606 return numbers.test(i); 607 } 608 609 void clear() { 610 contents.clear(); 611 numbers.clear(); 612 } 613}; 614} 615 616//===----------------------------------------------------------------------===// 617// GVN Pass 618//===----------------------------------------------------------------------===// 619 620namespace { 621 622 class VISIBILITY_HIDDEN GVN : public FunctionPass { 623 bool runOnFunction(Function &F); 624 public: 625 static char ID; // Pass identification, replacement for typeid 626 GVN() : FunctionPass((intptr_t)&ID) { } 627 628 private: 629 ValueTable VN; 630 631 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 632 633 // This transformation requires dominator postdominator info 634 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 635 AU.setPreservesCFG(); 636 AU.addRequired<DominatorTree>(); 637 AU.addRequired<MemoryDependenceAnalysis>(); 638 AU.addPreserved<MemoryDependenceAnalysis>(); 639 } 640 641 // Helper fuctions 642 // FIXME: eliminate or document these better 643 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 644 void val_insert(ValueNumberedSet& s, Value* v); 645 bool processLoad(LoadInst* L, 646 DenseMap<Value*, LoadInst*>& lastLoad, 647 SmallVector<Instruction*, 4>& toErase); 648 bool processInstruction(Instruction* I, 649 ValueNumberedSet& currAvail, 650 DenseMap<Value*, LoadInst*>& lastSeenLoad, 651 SmallVector<Instruction*, 4>& toErase); 652 bool processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase); 653 Value *performPHIConstruction(BasicBlock *BB, LoadInst* orig, 654 DenseMap<BasicBlock*, Value*> &Phis, 655 SmallPtrSet<BasicBlock*, 4>& visited); 656 void dump(DenseMap<BasicBlock*, Value*>& d); 657 }; 658 659 char GVN::ID = 0; 660 661} 662 663// createGVNPass - The public interface to this file... 664FunctionPass *llvm::createGVNPass() { return new GVN(); } 665 666static RegisterPass<GVN> X("gvn", 667 "Global Value Numbering"); 668 669STATISTIC(NumGVNInstr, "Number of instructions deleted"); 670STATISTIC(NumGVNLoad, "Number of loads deleted"); 671 672/// find_leader - Given a set and a value number, return the first 673/// element of the set with that value number, or 0 if no such element 674/// is present 675Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 676 if (!vals.test(v)) 677 return 0; 678 679 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 680 I != E; ++I) 681 if (v == VN.lookup(*I)) 682 return *I; 683 684 assert(0 && "No leader found, but present bit is set?"); 685 return 0; 686} 687 688/// val_insert - Insert a value into a set only if there is not a value 689/// with the same value number already in the set 690void GVN::val_insert(ValueNumberedSet& s, Value* v) { 691 uint32_t num = VN.lookup(v); 692 if (!s.test(num)) 693 s.insert(v); 694} 695 696void GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 697 printf("{\n"); 698 for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 699 E = d.end(); I != E; ++I) { 700 if (I->second == MemoryDependenceAnalysis::None) 701 printf("None\n"); 702 else 703 I->second->dump(); 704 } 705 printf("}\n"); 706} 707 708 709Value *GVN::performPHIConstruction(BasicBlock *BB, LoadInst* orig, 710 DenseMap<BasicBlock*, Value*> &Phis, 711 SmallPtrSet<BasicBlock*, 4>& visited) { 712 DenseMap<BasicBlock*, Value*>::iterator DI = Phis.find(BB); 713 if (DI != Phis.end()) 714 return DI->second; 715 716 unsigned numPreds = std::distance(pred_begin(BB), pred_end(BB)); 717 718 if (numPreds == 1) { 719 DenseMap<BasicBlock*, Value*>::iterator DI = Phis.find(BB); 720 if (DI != Phis.end()) { 721 Phis.insert(std::make_pair(BB, DI->second)); 722 return DI->second; 723 } else { 724 visited.insert(BB); 725 Value* domV = performPHIConstruction(*pred_begin(BB), orig, Phis, visited); 726 visited.erase(BB); 727 728 Phis.insert(std::make_pair(BB, domV)); 729 return domV; 730 } 731 } else { 732 PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", BB->begin()); 733 PN->reserveOperandSpace(numPreds); 734 Phis[BB] = PN; 735 736 visited.insert(BB); 737 // Fill in the incoming values for the block. 738 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 739 if (!visited.count(*PI)) 740 PN->addIncoming(performPHIConstruction(*PI, orig, Phis, visited), *PI); 741 else 742 PN->addIncoming(Phis[*PI], *PI); 743 visited.erase(BB); 744 745 bool all_same = PN->getNumIncomingValues() != 1; 746 Value* first = PN->getIncomingValue(0); 747 for (unsigned i = 1; i < PN->getNumIncomingValues(); ++i) 748 all_same &= (PN->getIncomingValue(i) == first); 749 750 if (all_same) { 751 PN->eraseFromParent(); 752 Phis[BB] = first; 753 return first; 754 } else { 755 return PN; 756 } 757 } 758} 759 760bool GVN::processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase) { 761 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 762 763 DenseMap<BasicBlock*, Value*> deps; 764 bool ret = MD.getNonLocalDependency(L, deps); 765 if (!ret) 766 return false; 767 768 DenseMap<BasicBlock*, Value*> repl; 769 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 770 I != E; ++I) 771 if (I->second == MemoryDependenceAnalysis::None) { 772 return false; 773 } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 774 if (S->getPointerOperand() == L->getPointerOperand()) 775 repl.insert(std::make_pair(I->first, S->getOperand(0))); 776 else 777 return false; 778 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 779 if (LD->getPointerOperand() == L->getPointerOperand()) 780 repl.insert(std::make_pair(I->first, LD)); 781 else 782 return false; 783 } else { 784 return false; 785 } 786 787 SmallPtrSet<BasicBlock*, 4> visited; 788 Value* v = performPHIConstruction(L->getParent(), L, repl, visited); 789 790 MD.removeInstruction(L); 791 L->replaceAllUsesWith(v); 792 toErase.push_back(L); 793 794 return true; 795} 796 797bool GVN::processLoad(LoadInst* L, 798 DenseMap<Value*, LoadInst*>& lastLoad, 799 SmallVector<Instruction*, 4>& toErase) { 800 if (L->isVolatile()) { 801 lastLoad[L->getPointerOperand()] = L; 802 return false; 803 } 804 805 Value* pointer = L->getPointerOperand(); 806 LoadInst*& last = lastLoad[pointer]; 807 808 // ... to a pointer that has been loaded from before... 809 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 810 Instruction* dep = MD.getDependency(L); 811 if (dep == MemoryDependenceAnalysis::NonLocal && 812 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) 813 processNonLocalLoad(L, toErase); 814 bool deletedLoad = false; 815 816 while (dep != MemoryDependenceAnalysis::None && 817 dep != MemoryDependenceAnalysis::NonLocal && 818 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 819 // ... that depends on a store ... 820 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 821 if (S->getPointerOperand() == pointer) { 822 // Remove it! 823 MD.removeInstruction(L); 824 825 L->replaceAllUsesWith(S->getOperand(0)); 826 toErase.push_back(L); 827 deletedLoad = true; 828 NumGVNLoad++; 829 } 830 831 // Whether we removed it or not, we can't 832 // go any further 833 break; 834 } else if (!last) { 835 // If we don't depend on a store, and we haven't 836 // been loaded before, bail. 837 break; 838 } else if (dep == last) { 839 // Remove it! 840 MD.removeInstruction(L); 841 842 L->replaceAllUsesWith(last); 843 toErase.push_back(L); 844 deletedLoad = true; 845 NumGVNLoad++; 846 847 break; 848 } else { 849 dep = MD.getDependency(L, dep); 850 } 851 } 852 853 if (!deletedLoad) 854 last = L; 855 856 return deletedLoad; 857} 858 859/// buildsets_availout - When calculating availability, handle an instruction 860/// by inserting it into the appropriate sets 861bool GVN::processInstruction(Instruction* I, 862 ValueNumberedSet& currAvail, 863 DenseMap<Value*, LoadInst*>& lastSeenLoad, 864 SmallVector<Instruction*, 4>& toErase) { 865 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 866 return processLoad(L, lastSeenLoad, toErase); 867 } 868 869 unsigned num = VN.lookup_or_add(I); 870 871 if (currAvail.test(num)) { 872 Value* repl = find_leader(currAvail, num); 873 874 I->replaceAllUsesWith(repl); 875 toErase.push_back(I); 876 return true; 877 } else if (!I->isTerminator()) { 878 currAvail.set(num); 879 currAvail.insert(I); 880 } 881 882 return false; 883} 884 885// GVN::runOnFunction - This is the main transformation entry point for a 886// function. 887// 888bool GVN::runOnFunction(Function &F) { 889 // Clean out global sets from any previous functions 890 VN.clear(); 891 availableOut.clear(); 892 893 bool changed_function = false; 894 895 DominatorTree &DT = getAnalysis<DominatorTree>(); 896 897 SmallVector<Instruction*, 4> toErase; 898 899 // Top-down walk of the dominator tree 900 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 901 E = df_end(DT.getRootNode()); DI != E; ++DI) { 902 903 // Get the set to update for this block 904 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 905 DenseMap<Value*, LoadInst*> lastSeenLoad; 906 907 BasicBlock* BB = DI->getBlock(); 908 909 // A block inherits AVAIL_OUT from its dominator 910 if (DI->getIDom() != 0) 911 currAvail = availableOut[DI->getIDom()->getBlock()]; 912 913 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 914 BI != BE; ++BI) { 915 changed_function |= processInstruction(BI, currAvail, lastSeenLoad, toErase); 916 917 NumGVNInstr += toErase.size(); 918 919 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 920 E = toErase.end(); I != E; ++I) 921 (*I)->eraseFromParent(); 922 923 toErase.clear(); 924 } 925 } 926 927 return changed_function; 928} 929