GVN.cpp revision 054ab94bff7827b8004465b75dfe0d539568621a
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com//===- GVN.cpp - Eliminate redundant values and loads ------------===// 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// The LLVM Compiler Infrastructure 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// This file was developed by the Owen Anderson and is distributed under 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// the University of Illinois Open Source License. See LICENSE.TXT for details. 7971d0c8049c6bfc7a58f0b41f8f59f9ec9ca077bbsalomon@google.com// 857f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com//===----------------------------------------------------------------------===// 957f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com// 1057f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com// This pass performs global value numbering to eliminate fully redundant 1157f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com// instructions. It also performs simple dead load elimination. 1257f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com// 1357f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com//===----------------------------------------------------------------------===// 1457f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com 1557f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com#define DEBUG_TYPE "gvn" 16b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com 176f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com#include "llvm/Transforms/Scalar.h" 1837269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com#include "llvm/BasicBlock.h" 197bc13a62609149f0b535c2f3ff7210eb834d8b36epoger@google.com#include "llvm/Constants.h" 205f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com#include "llvm/DerivedTypes.h" 21b9b9a18ab459c2616ac4a52c9f8cc0637d284229reed@android.com#include "llvm/Function.h" 22d9ba9a05d6f5766fdb1378b6ed84c0659009a8dascroggo@google.com#include "llvm/Instructions.h" 238a85d0c4938173476d037d7af0ee3b9436a1234ereed@google.com#include "llvm/Value.h" 244370aedf7f55af74e9ebb4ad1c2e010c08236dfajunov@google.com#include "llvm/Analysis/Dominators.h" 25971d0c8049c6bfc7a58f0b41f8f59f9ec9ca077bbsalomon@google.com#include "llvm/ADT/BitVector.h" 265e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org#include "llvm/ADT/DenseMap.h" 27de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com#include "llvm/ADT/DepthFirstIterator.h" 28c41295d1223136da4f9e4c65b7145360684ede4bcommit-bot@chromium.org#include "llvm/ADT/SmallPtrSet.h" 295af9b2032b552516c9223d9fb22185b022b13c62scroggo@google.com#include "llvm/ADT/SmallVector.h" 308015dd83ae37147bb630d4751030868051ad0caereed@android.com#include "llvm/ADT/Statistic.h" 318015dd83ae37147bb630d4751030868051ad0caereed@android.com#include "llvm/Analysis/MemoryDependenceAnalysis.h" 328015dd83ae37147bb630d4751030868051ad0caereed@android.com#include "llvm/Support/CFG.h" 33e3bb3bce3e9c1f3bc8ee779b1b3383c18e560bcecommit-bot@chromium.org#include "llvm/Support/Compiler.h" 34e8ebeb1f8fde6525bbab988c6090a5d3ab19855bepoger@google.comusing namespace llvm; 350dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org 369875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com//===----------------------------------------------------------------------===// 37977b9c8af3ef1b9a2fa2a0037cf3734cf2ba13d9robertphillips@google.com// ValueTable Class 385e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org//===----------------------------------------------------------------------===// 3972c9672ce274a3b6cb40800d66374edf25b157a3scroggo@google.com 40f711f320a34216fc9f64839b90b99a1492c54e09epoger@google.com/// This class holds the mapping between values and value numbers. It is used 412a48c3adb7cf4fc754f99a41352210b4a99edf04bsalomon@google.com/// as an efficient mechanism to determine the expression-wise equivalence of 42310478e72c63e639373465216271b81f1e4a9136epoger@google.com/// two values. 433cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.orgnamespace { 4472c9672ce274a3b6cb40800d66374edf25b157a3scroggo@google.com struct VISIBILITY_HIDDEN Expression { 450770044da6d61dcbc8d9673fed8dd92460faa314reed@google.com enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM, 46515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 47515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 48515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 49515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 50515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 51515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 52ed5eb4ef2aa1d6c705bc3ed466f9caba2a230a2bepoger@google.com SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 53ed5eb4ef2aa1d6c705bc3ed466f9caba2a230a2bepoger@google.com FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 54cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY, 55cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com TOMBSTONE }; 56cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com 57cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com ExpressionOpcode opcode; 586f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com const Type* type; 596f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com uint32_t firstVN; 606f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com uint32_t secondVN; 61cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com uint32_t thirdVN; 6280724dfeb320d1152128cd33636c9024952432d3epoger@google.com SmallVector<uint32_t, 4> varargs; 63cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com 64123ac1d4eab757052407064623643fdc59f85363bsalomon@google.com Expression() { } 65cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com Expression(ExpressionOpcode o) : opcode(o) { } 66cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com 67cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com bool operator==(const Expression &other) const { 6876c913db20de7ae1baa49ae66e943bf7f40781ccepoger@google.com if (opcode != other.opcode) 6976c913db20de7ae1baa49ae66e943bf7f40781ccepoger@google.com return false; 708923c6cfd580ac9accb11b909fa2a033d69553aareed@google.com else if (opcode == EMPTY || opcode == TOMBSTONE) 715e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org return true; 728923c6cfd580ac9accb11b909fa2a033d69553aareed@google.com else if (type != other.type) 730770044da6d61dcbc8d9673fed8dd92460faa314reed@google.com return false; 749875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com else if (firstVN != other.firstVN) 759875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com return false; 760770044da6d61dcbc8d9673fed8dd92460faa314reed@google.com else if (secondVN != other.secondVN) 7700dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return false; 78e3cc2eb88fef9b2123c6ea2ed813ce53b6385926epoger@google.com else if (thirdVN != other.thirdVN) 79e3cc2eb88fef9b2123c6ea2ed813ce53b6385926epoger@google.com return false; 80e3cc2eb88fef9b2123c6ea2ed813ce53b6385926epoger@google.com else { 81b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com if (varargs.size() != other.varargs.size()) 82b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com return false; 83b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com 84b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com for (size_t i = 0; i < varargs.size(); ++i) 8546cce91f4859b9c229938d4d649870c0a43b1806reed@google.com if (varargs[i] != other.varargs[i]) 8646cce91f4859b9c229938d4d649870c0a43b1806reed@google.com return false; 8746cce91f4859b9c229938d4d649870c0a43b1806reed@google.com 8846cce91f4859b9c229938d4d649870c0a43b1806reed@google.com return true; 8900dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com } 9000dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com } 9100dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com 9200dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com bool operator!=(const Expression &other) const { 9300dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com if (opcode != other.opcode) 943914958a49ee089ddeb04acc16373aae8bc2eaf7bsalomon@google.com return true; 953914958a49ee089ddeb04acc16373aae8bc2eaf7bsalomon@google.com else if (opcode == EMPTY || opcode == TOMBSTONE) 963914958a49ee089ddeb04acc16373aae8bc2eaf7bsalomon@google.com return false; 973914958a49ee089ddeb04acc16373aae8bc2eaf7bsalomon@google.com else if (type != other.type) 98dd0ac281e920b01a63789893cc3e7422789658ddreed@android.com return true; 9900dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com else if (firstVN != other.firstVN) 100d4dfd10bb6f9bf3ac6e1ebc9bc3ae22c6d06321freed@google.com return true; 101dd0ac281e920b01a63789893cc3e7422789658ddreed@android.com else if (secondVN != other.secondVN) 10200dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return true; 103dd0ac281e920b01a63789893cc3e7422789658ddreed@android.com else if (thirdVN != other.thirdVN) 10400dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return true; 105dd0ac281e920b01a63789893cc3e7422789658ddreed@android.com else { 10600dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com if (varargs.size() != other.varargs.size()) 10700dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return true; 10800dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com 109d4dfd10bb6f9bf3ac6e1ebc9bc3ae22c6d06321freed@google.com for (size_t i = 0; i < varargs.size(); ++i) 11000dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com if (varargs[i] != other.varargs[i]) 111dd0ac281e920b01a63789893cc3e7422789658ddreed@android.com return true; 11200dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com 11300dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return false; 11400dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com } 11500dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com } 11600dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com }; 11700dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com 11800dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com class VISIBILITY_HIDDEN ValueTable { 119d4dfd10bb6f9bf3ac6e1ebc9bc3ae22c6d06321freed@google.com private: 12000dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com DenseMap<Value*, uint32_t> valueNumbering; 12100dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com DenseMap<Expression, uint32_t> expressionNumbering; 12200dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com 12300dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com uint32_t nextValueNumber; 124ce057fec926f8ec1d60ed4722d1e51a0086e7976epoger@google.com 125ce057fec926f8ec1d60ed4722d1e51a0086e7976epoger@google.com Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 126ce057fec926f8ec1d60ed4722d1e51a0086e7976epoger@google.com Expression::ExpressionOpcode getOpcode(CmpInst* C); 127ce057fec926f8ec1d60ed4722d1e51a0086e7976epoger@google.com Expression::ExpressionOpcode getOpcode(CastInst* C); 128ce057fec926f8ec1d60ed4722d1e51a0086e7976epoger@google.com Expression create_expression(BinaryOperator* BO); 129686abdfab0e4c45de1fd30774896c46e43a299acvandebo@chromium.org Expression create_expression(CmpInst* C); 1303cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org Expression create_expression(ShuffleVectorInst* V); 1313cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org Expression create_expression(ExtractElementInst* C); 1323cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org Expression create_expression(InsertElementInst* V); 1333cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org Expression create_expression(SelectInst* V); 1343cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org Expression create_expression(CastInst* C); 1353cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org Expression create_expression(GetElementPtrInst* G); 1363cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org public: 1373cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org ValueTable() { nextValueNumber = 1; } 1383cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org uint32_t lookup_or_add(Value* V); 1393cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org uint32_t lookup(Value* V) const; 140686abdfab0e4c45de1fd30774896c46e43a299acvandebo@chromium.org void add(Value* V, uint32_t num); 141686abdfab0e4c45de1fd30774896c46e43a299acvandebo@chromium.org void clear(); 1427361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com void erase(Value* v); 1437361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com unsigned size(); 1447361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com }; 1457361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com} 146f28dd8ab109663a6fe67fd4ee3d66248e0dac686epoger@google.com 1477361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.comnamespace llvm { 1487361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.comtemplate <> struct DenseMapKeyInfo<Expression> { 1497361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); } 1507361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); } 1519875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com 1527361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com static unsigned getHashValue(const Expression e) { 1537361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com unsigned hash = e.opcode; 154cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com 1557361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com hash = e.firstVN + hash * 37; 1567361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com hash = e.secondVN + hash * 37; 1577361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com hash = e.thirdVN + hash * 37; 1584c75f241cb75f202cfa51569ba8dc4749a28a9f7bsalomon@google.com 1599875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com hash = (unsigned)((uintptr_t)e.type >> 4) ^ 1609875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com (unsigned)((uintptr_t)e.type >> 9) + 1610dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org hash * 37; 1620dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org 1630dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end(); 1640dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org I != E; ++I) 1650dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org hash = *I + hash * 37; 1660dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org 16710afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org return hash; 16810afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org } 169971aca75572ed6e0c5e1cc959173dc58ca7b6b8dreed@google.com static bool isPod() { return true; } 17010afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org}; 171971aca75572ed6e0c5e1cc959173dc58ca7b6b8dreed@google.com} 17210afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org 17310afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org//===----------------------------------------------------------------------===// 17410afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org// ValueTable Internal Functions 175971aca75572ed6e0c5e1cc959173dc58ca7b6b8dreed@google.com//===----------------------------------------------------------------------===// 17610afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.orgExpression::ExpressionOpcode 17710afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org ValueTable::getOpcode(BinaryOperator* BO) { 178de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com switch(BO->getOpcode()) { 179de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case Instruction::Add: 180de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::ADD; 181de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case Instruction::Sub: 182de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::SUB; 183de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case Instruction::Mul: 184de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::MUL; 185de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case Instruction::UDiv: 186de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::UDIV; 187de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case Instruction::SDiv: 188de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::SDIV; 189de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case Instruction::FDiv: 190608ea6508ae2e9ea05ea863ba50fc27d44d2eae9commit-bot@chromium.org return Expression::FDIV; 19173a7ea3ae0d37ee28f90d6b38c49fda052638253edisonn@google.com case Instruction::URem: 192d9dfa18372119c8e1318125d2075fa80e0819094edisonn@google.com return Expression::UREM; 1935079d2c2a0dc0deacecccc6ef9d1c45c6c7982e4epoger@google.com case Instruction::SRem: 1945079d2c2a0dc0deacecccc6ef9d1c45c6c7982e4epoger@google.com return Expression::SREM; 1955079d2c2a0dc0deacecccc6ef9d1c45c6c7982e4epoger@google.com case Instruction::FRem: 1965079d2c2a0dc0deacecccc6ef9d1c45c6c7982e4epoger@google.com return Expression::FREM; 197de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case Instruction::Shl: 198de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::SHL; 1996f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com case Instruction::LShr: 2006f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::LSHR; 2015f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com case Instruction::AShr: 2025f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com return Expression::ASHR; 203e8ebeb1f8fde6525bbab988c6090a5d3ab19855bepoger@google.com case Instruction::And: 204659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::AND; 205659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com case Instruction::Or: 206659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::OR; 207659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com case Instruction::Xor: 208659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::XOR; 209659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com 210659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com // THIS SHOULD NEVER HAPPEN 211659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com default: 212e8ebeb1f8fde6525bbab988c6090a5d3ab19855bepoger@google.com assert(0 && "Binary operator with unknown opcode?"); 21357f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com return Expression::ADD; 21457f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com } 21557f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com} 216e8ebeb1f8fde6525bbab988c6090a5d3ab19855bepoger@google.com 217e8ebeb1f8fde6525bbab988c6090a5d3ab19855bepoger@google.comExpression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 218e8ebeb1f8fde6525bbab988c6090a5d3ab19855bepoger@google.com if (C->getOpcode() == Instruction::ICmp) { 219e8ebeb1f8fde6525bbab988c6090a5d3ab19855bepoger@google.com switch (C->getPredicate()) { 220de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case ICmpInst::ICMP_EQ: 22110afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org return Expression::ICMPEQ; 22210afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org case ICmpInst::ICMP_NE: 223659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::ICMPNE; 224659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com case ICmpInst::ICMP_UGT: 225659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::ICMPUGT; 226659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com case ICmpInst::ICMP_UGE: 227659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::ICMPUGE; 228659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com case ICmpInst::ICMP_ULT: 229659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::ICMPULT; 230659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com case ICmpInst::ICMP_ULE: 231659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::ICMPULE; 232659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com case ICmpInst::ICMP_SGT: 233659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::ICMPSGT; 234659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com case ICmpInst::ICMP_SGE: 235ccd7afb6fb2df9774e57fb4d7f62f9504cabf03escroggo@google.com return Expression::ICMPSGE; 236659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com case ICmpInst::ICMP_SLT: 237659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return Expression::ICMPSLT; 2386f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com case ICmpInst::ICMP_SLE: 2396f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::ICMPSLE; 2406f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com 2416f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com // THIS SHOULD NEVER HAPPEN 2426f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com default: 2436f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com assert(0 && "Comparison with unknown predicate?"); 2446f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::ICMPEQ; 2456f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com } 2466f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com } else { 2476f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com switch (C->getPredicate()) { 2486f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com case FCmpInst::FCMP_OEQ: 2496f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::FCMPOEQ; 2506f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com case FCmpInst::FCMP_OGT: 2516f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::FCMPOGT; 2526f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com case FCmpInst::FCMP_OGE: 2536f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::FCMPOGE; 2546f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com case FCmpInst::FCMP_OLT: 2556f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::FCMPOLT; 2566f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com case FCmpInst::FCMP_OLE: 2576f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::FCMPOLE; 2586f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com case FCmpInst::FCMP_ONE: 2596f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::FCMPONE; 2606f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com case FCmpInst::FCMP_ORD: 2616f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com return Expression::FCMPORD; 262de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case FCmpInst::FCMP_UNO: 263de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::FCMPUNO; 264de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case FCmpInst::FCMP_UEQ: 265de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::FCMPUEQ; 266de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case FCmpInst::FCMP_UGT: 2675f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return Expression::FCMPUGT; 2685f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com case FCmpInst::FCMP_UGE: 2695f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return Expression::FCMPUGE; 2705f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com case FCmpInst::FCMP_ULT: 2715f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return Expression::FCMPULT; 2725f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com case FCmpInst::FCMP_ULE: 2735f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return Expression::FCMPULE; 2745f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com case FCmpInst::FCMP_UNE: 2755f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return Expression::FCMPUNE; 2765efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com 2775efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com // THIS SHOULD NEVER HAPPEN 2785f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com default: 2795f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com assert(0 && "Comparison with unknown predicate?"); 2805f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return Expression::FCMPOEQ; 2815f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } 282de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com } 283de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com} 284de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 285de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.comExpression::ExpressionOpcode 286de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com ValueTable::getOpcode(CastInst* C) { 287de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com switch(C->getOpcode()) { 28879d3cb4ba74651ceaa862005a4244460e4662afdvandebo@chromium.org case Instruction::Trunc: 28910afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org return Expression::TRUNC; 2900dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org case Instruction::ZExt: 2915f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return Expression::ZEXT; 2925f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com case Instruction::SExt: 2935f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return Expression::SEXT; 294de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com case Instruction::FPToUI: 295de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::FPTOUI; 2960dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org case Instruction::FPToSI: 2970dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org return Expression::FPTOSI; 2980dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org case Instruction::UIToFP: 2990dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org return Expression::UITOFP; 3000dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org case Instruction::SIToFP: 3010dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org return Expression::SITOFP; 3020dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org case Instruction::FPTrunc: 303de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return Expression::FPTRUNC; 3049875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com case Instruction::FPExt: 3056f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com return Expression::FPEXT; 306310478e72c63e639373465216271b81f1e4a9136epoger@google.com case Instruction::PtrToInt: 3076f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com return Expression::PTRTOINT; 308310478e72c63e639373465216271b81f1e4a9136epoger@google.com case Instruction::IntToPtr: 309310478e72c63e639373465216271b81f1e4a9136epoger@google.com return Expression::INTTOPTR; 310310478e72c63e639373465216271b81f1e4a9136epoger@google.com case Instruction::BitCast: 311310478e72c63e639373465216271b81f1e4a9136epoger@google.com return Expression::BITCAST; 312310478e72c63e639373465216271b81f1e4a9136epoger@google.com 313310478e72c63e639373465216271b81f1e4a9136epoger@google.com // THIS SHOULD NEVER HAPPEN 314310478e72c63e639373465216271b81f1e4a9136epoger@google.com default: 315310478e72c63e639373465216271b81f1e4a9136epoger@google.com assert(0 && "Cast operator with unknown opcode?"); 316310478e72c63e639373465216271b81f1e4a9136epoger@google.com return Expression::BITCAST; 317310478e72c63e639373465216271b81f1e4a9136epoger@google.com } 318310478e72c63e639373465216271b81f1e4a9136epoger@google.com} 319310478e72c63e639373465216271b81f1e4a9136epoger@google.com 320310478e72c63e639373465216271b81f1e4a9136epoger@google.comExpression ValueTable::create_expression(BinaryOperator* BO) { 321310478e72c63e639373465216271b81f1e4a9136epoger@google.com Expression e; 32285195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org 323310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.firstVN = lookup_or_add(BO->getOperand(0)); 324310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.secondVN = lookup_or_add(BO->getOperand(1)); 325310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.thirdVN = 0; 326310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.type = BO->getType(); 3273a882dda0787e6957cfb37f6b5a68bcd31ce5cf7epoger@google.com e.opcode = getOpcode(BO); 3283a882dda0787e6957cfb37f6b5a68bcd31ce5cf7epoger@google.com 3293e62ebf93b43139202ce803245411467c7ed13ffcommit-bot@chromium.org return e; 3303e62ebf93b43139202ce803245411467c7ed13ffcommit-bot@chromium.org} 3313e62ebf93b43139202ce803245411467c7ed13ffcommit-bot@chromium.org 3323a882dda0787e6957cfb37f6b5a68bcd31ce5cf7epoger@google.comExpression ValueTable::create_expression(CmpInst* C) { 3333a882dda0787e6957cfb37f6b5a68bcd31ce5cf7epoger@google.com Expression e; 3343a882dda0787e6957cfb37f6b5a68bcd31ce5cf7epoger@google.com 3353a882dda0787e6957cfb37f6b5a68bcd31ce5cf7epoger@google.com e.firstVN = lookup_or_add(C->getOperand(0)); 3363a882dda0787e6957cfb37f6b5a68bcd31ce5cf7epoger@google.com e.secondVN = lookup_or_add(C->getOperand(1)); 3373a882dda0787e6957cfb37f6b5a68bcd31ce5cf7epoger@google.com e.thirdVN = 0; 3383a882dda0787e6957cfb37f6b5a68bcd31ce5cf7epoger@google.com e.type = C->getType(); 33985195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org e.opcode = getOpcode(C); 34085195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org 34185195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org return e; 34285195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org} 34385195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org 34485195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.orgExpression ValueTable::create_expression(CastInst* C) { 34585195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org Expression e; 34685195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org 34785195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org e.firstVN = lookup_or_add(C->getOperand(0)); 34885195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org e.secondVN = 0; 34985195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org e.thirdVN = 0; 35085195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org e.type = C->getType(); 35185195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org e.opcode = getOpcode(C); 35285195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org 35385195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org return e; 35485195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org} 35585195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org 35685195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.orgExpression ValueTable::create_expression(ShuffleVectorInst* S) { 35785195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org Expression e; 35885195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org 35985195486939b19a88b25b3ba0a1ad6640980fb5acommit-bot@chromium.org e.firstVN = lookup_or_add(S->getOperand(0)); 360310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.secondVN = lookup_or_add(S->getOperand(1)); 361310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.thirdVN = lookup_or_add(S->getOperand(2)); 362310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.type = S->getType(); 363310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.opcode = Expression::SHUFFLE; 364310478e72c63e639373465216271b81f1e4a9136epoger@google.com 365659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return e; 366659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com} 367310478e72c63e639373465216271b81f1e4a9136epoger@google.com 368310478e72c63e639373465216271b81f1e4a9136epoger@google.comExpression ValueTable::create_expression(ExtractElementInst* E) { 369310478e72c63e639373465216271b81f1e4a9136epoger@google.com Expression e; 370310478e72c63e639373465216271b81f1e4a9136epoger@google.com 371310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.firstVN = lookup_or_add(E->getOperand(0)); 372310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.secondVN = lookup_or_add(E->getOperand(1)); 373310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.thirdVN = 0; 374310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.type = E->getType(); 3756f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com e.opcode = Expression::EXTRACT; 37615655b241bfe1d77032e88115f119684722c10e0epoger@google.com 377eb06636133b6b5971964e5bce5ce5ca71d9ea960epoger@google.com return e; 378eb06636133b6b5971964e5bce5ce5ca71d9ea960epoger@google.com} 379310478e72c63e639373465216271b81f1e4a9136epoger@google.com 380659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.comExpression ValueTable::create_expression(InsertElementInst* I) { 381caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com Expression e; 382310478e72c63e639373465216271b81f1e4a9136epoger@google.com 383310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.firstVN = lookup_or_add(I->getOperand(0)); 384310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.secondVN = lookup_or_add(I->getOperand(1)); 385310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.thirdVN = lookup_or_add(I->getOperand(2)); 386310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.type = I->getType(); 38757f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com e.opcode = Expression::INSERT; 388310478e72c63e639373465216271b81f1e4a9136epoger@google.com 38915655b241bfe1d77032e88115f119684722c10e0epoger@google.com return e; 390310478e72c63e639373465216271b81f1e4a9136epoger@google.com} 391310478e72c63e639373465216271b81f1e4a9136epoger@google.com 392310478e72c63e639373465216271b81f1e4a9136epoger@google.comExpression ValueTable::create_expression(SelectInst* I) { 393310478e72c63e639373465216271b81f1e4a9136epoger@google.com Expression e; 394310478e72c63e639373465216271b81f1e4a9136epoger@google.com 395310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.firstVN = lookup_or_add(I->getCondition()); 396310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.secondVN = lookup_or_add(I->getTrueValue()); 397310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.thirdVN = lookup_or_add(I->getFalseValue()); 3985079d2c2a0dc0deacecccc6ef9d1c45c6c7982e4epoger@google.com e.type = I->getType(); 399310478e72c63e639373465216271b81f1e4a9136epoger@google.com e.opcode = Expression::SELECT; 400310478e72c63e639373465216271b81f1e4a9136epoger@google.com 401310478e72c63e639373465216271b81f1e4a9136epoger@google.com return e; 402310478e72c63e639373465216271b81f1e4a9136epoger@google.com} 40357f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com 40457f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.comExpression ValueTable::create_expression(GetElementPtrInst* G) { 405310478e72c63e639373465216271b81f1e4a9136epoger@google.com Expression e; 40651dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com 40751dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com e.firstVN = lookup_or_add(G->getPointerOperand()); 40851dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com e.secondVN = 0; 40951dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com e.thirdVN = 0; 41051dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com e.type = G->getType(); 41151dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com e.opcode = Expression::GEP; 4125079d2c2a0dc0deacecccc6ef9d1c45c6c7982e4epoger@google.com 41351dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 41451dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com I != E; ++I) 41551dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com e.varargs.push_back(lookup_or_add(*I)); 41651dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com 41751dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com return e; 41851dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com} 41951dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com 42051dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com//===----------------------------------------------------------------------===// 42151dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com// ValueTable External Functions 42251dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com//===----------------------------------------------------------------------===// 42351dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com 42451dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com/// lookup_or_add - Returns the value number for the specified value, assigning 42551dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com/// it a new number if it did not have one before. 42651dbabee67ea1285e1115e535d26944d4da99be5epoger@google.comuint32_t ValueTable::lookup_or_add(Value* V) { 42751dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 42851dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com if (VI != valueNumbering.end()) 42951dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com return VI->second; 43051dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com 43151dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com 43251dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 43351dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com Expression e = create_expression(BO); 43451dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com 435310478e72c63e639373465216271b81f1e4a9136epoger@google.com DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 43651dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com if (EI != expressionNumbering.end()) { 43751dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com valueNumbering.insert(std::make_pair(V, EI->second)); 438310478e72c63e639373465216271b81f1e4a9136epoger@google.com return EI->second; 43951dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com } else { 440310478e72c63e639373465216271b81f1e4a9136epoger@google.com expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 441310478e72c63e639373465216271b81f1e4a9136epoger@google.com valueNumbering.insert(std::make_pair(V, nextValueNumber)); 442310478e72c63e639373465216271b81f1e4a9136epoger@google.com 443310478e72c63e639373465216271b81f1e4a9136epoger@google.com return nextValueNumber++; 444310478e72c63e639373465216271b81f1e4a9136epoger@google.com } 445310478e72c63e639373465216271b81f1e4a9136epoger@google.com } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 446310478e72c63e639373465216271b81f1e4a9136epoger@google.com Expression e = create_expression(C); 447310478e72c63e639373465216271b81f1e4a9136epoger@google.com 448310478e72c63e639373465216271b81f1e4a9136epoger@google.com DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 449310478e72c63e639373465216271b81f1e4a9136epoger@google.com if (EI != expressionNumbering.end()) { 450310478e72c63e639373465216271b81f1e4a9136epoger@google.com valueNumbering.insert(std::make_pair(V, EI->second)); 45151dbabee67ea1285e1115e535d26944d4da99be5epoger@google.com return EI->second; 45257f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com } else { 453310478e72c63e639373465216271b81f1e4a9136epoger@google.com expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 45457f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com valueNumbering.insert(std::make_pair(V, nextValueNumber)); 45557f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com 4560dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org return nextValueNumber++; 457de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com } 4580dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 4590dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org Expression e = create_expression(U); 4600dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org 4610dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 4620dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org if (EI != expressionNumbering.end()) { 463de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com valueNumbering.insert(std::make_pair(V, EI->second)); 4649875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com return EI->second; 4655f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else { 4665f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 4675f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com valueNumbering.insert(std::make_pair(V, nextValueNumber)); 4685f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 4695f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return nextValueNumber++; 4705f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } 4715f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 4725f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com Expression e = create_expression(U); 4735f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 4745f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 4755f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com if (EI != expressionNumbering.end()) { 476de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com valueNumbering.insert(std::make_pair(V, EI->second)); 477de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return EI->second; 478de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com } else { 479de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 480dbfac8a72393eaf01670aeb3244de0e18d8faf98junov@google.com valueNumbering.insert(std::make_pair(V, nextValueNumber)); 48179d3cb4ba74651ceaa862005a4244460e4662afdvandebo@chromium.org 4829875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com return nextValueNumber++; 4835f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } 4845f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 4855f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com Expression e = create_expression(U); 4865f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 4875f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 4885f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com if (EI != expressionNumbering.end()) { 4895f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com valueNumbering.insert(std::make_pair(V, EI->second)); 4905f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return EI->second; 4915f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else { 4925f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 4935f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com valueNumbering.insert(std::make_pair(V, nextValueNumber)); 4945f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 4955f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return nextValueNumber++; 4965f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } 4975f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 4985f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com Expression e = create_expression(U); 4995f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 5005f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 5015f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com if (EI != expressionNumbering.end()) { 5025f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com valueNumbering.insert(std::make_pair(V, EI->second)); 5035f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return EI->second; 5045f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else { 5055f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 5065f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5075f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 5085f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return nextValueNumber++; 5095f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } 510908f5836626d792c5e33ad93f44c6a418a0cc8f5epoger@google.com } else if (CastInst* U = dyn_cast<CastInst>(V)) { 5115f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com Expression e = create_expression(U); 5125f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 5135f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 5145f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com if (EI != expressionNumbering.end()) { 515908f5836626d792c5e33ad93f44c6a418a0cc8f5epoger@google.com valueNumbering.insert(std::make_pair(V, EI->second)); 5165f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return EI->second; 5175f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else { 5185f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 5195f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5205f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 5215f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return nextValueNumber++; 522908f5836626d792c5e33ad93f44c6a418a0cc8f5epoger@google.com } 5235f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 5245f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com Expression e = create_expression(U); 5255f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 5265f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 527908f5836626d792c5e33ad93f44c6a418a0cc8f5epoger@google.com if (EI != expressionNumbering.end()) { 5285f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com valueNumbering.insert(std::make_pair(V, EI->second)); 5295f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return EI->second; 5305f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else { 5315f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 5325f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5335f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 5345f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return nextValueNumber++; 5355f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } 5365f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } else { 537908f5836626d792c5e33ad93f44c6a418a0cc8f5epoger@google.com valueNumbering.insert(std::make_pair(V, nextValueNumber)); 5385f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com return nextValueNumber++; 5395f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com } 5405f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com} 5415f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 5425f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com/// lookup - Returns the value number of the specified value. Fails if 54309fd4d216963c498c24ba355accce9337a5029a8scroggo@google.com/// the value has not yet been numbered. 5449875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.comuint32_t ValueTable::lookup(Value* V) const { 545aef73617d1bcede80145a13639668f958a3863d8reed@google.com DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 546de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com if (VI != valueNumbering.end()) 5479875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com return VI->second; 548de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com else 549de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com assert(0 && "Value not numbered?"); 550de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 551de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com return 0; 552aef73617d1bcede80145a13639668f958a3863d8reed@google.com} 553de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 554de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com/// clear - Remove all entries from the ValueTable 555de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.comvoid ValueTable::clear() { 556b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com valueNumbering.clear(); 5576f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com expressionNumbering.clear(); 558123ac1d4eab757052407064623643fdc59f85363bsalomon@google.com nextValueNumber = 1; 5596f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com} 5606f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com 561de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com//===----------------------------------------------------------------------===// 562de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com// ValueNumberedSet Class 563de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com//===----------------------------------------------------------------------===// 564de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.comnamespace { 565b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.comclass ValueNumberedSet { 566de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com private: 5671f2f338e23789f3eef168dcbd8171a28820ba6c1robertphillips@google.com SmallPtrSet<Value*, 8> contents; 568de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com BitVector numbers; 56966070a527c480d1cef5f7f7136f68d4f17b68f06junov@chromium.org public: 570de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com ValueNumberedSet() { numbers.resize(1); } 57166070a527c480d1cef5f7f7136f68d4f17b68f06junov@chromium.org ValueNumberedSet(const ValueNumberedSet& other) { 572de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com numbers = other.numbers; 573aef73617d1bcede80145a13639668f958a3863d8reed@google.com contents = other.contents; 574de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com } 575de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 576de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com typedef SmallPtrSet<Value*, 8>::iterator iterator; 577de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 5781f2f338e23789f3eef168dcbd8171a28820ba6c1robertphillips@google.com iterator begin() { return contents.begin(); } 579de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com iterator end() { return contents.end(); } 58066070a527c480d1cef5f7f7136f68d4f17b68f06junov@chromium.org 581de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com bool insert(Value* v) { return contents.insert(v); } 58266070a527c480d1cef5f7f7136f68d4f17b68f06junov@chromium.org void insert(iterator I, iterator E) { contents.insert(I, E); } 583de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com void erase(Value* v) { contents.erase(v); } 584aef73617d1bcede80145a13639668f958a3863d8reed@google.com unsigned count(Value* v) { return contents.count(v); } 585de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com size_t size() { return contents.size(); } 586de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 587de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com void set(unsigned i) { 588de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com if (i >= numbers.size()) 589de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com numbers.resize(i+1); 590de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 591de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com numbers.set(i); 592de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com } 5935f6a00775511b5675607c2bfdbb096c0a815025depoger@google.com 5946f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com void operator=(const ValueNumberedSet& other) { 59546cce91f4859b9c229938d4d649870c0a43b1806reed@google.com contents = other.contents; 596de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com numbers = other.numbers; 597de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com } 598c938c48bf426c322e2cb45b4bfaf8a2ee5a2a3c5junov@chromium.org 5995a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com void reset(unsigned i) { 6005a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com if (i < numbers.size()) 601de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com numbers.reset(i); 602de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com } 6035a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com 6045a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com bool test(unsigned i) { 6055a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com if (i >= numbers.size()) 6065a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com return false; 6075a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com 608041e2dbc0614e3341e1349fd0e962744a45b6194skia.committer@gmail.com return numbers.test(i); 6095a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com } 6105a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com 6115a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com void clear() { 6125a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com contents.clear(); 6135a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com numbers.clear(); 6145a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com } 6155a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com}; 6165a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com} 6175a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com 6185a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com//===----------------------------------------------------------------------===// 6195a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com// GVN Pass 6205a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com//===----------------------------------------------------------------------===// 6215a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com 6225a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.comnamespace { 6235a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com 6245a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com class VISIBILITY_HIDDEN GVN : public FunctionPass { 625041e2dbc0614e3341e1349fd0e962744a45b6194skia.committer@gmail.com bool runOnFunction(Function &F); 6265a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com public: 6275a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com static char ID; // Pass identification, replacement for typeid 6285a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com GVN() : FunctionPass((intptr_t)&ID) { } 6295a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com 6305a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com private: 631041e2dbc0614e3341e1349fd0e962744a45b6194skia.committer@gmail.com ValueTable VN; 632041e2dbc0614e3341e1349fd0e962744a45b6194skia.committer@gmail.com 6335a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com DenseMap<BasicBlock*, ValueNumberedSet> availableOut; 6345a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com 6355a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com // This transformation requires dominator postdominator info 6365a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com virtual void getAnalysisUsage(AnalysisUsage &AU) const { 6375a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com AU.setPreservesCFG(); 6385a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com AU.addRequired<DominatorTree>(); 6395a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com AU.addRequired<MemoryDependenceAnalysis>(); 6405a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com AU.addPreserved<MemoryDependenceAnalysis>(); 6415a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com } 6425a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com 6435a7d029fd6fcdf161b58c09887c6f745c37f1855robertphillips@google.com // Helper fuctions 644b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com // FIXME: eliminate or document these better 645de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com Value* find_leader(ValueNumberedSet& vals, uint32_t v) ; 6465e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org void val_insert(ValueNumberedSet& s, Value* v); 647de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com bool processLoad(LoadInst* L, 648de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com DenseMap<Value*, LoadInst*>& lastLoad, 6495e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org SmallVector<Instruction*, 4>& toErase); 6505e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org bool processInstruction(Instruction* I, 65173a7ea3ae0d37ee28f90d6b38c49fda052638253edisonn@google.com ValueNumberedSet& currAvail, 65273a7ea3ae0d37ee28f90d6b38c49fda052638253edisonn@google.com DenseMap<Value*, LoadInst*>& lastSeenLoad, 65373a7ea3ae0d37ee28f90d6b38c49fda052638253edisonn@google.com SmallVector<Instruction*, 4>& toErase); 65473a7ea3ae0d37ee28f90d6b38c49fda052638253edisonn@google.com bool processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase); 655de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, 6565e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org DenseMap<BasicBlock*, Value*> &Phis); 6575e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org void dump(DenseMap<BasicBlock*, Value*>& d); 6585e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org }; 659de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 6605e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org char GVN::ID = 0; 6615e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org 6625e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org} 6635e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org 6645e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org// createGVNPass - The public interface to this file... 6655e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.orgFunctionPass *llvm::createGVNPass() { return new GVN(); } 6665e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org 6675e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.orgstatic RegisterPass<GVN> X("gvn", 6685e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org "Global Value Numbering"); 6695e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org 6705e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.orgSTATISTIC(NumGVNInstr, "Number of instructions deleted"); 6715e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.orgSTATISTIC(NumGVNLoad, "Number of loads deleted"); 6725e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org 6735e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org/// find_leader - Given a set and a value number, return the first 6745e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org/// element of the set with that value number, or 0 if no such element 6755e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org/// is present 6765e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.orgValue* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) { 6775e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org if (!vals.test(v)) 6785e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org return 0; 6795e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org 6805e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end(); 6815e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org I != E; ++I) 6825e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org if (v == VN.lookup(*I)) 6835e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org return *I; 6845e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org 68573a7ea3ae0d37ee28f90d6b38c49fda052638253edisonn@google.com assert(0 && "No leader found, but present bit is set?"); 6865e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org return 0; 6875e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org} 6885e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org 6895e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org/// val_insert - Insert a value into a set only if there is not a value 6905e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org/// with the same value number already in the set 6915e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.orgvoid GVN::val_insert(ValueNumberedSet& s, Value* v) { 6925e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org uint32_t num = VN.lookup(v); 6935e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org if (!s.test(num)) 6945e00989a283111cef05bed8102e45c16651e43e4commit-bot@chromium.org s.insert(v); 6959875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com} 696de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 697de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.comvoid GVN::dump(DenseMap<BasicBlock*, Value*>& d) { 698de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com printf("{\n"); 699de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(), 700de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com E = d.end(); I != E; ++I) { 701de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com if (I->second == MemoryDependenceAnalysis::None) 702de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com printf("None\n"); 703de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com else 704de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com I->second->dump(); 705de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com } 706de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com printf("}\n"); 707de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com} 708de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 709de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 710de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com/// GetValueForBlock - Get the value to use within the specified basic block. 711de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com/// available values are in Phis. 712de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.comValue *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, 713de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com DenseMap<BasicBlock*, Value*> &Phis) { 714de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 715aef73617d1bcede80145a13639668f958a3863d8reed@google.com // If we have already computed this value, return the previously computed val. 716de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com Value *&V = Phis[BB]; 717de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com if (V) return V; 718de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com 719de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com if (std::distance(pred_begin(BB), pred_end(BB)) == 1) 7209875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com return V = GetValueForBlock(*pred_begin(BB), orig, Phis); 7219875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com 72237269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 72384a1802b072d76657261eada3018955283ab29d2epoger@google.com // now, then get values to fill in the incoming values for the PHI. 72484a1802b072d76657261eada3018955283ab29d2epoger@google.com PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", 72584a1802b072d76657261eada3018955283ab29d2epoger@google.com BB->begin()); 72684a1802b072d76657261eada3018955283ab29d2epoger@google.com PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); 72784a1802b072d76657261eada3018955283ab29d2epoger@google.com V = PN; 72884a1802b072d76657261eada3018955283ab29d2epoger@google.com 72984a1802b072d76657261eada3018955283ab29d2epoger@google.com bool all_same = true; 73084a1802b072d76657261eada3018955283ab29d2epoger@google.com Value* first = 0; 73184a1802b072d76657261eada3018955283ab29d2epoger@google.com 73284a1802b072d76657261eada3018955283ab29d2epoger@google.com // Fill in the incoming values for the block. 7335efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 7345efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com Value* val = GetValueForBlock(*PI, orig, Phis); 7355efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com if (first == 0) 73684a1802b072d76657261eada3018955283ab29d2epoger@google.com first = val; 73784a1802b072d76657261eada3018955283ab29d2epoger@google.com else if (all_same && first != val) 73884a1802b072d76657261eada3018955283ab29d2epoger@google.com all_same = false; 73984a1802b072d76657261eada3018955283ab29d2epoger@google.com 74084a1802b072d76657261eada3018955283ab29d2epoger@google.com PN->addIncoming(val, *PI); 7415efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com } 7425efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com 74384a1802b072d76657261eada3018955283ab29d2epoger@google.com if (all_same) { 74484a1802b072d76657261eada3018955283ab29d2epoger@google.com MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 74584a1802b072d76657261eada3018955283ab29d2epoger@google.com 74684a1802b072d76657261eada3018955283ab29d2epoger@google.com MD.removeInstruction(PN); 74784a1802b072d76657261eada3018955283ab29d2epoger@google.com PN->replaceAllUsesWith(first); 74884a1802b072d76657261eada3018955283ab29d2epoger@google.com PN->eraseFromParent(); 74984a1802b072d76657261eada3018955283ab29d2epoger@google.com 75084a1802b072d76657261eada3018955283ab29d2epoger@google.com return first; 75184a1802b072d76657261eada3018955283ab29d2epoger@google.com } 75284a1802b072d76657261eada3018955283ab29d2epoger@google.com 75384a1802b072d76657261eada3018955283ab29d2epoger@google.com return PN; 75484a1802b072d76657261eada3018955283ab29d2epoger@google.com} 75584a1802b072d76657261eada3018955283ab29d2epoger@google.com 75684a1802b072d76657261eada3018955283ab29d2epoger@google.combool GVN::processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase) { 75784a1802b072d76657261eada3018955283ab29d2epoger@google.com MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 75884a1802b072d76657261eada3018955283ab29d2epoger@google.com 75984a1802b072d76657261eada3018955283ab29d2epoger@google.com DenseMap<BasicBlock*, Value*> deps; 76084a1802b072d76657261eada3018955283ab29d2epoger@google.com bool ret = MD.getNonLocalDependency(L, deps); 76184a1802b072d76657261eada3018955283ab29d2epoger@google.com if (!ret) 76284a1802b072d76657261eada3018955283ab29d2epoger@google.com return false; 76384a1802b072d76657261eada3018955283ab29d2epoger@google.com 76484a1802b072d76657261eada3018955283ab29d2epoger@google.com DenseMap<BasicBlock*, Value*> repl; 76584a1802b072d76657261eada3018955283ab29d2epoger@google.com for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end(); 76684a1802b072d76657261eada3018955283ab29d2epoger@google.com I != E; ++I) 76784a1802b072d76657261eada3018955283ab29d2epoger@google.com if (I->second == MemoryDependenceAnalysis::None) { 76884a1802b072d76657261eada3018955283ab29d2epoger@google.com return false; 76984a1802b072d76657261eada3018955283ab29d2epoger@google.com } else if (I->second == MemoryDependenceAnalysis::NonLocal) { 77084a1802b072d76657261eada3018955283ab29d2epoger@google.com continue; 77184a1802b072d76657261eada3018955283ab29d2epoger@google.com }else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) { 77284a1802b072d76657261eada3018955283ab29d2epoger@google.com if (S->getPointerOperand() == L->getPointerOperand()) 7735efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com repl.insert(std::make_pair(I->first, S->getOperand(0))); 7745efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com else 7755efdd0cb9cdf4c2017dc6ad70b2503bf04234d9bepoger@google.com return false; 77684a1802b072d76657261eada3018955283ab29d2epoger@google.com } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) { 77784a1802b072d76657261eada3018955283ab29d2epoger@google.com if (LD->getPointerOperand() == L->getPointerOperand()) 77884a1802b072d76657261eada3018955283ab29d2epoger@google.com repl.insert(std::make_pair(I->first, LD)); 779908f5836626d792c5e33ad93f44c6a418a0cc8f5epoger@google.com else 7806f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com return false; 78137269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com } else { 78237269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com return false; 78337269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com } 7845f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com 78537269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com SmallPtrSet<BasicBlock*, 4> visited; 78637269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com Value* v = GetValueForBlock(L->getParent(), L, repl); 7876f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com 788659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com MD.removeInstruction(L); 789659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com L->replaceAllUsesWith(v); 79037269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com toErase.push_back(L); 79137269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com 792caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com return true; 793caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com} 794caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com 795caac3db48f74676889006b5520b766b572b5e9b2epoger@google.combool GVN::processLoad(LoadInst* L, 796caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com DenseMap<Value*, LoadInst*>& lastLoad, 79737269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com SmallVector<Instruction*, 4>& toErase) { 7986f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com if (L->isVolatile()) { 7996f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com lastLoad[L->getPointerOperand()] = L; 800659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com return false; 801659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com } 802caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com 8036f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com Value* pointer = L->getPointerOperand(); 804659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com LoadInst*& last = lastLoad[pointer]; 805659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com 80637269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com // ... to a pointer that has been loaded from before... 807ce057fec926f8ec1d60ed4722d1e51a0086e7976epoger@google.com MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 808ce057fec926f8ec1d60ed4722d1e51a0086e7976epoger@google.com Instruction* dep = MD.getDependency(L); 80937269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com if (dep == MemoryDependenceAnalysis::NonLocal && 81037269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com L->getParent() != &L->getParent()->getParent()->getEntryBlock()) 81137269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com processNonLocalLoad(L, toErase); 8126f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com bool deletedLoad = false; 8135f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com 8145f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com while (dep != MemoryDependenceAnalysis::None && 8155f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com dep != MemoryDependenceAnalysis::NonLocal && 8165f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com (isa<LoadInst>(dep) || isa<StoreInst>(dep))) { 8175f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com // ... that depends on a store ... 8185f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com if (StoreInst* S = dyn_cast<StoreInst>(dep)) { 8195f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com if (S->getPointerOperand() == pointer) { 8205f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com // Remove it! 8215f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com MD.removeInstruction(L); 8225f99545de67ee729b4b17f1aae56f8c9dcf460f9epoger@google.com 8236f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com L->replaceAllUsesWith(S->getOperand(0)); 824caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com toErase.push_back(L); 825caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com deletedLoad = true; 826caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com NumGVNLoad++; 827caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com } 828caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com 829caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com // Whether we removed it or not, we can't 830caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com // go any further 831caac3db48f74676889006b5520b766b572b5e9b2epoger@google.com break; 83284a1802b072d76657261eada3018955283ab29d2epoger@google.com } else if (!last) { 83384a1802b072d76657261eada3018955283ab29d2epoger@google.com // If we don't depend on a store, and we haven't 83484a1802b072d76657261eada3018955283ab29d2epoger@google.com // been loaded before, bail. 83537269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com break; 8366f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com } else if (dep == last) { 8376f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com // Remove it! 8386f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com MD.removeInstruction(L); 8396f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com 840de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com L->replaceAllUsesWith(last); 84184a1802b072d76657261eada3018955283ab29d2epoger@google.com toErase.push_back(L); 84284a1802b072d76657261eada3018955283ab29d2epoger@google.com deletedLoad = true; 84384a1802b072d76657261eada3018955283ab29d2epoger@google.com NumGVNLoad++; 84484a1802b072d76657261eada3018955283ab29d2epoger@google.com 84584a1802b072d76657261eada3018955283ab29d2epoger@google.com break; 8466f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com } else { 8476f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com dep = MD.getDependency(L, dep); 84884a1802b072d76657261eada3018955283ab29d2epoger@google.com } 849ee8a8e3931c1d3f39755ee8beaf0c7cb1ba91888epoger@google.com } 85037269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com 85137269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com if (!deletedLoad) 8526f7f14d061b045a58a888ee5450b4596797dc453epoger@google.com last = L; 85337269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com 85437269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com return deletedLoad; 85537269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com} 85637269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com 8576f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com/// buildsets_availout - When calculating availability, handle an instruction 85837269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com/// by inserting it into the appropriate sets 859ee8a8e3931c1d3f39755ee8beaf0c7cb1ba91888epoger@google.combool GVN::processInstruction(Instruction* I, 86037269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com ValueNumberedSet& currAvail, 8611ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com DenseMap<Value*, LoadInst*>& lastSeenLoad, 86276c913db20de7ae1baa49ae66e943bf7f40781ccepoger@google.com SmallVector<Instruction*, 4>& toErase) { 86337269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com if (LoadInst* L = dyn_cast<LoadInst>(I)) { 86437269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com return processLoad(L, lastSeenLoad, toErase); 865d4993ff3605102036f83d5834d9a022d780e5488epoger@google.com } 86676c913db20de7ae1baa49ae66e943bf7f40781ccepoger@google.com 86737269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com unsigned num = VN.lookup_or_add(I); 868d4993ff3605102036f83d5834d9a022d780e5488epoger@google.com 8691ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com if (currAvail.test(num)) { 8701ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com Value* repl = find_leader(currAvail, num); 87176c913db20de7ae1baa49ae66e943bf7f40781ccepoger@google.com 8721ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com I->replaceAllUsesWith(repl); 8731ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com toErase.push_back(I); 8741ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com return true; 8751ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com } else if (!I->isTerminator()) { 87637269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com currAvail.set(num); 8771ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com currAvail.insert(I); 878ee8a8e3931c1d3f39755ee8beaf0c7cb1ba91888epoger@google.com } 8791ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com 880ee8a8e3931c1d3f39755ee8beaf0c7cb1ba91888epoger@google.com return false; 8811ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com} 8821ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com 8831ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com// GVN::runOnFunction - This is the main transformation entry point for a 8841ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com// function. 8851ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com// 8861ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.combool GVN::runOnFunction(Function &F) { 8871ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com // Clean out global sets from any previous functions 8881ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com VN.clear(); 8891ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com availableOut.clear(); 8901ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com 8911ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com bool changed_function = false; 8921ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com 8931ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com DominatorTree &DT = getAnalysis<DominatorTree>(); 8941ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com 8951ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com SmallVector<Instruction*, 4> toErase; 8961ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com 8971ddfbc201a5445d2da17d2a087a1ec88cc980ffbepoger@google.com // Top-down walk of the dominator tree 898de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.com for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), 89937269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com E = df_end(DT.getRootNode()); DI != E; ++DI) { 900ee8a8e3931c1d3f39755ee8beaf0c7cb1ba91888epoger@google.com 90137269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com // Get the set to update for this block 90237269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com ValueNumberedSet& currAvail = availableOut[DI->getBlock()]; 90337269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com DenseMap<Value*, LoadInst*> lastSeenLoad; 90437269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com 90537269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com BasicBlock* BB = DI->getBlock(); 90676c913db20de7ae1baa49ae66e943bf7f40781ccepoger@google.com 9079ef89ce8b7eb270b37941553099654129f2e0a04epoger@google.com // A block inherits AVAIL_OUT from its dominator 908a243b22422c82def12282f2ea713121716e30621epoger@google.com if (DI->getIDom() != 0) 90937269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com currAvail = availableOut[DI->getIDom()->getBlock()]; 91037269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com 91137269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 91237269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com BI != BE; ) { 91337269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com changed_function |= processInstruction(BI, currAvail, lastSeenLoad, toErase); 9148fc3766c58ec879389c3c83c96a73e50ff59eb78vandebo@chromium.org 915e33e137623d56a9d61f00ef74c6ad2e998613062epoger@google.com NumGVNInstr += toErase.size(); 916e33e137623d56a9d61f00ef74c6ad2e998613062epoger@google.com 91737269607334b99bf814c7dc6b426745d9b7c7e3fepoger@google.com // Avoid iterator invalidation 9186f6568b27eae62fea23ab8192c6da02ab892bb5eepoger@google.com ++BI; 9198fc3766c58ec879389c3c83c96a73e50ff59eb78vandebo@chromium.org 9200dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 921659c8c06cdc6c825004515240f81a8dafb2b4b0fepoger@google.com E = toErase.end(); I != E; ++I) 922e33e137623d56a9d61f00ef74c6ad2e998613062epoger@google.com (*I)->eraseFromParent(); 923e33e137623d56a9d61f00ef74c6ad2e998613062epoger@google.com 924e33e137623d56a9d61f00ef74c6ad2e998613062epoger@google.com toErase.clear(); 925e33e137623d56a9d61f00ef74c6ad2e998613062epoger@google.com } 926e33e137623d56a9d61f00ef74c6ad2e998613062epoger@google.com } 9270dcbece326ce2fa1f9046aa69a21bb99de08714avandebo@chromium.org 928c824c83ec1402e68e827e8920278a86793a12c0cepoger@google.com return changed_function; 929c824c83ec1402e68e827e8920278a86793a12c0cepoger@google.com} 930c824c83ec1402e68e827e8920278a86793a12c0cepoger@google.com