GVN.cpp revision 663e441a752cabef645fdb2640b6f1d5dc66207b
1a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor//===- GVN.cpp - Eliminate redundant values and loads ------------===// 2a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// 3a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// The LLVM Compiler Infrastructure 4a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// 5a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// This file is distributed under the University of Illinois Open Source 6a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// License. See LICENSE.TXT for details. 7a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// 8a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor//===----------------------------------------------------------------------===// 9a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// 10a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// This pass performs global value numbering to eliminate fully redundant 11894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor// instructions. It also performs simple dead load elimination. 12894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor// 13894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor// Note that this pass does the value numbering itself, it does not use the 14a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// ValueNumbering analysis passes. 15a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// 16a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor//===----------------------------------------------------------------------===// 17a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 18a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#define DEBUG_TYPE "gvn" 191a49d97d762570027863e9209af81d445e4f1502Douglas Gregor#include "llvm/Transforms/Scalar.h" 201a49d97d762570027863e9209af81d445e4f1502Douglas Gregor#include "llvm/BasicBlock.h" 21a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/Constants.h" 22fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor#include "llvm/DerivedTypes.h" 23a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/Function.h" 24651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines#include "llvm/Instructions.h" 25a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/Value.h" 26a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/ADT/DenseMap.h" 271a49d97d762570027863e9209af81d445e4f1502Douglas Gregor#include "llvm/ADT/DepthFirstIterator.h" 281a49d97d762570027863e9209af81d445e4f1502Douglas Gregor#include "llvm/ADT/SmallPtrSet.h" 291a49d97d762570027863e9209af81d445e4f1502Douglas Gregor#include "llvm/ADT/SmallVector.h" 301a49d97d762570027863e9209af81d445e4f1502Douglas Gregor#include "llvm/ADT/Statistic.h" 311a49d97d762570027863e9209af81d445e4f1502Douglas Gregor#include "llvm/Analysis/Dominators.h" 32a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/Analysis/AliasAnalysis.h" 33a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/Analysis/MemoryDependenceAnalysis.h" 34a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/Support/CFG.h" 35a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/Support/CommandLine.h" 36a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/Support/Compiler.h" 37809d254c1f1521c141c8807638c29d67b50ebf29Benjamin Kramer#include "llvm/Support/Debug.h" 38a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor#include "llvm/Transforms/Utils/BasicBlockUtils.h" 39677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor#include <cstdio> 40677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregorusing namespace llvm; 41a5a3e01c504c00b1860286540090695ec0167531Douglas Gregor 42677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas GregorSTATISTIC(NumGVNInstr, "Number of instructions deleted"); 43a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas GregorSTATISTIC(NumGVNLoad, "Number of loads deleted"); 44a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas GregorSTATISTIC(NumGVNPRE, "Number of instructions PRE'd"); 45a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas GregorSTATISTIC(NumGVNBlocks, "Number of blocks merged"); 46677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor 47677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregorstatic cl::opt<bool> EnablePRE("enable-pre", 48a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor cl::init(true), cl::Hidden); 49894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor 50a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor//===----------------------------------------------------------------------===// 51a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor// ValueTable Class 52894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor//===----------------------------------------------------------------------===// 53894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor 54894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor/// This class holds the mapping between values and value numbers. It is used 55894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor/// as an efficient mechanism to determine the expression-wise equivalence of 56894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor/// two values. 57894719bf99cf0131d954c714179bb47eee472b91Douglas Gregornamespace { 58894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor struct VISIBILITY_HIDDEN Expression { 59a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 601a49d97d762570027863e9209af81d445e4f1502Douglas Gregor FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 611a49d97d762570027863e9209af81d445e4f1502Douglas Gregor ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 62651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 631a49d97d762570027863e9209af81d445e4f1502Douglas Gregor FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 641a49d97d762570027863e9209af81d445e4f1502Douglas Gregor FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 651a49d97d762570027863e9209af81d445e4f1502Douglas Gregor FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 661a49d97d762570027863e9209af81d445e4f1502Douglas Gregor SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 671a49d97d762570027863e9209af81d445e4f1502Douglas Gregor FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 681a49d97d762570027863e9209af81d445e4f1502Douglas Gregor PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT, 691a49d97d762570027863e9209af81d445e4f1502Douglas Gregor EMPTY, TOMBSTONE }; 701a49d97d762570027863e9209af81d445e4f1502Douglas Gregor 711a49d97d762570027863e9209af81d445e4f1502Douglas Gregor ExpressionOpcode opcode; 721a49d97d762570027863e9209af81d445e4f1502Douglas Gregor const Type* type; 73677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor uint32_t firstVN; 74677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor uint32_t secondVN; 75fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor uint32_t thirdVN; 76677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor SmallVector<uint32_t, 4> varargs; 77677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor Value* function; 78677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor 79677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor Expression() { } 80677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor Expression(ExpressionOpcode o) : opcode(o) { } 81677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor 82677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor bool operator==(const Expression &other) const { 831a49d97d762570027863e9209af81d445e4f1502Douglas Gregor if (opcode != other.opcode) 84677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor return false; 85677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor else if (opcode == EMPTY || opcode == TOMBSTONE) 86677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor return true; 871a49d97d762570027863e9209af81d445e4f1502Douglas Gregor else if (type != other.type) 88677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor return false; 89677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor else if (function != other.function) 90677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor return false; 911a49d97d762570027863e9209af81d445e4f1502Douglas Gregor else if (firstVN != other.firstVN) 921a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return false; 931a49d97d762570027863e9209af81d445e4f1502Douglas Gregor else if (secondVN != other.secondVN) 941a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return false; 951a49d97d762570027863e9209af81d445e4f1502Douglas Gregor else if (thirdVN != other.thirdVN) 961a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return false; 97677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor else { 981a49d97d762570027863e9209af81d445e4f1502Douglas Gregor if (varargs.size() != other.varargs.size()) 991a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return false; 100677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor 1011a49d97d762570027863e9209af81d445e4f1502Douglas Gregor for (size_t i = 0; i < varargs.size(); ++i) 102677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor if (varargs[i] != other.varargs[i]) 1031a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return false; 104fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor 105fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor return true; 106fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor } 107fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor } 108fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor 109fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor bool operator!=(const Expression &other) const { 1101a49d97d762570027863e9209af81d445e4f1502Douglas Gregor if (opcode != other.opcode) 1111a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return true; 1121a49d97d762570027863e9209af81d445e4f1502Douglas Gregor else if (opcode == EMPTY || opcode == TOMBSTONE) 1131a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return false; 1141a49d97d762570027863e9209af81d445e4f1502Douglas Gregor else if (type != other.type) 1151a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return true; 116fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor else if (function != other.function) 117a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor return true; 118677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor else if (firstVN != other.firstVN) 1191a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return true; 1201a49d97d762570027863e9209af81d445e4f1502Douglas Gregor else if (secondVN != other.secondVN) 1219ef9b8540a608a93efaaae1d26d94e8087c30b55David Blaikie return true; 1229ef9b8540a608a93efaaae1d26d94e8087c30b55David Blaikie else if (thirdVN != other.thirdVN) 123a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor return true; 124a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor else { 1251a49d97d762570027863e9209af81d445e4f1502Douglas Gregor if (varargs.size() != other.varargs.size()) 1261a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return true; 127a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 128a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor for (size_t i = 0; i < varargs.size(); ++i) 129a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor if (varargs[i] != other.varargs[i]) 130a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor return true; 131a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 132a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor return false; 133a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor } 134a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor } 135a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor }; 136a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 137a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor class VISIBILITY_HIDDEN ValueTable { 138a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor private: 139a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor DenseMap<Value*, uint32_t> valueNumbering; 140a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor DenseMap<Expression, uint32_t> expressionNumbering; 141a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor AliasAnalysis* AA; 142a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor MemoryDependenceAnalysis* MD; 143a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor DominatorTree* DT; 144a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 145a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor uint32_t nextValueNumber; 146a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 147a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 148677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor Expression::ExpressionOpcode getOpcode(CmpInst* C); 149a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor Expression::ExpressionOpcode getOpcode(CastInst* C); 15087f9d81d0ab806dcf6ca50a0c068dcb2ba7f51b3Argyrios Kyrtzidis Expression create_expression(BinaryOperator* BO); 15187f9d81d0ab806dcf6ca50a0c068dcb2ba7f51b3Argyrios Kyrtzidis Expression create_expression(CmpInst* C); 15287f9d81d0ab806dcf6ca50a0c068dcb2ba7f51b3Argyrios Kyrtzidis Expression create_expression(ShuffleVectorInst* V); 15387f9d81d0ab806dcf6ca50a0c068dcb2ba7f51b3Argyrios Kyrtzidis Expression create_expression(ExtractElementInst* C); 15487f9d81d0ab806dcf6ca50a0c068dcb2ba7f51b3Argyrios Kyrtzidis Expression create_expression(InsertElementInst* V); 155a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor Expression create_expression(SelectInst* V); 156a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor Expression create_expression(CastInst* C); 157a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor Expression create_expression(GetElementPtrInst* G); 158a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor Expression create_expression(CallInst* C); 159677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor Expression create_expression(Constant* C); 160a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor public: 161a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor ValueTable() : nextValueNumber(1) { } 162a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor uint32_t lookup_or_add(Value* V); 163677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor uint32_t lookup(Value* V) const; 164677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor void add(Value* V, uint32_t num); 165a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor void clear(); 166188bdcd1aaf5e9f457cec6851707d7dc3e7bbb15Douglas Gregor void erase(Value* v); 167677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor unsigned size(); 168188bdcd1aaf5e9f457cec6851707d7dc3e7bbb15Douglas Gregor void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 169894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor AliasAnalysis *getAliasAnalysis() const { return AA; } 170894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } 171a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor void setDomTree(DominatorTree* D) { DT = D; } 1721a49d97d762570027863e9209af81d445e4f1502Douglas Gregor uint32_t getNextUnusedValueNumber() { return nextValueNumber; } 173a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor }; 174894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor} 175894719bf99cf0131d954c714179bb47eee472b91Douglas Gregor 176a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregornamespace llvm { 177188bdcd1aaf5e9f457cec6851707d7dc3e7bbb15Douglas Gregortemplate <> struct DenseMapInfo<Expression> { 178188bdcd1aaf5e9f457cec6851707d7dc3e7bbb15Douglas Gregor static inline Expression getEmptyKey() { 1791a49d97d762570027863e9209af81d445e4f1502Douglas Gregor return Expression(Expression::EMPTY); 180fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor } 181fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor 182fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor static inline Expression getTombstoneKey() { 183fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor return Expression(Expression::TOMBSTONE); 184fa69fc19121da3fc5673ccc00d4e8afa5b540a4fDouglas Gregor } 185677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor 1861a49d97d762570027863e9209af81d445e4f1502Douglas Gregor static unsigned getHashValue(const Expression e) { 1871a49d97d762570027863e9209af81d445e4f1502Douglas Gregor unsigned hash = e.opcode; 188a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 1896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines hash = e.firstVN + hash * 37; 1906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines hash = e.secondVN + hash * 37; 1916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines hash = e.thirdVN + hash * 37; 192a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 193a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 194a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor (unsigned)((uintptr_t)e.type >> 9)) + 195a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor hash * 37; 196a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 197a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 198a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor E = e.varargs.end(); I != E; ++I) 199a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor hash = *I + hash * 37; 200a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor 201a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor hash = ((unsigned)((uintptr_t)e.function >> 4) ^ 202a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor (unsigned)((uintptr_t)e.function >> 9)) + 203a6b00fc97669aa25d89ae9f202b05dfadfd0e324Douglas Gregor hash * 37; 204 205 return hash; 206 } 207 static bool isEqual(const Expression &LHS, const Expression &RHS) { 208 return LHS == RHS; 209 } 210 static bool isPod() { return true; } 211}; 212} 213 214//===----------------------------------------------------------------------===// 215// ValueTable Internal Functions 216//===----------------------------------------------------------------------===// 217Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) { 218 switch(BO->getOpcode()) { 219 default: // THIS SHOULD NEVER HAPPEN 220 assert(0 && "Binary operator with unknown opcode?"); 221 case Instruction::Add: return Expression::ADD; 222 case Instruction::Sub: return Expression::SUB; 223 case Instruction::Mul: return Expression::MUL; 224 case Instruction::UDiv: return Expression::UDIV; 225 case Instruction::SDiv: return Expression::SDIV; 226 case Instruction::FDiv: return Expression::FDIV; 227 case Instruction::URem: return Expression::UREM; 228 case Instruction::SRem: return Expression::SREM; 229 case Instruction::FRem: return Expression::FREM; 230 case Instruction::Shl: return Expression::SHL; 231 case Instruction::LShr: return Expression::LSHR; 232 case Instruction::AShr: return Expression::ASHR; 233 case Instruction::And: return Expression::AND; 234 case Instruction::Or: return Expression::OR; 235 case Instruction::Xor: return Expression::XOR; 236 } 237} 238 239Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 240 if (isa<ICmpInst>(C) || isa<VICmpInst>(C)) { 241 switch (C->getPredicate()) { 242 default: // THIS SHOULD NEVER HAPPEN 243 assert(0 && "Comparison with unknown predicate?"); 244 case ICmpInst::ICMP_EQ: return Expression::ICMPEQ; 245 case ICmpInst::ICMP_NE: return Expression::ICMPNE; 246 case ICmpInst::ICMP_UGT: return Expression::ICMPUGT; 247 case ICmpInst::ICMP_UGE: return Expression::ICMPUGE; 248 case ICmpInst::ICMP_ULT: return Expression::ICMPULT; 249 case ICmpInst::ICMP_ULE: return Expression::ICMPULE; 250 case ICmpInst::ICMP_SGT: return Expression::ICMPSGT; 251 case ICmpInst::ICMP_SGE: return Expression::ICMPSGE; 252 case ICmpInst::ICMP_SLT: return Expression::ICMPSLT; 253 case ICmpInst::ICMP_SLE: return Expression::ICMPSLE; 254 } 255 } 256 assert((isa<FCmpInst>(C) || isa<VFCmpInst>(C)) && "Unknown compare"); 257 switch (C->getPredicate()) { 258 default: // THIS SHOULD NEVER HAPPEN 259 assert(0 && "Comparison with unknown predicate?"); 260 case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ; 261 case FCmpInst::FCMP_OGT: return Expression::FCMPOGT; 262 case FCmpInst::FCMP_OGE: return Expression::FCMPOGE; 263 case FCmpInst::FCMP_OLT: return Expression::FCMPOLT; 264 case FCmpInst::FCMP_OLE: return Expression::FCMPOLE; 265 case FCmpInst::FCMP_ONE: return Expression::FCMPONE; 266 case FCmpInst::FCMP_ORD: return Expression::FCMPORD; 267 case FCmpInst::FCMP_UNO: return Expression::FCMPUNO; 268 case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ; 269 case FCmpInst::FCMP_UGT: return Expression::FCMPUGT; 270 case FCmpInst::FCMP_UGE: return Expression::FCMPUGE; 271 case FCmpInst::FCMP_ULT: return Expression::FCMPULT; 272 case FCmpInst::FCMP_ULE: return Expression::FCMPULE; 273 case FCmpInst::FCMP_UNE: return Expression::FCMPUNE; 274 } 275} 276 277Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) { 278 switch(C->getOpcode()) { 279 default: // THIS SHOULD NEVER HAPPEN 280 assert(0 && "Cast operator with unknown opcode?"); 281 case Instruction::Trunc: return Expression::TRUNC; 282 case Instruction::ZExt: return Expression::ZEXT; 283 case Instruction::SExt: return Expression::SEXT; 284 case Instruction::FPToUI: return Expression::FPTOUI; 285 case Instruction::FPToSI: return Expression::FPTOSI; 286 case Instruction::UIToFP: return Expression::UITOFP; 287 case Instruction::SIToFP: return Expression::SITOFP; 288 case Instruction::FPTrunc: return Expression::FPTRUNC; 289 case Instruction::FPExt: return Expression::FPEXT; 290 case Instruction::PtrToInt: return Expression::PTRTOINT; 291 case Instruction::IntToPtr: return Expression::INTTOPTR; 292 case Instruction::BitCast: return Expression::BITCAST; 293 } 294} 295 296Expression ValueTable::create_expression(CallInst* C) { 297 Expression e; 298 299 e.type = C->getType(); 300 e.firstVN = 0; 301 e.secondVN = 0; 302 e.thirdVN = 0; 303 e.function = C->getCalledFunction(); 304 e.opcode = Expression::CALL; 305 306 for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 307 I != E; ++I) 308 e.varargs.push_back(lookup_or_add(*I)); 309 310 return e; 311} 312 313Expression ValueTable::create_expression(BinaryOperator* BO) { 314 Expression e; 315 316 e.firstVN = lookup_or_add(BO->getOperand(0)); 317 e.secondVN = lookup_or_add(BO->getOperand(1)); 318 e.thirdVN = 0; 319 e.function = 0; 320 e.type = BO->getType(); 321 e.opcode = getOpcode(BO); 322 323 return e; 324} 325 326Expression ValueTable::create_expression(CmpInst* C) { 327 Expression e; 328 329 e.firstVN = lookup_or_add(C->getOperand(0)); 330 e.secondVN = lookup_or_add(C->getOperand(1)); 331 e.thirdVN = 0; 332 e.function = 0; 333 e.type = C->getType(); 334 e.opcode = getOpcode(C); 335 336 return e; 337} 338 339Expression ValueTable::create_expression(CastInst* C) { 340 Expression e; 341 342 e.firstVN = lookup_or_add(C->getOperand(0)); 343 e.secondVN = 0; 344 e.thirdVN = 0; 345 e.function = 0; 346 e.type = C->getType(); 347 e.opcode = getOpcode(C); 348 349 return e; 350} 351 352Expression ValueTable::create_expression(ShuffleVectorInst* S) { 353 Expression e; 354 355 e.firstVN = lookup_or_add(S->getOperand(0)); 356 e.secondVN = lookup_or_add(S->getOperand(1)); 357 e.thirdVN = lookup_or_add(S->getOperand(2)); 358 e.function = 0; 359 e.type = S->getType(); 360 e.opcode = Expression::SHUFFLE; 361 362 return e; 363} 364 365Expression ValueTable::create_expression(ExtractElementInst* E) { 366 Expression e; 367 368 e.firstVN = lookup_or_add(E->getOperand(0)); 369 e.secondVN = lookup_or_add(E->getOperand(1)); 370 e.thirdVN = 0; 371 e.function = 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.function = 0; 385 e.type = I->getType(); 386 e.opcode = Expression::INSERT; 387 388 return e; 389} 390 391Expression ValueTable::create_expression(SelectInst* I) { 392 Expression e; 393 394 e.firstVN = lookup_or_add(I->getCondition()); 395 e.secondVN = lookup_or_add(I->getTrueValue()); 396 e.thirdVN = lookup_or_add(I->getFalseValue()); 397 e.function = 0; 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.function = 0; 411 e.type = G->getType(); 412 e.opcode = Expression::GEP; 413 414 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 415 I != E; ++I) 416 e.varargs.push_back(lookup_or_add(*I)); 417 418 return e; 419} 420 421//===----------------------------------------------------------------------===// 422// ValueTable External Functions 423//===----------------------------------------------------------------------===// 424 425/// add - Insert a value into the table with a specified value number. 426void ValueTable::add(Value* V, uint32_t num) { 427 valueNumbering.insert(std::make_pair(V, num)); 428} 429 430/// lookup_or_add - Returns the value number for the specified value, assigning 431/// it a new number if it did not have one before. 432uint32_t ValueTable::lookup_or_add(Value* V) { 433 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 434 if (VI != valueNumbering.end()) 435 return VI->second; 436 437 if (CallInst* C = dyn_cast<CallInst>(V)) { 438 if (AA->doesNotAccessMemory(C)) { 439 Expression e = create_expression(C); 440 441 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 442 if (EI != expressionNumbering.end()) { 443 valueNumbering.insert(std::make_pair(V, EI->second)); 444 return EI->second; 445 } else { 446 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 447 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 448 449 return nextValueNumber++; 450 } 451 } else if (AA->onlyReadsMemory(C)) { 452 Expression e = create_expression(C); 453 454 if (expressionNumbering.find(e) == expressionNumbering.end()) { 455 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 456 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 457 return nextValueNumber++; 458 } 459 460 MemDepResult local_dep = MD->getDependency(C); 461 462 if (local_dep.isNone()) { 463 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 464 return nextValueNumber++; 465 } 466 467 if (Instruction *LocalDepInst = local_dep.getInst()) { 468 if (!isa<CallInst>(LocalDepInst)) { 469 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 470 return nextValueNumber++; 471 } 472 473 CallInst* local_cdep = cast<CallInst>(LocalDepInst); 474 475 if (local_cdep->getCalledFunction() != C->getCalledFunction() || 476 local_cdep->getNumOperands() != C->getNumOperands()) { 477 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 478 return nextValueNumber++; 479 } 480 481 if (!C->getCalledFunction()) { 482 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 483 return nextValueNumber++; 484 } 485 486 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 487 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 488 uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); 489 if (c_vn != cd_vn) { 490 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 491 return nextValueNumber++; 492 } 493 } 494 495 uint32_t v = lookup_or_add(local_cdep); 496 valueNumbering.insert(std::make_pair(V, v)); 497 return v; 498 } 499 500 501 SmallVector<std::pair<BasicBlock*, MemDepResult>, 32> deps; 502 MD->getNonLocalDependency(C, deps); 503 CallInst* cdep = 0; 504 505 // Check to see if we have a single dominating call instruction that is 506 // identical to C. 507 for (SmallVector<std::pair<BasicBlock*, MemDepResult>, 32> 508 ::iterator I = deps.begin(), E = deps.end(); I != E; ++I) { 509 // Ignore non-local dependencies. 510 if (I->second.isNonLocal()) 511 continue; 512 513 // We don't handle non-depedencies. If we already have a call, reject 514 // instruction dependencies. 515 if (I->second.isNone() || cdep != 0) { 516 cdep = 0; 517 break; 518 } 519 520 CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->second.getInst()); 521 // FIXME: All duplicated with non-local case. 522 if (NonLocalDepCall && DT->properlyDominates(I->first, C->getParent())){ 523 cdep = NonLocalDepCall; 524 continue; 525 } 526 527 cdep = 0; 528 break; 529 } 530 531 if (!cdep) { 532 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 533 return nextValueNumber++; 534 } 535 536 if (cdep->getCalledFunction() != C->getCalledFunction() || 537 cdep->getNumOperands() != C->getNumOperands()) { 538 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 539 return nextValueNumber++; 540 } 541 if (!C->getCalledFunction()) { 542 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 543 return nextValueNumber++; 544 } 545 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 546 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 547 uint32_t cd_vn = lookup_or_add(cdep->getOperand(i)); 548 if (c_vn != cd_vn) { 549 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 550 return nextValueNumber++; 551 } 552 } 553 554 uint32_t v = lookup_or_add(cdep); 555 valueNumbering.insert(std::make_pair(V, v)); 556 return v; 557 558 } else { 559 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 560 return nextValueNumber++; 561 } 562 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 563 Expression e = create_expression(BO); 564 565 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 566 if (EI != expressionNumbering.end()) { 567 valueNumbering.insert(std::make_pair(V, EI->second)); 568 return EI->second; 569 } else { 570 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 571 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 572 573 return nextValueNumber++; 574 } 575 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 576 Expression e = create_expression(C); 577 578 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 579 if (EI != expressionNumbering.end()) { 580 valueNumbering.insert(std::make_pair(V, EI->second)); 581 return EI->second; 582 } else { 583 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 584 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 585 586 return nextValueNumber++; 587 } 588 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 589 Expression e = create_expression(U); 590 591 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 592 if (EI != expressionNumbering.end()) { 593 valueNumbering.insert(std::make_pair(V, EI->second)); 594 return EI->second; 595 } else { 596 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 597 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 598 599 return nextValueNumber++; 600 } 601 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 602 Expression e = create_expression(U); 603 604 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 605 if (EI != expressionNumbering.end()) { 606 valueNumbering.insert(std::make_pair(V, EI->second)); 607 return EI->second; 608 } else { 609 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 610 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 611 612 return nextValueNumber++; 613 } 614 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 615 Expression e = create_expression(U); 616 617 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 618 if (EI != expressionNumbering.end()) { 619 valueNumbering.insert(std::make_pair(V, EI->second)); 620 return EI->second; 621 } else { 622 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 623 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 624 625 return nextValueNumber++; 626 } 627 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 628 Expression e = create_expression(U); 629 630 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 631 if (EI != expressionNumbering.end()) { 632 valueNumbering.insert(std::make_pair(V, EI->second)); 633 return EI->second; 634 } else { 635 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 636 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 637 638 return nextValueNumber++; 639 } 640 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 641 Expression e = create_expression(U); 642 643 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 644 if (EI != expressionNumbering.end()) { 645 valueNumbering.insert(std::make_pair(V, EI->second)); 646 return EI->second; 647 } else { 648 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 649 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 650 651 return nextValueNumber++; 652 } 653 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 654 Expression e = create_expression(U); 655 656 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 657 if (EI != expressionNumbering.end()) { 658 valueNumbering.insert(std::make_pair(V, EI->second)); 659 return EI->second; 660 } else { 661 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 662 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 663 664 return nextValueNumber++; 665 } 666 } else { 667 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 668 return nextValueNumber++; 669 } 670} 671 672/// lookup - Returns the value number of the specified value. Fails if 673/// the value has not yet been numbered. 674uint32_t ValueTable::lookup(Value* V) const { 675 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 676 assert(VI != valueNumbering.end() && "Value not numbered?"); 677 return VI->second; 678} 679 680/// clear - Remove all entries from the ValueTable 681void ValueTable::clear() { 682 valueNumbering.clear(); 683 expressionNumbering.clear(); 684 nextValueNumber = 1; 685} 686 687/// erase - Remove a value from the value numbering 688void ValueTable::erase(Value* V) { 689 valueNumbering.erase(V); 690} 691 692//===----------------------------------------------------------------------===// 693// GVN Pass 694//===----------------------------------------------------------------------===// 695 696namespace { 697 struct VISIBILITY_HIDDEN ValueNumberScope { 698 ValueNumberScope* parent; 699 DenseMap<uint32_t, Value*> table; 700 701 ValueNumberScope(ValueNumberScope* p) : parent(p) { } 702 }; 703} 704 705namespace { 706 707 class VISIBILITY_HIDDEN GVN : public FunctionPass { 708 bool runOnFunction(Function &F); 709 public: 710 static char ID; // Pass identification, replacement for typeid 711 GVN() : FunctionPass(&ID) { } 712 713 private: 714 MemoryDependenceAnalysis *MD; 715 DominatorTree *DT; 716 717 ValueTable VN; 718 DenseMap<BasicBlock*, ValueNumberScope*> localAvail; 719 720 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 721 PhiMapType phiMap; 722 723 724 // This transformation requires dominator postdominator info 725 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 726 AU.addRequired<DominatorTree>(); 727 AU.addRequired<MemoryDependenceAnalysis>(); 728 AU.addRequired<AliasAnalysis>(); 729 730 AU.addPreserved<DominatorTree>(); 731 AU.addPreserved<AliasAnalysis>(); 732 } 733 734 // Helper fuctions 735 // FIXME: eliminate or document these better 736 bool processLoad(LoadInst* L, 737 DenseMap<Value*, LoadInst*> &lastLoad, 738 SmallVectorImpl<Instruction*> &toErase); 739 bool processInstruction(Instruction* I, 740 DenseMap<Value*, LoadInst*>& lastSeenLoad, 741 SmallVectorImpl<Instruction*> &toErase); 742 bool processNonLocalLoad(LoadInst* L, 743 SmallVectorImpl<Instruction*> &toErase); 744 bool processBlock(DomTreeNode* DTN); 745 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 746 DenseMap<BasicBlock*, Value*> &Phis, 747 bool top_level = false); 748 void dump(DenseMap<uint32_t, Value*>& d); 749 bool iterateOnFunction(Function &F); 750 Value* CollapsePhi(PHINode* p); 751 bool isSafeReplacement(PHINode* p, Instruction* inst); 752 bool performPRE(Function& F); 753 Value* lookupNumber(BasicBlock* BB, uint32_t num); 754 bool mergeBlockIntoPredecessor(BasicBlock* BB); 755 void cleanupGlobalSets(); 756 }; 757 758 char GVN::ID = 0; 759} 760 761// createGVNPass - The public interface to this file... 762FunctionPass *llvm::createGVNPass() { return new GVN(); } 763 764static RegisterPass<GVN> X("gvn", 765 "Global Value Numbering"); 766 767void GVN::dump(DenseMap<uint32_t, Value*>& d) { 768 printf("{\n"); 769 for (DenseMap<uint32_t, Value*>::iterator I = d.begin(), 770 E = d.end(); I != E; ++I) { 771 printf("%d\n", I->first); 772 I->second->dump(); 773 } 774 printf("}\n"); 775} 776 777Value* GVN::CollapsePhi(PHINode* p) { 778 Value* constVal = p->hasConstantValue(); 779 if (!constVal) return 0; 780 781 Instruction* inst = dyn_cast<Instruction>(constVal); 782 if (!inst) 783 return constVal; 784 785 if (DT->dominates(inst, p)) 786 if (isSafeReplacement(p, inst)) 787 return inst; 788 return 0; 789} 790 791bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 792 if (!isa<PHINode>(inst)) 793 return true; 794 795 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 796 UI != E; ++UI) 797 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 798 if (use_phi->getParent() == inst->getParent()) 799 return false; 800 801 return true; 802} 803 804/// GetValueForBlock - Get the value to use within the specified basic block. 805/// available values are in Phis. 806Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 807 DenseMap<BasicBlock*, Value*> &Phis, 808 bool top_level) { 809 810 // If we have already computed this value, return the previously computed val. 811 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 812 if (V != Phis.end() && !top_level) return V->second; 813 814 // If the block is unreachable, just return undef, since this path 815 // can't actually occur at runtime. 816 if (!DT->isReachableFromEntry(BB)) 817 return Phis[BB] = UndefValue::get(orig->getType()); 818 819 BasicBlock* singlePred = BB->getSinglePredecessor(); 820 if (singlePred) { 821 Value *ret = GetValueForBlock(singlePred, orig, Phis); 822 Phis[BB] = ret; 823 return ret; 824 } 825 826 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 827 // now, then get values to fill in the incoming values for the PHI. 828 PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle", 829 BB->begin()); 830 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 831 832 if (Phis.count(BB) == 0) 833 Phis.insert(std::make_pair(BB, PN)); 834 835 // Fill in the incoming values for the block. 836 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 837 Value* val = GetValueForBlock(*PI, orig, Phis); 838 PN->addIncoming(val, *PI); 839 } 840 841 VN.getAliasAnalysis()->copyValue(orig, PN); 842 843 // Attempt to collapse PHI nodes that are trivially redundant 844 Value* v = CollapsePhi(PN); 845 if (!v) { 846 // Cache our phi construction results 847 phiMap[orig->getPointerOperand()].insert(PN); 848 return PN; 849 } 850 851 PN->replaceAllUsesWith(v); 852 853 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 854 E = Phis.end(); I != E; ++I) 855 if (I->second == PN) 856 I->second = v; 857 858 DEBUG(cerr << "GVN removed: " << *PN); 859 MD->removeInstruction(PN); 860 PN->eraseFromParent(); 861 862 Phis[BB] = v; 863 return v; 864} 865 866/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 867/// non-local by performing PHI construction. 868bool GVN::processNonLocalLoad(LoadInst* L, 869 SmallVectorImpl<Instruction*> &toErase) { 870 // Find the non-local dependencies of the load 871 SmallVector<std::pair<BasicBlock*, MemDepResult>, 32> deps; 872 MD->getNonLocalDependency(L, deps); 873 874 DEBUG(cerr << "INVESTIGATING NONLOCAL LOAD: " << deps.size() << *L); 875 876 877 // If we had to process more than one hundred blocks to find the 878 // dependencies, this load isn't worth worrying about. Optimizing 879 // it will be too expensive. 880 if (deps.size() > 100) 881 return false; 882 883 BasicBlock *EntryBlock = &L->getParent()->getParent()->getEntryBlock(); 884 885 DenseMap<BasicBlock*, Value*> repl; 886 887 // Filter out useless results (non-locals, etc) 888 for (SmallVector<std::pair<BasicBlock*, MemDepResult>, 32>::iterator 889 I = deps.begin(), E = deps.end(); I != E; ++I) { 890 if (I->second.isNone()) { 891 repl[I->first] = UndefValue::get(L->getType()); 892 continue; 893 } 894 895 if (I->second.isNonLocal()) { 896 // If this is a non-local dependency in the entry block, then we depend on 897 // the value live-in at the start of the function. We could insert a load 898 // in the entry block to get this, but for now we'll just bail out. 899 // FIXME: Consider emitting a load in the entry block to catch this case! 900 if (I->first == EntryBlock) 901 return false; 902 continue; 903 } 904 905 if (StoreInst* S = dyn_cast<StoreInst>(I->second.getInst())) { 906 if (S->getPointerOperand() != L->getPointerOperand()) 907 return false; 908 repl[I->first] = S->getOperand(0); 909 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second.getInst())) { 910 if (LD->getPointerOperand() != L->getPointerOperand()) 911 return false; 912 repl[I->first] = LD; 913 } else { 914 return false; 915 } 916 } 917 918 // Use cached PHI construction information from previous runs 919 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 920 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 921 I != E; ++I) { 922 if ((*I)->getParent() == L->getParent()) { 923 L->replaceAllUsesWith(*I); 924 toErase.push_back(L); 925 NumGVNLoad++; 926 return true; 927 } 928 929 repl.insert(std::make_pair((*I)->getParent(), *I)); 930 } 931 932 DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD: " << *L); 933 934 // Perform PHI construction 935 SmallPtrSet<BasicBlock*, 4> visited; 936 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 937 L->replaceAllUsesWith(v); 938 toErase.push_back(L); 939 NumGVNLoad++; 940 return true; 941} 942 943/// processLoad - Attempt to eliminate a load, first by eliminating it 944/// locally, and then attempting non-local elimination if that fails. 945bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad, 946 SmallVectorImpl<Instruction*> &toErase) { 947 if (L->isVolatile()) { 948 lastLoad[L->getPointerOperand()] = L; 949 return false; 950 } 951 952 Value* pointer = L->getPointerOperand(); 953 LoadInst*& last = lastLoad[pointer]; 954 955 // ... to a pointer that has been loaded from before... 956 bool removedNonLocal = false; 957 MemDepResult dep = MD->getDependency(L); 958 if (dep.isNonLocal() && 959 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 960 removedNonLocal = processNonLocalLoad(L, toErase); 961 962 if (!removedNonLocal) 963 last = L; 964 965 return removedNonLocal; 966 } 967 968 969 bool deletedLoad = false; 970 971 // Walk up the dependency chain until we either find 972 // a dependency we can use, or we can't walk any further 973 while (Instruction *DepInst = dep.getInst()) { 974 // ... that depends on a store ... 975 if (StoreInst* S = dyn_cast<StoreInst>(DepInst)) { 976 if (S->getPointerOperand() == pointer) { 977 // Remove it! 978 L->replaceAllUsesWith(S->getOperand(0)); 979 toErase.push_back(L); 980 deletedLoad = true; 981 NumGVNLoad++; 982 } 983 984 // Whether we removed it or not, we can't 985 // go any further 986 break; 987 } else if (!isa<LoadInst>(DepInst)) { 988 // Only want to handle loads below. 989 break; 990 } else if (!last) { 991 // If we don't depend on a store, and we haven't 992 // been loaded before, bail. 993 break; 994 } else if (DepInst == last) { 995 // Remove it! 996 L->replaceAllUsesWith(last); 997 toErase.push_back(L); 998 deletedLoad = true; 999 NumGVNLoad++; 1000 break; 1001 } else { 1002 dep = MD->getDependencyFrom(L, DepInst, DepInst->getParent()); 1003 } 1004 } 1005 1006 // If this load really doesn't depend on anything, then we must be loading an 1007 // undef value. This can happen when loading for a fresh allocation with no 1008 // intervening stores, for example. 1009 if (dep.isNone()) { 1010 // If this load depends directly on an allocation, there isn't 1011 // anything stored there; therefore, we can optimize this load 1012 // to undef. 1013 L->replaceAllUsesWith(UndefValue::get(L->getType())); 1014 toErase.push_back(L); 1015 deletedLoad = true; 1016 NumGVNLoad++; 1017 } 1018 1019 if (!deletedLoad) 1020 last = L; 1021 1022 return deletedLoad; 1023} 1024 1025Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { 1026 DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB); 1027 if (I == localAvail.end()) 1028 return 0; 1029 1030 ValueNumberScope* locals = I->second; 1031 1032 while (locals) { 1033 DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num); 1034 if (I != locals->table.end()) 1035 return I->second; 1036 else 1037 locals = locals->parent; 1038 } 1039 1040 return 0; 1041} 1042 1043/// processInstruction - When calculating availability, handle an instruction 1044/// by inserting it into the appropriate sets 1045bool GVN::processInstruction(Instruction *I, 1046 DenseMap<Value*, LoadInst*> &lastSeenLoad, 1047 SmallVectorImpl<Instruction*> &toErase) { 1048 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1049 bool changed = processLoad(L, lastSeenLoad, toErase); 1050 1051 if (!changed) { 1052 unsigned num = VN.lookup_or_add(L); 1053 localAvail[I->getParent()]->table.insert(std::make_pair(num, L)); 1054 } 1055 1056 return changed; 1057 } 1058 1059 uint32_t nextNum = VN.getNextUnusedValueNumber(); 1060 unsigned num = VN.lookup_or_add(I); 1061 1062 // Allocations are always uniquely numbered, so we can save time and memory 1063 // by fast failing them. 1064 if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) { 1065 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1066 return false; 1067 } 1068 1069 // Collapse PHI nodes 1070 if (PHINode* p = dyn_cast<PHINode>(I)) { 1071 Value* constVal = CollapsePhi(p); 1072 1073 if (constVal) { 1074 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1075 PI != PE; ++PI) 1076 if (PI->second.count(p)) 1077 PI->second.erase(p); 1078 1079 p->replaceAllUsesWith(constVal); 1080 toErase.push_back(p); 1081 } else { 1082 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1083 } 1084 1085 // If the number we were assigned was a brand new VN, then we don't 1086 // need to do a lookup to see if the number already exists 1087 // somewhere in the domtree: it can't! 1088 } else if (num == nextNum) { 1089 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1090 1091 // Perform value-number based elimination 1092 } else if (Value* repl = lookupNumber(I->getParent(), num)) { 1093 // Remove it! 1094 VN.erase(I); 1095 I->replaceAllUsesWith(repl); 1096 toErase.push_back(I); 1097 return true; 1098 } else { 1099 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1100 } 1101 1102 return false; 1103} 1104 1105// GVN::runOnFunction - This is the main transformation entry point for a 1106// function. 1107// 1108bool GVN::runOnFunction(Function& F) { 1109 MD = &getAnalysis<MemoryDependenceAnalysis>(); 1110 DT = &getAnalysis<DominatorTree>(); 1111 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1112 VN.setMemDep(MD); 1113 VN.setDomTree(DT); 1114 1115 bool changed = false; 1116 bool shouldContinue = true; 1117 1118 // Merge unconditional branches, allowing PRE to catch more 1119 // optimization opportunities. 1120 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { 1121 BasicBlock* BB = FI; 1122 ++FI; 1123 bool removedBlock = MergeBlockIntoPredecessor(BB, this); 1124 if (removedBlock) NumGVNBlocks++; 1125 1126 changed |= removedBlock; 1127 } 1128 1129 while (shouldContinue) { 1130 shouldContinue = iterateOnFunction(F); 1131 changed |= shouldContinue; 1132 } 1133 1134 if (EnablePRE) { 1135 bool PREChanged = true; 1136 while (PREChanged) { 1137 PREChanged = performPRE(F); 1138 changed |= PREChanged; 1139 } 1140 } 1141 1142 cleanupGlobalSets(); 1143 1144 return changed; 1145} 1146 1147 1148bool GVN::processBlock(DomTreeNode* DTN) { 1149 BasicBlock* BB = DTN->getBlock(); 1150 SmallVector<Instruction*, 8> toErase; 1151 DenseMap<Value*, LoadInst*> lastSeenLoad; 1152 bool changed_function = false; 1153 1154 if (DTN->getIDom()) 1155 localAvail[BB] = 1156 new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]); 1157 else 1158 localAvail[BB] = new ValueNumberScope(0); 1159 1160 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1161 BI != BE;) { 1162 changed_function |= processInstruction(BI, lastSeenLoad, toErase); 1163 if (toErase.empty()) { 1164 ++BI; 1165 continue; 1166 } 1167 1168 // If we need some instructions deleted, do it now. 1169 NumGVNInstr += toErase.size(); 1170 1171 // Avoid iterator invalidation. 1172 bool AtStart = BI == BB->begin(); 1173 if (!AtStart) 1174 --BI; 1175 1176 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1177 E = toErase.end(); I != E; ++I) { 1178 DEBUG(cerr << "GVN removed: " << **I); 1179 MD->removeInstruction(*I); 1180 (*I)->eraseFromParent(); 1181 } 1182 1183 if (AtStart) 1184 BI = BB->begin(); 1185 else 1186 ++BI; 1187 1188 toErase.clear(); 1189 } 1190 1191 return changed_function; 1192} 1193 1194/// performPRE - Perform a purely local form of PRE that looks for diamond 1195/// control flow patterns and attempts to perform simple PRE at the join point. 1196bool GVN::performPRE(Function& F) { 1197 bool changed = false; 1198 SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit; 1199 for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()), 1200 DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { 1201 BasicBlock* CurrentBlock = *DI; 1202 1203 // Nothing to PRE in the entry block. 1204 if (CurrentBlock == &F.getEntryBlock()) continue; 1205 1206 for (BasicBlock::iterator BI = CurrentBlock->begin(), 1207 BE = CurrentBlock->end(); BI != BE; ) { 1208 if (isa<AllocationInst>(BI) || isa<TerminatorInst>(BI) || 1209 isa<PHINode>(BI) || BI->mayReadFromMemory() || 1210 BI->mayWriteToMemory()) { 1211 BI++; 1212 continue; 1213 } 1214 1215 uint32_t valno = VN.lookup(BI); 1216 1217 // Look for the predecessors for PRE opportunities. We're 1218 // only trying to solve the basic diamond case, where 1219 // a value is computed in the successor and one predecessor, 1220 // but not the other. We also explicitly disallow cases 1221 // where the successor is its own predecessor, because they're 1222 // more complicated to get right. 1223 unsigned numWith = 0; 1224 unsigned numWithout = 0; 1225 BasicBlock* PREPred = 0; 1226 DenseMap<BasicBlock*, Value*> predMap; 1227 for (pred_iterator PI = pred_begin(CurrentBlock), 1228 PE = pred_end(CurrentBlock); PI != PE; ++PI) { 1229 // We're not interested in PRE where the block is its 1230 // own predecessor, on in blocks with predecessors 1231 // that are not reachable. 1232 if (*PI == CurrentBlock) { 1233 numWithout = 2; 1234 break; 1235 } else if (!localAvail.count(*PI)) { 1236 numWithout = 2; 1237 break; 1238 } 1239 1240 DenseMap<uint32_t, Value*>::iterator predV = 1241 localAvail[*PI]->table.find(valno); 1242 if (predV == localAvail[*PI]->table.end()) { 1243 PREPred = *PI; 1244 numWithout++; 1245 } else if (predV->second == BI) { 1246 numWithout = 2; 1247 } else { 1248 predMap[*PI] = predV->second; 1249 numWith++; 1250 } 1251 } 1252 1253 // Don't do PRE when it might increase code size, i.e. when 1254 // we would need to insert instructions in more than one pred. 1255 if (numWithout != 1 || numWith == 0) { 1256 BI++; 1257 continue; 1258 } 1259 1260 // We can't do PRE safely on a critical edge, so instead we schedule 1261 // the edge to be split and perform the PRE the next time we iterate 1262 // on the function. 1263 unsigned succNum = 0; 1264 for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors(); 1265 i != e; ++i) 1266 if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) { 1267 succNum = i; 1268 break; 1269 } 1270 1271 if (isCriticalEdge(PREPred->getTerminator(), succNum)) { 1272 toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum)); 1273 changed = true; 1274 BI++; 1275 continue; 1276 } 1277 1278 // Instantiate the expression the in predecessor that lacked it. 1279 // Because we are going top-down through the block, all value numbers 1280 // will be available in the predecessor by the time we need them. Any 1281 // that weren't original present will have been instantiated earlier 1282 // in this loop. 1283 Instruction* PREInstr = BI->clone(); 1284 bool success = true; 1285 for (unsigned i = 0; i < BI->getNumOperands(); ++i) { 1286 Value* op = BI->getOperand(i); 1287 if (isa<Argument>(op) || isa<Constant>(op) || isa<GlobalValue>(op)) 1288 PREInstr->setOperand(i, op); 1289 else { 1290 Value* V = lookupNumber(PREPred, VN.lookup(op)); 1291 if (!V) { 1292 success = false; 1293 break; 1294 } else 1295 PREInstr->setOperand(i, V); 1296 } 1297 } 1298 1299 // Fail out if we encounter an operand that is not available in 1300 // the PRE predecessor. This is typically because of loads which 1301 // are not value numbered precisely. 1302 if (!success) { 1303 delete PREInstr; 1304 BI++; 1305 continue; 1306 } 1307 1308 PREInstr->insertBefore(PREPred->getTerminator()); 1309 PREInstr->setName(BI->getName() + ".pre"); 1310 predMap[PREPred] = PREInstr; 1311 VN.add(PREInstr, valno); 1312 NumGVNPRE++; 1313 1314 // Update the availability map to include the new instruction. 1315 localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr)); 1316 1317 // Create a PHI to make the value available in this block. 1318 PHINode* Phi = PHINode::Create(BI->getType(), 1319 BI->getName() + ".pre-phi", 1320 CurrentBlock->begin()); 1321 for (pred_iterator PI = pred_begin(CurrentBlock), 1322 PE = pred_end(CurrentBlock); PI != PE; ++PI) 1323 Phi->addIncoming(predMap[*PI], *PI); 1324 1325 VN.add(Phi, valno); 1326 localAvail[CurrentBlock]->table[valno] = Phi; 1327 1328 BI->replaceAllUsesWith(Phi); 1329 VN.erase(BI); 1330 1331 Instruction* erase = BI; 1332 BI++; 1333 DEBUG(cerr << "GVN removed: " << *erase); 1334 MD->removeInstruction(erase); 1335 erase->eraseFromParent(); 1336 changed = true; 1337 } 1338 } 1339 1340 for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator 1341 I = toSplit.begin(), E = toSplit.end(); I != E; ++I) 1342 SplitCriticalEdge(I->first, I->second, this); 1343 1344 return changed || toSplit.size(); 1345} 1346 1347// iterateOnFunction - Executes one iteration of GVN 1348bool GVN::iterateOnFunction(Function &F) { 1349 cleanupGlobalSets(); 1350 1351 // Top-down walk of the dominator tree 1352 bool changed = false; 1353 for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()), 1354 DE = df_end(DT->getRootNode()); DI != DE; ++DI) 1355 changed |= processBlock(*DI); 1356 1357 return changed; 1358} 1359 1360void GVN::cleanupGlobalSets() { 1361 VN.clear(); 1362 phiMap.clear(); 1363 1364 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator 1365 I = localAvail.begin(), E = localAvail.end(); I != E; ++I) 1366 delete I->second; 1367 localAvail.clear(); 1368} 1369