GVN.cpp revision 9528f11481e6840a10442733f1dc45c04b79d596
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===- GVN.cpp - Eliminate redundant values and loads ------------===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file was developed by the Owen Anderson and is distributed under 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the University of Illinois Open Source License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This pass performs global value numbering to eliminate fully redundant 11868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// instructions. It also performs simple dead load elimination. 121320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 149ab5563a3196760eb381d102cbb2bc0f7abc6a50Ben Murdoch 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_TYPE "gvn" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Transforms/Scalar.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/BasicBlock.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Constants.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/DerivedTypes.h" 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Function.h" 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Instructions.h" 23c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Value.h" 24c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Analysis/Dominators.h" 25c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/ADT/BitVector.h" 26c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/ADT/DenseMap.h" 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/DepthFirstIterator.h" 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/SmallPtrSet.h" 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/SmallVector.h" 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/Statistic.h" 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Analysis/MemoryDependenceAnalysis.h" 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/CFG.h" 33868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "llvm/Support/Compiler.h" 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace llvm; 35868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ValueTable Class 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 39868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 40868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)/// This class holds the mapping between values and value numbers. It is used 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// as an efficient mechanism to determine the expression-wise equivalence of 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// two values. 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 446e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) struct VISIBILITY_HIDDEN Expression { 456e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 51868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 53868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY, 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TOMBSTONE }; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 57868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ExpressionOpcode opcode; 58868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) const Type* type; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t firstVN; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t secondVN; 61868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) uint32_t thirdVN; 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SmallVector<uint32_t, 4> varargs; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression() { } 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression(ExpressionOpcode o) : opcode(o) { } 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator==(const Expression &other) const { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (opcode != other.opcode) 696e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) return false; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (opcode == EMPTY || opcode == TOMBSTONE) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (type != other.type) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (firstVN != other.firstVN) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (secondVN != other.secondVN) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (thirdVN != other.thirdVN) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (varargs.size() != other.varargs.size()) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < varargs.size(); ++i) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (varargs[i] != other.varargs[i]) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 90c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator!=(const Expression &other) const { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (opcode != other.opcode) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (opcode == EMPTY || opcode == TOMBSTONE) 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (type != other.type) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (firstVN != other.firstVN) 100c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (secondVN != other.secondVN) 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else if (thirdVN != other.thirdVN) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else { 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (varargs.size() != other.varargs.size()) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < varargs.size(); ++i) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (varargs[i] != other.varargs[i]) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) class VISIBILITY_HIDDEN ValueTable { 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DenseMap<Value*, uint32_t> valueNumbering; 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DenseMap<Expression, uint32_t> expressionNumbering; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t nextValueNumber; 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression::ExpressionOpcode getOpcode(CmpInst* C); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression::ExpressionOpcode getOpcode(CastInst* C); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression create_expression(BinaryOperator* BO); 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression create_expression(CmpInst* C); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression create_expression(ShuffleVectorInst* V); 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression create_expression(ExtractElementInst* C); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression create_expression(InsertElementInst* V); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression create_expression(SelectInst* V); 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression create_expression(CastInst* C); 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Expression create_expression(GetElementPtrInst* G); 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ValueTable() { nextValueNumber = 1; } 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t lookup_or_add(Value* V); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t lookup(Value* V) const; 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void add(Value* V, uint32_t num); 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void clear(); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void erase(Value* v); 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned size(); 1447dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch }; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace llvm { 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <> struct DenseMapKeyInfo<Expression> { 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline Expression getEmptyKey() { 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression(Expression::EMPTY); 151868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 153868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) static inline Expression getTombstoneKey() { 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression(Expression::TOMBSTONE); 155868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static unsigned getHashValue(const Expression e) { 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned hash = e.opcode; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) hash = e.firstVN + hash * 37; 161868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) hash = e.secondVN + hash * 37; 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) hash = e.thirdVN + hash * 37; 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) hash = (unsigned)((uintptr_t)e.type >> 4) ^ 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (unsigned)((uintptr_t)e.type >> 9) + 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) hash * 37; 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) E = e.varargs.end(); I != E; ++I) 17068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) hash = *I + hash * 37; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return hash; 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static bool isPod() { return true; } 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ValueTable Internal Functions 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Expression::ExpressionOpcode 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ValueTable::getOpcode(BinaryOperator* BO) { 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch(BO->getOpcode()) { 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::Add: 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::ADD; 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::Sub: 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::SUB; 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::Mul: 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::MUL; 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::UDiv: 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::UDIV; 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::SDiv: 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::SDIV; 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::FDiv: 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::FDIV; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::URem: 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::UREM; 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::SRem: 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::SREM; 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::FRem: 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::FREM; 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::Shl: 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::SHL; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::LShr: 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::LSHR; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::AShr: 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::ASHR; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::And: 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::AND; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::Or: 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::OR; 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Instruction::Xor: 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Expression::XOR; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215 // THIS SHOULD NEVER HAPPEN 216 default: 217 assert(0 && "Binary operator with unknown opcode?"); 218 return Expression::ADD; 219 } 220} 221 222Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 223 if (C->getOpcode() == Instruction::ICmp) { 224 switch (C->getPredicate()) { 225 case ICmpInst::ICMP_EQ: 226 return Expression::ICMPEQ; 227 case ICmpInst::ICMP_NE: 228 return Expression::ICMPNE; 229 case ICmpInst::ICMP_UGT: 230 return Expression::ICMPUGT; 231 case ICmpInst::ICMP_UGE: 232 return Expression::ICMPUGE; 233 case ICmpInst::ICMP_ULT: 234 return Expression::ICMPULT; 235 case ICmpInst::ICMP_ULE: 236 return Expression::ICMPULE; 237 case ICmpInst::ICMP_SGT: 238 return Expression::ICMPSGT; 239 case ICmpInst::ICMP_SGE: 240 return Expression::ICMPSGE; 241 case ICmpInst::ICMP_SLT: 242 return Expression::ICMPSLT; 243 case ICmpInst::ICMP_SLE: 244 return Expression::ICMPSLE; 245 246 // THIS SHOULD NEVER HAPPEN 247 default: 248 assert(0 && "Comparison with unknown predicate?"); 249 return Expression::ICMPEQ; 250 } 251 } else { 252 switch (C->getPredicate()) { 253 case FCmpInst::FCMP_OEQ: 254 return Expression::FCMPOEQ; 255 case FCmpInst::FCMP_OGT: 256 return Expression::FCMPOGT; 257 case FCmpInst::FCMP_OGE: 258 return Expression::FCMPOGE; 259 case FCmpInst::FCMP_OLT: 260 return Expression::FCMPOLT; 261 case FCmpInst::FCMP_OLE: 262 return Expression::FCMPOLE; 263 case FCmpInst::FCMP_ONE: 264 return Expression::FCMPONE; 265 case FCmpInst::FCMP_ORD: 266 return Expression::FCMPORD; 267 case FCmpInst::FCMP_UNO: 268 return Expression::FCMPUNO; 269 case FCmpInst::FCMP_UEQ: 270 return Expression::FCMPUEQ; 271 case FCmpInst::FCMP_UGT: 272 return Expression::FCMPUGT; 273 case FCmpInst::FCMP_UGE: 274 return Expression::FCMPUGE; 275 case FCmpInst::FCMP_ULT: 276 return Expression::FCMPULT; 277 case FCmpInst::FCMP_ULE: 278 return Expression::FCMPULE; 279 case FCmpInst::FCMP_UNE: 280 return Expression::FCMPUNE; 281 282 // THIS SHOULD NEVER HAPPEN 283 default: 284 assert(0 && "Comparison with unknown predicate?"); 285 return Expression::FCMPOEQ; 286 } 287 } 288} 289 290Expression::ExpressionOpcode 291 ValueTable::getOpcode(CastInst* C) { 292 switch(C->getOpcode()) { 293 case Instruction::Trunc: 294 return Expression::TRUNC; 295 case Instruction::ZExt: 296 return Expression::ZEXT; 297 case Instruction::SExt: 298 return Expression::SEXT; 299 case Instruction::FPToUI: 300 return Expression::FPTOUI; 301 case Instruction::FPToSI: 302 return Expression::FPTOSI; 303 case Instruction::UIToFP: 304 return Expression::UITOFP; 305 case Instruction::SIToFP: 306 return Expression::SITOFP; 307 case Instruction::FPTrunc: 308 return Expression::FPTRUNC; 309 case Instruction::FPExt: 310 return Expression::FPEXT; 311 case Instruction::PtrToInt: 312 return Expression::PTRTOINT; 313 case Instruction::IntToPtr: 314 return Expression::INTTOPTR; 315 case Instruction::BitCast: 316 return Expression::BITCAST; 317 318 // THIS SHOULD NEVER HAPPEN 319 default: 320 assert(0 && "Cast operator with unknown opcode?"); 321 return Expression::BITCAST; 322 } 323} 324 325Expression ValueTable::create_expression(BinaryOperator* BO) { 326 Expression e; 327 328 e.firstVN = lookup_or_add(BO->getOperand(0)); 329 e.secondVN = lookup_or_add(BO->getOperand(1)); 330 e.thirdVN = 0; 331 e.type = BO->getType(); 332 e.opcode = getOpcode(BO); 333 334 return e; 335} 336 337Expression ValueTable::create_expression(CmpInst* C) { 338 Expression e; 339 340 e.firstVN = lookup_or_add(C->getOperand(0)); 341 e.secondVN = lookup_or_add(C->getOperand(1)); 342 e.thirdVN = 0; 343 e.type = C->getType(); 344 e.opcode = getOpcode(C); 345 346 return e; 347} 348 349Expression ValueTable::create_expression(CastInst* C) { 350 Expression e; 351 352 e.firstVN = lookup_or_add(C->getOperand(0)); 353 e.secondVN = 0; 354 e.thirdVN = 0; 355 e.type = C->getType(); 356 e.opcode = getOpcode(C); 357 358 return e; 359} 360 361Expression ValueTable::create_expression(ShuffleVectorInst* S) { 362 Expression e; 363 364 e.firstVN = lookup_or_add(S->getOperand(0)); 365 e.secondVN = lookup_or_add(S->getOperand(1)); 366 e.thirdVN = lookup_or_add(S->getOperand(2)); 367 e.type = S->getType(); 368 e.opcode = Expression::SHUFFLE; 369 370 return e; 371} 372 373Expression ValueTable::create_expression(ExtractElementInst* E) { 374 Expression e; 375 376 e.firstVN = lookup_or_add(E->getOperand(0)); 377 e.secondVN = lookup_or_add(E->getOperand(1)); 378 e.thirdVN = 0; 379 e.type = E->getType(); 380 e.opcode = Expression::EXTRACT; 381 382 return e; 383} 384 385Expression ValueTable::create_expression(InsertElementInst* I) { 386 Expression e; 387 388 e.firstVN = lookup_or_add(I->getOperand(0)); 389 e.secondVN = lookup_or_add(I->getOperand(1)); 390 e.thirdVN = lookup_or_add(I->getOperand(2)); 391 e.type = I->getType(); 392 e.opcode = Expression::INSERT; 393 394 return e; 395} 396 397Expression ValueTable::create_expression(SelectInst* I) { 398 Expression e; 399 400 e.firstVN = lookup_or_add(I->getCondition()); 401 e.secondVN = lookup_or_add(I->getTrueValue()); 402 e.thirdVN = lookup_or_add(I->getFalseValue()); 403 e.type = I->getType(); 404 e.opcode = Expression::SELECT; 405 406 return e; 407} 408 409Expression ValueTable::create_expression(GetElementPtrInst* G) { 410 Expression e; 411 412 e.firstVN = lookup_or_add(G->getPointerOperand()); 413 e.secondVN = 0; 414 e.thirdVN = 0; 415 e.type = G->getType(); 416 e.opcode = Expression::GEP; 417 418 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 419 I != E; ++I) 420 e.varargs.push_back(lookup_or_add(*I)); 421 422 return e; 423} 424 425//===----------------------------------------------------------------------===// 426// ValueTable External Functions 427//===----------------------------------------------------------------------===// 428 429/// lookup_or_add - Returns the value number for the specified value, assigning 430/// it a new number if it did not have one before. 431uint32_t ValueTable::lookup_or_add(Value* V) { 432 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 433 if (VI != valueNumbering.end()) 434 return VI->second; 435 436 437 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 438 Expression e = create_expression(BO); 439 440 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 441 if (EI != expressionNumbering.end()) { 442 valueNumbering.insert(std::make_pair(V, EI->second)); 443 return EI->second; 444 } else { 445 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 446 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 447 448 return nextValueNumber++; 449 } 450 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 451 Expression e = create_expression(C); 452 453 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 454 if (EI != expressionNumbering.end()) { 455 valueNumbering.insert(std::make_pair(V, EI->second)); 456 return EI->second; 457 } else { 458 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 459 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 460 461 return nextValueNumber++; 462 } 463 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 464 Expression e = create_expression(U); 465 466 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 467 if (EI != expressionNumbering.end()) { 468 valueNumbering.insert(std::make_pair(V, EI->second)); 469 return EI->second; 470 } else { 471 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 472 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 473 474 return nextValueNumber++; 475 } 476 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 477 Expression e = create_expression(U); 478 479 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 480 if (EI != expressionNumbering.end()) { 481 valueNumbering.insert(std::make_pair(V, EI->second)); 482 return EI->second; 483 } else { 484 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 485 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 486 487 return nextValueNumber++; 488 } 489 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 490 Expression e = create_expression(U); 491 492 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 493 if (EI != expressionNumbering.end()) { 494 valueNumbering.insert(std::make_pair(V, EI->second)); 495 return EI->second; 496 } else { 497 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 498 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 499 500 return nextValueNumber++; 501 } 502 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 503 Expression e = create_expression(U); 504 505 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 506 if (EI != expressionNumbering.end()) { 507 valueNumbering.insert(std::make_pair(V, EI->second)); 508 return EI->second; 509 } else { 510 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 511 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 512 513 return nextValueNumber++; 514 } 515 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 516 Expression e = create_expression(U); 517 518 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 519 if (EI != expressionNumbering.end()) { 520 valueNumbering.insert(std::make_pair(V, EI->second)); 521 return EI->second; 522 } else { 523 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 524 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 525 526 return nextValueNumber++; 527 } 528 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 529 Expression e = create_expression(U); 530 531 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 532 if (EI != expressionNumbering.end()) { 533 valueNumbering.insert(std::make_pair(V, EI->second)); 534 return EI->second; 535 } else { 536 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 537 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 538 539 return nextValueNumber++; 540 } 541 } else { 542 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 543 return nextValueNumber++; 544 } 545} 546 547/// lookup - Returns the value number of the specified value. Fails if 548/// the value has not yet been numbered. 549uint32_t ValueTable::lookup(Value* V) const { 550 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 551 if (VI != valueNumbering.end()) 552 return VI->second; 553 else 554 assert(0 && "Value not numbered?"); 555 556 return 0; 557} 558 559/// clear - Remove all entries from the ValueTable 560void ValueTable::clear() { 561 valueNumbering.clear(); 562 expressionNumbering.clear(); 563 nextValueNumber = 1; 564} 565 566/// erase - Remove a value from the value numbering 567void ValueTable::erase(Value* V) { 568 valueNumbering.erase(V); 569} 570 571//===----------------------------------------------------------------------===// 572// ValueNumberedSet Class 573//===----------------------------------------------------------------------===// 574namespace { 575class ValueNumberedSet { 576 private: 577 SmallPtrSet<Value*, 8> contents; 578 BitVector numbers; 579 public: 580 ValueNumberedSet() { numbers.resize(1); } 581 ValueNumberedSet(const ValueNumberedSet& other) { 582 numbers = other.numbers; 583 contents = other.contents; 584 } 585 586 typedef SmallPtrSet<Value*, 8>::iterator iterator; 587 588 iterator begin() { return contents.begin(); } 589 iterator end() { return contents.end(); } 590 591 bool insert(Value* v) { return contents.insert(v); } 592 void insert(iterator I, iterator E) { contents.insert(I, E); } 593 void erase(Value* v) { contents.erase(v); } 594 unsigned count(Value* v) { return contents.count(v); } 595 size_t size() { return contents.size(); } 596 597 void set(unsigned i) { 598 if (i >= numbers.size()) 599 numbers.resize(i+1); 600 601 numbers.set(i); 602 } 603 604 void operator=(const ValueNumberedSet& other) { 605 contents = other.contents; 606 numbers = other.numbers; 607 } 608 609 void reset(unsigned i) { 610 if (i < numbers.size()) 611 numbers.reset(i); 612 } 613 614 bool test(unsigned i) { 615 if (i >= numbers.size()) 616 return false; 617 618 return numbers.test(i); 619 } 620 621 void clear() { 622 contents.clear(); 623 numbers.clear(); 624 } 625}; 626} 627 628//===----------------------------------------------------------------------===// 629// GVN Pass 630//===----------------------------------------------------------------------===// 631 632namespace { 633 634 class VISIBILITY_HIDDEN GVN : public FunctionPass { 635 bool runOnFunction(Function &F); 636 public: 637 static char ID; // Pass identification, replacement for typeid 638 GVN() : FunctionPass((intptr_t)&ID) { } 639 640 private: 641 ValueTable VN; 642 643 DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 644 645 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 646 PhiMapType phiMap; 647 648 649 // This transformation requires dominator postdominator info 650 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 651 AU.setPreservesCFG(); 652 AU.addRequired<DominatorTree>(); 653 AU.addRequired<MemoryDependenceAnalysis>(); 654 AU.addPreserved<MemoryDependenceAnalysis>(); 655 } 656 657 // Helper fuctions 658 // FIXME: eliminate or document these better 659 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 660 void val_insert(ValueNumberedSet& s, Value* v); 661 bool processLoad(LoadInst* L, 662 DenseMap<Value*, LoadInst*>& lastLoad, 663 SmallVector<Instruction*, 4>& toErase); 664 bool processInstruction(Instruction* I, 665 ValueNumberedSet& currAvail, 666 DenseMap<Value*, LoadInst*>& lastSeenLoad, 667 SmallVector<Instruction*, 4>& toErase); 668 bool processNonLocalLoad(LoadInst* L, 669 SmallVector<Instruction*, 4>& toErase); 670 Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 671 DenseMap<BasicBlock*, Value*> &Phis, 672 bool top_level = false); 673 void dump(DenseMap<BasicBlock*, Value*>& d); 674 }; 675 676 char GVN::ID = 0; 677 678} 679 680// createGVNPass - The public interface to this file... 681FunctionPass *llvm::createGVNPass() { return new GVN(); } 682 683static RegisterPass<GVN> X("gvn", 684 "Global Value Numbering"); 685 686STATISTIC(NumGVNInstr, "Number of instructions deleted"); 687STATISTIC(NumGVNLoad, "Number of loads deleted"); 688 689/// find_leader - Given a set and a value number, return the first 690/// element of the set with that value number, or 0 if no such element 691/// is present 692Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 693 if (!vals.test(v)) 694 return 0; 695 696 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 697 I != E; ++I) 698 if (v == VN.lookup(*I)) 699 return *I; 700 701 assert(0 && "No leader found, but present bit is set?"); 702 return 0; 703} 704 705/// val_insert - Insert a value into a set only if there is not a value 706/// with the same value number already in the set 707void GVN::val_insert(ValueNumberedSet& s, Value* v) { 708 uint32_t num = VN.lookup(v); 709 if (!s.test(num)) 710 s.insert(v); 711} 712 713void GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 714 printf("{\n"); 715 for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 716 E = d.end(); I != E; ++I) { 717 if (I->second == MemoryDependenceAnalysis::None) 718 printf("None\n"); 719 else 720 I->second->dump(); 721 } 722 printf("}\n"); 723} 724 725 726/// GetValueForBlock - Get the value to use within the specified basic block. 727/// available values are in Phis. 728Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 729 DenseMap<BasicBlock*, Value*> &Phis, 730 bool top_level) { 731 732 // If we have already computed this value, return the previously computed val. 733 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 734 if (V != Phis.end() && !top_level) return V->second; 735 736 BasicBlock* singlePred = BB->getSinglePredecessor(); 737 if (singlePred) { 738 Value *ret = GetValueForBlock(singlePred, orig, Phis); 739 Phis[BB] = ret; 740 return ret; 741 } 742 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 743 // now, then get values to fill in the incoming values for the PHI. 744 PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", 745 BB->begin()); 746 PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 747 748 if (Phis.count(BB) == 0) 749 Phis.insert(std::make_pair(BB, PN)); 750 751 bool all_same = true; 752 Value* first = 0; 753 754 // Fill in the incoming values for the block. 755 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 756 Value* val = GetValueForBlock(*PI, orig, Phis); 757 if (first == 0) 758 first = val; 759 else if (all_same && first != val) 760 all_same = false; 761 762 PN->addIncoming(val, *PI); 763 } 764 765 if (all_same) { 766 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 767 768 MD.removeInstruction(PN); 769 PN->replaceAllUsesWith(first); 770 771 SmallVector<BasicBlock*, 4> toRemove; 772 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 773 E = Phis.end(); I != E; ++I) 774 if (I->second == PN) 775 toRemove.push_back(I->first); 776 for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(), 777 E= toRemove.end(); I != E; ++I) 778 Phis[*I] = first; 779 780 PN->eraseFromParent(); 781 782 Phis[BB] = first; 783 784 return first; 785 } 786 787 phiMap[orig->getPointerOperand()].insert(PN); 788 return PN; 789} 790 791bool GVN::processNonLocalLoad(LoadInst* L, 792 SmallVector<Instruction*, 4>& toErase) { 793 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 794 795 DenseMap<BasicBlock*, Value*> deps; 796 MD.getNonLocalDependency(L, deps); 797 798 DenseMap<BasicBlock*, Value*> repl; 799 800 for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 801 I != E; ++I) 802 if (I->second == MemoryDependenceAnalysis::None) { 803 return false; 804 } else if (I->second == MemoryDependenceAnalysis::NonLocal) { 805 continue; 806 }else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 807 if (S->getPointerOperand() == L->getPointerOperand()) 808 repl[I->first] = S->getOperand(0); 809 else 810 return false; 811 } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 812 if (LD->getPointerOperand() == L->getPointerOperand()) 813 repl[I->first] = LD; 814 else 815 return false; 816 } else { 817 return false; 818 } 819 820 SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()]; 821 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 822 I != E; ++I) { 823 if ((*I)->getParent() == L->getParent()) { 824 MD.removeInstruction(L); 825 L->replaceAllUsesWith(*I); 826 toErase.push_back(L); 827 NumGVNLoad++; 828 829 return true; 830 } else { 831 repl.insert(std::make_pair((*I)->getParent(), *I)); 832 } 833 } 834 835 SmallPtrSet<BasicBlock*, 4> visited; 836 Value* v = GetValueForBlock(L->getParent(), L, repl, true); 837 838 MD.removeInstruction(L); 839 L->replaceAllUsesWith(v); 840 toErase.push_back(L); 841 NumGVNLoad++; 842 843 return true; 844} 845 846bool GVN::processLoad(LoadInst* L, 847 DenseMap<Value*, LoadInst*>& lastLoad, 848 SmallVector<Instruction*, 4>& toErase) { 849 if (L->isVolatile()) { 850 lastLoad[L->getPointerOperand()] = L; 851 return false; 852 } 853 854 Value* pointer = L->getPointerOperand(); 855 LoadInst*& last = lastLoad[pointer]; 856 857 // ... to a pointer that has been loaded from before... 858 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 859 Instruction* dep = MD.getDependency(L); 860 if (dep == MemoryDependenceAnalysis::NonLocal && 861 L->getParent() != &L->getParent()->getParent()->getEntryBlock()) 862 processNonLocalLoad(L, toErase); 863 bool deletedLoad = false; 864 865 while (dep != MemoryDependenceAnalysis::None && 866 dep != MemoryDependenceAnalysis::NonLocal && 867 (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 868 // ... that depends on a store ... 869 if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 870 if (S->getPointerOperand() == pointer) { 871 // Remove it! 872 MD.removeInstruction(L); 873 874 L->replaceAllUsesWith(S->getOperand(0)); 875 toErase.push_back(L); 876 deletedLoad = true; 877 NumGVNLoad++; 878 } 879 880 // Whether we removed it or not, we can't 881 // go any further 882 break; 883 } else if (!last) { 884 // If we don't depend on a store, and we haven't 885 // been loaded before, bail. 886 break; 887 } else if (dep == last) { 888 // Remove it! 889 MD.removeInstruction(L); 890 891 L->replaceAllUsesWith(last); 892 toErase.push_back(L); 893 deletedLoad = true; 894 NumGVNLoad++; 895 896 break; 897 } else { 898 dep = MD.getDependency(L, dep); 899 } 900 } 901 902 if (!deletedLoad) 903 last = L; 904 905 return deletedLoad; 906} 907 908/// buildsets_availout - When calculating availability, handle an instruction 909/// by inserting it into the appropriate sets 910bool GVN::processInstruction(Instruction* I, 911 ValueNumberedSet& currAvail, 912 DenseMap<Value*, LoadInst*>& lastSeenLoad, 913 SmallVector<Instruction*, 4>& toErase) { 914 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 915 return processLoad(L, lastSeenLoad, toErase); 916 } 917 918 unsigned num = VN.lookup_or_add(I); 919 920 if (currAvail.test(num)) { 921 Value* repl = find_leader(currAvail, num); 922 923 VN.erase(I); 924 I->replaceAllUsesWith(repl); 925 toErase.push_back(I); 926 return true; 927 } else if (!I->isTerminator()) { 928 currAvail.set(num); 929 currAvail.insert(I); 930 } 931 932 return false; 933} 934 935// GVN::runOnFunction - This is the main transformation entry point for a 936// function. 937// 938bool GVN::runOnFunction(Function &F) { 939 // Clean out global sets from any previous functions 940 VN.clear(); 941 availableOut.clear(); 942 phiMap.clear(); 943 944 bool changed_function = false; 945 946 DominatorTree &DT = getAnalysis<DominatorTree>(); 947 948 SmallVector<Instruction*, 4> toErase; 949 950 // Top-down walk of the dominator tree 951 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 952 E = df_end(DT.getRootNode()); DI != E; ++DI) { 953 954 // Get the set to update for this block 955 ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 956 DenseMap<Value*, LoadInst*> lastSeenLoad; 957 958 BasicBlock* BB = DI->getBlock(); 959 960 // A block inherits AVAIL_OUT from its dominator 961 if (DI->getIDom() != 0) 962 currAvail = availableOut[DI->getIDom()->getBlock()]; 963 964 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 965 BI != BE; ) { 966 changed_function |= processInstruction(BI, currAvail, 967 lastSeenLoad, toErase); 968 969 NumGVNInstr += toErase.size(); 970 971 // Avoid iterator invalidation 972 ++BI; 973 974 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 975 E = toErase.end(); I != E; ++I) 976 (*I)->eraseFromParent(); 977 978 toErase.clear(); 979 } 980 } 981 982 return changed_function; 983} 984