GVN.cpp revision b388ca9544f66899ad7f6be665e2bc7529888254
124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===- GVN.cpp - Eliminate redundant values and loads ------------===// 224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// The LLVM Compiler Infrastructure 424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// This file was developed by the Owen Anderson and is distributed under 624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// the University of Illinois Open Source License. See LICENSE.TXT for details. 724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 1024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// This pass performs global value numbering to eliminate fully redundant 1124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// instructions. It also performs simple dead load elimination. 1224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 1324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 1424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 1524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#define DEBUG_TYPE "gvn" 1624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 17a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham#include "llvm/Transforms/Scalar.h" 1824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/BasicBlock.h" 1924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/Constants.h" 2024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/DerivedTypes.h" 21e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice#include "llvm/Function.h" 2222defe8b06df5b1f09b53bda255ef07513abc04cGreg Clayton#include "llvm/Instructions.h" 2322defe8b06df5b1f09b53bda255ef07513abc04cGreg Clayton#include "llvm/Value.h" 24e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice#include "llvm/ADT/BitVector.h" 2524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/ADT/DenseMap.h" 2624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/ADT/DepthFirstIterator.h" 2724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/ADT/SmallPtrSet.h" 2824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/ADT/SmallVector.h" 29eddffe93d2c9ebb575e7b03fe1c5e71f9ecaf9f1Caroline Tice#include "llvm/ADT/Statistic.h" 3024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/Analysis/Dominators.h" 3124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/Analysis/AliasAnalysis.h" 3224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/Analysis/MemoryDependenceAnalysis.h" 3324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/Support/CFG.h" 3424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/Support/Compiler.h" 3524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnerusing namespace llvm; 3624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 3724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 3824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// ValueTable Class 3924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 4024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 4124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// This class holds the mapping between values and value numbers. It is used 4224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// as an efficient mechanism to determine the expression-wise equivalence of 4324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// two values. 4424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnernamespace { 4524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner struct VISIBILITY_HIDDEN Expression { 4624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 4724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 4824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 4924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 50a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 51a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 52a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 53a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 54a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 5524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY, 5624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner TOMBSTONE }; 5724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 5824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner ExpressionOpcode opcode; 5924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner const Type* type; 6024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner uint32_t firstVN; 61a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham uint32_t secondVN; 62a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham uint32_t thirdVN; 63a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham SmallVector<uint32_t, 4> varargs; 64a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham Value* function; 65a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham 6654e7afa84d945f9137f9372ecde432f9e1a702fcGreg Clayton Expression() { } 67a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham Expression(ExpressionOpcode o) : opcode(o) { } 68a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham 69a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham bool operator==(const Expression &other) const { 70a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham if (opcode != other.opcode) 71a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return false; 72a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else if (opcode == EMPTY || opcode == TOMBSTONE) 73a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return true; 74b1a9862ba1ceb219b6042ff3f8c6ff591867ae26Greg Clayton else if (type != other.type) 75a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return false; 76a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else if (function != other.function) 77a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return false; 7854e7afa84d945f9137f9372ecde432f9e1a702fcGreg Clayton else if (firstVN != other.firstVN) 79a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return false; 80a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else if (secondVN != other.secondVN) 81b1a9862ba1ceb219b6042ff3f8c6ff591867ae26Greg Clayton return false; 82b1a9862ba1ceb219b6042ff3f8c6ff591867ae26Greg Clayton else if (thirdVN != other.thirdVN) 83a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return false; 84a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else { 85b1a9862ba1ceb219b6042ff3f8c6ff591867ae26Greg Clayton if (varargs.size() != other.varargs.size()) 86b1a9862ba1ceb219b6042ff3f8c6ff591867ae26Greg Clayton return false; 87a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham 88a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham for (size_t i = 0; i < varargs.size(); ++i) 89a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham if (varargs[i] != other.varargs[i]) 909c3cfe397d6040a46677e201c2682cc2a5163fe9Eli Friedman return false; 91a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham 92a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return true; 93a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham } 94a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham } 95a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham 96a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham bool operator!=(const Expression &other) const { 97a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham if (opcode != other.opcode) 98a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return true; 99a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else if (opcode == EMPTY || opcode == TOMBSTONE) 100a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return false; 101a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else if (type != other.type) 102b1a9862ba1ceb219b6042ff3f8c6ff591867ae26Greg Clayton return true; 103a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else if (function != other.function) 104a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return true; 105a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else if (firstVN != other.firstVN) 106b1a9862ba1ceb219b6042ff3f8c6ff591867ae26Greg Clayton return true; 107a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else if (secondVN != other.secondVN) 108b1a9862ba1ceb219b6042ff3f8c6ff591867ae26Greg Clayton return true; 109a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else if (thirdVN != other.thirdVN) 110a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return true; 111a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham else { 112a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham if (varargs.size() != other.varargs.size()) 113a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return true; 11454e7afa84d945f9137f9372ecde432f9e1a702fcGreg Clayton 115a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham for (size_t i = 0; i < varargs.size(); ++i) 116a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham if (varargs[i] != other.varargs[i]) 117a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return true; 118a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham 119a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham return false; 120a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham } 121a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham } 122b1a9862ba1ceb219b6042ff3f8c6ff591867ae26Greg Clayton }; 123a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham 124a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham class VISIBILITY_HIDDEN ValueTable { 125a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham private: 126a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham DenseMap<Value*, uint32_t> valueNumbering; 127a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham DenseMap<Expression, uint32_t> expressionNumbering; 128a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham AliasAnalysis* AA; 129a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham 130a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham uint32_t nextValueNumber; 131a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham 132a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 13354e7afa84d945f9137f9372ecde432f9e1a702fcGreg Clayton Expression::ExpressionOpcode getOpcode(CmpInst* C); 13424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression::ExpressionOpcode getOpcode(CastInst* C); 13524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression create_expression(BinaryOperator* BO); 13624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression create_expression(CmpInst* C); 13724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression create_expression(ShuffleVectorInst* V); 13824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression create_expression(ExtractElementInst* C); 13924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression create_expression(InsertElementInst* V); 14024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression create_expression(SelectInst* V); 141a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham Expression create_expression(CastInst* C); 142a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham Expression create_expression(GetElementPtrInst* G); 14354e7afa84d945f9137f9372ecde432f9e1a702fcGreg Clayton Expression create_expression(CallInst* C); 144a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham public: 145a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham ValueTable() : nextValueNumber(1) { } 146a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham uint32_t lookup_or_add(Value* V); 147a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham uint32_t lookup(Value* V) const; 148a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham void add(Value* V, uint32_t num); 149a30baf5b257c7a62c5888679e7c1ac8eb47ca6d7Jim Ingham void clear(); 15024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner void erase(Value* v); 15124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner unsigned size(); 15224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 15324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner }; 15424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 15524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 15624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnernamespace llvm { 15724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnertemplate <> struct DenseMapInfo<Expression> { 15824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner static inline Expression getEmptyKey() { 15924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression(Expression::EMPTY); 16024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 16124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 16224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner static inline Expression getTombstoneKey() { 16324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression(Expression::TOMBSTONE); 16424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 16524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 16624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner static unsigned getHashValue(const Expression e) { 16724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner unsigned hash = e.opcode; 16824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 16924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner hash = e.firstVN + hash * 37; 17024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner hash = e.secondVN + hash * 37; 17124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner hash = e.thirdVN + hash * 37; 17224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 17324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner hash = (unsigned)((uintptr_t)e.type >> 4) ^ 17424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner (unsigned)((uintptr_t)e.type >> 9) + 17524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner hash * 37; 17624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 177c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 178c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham E = e.varargs.end(); I != E; ++I) 179d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton hash = *I + hash * 37; 180d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 181c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham hash = (unsigned)((uintptr_t)e.function >> 4) ^ 182c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham (unsigned)((uintptr_t)e.function >> 9) + 183c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham hash * 37; 184c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham 185c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham return hash; 186c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham } 18724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner static bool isEqual(const Expression &LHS, const Expression &RHS) { 18824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return LHS == RHS; 18924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 19024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner static bool isPod() { return true; } 191d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton}; 192d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton} 19324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 19424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 19524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// ValueTable Internal Functions 19624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 19724943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerExpression::ExpressionOpcode 19824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner ValueTable::getOpcode(BinaryOperator* BO) { 19924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner switch(BO->getOpcode()) { 20024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::Add: 20124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::ADD; 20224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::Sub: 20324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::SUB; 20424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::Mul: 20524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::MUL; 20624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::UDiv: 20724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::UDIV; 20824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::SDiv: 20924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::SDIV; 21024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::FDiv: 21124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FDIV; 21224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::URem: 21324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::UREM; 21424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::SRem: 21524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::SREM; 21624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::FRem: 21724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FREM; 21824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::Shl: 21924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::SHL; 22024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::LShr: 22124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::LSHR; 22224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::AShr: 22324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::ASHR; 224d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton case Instruction::And: 22524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::AND; 22624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::Or: 22724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::OR; 22824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::Xor: 22924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::XOR; 23024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 23124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner // THIS SHOULD NEVER HAPPEN 23224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner default: 23324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner assert(0 && "Binary operator with unknown opcode?"); 23424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::ADD; 235d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton } 23624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 23724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 23824943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerExpression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 239d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton if (C->getOpcode() == Instruction::ICmp) { 24024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner switch (C->getPredicate()) { 24124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case ICmpInst::ICMP_EQ: 24224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::ICMPEQ; 24324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case ICmpInst::ICMP_NE: 244c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham return Expression::ICMPNE; 245c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham case ICmpInst::ICMP_UGT: 246c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham return Expression::ICMPUGT; 247c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham case ICmpInst::ICMP_UGE: 248c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham return Expression::ICMPUGE; 249d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton case ICmpInst::ICMP_ULT: 250c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham return Expression::ICMPULT; 251c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham case ICmpInst::ICMP_ULE: 252c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham return Expression::ICMPULE; 253d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton case ICmpInst::ICMP_SGT: 254d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return Expression::ICMPSGT; 255d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton case ICmpInst::ICMP_SGE: 256c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham return Expression::ICMPSGE; 257c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham case ICmpInst::ICMP_SLT: 258d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return Expression::ICMPSLT; 259c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham case ICmpInst::ICMP_SLE: 26024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::ICMPSLE; 261c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham 262c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham // THIS SHOULD NEVER HAPPEN 26324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner default: 26424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner assert(0 && "Comparison with unknown predicate?"); 26524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::ICMPEQ; 26624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 26724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else { 26824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner switch (C->getPredicate()) { 26924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_OEQ: 27024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPOEQ; 27124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_OGT: 27224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPOGT; 27324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_OGE: 27424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPOGE; 27524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_OLT: 27624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPOLT; 27724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_OLE: 27824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPOLE; 27924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_ONE: 28024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPONE; 28124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_ORD: 28224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPORD; 28324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_UNO: 28424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPUNO; 28524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_UEQ: 28624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPUEQ; 28724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_UGT: 28824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPUGT; 28924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_UGE: 29024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPUGE; 29124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_ULT: 29224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPULT; 29324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_ULE: 29424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPULE; 29524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case FCmpInst::FCMP_UNE: 29624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPUNE; 29724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 29824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner // THIS SHOULD NEVER HAPPEN 29924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner default: 30024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner assert(0 && "Comparison with unknown predicate?"); 30124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FCMPOEQ; 30224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 30324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 30424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 30524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 30624943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerExpression::ExpressionOpcode 30724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner ValueTable::getOpcode(CastInst* C) { 30824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner switch(C->getOpcode()) { 30924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::Trunc: 31024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::TRUNC; 31124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::ZExt: 31224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::ZEXT; 31324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::SExt: 31424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::SEXT; 31524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::FPToUI: 31624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FPTOUI; 31724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::FPToSI: 31824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FPTOSI; 31924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::UIToFP: 32024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::UITOFP; 32124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::SIToFP: 32224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::SITOFP; 32324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::FPTrunc: 32424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FPTRUNC; 32524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner case Instruction::FPExt: 32624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Expression::FPEXT; 327d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton case Instruction::PtrToInt: 328d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return Expression::PTRTOINT; 329d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton case Instruction::IntToPtr: 330d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return Expression::INTTOPTR; 331d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton case Instruction::BitCast: 332d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return Expression::BITCAST; 333d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 334d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton // THIS SHOULD NEVER HAPPEN 335d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton default: 336d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton assert(0 && "Cast operator with unknown opcode?"); 337d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return Expression::BITCAST; 338d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton } 339d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton} 340d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 341d6d806ceff943ca26c008f704013f18920685cfdGreg ClaytonExpression ValueTable::create_expression(CallInst* C) { 342d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton Expression e; 343d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 344d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.type = C->getType(); 345d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.firstVN = 0; 346d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.secondVN = 0; 347d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.thirdVN = 0; 348d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.function = C->getCalledFunction(); 349d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.opcode = Expression::CALL; 350d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 351d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 352d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton I != E; ++I) 353d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.varargs.push_back(lookup_or_add(*I)); 354d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 355d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return e; 356d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton} 357d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 358d6d806ceff943ca26c008f704013f18920685cfdGreg ClaytonExpression ValueTable::create_expression(BinaryOperator* BO) { 359d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton Expression e; 360d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 361d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.firstVN = lookup_or_add(BO->getOperand(0)); 362d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.secondVN = lookup_or_add(BO->getOperand(1)); 363d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.thirdVN = 0; 364d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.function = 0; 365d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.type = BO->getType(); 366d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.opcode = getOpcode(BO); 367d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 368d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return e; 369d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton} 370d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 371d6d806ceff943ca26c008f704013f18920685cfdGreg ClaytonExpression ValueTable::create_expression(CmpInst* C) { 372d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton Expression e; 373d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 374d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.firstVN = lookup_or_add(C->getOperand(0)); 375d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.secondVN = lookup_or_add(C->getOperand(1)); 376d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.thirdVN = 0; 377d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.function = 0; 378d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.type = C->getType(); 379d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.opcode = getOpcode(C); 380d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton 38124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return e; 38224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 38324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 38424943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerExpression ValueTable::create_expression(CastInst* C) { 38524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e; 38624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 38724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.firstVN = lookup_or_add(C->getOperand(0)); 38824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.secondVN = 0; 389d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton e.thirdVN = 0; 39024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.function = 0; 39124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.type = C->getType(); 39224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.opcode = getOpcode(C); 39324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 39424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return e; 39524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 39624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 39724943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerExpression ValueTable::create_expression(ShuffleVectorInst* S) { 39824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e; 39924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 40024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.firstVN = lookup_or_add(S->getOperand(0)); 40124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.secondVN = lookup_or_add(S->getOperand(1)); 40224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.thirdVN = lookup_or_add(S->getOperand(2)); 40324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.function = 0; 40424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.type = S->getType(); 40524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.opcode = Expression::SHUFFLE; 40624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 40724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return e; 40824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 40924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 41024943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerExpression ValueTable::create_expression(ExtractElementInst* E) { 41124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e; 41224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 41324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.firstVN = lookup_or_add(E->getOperand(0)); 41424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.secondVN = lookup_or_add(E->getOperand(1)); 41524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.thirdVN = 0; 41624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.function = 0; 41724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.type = E->getType(); 41824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.opcode = Expression::EXTRACT; 41924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 42024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return e; 42124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 42224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 42324943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerExpression ValueTable::create_expression(InsertElementInst* I) { 42424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e; 42524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 42624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.firstVN = lookup_or_add(I->getOperand(0)); 42724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.secondVN = lookup_or_add(I->getOperand(1)); 42824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.thirdVN = lookup_or_add(I->getOperand(2)); 42924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.function = 0; 43024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.type = I->getType(); 43124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.opcode = Expression::INSERT; 43224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 43324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return e; 43424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 43524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 43624943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerExpression ValueTable::create_expression(SelectInst* I) { 43724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e; 43824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 43924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.firstVN = lookup_or_add(I->getCondition()); 44024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.secondVN = lookup_or_add(I->getTrueValue()); 44124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.thirdVN = lookup_or_add(I->getFalseValue()); 44224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.function = 0; 44324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.type = I->getType(); 44424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.opcode = Expression::SELECT; 44524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 44624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return e; 44724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 44824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 44924943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerExpression ValueTable::create_expression(GetElementPtrInst* G) { 45024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e; 45124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 45224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.firstVN = lookup_or_add(G->getPointerOperand()); 45324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.secondVN = 0; 45424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.thirdVN = 0; 45524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.function = 0; 45624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.type = G->getType(); 45724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.opcode = Expression::GEP; 45824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 45924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 46024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner I != E; ++I) 46124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner e.varargs.push_back(lookup_or_add(*I)); 46224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 46324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return e; 46424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 46524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 46624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 46724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// ValueTable External Functions 46824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 46924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 47024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// lookup_or_add - Returns the value number for the specified value, assigning 47124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// it a new number if it did not have one before. 47224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattneruint32_t ValueTable::lookup_or_add(Value* V) { 47324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 47424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (VI != valueNumbering.end()) 47524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return VI->second; 47624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 47724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (CallInst* C = dyn_cast<CallInst>(V)) { 47824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (C->getCalledFunction() && 47924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner AA->doesNotAccessMemory(C->getCalledFunction())) { 48024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e = create_expression(C); 48124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 48224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 48324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (EI != expressionNumbering.end()) { 48424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, EI->second)); 48524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return EI->second; 48624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else { 48724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 48824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, nextValueNumber)); 48924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 49024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return nextValueNumber++; 49124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 49224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else { 493eddffe93d2c9ebb575e7b03fe1c5e71f9ecaf9f1Caroline Tice valueNumbering.insert(std::make_pair(V, nextValueNumber)); 494eddffe93d2c9ebb575e7b03fe1c5e71f9ecaf9f1Caroline Tice return nextValueNumber++; 495eddffe93d2c9ebb575e7b03fe1c5e71f9ecaf9f1Caroline Tice } 496eddffe93d2c9ebb575e7b03fe1c5e71f9ecaf9f1Caroline Tice } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 497eddffe93d2c9ebb575e7b03fe1c5e71f9ecaf9f1Caroline Tice Expression e = create_expression(BO); 498537a7a86687683fd403ce652d178fbc89e06ef9fGreg Clayton 499e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 50027345db7bc4167078014798032137b0452f4cab9Greg Clayton if (EI != expressionNumbering.end()) { 50127345db7bc4167078014798032137b0452f4cab9Greg Clayton valueNumbering.insert(std::make_pair(V, EI->second)); 502e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice return EI->second; 50327345db7bc4167078014798032137b0452f4cab9Greg Clayton } else { 50427345db7bc4167078014798032137b0452f4cab9Greg Clayton expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 50527345db7bc4167078014798032137b0452f4cab9Greg Clayton valueNumbering.insert(std::make_pair(V, nextValueNumber)); 50627345db7bc4167078014798032137b0452f4cab9Greg Clayton 50727345db7bc4167078014798032137b0452f4cab9Greg Clayton return nextValueNumber++; 50827345db7bc4167078014798032137b0452f4cab9Greg Clayton } 509e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 51027345db7bc4167078014798032137b0452f4cab9Greg Clayton Expression e = create_expression(C); 51127345db7bc4167078014798032137b0452f4cab9Greg Clayton 51227345db7bc4167078014798032137b0452f4cab9Greg Clayton DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 51327345db7bc4167078014798032137b0452f4cab9Greg Clayton if (EI != expressionNumbering.end()) { 51427345db7bc4167078014798032137b0452f4cab9Greg Clayton valueNumbering.insert(std::make_pair(V, EI->second)); 51527345db7bc4167078014798032137b0452f4cab9Greg Clayton return EI->second; 516e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice } else { 51727345db7bc4167078014798032137b0452f4cab9Greg Clayton expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 51827345db7bc4167078014798032137b0452f4cab9Greg Clayton valueNumbering.insert(std::make_pair(V, nextValueNumber)); 51927345db7bc4167078014798032137b0452f4cab9Greg Clayton 52027345db7bc4167078014798032137b0452f4cab9Greg Clayton return nextValueNumber++; 52127345db7bc4167078014798032137b0452f4cab9Greg Clayton } 52227345db7bc4167078014798032137b0452f4cab9Greg Clayton } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 52327345db7bc4167078014798032137b0452f4cab9Greg Clayton Expression e = create_expression(U); 52427345db7bc4167078014798032137b0452f4cab9Greg Clayton 52527345db7bc4167078014798032137b0452f4cab9Greg Clayton DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 52627345db7bc4167078014798032137b0452f4cab9Greg Clayton if (EI != expressionNumbering.end()) { 527e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice valueNumbering.insert(std::make_pair(V, EI->second)); 528e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice return EI->second; 529e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice } else { 530e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 531e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice valueNumbering.insert(std::make_pair(V, nextValueNumber)); 532e9ca3a4130bfb76765256549e01c759da8ec2f1dCaroline Tice 533c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham return nextValueNumber++; 534c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham } 535c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 536c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham Expression e = create_expression(U); 537c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham 538d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 539d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton if (EI != expressionNumbering.end()) { 540d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton valueNumbering.insert(std::make_pair(V, EI->second)); 541d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return EI->second; 542c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham } else { 543c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 544d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton valueNumbering.insert(std::make_pair(V, nextValueNumber)); 545c4547c59f2e8390bdbf92484c851be06395b8e77Jim Ingham 546d6d806ceff943ca26c008f704013f18920685cfdGreg Clayton return nextValueNumber++; 54724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 54824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 54924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e = create_expression(U); 55024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 55124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 55224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (EI != expressionNumbering.end()) { 55324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, EI->second)); 55424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return EI->second; 55524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else { 55624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 55724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, nextValueNumber)); 55824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 55924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return nextValueNumber++; 56024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 56124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 56224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e = create_expression(U); 56324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 56424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 56524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (EI != expressionNumbering.end()) { 56624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, EI->second)); 56724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return EI->second; 56824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else { 56924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 57024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, nextValueNumber)); 57124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 57224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return nextValueNumber++; 57324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 57424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else if (CastInst* U = dyn_cast<CastInst>(V)) { 57524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e = create_expression(U); 57624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 57724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 57824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (EI != expressionNumbering.end()) { 57924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, EI->second)); 58024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return EI->second; 58124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else { 58224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 58324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, nextValueNumber)); 58424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 58524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return nextValueNumber++; 586b586901fb633b898e19bdfc8d605b4e89a3ab5b8Eli Friedman } 58724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 58824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Expression e = create_expression(U); 58924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 59024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 59124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (EI != expressionNumbering.end()) { 59224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, EI->second)); 59324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return EI->second; 59424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else { 59524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 59624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, nextValueNumber)); 59724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 59824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return nextValueNumber++; 59924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 60024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else { 60124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.insert(std::make_pair(V, nextValueNumber)); 60224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return nextValueNumber++; 60324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 60424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 60524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 60624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// lookup - Returns the value number of the specified value. Fails if 60724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// the value has not yet been numbered. 60824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattneruint32_t ValueTable::lookup(Value* V) const { 60924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 61024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (VI != valueNumbering.end()) 61124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return VI->second; 61224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner else 61324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner assert(0 && "Value not numbered?"); 61424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 61524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return 0; 61624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 61724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 61824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// clear - Remove all entries from the ValueTable 61924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnervoid ValueTable::clear() { 62024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.clear(); 62124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner expressionNumbering.clear(); 62224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner nextValueNumber = 1; 62324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 62424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 62524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// erase - Remove a value from the value numbering 62624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnervoid ValueTable::erase(Value* V) { 62724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner valueNumbering.erase(V); 62824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 62924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 63024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 63149ce682dfa7993d31206cea19ce7006cd3f3077eGreg Clayton// ValueNumberedSet Class 63249ce682dfa7993d31206cea19ce7006cd3f3077eGreg Clayton//===----------------------------------------------------------------------===// 63324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnernamespace { 63449ce682dfa7993d31206cea19ce7006cd3f3077eGreg Claytonclass ValueNumberedSet { 63524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner private: 63649ce682dfa7993d31206cea19ce7006cd3f3077eGreg Clayton SmallPtrSet<Value*, 8> contents; 63749ce682dfa7993d31206cea19ce7006cd3f3077eGreg Clayton BitVector numbers; 63824b48ff28b7c60dd4598212c3e77935a0fc1142dGreg Clayton public: 63924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner ValueNumberedSet() { numbers.resize(1); } 64024b48ff28b7c60dd4598212c3e77935a0fc1142dGreg Clayton ValueNumberedSet(const ValueNumberedSet& other) { 64149ce682dfa7993d31206cea19ce7006cd3f3077eGreg Clayton numbers = other.numbers; 64224b48ff28b7c60dd4598212c3e77935a0fc1142dGreg Clayton contents = other.contents; 64349ce682dfa7993d31206cea19ce7006cd3f3077eGreg Clayton } 64424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 64524b48ff28b7c60dd4598212c3e77935a0fc1142dGreg Clayton typedef SmallPtrSet<Value*, 8>::iterator iterator; 64624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 64749ce682dfa7993d31206cea19ce7006cd3f3077eGreg Clayton iterator begin() { return contents.begin(); } 64824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner iterator end() { return contents.end(); } 64924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 65024b48ff28b7c60dd4598212c3e77935a0fc1142dGreg Clayton bool insert(Value* v) { return contents.insert(v); } 65149ce682dfa7993d31206cea19ce7006cd3f3077eGreg Clayton void insert(iterator I, iterator E) { contents.insert(I, E); } 65224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner void erase(Value* v) { contents.erase(v); } 65324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner unsigned count(Value* v) { return contents.count(v); } 65424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner size_t size() { return contents.size(); } 65524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 65624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner void set(unsigned i) { 65724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (i >= numbers.size()) 65824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner numbers.resize(i+1); 65924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 66024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner numbers.set(i); 66124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 66224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 66324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner void operator=(const ValueNumberedSet& other) { 66424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner contents = other.contents; 66524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner numbers = other.numbers; 66624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 66724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 66824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner void reset(unsigned i) { 66924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (i < numbers.size()) 67024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner numbers.reset(i); 67124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 67224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 67324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner bool test(unsigned i) { 67424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (i >= numbers.size()) 67524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return false; 67624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 67724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return numbers.test(i); 67824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 67924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 68024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner void clear() { 68124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner contents.clear(); 68224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner numbers.clear(); 68324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 68424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner}; 68524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 68624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 68724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 68824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// GVN Pass 68924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 690704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton 691704363531ee4877ccc6d35d0702876096f54c67bGreg Claytonnamespace { 692704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton 693704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton class VISIBILITY_HIDDEN GVN : public FunctionPass { 694704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton bool runOnFunction(Function &F); 695704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton public: 696704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton static char ID; // Pass identification, replacement for typeid 697704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton GVN() : FunctionPass((intptr_t)&ID) { } 698704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton 699704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton private: 700704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton ValueTable VN; 701704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton 702704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 703704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton 704704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 705704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton PhiMapType phiMap; 706704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton 707704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton 708704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton // This transformation requires dominator postdominator info 709704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton virtual void getAnalysisUsage(AnalysisUsage &AU) const { 710704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton AU.setPreservesCFG(); 711704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton AU.addRequired<DominatorTree>(); 712704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton AU.addRequired<MemoryDependenceAnalysis>(); 713704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton AU.addRequired<AliasAnalysis>(); 714704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton AU.addPreserved<AliasAnalysis>(); 715704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton AU.addPreserved<MemoryDependenceAnalysis>(); 716704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton } 717704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton 718704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton // Helper fuctions 719704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton // FIXME: eliminate or document these better 720704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 721704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton void val_insert(ValueNumberedSet& s, Value* v); 722704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton bool processLoad(LoadInst* L, 723704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton DenseMap<Value*, LoadInst*>& lastLoad, 724704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton SmallVector<Instruction*, 4>& toErase); 72524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner bool processInstruction(Instruction* I, 72624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner ValueNumberedSet& currAvail, 72724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner DenseMap<Value*, LoadInst*>& lastSeenLoad, 72824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner SmallVector<Instruction*, 4>& toErase); 72924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner bool processNonLocalLoad(LoadInst* L, 73024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner SmallVector<Instruction*, 4>& toErase); 73124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 73224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner DenseMap<BasicBlock*, Value*> &Phis, 73324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner bool top_level = false); 73424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner void dump(DenseMap<BasicBlock*, Value*>& d); 73524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner bool iterateOnFunction(Function &F); 73624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Value* CollapsePhi(PHINode* p); 737704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton bool isSafeReplacement(PHINode* p, Instruction* inst); 73824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner }; 73924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 74024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner char GVN::ID = 0; 74124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 74224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 74324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 74424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// createGVNPass - The public interface to this file... 74524943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerFunctionPass *llvm::createGVNPass() { return new GVN(); } 74624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 74724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnerstatic RegisterPass<GVN> X("gvn", 74824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner "Global Value Numbering"); 74924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 75024943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerSTATISTIC(NumGVNInstr, "Number of instructions deleted"); 75124943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerSTATISTIC(NumGVNLoad, "Number of loads deleted"); 75224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 75324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// find_leader - Given a set and a value number, return the first 75424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// element of the set with that value number, or 0 if no such element 75524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// is present 75624943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerValue* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 75724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (!vals.test(v)) 75824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return 0; 75924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 76024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 761704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton I != E; ++I) 762704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton if (v == VN.lookup(*I)) 763704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton return *I; 764704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton 765704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton assert(0 && "No leader found, but present bit is set?"); 76624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return 0; 767704363531ee4877ccc6d35d0702876096f54c67bGreg Clayton} 76824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 76924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// val_insert - Insert a value into a set only if there is not a value 77024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// with the same value number already in the set 77124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnervoid GVN::val_insert(ValueNumberedSet& s, Value* v) { 77224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner uint32_t num = VN.lookup(v); 77324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (!s.test(num)) 77424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner s.insert(v); 77524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 77654e7afa84d945f9137f9372ecde432f9e1a702fcGreg Clayton 77724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnervoid GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 77824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner printf("{\n"); 77924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 78024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner E = d.end(); I != E; ++I) { 78124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (I->second == MemoryDependenceAnalysis::None) 78224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner printf("None\n"); 78324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner else 78424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner I->second->dump(); 78524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 78624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner printf("}\n"); 78724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner} 78824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 78924943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerValue* GVN::CollapsePhi(PHINode* p) { 7903d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton DominatorTree &DT = getAnalysis<DominatorTree>(); 79124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Value* constVal = p->hasConstantValue(); 79224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 79324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (constVal) { 7943d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton if (Instruction* inst = dyn_cast<Instruction>(constVal)) { 7953d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton if (DT.dominates(inst, p)) 79624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (isSafeReplacement(p, inst)) 7973d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton return inst; 79824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } else { 7993d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton return constVal; 8003d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton } 8013d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton } 8023d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton 8033d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton return 0; 8043d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton} 8053d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Clayton 8063d0e2c2de1b965b6dc171a618ddb8144419ae6f5Greg Claytonbool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 80724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner if (!isa<PHINode>(inst)) 808 return true; 809 810 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 811 UI != E; ++UI) 812 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 813 if (use_phi->getParent() == inst->getParent()) 814 return false; 815 816 return true; 817} 818 819/// GetValueForBlock - Get the value to use within the specified basic block. 820/// available values are in Phis. 821Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 822 DenseMap<BasicBlock*, Value*> &Phis, 823 bool top_level) { 824 825 // If we have already computed this value, return the previously computed val. 826 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 827 if (V != Phis.end() && !top_level) return V->second; 828 829 BasicBlock* singlePred = BB->getSinglePredecessor(); 830 if (singlePred) { 831 Value *ret = GetValueForBlock(singlePred, orig, Phis); 832 Phis[BB] = ret; 833 return ret; 834 } 835 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 836 // now, then get values to fill in the incoming values for the PHI. 837 PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", 838 BB->begin()); 839 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 840 841 if (Phis.count(BB) == 0) 842 Phis.insert(std::make_pair(BB, PN)); 843 844 // Fill in the incoming values for the block. 845 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 846 Value* val = GetValueForBlock(*PI, orig, Phis); 847 848 PN->addIncoming(val, *PI); 849 } 850 851 // Attempt to collapse PHI nodes that are trivially redundant 852 Value* v = CollapsePhi(PN); 853 if (v) { 854 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 855 856 MD.removeInstruction(PN); 857 PN->replaceAllUsesWith(v); 858 859 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 860 E = Phis.end(); I != E; ++I) 861 if (I->second == PN) 862 I->second = v; 863 864 PN->eraseFromParent(); 865 866 Phis[BB] = v; 867 868 return v; 869 } 870 871 // Cache our phi construction results 872 phiMap[orig->getPointerOperand()].insert(PN); 873 return PN; 874} 875 876/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 877/// non-local by performing PHI construction. 878bool GVN::processNonLocalLoad(LoadInst* L, 879 SmallVector<Instruction*, 4>& toErase) { 880 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 881 882 // Find the non-local dependencies of the load 883 DenseMap<BasicBlock*, Value*> deps; 884 MD.getNonLocalDependency(L, deps); 885 886 DenseMap<BasicBlock*, Value*> repl; 887 888 // Filter out useless results (non-locals, etc) 889 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 890 I != E; ++I) 891 if (I->second == MemoryDependenceAnalysis::None) { 892 return false; 893 } else if (I->second == MemoryDependenceAnalysis::NonLocal) { 894 continue; 895 } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 896 if (S->getPointerOperand() == L->getPointerOperand()) 897 repl[I->first] = S->getOperand(0); 898 else 899 return false; 900 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 901 if (LD->getPointerOperand() == L->getPointerOperand()) 902 repl[I->first] = LD; 903 else 904 return false; 905 } else { 906 return false; 907 } 908 909 // Use cached PHI construction information from previous runs 910 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 911 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 912 I != E; ++I) { 913 if ((*I)->getParent() == L->getParent()) { 914 MD.removeInstruction(L); 915 L->replaceAllUsesWith(*I); 916 toErase.push_back(L); 917 NumGVNLoad++; 918 919 return true; 920 } else { 921 repl.insert(std::make_pair((*I)->getParent(), *I)); 922 } 923 } 924 925 // Perform PHI construction 926 SmallPtrSet<BasicBlock*, 4> visited; 927 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 928 929 MD.removeInstruction(L); 930 L->replaceAllUsesWith(v); 931 toErase.push_back(L); 932 NumGVNLoad++; 933 934 return true; 935} 936 937/// processLoad - Attempt to eliminate a load, first by eliminating it 938/// locally, and then attempting non-local elimination if that fails. 939bool GVN::processLoad(LoadInst* L, 940 DenseMap<Value*, LoadInst*>& lastLoad, 941 SmallVector<Instruction*, 4>& toErase) { 942 if (L->isVolatile()) { 943 lastLoad[L->getPointerOperand()] = L; 944 return false; 945 } 946 947 Value* pointer = L->getPointerOperand(); 948 LoadInst*& last = lastLoad[pointer]; 949 950 // ... to a pointer that has been loaded from before... 951 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 952 bool removedNonLocal = false; 953 Instruction* dep = MD.getDependency(L); 954 if (dep == MemoryDependenceAnalysis::NonLocal && 955 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { 956 removedNonLocal = processNonLocalLoad(L, toErase); 957 958 if (!removedNonLocal) 959 last = L; 960 961 return removedNonLocal; 962 } 963 964 965 bool deletedLoad = false; 966 967 // Walk up the dependency chain until we either find 968 // a dependency we can use, or we can't walk any further 969 while (dep != MemoryDependenceAnalysis::None && 970 dep != MemoryDependenceAnalysis::NonLocal && 971 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 972 // ... that depends on a store ... 973 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 974 if (S->getPointerOperand() == pointer) { 975 // Remove it! 976 MD.removeInstruction(L); 977 978 L->replaceAllUsesWith(S->getOperand(0)); 979 toErase.push_back(L); 980 deletedLoad = true; 981 NumGVNLoad++; 982 } 983 984 // Whether we removed it or not, we can't 985 // go any further 986 break; 987 } else if (!last) { 988 // If we don't depend on a store, and we haven't 989 // been loaded before, bail. 990 break; 991 } else if (dep == last) { 992 // Remove it! 993 MD.removeInstruction(L); 994 995 L->replaceAllUsesWith(last); 996 toErase.push_back(L); 997 deletedLoad = true; 998 NumGVNLoad++; 999 1000 break; 1001 } else { 1002 dep = MD.getDependency(L, dep); 1003 } 1004 } 1005 1006 if (!deletedLoad) 1007 last = L; 1008 1009 return deletedLoad; 1010} 1011 1012/// processInstruction - When calculating availability, handle an instruction 1013/// by inserting it into the appropriate sets 1014bool GVN::processInstruction(Instruction* I, 1015 ValueNumberedSet& currAvail, 1016 DenseMap<Value*, LoadInst*>& lastSeenLoad, 1017 SmallVector<Instruction*, 4>& toErase) { 1018 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 1019 return processLoad(L, lastSeenLoad, toErase); 1020 } 1021 1022 unsigned num = VN.lookup_or_add(I); 1023 1024 // Collapse PHI nodes 1025 if (PHINode* p = dyn_cast<PHINode>(I)) { 1026 Value* constVal = CollapsePhi(p); 1027 1028 if (constVal) { 1029 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 1030 PI != PE; ++PI) 1031 if (PI->second.count(p)) 1032 PI->second.erase(p); 1033 1034 p->replaceAllUsesWith(constVal); 1035 toErase.push_back(p); 1036 } 1037 // Perform value-number based elimination 1038 } else if (currAvail.test(num)) { 1039 Value* repl = find_leader(currAvail, num); 1040 1041 VN.erase(I); 1042 I->replaceAllUsesWith(repl); 1043 toErase.push_back(I); 1044 return true; 1045 } else if (!I->isTerminator()) { 1046 currAvail.set(num); 1047 currAvail.insert(I); 1048 } 1049 1050 return false; 1051} 1052 1053// GVN::runOnFunction - This is the main transformation entry point for a 1054// function. 1055// 1056bool GVN::runOnFunction(Function& F) { 1057 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 1058 1059 bool changed = false; 1060 bool shouldContinue = true; 1061 1062 while (shouldContinue) { 1063 shouldContinue = iterateOnFunction(F); 1064 changed |= shouldContinue; 1065 } 1066 1067 return changed; 1068} 1069 1070 1071// GVN::iterateOnFunction - Executes one iteration of GVN 1072bool GVN::iterateOnFunction(Function &F) { 1073 // Clean out global sets from any previous functions 1074 VN.clear(); 1075 availableOut.clear(); 1076 phiMap.clear(); 1077 1078 bool changed_function = false; 1079 1080 DominatorTree &DT = getAnalysis<DominatorTree>(); 1081 1082 SmallVector<Instruction*, 4> toErase; 1083 1084 // Top-down walk of the dominator tree 1085 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 1086 E = df_end(DT.getRootNode()); DI != E; ++DI) { 1087 1088 // Get the set to update for this block 1089 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 1090 DenseMap<Value*, LoadInst*> lastSeenLoad; 1091 1092 BasicBlock* BB = DI->getBlock(); 1093 1094 // A block inherits AVAIL_OUT from its dominator 1095 if (DI->getIDom() != 0) 1096 currAvail = availableOut[DI->getIDom()->getBlock()]; 1097 1098 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 1099 BI != BE; ) { 1100 changed_function |= processInstruction(BI, currAvail, 1101 lastSeenLoad, toErase); 1102 1103 NumGVNInstr += toErase.size(); 1104 1105 // Avoid iterator invalidation 1106 ++BI; 1107 1108 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 1109 E = toErase.end(); I != E; ++I) 1110 (*I)->eraseFromParent(); 1111 1112 toErase.clear(); 1113 } 1114 } 1115 1116 return changed_function; 1117} 1118