GVN.cpp revision f41fcbb60d909ebae0e31300322b94922c1ee886
10d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===- GVN.cpp - Eliminate redundant values and loads ---------------------===// 20d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// 30d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// The LLVM Compiler Infrastructure 40d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// 50d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// This file is distributed under the University of Illinois Open Source 60d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// License. See LICENSE.TXT for details. 70d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// 80d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 90d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// 100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// This pass performs global value numbering to eliminate fully redundant 110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// instructions. It also performs simple dead load elimination. 120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// 130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// Note that this pass does the value numbering itself; it does not use the 140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// ValueNumbering analysis passes. 150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// 160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#define DEBUG_TYPE "gvn" 190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Transforms/Scalar.h" 200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/BasicBlock.h" 210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Constants.h" 220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/DerivedTypes.h" 230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Function.h" 240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/IntrinsicInst.h" 250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Value.h" 260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/ADT/DenseMap.h" 270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/ADT/DepthFirstIterator.h" 280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/ADT/PostOrderIterator.h" 290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/ADT/SmallPtrSet.h" 300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/ADT/SmallVector.h" 310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/ADT/Statistic.h" 320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Analysis/Dominators.h" 330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Analysis/AliasAnalysis.h" 340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Analysis/MemoryDependenceAnalysis.h" 350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Support/CFG.h" 360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Support/CommandLine.h" 370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Support/Compiler.h" 380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Support/Debug.h" 390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include "llvm/Transforms/Utils/BasicBlockUtils.h" 400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#include <cstdio> 410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarusing namespace llvm; 420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarSTATISTIC(NumGVNInstr, "Number of instructions deleted"); 440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarSTATISTIC(NumGVNLoad, "Number of loads deleted"); 450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarSTATISTIC(NumGVNPRE, "Number of instructions PRE'd"); 460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarSTATISTIC(NumGVNBlocks, "Number of blocks merged"); 470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarSTATISTIC(NumPRELoad, "Number of loads PRE'd"); 480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarstatic cl::opt<bool> EnablePRE("enable-pre", 500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar cl::init(true), cl::Hidden); 510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarcl::opt<bool> EnableLoadPRE("enable-load-pre"/*, cl::init(true)*/); 520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// ValueTable Class 550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// This class holds the mapping between values and value numbers. It is used 580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// as an efficient mechanism to determine the expression-wise equivalence of 590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// two values. 600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarnamespace { 610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar struct VISIBILITY_HIDDEN Expression { 620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT, 720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar EMPTY, TOMBSTONE }; 730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ExpressionOpcode opcode; 750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar const Type* type; 760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t firstVN; 770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t secondVN; 780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t thirdVN; 790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVector<uint32_t, 4> varargs; 800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* function; 810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression() { } 830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression(ExpressionOpcode o) : opcode(o) { } 840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool operator==(const Expression &other) const { 860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (opcode != other.opcode) 870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else if (opcode == EMPTY || opcode == TOMBSTONE) 890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else if (type != other.type) 910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else if (function != other.function) 930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else if (firstVN != other.firstVN) 950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else if (secondVN != other.secondVN) 970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else if (thirdVN != other.thirdVN) 990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 1000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else { 1010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (varargs.size() != other.varargs.size()) 1020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 1030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (size_t i = 0; i < varargs.size(); ++i) 1050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (varargs[i] != other.varargs[i]) 1060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 1070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 1090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 1100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 1110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool operator!=(const Expression &other) const { 1130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return !(*this == other); 1140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 1150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar }; 1160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar class VISIBILITY_HIDDEN ValueTable { 1180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar private: 1190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Value*, uint32_t> valueNumbering; 1200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t> expressionNumbering; 1210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar AliasAnalysis* AA; 1220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MemoryDependenceAnalysis* MD; 1230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DominatorTree* DT; 1240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t true_vn, false_vn; 1250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t nextValueNumber; 1270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 1290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression::ExpressionOpcode getOpcode(CmpInst* C); 1300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression::ExpressionOpcode getOpcode(CastInst* C); 1310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(BinaryOperator* BO); 1320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(CmpInst* C); 1330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(ShuffleVectorInst* V); 1340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(ExtractElementInst* C); 1350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(InsertElementInst* V); 1360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(SelectInst* V); 1370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(CastInst* C); 1380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(GetElementPtrInst* G); 1390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(CallInst* C); 1400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression create_expression(Constant* C); 1410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar public: 1420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ValueTable() : nextValueNumber(1) { 1430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar true_vn = lookup_or_add(ConstantInt::getTrue()); 1440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar false_vn = lookup_or_add(ConstantInt::getFalse()); 1450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 1460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t getTrueVN() { return true_vn; } 1480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t getFalseVN() { return false_vn; } 1490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t lookup_or_add(Value* V); 1510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t lookup(Value* V) const; 1520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void add(Value* V, uint32_t num); 1530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void clear(); 1540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void erase(Value* v); 1550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar unsigned size(); 1560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 1570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar AliasAnalysis *getAliasAnalysis() const { return AA; } 1580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } 1590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void setDomTree(DominatorTree* D) { DT = D; } 1600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t getNextUnusedValueNumber() { return nextValueNumber; } 1610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void verifyRemoved(const Value *) const; 1620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar }; 1630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 1640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarnamespace llvm { 1660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakartemplate <> struct DenseMapInfo<Expression> { 1670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar static inline Expression getEmptyKey() { 1680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return Expression(Expression::EMPTY); 1690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 1700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar static inline Expression getTombstoneKey() { 1720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return Expression(Expression::TOMBSTONE); 1730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 1740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar static unsigned getHashValue(const Expression e) { 1760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar unsigned hash = e.opcode; 1770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar hash = e.firstVN + hash * 37; 1790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar hash = e.secondVN + hash * 37; 1800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar hash = e.thirdVN + hash * 37; 1810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 1830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar (unsigned)((uintptr_t)e.type >> 9)) + 1840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar hash * 37; 1850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 1870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar E = e.varargs.end(); I != E; ++I) 1880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar hash = *I + hash * 37; 1890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar hash = ((unsigned)((uintptr_t)e.function >> 4) ^ 1910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar (unsigned)((uintptr_t)e.function >> 9)) + 1920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar hash * 37; 1930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 1940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return hash; 1950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 1960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar static bool isEqual(const Expression &LHS, const Expression &RHS) { 1970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return LHS == RHS; 1980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 1990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar static bool isPod() { return true; } 2000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar}; 2010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 2020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 2030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 2040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// ValueTable Internal Functions 2050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 2060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) { 2070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar switch(BO->getOpcode()) { 2080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar default: // THIS SHOULD NEVER HAPPEN 2090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar assert(0 && "Binary operator with unknown opcode?"); 2100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::Add: return Expression::ADD; 2110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::Sub: return Expression::SUB; 2120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::Mul: return Expression::MUL; 2130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::UDiv: return Expression::UDIV; 2140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::SDiv: return Expression::SDIV; 2150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::FDiv: return Expression::FDIV; 2160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::URem: return Expression::UREM; 2170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::SRem: return Expression::SREM; 2180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::FRem: return Expression::FREM; 2190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::Shl: return Expression::SHL; 2200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::LShr: return Expression::LSHR; 2210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::AShr: return Expression::ASHR; 2220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::And: return Expression::AND; 2230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::Or: return Expression::OR; 2240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::Xor: return Expression::XOR; 2250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 2260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 2270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 2280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 2290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<ICmpInst>(C) || isa<VICmpInst>(C)) { 2300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar switch (C->getPredicate()) { 2310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar default: // THIS SHOULD NEVER HAPPEN 2320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar assert(0 && "Comparison with unknown predicate?"); 2330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_EQ: return Expression::ICMPEQ; 2340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_NE: return Expression::ICMPNE; 2350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_UGT: return Expression::ICMPUGT; 2360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_UGE: return Expression::ICMPUGE; 2370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_ULT: return Expression::ICMPULT; 2380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_ULE: return Expression::ICMPULE; 2390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_SGT: return Expression::ICMPSGT; 2400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_SGE: return Expression::ICMPSGE; 2410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_SLT: return Expression::ICMPSLT; 2420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case ICmpInst::ICMP_SLE: return Expression::ICMPSLE; 2430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 2440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 2450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar assert((isa<FCmpInst>(C) || isa<VFCmpInst>(C)) && "Unknown compare"); 2460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar switch (C->getPredicate()) { 2470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar default: // THIS SHOULD NEVER HAPPEN 2480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar assert(0 && "Comparison with unknown predicate?"); 2490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ; 2500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_OGT: return Expression::FCMPOGT; 2510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_OGE: return Expression::FCMPOGE; 2520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_OLT: return Expression::FCMPOLT; 2530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_OLE: return Expression::FCMPOLE; 2540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_ONE: return Expression::FCMPONE; 2550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_ORD: return Expression::FCMPORD; 2560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_UNO: return Expression::FCMPUNO; 2570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ; 2580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_UGT: return Expression::FCMPUGT; 2590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_UGE: return Expression::FCMPUGE; 2600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_ULT: return Expression::FCMPULT; 2610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_ULE: return Expression::FCMPULE; 2620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case FCmpInst::FCMP_UNE: return Expression::FCMPUNE; 2630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 2640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 2650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 2660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) { 2670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar switch(C->getOpcode()) { 2680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar default: // THIS SHOULD NEVER HAPPEN 2690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar assert(0 && "Cast operator with unknown opcode?"); 2700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::Trunc: return Expression::TRUNC; 2710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::ZExt: return Expression::ZEXT; 2720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::SExt: return Expression::SEXT; 2730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::FPToUI: return Expression::FPTOUI; 2740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::FPToSI: return Expression::FPTOSI; 2750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::UIToFP: return Expression::UITOFP; 2760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::SIToFP: return Expression::SITOFP; 2770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::FPTrunc: return Expression::FPTRUNC; 2780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::FPExt: return Expression::FPEXT; 2790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::PtrToInt: return Expression::PTRTOINT; 2800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::IntToPtr: return Expression::INTTOPTR; 2810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar case Instruction::BitCast: return Expression::BITCAST; 2820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 2830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 2840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 2850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression ValueTable::create_expression(CallInst* C) { 2860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e; 2870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 2880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.type = C->getType(); 2890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.firstVN = 0; 2900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.secondVN = 0; 2910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.thirdVN = 0; 2920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.function = C->getCalledFunction(); 2930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.opcode = Expression::CALL; 2940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 2950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 2960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar I != E; ++I) 2970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.varargs.push_back(lookup_or_add(*I)); 2980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 2990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return e; 3000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 3010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression ValueTable::create_expression(BinaryOperator* BO) { 3030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e; 3040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.firstVN = lookup_or_add(BO->getOperand(0)); 3060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.secondVN = lookup_or_add(BO->getOperand(1)); 3070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.thirdVN = 0; 3080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.function = 0; 3090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.type = BO->getType(); 3100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.opcode = getOpcode(BO); 3110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return e; 3130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 3140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression ValueTable::create_expression(CmpInst* C) { 3160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e; 3170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.firstVN = lookup_or_add(C->getOperand(0)); 3190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.secondVN = lookup_or_add(C->getOperand(1)); 3200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.thirdVN = 0; 3210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.function = 0; 3220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.type = C->getType(); 3230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.opcode = getOpcode(C); 3240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return e; 3260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 3270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression ValueTable::create_expression(CastInst* C) { 3290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e; 3300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.firstVN = lookup_or_add(C->getOperand(0)); 3320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.secondVN = 0; 3330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.thirdVN = 0; 3340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.function = 0; 3350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.type = C->getType(); 3360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.opcode = getOpcode(C); 3370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return e; 3390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 3400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression ValueTable::create_expression(ShuffleVectorInst* S) { 3420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e; 3430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.firstVN = lookup_or_add(S->getOperand(0)); 3450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.secondVN = lookup_or_add(S->getOperand(1)); 3460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.thirdVN = lookup_or_add(S->getOperand(2)); 3470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.function = 0; 3480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.type = S->getType(); 3490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.opcode = Expression::SHUFFLE; 3500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return e; 3520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 3530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression ValueTable::create_expression(ExtractElementInst* E) { 3550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e; 3560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.firstVN = lookup_or_add(E->getOperand(0)); 3580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.secondVN = lookup_or_add(E->getOperand(1)); 3590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.thirdVN = 0; 3600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.function = 0; 3610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.type = E->getType(); 3620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.opcode = Expression::EXTRACT; 3630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return e; 3650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 3660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression ValueTable::create_expression(InsertElementInst* I) { 3680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e; 3690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.firstVN = lookup_or_add(I->getOperand(0)); 3710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.secondVN = lookup_or_add(I->getOperand(1)); 3720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.thirdVN = lookup_or_add(I->getOperand(2)); 3730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.function = 0; 3740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.type = I->getType(); 3750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.opcode = Expression::INSERT; 3760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return e; 3780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 3790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression ValueTable::create_expression(SelectInst* I) { 3810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e; 3820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.firstVN = lookup_or_add(I->getCondition()); 3840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.secondVN = lookup_or_add(I->getTrueValue()); 3850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.thirdVN = lookup_or_add(I->getFalseValue()); 3860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.function = 0; 3870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.type = I->getType(); 3880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.opcode = Expression::SELECT; 3890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return e; 3910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 3920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarExpression ValueTable::create_expression(GetElementPtrInst* G) { 3940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e; 3950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 3960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.firstVN = lookup_or_add(G->getPointerOperand()); 3970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.secondVN = 0; 3980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.thirdVN = 0; 3990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.function = 0; 4000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.type = G->getType(); 4010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.opcode = Expression::GEP; 4020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 4040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar I != E; ++I) 4050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar e.varargs.push_back(lookup_or_add(*I)); 4060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return e; 4080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 4090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 4110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// ValueTable External Functions 4120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 4130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// add - Insert a value into the table with a specified value number. 4150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarvoid ValueTable::add(Value* V, uint32_t num) { 4160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, num)); 4170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 4180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// lookup_or_add - Returns the value number for the specified value, assigning 4200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// it a new number if it did not have one before. 4210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakaruint32_t ValueTable::lookup_or_add(Value* V) { 4220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 4230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (VI != valueNumbering.end()) 4240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return VI->second; 4250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (CallInst* C = dyn_cast<CallInst>(V)) { 4270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (AA->doesNotAccessMemory(C)) { 4280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(C); 4290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 4310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EI != expressionNumbering.end()) { 4320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, EI->second)); 4330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return EI->second; 4340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 4350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 4360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 4370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 4390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 4400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (AA->onlyReadsMemory(C)) { 4410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(C); 4420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (expressionNumbering.find(e) == expressionNumbering.end()) { 4440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 4450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 4460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 4470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 4480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MemDepResult local_dep = MD->getDependency(C); 4500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!local_dep.isDef() && !local_dep.isNonLocal()) { 4520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 4530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 4540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 4550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (local_dep.isDef()) { 4570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar CallInst* local_cdep = cast<CallInst>(local_dep.getInst()); 4580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (local_cdep->getNumOperands() != C->getNumOperands()) { 4600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 4610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 4620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 4630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (unsigned i = 1; i < C->getNumOperands(); ++i) { 4650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t c_vn = lookup_or_add(C->getOperand(i)); 4660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); 4670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (c_vn != cd_vn) { 4680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 4690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 4700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 4710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 4720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t v = lookup_or_add(local_cdep); 4740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, v)); 4750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return v; 4760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 4770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Non-local case. 4790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar const MemoryDependenceAnalysis::NonLocalDepInfo &deps = 4800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->getNonLocalCallDependency(CallSite(C)); 4810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // FIXME: call/call dependencies for readonly calls should return def, not 4820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // clobber! Move the checking logic to MemDep! 4830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar CallInst* cdep = 0; 4840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Check to see if we have a single dominating call instruction that is 4860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // identical to C. 4870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (unsigned i = 0, e = deps.size(); i != e; ++i) { 4880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar const MemoryDependenceAnalysis::NonLocalDepEntry *I = &deps[i]; 4890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Ignore non-local dependencies. 4900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (I->second.isNonLocal()) 4910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar continue; 4920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 4930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // We don't handle non-depedencies. If we already have a call, reject 4940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // instruction dependencies. 4950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (I->second.isClobber() || cdep != 0) { 4960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar cdep = 0; 4970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar break; 4980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 4990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->second.getInst()); 5010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // FIXME: All duplicated with non-local case. 5020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (NonLocalDepCall && DT->properlyDominates(I->first, C->getParent())){ 5030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar cdep = NonLocalDepCall; 5040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar continue; 5050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar cdep = 0; 5080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar break; 5090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!cdep) { 5120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 5140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (cdep->getNumOperands() != C->getNumOperands()) { 5170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 5190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (unsigned i = 1; i < C->getNumOperands(); ++i) { 5210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t c_vn = lookup_or_add(C->getOperand(i)); 5220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t cd_vn = lookup_or_add(cdep->getOperand(i)); 5230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (c_vn != cd_vn) { 5240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 5260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t v = lookup_or_add(cdep); 5300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, v)); 5310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return v; 5320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 5340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 5360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 5380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(BO); 5390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 5410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EI != expressionNumbering.end()) { 5420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, EI->second)); 5430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return EI->second; 5440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 5450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 5460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 5490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 5510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(C); 5520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 5540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EI != expressionNumbering.end()) { 5550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, EI->second)); 5560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return EI->second; 5570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 5580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 5590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 5620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 5640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(U); 5650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 5670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EI != expressionNumbering.end()) { 5680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, EI->second)); 5690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return EI->second; 5700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 5710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 5720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 5750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 5770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(U); 5780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 5800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EI != expressionNumbering.end()) { 5810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, EI->second)); 5820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return EI->second; 5830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 5840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 5850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 5880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 5890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 5900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(U); 5910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 5920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 5930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EI != expressionNumbering.end()) { 5940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, EI->second)); 5950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return EI->second; 5960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 5970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 5980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 6010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 6020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 6030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(U); 6040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 6060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EI != expressionNumbering.end()) { 6070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, EI->second)); 6080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return EI->second; 6090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 6100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 6110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 6120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 6140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 6150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (CastInst* U = dyn_cast<CastInst>(V)) { 6160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(U); 6170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 6190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EI != expressionNumbering.end()) { 6200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, EI->second)); 6210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return EI->second; 6220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 6230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 6240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 6250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 6270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 6280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 6290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Expression e = create_expression(U); 6300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 6320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EI != expressionNumbering.end()) { 6330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, EI->second)); 6340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return EI->second; 6350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 6360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 6370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 6380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 6400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 6410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 6420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.insert(std::make_pair(V, nextValueNumber)); 6430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return nextValueNumber++; 6440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 6450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 6460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// lookup - Returns the value number of the specified value. Fails if 6480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// the value has not yet been numbered. 6490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakaruint32_t ValueTable::lookup(Value* V) const { 6500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 6510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar assert(VI != valueNumbering.end() && "Value not numbered?"); 6520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return VI->second; 6530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 6540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// clear - Remove all entries from the ValueTable 6560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarvoid ValueTable::clear() { 6570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.clear(); 6580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar expressionNumbering.clear(); 6590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar nextValueNumber = 1; 6600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 6610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// erase - Remove a value from the value numbering 6630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarvoid ValueTable::erase(Value* V) { 6640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar valueNumbering.erase(V); 6650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 6660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// verifyRemoved - Verify that the value is removed from all internal data 6680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// structures. 6690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarvoid ValueTable::verifyRemoved(const Value *V) const { 6700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (DenseMap<Value*, uint32_t>::iterator 6710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) { 6720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar assert(I->first != V && "Inst still occurs in value numbering map!"); 6730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 6740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 6750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 6770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// GVN Pass 6780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar//===----------------------------------------------------------------------===// 6790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarnamespace { 6810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar struct VISIBILITY_HIDDEN ValueNumberScope { 6820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ValueNumberScope* parent; 6830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<uint32_t, Value*> table; 6840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ValueNumberScope(ValueNumberScope* p) : parent(p) { } 6860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar }; 6870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 6880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarnamespace { 6900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar class VISIBILITY_HIDDEN GVN : public FunctionPass { 6920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool runOnFunction(Function &F); 6930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar public: 6940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar static char ID; // Pass identification, replacement for typeid 6950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar GVN() : FunctionPass(&ID) { } 6960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 6970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar private: 6980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MemoryDependenceAnalysis *MD; 6990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DominatorTree *DT; 7000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ValueTable VN; 7020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, ValueNumberScope*> localAvail; 7030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 7050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PhiMapType phiMap; 7060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // This transformation requires dominator postdominator info 7090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar virtual void getAnalysisUsage(AnalysisUsage &AU) const { 7100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar AU.addRequired<DominatorTree>(); 7110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar AU.addRequired<MemoryDependenceAnalysis>(); 7120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar AU.addRequired<AliasAnalysis>(); 7130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar AU.addPreserved<DominatorTree>(); 7150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar AU.addPreserved<AliasAnalysis>(); 7160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 7170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Helper fuctions 7190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // FIXME: eliminate or document these better 7200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool processLoad(LoadInst* L, 7210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVectorImpl<Instruction*> &toErase); 7220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool processInstruction(Instruction* I, 7230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVectorImpl<Instruction*> &toErase); 7240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool processNonLocalLoad(LoadInst* L, 7250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVectorImpl<Instruction*> &toErase); 7260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool processBlock(BasicBlock* BB); 7270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value *GetValueForBlock(BasicBlock *BB, Instruction* orig, 7280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, Value*> &Phis, 7290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool top_level = false); 7300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void dump(DenseMap<uint32_t, Value*>& d); 7310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool iterateOnFunction(Function &F); 7320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* CollapsePhi(PHINode* p); 7330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool isSafeReplacement(PHINode* p, Instruction* inst); 7340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool performPRE(Function& F); 7350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* lookupNumber(BasicBlock* BB, uint32_t num); 7360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool mergeBlockIntoPredecessor(BasicBlock* BB); 7370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* AttemptRedundancyElimination(Instruction* orig, unsigned valno); 7380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void cleanupGlobalSets(); 7390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar void verifyRemoved(const Instruction *I) const; 7400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar }; 7410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar char GVN::ID = 0; 7430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 7440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// createGVNPass - The public interface to this file... 7460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarFunctionPass *llvm::createGVNPass() { return new GVN(); } 7470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarstatic RegisterPass<GVN> X("gvn", 7490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar "Global Value Numbering"); 7500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarvoid GVN::dump(DenseMap<uint32_t, Value*>& d) { 7520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar printf("{\n"); 7530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (DenseMap<uint32_t, Value*>::iterator I = d.begin(), 7540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar E = d.end(); I != E; ++I) { 7550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar printf("%d\n", I->first); 7560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar I->second->dump(); 7570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 7580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar printf("}\n"); 7590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 7600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarValue* GVN::CollapsePhi(PHINode* p) { 7620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* constVal = p->hasConstantValue(); 7630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!constVal) return 0; 7640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Instruction* inst = dyn_cast<Instruction>(constVal); 7660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!inst) 7670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return constVal; 7680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (DT->dominates(inst, p)) 7700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isSafeReplacement(p, inst)) 7710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return inst; 7720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return 0; 7730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 7740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarbool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 7760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!isa<PHINode>(inst)) 7770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 7780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 7800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar UI != E; ++UI) 7810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 7820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (use_phi->getParent() == inst->getParent()) 7830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 7840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 7860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 7870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// GetValueForBlock - Get the value to use within the specified basic block. 7890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// available values are in Phis. 7900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarValue *GVN::GetValueForBlock(BasicBlock *BB, Instruction* orig, 7910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, Value*> &Phis, 7920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool top_level) { 7930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we have already computed this value, return the previously computed val. 7950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 7960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (V != Phis.end() && !top_level) return V->second; 7970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 7980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If the block is unreachable, just return undef, since this path 7990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // can't actually occur at runtime. 8000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!DT->isReachableFromEntry(BB)) 8010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return Phis[BB] = UndefValue::get(orig->getType()); 8020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (BasicBlock *Pred = BB->getSinglePredecessor()) { 8040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value *ret = GetValueForBlock(Pred, orig, Phis); 8050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Phis[BB] = ret; 8060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return ret; 8070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 8080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Get the number of predecessors of this block so we can reserve space later. 8100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If there is already a PHI in it, use the #preds from it, otherwise count. 8110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Getting it from the PHI is constant time. 8120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar unsigned NumPreds; 8130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (PHINode *ExistingPN = dyn_cast<PHINode>(BB->begin())) 8140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar NumPreds = ExistingPN->getNumIncomingValues(); 8150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else 8160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar NumPreds = std::distance(pred_begin(BB), pred_end(BB)); 8170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 8190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // now, then get values to fill in the incoming values for the PHI. 8200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle", 8210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BB->begin()); 8220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PN->reserveOperandSpace(NumPreds); 8230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Phis.insert(std::make_pair(BB, PN)); 8250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Fill in the incoming values for the block. 8270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 8280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* val = GetValueForBlock(*PI, orig, Phis); 8290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PN->addIncoming(val, *PI); 8300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 8310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar VN.getAliasAnalysis()->copyValue(orig, PN); 8330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Attempt to collapse PHI nodes that are trivially redundant 8350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* v = CollapsePhi(PN); 8360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!v) { 8370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Cache our phi construction results 8380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (LoadInst* L = dyn_cast<LoadInst>(orig)) 8390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar phiMap[L->getPointerOperand()].insert(PN); 8400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else 8410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar phiMap[orig].insert(PN); 8420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return PN; 8440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 8450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PN->replaceAllUsesWith(v); 8470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PointerType>(v->getType())) 8480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->invalidateCachedPointerInfo(v); 8490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 8510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar E = Phis.end(); I != E; ++I) 8520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (I->second == PN) 8530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar I->second = v; 8540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DEBUG(cerr << "GVN removed: " << *PN); 8560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->removeInstruction(PN); 8570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PN->eraseFromParent(); 8580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DEBUG(verifyRemoved(PN)); 8590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Phis[BB] = v; 8610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return v; 8620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 8630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// IsValueFullyAvailableInBlock - Return true if we can prove that the value 8650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// we're analyzing is fully available in the specified block. As we go, keep 8660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// track of which blocks we know are fully alive in FullyAvailableBlocks. This 8670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// map is actually a tri-state map with the following values: 8680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// 0) we know the block *is not* fully available. 8690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// 1) we know the block *is* fully available. 8700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// 2) we do not know whether the block is fully available or not, but we are 8710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// currently speculating that it will be. 8720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// 3) we are speculating for this block and have used that to speculate for 8730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// other blocks. 8740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarstatic bool IsValueFullyAvailableInBlock(BasicBlock *BB, 8750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, char> &FullyAvailableBlocks) { 8760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Optimistically assume that the block is fully available and check to see 8770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // if we already know about this block in one lookup. 8780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar std::pair<DenseMap<BasicBlock*, char>::iterator, char> IV = 8790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar FullyAvailableBlocks.insert(std::make_pair(BB, 2)); 8800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If the entry already existed for this block, return the precomputed value. 8820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!IV.second) { 8830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If this is a speculative "available" value, mark it as being used for 8840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // speculation of other blocks. 8850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (IV.first->second == 2) 8860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar IV.first->second = 3; 8870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return IV.first->second != 0; 8880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 8890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Otherwise, see if it is fully available in all predecessors. 8910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 8920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If this block has no predecessors, it isn't live-in here. 8940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (PI == PE) 8950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar goto SpeculationFailure; 8960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 8970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (; PI != PE; ++PI) 8980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If the value isn't fully available in one of our predecessors, then it 8990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // isn't fully available in this block either. Undo our previous 9000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // optimistic assumption and bail out. 9010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks)) 9020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar goto SpeculationFailure; 9030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 9050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// SpeculationFailure - If we get here, we found out that this is not, after 9070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// all, a fully-available block. We have a problem if we speculated on this and 9080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar// used the speculation to mark other blocks as available. 9090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarSpeculationFailure: 9100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar char &BBVal = FullyAvailableBlocks[BB]; 9110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we didn't speculate on this, just return with it set to false. 9130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (BBVal == 2) { 9140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BBVal = 0; 9150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 9160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 9170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we did speculate on this value, we could have blocks set to 1 that are 9190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // incorrect. Walk the (transitive) successors of this block and mark them as 9200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // 0 if set to one. 9210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVector<BasicBlock*, 32> BBWorklist; 9220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BBWorklist.push_back(BB); 9230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar while (!BBWorklist.empty()) { 9250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BasicBlock *Entry = BBWorklist.pop_back_val(); 9260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Note that this sets blocks to 0 (unavailable) if they happen to not 9270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // already be in FullyAvailableBlocks. This is safe. 9280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar char &EntryVal = FullyAvailableBlocks[Entry]; 9290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (EntryVal == 0) continue; // Already unavailable. 9300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Mark as unavailable. 9320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar EntryVal = 0; 9330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (succ_iterator I = succ_begin(Entry), E = succ_end(Entry); I != E; ++I) 9350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BBWorklist.push_back(*I); 9360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 9370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 9390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 9400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 9420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// non-local by performing PHI construction. 9430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarbool GVN::processNonLocalLoad(LoadInst *LI, 9440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVectorImpl<Instruction*> &toErase) { 9450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Find the non-local dependencies of the load. 9460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVector<MemoryDependenceAnalysis::NonLocalDepEntry, 64> Deps; 9470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->getNonLocalPointerDependency(LI->getOperand(0), true, LI->getParent(), 9480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Deps); 9490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar //DEBUG(cerr << "INVESTIGATING NONLOCAL LOAD: " << Deps.size() << *LI); 9500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we had to process more than one hundred blocks to find the 9520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // dependencies, this load isn't worth worrying about. Optimizing 9530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // it will be too expensive. 9540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (Deps.size() > 100) 9550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 9560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we had a phi translation failure, we'll have a single entry which is a 9580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // clobber in the current block. Reject this early. 9590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (Deps.size() == 1 && Deps[0].second.isClobber()) 9600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 9610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Filter out useless results (non-locals, etc). Keep track of the blocks 9630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // where we have a value available in repl, also keep track of whether we see 9640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // dependencies that produce an unknown value for the load (such as a call 9650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // that could potentially clobber the load). 9660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVector<std::pair<BasicBlock*, Value*>, 16> ValuesPerBlock; 9670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVector<BasicBlock*, 16> UnavailableBlocks; 9680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (unsigned i = 0, e = Deps.size(); i != e; ++i) { 9700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BasicBlock *DepBB = Deps[i].first; 9710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MemDepResult DepInfo = Deps[i].second; 9720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (DepInfo.isClobber()) { 9740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar UnavailableBlocks.push_back(DepBB); 9750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar continue; 9760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 9770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Instruction *DepInst = DepInfo.getInst(); 9790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Loading the allocation -> undef. 9810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<AllocationInst>(DepInst)) { 9820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ValuesPerBlock.push_back(std::make_pair(DepBB, 9830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar UndefValue::get(LI->getType()))); 9840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar continue; 9850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 9860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (StoreInst* S = dyn_cast<StoreInst>(DepInst)) { 9880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Reject loads and stores that are to the same address but are of 9890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // different types. 9900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // NOTE: 403.gcc does have this case (e.g. in readonly_fields_p) because 9910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // of bitfield access, it would be interesting to optimize for it at some 9920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // point. 9930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (S->getOperand(0)->getType() != LI->getType()) { 9940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar UnavailableBlocks.push_back(DepBB); 9950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar continue; 9960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 9970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 9980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ValuesPerBlock.push_back(std::make_pair(DepBB, S->getOperand(0))); 9990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (LoadInst* LD = dyn_cast<LoadInst>(DepInst)) { 10010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (LD->getType() != LI->getType()) { 10020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar UnavailableBlocks.push_back(DepBB); 10030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar continue; 10040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 10050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ValuesPerBlock.push_back(std::make_pair(DepBB, LD)); 10060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 10070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar UnavailableBlocks.push_back(DepBB); 10080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar continue; 10090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 10100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 10110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we have no predecessors that produce a known value for this load, exit 10130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // early. 10140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (ValuesPerBlock.empty()) return false; 10150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If all of the instructions we depend on produce a known value for this 10170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // load, then it is fully redundant and we can use PHI insertion to compute 10180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // its value. Insert PHIs and remove the fully redundant value now. 10190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (UnavailableBlocks.empty()) { 10200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Use cached PHI construction information from previous runs 10210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallPtrSet<Instruction*, 4> &p = phiMap[LI->getPointerOperand()]; 10220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // FIXME: What does phiMap do? Are we positive it isn't getting invalidated? 10230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 10240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar I != E; ++I) { 10250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if ((*I)->getParent() == LI->getParent()) { 10260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD #1: " << *LI); 10270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar LI->replaceAllUsesWith(*I); 10280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PointerType>((*I)->getType())) 10290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->invalidateCachedPointerInfo(*I); 10300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar toErase.push_back(LI); 10310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar NumGVNLoad++; 10320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 10330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 10340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ValuesPerBlock.push_back(std::make_pair((*I)->getParent(), *I)); 10360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 10370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD: " << *LI); 10390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, Value*> BlockReplValues; 10410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 10420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Perform PHI construction. 10430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 10440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar LI->replaceAllUsesWith(v); 10450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PHINode>(v)) 10470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar v->takeName(LI); 10480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PointerType>(v->getType())) 10490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->invalidateCachedPointerInfo(v); 10500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar toErase.push_back(LI); 10510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar NumGVNLoad++; 10520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 10530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 10540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!EnablePRE || !EnableLoadPRE) 10560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 10570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Okay, we have *some* definitions of the value. This means that the value 10590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // is available in some of our (transitive) predecessors. Lets think about 10600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // doing PRE of this load. This will involve inserting a new load into the 10610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // predecessor when it's not available. We could do this in general, but 10620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // prefer to not increase code size. As such, we only do this when we know 10630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // that we only have to insert *one* load (which means we're basically moving 10640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // the load, not inserting a new one). 10650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Everything we do here is based on local predecessors of LI's block. If it 10670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // only has one predecessor, bail now. 10680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BasicBlock *LoadBB = LI->getParent(); 10690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (LoadBB->getSinglePredecessor()) 10700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 10710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we have a repl set with LI itself in it, this means we have a loop where 10730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // at least one of the values is LI. Since this means that we won't be able 10740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // to eliminate LI even if we insert uses in the other predecessors, we will 10750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // end up increasing code size. Reject this by scanning for LI. 10760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 10770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (ValuesPerBlock[i].second == LI) 10780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 10790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Okay, we have some hope :). Check to see if the loaded value is fully 10810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // available in all but one predecessor. 10820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // FIXME: If we could restructure the CFG, we could make a common pred with 10830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // all the preds that don't have an available LI and insert a new load into 10840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // that one block. 10850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BasicBlock *UnavailablePred = 0; 10860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, char> FullyAvailableBlocks; 10880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 10890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar FullyAvailableBlocks[ValuesPerBlock[i].first] = true; 10900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i) 10910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar FullyAvailableBlocks[UnavailableBlocks[i]] = false; 10920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); 10940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PI != E; ++PI) { 10950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks)) 10960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar continue; 10970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 10980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If this load is not available in multiple predecessors, reject it. 10990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (UnavailablePred && UnavailablePred != *PI) 11000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 11010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar UnavailablePred = *PI; 11020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 11030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar assert(UnavailablePred != 0 && 11050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar "Fully available value should be eliminated above!"); 11060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If the loaded pointer is PHI node defined in this block, do PHI translation 11080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // to get its value in the predecessor. 11090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value *LoadPtr = LI->getOperand(0)->DoPHITranslation(LoadBB, UnavailablePred); 11100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Make sure the value is live in the predecessor. If it was defined by a 11120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // non-PHI instruction in this block, we don't know how to recompute it above. 11130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (Instruction *LPInst = dyn_cast<Instruction>(LoadPtr)) 11140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!DT->dominates(LPInst->getParent(), UnavailablePred)) { 11150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DEBUG(cerr << "COULDN'T PRE LOAD BECAUSE PTR IS UNAVAILABLE IN PRED: " 11160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar << *LPInst << *LI << "\n"); 11170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 11180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 11190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // We don't currently handle critical edges :( 11210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) { 11220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DEBUG(cerr << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '" 11230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar << UnavailablePred->getName() << "': " << *LI); 11240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 11250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 11260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Okay, we can eliminate this load by inserting a reload in the predecessor 11280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // and using PHI construction to get the value in the other predecessors, do 11290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // it. 11300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DEBUG(cerr << "GVN REMOVING PRE LOAD: " << *LI); 11310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false, 11330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar LI->getAlignment(), 11340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar UnavailablePred->getTerminator()); 11350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, Value*> BlockReplValues; 11370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 11380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BlockReplValues[UnavailablePred] = NewLoad; 11390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Perform PHI construction. 11410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 11420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar LI->replaceAllUsesWith(v); 11430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PHINode>(v)) 11440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar v->takeName(LI); 11450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PointerType>(v->getType())) 11460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->invalidateCachedPointerInfo(v); 11470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar toErase.push_back(LI); 11480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar NumPRELoad++; 11490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 11500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 11510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// processLoad - Attempt to eliminate a load, first by eliminating it 11530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// locally, and then attempting non-local elimination if that fails. 11540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarbool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) { 11550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (L->isVolatile()) 11560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 11570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* pointer = L->getPointerOperand(); 11590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // ... to a pointer that has been loaded from before... 11610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MemDepResult dep = MD->getDependency(L); 11620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If the value isn't available, don't do anything! 11640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (dep.isClobber()) 11650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 11660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If it is defined in another block, try harder. 11680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (dep.isNonLocal()) 11690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return processNonLocalLoad(L, toErase); 11700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Instruction *DepInst = dep.getInst(); 11720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) { 11730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Only forward substitute stores to loads of the same type. 11740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // FIXME: Could do better! 11750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (DepSI->getPointerOperand()->getType() != pointer->getType()) 11760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 11770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Remove it! 11790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar L->replaceAllUsesWith(DepSI->getOperand(0)); 11800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PointerType>(DepSI->getOperand(0)->getType())) 11810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->invalidateCachedPointerInfo(DepSI->getOperand(0)); 11820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar toErase.push_back(L); 11830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar NumGVNLoad++; 11840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 11850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 11860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) { 11880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Only forward substitute stores to loads of the same type. 11890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // FIXME: Could do better! load i32 -> load i8 -> truncate on little endian. 11900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (DepLI->getType() != L->getType()) 11910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 11920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 11930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Remove it! 11940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar L->replaceAllUsesWith(DepLI); 11950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PointerType>(DepLI->getType())) 11960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->invalidateCachedPointerInfo(DepLI); 11970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar toErase.push_back(L); 11980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar NumGVNLoad++; 11990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 12000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 12010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If this load really doesn't depend on anything, then we must be loading an 12030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // undef value. This can happen when loading for a fresh allocation with no 12040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // intervening stores, for example. 12050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<AllocationInst>(DepInst)) { 12060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar L->replaceAllUsesWith(UndefValue::get(L->getType())); 12070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar toErase.push_back(L); 12080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar NumGVNLoad++; 12090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 12100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 12110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 12130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 12140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarValue* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { 12160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB); 12170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (I == localAvail.end()) 12180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return 0; 12190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ValueNumberScope* locals = I->second; 12210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar while (locals) { 12230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num); 12240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (I != locals->table.end()) 12250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return I->second; 12260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else 12270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar locals = locals->parent; 12280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 12290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return 0; 12310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 12320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// AttemptRedundancyElimination - If the "fast path" of redundancy elimination 12340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// by inheritance from the dominator fails, see if we can perform phi 12350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// construction to eliminate the redundancy. 12360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish MahendrakarValue* GVN::AttemptRedundancyElimination(Instruction* orig, unsigned valno) { 12370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BasicBlock* BaseBlock = orig->getParent(); 12380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallPtrSet<BasicBlock*, 4> Visited; 12400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVector<BasicBlock*, 8> Stack; 12410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Stack.push_back(BaseBlock); 12420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, Value*> Results; 12440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Walk backwards through our predecessors, looking for instances of the 12460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // value number we're looking for. Instances are recorded in the Results 12470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // map, which is then used to perform phi construction. 12480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar while (!Stack.empty()) { 12490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BasicBlock* Current = Stack.back(); 12500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Stack.pop_back(); 12510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we've walked all the way to a proper dominator, then give up. Cases 12530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // where the instance is in the dominator will have been caught by the fast 12540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // path, and any cases that require phi construction further than this are 12550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // probably not worth it anyways. Note that this is a SIGNIFICANT compile 12560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // time improvement. 12570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (DT->properlyDominates(Current, orig->getParent())) return 0; 12580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<BasicBlock*, ValueNumberScope*>::iterator LA = 12600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar localAvail.find(Current); 12610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (LA == localAvail.end()) return 0; 12620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar DenseMap<uint32_t, Value*>::iterator V = LA->second->table.find(valno); 12630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (V != LA->second->table.end()) { 12650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Found an instance, record it. 12660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Results.insert(std::make_pair(Current, V->second)); 12670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar continue; 12680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 12690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we reach the beginning of the function, then give up. 12710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (pred_begin(Current) == pred_end(Current)) 12720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return 0; 12730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (pred_iterator PI = pred_begin(Current), PE = pred_end(Current); 12750d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PI != PE; ++PI) 12760d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (Visited.insert(*PI)) 12770d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Stack.push_back(*PI); 12780d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 12790d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12800d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If we didn't find instances, give up. Otherwise, perform phi construction. 12810d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (Results.size() == 0) 12820d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return 0; 12830d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar else 12840d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return GetValueForBlock(BaseBlock, orig, Results, true); 12850d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar} 12860d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12870d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// processInstruction - When calculating availability, handle an instruction 12880d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar/// by inserting it into the appropriate sets 12890d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakarbool GVN::processInstruction(Instruction *I, 12900d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar SmallVectorImpl<Instruction*> &toErase) { 12910d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (LoadInst* L = dyn_cast<LoadInst>(I)) { 12920d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar bool changed = processLoad(L, toErase); 12930d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12940d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!changed) { 12950d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar unsigned num = VN.lookup_or_add(L); 12960d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar localAvail[I->getParent()]->table.insert(std::make_pair(num, L)); 12970d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 12980d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 12990d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return changed; 13000d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 13010d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13020d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t nextNum = VN.getNextUnusedValueNumber(); 13030d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar unsigned num = VN.lookup_or_add(I); 13040d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13050d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (BranchInst* BI = dyn_cast<BranchInst>(I)) { 13060d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 13070d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13080d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (!BI->isConditional() || isa<Constant>(BI->getCondition())) 13090d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 13100d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13110d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* branchCond = BI->getCondition(); 13120d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar uint32_t condVN = VN.lookup_or_add(branchCond); 13130d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13140d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BasicBlock* trueSucc = BI->getSuccessor(0); 13150d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar BasicBlock* falseSucc = BI->getSuccessor(1); 13160d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13170d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar localAvail[trueSucc]->table.insert(std::make_pair(condVN, 13180d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ConstantInt::getTrue())); 13190d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar localAvail[falseSucc]->table.insert(std::make_pair(condVN, 13200d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar ConstantInt::getFalse())); 13210d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 13220d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13230d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Allocations are always uniquely numbered, so we can save time and memory 13240d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // by fast failing them. 13250d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) { 13260d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 13270d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return false; 13280d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 13290d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13300d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Collapse PHI nodes 13310d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (PHINode* p = dyn_cast<PHINode>(I)) { 13320d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar Value* constVal = CollapsePhi(p); 13330d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13340d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (constVal) { 13350d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 13360d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PI != PE; ++PI) 13370d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar PI->second.erase(p); 13380d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13390d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar p->replaceAllUsesWith(constVal); 13400d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PointerType>(constVal->getType())) 13410d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->invalidateCachedPointerInfo(constVal); 13420d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar VN.erase(p); 13430d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13440d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar toErase.push_back(p); 13450d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else { 13460d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 13470d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } 13480d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13490d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // If the number we were assigned was a brand new VN, then we don't 13500d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // need to do a lookup to see if the number already exists 13510d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // somewhere in the domtree: it can't! 13520d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (num == nextNum) { 13530d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 13540d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13550d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Perform fast-path value-number based elimination of values inherited from 13560d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // dominators. 13570d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (Value* repl = lookupNumber(I->getParent(), num)) { 13580d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Remove it! 13590d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar VN.erase(I); 13600d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar I->replaceAllUsesWith(repl); 13610d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PointerType>(repl->getType())) 13620d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->invalidateCachedPointerInfo(repl); 13630d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar toErase.push_back(I); 13640d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar return true; 13650d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar 13660d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar#if 0 13670d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Perform slow-pathvalue-number based elimination with phi construction. 13680d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar } else if (Value* repl = AttemptRedundancyElimination(I, num)) { 13690d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar // Remove it! 13700d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar VN.erase(I); 13710d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar I->replaceAllUsesWith(repl); 13720d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar if (isa<PointerType>(repl->getType())) 13730d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar MD->invalidateCachedPointerInfo(repl); 13740d8951cef4b1a1dbf4ff5ba3e8796cf1d4503098Harish Mahendrakar toErase.push_back(I); 1375 return true; 1376#endif 1377 } else { 1378 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 1379 } 1380 1381 return false; 1382} 1383 1384/// runOnFunction - This is the main transformation entry point for a function. 1385bool GVN::runOnFunction(Function& F) { 1386 MD = &getAnalysis<MemoryDependenceAnalysis>(); 1387 DT = &getAnalysis<DominatorTree>(); 1388 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1389 VN.setMemDep(MD); 1390 VN.setDomTree(DT); 1391 1392 bool changed = false; 1393 bool shouldContinue = true; 1394 1395 // Merge unconditional branches, allowing PRE to catch more 1396 // optimization opportunities. 1397 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { 1398 BasicBlock* BB = FI; 1399 ++FI; 1400 bool removedBlock = MergeBlockIntoPredecessor(BB, this); 1401 if (removedBlock) NumGVNBlocks++; 1402 1403 changed |= removedBlock; 1404 } 1405 1406 unsigned Iteration = 0; 1407 1408 while (shouldContinue) { 1409 DEBUG(cerr << "GVN iteration: " << Iteration << "\n"); 1410 shouldContinue = iterateOnFunction(F); 1411 changed |= shouldContinue; 1412 ++Iteration; 1413 } 1414 1415 if (EnablePRE) { 1416 bool PREChanged = true; 1417 while (PREChanged) { 1418 PREChanged = performPRE(F); 1419 changed |= PREChanged; 1420 } 1421 } 1422 // FIXME: Should perform GVN again after PRE does something. PRE can move 1423 // computations into blocks where they become fully redundant. Note that 1424 // we can't do this until PRE's critical edge splitting updates memdep. 1425 // Actually, when this happens, we should just fully integrate PRE into GVN. 1426 1427 cleanupGlobalSets(); 1428 1429 return changed; 1430} 1431 1432 1433bool GVN::processBlock(BasicBlock* BB) { 1434 // FIXME: Kill off toErase by doing erasing eagerly in a helper function (and 1435 // incrementing BI before processing an instruction). 1436 SmallVector<Instruction*, 8> toErase; 1437 bool changed_function = false; 1438 1439 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1440 BI != BE;) { 1441 changed_function |= processInstruction(BI, toErase); 1442 if (toErase.empty()) { 1443 ++BI; 1444 continue; 1445 } 1446 1447 // If we need some instructions deleted, do it now. 1448 NumGVNInstr += toErase.size(); 1449 1450 // Avoid iterator invalidation. 1451 bool AtStart = BI == BB->begin(); 1452 if (!AtStart) 1453 --BI; 1454 1455 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1456 E = toErase.end(); I != E; ++I) { 1457 DEBUG(cerr << "GVN removed: " << **I); 1458 MD->removeInstruction(*I); 1459 (*I)->eraseFromParent(); 1460 DEBUG(verifyRemoved(*I)); 1461 } 1462 toErase.clear(); 1463 1464 if (AtStart) 1465 BI = BB->begin(); 1466 else 1467 ++BI; 1468 } 1469 1470 return changed_function; 1471} 1472 1473/// performPRE - Perform a purely local form of PRE that looks for diamond 1474/// control flow patterns and attempts to perform simple PRE at the join point. 1475bool GVN::performPRE(Function& F) { 1476 bool Changed = false; 1477 SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit; 1478 DenseMap<BasicBlock*, Value*> predMap; 1479 for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()), 1480 DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { 1481 BasicBlock* CurrentBlock = *DI; 1482 1483 // Nothing to PRE in the entry block. 1484 if (CurrentBlock == &F.getEntryBlock()) continue; 1485 1486 for (BasicBlock::iterator BI = CurrentBlock->begin(), 1487 BE = CurrentBlock->end(); BI != BE; ) { 1488 Instruction *CurInst = BI++; 1489 1490 if (isa<AllocationInst>(CurInst) || isa<TerminatorInst>(CurInst) || 1491 isa<PHINode>(CurInst) || (CurInst->getType() == Type::VoidTy) || 1492 CurInst->mayReadFromMemory() || CurInst->mayWriteToMemory() || 1493 isa<DbgInfoIntrinsic>(CurInst)) 1494 continue; 1495 1496 uint32_t valno = VN.lookup(CurInst); 1497 1498 // Look for the predecessors for PRE opportunities. We're 1499 // only trying to solve the basic diamond case, where 1500 // a value is computed in the successor and one predecessor, 1501 // but not the other. We also explicitly disallow cases 1502 // where the successor is its own predecessor, because they're 1503 // more complicated to get right. 1504 unsigned numWith = 0; 1505 unsigned numWithout = 0; 1506 BasicBlock* PREPred = 0; 1507 predMap.clear(); 1508 1509 for (pred_iterator PI = pred_begin(CurrentBlock), 1510 PE = pred_end(CurrentBlock); PI != PE; ++PI) { 1511 // We're not interested in PRE where the block is its 1512 // own predecessor, on in blocks with predecessors 1513 // that are not reachable. 1514 if (*PI == CurrentBlock) { 1515 numWithout = 2; 1516 break; 1517 } else if (!localAvail.count(*PI)) { 1518 numWithout = 2; 1519 break; 1520 } 1521 1522 DenseMap<uint32_t, Value*>::iterator predV = 1523 localAvail[*PI]->table.find(valno); 1524 if (predV == localAvail[*PI]->table.end()) { 1525 PREPred = *PI; 1526 numWithout++; 1527 } else if (predV->second == CurInst) { 1528 numWithout = 2; 1529 } else { 1530 predMap[*PI] = predV->second; 1531 numWith++; 1532 } 1533 } 1534 1535 // Don't do PRE when it might increase code size, i.e. when 1536 // we would need to insert instructions in more than one pred. 1537 if (numWithout != 1 || numWith == 0) 1538 continue; 1539 1540 // We can't do PRE safely on a critical edge, so instead we schedule 1541 // the edge to be split and perform the PRE the next time we iterate 1542 // on the function. 1543 unsigned succNum = 0; 1544 for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors(); 1545 i != e; ++i) 1546 if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) { 1547 succNum = i; 1548 break; 1549 } 1550 1551 if (isCriticalEdge(PREPred->getTerminator(), succNum)) { 1552 toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum)); 1553 continue; 1554 } 1555 1556 // Instantiate the expression the in predecessor that lacked it. 1557 // Because we are going top-down through the block, all value numbers 1558 // will be available in the predecessor by the time we need them. Any 1559 // that weren't original present will have been instantiated earlier 1560 // in this loop. 1561 Instruction* PREInstr = CurInst->clone(); 1562 bool success = true; 1563 for (unsigned i = 0, e = CurInst->getNumOperands(); i != e; ++i) { 1564 Value *Op = PREInstr->getOperand(i); 1565 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op)) 1566 continue; 1567 1568 if (Value *V = lookupNumber(PREPred, VN.lookup(Op))) { 1569 PREInstr->setOperand(i, V); 1570 } else { 1571 success = false; 1572 break; 1573 } 1574 } 1575 1576 // Fail out if we encounter an operand that is not available in 1577 // the PRE predecessor. This is typically because of loads which 1578 // are not value numbered precisely. 1579 if (!success) { 1580 delete PREInstr; 1581 DEBUG(verifyRemoved(PREInstr)); 1582 continue; 1583 } 1584 1585 PREInstr->insertBefore(PREPred->getTerminator()); 1586 PREInstr->setName(CurInst->getName() + ".pre"); 1587 predMap[PREPred] = PREInstr; 1588 VN.add(PREInstr, valno); 1589 NumGVNPRE++; 1590 1591 // Update the availability map to include the new instruction. 1592 localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr)); 1593 1594 // Create a PHI to make the value available in this block. 1595 PHINode* Phi = PHINode::Create(CurInst->getType(), 1596 CurInst->getName() + ".pre-phi", 1597 CurrentBlock->begin()); 1598 for (pred_iterator PI = pred_begin(CurrentBlock), 1599 PE = pred_end(CurrentBlock); PI != PE; ++PI) 1600 Phi->addIncoming(predMap[*PI], *PI); 1601 1602 VN.add(Phi, valno); 1603 localAvail[CurrentBlock]->table[valno] = Phi; 1604 1605 CurInst->replaceAllUsesWith(Phi); 1606 if (isa<PointerType>(Phi->getType())) 1607 MD->invalidateCachedPointerInfo(Phi); 1608 VN.erase(CurInst); 1609 1610 DEBUG(cerr << "GVN PRE removed: " << *CurInst); 1611 MD->removeInstruction(CurInst); 1612 CurInst->eraseFromParent(); 1613 DEBUG(verifyRemoved(CurInst)); 1614 Changed = true; 1615 } 1616 } 1617 1618 for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator 1619 I = toSplit.begin(), E = toSplit.end(); I != E; ++I) 1620 SplitCriticalEdge(I->first, I->second, this); 1621 1622 return Changed || toSplit.size(); 1623} 1624 1625/// iterateOnFunction - Executes one iteration of GVN 1626bool GVN::iterateOnFunction(Function &F) { 1627 cleanupGlobalSets(); 1628 1629 for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()), 1630 DE = df_end(DT->getRootNode()); DI != DE; ++DI) { 1631 if (DI->getIDom()) 1632 localAvail[DI->getBlock()] = 1633 new ValueNumberScope(localAvail[DI->getIDom()->getBlock()]); 1634 else 1635 localAvail[DI->getBlock()] = new ValueNumberScope(0); 1636 } 1637 1638 // Top-down walk of the dominator tree 1639 bool changed = false; 1640#if 0 1641 // Needed for value numbering with phi construction to work. 1642 ReversePostOrderTraversal<Function*> RPOT(&F); 1643 for (ReversePostOrderTraversal<Function*>::rpo_iterator RI = RPOT.begin(), 1644 RE = RPOT.end(); RI != RE; ++RI) 1645 changed |= processBlock(*RI); 1646#else 1647 for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()), 1648 DE = df_end(DT->getRootNode()); DI != DE; ++DI) 1649 changed |= processBlock(DI->getBlock()); 1650#endif 1651 1652 return changed; 1653} 1654 1655void GVN::cleanupGlobalSets() { 1656 VN.clear(); 1657 phiMap.clear(); 1658 1659 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator 1660 I = localAvail.begin(), E = localAvail.end(); I != E; ++I) 1661 delete I->second; 1662 localAvail.clear(); 1663} 1664 1665/// verifyRemoved - Verify that the specified instruction does not occur in our 1666/// internal data structures. 1667void GVN::verifyRemoved(const Instruction *Inst) const { 1668 VN.verifyRemoved(Inst); 1669 1670 // Walk through the PHI map to make sure the instruction isn't hiding in there 1671 // somewhere. 1672 for (PhiMapType::iterator 1673 I = phiMap.begin(), E = phiMap.end(); I != E; ++I) { 1674 assert(I->first != Inst && "Inst is still a key in PHI map!"); 1675 1676 for (SmallPtrSet<Instruction*, 4>::iterator 1677 II = I->second.begin(), IE = I->second.end(); II != IE; ++II) { 1678 assert(*II != Inst && "Inst is still a value in PHI map!"); 1679 } 1680 } 1681 1682 // Walk through the value number scope to make sure the instruction isn't 1683 // ferreted away in it. 1684 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator 1685 I = localAvail.begin(), E = localAvail.end(); I != E; ++I) { 1686 const ValueNumberScope *VNS = I->second; 1687 1688 while (VNS) { 1689 for (DenseMap<uint32_t, Value*>::iterator 1690 II = VNS->table.begin(), IE = VNS->table.end(); II != IE; ++II) { 1691 assert(II->second != Inst && "Inst still in value numbering scope!"); 1692 } 1693 1694 VNS = VNS->parent; 1695 } 1696 } 1697} 1698